JournalsjemsVol. 24, No. 4pp. 1431–1448

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

  • Han Huang

    University of Michigan, Ann Arbor, USA
  • Boaz A. Slomka

    Weizmann Institute of Science, Rehovot, Israel
  • Tomasz Tkocz

    Carnegie Mellon University, Pittsburgh, USA
  • Beatrice-Helen Vritsiou

    University of Alberta, Edmonton, Canada
Improved bounds for Hadwiger’s covering problem via thin-shell estimates cover
Download PDF

This article is published open access under our Subscribe to Open model.

Abstract

A central problem in discrete geometry, known as Hadwiger's covering problem, asks what the smallest natural number N(n)N(n) is such that every convex body in Rn\mathbb{R}^{n} can be covered by a union of the interiors of at most N(n)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 (2nn)nlnn{2n \choose n}n\ln n.

In this note, we improve this bound by a subexponential factor. That is, we prove a bound of the order of (2nn)ecn{2n \choose n}e^{-c\sqrt{n}} for some universal constant c>0c>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 KK with a translate of K-K; in fact, we get the same lower bound for the volume of the intersection of KK and K-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)N(n) when restricting our attention to convex bodies that are ψ2\psi_{2}. By a slightly different approach, an exponential improvement is established also for classes of convex bodies with positive modulus of convexity.

Cite this article

Han Huang, Boaz A. Slomka, Tomasz Tkocz, Beatrice-Helen Vritsiou, Improved bounds for Hadwiger’s covering problem via thin-shell estimates. J. Eur. Math. Soc. 24 (2022), no. 4, pp. 1431–1448

DOI 10.4171/JEMS/1132