PUMaC 2007 · 加试

PUMaC 2007 Power Test: Lattices A real n -dimensional lattice Λ is a set of n -tuples ( a , a , . . . , a ) of real numbers with the 1 2 n following properties:

1. The all-zero-tuple 0 = (0 , 0 , . . . , 0) belongs to Λ.
2. If u = ( a , a , . . . , a ) and v = ( b , b , . . . , b ) belong to Λ, then so do − u = ( − a , − a , . . . , − a ) 1 2 n 1 2 n 1 2 n and u + v = ( a + b , a + b , . . . , a + b ). 1 1 2 2 n n 2 For example, the set Z of ordered pairs of integers forms a lattice, as does the trivial n - dimensional lattice, which consists of the single n -tuple 0 . The distance between two n -tuples ( a , a , . . . , a ) and ( b , b , . . . , b ) in a lattice Λ is the 1 2 n 1 2 n √ 2 2 2 standard Euclidean distance ( b − a ) + ( b − a ) + . . . + ( b − a ) . 1 1 2 2 n n Given a lattice Λ, we refer to its elements as either points , or the vectors they represent. For the problems below, show all your work and give justification for all answers, unless other- wise indicated. Answers given without justification will not be given full credit. 1 Minimal Vectors The minimal vectors of a lattice are the ones (other than the 0 vector) represented by the points closest to the origin, 0 . The norm of a minimal vector is the square of the distance from the point that represents it to the origin. The norm of a minimal vector of a lattice is called the minimal 2 norm of that lattice. In Z , the minimal vectors are (1 , 0), (0 , 1), ( − 1 , 0), and (0 , − 1). 1 a) How many minimal vectors are there in the 1-dimensional lattice Z ? 3 b) How many minimal vectors are there in the 3-dimensional lattice Z ? m c) Given any integer m , how many minimal vectors are there in the m -dimensional lattice Z ? 1

n The checkerboard lattice D is the set of all points in Z for which the sum of all n coordinates n is even. d) How many minimal vectors are there in D ? 3 e) Given any integer m , how many minimal vectors are there in D ? m 2 Bases 3 3 Consider the lattice Z . We can find three vectors v , v , v such that any vector in Z may be 1 2 3 3 ∑ expressed in the form k v , where k , k , k are integers. The vectors v , v , v are then called i i 1 2 3 1 2 3 i =1 3 3 a basis for the lattice Z . The vectors (1 , 0 , 0), (0 , 1 , 0), and (0 , 0 , 1) form a basis for Z , because 3 any vector ( a, b, c ) ∈ Z can be expressed as ( a, b, c ) = a (1 , 0 , 0) + b (0 , 1 , 0) + c (0 , 0 , 1), and the coefficents a , b , and c are integers. m a) Give a basis for Z . b) Give a basis for D . m c) Consider the 8-dimensional lattice with basis vectors (2 , 0 , 0 , 0 , 0 , 0 , 0 , 0) , ( − 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0) , (0 , − 1 , 1 , 0 , 0 , 0 , 0 , 0) , (0 , 0 , − 1 , 1 , 0 , 0 , 0 , 0) , (0 , 0 , 0 , − 1 , 1 , 0 , 0 , 0) , (0 , 0 , 0 , 0 , − 1 , 1 , 0 , 0) , (0 , 0 , 0 , 0 , 0 , − 1 , 1 , 0) , 1 1 1 1 1 1 1 1 ( , , , , , , , ) . 2 2 2 2 2 2 2 2 Which points can be in this lattice, what is the minimal norm, and how many minimal vectors are there? The lattice given in part (c) is called the E diamond lattice . 8 3 3 d) Prove that we can describe the lattice Z with D as follows: Z consists of all points in 3 D and all points which are obtained by adding the vector (1 , 1 , 1) to a point in D . (We shall 3 3 3 denote this by Z = D ∪ ( D + (1 , 1 , 1)).) 3 3 e) Give a similar description of E in terms of D . 8 8 2

3 Sphere Packings Lattices can be useful for describing sphere packings , the classical problem of finding how densely a large number of identical spheres can be packed together, wasting as little space as possible. The sphere-packing problem can be generalized to any number of dimensions. In two dimensions, we have circle-packing. In 500 dimensions, we have the packing of 500-dimensional hyperspheres. The density of a packing is defined as the fraction of the total volume (or area, or n-dimensional volume) occupied by the spheres. For the purposes of this problem, packings will always tessellate n -dimensional space, so their density can be calculated by analyzing one tessella. If the centers of the spheres of a packing form a lattice, we say that a basis for this lattice is also a basis for the packing. For simplicity, we will consider only packings of n -dimensional space extending infinitely in all directions, not of containers with boundaries. a) Draw a diagram of the densest (2-dimensional) circle packing. No justification is necessary. If we place the center of one circle at the origin, the centers of the circles in the packing from part (a) form a lattice which we call A . We will give the name A to any lattice having this shape 2 2 (so the lattice is only unique up to rotation and scale about the origin). 1 b) Find a basis for your packing from part (a) if your circles have radius and lie in the xy - 2 plane. √ 2 3 c) If the circles from part (a) have radius and are placed on the plane x + y + z = 0 in R , prove 2 that (1 , − 1 , 0) and (0 , 1 , − 1) form a basis for the packing, up to rotation. d) Find the density of the packing in parts (b) and (c). e) The densest sphere-packing in three dimensions is believed (but not proven) to be one represented by the lattice D . Compute the maximum density of this packing. 3 4 Sub-Lattices of E 8 n ∑ Two n -dimensional vectors ( v , v , . . . , v ) and ( u , u , . . . , u ) are perpendicular if v u = 0. 1 2 n 1 2 n i i i =1 For example, the 5-dimensional vectors (1 , 4 , − 3 , 2 , 8) and ( − 1 , 1 , 3 , − 5 , 2) are perpendicular because 1 · ( − 1) + 4 · 1 + ( − 3) · 3 + 2 · ( − 5) + 8 · 2 = 0. a) Given a vector v ∈ E , the set of vectors in E that are perpendicular to v form the lattice 8 8 3

1 1 1 1 1 1 1 1 E . Taking v = ( , , , , , , , ), describe the resulting lattice E , giving necessary and suf- 7 7 2 2 2 2 2 2 2 2 ficient conditions for a point to be in the lattice, as well as the minimal norm and the number of minimal vectors. Any n -dimensional lattice L has a dual lattice L ∗ consisting of all n-dimensional vectors n n n ∑ ( x , x , . . . , x ) such that x u is an integer for every vector ( u , u , . . . , u ) ∈ L . 1 2 n i i 1 2 n n i =1 1 1 1 1 1 1 3 3 b) One of the minimal vectors in E ∗ is ( , , , , , , − , − ). How many minimal vectors 7 4 4 4 4 4 4 4 4 are there in E ∗ ? 7 Given a subset Λ of E that forms a (rotated) lattice A , all the vectors in E that are perpen- 8 2 8 dicular to every vector in Λ form the lattice E . 6 1 1 1 1 1 1 1 1 c) Prove that (1 , 0 , 0 , 0 , 0 , 0 , 0 , 1) and ( , , , , , , , ) form a basis for A . 2 2 2 2 2 2 2 2 2 d) Using the version of A from (c), find the minimal vectors of E . 2 6 e) Find the minimal vectors of E ∗ . 6 5 Complex Lattices A complex lattice is a lattice with complex coordinates instead of real coordinates. A complex n -dimensional Gaussian lattice Λ has a basis v , v , . . . , v of vectors with complex coordinates, and 1 2 n n ∑ any vector in Λ may be expressed in the form k v , where k , k , . . . , k are Gaussian integers . i i 1 2 n i =1 The Gaussian integers G are the numbers of the form a + bi , where a and b are integers. The ordered pair ( x, y ) can be used to represent the complex number x + yi , so any 2 n - dimensional real lattice can be expressed as an n -dimensional complex lattice. For example, the 2 1 lattice Z is the complex lattice G . 2 m a) Express the real lattice Z as an m -dimensional complex lattice over the Gaussian integers. Another sort of complex lattice can be defined over the Eisenstein integers E (instead of the Gaussian integers), the set of numbers of the form a + bω , where a and b are real integers and √ − 1+ 3 i 3 ω = . (Note that ω = 1.) The Eisenstein integers are useful for expressing hexagonal and 2 4

diamond lattices as complex lattices. For example, the lattice A can be simply expressed as the 2 1 complex lattice E . √ b) Consider the complex 3-dimensional Eisenstein lattice with basis vectors ( 3 i, 0 , 0), (1 , − 1 , 0), and (1 , 0 , − 1). Find the minimal vectors of this lattice, and show that the lattice is equivalent to E ∗ (ie., that it has the same properties as the lattice found in part (e) of question 4). 6 5