A single-lattice covering bound of order n log n

Introduction

For a convex body $K \subset\mathbb{R}^n$, its lattice covering density is

Here a convex body is compact with nonempty interior, and $\det\Lambda$ denotes lattice covolume. The density is the average number of translates covering a point in a fundamental cell: integrating the covering multiplicity over that cell gives $\operatorname{vol}_n(K)$. Thus density measures the overlap needed to cover space when the centers must form one lattice. We prove the following bound.

Theorem 1.1. There is an absolute constant $C > 0$ such that, for every integer $n \ge2$ and every convex body $K \subset\mathbb{R}^n$, one full-rank lattice $\Lambda$ satisfies

No symmetry or boundary regularity is assumed.

History and significance. Rogers proved that every convex body in dimension $n \ge3$ admits a translative covering of density at most $n \log n + n \log\log n + 5n$ [6]. The centers in that construction may be a finite union of lattice cosets. Fejes Tóth later obtained the same leading density using only $O(\log n)$ cosets of one lattice [2]. Requiring the centers to form one lattice is a stronger constraint, and a translative bound does not establish Theorem 1.1. For general lattice coverings, Rogers obtained the bound $n^{\log_2 \log n + O(1)}$ [8]. Ordentlich, Regev, and Weiss replaced it by the universal quadratic bound $\theta_L(K) = O(n^2)$ [5]. Li and Liu subsequently proved

uniformly over convex bodies [3]. Their binary-correction companion improves the exponent of $\log\log n$ to $\frac{2}{3}\log_2(2\pi e) + o(1)$ [4]. Theorem 1.1 removes this remaining iterated-logarithmic loss and gives the constant-factor $n \log n$ bound. In every sufficiently large dimension, Li and Liu also give centrally symmetric bodies with lattice covering density at least $cn \log n$ [3], Theorem 1.3]. Together these results determine the supremum of lattice covering density over bodies in dimension $n$, up to absolute constant factors, as $n \log n$. This statement concerns the supremum over bodies, rather than the covering density of every individual body. A translative lower bound must exclude all center configurations and is a separate question; the present theorem and its proof concern the single-lattice upper bound.

The new mechanism. The proof develops the horizontal–vertical framework and binary-correction ideas of Li and Liu [3, 4]. Write a point as $(x,y)$, where $x$ is the horizontal coordinate and the vertical coordinate $y$ has much smaller dimension. Translating vertically lets several horizontal sections of the same body contribute to covering a given height. The pointwise Gaussian marginal theorem of Eldan and Klartag [1] controls the volumes of these sections after an affine normalization. The lattice mean-hole method of Rogers and Schmidt [7, 9], in the form of Ordentlich–Regev–Weiss [5], Theorem 2.3], then provides one horizontal lattice with an exponentially small uncovered fraction for every section on a finite list.

The remaining task is to distribute these horizontal contributions by one linear shear of a vertical lattice. A binary correction offers two adjacent integer choices in each vertical coordinate. In Li and Liu’s two-stage construction, one auxiliary correction is chosen for an entire weighted Boolean cube [4], Theorem 6.2]. Here the corrections themselves form a hierarchy: we retain their weighted branches through all intermediate blocks.

The total Gaussian mass of the retained family, multiplied by the vertical lattice covolume, stays above an absolute constant, while every individual atom becomes very small. These two properties play different roles: the total mass supplies enough horizontal load, and the atom bound keeps every section within the range of the mean-hole estimate. The corrections are arranged in successively smaller blocks, with sizes approximately $b$, $b^{0.9}$, $b^{0.9^2}$, $\ldots$, stopped at a fixed absolute cutoff. Each block loses only $O(b^{-1/100})$ of the mass. The resulting losses are summable even when the number of blocks grows.

Two auxiliary statements isolate features of potential independent use. The finite-group sampler in Lemma 3.1 converts an almost-everywhere average into a uniform lower average using random subset sums; its cost depends on $\log|H|$, rather than $|H|$. Lemma 6.1 extends the simultaneous Boolean-shift argument of Li and Liu [3], Theorem 4.3] to finitely many binary-suffix patterns with one linear shear. The values of the branch bases can depend on later choices; only the unit separation of two siblings is needed. This preserves the single-lattice structure throughout.

Organization. Section 2 derives the precise section and horizontal lattice estimates from two established results, stating their hypotheses explicitly. Section 3 proves the uniform finite-group sampler. Sections 4 and 5 construct the folded Gaussian blocks and their weighted branching hierarchy. Section 6 chooses the common shear and removes the final holes by a dilation of factor $1 + 1/n$. All new probabilistic and geometric arguments are proved below; no estimate on a single successful branch substitutes for a bound on their total weight.

Notation and constants. Euclidean volume is written $\operatorname{vol}_d$. Expectations over finite groups use uniform probability; $|A|$ denotes cardinality for a finite set. On a lattice torus, $|A|$ instead denotes normalized Haar measure. The standard Gaussian density is

All logarithms are natural except $\log_2$. The constants $c,C$ may change from line to line and are absolute. Asymptotic statements concern sufficiently large dimensions or block sizes; their thresholds never depend on the convex body. The particular decimal exponents below are chosen for strict inequalities, not optimization. A fixed cutoff may be large, but it is chosen before the dimension and remains absolute.

Geometric and horizontal preparations

We use two established results: the pointwise Gaussian marginal theorem of Eldan and Klartag, and the Rogers–Schmidt mean-hole estimate. From the first we derive a finite list of bodies contained in nearby horizontal sections; from the second we obtain one horizontal lattice that works for the whole list. Neither result requires symmetry. This section develops the finite-section and common-lattice preparation of Li and Liu [3], with the precise bounds used in our construction.

A finite list of horizontal sections

Theorem 1 of Eldan and Klartag [1] has the following consequence. There are absolute constants $\alpha,\beta,\gamma,C_0>0$ such that, for all sufficiently large $n$, every isotropic random vector $X\in\mathbb{R}^n$ with a log-concave density has the following property: for each integer $1\le D\le n^\alpha$, there is a $D$-dimensional subspace $E$ whose orthogonal marginal has density $f_E$ satisfying

Here isotropic means $\mathbb{E}X=0$ and $\mathbb{E}XX^{\mathsf T}=I_n$; orthonormal coordinates identify $E$ with $\mathbb{R}^D$. For a uniform law on a convex body, we use the canonical marginal density given by the section integral. We only use the lower bound in (1).

Lemma 2.1 (Section labels). There are absolute constants $c,C>0$ with the following property. Fix $M\ge1$. For all sufficiently large $n$, with threshold depending only on $M$, suppose that $D$ is a positive integer and

Every convex body in $\mathbb{R}^n$ has an invertible affine image $K\subset\mathbb{R}^m\times\mathbb{R}^D$ and a list of at most $(Cm^2)^D$ convex bodies $J_a\subset\mathbb{R}^m$ such that, writing $K_y=\{x:(x,y)\in K\}$, for every $\lVert y\rVert\le R$ some label $a$ satisfies

Proof. An affine transformation makes the uniform law on the given body isotropic: its covariance matrix is positive definite because the body has nonempty interior. The uniform density is log-concave. Put $S=2DR+2$. Uniformly over the displayed range of $D,R$, for sufficiently large $n$ we have

Choose $E$ from (1) and use orthonormal coordinates $E^\perp\times E$. Write $K$ for the resulting body. By Fubini’s theorem, $\operatorname{vol}_m(K_y)/\operatorname{vol}_n(K)$ is a version of the marginal density. The lower bound holds at every required height, independently of density versions: compactness implies that, as $y'\to y$, the fiber $K_{y'}$ is eventually contained in $K_y+\varepsilon B_m$ for each $\varepsilon>0$, where $B_m$ is the unit ball. Continuity of volume under decreasing compact neighborhoods shows that $y\mapsto\operatorname{vol}_m(K_y)$ is upper semicontinuous. Its almost-everywhere Gaussian lower bound therefore extends to every $\lVert y\rVert\le S < n^\beta$ by approaching from the full-measure set. Consequently

We first arrange that $0 \in K_y$ whenever $\lVert y\rVert\le2R$. Take a centered regular simplex in $\mathbb{R}^D$ of inradius $2R$; its vertices $v_0,\ldots,v_D$ have norm $2DR < S$. Each section at a vertex is nonempty by Equation (3), so choose $x_i \in K_{v_i}$. There is an affine map $T:\mathbb{R}^D \to\mathbb{R}^m$ with $T(v_i)=x_i$ for all $i$. Replace the body by its image under $(x,y)\mapsto(x-T(y),y)$. This map has determinant one and translates each horizontal section; thus it preserves both its volume and Equation (3). The new body contains $(0,v_i)$ for every vertex. By convexity it contains $(0,y)$ for every $y$ in the simplex, which includes the ball of radius $2R$.

Let $\{y_a\}$ be a maximal $R/m^2$-separated set in the closed ball of radius $R$. It is an $R/m^2$-net. Comparing the disjoint balls of radius $R/(2m^2)$ about its points with the ball of radius $R+R/(2m^2)$ gives

If $\lVert y-y_a\rVert\le R/m^2$, set $z=y_a+m^2(y-y_a)$. Then $\lVert z\rVert\le2R$ and $y=(1-m^{-2})y_a+m^{-2}z$. Since $(0,z)\in K$, convexity yields

For $m\ge2$, Bernoulli’s inequality gives $(1-m^{-2})^m \ge1-m^{-1}\ge1/2$. By Equation (3), the body $(1-m^{-2})K_{y_a}$ therefore has volume at least $\frac{1}{4}\operatorname{vol}_n(K)\gamma_D(y_a)$. It contains zero, so a further homothety about zero gives a convex body $J_a$ contained in it with exactly

For a chosen nearby $y_a$,

Equations (2.5) and (4) prove Equation (2), and Equation (2.4) bounds the list size. All thresholds used above depend only on $M$, not on the body. □

One lattice for all labels

For a lattice $\Lambda\subset\mathbb{R}^m$, write

where the measure on $\mathbb{R}^m/\Lambda$ is normalized to be a probability measure. Let $\mu_m$ be the invariant probability measure on the space of unimodular lattices in $\mathbb{R}^m$, and put

The estimate of Rogers and Schmidt [7, 9], in the form of Ordentlich–Regev–Weiss [5] [Theorem 2.3], states that there is an absolute constant $C_R>0$ such that every Borel set $J\subset\mathbb{R}^m$ of volume $u\le\eta_m$ satisfies

Lemma 2.2 (Common horizontal lattice). Let $J_1,\ldots,J_N$ be convex bodies in $\mathbb{R}^m$, let $D_h>0$, and set $u_a=\operatorname{vol}_m(J_a)/D_h$. If

there is a lattice $\Lambda_h$ of determinant $D_h$ satisfying

In particular, this conclusion holds for all sufficiently large $m$ if

The dimension threshold in this last formulation depends only on the three numerical bounds, not on the shapes of the bodies.

Proof. Replace every $J_a$ by $J'_a=D_h^{-1/m}J_a$, so that $\operatorname{vol}_m(J'_a)=u_a$. Equation (5) gives

Markov’s inequality bounds the probability that $h_\Lambda(J'_a)>e^{-u_a/2}$ by $(1+C_R)e^{-u_a/2}$. The sum of these probabilities is less than one by Equation (6). Thus a single unimodular lattice $\Lambda$ satisfies all the desired inequalities. Set $\Lambda_h=D_h^{1/m}\Lambda$; scaling identifies the normalized tori, preserves the hole proportions, and gives determinant $D_h$.

Finally, $\eta_m/m\to\frac14\log(27/16)>0$, so $\max_a u_a=o(m)$ ensures the first condition in Equation (6). The other two numerical bounds give

which ensures the second. □

A uniform Boolean sampler

We next construct an averaging operator from random subset sums. The exponential-potential argument develops the finite-group binary correction of Li and Liu [4]; we prove the weighted estimate with random shifts used below, including all required quantitative bounds. A second moment estimate alone gives a good approximation at most base points. A second group of random shifts upgrades this to a lower bound at every base point. This distinction will allow a later block to sample an earlier one even when its base point depends on other lattice choices.

Lemma 3.1 (Uniform Boolean sampling). There is an absolute constant $b_0$ with the following property. Let $b\ge b_0$, let $H$ be a finite abelian group written additively, and suppose that

Let $s$ be an integer satisfying $b^{0.69}\le s\le b$, and choose $w_1,\ldots,w_s$ independently and uniformly in $H$. With $c_*=(\log2)/8$, the probability that

is at least

In particular, the failure probability is at most $b^{-1/2}$ after increasing $b_0$.

Proof. Put $\delta=b^{-1/10}$, $k=\lfloor s/2\rfloor$, and $j_*=s-k$. We use the first $k$ shifts to define

Temporarily take $x$ independently uniform in $H$. For two distinct bit vectors $\varepsilon,\varepsilon'$, their arguments in this average are independent uniform points. To see this, choose an index at which the bits differ and condition on all other shifts. The map from $x$ and that remaining shift to the two arguments is a bijection of $H\times H$: subtracting the arguments determines the shift with coefficient $1$ or $-1$, and then determines $x$. This works in every finite abelian group, with no restriction on its order. Consequently,

For fixed first-stage shifts, let

Chebyshev’s inequality, $\bar g\geq1/2$, and Equation (8) give

The last inequality holds for all sufficiently large $b$, uniformly in $s\geq b^{0.69}$. Indeed, its logarithm is at most

and the first three terms are at most $s\log2/4$ once $b$ is large. Markov’s inequality therefore yields

Fix any first-stage shifts for which $\beta\leq\exp(-c_*s)$. For $0\leq j\leq j_*$, let

Here we count bit labels with multiplicity, even if their subset sums coincide. Thus, for a fresh shift $w=w_{k+j+1}$,

Set $\theta=c_*s/2$ and introduce the potential

Since $N_0=\mathbf{1}_{\mathcal{G}}$, the bound on $\beta$ gives

Most importantly, conditional on every shift chosen so far,

The last equality uses the bijection $(x,w)\mapsto(x,x-w)$ of $H\times H$. It makes no independence assumption about the subset-sum labels themselves.

Conditional Markov’s inequality applied to (10) shows that

There are $j_*\le b$ steps. Except on an event of conditional probability at most $be^{-\theta\delta}$, the recursion holds at every step and gives

For each $x$, its single summand in the potential implies

Combining this with (3.6) yields

For the last inequality, use $\theta\ge(c_*/2)b^{0.69}$, $j_*\ge b^{0.69}/2$, and $\log|H|\le b^4$. Uniformly under these bounds, $1/\theta\le\delta/2$ and $\log|H|/(\theta2^{j_*})\le\delta/2$ once $b_0$ is sufficiently large.

Finally, the full average factors as

On labels counted by $N_{j_*}(x)$, the summand is at least $(1-\delta)\bar g$; all other summands are nonnegative. Thus (11) bounds this expression below by

simultaneously for every $x$. By (9), the total failure probability is at most

as asserted. All thresholds used above are absolute.

Remark 3.2 (Uniformity and offsets). The first stage controls only the proportion of bad base points. A direct union bound over $H$ would be insufficient under the allowed bound $\log|H|\le b^4$. The second-stage potential instead pays $\log|H|$ in (11), divided by an exponentially large number of labels. Once its conclusion holds, the base point can be replaced by any element of $H$, including an offset determined by other random columns. In particular, suppose a subset is chosen independently of the column values and its size lies in the range of Lemma 3.1. One may condition on that subset, apply the lemma to its columns, and then insert arbitrary offsets formed from the complementary columns. This observation will justify the biased-bit mixtures below.

Folded Gaussian blocks

We next turn the uniform Boolean sampler into a distribution adapted to Gaussian weights. The folded Gaussian and biased-bit description follow the setup of Li and Liu [3] and [4]; all estimates required for the hierarchy are proved here. Throughout this section all constants, including the lower threshold on the integer block size $b$, are absolute. For a finite set or group, an expectation with an unqualified subscript denotes the uniform average.

Each point of a unit cube has two adjacent integer corrections in each coordinate, zero and one. We attach a Gaussian weight to every resulting bit vector. Summing these weights folds the Gaussian onto the cube; their normalized values form a product law on the bits. We retain cube locations where this sum has its typical size and no single bit vector carries too much weight. After discretizing the cube, a line subgroup lets us choose at most one usable location in each coset while retaining almost all of the mean weight. The preimage of that subgroup is one lattice. The next section will use these block lattices together.

The folded distribution and its grid

Set

where $0 \le t \le1$ in the definition of $f_b$ and $t \in[0,1]^b$ in that of $F_b$. At $t \in[0,1]^b$, let $P_{b,t}$ be the product probability distribution on $\{0,1\}^b$ whose $j$th coordinate has probabilities

Thus the following identity holds for every bit vector:

Write

Lemma 4.1 (Folded Gaussian grid). For every sufficiently large $b$, there is a prime $p_b$ satisfying

Let $G_b=\mathbb{F}_{p_b}^b$, and associate with $z\in G_b$ the anchor $t_z=z/p_b\in[0,1)^b$, using the representatives $0,\ldots,p_b-1$ in every coordinate. Define the eligible set $E_b\subset G_b$ by the two conditions

Then

Moreover, $\mu_b=\log h_b+O(1)$. Put $\eta_b=bh_b^2/p_b$. If $t$ belongs to the grid cell $Q_z=t_z+[0,p_b^{-1})^b$, then, for every $\varepsilon\in\{0,1\}^b$,

There is an absolute $c>0$ such that, for every eligible $z$, every $t\in Q_z$, and every $\varepsilon\in\{0,1\}^b$,

Proof. First, if $X$ is a standard normal random variable, then $a_b=\mathbb{P}(|X|\le h_b)$. The map

pushes its conditional law on $[-h_b,h_b]$ to the probability density $f_b/a_b$ on $[0,1]$. At the resulting point $t$, one summand in $f_b(t)$ equals $h_b\gamma_1(X)$, whereas $f_b(t)\le2h_b/\sqrt{2\pi}$ everywhere. Consequently

The conditional second moment is bounded by an absolute constant, proving $\mu_b=\log h_b+O(1)$. The elementary Gaussian tail estimate also gives

Here is an elementary way to choose the prime, avoiding any quantitative prime-gap input. Since $\mu_b\ge\log h_b-C\to\infty$, $T=b\mu_b-3b^{0.56}$ is positive for large $b$. Set $l=\lfloor e^T/2\rfloor$. For a prime $q$, the factorial valuation formula gives

Thus the power of each prime in the binomial coefficient is at most $2l$. If all its prime divisors were at most $l/\log(2l)$, their number would be at most $l/\log(2l)$, and hence $\log\binom{2l}{l}\le l$. This contradicts $\binom{2l}{l}\ge4^l/(2l+1)>e^l$ for large $l$. There is therefore a prime divisor $p_b$ with

It follows that $T-O(\log T)\le\log p_b\le T$. Since $\mu_b=O(\log\log b)$, we have $\log T=O(\log b)=o(b^{0.56})$; this proves eq:4.3. In particular $p_b$ grows faster than every fixed power of $b$, and so does $1/\eta_b$.

To prove the mass assertions, first work in the continuous cube with probability density $F_b/a_b^b$. Its coordinates are independent, and $\log F_b$ has mean $b\mu_b$. The function $\log f_b$ takes values in an interval of length $O(1+h_b^2)$: the upper bound was given above, and a nearest-endpoint summand gives $f_b(t)\ge h_b(2\pi)^{-1/2}e^{-h_b^2/8}$. Consequently

For one coordinate, on the interval $|t-1/2|\le(2h_b^2)^{-1}$ we have $f_b(t)\ge ch_be^{-h_b^2/8}$, with an absolute $c>0$. Its probability under $f_b/a_b$ is therefore at least $ch_b^{-1}b^{-9/32}$. The number $N$ of coordinates in this interval is binomial with mean

for sufficiently large $b$, since $23/32 > 0.70$. Its variance is at most its mean, so

Thus a set of continuous $F_b$-mass $1 - O(b^{-1/20})$ satisfies the logarithmic eligibility condition with half its tolerance and the balanced-coordinate condition with half its interval width.

For each $e \in\{0,1\}$ and $u \in[0,1]$,

The same bound holds for $|(\log f_b)'|$, since its derivative is a weighted average of these two logarithmic derivatives. Integrating along the coordinates of a grid cell proves Equation eq:4.6. Rounding a continuous point down to its anchor changes $\log F_b$ by at most $\eta_b$ and every coordinate by less than $p_b^{-1}$. Since $\eta_b < \frac{1}{2}b^{0.56}$ and $p_b^{-1} < (2h_b^2)^{-1}$ for large $b$, the stricter continuous event just considered rounds into $E_b$. In addition, summing the first bound in Equation eq:4.6 over all cells gives

Applying the corresponding comparison on cells whose anchors lie in $E_b$ gives the lower bound on their weighted grid mass. Its upper bound is the total grid mass. Equation (19) now proves both assertions in Equation eq:4.5.

Finally, the odds of a coordinate bit at $t$ are

On a balanced coordinate at an eligible anchor, each bit value has probability at least $\alpha=(1+e)^{-1}$. Therefore $P_{b,t_z}(\varepsilon)\le(1-\alpha)^{b^{0.70}}$ for every $\varepsilon$. Equations eq:4.3 and eq:4.4 give $F_b(t_z)/p_b\le e^{b^{0.56}}$. Since $0.56<0.70$, their product is at most $e^{-cb^{0.70}}$ after decreasing an absolute $c>0$ and increasing the absolute threshold. Equation eq:4.6 proves the same assertion at all points of the cell, again decreasing $c$ if needed.

The exponents are chosen to leave room between four different estimates:

The information window exceeds the square-root fluctuation scale; the previous block’s weight cap fits the sampler; and the number of balanced coordinates exceeds the number of fair bits needed. The first block will have size about $(\log\log n)^2$, so $2(0.70)>1$ also makes its atom bound stronger than the final logarithmic loss. None of these values is intended to be optimal.

Usable anchors and sparse line maxima

The next lemma has two roles. Most of the folded Gaussian mass is kept on anchors whose biased bits sample a prescribed preceding block uniformly in its base point. A suitable line in the new grid then permits this mass to be represented by one selected anchor in each coset.

Lemma 4.2 (Usable anchors). There are absolute constants $A, B > 0$ with the following property. Let $b \ge B$ be an integer, and use the objects in Lemma 4.1. Suppose that $H$ is a finite abelian group, $\log|H| \le b^4$, and $g_0 : H \to[0,\infty)$ satisfies

for some $1 \le a \le b^{1/0.9}$. Then one can choose shifts $w_1,\ldots,w_b \in H$, a usable set $U_b \subset E_b$, and a one-dimensional linear subspace $C_b \subset G_b$ such that, writing $W_\varepsilon= \sum_{j=1}^b \varepsilon_j w_j$,

Define $v_b(z)=\frac{F_b(t_z)}{p_b}\mathbf{1}_{U_b}(z)$, $g_b(x)=\max_{c\in C_b}v_b(x-c)$, $\bar{g}_b=\mathbb{E}_{x\in G_b}g_b(x)$.

These choices satisfy

There is also a base version with no $H$, $g_0$, or $W$: take $U_b=E_b$ and choose $C_b$ so that the conclusions concerning $g_b$ in (23) hold.

Proof. We first select $W$ and $U_b$ when preceding data are given. For large $b$, the bound on $a$ implies

because $0.56/0.9<0.65$. Thus $g_0$ satisfies the cap in Lemma 3.1. Choose the columns $w_j$ independently and uniformly from $H$.

Fix an eligible anchor $z$. A bit whose probability of being 1 is $q$ has the following exact mixture representation: with probability $2\min(q,1-q)$ use a fair bit, and otherwise use its more likely value. Make the mixture choices independently at the $b$ coordinates. Write $S\subset\{1,\ldots,b\}$ for the coordinates chosen to be fair, and $d_j$ for the deterministic value at $j\notin S$. Conditional on these choices, the resulting vector has fair independent bits on $S$ and the values $d_j$ elsewhere; averaging these conditional laws recovers $P_{b,t_z}$ exactly.

By (20), at least $b^{0.70}$ coordinates are selected into $S$ with probability at least $2\alpha$, where $\alpha=(1+e)^{-1}$. Apply Chebyshev’s inequality to the number selected among these coordinates. Its mean is at least $2\alpha b^{0.70}$, its variance is at most its mean, and $b^{0.69}$ is at most half its mean for sufficiently large $b$. Hence

For any fixed $S$ with $b^{0.69}\le|S|\le b$, its columns remain independent uniform elements of $H$. Lemma 3.1 therefore shows, with failure probability $O(b^{-1/2})$ over $W$, that

The conclusion is simultaneous for every $y$. In particular it allows $y=x-\sum_{j\notin S}d_jw_j$, even though that offset involves the other columns of $W$. There is no conditioning on those columns in applying the sampler to the selected ones.

Let $q_W(z)$ be the mixture probability that either $|S| < b^{0.69}$ or the displayed uniform sampler conclusion fails for its selected columns. Equation (24) and Lemma 3.1 imply $\mathbb{E}_{W}q_W(z) \le Cb^{-1/2}$ for each eligible $z$. The weighted average is therefore bounded by

Fix one $W$ for which the inner expectation is at most this last bound, and set

Weighted Markov’s inequality gives the explicit discarded mass

Together with Equation eq:4.5, this proves the last assertion of Equation (23). At every remaining anchor, average the uniform sampler conclusion over successful mixture components and use nonnegativity on the others. For all $x\in H$ the result is at least

proving Equation (21).

It remains to choose $C_b$. The following argument applies both to this $U_b$ and, in the base version, to $U_b=E_b$. Put

The lower eligible weight gives

Choose a line $C\subset G_b$ uniformly among one-dimensional linear subspaces. For any fixed nonzero $u\in G_b$,

Consequently, for every $z\in U_b$, the event $C_C(z)$ that $z+C$ contains another point of $U_b$ has probability at most

The last inequality uses the upper bound in Equation eq:4.3.

For a fixed line, write $S_C(x)=\sum_{c\in C}v_b(x-c)$ and $g_C(x)=\max_{c\in C}v_b(x-c)$. The normalization in Equation (22) ensures

If a coset contains at most one usable anchor, its sum and maximum agree. Otherwise, charge their difference to all usable weights in that coset. This gives the pointwise bound

Averaging first over $x$ and then over $C$ yields

In particular the $p_{b}^{-1}$ in $v_{b}$ cancels the $p_{b}$ translates in the coset sum; the estimate controls lost weight, not just the number of colliding cosets. Some line $C_{b}$ thus satisfies

This proves the mean assertion, in fact with the stronger error $O(b^{-1/20})$. Finally every usable anchor is eligible, so $v_{b}(z) \le e^{5b^{0.56}}$ by Equations eq:4.3 and eq:4.4; the same bound holds for its coset maximum. Enlarging the absolute constants $A,B$ completes both versions of the lemma. □

Remark 4.3. The function $g_{b}$ need not have a positive lower bound at every point: many cosets can contain no usable anchor. Its mean is close to one, and Equation (21) is what recovers that mean uniformly at the next stage. This distinction is essential when the blocks are assembled.

For use in that assembly, the grid construction has the following exact interpretation in a lattice. We identify elements of $C_{b}$ with their integer representatives when writing $C_{b}/p_{b}$.

Lemma 4.4 (From a coset to a Gaussian cell). Let $L_{b}=\mathbb{Z}^{b}+C_{b}/p_{b}$. For $t\in\mathbb{R}^{b}$ put $k=\lfloor p_{b}t\rfloor\in\mathbb{Z}^{b}$ and $x=k\pmod{p_{b}}\in G_{b}$. Floors and fractional parts are taken coordinatewise. If $g_{b}(x)>0$, choose $c\in C_{b}$ attaining its maximum and let $z=x-c\in U_{b}$, again using standard representatives. Then

For all $\varepsilon\in\{0,1\}^{b}$, the point $\lambda+\varepsilon$ lies in $L_{b}$, its residual $t-\lambda-\varepsilon=\tau-\varepsilon$ has coordinates in $[-1,1]$, and

The corresponding individual weight is at most $e^{-c b^{0.70}}$.

Proof. The integer vector $k-z$ reduces to $c$ modulo $p_{b}$, proving $\lambda\in L_{b}$. The remaining identities in Equation (28) follow from $p_{b}t=k+\{p_{b}t\}$ and the chosen maximizing anchor. Adding an integer bit vector preserves $L_{b}$. Since $\tau\in[0,1)^{b}$, the residual coordinate bound follows. Apply Equations eq:4.6 and (18) at $\tau\in Q_{z}$ to obtain the stated lower and upper estimates. □

In the hierarchy below, the preceding group is $H=G_{a}$ with $a\le b^{1/0.9}$. Its size satisfies the remaining hypothesis of Lemma 4.2, because

for sufficiently large $b$. Both this bound and the cap comparison in the proof have strict exponent margins. Thus the same absolute cutoff works at every level, independently of the number of blocks.

A hierarchy of branching lattice points

The preceding block estimates produce a function whose mean is close to one, although the function may vanish at many targets. We now arrange blocks in decreasing sizes. The bits in one block sample the mean of the preceding block; a final block of bounded size supplies a starting point. Keeping all the intermediate branches is what preserves their total weight. The data are chosen from the largest block to the smallest: each new block samples the function already fixed in its predecessor. For a given target, the lattice points are selected in the reverse order, starting with the terminal block and then choosing the earlier blocks conditional on the suffix already selected.

The block sizes and the lattice

Fix a sufficiently large absolute integer $B$, whose requirements will be specified below. Starting with an integer $b_1 \ge B$, form a finite list by putting

whenever this number is at least $B$, and otherwise stopping. Let $r$ be the last index. Increasing $B$ ensures that

Use the notation of the preceding section at size $b_i$: $h_i=h_{b_i}$, $p_i=p_{b_i}$, $G_i=\mathbb{F}_{p_i}^{b_i}$, $F_i=F_{b_i}$, and $P_{i,t}=P_{b_i,t}$. The eligible and usable anchors are always represented by $t_z=z/p_i\in[0,1)^{b_i}$. Apply Lemma 4.2 successively. In the first block there is no preceding function. In each subsequent block apply it to $g_{i-1}$ on $G_{i-1}$. Its hypotheses hold for sufficiently large $B$: if $b=b_i$, then $b_{i-1}\le b^{1/0.9}$ and

The first inequality uses $0.56/0.9<0.65$, and the second has the slack $2/0.9<4$. The means belong to $[1/2,2]$ after another increase of $B$. We obtain usable sets $U_i\subset G_i$, lines $C_i\subset G_i$, and, for $i<r$, matrices $W_i$ of size $b_i$ by $b_{i+1}$ with entries in $\mathbb{F}_{p_i}$. Thus

where $\bar{g}_i=\mathbb{E}_{x\in G_i}g_i(x)$ and $A$ is absolute. Moreover, every $z\in U_i$ with $i>1$ satisfies

All constants in these estimates are independent of the number of blocks.

For $i\le r$, define the raw coordinate lattice

Here the right side means the union of the integer translates of the standard representatives divided by $p_i$; it is independent of the choice of representatives. It is a lattice of determinant $p_i^{-1}$. Indeed, choose a generator $c$ of $C_i$ with its $j$th coordinate equal to 1. The vector $c/p_i$ and the vectors $e_k$ for $k \ne j$ are a basis: they generate $e_j = p_i(c/p_i) - \sum_{k\ne j} c_k e_k$ and all of $L_i$, and their determinant has absolute value $1/p_i$.

Adjoin a terminal block of size

Its size is bounded by a constant depending only on the fixed cutoff $B$. Define $W_r$, of size $b_r$ by $T$, by using the columns $2^k e_j \pmod{p_r}$ for each $1 \le j \le b_r$ and $0 \le k < \lceil\log_2 p_r \rceil$. Consequently

Use standard integer representatives for every $W_i$, and put

Each entry of $A_i$ belongs to $[0,1)$ and is an integer multiple of $1/p_i$. On raw block coordinates $\ell=(\ell_1,\ldots,\ell_{r+1})$, define the invertible block upper triangular map $M$ by

In particular, $\Lambda_v=ML$ is a single full-rank lattice, with

The fractional off-diagonal entries do not change this conclusion: $M$ is one invertible linear map applied to the product lattice $L$.

Proposition 5.1 (Weighted vertical patterns). There are absolute constants $B,C,c,\kappa>0$ such that, for every integer $b_1\ge B$, the construction above has

For every $y\in\mathbb{R}^D$ there is a finite nonempty pattern $P_y\subset L$ such that

The terminal block is constant on the pattern. For each ordinary block $i$ and each fixed suffix $(\ell_{i+1},\ldots,\ell_{r+1})$, its retained values belong to $\lambda_i+\{0,1\}^{b_i}$ for one $\lambda_i\in L_i$ depending on that suffix. In particular $|P_y|\le2^D$.

Order the scalar coordinates by increasing block index and denote them by $\ell[1],\ldots,\ell[D]$. Conditional on any fixed scalar suffix $\ell[j+1],\ldots,\ell[D]$, the possible next values $\ell[j]$ are at most two; if there are two, they differ by 1. This property is preserved upon deleting any subset of the pattern.

If $y \in M[0,1)^D$, all raw coordinates can in addition be restricted to the fixed finite alphabets

For an ordinary block the logarithm of each scalar alphabet size is $O(D\log(D+2)+b_i\log b_i)$; the terminal version omits the second term. All implicit constants are absolute.

Proof. The size and radius bounds follow from Equation (30), the formula $h_i^2 = (9/4)\log b_i$, and the absolute bound on $T$. We prove the weight estimates by an induction that allows an empty intermediate pattern.

Truncated patterns. Retain just the ordinary blocks $1,\ldots,i$, omitting the interaction of block $i$ with its successor. Write $M^{[i]}$ for this truncated map, $d_i=\sum_{j\le i}b_j$, and $D_v^{[i]}=\prod_{j\le i}h_j^{b_j}/p_j$. We claim that for every $y=(y_1,\ldots,y_i)\in\mathbb{R}^{d_i}$ there is a pattern with total weight at least

where

for an absolute $C_0$. The residual and block-branching properties in the proposition are part of this induction. Empty patterns are permitted when $g_i(x_i)=0$.

Fix the lexicographic order on the standard representatives of each finite group; when a maximum has ties, choose the least maximizing anchor. Suppose $g_i(x_i)>0$. Choose a usable anchor $z\in x_i-C_i$ realizing the maximum in Equation (31). By Lemma 4.4 there is $\lambda_i\in L_i$ such that

Consider all choices $\ell_i=\lambda_i+\epsilon$, with $\epsilon\in\{0,1\}^{b_i}$. Their individual block weights satisfy

by Equation eq:4.6. Since each coordinate of $t$ is in $[0,1)$, the corresponding residual has absolute value at most $h_i$. For $i=1$, summing Equation (41) over all bits proves Equation (39) with $a_1=e^{-\delta_1}$.

For $i>1$, attach the preceding induction pattern to each bit choice, using the modified target whose last block is

and whose earlier blocks are unchanged. This is allowed even when its preceding pattern is empty. The new preceding grid index is exactly $x-W_{i-1}\epsilon$, where

Indeed, the vector $W_{i-1}\epsilon$ is integral and hence commutes with the coordinate floor as a translation. The fixed vector $W_{i-1}\lambda_i$ need not be integral; in particular, no compatibility between the adjacent primes is required.

Patterns attached to different bit vectors are disjoint because their last blocks differ. Since $F_i(t_z)/p_i = g_i(x_i)$, multiplying their weights by (41) and summing over every bit vector gives total weight at least

(32) recovers the preceding mean from this sum. Thus we may take

where the second line uses the mean bound in (31). The prime estimates imply that $\delta_i$ decays faster than any fixed negative power of $b_i$. As $b_{i-1}\ge b_i$, increasing one absolute constant $C_0$ bounds the new multiplier below by $1-C_0b_i^{-1/100}$ and yields (40), including its base case. This step uses the weighted sum over all bits, not a choice of one successful bit.

Summable losses. Set $a=1/100$. (30) gives the explicit bound

Choose $B$ so that $C_0B^{-a}\le1/2$. Using $\log(1-u)\ge-2u$ for $0\le u\le1/2$, the products in (40) are bounded below by the positive absolute constant

This lower bound is independent of $r$ and $b_1$.

The terminal correction. For the full target $y$, choose a terminal raw point of the form $\ell_{r+1}=\lfloor y_{r+1}\rfloor+\epsilon$. After accounting for its integer part, varying $\epsilon$ shifts the last ordinary grid index by $-W_r\epsilon$. By (5.5) we can place that index at any point of $G_r$. Since $\overline{g}_r\ge1/2$, choose it at a point with $g_r\ge1/2$. Apply (39) to the first $r$ blocks with this fixed terminal contribution subtracted from $y_r$. Every coordinate of the terminal residual has absolute value at most one, and therefore its Gaussian factor is at least $(2\pi e)^{-T/2}$. If $T_*(B)$ is an upper bound for all possible terminal dimensions, the resulting full pattern has total weight at least

The cutoff $B$ is now fixed, so $\kappa$ is absolute. This proves (36) and, in particular, nonemptiness.

Individual weights and branching. Every retained point comes from a usable anchor in every ordinary block. The atom estimate in (18), followed by the upper rounding estimate in eq:4.6, bounds its individual normalized block weight by

after increasing $B$ and decreasing the absolute constant $c > 0$. The terminal Gaussian factor is at most $(2\pi)^{-T/2} \le1$. Multiplication over all blocks proves Equation (37). The preceding construction already proves all residual bounds.

Different bit vectors at a recursive step have different last blocks. Thus a fixed suffix of later blocks identifies a unique recursive branch. On that branch the construction chose one base $\lambda_i$ before enumerating its bits and retained a subset of its Boolean translate. Distinct branches are distinct raw lattice points. Once a scalar suffix is fixed, the next coordinate can therefore only be the corresponding coordinate of $\lambda_i$ or that coordinate plus one. Further deletion of points cannot destroy this assertion. This proves the stated scalar suffix rule and the cardinality bound.

Finite alphabets. Finally suppose $y = Mz$ with $z \in[0,1)^D$, and put $e_i = z_i - \ell_i$. Equation (35) and the entry bounds on $A_i$ imply

Backward iteration bounds all coordinates of $\ell$ by $1 + (D+2)^D$. Also $L_i \subset p_i^{-1}\mathbb{Z}^{b_i}$ and the terminal lattice is integral. These facts give Equation (38). Each ordinary scalar alphabet has at most $2Q_{\mathrm{raw}}p_i + 1$ elements; $\log p_i = O(b_i\log b_i)$ gives its asserted logarithmic bound. □

For the covering construction we take $b_1 = \lceil(\log\log n)^2\rceil$ once $n$ is sufficiently large. Proposition 5.1 then has $D = O((\log\log n)^2 + 1)$, and both $D$ and $R$ satisfy the polynomial bounds required in Lemma 2.1.

One shear and exact coverage

We extend the simultaneous Boolean-shift argument of Li and Liu [3] (Theorem 4.3) to patterns whose branch bases may depend on later coordinates. Unit separation between siblings still allows one linear shear to treat every pattern in a finite family. Throughout this section all measures on a lattice torus are normalized Haar measures.

A simultaneous shear for finitely many patterns

A labeled pattern in $\mathbb{R}^q$ is a finite nonempty set of points, with one label assigned to each point. Call it binary by suffixes, if, after fixing any suffix of coordinates, the next coordinate has at most two possible values, and two such values always differ by 1. For $q = 0$ a pattern is a single label. Such a pattern has at most $2^q$ points. Deleting points preserves the suffix rule; the result is again a pattern whenever it is nonempty. Taking a nonempty slice at the last coordinate and then deleting that coordinate also preserves the rule.

Figure 1 shows why a fixed global binary cube is not required.

Lemma 6.1 (Simultaneous shear). Let $\mathcal{T} = \mathbb{R}^m/\Lambda_h$, and let $U_a \subset\mathcal{T}$ be measurable sets with $|U_a| \le\eta_a$, where $\eta_a > 0$. For $0 \le q \le D$, let $\mathcal{P}_q$ be finite families of labeled patterns in $\mathbb{R}^q$, binary by suffixes. Suppose they are closed under last-coordinate slicing. Write

ends_mid=1 There are real vectors $Z_1,\ldots,Z_D \in\mathbb{R}^m$ such that, for every $P \in\mathcal{P}_q$,

Here $l[j]$ denotes the $j$th scalar coordinate of $l$.

Proof. The assertion in dimension zero is the assumed bound on each $U_a$. Suppose $Z_1,\ldots,Z_{q-1}$ have been fixed so that all preceding estimates hold. A pattern with just one value of $l[q]$ preserves its bound under the resulting common translation.

Otherwise the two last-coordinate values are $v$ and $v+1$. Let the two slices have cardinalities $k_1$ and $k_2$, and let $A$ and $B$ be their intersection sets. Choose $Z_q$ uniformly in a fixed fundamental parallelepiped of $\Lambda_h$. Translation invariance gives

This identity is valid even when $v$ is not an integer: the products $vZ_q$ and $(v+1)Z_q$ are formed in $\mathbb{R}^m$ before projection. Only the relative shift must be Haar uniform. By Fubini,

Markov’s inequality bounds the probability of violating (44) by $1/L_*$. If either slice has measure zero the intersection has measure zero almost surely, which gives the same conclusion. A union bound over $\mathcal{P}_q$ has total probability less than one, so one choice of $Z_q$ works for all its patterns. Induction proves the result.

Removing a small hole

The next argument is the classical completion-by-dilation method of Rogers [8]. We use the small-dilation form also given by Fejes Tóth [2], and include its proof for the single-lattice setting.

Lemma 6.2 (Completion). Let $K \subset\mathbb{R}^n$ be a convex body and $\Gamma$ a full-rank lattice. If its hole proportion $\delta=1-|\pi_\Gamma(K)|$ satisfies

for a positive integer $k$, then $(1+1/k)K+\Gamma=\mathbb{R}^n$. Proof. Multiplication by $k$ on $\mathbb{R}^n/\Gamma$ maps $\pi_\Gamma(K/k)$ onto $\pi_\Gamma(K)$. Its image has measure at most $k^n$ times the measure of the original set: partition a fundamental parallelepiped into $k^n$ cells on which the map is injective. Consequently

For every point $x$ of the torus, the sets $\pi_\Gamma(K)$ and $x-\pi_\Gamma(K/k)$ have measures summing to more than one and therefore intersect. Thus $\pi_\Gamma(K)+\pi_\Gamma(K/k)$ is the whole torus. Finally, convexity gives $K+K/k=(1+1/k)K$. Neither symmetry nor the inclusion $0\in K$ is required.

Proof of the covering theorem

Proof of Theorem 1.1. All constants in the vertical construction, including its cutoff $B$, are fixed first. For sufficiently large $n$, put $s=\log\log n$ and use Proposition 5.1 with $b_1=\lceil s^2\rceil$. Retain its notation $L$, $M$, $D$, $D_v$, $b_i$, $h_i$, and set

Here $D=O(s^2+1)$ and $R$ is bounded by a fixed polynomial in $s$. After passing to the affine coordinates of Lemma 2.1, there are at most $(Cm^2)^D$ horizontal bodies $J_a$ such that every $v$ with $\lVert v\rVert\le R$ has a label satisfying

Choose an absolute constant $C_*$ later and put

For any vertical target $y$, use its pattern from Proposition 5.1 and label each raw point $l$ by a body contained in the section at $y-Ml$. The residual bound permits (45). With the chosen horizontal covolume, the normalized section volume is comparable to the corresponding normalized Gaussian weight multiplied by $\rho$:

Thus the total weight supplies the sum of the horizontal loads, while the atom bound controls each load separately. These estimates give

where $c_3=c_{\mathrm{sec}}\kappa>0$ is absolute. Three scale comparisons are needed. First,

Second, every pattern has at most $2^D$ points, so deleting those with $u_a(l)<\sqrt m$ loses at most

Third, the logarithm of the number of labels is $O(D\log m)=o(\sqrt{m})$. These statements follow from $D=O(s^2+1)$ and $\log n=e^s$; all their constants are independent of $K$. In particular the retained pattern is nonempty and has load at least $c_3\rho/2$ for large $n$.

Restrict the label list to $\sqrt{m}\le u_a\le U_n$. Lemma 2.2 gives one lattice $\Lambda_h$ of covolume $D_h$ for which the hole sets

satisfy $lvert U_a\rvert\le e^{-u_a/2}$ simultaneously. We next select one shear that works for every retained pattern, not a separate shear for each target.

A finite family for all targets. Initially restrict to $y=Mz$ with $z\in[0,1)^D$. This is enough because $L$ contains $\mathbb{Z}^D$; after the final lattice is defined, integer raw translations will reduce any target to this region. The finite-alphabet conclusion of Proposition 5.1 places each scalar raw coordinate in $[-Q_{\rm raw},Q_{\rm raw}]$, where $Q_{\rm raw}=1+(D+2)^D$. In block $i\le r$ it is a multiple of $1/p_i$; in the terminal block it is an integer. The logarithmic alphabet size is therefore at most

for some fixed absolute exponent $c_0$.

Order scalar coordinates by increasing block index, and take $\mathcal{P}_q$ to be all labeled patterns on the first $q$ coordinate alphabets that are binary by suffixes, for $0\le q\le D$. This includes every retained full pattern: the base in a block depends only on later blocks, and deleting points cannot introduce a third value at any suffix. The families are closed under slicing.

Let $\mathcal{A}_j$ be the alphabet of scalar coordinate $j$, and let $N_{\mathrm{lab}}$ be the number of retained section labels. A labeled point consists of a coordinate tuple and one such label, so $N=N_{\mathrm{lab}}\prod_{j=1}^D\lvert\mathcal{A}_j\rvert$ bounds their number in each of these coordinate spaces. Consequently

For example, the last bound follows by encoding a set of at most $2^D$ points as a list of that length, padded with a dummy symbol. Take $L_\ast=2(Q+1)$. Then

Indeed $4^D$ times any fixed polynomial in $s$ is $\exp(O(s^2))=o(n)$.

The covering lattice. Apply Lemma 6.1 with $\eta_a=e^{-u_a/2}$ and set $Zl=\sum_{j=1}^D l[j]Z_j$. Define

It is a full-rank lattice, being the image of the product lattice $\Lambda_h\times L$ under an invertible block triangular linear map. Its covolume is exactly $D_hD_v$, so $\operatorname{vol}_n(K)/\det\Gamma=\rho$.

For a fixed $y$ and a retained labeled pattern, each $J_a(l)$ lies in the section $K_{y-Ml}$. The uncovered horizontal points of $K+\Gamma$, viewed in $T=\mathbb{R}^m/\Lambda_h$, therefore lie in

For $y \in M[0,1)^D$, Lemma 6.1 and the retained load give the uniform bound

For other $y$, reduce $M^{-1}y$ modulo $\mathbb{Z}^D$ and translate by the corresponding point $(Zk,Mk)\in\Gamma$. This only translates the horizontal section on its torus, so the same bound holds.

Let $F_h,F_v$ be fundamental parallelepipeds of $\Lambda_h$ and $ML$. Their product is a measurable fundamental domain for $\Gamma$: first reduce the vertical coordinate using a point $(Zl,Ml)$, and then reduce the horizontal coordinate using $\Lambda_h$. The union $K+\Gamma$ is closed, since translates of the compact set $K$ by a lattice are locally finite. Its complement is therefore measurable, and Fubini integrates Equation (6.9) over $F_v$. No measurable selection of auxiliary patterns is needed. Equations (6.3) and (6.7) yield

once $C_*$ is a sufficiently large absolute constant and then $n$ is sufficiently large. Since $n^{-2n}<(1-n^{-2n})n^{-n}$ for $n\ge2$, Lemma 6.2 with $k=n$ gives $(1+1/n)K+\Gamma=\mathbb{R}^n$. Thus

is a single covering lattice for $K$, of density

Affine invariance and the remaining dimensions. Translations of a body do not change the covering property, and invertible linear maps applied to both body and lattice preserve density. Hence the affine normalization can be undone.

There remains only a fixed finite set of dimensions. In each such dimension choose a maximum-volume simplex with vertices in $K$, which exists by compactness and has positive volume. Put its vertices at $0,e_1,\ldots,e_n$ by an affine map. Replacing the $j$th nonzero vertex by any $x\in K$ changes the determinant to $x_j$, so maximality gives $\lvert x_j\rvert\le1$. Thus

The lattice $n^{-1}\mathbb{Z}^n$ covers by translates of the smaller cube and therefore of $K$, with density at most $(2n)^n$. The maximum of $(2n)^n/(n\log n)$ over the remaining finite set can be absorbed in one absolute constant. This proves the theorem for every $n\ge2$.