On the Gaussian Measure Over Lattices

摘要

We study the Gaussian mass of a lattice coset (n/a), where L ⊂ Rn is a lattice and t ∈ Rn is a vector describing a shift of the lattice. In particular, we use bounds on this Gaussian mass to obtain a partial converse to Minkowski's celebrated theorem bounding the number of lattice points in a ball.;We also consider the discrete Gaussian distribution DL--t,s induced by the Gaussian measure over L--t, and we use procedures for sampling from this distribution to construct the current fastest known algorithms for the two most important computation problems over lattices, the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP).;Finally, we study rhos(L--t ) and DL--t ,s as interesting computational and mathematical objects in their own right. In particular, we show that the computational problem of sampling from DL--t,s is equivalent to CVP in a very strong sense (and we show a much weaker result relating DL,s and SVP). We also prove a number of bounds on the moments of D L--t,s and various monotonicity properties of rhos(L--t).