Two AI agents just sharpened results in combinatorial optimization that human mathematicians had left at rougher estimates.
Researchers built a system with a coding agent and a theory agent working in tandem. The coding agent proposes constraints that tighten a convex relaxation of a hard nonconvex problem. The theory agent checks each proposal and hunts for counterexamples. Any bound that survives is certified by a dual-feasible point verified in rigorous interval arithmetic — meaning the system does not just claim an improvement, it proves one. The team applied this to two optimization constants previously studied in the AlphaEvolve paper: the first autocorrelation inequality and the Erdos minimum-overlap constant.
The results are modest in absolute terms but meaningful in context. Certified lower bounds moved from 1.28 to 1.2937 on the first constant, and from 0.379005 to 0.37912 on the second. What matters is the method: prior AI-assisted math work focused on finding upper bounds through extremal constructions. This addresses the complementary problem — provable lower bounds — which is typically harder to automate because it requires formal verification, not just clever search.
AlphaEvolve drew attention for using AI to beat human records in combinatorial math; this work shows the same autoresearch loop can be aimed at the rigorous, proof-side of the ledger, not just the experimental one.