The travelling salesman’s constant

Imagine for a moment that you are a travelling salesman, seeking the shortest round trip through a million points scattered at random over a square whose sides are one unit long. Through simulation, we know that this unfortunate salesman’s journey will be about 712 units long. In 1959 John Hammersley and his doctoral students at Oxford, Jillian Beardwood and John Halton, proved that once n is large, the shortest round trip through n random points has a length close to β√n, where β is a constant that does not depend on how the points fall.Strictly, the length divided by √n tends to β with probability one. The theorem also covers other regions, other ways of scattering the points and higher dimensions, each dimension with its own constant. β is also called the Beardwood–Halton–Hammersley constant. Johnson, McGeoch and Rothberg estimated 0.7124 ± 0.0002 in 1996, by way of the Held–Karp bound computed on very large instances. Percus and Martin found 0.7120 ± 0.0002 the same year, on a square whose opposite edges are joined. By the theorem’s scaling, n stops spread evenly over an area A need a round of about β√(nA); Dong and Cao’s preprint points to this use in planning. Computer experiments put β near 0.7124, from which we get the 712 units for a million points. No one has proved that value, and proofs so far give only upper and lower bounds for β (Figure 1).

Beardwood, Halton and Hammersley’s own construction gave an upper bound of 0.9212 in 1959, and the bound hardly moved for 64 years. In 2015 Stefan Steinerberger lowered it by less than a millionth. In 2023 Yu and Carlsson, and in 2026 Gaudio and Guan, brought it down to just over 0.903. On 2 October 2026 Zhuolun Dong and Junyu Cao posted a proof that β is at most 0.8810. Nine days later I posted a preprint that brings the bound down to 0.8618. That step of 0.019 is nearly half as large as the whole fall from 1959 to Dong and Cao.Yu and Carlsson’s preprint of 2023 states 0.90304. Their article of 2026, under the names Carlsson and Yu, gives 0.9038, the value used here and the one that Gaudio and Guan’s 0.90367 improves on. From 0.9212 to Dong and Cao’s 0.8810 is a fall of 0.040; the new step is 0.019. For the lower bound, Beardwood, Halton and Hammersley proved 0.625; Steinerberger raised it in 2015, to 0.6268 as corrected by Gaudio and Jaillet, who raised it to 0.6277 in 2020; and Dong and Cao’s preprint gives 0.6421.

Both proofs follow a plan that Steinerberger proposed in 2015. He kept the strips of 1959, but within a strip he would take the points in blocks of a few and visit each block in its shortest order. The difficulty lies in proving how short such a tour is on average. The new paper bounds that average more tightly than Dong and Cao did, and so can take blocks of ten points where they took six.

The zigzag of 1959

An upper bound for β needs only one way of touring random points whose average length can be worked out, since the shortest tour is never longer. A computer search finds far shorter tours, but nobody can say what their average is.

The tour of 1959 is a zigzag. Cut the square into horizontal strips. Visit the points of the first strip from left to right, those of the next from right to left, and so on, then join the ends. Each of the n points has about 1/n of the square to itself, so neighbours lie about 1/√n apart, and a tour of n such steps is about √n long. Strip heights below are in units of 1/√n.

In thin strips the tour makes long jumps along the strip between consecutive points, and in tall strips it climbs up and down between them. A height of √3, close to the best, balances the two and gives the bound of 1959 (Figure 2).Seen from inside a strip, random points form a Poisson process: the gaps between consecutive points along the strip are exponential, with mean 1/h for strips of height h, and the heights within the strip are uniform. The average length of a step is then a double integral, and the tour’s length divided by √n tends to it; at h = √3 it is 0.92116. Beardwood, Halton and Hammersley printed 0.92037, which Steinerberger believes came from their numerical integration. Few had used strips in 1955 to show that a path through any n points in the square is at most √(2n) + 1.75 long, and Steinerberger notes that the argument of 1959 is very similar.

Taking C before B

Steinerberger’s own gain of 2015 came from swapping two neighbouring points in patterns like the one in Figure 3.Steinerberger proved the swap worth at least (9/16)·10⁻⁶, with deliberately rough estimates, while simulation suggested far more. In the same paper, a simulation of separate groups of six points in strips of height √3, each group with its end points kept in place, suggested about 0.8902. Yu and Carlsson first proved a bound with blocks that share their end points, as below. Four points A, B, C and D lie half a unit apart along the strip, at heights 0, 1.2, 0 and 1.2. From left to right the path makes three slanting steps of 1.3 each, 3.9 in all, since each is the long side of a right triangle with sides 0.5 and 1.2. Taking C before B makes two flat steps of 1 and one slanting step of 1.3, which is 3.3. The path still starts at A and ends at D.

Steinerberger’s plan does this for whole groups of points. A block is a run of consecutive points of a strip. Its first and last points are shared with the neighbouring blocks and stay in place, while its inner points are visited in the shortest order. A strip is then a chain of blocks, and the tour’s average length is the sum of the blocks’ average paths. The gain grows with block size, by less with each point added, from six points to eight and ten in Figure 4. In blocks of six points the best strip height rises to about 2, and the tour’s average falls from 0.9212√n to about 0.8743√n.

A block’s path in its shortest order is the minimum of many lengths, one for each order of the inner points: 24 orders for six points, 40,320 for ten. The average length of a single step can be worked out as an integral, so a path that always visited the points in the same order could be averaged one step at a time. But the shortest order changes from block to block, and its steps change with it. A simulation such as Figure 4’s estimates the average and proves nothing. Steinerberger’s plan stayed a proposal until 2023.

Orders chosen in advance

Yu and Carlsson divided the possible blocks into cells of similar ones and fixed one order in advance for each cell, drawing their cells with a decision tree. Dong and Cao’s cells come from a grid. A block of six points is described by eleven numbers: the five gaps between consecutive points along the strip and the six heights. Cut the range of each gap into a few intervals and the strip into a few bands. A cell is then one interval for each gap and one band for each point, and every block falls in exactly one cell.

Within a cell the order no longer changes, and the average length of a fixed path is the sum of the average lengths of its steps. Only averages of single steps over a cell are left, and an upper bound for each of those is enough. Each cell takes the order whose step bounds add up to the least (Figure 5). Some blocks are given a longer path than their shortest one; that is the price of an average that can be bounded.The bound for blocks is the paper’s Theorem 2.2, set out in the appendix. It holds for any way of choosing orders that looks only at the block, which is what allows an order fixed for a whole cell.

Dong and Cao used twelve intervals for each gap and twenty bands for the heights, which makes about sixteen trillion cells.That is 12⁵·20⁶, about 1.6·10¹³. Dong and Cao’s strips have height 2, and their cells are all equally likely. Symmetries of the block (reading it from the other end, turning it upside down, moving all its points up together) reduce the count. Dong and Cao use rational arithmetic, and speak of blocks of five, counting only the points each block adds. They also give 0.8749 from a random sample of blocks, which holds with probability at least 1 − 10⁻⁴ over the sampling; it is a statement of probability, not a proved bound. Yu and Carlsson used blocks of five points and interval arithmetic. For each step they bounded its average length over a cell by the square root of the average of its square. That bound can be found in closed form, because the squared length is a polynomial in the gaps and heights.The second-moment bound is Jensen’s inequality for the square root: the average of a square root is at most the square root of the average. For a length L with average m and variance v, the bound √(m² + v) exceeds m by about v/2m when v is small. It is too large by roughly the variance of the step’s length divided by twice its average, so it is close only where the length varies little, which means on small cells. With sixteen trillion cells, Dong and Cao proved β ≤ 0.8810.

Why sixteen trillion cells?

Small cells let each cell’s order fit its blocks more closely, and they bring the second-moment bound closer to the true average.

The paper’s program measured the two effects on random blocks of six points in Dong and Cao’s cells.The program simulated 4·10⁶ blocks in Dong and Cao’s cells, as the paper reads their setting: their cell bound averages 0.88093 ± 0.00012 over the sampled cells, matching their 0.8810; the paths of their cells’ orders 0.87467 ± 0.00012; the shortest orders of the same blocks 0.87418 ± 0.00012, where Dong and Cao report 0.87426. On the same blocks the difference is 0.000493 ± 0.000001. This is a reading of their cells and their bound, not a repetition of their proof. Dong and Cao’s bound, 0.8810, lies 0.0068 above the average path of the same blocks in their shortest orders. Of that difference, 0.0005 comes from choosing one order per cell and the other 0.0063 from the second-moment bound (Figure 6). A bound that stays close on large cells could succeed with far fewer cells.

Chords on a fine mesh

Drawn against one of the gaps, a step’s length bends upward. Join two points of such a convex curve with a straight chord, and the chord lies above the curve between them. Average the curve and the chord over the same stretch, with any weighting, and the chord’s average is the larger. Since the chord is straight, its average is simply its height at the average gap. Edmundson proved this chord bound in 1957 and Madansky in 1959, the year of the zigzag, and it became a standard tool for planning under uncertainty.

One chord is crude. Take one step, between two points 0.2 apart in height, and let its gap range over the paper’s narrowest interval, from 0 to 3/8 of the average gap. A single chord across that interval gives a bound 9.5% too large, where the second-moment bound is 2.9% too large. Cut the interval into a mesh of small pieces, with a chord across each, and the chords hug the curve. On a cell five times as wide, the second-moment bound for the same step is 19% too large, and the paper’s mesh gives a chord bound 0.0007% too large (Figure 7).If f is convex on an interval, its average over any distribution on the interval is at most the height of the chord at the mean. Huang, Ziemba and Ben-Tal (1977) and Kall and Wallace (1994) treat it as standard in stochastic programming. The paper applies it one variable at a time, which is allowed because within a cell the gaps and the heights are independent and the length is convex in each of them. Its mesh cuts the gaps into pieces 1/128 of the average gap, weighted by the exponential distribution, and each height band into 64 pieces. On the narrowest interval itself, the chords on the paper’s mesh are 0.0046% too large. The separate steps are not new: Yu and Carlsson bounded one integral with chords, and Carlsson’s program of 2024 is designed to take for each cell the order with the least bound, using convexity on a grid and bounding a path on a cell by its largest corner value. The paper adds the combination and its scheme of integer arithmetic.

A finer mesh costs more work only once, in preparing the step bounds; it adds nothing to the work of each cell. A step’s bound depends on its cell through two things only: how many of the gaps it spans fall in each interval, and how far apart the bands of its two points are. For blocks of ten points that is a table of 4,284 entries, which serves every cell however fine the mesh.

Dong and Cao’s conclusion had named finer partitions and larger blocks among the ways forward. Because chords stay close on wide cells, the paper makes its cells coarser instead: four intervals for each gap and six bands for the heights.The boundaries are given in the appendix. They and the strip heights were chosen by simulation, which affects how good the bound is but not whether it holds. For blocks of six points that makes about 48 million cells, and the bound is already 0.8789, below Dong and Cao’s 0.8810. Orders chosen on coarse cells fit their blocks less well. The bound is now 0.0046 above the average of the shortest paths, nearly all of it from the orders, while the chords add less than 0.00001 (Figure 6).

Sixteen trillion cells again

Larger blocks leave more room for a good order, and the cells saved can pay for them. Each extra point adds a gap, which can fall in any of four intervals, and a height, which can fall in any of six bands, so it multiplies the number of cells by 24. Blocks of ten points have about sixteen trillion cells, as many as Dong and Cao used for six, although each cell now takes more work. To see a tour made of such blocks, redraw Figure 2 in blocks of ten. On blocks of ten points, in strips of height 2.2, the computation gives the paper’s main result: β < 0.8618 (Figure 8).The bounds for blocks of six to ten points, each rounded up, are 0.878821, 0.872869, 0.868076, 0.864608 and 0.861716, at strip heights 2, 2, 2.1, 2.1 and 2.2. The last is 0.861715646305 to twelve places.

The method also has a floor, as Steinerberger already noted in 2015. No choice of orders can do better than the shortest order in every block, and for blocks of ten points simulations put that at about 0.8540, within 0.008 of the bound.The paper simulated 40 million blocks for every size from six to eleven points, the same blocks at each of three or four strip heights. At the best height, with standard errors of at most 0.00004, they give 0.8743, 0.8671, 0.8618, 0.8574, 0.8540 and 0.8509; the 0.8618 for eight points shares its digits with the main result by chance. These heights need not be the best for the bound itself. Each bound lies above the shortest orders at its own strip height, and less than 0.00001 of that distance comes from the mesh, the truncation and the rounding. Gaudio and Guan discuss the floor too; their estimates go down to blocks of nine points, and the paper’s blocks of ten, in taller strips, go below them. Yu and Carlsson’s repositories show simulated values of the shortest order for blocks of four to ten points. Nearly all of the distance comes from making each cell share an order. Larger blocks lower the floor only slowly. Gaudio and Guan let a point near the edge of a strip be visited from the next strip, and their simulations put such tours at about 0.850 for blocks of nine points, below the 0.8574 of the shortest order within strips. The paper’s last section asks whether Gaudio and Guan’s bound for such tours can be evaluated rigorously for blocks of six points or more.Gaudio and Guan’s 0.850 is for blocks of nine points with crossovers, in strips of height 2, from a heuristic construction of the tour. The paper’s other question is whether a partition like Yu and Carlsson’s decision tree would do better for blocks of eight to ten points. Even these floors lie well above the 0.7124 that experiments give for β.

Rounded towards a larger total

The last step of the paper’s proof adds up a number for each cell, sixteen trillion of them for blocks of ten points, and divides the total by a known large number to give the bound on β. Done in floating point, the sum would need a bound on every rounding error. Instead, the paper sets out the sum step by step in a recipe that works with integers. The recipe replaces every real number by an integer on a fixed scale and rounds every division and square root in the direction that makes the total larger, so the total can only come out too large, and no bound on rounding errors is needed.For blocks of ten points the total is a sum of 262,144 cell sums, one for each choice of gap intervals, each over the 60,466,176 choices of height bands. The bound is h₂A₀ / (6^k+1 · 2³² · k · h₁) for blocks of k + 1 points and strips of height h₁/h₂, where A₀ is the total and 2³² is the scale of the table’s entries. Probabilities and weights are held at the scale 2⁴⁸, and powers of the exponential at 2⁶². The cheapest order in a cell is found by the dynamic program of Held and Karp and of Bellman (1962). Three identities save time without changing a number: a block read from its other end, heights turned upside down, and inner paths shared between cells. The first two are among the symmetries that Dong and Cao use.

We execute the recipe separately in C, Rust and Python programs sharing no code, to minimise the probability of error. Because the arithmetic is exact, any correct program must reach exactly the same total, which they do. That agreement rules out a slip in any one program; it cannot catch a misreading of the recipe that all three share. The fastest program takes slightly over an hour on a desktop computer.

The proof assistant Lean then recomputes the totals for blocks of six to ten points a fourth time, from definitions transcribed from the recipe. Its evaluation runs as compiled code that Lean’s own proof checker does not check, and it confirms the arithmetic only: the inequalities that turn the tour’s average length into the recipe’s sum are in the paper, not in Lean.

The paper’s GitHub repository holds the programs and their results, and the sum for blocks of six points is small enough to check in a browser!

0.8618, with an asterisk

The paper exists as a preprint, posted on GitHub, and has not been refereed. Its inequalities reduce the tour’s average length to the recipe’s sum, and they rest on one theorem, Yu and Carlsson’s bound for β from a block’s average path.

Damek Davis, Paata Ivanisvili and Terence Tao maintain a list of Optimisation Constants in Mathematics, which includes the upper and lower bounds for the Beardwood–Halton–Hammersley constant. When I asked for the new bound to be added, I wrote: “None of this has been refereed, so I have marked the bound with an asterisk.” On 18 October the list took the result, as “0.8810 (0.8618*)”, with the new bound marked unverified.The list, Optimization constants in mathematics, began with a post on Tao’s blog on 22 January 2026; the salesman’s constant is its constant 12. Its page gives 0.92117 from 1959, Steinerberger’s improvement, Yu and Carlsson’s preprint value of 0.90304, Dong and Cao’s 0.8810 and the paper’s 0.8618*, and the lower bounds 0.625, 0.6268 and 0.6277. Its news entry reads “improved upper bound (unverified)”. The pull request is teorth/optimizationproblems#222.

@misc{okeefe2026salesman,
  author = {Devin O'Keefe},
  title  = {The travelling salesman’s constant},
  year   = {2026},
  url    = {https://devinokeefe.com/salesman-constant/},
  note   = {Explainer for the paper An upper bound for the Euclidean travelling salesman constant}
}