Bounds on the density of smooth lattice coverings

Abstract Let $$\cal{K}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>K</mml:mi> </mml:mrow> </mml:math> be a convex body in ℝ n , let L be a lattice with unit covolume, and let η &gt; 0. We say that $$\cal{K}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>K</mml:mi> </mml:mrow> </mml:math> and L form an η -smooth cover if each point x ∈ ℝ n is covered by (1 ± η )vol( $$\cal{K}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>K</mml:mi> </mml:mrow> </mml:math> ) translates of $$\cal{K}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>K</mml:mi> </mml:mrow> </mml:math> by L . We prove that for any positive σ and η , asymptotically as n → ∞, for any $$\cal{K}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>K</mml:mi> </mml:mrow> </mml:math> of volume n 3+ σ , one can find a lattice L for which $$\cal{K}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>K</mml:mi> </mml:mrow> </mml:math> , L form an η -smooth cover. Moreover, this property is satisfied with high probability for a lattice chosen randomly, according to the Haar–Siegel measure on the space of lattices. Similar results hold for random construction-A lattices, albeit with a worse power law, provided that the ratio between the covering and packing radii of ℤ n with respect to $$\cal{K}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>K</mml:mi> </mml:mrow> </mml:math> is at most polynomial in n . Our proofs rely on a recent breakthrough of Dhar and Dvir on the discrete Kakeya problem.