Skip to content

Two Erdős Problems on Points in the Plane and AI

Source: Computational Complexity Blog \ Author: Lance Fortnow and Bill Gasarch \ Date Published: May 24, 2026

TL;DR

Bill Gasarch (writing on the Computational Complexity blog he co-authors with Lance Fortnow) contrasts two classic Erdős problems from 1946 that took very different paths to resolution — one solved by decades of steady human effort, the other cracked by an OpenAI model this month. He uses the comparison to reflect on the nature of mathematical progress, the role of AI, and what mathematicians should learn from the moment.

The Two Problems

1. Erdős Distinct Distance Problem (solved by humans)

  • Definition: Minimum number of distinct distances determined by any set of n points in the plane.
  • Bounds (Erdős, 1946): Between Ω(n^{1/2}) and O(n / log^{1/2} n).
  • Progress: Decades of incremental improvements by mathematicians.
  • Final result (Guth & Katz, 2011): g(n) ≥ Ω(n / log n) — nearly closing the gap.
  • Key point: Solved without computer assistance, after steady human progress.

2. Erdős Unit Distance Problem (cracked by AI)

  • Definition: Maximum number of unit-distance pairs among n points.
  • Erdős conjecture (1946): f(n) = O(n^{1+ε}) for all ε.
  • Previous bounds: Lower bound of n^{1+Ω(1/log log n)} (grid construction); upper bound of O(n^{4/3}) (Spencer, Szemerédi, Trotter, 1984).
  • Status before 2026: Almost no progress in decades. The conjecture was widely believed true.
  • Breakthrough (May 20, 2026): An OpenAI general-purpose reasoning model produced a counterexample — an infinite family of point sets with more than n^{1+ε} unit distances for a fixed ε.
  • First verified by Mark Selke and Metaab Sawhney (OpenAI).
  • Streamlined and explained by Alon, Bloom, Gowers, Litt, Sawin, Shankar, Tsimermann, Wang, Wood.
  • Will Sawin sharpened ε to approximately 0.014.
  • Technique: uses more complicated number fields (degree goes to infinity) instead of Gaussian integers.

Gasarch's Analysis

On the nature of the result

  1. Well-known problem: Not some obscure corner of mathematics — Erdős problems are famous.
  2. Readable proof: The final human-verified proof is understandable, alleviating fears of unverifiable black-box mathematics.
  3. Hard combination: The AI combined algebraic number theory with discrete geometry — tools not standard in combinatorial geometry — in a way no human had thought to try. And it disproved a conjecture widely believed true.
  4. Counterexample vs. theorem: A counterexample is less impressive than proving a theorem (like Guth-Katz). Gasarch wonders if AI could do that.

On AI vs. Human Roles

  1. AI-generated vs. AI-assisted: Some (like Gary Marcus) argue this was AI-assisted; Gasarch calls it AI-generated, but notes it's a continuum.
  2. Humans as grad students: "In the future, we will all be grad students, verifying and cleaning up what AI outputs."
  3. Combining vs. creating: The AI was good at combining known concepts. "The distinction between combining known ideas and coming up with new ones is very thin."

On Impact and the Future

  1. Short-term good, long-term risk: Great for solving problems. Long-term risk is losing the ability or patience to do proofs ourselves.
  2. Two lessons for mathematicians:
  3. (a) Breadth: Know many fields so you can combine ideas like the AI did.
  4. (b) Depth: Know one field deeply so you can do something new that current AI could not.
  5. Outcome vs. understanding: Medicine values outcomes. "Mathematics also values understanding. Does reading a proof that AI did give the same understanding as coming up with it yourself?"
  6. Two futures:
    • ONE (Rare Event): A "perfect storm" — counterexample, known math, interesting. Might not recur soon.
    • TWO (New Normal): "Since AI makes it easy to get help, my fear is that eventually we will all be Bill Gasarch — scary."

Key Takeaways

  1. The Distinct Distance Problem (human-solved) and Unit Distance Problem (AI-solved) make for a natural before-and-after comparison — one showing steady incremental progress, the other a sudden paradigm shift from outside the field.
  2. Gasarch's core concern is not that AI will replace mathematicians, but that it will erode the patience and motivation to do deep reasoning ourselves.
  3. The advice to mathematicians — cultivate both breadth and depth — predates AI, but the arrival of a tool that can combine fields effortlessly makes breadth more urgent than ever.