Lecture 19: Minkowski’s Theorem, Shortest/Closest Vector Problem, Lattice Basis Reduction, Gauss’ Algorithm

18.409 An Algorithmist’s Toolkit 11/17/2009 Lecture 19 Lecturer: Jonathan Kelner 1 Scribe: Steven Sam Review of last lecture Recall that L ⊂ Rn is a lattice if L is a discrete set and is closed under addition and negation. In this lecture, we assume that all lattices are full-rank, i.e., the vectors in the lattice span Rn . Given linearly independent b1 , . . . , bn ∈ Rn , one can form a lattice L(B) = L(b1 , . . . , bn ) = {Bx | x ∈ Zn }, where B is the set of the bi ’s. We call the bi ’s (and also the set B) a basis for L(B). Recall that a lattice can have many different bases. As opposed to linear algebra over a field, change of bases for lattices is more rigid, since the integrality constraints must be preserved. Because of this, one cannot usually find an orthonormal basis, and instead one of the most fundamental problems becomes finding a nice basis, which consists of short and almost orthogonal vectors. Recall that for a basis B of L, the fundamental parallelepiped is P (B) = {Bx | x ∈ [0, 1)n }. Furthermore, if L is full rank, then the determinant of L is defined as Vol(P (B)) = | det(B)|, and this is independent of the choice of a basis. The determinant is inversely proportional to the density of a lattice. We say that an n × n matrix M is unimodular if all entries of M are integers, and | det(M )| = 1. Last time we saw that a matrix U is unimodular if and only if U −1 is unimodular. This implies that an inverse of a unimodular matrix has integer entries. Unimodular matrices are interesting for us, because two lattice bases B1 and B2 are equivalent if and only if B1 = U B2 , for some unimodular matrix U . Moreover two bases are equivalent if and only if one can be obtained from the other by the following operations: • bi ← bi + k · bj , for i =  j and k ∈ Z, • swapping vectors: bi ↔ bj , • bi ← −bi . Last time, we proved the following theorem, which we will need for the proof of Minkowski’s theorem. Theorem 1 (Blichfield) For any full rank lattice L and measurable set S ⊆ Rn with Vol(S) > det(L), there exist distinct z1 , z2 ∈ S such that z1 − z2 ∈ L. 2 Minkowski’s theorem Theorem 2 (Minkowski’s Theorem) If L is a full rank lattice, and S any centrally-symmetric convex set of volume greater than 2n · det(L), then K contains a nonzero point of L. Proof Consider the set Ŝ = 12 S. Then Vol(Ŝ) = 2−n Vol(S) > det(L) by assumption. So we can apply Blichfield’s theorem to conclude that there exist distinct points z1 , z2 ∈ Ŝ such that z1 − z2 ∈ L. In particular, 2z1 , 2z2 ∈ K. Since K is centrally-symmetric, we also have −2z2 ∈ K. Hence the point z1 − z2 = 12 (2z1 + (−2z2 )) is in K since it is convex. This theorem is very useful in many settings. For one, many nice number theory theorems follow from it. It also guarantees that the length λ1 (L) of the shortest vector in the lattice is not too big. 19-1 Corollary 3 For any full-rank lattice L, λ1 (L) ≤ √ n · (det L)1/n . Proof We n for some radius r. This ball contains the hypercube  r),  n first bound the volume of the ball B(0, − √rn , √rn . Hence, its volume is greater than √2rn . √ For r = n · det(L)1/n , the volume of B(0, r) is greater than 2n · det(√ L), so the ball contains a nonzero lattice vector, and therefore, the length of the shortest vector is at most n · det(L)1/n . The above corollary easily generalizes to other minima. For instance, we will see in a problem set that 1/n  n  √ λi (L) ≤ n · (det L)1/n , i=1 where λi (L) is the length of the ith shortest vector. 3 Algorithmic questions One could ask, for instance, if the bound given above for λ1 (L) is tight, and when it holds. Here we will focus on the algorithmic aspect of lattices. There are several interesting questions that one can ask for lattices. We assume that all lattices have integer coordinates. This is the same as giving them rational coordinates, since we can always multiply all coordinates of all vectors by the least common multiple of their denominators. • Shortest Vector Problem (SVP): Find the shortest vector in L. Finding just the length of the shortest vector is equivalent. • Closest Vector Problem (CVP): Find the vector in L closest to some given point p. Both of the above problems are NP-hard, so one usually focuses on the approximate version of them: “Find a vector within γ of the optimum”. Some similar questions, like “Does a vector of a given length exist?” turn out to be non-equivalent. For the approximation versions of SVP and CVP, the gaps between the best known upper and lower bounds are very large. For instance, the best polynomial time algorithms for these problems get approxi­ mation factors which are essentially exponential in n. The best known factor is roughly 2O(n log log n/ log n) . The best exact algorithm runs in 2O(n) time. It turns out that one cannot find the vector guaranteed by Minkowski’s Theorem. SVP is hard to approximate within any constant factor √ unless NP = RP. CVP is hard to approximate within nO(1/ log log n) . Approximation within the factor n is in NP ∩ co-NP. 4 Lattice basis reduction We will show a polynomial time algorithm to approximately solve the SVP within a factor of 2O(n) . Because of an exponential error this might seem to be a very weak and useless result. Nevertheless, this algorithm is good enough to give extremely striking results both in theory and practice. For instance, it can be used to show that an integer program with a constant number of variables can be solved in polynomial time. 4.1 Review of the Gram–Schmidt algorithm Since our approach resembles the Gram–Schmidt algorithm, we first review this method for orthogonalizing a basis for inner product spaces. We are given a basis b1 , . . . , bn for a vector space, and we want to construct an orthogonal basis b1 , . . . , bn such that span(b1 , . . . , bk ) = span(b1 , . . . , bk ), for all k ∈ {1, . . . , k}. In the Gram–Schmidt algorithm, the vectors bi are usually normalized, but we will not do it here. The process works as follows: 19-2 • Let b1 := b1 . • For k = 2 to n: bk := bk − [projection of bk onto span(b1 , . . . , bk−1 )]. The projection is computed in the following way: projection of bk onto span(b1 , . . . , bk−1 ) = projection of bk onto span(b1 , . . . , bk−1 ) k−1 = projection of bk onto bi = i=1 k−1 i=1 bk · bi  b bi 2 i We set coefficients μki so that μkk = 1, and k bk = μki bi . i=1  Therefore, we can write the above as B = M B , where the basis vectors are rows of B and B  , and ⎤ ⎡ ⎤ ⎡ 1 0 0 ··· 0 0 0 ··· 0 μ11 ⎢ ⎢ 0 ··· 0 ⎥ 1 0 ··· 0 ⎥ ⎥ ⎢ μ21 ⎥ ⎢ μ21 μ22 = M =⎢ . ⎢ ⎥ . . . . . . . ⎥. .. .. .. .. .. ⎦ ⎣ .. .. .. ⎣ .. . .. ⎦ . μn1 μn2 μn3 · · · μnn μn1 μn2 μn3 · · · 1 Note that det(M ) = 1, so for lattices, we have Vol(B) = Vol(B  ), but since entries of M are not necessarily integers, L(B) = L(B  ) does not have to hold. However, B  can be used to bound the length λ1 (L(B)) of the shortest vector in L(B). Lemma 4 For any nonzero b ∈ L(B), b ≥ mini bi . Proof Every nonzero b ∈ L(B) can be expressed as b = integer. We have k k i λ i bi = b= i=1 λi i=1 and therefore, b k i=1 μij bj = λk bk + j=1 2 λi bi , where λk =  0 and for each λi is an k−1 k λi μij bj , j=1 i=1 ≥ λk bk ≥ bk 2 , which finishes the proof. 4.2 Gauss’s Algorithm We start by presenting an algorithm for solving the 2-dimensional SVP exactly. We call a basis u, v for a 2-dimensional lattice reduced if u ≤ v , and 2|u · v| ≤ u 2 . One can show that the following claim holds. Proposition 5 A reduced basis for a 2-dimensional lattice contains the first two successive minima of L. Sketch of Proof Rotate the plane, so that u = (u1 , 0), and v = (v1 , v2 ). We claim that the vector v is a vector with the smallest possible nonnegative second coordinate. The property 2|u · v| ≤ u 2 implies that v1 ∈ [− u21 , u21 ], which in turn implies that v is the shortest vector whose second coordinate is v2 . Because √ 3/2|u|, every vector whose second coordinate is greater than |v2 | (that is, at least 2|v2 |) has |v2 | ≥ √ √ length at least 3|u| and cannot be shorter than u. Therefore, u is the shortest vector. Also, since |v2 | ≥ 3/2|v|, 19-3 one can show that every vector with second coordinate greater than |v2 | has length at least implies that v is the shortest vector not generated by u. √ 3|v|. This A formal description of Gauss’s algorithm follows. While {u, v}, where u ≤ v , is not reduced: • Set v := v − mu, where m ∈ Z is chosen to minimize the length of v − mu. • If u ≤ v , break. • If v ≤ u , then swap u and v, and repeat. In the second step, if u ≤ v even after the reduction, the basis cannot be further reduced and one can prove that 2|u · v| ≤ u 2 . The algorithm is like a 2-dimensional discrete version of Gram–Schmidt, and is similar to the Euclidean GCD algorithm. Can we make it run in polynomial time? It turns out that it actually does run in polynomial time, but the proof of this fact is not obvious, and therefore, we do not present it here. Instead of this, we replace the termination criterion with If (1 − ε) u ≤ v , break. It is easy to prove that the modified algorithm gives an (1 − ε) approximate answer. Now in each reduction, we decrease the length of one of the vectors by at least a constant factor. Therefore the modified algorithm runs in weakly polynomial O(log( u + v )/ε) time. The proof that Gauss’s algorithm runs in polynomial time uses the fact that for a sufficiently small ε, after the modified algorithm stops, only one more reduction suffices to get a reduced basis. 4.3 Reduced bases We want to extend the notion of reduced bases to higher dimensions. In order to find a short vector in the lattice, we would like to perform a discrete version of the Gram–Schmidt. So we need to formalize the notion of being orthogonal in lattice problems. One way to do this is to say that the result of our procedure is “almost orthogonalized” so that doing Gram–Schmidt does not change much. In this section, we use the notation from Section 4.1. Definition 6 (Reduced bases) Let {b1 , . . . , bn } be a basis for a lattice L and let M be its Gram–Schmidt matrix defined above. Then {b1 , . . . , bn } is a reduced basis if it meets the following two conditions: 1. All the non-diagonal entries of M satisfy |μik | ≤ 1/2. 2. For each i, πSi bi Remark do. 2 ≤ 4 3 πSi bi+1 2 , where Si is the subspace orthogonal to span(b1 , . . . , bi−1 ). The constant 4/3 here is somewhat arbitrary. In fact, any number strictly between 1 and 4 will Remark Condition 2 is equivalent to bi+1 + μi+1,i bi 2 ≥ 34 bi 2 and one may think it as requiring that the projections of any two successive basis vectors bi and bi+1 onto Si satisfy a gapped norm ordering condition, analogous to what we did in Gauss’s algorithm for 2-dimensional case. 19-4