The optimal order of overlap needed to cover high-dimensional space

← All digests

Family 092 · Convex and metric geometry
Importance 5/5 · Provisional editorial rating
Sources consulted 2026-10-14

1. The question

Cover the plane with translated copies of a fixed shape. A square can tile with no wasted overlap. Disks must overlap if no gaps are to remain. In higher dimensions, how much overlap can an arbitrary convex body force?

There are two versions of this question. In a lattice covering, the centers form one regular lattice. In a translative covering, they may be arranged freely, with no periodicity requirement. Allowing more freedom can only make covering easier.

The two manuscripts in this family claim matching answers at the level of worst-case dimensional order. M1 gives every convex body a single-lattice covering of density at most a constant times $n\log n$. M2 constructs bodies for which even unrestricted translates require at least that order of density. Together, the claims locate the hardest covering problems to within absolute constant factors.

2. Background and essential definitions

A convex body $K\subset\mathbb R^n$ is compact, convex and full-dimensional. A set of centers $X$ covers space by translates of $K$ if

$$K+X=\bigcup_{x\in X}(K+x)=\mathbb R^n.$$

Centers are locally finite: every bounded region contains only finitely many. Rotations of individual copies are not allowed; all copies are translations of the same body.

For a full-rank lattice $\Lambda$, its determinant is the volume of a fundamental cell. The lattice covering density is

$$\theta_L(K)=\inf_{K+\Lambda=\mathbb R^n} \frac{|K|}{\det\Lambda}.$$

The ratio is the average number of copies covering a point. It is not the fraction of space covered, which is already one. Density one corresponds to a covering with no overlap except on negligible boundaries.

For arbitrary centers, put $Q_R=[-R,R]^n$ and define

$$\theta_T(K)=\inf_{K+X=\mathbb R^n} |K|\limsup_{R\to\infty}\frac{\#(X\cap Q_R)}{(2R)^n}.$$

A periodic covering can use finitely many cosets of one lattice, $X=\Lambda+T$. Its density is $|T||K|/\det\Lambda$, where representatives in $T$ are distinct modulo the lattice. Taking the infimum over all such finite unions gives the same optimum as unrestricted translative covering, by periodization. This equality of infima does not mean that every individual covering is periodic or has a density limit.

Necessarily $\theta_T(K)\leq\theta_L(K)$. An upper bound for the more restrictive lattice problem is especially strong; a lower bound for the less restrictive translative problem is especially strong.

3. Development history and previous partial results

Rogers’s 1957 covering theorem gave every convex body a translative covering of density at most

$$n\log n+n\log\log n+5n$$

in dimensions at least three. Such a covering can use multiple lattice cosets. Fejes Tóth later obtained the same leading order using only logarithmically many cosets. Neither statement forces all centers to lie in one lattice.

For that stricter problem, Rogers had a larger general bound. Ordentlich, Regev and Weiss’s lattice-covering theorem improved the universal estimate to order $n^2$. Li and Liu’s 2026 work approached $n\log n$ with an extra iterated-logarithmic factor; their binary-correction companion reduced that remaining loss further.

Li and Liu also constructed centrally symmetric bodies whose lattice covering density is at least a constant times $n\log n$. That lower bound rules out efficient lattices, but it does not rule out a clever irregular arrangement of centers. M2 addresses this stronger exclusion.

For Euclidean balls, classical lower bounds are linear in dimension, while known upper bounds are of order $n\log n$. The family does not close that ball-specific gap. Its lower construction chooses a body designed to be difficult, rather than proving that balls themselves require the worst-case order.

This distinction also separates a random-center failure from a genuine covering lower bound. Showing that typical random centers miss a point leaves open exceptional efficient arrangements. M2 instead samples the body and claims that one realization defeats every low-density arrangement.

4. What the new manuscripts claim

M1 states that an absolute constant $C$ exists such that every convex body $K\subset\mathbb R^n$, $n\geq2$, admits one full-rank lattice with

$$K+\Lambda=\mathbb R^n, \qquad \frac{|K|}{\det\Lambda}\leq Cn\log n.$$

No central symmetry or boundary regularity is required. The constant is uniform over the shape and dimension.

M2 states that absolute constants $c>0$ and $n_0$ exist such that, for every $n\geq n_0$, some centrally symmetric convex body $K_n$ satisfies

$$\theta_T(K_n)>cn\log n.$$

The bodies can also be chosen as centrally symmetric polytopes with rational vertices. The lower bound excludes all locally finite center arrangements, via the periodic-covering reduction; it does not restrict the number of cosets in an intermediate periodic arrangement.

Combining the two claims gives

$$\sup_{K\subset\mathbb R^n}\theta_T(K) \asymp n\log n, \qquad \sup_{K\subset\mathbb R^n}\theta_L(K) \asymp n\log n.$$

The notation $\asymp$ means bounded above and below by positive absolute constant multiples for sufficiently large $n$. The same worst-case order holds when the bodies in the suprema are restricted to centrally symmetric ones.

This is not a formula for every $K$. Cubes still tile at density one. Nor is it a sharp leading constant: the upper and lower absolute constants are not claimed to coincide.

5. Why the advance matters

Importance: 5/5. The pair would determine the optimal order of two longstanding extremal covering problems. The upper result removes the remaining loss in a single-lattice construction; the lower result shows that unrestricted freedom of placement cannot remove the logarithmic factor in the worst case.

The lower theorem would also answer negatively the proposed universal linear bound $\theta_T(K)\leq Cn$. The obstruction persists even under central symmetry and can be realized by rational polytopes, so it is not tied to an exotic nonmeasurable shape or a pathological boundary.

There is a useful conceptual balance. Regular placement is powerful enough to achieve the optimal worst-case order, yet irregular placement can still help particular bodies. The two theorems do not say lattice and translative covering densities are equal for each shape.

The rating reflects the dimensional-order resolution and the breadth of the quantifiers. It does not imply that the constructions give small practical constants, efficient algorithms, or the answer for specific familiar bodies such as balls.

6. The main idea

The upper bound: many useful sections, one lattice

M1 splits coordinates into a large horizontal part and a much smaller vertical part. After an affine normalization, a Gaussian-marginal theorem controls the volumes of horizontal sections at relevant heights. A finite list of such sections approximates the geometric data needed for the covering.

A classical mean-hole estimate then supplies one horizontal lattice leaving an exponentially small uncovered fraction for every section on the list. The remaining issue is how to arrange their contributions at all heights without introducing many independent lattices.

The manuscript develops a hierarchy of binary corrections in the vertical coordinates. At each stage, adjacent integer choices form weighted branches. Two controls are retained simultaneously: the total Gaussian weight stays substantial, while each individual branch weight becomes small. The first ensures enough aggregate covering contribution; the second keeps individual sections in the range where the mean-hole estimate applies.

A common linear shear distributes these contributions while preserving one full-rank lattice. The losses across successively smaller correction blocks are summable. A final dilation by $1+1/n$ fills the tiny remaining holes at a bounded multiplicative volume cost, since $(1+1/n)^n\leq e$.

The lower bound: choose a body that defeats every arrangement

M2 intersects a slightly enlarged ball with symmetric slabs whose normals are chosen by a Poisson process. The resulting random body retains substantial volume with positive probability, while the random cuts create many opportunities for holes in a proposed covering.

The key quantifier is “every arrangement.” A net of lattice bases cannot represent arbitrary finite unions of cosets. The paper instead localizes any hypothetical efficient periodic covering to a fixed window, keeps its center list with multiplicities, and rounds that list to a finite grid. Periodic averaging bounds the list size even for skew lattices or very short periods. Crucially, the finite class is fixed before the random body is sampled.

For a target point and a possible covering center, certain caps of slab normals would cut that target out of the corresponding translate. A hole certificate requires suitable Poisson normals to hit all the necessary cap conditions. Nearly coincident caps are dependent, so the argument groups them and controls overlaps between certificates rather than treating every event as independent.

Many targets are chosen with two levels of angular separation. A lower-tail estimate gives a probability of successful covering small enough to sum over every rounded pattern. A second-moment estimate alone would not supply that strength. One body realization therefore retains adequate volume while defeating the entire candidate class.

Periodization finally transfers the exclusion from all periodic arrangements to arbitrary translative coverings. The rational-polytope conclusion follows by approximation with the strict inequality preserved.

7. Scope, limitations, and open questions

The estimates concern translations of a fixed convex body. Allowing each copy to rotate changes the problem. Bodies are full-dimensional, and covering density counts overlap with multiplicity.

M1 gives all dimensions $n\geq2$ after absorbing finitely many low dimensions into an absolute constant. M2 gives its hard examples only in sufficiently large dimensions. Neither optimizes the numerical constants or identifies a unique worst-case body.

The equality between periodic and unrestricted optimal densities is an infimum statement. It does not assert that every nonperiodic arrangement has matching upper and lower densities, or that an optimal covering must be attained.

The covering density of Euclidean balls remains a separate asymptotic question. Likewise, finding explicit small descriptions of extremal examples or efficiently constructing a near-optimal single lattice goes beyond the existence claims summarized here.

8. Sources and further reading

M1 develops the hierarchical correction and common-shear construction for the lattice upper bound. M2 develops the random-slab body, finite-pattern reduction and simultaneous exclusion for the translative lower bound.

The linked Rogers, Ordentlich–Regev–Weiss and Li–Liu papers provide the main earlier covering bounds. Eldan and Klartag’s pointwise Gaussian-marginal theorem is an explicit input to M1. M2’s appendix states the precise periodization principle needed to pass from finite unions of lattice cosets to unrestricted coverings.

Source manuscripts

• M1. OpenAI, A single-lattice covering bound of order n log n (September 23, 2026).
• M2. OpenAI, Translative covering densities of order n log n (September 23, 2026).

Sources consulted on 14 October 2026 at repository revision 1581d4c. Download the manuscript citations.