OpenFrontiers
Join
← Back to the index
OP-12055OpenOptimization

Gilbert-Pollak conjecture (Steiner ratio) (C43C_{43})

Gilbert-Pollak conjecture (Steiner ratio): determine C43C_{43} or improve its bounds; the repository records 0.8559 (0.860*) (lower) and 0.86602540378 (upper).

MSC 90C27 · Combinatorial optimizationMSC 05C05 · Trees

Editorial MSC2020 classification. Original article codes and source evidence are recorded in the literature directory.

Licensed source statementAs of Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differSource & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

C43C_{43} is defined as the infimum of the ratio of the length of the Steiner Minimal Tree to the length of the Euclidean Minimum Spanning Tree over all finite sets of points V⊆R2V \subseteq \mathbb{R}^2: C43=inf⁡VLS(V)/LM(V)C_{43} = \inf_{V}L_S(V)/L_M(V), where LS(V)L_S(V) and LM(V)L_M(V) denote the lengths of Steiner Minimal Tree and Minimum Spanning Tree, respectively.

Consider a set VV of nn points in the Euclidean plane R2\mathbb{R}^2. A spanning tree on VV is a connected, acyclic graph with vertex set VV. When the length of each edge is defined as the Euclidean distance between its endpoints, a spanning tree that minimizes the total length is called a Minimum Spanning Tree. The shortest network interconnecting all points in VV, where the length of each edge is measured by Euclidean distance, is necessarily a tree, referred to as a Steiner Minimal Tree. A Steiner Minimal Tree may contain auxiliary vertices not in VV.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

  • In 1968, Gilbert and Pollak conjectured that Steiner ratio is 3/2≈0.866\sqrt{3}/2 \approx 0.866, but this remains unproven. More information can be found at Wikipedia page on the Gilbert-Pollak conjecture.
  • The 0.85590.8559 and 0.8600.860 bounds are computer-assisted results of the same kind: a finite set of per-region inequality certificates resting on a layer of human-proved geometric lemmas. [S2026] independently re-verified the [KHSHGW2026] certificate layer (330,193,755 records, zero failures) with clean-room software, then regenerated the partitions at the higher target using the same lemma set and verified all 1,104,177,103 resulting regions. Both bounds are conditional on the [KHSHGW2026] lemma layer.

References (from the repository page)

  • [GP1968] Gilbert, E. N. and Pollak, H. O. Steiner minimal trees. SIAM Journal on Applied Mathematics, 16(1):1–29, 1968.
  • [GH1976] Graham, R. L. and Hwang, F. K. Remarks on steiner minimal trees. Bull. Inst. Math. Acad. Sinica, 4(1):177–182, 1976.
  • [CH1978] Chung, F. and Hwang, F. A lower bound for the steiner tree problem. SIAM Journal on Applied Mathematics, 34(1): 27–36, 1978.
  • [DH1983] Du, D.-Z. and Hwang, F. K. A new bound for the steiner ratio. Transactions of the American Mathematical Society, 278(1):137–148, 1983.
  • [CG1985] Chung, F. R. and Graham, R. L. A new bound for euclidean steiner minimal trees. Annals of the New York Academy of Sciences, 440(1):328–346, 1985.
  • [KHSHGW2026] Ke, Y., Huang, T., Shu, Y., He, D., Gai, J., and Wang, L. Towards Solving the Gilbert-Pollak Conjecture via Large Language Models. arXiv:2601.22365. Preprint (2026).
  • [S2026] Claude Fable 5 (Anthropic) and Savva, J. An Independent Verification of the Gilbert-Pollak Certificate Layer and a Certificate-Layer Bound of 0.8600.860 for the Steiner Ratio. doi:10.5281/zenodo.22223485. Preprint (2026). Code and data: github.com/aimathpapers/Steiner_Ratio.

Progress & source assessment

Repository table (commit 2c1968c, 26 September 2026): best known lower bound 0.8559 (0.860*); best known upper bound 0.86602540378. Values marked with an asterisk have minimal verification.

Known upper bounds

Bound Reference Comments
3/2≈0.866\sqrt{3}/2 \approx 0.866 [GP1968] equilateral triangle

Known lower bounds

Bound Reference Comments
0.50.5 [GP1968]
0.5770.577 [GH1976]
0.7430.743 [CH1978]
0.80.8 [DH1983]
0.8240.824 [CG1985]
0.85590.8559 [KHSHGW2026] New improvement, preprint
0.8600.860* [S2026] Certificate layer, independently verified; same lemma set as [KHSHGW2026]. Asterisked: the source is a self-archived preprint, and the bound is conditional on the [KHSHGW2026] lemma layer.
References
  1. [1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — Gilbert-Pollak conjecture (Steiner ratio) ($C_{43}$) linkApache-2.0 (repository license); constant pages reproduced with attribution; repository references retained.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.