Skip to content
Preprint

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

Oct 2026 · 1 citation · ⚡ 1 influential · 48 references
Computer Science Mathematics

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 $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)\approx 0.1839$. This matches the worst-case enumeration exponent of Hanrot-Stehl\'{e} 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: \begin{align} 0.1464 \approx \frac{2-\sqrt{2}}{4}\leq c<0.1474. \end{align} 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 \geq 1/8$, discussed by Nguyen and Hanrot-Stehl\'{e}, 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 \leq 1/(4\sqrt{e}) \approx 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.

View source

Similar papers

Preprint Oct 2026

The Golomb--Welch conjecture for arbitrary centre sets

We prove that for all $n\ge3$ and $r\ge2$, the Lee ball $B_n(r)$ does not tile $\Z^n$ by translations, resolving the Golomb--Welch conjecture for arbitrary centre sets and completing the existence classification of perfect Lee codes in $\Z^n$. The proof combines translation-invariant averaging, boundary contact identit...

Bo-Cong Chen, Jing Huang, Gao-Jun Luo · 0 citations
Sep 2026

Smooth Sailing through Spherical Shells: Provable Random-Lattice Sieving in Time 20.292n

In an attempt to close the gap between the best provable and heuristic algorithms for hard lattice problems, such as the shortest (SVP) and closest vector problem (CVP), we analyze lattice sieving on Haar-random unimodular lattices. With well-chosen modifications to heuristic sieving, we show that the heuristic assumpt...

Emmanouil Doulgerakis, Thijs Laarhoven · 0 citations
Preprint Oct 2026

Sharp Asymptotics for the Solvability Probability of Random Stable Roommates

For even $n$, let $P_n$ be the probability that independent uniform strict preference lists on $n$ participants admit a stable perfect matching. We prove \[ P_n\sim\frac{e\,2^{1/4}\Gamma(3/4)}{\sqrt\pi}\,n^{-1/4}. \] This establishes Mertens's conjectured exponent of decay, with a leading constant different from his or...

Caden Young, Ian Studebaker · 0 citations
Review Oct 2026

Sparse coloring for isosceles-free grids: an AI-assisted proof case study

We study the largest size $C(n)$ of a subset of the $n\times n$ integer grid containing no isosceles triple, including equally spaced collinear triples. We prove $C(n)=\Omega\left(n\sqrt{\log\log n/\log n}\right)$ by applying the sparse hypergraph coloring theorem of Cooper and Mubayi. Elementary geometry and primitive...

Yu-Kai Song · 0 citations
Preprint Oct 2026

Extended-range percolation on lattices with cubic and non-compact neighborhoods in three dimensions

Using MC simulations based on an efficient single-cluster growth algorithm, we investigate two types of three-dimensional extended-range percolation models, namely cubic and complex (non-compact) neighborhoods. We obtain high-precision percolation thresholds $p_c$ for approximately 100 distinct structures and further e...

Zhe Zhang, Yuxuan Fan, Yang Yang et al. · 0 citations
Preprint Oct 2026

Explicit upper bounds on the threshold of one-dimensional long-range percolation

We study bond percolation on the one-dimensional lattice in which two sites at distance $r$ are connected with probability $p_r=C/r^{1+\sigma}$, where $0<\sigma<1$. An infinite cluster exists if $C$ exceeds a critical value $C_c(\sigma)$, which is not known exactly: the available results are the lower bound of Schulman...

Guy Amit · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.