Lecture 18: Lattices, Fundamental Parallelepiped and Dual of a Lattice, Shortest Vectors, Blichfield’s Theorem

18.409 An Algorithmist’s Toolkit 2009-11-12 Lecture 18 Lecturer: Jonathan Kelner 1 Scribe: Colin Jia Zheng Lattice Definition. (Lattice) Given n � linearly independent vectors b1 , · · · , bn ∈ Rm , the lattice generated by them is defined as L(b1 , b2 , · · · bn ) = { xi bi |xi ∈ Z}. We refer to b1 , · · · , bn as a basis of the lattice. Equivalently, if we define B as the m × n matrix whose columns are b1 , · · · , bn , then the lattice generated by B is L(B) = L(b1 , b2 , · · · , bn ) = {Bx|x ∈ Zn }. We say that the rank of the lattice is n and its dimension is m. If n = m, the lattice is called a full-rank lattice. It is easy to see that, L is a lattice if and only if L is a discrete subgroup of (Rn , +). Remark. We will mostly consider full-rank lattices, as the more general case is not substantially different. T Example. The lattice generated by (1, 0) and (0, 1)T is Z2 , the lattice of all integers points (see Figure 1(a)). T This basis is not unique: for example, (1, 1) and (2, 1)T also generate Z2 (see Figure 1 (b)). Yet another T T T T 2 basis of Z is given by (2005, 1) ; (2006, 1) . On the other hand, (1, 1) , (2, 0) is not a basis of Z2 : instead, it generates the lattice of all integer points whose coordinates sum to an even number (see Figure T 1 (c)). All the examples so far were of full-rank lattices. An example of a lattice that is not full is L((2, 1) ) (see Figure 1(d)). It is of dimension 2 and of rank 1. Finally, the lattice Z = L((1)) is a one-dimensional full-rank lattice. Figure 1: Lattices of R2 Image courtesy of Oded Regev. Used with permission. Definition. For matrix B, P (B) = {Bx|x ∈ [0, 1)n } is the fundamental parallelepiped of B. Examples of fundamental parallelepipeds are the gray areas in Figure 1. For a full rank lattice L(B), P (B) tiles Rn in the pattern L(B), in the sense that Rn = {P (B) + x : x ∈ L(B)}; see Figure 2. 18-1 Figure 2: P (B) tiles Rn Image courtesy of Oded Regev. Used with permission. In Figure 1, we saw that not every set of n linearly independent vectors B in a rank n full-rank lattice Λ is a basis of Λ. The fundamental parallelepiped characterizes exactly when B is a basis: Lemma. Let Λ be a rank n full-rank lattice and B an invertible n × n matrix. Then B is a basis (of Λ) if and only if P (B) ∩ Λ = {0}. Proof. “ ⇒ ” is obvious: Λ only contains elements with integer coordinates under B, and 0 is the only element of P (B) with integer coordinates. For “ ⇐ ”, need to show that any lattice point x = By satisfies yi ∈ Z. Note that By � with yi� = yi − �yi � is a lattice point in P (B). By our assumption By � = 0, ie yi ∈ Z. It is natural to ask when are two invertible matices A, B equivalent bases, ie bases of the same lattice. It turns out that this happens if and only if A, B are related by a unimodular matrix. Definition. A square matrix U is unimodular if all entries are integer and det(U ) = ±1. Lemma. U is unimodular iff U −1 is unimodular. Proof. Suppose U is unimodular. Clearly U −1 has ±1 determinant. To see that U −1 has integer entries, note that they are simply signed minors of U divided by det(U ). Lemma. Nonsingular matrices B1 , B2 are equivalent bases if and only if B2 = B1 U for some unimodular matrix U . Proof. “⇒”: Since each column of B1 has integer coordinates under B2 , B1 = B2 U for some integer matrix U . Similarly B2 = B1 V for some integer matrix V . Hence B1 = B1 V U , ie V U = I. Since V, U are both integer matrices, this means that det(U ) = ±1, as required. “⇐”: Note that each column of B2 is contained in L(B1 ) and vice versa. Corollary. Nonsingular matrices B1 , B2 are equivalent if and only if one can be obtained from the other by the following operations on columns: 1. bi ↔ bi + kbj for some k ∈ Z 2. bi ↔ bj 3. bi ← −bi Now that it is clear that bases of a lattice have the same absolute determinant, we can proceed to define the determinant of lattice: Definition. (Determinant of lattice) Let L = L(B) be a lattice of rank � n. We define the determinant of L, denoted det(L), as the n-dimensional volume of P (B), ie det(L) = det(B T B). In particular if L is a full rank lattice, det(L) = |det(B)|. 18-2 1.1 Dual lattices Definition. The dual Λ∗ of lattice Λ is {x ∈ Rn : ∀v ∈ Λ, x · v ∈ Z}. Equivalently, the dual can be viewed as the set of linear functionals from Λ to Z. Figure 3: Dual lattice Image courtesy of Oded Regev. Used with permission. Definition. For matrix B, its the dual basis B ∗ is the unique basis that satisfies 1. span(B) = span(B ∗ ) 2. B T B ∗ = I Fact. (L(B))∗ = L(B ∗ ). Fact. (Λ∗ )∗ = Λ. Fact. det(Λ∗ ) = 2 1 det(Λ) . Shortest vectors and successive minima One basic parameter of a lattice is the length of the shortest nonzero vector in the lattice, denoted λ1 . How about the second shortest? We are not interested in the second/third/etc shortest vectors which happen to be simply scaler multiples of the shortest vector. Instead, one requires that the next “minimum” increases the dimension of the space spanned: Definition. The ith successive minimum of lattice Λ, λi (Λ), is defined to be inf{r| dim(span(Λ ∩ B̄(0, r)) ≥ i}. Figure 4: λ1 (Λ) = 1, λ2 Λ = 2.3 Image courtesy of Oded Regev. Used with permission. The following theorem, due to Blichfield, has various important consequences, and in particular can be used to bound λ1 . Theorem. (Blichfield) For any full-rank lattice Λ and (measurable) set S ⊆ Rn with vol(S) > det(Λ), there exist distinct z1 , z2 ∈ S such that z1 − z2 ∈ Λ. 18-3 Proof. Let B be a basis : y ∈ P (B)} and Sx to be = S ∩ (x + P (B)) (see of Λ. Define x + P (B) to be {x + y � Figure 5). Since S = x∈Λ Sx we conclude that vol(S) = x∈Λ vol(Sx ). Let Sˆx denote {z − x : z ∈ Sx }. � Then vol(Sˆx ) = vol(Sx ), ie x∈Λ vol(Sˆx ) = vol(S) > vol(P (B)). Therefore, there must exist nondisjoint Sˆx and Sˆy for x = � y. Consider any nonzero z ∈ Sˆx ∩ Sˆy , then z + x, z + y ∈ S and x − y = (z + x) − (z + y) ∈ Λ, as required. Figure 5: Blichfield’s theorem Image courtesy of Oded Regev. Used with permission. As a corollary of Blichfield’s theorem, we obtain the following theorem due to Minkowski, which says that any large enough centrally-symmetric convex set contains a nonzero lattice point. A set S is centrallysymmetric if it is closed under negation. It is easy to see that the theorem is false if we drop either of the central-symmetry or the convexity requirement. Theorem. (Minkowski) Let Λ be a full-rank lattice of rank n. Any centrally-symmetric convex set S with vol(S) > 2n det(Λ) contains a nonzero lattice point. 18-4