# The optimal order of convex-body covering density

> The worst convex shape needs covering density about n log n in dimension n, lattice or not. Plain-English explainer, Lean status and sources.

Canonical: https://closedform.nishachay.tech/e/openai-math-2026-092/
Last updated: 2026-10-11

**The worst convex shape needs covering density about n log n in dimension n, lattice or not.**

**Trust:** Formal proof listed · **Papers:** 2 · **First paper:** September 23, 2026 · **Field:** Convex and metric geometry · **Entry:** 092

*Explained by AI.* Drafted by one AI model and checked sentence by sentence against the paper by a different one. Spot a mistake? Report an error.

Covering space with sliding copies of a solid shape always wastes some overlap. Covering density measures that overlap as the average number of copies over a point. These papers prove that the worst shape in dimension n needs density of size n log n, and never more. This holds whether the copies sit on one regular grid or anywhere at all.

## At a glance

- **First step:** 1957 (C. A. Rogers, upper bound n log n + n log log n + 5n)
- **Significance:** Major. It settles the growth rate of worst-case covering density, matching Rogers' 1957 upper bound and answering a recorded question.
- **Trust:** Formal proof listed
- **Field:** Convex and metric geometry (2 papers)

## 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 factor[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 n[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 share[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 covering[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 body[5]. The body is random: a ball trimmed by many randomly tilted flat slabs[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 factors[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 C[8]. The result concerns the worst body, not every body[9]. For a round ball, the right order is still open, between order n and about half of n log n[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.

## Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

## Hype check

Major if the proofs hold. The Lean scope note lists both main statements. The constants are unnamed, and the ball case stays open. No specialist review has been published.

## Words used

- **Convex body:** A solid, bounded shape with no dents or holes, such as a ball or a cube.
- **Covering density:** The average number of copies of a shape lying over a typical point when the copies cover all of space.
- **Lattice:** A regular grid of points made by repeating n fixed steps in every combination.
- **Translative covering:** A covering of space by copies of one shape that are slid into place, never turned.
- **Centrally symmetric:** A shape that looks the same after flipping every point through its centre.
- **Order n log n:** Growing like n times the logarithm of n, up to fixed factors that do not depend on n.

## The original papers (2)

- [A single-lattice covering bound of order n log n](https://github.com/openai/math/blob/main/preprints/A-single-lattice-covering-bound-of-order-n-log-n-September-23-2026/paper.pdf) - September 23, 2026 · Formal proof listed
- [Translative covering densities of order n log n](https://github.com/openai/math/blob/main/preprints/Translative-covering-densities-of-order-n-log-n-September-23-2026/paper.pdf) - September 23, 2026

- [Lean notes](https://github.com/openai/math/blob/main/lean/docs/092.md)

## Quoted lines from the paper (10)

[1] From [A single-lattice covering bound of order n log n](https://github.com/openai/math/blob/main/preprints/A-single-lattice-covering-bound-of-order-n-log-n-September-23-2026/paper.pdf):

> Theorem … removes this remaining iterated-logarithmic loss and gives the constant-factor $n\log n$ bound.

[2] From [A single-lattice covering bound of order n log n](https://github.com/openai/math/blob/main/preprints/A-single-lattice-covering-bound-of-order-n-log-n-September-23-2026/paper.pdf):

> No symmetry or boundary regularity is assumed.

[3] From [A single-lattice covering bound of order n log n](https://github.com/openai/math/blob/main/preprints/A-single-lattice-covering-bound-of-order-n-log-n-September-23-2026/paper.pdf):

> The resulting losses are summable even when the number of blocks grows.

[4] From [Translative covering densities of order n log n](https://github.com/openai/math/blob/main/preprints/Translative-covering-densities-of-order-n-log-n-September-23-2026/paper.pdf):

> There are absolute constants $c>0$ and $n_0$ such that, for every integer $n\ge n_0$, some centrally symmetric convex body $K_n\subset\mathbb R^n$ satisfies \[ \theta_T(K_n)>c n\log n. \]

[5] From [Translative covering densities of order n log n](https://github.com/openai/math/blob/main/preprints/Translative-covering-densities-of-order-n-log-n-September-23-2026/paper.pdf):

> The resulting finite class is fixed before the body is sampled, so it includes arrangements chosen after the body is known.

[6] From [Translative covering densities of order n log n](https://github.com/openai/math/blob/main/preprints/Translative-covering-densities-of-order-n-log-n-September-23-2026/paper.pdf):

> Intersect a slightly enlarged Euclidean ball with symmetric slabs whose unit normals are sampled by a Poisson process.

[7] From [Translative covering densities of order n log n](https://github.com/openai/math/blob/main/preprints/Translative-covering-densities-of-order-n-log-n-September-23-2026/paper.pdf):

> As $n\to\infty$, each of the four quantities \begin{gather*} \sup_{K\in\mathcal K^n}\theta_T(K),\qquad \sup_{K\in\mathcal K^n_{\mathrm{sym}}}\theta_T(K),\\ \sup_{K\in\mathcal K^n}\theta_L(K),\qquad \sup_{K\in\mathcal K^n_{\mathrm{sym}}}\theta_L(K) \end{gather*} has order $n\log n$, with absolute comparison constants.

[8] From [Translative covering densities of order n log n](https://github.com/openai/math/blob/main/preprints/Translative-covering-densities-of-order-n-log-n-September-23-2026/paper.pdf):

> The constant in Theorem … is not optimized.

[9] From [A single-lattice covering bound of order n log n](https://github.com/openai/math/blob/main/preprints/A-single-lattice-covering-bound-of-order-n-log-n-September-23-2026/paper.pdf):

> This statement concerns the supremum over bodies, rather than the covering density of every individual body.

[10] From [Translative covering densities of order n log n](https://github.com/openai/math/blob/main/preprints/Translative-covering-densities-of-order-n-log-n-September-23-2026/paper.pdf):

> The gap for Euclidean balls remains; our theorem determines the optimal order when the convex body may also be chosen.

## Other sources

- [C. A. Rogers, “A note on coverings”, Mathematika 4 (1957), 1–6](https://doi.org/10.1112/S0025579300001030)
- [C. A. Rogers, “Lattice coverings of space”, Mathematika 6 (1959), 33–39](https://doi.org/10.1112/S002557930000190X)
- [O. Ordentlich, O. Regev and B. Weiss, “New bounds on the density of lattice coverings”, Journal of the AMS 35 (2022), 295–308](https://doi.org/10.1090/jams/984)
- [H. Li and X. Liu, “Nearly sharp bounds for lattice coverings by convex bodies”, arXiv:2607.28429v2 (2026)](https://arxiv.org/abs/2607.28429v2)
- [M. Naszódi, “Flavors of Translative Coverings”, New Trends in Intuitive Geometry, Bolyai Society Mathematical Studies 27 (2018), 335–358](https://doi.org/10.1007/978-3-662-57413-3_14)
- [openai/math, “A single-lattice covering bound of order n log n” (2026)](https://github.com/openai/math/blob/main/preprints/A-single-lattice-covering-bound-of-order-n-log-n-September-23-2026/paper.pdf): “There is an absolute constant $C>0$ such that, for every integer”
- [openai/math, “Translative covering densities of order n log n” (2026)](https://github.com/openai/math/blob/main/preprints/Translative-covering-densities-of-order-n-log-n-September-23-2026/paper.pdf): “This answers negatively the universal linear-bound question recorded by”

## Related

- [Triangular-lattice optimality, long-range Riesz and Coulomb energies, and spherical logarithmic energy](https://closedform.nishachay.tech/e/openai-math-2026-090/) - Convex and metric geometry
- [Hyperbolicity cones without semidefinite lifts](https://closedform.nishachay.tech/e/openai-math-2026-095/) - Convex and metric geometry
- [Cylinder coverings below the half-area bound](https://closedform.nishachay.tech/e/openai-math-2026-100/) - Convex and metric geometry
- [Logarithmic and L p Brunn–Minkowski inequalities and the B-conjecture](https://closedform.nishachay.tech/e/openai-math-2026-091/) - Convex and metric geometry
- [Dimension-free logarithmic Sobolev inequality for subgaussian log-concave measures](https://closedform.nishachay.tech/e/openai-math-2026-093/) - Convex and metric geometry
- [Convex and metric geometry](https://closedform.nishachay.tech/science/mathematics/convex-and-metric-geometry/) - Field · 15 results
- [Open since the 1950s](https://closedform.nishachay.tech/open-since/1950s/) - Era · 23 results
- [Lean-checked results](https://closedform.nishachay.tech/trust/lean-checked/) - Trust · 242 results
- [Report an error](https://github.com/nishachay/closed-form/issues/new?template=report-error.yml&labels=entry-error&title=%5Bentry%20092%5D%20)