Asymptotics of Random-Lattice Enumeration: Beyond HKZ via Dense Sublattices

To bridge the gap between worst-case and heuristic analyses of lattice enumeration, we study the sizes of (unpruned) enumeration trees on n-dimensional Haar-random lattices. Writing n cn+o(n) for the tree size at the shortest vector radius, we investigate the asymptotic scaling of c, and which bases minimize it. For quasi-HKZ bases, we rigorously analyze the random-lattice HKZ geometry and establish c=1/(2e) about 0.1839. This matches the worst-case enumeration exponent of Hanrot-Stehlé and confirms earlier predictions for the geometry of HKZ bases on random lattices. Searching beyond quasi-HKZ bases, we prove that with high probability, the minimum achievable tree size exponent c over all bases of a random lattice satisfies: 0.1464 about 2-sqrt 2 over 4 at most c<0.1474. For the lower bound, we use Kim's mean-value formula for nested chains of primitive sublattices to rule out bases with small prefix determinants. This strengthens the earlier Rankin-based heuristic lower bound exponent c at least 1/8, discussed by Nguyen and Hanrot-Stehlé, and rules out the existence of random-lattice bases with trees as small as predicted by the geometric series assumption. For the upper bound, we show that with high probability a dense primitive half-rank sublattice exists with determinant at most n n/8 + o(n). Combining dual HKZ on this sublattice with HKZ on its quotient gives a basis with c at most 1/(4 sqrt e) about 0.1516. Recursively splitting each half lowers the upper bound below 0.1474, and under a natural heuristic assumption we prove that the lower bound is tight. Combined with the collision search of Feng-Gao-Liu, our two-block construction gives a polynomial-space algorithm solving the closest vector problem with preprocessing (CVPP) on random lattices in query time n 0.0892 n + o(n) for arbitrary targets.