A Uniform Random-Lattice Tail Bound for the SVP Kissing-Profile Parameter

A recent SICOMP paper on classical and quantum algorithms for the shortest vector problem introduced a lattice-dependent parameter $\gamma (L)$, bounded universally in the exponential sense by $2^{0.402n+o(n)}$, and conjectured that this parameter is $2^{o(n)}$ for most lattices. We prove the Haar–Siegel random-lattice version in a stronger, dimension-uniform form. Let $X_n={\mathrm{SL}}_n(\mathbb{R})\mathrm{/}{\mathrm{SL}}_n(\mathbb{Z})$, let ${\mu }_n$ be its invariant probability measure, and let $\gamma (L)={\sup }_{r\ge 1}{N}_L(r{\lambda }_1(L))\mathrm{/}{r}^n$, where $N_L(R)$ counts nonzero vectors of $L$ of Euclidean norm at most $R$. For every $n\ge 3$ and every $T>0$, $${\mu }_n\{L\in X_n:\gamma (L)>T\}\le C{T}^{-1}$$ with an absolute constant $C$. Consequently, for every sequence $a_n\to \mathrm{\infty }$, $\gamma (L_n)\le a_n$ with ${\mu }_n$-probability tending to one; in particular $\gamma (L_n)=2^{o(n)}$ with high probability. In the product model of independent Haar–Siegel lattices, $\gamma (L_n)\le \exp (\sqrt{n})$ eventually almost surely. The proof uses Rogers’s second-moment estimate only through a dyadic self-normalization argument around the random scale ${\lambda }_1(L)$.