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

> Source: <https://firstprinciples.com/blog-article/ai-system-theo-conjecture-solves-35-year-old-math-conjecture>
> Published: 2026-07-29 20:21:48+00:00

FirstPrinciples

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

In the 1980s, a program called [Graffiti](https://en.wikipedia.org/wiki/Graffiti_(program)) started asking questions nobody had thought to ask, and one of them caught the attention of [Paul Erdős](https://en.wikipedia.org/wiki/Paul_Erd%C5%91s). Almost forty years later, [Randy Davila](https://scholar.google.com/citations?user=LOrmuLEAAAAJ&hl=en) handed that same question to [Theo-Conjecture](https://firstprinciples.com/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](https://www.researchgate.net/publication/410906746_The_Havel-Hakimi_Residue_of_Common-Divisor_Graphs_Resolving_and_Extending_a_Problem_of_Graffiti_and_Erdos?channel=doi&linkId=6a68d587303c7d450cb0ebc3&showFulltext=true) 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.

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 ](https://en.wikipedia.org/wiki/Havel%E2%80%93Hakimi_algorithm)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](https://en.wikipedia.org/wiki/Siemion_Fajtlowicz), a mathematician at the [University of Houston](https://www.uh.edu/), 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](https://scholar.google.com/citations?user=1mwJPHYAAAAJ&hl=en), [László Lovász](https://en.wikipedia.org/wiki/L%C3%A1szl%C3%B3_Lov%C3%A1sz) and [Paul Seymour](https://en.wikipedia.org/wiki/Paul_Seymour_(mathematician)). 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](https://en.wikipedia.org/wiki/Odile_Favaron), Mahéo, and Saclé proved that the following year, and the [proof ](https://onlinelibrary.wiley.com/doi/10.1002/jgt.3190150107)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](https://scholar.google.com/citations?user=BvyGVOoAAAAJ&hl=en), 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.

## The problem comes back around

Randy Davila is a graph theorist and Member of Technical Staff at [FirstPrinciples](https://firstprinciples.com/), with an academic affiliation at [Rice University](https://www.rice.edu/). Since 2016 he's been building [TxGraffiti](https://txgraffiti2.readthedocs.io/en/latest/), 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.

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](https://en.wikipedia.org/wiki/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.

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.

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 ratio around and it reads just as cleanly:

*π(n) / R(Gₙ) → 1.550546...*

To be clear about what this isn't, it's not a faster way to count primes, and it doesn't touch the Riemann hypothesis. But the appearance of the zeta function here isn't a coincidence either. It falls out naturally from summing up the layered, multiplicative structure created by prime divisors, and the graph-theoretic proof explains exactly why the residue, a number that only ever looks at degrees, ends up capturing that same leading behavior.

The second-order term is the genuinely new part. It doesn't just tell you where the residue is heading asymptotically, but how fast the finite graph closes in on that destination.

## A tighter mystery, still open

One especially clean question came out of all this and hasn't been settled yet. Across every value tested consecutively up through n = 10,000, and at scattered checkpoints up to a million, the residue never strayed more than two integers from the rounded-up Caro-Wei sum:

*⌈CW(Gₙ)⌉ ≤ R(Gₙ) ≤ ⌈CW(Gₙ)⌉ + 2*

Nobody has proven that yet. If it holds, it would replace the theorem's current asymptotic error term with a hard, absolute bound of at most two, and it would explain the fine-grained behavior of the Havel-Hakimi procedure far more precisely than the degree-switching argument currently does.

There's also a bigger point sitting underneath all of this. Graffiti's role was to propose a relationship and hand it to a mathematician for judgment. Theo-Conjecture turns that same exchange into a running, iterative loop. Its registry holds onto examples and formulas, but it also holds onto the failed conjectures, the counterexamples, the abandoned representations, and the proof obligations nobody's finished yet. The language model gets to reorganize the problem and decide what to try next. The conjecturing engine supplies disciplined breadth. The exact computations get to say no. And the human advisor stays responsible for the purpose behind the search and the final proof.

Trace the line from Fajtlowicz through Erdős and Staton, on to Davila, Lagarias and Chung, and finally into the Theo-Conjecture loop, and what you get isn't a story about machines replacing mathematicians. It's a story about mathematical memory becoming something you can actually run, and about a language model gaining real leverage by leaning on a specialized discovery system again and again, instead of trying to reason its way through alone. A question left on a wall for decades finally found a generation of tools that could read it differently.

## Further reading

*Ermelinda DeLaViña, **Some History of the Development of Graffiti (uhd.edu)*

*Siemion Fajtlowicz, **“On Conjectures of Graffiti,” Discrete Mathematics (1988)*

*Randy Davila, **“Automated conjecturing in mathematics with TxGraffiti” (arXiv:2409.19379)*

*Paul Erdős biography, **MacTutor History of Mathematics*

*Jeffrey Lagarias, University of Michigan*

*Fan Chung Graham's publication list**, including the undated common-divisor residue preprint listing*

Odile Favaron, Maryvonne Mahéo, and Jean-Francois Saclé, [On the residue of a graph (Journal of Graph Theory, 15(1):39–64, 1991)](https://onlinelibrary.wiley.com/doi/10.1002/jgt.3190150107)

*The theorem and proof described here are contained in a **research manuscript** under preparation and have not yet completed peer review. Historical claims based on private correspondence are identified explicitly in the editorial source notes.*