Towards Solving the Gilbert-Pollak Conjecture via Large Language Models

arXiv:2601.22365 · cs.DM, cs.LG · Submitted 2026-01-29 · Read on arXiv

cs.DM, cs.LG

Submitted: 2026-01-29

Updated: 2026-09-02

Comments: Published in ICML 2026

Code: https://github.com/keyisi2006/Steine

License: http://creativecommons.org/licenses/by/4.0/

The gist: The Gilbert-Pollak Conjecture, also known as the Steiner Ratio Conjecture, states that for any finite point set in the Euclidean plane, the Steiner minimum tree has length at least sqrt 3 /2 about

Terminology

Abstract

The Gilbert-Pollak Conjecture, also known as the Steiner Ratio Conjecture, states that for any finite point set in the Euclidean plane, the Steiner minimum tree has length at least sqrt 3 /2 about 0.866 times that of the Euclidean minimum spanning tree (the Steiner ratio). A sequence of improvements through the 1980s culminated in a lower bound of 0.824, with no substantial progress reported over the past three decades. Recent advances in LLMs have demonstrated strong performance on contest-level mathematical problems, yet their potential for addressing open, research-level questions remains largely unexplored. In this work, we present a novel AI system for obtaining tighter lower bounds on the Steiner ratio. Rather than directly prompting LLMs to solve the conjecture, we task them with generating rule-constrained geometric lemmas implemented as executable code. These lemmas are then used to construct a collection of specialized functions, which we call verification functions, that yield theoretically certified lower bounds of the Steiner ratio. Through progressive lemma refinement driven by reflection, the system establishes a new certified lower bound of 0.8559 for the Steiner ratio. The entire research effort involves only thousands of LLM calls, demonstrating the strong potential of LLM-based systems for advanced mathematical research.

Sources

Related papers