Some Convex Bodies Require Translative Covering Density Of Order n log n

Covering density counts material used, not just how much of the floor is covered. Copies of a shape may overlap, and those overlaps count toward the total. A square tiling of the plane has density one; overlaying a shifted copy of the same tiling still covers every point, but raises the density to two.

The September 2026 OpenAI manuscript claims that in every sufficiently large dimension n, there is a centrally symmetric convex body whose optimal translative covering density exceeds c n log n, for some absolute constant c > 0. “Translative” means copies can be shifted but not rotated or resized. The result is about the existence of difficult bodies—not about every body or every dimension.

The manuscript pairs this lower bound with Rogers’s upper bound, of order n log n for all convex bodies. Together, they identify the worst-case order of translative covering density. They rule out a universal bound proportional only to n, but do not settle the separate question of the density required to cover with Euclidean balls.

A single lattice covering is only one way to arrange copies. The manuscript allows periodic arrangements made from any finite number of shifted lattice copies, with no fixed limit on that number. Its challenge is therefore to rule out all such finite patterns, not just a particular lattice.

The authors use periodization to relate periodic coverings to unrestricted ones. Starting with a large covered cube, they retain centers in a surrounding buffer and repeat the resulting finite pattern. As the cube grows, the relative cost of its boundary tends to zero. This gives equality between the infimum density for periodic arrangements and the unrestricted infimum.

That equality is about infima; it does not mean every covering is periodic, or that the upper and lower densities of an individual arrangement coincide. It lets the proof target periodic coverings while preserving the claimed optimal density.

The proposed body begins with a slightly enlarged ball and intersects it with symmetric slabs. Each slab is bounded by parallel planes one unit from the origin; its normal direction is drawn from a Poisson process. Since every slab contains the unit ball, the intersection remains centrally symmetric and convex. The two-dimensional illustration is only a schematic, not a high-dimensional example or a realization of the Poisson construction.

The first proof step shows that the random intersection is not usually too small. Set a = 1 + ε, with ε a fixed tiny positive constant, and choose the Poisson intensity so that a point at distance a has expected one cutting normal. For any point inside the radius-a ball, the expected number of cuts is at most one. Its probability of surviving all cuts is therefore at least e⁻¹.

Integrating these pointwise survival probabilities gives expected body volume at least e⁻¹|aB|, where |aB| is the volume of the radius-a ball. This integration does not require different points’ survival events to be independent.

The manuscript then turns the expected-volume bound into a positive probability of obtaining a substantial-volume body. Let X = |K|/|aB|. The body lies within radius b = a(1 + 1/n), so X < 3. If p is the probability that X > 1/32, then e⁻¹ ≤ E[X] ≤ (1 − p)/32 + 3p. Rearranging gives p ≥ 0.1133…. Thus a body with volume greater than |aB|/32 occurs with probability bounded away from zero as dimension grows.

Volume alone does not establish high covering density. The proof must show that the same body resists every sufficiently low-intensity covering, including arrangements selected after the body is known.

The manuscript’s localization argument reduces a low-intensity periodic covering to a finite list of relevant centers in a bounded window. It rounds those centers to a fine grid and slightly enlarges the body so coverage survives rounding. Crucially, the family of candidate lists is fixed before the random body is sampled. The argument is intended to cover even very short or skew lattice periods. The localization proof is a technical step in the manuscript.

For a fixed list and target point, each center gives a residual vector from that center to the target. A Poisson normal cuts the residual when its dot product with it exceeds the slab half-width in absolute value. If every relevant copy is cut away from the target, that point is uncovered. But the cutting events are dependent: similar residuals may have nearly identical sets of cutting normals.

The manuscript addresses this dependence by grouping conditions into blocks and counting assignments of distinct Poisson normals to shared cutting subsets. It chooses many targets with separated residual directions at a fine scale, while arranging that most target pairs have disjoint cutting sets at a coarser scale. The block estimates handle dependence among conditions for one target; a Poisson version of Janson’s inequality controls the chance that a candidate list covers the whole window. The manuscript bounds this chance by a doubly exponentially small quantity. That decay is needed because the number of candidate lists is enormous; the proof shows it beats their growth. A second-moment estimate alone would not suffice.

The volume event has probability at least about 11 percent, while the probability that any retained low-intensity candidate covers the window tends to zero. The manuscript concludes that, for sufficiently large dimension, there is a body with both substantial volume and no such efficient covering.

If ρ₀ is the excluded center intensity, the density lower bound is ρ₀|K|. Taking ρ₀ = R/(|aB|/32) and using |K| > |aB|/32 gives density greater than R, with R chosen as a small absolute constant times n log n. Periodization carries the conclusion from the periodic setting to unrestricted coverings.

The local volume argument establishes a positive probability of sufficient volume. The global conclusion depends on the manuscript’s localization, block, and dependence estimates, which are outlined here rather than reproduced in full. Taken together, those steps yield the claimed existence result: one sufficiently large-volume body that defeats every low-density arrangement.