Google DeepMind's AlphaProof Nexus solves nine open Erdős problems

Researchers at Google DeepMind reported that AlphaProof Nexus, a system combining a large language model with the Lean formal-proof checker, had autonomously resolved 9 of 353 open Erdős problems and proved 44 of 492 open conjectures from the Online Encyclopedia of Integer Sequences (OEIS). Two of the Erdős problems solved had been open for 56 years. The system also settled a 15-year-old question about Hilbert functions in algebraic geometry and improved a known bound in convex optimisation, and the researchers said it was being applied to ongoing research in combinatorics, graph theory and quantum optics.

The method addressed a standard weakness of LLM-generated mathematics — plausible-sounding but incorrect proofs — by requiring every proof step to pass Lean’s compiler before being accepted, with error messages fed back to the model for revision rather than trusting its reasoning unchecked. The language-model component was Gemini 3.1 Pro. Inference cost per solved problem ran to a few hundred dollars. The paper noted that a simpler baseline agent, using only the language model and compiler feedback without additional scaffolding, was able to reproduce all nine Erdős results, which the authors attributed to gains in the underlying language model and to the grounding effect of compiler feedback rather than to specialised search machinery.

Because 9 of 353 attempted problems is a low hit rate, and the OEIS conjectures proved are individually minor, the result illustrated formal verification’s chief evidentiary advantage over benchmark scores: even a small number of solved problems is checkable rather than merely reported, since Lean either accepts or rejects each purported proof by construction.