The optimal order of convex-body covering density

The explanation

Cover a floor with square tiles and nothing overlaps. Every point sits under exactly one tile. Try the same with round coins and it fails. Circles leave gaps, so some coins must overlap. Take coins of radius 1 and put their centres on a honeycomb grid, just close enough to leave no gap. Each centre then owns a hexagon of area about 2.598. Each coin has area π, about 3.142. So a typical point sits under about 3.142 / 2.598 = 1.21 coins.

That average is the covering density. It counts how many copies cover a typical point, overlaps included. The square scores 1, the lowest possible. Mathematicians ask the same question for any convex body in any dimension n. A convex body is a solid shape with no dents or holes, like a ball or a cube. The copies may only slide, never turn. The big question is about the worst shape. How high must the density be for the hardest body in dimension n?

In 1957, C. A. Rogers gave an upper limit for every convex body in dimension 3 or more. His coverings have density at most n log n + n log log n + 5n, with natural logarithms. In dimension 100 that is about 1,113. In dimension 1,000 it is about 13,840. His centres may form several shifted copies of one grid. Nobody knew whether some shapes truly need that much. Márton Naszódi recorded the question of a limit that grows only in step with n, some fixed number times n.

A stricter version demands that the centres form one lattice. A lattice is a regular grid of points, built by repeating n fixed steps in every combination. One grid gives far less freedom than several shifted grids. Rogers reached a lattice bound in 1959 that grew faster than any power of n. Ordentlich, Regev and Weiss cut it to order n² in 2022. In 2026, Heng Li and Xizhi Liu reached C n log n (log log n)^(10/3+o(1)). Here C is a fixed number. The extra factor grows very slowly. At n = 1,000, (log log n)^(10/3) is about 9. Li and Liu also built centrally symmetric bodies that need lattice density at least c n log n. Centrally symmetric means the shape looks the same when flipped through its centre.

The first paper removes that slow extra factorSource 1. It proves a lattice bound for every convex body in dimension 2 or more. The density can be held to at most C n log nSource 2. The number C is fixed and does not depend on the body or the dimension. No symmetry or smooth boundary is needed. The obstacle was rigidity. With several shifted grids, you can add copies where holes remain. With one lattice, a single choice of n steps fixes every centre at once. The paper builds that one lattice in stages. Each stage loses only a tiny shareSource 3. The losses add up to a bounded total, even as the stages multiply.

The second paper attacks the other side. For every large enough n, it builds a centrally symmetric body that resists every coveringSource 4. Any arrangement of sliding copies, on a lattice or not, needs density above c n log n. Here c is a fixed positive number. Li and Liu's lower bound only ruled out single lattices. The new difficulty is ruling out every arrangement at once, including ones chosen after seeing the bodySource 5. The body is random: a ball trimmed by many randomly tilted flat slabsSource 6. The paper squeezes all low-density arrangements into one finite list, fixed before the body is drawn. It then shows each listed arrangement leaves a hole, except with vanishing probability.

Put together, the worst-case density grows like n log n, up to fixed factorsSource 7. That holds for lattice coverings and for unrestricted ones. It also holds when only centrally symmetric bodies are allowed. Rogers' 1957 formula was the right size all along. No fixed multiple of n can work in every dimension. In dimension 1,000, a limit of n would mean density 1,000, while n log n is about 6,908.

Three limits matter. The papers give no numerical values for c and CSource 8. The result concerns the worst body, not every bodySource 9. For a round ball, the right order is still open, between order n and about half of n log nSource 10.

How sure is this? The Lean scope note lists a formal statement of the single-lattice bound. It also lists the n log n order for all four worst-case densities. These are sliding or lattice, over all bodies or symmetric ones. Lean is a computer proof checker. The paper's extra claim about polytopes with rational corners is not in that scope note. No specialist review has been published.

What it doesn't show. This does not give the best density for any particular shape, such as a ball, or numerical constants.