TejasviTomar
October 2026 · Preprint

The Steiner ratio is at least 0.8564

Tejasvi Singh Tomar

In plain words

On a flat map, the shortest road network that joins a set of towns may need extra junctions between them. Gilbert and Pollak conjectured in 1968 that junctions never save more than about 13.4 percent compared with the best network without them. That is the saving for three towns at the corners of an equilateral triangle. In 2026, Ke and colleagues gave a computer-assisted proof of a looser limit: junctions never save more than 14.41 percent. In this paper, two new geometric results let the same method lower the limit to 14.36 percent.

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 that it equals √3/2 = 0.8660…. We prove that it is at least 2141/2500 = 0.8564, improving the bound 0.8559 of Ke, Huang, Shu, He, Gai and Wang. Their method reduces the induction step of Du and Hwang to finitely many inequalities on boxes in the space of local configurations of a Steiner minimal tree. We use it with complete proofs of the geometric lemmas it needs, with two new lemmas that use the minimality of the tree among all networks, and with explicit networks for reconnections of four points. Our certificate consists of 555,102,905 boxes. A checker written independently of the program that generated them verifies, in ball arithmetic at the value 2141/2500, the inequality of every box that meets the domain of its family, and a second program verifies that the boxes of each family tile its parameter space. We also show that, near one configuration, every splitting of the form used by Ke et al., priced with their lemmas, has positive cost once the ratio is at least 0.856. A complete certificate of this form for any value of at least 0.856, such as the conditional value 0.860 listed in Tao’s repository of optimization constants, therefore needs lemmas beyond the published ones.

Two panels on white, with no axes or labels. Left: a tree of straight black edges that meet at 120 degrees, with three yellow dots at its outer ends, five white dots at its junctions, two edges in magenta and four short dashed stubs at its lower end. Right: a square with a black frame, divided into rectangles of several sizes, most of them small squares in a grid, coloured teal (a large central region), yellow (upper right), green (lower right) and light grey (the rest), with a magenta dot inside the teal region.
Illustration of the certificate. Left: the local configuration d_regular from Figure 1 of the paper, drawn with the edge AX as the unit of length and with edge lengths b = 1.2655 (XB), s = 0.9688 (XY), c = 1.2 (YZ), d = 0.2655 (YD), e = 0.6 (ZR) and f = 0.9062 (ZQ). The yellow dots are the terminals A, B and D. The white dots are the Steiner points X, Y and Z, together with the vertices R and Q, which may each be a terminal or a Steiner point. The dashed edges continue into the rest of the tree. The two magenta edges have lengths c and e. Right: a slice through the part of the certificate for d_regular configurations with f ≥ d, taken at the values of b, s, d and f used on the left. The horizontal axis is c, from 0.9 to 1.75, and the vertical axis is e, from 0.15 to 1. Each box carries one splitting of the tree. The checker verifies the cost bound of that splitting at the corners of the box; this suffices because the bound is convex in the edge lengths. The three splittings that cover the most area here are shown in teal, yellow and green, and the other six in grey. The magenta dot is the configuration on the left.