Covering large-dimensional Euclidean spaces by random translates of a given convex body

Abstract

Determining the minimum density of a covering of ${\mathbb{R}}^n$ by Euclidean unit balls as $n\to \infty$ is a major open problem, with the best known results being the lower bound of $\left({\mathrm{e}}^{-3/2}+o(1)\right)n$ by Coxeter, Few and Rogers [Mathematika 6, 1959] and the upper bound of $\left(1/2+o(1)\right)n\ln n$ by Dumer [Discrete Comput. Geom. 38, 2007]. We prove that there are ball coverings of ${\mathbb{R}}^n$ attaining the asymptotically best known density $\left(1/2+o(1)\right)n\ln n$ such that, additionally, every point of ${\mathbb{R}}^n$ is covered at most $\left(\mathrm{1.79556...}+o(1)\right)n\ln n$ times. This strengthens the result of Erdős and Rogers [Acta Arith. 7, 1961/62] who had the maximum multiplicity at most $\left(\mathrm{e}+o(1)\right)n\ln n$. On the other hand, we show that the method that was used for the best known ball coverings (when one takes a random subset of centres in a fundamental domain of a suitable lattice in ${\mathbb{R}}^n$ and extends this periodically) fails to work if the density is less than $(1/2+o(1))n\ln n$; in fact, this result remains true if we replace the ball by any convex body $K$. Also, we observe that a ``worst'' convex body $K$ here is a cube, for which the packing density coming from random constructions is only $(1+o(1))n\ln n$.