Strong mixing and uniform density conjecture for LLL coefficients

At least 7 years old · documented by

Let D\mathcal{D} be a “generic” distribution on the set of bases in Rn\mathbb{R}^n used to sample inputs for LLL. For the pile toppled at iteration ii, let k(i)k(i) denote its index, so that μk(i)\mu_{k(i)} is a random variable determined by the input distribution.

LLL mixing and density conjecture. (i) The sequence (∣μk(i)∣)i=1,2,…(|\mu_{k(i)}|)_{i=1,2,\ldots} is strongly mixing as a stochastic process. (ii) Each ∣μk(i)∣|\mu_{k(i)}| is contained in a compact subset SS of the set of all probability density functions on [0,0.5][0,0.5] with respect to the L∞L^\infty-norm, where SS 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

Never refreshed

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.