Notes for UMich EECS 598 (2015): Homework 1

Hero image
Hero image

Notes for UMich EECS 598 (2015) are for Lattices in Cryptography virtually instructed by Chris Peikert (i.e., I taught myself using resources made available by him). This entry is for homework 1.

Update on 5 January 2020. I managed to give an ugly solution to the extra credit problem.

Problem 1. Given a generating set output the (positive) greatest common divisor of those elements. Euclidean algorithm for computing the GCD of two numbers runs in polynomial time, and the output is shorter than the input. Therefore, the total running time is polynomial.

Problem 2. Note that the two inequalities are equalities when For consider the basis where is a positive integer. The determinant bound is and the shortest Gram–Schmidt vector has length 1. We now consider any non-zero lattice point

  • When the smallest possible length is attained when
  • When its length is at least
  • When its length is at least

The above covers all possible cases. Therefore, we have

Problem 3(a). By definition, for any there exists unique s.t. which means for some This further translates into Therefore, is non-empty. Suppose then for some This means By the uniqueness of it follows that hence This completes the proof that the intersection is a singleton set.

Problem 3(b). Given find (using Gaussian elimination) real coefficients s.t. We then have

Problem 3(c). We use QDU decomposition. Suppose and where is orthogonal, is positive diagonal, and is upper-unitriangular. Let

First, we show only if for Let be a vector in this intersection, then for some s.t. Moving terms around and cancelling we get Suppose for the sake of contradiction that and that its last non-zero entry were the one. Using the upper-unitriangularity, we would get This is a contradiction because the left-hand side would be a non-zero integer. Therefore,

Next, we show that its translations using lattice points cover algorithmically. This amounts to solving from where is any vector in and the other symbols inherit their meanings from the first part. We solve from the last entry to the first. Suppose we have computed we then set This can be done efficiently and, by inspection, gives a correct solution.

Problem 4. The volume of an dimensional ball of radius is (This formula is due to Xianfu Wang.) Setting this to be at least we get (using Stirling’s formula)

Problem 5. We first show that its translations by lattice points do not overlap. Suppose for the sake of contradiction that for but We would have but by swapping the roles of in the above argument. Therefore, the translations of by lattice points do not overlap.

Next, for all points whose closest lattice point is unique, it is easy to verify that it lies in the translate of by the closest lattice point to it. If a point is closest to two distinct lattice points, it cannot be in a translate of by any lattice point.

(Assume the lattice is full-rank by convention.) The points whose closest lattice points are not unique form a null set (set of measure 0, i.e., rare). To see this, consider enumerating non-singleton closest lattice point set The set of points that have the same lengths to all points in has measure zero, so the union of countably many of them still has measure zero.

Voronoi cells (by George Chanturia)
Voronoi cells (by George Chanturia)

Extra Credit. I currently have no idea how to intrinsically extend Voronoi cell into a fundamental region. One can pathologically extend Voronoi cell to a fundamental region, using the axiom of choice. I still do not know how to do this non-pathologically.

Let be the family of supersets of s.t. its translations by lattice points do not overlap (i.e., a subset of a candidate fundamental region). Assign set-theoretic order to this family of sets.

For any chain take We now verify that It is obvious that Moreover, if for lattice points we have for Suppose for Since is a chain, WLoG we assume then which implies by the definition of and the fact that Therefore, we have It clearly is an upper bound of

By Zorn’s lemma, there exists a maximal element We now verify that is a fundamental region. Since its translations by lattice points do not overlap. Let If then Otherwise, we have due to the maximality of Clearly so there exists distinct lattice points s.t. Note that therefore, WLoG we assume for some giving us This completes the proof.

Note that the region can be made ‘prettier’ by restricting to contain only subsets of This way, the found fundamental region is bounded and measurable.

Please enable JavaScript to view the comments powered by Disqus.