Creative solution: AI solves 60-year-old Erdős problem

Contents

23-year-old Liam Price has solved a decades-old mathematical problem with a single prompt to GPT-5.4 Pro – in a way that has caused more astonishment in the professional world than many other AI successes in mathematics. He wasn't even aware of which problem he had solved. The fact that artificial intelligence can achieve real breakthroughs in mathematical problems remains controversial in the professional world.

He told Scientific American: “I don't even know what this problem is.” He only occasionally works on Erdős' problems and feeds them to the AI to see what results he gets. “Then it delivered a seemingly correct solution.” The problem #1196 is now officially marked as solved on the platform erdosproblems.com; the proof has been formally verified in the proof assistant Lean.

The mathematics behind it

But what exactly did Price prove? At the center is a conjecture by Paul Erdős, András Sárközy, and Endre Szemerédi on the structure of so-called primitive sets. A primitive set is a set of integers greater than 1 in which no element divides another.

A set A ⊂ ℕ is called primitive if for all a, b ∈ A with a ≠ b, the following holds:

Erdős introduced a characteristic sum for such sets, often referred to as the “Erdős sum.” For a primitive set A, it is defined as:

Problem #1196 deals with primitive sets whose elements are all greater than a parameter x. Thus, we consider primitive sets

The Erdős–Sárközy–Szemerédi conjecture roughly states that the Erdős sum of such sets is asymptotically not greater than 1. More precisely: For any primitive set A⊂[x,∞), it should hold

Before the current AI solution, the best known general bound was a paper by Jared Lichtman from 2023, which, however, left a gap of about 40 percent to the conjectured limit of 1.

where γ denotes the Euler-Mascheroni constant. This made it clear that the sum remains bounded, but the limit of 1 conjectured by Erdős had not yet been reached.

What GPT‑5.4 Pro proved

Price was able to show with GPT‑5.4 Pro that for any primitive set A ⊂ [x, ∞), a sharper bound actually holds, which asymptotically converges to 1. The proof even provides an explicit convergence rate: the distance to the bound 1 shrinks at least proportionally to 1/log x

for all primitive sets A and sufficiently large x. This implies in particular.

Methodological Core: Markov Chains in Number Theory

The actual surprise lies in the proof idea. GPT-5.4 Pro proposed an approach via Markov chains: the multiplicative structure of integers is modeled as a random process in which prime factors are gradually extracted from a number n. The distribution of the resulting “prime factor paths” can then be analyzed using tools from probability theory.

This bridge between analytic number theory and stochastic process theory is what Fields Medalist Terence Tao describes in the forum of erdosproblems.com as a closer connection between the “anatomy of integers” and Markov process theory than has been explicitly highlighted in the professional literature so far.

What distinguishes this proof from previous AI successes

The proof fundamentally follows a series that made headlines in the fall of 2025: at that time, OpenAI employees presented several Erdős problems on X that GPT-5 had allegedly solved. Disillusionment followed shortly after – as Terence Tao and Thomas Bloom clarified, the model had not found new proofs but had merely unearthed already published results. However, it was already known that Erdős issues could indeed be cracked with the help of AI: Erdős #281 and #728 were solved using GPT-5.2 as early as January.

However, this time it is not a problem that has already been solved in the literature. “It seems that the literature had managed to focus on a somewhat suboptimal approach in which the opening move was to transfer the problem to a continuous setting, but the AI runs consistently stayed in the discrete world and managed to utilize various existing tools from discrete mathematics mostly centering around methods relating to the LYM inequality to reach a solution,” says Tao. In retrospect, the problem might have been simpler than expected, a kind of mental block.

However, the proof led by the AI was by no means ready for publication. According to Lichtman, the raw output from GPT-5.4 Pro was quite poor – it took an expert to understand what the model was trying to say. Lichtman and Tao have since shortened the proof so that the language model's key insight is clearer. Thomas Bloom, operator of the Erdős Problems database, characterized the story on X as an example of how AIs can be used to supplement and enhance human research.

Can AI discover (mathematical) knowledge?

The case falls within an ongoing debate about whether large language models can discover new knowledge of mathematics and other disciplines that goes beyond the data points learned during training. Ten leading mathematicians have already systematically investigated this question – with disappointing results for AI creativity. In the forum of erdosproblems.com, Tao urges caution regarding possible “survivor bias.” Thousands of instances of these models are unleashed on the problems among the Erdős problems alone, but only the successful or partially successful cases are reported. (vza)