Asymptotics of Random-Lattice Enumeration: Beyond HKZ via Dense Sublattices
Abstract
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 ncn+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)≈ 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 ≈ (2−√2)/4≤ 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 ≥ 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 nn/8 + o(n). Combining dual HKZ on this sublattice with HKZ on its quotient gives a basis with c ≤ 1/(4√e) ≈ 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 n0.0892 n + o(n) for arbitrary targets.
Related
- Normal and Lognormal Asymptotics for Lattice-Point Counts in Random Translates of High-Dimensional Balls
- Universal Asymptotics and Exact Enumeration of Eulerian Maps
- Weighted lattice point enumeration in lecture hall order polytopes
- Certain Standard Young Tableaux of Non-Classical Shapes and Lattice Path Enumeration
- The Last Isolated Vertex in Random-Order Uncovering of Cycles and Their Powers: Exact Enumeration and Weibull Limits
BibTeX
@misc{laarhoven2026asymptotics,
title = {{Asymptotics of Random-Lattice Enumeration: Beyond HKZ via Dense Sublattices}},
author = {Thijs Laarhoven},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15265},
eprint = {2610.15265},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15265},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Asymptotics of Random-Lattice Enumeration: Beyond HKZ via Dense Sublattices
AU - Thijs Laarhoven
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.15265
UR - https://arxiv.org/abs/2610.15265
AB - 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)≈ 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 ≈ (2−√2)/4≤ 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 ≥ 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 ≤ 1/(4√e) ≈ 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.
ER -