5
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ 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$? $\endgroup$ Sep 20, 2020 at 12:45
  • $\begingroup$ @DmitriPanov I allow for any configurations of points. $\endgroup$
    – Sascha
    Sep 20, 2020 at 13:16
  • $\begingroup$ 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}.$ $\endgroup$
    – Sascha
    Sep 20, 2020 at 13:37
  • $\begingroup$ Thanks! And just to double check, $[1,2]$ means the interval $[1,2]$ (not the union of $1$ and $2$) $\endgroup$ Sep 20, 2020 at 13:42
  • $\begingroup$ @DmitriPanov that's right. $\endgroup$
    – Sascha
    Sep 20, 2020 at 16:31

1 Answer 1

2
$\begingroup$

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.

Old answer

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.

$\endgroup$
2
  • $\begingroup$ 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... $\endgroup$
    – Sascha
    Sep 20, 2020 at 15:29
  • $\begingroup$ I'll need to think about this. This might be harder. I think this depends on whether positioning points in a lattice (for, example Eisensteins one) gives you the best possible score for one vertex. So some variant of the problem (if you fiddle with the intervals [1, 2] and [2, 3] might have a solution using isoperimetric inequality $\endgroup$ Sep 20, 2020 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.