The Unit Distance Problem: Erdős’s Lattices, AI-Aided Breakthrough, and Community-Optimized Solutions

Date: June 2026

Author: Michael T. M. Emmerich

For a finite set $P$ of points in the plane, let $U(P)$ denote the number of unordered pairs of points in $P$ that are exactly one unit apart. For each positive integer $n$ , let $u(n)$ be the largest possible value of $U(P)$ among all planar point sets $P$ of size $n$ .

The unit distance problem asks how fast this maximum count can grow as the size of the point set increases. Erdős conjectured in 1946 that the optimal growth rate is essentially the one achieved by his lattice construction: the maximum number of unit distances among $n$ points should be bounded above by $n^{1+C/\log\log n}$ , for some absolute constant $C$ .

The conjecture was natural because the best classical examples came from arithmetic lattices: square or rectangular grids, and variants built from many integer representations of one squared length. These examples produce many exact unit distances, but still fit the philosophy that the exponent should be $1$ in the limit.

It is important to keep the word “exact” in mind. The problem is not a packing problem. If we draw disks of radius $1/2$ around the points, then a unit-distance edge means that two disks are tangent, but other disks are allowed to overlap. What matters is the graph whose edges join pairs of points at distance exactly $1$ .

Why lattices looked convincing

The hexagonal packing is a familiar way to make many tangent half-unit disks. In the square $[0,10]^2$ , the clipped hexagonal arrangement below has $105$ centers and $274$ unit-distance pairs. It is geometrically efficient and visually persuasive, but it is not asymptotically decisive for the unit-distance problem.

Figure. A clipped hexagonal packing in $[0,10]^2$ . It has $105$ centers and $274$ unit-distance pairs.

A different lattice idea is to work on a scaled integer grid and to use several displacement vectors of the same Euclidean length. For example, in the grid $(i/\sqrt 5,j/\sqrt 5)$ , the integer displacements $(\pm1,\pm2)$ and $(\pm2,\pm1)$ all have length $1$ after scaling. The local picture therefore has several directions of red unit-distance edges. This is closer to the arithmetic spirit of the classical lower bounds: the more representations a squared length has, the more unit directions one can use.

Figure. Local views of a multidirectional lattice based on squared length $5$ . Points lie on $(i/\sqrt 5,j/\sqrt 5)$ , and red segments of unit length 1 come from the displacement vectors $(\pm1,\pm2)$ and $(\pm2,\pm1)$ .

These pictures explain why Erdős’s conjecture was plausible. Lattices give elegant constructions, and number theory improves them by finding lengths with many representations. The 2026 breakthrough shows that this lattice intuition was not the whole story.

What changed in 2026

In 2026, an OpenAI team announced a counterexample to Erdős’s unit-distance conjecture [OpenAI 2026]. A short human-verified exposition by N. Alon, T. F. Bloom, W. T. Gowers, D. Litt, W. Sawin, A. Shankar, J. Tsimerman, V. Wang, and M. Matchett Wood explained the structure of the argument [Alon et al. 2026]. The key point is not a new clever finite drawing in the plane. Rather, the construction imports ideas from algebraic number theory into combinatorial geometry.

Very roughly, the new construction uses algebraic number fields with unusually favorable arithmetic: large degree, controlled discriminant, and many primes of small norm. The role of the Golod-Shafarevich method is to certify the existence of sufficiently large towers of fields. Once such arithmetic data are available, they can be turned into large planar point sets with more unit distances than any $n^{1+o(1)}$ law permits.

The first OpenAI result was qualitative in the exponent: it disproved the conjecture by proving that some fixed $\varepsilon>0$ is possible. For a reader who wants a numerical statement, the next step was crucial.

Sawin’s explicit refinement

W. Sawin gave an explicit quantitative version of the new method [Sawin 2026]. His theorem proves that there are arbitrarily large $n$ -point sets in the plane with more than $n^{1.014}$ unit-distance pairs. This changed the story from “there exists some positive exponent gain” to a concrete lower bound certificate.

Sawin’s explicit criterion also introduced a finite optimization problem over integer values and subsets of prime numbers. In the notation used in the report [Emmerich 2026], one chooses a finite set $T$ of odd primes, a finite set $S_Q$ of rational primes, positive integer multiplicities $k(p)$ for $p\in S_Q$ , and a real parameter $R>1$ . The set $T$ determines a quadratic field

$\displaystyle Q=\mathbb Q\left(\sqrt{\prod_{q\in T} q}\right),$

and the primes in $S_Q$ must satisfy arithmetic side conditions in $Q$ . The Golod-Shafarevich condition appears as a budget constraint: certain weights associated with the selected prime numbers must sum up to a total overall budget. In the reported certificates this budget is exactly saturated.

For a fixed feasible certificate, the exponent gain is computed by an explicit objective of the form

$\displaystyle \delta(T,S_Q,k,R)=\frac{N(T,S_Q,k,R)}{D(T,S_Q,k,R)},$

where, with $e(p)=2$ for $p=2$ or $p\in T$ and $e(p)=1$ otherwise,

$\displaystyle \begin{aligned} N={}&\log(1-1/R)+\frac12\log(2\pi/e) +\sum_{p\in S_Q}\frac{1}{4e(p)}\log(k(p)+1)\\ &{}-\frac18\log\left(4\prod_{q\in T}q\right) -\frac12\log\log\sqrt{4\prod_{q\in T}q},\\ D={}&\log\left(2R\prod_{p\in S_Q}p^{k(p)/(2e(p))}+1\right). \end{aligned}$

Thus the mathematical certificate has become a nonlinear integer optimization problem with arithmetic feasibility constraints. Such problems are typically hard to solve: they require either compute-heavy exhaustive search, which easily becomes intractable due to combinatorial explosion, or heuristic algorithms whose behavior can be improved by tailoring them to the search space and constraints.

What the optimization report adds

In my arXiv report [Emmerich 2026], I developed such a tailored optimization heuristic and applied it to find better solutions for Sawin’s proposed nonlinear integer optimization problem. The report first implements a verification pipeline and validates it by reproducing Sawin’s published certificate. This is an important sanity check: before improving the numbers, the code must recover the known value and all number-theoretic constraints must pass the test for candidate solutions.

Within this framework, two optimization layers are then added. First, a deterministic greedy heuristic treats the Golod–Shafarevich side condition as a budgeted selection problem. Candidate primes are scored by their expected contribution to the numerator of $\delta$ relative to their budget cost. After selecting primes and multiplicities, the method scans the parameter $R$ . This already improved Sawin’s displayed value

$\displaystyle \delta=0.014114428678\ldots$

$\displaystyle \delta=0.015171805637\ldots .$

Second, the report uses a tailored integer evolution strategy, a variant of an evolutionary algorithm adapted to Sawin’s finite nonlinear certificate problem. The starting point is Rudolph’s integer evolution strategy, which is further extended by problem-specific enhancements of the search operators. A deterministic greedy construction is used for seeding; the variables are kept genuinely integer-valued, namely selected prime indices, multiplicities $k(p)$ , and the numerator of a rational representation of the continuous parameter $R$ ; mutation is $\ell_1$ -native and integer-local, following the spirit of Rudolph’s symmetric and maximum-entropy double-geometric integer mutation operator; integer recombination mixes information from parent certificates and improves the “last-mile” performance of the method; and repair operators restore the arithmetic side conditions and the Golod–Shafarevich budget after variation. In this way, recombination and repair are not generic add-ons but part of the number-theoretic constraint handling, while the overall computation remains lightweight enough to be replicated on standard hardware.

The tailored integer evolution strategy gives

$\displaystyle \delta=0.015262868817\ldots .$

The cautious consequence inside this original same- $T$ computational framework is therefore

$\displaystyle u(n)>n^{1.0152}$

for arbitrarily large $n$ .

Together with F. Cordella, the same lightweight optimization-verification pipeline was later extended to a larger prime range. The resulting Zenodo dataset [Emmerich and Cordella 2026] gives an extended- $T$ certificate with $\#T=67$ and supports the clean statement

$\displaystyle u(n)>n^{1.031}.$

This is a reproducible certificate produced with affordable hardware and compute effort, but it is not the best currently known certificate. The Emmerich–Cordella development was carried out independently of the MathOverflow optimization thread: we first searched through classical publication channels, preprint servers, and deposited artifacts for known results, and then extended the lightweight optimization-verification framework. In parallel, a very active MathOverflow discussion explored stronger certificate values and related formulations. The table below therefore classifies results by source and scope; it is not intended as a chronological timeline.

The MathOverflow and Erdős-problems community announced stronger certificate values, notably contributions by E. Naslund and Tseng. These relied on more computationally exhaustive or brute-force optimization methods using fast hardware and efficient computer languages. While some of these certificates were still proposed within Sawin-style frameworks, more recent improvements also consider modified or less strict constraint systems, sharpened estimates, or additional degrees of freedom beyond the original same- $T$ formulation.

Certificate / source	Source and scope	$\delta$	Clean consequence
Sawin	explicit published baseline and certificate criterion	$0.014114428678\ldots$	$u(n)>n^{1.014}$
Greedy optimization	same- $T$ deterministic heuristic in the report’s computationally lightweight framework	$0.015171805637\ldots$	$u(n)>n^{1.015}$
Tailored Integer Evolution Strategy	same- $T$ greedy-seeded integer search with $\ell_1$ -native mutation, recombination, and repair operators for number-theoretic constraint handling	$0.015262868817\ldots$	$u(n)>n^{1.0152}$
Emmerich–Cordella Zenodo dataset [Emmerich and Cordella 2026]	extended-prime-range certificate, $\#T=67$ , produced with the same lightweight optimization-verification pipeline; a reproducible extension of the framework, developed independently of the MathOverflow optimization thread and not presented as a record claim	$\delta>0.031$	$u(n)>n^{1.031}$
Tseng certificate package	independent pointwise proof/certificate package from the MathOverflow discussion; it uses Sawin’s construction as a black box but organizes the finite certificate through prime-ideal microselection, a fractional-knapsack model, and dyadic-circle covering rather than the report’s lightweight integer-ES formulation	$0.03158935$	pointwise lower bound in the $1.03158935$ exponent range
Naslund / MathOverflow developments	stronger public frontier reports from the MathOverflow discussion, based in part on less strict or modified constraint systems than Sawin’s original displayed certificate problem, including strengthened estimates and reoptimized finite data	$>0.035$ , with later reports beyond $0.036$	frontier reports have moved beyond $n^{1.036}$ , subject to the caveats of the corresponding formulation

Table. Classification of explicit unit-distance lower-bound certificates by framework and source. The first three rows are the certificate levels directly compared in the optimization report for Sawin’s original finite parameter formulation with the same ramified prime set $T$ . The Emmerich–Cordella row records an extended-prime-range certificate produced with the same computationally lightweight pipeline and developed independently of the MathOverflow optimization thread. The Tseng and Naslund / MathOverflow rows record independent or community-driven results that are numerically stronger, but they should not be read as direct outputs of the report’s original lightweight same- $T$ framework. In particular, some recent frontier discussions work with less strict or modified constraint systems than Sawin’s original displayed certificate problem, or with strengthened estimates inside the underlying proof, and therefore belong in the table as context rather than as like-for-like comparisons.

The dates are remarkable, but they should not be read as a single linear development. On 20 May 2026, OpenAI announced a proof that the classical lattice intuition behind Erdős’s conjecture was not the whole story: number-theoretic, non-classical-lattice constructions can yield lower bounds beyond $n^{1+o(1)}$ . On the same day, Sawin posted the explicit certificate framework and the first numerical exponent gain, $\delta=0.014\ldots$ . Between 20 May and 6 June, several strands of work proceeded in parallel. My subsequent work with F. Cordella followed classical publication channels, preprint servers, and artifact searches, and led to a lightweight reproducible extended- $T$ certificate deposited on Zenodo. At the same time, MathOverflow and Erdős-problems discussions independently explored stronger numerical certificates, more exhaustive search strategies, pointwise proof packages, and less strict or sharpened variants of the original constraint system.

References

P. Erdős, “On sets of distances of $n$ points,” American Mathematical Monthly, vol. 53, no. 5, pp. 248-250, 1946.
E. Szemerédi and W. T. Trotter, “Extremal problems in discrete geometry,” Combinatorica, vol. 3, pp. 381-392, 1983.
J. Spencer, E. Szemerédi, and W. T. Trotter, “Unit distances in the Euclidean plane,” in Graph Theory and Combinatorics, pp. 294-304, 1984.
OpenAI, “An OpenAI model has disproved a central conjecture in discrete geometry,” May 20, 2026. Available at https://openai.com/index/model-disproves-discrete-geometry-conjecture/.
N. Alon, T. F. Bloom, W. T. Gowers, D. Litt, W. Sawin, A. Shankar, J. Tsimerman, V. Wang, and M. Matchett Wood, “Remarks on the disproof of the unit distance conjecture,” arXiv:2605.20695, 2026. Available at https://arxiv.org/abs/2605.20695.
W. Sawin, “An explicit lower bound for the unit distance problem,” arXiv:2605.20579, 2026. Available at https://arxiv.org/abs/2605.20579.
M. T. M. Emmerich and F. Cordella, “Optimized Certificate for the Unit Distance Problem with Extended Prime Number Range,” dataset, Zenodo, June 6, 2026. doi: 10.5281/zenodo.20551478. Available at https://zenodo.org/records/20551478.
G. Rudolph, “An evolutionary algorithm for integer programming,” in Parallel Problem Solving from Nature – PPSN III, Lecture Notes in Computer Science, vol. 866, pp. 139-148, 1994. doi: 10.1007/3-540-58484-6_258.
L. Fejes Tóth, “Ueber die dichteste Kugellagerung,” Mathematische Zeitschrift, vol. 48, pp. 676-684, 1942. doi: 10.1007/BF01180035.
D. G. Mixon, “What is the unit distance exponent?,” MathOverflow question and discussion thread, question 511514, 2026. Available at https://mathoverflow.net/questions/511514/what-is-the-unit-distance-exponent.
E. Naslund, answer to “What is the unit distance exponent?,” MathOverflow question 511514, 2026. Available at https://mathoverflow.net/questions/511514/what-is-the-unit-distance-exponent.
Tseng, “Certified pointwise lower bound for the Erdős unit-distance problem: proof package,” software/proof artifact, 2026. Available at https://github.com/Tseng-math/erdos-unit-distance-pointwise-certificate and doi: 10.5281/zenodo.20357019.
M. T. M. Emmerich, “Optimizing Explicit Unit-Distance Lower-Bound Certificates,” arXiv:2606.03419, 2026. Available at https://arxiv.org/abs/2606.03419.

The Unit Distance Problem: Erdős’s Lattices, AI-Aided Breakthrough, and Community-Optimized Solutions

Share this:

Leave a comment Cancel reply