Recent advancements in large language models have shown impressive results in competitive mathematics and programming, but their ability to make new mathematical discoveries, like proving new theorems or finding new structures, has been limited. Mathematics and theoretical computer science require absolute correctness, meaning any AI method must either be verified by a computer without human help or checked by an expert.
A new study, “Reinforced Generation of Combinatorial Structures: Applications to Complexity Theory,” shows how AlphaEvolve, an AI system developed by Google DeepMind, helps find new mathematical structures in complexity theory, a field that studies how hard computational problems are. AlphaEvolve uses large language models (LLMs) to improve code snippets through a feedback loop, starting with simple code and refining it to create better solutions. This led to discoveries in two areas: improving limits on approximating the maximum cut problem for four groups (MAX-4-CUT) and tightening bounds on the difficulty of checking properties of random graphs.
Advancing theorems through AI techniques
Complexity theory often seeks universal truths that apply to all cases of a problem, not just specific examples. AlphaEvolve tackles this by using a technique called lifting, where a small, finite structure in a proof is improved to support a broader, universal statement. This method keeps the rest of the proof unchanged, making verification easier. For example, in the MAX-4-CUT problem, where the goal is to divide a network into four groups to maximize connections between them, AlphaEvolve found a complex structure with 19 nodes and varied connection weights. This discovery improved the known limit of approximation from 0.9883 to 0.987, a small but significant step in a challenging field. Similarly, for random graphs, AlphaEvolve found special graphs called Ramanujan graphs with up to 163 nodes, improving the understanding of how hard it is to certify certain properties. These results were verified using computer programs to ensure absolute correctness, with AlphaEvolve speeding up the process dramatically. While not definitive, these findings suggest AI could become a valuable tool in mathematical discovery, though verifying results remains a key challenge.
