PuMAC 2009-10 Power Test Solution A Version 21 Problems; 86 Points 1 Notation Throughout the solutions we will refer to { (1 , 0 , . . . , 0) , (0 , 1 , . . . , 0) , . . . , (0 , 0 , . . . , 1) } as the n standard basis of Z . The vector with the i th entry equal to one and the rest zero will be denoted by e ~ . i 2 Lattices (4 Problems; 15 Points) Problem 2.1 (3pts) . What are all the lattices in dimension one (That is, specify their general form in the simplest possible terms). Let L be a lattice of dimension 1. If L 6 = { 0 } , L contains a smallest positive integer d . We claim that L = d Z . Suppose a ∈ L . By the division algorithm, write a = qd + r , 0 ≤ r < d . Then r = a − qd ∈ L and hence r = 0 by the minimality of d . Thus d | a , which shows L ⊂ d Z . The opposite containment is obvious. Including { 0 } , L = d Z for nonnegative integers d . Problem 2.2 (4pts) . Prove that the lattice in dimension n generated by a set S is full if n and only if every vector in Z is expressible as a rational linear combination of vectors in ∑ n S , i.e. if every ~ a ∈ Z is expressible in the form a x , where x ∈ S and a ∈ Q . i i i i n Suppose lattice L generated by S is full. Then given ~ a ∈ Z , N~ a ∈ L for some positive integer N , so N~ a can be written as an integral linear combination of vectors in S . Dividing through by N gives ~ a as a rational linear combination of vectors in S . n Conversely, given any ~ a ∈ Z , write it as a rational linear combination of vectors in S : ∏ p p 1 k ~ a = s ~ + · · · + s ~ . Multiplying through by N = q gives N~ a as an integral linear 1 k i q q 1 k combination of s , so N~ a ∈ L . i Problem 2.3 (4pts) . Is the lattice generated by { (2 , 1 , 6) , (5 , 6 , 8) , (1 , 1 , 2) } full? Since (2 , 1 , 6) + (5 , 6 , 8) = 7(1 , 1 , 2), the lattice generated by { (2 , 1 , 6) , (5 , 6 , 8) } is full if and only if the lattice generated by { (2 , 1 , 6) , (5 , 6 , 8) , (1 , 1 , 2) } is full. Now the condition in Problem 2.2 is that     ( ) 2 5 x a 1     1 6 y

a 2 6 8 z 1

has rational solutions a , a for any integer triple ( x, y, z ). Consider ( x, y, z ) = (0 , 0 , 1), 1 2 then 2 a + 5 a = 1 a + 6 a = 0. Solving for two unknowns with two equations yields 1 2 1 2 a = a = 0 as the only possible solution. We see that it is impossible to simultaneously also 1 2 have 6 a + 8 a = 1 so the lattice is not full. 1 2 Problem 2.4 (4pts) . Is the lattice generated by { (2 , 1 , 6) , (5 , 6 , 8) , (1 , 2 , 2) } full? We now wish to solve       2 5 1 a x 1       1 6 2 a = y . 2 6 8 2 a z 3 The matrix is invertible, having determinant 2(12 − 16) − 5(2 − 12) + 1(8 − 36) = 14 6 = 0. Multiplying both sides by the inverse on the left, which has rational entries, produces rational a for any triple ( x, y, z ), so this lattice is full. One can use other methods to solve this system i of equations as long as it is justified why the solution will be rational. 3 Determinant and Divisor (5 Problems; 17 Points) ~ ~ Problem 3.1 (2pts) . Show that ~ a + L = b + L if and only if ~ a − b ∈ L . ~ ~ ~ ~ ~ ~ If ~ a + L = b + L , then in particular ~ a + 0 ∈ b + L , so ~ a = b + l for some l ∈ L and thus ~ ~ ~ ~ ~ ~ ~ ~ ~ a − b = l ∈ L . Conversely, suppose ~ a − b ∈ L . For any l ∈ L , we have ~ a + l = b + ( ~ a − b + l ) ~ ~ ~ ~ ~ ~ ~ with ~ a − b + l ∈ L , so ~ a + l ∈ b + L . This shows ~ a + L ⊂ b + L . Since − ( ~ a − b ) = b − ~ a , ~ exchanging the roles of ~ a and b in the above argument shows the opposite containment. ~ Hence ~ a + L = b + L . ~ ~ Problem 3.2 (2pts) . Show that if ~ a − b / ∈ L , then ( ~ a + L ) ∩ ( b + L ) = ∅ . ~ ~ ~ ~ ~ We check the contrapositive: if ( ~ a + L ) ∩ ( b + L ) 6 = ∅ , then ~ a + l = b + l for some l ∈ L , 1 2 i ~ ~ ~ so ~ a − b = l − l ∈ L . 2 1 Problem 3.3 (3pts) . Let L be the lattice generated by { (1 , 2) , (2 , 1) } . Draw the colattices (0 , 0) + L , (0 , 1) + L , and (0 , 2) + L . If you drew the diagram correctly, it should sort of jump out that these are distinct colattices. If it doesn’t jump out, check your diagram! Now prove that these colattices are in fact distinct without using the diagram. Also, prove that L has no more colattices. Hence, conclude that det L = 3 . We show that ( a, b ) ∈ L iff 3 | a + b . Any ( a, b ) ∈ L has the form n (1 , 2) + m (2 , 1) = ( n + 2 m, 2 n + m ) for integers n and m , so a + b = 3( n + m ). Conversely, if 3 | a + b , then ( ) ( ) a + b a + b ( a, b ) = b − (1 , 2) + a − (2 , 1) ∈ L. 3 3 By the above criteria, the difference of any two distinct vectors in { (0 , i ) : i = 0 , 1 , 2 } does not lie in L . Then by Problem 3.1, (0 , i ) + L , i = 0 , 1 , 2, are distinct. For an arbitrary colattice ( a, b )+ L , 3 | a + b − i for i = 0 , 1 , or 2. Then ( a, b ) − (0 , i ) ∈ L , so ( a, b )+ L = (0 , i )+ L by Problem 3.1. Hence these are all the colattices, i.e. det L = 3. 2

Problem 3.4 (5pts) . , Prove that a lattice is full if and only if its determinant is finite. Suppose L is full. Then for each k = 1 , . . . , n , N e ~ ∈ L for some positive integer N . i i i Given any ~ a = ( a , . . . , a ) ∈ L , write a = q N + r , 0 ≤ r < N , by the division algorithm 1 n i i i i i i on each coordinate. Then ~ a − ( r , . . . , r ) = ( q N , . . . , q N ) = q ( N e ~ ) + · · · + q ( N e ~ ) ∈ L. 1 n 1 1 n n 1 1 1 n n n By Problem 3.1, ~ a + L = ( r , . . . , r )+ L . There are only finitely many colattices ( r , . . . , r )+ 1 n 1 n L with 0 ≤ r < N , so det L < ∞ . i i n Now suppose det L < ∞ . Then given ~ a ∈ Z , the colattices k~ a + L , k ∈ Z , cannot all be distinct, so k ~ a + L = k ~ a + L for some k > k . By Problem 3.1, this implies ( k − k ) ~ a ∈ L . 1 2 1 2 1 2 Taking N = k − k shows that L is full. 1 2 Problem 3.5 (5pts) . Prove that if L is a full lattice in dimension n , then its determinant n is divisible by (div L ) . n n Let div L be denoted by d so that we have the series of inclusions L ⊂ d Z ⊂ Z . There n n n n are d colattices of d Z in Z explicitly given as A = { ( a , . . . , a ) + d Z | 0 ≤ a ≤ d − 1 } . 1 1 n i Consider the set of colattices of L which we will denote A . A function f : A → A can be 2 2 1 n ~ defined by f ( ~ a + L ) = ~ a + d Z . Note that it does not matter if we choose a different b to n ~ represent the same collatice because then ~ a − b ∈ L ⊂ d Z so they define the same collatice n − 1 n n of d Z . Let f ( ~ a + d Z ) denote the subset of A which maps to ~ a + d Z by f . This set 2 is non-empty and its size does not vary as we vary the collatice in A . Indeed, let c be 1 i − 1 n n such that { c + L | 1 ≤ i ≤ k } = f ( d Z ). For any ~ a + d Z ∈ A it is easy to check that i 1 − 1 n − 1 n { ~ a + c + L | 1 ≤ i ≤ k } = f ( ~ a + d Z ). Now A has been partitioned by the f ( ~ a + d Z ) i 1 n n n into d distinct sets each of size k . We conclude that kd = det L and so (div L ) divides the determinant of L . 4 Finite Generation (3 Problems; 13 Points) Problem 4.1 (3pts) . Prove that if L % L , then det L < det L (or both are ∞ ). 1 2 1 2 Let A and A be the sets of colattices of L and L respectively so that the size of A 1 2 1 2 i is det L . If A is an infinite set, then we are already done. Let A be a finite set. We can i 2 2 define a function f : A → A by sending a colattice ~ a + L ∈ A to ~ a + L ∈ A . Note 2 1 2 2 1 1 ~ ~ ~ that if ~ a + L = b + L then ~ a + L = b + L because of Problem 3.1 and ~ a − b ∈ L ⊂ L . 2 2 1 1 2 1 Furthermore, every collatice in A is mapped to by some collatice in A simply by considering 1 2 n f ( ~ a + L ) = ~ a + L for any ~ a ∈ Z . Therefore, the number of elements of A is less than 2 1 1 or equal to the number of elements of A . To prove the strict inequality, we need to exhibit 2 ~ ~ two colattices in A mapping to the same colattice in A . Take l ∈ L with l / ∈ L , then 2 1 1 2 ~ ~ ~ f ( l + L ) = f ( 0 + L ) = L but l + L 6 = L . 2 2 1 2 2 Problem 4.2 (5pts) . Prove that every full lattice has a full sublattice that is finitely gener- ated. 3

n Let L denote our full lattice in Z and let e ~ for 1 ≤ i ≤ n be the standard basis. By the i definition of fullness, there exist positive integers N for 1 ≤ i ≤ n such that N e ~ ∈ L . The i i i lattice K generated by { N e ~ } is a sublattice of L because any integer linear combination i i of vectors in a lattice is still a vector in the lattice. To see that K is full, take any ~ a ∈ Z ∑ ∏ written as ~ a = k e ~ , then N ~ a is in K . i i i Problem 4.3 (5pts) . Prove that every full lattice if finitely generated. We combine the last two problems to solve this problem. Consider the set of finitely generated full sublattices of L . These lattices have finite determinant by Problem 3.4 and so by the well ordering principle, there must be a finitely generated full sublattice M with ~ ~ minimal determinant. Assume M does not equal to L so that we can take l ∈ L with l / ∈ M . ~ The generators of M together with l generate a finitely generated full sublattice of L which ′ ′ ′ ′ we will call M . Clearly M % M so by Problem 4.1 det M < det M . Therefore M violates the minimality of M so it must have been that M = L and L is finitely generated. 5 Isomorphism Types of Lattices (7 Problems; 28 Points) n Definition 5.1. Two lattices L and L in Z are said to be isomorphic iff there exists a 1 2 n n n m linear bijection f : Z → Z which is also a bijection from L to L . [A map f : Z → Z 1 2 ~ ~ ~ ~ is said to be linear iff f ( 0) = 0, and f ( ~ a + b ) = f ( ~ a ) + f ( b )]. 2 2 For example, the linear bijection f : Z → Z defined by f ( x, y ) = (5 x + 2 y, 2 x + y ) is also a bijection from the lattice L generated by { (2 , 1) , (1 , 2) } to the lattice L generated 1 2 by { f (2 , 1) , f (1 , 2) } = { (12 , 5) , (9 , 4) } ; hence L and L are isomorphic. Note that L is also 1 2 2 the lattice generated by { (3 , 0) , (0 , 1) } . Problem 5.1 (2pts) . Prove that div is an isomorphism invariant. n n Let the two lattices L and L be isomorphic by the bijective linear map f : Z → Z . 1 2 n First we show that for any ~ a ∈ Z and any d a positive integer, f ( d~ a ) = df ( ~ a ). This is true for d = 1. If it is true for d then it is true for d + 1 by f ((1 + d ) ~ a ) = f ( ~ a + d~ a ) = f ( ~ a ) + f ( d~ a ) = f ( ~ a ) + df ( ~ a ) = (1 + d ) f ( ~ a ) . If the divisors of L and L are denoted d and d respectively then this shows that because 1 2 1 2 every member of L is of the form d ~ a then so is every member of L . Now d ≥ d by 1 1 1 2 1 − 1 definition. Taking f reverses the roles to obtain d ≥ d and therefore d = d . 1 2 1 2 Problem 5.2 (2pts) . Prove that det is an isomorphism invariant. n n Let two lattices L and L be isomorphic by the bijective linear map f : Z → Z . 1 2 Consider a collatice ~ a + L which maps by f to f ( ~ a ) + f ( L ) = f ( ~ a ) + L . Therefore f maps 1 1 2 − 1 collatices to collatices. The inverse map f is an inverse to that map on collatices, so the number of collatices of L is equal to the number of collatices of L . 1 2 Problem 5.3 (3pts) . Are the lattices generated by { (3 , 0) , (0 , 5) } and { (1 , 0) , (0 , 15) } iso- morphic? 4

Yes, the lattices are isomorphic. This follows from Problem 5.6 below, since both lattices have divisor 1 and determinant 15. Problem 5.4 (3pts) . Are the lattices generated by { (2 , 0) , (0 , 4) } and { (1 , 0) , (0 , 8) } isomor- phic? No, the lattices are not isomorphic. This follows from Problem 5.1 above since the divisors are 2 and 1 respectively. 2 Problem 5.5 (4pts) . For any two integers d ≥ 1 and ∆ ≥ 1 with ∆ divisible by d , give an 2 example of a lattice in Z with divisor d and determinant ∆ . 2 Consider the lattice L generated by { ( d, 0) , (0 , ∆ /d ) } . Since d divides ∆, we know that d divides ∆ /d . Thus the divisor of L is at least d . By looking at the first generator, we conclude that the divisor of L is at most d . Thus div L = d . Also we certainly have det L = d · (∆ /d ) = ∆. 2 Problem 5.6 (7pts) . Prove that if two full lattices in Z have the same determinant and 2 same divisor then they are isomorphic. Conclude that all full lattices in Z are isomorphic to one of the lattices from problem 5.5 (don’t forget the result of problem 3.5). By rescaling, it suffices to treat the case that d = 1. Suppose we are given a full lattice L in dimension two with div L = 1 and det L = ∆. We would like to show that L is isomorphic to the lattice generated by { (1 , 0) , (0 , ∆) } . Since L is full, we know that ( E, 0) ∈ L for some large E . Pick the smallest such E , and let ~ a = (0 , E ) ∈ L . Now again since L is full, the set of y -coordinates of vectors in L ~ contains some elements other than zero. Thus we can find a vector b = ( C, D ) ∈ L where ~ C > 0 is as small as possible. From our choice of vectors, it is clear that ~ a and b generate L . Thus since div L = 1, we know that gcd( C, D, E ) = 1. Thus there exists an integer k such that gcd( C, D + kE ) = 1. WLOG, we may assume that k = 0. Thus gcd( C, D ) = 1, C D so there exist integers x, y with Cx + Dy = 1. Now consider the matrix M = ( ). Since − y x − 1 det M = Cx + Dy = 1, M is invertible and M has integer entries. Thus we may apply − 1 ′ the matrix M to the generators of L and get generators of an isomorphic lattice L . Since ′ ~ M (1 , 0) = b , we conclude that (1 , 0) ∈ L . Now we are done, since every lattice containing (1 , 0) is equal to the lattice generated by { (1 , 0) , (0 , P ) } for some integer P . Comparing determinants, we conclude that P = ∆, so the desired isomorphism is demonstrated. Problem 5.7 (7pts) . Prove that divisor and determinant do not characterize lattices in 3 dimension three. That is, construct two lattices L and L in Z which have the same 1 2 determinant and the same divisor but which are not isomorphic. Let L be the lattice generated by { (1 , 0 , 0) , (0 , 2 , 0) , (0 , 0 , 2) } and let L be the lattice 1 2 generated by { (1 , 0 , 0) , (0 , 1 , 0) , (0 , 0 , 4) } . Both L and L have divisor 1 and determinant 4. 1 2 3 By inspection, we see that for any vector ~ a ∈ Z , it is true that 2 ~ a ∈ L . This property 1 is clearly preserved under isomorphism. However, the vector ~ a = (0 , 0 , 1) satisfies 2 ~ a / ∈ L . 2 Thus L and L are not isomorphic. 1 2 5

6 Canonical Form (2 Problems; 13 Points) The following theorem is true (proving it is not part of this test). Theorem 6.1. Every lattice in dimension n is isomorphic to the lattice generated by { d ~ e , . . . , d ~ e } (6.1) 1 1 n n for some d ∈ N ∪ { 0 } where d | d . Furthermore, the sequence of integers ( d ; . . . ; d ) is i i i +1 1 n isomorphism invariant; it is called the signature of the lattice. You may assume it is true for any of your work on problems appearing after this point in the test. Problem 6.1 (5pts) . Calculate the signature of the lattice generated by: { (2 , 2 , 0) , (0 , 3 , 3) } (6.2) Since the signature is isomorphism-invariant, we will change the base space slightly, and take the given lattice (call it L ) to be the lattice generated by { (2 , 2 , 0) , (3 , 0 , 3) } . We can do that by the isomorphism that switches the first two coordinates of an element [so (2 , 2 , 0) goes to itself, and (0 , 3 , 3) goes to (3 , 0 , 3)]. So it is enough to find the signature of this lattice. But we immediately have (3 , 0 , 3) − (2 , 2 , 0) = (1 , − 2 , 3) and (2 , 2 , 0) − 2(1 , − 2 , 3) = (0 , 6 , − 6), so that our lattice L is in fact generated by (1 , − 2 , 3) and (0 , 6 , − 6). So now, call (1 , − 2 , 3) = e 1 n and (0 , 1 , − 1) = e . It is easy to show that in Z , these basis vectors are exactly equivalent 2 to the usual definitions of e = (1 , 0 , 0) and e = (0 , 1 , 0). In particular, the lattice L is 1 2 generated by 1 e and 6 e and 0 e . So, since we have isomorphism invariance, the lattice 1 2 3 must also be generated by { 1(1 , 0 , 0) , 6(0 , 1 , 0) , 0(0 , 0 , 1) } . Hence, the signature of the lattice is (1; 6; 0). Problem 6.2 (8pts) . Calculate the signature of the lattice generated by: { (0 , 2 , 5 , 3) , (5 , 4 , 5 , 7) , (5 , 9 , 7 , 1) , (5 , 7 , 5 , 7) } (6.3) The signature is (1; 1; 3; 180). In general, a lattice can be represented by a matrix M with columns generating the lattice. The same lattice is generated if one replaces the columns by invertible linear combinations. One can also obtain an isomorphic lattice by taking bijective linear transformations of the n underlying Z which amounts to replacing the rows by invertible linear combinations. The goal is to compute the signature of the lattice by transforming the matrix M into a diagonal matrix. In this case M is the 4 by 4 matrix   0 5 5 5   2 4 9 7   .   5 5 7 5 3 7 1 7 6

By using the third column to eliminate the bottom row and one obtains   − 15 − 30 5 − 30   − 25 − 59 9 − 56   .   − 16 − 44 7 − 44 0 0 1 0 Using the fourth row, one can now elminate the entries in the third column and we are now left with the remaining three by three matrix   15 30 30   25 59 56 . 16 44 44 Subtracting the first row from the second and third, then clearing out the first column with the last row yields   0 − 180 − 180   0 − 111 − 114 . 1 14 14 Clearing out the bottom row now leaves us with a two by two matrix which we easily reduce in a few steps: ( ) ( ) ( ) 180 180 180 0 3 0 → → 111 114 111 3 0 180 This solution is very close to a proof of Theorem 6.1. See if you can figure it out. 7