Translative Covering Density: How OpenAI Proved Some Convex Bodies Need n log n

A floor tiled with squares uses one square’s worth of material per square’s worth of space. In high dimensions, some convex shapes make that economy impossible even when you can place each copy wherever you like. OpenAI’s September 2026 preprint proves that, in every sufficiently large dimension, some centrally symmetric convex body has translative covering density greater than cnlogncn\log n for an absolute constant c>0c>0. Combined with Rogers’ upper bound, that puts the worst-case covering density of convex bodies at order nlognn\log n. The decisive step is to find a single body that defeats every low-density placement, including placements designed after its shape is known.

1. What Is Translative Covering Density, and How Is It Measured?

A convex body KK in ℝn\mathbb{R}^n is compact, contains the segment between any two of its points, and has nonempty interior. A translate K+xK+x moves every point of the body by the same vector xx, preserving its orientation and size. A set of centers XX covers space if every point belongs to at least one of those translates. The paper takes XX to be locally finite, so each bounded region contains finitely many centers.

Key Facts About the Covering Result
QuantityWhat It Means
SettingTranslated copies of one convex body cover all of Euclidean space.
DensityThe volume of the copies per unit volume, counting overlap.
Hard ExamplesSome centrally symmetric bodies exceed cnlogncn\log n in every sufficiently large dimension.
Worst-Case OrderRogers’ upper bound and the new examples give Θ(nlogn)\Theta(n\log n).

The paper measures an arrangement using the number of centers in the cube QR=[−R,R]nQ_R=[-R,R]^n. Multiply the count per unit volume by vol(K)\operatorname{vol}(K), take the upper limit as the cube grows, and then take the infimum over covering arrangements. The upper limit allows for arrangements whose center counts per unit volume never settle to a single value.

For a periodic covering, a full-rank lattice Λ\Lambda repeats a finite set TT of distinct offsets modulo the lattice. Each offset produces one copy of the lattice, called a coset. The periodic density is |T|vol(K)/detΛ|T|\operatorname{vol}(K)/\det\Lambda, where detΛ\det\Lambda is the volume of a fundamental cell. This density equals the average number of translates containing a point in that cell. A lattice covering uses just one coset. The planar triangular lattice illustrates that a lattice basis can use nonperpendicular vectors, so its fundamental cell can be skewed.

For a worked example, unit squares centered on ℤ2\mathbb{Z}^2 give a periodic tiling of the plane with density 1. Place the same squares on a square grid spaced half a unit apart in both directions. Each cell now has area 1/41/4, so the density is 4 and almost every point lies in four squares. Both arrangements cover the entire plane. The extra density records the repeated coverage.

2. Rogers’ Covering Bound and the Unresolved Linear Question

In 1957, C. A. Rogers showed that every convex body in dimension n≥3n\geq3 admits a periodic translative covering with density at most

nlog⁡n+nlog⁡log⁡n+5nn\log n+n\log\log n+5n

Here and throughout the paper, log\log is the natural logarithm. Gábor Fejes Tóth later improved the lower-order term and obtained coverings using only O(logn)O(\log n) cosets.

Equal Euclidean balls were known to force a density at least proportional to dimension. That lower bound left room for a single constant times dimension to cover every body. Márton Naszódi recorded that universal linear-bound question, which the new manuscript answers.

3. OpenAI’s Theorem: Some Symmetric Convex Bodies Require n log n

Theorem 1.1 says that there are absolute constants c>0c>0 and n0n_0 such that for every integer n≥n0n\geq n_0 there exists a centrally symmetric body Kn⊂ℝnK_n\subset\mathbb{R}^n satisfying

θT(Kn)>cnlog⁡n\theta_T(K_n)>cn\log n

Here θT\theta_T is the optimal translative covering density. Reflection through its center leaves a centrally symmetric body unchanged. The body can vary with dimension. For any proposed universal bound CnCn, taking nn sufficiently large makes clognc\log n exceed CC. There is then a symmetric counterexample in that dimension. Rogers’ bound and the theorem put the supremum of θT(K)\theta_T(K) between positive constant multiples of nlognn\log n, even when the supremum ranges only over centrally symmetric convex bodies.

4. Why Earlier Lattice Covering Proofs Could Not Settle the Problem

Heng Li and Xizhi Liu had already proved an order-nlognn\log n lower bound for lattice covering density. Their random-slab construction supplied much of the geometric and probabilistic machinery used here. The restriction to one lattice matters because an optimizer with several offsets can interleave separate copies of the same grid. A lower bound on each single-lattice covering gives no lower bound of the same size on the optimum over all these additional choices.

There is also a difference between randomizing centers and randomizing the body. In the packing-torus model studied by Bukh and coauthors, Poisson centers can fail with high probability at a specified density of order nlognn\log n. A specially placed set of centers might still cover that given body. OpenAI instead samples a body and needs one outcome that defeats every permitted low-density arrangement.

5. Constructing the Difficult Convex Body Using Random Slabs

	A 2D slice shows paired slab cuts shaping a symmetric body for the translative covering density proof.
A 2D slice shows paired slab cuts shaping a symmetric body for the translative covering density proof.

Start with the Euclidean unit ball BB. Set ε=2−30\varepsilon=2^{-30} and a=1+εa=1+\varepsilon, and take an outer ball of radius b=a(1+1/n)b=a(1+1/n). A unit vector uu specifies a slab |u⋅x|≤1|u\cdot x|\leq1 of half-width 1 around the origin. Let Π\Pi be a Poisson process on the unit sphere Sn−1S^{n-1} with intensity measure μ=Mσ\mu=M\sigma, where σ\sigma is uniform probability measure on the sphere. Equivalently, draw a Poisson number of normals with mean MM, then choose each independently and uniformly. The body is

K=bB∩⋂u∈Π{x:|u⋅x|≤1}K=bB\cap\bigcap_{u\in\Pi}\{x:\lvert u\cdot x\rvert\leq1\}

Every slab and the outer ball are symmetric about the origin, and their intersection contains BB. The parameter MM is the reciprocal of the surface probability that a normal cuts a point at distance aa. At distance at most aa, the expected number of cutting normals is at most 1, so the probability a point survives is at least e−1e^{-1}.

Integrating this survival probability over aBaB gives expected volume at least e−1ωnane^{-1}\omega_n a^n, where ωn=vol(B)\omega_n=\operatorname{vol}(B). The outer ball caps the volume at less than 3ωnan3\omega_n a^n. Lemma 2.1 combines these bounds to give a dimension-independent positive probability of volume strictly greater than 2vωnan2v\omega_n a^n, with v=1/64v=1/64. That margin later converts a bound on centers per unit volume into a bound on covering density.

6. Reducing Infinitely Many Covering Arrangements to Finite Patterns

Proposition 3.1 starts from a hypothetical periodic covering at or below a fixed center-intensity threshold. Averaging modulo its lattice gives the expected number of indexed centers in a shifted window as intensity times window volume. The calculation works for short periods, skew fundamental cells, and any finite number of cosets. Every occurrence contributes to the average, including repeated center positions in an indexed list.

The proof picks a translate of a small ball BDB_D, of fixed radius D=2−10D=2^{-10}, with two properties. Its neighborhood has few enough centers to retain in a bounded list, and a substantial fraction of points in the window are suitable targets. Those targets have no center extremely close by, only a controlled number of centers within covering distance, and bounded total radial cost. The last condition sums the weights wa(r)=1+nmax(1−r2/a2,0)w_a(r)=1+n\max(1-r^2/a^2,0) over nearby centers, with rr the distance to the target. The weight rises as a center moves inward from distance aa. Average estimates and Markov’s inequality give a window where these requirements coexist.

Each retained center is rounded to a fixed grid. Two indices that round to the same point are kept, so the count and cost estimates still apply to the full list. The displacement is absorbed by a slightly enlarged body K+K^+, obtained by adding 3η3\eta to both the ball radius and the slab half-width, with η=n−4\eta=n^{-4}. Coverage of the original window by KK therefore implies coverage of BDB_D by the rounded translates of K+K^+.

This produces a finite family ℱn\mathcal{F}_n of possible lists before the normals are drawn. The logarithm of the number of lists is at most exp(λ0n+O(logn))\exp(\lambda_0 n+O(\log n)), where λ0=log(1+D/a)\lambda_0=\log(1+D/a). Any covering at the specified intensity must leave a pattern in this family.

7. Spherical Caps: How a Slab Creates an Uncovered Point

At a target yy, only a center pp within the outer radius of K+K^+ can contribute coverage. Its residual vector is x=y−px=y-p. The normals that cut this residual form an antipodal pair of spherical caps:

C(x)={u∈Sn−1:|u⋅x|>1+3η}C(x)=\{u\in S^{n-1}:\lvert u\cdot x\rvert>1+3\eta\}

Indeed, if uu belongs to C(x)C(x), the residual violates the slab constraint, so yy falls outside p+K+p+K^+. For a residual of length rr, a half-cap consists of directions within angle arccos((1+3η)/r)\arccos((1+3\eta)/r) of its signed axis when r>1+3ηr>1+3\eta. Longer residuals give wider caps at the same threshold. This explains the radial budget: shorter residuals generally require rarer normals and cost more in the estimate.

Two cap pairs can share candidate normals. The natural angular distance is the smaller angle between their axes after identifying opposite directions. The paper bounds normalized cap overlap by a quantity that falls exponentially with a distance combining angular separation and the difference in logarithmic cap intensities. It also lower-bounds the common intersection for suitably clustered caps. Together these estimates say when several cuts can share a normal and when sharing is unlikely.

8. Grouping Cap Conditions and Building Poisson Witnesses

	Two sampled normals cut three translates at one point in the translative covering density proof.
Two sampled normals cut three translates at one point in the translative covering density proof.

Requiring an independent cut for each residual would misrepresent nearly coincident caps. The proof groups the residual indices into blocks and chooses one measurable subset of the common cap intersection for each block. A normal in that subset cuts every translate in its block. For example, if three center indices coincide after rounding, their three cap conditions are identical. A single normal in that common cap cuts all three occurrences.

A witness assigns a distinct sampled Poisson point to each block’s subset. This is a sufficient certificate of a hole: all nearby translates are cut, and farther translates were already ruled out by the outer radius. For labeled blocks the expected number of such assignments, called the activity, is the product of their subset intensities. The Poisson factorial-moment formula gives that product even when subsets overlap.

The partition must keep the activity large enough and control how assignments can overlap. Proposition 5.1 merges blocks under a logarithmic cost budget. Once merging stops, its estimates bound both the total loss in subset intensities and the overlap between different subsets. Those bounds matter even at one target, where different witnesses can reuse some of the same Poisson points.

9. Janson’s Inequality and the Probability of Unavoidable Holes

For one fixed pattern, the proof selects ⌊exp(nlogn/16)⌋\lfloor\exp(n\log n/16)\rfloor suitable targets before sampling the normals. It uses two angular scales for residuals at different targets, with HH a fixed positive constant.

The Two Angular Scales in Lemma 7.2
ScaleRole in the Proof
Fine Hlogn/nH\sqrt{\log n/n}Every pair of distinct targets meets this separation across all relevant residuals.
Coarse 4ε4\sqrt{\varepsilon}Most pairs meet this stronger separation, making their cutting caps disjoint across targets.

The selection is possible because near-parallel residuals confine the second target to a thin cylinder around an axis through its center. The cylinder’s cross-sectional volume falls rapidly in high dimension. A counting argument over the center labels and target pairs gives separation at the fine scale everywhere, and at the coarse scale for all but an exponentially small fraction of pairs.

To use Janson’s inequality, the proof compares witnesses with similar expected counts, keeping a bin in which the activities differ by at most a factor of two. An overlap diagram is a partial matching of blocks whose slots reuse the same Poisson point in two assignments. Its weight involves the measures of the shared subsets’ intersections. The sum includes same-target and cross-target diagrams.

Proposition 6.2 bounds the probability that every chosen target has zero witnesses. Write ZyZ_y for the witness count at target yy, νy\nu_y for its activity, and DyzD_{yz} for the sum of nonempty matching weights for targets y,zy,z. In the chosen bin the bound is

Pr⁡(∀y, Zy=0)≤exp⁡[−(∑yνy)22∑y,zDyz]\Pr(\forall y,\ Z_y=0)\leq\exp\left[-\frac{(\sum_y\nu_y)^2}{2\sum_{y,z}D_{yz}}\right]

The many targets keep the total activity large relative to the same-target overlap terms. Fine separation limits the dependence between the remaining pairs, and coarse separation makes most cross-target diagram sums vanish. Since full coverage forces zero hole witnesses at every target, Proposition 7.3 gives a doubly exponential upper bound on one pattern’s chance of covering the window.

10. Completing the Proof: Why Every Low-Density Covering Fails

	The translative covering density proof rounds centers, bounds each pattern, and transfers the result to all coverings.
The translative covering density proof rounds centers, bounds each pattern, and transfers the result to all coverings.

The union bound adds these success probabilities over ℱn\mathcal{F}_n. The fixed-pattern probability is at most exp[−exp(γn−O(logn))]\exp[-\exp(\gamma n-O(\log n))], with γ>λ0\gamma>\lambda_0. Its decay beats the growth in the number of patterns. Thus the probability that any retained list covers the window tends to zero. The volume event still has positive probability, so some realization has enough volume and defeats every retained pattern.

If a periodic covering of that realization had intensity at most ρ0=cnlogn/(2vωnan)\rho_0=cn\log n/(2v\omega_n a^n), localization would produce a successful retained list. Hence the infimum of periodic densities is at least ρ0vol(K)\rho_0\operatorname{vol}(K), which strictly exceeds cnlogncn\log n by the volume margin. Appendix A gives the final transfer:

θT(K)=θper(K)\theta_T(K)=\theta_{\mathrm{per}}(K)

To see the principle, take a large cube and retain every center that could cover any point in it, including centers within a fixed-width border outside the cube. Repeat that finite list with the cube’s periods. In fixed dimension the relative border overhead vanishes as the cube grows, yielding equality of the two infima.

11. What the n log n Result Establishes and What Remains Open

The paper gives the same lower bound, with the same constant, for some centrally symmetric polytopes with rational vertices. Approximate the successful body from inside by such polytopes and retain enough volume to preserve the strict margin. Any covering by a smaller polytope still covers by the containing body at the same center intensity, so the same threshold applies.

A companion manuscript supplies an order-nlognn\log n upper bound using a single lattice. OpenAI’s release announcement describes the wider collection. The family’s Lean scope note and proof code cover the order of the four suprema, for lattice and translative coverings over all convex bodies and over symmetric ones. The preprint separately supplies the written random-slab argument and rational-polytope corollary.

The construction proves existence in large dimensions. The constants are unoptimized, and the proof gives no efficiency guarantee for finding a successful body. For Euclidean balls, the manuscript records a linear lower bound in order and Dumer’s upper bound of (1/2+o(1))nlogn(1/2+o(1))n\log n. The exact order for that fixed shape remains open. What is settled is the worst-case translative covering density when the shape can vary. For another proof in convex geometry, read Binary Verse AI’s coverage of the logarithmic Brunn–Minkowski conjecture.

What is translative covering density?

Translative covering density is the lowest achievable density, taken as an infimum, when copies of one convex body cover Euclidean space by translations alone. Density counts the volume of the copies per unit volume of space, with overlaps counted repeatedly. It can exceed 1.

Why is n log n the optimal order for convex-body covering density?

Rogers gave a universal upper bound of order n log n. In every sufficiently large dimension, the new theorem gives a centrally symmetric convex body whose translative covering density exceeds c n log n for an absolute constant c > 0. Together these bounds give worst-case order Θ(n log n).

Why did earlier lattice covering results not solve the problem?

The earlier lower bound restricts the centers to one full-rank lattice. Allowing a periodic pattern with several lattice cosets enlarges the set of candidate arrangements. The new proof rules out every periodic pattern below its threshold and uses periodization to transfer the lower bound to unrestricted coverings.

How do random slabs and Poisson witnesses prove that coverings must have holes?

Random slabs cut a convex body out of an outer ball. At each candidate point, spherical caps identify slab normals that cut individual translates. A witness assigns distinct sampled normals to blocks of cap conditions so that every relevant translate is cut at that point. A Poisson version of Janson’s inequality bounds the probability that a pattern covers every target.

Does the n log n lower bound apply to every convex body?

The theorem guarantees difficult examples in each sufficiently large dimension. Other bodies can be much easier to cover. For example, a cube can tile Euclidean space by translations with density 1.

Does the proof settle covering density for spheres and polytopes?

It gives the same lower-bound order for some centrally symmetric polytopes with rational vertices. For Euclidean balls, the paper records a linear lower bound and an upper bound of order n log n. The exact asymptotic order for balls remains open.

How is covering density different from packing density?

Packing requires the interiors of copies to be disjoint and measures how much space they occupy. Covering requires every point to lie in at least one copy and measures the volume contributed by all copies, including overlaps.

Leave a Comment