# True Lovàsz condition and definition of a LLL-reduced basis

I am studying the Shortest Vector Problem and I have some troubles understanding the actual Lovàsz condition used in the LLL algorithm.

On the one hand, the original LLL article, the Springer book "The LLL Algorithm" and A Complete Analysis of the BKZ Lattice Reduction Algorithm state that the LLL algorithm outputs a reduced basis meaning that:

• $$|\mu_{i,j}| \le 0.5\quad\forall 1\le j < i \le n$$ and
• $$\delta\|b_k^*\|^2 \le \|b^*_{k+1} + \mu_{k+1,k}b^*_k\|^2$$

On the other hand, other sources, like International Symposium on Mathematics, Quantum Theory, and Cryptography, page 198, Wikipedia and these course notes state that the LLL algorithm outputs a reduced basis meaning that:

• $$|\mu_{i,j}| \le 0.5\quad\forall 1\le j < i \le n$$ and
• $$\delta\|b_k^*\|^2 \le \|b^*_{k+1}\|^2 + \mu_{k+1,k}^2\|b^*_k\|^2$$

I am a bit confused as I cannot even apply the triangle inequality to infer the latter from the former.

Any hint is appreciated.

• Nov 3, 2023 at 20:05
• Maybe the closest answer is about the definition of a norm by Mark On the spectral norm in lattice-based cryptography Nov 3, 2023 at 20:16
• I thought of triangle inequality but while $\|b^*_{k+1} + \mu_{k+1,k} b^*_k\| \le \|b^*_{k+1}\| + \mu_{k+1,k}\|b^*_k\|$ is valid, if we square it we obtain $\|b^*_{k+1} + \mu_{k+1,k} b^*_k\|^2 \le \|b^*_{k+1}\|^2 + \mu_{k+1,k}^2\|b^*_k\|^2 \mathbf{+ 2\mu_{k+1,k}\|b^*_{k+1}\|\|b^*_k\|}$. I know no ways to check if $\|b^*_{k+1} + \mu_{k+1,k} b^*_k\|^2 \le \|b^*_{k+1}\|^2 + \mu_{k+1,k}^2\|b^*_k\|^2$ is also true (which is what we want). Or am I missing something? Nov 3, 2023 at 20:57
• And even if the triangle inequality explained the validity of the second definition, they are not equivalent: if LLL returns a basis $B$ that followed the first definition, then, assuming the inequality can be applied, it follows also the second one, but the opposite is not true (if $B$ follows the second "version" of the Lovász condition, we have no ways to say it also follows the first). PS: a small note, I'm unable to edit my former comment, but there is a typo: $\|b^*_{k+1}+\mu_{k+1,k}b^*_k\|\le\|b^*_{k+1}\|+\mathbf{|\mu_{k+1,k}|}\|b^*_k\|$ Nov 3, 2023 at 21:06
• It is worth mentioning that often when working with the squared euclidean norm $\lVert x+y\rVert_2^2$, one may apply convexity of $x\mapsto \lVert x\rVert_2^2$ as a substitute for the triangle inequality. Working on this briefly I it hasn't sufficed (for me) to show equivalence, but it might plausibly be useful anyway, hence this comment.
– Mark
Nov 3, 2023 at 21:29

For the Euclidean norm, both conditions are equivalent because $$b^*_{k}$$ and $$b^*_{k+1}$$ are orthogonal.

Remember that they are obtained via Gram-Schmidt orthogonalization, thus, $$b^*_{k} \cdot b^*_{k+1} = 0$$.

Also, remember that for any vectors $$u$$ and $$v$$, because the Euclidean norm is $$\|u\| = \sqrt{u \cdot u}$$, we have

$$\|u + v\|^2 = (u + v) \cdot (u + v) = u\cdot u + v \cdot v + 2\cdot u\cdot v = \|u\|^2+\|v\|^2 + 2\cdot u\cdot v$$

Then, if $$u$$ and $$v$$ are orthogonal, we obtain $$\|u + v\|^2 = (u + v) \cdot (u + v) = u\cdot u + v \cdot v + 2\cdot u\cdot v = \|u\|^2+\|v\|^2$$.

From your comments, it seems that you are getting confused because you are using the "squared triangular inequality", which says that

$$\|u + v\|^2 \le \|v\|^2 + \|v\|^2 + 2\|u\|\|v\|$$

This is true, of course, but this inequality is often obtained using the Cauchy–Schwarz inequality, i.e., $$u\cdot v \le \|u\|\|v\|$$... That is, we write

$$\|u + v\|^2 = (u + v) \cdot (u + v) = u\cdot u + v \cdot v + 2\cdot u\cdot v = \|u\|^2+\|v\|^2 + 2\cdot u\cdot v ~~ (1)$$

then use Cauchy–Schwarz to obtain

$$\|u + v\|^2 \le \|u\|^2+\|v\|^2 + 2\cdot \|u\|\cdot \|v\|$$.

But of course, in your case, instead of using this upper bound, you can just set $$u \cdot v = 0$$ in Equality (1)

• @kelala thanks! Nov 6, 2023 at 21:02
• So just to complete the trivial passages: $\delta\|b^*_k\|^2 \le \|b^*_{k+1} + \mu_{k+1,k}b^*_k\|^2 = \|b^*_{k+1}\|^2 + \mu_{k+1,k}^2\|b^*_k\|^2$ therefore $(\delta - \mu_{k+1,k}^2)\|b^*_k\| \le \|b^*_{k+1}\|^2$ which is the common other "version" of the Lovász condition. Thanks a lot for your answer! :) Nov 7, 2023 at 12:39