Erdős Unit Distance Problem

The Erdős unit distance problem asks to determine the maximum number of occurrences of the same distance among points in the plane. It is equivalent to finding a maximally dense unit-distance graph on vertices.

Erdős (1946) proved a lower bound of , where is big-Omega notation, and he offered a $500 prize for a matching upper bound. The conjectured matching bound, in the form , where denotes a quantity tending to 0 in little-O notation, or more concretely for some absolute constant , was refuted by an OpenAI-generated proof (Alon et al. 2026, OpenAI 2026). The proof constructs point sets for infinitely many with at least unit-distance pairs for some fixed . Sawin (2026) subsequently made the bound explicit and proved that, for arbitrarily large , more than unit-distance pairs occur. The construction uses algebraic number fields, infinite class field towers, and the Golod-Shafarevich theorem, and gives an asymptotic counterexample to square grid optimality.

Finite pieces of the explicit construction are illustrated above. They are obtained by taking and points with , then joining pairs at unit distance (S. Yang, in Pegg 2026). The case has 625 vertices and 2800 edges, giving graph density 14/975 and edge count per vertex 112/25. Increasing reduces boundary effects in these finite pieces, but this box family still has only linearly many unit-distance pairs in the number of vertices (so the parameter in the illustration is not the asymptotic parameter in Sawin's proof). In Sawin's asymptotic construction, arbitrarily large comes from number fields of increasing degree, giving higher-dimensional lattices with many vectors whose projections have length 1.

For the finite box graph with , exact coordinates and NumberFieldDiscriminant[x] show that the points generate number fields whose discriminants are supported only at the primes 2 and 3. Applying the same check to the exact coordinates of Heule graphs and Parts graphs instead brings in the primes 3, 5, and 11 (E. Pegg, pers. comm., May 22, 2026).

However, the true order of remains unknown. The best upper bound currently known is , where is big-O notation (Szemerédi 2016). In particular, the OpenAI construction gives an infinite family of point sets beating the conjectured grid-type asymptotic bound, but does not give a matching upper bound or characterize extremal configurations.

Exact values of for were obtained by Schade (1993) together with the complete sets of densest graphs for . Agoston and Pálvőlgyi (2022) subsequently determined the exact value of , and Alexeev et al. (2025) found for as well as a complete set of densest graphs. All but one of these graphs (one of the 7 on 17 vertices whose unit-distance embedding does not reside within the Moser ring) were previously discovered by Engel et al. (2024).

For , 2, ..., is given by 0, 1, 3, 5, 7, 9, 12, 14, 18, 20, 23, 27, 30, 33, 37, 41, 43, 46, 50, 54, 57, ... (OEIS A186705). The corresponding numbers of nonisomorphic maximally dense unit-distance graphs are 1, 1, 1, 1, 1, 4, 1, 3, 1, 1, 2, 1, 1, 2, 1, 1, 7, 16, 3, 1, 5, ... (OEIS A385657; Alexeev et al. 2025).