Non-coplanar unit distances
Reports that LLMs have killed the Erdős unit distance problem turn out to be greatly exaggerated. There is still plenty not yet understood about the problem.
The problem asks, for \(n\) points in the Euclidean plane, how many pairs can be at unit distance from each other? When Paul Erdős posed the problem in 1946, he observed that the graph of unit distances cannot contain a subgraph of the form \(K_{2,3}\), a complete bipartite subgraph with two vertices on one side and three on the other. One way to see this is to draw unit circles through the two vertices on one side of a supposed \(K_{2,3}\) subgraph. These cross each other at most twice, and their two crossing points are the only points that can be vertices on the other side of the subgraph. Through reasoning later generalized as the Kővári–Sós–Turán theorem, Erdős observed that this forbidden subgraph implies an \(O(n^{3/2})\) upper bound on the number of unit distances. More generally, the Kővári–Sós–Turán theorem implies that when \(K_{a,b}\) is forbidden from an \(n\)-vertex graph, the number of edges in the graph is \(O(n^{2-1/\min(a,b)})\). Subsequent researchers used different reasoning to reduce Erdős’s upper bound to \(O(n^{4/3})\).
Erdős also found a set of points with a slightly superlinear number of unit distances, \(n^{1+\omega(1/\log\log n)}\), by scaling a square grid with \(n\) points in it by a factor of \(1/r\), where \(r\) is chosen somewhat smaller than \(\sqrt n\) (so that a unit distance fits comfortably into the scaled grid) but so that \(r\) has many prime factors congruent to \(1\) mod \(4\). This leads to the existence of many integer right triangles with side length \(r\) and many copies of the hypotenuses of these triangles in the grid. For instance the image below shows many unit-length diagonal segments in an \(8\times 8\) grid scaled by \(r=5\), based on a \(3\)–\(4\)–\(5\) right triangle; the axis-parallel unit-length segments are not shown. Recent combinations of LLM and human effort by Will Sawin have improved this lower bound to \(\Omega(n^{1.014})\), disproving Erdős’s conjecture that the upper bound should be \(n^{1+o(1)}\). But there is still a lot of room between the lower bound exponent of \(1.014\) and the upper bound exponent of \(4/3\).
What about higher dimensions? In three dimensions there is another gap between a lower bound exponent of \(4/3\) and an upper bound exponent of \(295/197\approx 1.4975\). But there it stops. Already in four dimensions one can obtain arbitrarily large sets of points with dense complete bipartite graphs of unit distances, for instance by placing \(n/2\) points each on two perpendicular circles of radii \(3/5\) and \(4/5\) (Pythagoras again!) in the \(xy\)- and \(zw\)-planes.
Or does it stop? One obvious feature of Erdős’s scaled grid example is that it contains many collinear points. It is not obvious why this should be helpful for creating many unit distances, because each point can only have two unit-distance neighbors on each line. The new improved examples for the unit distance problem take the form of projections of higher-dimensional lattices into the plane (with carefully chosen algebraic properties generalizing the existence of many integer right triangles) and these too have many collinear points. This naturally raises the question: when points in the plane have no lines through three or more points, how does this forbidden pattern affect the number of unit distances that these restricted point sets can have? It’s still nonlinear: one can project any hypercube into the plane so that all its edges have unit distances, producing for a suitable projection non-collinear point sets with \(\Omega(n\log n)\) unit distances. I don’t know of any examples with asymptotically larger numbers than the hypercube, but perhaps I’m missing some known constructions.
In \(d\)-dimensional space, the analogous restriction is that no \(d+1\) points lie on a hyperplane. The common neighbors of any two points \(p\) and \(q\) do all lie on a hyperplane (the hyperplane that perpendicularly bisects segment \(pq\)) so this restriction causes us to forbid the subgraph \(K_{2,d+1}\). (We can rephrase this idea as the statement that, for any system of unit spheres whose tangencies contain a biclique \(K_{a,b}\) with \(\min(a,b)\ge 2\), the centers of the spheres on each side of the biclique must be coplanar; this is analogous to a statement on bicliques of non-unit spheres with \(\min(a,b)\ge 3\) from my recent paper on sphere tangencies and unit distances, but much easier.) By the Kővári–Sós–Turán theorem, forbidding the subgraph \(K_{2,d+1}\) implies that, for a \(d\)-dimensional point set with no \(d+1\) points on a hyperplane, there can be at most \(O(n^{3/2})\) unit distances.
Can a matching \(\Omega(n^{3/2})\) lower bound be achieved, in high enough dimensions, or alternatively, is there some limiting exponent \(c<3/2\) (perhaps even \(c=1\)) so that point sets with no \(d+1\) points on a hyperplane have \(n^{c+o(1)}\) unit distances? I don’t know.