Open problem, Geometry, Combinatorics and discrete mathematics, posed 1946

Erdős unit distance problem

OpenErdős

Determine the asymptotic order of magnitude of $u(n)$ , the maximum number of pairs of points separated by Euclidean distance $1$ among any set of $n$ points in the plane $\mathbb{R}^2$ .

Posed by, 1946Paul Erdős

Research frontier as of 2026

As of 2026, the exact asymptotic exponent of $u(n)$ in the Euclidean plane remains open, though the landscape shifted dramatically in May 2026. For eighty years, the best lower bound was Erdős's 1946 integer-grid bound $n^{1+c/\log\log n}$ , and Erdős conjectured that $u(n) = n^{1+o(1)}$ . In May 2026, an AI-discovered algebraic number field construction (verified in preprints by Alon et al. and refined by Sawin) disproved Erdős's conjecture, proving $u(n) = \Omega(n^{1.014})$ and narrowing the true growth rate to lie strictly between a power-saving polynomial above $n^1$ and the 1984 Spencer–Szemerédi–Trotter upper bound $O(n^{4/3})$ .

Best known results

The best general upper bound is $u(n) = O(n^{4/3})$ , proved by Spencer, Szemerédi, and Trotter (1984).
An explicit lower bound of $u(n) > n^{1.014}$ for arbitrarily large $n$ was established in 2026 (Sawin, preprint, building on the OpenAI counterexample verified by Alon et al.), disproving Erdős's $n^{1+o(1)}$ conjecture.

Tools and where they stop

Tool	Achieved	Where it stops
Incidence geometry and crossing number inequalities (Szemerédi–Trotter, Székely)	Proves the upper bound $u(n) = O(n^{4/3})$ by bounding incidences between $n$ points and $n$ unit circles	Topological and bipartite-graph crossing bounds cannot distinguish unit Euclidean circles from pseudocircles that genuinely achieve $\Theta(n^{4/3})$ incidences
Algebraic number fields and Golod–Shafarevich class field towers (Alon et al., Sawin)	Constructs point sets in $\mathbb{C} \cong \mathbb{R}^2$ from number fields of large degree with small discriminant and many split primes of norm $1$ , achieving $u(n) > n^{1.014}$	Sawin showed that known unconditional number-field constructions via this framework cannot push the exponent beyond roughly $1.2143$ , leaving a gap below $4/3$

Open questions

What is the true asymptotic exponent $\limsup_{n \to \infty} \frac{\log u(n)}{\log n}$ in the Euclidean plane?
Can the $O(n^{4/3})$ upper bound be improved to $O(n^{4/3 - c})$ for some $c > 0$ using algebraic rigidity of unit circles?

References

Paul Erdős (1946). On sets of distances of n points · DOI:10.1080/00029890.1946.11991674
Joel Spencer, Endre Szemerédi, William T. Trotter (1984). Unit distances in the Euclidean plane · DOI:10.1007/pl00000428
Noga Alon, Thomas F. Bloom, W. T. Gowers, Daniel Litt, Will Sawin, Arul Shankar, Jacob Tsimerman, Victor Wang, Melanie Matchett Wood (2026). Remarks on the disproof of the unit distance conjecture · arXiv:2605.20695v1 [preprint, not peer-reviewed]
Will Sawin (2026). An explicit lower bound for the unit distance problem · arXiv:2605.20579v1 [preprint, not peer-reviewed]