THE TRAVELLING SALESMAN'S HIDDEN NUMBER, CORNERED

AI use declared. In a “Disclosure of AI Use”, the authors state that they used the AI tool GPT-5.6 Sol Pro in preparing the paper, that they reviewed and verified all results, and that they take full responsibility for its content. Their code is available on request.

The travelling salesman problem asks for the shortest tour that visits each point of a set once and returns to the start. Now make the points random: throw n points uniformly into a square of side 1 and ask how long the shortest tour is.

In 1959, Beardwood, Halton and Hammersley proved a striking answer. As n grows, the length of the best tour becomes almost surely equal to β√n, where β is a universal constant — the same for every random scattering. They also showed that 0.625 ≤ β ≤ 0.9212.

More than sixty-five years later, nobody knows β. There is no formula. Large computer experiments put it at about 0.7124, but an experiment is not a proof. Until now, the best proven bounds were 0.6277 ≤ β ≤ 0.90367. Such constants matter in logistics, where they are used to estimate the length of delivery routes without computing them — which is why the new result comes from the McCombs School of Business of the University of Texas at Austin, by Zhuolun Dong and Junyu Cao.

The new bracket

The paper proves:

0.6421 ≤ β ≤ 0.8810

and, using random sampling, shows that 0.6536 ≤ β ≤ 0.8749 with a probability of at least 1 − 2 × 10⁻⁴. That probability concerns the randomness of the computer sampling, not β itself, which is a fixed number.

From below: cut the long edges

To prove that every tour must be long, the authors look at what happens if you delete all the edges of a tour longer than some length r. The tour breaks into pieces of path, and each piece stays inside a cluster of points that are within r of one another. The more paths a cluster needs to be covered, the more long edges the tour must have had. Adding this up over every possible r gives the tour length:

ℓ(H) = ∫₀^∞ N_H(r) dr,

where N_H(r) counts the edges longer than r.

Isolated points and path ends give the old term 5/8 = 0.625 — exactly the 1959 bound. The new ingredient is a series of corrections from small clusters of 3, 4 and 5 points, each an integral over the possible positions of the points. These integrals cannot be computed exactly, so the authors chop their domains into tiny cubes and bound each cube from below, with every irrational number rounded in the unfavourable direction so that the result is a genuine bound:

β ≥ 0.625 + 0.01113528859 + 0.005040573276 + 0.001015487669 > 0.6421.

From above: zigzag in blocks of five

An upper bound only needs one good tour. The classic recipe cuts the square into horizontal strips and sweeps them in a zigzag, left to right, then right to left. The new twist: inside each strip, points are taken in blocks of five, and each block is visited in the best of its 24 possible orders.

The expected length of a block is an eleven-dimensional integral — five horizontal gaps between points and six heights. The authors bound it numerically on a fine grid, again with rational numbers rounded the safe way, and obtain β < 0.8810.

The gap that remains

The bracket has narrowed from a width of about 0.28 to about 0.24, but the empirical value 0.7124 still sits well inside it. Finer grids, sharper estimates of overlapping disc areas and longer blocks could tighten it further. Closing the remaining distance, the authors write, “may require new techniques.”