Theo Conjecture solves 35-year-old math problem, finds a term no one predicted

Conjecturing

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

4min read

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.

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.

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.

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:

α(Gₙ) = π(n)

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.

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.

A shortcut that shouldn't work (but does)

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.

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.

Eventually you're left with nothing but zeros. Count them. That count is called the residue of the graph, written R(G).

Computing the residue is fast, and it always undersells the truth in a predictable direction:

R(G) ≤ α(G)

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:

R(Gₙ) ≤ π(n)

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?

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.

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 to filter out anything true but boring. Fajtlowicz wasn't just trying to generate formulas, he was trying to understand what makes a mathematical statement worth a mathematician's time.

Graffiti's conjectures ended up inspiring hundreds of papers and drew the attention of mathematicians like Paul Erdős, Fan Chung, László Lovász and Paul Seymour. Erdős, in particular, was a natural fit. He spent much of his life bouncing between collaborators, concrete examples and open problems in number theory and combinatorics, and Fajtlowicz once summed up the resemblance between the man and the machine in a single line:

“Whatever the differences, Erdős and Graffiti had one point in common: their ideas were deeply rooted in examples.”

In November 1987, Fajtlowicz introduced the residue as an invariant into Graffiti and conjectured that it can never exceed the independence number. Favaron, Mahéo, and Saclé proved that the following year, and the proof was published in 1991. Graffiti then turned its attention to these common-divisor graphs on the integers, and the question made it into the running list of open problems called Written on the Wall, as Conjecture 448.

Erdős showed that the residue grows at least as fast as n / log n, the same rate as the prime-counting function itself. Working with the graph theorist William Staton, he pinned down the leading constant more precisely:

ζ(2) − 1 = π² / 6 − 1 = 0.644934...

That ζ(2) is a well-known value of the Riemann zeta function, the same function at the center of one of math's most famous open problems. Erdős then asked whether anyone could find a matching upper bound of the same order. Fajtlowicz guessed the constant might be 2/3. Staton, however, had a different hunch. He hypothesized that the Erdős-Staton lower bound wasn't just a lower bound, it was the exact answer. Written on the Wall records his position plainly: “Bill Staton thinks that the residue ... is asymptotically (π²/6 − 1) n / log n.”

Numerical checks up through n = 10,000 backed him up. But nobody produced a proof, at least not one that made it into any record anyone could find.

Dr. William A. “Bill” Staton III (Credit: HT Media)

The problem comes back around

Randy Davila is a graph theorist and Member of Technical Staff at FirstPrinciples, with an academic affiliation at Rice University. Since 2016 he's been building TxGraffiti, a modern successor to Fajtlowicz's original program. The core idea carried over intact, where every example and every invariant should be laid out clearly enough that a mathematician can look at it, poke at it, and push back.

The common-divisor residue question developed across two eras of machine-assisted mathematics, from Fajtlowicz's implementation of the residue in 1987 through the Theo-Conjecture proof workflow in 2026.

Davila rediscovered the common-divisor graph independently and rebuilt its data from scratch. In 2025 he sent his computations and plots to the number theorist Jeffrey Lagarias, who traced the question back through a set of hard-to-find Fajtlowicz documents and mentioned related work he'd done with Fan Chung. Chung's own publication list now lists an undated preprint called Bounds for Havel-Hakimi residues of non-coprime graphs, crediting Chung alongside Erdős, Lagarias and Staton, though there's no linked manuscript or theorem statement attached to it. Worth flagging directly: this chronology comes from private correspondence, and it should be independently confirmed with Lagarias and Chung before anyone treats it as settled history.

Still, the reconstruction did two useful things. It confirmed exactly what the conjecture claimed, and it clarified what a real advance would need to look like. That is, an upper bound that matches the Erdős-Staton constant, ideally with something beyond just the leading term.

That's the shape of the problem Davila fed into the Theo-Conjecture loop. Theo-Conjecture isn't a chatbot, and it isn't a formula-spitting machine either. It's a discovery system with a human advisor in the loop, where a large language model acts as an agent, repeatedly calling a combinatorial conjecturing engine, running exact computations, and updating an evolving mathematical memory as it goes.

The advisor-supervised Theo-Conjecture loop. A registry is an inspectable table whose rows are executable mathematical objects and whose columns are defined numerical invariants or Boolean predicates. An LLM agent builds and revises the registry, invokes Theo-Conjecture, interprets its ranked relations and launches exact counterexample searches. It can repeat this cycle with broad procedural autonomy; the human advisor controls objectives, significance and proof acceptance.

Every attempt gets kept (including the ones that fail) in a running record the model can search back through and build on later. Importantly, nothing counts as proven just because the model said so, or because it matched a pile of examples. A human mathematician has to sign off before anything counts as a real result.

That's what made the failures useful instead of wasted. When an idea didn't hold up, it stayed on the record and shaped what got tried next, rather than getting quietly dropped.

What the failures actually taught it

The system's first idea was wrong. It tried to explain the residue using how many numbers in a range have no repeated prime factors, and the prediction missed by a wide and growing margin, off by 739 at larger values. That ruled the idea out completely.

A better match came from a quantity called the Caro-Wei sum, which looks at how many connections each number has rather than which specific numbers are connected. Using it, the old ζ(2) − 1 constant fell out naturally, along with a second term nobody had predicted. That still only proved half the story, a lower bound. Closing the gap took a real insight, and realizing the residue only cares about how many connections each number has, never which ones specifically. So the whole graph can be redrawn, as long as every number keeps the same number of connections it started with.

The proof replaces prime-to-composite incidences by cliques of equal-degree prime vertices, then repairs the composite degrees elsewhere. Every degree is preserved, but the rewired graph has a simpler independent-set structure.

Here's what that redrawing looks like. Group the primes that share the same number of connections into a tight cluster where they're all connected to each other, and let ordinary composite numbers absorb the connections that got displaced. Once primes are clustered that way, it's easy to see you can never pick more than one of them at a time, which is exactly the bound Staton predicted.

The result

Putting all of that together proves Staton's original prediction and adds a second-order term nobody had found before:

R(Gₙ) = c₀ · n/log n + (c₀ − A) · n/log²n + O(n/log³n)

where

c₀ = ζ(2) − 1     and     A = Σ(k=2 to ∞) log k / [k²(k−1)] = 0.3201986326...

Which gives us, in the limit:

R(Gₙ) · log n / n  →  ζ(2) − 1

Put in plain terms, that theorem says the quick, degree-only calculation captures a fixed, predictable fraction of the true prime count as n grows. Flip the

[truncated for AI cost control]