# Lovász $\delta$ condition for LLL Algorithm

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?

-
Just corrected the spelling of "Lovász". See cs.elte.hu/~lovasz –  Sándor Kovács Dec 26 '11 at 21:10
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? –  J.A Dec 27 '11 at 8:54
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? –  J.A Dec 28 '11 at 15:07

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 Hermite factor on average increases exponentially by

$0.806\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 use the Hermite factors to estimate the average approximation factor by

$\sqrt{\frac{\pi\cdot e}{2\cdot d}}\cdot 0.806\cdot 1.0219^d$,

slightly less exponential in $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.

-