HEXAGONbeta

The Steiner ratio is at least 0.8564

A mix of human-written and AI-generated textHuman understanding: all partsmath.CO — Combinatoricsmath.MG — Metric Geometrycs.CG — Computational Geometrymath.OC — Optimization and Control

Contributed by Tejasvi Singh Tomar ↗

Version 1 / Nov 12, 2026 / CC BY 4.0

Abstract

The Steiner ratio is the infimum, over finite sets of points in the Euclidean plane, of the length of a Steiner minimal tree divided by the length of a minimum spanning tree. Gilbert and Pollak conjectured in 1968 that it equals 3/2≈0.8660\sqrt3/2\approx0.8660, and the conjecture is open. We prove that it is at least 2141/2500=0.85642141/2500=0.8564, improving the bound 0.85590.8559 of Ke, Huang, Shu, He, Gai and Wang. Their method reduces the induction step of Du and Hwang's 1983 proof of the bound 0.80.8 to finitely many inequalities on boxes in a space of local configurations of a Steiner minimal tree, which are checked by computer. These inequalities use estimates for the positions of terminals outside the local configuration. We prove all the geometric lemmas that our certificate uses, filling gaps in two proofs of Ke et al., and we add two such estimates that hold for more parameter values than the published ones. Within this method some new estimate is necessary: with the published estimates, no certificate of this kind reaches 0.8560.856, whatever the boxes. The computer-assisted part is also verified in Lean 4, by a proof whose checks all run in Lean's kernel; the rest of the argument enters the formal proof as hypotheses.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23716009

References

  1. F. R. K. Chung and R. L. Graham, A new bound for Euclidean Steiner minimal trees , Ann. New York Acad. Sci. 440 (1985), 328--346.
  2. F. R. K. Chung and F. K. Hwang, A lower bound for the Steiner tree problem , SIAM J. Appl. Math. 34 (1978), 27--36.
  3. D.-Z. Du and F. K. Hwang, A new bound for the Steiner ratio , Trans. Amer. Math. Soc. 278 (1983), 137--148.
  4. D.-Z. Du and F. K. Hwang, The Steiner ratio conjecture of Gilbert and Pollak is true , Proc. Natl. Acad. Sci. USA 87 (1990), 9464--9466.
  5. D.-Z. Du and F. K. Hwang, A proof of the Gilbert--Pollak conjecture on the Steiner ratio , Algorithmica 7 (1992), 121--135.
  6. D.-Z. Du, F. K. Hwang, G. D. Song and G. Y. Ting, Steiner minimal trees on sets of four points , Discrete Comput. Geom. 2 (1987), 401--414.
  7. D.-Z. Du, F. K. Hwang and E. Y. Yao, The Steiner ratio conjecture is true for five points , J. Combin. Theory Ser. A 38 (1985), 230--240.
  8. D.-Z. Du, E. Y. Yao and F. K. Hwang, A short proof of a result of Pollak on Steiner minimal trees , J. Combin. Theory Ser. A 32 (1982), 396--400.
  9. The FLINT team, FLINT: Fast Library for Number Theory , https://flintlib.org.link
  10. R. L. Graham and F. K. Hwang, Remarks on Steiner minimal trees , Bull. Inst. Math. Acad. Sinica 4 (1976), 177--182.
Show all 21 referencesShow fewer references
  1. E. N. Gilbert and H. O. Pollak, Steiner minimal trees , SIAM J. Appl. Math. 16 (1968), 1--29.
  2. A. O. Ivanov and A. A. Tuzhilin, The Steiner ratio Gilbert--Pollak conjecture is still open , Algorithmica 62 (2012), 630--632.
  3. F. Johansson, Arb: efficient arbitrary-precision midpoint-radius interval arithmetic , IEEE Trans. Comput. 66 (2017), 1281--1292.
  4. Y. Ke, T. Huang, Y. Shu, D. He, J. Gai and L. Wang, Towards solving the Gilbert--Pollak conjecture via large language models , in: Proceedings of the 43rd International Conference on Machine Learning, PMLR 306 (2026), 56442--56498; we cite the numbering of arXiv:2601.22365v3. Code: https://github.com/keyisi2006/Steiner-Ratio, commit 8f19604.arXiv
  5. L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language , in: Automated Deduction -- CADE 28, Lecture Notes in Comput. Sci. 12699 , Springer, 2021, 625--635.
  6. The mathlib Community, The Lean mathematical library , in: Proc. 9th ACM SIGPLAN Int. Conf. Certified Programs and Proofs (CPP 2020), 2020, 367--381.
  7. H. O. Pollak, Some remarks on the Steiner problem , J. Combin. Theory Ser. A 24 (1978), 278--295.
  8. J. H. Rubinstein and D. A. Thomas, The Steiner ratio conjecture for six points , J. Combin. Theory Ser. A 58 (1991), 54--77.
  9. J. Savva, Steiner_Ratio: independent verification of the Gilbert-Pollak certificate layer and a certificate-layer bound of 0.860 , Zenodo, 2026, doi:10.5281/zenodo.22223485 (https://doi.org/10.5281/zenodo.22223485).DOI
  10. T. Tao et al., Optimization constants in mathematics , online repository, https://teorth.github.io/optimizationproblems/, 2026.link
  11. E. Weiszfeld, Sur le point pour lequel la somme des distances de nn points donnés est minimum , Tôhoku Math. J. 43 (1937), 355--386.

Version history

  1. v1 · 19 pagesSubmitted by Tejasvi Singh TomarPublished on Zenodo: https://doi.org/10.5281/zenodo.23716009CurrentNov 12, 2026