most recent 30 from http://mathoverflow.net 2013-05-19T03:24:02Z http://mathoverflow.net/feeds/question/61945 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/61945/how-often-does-lll-reduction-produce-optimal-result-is-there-condition-or Alexander Chervov 2011-04-16T19:05:18Z 2011-04-16T20:40:37Z

<p>Consider some lattice in R^4 (C^4) or C^8. Famous "lattice reduction" procedures (like LLL latice reduction) produces some "reduced basis". However in general there results are not "the best reduced".</p> <p>Is there some understanding (at least informal) what are the conditions on lattice such that LLL (or similar) reduction will produce "the best result" ?</p> <p>More precisely let me consider the following situation - take a 4*4 matrix and generate its elements from normal distribution N(0,1). Consider the lattice generated by the columns of this matrix. What is the probability that LLL-reduction will produce the "best results" ? </p> <p>I have made some (not many) experiments with LLL reduction - the integer valued matrices which change original random basis to "reduced one" have quite small coefficients in many cases +-1 sometimes 2,3 but rarely more... well these are not "well-checked" observations... What does it mean ? Does it correspond to some theory ?</p>

http://mathoverflow.net/questions/61945/how-often-does-lll-reduction-produce-optimal-result-is-there-condition-or/61951#61951 Victor Miller 2011-04-16T20:23:05Z 2011-04-16T20:40:37Z

<p>This paper</p> <p>"On the reduction of a random basis" by Ali Akhavi,Jean-Francois Marckert, and Alain Rouault</p> <p><a href="http://www.siam.org/proceedings/analco/2007/anl07_028aakhavi.pdf" rel="nofollow">http://www.siam.org/proceedings/analco/2007/anl07_028aakhavi.pdf</a></p> <p>purports to answer your question.</p> <p>Added later: There is a real question about what is the right meaning of a "random lattice". You should see the paper "On the equidistribution of Hecke points" by Daniel Goldstein and Andrew Mayer Forum Mathematicorum Volume 15, Issue 2, Pages 165–189. In that paper they look at the natural Haar measure on the space of $n$-dimensional lattices.</p>