Theo-Conjecture Proves 35-Year-Old Math Conjecture, Finds New Term

AI Proves 35-Year-Old Math Conjecture, Uncovers New Term

An automated discovery system called Theo-Conjecture has proven a conjecture about prime numbers that had stumped mathematicians since the 1980s. The proof not only confirms a long-held guess by Paul Erdős and William Staton but also reveals an unexpected second-order term, offering new insight into the connection between graph theory and number theory.

The Problem: Common-Divisor Graphs

Take integers from 2 to n, draw each as a vertex, and connect two vertices if they share a common factor greater than 1. This creates a graph Gₙ. The primes form an independent set (no edges between them), and in fact the largest possible independent set. The size of this maximum independent set, α(Gₙ), equals π(n), the number of primes ≤ n.

A much faster computation, the Havel-Hakimi procedure, produces a lower bound called the residue R(Gₙ). The procedure sorts vertex degrees (number of connections), repeatedly removes the highest degree d, subtracts 1 from the next d degrees, sorts again, and counts zeros at the end. For Gₙ, R(Gₙ) ≤ π(n). The question: how tight is this bound? Erdős and Staton showed R(Gₙ) ≥ (π²/6 − 1) n/log n, and Staton conjectured this was asymptotically exact.

Theo-Conjecture's Approach

Randy Davila, a graph theorist at FirstPrinciples and Rice University, fed this problem into Theo-Conjecture, a system where an LLM agent repeatedly calls a combinatorial conjecturing engine, runs exact computations, and maintains an evolving mathematical memory. The system tried and discarded several ideas. A key breakthrough: realizing the residue depends only on vertex degrees, not specific connections, allowing the graph to be rewired into a simpler structure. The proof clusters primes by degree and shows the residue's asymptotic behavior matches Staton's constant c₀ = ζ(2) − 1 ≈ 0.644934.

The Result: Known Constant + New Term

The theorem proved by Theo-Conjecture:

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

where A = Σ_{k=2}^∞ log k / [k²(k−1)] ≈ 0.3201986326.

This confirms Staton's prediction and adds the second-order term A. The limit:

lim_{n→∞} R(Gₙ) · log n / n = ζ(2) − 1

Or equivalently, π(n)/R(Gₙ) → 1.550546...

Why It Matters for Developers

This isn't just abstract math. The residue computation is O(n log n) and gives a provable lower bound on the prime count. For large n, this provides a fast, deterministic estimate without factoring numbers. The technique of rewiring graphs by degree while preserving residue could inspire new graph algorithms for independence number approximations.

The broader lesson: AI systems like Theo-Conjecture can tackle open problems by iterating through failures, keeping a record of what didn't work, and building on partial results. The human-in-the-loop ensures only verified results are accepted.

How Theo-Conjecture Works

The system uses an LLM agent to build a registry: a table of mathematical objects (graphs, invariants) with columns for numeric properties. The agent repeatedly calls the Theo-Conjecture engine, which generates candidate inequalities, ranks them, and searches for counterexamples. The human advisor sets objectives and validates proofs. This cycle can run autonomously, but human oversight is critical.

The Second-Order Term Nobody Predicted

Staton and others expected only the leading term. The A constant, derived from an infinite sum, was a surprise. It arises from the detailed distribution of prime degrees. This shows that even well-explored conjectures can yield new structure when tackled with computational search.

What's Next

The proof is published on FirstPrinciples' blog. Davila plans to extend the technique to other graph invariants. For developers, this demonstrates how LLMs can be combined with symbolic engines to produce verifiable results in mathematics and potentially in program analysis or optimization.

If you work on graph algorithms or number theory, the source code and data for Theo-Conjecture are available on GitHub. Try running the residue computation on your own graphs — the Havel-Hakimi algorithm is just a few lines of Python.