Lattice and translative coverings at the n log n scale

Source and verification

This article explains family 092 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Translative and lattice covering densities

A translative covering of ${\mathbb{R}}^n$ by a convex body $K$ is a family of translates $x+K$ whose union is the whole space. Density measures their asymptotic total volume per unit volume, counting overlaps.

For a covering lattice $\Lambda$, the density is $|K|/\det \Lambda$, where $\det \Lambda$ is a fundamental-cell volume. Its infimum is ${\theta }_L(K)$. Allowing arbitrary locally finite center sets and upper asymptotic densities gives ${\theta }_T(K)$. Necessarily

$$1\le {\theta }_T(K)\le {\theta }_L(K).$$

The first inequality follows by integrating covering multiplicity over large regions; boundary errors disappear in the limit. The second holds because lattices are among the admissible center sets.

Periodization permits finite unions of lattice cosets when taking the translative infimum. Such a union need not be one lattice, a distinction central to the upper-bound manuscript.

🏷️ Matching worst-case orders

Statements in the family

There is an absolute $C$ such that every convex body in dimension $n\ge 2$ satisfies

$${\theta }_L(K)\le Cn\log n.$$

The construction uses one covering lattice. (OpenAI, 2026)

There is an absolute $c>0$ such that, in all sufficiently large dimensions, some centrally symmetric body $K_n$ satisfies

$${\theta }_T(K_n)>cn\log n.$$

Rational polytopes can be used as witnesses. (OpenAI, 2026b)

Together with ${\theta }_T\le {\theta }_L$, these claims give

$$\begin{array}{rl}\underset{K}{\sup }{\theta }_T(K)& \asymp n\log n,\\ \underset{K}{\sup }{\theta }_L(K)& \asymp n\log n.\end{array}$$

These are worst-case statements. A cube tiles space with density one. The lower bound also does not identify the optimal covering density of Euclidean balls.

🏷️ Repairing holes within a single lattice

Suppose an arrangement leaves sparse holes. Adding translates at the holes may cost little density but usually produces many cosets or an irregular point set. A theorem about ${\theta }_L$ must instead repair holes through parameters of one additive lattice.

The first manuscript splits horizontal and vertical directions and analyzes section volumes through a Gaussian marginal. It chooses a common horizontal lattice with small average uncovered mass for a finite collection of relevant sections. The remaining task is to synchronize the vertical layers without accumulating their errors. (OpenAI, 2026a)

A weighted hierarchy of blocks handles this synchronization. Scales descend through powers, schematically $b,b^{0.9},\dots$, to a fixed cutoff. Relative mass losses are bounded by negative powers such as $b^{-1/100}$ and made summable. The construction also controls the largest atom. Small exceptional mass and small maximum atom are distinct requirements; an average estimate does not imply both.

A shared shear coordinates the layers. As a linear transformation of a lattice, it preserves the one-lattice structure. A final dilation by $1+1/n$ removes the residual geometric error. Its cost is bounded because

$$(1+1/n{)}^n\le e.$$

A fixed dilation larger than one would have exponential volume cost, which would destroy the desired order. The dimensional scale of this last correction is therefore part of the argument.

🏷️ A random body resisting every arrangement

The lower-bound paper constructs a body from random slabs, using a Poisson model for directions. It must defeat every sufficiently sparse center arrangement, including one chosen after the body is known. Showing that random centers usually fail would not establish a lower bound for ${\theta }_T$. (OpenAI, 2026b)

The source rounds local lists of candidate centers. These lists retain multiplicities and accommodate skew lattices and arbitrarily many cosets. This prevents an unnoticed restriction to coverings of bounded combinatorial complexity.

For each rounded candidate, it constructs many potential holes. A hole certificate depends on a controlled block of random caps or slab data. The certificates are dependent, so an independent-product probability calculation is unavailable. A Janson-type lower-tail estimate bounds the probability that all these potential holes are blocked.

There are exponentially many targets, on a scale $\exp (c_{1}n\log n)$. The resulting failure probability is small enough to take a union bound over all rounded center patterns. After this union bound, one body simultaneously defeats every admissible low-density pattern. The quantifier order is the reason the random construction proves an extremal statement.

Approximation then transfers the obstruction to rational polytopes while preserving a strict density gap. The source’s discretization and dependent-event estimates are the substantial inputs; the comparison between the two covering densities supplies the stated matching orders.

🏷️ Affine invariance and examples

For an invertible $T$, the covering $\Lambda +K$ becomes $T\Lambda +TK$. Both $|K|$ and $\det \Lambda$ acquire $|\det T|$, so ${\theta }_L(TK)={\theta }_L(K)$. The translative density has the same invariance. Thus a long thin parallelepiped still has density one: anisotropy alone does not force inefficient covering.

The lower examples must instead encode many mutually incompatible local covering requirements. That is the role of the random slab construction. The upper construction must handle these requirements without assuming symmetry, smoothness, or a preferred ellipsoidal shape.

🏷️ Key steps and proof outlines

Horizontal averaging must work for every retained section

The upper-bound manuscript first puts the body in an affine position where a Gaussian approximation controls a suitable marginal. It extracts a finite list of relevant horizontal sections and chooses one horizontal lattice that has small uncovered average for all their labels. Simultaneity is essential: choosing a different good lattice for each section would not assemble into a single lattice in the full space.

The folded Gaussian block construction turns truncated Gaussian coordinates into weighted points in a fundamental interval. The fold preserves the relevant mass while making it compatible with periodic lattice coordinates. It also provides pointwise control of the largest weight. A distribution can have small total exceptional mass and still contain one large atom; the hierarchy needs both properties to prevent one branch from dominating a later averaging step. (OpenAI, 2026a)

A Boolean sampler supplies uniform averaging over translations

The sampler averages a function over sums of selected shifts,

$$A(x)=2^{-k}\sum _{ϵ\in \{0,1{\}}^k}g\left(x-\sum _i{ϵ}_i{w}_i\right).$$

When the shifts and the base point are sampled in the appropriate finite group, distinct bit patterns yield pairwise independent arguments. Expanding $\mathbb{E}|A-\mathbb{E}g{|}^2$ therefore cancels cross terms and gives a variance improvement. Additional shifts upgrade this average control to the finite family of patterns required by the hierarchy.

The construction uses the sampler at successively smaller block sizes. Each stage loses only a negative power of the current size, and the block sizes descend rapidly enough that the losses remain summable until a fixed cutoff. The induction allows empty intermediate patterns, so no nonexistent branch is normalized by a positive mass.

One shear repairs all layers without adding arbitrary centers

A shear maps a lattice to a lattice. The final argument selects its columns successively. At each coordinate, patterns occupying one layer retain their bound under a common translation; patterns occupying two neighboring layers are averaged over the new shear parameter. This inductive averaging produces one choice satisfying all finitely many pattern estimates simultaneously.

The residual holes are removed by dilation at relative scale $1/n$. Volume is multiplied by at most $(1+1/n{)}^n\le e$. A dilation by a dimension-independent amount would instead have exponential cost. Thus exact coverage and the $n\log n$ density bound depend on a quantitatively tiny final repair, not merely on knowing that the uncovered volume is small.

The lower-bound body must defeat adaptive center choices

The random body is an intersection of slabs with Poisson-distributed normals, together with deterministic geometric bounds. Its volume is controlled by integrating the probability that each point survives all slab tests. For a point in a suitable inner ball, the expected number of excluding normals is bounded, so the survival probability is bounded below by a fixed constant.

A covering chosen after the body is known can depend on every slab. To handle this quantifier order, the source first replaces all possible low-density periodic coverings by a deterministic finite family of rounded local patterns. Centers retain their multiplicities. Averaging locates a region with a controlled number of centers, and rounding changes the body to a slightly enlarged comparison body. The enlargement makes the implication robust: a genuine covering would produce one rounded pattern covering the designated test region. (OpenAI, 2026b)

Dependent hole witnesses beat the number of patterns

For each rounded pattern, choose many potential holes. A witness at a hole specifies cap conditions on the Poisson normals that exclude all relevant nearby centers. Different holes can share cap data, so their events are dependent. The cap-intersection estimates and grouping procedure quantify this overlap and assign logarithmic costs to blocks of related conditions.

The Poisson lower-tail lemma bounds the probability that no hole witness succeeds. Its proof passes through finite Bernoulli approximations and correlation inequalities before returning to the Poisson process. The resulting failure probability is strong enough to union-bound over every rounded pattern. Intersecting with the positive-volume event then produces a single body that defeats all low-density arrangements.

Finally, periodization transfers the obstruction from periodic coverings to arbitrary locally finite coverings: a large finite patch covering a cube is repeated, with a boundary margin accounting for the body’s diameter. Approximation from inside by symmetric rational polytopes preserves a strict density gap. These last steps explain why the conclusion concerns the full translative infimum and admits rational witnesses, rather than only one finite random experiment.

See Also

Triangular lattice energies and packing studies optimality for pair interactions. Finite cylinder coverings distinguishes continuous arrangements from actual finite covers.

🏷️ Manuscripts and verification scope

• A single-lattice covering bound of order n log n — pinned manuscript and companion source.
• Translative covering densities of order n log n — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The scope describes both headline density bounds and their worst-case order consequences. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. A single-lattice covering bound of order n log n.

🐻  OpenAI 2026b. Translative covering densities of order n log n.