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

Date: June 2026

Author: Michael T. M. Emmerich

This report is about the unit disc problem, a problem that was receiving recently renewed attention because AI tools [OpenAI2026] helped to disprove a long open conjecture on this problem. We will discuss the problem and the geometrical conjecture, and how the main idea of how it was disproved. Then we look at how this work is related to optimization. To this optimization line of research I also have made a small contribution by proposing and making available a heuristic certificate optimizer. Finally, we will have a look at the fast evolving progress driven by the mathematical community and online collaboration in this field after the OpenAI breakthrough.

But let us first look at the problem itself as well as at its characteristics:

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.

The problem is not a packing problem as one might suspect at first glance. 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. As we see in the pictures below the unit disc packing leads to a very regular and symmetric configuration of the unit distance problem, but it is by far not the optimum.

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 is the densest possible packing of non-overlapping discs [Tóth1942]. 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 classical lower bounds that were considered in the conjecture of Erdős conjecture: 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$ . The lower picture is a zoomed in version of the upper picture. 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)$ .

The pictures above show that lattices give elegant constructions and why it was plausible to believe the optimum solution to the unit distance problem should be a multi-directional lattice. The 2026 breakthroughs show, however, that this intuition was wrong and better solutions than such lattices are possible.

What changed in 2026

On May 20th, 2026, an OpenAI team announced a counterexample to Erdős’s unit-distance conjecture [OpenAI 2026] that was found with the aid of their software ChatGPT 5.5. A 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 construction imports ideas from algebraic number theory into combinatorial geometry to prove by counterexample that a consequence of Erdoes conjecture would lead to a contradiction.

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 the conjectured $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$ must be possible. For a reader who wants a numerical statement, the next step was crucial.

Sawin’s explicit refinement

W. Sawin, a mathematician at Princeton University, gave an explicit quantitative version of the new method and the first explicit lower bound in a preprint published on ArXiV on the same day (May 20th, 2026) than the OpenAI announcement [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 so-called 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 certificates that follow Sawin’s construction 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}$

Even we we are not experts in number theory and do not fully understand the origins of these equations, we can see that finding a mathematical certificate has become a nonlinear integer optimization (maximization) 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. Heuristic algorithms offer an alternative search method which does not guarantee finding optimum solutions but can sometimes establish new best candidates. As discussed below, the search performance of such heuristics can be improved by tailoring them to the search space and constraints.

Optimization of unit distant certificates

Our arXiv report and github-published code [Emmerich 2026] develops such a tailored optimization heuristic for improving Sawin’s explicit certificate. It was motivated by Sawin’s comment that the first explicit certificate was not yet optimized. Our goal was therefore 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 were added. First, a deterministic greedy heuristic treats the Golod–Shafarevich side condition as a budgeted selection problem to construct first feasible and relatively good candidate solutions. 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 slightly from

$\displaystyle \delta=0.014114428678\ldots$

$\displaystyle \delta=0.015171805637\ldots .$

Second, starting from random solution candidates and the ‘greedily constructed’ candidates the strategy evolves solution by means of a randomized search heuristic: a tailored integer evolution strategy. Integer evolution strategies are a variant of an evolutionary algorithms that were specifically designed for non-linear integer optimization [Rudolph95]. Rudolph’s integer evolution strategy uses a double Geometric distribution for mutation, since it aligns well in terms of symmetry and entropy with optimization over integer lattices. It also features recombination which can be used to exchange genetic information between individuals and it has in our more recent studies shown to improve ‘last mile’ performance – meaning fine tuning of integer values in near optimum regimes. As further problem-specific enhancements the deterministic greedy construction is used for seeding; all 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$ ; and repair operators restore the arithmetic side conditions and the Golod–Shafarevich budget after variation. Compared to exhaustive search over combined integer ranges, the overall computation remains lightweight enough to be replicated on standard hardware.

Keeping the T-range fixed the tailored integer evolution strategy provided

$\displaystyle \delta=0.015262868817\ldots .$

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

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

for arbitrarily large $n$ .

After release of the optimization and verification package on github and a first version of a technical report on ArXiV, subsequent work with F. Cordella, using the same lightweight optimization-verification pipeline extended to a larger prime range, resulted in a further significant improvement that was published as a Zenodo dataset [Emmerich and Cordella 2026]: We found an extended- $T$ certificate with $\#T=67$ that supports the clean statement

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

This is a reproducible certificate produced with affordable hardware and compute effort, but it is not the best currently known certificate and it is similar to the slightly better result by Tseng (published independently on Zenodo, Tseng26).

Results reported by the Community via MathOverflow

In parallel to our development, after the announcement of OpenAI, started a discussion on MathOverflow – an online platform where mathematicians discuss new results, possible solutions to open problems, or ideas. In this discussion Naslund [Naslund2026] proposed the up-to-now best found solutions and he reportedly found them by exhaustive search by means of speed-optimized optimization in the fast C programming language. In this community the certificate 1.035… seems to be – at the time of writing this – the most widely accepted one. Newer results hint at the possibility of relaxing the constraints proposed by Sawin to achieve even sharper lower bounds. It requires substantial knowledge in algebraic number theory to be able to judge the correctness of such new constraint systems and the recent challenge is thus not anymore in solving a numerical optimization problem.

The current shift towards more permissive constraint systems might make our specific integer optimization and verification pipeline outdated and in need of revision. Although it would still produce valid certificates within Sawin’s restrictive system, it is unlikely that these will provide the best certificates for the unit distance problem. Still, this story may show that tailored randomized search heuristics can have potential application in fields of rather pure mathematics.

The below summarized timeline is quite remarkable as it shows how fast developments in mathematics have become as a result of online collaboration via dedicated result-sharing and discussion platforms such as github, zenodo, and mathoverflow, fast preprint availability (such as ArXiV), and support by advanced AI tools:

20 May 2026: OpenAI and Sawin. 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.014114428678\ldots$ , giving the clean consequence $u(n)>n^{1.014}$ .
Computational optimization within Sawin’s original same- $T$ framework. Tseng provided a pointwise proof/certificate package in the $1.03158935$ exponent range. Our subsequently published Emmerich–Cordella Zenodo dataset gave an extended- $T$ certificate with $\#T=67$ and supports the statement $u(n)>n^{1.0315}$ and a reusable, independently (from Tseng) developed optimization and verification pipeline.
Parallel MathOverflow and Erdős-problems activity. Independently, the online community explored stronger numerical certificates and related formulations. Naslund and other MathOverflow developments reported frontier values. Naslund’s proposed bound was in the $1.035\ldots$ exponent range, equivalently a gain beyond $\delta>0.035$ , with later reports moving beyond $1.036$ . These stronger results relied on computationally exhaustive searches in extended T subspaces, pointwise certificate packages, sharpened estimates, or modified and sometimes less strict constraint systems.

In the mathematical sciences it is however essential that all important results undergo a thorough peer review process in order to become established results. At the time of writing, all these developments should therefore still be viewed as preliminary. The OpenAI announcement, the arXiv reports, Zenodo results, the MathOverflow discussions, and the deposited certificate packages have not yet passed through a full peer-review cycle. For a cautious statement about currently documented explicit lower-bound certificates beyond Erdős’s conjectured threshold, Sawin’s 2026 report is therefore a natural reference point: it gives a clear published preprint formulation of the explicit certificate criterion by a reputable expert in the field of combinatorial geometry and proves the clean bound $u(n)>n^{1.014}$ for arbitrarily large $n$ .

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