Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm

What is the importance of the $\delta$ parameter for LLL bases called Lovász condition?

Wiki seems to mention that the higher the $\delta$ the better.

What does it mean when $\delta = 1$? Can we find shortest vector and closest vector easily if $\delta =1$? What are typical error in approximations when $\delta = 1$?

In the SVP and CVP algorithm presented below, is there any connection to $\delta$ on the approximation error.

http://www.cs.tau.ac.il/~odedr/teaching/lattices_fall_2004/ln/cvp.pdf

Finally is there a reference that talks about connections to CVP and minimum distance?

share|improve this question
3  
Just corrected the spelling of "Lovász". See cs.elte.hu/~lovasz –  Sándor Kovács Dec 26 '11 at 21:10
4  
yes, you and wiki are right - $\delta$ is related to the quality of the approximation. The point is that ideal case would be $\delta=1$ - but there is no polynomial algorithm for this. As an example you can take R^2. Then the conditions become quite transparent. LLL - is something like Gram-Schimidt but with integer coefficients. –  Alexander Chervov Dec 27 '11 at 4:32
    
@Alexander Chervov: So you are saying $\delta \le 1$ holds? What if $\delta = 1$? What do you mean by $\delta = 1$ is the ideal case? –  Turbo Dec 27 '11 at 8:54
2  
It does not make much sense to say “$\delta\le1$ holds”. The $\delta$ is an input parameter of the algorithm, so you get to choose it, but yes, for the algorithm to work it needs to be $\le1$ ($< 1$ if it is to run in polynomial time). –  Emil Jeřábek Dec 28 '11 at 11:44
    
@Emil Jerabek. Got it. Say I have a basis set which naturally has $\delta = 1$. What can one say about approximating cvp and svp? any standard algorithms for finding cvp and svp? –  Turbo Dec 28 '11 at 15:07

1 Answer 1

This will answer your questions on $\delta$: The case $\delta=1$, sometimes referred to as the ideal or optimal LLL-Algorithm, is the most natural way to define the swap condition between vectors after the length reduction step, as it forces to swap $b_k$ and $b_{k+1}$ if and only if its orthogonal 'emergence', i.e. orthogonal distance of $b_{k+1}$ with respect to the linear span of the $b_1,\ldots,b_{k-1}$ is smaller than the orthogonal emergence of $b_k$. Some people refer this type of reduction to Hermite, who applies this algorithm in order to prove an upper bound for the Hermite constant in any dimension $d$.

Lovász introduced the relaxation factor $\left(\frac{1}{2}\right)^2< \delta<1$ for the swap condition

$d(b_{k+1},Span(b_1,\ldots,b_{k-1}))<\sqrt{\delta}\cdot d(b_{k},Span(b_1,\ldots,b_{k-1}))$,

in order to be able to prove an upperbound for the time complexity of the algorithm which is polynomial in the magnitude of the initial basis AND the dimension $d$. Also in the ideal case $\delta=1$ the algorithm is still polynomial with respect to the magnitude of the basis (A. Akhavi, The optimal LLL algorithm is still polynomial in fixed dimension,Theoretical Computer Science 297 (2003),1-3, pp.3–23), but it is still an open problem whether it is also polynomial in the dimension $d$.

The factor $\delta$ can be regarded as a strictness factor: the closer it is to $1$, the more orthogonal the reduced basis will be in general, and therefore both its Hermite factor as well as its approximation factor for the minimal lattice norm $\lambda_1$ are better. I don't know of any strict theoretical proof of this connection, but extensive experiments as made by Gama, Nguyen and Stehlé (cf. P. Nguyen, D. Stehlé, LLL on average, Algorithmic Number Theory 4076 (2006), pp.1-17 or N. Gama, P. Nguyen, Predicting lattice reduction, Proc. of the EUROCRYPT 2008, Vol. 4965, pp.31-51) show that for LLL with $\delta=0.999$ the average Hermite factor, taking samples from an equidistributed (according to a natural measure on lattices described in D.Goldstein, A.Mayer, On the equidistribution of Hecke points, Forum Mathematicum (2003) 15, 2, pp. 165-189) sequence of integer lattices, increases exponentially by

$ 0.801\cdot 1.0219^d$,

which shows much better performance than predicted by the theoretic upper bound $(4/3)^\frac{d}{4}\approx 1.074^d$. Using what is called Gaussian heuristics, one can take the Hermite factors to estimate the average approximation factor by

$average \frac{\|b_1\|}{\lambda_1}\approx\sqrt{\frac{\pi\cdot e}{2\cdot d}}\cdot 0.801\cdot 1.0219^d$,

slightly less exponential in $d$. According to a frequently cited draft of M.Ajtai, Generating random lattices according to the invariant distribution (2006), this heuristics is quite accurate for high dimension lattices. Unfortunately, I have never found the draft itself or any later on published paper.

However, if you don't want to rely on Gaussian heuristics, the bounds I derived from my own experiments running LLL with $\delta=1$ on integer lattices from dimension $30$ to $100$, choosing random knapsack type bases of magnitude $2^{20d}$, are

$0.3444\cdot 1.0136^d\leq average \frac{\|b_1\|}{\lambda_1} \leq 0.6688\cdot 1.0442^d,$

the lower bound representing the Gaussian heuristics, again much better than the proven upper bound $(4/3)^{d/2}\approx 1.1547^d$.

For less ideal $\delta$, I don't know any published estimate of the average behaviour. The experiments I've done by myself seem to verify the thumb rule: the smaller $\delta$, the faster reduction is done, but the more volatile the quality of the results, and moreover the stronger is the exponential growth of the average Hermite and approximation factors.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.