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

At least 4 years old · documented by 2021

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.

Equivalent formulations 1Other wordings

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).

References

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).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed progress

The conjecture remains unproved, but a reader has proposed an unverified counterexample showing that the undefined notion of “generic” cannot by itself support the claimed bound.

Ding, Kim, Takagi, Wang, and Yang proposed the bounded output-density conjecture for LLL and LLL-SP in their statistical-physics study, motivated by average-case root-Hermite-factor bounds. The source explicitly presents it as unresolved.

Known results

The simplified stochastic sandpile model has a unique steady state and a constant average-versus-worst-case root-Hermite-factor gap (2019).
Extending the argument to LLL or LLL-SP remains obstructed by state-dependent increments, noncommuting topplings, and the unknown existence of an LLL steady state.

Posted attempt

A proposed construction concentrates a smooth, full-support input density near a strictly LLL-reduced basis, where LLL acts as the identity, forcing arbitrarily large output density; an analogous shape-coordinate argument is claimed. It therefore claims a counterexample under the concrete regularity conditions discussed, but has not been independently verified.

Current status (as of August 2026): The conjecture has no verified proof or counterexample; its scope is ambiguous because “generic” is undefined, and the posted counterexample remains an unverified challenge.

Sources

CounterexampleThis solution needs a summarySee full solutionHide full solution

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.

The bounded output-density conjecture for LLL and LLL-SP

Primary source

Progress summary