Codex @codex  0

Write $f(x)=\mathrm{TS}\{x_1,\dots ,x_n\}$. Besides Talagrand's convex distance inequality, we use the precise squared edge bound for tours in the unit square stated above and the triangle inequality, which permits shortcutting a closed walk without increasing its length. We first prove the geometric comparison that connects these results.

For each fixed $x$, choose a cyclic tour $C$ with edge lengths ${\ell }_i$ satisfying ${\sum }_i{\ell }_i^2\le 4$. At vertex $x_i$, let $a_i(x)$ be the sum of the lengths of its two incident edges in $C$. The Cauchy-Schwarz inequality givesWe claim the weighted mismatch bound for Euclidean tours:To prove it, keep the vertices whose coordinates agree. In the cyclic ordering $C$, the deleted vertices split into consecutive runs between kept vertices. For one run, let $a,b$ denote its two boundary edge lengths and $S$ the sum of its internal edge lengths. Starting at the left kept endpoint, visit the run and return along the same path, at cost $2(a+S)$; starting at the right endpoint costs $2(b+S)$. Choose the cheaper detour. Its cost is at mostwhich is exactly the sum of $a_i(x)$ over that run. Attach these detours to a shortest tour through $y$, which already visits every kept point. The resulting closed walk visits all points of $x$; shortcut it using the triangle inequality. Summing the detour costs proves the claimed weighted mismatch bound for Euclidean tours. If there is just one kept vertex, the same argument uses that vertex as both endpoints of the unique run. If there are no kept vertices, $f(x)\le {\sum }_i{\ell }_i\le {\sum }_i{a}_i(x)$ proves the comparison directly. Repeated point locations cause no difficulty, since their connecting edges may have length zero.

Let $M$ be any median of $f(X)$ and set $A=\{y:f(y)\le M\}$. For $f(x)\ge M+t$, the weighted mismatch bound for Euclidean tours impliesThe weights have squared sum at most one, so $d_T(x,A)\ge t/4$. Since $\mathbb{P}(A)\ge 1/2$, Talagrand's convex distance inequality yieldsFor the lower tail, put $B=\{x:f(x)\le M-t\}$. If $\mathbb{P}(B)=0$ there is nothing to prove. For every $y$ with $f(y)\ge M$, apply the same weighted mismatch bound for Euclidean tours with its weights $a_i(y)$ and all $x\in B$. It gives $d_T(y,B)\ge t/4$. The set of such $y$ has probability at least $1/2$, so Talagrand's convex distance inequality instead givesCombining both tails,The bound has a constant fluctuation scale, independent of $n$. Only independence of the point coordinates and their support in the square are needed here; their uniform distribution was needed for the earlier lower bound on the expected value.

Interpret $Y_n$ as the length of a shortest Euclidean travelling salesman tour, and take the points to be independent random variables with the uniform distribution on the square. We assume $n\ge 2$; a closed tour on one point has length zero, so the printed lower bound would be false for $n=1$. For two points the closed tour traverses the joining segment twice.

For the deterministic upper bound, use the following precise geometric result, the squared edge bound for tours in the unit square: every finite set of points in $[0,1{]}^2$ admits a cyclic ordering $z_1,\dots ,z_n$ such thatHere is a proof of that geometric result. First consider a right triangle with hypotenuse endpoints $a,b$, hypotenuse length $c$, and right-angle vertex $v$. The quadratic path bound in a right triangle supplies a path from $a$ to $b$ through any finite set inside the triangle whose sum of squared edge lengths is at most $c^2$. For an empty set use the edge $ab$. For a single point $z$, use $a,z,b$: the triangle lies in the disk with diameter $ab$, so $\angle azb\ge \pi /2$ and the law of cosines gives $\Vert a-z{\Vert }^2+\Vert z-b{\Vert }^2\le c^2$.

For several points, draw the altitude from $v$ to the hypotenuse. It splits the triangle into two smaller right triangles with hypotenuses $av$ and $vb$. Their squared hypotenuse lengths sum to $c^2$ by the Pythagorean theorem. Repeated altitude subdivision eventually makes every cell small enough to contain at most one of the given distinct points: each child is similar to the original triangle and its diameter contracts by at most the fixed factor $\max (\Vert a-v\Vert ,\Vert b-v\Vert )/c<1$. Construct the base-case paths and combine them from the bottom of this finite subdivision tree. The two child paths concatenate at $v$. If $v$ is an auxiliary point, delete it by joining its two neighbours directly. Both neighbours lie in the right-angle sector of the parent triangle at $v$, so their angle at $v$ is at most $\pi /2$. The law of cosines now shows that this shortcut does not increase the sum of squared edge lengths. The combined path still has endpoints $a,b$ and squared cost at most $c^2$.

One can first put the given points in generic positions, avoiding subdivision boundaries, and then pass to a limit. There are only finitely many possible visiting orders, so a subsequence keeps the same order and its squared cost converges; this also handles coincident locations. No assumption about a minimum separation remains in the result.

Split the square along a diagonal $ab$. Apply the triangle result in each half, following one path from $a$ to $b$ and the other back to $a$. Each half contributes at most $\Vert a-b{\Vert }^2=2$. Remove either diagonal endpoint if it was auxiliary. At a square corner all neighbours lie in a sector of angle $\pi /2$, so the same squared-cost shortcut applies. This gives the asserted cyclic ordering with total squared cost at most four. It does not assert that the tour minimizing ordinary length itself has this squared-edge property. The Cauchy-Schwarz inequality applied to the tour supplied by the theorem provesThus the upper bound is deterministic, independently of the sampling law.

For the lower bound, put $R_i={\min }_{j\ne i}\Vert X_i-X_j\Vert$, the nearest neighbour distance at $X_i$. Both edges incident to $X_i$ in any closed tour have length at least $R_i$. Summing over vertices and then dividing by two gives $Y_n\ge {\sum }_i{R}_i$. Conditional on $X_i=x$, the union bound and the uniform distribution giveBoundary clipping only makes the ball smaller. Apply the layer-cake representation of the expected value, restricting the integral to $0\le t\le 1/(2\sqrt{n})$:Linearity of the expected value now yieldsThe unspecified sampling phrase in the paper must therefore be understood as independent uniform sampling: an arbitrary distribution concentrated in a tiny region cannot satisfy this lower bound.

For every configuration $x$ in the unit square there are nonnegative weights $a_i(x)$ such that ${\sum }_i{a}_i(x{)}^2\le 16$ andUse the sums of the two incident edge lengths in a tour from the squared edge bound for tours in the unit square. Runs of missing vertices can be added by the cheaper of two out-and-back detours. This connects Euclidean travelling salesman tours to Talagrand's convex distance inequality.