An AI Just Solved a 1996 Erdős Problem—and the Simplest Agent Won

An AI Just Solved a 1996 Erdős Problem—and the Simplest Agent Won Source: https://arxiv.org/abs/2605.22763 Paper was published on May 21, 2026 This episode was AI-generated on May 22, 2026. The script was written by an AI language model and the host voices were synthesized by Eleven Labs. The producer is not affiliated with Anthropic or Eleven Labs. A Google DeepMind system autonomously cracked nine open Erdős problems—including one that sat unsolved for thirty years—for a few hundred dollars each, with proofs verified by the Lean compiler. The twist: the team's elaborate evolutionary search system was beaten on most problems by a twenty-line script that just iterates an LLM against a compiler. The implications for AI engineering go well beyond mathematics. Key Takeaways: - Why coupling an LLM to the Lean proof checker dissolves the trust problem in AI-generated mathematics—and where that guarantee actually ends - How a 'Ralph loop' of LLM plus compiler plus retry matched a sophisticated evolutionary system with AlphaProof, tournament Elo ranking, and shared caches - The actual proof idea behind Erdős problem 125, including how irrationality of log(4)/log(3) gets weaponized to crush sumset density to zero - How the agent surfaced a thirty-year-old ambiguity in Erdős's original problem statement just by being forced to commit to a formal reading - Where the verification guarantee leaks: LLM judges scoring proof sketches reward confident-sounding hallucinated citations, biasing the search upstream of the compiler - Why the selection bias in the problem set, the cost of failed runs, and the human work of formalization make the headline numbers less clean than they look 29:03 - The trust problem in AI-generated math: Why plausible-looking LLM proofs have been economically useless to working mathematicians, and how Lean's compiler is supposed to fix that. 03:52 - The Ralph loop and the basic agent: A walkthrough of Agent A—the embarrassingly simple LLM-plus-compiler-plus-retry setup that did most of the work. 07:44 - Inside Erdős 125: The metronome intuition behind the density-zero proof and how the agent decomposes subgoals and delegates to AlphaProof. 11:37 - The fancy system that mostly didn't win: Evolutionary search with Elo-ranked proof sketches, a shared cache, and AlphaProof calls—and why it only paid off on the hardest problems. 15:29 - The ambiguity-surfacing side effect: How formalizing Erdős 125 and 741 forced long-standing imprecisions in the informal statements into the open. 19:21 - A geometric proof that feels like a magic trick: Erdős 846 and the agent's translation of a collinearity problem into graph-theoretic Ramsey territory. 23:14 - Steelmanning the skeptics: Selection bias in the problem set, hidden costs of failed runs, the heavy lifting humans do in formalization, and the hallucinated-citation failure mode. 27:06 - What actually changed: How the bottleneck shifts from verifying proofs to verifying problem statements, and what the 'simple loops beat scaffolding' finding might mean beyond math. Recommended Reading: - AlphaEvolve: A coding agent for scientific and algorithmic discovery: The evolutionary search ancestor of the Agent C/D system discussed in the episode, providing context for the 'fancy scaffolding' that the basic Ralph loop ended up matching. (https://arxiv.org/abs/2506.13131) - Mathematical discoveries from program search with large language models (FunSearch): The original DeepMind work establishing LLM-driven search for new mathematical results, which the episode positions as the lineage that Agent D descends from. (https://doi.org/10.1038/s41586-023-06924-6) - Solving olympiad geometry without human demonstrations (AlphaGeometry): A useful contrast to the episode's framing of olympiad problems as 'the easier version' — shows what tightly-scaffolded, domain-specific provers achieved before frontier LLMs closed the gap. (https://doi.org/10.1038/s41586-023-06747-5) - The Lean Mathematical Library (Mathlib): The community formalization library whose maturity the episode credits as one of the four necessary ingredients for the paper's results. (https://arxiv.org/abs/1910.09336)