Mathematician Randy Davila Claims Proof of a Longstanding Conjecture Using the Theo-Conjecture AI System
Mathematician Randy Davila Claims Proof of a Longstanding Conjecture Using the Theo-Conjecture AI System
On July 28, Randy Davila posted a preprint on common divisor graphs. Theo-Conjecture explored mathematical ideas and tested them computationally, while Davila formulated the proof.
Consider the integers from 2 to n. Two integers are joined by an edge if they share a divisor greater than one. Distinct prime numbers are not connected to one another, so they form a large set of vertices with no edges between them. Mathematicians seek upper bounds on the size of such sets. In this case, the bound is related to the distribution of prime numbers.
In 1987, the Graffiti program proposed the Havel–Hakimi residue algorithm. It takes the number of neighbors of each vertex, reduces this list step by step, and finally counts the remaining zeros. The algorithm sees only the vertex degrees, yet its output turns out to be close to the number of primes.
Davila's preprint claims that, for the common divisor graph, this quantity grows with an exact leading constant. It also derives the next term in the asymptotic expansion. The graph problem is therefore reduced to determining how far an algorithm can go when it knows only the number of neighbors of each vertex.
The description of Theo-Conjecture's work traces the path to this formula. The system stored verified objects, conjectures, and the results of previous attempts. It first connected the residue to the number of squarefree integers. Exact calculations revealed a discrepancy at 739. The counterexample at 739 remained in the attempt log and prompted the system to search for a different formula.
The next conjecture led to the Caro–Wei sum, which estimates the size of a set of vertices with no edges between them using their numbers of neighbors. This produced the leading constant. For the other bound, Davila used a property of the residue: it depends only on the degree sequence, so the graph can be rearranged while preserving the number of neighbors of every vertex. In the resulting construction, prime vertices of the same degree are grouped into cliques, while the connections are transferred to composite numbers. The two bounds have the same leading term.
Davila turned a sequence of conjectures, computations, and a counterexample into a proof. The system's log retained not only the successful formula, but also the error that changed the next step of the search.