Every Convex Body Has a Lattice Covering of Density O(n log n)

A lattice constraint can make a covering less efficient: copies of a shape must sit at points generated by integer combinations of the same independent vectors. The OpenAI manuscript gives a bound on the cost of that constraint. For every compact convex body K with nonempty interior in dimension n ≥ 2, there is a single lattice Λ that covers all of space with density at most C n log n. The absolute constant C does not depend on the body or the dimension.

The body need not be symmetric or smooth. This is a universal upper bound on how bad the hardest bodies can be, not the density of every shape. A square, for example, can tile the plane with density one.

Covering density is the volume of the body divided by the volume of a lattice cell. In the square example, one copy fills each cell exactly, so the density is one. Squeeze the lattice while leaving the square unchanged and the copies overlap; the density rises. Overlap is allowed, but gaps are not. Density measures the average number of copies covering a point.

The word “single” is substantive. Several shifted lattices can combine into a periodic covering without forming one lattice. The manuscript’s claim is that one lattice suffices.

The proof divides the coordinates into many horizontal directions and a smaller number of vertical ones. At each vertical position, the body has a horizontal section. After an affine change of coordinates, an established Gaussian marginal theorem estimates the volumes of these sections in the range the argument needs. The body is not being approximated by a Gaussian: Gaussian values estimate how much horizontal material is available at different heights.

A second established result estimates the holes left by a random horizontal lattice. The proof uses it to select one horizontal lattice that works for a finite family of section bodies. Those sections nearly cover their horizontal spaces, but small uncovered regions remain. If the holes from different sections line up, they can still leave a hole in the full-dimensional covering.

The challenge is not merely to find sections with good average coverage. The vertical choices must be coordinated so their remaining holes do not align, while the resulting arrangement still belongs to one lattice.

The proof builds a branching family of vertical choices. At each coordinate, a correction offers at most two adjacent integer values. Each choice carries a Gaussian weight. Keeping only one successful branch could discard most of the useful weight, so the argument retains weighted branches through a hierarchy of smaller blocks. Their sizes decrease roughly from b to b to the power 0.9, then b to the power 0.81, and onward to a fixed cutoff.

The retained branches must satisfy two conditions. Their total weight stays above a positive absolute constant, providing enough horizontal covering material. At the same time, the weight of any individual branch becomes tiny, keeping each section within the range where the horizontal estimate applies. The losses across the blocks have a bounded sum, so the total weight survives as the hierarchy proceeds.

A local counting identity helps convert average success into a guarantee that no point is badly served. In a finite additive group, let N(x) count labeled subset sums that take x to a good point. Labels count separately even if two sums coincide. Adding a fresh shift w doubles the choices, making the new count N(x) + N(x − w).

Assign a penalty f(x) = exp(−θN(x)), where θ is positive. After the shift, the penalty at x is f(x)f(x − w). Averaging over x and a uniform shift w, every pair x and y appears exactly once, because its shift is determined by y = x − w. The double average therefore factors into two copies of the average penalty, Φ².

That identity is local, not the full theorem. Further probability estimates and iteration, omitted from the explanation, use it to produce a uniform lower bound. Its role is to show how another shift can expose poorly served points that an average might conceal.

A branching construction might seem to require unrelated translations at different heights. That would not meet the theorem’s one-lattice condition. The proof instead assembles the vertical blocks using one invertible triangular linear map, then applies a shear that shifts horizontal position linearly with the vertical coordinates. An invertible linear map sends a lattice to another lattice; it does not turn the branches into separate translated lattices.

There is also a useful separation property in the branching rule. Once the later coordinates are fixed, the next coordinate has at most two possible values, separated by one. Different choices of later coordinates may give different bases, but that unit separation makes the siblings’ relative random shear uniform across a horizontal lattice cell. A simultaneous shear argument then selects one shear that works for every pattern in the finite family. It is one global choice, not a separate repair at each height.

For sufficiently large dimensions, the estimates leave an uncovered fraction δ of at most n to the power −2n. The proof then removes the remaining holes using a small copy of the body.

View one lattice cell with opposite faces identified, and let A be the portion covered by the original lattice translates. The image of K scaled by 1/n in this cell has measure at least (1 − δ) divided by n to the n: multiplying that image by n maps it onto the covered set, and multiplication can increase measure by at most n to the n. Since δ is smaller than (1 − δ) divided by n to the n, this small copy has more measure than the uncovered set.

Consequently every translate of the reflection of the small copy must intersect A. Otherwise that translate would fit inside the uncovered region, which has less measure. Thus every point in the cell is a sum of a point in A and a point in the small copy. By convexity, K plus (1/n)K equals (1 + 1/n)K, so the enlarged body covers the cell.

To keep the original body unchanged, shrink the lattice instead. This raises density by a factor of (1 + 1/n) to the n, which is at most e. Undoing the affine change preserves density, and a separate elementary argument handles bounded dimensions.

The proof’s central coordination problem is to preserve enough total weight across many compatible corrections while keeping each contribution small. The final geometric step turns the near-cover those estimates provide into a complete covering by one lattice. The result is the claimed C n log n bound.