A central problem in discrete geometry, known as Hadwigers covering problem, asks what the smallest natural number $Nleft(nright)$ is such that every convex body in ${mathbb R}^{n}$ can be covered by a union of the interiors of at most $Nleft(nright)$ 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 ${2n choose n}nln n$. In this note, we improve this bound by a sub-exponential factor. That is, we prove a bound of the order of ${2n choose n}e^{-csqrt{n}}$ for some universal constant $c>0$. Our approach combines ideas from previous work 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 $Nleft(nright)$ 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.
Download