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:

def euclid(m,n):
    while n!=0:
        q = round(m/n)
        m -= q*n
        if abs(n) > abs(m):
            m, n = n, m
    return abs(m)

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

def lagrange(b1,b2):
    mu = 1
    while mu != 0:
        mu = round((b1*b2) / (b1*b1))
        b2 -= mu*b1
        if b1*b1 > b2*b2:
            b1, b2 = b2, b1
    return b1, b2

Here μ\muis actually the Gram-Schmidt coefficient μ2,1\mu_{2,1}and it turns out that this algorithm will always find the shortest possible basis! Using the basis

b1=(1.8,1.2)b2=(3.6,2.3)\begin{matrix} b_1&=&(-1.8,1.2)\\ b_2&=&(-3.6,2.3) \end{matrix}

the Lagrange reduction looks like

and here we see it clearly gives the shortest vectors.

Optimality proof

Let LLbe a lattice. The basis b1,b2b_1,b_2is defined to be the shortest for any other basis b1,b2,b1b2b_1',b_2',\left\lVert b_1'\right\rVert\leq\left\lVert b_2'\right\rVert, we have b1b1\left\lVert b_1\right\rVert\leq\left\lVert b_1'\right\rVertand b2b2\left\lVert b_2\right\rVert\leq\left\lVert b_2'\right\rVert. 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 b1,b2b_1,b_2be the output of the Lagrange reduction for some lattice LL. To prove that Lagrange reduction gives the shortest basis, we first show that b1\left\lVert b_1\right\rVertis the shortest vector in LL.

We know that b1,b2b1212\frac{\left|\langle b_1,b_2\rangle\right|}{\left\lVert b_1\right\rVert^2}\le\frac12from the algorithm directly. Let v=mb1+nb2Lv=mb_1+nb_2\in Lbe any element in LL. We first show that b1v\left\lVert b_1\right\rVert\leq\left\lVert v\right\rVert:

v2=mb1+nb22=m2b12+2mnb1,b2+n2b22m2b12mnb12+n2b12=(m2mn+n2)b12\begin{align*} \left\lVert v\right\rVert^2&=\left\lVert mb_1+nb_2\right\rVert^2\\ &=m^2\left\lVert b_1\right\rVert^2+2mn\langle b_1,b_2\rangle+n^2\left\lVert b_2\right\rVert^2\\ &\geq m^2\left\lVert b_1\right\rVert^2-|mn|\left\lVert b_1\right\rVert^2+n^2\left\lVert b_1\right\rVert^2\\ &=\left(m^2-|mn|+n^2\right)\left\lVert b_1\right\rVert^2\\ \end{align*}

Since m2mn+n2=(mn2)2+34n2m^2-mn+n^2=\left(m-\frac n2\right)^2+\frac34n^2, this quantity is only 00when m=n=0m=n=0and is a positive integer for all other cases, hence vb1\left\lVert v\right\rVert\geq\left\lVert b_1\right\rVertand b1\left\lVert b_1\right\rVertis a shortest vector of LL. Note that we can have multiple vectors with the same norm as b1b_1, for instance b1-b_1. So this is not a unique shortest vector.

Suppose there exists some basis b1,b2b'_1,b'_2for LLsuch that b1b2\left\lVert b_1'\right\rVert\leq\left\lVert b_2'\right\rVert. We show that b2b2\left\lVert b_2\right\rVert\leq\left\lVert b_2'\right\rVert. Let b2=mb1+nb2b_2'=mb_1+nb_2.

If n=0n=0, then b2=±b1b_2'=\pm b_1as b1,b2b_1',b_2'must form a basis. This means that b1=b1=b2\left\lVert b_1\right\rVert=\left\lVert b_1'\right\rVert=\left\lVert b_2'\right\rVert and by the inequality above, we must have ±b1=b2\pm b_1'=b_2or ±b1=b1+b2\pm b_1'=b_1+b_2. The first case tells us that b1=b2\left\lVert b'_1\right\rVert=\left\lVert b_2\right\rVert. By squaring the second case, we get

b12=b1+b22b12=b12+2b1,b2+b220=2b1,b2+b22b12b22\begin{align*} \left\lVert b'_1\right\rVert^2&=\left\lVert b_1+b_2\right\rVert^2\\ \left\lVert b'_1\right\rVert^2&=\left\lVert b_1\right\rVert^2+2\langle b_1,b_2\rangle+\left\lVert b_2\right\rVert^2\\ 0&=2\langle b_1,b_2\rangle+\left\lVert b_2\right\rVert^2\\ \left\lVert b_1\right\rVert^2&\leq\left\lVert b_2\right\rVert^2\\ \end{align*}

but since b1\left\lVert b_1\right\rVertis the shortest vector, b1=b2\left\lVert b_1\right\rVert=\left\lVert b_2\right\rVert.

Otherwise, we have m,n0m,n\neq0 and m2mn+n21m^2-mn+n^2\geq1, so

b22=m2b12+2mnb1,b2+n2b22m2b12mnb12+n2b22=n2(b22b12)+(m2mn+n2)b12(n21)(b22b12)+b22b22\begin{align*} \left\lVert b'_2\right\rVert^2&=m^2\left\lVert b_1\right\rVert^2+2mn\langle b_1,b_2\rangle+n^2\left\lVert b_2\right\rVert^2\\ &\geq m^2\left\lVert b_1\right\rVert^2-|mn|\left\lVert b_1\right\rVert^2+n^2\left\lVert b_2\right\rVert^2\\ &=n^2\left(\left\lVert b_2\right\rVert^2-\left\lVert b_1\right\rVert^2\right)+\left(m^2-|mn|+n^2\right)\left\lVert b_1\right\rVert^2\\ &\geq\left(n^2-1\right)\left(\left\lVert b_2\right\rVert^2-\left\lVert b_1\right\rVert^2\right)+\left\lVert b_2\right\rVert^2\\ &\geq\left\lVert b_2\right\rVert^2 \end{align*}

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 b1=b2=b1+b2\left\lVert b_1\right\rVert=\left\lVert b_2\right\rVert=\left\lVert b_1+b_2\right\rVert. 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 https://arxiv.org/abs/1009.4322 for the details)

3*) Let μ2,1=μ2,1+ε=μ+ϵ\mu_{2,1}=\lfloor\mu_{2,1}\rceil+\varepsilon=\mu+\epsilon, show that

b22((μ12)2ε2)b12+b2μb1\left\lVert b_2\right\rVert^2\geq\left(\left(|\mu|-\frac12\right)^2-\varepsilon^2\right)\left\lVert b_1\right\rVert^2+\left\lVert b_2-\mu b_1\right\rVert

and show that μ2|\mu|\geq2for all steps in the algorithm except the first and last, hence b1b2\left\lVert b_1\right\rVert\left\lVert b_2\right\rVertdecreases by at least 3\sqrt3 at each loop and the algorithm runs in polynomial time.

Last updated