Improved bounds for Hadwiger’s covering problem via thin-shell estimates

Abstract

A central problem in discrete geometry, known as Hadwiger's covering problem, asks what the smallest natural number $N(n)$ is such that every convex body in ${\mathbb{R}}^n$ can be covered by a union of the interiors of at most $N(n)$ of its translates. Despite continuous efforts, the best general upper bound known for this number remains as it was more than sixty years ago, of the order of $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)n\ln n$.

In this note, we improve this bound by a subexponential factor. That is, we prove a bound of the order of $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)e^{-c\sqrt{n}}$ for some universal constant $c>0$.

Our approach combines ideas from [3] by Artstein-Avidan and the second named author with tools from asymptotic geometric analysis. One of the key steps is proving a new lower bound for the maximum volume of the intersection of a convex body $K$ with a translate of $-K$; in fact, we get the same lower bound for the volume of the intersection of $K$ and $-K$ when they both have barycenter at the origin. To do so, we make use of measure concentration, and in particular of thin-shell estimates for isotropic log-concave measures.

Using the same ideas, we establish an exponentially better bound for $N(n)$ when restricting our attention to convex bodies that are ${\psi }_2$. By a slightly different approach, an exponential improvement is established also for classes of convex bodies with positive modulus of convexity.