Abstract:The Gilbert-Pollak Conjecture \citep{gilbert1968steiner}, 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 \approx 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.
| Comments: | 44 pages, 11 figures |
| Subjects: | Discrete Mathematics (cs.DM); Machine Learning (cs.LG) |
| Cite as: | arXiv:2601.22365 [cs.DM] |
| (or arXiv:2601.22365v2 [cs.DM] for this version) | |
| https://doi.org/10.48550/arXiv.2601.22365 arXiv-issued DOI via DataCite |
From: Jingchu Gai [view email]
[v1]
Thu, 29 Jan 2026 22:18:04 UTC (1,689 KB)
[v2]
Thu, 21 May 2026 02:46:16 UTC (1,061 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。