Strong mixing and uniform density conjecture for LLL coefficients
Let be a “generic” distribution on the set of bases in used to sample inputs for LLL. For the pile toppled at iteration , let denote its index, so that is a random variable determined by the input distribution.
LLL mixing and density conjecture. (i) The sequence is strongly mixing as a stochastic process. (ii) Each is contained in a compact subset of the set of all probability density functions on with respect to the -norm, where is independent of the dimension, the input distribution, and any other variable.
This is proposed as a rigorous version of the claim that LLL is essentially a sandpile model. The first part formalizes the heuristic that widely separated coefficients are nearly independent; the second asserts a dimension- and distribution-independent compactness property. The source gives no resolution of either assertion.
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).
Additional references
2 papers in this index state this conjecture (2018–2021). The statement above is taken from the most recent of them; the others are arXiv:1804.03285.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.