2d5618e cad1fc6
=====================================================================
A SINGLE-LATTICE COVERING BOUND OF ORDER n log n
=====================================================================
A self-contained rewrite for a curious high-school reader who knows
a little geometry and a little probability. Everything is stated and
then proved. Two deep facts are imported from the literature: the Eldan--Klartag
marginal theorem and the Rogers--Schmidt mean-hole estimate. Everything
else, including the Li--Liu binary correction and the completion
argument, is re-proved from scratch.
Contents
1. The problem and the answer
2. Lattices, density, and why "one lattice" is harder
3. The main theorem
4. History
5. The strategy in one page
6. Notation and standard facts
7. Geometric preparation: horizontal sections
8. A uniform Boolean sampler
9. Folded Gaussian blocks
10. The branching hierarchy
11. One shear, and exact coverage
12. Assembling the main theorem
13. References
---------------------------------------------------------------------
1. THE PROBLEM AND THE ANSWER
---------------------------------------------------------------------
A convex body in R^n is a compact, solid shape with no dents: every
straight segment between two of its points lies inside it. Think of a
disk, a triangle, or an egg. Now take infinitely many copies of a fixed
convex body K, and move each copy so that its base point is one of the
points of a fixed grid (a lattice). We want those copies to cover all
of R^n, with as little overlap as possible.
The number we track is the covering density: the average number of
copies of K lying over a typical point of space. The value 1 is ideal.
Bigger values mean more wasted overlap. In dimension n the question
"how small can this average be?" has been studied for over a century.
This paper proves the sharp-order result for a single lattice:
MAIN THEOREM. There is an absolute constant C > 0 such that, for
every dimension n >= 2 and every convex body K in R^n, there is ONE
full-rank lattice L with
K + L = R^n (the copies cover everything), and
vol_n(K) / det(L) <= C n log n (the density is at most n log n
up to a constant factor).
The constant C is the same for every K and every n. There is no
assumption of symmetry or of a smooth boundary.
---------------------------------------------------------------------
2. LATTICES, DENSITY, AND WHY "ONE LATTICE" IS HARDER
---------------------------------------------------------------------
A lattice in R^n is the set of all integer combinations of n fixed
independent vectors b1,...,bn:
L = { k1 b1 + ... + kn bn : each ki is an integer }.
The standard example is Z^n, the set of points with integer
coordinates. The box [0,1)^n is a fundamental cell of Z^n: one copy
per lattice point, no overlap, tiles all of space. The volume of a
fundamental cell is the same for any choice of cell, and is called
the determinant (or covolume) det(L). For Z^n it is 1.
To cover space with copies of K placed at the points of L, we want
every point of R^n to be within "K-distance" of some lattice point.
If a fundamental cell of L has volume det(L), then a typical point is
covered by about vol_n(K)/det(L) copies of K. Precisely, integrate the
covering multiplicity over one fundamental cell: the integral equals
vol_n(K), so the average multiplicity is vol_n(K)/det(L). That is the
covering density.
DEFINITION. The lattice covering density of K is
theta_L(K) = inf { vol_n(K)/det(L) :
L full-rank, K+L = R^n }.
Now the "one lattice" restriction. There is a weaker notion in which
the centers of the copies are allowed to be a finite union of
translates of a single lattice:
centers = (a1 + L) union ... union (ak + L).
This gives k cosets of one lattice. Covering by several cosets is
strictly easier than covering by one, because you can distribute the
copies more cleverly. Rogers' classical translative bound and the
Fejes Toth refinement are of this multi-coset type. The theorem proven
here needs the centers themselves to be a single lattice: L alone, no
extra cosets. That is the strong statement.
---------------------------------------------------------------------
3. THE MAIN THEOREM, STATED PRECISELY
---------------------------------------------------------------------
THEOREM (main). There is an absolute constant C > 0 such that, for
every integer n >= 2 and every convex body K in R^n, there is one
full-rank lattice L in R^n with
K + L = R^n (coverage), and
vol_n(K)/det(L) <= C n log n (bounded density).
Here vol_n is n-dimensional volume, log is the natural logarithm, and
C does not depend on K or n.
Two remarks clarify what is and is not being claimed.
(1) This is a bound on the supremum of lattice covering density over
all bodies in dimension n, up to a constant factor. It does not assert
that every individual body has density close to n log n; many bodies
(the cube, the ball) cover far more efficiently.
(2) A matching lower bound is known from the other side. For every
large enough n there exist centrally symmetric bodies whose best
single-lattice covering density is at least c n log n for a fixed
constant c > 0. So n log n is the correct order of the worst case.
The proof rests on two imported theorems:
(EK) the Eldan--Klartag pointwise Gaussian marginal theorem;
(RS) the Rogers--Schmidt mean-hole estimate, in the numerical form
given by Ordentlich--Regev--Weiss.
It also follows the Li--Liu binary-correction METHOD, but re-proves that
method from scratch here as the "uniform Boolean sampler" (Lemma 8.1),
so the binary correction is used, not assumed.
---------------------------------------------------------------------
4. HISTORY
---------------------------------------------------------------------
1957. Rogers showed that a convex body K in dimension n admits a
translative (multi-coset) covering of density at most
n log n + n log log n + 5n. The centers there are a finite union of
lattice cosets.
1959. Rogers obtained the first general single-lattice bound, of order
n^{log_2 log n + O(1)}. This grows much faster than n log n.
2009. Fejes Toth recovered the leading n log n for translative
coverings using only O(log n) cosets of one lattice. The centers are
still several cosets, not a single lattice.
2022. Ordentlich, Regev, and Weiss proved the universal quadratic
single-lattice bound theta_L(K) = O(n^2). This was the first bound of
polynomial order in n for one lattice.
2026 (Li--Liu). Li and Liu proved the near-optimal single-lattice
bound
theta_L(K) <= C n log n (log log n)^{10/3 + o(1)},
uniformly over all convex bodies. A companion manuscript sharpens the
exponent of log log n to (2/3) log_2(2 pi e) + o(1). These removed all
but an iterated-logarithmic factor.
This paper removes that last factor and proves theta_L(K) <= C n log n
outright, with one lattice. In the same regime Li and Liu exhibit
centrally symmetric bodies whose density is at least c n log n for a
constant c. Together, these pin the worst-case single-lattice covering
density to order n log n.
---------------------------------------------------------------------
5. THE STRATEGY IN ONE PAGE
---------------------------------------------------------------------
We write a point of R^n as (x,y), with x the "horizontal" coordinate
in R^m and y the "vertical" coordinate in R^D, where D is much smaller
than m = n - D. Two ideas do all the work.
IDEA A (vertical stacking). Because D is small, we can afford to look
at many horizontal slices of K. Moving a point vertically by small
amounts lets several slices of K sit over the same height y. If we
can get one horizontal lattice Lambda_h that covers each slice with
exponentially small holes, then stacking enough vertical contributions
closes the holes entirely.
IDEA B (binary correction, organized as a hierarchy). A single
vertical lattice translate gives one slice per point. To stack many
slices we choose, for each vertical coordinate, one of two adjacent
integer values. That doubles the number of slices per step, but the
Gaussian weight of each extra slice drops geometrically. Li and Liu
allow one such binary correction for an entire weighted Boolean cube.
We instead let the corrections themselves form a hierarchy: we retain
the weighted branches through many intermediate blocks, so their
total Gaussian weight stays above a fixed constant while every
individual branch becomes very light.
The two properties play complementary roles:
- the TOTAL retained weight supplies enough horizontal load that
the common-lattice argument can cover with tiny holes;
- the ATOM bound (each retained branch is light) keeps each
individual slice within the range where the mean-hole estimate
applies.
The blocks are sized roughly b, b^{0.9}, b^{0.9^2}, ... down to a
fixed absolute cutoff. Each block loses only O(b^{-1/100}) of the
mass, and those losses are summable even as the number of blocks
grows.
Once the vertical arrangement and the horizontal lattice are fixed,
one final linear "shear" chooses a single vertical offset that works
simultaneously for all retained slices. That shear is the only place
the single-lattice structure is delicate, and section 11 proves a
simultaneous-shear lemma just for this purpose. Finally, a dilation
by the tiny factor 1 + 1/n eliminates the last holes without changing
the density by more than a constant factor.
---------------------------------------------------------------------
6. NOTATION AND STANDARD FACTS
---------------------------------------------------------------------
To keep formulas short we gather the conventions and the elementary
facts they rely on.
VOLUME. For a measurable set A in R^d, vol_d(A) is its d-dimensional
volume. For the whole body we write vol_n(K).
GAUSSIAN. The standard Gaussian density on R^d is
gamma_d(y) = (2 pi)^{-d/2} exp(-|y|^2 / 2).
It integrates to 1. Its one-dimensional version is
gamma_1(t) = (1/sqrt(2 pi)) exp(-t^2/2). The single most-used fact
about it is the tail estimate: for large h > 0,
Prob(|X| <= h) = 1 - 2 Prob(X > h),
Prob(X > h) <= (1/h) gamma_1(h) = (1/h) (2 pi)^{-1/2} e^{-h^2/2}.
INTEGERS AND FLOORS. For x in R^d, floor(x) applies to each coordinate
and {x} = x - floor(x) is the coordinatewise fractional part, valued
in [0,1)^d.
FINITE GROUPS AND EXPECTATIONS. For a finite set or finite abelian
group H, E_{x in H} f(x) means the uniform average (1/|H|) sum_x f(x),
and Prob means uniform probability. |A| is the number of elements of
the finite set A. When A sits on a lattice torus (below), |A| instead
denotes its normalized Haar measure.
LATTICE TORUS. Let Lambda be a full-rank lattice in R^m. The quotient
T = R^m / Lambda is a compact group. It has a unique translation-
invariant probability measure (Haar measure): if F is any fundamental
parallelepiped of Lambda, then the measure of the image of a set S is
vol_m(S intersect F)/det(Lambda). We write |A| for the measure of a
subset A of T. The natural projection is written pi_Lambda: R^m -> T.
Important: for a subset J of R^m, its image pi_Lambda(J) is the set of
torus points covered by some translate of J; its complement is the
hole set. The number
h_Lambda(J) = 1 - |pi_Lambda(J)|
is the hole proportion: the fraction of the torus NOT covered by
J + Lambda. It is a probability, between 0 and 1.
LATTICES AND COVOLUME. A lattice built from vectors b_1,...,b_m is
written Lambda = Z b_1 + ... + Z b_m. Its determinant det(Lambda) is
the volume of any fundamental parallelepiped. If T is an invertible
linear map, then T(Lambda) is a lattice with det(T Lambda) =
|det T| det(Lambda). Scaling Lambda by a factor s changes its
determinant by s^m.
CONSTANTS. The letters c and C always denote absolute positive
constants, possibly changing from line to line. They never depend on
the convex body K or on the growing dimension. The decimal exponents
used later (0.56, 0.65, 0.69, 0.70, ...) are chosen only to satisfy
strict inequalities; they are not optimal.
ASYMPTOTICS. "Sufficiently large n" (or sufficiently large block size
b) means beyond an absolute threshold that does not depend on K. Some
lemmas fix an absolute integer B large enough for a finite list of
inequalities to hold; that B is chosen once, before n grows, and stays
absolute throughout.
TWO SMALL INEQUALITIES WE USE REPEATEDLY.
(i) Bernoulli: for 0 <= t <= 1 and integer m >= 1,
(1 - t)^m >= 1 - mt. In particular for m = n^2 and t = n^{-2},
(1 - n^{-2})^n >= 1 - 1/n >= 1/2 when n >= 2.
(ii) log(1 - u) >= -2u for 0 <= u <= 1/2.
These two turn multiplicative loss estimates into additive ones.
---------------------------------------------------------------------
7. GEOMETRIC PREPARATION: HORIZONTAL SECTIONS
---------------------------------------------------------------------
This section turns two known theorems into the two tools the rest of
the proof needs:
TOOL 1. For a convex body K in R^n, we can find a small finite list
of m-dimensional bodies J_a, each sitting inside a horizontal slice
of K at some height y_a, whose volumes are comparable to the slice
volumes. Small list = polynomial in the number of slices.
TOOL 2. For any such finite list, there is ONE horizontal lattice
Lambda_h that covers every J_a with exponentially small holes,
provided each J_a is small compared to the lattice determinant and
the list is short compared to sqrt(m).
Together, Tools 1 and 2 mean: one horizontal lattice already covers
almost everything in every relevant slice. The vertical work of the
next sections then plugs the residual holes.
7.1 A finite list of horizontal sections.
We first state the imported input, then derive what we need.
IMPORTED FACT (Eldan--Klartag). There are absolute constants
alpha, beta, gamma, C_0 > 0 with the following property. For all
sufficiently large n, and for every isotropic log-concave random
vector X in R^n (isotropic means E X = 0 and E XX^T = I_n), for each
integer D with 1 <= D <= n^alpha, there is a D-dimensional subspace E
whose orthogonal marginal has density f_E satisfying
| f_E(y)/gamma_D(y) - 1 | <= C_0 n^{-gamma}
for all y in E with |y| <= n^beta. (EK)
We only use the LOWER bound in (EK): f_E(y) >= (1/2) gamma_D(y) in the
range. To get a version of (EK) for the uniform law on a convex body
K, note that after an affine change of coordinates making that law
isotropic -- which is possible because K has nonempty interior, so
its covariance matrix is positive definite -- the uniform density is
log-concave. By Fubini, the marginal density of the vertical
coordinate is exactly vol_m(K_y)/vol_n(K), where K_y is the
horizontal slice at height y. So (EK) says: after this change of
coordinates, most horizontal slices have volume close to
vol_n(K) gamma_D(y).
The next lemma makes this uniform over all relevant heights, fixes
a finite list of slices, and records the small list of bodies we will
cover horizontally.
LEMMA 7.1 (section labels). There are absolute constants c, C > 0 with
the following property. Fix M >= 1. For all sufficiently large n, with
threshold depending only on M, suppose D is a positive integer and
1 <= D, R <= M (1 + log log n)^M, m = n - D.
Then every convex body K in R^n has an invertible affine image, again
written K, contained in R^m x R^D, and a list of at most (C m^2)^D
convex bodies J_a contained in R^m such that, writing K_y = {x in R^m :
(x,y) in K} for the horizontal slice at height y, for every |y| <= R
there is a label a with
J_a is contained in K_y, and
c vol_n(K) gamma_D(y) <= vol_m(J_a)
<= C vol_n(K) gamma_D(y). (7.1)
In words: at every height |y| <= R, one of the listed bodies fits
inside the slice and has volume comparable to the "expected" slice
volume vol_n(K) gamma_D(y).
PROOF OF LEMMA 7.1.
Step 1: the slice volume is at least half its expected value. Put the
uniform law on the given K in isotropic position; this is one invertible
affine map and does not change anything about covering densities or
ratios of volumes. Choose the subspace E from (EK) and use orthonormal
coordinates E^perp x E, writing a point as (x,y) with x in R^m and y in
E. Put S = 2DR + 2. Uniformly over the range 1 <= D,R <= M(1+loglog n)^M
we have D <= n^alpha, S < n^beta, and C_0 n^{-gamma} <= 1/2 for n large
enough. By Fubini, vol_m(K_y)/vol_n(K) is a version of the marginal
density of y, so (EK) yields
vol_m(K_y) >= (1/2) vol_n(K) gamma_D(y) (7.2)
for almost every y with |y| <= S. We want (7.2) at EVERY such y, not
just almost every. The trick is that y -> vol_m(K_y) is upper
semicontinuous. Indeed, if y' -> y, the compact convex slice K_{y'} is
eventually contained in the epsilon-neighbourhood K_y + eps B_m of K_y
for each eps > 0 (convexity plus compactness), so its volume cannot
exceed vol_m(K_y) + o(1). A function that is bounded below almost
everywhere by a continuous strictly positive function is therefore
bounded below by it EVERYWHERE, by approaching from the good set.
Hence (7.2) holds for all |y| <= S, not just almost all.
Step 2: arrange that every relevant slice contains the origin. Put a
centered regular simplex in R^D with inradius 2R; its D+1 vertices
v_0,...,v_D have norm 2DR < S. By (7.2) each slice K_{v_i} is nonempty,
so pick x_i in K_{v_i}. There is an affine map T: R^D -> R^m with
T(v_i) = x_i for all i. Replace K by its image under the determinant-one
map (x,y) -> (x - T(y), y). This translates each horizontal slice by a
fixed vector, so slice volumes and inequality (7.2) are unchanged. The
new body contains (0, v_i) for every vertex i; by convexity it contains
(0,y) for every y in the simplex, in particular for every |y| <= 2R.
Step 3: a finite net of heights. 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) around its points with the ball of
radius R + R/(2m^2) gives
#{y_a} <= (1 + 2 m^2)^D <= (3 m^2)^D. (7.3)
Step 4: nearby slices contain scaled-down net slices. If |y - y_a| <=
R/m^2, set z = y_a + m^2(y - y_a). Then |z| <= 2R and
y = (1 - m^{-2}) y_a + m^{-2} z. Since (0,z) lies in K by Step 2,
convexity gives
(1 - m^{-2}) K_{y_a} is contained in K_y. (7.4)
Step 5: a body of prescribed volume inside the scaled slice. By
Bernoulli's inequality (Section 6, item i), (1 - m^{-2})^m >= 1 - m^{-1}
>= 1/2 for m >= 2. Hence by (7.2) the scaled slice (1 - m^{-2}) K_{y_a}
has volume at least (1/4) vol_n(K) gamma_D(y_a). That scaled slice is
convex and contains 0 (Step 2). Shrinking it about 0 by a further
homothety gives a convex body J_a contained in it with EXACTLY
vol_m(J_a) = (1/8) vol_n(K) gamma_D(y_a). (7.5)
Step 6: the volume comparison. For a chosen label a with |y - y_a| <=
R/m^2,
| log( gamma_D(y_a)/gamma_D(y) ) |
<= (1/2) |y_a - y| (|y_a| + |y|) <= R^2/m^2 = o(1).
So gamma_D(y_a) and gamma_D(y) agree up to a factor 1 + o(1). Combine
(7.4) (J_a lies inside K_y) with (7.5) and this factor: the two-sided
bound (7.1) follows with the constants c, C adjusted by absolute
factors. The list size is (7.3). All thresholds depend only on M, never
on K. That proves Lemma 7.1.
7.2 One lattice that works for every label.
The mean-hole estimate says that for a random lattice, the hole
proportion of a set of volume u is about e^{-u}, on average. Because
e^{-u} is tiny when u is large, a single random lattice already covers
a fixed convex body almost entirely. We need one lattice that does
this for all the J_a simultaneously. That is possible because the
number of J_a is small compared with sqrt(m), so a union bound works.
We need one more careful point. The mean-hole estimate is about a
RANDOM UNIMODULAR lattice, with respect to a specific probability
measure mu_m on unimodular lattices in R^m. We restate it as an
imported fact.
IMPORTED FACT (Rogers--Schmidt; numerical form of Ordentlich--Regev--
Weiss). Let mu_m be the invariant probability measure on unimodular
lattices in R^m, and put
eta_m = (m/4) log(27/16) - 3 log m.
There is an absolute constant C_R > 0 such that for every Borel set
J contained in R^m of volume u <= eta_m,
| E_{Lambda in mu_m} h_Lambda(J) - e^{-u} |
<= C_R e^{-eta_m}. (RS)
Here h_Lambda(J) = 1 - |pi_Lambda(J)| is the hole proportion, as in
Section 6. The intuition: choose a random unimodular lattice. The
probability that a point of the torus falls in J + Lambda, on average
over the torus and over Lambda, is roughly the number of lattice
points of Lambda per unit volume times vol_m(J) = u. But the lattice
points repel each other, so the actual covering probability is
slightly larger than the naive e^{-u}; the error term C_R e^{-eta_m}
accounts for the correction.
LEMMA 7.2 (common horizontal lattice). Let J_1,...,J_N be convex
bodies in R^m, let D_h > 0, and put u_a = vol_m(J_a)/D_h. If
max_a u_a <= eta_m,
(1 + C_R) sum_{a=1}^N e^{-u_a/2} < 1, (7.6)
then there is a lattice Lambda_h of determinant D_h such that
h_{Lambda_h}(J_a) <= e^{-u_a/2} for all a. (7.7)
In particular, the conclusion holds for all sufficiently large m if
min_a u_a >= sqrt(m), max_a u_a = o(m), log N = o(sqrt m). (7.8)
The dimension threshold in (7.8) depends only on the numerical bounds
in (7.8), never on the shapes of the J_a.
PROOF OF LEMMA 7.2.
Step 1: rescale so all bodies have the desired normalized volume. Let
s = D_h^{-1/m} > 0 and set J'_a = s J_a. Then
vol_m(J'_a) = s^m vol_m(J_a) = vol_m(J_a)/D_h = u_a.
Step 2: bound the average hole proportion of each J'_a. By (RS) and
the hypothesis max_a u_a <= eta_m,
E_{Lambda in mu_m} h_Lambda(J'_a)
<= e^{-u_a} + C_R e^{-eta_m}
<= (1 + C_R) e^{-u_a}. (7.9)
Step 3: bound the failure probability of one a by Markov's inequality.
For a nonnegative random variable X, Prob(X > t) <= E X / t. Using
(7.9) with t = e^{-u_a/2},
Prob_{mu_m} ( h_Lambda(J'_a) > e^{-u_a/2} )
<= (1 + C_R) e^{-u_a/2}. (7.10)
Step 4: union bound over all a. The total failure probability is at
most
(1 + C_R) sum_{a=1}^N e^{-u_a/2}
which is < 1 by (7.6). So with positive probability a random unimodular
Lambda succeeds for every a at once; in particular, some Lambda
satisfies h_Lambda(J'_a) <= e^{-u_a/2} for every a.
Step 5: undo the scaling. Let Lambda_h = D_h^{1/m} Lambda. Then
det(Lambda_h) = D_h, and the normalized torus R^m/Lambda_h is
isomorphic (as a measure-preserving group) to R^m/Lambda, so hole
proportions are unchanged:
h_{Lambda_h}(J_a) = h_Lambda(J'_a) <= e^{-u_a/2}.
That is (7.7).
Step 6: check the particular regime (7.8). Here
eta_m/m -> (1/4) log(27/16) > 0, so max_a u_a = o(m) forces
max_a u_a <= eta_m for large m and (7.6)'s first line is satisfied. For
the second line,
(1 + C_R) sum_{a=1}^N e^{-u_a/2}
<= (1 + C_R) exp( log N - (1/2) sqrt(m) ),
because every u_a >= sqrt(m) forces each e^{-u_a/2} <= e^{-sqrt(m)/2},
so the sum carries a factor N and an exponential decay. With
log N = o(sqrt m), this is o(1). Hence (7.6) holds, and by Steps 1-5
so does (7.7). This proves Lemma 7.2.
---------------------------------------------------------------------
8. A UNIFORM BOOLEAN SAMPLER
---------------------------------------------------------------------
Here is the engine that, in the next sections, lets one block of
coordinates "sample" the average value of a function defined on the
block before it. We work on a finite abelian group H. We are given a
function g: H -> [0, infinity) whose average
gbar = E_{x in H} g(x)
is close to 1 (between 1/2 and 2). We want to approximate gbar, at
EVERY base point x in H, by an average of g over random subset sums.
But "average over random subset sums" needs the shifts to be chosen
once and then work for all x simultaneously. We achieve that by a
two-stage choice of shifts.
We make b choices of shift w_1,...,w_b in H, uniformly and
independently. Then for a subset of s <= b of them we form the 2^s
subset sums and average g over those. The result is a random variable
that depends on the chosen shifts. The theorem below says: with high
probability over the shifts, the average is close to gbar, uniformly
in x.
The proof is two-stage. Stage 1 uses only k = floor(s/2) shifts and a
second-moment estimate to show that at MOST base points x, the average
is bad (a good FRACTION of base points). Stage 2 uses the remaining
shifts and an exponential potential to upgrade "good fraction" to
"good everywhere". The potential trick pays the cost log|H| only
through a division by 2^{j_*}, which is enormous, so the final bound
has an exponentially small failure probability.
LEMMA 8.1 (uniform Boolean sampling). There is an absolute constant
b_0 with the following property. Let b >= b_0, let H be a finite
abelian group written additively, and suppose
log |H| <= b^4,
0 <= g <= exp(b^{0.65}), (8.1)
gbar = E_{x in H} g(x) is in [1/2, 2].
Let s be an integer with b^{0.69} <= s <= b. Choose w_1,...,w_s
independently and uniformly in H. Put c_* = (log 2)/8. Then with
probability at least
1 - exp(-c_* b^{0.69}) - b exp( -(c_*/2) b^{0.59} ), (8.2)
the following holds for EVERY x in H:
2^{-s} sum_{eps in {0,1}^s}
g( x - sum_{i=1}^s eps_i w_i )
>= (1 - 3 b^{-1/10}) gbar. (8.3)
In particular, since the two terms in (8.2) are exponentially small
in b^{0.69} and b^{0.59} respectively, the failure probability is at
most b^{-1/2} once b_0 is chosen large enough.
PROOF OF LEMMA 8.1.
Step 0: two parameters. Put delta = b^{-1/10}, k = floor(s/2), and
j_* = s - k. Then k >= b^{0.69}/2 and j_* >= b^{0.69}/2, so both
stages get plenty of shifts.
STAGE 1: A GOOD FRACTION OF BASE POINTS IS GOOD
For the first k shifts define
A(x) = 2^{-k} sum_{eps in {0,1}^k}
g( x - sum_{i=1}^k eps_i w_i ).
Also, temporarily, let x itself be a uniformly random point of H,
independent of the shifts.
Step 1.1: the pairwise arguments are independent. For two DISTINCT bit
vectors eps and eps' in {0,1}^k, choose an index where they differ, say
index i. Condition on all shifts other than w_i. Then the two inputs to
g, namely x - sum eps_j w_j and x - sum eps'_j w_j, are sums that differ
only in the coefficient of w_i, with coefficients differing by +/-1.
The map (x, w_i) -> (the two inputs) is a bijection of H x H:
subtracting the two inputs determines w_i (up to sign), and then
determines x. So the two inputs are independent uniform in H. Nothing
about H's order is used. This holds in every finite abelian group.
Step 1.2: a variance identity. Because of Step 1.1, cross terms
average to gbar^2, and the diagonal contributes E g^2. So
E_{w_1..w_k, x} (A(x) - gbar)^2
= 2^{-k} ( E_x g(x)^2 - gbar^2 )
<= 2^{-k} E_x g(x)^2
<= 2^{-k} exp(2 b^{0.65}). (8.4)
The last inequality is (8.1): g <= exp(b^{0.65}), so g^2 <=
exp(2 b^{0.65}) pointwise.
Step 1.3: a controlled bad fraction. For fixed first-stage shifts, put
G = { x in H : A(x) >= (1 - delta) gbar },
beta = 1 - |G|/|H|.
Here beta is the FRACTION of base points on which A is bad. Chebyshev's
inequality, together with gbar >= 1/2 and (8.4), gives
E_{w_1..w_k} beta <= 4 b^{1/5} 2^{-k} exp(2 b^{0.65})
<= exp(-2 c_* s). (8.5)
The last bound is the only place the exponents line up. Its logarithm,
by increasing constants, is at most
log 8 + (1/5) log b + 2 b^{0.65} - (1/2) s log 2,
and because s >= b^{0.69} while b^{0.65} = o(b^{0.69}), the first three
terms are at most (1/4) s log 2 once b is large; the remaining amount
beats 2 c_* s. So for b beyond an absolute b_0, (8.5) holds, uniformly
in s in the allowed range.
Step 1.4: convert the average to a probability. Markov's inequality on
the nonnegative random variable beta gives
Prob { beta > exp(-c_* s) } <= exp(-c_* s). (8.6)
So with probability at least 1 - exp(-c_* s), the bad fraction beta of
base points is at most exp(-c_* s): almost every base point is good.
STAGE 2: UPGRADING "GOOD FRACTION" TO "GOOD EVERYWHERE"
Now fix the first-stage shifts, but only those for which beta <=
exp(-c_* s). That is the good event from (8.6). We use the remaining
shifts w_{k+1}, ..., w_s. There are j_* of them.
Step 2.1: a counting function. For 0 <= j <= j_*, define
N_j(x) = sum_{eta in {0,1}^j} ind_G( x - sum_{i=1}^j eta_i w_{k+i} ).
Here ind_G(y) is 1 if y is in G and 0 otherwise. Distinct bit vectors
eta are COUNTED WITH MULTIPLICITY, even if two of them produce the same
subset sum. This multiplicity convention is what makes the recursion
below exact.
For a fresh shift w = w_{k+j+1}, the recursion is
N_{j+1}(x) = N_j(x) + N_j(x - w). (8.7)
Step 2.2: an exponential potential. Fix theta = c_* s / 2 > 0, and let
Phi_j = E_{x in H} exp( - theta N_j(x) ).
Initially, N_0 = ind_G, so at every x, exp(-theta N_0(x)) is e^{-theta}
if x is in G, else 1. Thus
Phi_0 = beta + (1 - beta) e^{-theta}
<= e^{-2theta} + e^{-theta},
where we used beta <= exp(-c_* s) = e^{-2 theta} and 1 - beta <= 1.
Taking logs, log Phi_0 <= -theta + 1 for large s.
Step 2.3: the potential squares. Conditional on every shift chosen so
far, average over the fresh shift w = w_{k+j+1}:
E_w Phi_{j+1}
= E_{x, w} exp(-theta N_j(x)) exp(-theta N_j(x-w))
= Phi_j^2. (8.8)
The second equality uses the bijection (x, w) -> (x, x - w) of H x H.
Step 2.4: one bad step is rare. Conditional Markov's inequality applied
to (8.8) says
Prob( log Phi_{j+1} > 2 log Phi_j + theta delta | previous shifts )
<= e^{-theta delta}. (8.9)
There are j_* <= b steps. Union-bound all the bad steps: with
probability at least 1 - b e^{-theta delta} over all remaining shifts,
the recursion log Phi_{j+1} <= 2 log Phi_j + theta delta holds at every
step. Iterating that from log Phi_0 <= -theta + 1 gives
log Phi_j <= 2^j (-theta + 1) + (2^j - 1) theta delta. (8.10)
Step 2.5: uniform lower fraction of good labels. For EACH x, its single
summand in the potential Phi_j gives Phi_j >= |H|^{-1} e^{-theta N_j(x)}.
Combining with (8.10) and solving for N_j(x)/2^j,
N_{j_*}(x)/2^{j_*} >= 1 - delta - 1/theta
- log |H| / (theta 2^{j_*}). (8.11)
Since theta >= (c_*/2) b^{0.69}, 2^{j_*} is exponentially large in
b^{0.69}, and log |H| <= b^4, both correction terms are at most delta/2
once b_0 is large. So (8.11) says:
N_{j_*}(x)/2^{j_*} >= 1 - 2 delta, for EVERY x in H. (8.12)
Step 2.6: finish. The full Boolean average over ALL s shifts factors
2^{-s} sum_{eps in {0,1}^s} g(x - sum_{i=1}^s eps_i w_i)
= 2^{-j_*} sum_{eta in {0,1}^{j_*}}
A( x - sum_{i=1}^{j_*} eta_i w_{k+i} ).
On those eta labels counted by N_{j_*}(x), the corresponding summand
A(x - ...) is at least (1 - delta) gbar by the definition of G. All
other labels contribute a nonnegative amount. So (8.12) gives
2^{-s} sum_{eps} g(...) >= (1 - 2 delta)(1 - delta) gbar
>= (1 - 3 delta) gbar,
that is (8.3) with delta = b^{-1/10}. Stage 1's failure probability
was at most e^{-c_* s} <= e^{-c_* b^{0.69}}, and Stage 2's was at most
b e^{-theta delta} = b e^{-(c_*/2) b^{0.59}}. Summing these gives
(8.2). That proves Lemma 8.1.
REMARK 8.2 (uniformity and offsets). The reason we needed the
stronger "for every x" conclusion is that in later sections the base
point of one block is determined by choices made in OTHER blocks,
including random columns. A direct union bound over all of H would
require log|H| factors much smaller than b^4, which we cannot afford;
the second-stage potential sidesteps that by paying log|H| only once,
divided by the exponentially large 2^{j_*}. Once (8.3) holds, the base
point can then be replaced by ANY element of H, including an offset
determined by other random columns: the argument only used that
g >= 0, not that the base point was related to the shifts.
Concretely: suppose a subset S of {1,...,s} is chosen independently of
the values w_i, and its size |S| satisfies b^{0.69} <= |S| <= b. We may
condition on S, apply Lemma 8.1 to the columns with indices in S, and
afterwards insert arbitrary offsets built from the complementary
columns j not in S. This is exactly how the biased-bit mixture in the
next section is justified: the sets S of "fair" bits are chosen from a
distribution that depends on the block's target, but the actual column
values w_j are independent of S. This observation is what makes the
hierarchy quantifier "for every x in H" usable.
---------------------------------------------------------------------
9. FOLDED GAUSSIAN BLOCKS
---------------------------------------------------------------------
Now we build the objects that go into each block of the hierarchy.
The idea is to take a b-dimensional Gaussian and "fold" it onto the
unit cube [0,1]^b by summing, in each coordinate, the Gaussian weight
of nearby integer shifts. The result is a density on [0,1]^b. We then
put a fine grid on the cube and identify grid points with elements of
the finite field F_{p_b}. This turns the block into a finite abelian
group element where the Boolean sampler of section 8 can act.
The size of the grid prime p_b is chosen (Lemma 9.1 below) so that
the TYPICAL Gaussian weight of a grid point is neither too big nor too
small, just enough that the grid points sample the folded density
well. The eligible set E_b restricts to grid points whose folded weight
is close to typical AND whose coordinates are balanced in a certain
sense (each near 1/2 in at least b^{0.70} coordinates, which is
needed later to get enough fair bits).
Recall the standard Gaussian density gamma_1 and let log denote the
natural logarithm. Set
h_b = sqrt((9/4) log b),
f_b(t) = h_b gamma_1(h_b t) + h_b gamma_1(h_b (t - 1)), for 0<=t<=1,
F_b(t) = product_{j=1}^b f_b(t_j), for t in [0,1]^b.
The function f_b is the sum of two Gaussian bumps: one centered at 0,
one centered at 1. Roughly speaking, we are adding up the Gaussian
weight of the two integer corrections, 0 and 1, in each coordinate.
The total mass of f_b on [0,1] is
a_b = integral_0^1 f_b(t) dt = Prob( |X| <= h_b ),
with X a standard normal, because the second Gaussian bump contributes
exactly the probability that -h_b <= X <= 0. We record the log of a_b,
weighted by the density, as
mu_b = (1/a_b) integral_0^1 f_b(t) log f_b(t) dt.
The key point is that mu_b = log h_b + O(1). The b-fold product F_b
therefore has b-fold "typical log weight" b mu_b, which is of order
b log b. That is the number that fixes the grid prime p_b: we want the
prime to be roughly exp(b mu_b), so that the number of grid points
p_b^b matches the folded mass F_b around each typical point.
For a point t in [0,1]^b, the folded mass F_b(t) splits into the
Gaussian weight of each integer bit vector eps in {0,1}^b. Precisely,
define a product probability distribution P_{b,t} on {0,1}^b by
P_{b,t}(eps_j = e) = h_b gamma_1(h_b (t_j - e)) / f_b(t_j),
for e in {0,1}.
Then for EVERY eps in {0,1}^b, the following identity holds exactly:
h_b^b gamma_b( h_b (t - eps) ) = F_b(t) P_{b,t}(eps). (9.0)
Read it as: the Gaussian weight of the bit vector eps, near t, equals
the folded mass at t times the probability that P_{b,t} produces eps.
So the folded mass distributes over bit vectors exactly according to
P_{b,t}. This is why F_b and P_{b,t} always appear together.
The bit distribution P_{b,t} is "biased" when t_j is far from 1/2.
The odds of the two bits at coordinate j are
P_{b,t}(eps_j = 0) / P_{b,t}(eps_j = 1)
= exp( h_b^2 (1/2 - t_j) ). (9.0b)
So near t_j = 1/2, both values are nearly equally likely (a "fair"
bit); away from 1/2, one value dominates. In a set of b bits, only the
balanced coordinates (those with t_j near 1/2) give us fair bits to
feed into the sampler. Hence Lemma 9.1 requires at least b^{0.70}
balanced coordinates: that count becomes the "s" of the sampler.
Now comes the actual block. It is one long estimate: the grid prime
p_b exists, the eligible set has almost all the folded mass, the folded
mass does not change too fast across one grid cell, and every
individual bit vector is very light on the eligible set.
LEMMA 9.1 (folded Gaussian grid). For every sufficiently large integer
b there is a prime p_b with
b mu_b - 4 b^{0.56} <= log p_b <= b mu_b - 3 b^{0.56}. (9.1)
Let G_b = F_{p_b}^b, and for z in G_b let t_z = z/p_b in [0,1)^b
(using representatives 0,...,p_b - 1 in each coordinate). Define the
eligible set E_b subset of G_b by the two conditions
| log F_b(t_z) - b mu_b | <= b^{0.56}, and (9.2a)
#{ j : | t_{z,j} - 1/2 | <= h_b^{-2} } >= b^{0.70}. (9.2b)
Then
E_{z in G_b} F_b(t_z) = 1 + O(b^{-1/20}),
E_{z in G_b} F_b(t_z) ind_{E_b}(z) = 1 + O(b^{-1/20}). (9.2)
Moreover mu_b = log h_b + O(1). Put eta_b = b h_b^2 / p_b. If t lies
in the grid cell Q_z = t_z + [0, p_b^{-1})^b, then for every eps in
{0,1}^b,
e^{-eta_b} F_b(t_z) <= F_b(t) <= e^{eta_b} F_b(t_z), and
e^{-eta_b} (F_b(t_z)/p_b) P_{b,t_z}(eps)
<= (h_b^b/p_b) gamma_b( h_b (t - eps) )
<= e^{eta_b} (F_b(t_z)/p_b) P_{b,t_z}(eps). (9.3)
There is an absolute c > 0 such that, for every eligible z, every t in
Q_z, and every eps in {0,1}^b,
(F_b(t_z)/p_b) P_{b,t_z}(eps) <= e^{-c b^{0.70}}, and
(h_b^b/p_b) gamma_b( h_b (t - eps) ) <= e^{-c b^{0.70}}. (9.4)
In words: (9.1) picks the grid size. (9.2) says almost all folded grid
mass sits on eligible points, one with typical folded weight and many
balanced coordinates. (9.3) says folded weights and single-bit-vector
weights barely change across one grid cell. (9.4) says every individual
bit vector is exponentially light at an eligible point.
PROOF OF LEMMA 9.1, PART A: THE PRIME AND THE CONSTANT mu_b.
Step A1: mu_b = log h_b + O(1). Let X be a standard normal variable.
The map
X -> X/h_b if X >= 0,
X -> 1 + X/h_b if X < 0,
pushes the conditional law of X given |X| <= h_b onto the probability
density f_b/a_b on [0,1]. Consequently, at the resulting point t, one
of the two summands in f_b(t) equals exactly h_b gamma_1(X), while
f_b(t) <= 2 h_b/sqrt(2 pi) everywhere. Taking logs and expectation,
log h_b - (1/2) log(2 pi) - (1/2) E[X^2 | |X| <= h_b]
<= mu_b <= log h_b + log( 2/sqrt(2 pi) ).
The conditional second moment E[X^2 | |X| <= h_b] is at most an
absolute constant (it is at most 1, in fact), so mu_b = log h_b + O(1),
as claimed.
Step A2: f_b is bounded below. A nearest-endpoint summand gives
f_b(t) >= h_b (2 pi)^{-1/2} exp(-h_b^2/8) for all t in [0,1],
because at least one of t and t - 1 has absolute value at most 1/2 and
h_b (1/2) <= h_b/2, so the exponent is at least -h_b^2/8. Combined
with the upper bound in Step A1, log f_b takes values in an interval of
length O(1 + h_b^2).
Step A3: the total mass. The Gaussian tail estimate (Section 6) gives
1 - a_b = Prob(|X| > h_b) <= C h_b^{-1} e^{-h_b^2/2}
= C h_b^{-1} b^{-9/8}, (9.5)
since h_b^2/2 = (9/8) log b. Therefore
integral_{[0,1]^b} F_b = a_b^b = 1 - O(b^{-1/8}).
Step A4: a prime of the right size. We avoid any quantitative prime-gap
input; the factorial trick is elementary and self-contained. Since
mu_b >= log h_b - C -> infinity, the number T = b mu_b - 3 b^{0.56} is
positive for large b. Put l = floor(e^T / 2).
Take any prime q. Legendre's formula for the power of q in the binomial
coefficient gives
v_q( C(2l, l) )
= sum_{k>=1} ( floor(2l/q^k) - 2 floor(l/q^k) )
<= floor( log_q(2l) ),
because each summand is at most 1 and vanishes for q^k > 2l. Hence the
power of any prime in C(2l,l) is at most 2l.
Now suppose all prime divisors of C(2l,l) were at most l/log(2l).
There would be at most l/log(2l) of them, each with valuation at most
2l, so
log C(2l, l) <= (l/log(2l)) * log(2l) = l.
But C(2l, l) >= 4^l/(2l+1) > e^l for large l, a contradiction. So some
prime divisor p_b of C(2l,l) exceeds l/log(2l), and being a divisor of a
number with all prime powers <= 2l, it is at most 2l. Hence
l/log(2l) < p_b <= 2l,
which gives T - O(log T) <= log p_b <= T. Since mu_b = O(log log b)
(from Step A1 and h_b = sqrt((9/4) log b)), we have log T = O(log b)
= o(b^{0.56}). Therefore
b mu_b - 4 b^{0.56} <= log p_b <= b mu_b - 3 b^{0.56}
for large b, which is (9.1). In particular p_b grows faster than every
fixed power of b, so 1/eta_b = p_b/(b h_b^2) also grows faster than every
fixed power of b (recall eta_b = b h_b^2 / p_b and h_b^2 = O(log b)).
That completes Part A.
PROOF OF LEMMA 9.1, PART B: MASS, ROUNDING, AND ATOM.
Step B1: the folded mass concentrates (continuous version). Consider
the continuous cube [0,1]^b with probability density F_b/a_b^b. Its
coordinates are independent, and log F_b = sum_j log f_b(t_j) has mean
b mu_b. By Step A2, log f_b takes values in an interval of length
O(1 + h_b^2) = O(log b), so
Var(log F_b) <= C b (log b)^2.
Applying Chebyshev at half the tolerance in (9.2a),
Prob( | log F_b - b mu_b | > (1/2) b^{0.56} )
<= C b^{-0.12} (log b)^2 = O(b^{-1/20}), (9.6)
because 2(0.56) - 1 = 0.12.
Step B2: the balanced-coordinate condition holds with high probability.
For ONE coordinate, on the interval | t - 1/2 | <= (2 h_b^2)^{-1} we
have f_b(t) >= c h_b exp(-h_b^2/8) with an absolute c > 0. Under the
law f_b/a_b its probability is therefore at least c h_b^{-1} e^{-h_b^2/8}
divided by a_b, and using (9.5) that is at least c' h_b^{-1} b^{-9/8}
for an absolute c' > 0. Let N be the number of coordinates (out of b)
falling in this interval. Then N is binomial with
E N >= c' h_b^{-1} b^{23/32} >= 2 b^{0.70}
once b is large, because 23/32 > 0.70 leaves room. Its variance is at
most its mean, so Chebyshev's inequality gives
Prob( N < b^{0.70} ) <= 4 / E N
<= C h_b b^{-23/32} = O(b^{-1/20}). (9.7)
The interval in (9.2b) is |t - 1/2| <= h_b^{-2}, which is TWICE the
half-width used above; so satisfying the condition on the narrower
interval implies satisfying (9.2b). Steps B1 and B2 together show: a
set of continuous F_b-mass 1 - O(b^{-1/20}) satisfies (9.2a) with half
its tolerance and (9.2b) with half its interval width.
Step B3: rounding to the grid, and (9.3). For e in {0,1} and u in
[0,1],
| (d/du) log( h_b gamma_1(h_b (u - e)) ) |
= h_b^2 |u - e| <= h_b^2.
The same bound holds for |(log f_b)'|, since its derivative is a
weighted average of these two logarithmic derivatives (both summands
nonnegative). Integrating along each coordinate of a grid cell shows
that when t and t' lie in the SAME cell (so |t_j - t'_j| < 1/p_b in
every coordinate),
| log F_b(t) - log F_b(t') | <= sum_j h_b^2 |t_j - t'_j|
<= b h_b^2 / p_b = eta_b.
This is the first inequality in (9.3). For the second inequality in
(9.3), apply (9.0) at the anchor t_z and (9.3)-first inequality at the
generic point t: the factor P_{b,t_z}(eps) is bounded by the folded
ratio, giving the displayed sandwich. This proves (9.3).
Step B4: rounding preserves eligibility. Rounding a continuous point
down to t_z changes log F_b by at most eta_b and each coordinate by
less than 1/p_b. Since eta_b < (1/2) b^{0.56} and 1/p_b < (2 h_b^2)^{-1}
for large b, the stricter continuous event from Step B1/B2 rounds INTO
the eligible set E_b. Summing (9.3)-first inequality over all cells
gives
e^{-eta_b} E_z F_b(t_z) <= integral_{[0,1]^b} F_b <= e^{eta_b} E_z F_b(t_z).
Combining with Step A3 (total mass a_b^b = 1 - O(b^{-1/8})) gives the
first line of (9.2). Applying the same comparison restricted to cells
whose anchors lie in E_b gives a lower bound on E_z F_b(t_z) ind_{E_b}(z);
an upper bound is just the full grid mass. Together with Step A3, this
gives the second line of (9.2), with error O(b^{-1/8}) + O(b^{-1/20}) =
O(b^{-1/20}). That proves (9.2).
Step B5: the atom bound (9.4). By (9.0b), the odds of a coordinate bit
at t are exp(h_b^2 (1/2 - t_j)). On a balanced coordinate at an
eligible anchor, each of the two bit values has probability at least
alpha = (1 + e)^{-1} > 0 (because |t_j - 1/2| <= h_b^{-2} forces the
odds to be at most e). Since at least b^{0.70} coordinates are balanced
at an eligible anchor, every bit vector eps has probability
P_{b,t_z}(eps) <= (1 - alpha)^{b^{0.70}}.
On the other hand, Equations (9.1) and (9.2a) give
F_b(t_z)/p_b <= exp(5 b^{0.56}). Since 0.56 < 0.70, the product
(F_b(t_z)/p_b) P_{b,t_z}(eps)
<= exp(5 b^{0.56} - c' b^{0.70}) <= exp(-c b^{0.70})
for an absolute c > 0 and b sufficiently large (take c = c'/2). This is
the first inequality in (9.4). The second inequality in (9.4) follows
by (9.3)-second inequality applied at any t in Q_z. That completes the
proof of Lemma 9.1.
Before going on, here is a short account of why these particular
decimal exponents were chosen. They are not optimal; they only need to
satisfy a chain of strict inequalities:
1/2 < 0.56,
0.56 / 0.9 < 0.65 < 0.69 < 0.70 < 23/32.
Read the chain from left to right. 0.56 > 1/2 makes the information
window in (9.2a) exceed the square-root fluctuation of log F_b (from
Step B1). 0.56/0.9 < 0.65 makes the weight cap of the PREVIOUS block
fit the sampler hypothesis (8.1) of the NEXT block, once we set
b_next = b^{0.9} (see section 10). 0.65 < 0.69 < 0.70 leaves room
between the weight cap, the number of "fair" bits, and the number of
balanced coordinates; each is used in a different inequality. Finally
0.70 < 23/32 is the numerical slack used in Step B2, and the strictness
of 2(0.70) > 1 is what lets the atom bound (9.4) at the FIRST block
outrun the logarithmic loss that appears in section 12 when we dilate
by 1 + 1/n.
Now the second block lemma. Its task is the following.
(1) On the group G_b = F_{p_b}^b of grid points, the block should
behave as a "weight function" g_b whose mean is close to 1. Its
values must be tiny at a large set of usable anchors, and it must
sample a target function g_0 on the PREVIOUS block (whose grid
group is H) uniformly in the base point of H.
(2) The line C_b inside F_{p_b}^b allows us to select at most ONE
eligible point per coset, so the resulting weight function has no
big "clumps". Only one point per line coset means the individual
atoms remain light while the total mass sits close to 1.
Lemma 9.2 does both. Its hypothesis g_0 is the previous block's weight;
its conclusion encodes the "sampler" property (9.8) and the "line max"
property (9.9).
Recall: E_b is the eligible set of Lemma 9.1, t_z = z/p_b, and
P_{b,t_z} is the biased-bit distribution.
LEMMA 9.2 (usable anchors). There are absolute constants A, B > 0 with
the following property. Let b >= B be an integer and use the objects of
Lemma 9.1. Suppose H is a finite abelian group with log |H| <= b^4, and
g_0 : H -> [0, infinity) satisfies
(1/2) <= gbar_0 := E_{x in H} g_0(x) <= 2, and
g_0(x) <= exp(5 a^{0.56}) for all x in H,
for some 1 <= a <= b^{1/0.9}. (The parameter a is the size of the
PREVIOUS block. See section 10 for why this bound arises.)
Then one can choose shifts w_1,...,w_b in H, a usable set U_b subset of
E_b, and a one-dimensional linear subspace C_b of G_b, such that,
writing W eps = sum_{j=1}^b eps_j w_j,
sum_{eps in {0,1}^b} P_{b,t_z}(eps) g_0( x - W eps )
>= (1 - A b^{-1/100}) gbar_0, for all z in U_b, x in H. (9.8)
Define
v_b(z) = (F_b(t_z)/p_b) ind_{U_b}(z),
g_b(x) = max_{c in C_b} v_b(x - c),
gbar_b = E_{x in G_b} g_b(x).
These choices satisfy
| gbar_b - 1 | <= A b^{-1/100},
0 <= g_b(x) <= exp(5 b^{0.56}) for all x in G_b, (9.9)
| E_z F_b(t_z) ind_{U_b}(z) - 1 | <= A b^{-1/20}.
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 in (9.9) about g_b hold.
The two properties (9.8) and (9.9) are the whole content. (9.8) is the
biased-bit sampler: at every usable anchor z and every base point x in
H, the average of g_0 over biased bits recovers the mean gbar_0 up to a
loss of order b^{-1/100}. That is the mechanism by which one block
samples the previous one. (9.9) says the block itself has mean close to
1, is bounded by exp(5 b^{0.56}) (so it can be the INPUT of the NEXT
block), and reduces to nearly all of E_b.
PROOF OF LEMMA 9.2.
PART 1: THE BIASED-BIT SAMPLER (9.8)
Step 1.1: the cap of g_0 is small enough. The hypothesis a <= b^{1/0.9}
gives, for large b,
5 a^{0.56} <= 5 b^{0.56/0.9} <= b^{0.65},
because 0.56/0.9 < 0.65. So g_0 satisfies the cap hypothesis (8.1) of
Lemma 8.1 with this b. This is exactly where the chain of exponents is
used.
Step 1.2: a fair/biased mixture for each bit. Fix an eligible anchor z
and consider the biased bits P_{b,t_z}. A bit with 1-probability q has
the exact mixture representation: with probability 2 min(q,1-q) use a
FAIR bit (1/2 each), and otherwise use its MORE LIKELY value
deterministically. These choices are made independently at each of the
b coordinates. Write S subset of {1,...,b} for the coordinates where a
fair bit was chosen, and d_j for the deterministic value at j not in S.
Conditional on the choices (S, d), the resulting eps in {0,1}^b has fair
independent bits on S and fixed values d_j elsewhere. Averaging the
conditional laws over all (S,d) reproduces P_{b,t_z} exactly. So:
P_{b,t_z} = E_{S,d} [ Uniform law on
{ eps : eps_j = d_j for j not in S, eps_j free for j in S } ].
Step 1.3: enough fair bits. On a balanced coordinate, both bits have
probability at least alpha = (1+e)^{-1}. So each balanced coordinate is
chosen into S with probability at least 2 alpha. Since the anchor z is
eligible, there are at least b^{0.70} balanced coordinates (9.2b). Let
K be the number of these balanced coordinates that are chosen into S.
Then K is binomial with mean at least 2 alpha b^{0.70} and variance at
most its mean. Chebyshev's inequality, using that b^{0.69} is at most
HALF the mean for large b, gives
Prob( K < b^{0.69} ) <= 4 / (2 alpha b^{0.70})
= O(b^{-0.70}) = O(b^{-1/2}). (9.10)
Step 1.4: apply the sampler to the selected columns. Fix any realization
of S with b^{0.69} <= |S| <= b. This is exactly the range for the
parameter s of Lemma 8.1. The columns w_j for j in S are independent
uniform in H (because all columns are chosen independently before S; see
Remark 8.2). By Lemma 8.1, applied to those columns, with failure
probability at most b^{-1/2} over w restricted to S,
2^{-|S|} sum_{eps in {0,1}^S}
g_0( y - sum_{j in S} eps_j w_j )
>= (1 - C b^{-1/10}) gbar_0, for all y in H. (9.11)
The conclusion is simultaneous in y. So we may plug in
y = x - sum_{j notin S} d_j w_j: the offset comes from the OTHER columns,
which are irrelevant inside Lemma 8.1's argument, but which we insert
afterwards (Remark 8.2).
Step 1.5: a good set U_b. Let q_W(z) be the mixture probability (over
S,d for the fixed anchor z and the fixed W) that EITHER |S| < b^{0.69}
OR the uniform sampler conclusion (9.11) fails for the selected columns.
Combining (9.10) with Lemma 8.1 first gives E_W q_W(z) <= C b^{-1/2}
for each eligible z. Then averaging the weighted mass over z in E_b:
E_W E_z F_b(t_z) ind_{E_b}(z) q_W(z)
<= C b^{-1/2} E_z F_b(t_z) ind_{E_b}(z)
<= C' b^{-1/2}.
The last inequality uses (9.2), which says the weighted grid mass on
E_b is 1 + O(b^{-1/20}) <= 2. So there is at least one W with the inner
expectation <= C' b^{-1/2}; fix that W. Then define
U_b = { z in E_b : q_W(z) <= b^{-1/20} }.
Weighted Markov's inequality gives the explicit discarded mass
E_z F_b(t_z) ind_{E_b \ U_b}(z)
<= C' b^{-1/2 + 1/20} = C' b^{-9/20}. (9.12)
Together with (9.2), this proves the third assertion in (9.9):
E_z F_b(t_z) ind_{U_b}(z) = 1 + O(b^{-1/20}).
Step 1.6: prove (9.8). At every z in U_b and every x in H, average the
uniform sampler conclusion (9.11) over the successful mixture components
(the (S,d) with |S| >= b^{0.69} and the sampler conclusion), and use
NONNEGATIVITY of g_0 on the unsuccessful ones. That yields
sum_eps P_{b,t_z}(eps) g_0(x - W eps)
>= (1 - b^{-1/20})(1 - C b^{-1/10}) gbar_0
>= (1 - A b^{-1/100}) gbar_0,
by choosing A large and using that the two loss terms add up to
something bounded by A b^{-1/100} (both exponents, 1/20 and 1/10, are
strictly larger than 1/100). That is (9.8).
PART 2: THE LINE, AND (9.9)
This part chooses C_b. The following argument works both for the U_b
just constructed, and (in the base version) with U_b = E_b.
Step 2.1: two auxiliaries. Put
M = E_z F_b(t_z) ind_{U_b}(z) = 1 + O(b^{-1/20}), and
d = |U_b| / p_b^b.
The lower eligible weight gives
d <= M exp(-b mu_b + b^{0.56}) <= 2 exp(-b mu_b + b^{0.56}). (9.13)
Indeed, every z in U_b has F_b(t_z) >= exp(b mu_b - b^{0.56}) by (9.2a),
and a lower bound on the average F_b ind_{U_b} forces a bound on the
FRACTION d.
Step 2.2: a random line collides rarely. Choose a one-dimensional linear
subspace C of G_b uniformly at random (equivalently, choose a random
nonzero vector and take its F_{p_b}-span). For any fixed nonzero u in
G_b,
Prob_C( u in C ) = (p_b - 1) / (p_b^b - 1),
the fraction of nonzero vectors in G_b that lie on a given 1-D subspace.
Consequently, for every z in U_b, the event C_C(z) that "z + C meets
U_b in a point OTHER than z" has probability (in C)
Prob_C( C_C(z) ) <= (|U_b| - 1) (p_b - 1)/(p_b^b - 1)
<= 2 p_b d <= 4 exp(-2 b^{0.56}). (9.14)
Here (|U_b| - 1)/(p_b^b - 1) counts the other points u of U_b - z, each
lying in C with the given probability. The last step uses (9.13) and
2 p_b exp(-b mu_b + b^{0.56}) = 2 exp(b^{0.56} + log p_b - b mu_b)
<= 2 exp(b^{0.56} - 3 b^{0.56}) = 2 exp(-2 b^{0.56}) by (9.1).
Step 2.3: a loss bound for the line maximum. Fix a line C. Put
S_C(x) = sum_{c in C} v_b(x - c),
g_C(x) = max_{c in C} v_b(x - c).
The normalization in the definition of v_b, together with Fubini over the
torus R^m/G_b and the fact that |C| = p_b translates, gives
E_{x in G_b} S_C(x) = p_b E_{z in G_b} v_b(z) = M. (9.15)
If the coset x - C contains at most one usable anchor, then S_C(x) and
g_C(x) agree, because the sum has at most one nonzero term. Otherwise,
charge S_C - g_C to all usable weights in that coset whose anchors
collide: for each such c, the point x - c is in C_C (as a point of U_b
that has another usable neighbor on C). Summing:
0 <= S_C(x) - g_C(x)
<= sum_{c in C} v_b(x - c) ind_{C_C}(x - c). (9.16)
This is pointwise and holds for every x. Averaging first over x and then
over C and using Fubini again,
E_C E_x ( S_C(x) - g_C(x) )
<= E_C [ p_b E_z v_b(z) ind_{C_C}(z) ]
= E_z F_b(t_z) ind_{U_b}(z) Prob_C( C_C(z) )
<= 4 M exp(-2 b^{0.56}). (9.17)
The p_b factor from E_x S_C is canceled by the p_b factor in v_b having
mass p_b^{-1} P_{b,t_z}, so the estimate loses only a hopelessly small
fraction of the weighted mass. The key point: a random line loses no
more than a factor exp(-2 b^{0.56}) of the weighted mass on average.
Step 2.4: choose a good line. Since the average loss is bounded by
4 M exp(-2 b^{0.56}), some line C_b satisfies
M - 4 M exp(-2 b^{0.56}) <= E_x g_{C_b}(x) = gbar_b <= M.
This proves the first assertion in (9.9):
| gbar_b - 1 | <= | M - 1 | + 4 M exp(-2 b^{0.56})
<= A b^{-1/100},
after enlarging A.
Step 2.5: the cap in (9.9). Every usable anchor lies in E_b, so by
(9.1) and (9.2a),
v_b(z) = F_b(t_z)/p_b <= exp(5 b^{0.56}).
The same bound holds for any coset maximum of v_b, because a maximum is
one of the values. This is the second assertion in (9.9).
Step 2.6: both versions. The argument of Parts 1-2 applies with U_b as
constructed (the biased case) and with U_b = E_b (the base case); the
only difference is whether (9.8) is asserted. Enlarging the absolute
constants A, B one last time absorbs all the O(.) in the estimates.
This completes Lemma 9.2.
REMARK 9.3 (why g_b can vanish). The function g_b need not have a
positive lower bound at every point of G_b. Many cosets of C_b can
contain no usable anchor at all, and there g_b is exactly zero. This
is not an oversight: their total weighted mass is tiny, because
Lemma 9.2 has already shown that the usable set carries almost all of
the weighted mass (third line of (9.9)). What g_b does have is:
(i) mean close to 1: | gbar_b - 1 | <= A b^{-1/100};
(ii) a pointwise cap: 0 <= g_b <= exp(5 b^{0.56}).
Both (i) and (ii) are exactly the hypotheses that will feed Lemma 9.2
at the NEXT (smaller) block. The fact that g_b vanishes on most
points will be recovered by (9.8): at the next stage, the biased bits
average g_b over a whole Boolean cube and see its mean gbar_b, not its
pointwise values. This distinction between "mean close to 1" and
"positive everywhere" is essential when blocks are assembled in
section 10; it is exactly why we must propagate the MEAN.
The last piece of section 9 is a bookkeeping lemma. It converts an
element x of the finite group G_b into a genuine lattice point in
R^b, plus a residual in a grid cell, so that Gaussian weights in real
space become the folded weights F_b we have been working with.
Recall from Lemma 9.1: p_b, t_z = z/p_b, F_b, the eligible set E_b,
the usable set U_b, the line C_b, the weight function g_b, and
eta_b = b h_b^2 / p_b.
LEMMA 9.4 (from a coset to a Gaussian cell). Let
L_b = Z^b + C_b/p_b in R^b. For t in R^b put k = floor(p_b t) in Z^b
and x = k mod p_b in G_b (the reduction of each coordinate of k modulo
p_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 (using standard representatives in each coordinate).
Then
lambda = (k - z)/p_b lies in L_b,
tau = t - lambda = ( z + {p_b t} )/p_b lies in Q_z,
g_b(x) = F_b(t_z)/p_b, (9.18)
with {p_b t} the coordinatewise fractional part. For every eps in
{0,1}^b:
lambda + eps lies in L_b,
the residual t - lambda - eps = tau - eps has all coordinates in
[-1, 1], and
(h_b^b / p_b) gamma_b( h_b ( t - lambda - eps ) )
>= e^{-eta_b} g_b(x) P_{b,t_z}(eps). (9.19)
The corresponding individual weight is at most e^{-c b^{0.70}} for the
absolute c of (9.4).
In words: after picking the anchor z that attains the line maximum
g_b(x), the point x - z / p_b lies in the lattice L_b, and it drags t
into the grid cell Q_z. The Gaussian weight of any nearby lattice
point lambda + eps is a small multiple of g_b(x) P_{b,t_z}(eps); that
is what lets us feed the biased-bit sampler directly into the covering
argument of section 12.
PROOF OF LEMMA 9.4.
Step 1: lambda is a lattice point. By construction x = k mod p_b and
z = x - c, so k - z is congruent to c modulo p_b, coordinatewise. That
is exactly the statement that lambda = (k - z)/p_b lies in
Z^b + C_b/p_b = L_b.
Step 2: the residual lies in the right cell. Recall x = k mod p_b and
z = x - c, where c is the chosen maximizing element of C_b. Then
tau = t - lambda = (p_b t - k + z)/p_b = ( z + {p_b t} )/p_b.
The vector z has integer coordinates in {0,...,p_b-1}, and {p_b t} has
all coordinates in [0,1). So each coordinate of tau lies in
[t_{z,j}, t_{z,j} + 1/p_b). That is tau in Q_z.
Step 3: the identity g_b(x) = F_b(t_z)/p_b. By definition g_b(x) is the
maximum over c in C_b of v_b(x - c). The maximizing c is our chosen one,
so g_b(x) = v_b(z) = F_b(t_z)/p_b, the third line of (9.18).
Step 4: residual coordinates in [-1,1]. Since tau in [0,1)^b, for eps in
{0,1}^b we have tau_j - eps_j in (-1, 1]. That is the stated bound, and
it means the Gaussian factor gamma_b(h_b(tau - eps)) is a genuine
(untruncated) Gaussian weight, not a far tail.
Step 5: the lower weight bound (9.19). Combining the folded identity
(9.0) at t_z with the rounding bound (9.3),
(h_b^b / p_b) gamma_b( h_b (t - lambda - eps) )
= (h_b^b / p_b) gamma_b( h_b (tau - eps) )
>= e^{-eta_b} (F_b(t_z)/p_b) P_{b,t_z}(eps)
= e^{-eta_b} g_b(x) P_{b,t_z}(eps).
That is (9.19).
Step 6: the atom bound. The right-hand side of (9.4), applied with
t = tau in Q_z and with the same eps, gives
(h_b^b/p_b) gamma_b(h_b(tau - eps)) <= e^{-c b^{0.70}}. That is the
last assertion of Lemma 9.4. QED.
This closes section 9. One last check that the hypotheses fit the
hierarchy. In section 10 the "previous group" will be H = G_a with
a <= b^{1/0.9}. Its size satisfies log|G_a| = a log p_a, and by (9.1),
log p_a = O(a log a), so
log |G_a| = O(a^2 log log a)
<= O( b^{2/0.9} log log b ) <= b^4
for sufficiently large b, since 2/0.9 < 4 leaves slack. The cap
comparison 5 a^{0.56} <= b^{0.65} was checked in Step 1.1 of Lemma 9.2.
Both bounds have strict exponent margins, so the SAME absolute cutoff
B works at every level of the hierarchy, no matter how many blocks there
are.
---------------------------------------------------------------------
10. THE BRANCHING HIERARCHY
---------------------------------------------------------------------
The block lemmas of section 9 concern ONE block. To prove a covering
theorem we must stack many blocks, each one smaller than the last,
until they hit a fixed absolute size. The block sizes go down
geometrically, so the sum of their weights stays controlled, and the
logarithmic dimension n log n is the toll we pay.
Two features of the arrangement matter.
(i) WE ASSEMBLE FROM LARGE TO SMALL. The largest block is fixed
first, with no input from an earlier block (the base case of
Lemma 9.2). Each subsequent, smaller block is chosen by applying
Lemma 9.2 to the function g already fixed in the block just above.
(ii) FOR A GIVEN TARGET, THE BRANCHES ARE SELECTED FROM SMALL TO
LARGE. When we later pick lattice points for a specific target y,
we start at the terminal (smallest) block and work upwards,
choosing earlier blocks conditional on the suffix already chosen.
That is why the sampler must be uniform in the base point.
10.1 Block sizes and the vertical data.
Fix a sufficiently large absolute integer B, whose requirements are
specified below. Starting from an integer b_1 >= B, form a finite
list by
b_{i+1} = ceil( b_i^{0.9} )
whenever this number is at least B, and otherwise stop. Let r be the
last index. Increasing B ensures that
b_{i+1} <= (1/2) b_i,
B <= b_r < B^{1/0.9},
sum_{i=1}^r b_i <= 2 b_1. (10.1)
Use the notation of section 9 at size b_i: h_i = h_{b_i}, p_i = p_{b_i},
G_i = F_{p_i}^{b_i}, F_i = F_{b_i}, P_{i,t} = P_{b_i,t}. Anchors are
t_z = z/p_i in [0,1)^{b_i}.
Apply Lemma 9.2 successively. In the first block there is no preceding
function, so we take its BASE version, which supplies U_1 = E_1, C_1,
and g_1. In each subsequent block we apply Lemma 9.2 to the function
g_{i-1} on G_{i-1}. Its hypotheses hold for sufficiently large B: with
b = b_i, we have b_{i-1} <= b^{1/0.9} and
5 b_{i-1}^{0.56} <= b^{0.65},
log|G_{i-1}| = b_{i-1} log p_{i-1}
= O( b_{i-1}^2 log b_{i-1} ) <= b^4.
The first inequality uses 0.56/0.9 < 0.65, and the second has the slack
2/0.9 < 4. The means fall into [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 F_{p_i}. The
block functions are
g_i(x) = max_{c in C_i} (F_i(t_{x-c})/p_i) ind_{U_i}(x - c),
gbar_i = E_{x in G_i} g_i(x), (10.2)
| gbar_i - 1 | <= A b_i^{-1/100},
0 <= g_i <= exp(5 b_i^{0.56}), (10.2b)
with A absolute. Moreover, every z in U_i with i > 1 satisfies the
SAMPLER CHAIN:
sum_{eps in {0,1}^{b_i}} P_{i,t_z}(eps) g_{i-1}( x - W_{i-1} eps )
>= (1 - A b_i^{-1/100}) gbar_{i-1}, for all x in G_{i-1}.
(10.3)
Read (10.3) as: the biased bits of block i, summed with weights g_{i-1},
recover the MEAN of block i-1, uniformly in the base point x. Combined
with |gbar_{i-1} - 1| small, the recovery is nearly exact. All constants
in (10.2)-(10.3) are independent of the number of blocks.
10.2 The raw lattices and the vertical map.
For 1 <= i <= r, define the raw coordinate lattice
L_i = Z^{b_i} + p_i^{-1} C_i, (10.4)
the union of the integer translates of (representatives of) C_i divided
by p_i; this is independent of the representatives. It is a lattice of
determinant p_i^{-1}. Indeed, choose a generator c of C_i with its jth
coordinate equal to 1. The vectors c/p_i and e_k (k != j) are a basis:
they generate e_j = p_i (c/p_i) - sum_{k != 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
T = b_{r+1} = b_r ceil(log_2 p_r), h_{r+1} = 1, L_{r+1} = Z^T.
Its size is bounded by a constant depending only on the fixed cutoff B.
The associated matrix W_r, of size b_r by T, uses the columns
2^k e_j mod p_r, for 1 <= j <= b_r and 0 <= k < ceil(log_2 p_r). Its
column sums exhaust every group element:
{ W_r eps : eps in {0,1}^T } = G_r. (10.5)
Use standard integer representatives of every W_i, and put
A_i = p_i^{-1} W_i (1 <= i <= r),
L = product_{i=1}^{r+1} L_i,
D = sum_{i=1}^{r+1} b_i.
Every entry of A_i lies in [0,1) and is an integer multiple of 1/p_i.
Block raw coordinates are written ell = (ell_1, ..., ell_{r+1}). Define
the invertible block upper triangular map M by
(M ell)_i = h_i ( ell_i + A_i ell_{i+1} ) (i <= r),
(M ell)_{r+1} = ell_{r+1}. (10.6)
Then Lambda_v = M L is a single full-rank lattice, with
D_v = det Lambda_v = product_{i=1}^r ( h_i^{b_i} / p_i ). (10.7)
The fractional off-diagonal entries do not change this: M is one
invertible linear map applied to the product lattice L, and an invertible
linear map multiplies the determinant by its determinant.
10.3 The weighted vertical patterns.
This is the central structure produced by sections 8-9 and assembled
here. For each vertical target y in R^D, the hierarchy produces a
finite nonempty set of raw lattice points ell (a "pattern") whose
residuals are small in every block and whose total Gaussian weight is
at least a fixed absolute constant. That fixed total weight is what
will later supply enough horizontal load. At the same time, EVERY
individual point is extremely light, which keeps each raw slice small
enough for the common-lattice lemma.
PROPOSITION 10.1 (weighted vertical patterns). There are absolute
constants B, C, c, kappa > 0 such that, for every integer b_1 >= B, the
construction above has
D <= C (b_1 + 1),
R^2 = sum_{i=1}^{r+1} b_i h_i^2 <= C ( b_1 log(b_1+1) + 1 ). (10.8)
For every y in R^D there is a finite nonempty pattern P_y subset of L
such that
| (y - M ell)_i |_infinity <= h_i
for every ell in P_y and every 1 <= i <= r+1, (10.9a)
sum_{ell in P_y} D_v gamma_D( y - M ell ) >= kappa, (10.9b)
max_{ell in P_y} D_v gamma_D( y - M ell )
<= exp( -c b_1^{0.70} ). (10.9c)
The terminal block is CONSTANT on the pattern. For each ordinary
block i and each fixed suffix (ell_{i+1}, ..., ell_{r+1}), its retained
values ell_i belong to lambda_i + {0,1}^{b_i} for one lattice point
lambda_i in L_i depending on that suffix. In particular,
|P_y| <= 2^D.
Order the scalar coordinates by increasing block index, and write them
ell[1], ..., ell[D]. Conditional on any fixed scalar suffix
ell[j+1], ..., ell[D], the possible next values ell[j] are at most two;
if there are two, they differ by 1 (the sibling separation). 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 fixed finite alphabets:
ell_i in ( p_i^{-1} Z intersect [-Q_raw, Q_raw] )^{b_i} (i <= r),
ell_{r+1} in ( Z intersect [-Q_raw, Q_raw] )^T,
Q_raw = 1 + (D+2)^D. (10.10)
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 drops the second
term. All implicit constants are absolute.
In words: (i) residuals are small in the h_i scale; (ii) total weight
>= kappa > 0; (iii) each individual atom is <= exp(-c b_1^{0.70}), tiny;
(iv) the pattern is binary by suffixes with sibling gap exactly 1.
Properties (ii) and (iii) are complementary: the total supplies
horizontal load, while the atom bound keeps each slice within reach of
the mean-hole estimate. Property (iv) is exactly the shape the shear
lemma of section 11 accepts.
PROOF OF PROPOSITION 10.1.
The size and radius bounds in (10.8) follow from (10.1), the formula
h_i^2 = (9/4) log b_i, and the absolute bound on the terminal block
size T. (T <= b_r ceil(log_2 p_r), and b_r, log p_r are bounded by
constants once B is fixed.) We prove the weight estimates by induction
on the number of ordinary blocks, allowing the intermediate pattern to
be empty.
PART 1: THE INDUCTION ON TRUNCATED PATTERNS.
Step 1.1: truncate. Keep only the ordinary blocks 1,...,i, dropping the
interaction of block i with its successor. Write M^{[i]} for this
truncated map, d_i = sum_{j<=i} b_j, and
D_v^{[i]} = product_{j<=i} h_j^{b_j}/p_j. We claim: for every
y = (y_1,...,y_i) in R^{d_i} there is a (possibly empty) pattern
P^{[i]}_y of raw points in product_{j<=i} L_j with total weight at
least
sum_{ell in P^{[i]}_y} D_v^{[i]} gamma_{d_i}( y - M^{[i]} ell )
>= a_i g_i(x_i),
where x_i = floor( p_i y_i / h_i ) mod p_i, (10.11)
and
a_i >= product_{j=1}^i ( 1 - C_0 b_j^{-1/100} ) (10.12)
for an absolute C_0. The residual and block-branching properties of
the proposition are part of this induction. Empty patterns are allowed
precisely when g_i(x_i) = 0.
Fix the lexicographic order on standard representatives of each finite
group; when a maximum has ties, choose the least maximizing anchor.
Step 1.2: base case i = 1. If g_1(x_1) = 0, take the empty pattern and
(10.11) is trivial. Otherwise, pick a usable anchor z in x_1 - C_1
attaining the maximum in (10.2), so g_1(x_1) = F_1(t_z)/p_1. By
Lemma 9.4 there is lambda_1 in L_1 such that t = y_1/h_1 - lambda_1
lies in t_z + [0, 1/p_1)^{b_1}. Consider all choices
ell_1 = lambda_1 + eps for eps in {0,1}^{b_1}. Their individual block
weights satisfy, by (9.19) with delta_1 in place of eta_1,
(h_1^{b_1}/p_1) gamma_{b_1}( h_1 (t - eps) )
>= e^{-delta_1} (F_1(t_z)/p_1) P_{1,t_z}(eps)
= e^{-delta_1} g_1(x_1) P_{1,t_z}(eps). (10.13)
Since each coordinate of t lies in [0,1), the residual
t - lambda_1 - eps has absolute value at most h_1 (this is the
residual bound (10.9a), with h_1). Summing (10.13) over all eps in
{0,1}^{b_1} and using that P_{1,t_z} sums to 1, the total weight is at
least e^{-delta_1} g_1(x_1). So (10.11) holds at i = 1 with
a_1 = e^{-delta_1}. Since delta_1 = b_1 h_1^2/p_1 = o(b_1^{-anything}),
taking C_0 large gives a_1 >= 1 - C_0 b_1^{-1/100} for large b_1, i.e.
(10.12) at i = 1.
Step 1.3: induction step i > 1. Assume block i has g_i(x_i) > 0;
otherwise take the empty pattern. Choose the least maximizing usable
anchor z in x_i - C_i, so g_i(x_i) = F_i(t_z)/p_i. By Lemma 9.4 there
is lambda_i in L_i with t = y_i/h_i - lambda_i in t_z + [0,1/p_i)^{b_i}.
For each bit choice eps in {0,1}^{b_i}, let ell_i = lambda_i + eps, and
attach a preceding-truncated pattern from block i-1. The point is that
the interaction with block i shifts the target for block i-1. Concretely,
put the MODIFIED TARGET
y~_{i-1}
= y_{i-1} - h_{i-1} A_{i-1} (lambda_i + eps),
and use induction with (~y_{i-1}) for the first i-1 blocks, leaving the
earlier blocks of the target unchanged. This is allowed even if the
resulting preceding pattern is empty.
Step 1.4: the resulting grid shift is exactly what (10.3) needs. The
new preceding grid index is
x
= floor( p_{i-1} y_{i-1}/h_{i-1} - W_{i-1} lambda_i )
mod p_{i-1}. (10.14)
Indeed, W_{i-1} eps is an INTEGER vector, so translating by it commutes
with the coordinatewise floor. But W_{i-1} lambda_i need not be an
integer, so we FIX it in (10.14) before varying eps. This is the reason
x does not depend on eps: only the integer part moves with eps. No
compatibility between adjacent primes p_{i-1} and p_i is required.
Step 1.5: disjointness and total weight. Patterns attached to different
bit vectors eps have different last blocks (they differ in ell_i), so
they are disjoint as raw points in product_{j<=i} L_j. Multiplying
their weights by (10.13)-analogue (with i replacing 1) and summing over
eps:
sum over attached points
>= a_{i-1} e^{-delta_i} g_i(x_i)
* sum_{eps in {0,1}^{b_i}} P_{i,t_z}(eps) g_{i-1}(x - W_{i-1} eps),
where delta_i = b_i h_i^2 / p_i and the factor g_i(x_i) =
F_i(t_z)/p_i. By the sampler chain (10.3),
sum_eps P_{i,t_z}(eps) g_{i-1}(x - W_{i-1} eps)
>= (1 - A b_i^{-1/100}) gbar_{i-1}.
So the total weight is at least
a_{i-1} e^{-delta_i} (1 - A b_i^{-1/100}) gbar_{i-1} g_i(x_i). Take
a_i = a_{i-1} e^{-delta_i} (1 - A b_i^{-1/100}) gbar_{i-1}
>= a_{i-1} e^{-delta_i}
* (1 - A b_i^{-1/100}) (1 - A b_{i-1}^{-1/100}),
using the mean bound |gbar_{i-1} - 1| <= A b_{i-1}^{-1/100} from
(10.2b). Since delta_i decays faster than any fixed negative power of
b_i, and b_{i-1} >= b_i, increasing one absolute constant C_0 bounds the
new multiplier below by 1 - C_0 b_i^{-1/100}, proving (10.12) at i. This
step uses the WEIGHTED SUM over all bits, never a choice of a single
successful bit.
PART 2: LOSSLESS PRODUCTS, TERMINAL BLOCK, ATOMS, BRANCHING, ALPHABETS.
Step 2.1: summable losses. Set a = 1/100. Equation (10.1) gives the
explicit bound
sum_{j=1}^r b_j^{-a}
<= b_r^{-a} sum_{k=0}^{r-1} 2^{-ak}
<= B^{-a} / (1 - 2^{-a}). (10.15)
Choose B so that C_0 B^{-a} <= 1/2. Using log(1 - u) >= -2u for
0 <= u <= 1/2, the product in (10.12) is bounded below by the positive
absolute constant
a_* = exp( -2 C_0 B^{-a} / (1 - 2^{-a}) ). (10.16)
This lower bound is independent of the number of blocks r and of b_1.
It is the first ingredient of the constant kappa.
Step 2.2: the terminal correction. For the full target y, choose a
terminal raw point of the form
ell_{r+1} = floor(y_{r+1}) + eps, eps in {0,1}^T.
After accounting for its integer part floor(y_{r+1}), varying eps shifts
the last ordinary grid index by -W_r eps. By (10.5) the achievable
shifts cover all of G_r, so we can place that grid index at any point of
G_r where g_r is large. Since gbar_r >= 1/2 (by (10.2)), some point has
g_r >= 1/2. Fix that terminal choice.
Apply the truncated induction (10.11) to the first r blocks, with this
fixed terminal contribution subtracted from y_r. Every coordinate of the
terminal residual y_{r+1} - M ell_{r+1} lies within absolute value at
most 1, so its Gaussian factor is at least
gamma_T( y_{r+1} - ell_{r+1} ) >= (2 pi e)^{-T/2},
(the worst case is each coordinate equal to +/-1, giving exp(-1/2) per
coordinate). If T_*(B) is an upper bound for all possible terminal
dimensions T (which is absolute once B is fixed), the resulting full
pattern has total weight at least
kappa := (1/2) a_* (2 pi e)^{-T_*(B)/2} > 0. (10.17)
The cutoff B is now fixed, so kappa is absolute. This proves (10.9b),
and, taking the pattern from a point where g_r >= 1/2, also nonemptiness.
Step 2.3: individual weights, (10.9c). Every retained point comes from a
usable anchor in every ordinary block. By the atom bound (9.4),
followed by the upper rounding estimate in (9.3),
(h_i^{b_i}/p_i) gamma_{b_i}( h_i (t - eps) )
<= e^{delta_i} exp( -c_0 b_i^{0.70} )
<= exp( -c b_i^{0.70} )
after increasing B and decreasing the absolute c > 0. The terminal
Gaussian factor is at most (2 pi)^{-T/2} <= 1. Multiplying over all
blocks, and noting that exp(-c b_i^{0.70}) <= exp(-c b_1^{0.70})
because b_i <= b_1, gives (10.9c).
Step 2.4: the branching property. 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 the Boolean translate lambda_i + {0,1}^{b_i}. Distinct
branches give distinct raw lattice points. As a result, once a scalar
suffix is fixed, the next scalar coordinate can only be the
corresponding coordinate of lambda_i or that coordinate plus one. The
RULE is: at a fixed scalar suffix, the next scalar value has at most two
choices, and they differ by exactly 1. Deleting any subset of the
pattern cannot destroy this assertion. This proves the sibling
separation and the |P_y| <= 2^D bound, completing the "binary by
suffixes" description.
Step 2.5: finite alphabets. Finally suppose y = M z with z in [0,1)^D.
Put e_i = z_i - ell_i, so that M ell - y = M e. Equation (10.9a) and the
entry bounds on A_i (each entry lies in [0,1)) give the backward
recursion
|| e_{r+1} ||_infinity <= 1,
|| e_i ||_infinity <= 1 + b_{i+1} || e_{i+1} ||_infinity
<= 1 + D || e_{i+1} ||_infinity.
Iterating backwards bounds every coordinate of ell by
1 + (D+2)^D. Also L_i subset p_i^{-1} Z^{b_i} and the terminal lattice
L_{r+1} = Z^T is integral. These two facts give (10.10). Each ordinary
scalar alphabet has at most 2 Q_raw p_i + 1 elements, and log p_i =
O(b_i log b_i), giving its asserted logarithmic size. All implicit
constants are absolute. This completes the proof of Proposition 10.1.
For the covering construction we will take
b_1 = ceil( (log log n)^2 ) once n is sufficiently large. Proposition
10.1 then has D = O((log log n)^2 + 1), and both D and R satisfy the
polynomial bounds required by Lemma 7.1.
---------------------------------------------------------------------
11. ONE SHEAR, AND EXACT COVERAGE
---------------------------------------------------------------------
Here is where the single-lattice requirement becomes delicate. So far
we have a horizontal lattice Lambda_h and, for each vertical target y,
a batch of retained raw points ell. Each contributes a horizontal slice
K_{y - M ell}; the horizontal lattice covers almost all of each slice,
leaving a hole set U_a of tiny measure. If the slices were placed at
INDEPENDENT horizontal offsets, their hole sets would overlap only in
measure (tiny)^(number of slices): exponentially small. But the slices
are NOT independent: their horizontal offsets are governed by ONE
vertical lattice Lambda_v = M L, i.e. by a single linear map.
We need a fact that lets ONE linear choice (the "shear") make the hole
sets line up "as if independent" for all target patterns at once. This
is the content of Lemma 11.1. The statement is a finite version of the
classical simultaneous Boolean-shift argument of Li and Liu, extended
to families of patterns whose branch bases may depend on LATER
coordinates. All that is actually used of a pattern's structure is the
unit separation between siblings.
The reason multiples cosets make life easy is now clear: with k
independent cosets, you can choose k independent shifts by hand. With
one lattice, the vertical offsets of different slices are forced to be
linear multiples of a single matrix M, and Lemma 11.1 must extract the
needed independence from the freedom in the coefficients Z_j.
11.1 The simultaneous shear for finitely many patterns.
Let us fix a little vocabulary.
DEFINITION 11.1. A LABELED PATTERN in R^q is a finite nonempty set of
points, with one label attached to each point. It is BINARY BY SUFFIXES
if, after fixing any suffix of coordinates, the next coordinate takes
at most two possible values, and any two such values differ by 1.
For q = 0 a pattern is a single label. Any binary-by-suffixes pattern in
R^q has at most 2^q points. Deleting points preserves the rule (give the
remaining points their original labels); if nothing remains, the
"pattern" is empty and is not used. Taking a nonempty slice at the last
coordinate and then dropping that coordinate also preserves the rule.
This is exactly the shape produced by Proposition 10.1: the possible
values at any scalar suffix split into at most two branches differing by
1.
A picture would help here. Think of a rooted tree: the root is the
pattern, its children are the two slices at the last coordinate, each
of those has two children at the second-to-last coordinate, and so on.
At each level the two children of a node correspond to two values that
differ by 1. The pairs "(a, a+1)" at sibling nodes need not be related
between branches. This is exactly what the inductively-built patterns of
Proposition 10.1 look like.
Now the shear lemma. Recall: T = R^m / Lambda_h is the horizontal torus,
pi_Lambda_h is the projection, |A| denotes normalized Haar measure on T.
LEMMA 11.1 (simultaneous shear). Let T = R^m / Lambda_h, and let
U_a subset of T be measurable sets with |U_a| <= eta_a for some eta_a > 0.
For 0 <= q <= D, let P_q be finite families of labeled patterns in R^q,
binary by suffixes. Suppose the families are CLOSED UNDER
LAST-COORDINATE SLICING. Write
Q = sum_{q=0}^D |P_q|, L_* > max(1, Q).
Then there are real vectors Z_1, ..., Z_D in R^m such that, for every
pattern P in P_q,
| intersection_{l in P}
( U_{a(l)} + pi_Lambda_h( sum_{j=1}^q l[j] Z_j ) ) |
<= L_*^{|P| - 1} prod_{l in P} eta_{a(l)}. (11.1)
Here a(l) is the label of the point l, |P| is its cardinality, and l[j]
is the jth scalar coordinate of l.
In words. The next sections will feed Lemma 11.1 the following data.
For each vertical target y and each retained raw point ell in P_y, we
have a slice index a(l) = a(ell). The set U_a is the hole set of slice
J_a on the horizontal torus. The offset sum_{j} l[j] Z_j is a common
horizontal "shear": it moves all slice hole sets by amounts designed to
look independent. If the intersections were independent, their measure
would be the product of the eta's. Lemma 11.1 gives this up to a
polynomial factor L_*^{|P|-1}. Since |P| <= 2^D and log L_* is small
compared with n log n once we set up the problem properly, this factor
is absorbed in the final n log n density.
PROOF OF LEMMA 11.1.
Induction on q. The statement is empty for q = 0 patterns with one
point each: the left side of (11.1) is |U_a| <= eta_a, the right side
is eta_a. That is the base case; note it holds for EVERY set U_a with
|U_a| <= eta_a, with no choice made.
Step 1: suppose Z_1, ..., Z_{q-1} are already fixed so that (11.1)
holds for every pattern in P_0, ..., P_{q-1}. We must choose Z_q in R^m
so that it works simultaneously for every pattern in P_q.
Step 2: patterns with a single last-coordinate value. If every point of
P in P_q has the same last coordinate v, then
U_{a(l)} + pi( sum_{j<=q-1} l[j] Z_j + v Z_q )
= ( U_{a(l)} + pi( sum_{j<=q-1} l[j] Z_j ) ) + pi(v Z_q)
is a COMMON translation of the corresponding set at level q-1. Since
Haar measure is translation invariant, the bound (11.1) for P at level
q follows from its bound at level q-1, no matter what Z_q is. Such
patterns never constrain Z_q.
Step 3: patterns with two last-coordinate values. Otherwise the two
last-coordinate values are v and v+1 (unit separation). Let the two
slices be P_v and P_{v+1} of cardinalities k_1, k_2, and let A, B be
their intersection sets:
A = intersection_{l in P_v}
( U_{a(l)} + pi( sum_{j<=q-1} l[j] Z_j ) ),
B = intersection_{l in P_{v+1}}
( U_{a(l)} + pi( sum_{j<=q-1} l[j] Z_j ) ).
The full intersection in (11.1) is
A + pi(v Z_q) intersect B + pi((v+1) Z_q).
Choose Z_q uniformly in a fixed fundamental parallelepiped of
Lambda_h (any fundamental domain of R^m / Lambda_h will do). Translation
invariance reduces this to a single relative shift: the intersection has
the same measure as
A intersect ( B + pi( Z_q ) ),
because translating both A and B by pi(v Z_q) leaves their intersection
unchanged. This identity is valid even when v is not an integer: the
products v Z_q, (v+1) Z_q are formed in R^m before projecting to the
torus.
Step 4: average the relative shift. By Fubini on the torus,
E_{Z_q} | A intersect ( B + pi(Z_q) ) |
= |A| * |B|.
Indeed, translate B by a Haar-random torus point: the expected overlap
with any fixed A is |A| |B|.
Step 5: bound the average by the product we want. By induction (applied
to P_v and P_{v+1}, which belong to P_{q-1} by the slicing hypothesis),
|A| <= L_*^{k_1 - 1} prod_{l in P_v} eta_{a(l)},
|B| <= L_*^{k_2 - 1} prod_{l in P_{v+1}} eta_{a(l)}.
Multiplying,
E_{Z_q} | A intersect ( B + pi(Z_q) ) |
<= L_*^{k_1 + k_2 - 2} prod_{l in P} eta_{a(l)}.
Compare this to the target bound L_*^{k_1 + k_2 - 1} prod_{l} eta_{a(l)}.
The average is smaller by a factor L_*.
Step 6: control the failure probability. Markov's inequality: since the
integrand is nonnegative and has the average above, the probability
that the integrand exceeds L_* times its average is at most 1/L_*. In
other words, the probability that Z_q VIOLATES (11.1) for this particular
pattern P is at most 1/L_*.
A degenerate case needs one line. If |A| = 0 or |B| = 0, the intersection
is empty almost surely, so the bound holds with probability one; that is
certainly consistent with the above.
Step 7: union bound over P_q. There are |P_q| patterns in P_q. By the
union bound, the total probability that any pattern in P_q violates
(11.1) is at most |P_q| / L_*. Since L_* > Q >= |P_q|, this is strictly
less than 1. So with positive probability, one choice of Z_q works for
EVERY pattern in P_q at once. Fix such a Z_q.
Step 8: induction. Iterating over q from 1 to D, we construct
Z_1, ..., Z_D simultaneously satisfying (11.1) for every pattern in every
P_q. That completes the induction and proves Lemma 11.1. QED.
A remark on what was essential. The proof uses only two properties of
patterns: each last-coordinate slice is again a pattern (so induction
applies), and the two possible last coordinates differ by 1 (so that the
difference is a single Z_q, not a pattern-dependent multiple). The base
values of the branches at different nodes are never compared. This is
exactly why Proposition 10.1 takes the trouble to prove the
binary-by-suffixes property.
11.2 Removing the last hole: a small dilation.
After the shear, the intersection of the hole sets is already
exponentially small, but not necessarily empty. There is a classical
trick from Rogers (1959) that removes a small residual hole by a tiny
dilation of K. The version we use is the small-dilation form quoted by
Fejes Toth (2009); we prove it in the single-lattice setting, since that
is all we need.
LEMMA 11.2 (completion). Let K subset of R^n be a convex body and Gamma
a full-rank lattice. If the hole proportion delta = 1 - |pi_Gamma(K)|
satisfies
delta < (1 - delta) k^{-n} (11.2)
for a positive integer k, then (1 + 1/k) K + Gamma = R^n.
Notice the two inequalities that make (11.2) work. On the right, k^{-n}
is much smaller than 1. On the left, delta must be very small to begin
with. The precise form ensures that the SMALLER the hole, the LESS
dilation is needed. As such, a virtually-covered body needs almost no
dilation to be fully covered.
PROOF OF LEMMA 11.2.
Step 1: measure the image under multiplication by k. On the torus
T = R^n / Gamma, consider the map [x] -> [k x]. This map pushes the
measure of the set pi_Gamma(K/k) (the image of the scaled-in body
K/k = { x/k : x in K }) onto pi_Gamma(K): [x] in pi_Gamma(K/k)
if and only if k x in K + Gamma, i.e. [k x] in pi_Gamma(K).
Step 2: bound how much measure can be concentrated. The map [x] -> [k x]
is k^n-to-1 in an averaged sense. Partition a fundamental parallelepiped
of Gamma into k^n small translates of size 1/k in each direction, on
each of which [x] -> [k x] is injective. So the map is at most k^n-to-1
on that partition, and
|pi_Gamma(K)| <= k^n |pi_Gamma(K/k)|.
Rearranging and using delta = 1 - |pi_Gamma(K)|:
|pi_Gamma(K/k)| >= k^{-n} (1 - delta) > delta = 1 - |pi_Gamma(K)|,
where the strict inequality is the hypothesis (11.2).
Step 3: conclude the covering. For every torus point [x], the two sets
pi_Gamma(K) and [x] - pi_Gamma(K/k) have measures summing to more than
1: |pi_Gamma(K)| + |pi_Gamma(K/k)| > |pi_Gamma(K)| + (1 - |pi_Gamma(K)|)
= 1. Two measurable subsets of a probability space whose measures sum
to more than 1 must intersect. Hence [x] belongs to
pi_Gamma(K) + pi_Gamma(K/k), i.e. x is in K + (K/k) + Gamma. Since this
holds for every x,
K + (K/k) + Gamma = R^n.
Step 4: convexity identifies the sum. For a convex body containing no
symmetry requirement and no interior condition beyond nonempty
interior, the classical identity
K + (1/k) K = (1 + 1/k) K
holds by convexity: every (1-t)u + tv with u, v in K is in K, and each
point of (1+1/k)K arises as u + w/k with u, w in K. Combining with
Step 3,
(1 + 1/k) K + Gamma = R^n.
That completes Lemma 11.2. QED.
Remark. In the covering argument of section 12, the hole delta will be
at most n^{-2n}, and we will take k = n. Then k^{-n} = n^{-n}, and
n^{-2n} < (1 - n^{-2n}) n^{-n} holds for n >= 2. So (11.2) is satisfied
with huge room to spare, and the dilation 1 + 1/n costs only a constant
factor in density: (1 + 1/n)^n <= e.
---------------------------------------------------------------------
12. ASSEMBLING THE MAIN THEOREM
---------------------------------------------------------------------
We now put everything together in ten steps. First fix the vertical
hierarchy (Step 1); build a finite list of horizontal slices (Step 2);
choose horizontal covolume and match loads (Steps 3-4); get one
common horizontal lattice (Step 6); fix one shear (Step 7); build the
covering lattice Gamma with tiny holes (Steps 8-9); and finally apply
completion plus affine/small-dimension reductions (Steps 9-10).
PROOF OF THEOREM (main).
Step 1: fix the vertical data. All constants in the vertical
construction, including its overall cutoff B, are chosen FIRST.
For sufficiently large n, let s = log log n and use Proposition 10.1
with b_1 = ceil(s^2). Keep the notation of that proposition:
L, M, D, D_v, b_i, h_i as constructed.
Set
R^2 = sum_{i=1}^{r+1} b_i h_i^2, m = n - D.
By Proposition 10.1, D = O(s^2 + 1) and R is bounded by a fixed
polynomial in s. The vertical lattice Lambda_v = M L and covolume D_v
are already fixed as well.
Step 2: horizontal slices. After passing to the affine coordinates of
Lemma 7.1, there are at most (C m^2)^D horizontal bodies J_a in R^m
such that every v with ||v|| <= R has a label a satisfying
J_a is contained in K_v, and
c_sec vol_n(K) gamma_D(v) <= vol_m(J_a)
<= C_sec vol_n(K) gamma_D(v). (12.1)
The number (C m^2)^D is exactly the list size of Lemma 7.1, and the
"for every ||v|| <= R" covers all residuals produced by the vertical
patterns (each residual has ||v||_infinity <= h_i <= R).
Step 3: horizontal covolume and horizontal load. Choose an absolute
constant C_* LATER (it will be taken huge; see step 7), and put
rho = C_* n log n,
D_h = vol_n(K) / (rho D_v),
u_a = vol_m(J_a) / D_h. (12.2a)
Step 4: match loads to Gaussian weights. Fix any vertical target y, use
its pattern P_y from Proposition 10.1, and label each raw point ell in
P_y by a body contained in the section at y - M ell (this is allowed
because the residual || y - M ell || <= R puts y - M ell inside the
range where (12.1) applies). With the chosen horizontal covolume, the
normalized section volume is comparable to the corresponding normalized
Gaussian weight multiplied by rho:
(c_sec/cmp) rho D_v gamma_D(y - M ell)
<= u_{a(ell)}
<= (C_sec/cmp) rho D_v gamma_D(y - M ell). (12.2b)
Here cmp is a benign absolute comparability constant from (12.1)
combining c_sec and C_sec, and the m-dimensional volumes are matched to
D_v gamma_D via the definition of D_h in (12.2a). The two load
inequalities follow:
sum_{ell in P_y} u_{a(ell)} >= c_3 rho, (12.2c)
max_{ell in P_y} u_{a(ell)} <= U_n := C rho exp(-c b_1^{0.70}),
(12.2d)
where c_3 > 0 is an absolute constant (proportional to kappa c_sec / D_v
with kappa from Proposition 10.1) and C is another absolute constant.
Equation (12.2c) is the SUM OF LOADS along a pattern (must be large);
(12.2d) is the MAXIMUM LOAD of any individual term (must be small).
Step 5: three scale comparisons. We need (12.2c)-(12.2d) to fit the
criteria of Lemma 7.2. There are three inequalities, all of the form
"small is small". First the load cap:
U_n / m
<= C exp( s - c' s^{1.4} ) -> 0, (12.3)
where we used b_1^{0.70} ~ s^{1.4} and rho/m = O(n log n / n) = O(log n).
The terms on the left decouple because s = log log n and s^{1.4} >
s once n is large. Second, every pattern has at most 2^D points, so
deleting those with u_{a(ell)} < sqrt(m) loses at most
2^D sqrt(m) = n^{1/2 + o(1)} = o(rho). (12.4)
Third, the logarithm of the number of labels is O(D log m) = o(sqrt m),
because D = O(s^2) and sqrt m ~ sqrt n. These three 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 (after discarding light
labels) is nonempty and has load at least c_3 rho / 2 for large n.
Step 6: horizontal lattice from Lemma 7.2. Restrict the label list to
those a with sqrt(m) <= u_a <= U_n. By (12.3)-(12.4) this still leaves
enough mass. A direct application of Lemma 7.2 (with the "for
sufficiently large m" form (7.8)) gives one lattice Lambda_h of
covolume D_h whose hole sets
U_a = ( R^m / Lambda_h ) \ pi_{Lambda_h}(J_a)
satisfy |U_a| <= e^{-u_a/2} simultaneously for all retained labels.
Thus the horizontal lattice has covered all listed slices up to tiny
holes.
Step 7: one shear for every target. We must choose ONE linear shear
(the vectors Z_1, ..., Z_D of Lemma 11.1) that works for every vertical
target at once, not for each target separately.
First reduce the target set. It suffices to handle y = M z with
z in [0,1)^D. This is because L contains Z^D, so after the final lattice
Gamma is built, any other y can be reduced to this region by an integer
raw translation, which is itself an element of the lattice Gamma; and
the horizontal leftover is a translation of the section on its torus.
We return to this reduction at the very end of Step 9.
By the finite-alphabet conclusion (10.10) of Proposition 10.1, when
y = M z with z in [0,1)^D, every raw scalar coordinate lies in a fixed
finite set. Precisely, an ordinary block scalar ell_i,j lies in
p_i^{-1} Z intersect [-Q_raw, Q_raw], and the terminal scalar lies in
Z intersect [-Q_raw, Q_raw], with
Q_raw = 1 + (D+2)^D.
So the logarithm of the alphabet size of any scalar coordinate is at
most
O( D log(D+2) + max_i log p_i ) = O( s^{c_0} )
for some fixed absolute exponent c_0, using log p_i = O(b_i log b_i) and
b_1 = ceil(s^2).
Now define the finite families. Order scalar coordinates by increasing
block index. For each 0 <= q <= D, let P_q be ALL labeled patterns on
the first q coordinate alphabets that are binary by suffixes. This
includes every retained full pattern: by Proposition 10.1, a branch base
in one block depends only on LATER blocks, and deleting points cannot
introduce a third value at any suffix. The families are closed under
slicing.
Bounds on the family sizes. Let A_j be the alphabet of scalar
coordinate j, and N_lab the number of retained section labels (from
Step 6, after discarding the light and heavy labels). A labeled point
consists of a coordinate tuple together with such a label. So
N = N_lab * prod_{j=1}^D |A_j| bounds the number of labeled points in
each coordinate space. Then
log( N + 1 ) = O( D log n + s^{c_1} ), and
Q := sum_{q=0}^D |P_q| <= (D+1) (N+1)^{2^D}, (12.4b)
for some fixed absolute exponent c_1. The last line follows by encoding
a set of at most 2^D points as a list of that length, padded with a
dummy symbol. Take
L_* = 2 (Q + 1), (recall Lemma 11.1 requires L_* > max(1,Q)).
Then
2^D log L_*
<= C 4^D ( D log n + s^{c_1} ) + C 2^D log(D+2)
= o( n log n ). (12.5)
Indeed 4^D times any fixed polynomial in s is exp(O(s^2)) = o(n), since
s = log log n.
Step 8: the covering lattice. Apply Lemma 11.1 with
eta_a = e^{-u_a/2} (the hole measure bound from Step 6) and set
Z l := sum_{j=1}^D l[j] Z_j. Define
Gamma = { ( h + Z l, M l ) : h in Lambda_h, l in L }. (12.6)
This is a full-rank lattice: it is the image of the product lattice
Lambda_h x L under an invertible block triangular linear map. Its
covolume is exactly D_h D_v, so
vol_n(K)/det Gamma = rho.
Step 9: bound the hole proportion. Fix y and a retained labeled
pattern. Each J_{a(ell)} lies in the section K_{y - M ell}. The
uncovered horizontal points, viewed on the torus T = R^m/Lambda_h,
lie in
intersection_{ell in P_y}
( U_{a(ell)} + pi_{Lambda_h}( Z ell ) ).
For y in M [0,1)^D, Lemma 11.1 and the retained load (12.2c) give the
uniform bound
( horizontal hole fraction at y )
<= exp( 2^D log L_* - c_3 rho / 4 ). (12.7)
For other y, reduce M^{-1} y modulo Z^D and translate by the
corresponding point ( Z k, M k ) in Gamma. This only translates the
horizontal section on its torus, so the same bound holds.
Fubini over a fundamental domain. Let F_h, F_v be fundamental
parallelepipeds of Lambda_h and M L. Their product is a measurable
fundamental domain for Gamma: reduce the vertical coordinate using a
point ( Z l, M l ), then the horizontal one using Lambda_h. The union
K + Gamma is closed (translates of a compact set by a lattice are
locally finite), so its complement is measurable, and Fubini integrates
(12.7) over F_v. No measurable selection of auxiliary patterns is
needed. Equations (12.2a) and (12.5) then yield
delta := 1 - |pi_Gamma(K)|
<= exp( o(n log n) - (c_3 C_* / 4) n log n )
<= n^{-2n},
once C_* is a sufficiently large absolute constant, and then n is
sufficiently large. Since
n^{-2n} < (1 - n^{-2n}) n^{-n} for n >= 2,
Lemma 11.2 with k = n applies, so
(1 + 1/n) K + Gamma = R^n.
Thus
Lambda = (1 + 1/n)^{-1} Gamma
is a single covering lattice for K, of density
vol_n(K)/det Lambda = (1+1/n)^n rho <= e C_* n log n.
That proves the main theorem apart from affine invariance and the
finitely many remaining small dimensions, which are step 10 below.
Step 10: affine invariance and the remaining dimensions. Two facts
finish the proof.
(A) AFFINE INVARIANCE. Translating a body does not change the covering
property (translation preserves both K + Lambda = R^n and vol_n/det
ratios). Applying an invertible linear map T to both body and lattice
preserves the covering property and multiplies both vol_n(K) and
det(Lambda) by |det T|, so the density is unchanged. Hence the affine
normalizations used in Lemma 7.1 and in Lemma 11.2 can be undone: a
covering lattice for the transformed body produces one for the
original with the same density. All the estimates above were made in
these normalized coordinates; the conclusion transfers back.
(B) FINITELY MANY SMALL DIMENSIONS. The proof in Steps 1-9 was carried
out for n above an absolute threshold. There remains only a fixed
finite set of dimensions n = 2, 3, ..., n_0. In each, choose a
maximum-volume simplex with vertices in K; it exists by compactness,
and has positive volume since K has nonempty interior. Put its vertices
at 0, e_1, ..., e_n by an affine map. Replacing the jth nonzero vertex
e_j by any point x in K leaves the other vertices 0, e_k (k != j)
fixed, so the new simplex has determinant |x_j|. By maximality,
|x_j| <= 1 for every x in K and every j. So K is contained in
[-1, 1]^n. On the other side, the original simplex conv{0, e_1,...,e_n}
contains [0, 1/n]^n (every point with all coordinates in [0,1/n] has
coordinate sum at most 1, hence lies in the simplex), and this simplex
is contained in K. So
[0, 1/n]^n is contained in K is contained in [-1, 1]^n.
The lattice (1/n) Z^n tiles R^n by translates of the cube [0, 1/n]^n,
and hence covers R^n by translates of K. Its density is at most
vol_n(K) / det( (1/n) Z^n )
= vol_n(K) n^n <= 2^n n^n = (2n)^n.
The maximum of (2n)^n / (n log n) over the remaining finite set of
dimensions is an absolute constant, absorbable into C. So the main
theorem holds in the remaining dimensions too. That completes the
proof of Theorem (main).
A closing summary. The logical chain is: (EK) -> horizontal slices
(Lemma 7.1); folded Gaussian blocks (Lemma 9.1) plus usable anchors
(Lemma 9.2) -> branching hierarchy (Prop 10.1); (RS) -> one horizontal
lattice with tiny holes (Lemma 7.2); a simultaneous shear (Lemma 11.1)
makes hole sets overlap as if independent; and finally completion
(Lemma 11.2) plus dilation gives density O(n log n). The decimal
exponents (0.56, 0.65, 0.69, 0.70, 23/32) are chosen only for strict
inequalities, not optimality; the constant C is finite though large.
---------------------------------------------------------------------
13. REFERENCES
---------------------------------------------------------------------
[EK] Ronen Eldan and Bo'az Klartag,
Pointwise estimates for marginals of convex bodies,
Journal of Functional Analysis 254 (2008), no. 8, 2275-2293.
doi:10.1016/j.jfa.2007.08.014, arXiv:0708.2513v1.
[FT09] Gabor Fejes Toth,
A note on covering by convex bodies,
Canadian Mathematical Bulletin 52 (2009), no. 3, 361-365.
doi:10.4153/CMB-2009-039-x.
[LL] Heng Li and Xizhi Liu,
Nearly sharp bounds for lattice coverings by convex bodies,
preprint, version 2, 10 August 2026, arXiv:2607.28429v2.
[LLC] Heng Li and Xizhi Liu,
Two-stage binary correction for nearly linear lattice coverings,
unpolished manuscript, 2026 (author-hosted).
[ORW] Or Ordentlich, Oded Regev, and Barak Weiss,
New bounds on the density of lattice coverings,
Journal of the American Mathematical Society 35 (2022), no. 1,
295-308. doi:10.1090/jams/984, arXiv:2006.00340v1.
[Rog57] C. A. Rogers,
A note on coverings,
Mathematika 4 (1957), no. 1, 1-6.
doi:10.1112/S0025579300001030.
[Rog58] C. A. Rogers,
Lattice coverings of space: The Minkowski-Hlawka theorem,
Proceedings of the London Mathematical Society (3) 8 (1958),
447-465. doi:10.1112/plms/s3-8.3.447.
[Rog59] C. A. Rogers,
Lattice coverings of space,
Mathematika 6 (1959), no. 1, 33-39.
doi:10.1112/S002557930000190X.
[Sch58] Wolfgang M. Schmidt,
The measure of the set of admissible lattices,
Proceedings of the American Mathematical Society 9 (1958),
390-403. doi:10.2307/2032994.
---------------------------------------------------------------------
END OF DOCUMENT
---------------------------------------------------------------------