AI Finds a Novel Proof for an Erdős Problem

Increasingly capable Artificial Intelligence (AI) technologies are gaining steam in proving long-standing mathematical conjectures. The latest development involves a proof of another one of prolific mathematician Paul Erdős‘ 1,135 unsolved problems, but unlike AI’s previous accomplishments in tackling part of Erdős’ legacy, GPT-5.4′s proof of Erdős #1196 appears to be genuinely novel.

The previous proofs by AI systems of other Erdős problems did not answer the question of whether the technology was bringing anything new to the table. The problems themselves could be considered “low-hanging fruit“, whose unsolved status had more to do with the obscurity of the conjectures within the Erdős collection than their difficulty. When AI developed proofs for them, it more or less followed the playbook that mathematicians had established in proving other Erdős conjectures.

But Erdős’ 1196th conjecture is not in that category. Mathematicians had previously taken on the challenge of developing a proof for it, largely turning to the tools of probability and statistics in the process. But instead of copying that approach, GPT-5.4 Pro found the path for proving the conjecture differently. Mathematician Terrence Tao offered this observation:

I had previously stated the opinion that the AI-generated proof had inadvertently highlighted a tighter connection between the anatomy of integers and the theory of Markov chains than had previously been explicitly noted in the literature. Based on further developments, I would like to update that opinion to the following: the AI-generated proof artefact, when combined with subsequent (and mostly human-generated) analysis, has revealed a tight connection between the anatomy of integers and flow network theory that does not, to my knowledge, have any explicit precursor in the literature (although related uses of Markov chains in adjacent settings do appear in that literature).

The development of the proof was verified using the Lean proof assistant, which we would argue is the secret sauce behind why AI technologies are making such rapid progress in advancing proofs to unsolved problems in the field. The pairing of the technologies is key to the advancement.

Getting back to the novelty of the proof, here’s a comment by Jared Duker Lichtman, who developed the first proof of the related Erdős primitive set conjecture as part of his doctoral thesis in 2024.

In my doctorate, I proved the Erdős Primitive Set Conjecture, showing that the primes themselves are maximal among all primitive sets.

This problem will always be in my heart: I worked on it for 4 years (even when my mentors recommended against it!) and loved every minute of it.

[Primitive sets are a vast generalization of the prime numbers: A set S is called primitive if no number in S divides another.]

Now Erdős#1196 is an asymptotic version of Erdős’ conjecture, for primitive sets of “large” numbers. It was posed in 1966 by the Hungarian legends Paul Erdős, András Sárközy, and Endre Szemerédi.

I’d been working on it for many years, and consulted/badgered many experts about it, including my mentors Carl Pomerance and James Maynard.

The proof produced by GPT5.4 Pro was quite surprising, since it rejected the “gambit” that was implicit in all works on the subject since Erdős’ original 1935 paper. The idea to pass from analysis to probability was so natural & tempting from a human-conceptual point of view, that it obscured a technical possibility to retain (efficient, yet counter-intuitve) analytic terminology throughout, by use of the von Mangoldt function Lambda(n).

The closest analogy I would give would be that the main openings in chess were well-studied, but AI discovers a new opening line that had been overlooked based on human aesthetics and convention.

In fact, the von Mangoldt function itself is celebrated for it’s connection to primes and the Riemann zeta function–but its piecewise definition appears to be odd and unmotivated to students seeing it for the first time. By the same token, in Erdős#1196, the von Mangoldt weights seem odd and unmotivated but turn out to cleverly encode a fundamental identity sum_{q|n}Lambda(q) = log n, which is equivalent to unique factorization of n into primes. This is the exact trick that breaks the analytic issues arising in the “usual opening”.

Joshua Zelinsky offers perhaps the best framing of the accomplishment and what it could mean for additional progress:

Four things to note: #1196 is a decently well known problem. It wasn’t like Erdős-Straus level fame, but it is well known enough that I was familiar with it. Second, this is not a problem where no one had worked on it; there was a lot of prior work on it and closely related problems. Third, this is not example where the AI made small modifications to things in the literature or recognized that large parts of the problem were in an obscure paper. The approach the AI used is largely a different direction than the literature on this problem went. Fourth, and closely related to three, this proof does look like parts of it will inspire subsequent proofs because it really is going in a different direction which now looks likely to be a productive line of investigation for similar problems.

If this kind of progress continues, the productivity of AI technology in cracking unsolved math problems will be the biggest math story of the year. AI was already the biggest math story of 2025, but 2026 is shaping up to be even more so.