PUMaC 2009 · 加试 · 第 2 题
PUMaC 2009 — Power Round — Problem 2
题目详情
Problem 2.1 (3pts) . What are all the lattices in dimension one? (That is, specify their general form in the simplest possible terms.) 2 n Definition 2.2. A lattice L in dimension n is said to be full iff for every ~ a ∈ Z , there is a positive integer N so that N~ a ∈ L . For example, the lattice generated by { (1 , 1) , (1 , − 1) } is full. This is because, if ( a, b ) ∈ 2 Z , then 2( a, b ) = (2 a, 2 b ) = (( a + b ) + ( a − b ) , ( a + b ) − ( a − b )) = ( a + b )(1 , 1) + ( a − b )(1 , − 1). However, the lattice generated by { (6 , 12) , (10 , 20) } is not full. If you draw this then you will see why.
解析
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