Generative Artificial Intelligence-Assisted Discovery of a New Euclidean Held-Karp Bound

Can generative artificial intelligence contribute to new theory in operations research while separating exploratory search from checkable proof obligations? We report a case study in random Euclidean optimization. The mathematical contribution is a finite certificate for the Held-Karp relaxation of the traveling salesman problem. It assigns every mutual two-nearest-neighbor triangle a nonnegative residual price for every feasible vector. This pointwise property distinguishes the method from earlier tour-specific and minimum-spanning-tree routes. It permits integration over the full triangle family and yields a strict improvement over the classical nearest-neighbor baseline in every fixed dimension. A directed-rounding certificate proves that the planar Held-Karp and traveling salesman constants both exceed 0.64037. OpenAI Codex explored candidate routes, proposed reformulations, and drafted the initial verifier. Human review then consolidated the accepted proof chain and checked the theorem-critical computation.