OctoInformBeta

The optimal order of convex-body covering density

For an integer n≥2n\ge2, a convex body K⊂ℝnK\subset\mathbb R^n is a compact convex set with nonempty interior. For a full-rank lattice Λ⊂ℝn\Lambda\subset\mathbb R^n, write det⁡Λ\det\Lambda for its covolume. An exact lattice covering of KK is a covering K+Λ=ℝnK+\Lambda=\mathbb R^n by translates with centers in Λ\Lambda. The density of this covering is vol⁡n(K)/det⁡Λ\operatorname{vol}_n(K)/\det\Lambda, with Euclidean volume in the numerator. The lattice covering density θL(K)\theta_L(K) is the infimum of these densities over all exact lattice coverings of KK. The question is the growth with nn of the largest possible θL(K)\theta_L(K).

Rogers proved that every convex body admits a translative covering of density at most nlog⁡n+nlog⁡log⁡n+5nn\log n+n\log\log n+5n, with centers that need not form one lattice. For lattice coverings, Rogers obtained the bound nlog⁡2log⁡n+O(1)n^{\log_2\log n+O(1)}, and Ordentlich, Regev and Weiss the bound O(n2)O(n^2). Li and Liu proved θL(K)≤Cnlog⁡n(log⁡log⁡n)10/3+o(1)\theta_L(K)\le Cn\log n\,(\log\log n)^{10/3+o(1)} uniformly over convex bodies, with an absolute constant C>0C>0 and o(1)o(1) tending to zero as n→∞n\to\infty; their binary-correction companion lowers the exponent of log⁡log⁡n\log\log n to 23log⁡2(2πe)+o(1)\frac23\log_2(2\pi e)+o(1). Li and Liu also give, in every large enough dimension, bodies with lattice covering density at least cnlog⁡ncn\log n.

The preprint proves that there is an absolute constant C>0C>0 such that, for every integer n≥2n\ge2 and every convex body K⊂ℝnK\subset\mathbb R^n, one full-rank lattice Λ\Lambda gives an exact covering of density at most Cnlog⁡nCn\log n. With the lower bound of Li and Liu, the largest lattice covering density in dimension nn is of order nlog⁡nn\log n.

The Lean library LatticeCovering proves the preprint’s main theorem as the preprint states it, with no hypotheses beyond n≥2n\ge2 and KK being a convex body.

The results on these pages are those of the Lean library, each stated as the Lean library states it and linked to the Lean declaration behind it. Lean has checked every one of them, so the Lean library is the reference: where the preprint states a result differently, the statement on the page is the Lean library’s, and the preprint’s is given beside it. The preprint gives the results their order and their names.

The Lean library: LatticeCovering

LatticeCovering is a Lean library: 17 items, in six groups. Each has a page written by OctoInform, listed below.