Unconditional concentration of reduced-basis counts, LLL/BKZ analogues, and predicting which reduced bases LLL outputs (open problems from Kim–Venkatesh, The Behavior of Random Reduced Bases)

Kim and Venkatesh proved that for a random $n$-dimensional lattice $L$, the number $N(L)$ of Siegel-reduced bases with fixed parameter $T$ concentrates sharply: its mean grows like $T^{n^3/6}$ up to factors $\exp(o(n^3))$, and — assuming the Riemann hypothesis for the Riemann zeta function, the sole conditional input, used only in a bound for ratios of $\zeta$ near $\mathrm{Re}(s)=1$ — its standard deviation is at most $\exp(-a n^2)$ times its mean. They also showed that a uniformly random reduced basis is, with probability tending to 1, nearly as bad as the worst case, whereas LLL in practice outputs bases with short-vector quality about $(1.02)^n$ against the worst-case $(1.075)^n$: the algorithm selects unusually good bases. The paper left four concrete issues open, which together form the linked problem posed below: (1) remove the Riemann hypothesis from the concentration theorem; (2) extend the variance/concentration results to the reduction notions that algorithms actually output — the mean-growth analogue for LLL-reduced bases is known, but not the concentration, and nothing is established for BKZ-type block reduction (BKZ: block Korkine–Zolotarev, a blockwise strengthening of LLL); (3) the problem posed in the paper's introduction: determine a reliable heuristic that, given a reduced basis, predicts how frequently it occurs as the output of LLL-reduction on random input bases of the same lattice; and (4) quantify the 'dark' reduced bases that are essentially never output. No resolution of any component is known to date: the concentration theorem is still described as Riemann-hypothesis-conditional in the recent follow-up literature, and the statistical-physics line studying LLL's behavior remains heuristic, with its own open conjectures.

Background

A lattice $L\subset\mathbb{R}^n$ of covolume 1 (determinant 1) is the set of integer linear combinations of a basis $\mathcal{B}=(x_1,\dots,x_n)$ of $\mathbb{R}^n$. A classical theorem of C. L. Siegel gives a unique $\mathrm{SL}_n(\mathbb{R})$-invariant probability measure $\mu_n$ on the space $\mathcal{L}_n$ of such lattices, so 'a random lattice' is well defined. Write $x_i^*$ for the Gram–Schmidt projection of $x_i$ onto the orthogonal complement of the span of $x_{i+1},\dots,x_n$, and $x_i=x_i^*+\sum_{j>i}n_{ji}x_j^*$ (the expansion is in the Gram–Schmidt vectors). A basis is Siegel-reduced with parameter $T>1$ if $\|x_i^*\|\ge T^{-1}\|x_{i+1}^*\|$ and $|n_{ji}|\le 1/2$ for all $i$; then the last vector satisfies $\|x_n\|\le T^{(n-1)/2}$. (The indexing is reversed relative to the LLL literature: $x_n$ is the vector that reduction guarantees to be short.) The LLL algorithm of Lenstra, Lenstra and Lovász outputs, in polynomial time, bases satisfying a slightly stronger condition, so worst-case analysis gives $\|x_n\|\le(2/\sqrt{3})^{(n-1)/2}$, a per-dimension factor $(4/3)^{1/4}\approx 1.075$ when lengths are normalized by the covolume (the per-dimension quality of the short output vector is customarily reported as the root Hermite factor). Experiment — most systematically Nguyen and Stehlé's 'LLL on the average' — shows LLL in practice outputs $\|x_n\|\approx(1.02)^n$, far better than $1.075^n$, essentially independently of the input distribution. The same gap, and the empirical 'geometric series assumption' (GSA) that the Gram–Schmidt norms of an output basis decay nearly geometrically, pervade blockwise BKZ reduction — block Korkine–Zolotarev reduction, which strengthens LLL by applying exact reduction to projected blocks of consecutive basis vectors of bounded size, and which is the cryptanalytic workhorse (Chen–Nguyen) — whose security estimates rest on these unexplained regularities.

Kim and Venkatesh asked what a uniformly random reduced basis looks like, i.e. whether LLL's good practical behavior simply reflects the statistics of reduced bases. Siegel's mean value theorem (1945) computes averages of lattice-point counting functions over $\mathcal{L}_n$, and Schmidt (1960) computed the variance of the number of lattice points in a fixed ball, the $n=2$ instance of this circle of ideas; Kim–Venkatesh carried out the high-dimensional analogue for $N(L)$, the number of Siegel-reduced bases of $L$ with parameter $T$. Their Theorem 1.1 states: (i) $\lim_n\frac{1}{n^3\log T}\log\mathbb{E}_{\mu_n}N(L)=1/6$; (ii) assuming the Riemann hypothesis for $\zeta(s)$, the $\mu_n$-standard deviation of $N(L)$ is at most $\exp(-a n^2)$ times its mean; (iii) for a basis chosen uniformly at random from the set of all Siegel-reduced bases of covolume-1 lattices, the ratio $\|x_n\|/T^{(n-1)/2}$ concentrates at 1. Part (ii) is what makes the natural two-stage model — first a random lattice, then a uniform random reduced basis of it — equivalent to the one-stage model of a random reduced basis. Technically, $L\mapsto N(L)$ is a pseudo-Eisenstein series on the quotient $\mathrm{SL}_n(\mathbb{Z})\backslash\mathrm{SL}_n(\mathbb{R})$ (a sum over the discrete group of translates of a function on the space of bases), and its variance is computed from the spectral theory of the standard Eisenstein series — automorphic forms on that quotient whose constant terms are indexed by partitions of $n$; the Riemann hypothesis enters only in Lemma 6.2 of the paper, a bound for ratios $\zeta(1-z)/\zeta(1+z)$ near the line $\mathrm{Re}(s)=1$, used when the contour integration passes the pole of $\zeta$. The authors' footnote to that lemma anticipates that this use of the hypothesis can be removed by a more elaborate contour argument.

Part (iii) says a random reduced basis is nearly as bad as the worst case: LLL's good output is a property of the algorithm, not of reduced bases in general. Since almost all reduced bases are bad and LLL almost always outputs a good one, the algorithm 'selects' unusually good bases. Numerics reported in the first author's thesis suggest a very large number of 'dark' reduced bases that are practically never selected, and that the likelihood of a reduced basis $(x_i)_{1\le i\le n}$ being chosen by LLL is inversely related to its 'energy' $\prod_{i=1}^{n}\|x_i\wedge x_{i+1}\wedge\cdots\wedge x_n\|$, the product of the covolumes of the trailing sublattices spanned by $x_i,\dots,x_n$ (for $i=n$ the factor is $\|x_n\|$). The same thesis carries out the analogue of (i) for LLL-reduced bases: the mean count again follows the cubic growth law. What remains missing — the variance bound for LLL, anything for BKZ, the frequency heuristic, and the dark-bases quantification — is the subject of the problem stated below.

Problem Statement

The four linked unresolved tasks left by Kim–Venkatesh, with the common scientific objective of a complete, unconditional and algorithm-relevant statistical theory of the reduced bases of random lattices, together with a predictive account of which of them lattice-reduction algorithms output. Throughout, $\mu_n$ is the $\mathrm{SL}_n(\mathbb{R})$-invariant probability measure on the space of covolume-1 lattices in $\mathbb{R}^n$, and 'Siegel-reduced with parameter $T$' is as defined in the Background.

(1) Unconditional concentration. Prove, without any unproved hypothesis, that the $\mu_n$-standard deviation of $N(L)$ — the number of Siegel-reduced bases with parameter $T$ of a random covolume-1 lattice $L$ — is at most $\exp(-a n^2)$ times its mean, for some $a=a(T)>0$; the source establishes this only under the Riemann hypothesis, which it uses solely in Lemma 6.2 (a bound for ratios $\zeta(1-z)/\zeta(1+z)$ near $\mathrm{Re}(s)=1$ at a contour-shift step).

(2) Algorithm-relevant reduction notions. For LLL-reduced bases — where the analogue of the mean-growth result $\lim_n\frac{1}{n^3\log T}\log\mathbb{E}N_n=1/6$ is already known ($N_n$ denoting the number of LLL-reduced bases of a random covolume-1 lattice, in the source's notation) — establish the exponential-concentration analogue (equivalently, the equivalence between the two-stage model 'random lattice, then uniform random LLL-reduced basis' and the one-stage model of a random LLL-reduced basis); and, for BKZ-type block reduction, establish the analogous mean-growth result and the analogous exponential-concentration result, for which no such results are known. These are three independently refutable sub-claims — the LLL concentration statement, the BKZ mean-growth statement, and the BKZ concentration statement — and each may be settled either by proof or by an explicit counterexample refuting that specific statement; refuting any one of them settles that sub-claim but leaves the others open, so (2) counts as complete only when all three sub-claims are settled, the LLL strand and the BKZ strand alike.

(3) The posed Problem. Determine a reliable heuristic that, given a reduced basis $\mathcal{B}$, predicts how frequently it occurs as the output of LLL-reduction when 'random' input bases of the lattice $\mathbb{Z}\mathcal{B}$ are chosen. The source itself calls this 'not quite well-defined', so a solution must make the model explicit — the input distribution on input bases, the precise frequency notion, and a quantitative accuracy criterion under which 'reliable' is assessed. The conjecture from the thesis numerics, that the likelihood is inversely related to the energy $\prod_{i=1}^{n}\|x_i\wedge x_{i+1}\wedge\cdots\wedge x_n\|$, is a candidate to confirm, refine, or refute, not the definition of the task.

(4) Dark bases. Quantify and characterize the 'dark' reduced bases — those that exist but are produced with negligible frequency by practical reduction algorithms — for example by a measure-theoretic or algorithmic description of the set of reduced bases selected with vanishing frequency as the dimension grows.

The four components are scientifically linked: the selection phenomenon (3)–(4) presupposes the counting statistics (1)–(2), which are their rigorous foundation. The source's fifth stated direction, a broader theory of automorphic analysis on $\mathrm{SL}_n(\mathbb{Z})\backslash\mathrm{SL}_n(\mathbb{R})$ as $n\to\infty$, is separate from the four linked components above.

References

1. Seungki Kim and Akshay Venkatesh, The Behavior of Random Reduced Bases, International Mathematics Research Notices 2018(20), 6442–6480 (published online 26 April 2017), DOI 10.1093/imrn/rnx074, https://doi.org/10.1093/imrn/rnx074. Full text available via the preprint arXiv:1608.00767, https://arxiv.org/abs/1608.00767.
2. Seungki Kim, On the shape of a high-dimensional random lattice, PhD thesis, Stanford University, 2015. No DOI; cited as ref. [6] of arXiv:1608.00767 and ref. [17] of arXiv:2106.02158. Access point: Stanford Libraries' catalog, https://searchworks.stanford.edu
3. A. K. Lenstra, H. W. Lenstra Jr. and L. Lovász, Factoring polynomials with rational coefficients, Mathematische Annalen 261 (1982), 515–534, DOI 10.1007/BF01457454, https://doi.org/10.1007/BF01457454
4. Phong Q. Nguyen and Damien Stehlé, LLL on the Average, in Algorithmic Number Theory (ANTS 2006), Lecture Notes in Computer Science 4076, Springer, 2006, pp. 238–256, DOI 10.1007/11792086_18, https://doi.org/10.1007/11792086_18
5. Yuanmi Chen and Phong Q. Nguyen, BKZ 2.0: Better Lattice Security Estimates, in Advances in Cryptology — ASIACRYPT 2011, Lecture Notes in Computer Science 7073, Springer, 2011, pp. 1–20, DOI 10.1007/978-3-642-25385-0_1, https://doi.org/10.1007/978-3-642-25385-0_1
6. Carl Ludwig Siegel, A Mean Value Theorem in Geometry of Numbers, Annals of Mathematics (2) 46 (1945), 340–347, DOI 10.2307/1969027, https://doi.org/10.2307/1969027
7. Wolfgang M. Schmidt, A metrical theorem in geometry of numbers, Transactions of the American Mathematical Society 95 (1960), 516–529, DOI 10.1090/S0002-9947-1960-0117222-9, https://doi.org/10.1090/S0002-9947-1960-0117222-9
8. Ali Akhavi, Jean-François Marckert and Alain Rouault, On the reduction of a random basis, ESAIM: Probability and Statistics 13 (2009), 437–458, DOI 10.1051/ps:2008012, https://doi.org/10.1051/ps:2008012; preprint arXiv:math/0604331, https://arxiv.org/abs/math/0604331
9. Jintai Ding, Seungki Kim, Tsuyoshi Takagi and Yuntao Wang, LLL and stochastic sandpile models, arXiv:1804.03285 (2018), https://arxiv.org/abs/1804.03285
10. Jintai Ding, Seungki Kim, Tsuyoshi Takagi, Yuntao Wang and Bo-Yin Yang, A physical study of the LLL algorithm, Journal of Number Theory 244 (2023), 339–368, DOI 10.1016/j.jnt.2022.09.013, https://doi.org/10.1016/j.jnt.2022.09.013; preprint arXiv:2106.02158, https://arxiv.org/abs/2106.02158
11. Tamar Lichter Blanks and Stephen D. Miller, Generating Cryptographically-Strong Random Lattice Bases and Recognizing Rotations of $\mathbb{Z}^n$, in Post-Quantum Cryptography (PKC 2021), Lecture Notes in Computer Science, Springer, 2021, pp. 319–338, DOI 10.1007/978-3-030-81293-5_17, https://doi.org/10.1007/978-3-030-81293-5_17; preprint arXiv:2102.06344, https://arxiv.org/abs/2102.06344
12. Seungki Kim, Mean value formulas on sublattices and flags of the random lattice, Journal of Number Theory 241 (2022), 330–351, DOI 10.1016/j.jnt.2022.03.013, https://doi.org/10.1016/j.jnt.2022.03.013; preprint arXiv:2005.10874, https://arxiv.org/abs/2005.10874
13. Seungki Kim and Mishel Skenderi, Higher-rank pointwise discrepancy bounds and logarithm laws for generic lattices, Acta Arithmetica 205(3) (2022), 227–249, DOI 10.4064/aa220325-17-8, https://doi.org/10.4064/aa220325-17-8; preprint arXiv:2107.12510, https://arxiv.org/abs/2107.12510
14. Seokho Jin and Seungki Kim, A truncated inner product formula in the geometry of numbers, arXiv:2503.20010 (2025), https://arxiv.org/abs/2503.20010
15. Koen de Boer, Aurel Page, Radu Toma and Benjamin Wesolowski, Average Hardness of SIVP for Module Lattices of Fixed Rank, in Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC 2026), 2026, pp. 814–822, DOI 10.1145/3798129.3800796, https://doi.org/10.1145/3798129.3800796; preprint arXiv:2511.13659, https://arxiv.org/abs/2511.13659