Erdős Problems AI: Why They Fall and Math Class Doesn't

Erdős problems AI can solve are a specific kind of problem, and understanding which kind tells you more about the state of machine reasoning than any benchmark score. Paul Erdős left behind roughly a thousand catalogued problems. By August 2026, Quanta Magazine reported that the erdosproblems.com database listed 565 as solved and 652 as open, with AI systems credited for a growing share of recent progress.

The pattern in which ones fall is not random. And the reason is the most useful thing a parent can understand about AI and mathematics right now.

Key Takeaways

• Erdős problems concentrate in number theory, combinatorics, and graph theory, the areas where large language models have proven most capable.
• The structural reason: these problems often reduce to searching a large but well-defined space of constructions, and a proposed construction can be checked.
• The May 2026 unit distance result was the landmark, disproving a 1946 conjecture by finding a better family of point configurations.
• Verification is the bottleneck. Thomas Bloom of Manchester warns about AI-generated papers running 100 to 200 pages that “no human has read.”
• What has not fallen: problems needing genuinely new definitions, long conceptual scaffolding, or judgment about which question is worth asking.

Why Erdős problems AI can attack are the ones falling first

Paul Erdős was a Hungarian mathematician who posed problems compulsively, often with small cash prizes attached, across a career that produced collaborations with more than 500 people. The problems share a distinctive shape: easy to state, hard to solve, and heavily concentrated in discrete mathematics.

That shape is what makes them tractable for current models, and there are three structural reasons.

The search space is large but well-defined. Many Erdős problems ask whether an object with certain properties exists, or how large a count can get. That means a candidate answer is a construction: a specific arrangement, a specific set of integers, a specific graph. A model can propose constructions and reason about whether they satisfy the constraints. The unit distance result is exactly this: OpenAI’s model produced an infinite family of point configurations beating the assumed bound.

The statements are precise. A problem stated as an inequality with clear quantifiers can be checked in a way that “explain why this phenomenon occurs” cannot. Precision creates a target.

The prerequisite knowledge is compact. A number theory or combinatorics problem often needs a page of definitions, not a graduate course. That means the relevant training data is dense and the reasoning chain does not have to carry a whole field’s machinery.

Quanta’s account tracks specific results: Problem 728 solved by GPT-5.2 Pro in January 2026, Problem 1102 solved by Wouter van Doorn in November 2025, and Problem 1196 resolved collaboratively with Terence Tao and Jared Duker Lichtman in May 2026. Multiple labs are involved; the article notes OpenAI’s internal models, Google DeepMind agent teams, and the startup Harmonic’s Aristotle prover.

Problem types AI cracks versus problem types it does not

This table is my synthesis of what has and has not fallen, based on the Quanta reporting and the OpenAI result. I have flagged where I am extrapolating rather than citing.

Problem type	Example	Why AI does well or poorly	Status
Existence of a construction	Unit distance: find configurations beating a bound	Candidate objects can be proposed and checked	Cracked (May 2026)
Bounded arithmetic statements	Divisibility questions like Erdős Problem 728	Compact prerequisites, checkable claim	Cracked (Jan 2026)
Combinatorial counting bounds	Sum-product growth questions	Search-friendly, precise statement	Partially cracked (2026)
Graph-theoretic extremal problems	Maximum edges under a constraint	Discrete, enumerable structures	Frequently cracked
Problems needing a new definition	Building a framework where none exists	Requires inventing the vocabulary, not searching within it	Not cracked
Problems spanning many fields with long scaffolding	Programs like Langlands-style connections	Reasoning chains too long and too conceptual	Not cracked
Problems requiring taste	Deciding which conjecture matters	No objective target to optimize	Not applicable to AI
Continuous, analytic problems	Many partial differential equation questions	Less enumerable; fewer discrete candidates	Mostly open (my read)

The second half of the table is the part parents should care about. Noga Alon of Princeton told Quanta something blunt about the first half: “Once AI started to solve them, there is no point anymore.” He also said, in the same piece, that “many and maybe most good mathematicians will use AI.” Both things are true at once.

The verification bottleneck nobody solved

Here is the problem the field is actually stuck on, and it is not capability.

Thomas Bloom, who maintains the Erdős problems database at the University of Manchester, described the situation to Quanta: “A big problem is AI is being used a lot by people who aren’t mathematicians… No human has read it.” He was referring to AI-generated papers running 100 to 200 pages submitted as solutions.

The mechanics of that bottleneck are worth spelling out for a kid:

1. A model produces a long proof. Length is cheap for a machine.
2. Checking a proof is roughly as hard as writing one, and it is slower for a human than for the machine that generated it.
3. Formal verification tools like Lean can check a proof mechanically, but translating an informal proof into Lean is itself substantial work.
4. So proofs accumulate faster than they can be validated.

Quanta notes that formal verification is being used but sparingly: Nat Sothanaphan used the Aristotle prover to certify one proof’s logical coherence, and Liam Price used iterative verification with fresh model instances. Neither is a general solution. Our piece on how mathematicians verify a 125-page AI proof goes through the methods in detail.

There is also a sociological wrinkle. Quanta reports that some previously “solved” Erdős problems had been forgotten and were rediscovered by AI as if new, and that one high-profile claim in December 2025 turned out to duplicate a result Erdős himself had published in 1977. Knowing the literature is a human skill that models are still bad at.

How to Teach Your Kid About What AI Can and Cannot Search

The concept here is search space: the set of possible answers you are looking through. It is the single most useful mental model for understanding where AI is strong.

Ages 5–8: The Guessing Ladder

Think of a number between 1 and 100 and let your child guess, telling them only “higher” or “lower.” They will find it in about seven guesses. Then play again with “any number I can think of” and no range. They will get frustrated fast.

Same game, different search space. That is the whole idea: a machine is powerful when the space of possible answers is defined, and lost when it is not.

Ages 9–12: Count the Possibilities

Take four different colored blocks and ask how many distinct orders they can be put in. Have your child list them until they find the pattern (24, which is 4 factorial). Then ask about five blocks (120) and six (720).

Now the punchline: a computer can check all 720 arrangements instantly. It cannot check all arrangements of 20 blocks, because that number is about 2.4 quintillion. Ask them what a human does instead, and the answer is “find a reason, not a list.” That is proof.

Ages 13+: State a Problem Two Ways

Give your teen a question in two forms. Form A: “Is there a set of five whole numbers under 100 where no two of them add up to a third?” Form B: “Why do numbers behave this way?”

Form A has a search space and a checkable answer, which is where AI excels. Form B needs someone to decide what “this way” even means, which is where it does not. Have them articulate the difference in their own words. Then tell them about the Erdős pattern: the problems falling are Form A.

The question to ask: “Could a computer check every possible answer to this? If not, what would you need instead?”

Why math class is not obsolete, specifically

I want to give the concrete version of this argument, not the reassuring one.

Someone has to pick the problem. The arXiv paper “From Solvers to Research,” posted in July 2026 with Terence Tao among its 19 authors, argues that mathematicians retain “aesthetic judgment about which problems merit investigation, verification of solutions and proofs, and directing overall research strategy.” The model does not know which of the 652 open Erdős problems matters.

Someone has to check it. The 50% run success rate on the unit distance proof is the number to remember. OpenAI’s own account says correct solutions came in about half of repeated runs. Half the time, a competent reader is looking at something wrong.

Someone has to refine it. The original AI proof gave no explicit value of δ. Princeton’s Will Sawin later showed δ = 0.014. That is human work done after the machine finished.

Someone has to understand it. Bloom’s own test for an AI proof is whether it teaches us something: “has this taught us something new about the problem? Do we understand discrete geometry better now?” His verdict on the unit distance proof was “a moderated yes.” Understanding is a human deliverable.

And the practical counterargument to “AI does math so why learn it”: every one of those four jobs requires knowing the math. For how this maps onto careers, see our look at whether AI solving math problems ends math careers.

What to actually do at home

Teach the search-space question

“Could a computer just check all the possibilities?” is a question a 10-year-old can ask and it generalizes to almost every AI capability question they will encounter.

Separate stating from solving

Erdős’s genius was largely in posing problems, and that skill is untouched by any of this. Encourage your kid to write down questions they cannot answer. Keep a list.

Value knowing the literature

One of the recurring failure modes in this story is claiming a result that already existed. Knowing what has already been done is a real skill, and it is the one models are worst at.

What not to do

Do not tell your child that AI cannot do real math, because it demonstrably did. And do not tell them it can do all of it, because 652 Erdős problems remain open and the ones falling share a specific structure. The accurate version is more interesting than either simplification.

What to Watch For Over the Next 3 Months

• Week 4: Check the count on erdosproblems.com. The ratio of solved to open is the cleanest public scoreboard for this trend.
• Month 2 red flags: Any claim of an AI-solved problem without a named human verifier. After the December 2025 episode where a “solution” duplicated Erdős’s own 1977 result, that is the first thing to look for.
• Month 3 self-check: Ask your child to name one kind of question a computer could not search for the answer to. If they can, the search-space model has landed.

Frequently Asked Questions

How many Erdős problems has AI solved?

Exact attribution is contested. Quanta reported roughly 565 of about a thousand catalogued problems solved and 652 open as of August 2026, with AI credited in a growing share of recent solutions. Different labs report different counts, and some claimed solutions turned out to duplicate existing literature.

Why are number theory and combinatorics problems falling first?

Three reasons: candidate answers are often specific constructions that can be proposed and checked, the statements are precise enough to give the model a target, and the prerequisite knowledge is compact rather than requiring a whole field’s machinery.

What kinds of math problems has AI not solved?

Problems that require inventing new definitions or frameworks, problems with very long conceptual scaffolding across multiple fields, and anything requiring judgment about which question is worth asking. Continuous and analytic problems appear less tractable than discrete ones, though that is my read rather than a documented finding.

Is the verification problem being solved?

Not generally. Formal proof assistants like Lean can check proofs mechanically, but translating an informal proof into Lean is substantial work. Some individual proofs have been certified with tools like Aristotle, but Bloom’s concern about 100 to 200 page papers that “no human has read” stands.

Should my child still take advanced math?

The four jobs that remain human, choosing problems, verifying results, refining them, and understanding them, all require knowing the math. A student who cannot evaluate a proof cannot use an AI that produces proofs correctly about half the time.

---

About the author

Ricky Flores is the founder of HiWave Makers and an electrical engineer with 15+ years of experience building consumer technology at Apple, Samsung, and Texas Instruments. He writes about how kids learn to build, think, and create in a tech-saturated world. Read more at hiwavemakers.com.

---

Sources

1. Kakaes, K. (2026, August 3). “Why the legendary Erdős problems are falling to AI.” Quanta Magazine. https://www.quantamagazine.org/why-the-legendary-erdos-problems-are-falling-to-ai-20260803/
2. OpenAI. (2026, May 20). “An OpenAI model has disproved a central conjecture in discrete geometry.” https://openai.com/index/model-disproves-discrete-geometry-conjecture/
3. Bloom, T. “Erdős Problems.” University of Manchester. https://www.erdosproblems.com/
4. Jiang, E., Liang, X., et al. (with Tao, T.). (2026, July). “From Solvers to Research: Large Language Model-Driven Formal Mathematics at the Research Frontier.” arXiv:2607.07779. https://arxiv.org/pdf/2607.07779
5. Hulick, K. (2026, June 8). “AI guardrails and the Erdős math problem.” Science News. https://www.sciencenews.org/article/ai-guardrails-erdos-math-problem
6. Tao, T. (2025, January). “Machine-Assisted Proof.” Notices of the American Mathematical Society, 72(1), 6–13. https://www.ams.org/notices/202501/rnoti-p6.pdf
7. Bellan, R. (2026, May 20). “OpenAI claims it solved an 80-year-old math problem, for real this time.” TechCrunch. https://techcrunch.com/2026/05/20/openai-claims-it-solved-an-80-year-old-math-problem-for-real-this-time/