GoKawiilIn 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)
... continue reading