Nearly Sharp Bounds for Lattice Coverings by Convex Bodies

For an $n$-dimensional convex body $K$, let ${\theta }_L(K)$ denote its lattice covering density, and let ${\mathrm{\Theta }}_L^{\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}}(n)$ and ${\mathrm{\Theta }}_L^{\mathrm{s}\mathrm{y}\mathrm{m}}(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 $$cn\log n\le {\mathrm{\Theta }}_L^{\mathrm{s}\mathrm{y}\mathrm{m}}(n)\le {\mathrm{\Theta }}_L^{\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}}(n)\le Cn\log n(\log \log n{)}^{10\mathrm{/}3+o(1)}\mathrm{.}$$ 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\mathrm{/}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$.