## Wednesday, January 6, 2010

### Drills on LLL algorithm

Hello again,

Today I intend to discuss some problems from Regev's 2nd homework on the subject. I am indebted to Oded Regev, Nir Bitansky and Roy Kasher for these solutions. A special thanks to you all for letting me use your solutions. I will give due credit to the solvers when I use their solutions (and not mine).

So, first lets prove that a $\delta$-LLL reduced basis with $\delta = 3/4$ satisfies the following properties. (This is the $4th$ problem in the homework. The questions are in bold and are italicised).

4-a) Prove the following
$||b_1|| \leq 2^{(n-1)/4}*(det \Lambda)^{1/n}$

Do you see how to do it? Easy. Just make use of fact that $||b_1|| = ||b_1^*||$.
And that $(\delta-1/4)*||b_i^*||^2 \leq ||b_{i+1}^*||^2$

For $\delta = 3/4$, this means that $||b_i^*||^2 < 2* ||b_{i+1}^*||^2$.
Extending this, we quick get $||b_1|| = ||b_1^*|| \leq 2^{(i-1)/2}||b_i^*|| \forall i$

In particular,    $||b_1^*|| \leq ||b_1^*||$
$||b_1^*|| \leq \sqrt2||b_2^*||$
and,     $||b_1^*|| \leq 2||b_3^*||$

and so on upto $||b_1^*|| \leq 2^{(n-1)/2}||b_n^*||$

Multiplying all inequalities, we get $||b_1^*||^n = ||b_1||^n \leq det(\Lambda)*2^{(n*(n-1))/4}$

$\Rightarrow ||b_1|| \leq det(\Lambda)^{1/n}*2^{((n-1))/4}$

Hence proved.

4-b) Next consider this question
For any $1 \leq i \leq n, ||b_i|| \leq 2^{(i-1)/2}*||b_i^*||$

Why is that true? You remember the representation of basis vectors in Gram-Schmidt representation, right?

Let me write it down for your convenience.

$\begin{pmatrix}||b_1*||&\mu_{2,1}||b_1*||&...&\mu_{n,1}||b_1*||\\0&||b_2*||&...&\mu_{n,2}||b_2*||\\...&...&...&...\\...&...&...&...\\...&...&...&...\\0&0&...&||b_n*||\end{pmatrix}$

I hope you can see why the solution write itself. Pick $b_i$'s representation from this matrix.

You know that $||b_i||^2 = ||\mu_{i,1}b_1^*||^2 + ||\mu_{i,2}b_2^*||^2 + ... + ||\mu_{i,i-1}b_{i-1}^*||^2 + ||b_i^*||^2$

But, the Basis is $3/4$-LLL reduced. From the first condition on a base to be LLL reduced, we know that all $|\mu_{i,j}| \leq 1/2$

Thus, $||b_i||^2 \leq 1/4||b_1^*||^2 + 1/4||b_2^*||^2 + ... + 1/4||b_{i-1}^*||^2 + ||b_i^*||^2$

And, we also notice that $||b_l^*||^2 \leq 2^{(m-l)/2} ||b_m^*||^2$ for $l \leq m$. Thus, we have

$||b_i||^2 \leq ||b_i^*||^2 + \sum_{j=1}^{j=i-1}2^{i-j-2}||b_j^*||^2$

and you can work out that this implies the inequality in question.

4-c) Prove the following

$\Pi_{i=1}^{i=n}||b_i|| \leq 2^{(n*(n-1)/4)}*det(\Lambda)$

DO you remember the statement of 4-b). This one follows directly. (why?)

The homework also says the following -

Remark: the quantity $\Pi_{i=1}^{i=n}||b_i||/det(\Lambda)$ is known as the orthogonality defect of the basis; to see why, notice that it is 1 iff the basis is orthogonal; it can never be less than one by Hadamard’s inequality.

4-d) Prove the following

For any $1 \leq i \leq j \leq n$, $||b_i|| \leq 2^{(j-1)/2}||b_j^*||$

Well what do you think? What can you tell me using 4-b). ||b_i|| \leq 2^{(i-1)/2}*||b_i^*||$, right? And what do you know about the relation between$||b_i^*|| and ||b_j^*|| for $i \leq j$.

$||b_i^*|| \leq 2^{(j-i)/2}||b_j^*||$

Combine these two to get

$||b_i|| \leq 2^{(j-1)/2}||b_j^*||$ which settles the question.

4-e) Here is another. Prove

For any $1 \leq i \leq n$, $\lambda_i(\Lambda) \leq 2^{(i-1)/2}||b_i^*||$

Hmmm...what should we do now. Perhaps get some sleep. But this is easy. Lets finish $4^{th}$ problem altogether and then sleep (or take a break or whatever).

So, whats your idea? You have got to say something about the $i_{th}$ successive minima. It is less than some multiple of $||b_i^*||$. How to create the desired terms? Maybe you could show a relation between $\lambda_i$ and $||b_i||$ and then use our lovely 4-b)
That looks a bad prospect. We do not as of yet know of a direct connection between the two. Lets make some observations and keep the definition of $ith$ successive minima in your head.

You know that $\forall j \leq i$, $||b_j|| \leq 2^{(i-1)/2}||b_i^*||$ from 4-d). Thus, all these $i$ vectors (which are clearly independent) are less than the claimed RHS. In particular, the RHS is an upper bound on the length of $ith$ successive minima - which is precisely the statement we set out to prove.

4-f) Prove that

For any $1 \leq i \leq n$, $\lambda_i(\Lambda) \geq 2^{-(n-1)/2}||b_i||$

Hmm..I was not able to solve this problem on my own. Below, I invoke Roy Kasher's solution. He notes that

"By LLL property, for $i \eq j$, $||b_i^*|| \leq 2^{(j-i)/2}||b_j^*||$. That is, $||b_j^*|| \geq 2^{(i-j)/2}||b_i^*||$. Using 4-b), we obtain $||b_j^*|| \geq 2^{-(j-1)/2}||b_i||$."

So far so good. Now he fits in the missing piece (or the piece that I missed).

From previous homework (or in our case previous post), we know that $\lambda_i \geq min_{j=i...n}||b_j*||$.

Now everything falls into place. As Kasher goes onto note,
"$\lambda_i \geq min_{j=i...n}||b_j*|| \geq min_{j=1}^n 2^{-(j-1)/2}||b_i|| = 2^{-(n-1)/2}||b_i||$"

There are some more problems to come up. Wait till I get around to do that.

Thanks and Have a  Good day