Nearly Sharp Bounds for Lattice Coverings by Convex Bodies

Abstract

For an $n$-dimensional convex body $K$, let ${\theta }_L(K)$ denote its lattice covering density, and let ${\Theta }_L^{\mathrm{conv}}(n)$ and ${\Theta }_L^{\mathrm{sym}}(n)$ be the corresponding worst-case quantities over all convex bodies and over origin-symmetric convex bodies, respectively. Before this work, these quantities were known only to lie between a lower bound of order $n$ and an upper bound of order $n^2$, so even their polynomial order was undetermined. We prove that there are absolute constants $c,C>0$ such that \[ c n\log n \le Θ_L^{\mathrm{sym}}(n) \le Θ_L^{\mathrm{conv}}(n) \le Cn\log n\,(\log\log n)^{10/3+o(1)}. \] Thus both worst-case quantities are $n\log n(\log n{)}^{o(1)}$, and the upper and lower bounds differ by a factor at most $(\log \log n{)}^{10/3+o(1)}$. For the upper bound, a vertical--horizontal amplification based on weighted Boolean cubes combines covering estimates for low-codimensional sections into an exact lattice covering of an arbitrary convex body. For the lower bound, a random-slab construction and Poisson witnesses on flat tori show, with positive probability, that the resulting body admits no lattice covering of density below $cn\log n$.

45pp, lower bound improved to Ω(n log n), comments are welcome