Discrete Math, Seventh Problem Set (July 2)
REU 2003

Instructor: Laszlo Babai
Scribe: Varsha Dani

We now turn our attention to an algorithmic problem. Consider a lattice in ${\mathbb{R}}^n$, specified by a basis. We want to find the shortest non-zero vector in the lattice. Moreover, we would like to be able to do this ``efficiently,'' in the sense that the number of steps taken by the algorithm should be bounded by a polynomial function of the bit-length of the input (number of zeros and ones needed to describe the input).

Let $L= \sum_{i=1}^{n} {\mathbb{Z}}{\mathbf{b}}_i$ where the ${\mathbf{b}}_i \in {\mathbb{Z}}^n$ are linearly independent. Note that we restrict our attention to bases in ${\mathbb{Z}}^n$ rather than ${\mathbb{R}}^n$ because we need the number of bits in the input to be finite. The length is the total number of bits needed to describe all entries of the matrix $[b_1, b_2, \dots, b_n]$.

So for example if each coordinate has $m$ bits, then the input length is $m n^2$.

A polynomial time algorithm is one that takes at most $C_1 ($input length$)^{C_2}$ steps to execute. For example an algorithm that runs in $C ($input length$)^3$ steps is a cubic algorithm.

The shortest vector in a lattice is the zero vector. When we talk about ``the shortest vector'' in a lattice, we mean the shortest non-zero vector.

Finding the shortest vector in a lattice is NP-hard (Ajtai, 2000). Roughly speaking this means that the problem is at least as hard as any combinatorial search problem: if we could solve it in polynomial time, we could use that to solve any other combinatorial search problem in polynomial time. For example we could factor large numbers in polynomial time.

Lovász's lattice reduction algorithm (1980) which we are about to see is a polynomial time algorithm, and it does not find the shortest vector in the lattice. What it does find is a vector in the lattice that is ``short enough.'' Specifically, it finds a vector $x \in L$ with $\Vert{x}\Vert \le 2^{(n-1)/2} \mathrm{min} L$ where $n$ is the dimension and

$$\mathrm{min} L:= \min \{ \Vert{{\mathbf{v}}}\Vert\,:\, {\mathbf{v}} \in L, {\mathbf{v}} \ne 0 \}.$$

In fact it does more; it finds a certain ``nice'' basis for the lattice, called a Lovász-reduced basis. A ``nice'' basis is one that is ``close'' to being orthogonal in some vague sense. It will turn out that the first vector of a Lovász-reduced basis is a $2^{(n-1)/2}$-approximation to the shortest vector in the lattice.

First we need to define a Lovász-reduced basis. Recall the Gram-Schmidt orthogonalization process for obtaining an orthogonal basis for the span of a set of linearly independent vectors. If ${\mathbf{b}}_1, \dots, {\mathbf{b}}_n$ is the original basis, and ${\mathbf{b}}_1^*, \dots, {\mathbf{b}}_n^*$ is the orthogonalized basis then we have

$$(\forall i, 1 \le i \le n) \left( {\mathbf{b}}_i = {\mathbf{b}}_i^* + \sum_{j<i} \mu_{i,j} {\mathbf{b}}_j^* \right).$$

Now if the given basis ${\mathbf{b}}_1, \dots, {\mathbf{b}}_n$ is orthogonal then $(\forall i,j) \left( \mu_{i,j} =0 \right)$. One possible meaning of being ``close to orthogonal'' is that all the $\mu_{i,j}$ are small in absolute value; a Lovász-reduced basis intends to meet this objective.

Additionally, we do not want the basis vector ${\mathbf{b}}_i$ to be too close to the subspace $\mathcal{U}_{i-1}$, the span of ${\mathbf{b}}_1,\dots,{\mathbf{b}}_{i-1}$, i.e., we do not want ${\mathbf{b}}_i^*$ to have too small norm.

The following definition gives a prcise meaning to these two requirements:

Definition 0.1   A basis ${\mathbf{b}}_1,\dots,{\mathbf{b}}_n\in R^n$ is Lovász-reduced if after performing the Gram-Schmidt orthogonalization process on it, the following conditions hold:

1. $(\forall i,j) \left( \vert\mu_{i,j}\vert \le \frac{1}{2}\right)$;
2. $(\forall i) \left( \Vert{{\mathbf{b}}_{i+1}^*}\Vert \ge \frac{1}{\sqrt{2}} \Vert{{\mathbf{b}}_i^*}\Vert\right)$.

Note that the definition is sensitive to order: the same basis vectors in a different order may not form a Lovász-reduced basis.

The following lemma applies to all bases, not only to L-reduced ones. The lemma will be our key tool to proving that in a L-reduced basis, the first basis vector is not much longer than $\mathrm{min} L$.

Lemma 0.2   For all lattices and bases, $\mathrm{min} L\ge \min_{1 \le i \le n} \Vert{{\mathbf{b}}_i^*}\Vert$.

Proof. Let ${\mathbf{x}}\in L$, ${\mathbf{x}}\ne 0$. Then there exist $\alpha_i \in {\mathbb{Z}}$ not all zero, such that ${\mathbf{x}}= \sum_{i=1}^n \alpha_i {\mathbf{b}}_i$. Let $t$ be the largest index for which $\alpha_t \ne 0$, i.e., $\alpha_t \ne 0$ and $\alpha_i = 0$ for all $i >t$. Then ${\mathbf{x}}= \sum_{i=1}^t \alpha_i {\mathbf{b}}_i$. Now recall that the Gram-Schmidt process on ${\mathbf{b}}_1, \dots, {\mathbf{b}}_n$ produces orthogonal vectors ${\mathbf{b}}_1^*, \dots, {\mathbf{b}}_n^*$ with the property that for all $i$ with $1 \le i \le n$, ${\mathrm{Span}({\mathbf{b}}_1, \dots, {\mathbf{b}}_i)} = {\mathrm{Span}({\mathbf{b}}_1^*, \dots, {\mathbf{b}}_i^*)}$. Thus there exist $\beta_i \in {\mathbb{R}}$ such that ${\mathbf{x}}= \sum_{i=1}^t \beta_i {\mathbf{b}}_i$. Note that while the $\beta_i$ do not have to be integers, the last one, $\beta_t$ is an integer. To see this, note that for all $i$ with $1 \le i \le t$,

$$\alpha_i {\mathbf{b}}_i = \alpha_i {\mathbf{b}}_i^* + \sum_{j<i} \alpha_i \mu_{i,j} {\mathbf{b}}_j^*.$$

Summing this up for $i \le t$, we obtain

$${\mathbf{x}}= \sum_{i=1}^t \alpha_i {\mathbf{b}}_i = \sum_{i=1}^t... ...mathbf{b}}_i^* + \sum_{i=1}^t \sum_{j<i} \alpha_i \mu_{i,j} {\mathbf{b}}_j^*.$$

The second term on the right hand side does not contain ${\mathbf{b}}_t^*$, so ${\mathbf{b}}_t^*$ occurs only once, with coefficient $\alpha_t$. Since the ${\mathbf{b}}_i^*$ are linearly independent and ${\mathbf{x}}= \sum_{i=1}^t \beta_i {\mathbf{b}}_i^*$ it follows that $\beta_t =\alpha_t \in {\mathbb{Z}}$. Now since the ${\mathbf{b}}_i^*$ are orthogonal,

$$\Vert{{\mathbf{x}}}\Vert^2 = \sum_{i=1}^t \beta_i^2 \Vert{{\mathb... ...b}}_t^*}\Vert^2 \; \ge \; \min_{1 \le i \le n} \Vert{{\mathbf{b}}_i^*}\Vert^2,$$

where inequality (*) follows from the fact that if $\beta \in {\mathbb{Z}}$ and $\beta \ne 0$ then $\vert\beta\vert \ge 1$. Taking the minimum over all ${\mathbf{x}}\in L$ now completes the proof. $\qedsymbol$

Observation 0.3   If ${\mathbf{b}}_1, \dots, {\mathbf{b}}_n$ is a Lovász-reduced basis for the lattice $L$ then for all $i$, $\Vert{{\mathbf{b}}_1^*}\Vert \le 2^{(i-1)/2}\Vert{{\mathbf{b}}_i^*}\Vert$ (by induction, using property (2) of such a basis). Therefore

$$\Vert{{\mathbf{b}}_1^*}\Vert \le 2^{(n-1)/2} \min_{1 \le i \le n} {\mathbf{b}}_i^* \le 2^{(n-1)/2} \mathrm{min} L.$$

Since ${\mathbf{b}}_1^* = {\mathbf{b}}_1$ we have

Corollary 0.4   If ${\mathbf{b}}_1, \dots, {\mathbf{b}}_n$ is a Lovász-reduced basis for lattice $L$ then $\Vert{{\mathbf{b}}_1}\Vert \le 2^{(n-1)/2} \mathrm{min} L$.

We still have to find a Lovász-reduced basis in $L$.

Lovász's Algorithm

Input: $[{\mathbf{b}}_1, \dots , {\mathbf{b}}_n] \in {\mathbb{Z}}^{n \times n}$, non-singular.
Output: $[{\mathbf{b}}_1', \dots , {\mathbf{b}}_n'] \in {\mathbb{Z}}^{n \times n}$, a Lovász-reduced basis of the same lattice, i.e., $L = \sum_{i=1}^n {\mathbb{Z}}{\mathbf{b}}_i = \sum_{i=1}^n {\mathbb{Z}}{\mathbf{b}}_i'$.

The algorithm will make two kinds of steps, which try to achieve the two conditions in the definitions. The first kind will perform elementary transformations on the basis (replacing ${\mathbf{b}}_i$ by ${\mathbf{b}}_i-\alpha{\mathbf{b}}_j$ for a suitable scalar $\alpha$) with the goal to make the condition $\vert\mu_{i,j}\vert \le \frac{1}{2}$ hold. We repeat this type of steps until all $\mu_{i,j}$ satisfy this inequality (so condition (1) holds).

Once condition (1) has been achieved, we check for condition (2) and will switch the order of a pair of consecutive basis vectors where violation is found. We perform this operation only once per round. While it is not immediately clear how this kind of rearrangement is of any help, it is clear that such a rearrangement may destroy the condition $\vert\mu_{i,j}\vert \le \frac{1}{2}$ we have labored hard to achieve, so we must return to the elementary transformations to restore condition (1).

All in all, it is not evident that such an approach will converge to anything at all; but if it does converge, the result is a Lovász-reduced basis.

Making the $\mathbf{\mu_{i,j}}\;$s small
Let $\mathcal{U}_i$ denote ${\mathrm{Span}({\mathbf{b}}_1, \dots, {\mathbf{b}}_i)}$. If ${\mathbf{b}}_1^*, \dots {\mathbf{b}}_n^*$ are the vectors produced by the Gram-Schmidt process, then for all $i$, ${\mathrm{Span}({\mathbf{b}}_1^*, \dots, {\mathbf{b}}_i^*)}= \mathcal{U}_i$ and ${\mathbf{b}}_i-{\mathbf{b}}_i^*\in \mathcal{U}_{i-1}$; and these two conditions determine the ${\mathbf{b}}_i^*$. So the elementary transformations ${\mathbf{b}}_i\mapsto {\mathbf{b}}_i-\alpha{\mathbf{b}}_j$ $(j<i)$ do not change any of the ${\mathbf{b}}_i^*$. ${\mathbf{b}}_1', \dots {\mathbf{b}}_n'$ will produce the same vectors ${\mathbf{b}}_i^*$. On the other hand, the $\mu_{i,j}$ will change; we need to calculate this change to see that with the appropriate choice of the coefficient $\alpha\in{\mathbb{Z}}$, the condition $\vert\mu_{i,j}\vert\le 1/2$ will be achieved.

Here is then the first procedure:

Procedure ``coefficient reduction''
for $i=2$ to $n$
for $j=i-1$ downto $1$
${\mathbf{b}}_i := {\mathbf{b}}_i - \left\lfloor \mu_{i,j} \right\rceil {\mathbf{b}}_j$

Here $\lfloor x \rceil$ denotes the integer nearest to $x$. Ties are broken arbitrarily.

Complexity analysis: ``coefficient reduction'' requires $\binom{n}{2}$ elementary basis transformations, each of which takes $O(n)$ arithmetic operations. One more thing to worry about: do the integers involved grow in the process?

Swapping
Now we check property 2. If it is violated, we swap a violating pair ${\mathbf{b}}_i$ and ${\mathbf{b}}_{i+1}$. Then we start over with coefficient reduction again. If property 2 is ever satisfied after coefficient reduction then we are done. Here is the full algorithm in pseudocode:

Procedure ``Lattice Reduction''
while basis not Lovász-reduced
if $(\exists i>j)(\vert\mu_{i,j}\vert>1/2)$ then do coefficient reduction
else find first $i$ such that $\Vert{{\mathbf{b}}_{i+1}^*}\Vert < \frac{1}{\sqrt{2}} \Vert{{\mathbf{b}}_i^*}\Vert$;
swap ${\mathbf{b}}_i$ and ${\mathbf{b}}_{i+1}$;
update orthogonalized sequence.

To prove that this algorithm terminates, we use a potential function argument, a general method of algorithm analysis which assigns a value (the ``potential'') to each ``configuration'' of variables in such a way that each phase of the algorithm reduces the potantial.

The Lovász potential of a basis ${\mathbf{b}}_1, \dots, {\mathbf{b}}_n$ is defined to be the quantity

$$\mathop{\rm vol}\nolimits {({\mathbf{... ...dots \cdot \mathop{\rm vol}\nolimits {({\mathbf{b}}_1, \dots, {\mathbf{b}}_n)},$$

where $\mathop{\rm vol}\nolimits$ refers to the appropriate dimensional volume of the parallelepiped spanned by the vectors in the argument.

It follows from the exercise that the Lovász potential does not change under the ``coefficient reduction'' procedure. (Why?)

Therefore, for integral lattices, the Lovász potential is $\ge 1.$ It follows that the algorithm terminates in $O(\log{I})$ phases, where $I$ is the initial potential. Since each phase takes $O(n^2)$ steps, the algorithm takes $\log{I} O(n^2)$ steps.