Lagrange's algorithm

Overview

Lagrange's algorithm, often incorrectly called Gaussian reduction, is the 2D analouge to the Euclidean algorithm and is used for lattice reduction. Intuitively, lattice reduction is the idea of finding a new basis that consists of shorter vectors. Before going into Lagrange's algorithm, we first recap the Euclidean algorithm:

The algorithm primarily consists of two steps, a reduction step where the size of $m$is brought down by a multiple of $n$and a swapping step that ensures $m$is always the largest number. We can adapt this idea for lattices:

Here is actually the Gram-Schmidt coefficient and it turns out that this algorithm will always find the shortest possible basis! Using the basis

the Lagrange reduction looks like

and here we see it clearly gives the shortest vectors.

Optimality proof

Let be a lattice. The basis is defined to be the shortest for any other basis , we have and . Note that this generally cannot be generalized to other dimensions, however in dimension 2, this is possible and is given by Lagrange's algorithm. The proof is a somewhat messy sequence of inequalities that eventually lead to the conclusion we want.

Let be the output of the Lagrange reduction for some lattice . To prove that Lagrange reduction gives the shortest basis, we first show that is the shortest vector in .

We know that from the algorithm directly. Let be any element in . We first show that :

Since , this quantity is only when and is a positive integer for all other cases, hence and is a shortest vector of . Note that we can have multiple vectors with the same norm as , for instance . So this is not a unique shortest vector.

Suppose there exists some basis for such that . We show that . Let .

If , then as must form a basis. This means that and by the inequality above, we must have or . The first case tells us that . By squaring the second case, we get

but since is the shortest vector, .

Otherwise, we have and , so

Hence proving Lagrange's algorithm indeed gives us the shortest basis vectors.

Exercises

1) Show that the output of Lagrange's algorithm generate the same lattice as the input.

2) Find a case where . Notice that the vectors here is the equality case for the bound given in Exercise 4 of the introduction, this actually tells us that the optimal lattice circle packing in 2D is given by this precise lattice! It turns out that this is actually the optimal circle packing in 2D but the proof is significantly more involved. (See for the details)

3*) Let , show that

and show that for all steps in the algorithm except the first and last, hence decreases by at least at each loop and the algorithm runs in polynomial time.