guthkatz

The problem

In the same 1946 paper that posed the unit-distance problem, Paul Erdős asked the dual question: place n points in the plane. What is the minimum number of distinct pairwise distances they can determine? Call this number g(n).

The √n × √n integer grid is again the natural candidate. Its squared distances are exactly the integers expressible as a² + b². By Landau's 1908 theorem, the number of such integers up to N is asymptotic to N / √log N. So the grid gives g(n) ≤ O(n / √log n) — and Erdős conjectured this was tight.

The lower bound was where the trouble started. The trivial bound is g(n) = Ω(√n): with fewer distances than √n, the unit-distance graph at one of those distances would be too dense to embed in the plane. Closing the gap from √n up to n / √log n took 69 years.

The long climb

• 1952 — Moser: g(n) = Ω(n^2/3)
• 1984 — Chung: g(n) = Ω(n^5/7), via the Spencer–Szemerédi–Trotter incidence bound (which was their motivation in proving it)
• 1992 — Chung–Szemerédi–Trotter: n^4/5 / log n
• 1997 — Székely: g(n) = Ω(n^4/5) — the crossing-number proof of SST gives a slicker route to this bound
• 2001 — Solymosi–Tóth: g(n) = Ω(n^6/7−o(1))
• 2003 — Tardos: g(n) = Ω(n^{(4e−1)/(5e−1)−o(1)}) ≈ n^0.864
• 2004 — Katz–Tardos: g(n) = Ω(n^{(48−14e)/(55−16e)−o(1)}) ≈ n^0.8641
• 2015 — Guth–Katz: g(n) = Ω(n / log n)

The jump from n^0.864 to n / log n is enormous. Guth and Katz didn't grind out another exponent — they introduced a fundamentally new tool.

The polynomial method

Guth and Katz reduce the distinct-distances problem to an incidence problem about lines in ℝ³, and then attack that with algebraic geometry. The sketch:

1. Elekes–Sharir framework (2010): map each pair of points (p, q) ∈ P² to the rigid motion that takes p to q. Rigid motions of the plane form a 3-dimensional space ℝ × SO(2) ≈ ℝ³, and the rigid motions taking one point to another sweep out a line. Counting distinct distances reduces to counting incidences between special lines in ℝ³.
2. Polynomial ham sandwich: by Stone–Tukey, given a finite set of points in ℝ³, there's a polynomial of low degree whose zero set bisects them. This lets you build a polynomial of degree D whose zero set partitions the points into O(D³) cells, each holding ≤ n / D³ points.
3. The case split: a line in ℝ³ either lies in the polynomial's zero set, or crosses it transversally at most D times. Lines in the zero set are handled by classical algebraic-geometry bounds (Bezout, ruled surfaces). Lines crossing the zero set are handled cell-by-cell.
4. Balance: pick D so the two cases cancel, and the master bound falls out.

The argument's depth is its generality. The polynomial method, born in Dvir's 2008 proof of the finite-field Kakeya conjecture, exploded after Guth–Katz: it now resolves problems across additive combinatorics, geometric measure theory, and harmonic analysis.

The remaining gap

Erdős's conjectured bound is n / √log n. Guth–Katz proved n / log n. The ratio is √log n — sub-polynomial. For all practical purposes, the distinct-distances problem is solved; mathematicians still call the gap "the final √log n" and it's one of the more frustrating open problems in discrete geometry.

The grid example is conjecturally tight from above. The remaining open question — closing the √log n gap from below — would settle a problem first asked 80 years ago.

Compare and contrast

The unit-distance and distinct-distances problems share a 1946 source paper, a base example (the √n × √n grid), and an algebraic substrate (Gaussian integers). Their fates have diverged:

• Distinct distances was beaten by humans with algebraic geometry, in 2015. The grid was the right example all along; the proof was the hard part. ← you are here.
• Unit distances was disproven by an AI in 2026 — the grid was not the right example. The construction the AI found uses lattices in CM fields of growing degree. erdős →

Two problems, one paper, eighty years, opposite endings.

The dot pattern that produces the result

The √n × √n integer grid (the configuration shown in the grid tab) is the construction whose distinct-distance count matches the bound. Its pairwise squared distances are exactly the integers a² + b² with a, b ∈ {0, …, √n−1}; the number of distinct such integers, by Landau's 1908 theorem, is asymptotically 2n / √log(2n) — Erdős's conjectured floor for g(n).

Guth–Katz's 2015 lower bound of Ω(n / log n) says no n-point configuration can do better than that (i.e. cram fewer distinct distances) by more than a √log n factor. The grid is the optimum (modulo the gap); the proof is that no exotic configuration can beat it.

Toggle reveal all in the grid tab to overlay the dot pattern's full distance structure — every grid point becomes the centre of concentric rings at each distinct squared distance, and the moiré of those rings is the visual signature that produces Landau-many distinct distances.

What's in this site

• grid — interactive k×k grid. Hover a point: every other point gets coloured by its distance from the hovered one, so concentric "rings" of equal-distance points appear. Toggle reveal all to draw the rings themselves from every point — the dot-pattern structure that achieves Erdős's bound. Stats panel shows total distinct distances in the whole set, distinct distances from the hovered point, and ratios against the three reference quantities (trivial √n, Guth–Katz n/log n, Erdős conjecture n/√log n).
• growth — log-log chart of the historical lower bounds, from the trivial √n through the 1952–2004 climb, capped by Guth–Katz's 2015 n / log n. The Erdős conjecture is drawn as a dashed ceiling; the trivial upper n(n−1)/2 sits at the top.
• docs — this page.

sources

• Guth, L. and Katz, N. (2015). On the Erdős distinct distances problem in the plane. Annals of Mathematics 181, 155–190.
• Guth–Katz arxiv preprint (2010)
• Terry Tao — exposition of Guth–Katz on his blog
• erdosproblems.com #89 — the curated catalog entry
• Erdős, P. (1946). On sets of distances of n points. American Mathematical Monthly 53, 248–250 — the original.