# Packing in uniform domains

Given $$N$$ points $$X:=(x_i)_{i \in \{1,..,N\}}$$, we now define a score function $$S:X \rightarrow \mathbb{N}$$ that is $$S(X)= \sum_{i=1}^N S(x_i)$$ where the score of $$S(x_i)$$ is

$$S(x_i) = 2* \vert \{x_j; \vert x_i-x_j \vert \in [1,2]\} \vert+ \vert \{x_j; \vert x_i-x_j \vert \in [2,3]\} \vert$$ where $$\vert \bullet \vert$$ denotes the cardinality of the set. Moreover, we require that for all $$i\neq j$$ we have $$\vert x_i-x_j \vert \ge \frac{1}{2}.$$

Question: Is it true that any configuration of $$N$$ points with maximal possible score is in a domain of diameter $$c\sqrt{N}$$ for some fixed c?

• Do you assume that your configuration of $N$ points belongs to $\mathbb Z^2$, or you consider all possible configurations of points in $\mathbb R^2$? Sep 20, 2020 at 12:45
• @DmitriPanov I allow for any configurations of points. Sep 20, 2020 at 13:16
• My comment about the integer lattice was only intended to suggest that spacing of order 1 would in general lead to a configuration of size $\sqrt{N}.$ Sep 20, 2020 at 13:37
• Thanks! And just to double check, $[1,2]$ means the interval $[1,2]$ (not the union of $1$ and $2$) Sep 20, 2020 at 13:42
• @DmitriPanov that's right. Sep 20, 2020 at 16:31

What follows below is the new answer to the modified question, where we assume in addition $$|x_i-x_j|\ge 1$$ (probably one can ask $$|x_i-x_j|\ge 1-\varepsilon$$ for sufficiently small $$\varepsilon$$). I want to propose a positive solution of this problem modulo the following guess, which, I hope, is correct.

Guess. Consider the equilateral triangular lattice $$E$$ with distance $$1$$ between neighbouring points. Then there are exactly $$18$$ points on distance at most $$2$$ from a given one, and $$36$$ on distance at most $$3$$. So the score of each point is $$54=2*18+(36-18)$$. I guess, that for any set $$X$$ such that any two points are on distance at least $$1$$, in the punctured $$2$$-neighbourhood of any point $$x\in X$$ there are at most $$18$$ points of $$X$$. I guess that the same holds for points on distance at most $$3$$. If this is true then we have the following corollary: for any set $$X$$ satisfying $$|x_i-x_j|\ge 1$$ we have $$S(x_i)\le 54$$.

So from now on we assume that either the guess is correct, or we are working with a set $$X$$ such that each point of this set has score at most $$54$$.

I'll prove that under such condition the constant $$c$$ exists.

Proof. Note first of all that we can always construct a set $$X$$ with $$N$$ points, such that the score of $$X$$ is $$54N-10^{10}\sqrt{N}$$. Such a set can be given by intersecting $$E$$ with a disk of appropriate radius. (one can take a smaller constant than $$10^{10}$$, but it doesn't matter).

Assume by contradiction, that we constructed a set $$X$$ maximising the score and such that its diameter is more than $$10^{10^{10}}\sqrt{N}$$. Take the union of disks of radius $$3$$ around all points of $$X$$, and denote this set by $$U_3$$. It is easy to see that $$U_3$$ is connected. Indeed, if it is not, we can parallel translate its connected component by pushing one to another and increase this way the score of $$X$$. So, since the diameter of $$X$$ is at least $$10^{10^{10}}\sqrt{N}$$, the perimeter of the exterior boundary of $$U_3$$ is at least $$10^{10^{10}}\sqrt{N}$$. We will say that a point of $$X$$ contributes to the exterior boundary of $$U_3$$ if it is on distance $$3$$ from it. It is easy to see that the number of points of $$X$$ contributing to the exterior boundary is at least $$10^{(10^{10}-2)}\sqrt{N}$$ (because the length of a radius $$3$$ circle is $$<100$$). The final observation is that any point $$x$$ of $$X$$ that contributes to the boundary has score less than $$54$$. This is because the disk of radius $$3$$ around $$x$$ has a large sub-region, where points of $$X$$ can not lie (indeed, take a point $$y\in \partial U_3$$ on distance $$3$$ from $$x$$, then no point on distance less than $$3$$ from $$y$$ lies in $$X$$). Finally, taking into account the guess and the fact that the score of $$X$$ has to be at least $$54N-10^{10}\sqrt{N}$$, we get a contradiction.

Let's consider two variations of this question. In both cases the answer is yes. In the first case $$X$$ is any subset of $$\mathbb R^2$$ in the second it is a subset of $$\mathbb Z^2$$.
1 We assume first that $$X$$ is any subset of $$\mathbb R^2$$. In such case the set with maximal possible score has diameter at most $$6$$. Let me prove this. Let's first construct a set with score approximatively $$\frac{5}{3}N^2$$. To do this we put $$N/6$$ points in each vertice of the regular hexagon with side of length $$1$$.
Now, suppose we have a set with maximal score and suppose its diameter is more than $$6$$. We will construct a set with larger score which will give us a contradiction.
So, suppose $$X$$ has two points $$x_i, x_j$$ such that $$|x_i-x_j|>6$$. Let's take two disks of radius $$3$$ around both points. One of them contains at most $$N/2$$ points, which means $$S(x_i)$$ or $$S(x_j)$$ is at most $$N$$. Without loss of generality assume $$S(x_i)\le N$$. On the other hand, we know that $$S(X)\ge \frac{5 N^2}{3}$$. So, there is a point $$x_k$$ such that $$S(x_k)\ge\frac{5}{3}N$$. Move $$x_i$$ at the place of $$x_k$$, this will increase the score $$S(X)$$. Contradiction.
2 What follows is just a sketch of proof. We assume $$X\subset \mathbb Z^2$$. In such case each point $$x_i$$ contributes at most $$2*8+20=36$$ to the sum $$S(X)$$. Indeed, there are $$8$$ integer points on distance at most $$2$$ from a given one, and $$20$$ on distance in $$[2,3]$$. From this one can deduce the answer applying the isomperietric inequality to the set that is the union of $$2\times 2$$ squares with centres at points of $$X$$. I can give more details, if you want.
• interesting, thank you, indeed I was interested mostly in Case 1. Do you think one can include a penalization saying: All points, are at least a distance $1/2$ away from one another and then still get the $\sqrt{N}$ scaling? Cause now it seems there is nothing in my question that would make the volume grow... Sep 20, 2020 at 15:29