Solving a Conjecture of Erdős
Sets of points with the property that no two elements of the set are one unit distance apart are called unit-distance avoiding sets. If a point is in the unit-distance avoiding set, then the unit circle drawn around it does not intersect the set, but there is no restriction regarding the interior and the exterior of this circle.
When searching for unit-distance avoiding sets with high densities, the following construction naturally comes to mind: an open disc with a unit diameter is unit-distance avoiding, as all distances between its two points are less than 1. The most economical way to place such open discs in a unit-distance avoiding manner is to place them in a regular triangular lattice with a step size of 2. With this, the distance between any two points of different discs will strictly be greater than 1.
The density of the set constructed this way is approximately 0.2267. In 1967, Hallard Croft managed to improve this to about 0.2293. Croft did not drastically change the logic of the construction, but he realized it’s worth placing the discs a bit denser, even if it means that a small part has to be cut off from them to maintain the unit-distance avoiding property. The resulting set, which is the intersection of a disc and a regular hexagon with a carefully chosen side length, is referred to as Croft’s Tortoise (see Fig. 1).
Although Croft’s construction may seem somewhat arbitrary, and many have tried to find a better one since 1967, this has remained unsuccessful to this day.
How can we prove that a unit-distance avoiding set (which we’ll denote as $A$ from now on) cannot have a high density? A logical idea is the following: shift the set $A$ by a distance of 1 in some direction; the shifted set naturally has the same density as $A$. Let us denote the unit vector used for the shift as $x$, and the shifted set as $A+x$. Since $A$ does not contain two points at a unit distance from each other, the intersection of $A$ and $A+x$ is necessarily empty. From this, it immediately follows that the density of the set $A$ is at most $\frac{1}{2}$. Continuing with this idea, by choosing the position vectors of the vertices of a (arbitrarily placed) regular triangle with unit sides for the shifts, the three obtained shifted instances are pairwise disjoint, which gives an upper estimate of $\frac{1}{3}$ for the density of the set $A$.
Over the past 60 years, several papers have been written about density upper bounds achieved by extending this idea further, gradually refining the upper bound from 0.2857 to 0.2565.
In the meantime, another approach also proved to be fruitful, following the work of F. Vallentin and F. M. de Oliveira Filho. Recall that if we shift $A$ by a planar unit vector $x$, the resulting set $A + x$ is disjoint from $A$, so the density of the set $A \cap (A + x) $ is 0. A natural idea is to drop the unit length condition for the vector $x$. Thus, we can define a density as a function of $x$: this is the so-called autocorrelation function, with its formal definition being
$$ f(x) = \delta(A \cap (A + x)), $$ where $\delta$ denotes the density.
The autocorrelation function carries a lot of information about the set $A$. As the simplest example, note that $f(0) = \delta(A)$, while due to the unit-distance avoiding property, $f(x) = 0$ for all $ |x| = 1 $. However, this is just the tip of the iceberg, as with the help of the function, we can gain important estimates about the intersection structure when shifted by various vectors.
In 2018, analyzing the autocorrelation function allowed Ambrus and Matolcsi to prove the previously known strongest estimate 0.2544, but the 0.25 limit conjectured by Erdős still seemed distant.
The first breakthrough needed to prove the conjecture came when we managed to develop a common generalization of the above two earlier approaches. Unfortunately, we would need quite a few more definitions to be able to introduce this result in this blogpost. Focusing on the core idea, what we achieved is the following: for every point set on the plane we could write up a large linear program so that its solution was an upper bound for the density asked by Moser and Erdős.
Thus, we have reduced the problem to a search task: to prove Erdős’s conjecture, it was sufficient to find a set of points on the plane with certain properties. Unfortunately, finding the appropriate set of points with pen and paper was infeasible. Therefore, we attacked the problem using computer search. There were two properties of the problem aiding us in this quest. 1. monotonicity: adding points to the set never weakens the bound. 2. discreteness: for any configuration, there are only finitely many points such that adding them can improve the bound.
We have implemented a modified beam search. After several months of intensive experimentation, our high-performance computer cluster eventually managed to find a 23-point configuration suitable for proving the conjecture:
According to our result, published in the journal Mathematical Programming, the density of a unit-distance avoiding set on the plane cannot exceed 0.247. Since then, we have managed to improve this bound to 0.2415. Right now we are in the process of employing a transformer-based machine learning model to guide the computer search. Our goal is not just to find even better bounds for this problem, but more ambitiously, to attack related plane coloring problems such as the famous Hadwiger-Nelson problem.