TejasviTomar
October 2026 · Preprint

A lower bound of 0.6463 for the Beardwood–Halton–Hammersley constant

Tejasvi Singh Tomar

In plain words

Scatter n points at random in a square of side 1 and join them by the shortest round trip, the travelling salesman problem. In 1959 Beardwood, Halton and Hammersley proved that its length grows like a fixed constant times the square root of n, and that this constant is at least 0.625. Its exact value is unknown, and experiments suggest about 0.71. After small improvements, Dong and Cao proved 0.6421 in 2026, using integrals over small clusters of points. Bounding three of these integrals more tightly by a rigorous computation raises the proved bound to 0.6463.

Abstract

Let β be the constant of the Beardwood–Halton–Hammersley theorem: the shortest tour through n independent uniform random points in the unit square has length asymptotic to β√n almost surely. Dong and Cao proved β ≥ 0.6421. They show that β ≥ 5/8 + C3 + … + CK for every K, where Ck is an integral over configurations of k points in the plane that form a connected graph when points at distance at most 1 are joined, and they bound C3, C4 and C5 from below on a uniform grid of boxes. We bound the same three integrals more tightly and prove β ≥ 0.6463. On a box of configurations we bound the area of the union of the unit disks centred at the points by its first-order Taylor polynomial plus a remainder controlled by the angular motion of the vertices of the union, and we average this bound over the box. Boxes on which the graph varies, boxes that cross the boundary of the symmetry domain and boxes in which two points can coincide receive separate bounds. An adaptive bisection chooses the boxes, and a checker in ball arithmetic recomputes the bound on every box to which the search program assigns a nonzero value. It certifies C3 ≥ 0.0117130195, C4 ≥ 0.0063707166 and C5 ≥ 0.0032174604.

Two clusters of overlapping circles on white. Left: three circles centred on the corners of a magenta triangle, their union shaded light teal with a black outline and yellow dots where the outline passes from one circle to the next. Right: five circles in a chain from upper left to lower right, shaded the same way, with magenta lines joining nearby centres into a path that ends in a triangle, small white boxes around three of the centres (two squares, the larger around the top centre, and a narrow upright rectangle), a short horizontal bar at the lower right centre, and a faint grey halo of many thin outlines along the top, left and right edges of the union, widest around the top circle.
Illustration of two boxes of the certificate, one for C₃ (left) and one for C₅ (right), at the same scale. The first point is fixed at the origin, the second moves along a short horizontal segment and the others move in the small white rectangles (the box for C₃ is too small to see). For the configuration at the centre of each box, light teal shows the union of the unit disks around the points, whose area A enters the integrand g(G)·A^(−(k−1/2)) of C_k, with the unit circles in teal and, in magenta, the graph G that joins points at distance at most 1. The large yellow dots are the vertices of this union, where two circles meet on its boundary. The thin grey curves and small yellow dots are the boundaries and vertices of the unions for 60 random configurations from the same box (visible on the right): the paper bounds A on a box from above by its first-order Taylor polynomial at the centre plus a remainder that adds up, over these vertices, the displacement of the two centres times a bound on the angle that the vertex sweeps. Both boxes come from the sample of leaves in the repository, the one with the largest certified contribution for C₃ and, among those on which g is constant, for C₅.