ERDŐS 90: UNIT DISTANCES

Playground Controls

Lattice Config
Vertices ($n$):0
Unit Edges ($e$):0
Optimal Target
Best Known ($e_{opt}$):0
Goal Progress:0%
Canvas Help:
  • Click empty space to add points. Right-click points to delete.
Exact Unit Dist (80px ± 0.6)
Approx Unit Dist (± 2.5)
Hover/Drag Radar (80px)

The Planar Unit Distance Problem (Erdős Problem 90)

Given $n$ points in the Euclidean plane, what is the maximum number of pairs $e$ that can be at distance exactly 1?

  • The Erdős Conjecture (1946): Paul Erdős conjectured that for any $\epsilon > 0$, the maximum number of unit distance pairs is bounded by $O(n^{1+o(1)})$ as $n \to \infty$. This bound is achieved in square grids.
  • The 2026 AI Breakthrough: An internal reasoning model at OpenAI disproved this 80-year-old conjecture. The model proved that there exist point sets with at least $n^{1+\delta}$ unit-distance pairs for a constant $\delta > 0$, showing that lattices constructed using algebraic number theory can produce denser unit distances than regular square grids.
  • Will Sawin's Refinement: Following the AI discovery, Will Sawin published a constructive proof on arXiv showing that the number of unit distances grows at least as fast as $n^{1.014...}$ for arbitrarily large $n$. Later optimizations pushed this lower bound certificate to $n^{1.0152}$.
  • Higher-Dimensional Lattices: The counterexample relies on taking lattices in high-dimensional number fields and projecting them onto the plane. Rotate the 3D Grid and 4D Hypercube sliders above to see how coordinate alignment in higher dimensions creates dense unit-distance collisions when projected to 2D.
  • The Chromatic Number of the Plane: This problem is closely linked to the Hadwiger-Nelson problem, which asks for the minimum number of colors needed to color the plane so that no two points at distance 1 have the same color. The Moser Spindle preset (7 vertices, 11 edges) is a unit-distance graph that cannot be colored with 3 colors. Try switching to Color Nodes mode and test it yourself—you will find it requires at least 4 colors!

Lean 4 Unit Distance Graph Formalization

Here is the formal statement of a unit-distance graph and the Hadwiger-Nelson chromatic problem in Lean 4:

-- Lean 4 Formalization of Unit Distance Graphs and Hadwiger-Nelson Problem
import Mathlib.Analysis.Normed.Group.Basic
import Mathlib.Combinatorics.SimpleGraph.Basic
import Mathlib.Combinatorics.SimpleGraph.Coloring

open Metric Set SimpleGraph

/-- 
  A unit distance graph in ℝ² has vertices as points in the plane, 
  and edges between vertices at distance exactly 1.
-/
def UnitDistanceGraph (V : Set (ℝ × ℝ)) : SimpleGraph V where
  Adj u v := dist u.val v.val = 1
  symm u v h := by
    show dist v.val u.val = 1
    rw [dist_comm]
    exact h
  loopless u := by
    show dist u.val u.val ≠ 1
    rw [dist_self]
    norm_num

/--
  The Hadwiger-Nelson Problem (Chromatic Number of the Plane):
  The minimum number of colors needed to color the plane ℝ² such that 
  no two points at distance exactly 1 share the same color is at least 5 
  (proven by Aubrey de Grey in 2018) and at most 7.
-/
def ChromaticNumberOfPlane (χ : ℕ) : Prop :=
  ∃ (f : (ℝ × ℝ) → Fin χ), ∀ (p q : ℝ × ℝ), dist p q = 1 → f p ≠ f q

-- Aubrey de Grey's Theorem (2018)
theorem ChromaticNumberPlane_ge_five :
  ∀ (χ : ℕ), ChromaticNumberOfPlane χ → χ ≥ 5 := sorry