AI Is Solving Erdős Problems: Why Math's Legendary Puzzles Yield to Neural Networks

Neural networks have had their biggest mathematical successes on the problems of Paul Erdős, the iconoclastic Hungarian mathematician of the mid-20th century who left behind hundreds of unsolved problems. According to Quanta Magazine (3 August 2026), researchers are now studying in detail what makes Erdős problems so attractive to AI, in an effort to understand how neural networks will change the rest of mathematics.

Who Erdős was and why his problems are famous

Paul Erdős (1913–1996) was one of the most prolific mathematicians in history: more than 1500 papers co-authored with more than 500 colleagues, and thousands of open problems posed. Erdős lived a nomadic life, moving from university to university, and offered a cash prize for each solution, from $10 to $10 000 depending on difficulty. Many of the problems remained unsolved well into the 21st century.

Erdős problems share several characteristic traits:

• Concise statements: most problems are stated in 2–3 sentences
• Combinatorial nature: mainly number theory and graph theory
• A concrete, verifiable answer: a construction either exists or it does not
• "Elegant difficulty": a simple statement hides a deep proof

According to the mathematicians Quanta Magazine interviewed, it is exactly this combination that makes Erdős problems a good fit for modern AI.

Why do Erdős problems yield to neural networks?

The main reason is that the structure of Erdős problems maps well onto how formal proof systems work. Verifiers such as Lean and Coq let an AI propose a hypothesis and check each step for correctness one at a time. Without such a mechanism, neural networks can generate proofs that sound convincing but are mathematically wrong, a problem that has long limited the use of AI in science.

Combinatorial problems with a clear yes/no criterion are especially convenient: the model tries strategies, builds constructions and searches for counterexamples without the risk of accumulating errors in intermediate steps. In 2024, Google DeepMind's AlphaProof solved four of the six problems at the International Mathematical Olympiad (IMO 2024). Several of them were of the combinatorial type characteristic of the Erdős tradition.

What will this change in mathematics?

According to the researchers Quanta Magazine cites, Erdős problems have become a litmus test for mathematics as a whole. Once they understand why this particular class of problems yields to neural networks, scientists will be able to draw a map: where AI will help mathematicians in the coming years, and where human intuition will remain irreplaceable.

According to

Quanta Magazine's analysis, by studying Erdős problems, mathematicians are in effect looking for the answer to a more general question: which properties make a mathematical problem machine-solvable in principle.

An open question is whether the same approach works in less formalized areas: algebraic geometry, topology, and problems that require creating fundamentally new concepts. There, the researcher's intuition remains irreplaceable for now, and mathematicians stress this.

What this means

AI's success on Erdős problems signals a qualitative shift in mathematics: neural networks are moving from computational assistance to closing problems that stood open for decades. Working out where exactly the limit of AI's capabilities in science lies is one of the key research tasks for years to come.