AI Cracks 80-Year-Old Erdős Unit Distance Problem

Erdős Unit Distance Problem

For n points placed in the Euclidean plane, let u(n) denote the maximum possible number of unordered pairs whose distance equals 1. Paul Erdős (1946) conjectured that the optimal construction is a scaled square‑grid derived from Gaussian integers, giving an asymptotic bound u(n)=C·n+o(n) for some constant C.

Previously known constructions

Collinear placement yields n‑1 unit‑distance pairs.

A square‑grid of side length √n produces roughly (√2)·n pairs (the exact expression shown in the original source).

Scaling the Gaussian‑integer lattice improves the constant to an unspecified C but no construction exceeded the square‑grid growth rate.

AI‑generated construction

A general‑purpose large language model produced a new family of point sets that surpass the square‑grid bound. The model’s reasoning shifted from Gaussian integers to algebraic number theory and employed:

Large algebraic number‑field extensions.

Infinite class‑field towers.

The Golod‑Shafarevich theorem.

These tools yield point configurations with many more unit‑distance pairs than any previously known construction.

Quantitative improvement

Will Sawin (Princeton) refined the construction and proved that the asymptotic constant can be taken as approximately 0.014, i.e., u(n) ≥ 0.014·n for infinitely many n.

Key steps of the proof

Start from the Gaussian‑integer lattice as a baseline construction.

Recognize that its symmetry does not achieve the optimal density of unit distances.

Introduce algebraic number fields whose rings of integers have larger unit groups.

Construct infinite class‑field towers to obtain extensions with many units of norm 1.

Apply the Golod‑Shafarevich inequality to guarantee the existence of such towers.

Map algebraic integers of norm 1 to points in the plane, preserving unit distances.

Count the resulting unit‑distance pairs, establishing the constant ≈ 0.014.

Reference

OpenAI announcement: https://openai.com/index/model-disproves-discrete-geometry-conjecture/