AI system 'Theo Conjecture' solves 35-year-old math conjecture, finds a term no one predicted | FirstPrinciples Hub

Company

Resources

Get early access

Foundation

Get early Access

Blog

Conjecturing

AI system 'Theo Conjecture' solves 35-year-old math conjecture, finds a term no one predicted

FirstPrinciples

Jul 29, 2026<br>4min read

Share

Subscribe to newsletter

Thank you! Your submission has been received!

Oops! Something went wrong while submitting the form.

In the 1980s, a program called Graffiti started asking questions nobody had thought to ask, and one of them caught the attention of Paul Erdős. Almost forty years later, Randy Davila handed that same question to Theo-Conjecture, an automated discovery system supported by a large language model that proposes, tests and revises mathematical ideas in a loop. What came back was a proof of the answer Erdős and his collaborators had guessed at, an unexpected extra term nobody had predicted, and a glimpse of what it looks like when an AI agent and a human mathematician work a problem together.<br>Here's the picture to hold in your head. Take the integers from 2 through 30 and draw each one as a dot. Draw a line between two dots whenever the numbers share a factor greater than one. So 6 connects to 10, since both are divisible by 2, and 15 connects to 25, since both are divisible by 5.

The common-divisor graph \(G_{30}\). Vertices are the integers from 2 through 30, and two are joined when they share a factor greater than one. Gold edges meet a prime vertex, blue-grey edges join two composite vertices, and the ten gold prime vertices have no edges among themselves and form a maximum independent set.What you end up with is a graph, in the mathematical sense, of dots (vertices) joined by lines (edges). Color the primes gold. None of the gold dots touch each other, because two different primes never share a factor.<br>The surprising part? The primes aren't just some collection of unconnected dots. They form the largest possible group of dots with no connections between them at all. Mathematicians have a name for groups like these - an independent set. It's worth seeing why the primes win this contest.<br>Pick any independent set in the graph. Every number in it has to be coprime to every other number in it (that's what “no shared factors” means). Now pull out one prime factor from each number. Since none of those numbers share factors, the primes you just pulled out have to all be different from each other. Which means you can never gather more numbers into your independent set than there are primes to draw from in the first place. Written as a formula:

Here Gₙ is the graph built from the integers 2 through n, α(Gₙ) is the size of its largest independent set, and π(n) is the classic prime-counting function, the number of primes up to n.<br>That's a neat identity on its own; it turns a question about counting primes into a question about a graph. But it also opens a door to something more strange, a number you can compute quickly using nothing but arithmetic on a graph's structure, with no obvious connection to primes at all.<br>A shortcut that shouldn't work (but does)<br>Finding the largest independent set in a graph is, in general, a hard computational problem because it doesn't scale well. But there's a much easier number to get your hands on, called the degree of a vertex, meaning how many edges touch it.<br>There's a trick for turning degrees into a lower bound on independence, called the Havel-Hakimi procedure. List every vertex's degree, largest to smallest. Take the biggest number, call it d, cross it off, and subtract 1 from each of the next d entries in the list. Sort again. Repeat.<br>Eventually you're left with nothing but zeros. Count them. That count is called the residue of the graph, written R(G).<br>Computing the residue is fast, and it always undersells the truth in a predictable direction:

In other words, the residue is a certificate you can compute in seconds that guarantees a lower bound on the size of the largest independent set, without you ever having to find that set. Applied to our prime graph, that becomes:

So here's the real question. This residue calculation only ever looks at degrees. It never looks at which vertex connects to which. Does that stripped-down view still capture the right order of magnitude for counting primes? Or does throwing away all that structural detail throw away the answer too?<br>That question has a surprisingly long history, and it starts with one of the first serious attempts to get a machine to propose mathematics on its own.<br>Graffiti, Erdős, and a question left on the wall

Siemion Fajtlowicz and Paul Erdös, 1992 (Credit: Jerry Grossman's webpage).Siemion Fajtlowicz, a mathematician at the University of Houston, built a program called Graffiti in the mid-1980s. It stored a library of graphs along with numerical properties of each one, generated candidate inequalities relating those properties, and used a set of heuristics...