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

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
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.

• I have improved the wording at some places to make it clearer. But I still have a hard time to understand your upper bounds (though I guess they are correct). What do you mean by "the square connected the midpoints" and by "The green line four corners are of length $(\sqrt{3}-1)n/2$ entries"? Commented Jan 22, 2022 at 10:12
• @Wolfgang The square connect to the midpoints is the square that connect to four midpoints of four sides of the big square, in a total of $2n$ entries. The green corners of length $(\sqrt{3}-1)n$ entries means those green lines on those four corners are kind of diagonals of $(\sqrt{3}-1)n$ square... sorry for the confusion. Commented Jan 22, 2022 at 16:44

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.

• Thanks a lot! Since what we need is this kind of construction! Commented Jun 14, 2022 at 20:54

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:

• So... A248183 suggested $\sqrt{2}/2$ asymptotic... which is really close to the upper bound $\sqrt{3}-1$. This suggested some mixed pattern though Commented Jan 22, 2022 at 17:41
• Good news: That friend of mine suggested a $\sqrt 2/2$ upper bound, which, If your hypothesis (the exact number somewhat matches the sequence you gave me) is correct and we can construct using the pattern, this upper bound and lower bound matches. Commented Jan 22, 2022 at 22:29
• I'm sorry, but can I ask you to do me a favor... It seems that the construction has a central square boundary and there seem to be vague boundary on the four corners... Just like the location of the green entries in the proof of $n/\sqrt 2$. If you can give an asymptotic construction of $n/\sqrt 2$ based on your findings, I will really appreciate you for your work... Thank you so much for your work in advance! Commented Jan 23, 2022 at 1:57
• Is there a solution with $D_4$ or maybe even $D_8$ symmetry? Commented Jan 23, 2022 at 10:16
• @Wolfgang I named them Figure 1 through 11 just now. Commented Jan 28, 2022 at 22:40

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}$$.

• Sorry but this does not help... I have thought about this before, trying to fill in the central space. However, you could check the $2/3n$th entry on the first row, which is pointed by $2/3n$ (and no more) entries. This question seeks for maximin, not the average... Commented Jan 22, 2022 at 16:48
• Oh I see. I guess it is all the $O(1)$ which gave me the idea of combining "asymptotic" and "average". Where you talk about average, you are rather applying a pigeonhole principle. Commented Jan 22, 2022 at 17:22