Let D be a “generic” distribution on the set of bases of R^n, and let D^circ denote the corresponding output distribution of LLL or LLL-SP. Its probability density function is bounded above by a constant C. Bounded output-density conjecture. For every such D, the probability density function of D^circ is bounded from above by a constant C that depends only on n. Such a bound would help establish an upper bound on the average root-Hermite factor away from the worst case. The conjecture is motivated by the steady-state analysis of the simplified sandpile process, but the source gives no proof or resolution for LLL or LLL-SP.

Bounded output-density conjecture for LLL and LLL-SP

From papers

Let $\mathcal{D}$ be a “generic” distribution on the set of bases of $\mathbb{R}^n$ , and let $\mathcal{D}^{\circ}$ denote the corresponding output distribution of LLL or LLL-SP. Its probability density function is bounded above by a constant $C$ .

Bounded output-density conjecture. For every such $\mathcal{D}$ , the probability density function of $\mathcal{D}^{\circ}$ is bounded from above by a constant $C$ that depends only on $n$ .

Such a bound would help establish an upper bound on the average root-Hermite factor away from the worst case. The conjecture is motivated by the steady-state analysis of the simplified sandpile process, but the source gives no proof or resolution for LLL or LLL-SP.

Progress summary

Open

The conjecture remains unresolved: only a related simplified model is covered, and no proof or counterexample for LLL or LLL-SP was found.

The conjecture asserts that the output density of LLL or LLL-SP, starting from any “generic” distribution $\mathcal{D}$ of bases in $\mathbb{R}^n$ , is bounded by a constant depending only on $n$ . The retrieved paper presents this as Conjecture 4 and explicitly leaves it unresolved.

Known results

The analogous density and average-case bounds are established for the simplified stochastic sandpile model SSP, but not for LLL or LLL-SP.
Extending the argument to LLL requires additional conjectural control of the LLL dynamics, including Conjecture 2.

Current status (as of August 2026): The bounded output-density conjecture for LLL and LLL-SP remains open; the related SSP result is known, but no proof, counterexample, or subsequent verification for the stated conjecture was found.

Sources

ar5iv.labs.arxiv.org

Equivalent formulations 1

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

The bounded output-density conjecture for LLL and LLL-SP
Let $\mathcal{D}$ be a distribution on the set of bases of $\mathbb{R}^n$ , and let $\mathcal{D}^\circ$ denote the corresponding output distribution of LLL or LLL-SP. Bounded output-density conjecture. If $\mathcal{D}$ is generic, then the probability density function of $\mathcal{D}^\circ$ is bounded above by a constant $C$ depending only on $n$ . Such a bound would help establish that the average root-Hermite factor is bounded strictly away from the worst-case value, but the conjecture remains open.
source: Jintai Ding, Seungki Kim, Tsuyoshi Takagi and Yuntao Wang, “LLL and stochastic sandpile models”, arXiv:1804.03285 (2020).

Sources & referencesView supporting material

Primary source

Jintai Ding, Seungki Kim, Tsuyoshi Takagi, Yuntao Wang and Bo-Yin Yang, “A physical study of the LLL algorithm”, arXiv:2106.02158 (2022).

1 week ago

The published conjecture leaves “generic” mathematically undefined. Under every concrete input-regularity condition stated in the source, the proposed bound is false: it fails even for smooth, strictly positive, full-support input densities arbitrarily close in total variation to any prescribed background distribution. An unspecified additional restriction on “generic” could define a different conjecture.

Fix $n\ge2$ and a standard LLL parameter $\delta<1$ . Identify ordered bases with $\mathrm{GL}_n(\mathbb R)\subset\mathbb R^{n^2}$ . The identity basis $I_n$ is strictly LLL-reduced: all size-reduction coefficients vanish and the Lovász inequalities are strict. Therefore there is an open neighborhood $O$ of $I_n$ on which the LLL output map is exactly

T(B)=B.

Let $f_0$ be any smooth strictly positive full-support probability density, and choose any fixed $0<\eta<1$ , as small as desired. Set

f_\varepsilon(B) =(1-\eta)f_0(B) +\eta(2\pi\varepsilon^2)^{-n^2/2} \exp\!\left(-\frac{\|B-I_n\|_F^2}{2\varepsilon^2}\right).

Singular matrices have measure zero, so this is a smooth strictly positive full-support input law on bases, and

d_{\mathrm{TV}}(f_\varepsilon,f_0)\le\eta.

For every measurable $E\subset O$ , the output distribution satisfies

\mathbb P(T(B)\in E) \ge \mathbb P(B\in E) = \int_E f_\varepsilon(Y)\,dY.

Hence its output density $g_\varepsilon$ obeys $g_\varepsilon\ge f_\varepsilon$ almost everywhere on $O$ . By continuity,

\boxed{ \|g_\varepsilon\|_\infty \ge \eta(2\pi)^{-n^2/2}\varepsilon^{-n^2} \longrightarrow\infty. }

Thus no constant depending only on $n$ can bound all such output densities.

The obstruction also applies if the intended density is that of the Gram–Schmidt shape coordinates

r_i(B)=\log\frac{\|b_i^*\|}{\|b_{i+1}^*\|}, \qquad 1\le i<n.

Near $I_n$ , the derivative of $B\mapsto(r_1,\ldots,r_{n-1})$ has rank $n-1$ , since on positive diagonal bases it becomes $r_i=t_i-t_{i+1}$ . Choose a smooth probability bump of width $\varepsilon$ in these local shape coordinates and mix it into any full-support background with weight $\eta$ . Since LLL is the identity on the bump's support, the output shape density is at least $c\eta\varepsilon^{-(n-1)}$ , again unbounded.

Consequently, a valid repaired statement requires explicit quantitative anti-concentration restrictions on admissible input distributions; smoothness, full support, and arbitrarily small contamination of any reference law do not suffice.

Source: J. Ding, S. Kim, T. Takagi, Y. Wang, and B.-Y. Yang, “A physical study of the LLL algorithm,” Journal of Number Theory 244 (2023), 339–368, Conjecture 6, doi:10.1016/j.jnt.2022.09.013.

0 endorsements

Shivam Patel · 20 hours ago