---
name: unit-distance-problem
type: reference
title: "The Erdős Unit Distance Problem"
description: "Deep dive into the problem: history (1946), Erdős conjecture, OpenAI's disproof via algebraic number theory, and the landscape of bounds."
tags: [unit-distance, erdos, combinatorial-geometry, lower-bound, upper-bound, algebraic-number-theory]
timestamp: 2026-07-20
---

# The Erdős Unit Distance Problem

## Historical Origin

In 1946, Paul Erdős posed what would become one of the most celebrated open problems in combinatorial geometry:

> **Problem:** Let $u(n)$ denote the maximum number of pairs of points at unit distance among any set of $n$ points in the Euclidean plane $\mathbb{R}^2$. What is the asymptotic behavior of $u(n)$?

The 2005 book *Research Problems in Discrete Geometry* by Brass, Moser, and Pach calls it "possibly the best known (and simplest to explain) problem in combinatorial geometry." Noga Alon, a leading combinatorialist at Princeton, described it as "one of Erdős's favorite problems." Erdős himself offered a monetary prize for its resolution.

## The Conjecture

Erdős conjectured that $u(n) = n^{1+o(1)}$ — that is, the number of unit-distance pairs grows essentially linearly, with the additional exponent $o(1)$ tending to zero as $n \to \infty$.

### Known Lower Bounds (Pre-OpenAI)

The classical constructions achieving near-linear growth:

| Construction | $u(n)$ | Growth Rate |
|---|---|---|
| Points on a line | $n-1$ | Linear |
| Square grid | $\sim 2n$ | Linear |
| Rescaled square grid | $n^{1 + C/\log\log n}$ | Slightly superlinear |

The rescaled square grid, from Erdős's original 1946 work, was long believed to be essentially optimal. The additional term $C/\log\log(n)$ tends to zero, so the construction achieves growth only slightly faster than linear.

### Known Upper Bounds

| Bound | Authors | Year |
|---|---|---|
| $O(n^{4/3})$ | Spencer, Szemerédi, Trotter | 1984 |
| Refined upper bounds | Székely, Katz-Silier, Pach-Raz-Solymosi | Various |

The upper bound $O(n^{4/3})$ has remained essentially unchanged since 1984, despite extensive research.

## OpenAI's Disproof (May 2026)

On May 20, 2026, OpenAI announced that an internal reasoning model had produced a proof that $u(n) \neq n^{1+o(1)}$. The proof constructs infinite families of point sets achieving:

$$u(n) = \Omega(n^{1+\delta})$$

for a fixed $\delta > 0$, disproving the Erdős conjecture.

### The Construction Method

The proof replaces the Gaussian integers (used in Erdős's classical construction) with more sophisticated algebraic number fields that possess richer symmetries, enabling many more unit-length differences.

The key ingredients:

1. **Algebraic number fields** — Extensions of $\mathbb{Q}$ with unique factorization properties
2. **Unramified class field towers** — Infinite towers of field extensions where primes split completely
3. **Golod-Shafarevich theory** — Proves that certain towers are infinite by showing the Frattini quotient has sufficient capacity
4. **Unit norm generation** — Constructing elements of absolute value 1 in number fields using conjugate prime ideal pairs

### The Initial Proof

The original AI proof was purely existential: it demonstrated the *existence* of point sets with $u(n) = \Omega(n^{1+\delta})$ for some $\delta > 0$, but did not provide an explicit value. The proof yielded $\delta \sim 10^{-38}$ — positive but astronomically small.

### Mathematician Reactions

> "This has been one of Erdős's favorite problems… The solution by the internal model of OpenAI is, in my opinion, an outstanding achievement."
> — **Noga Alon** (Princeton)

> "There is no doubt that the solution to the unit-distance problem is a milestone in AI mathematics: if a human had written the paper and submitted it to the Annals of Mathematics and I had been asked for a quick opinion, I would have recommended acceptance without any hesitation."
> — **Tim Gowers** (Fields Medalist)

> "The model's CoT is deeply interesting. It is noteworthy that a significant majority of the thoughts are trying to construct a counterexample to the widely believed upper bound, rather than trying to prove it."
> — **Arul Shankar** (Number Theorist)

## The Explicit Bound: Will Sawin

Following OpenAI's announcement, Princeton mathematics professor Will Sawin refined the construction to provide an explicit exponent:

$$\delta = 0.014$$

This establishes that $u(n) = \Omega(n^{1.014})$, a concrete polynomial improvement over the classical bounds. Sawin's result demonstrated that the unramified tower construction could be pushed to yield meaningful exponents, not just existential ones.

## The Gap to Human SOTA

The human state of the art stands at $\delta > 0.036$ (Elo 2700+), representing the best known bounds achievable through these algebraic constructions. The gap from $\delta = 0.0196$ (H16) to $\delta > 0.036$ requires approximately an 84% improvement in the exponent.

## The Mathematical Framework

### From Geometry to Algebra

The connection between a geometric question (unit distances in the plane) and algebraic number theory works through the following chain:

1. **Unit distances** in $\mathbb{R}^2$ correspond to differences $|z_i - z_j| = 1$ among complex numbers $z_i, z_j$
2. **Algebraic number fields** $K/\mathbb{Q}$ provide structured sets of complex numbers with controlled norms
3. **Unramified extensions** $K_j/K$ produce increasingly rich sets of elements
4. **Unit norm generation** (Lemma 2.2) extracts elements with $|u| = 1$ from ideal products
5. **Point configurations** built from these elements yield many unit-distance pairs

### The Role of the Golod-Shafarevich Inequality

The [[unit-distance-golod-shafarevich|Golod-Shafarevich inequality]] is the central mechanism that guarantees the existence of infinite unramified towers. It constrains the relationship between:

- $d$: the rank of the Frattini quotient (class rank of the base field)
- $r$: the relation rank (constraints from prime splitting)
- $t$: the number of split rational primes

The inequality $r + 2t < d^2/4$ must be satisfied for the tower to be infinite. This creates a capacity constraint that limits how many primes can be killed, which in turn limits the entropy of unit generation.

### The CM Field Advantage

[[unit-distance-cm-fields|CM fields]] provide a critical advantage: complex conjugation pairs conjugate prime ideals, enabling independent unit generation from each pair via Lemma 2.2. This multiplies the entropy by the number of conjugate pairs, which grows with the degree of the base field.

The breakthrough in [[unit-distance-h16-breakthrough|H16]] was recognizing that the 2-class rank grows *exponentially* with the degree of the base field ($d = 2^N - 1$), while the root discriminant penalty grows only *linearly* ($\log H \sim \frac{1}{2} \sum \log p_i$).

## Current State of Knowledge

| Bound | Value | Source |
|---|---|---|
| Upper bound | $O(n^{4/3})$ | Spencer-Szemerédi-Trotter (1984) |
| Classical lower bound | $n^{1 + C/\log\log n}$ | Erdős (1946) |
| OpenAI existential | $n^{1+\delta}$, $\delta > 0$ | OpenAI (May 2026) |
| Sawin explicit | $n^{1.014}$ | Will Sawin (2026) |
| **H16 proven** | **$n^{1.019603}$** | **This research (H16)** |
| Human SOTA | $n^{1.036+}$ | Unknown methods |

## Related Problems

The Erdős unit distance problem belongs to a family of combinatorial geometry questions:

- **Erdős distinct distances problem** — Minimum number of distinct distances among $n$ points (solved by Guth and Katz, 2015)
- **Unit distances in higher dimensions** — Analogous questions in $\mathbb{R}^d$
- **Incidence geometry** — Szemerédi-Trotter type bounds
- **Algebraic constructions** — Moser's conjecture and related problems

## References

- OpenAI, "An OpenAI model has disproved a central conjecture in discrete geometry" (May 20, 2026)
- P. Erdős, "On sets of distances of $n$ points" (1946)
- W. Sawin, "Improved lower bound for the unit distance problem" (2026)
- Brass, Moser, Pach, *Research Problems in Discrete Geometry* (2005)
- OpenAI, `unit-distance-proof.pdf`, `unit-distance-remarks.pdf`, `unit-distance-cot.pdf`