More precise bound for the maximin number of arrows pointing to a square when square grid is filled with arrows

Question

The problem is as follows:

Suppose we fill each cell of a $n\times n$ square with one of the four arrows $\uparrow$, $\downarrow$, $\gets$, $\to$, like the following

$\begin{array}{|c|c|c|} \hline \downarrow & \downarrow & \gets\\ \hline \to& \to& \uparrow\\ \hline \to& \uparrow& \uparrow\\ \hline \end{array}$

We define that entry $A$ (in $i$th column $j$th row) points to entry $B$ (in $k$th column $l$th row) if one of the four happens:

1. $A$ is filled with $\uparrow$ and $j> l$ and $i=k$
2. $A$ is filled with $\downarrow$ and $j< l$ and $i=k$
3. $A$ is filled with $\gets$ and $j= l$ and $i<k$
4. $A$ is filled with $\to$ and $j= l$ and $i>k$

(This is straightforward if you really fill them with arrows...)

For the example above, only the entry in first row, third column, points to the left upper corner. The right bottom corner entry points to the entry on the first row, third column and the entry on the second row, third column.

Let $r(n)$ be the maximum number such that there is a filling method such that every entry is pointed to by at least $r(n)$ other entries.

Now we have a bound $\frac{2}{3}n+O(1)\le r(n)\le \frac{5}{6}n+O(1)$

(update: now $ r(n)\le \frac{3}{4}n+O(1)$)

(update2: now $ r(n)\le (\sqrt{3}-1)n+O(1)$)

(update3: now $ r(n)\le n/\sqrt{2}+O(1)$)

The lower bound is obtained by the following construction:

We first split the grid into the central $n/3\times n/3$ square surrounded by four regions as drawn. The red region is filled with $\to$, the green region is filled with $\downarrow$, The blue region is filled with $\gets$, the purple region is filled with $\uparrow$. The central square can be filled with anything. One can prove that every entry is pointed to by $\frac{2}{3}n+O(1)$ other entries.

On the other hand, counting the total number of entries one entry can point to, there are at most $\frac{5}{6}n^3+O(n^2)$ pairs (entry 1, entry 2) such that entry 1 points to entry 2. So, in average, an entry is pointed to by at most $5/6\; n+O(1)$ other entries.

Now, the question is: can the lower bound $2/3$ be raised and $5/6$ the upper bound be made smaller? I believe $2/3$ can be raised a little bit (for example, $0.01$) since the central $n/3\times n/3$ is not filled. But can it be substantially increased?

Any improvement is welcome and appreciated, even minor improvement with $2/3$ is welcome.

Update: a friend of mine gave me an $3/4\; n+O(1)$ upper bound. He considered the square connected the midpoints, where there are $2n$ entries. The entries inside the square point to at most one entry on the square, and the entries outside the square point to at most two. Thus, the number of entry points to the other entries is at most $1/2n^2+2\times 1/2n^2+O(n)=3/2n^2+O(n)$, and since there are $3n$ entries, averagely, one of the entries has at most $3n/4+O(1)$ entries points to it.

Update 2: That friend suggested another way: choose these entries in green

The green line four corners are of length $(\sqrt{3}-1)n/2$ entries. Using the similar argument above we can get $(\sqrt{3}-1)n+O(1)$ upper bound.

Update 3: That friend, again, suggested a way: choose these entries in green, the lengths of the green lines in the four corners are $\frac{\sqrt{2}-1}{2}n$ (they are the diagonal of the square of side length $\frac{\sqrt{2}-1}{2}n$) and the central green square has diagonal length $(2-\sqrt{2})n$ These entries on the central square we give them a weight of $1/2$. So all the entries in the outside four triangles will point to weight two entries, the entries inside the central square will point to weight $1/2$ (one entry on the central square) and the rest will point to weight $1$ (two entries on the corner green lines, or two entries on the central square.) So the total weight of pointing will be $n^2+O(n)$. The total weight of green entries is $\sqrt{2} n+O(1)$, and by average, the number of entries pointed to a certain entry is at most $n/\sqrt{2}+O(1)$, so there must be one entry pointed by at most other $n/\sqrt{2}+O(1)$ entries.

Answer 1

The lower bound can be substantially improved to $(1/\sqrt{2}-o(1))n$.

The proof goes in three parts: first a continuous analogue, then an LP analogue, and at last, the original problem.

The continuous analogue

The continuous analogue of the original problem can be stated as follows:

Let $U,D,R,L$ be Borel functions on $[0,1]\times [0,1] \rightarrow [0,1]$ satisfying $U+D+R+L=1$ and for every $(x,y) \in [0,1]\times [0,1]$, the value $\underset{0}{\overset{y}{\int}}U(x,t)dt+\underset{y}{\overset{1}{\int}}D(x,t)dt+\underset{0}{\overset{x}{\int}}R(t,y)dt+\underset{x}{\overset{1}{\int}}L(t,y)dt$ is at least $1/\sqrt2$.

Here $U,D,R,L$ are "densities of the up, down, right and left arrows", the first condition says that the "densities" at every point should add up to $1$, and the second condition says that every point should have at least a "mass" of $1/\sqrt{2}$ pointing to it.

The solution is as follows: Let $U$ be the function shown below.

The numbers surrounding the square are coordinates, and the numbers inside the square are the values of the function $U$.

The value $0$ is taken whenever $y \geq \frac12$.

When $y < \frac12 $, the value $\frac{2+\sqrt{2}}{4}$ is taken in the two side triangles, and the value $\frac{2-\sqrt{2}}{4}$ is taken in the lower triangle, and the value $\frac{1}{2}$ is taken otherwise (i.e. crossing dotted lines does not change the value of $U$). The top vertex of the lower triangle has coordinates $(\frac{1}{2},\frac{\sqrt{2}-1}{2})$, making the function $U$ left-right symmetric.

The functions $D, L, R$ are defined by their respective rotations of $U$, i.e. $D(x,y)=U(x,1-y)$, $R(x,y)=U(y,x)$ and $L(x,y)=R(1-x,y)$. It is easy to see that $U+D+L+R=1$.

Let $U^*(x,y)=\underset{0}{\overset{y}{\int}}U(x,t)dt$, i.e. the "mass" of up arrows pointing to $(x,y)$. Define the functions $D^*, L^*$ and $R^*$ in similar manners. Then the original problem reduces to studying the minimum of $U^*+D^*+R^*+L^*$.

The function $U^*$ is piecewise linear, and so is $U^*+D^*+R^*+L^*$.

The function $U^*+D^*+R^*+L^*$ is plotted below:

The numbers at the vertices represents the value of the function at that point. It does not matter whether they are in the square or not.

As the function is piecewise linear in every region, the function is determined by the numbers at the vertices. So it has minimum value $\frac{\sqrt{2}}{2}$. Thus the continuous problem is solved.

The LP analogue

Let $U',D',R',L'$ be $N\times N$ arrays with indices from $1$ to $N$ whose elements are in $[0,1]$. Now the respective value needed to be studied for the cell $(p,q)$ is $\underset{t=1}{\overset{q-1}{\sum}}U_{p,t}'+\underset{t=q+1}{\overset{N}{\sum}}D'_{p,t}+\underset{t=1}{\overset{p-1}{\sum}}R'_{t,q}+\underset{t=p+1}{\overset{N}{\sum}}L'_{t,q}$. This is the linear programming analogue of the original problem as noted by RobPratt.

The continuous problem provides a way to (approximately) solve the LP problem: Let $U_{p,q}'$ be the average of $U$ in $[\frac{p-1}{N},\frac{p}{N}] \times [\frac{q-1}{N},\frac{q}{N}]$ and define $D', R'$ and $L'$ similarly. Under such an assignment, the value for the cell $(p,q)$ is at least $\frac{\sqrt{2}}{2}N-C$ where $C$ is a constant independent with $N,p$ and $q$.

The arrays should be written in the order where $p$ goes from left to right, and $q$ goes from down to up. Only in such order can the meanings of $U', D', R'$ and $L'$ be retained.

The original problem

This is just a slight paraphrase of my comment in RobPratt's answer:

"Actually LP solutions serve as lower bounds. If we have a LP solution for $N \times N$ whose value is $K$, we can generate random arrow fillings on a $MN \times MN$ that matches the LP value arbitrarily close for sufficiently large $M$.

Dissect the $MN \times MN$ square into $N^2$ $M \times M$ sub-squares, corresponding to cells of the $N \times N$ LP solution. In a sub-square, let the directions of the cells be i.i.d. random variables with P(the arrow in the cell points at direction $x$) ($x\in\{\uparrow, \downarrow, \leftarrow, \rightarrow\}$) at least the value of the direction $x$ in the LP solution. Then as $M \rightarrow \infty$, it's asymptotically almost surely that every cell in the $MN \times MN$ square is pointed by at least $M(K-\epsilon)$ arrows, for any fixed $\epsilon>0$."

Taking into consideration that $K=\frac{\sqrt{2}}{2}n-O(1)$, we have proved that for every $\epsilon>0$ and sufficiently large $n$, there exists genuine solutions where every cell is pointed by at least $(\frac{\sqrt{2}}{2}-\epsilon)n$ arrows. (The divisibility issues are immaterial for any positive $\epsilon$.)

Hence $(1/\sqrt{2}-o(1))n$.

Discussion

By using dithering techniques, it may be possible to get a solution directly from the continuous analogue, skipping over the LP analogue, that has every cell pointed by at least $\frac{\sqrt{2}}{2}n-c$ arrows for a fixed constant $c>0$. But I have no references about the mathematical properties of dithering, so I do not know how to work out a proof.

Answer 2

I used integer linear programming (in SAS) to compute the exact values for $n\in\{2,\dots,50\}$, and they match https://oeis.org/A248183. Let $C_{i,j,d} \subseteq [n] \times [n]$ be the set of cells that can point to cell $(i,j)$ via direction $d$. Let binary decision variable $x_{i,j,d}$ indicate whether the arrow in cell $(i,j)$ points in direction $d$, and let $z$ represent the smallest number of arrows pointing to a cell. The problem is to maximize $z$ subject to \begin{align} \sum_d x_{i,j,d} &= 1 &&\text{for all $(i,j)$} \tag1\\ z &\le \sum_{(u,v) \in C_{i,j,d}} x_{u,v,d} && \text{for all $(i,j)$} \tag2 \end{align} Constraint $(1)$ chooses exactly one arrow per cell. Constraint $(2)$ enforces the maximin objective.

Figure 1 shows an optimal solution for $n=50$, with $r(50)=34$. Maybe it will suggest a pattern for general $n$.

Restricting U to the bottom half and D to the top half does not change the optimal values for $n\le 50$. For example, see Figure 2:

Nor does further restricting L to the right half and R to the left half. For example, see Figure 3:

For even $n \le 50$, the optimal values still do not change if you further restrict each direction to appear $n^2/4$ times. For example, see Figure 4:

Forcing horizontal and vertical symmetry, and forcing triangle with side length $10$ ($>10$ loses optimality), as suggested by @Wolfgang, but not forcing $n^2/4$ arrows per direction. See Figure 5:

Forcing diagonal symmetry loses optimality.

I also tried forcing horizontal and vertical symmetry, $r(50)=34$, and minimizing the number of D (hence U). The minimum is at most $192$, as shown in Figure 6:

With horizontal and vertical symmetry and $r(64)=44$, the minimum number of D (hence U) is $328$, as shown in Figure 7:

I solved the LP relaxation for $n=50$ with no restrictions and got objective value $34+6/7$. The resulting optimal solution is not unique. Figure 8 shows a plot where the color is determined by a fractional value $\ge 1/2$ (gray if the largest fractional value is $< 1/2$):

Figure 9 shows a heat map of the fractional assignments of cell to direction:

Figure 10 shows a heat map of the number of arrows pointing to each cell for an optimal LP solution with no restrictions:

Figure 11 shows a heat map of the number of arrows pointing to each cell for an optimal ILP solution with no restrictions:

Figure 12 shows a solution for $n=50$ where each cell has the minimum number $34$ of arrows pointing to it:

Answer 3

The lower bound can be improved to $\frac{13n}{18}\approx .7222n$ by iterating your construction in the central $n/3\times n/3$ square, instead of filling it "with anything". In addition to the average $\frac{2n}3$ pointings coming to each square from "outside", we have rectangular regions, viz. $4$ like the brown one (area $\frac n3\times\frac{2n}9$) getting in average $\frac n9$ pointings from the brown region in the center, $4$ like the yellow ones (area $(\frac n3+\frac n9)\times\frac{2n}{27}$) getting in average $\frac n{27}$ pointings from the yellow region in the center, and so on. This increases the average by a geometric series summing to $4\cdot\frac{n}{72}$, which makes the minimum bound $\frac{2n}{3}+\frac{n}{18}=\frac{13n}{18}$.