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

Determining the minimum density of a covering of ${\mathbb{R}}^n$ by Euclidean unit balls as $n\to \mathrm{\infty }$ is a major open problem, with the best known results being the lower bound of $({\mathrm{e}}^{-3\mathrm{/}2}+o(1))n$ by Coxeter, Few and Rogers [Mathematika 6, 1959] and the upper bound of $(1\mathrm{/}2+o(1))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 $(1\mathrm{/}2+o(1))n\ln n$ such that, additionally, every point of ${\mathbb{R}}^n$ is covered at most $(\mathrm{1.79556...}+o(1))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 $(\mathrm{e}+o(1))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\mathrm{/}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$.