AI system 'Theo Conjecture' solves 35-year-old math conjecture, finds a term no one predicted | FirstPrinciples Hub
Pangram verdict · v3.3
We believe that this text is a mix of AI and human-written content.
AI likelihood · overall
MixedArticle text · 1,150 words · 8 segments analyzed
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 wallSiemion 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 aroundRandy Davila is a graph theorist and Member of Technical Staff at FirstPrinciples, with an academic affiliation at Rice University.