Unit Distance Problem

Put $n$ dots on a sheet of paper. Measure the distance between each pair of dots, and count the pairs that are exactly 1 apart. The question is how large that count can be. Write $u (n)$ for the largest possible count.

Small cases show the idea. Three dots in an equilateral triangle give 3 pairs. Four dots, as two triangles that share a side, give 5 pairs. Seven dots, as a hexagon with its center, give 12 pairs. Exact answers are known only for small $n$ .

For many dots, start with a square grid with spacing 1. Each dot has 4 neighbors at distance 1: left, right, up and down. Each pair has two dots, so the count is about $2 n$ .

Now make the spacing smaller. With spacing $1 / 5$ , a dot that is 3 steps across and 4 steps up is exactly 1 away. This is the 3-4-5 triangle: ${(3 / 5)}^{2} + {(4 / 5)}^{2} = 1$ . Each dot now has 12 neighbors at distance 1, as the figure shows.

A grid with spacing

1 / 5

. The circle has radius 1 and passes through 12 grid points.

Other spacings give even more. Spacing $1 / \sqrt{65}$ gives 16 neighbors, and spacing $1 / \sqrt{1105}$ gives 32. Paul Erdős showed that the best grids give about $n^{1 + small}$ pairs, where the small part slowly shrinks to 0 as $n$ grows.

Erdős conjectured that nothing does much better than these grids. In this conjecture, the raised number on $n$ , called the exponent, gets closer and closer to 1 as $n$ grows. Mathematicians had also proved that the count is at most a fixed number times $n^{4 / 3}$ . So the true exponent lay somewhere between 1 and $4 / 3$ .

The exponent makes a large difference for large $n$ . Here $n^{4 / 3}$ means $n$ times the cube root of $n$ . For one million dots, that is 100 million pairs, which is 100 per dot. A grid with a well-chosen spacing gives about 26 per dot.

An OpenAI model disproved the conjecture. For infinitely many $n$ , it builds an arrangement with at least $n^{1 + δ}$ pairs, for a fixed number $δ$ , the Greek letter delta, above 0. Later work reached $δ = 0.043$ , so the exponent is at least 1.043 for those $n$ .

Here is the idea behind it. A complex number has the form $a + b i$ , where $i^{2} = - 1$ . It is a point on a flat map, with $a$ across and $b$ up. So each grid point is a complex number. Steps of length 1 then come from numbers such as $(3 + 4 i) / 5$ . The new construction uses much larger number systems, which have far more numbers of this kind.

A later OpenAI paper reports that the upper limit on the exponent is also below $4 / 3$ , by an unstated amount. The exact exponent is still unknown.