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

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. The programs and logs are archived at doi:10.5281/zenodo.23524862 and available at github.com/tejasvi/bhh-constant-bound.