Oct 2026· 1 citation· ⚡ 1 influential· 48 references
Computer ScienceMathematics
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.
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...
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...
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...
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...
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
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.