Proof. An affine transformation makes the uniform law on the given body isotropic: its covariance matrix is positive definite because the body has nonempty interior. The uniform density is log-concave. Put \(S=2DR+2\). Uniformly over the displayed range of \(D,R\), for sufficiently large \(n\) we have \[D\le n^\alpha,\qquad S<n^\beta, \qquad C_0n^{-\gamma}\le\tfrac12.\] Choose \(E\) from Equation (1) and use orthonormal coordinates \(E^\perp\times E\). Write \(K\) for the resulting body. By Fubini’s theorem, \(\operatorname{vol}_m(K_y)/\operatorname{vol}_n(K)\) is a version of the marginal density. The lower bound holds at every required height, independently of density versions: compactness implies that, as \(y'\to y\), the fiber \(K_{y'}\) is eventually contained in \(K_y+\varepsilon B_m\) for each \(\varepsilon>0\), where \(B_m\) is the unit ball. Continuity of volume under decreasing compact neighborhoods shows that \(y\mapsto\operatorname{vol}_m(K_y)\) is upper semicontinuous. Its almost-everywhere Gaussian lower bound therefore extends to every \(\|y\|\le S<n^\beta\) by approaching from the full-measure set. Consequently \[ \operatorname{vol}_m(K_y)\ge\tfrac12\operatorname{vol}_n(K)\gamma_D(y) \qquad (\|y\|\le S). \tag{3}\]

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

Let \(\{y_a\}\) be a maximal \(R/m^2\)-separated set in the closed ball of radius \(R\). It is an \(R/m^2\)-net. Comparing the disjoint balls of radius \(R/(2m^2)\) about its points with the ball of radius \(R+R/(2m^2)\) gives \[ \#\{y_a\}\le(1+2m^2)^D\le(3m^2)^D. \tag{4}\] If \(\|y-y_a\|\le R/m^2\), set \(z=y_a+m^2(y-y_a)\). Then \(\|z\|\le2R\) and \(y=(1-m^{-2})y_a+m^{-2}z\). Since \((0,z)\in K\), convexity yields \[ (1-m^{-2})K_{y_a}\subset K_y. \tag{5}\]

For \(m\ge2\), Bernoulli’s inequality gives \((1-m^{-2})^m\ge1-m^{-1}\ge1/2\). By Equation (3), the body \((1-m^{-2})K_{y_a}\) therefore has volume at least \(\tfrac14\operatorname{vol}_n(K)\gamma_D(y_a)\). It contains zero, so a further homothety about zero gives a convex body \(J_a\) contained in it with exactly \[ \operatorname{vol}_m(J_a)=\tfrac18\operatorname{vol}_n(K)\gamma_D(y_a). \tag{6}\] For a chosen nearby \(y_a\), \[\left|\log\frac{\gamma_D(y_a)}{\gamma_D(y)}\right| \le \frac{\|y_a-y\|(\|y_a\|+\|y\|)}2 \le R^2/m^2=o(1).\] Equations (5) and (6) prove Equation (2), and Equation (4) bounds the list size. All thresholds used above depend only on \(M\), not on the body. ◻

Proof. Replace every \(J_a\) by \(J'_a=D_h^{-1/m}J_a\), so that \(\operatorname{vol}_m(J'_a)=u_a\). Equation (7) gives \[\mathbb E_{\Lambda\sim\mu_m}h_{\Lambda}(J'_a) \le e^{-u_a}+C_{\mathrm R}e^{-\eta_m} \le(1+C_{\mathrm R})e^{-u_a}.\] Markov’s inequality bounds the probability that \(h_{\Lambda}(J'_a)>e^{-u_a/2}\) by \((1+C_{\mathrm R})e^{-u_a/2}\). The sum of these probabilities is less than one by Equation (8). Thus a single unimodular lattice \(\Lambda\) satisfies all the desired inequalities. Set \(\Lambda_h=D_h^{1/m}\Lambda\); scaling identifies the normalized tori, preserves the hole proportions, and gives determinant \(D_h\).

Finally, \(\eta_m/m\to\tfrac14\log(27/16)>0\), so \(\max_a u_a=o(m)\) ensures the first condition in Equation (8). The other two numerical bounds give \[(1+C_{\mathrm R})\sum_{a=1}^N e^{-u_a/2} \le(1+C_{\mathrm R})\exp\{\log N-\tfrac12\sqrt m\}=o(1),\] which ensures the second. ◻

Proof. First, if \(X\) is a standard normal random variable, then \(a_b=\mathbb P(|X|\le h_b)\). The map \[X\longmapsto \begin{cases} X/h_b,&X\ge0,\\ 1+X/h_b,&X<0 \end{cases}\] pushes its conditional law on \([-h_b,h_b]\) to the probability density \(f_b/a_b\) on \([0,1]\). At the resulting point \(t\), one summand in \(f_b(t)\) equals \(h_b\gamma_1(X)\), whereas \(f_b(t)\le2h_b/\sqrt{2\pi}\) everywhere. Consequently \[\log h_b-\frac12\log(2\pi) -\frac12\mathbb E[X^2\mid |X|\le h_b] \le\mu_b\le\log h_b+\log\frac2{\sqrt{2\pi}}.\] The conditional second moment is bounded by an absolute constant, proving \(\mu_b=\log h_b+O(1)\). The elementary Gaussian tail estimate also gives \[ 1-a_b\le C h_b^{-1}e^{-h_b^2/2} =C h_b^{-1}b^{-9/8},\qquad \int_{[0,1]^b}F_b(t)\,dt=a_b^b=1-O(b^{-1/8}). \tag{24}\]

Here is an elementary way to choose the prime, avoiding any quantitative prime-gap input. Since \(\mu_b\ge\log h_b-C\to\infty\), \(T=b\mu_b-3b^{0.56}\) is positive for large \(b\). Set \(l=\lfloor e^T/2\rfloor\). For a prime \(q\), the factorial valuation formula gives \[v_q\binom{2l}{l} =\sum_{k\ge1}\left(\left\lfloor\frac{2l}{q^k}\right\rfloor -2\left\lfloor\frac l{q^k}\right\rfloor\right) \le\lfloor\log_q(2l)\rfloor.\] Thus the power of each prime in the binomial coefficient is at most \(2l\). If all its prime divisors were at most \(l/\log(2l)\), their number would be at most \(l/\log(2l)\), and hence \(\log\binom{2l}{l}\le l\). This contradicts \(\binom{2l}{l}\ge4^l/(2l+1)>e^l\) for large \(l\). There is therefore a prime divisor \(p_b\) with \[\frac l{\log(2l)}<p_b\le2l.\] It follows that \(T-O(\log T)\le\log p_b\le T\). Since \(\mu_b=O(\log\log b)\), we have \(\log T=O(\log b)=o(b^{0.56})\); this proves Equation (19). In particular \(p_b\) grows faster than every fixed power of \(b\), and so does \(1/\eta_b\).

To prove the mass assertions, first work in the continuous cube with probability density \(F_b/a_b^b\). Its coordinates are independent, and \(\log F_b\) has mean \(b\mu_b\). The function \(\log f_b\) takes values in an interval of length \(O(1+h_b^2)\): the upper bound was given above, and a nearest-endpoint summand gives \(f_b(t)\ge h_b(2\pi)^{-1/2}e^{-h_b^2/8}\). Consequently \[\operatorname{Var}(\log F_b)\le Cb(\log b)^2, \qquad \mathbb P\left(\left|\log F_b-b\mu_b\right|> \frac12b^{0.56}\right) \le C b^{-0.12}(\log b)^2=O(b^{-1/20}).\] For one coordinate, on the interval \(|t-1/2|\le(2h_b^2)^{-1}\) we have \(f_b(t)\ge c h_b e^{-h_b^2/8}\), with an absolute \(c>0\). Its probability under \(f_b/a_b\) is therefore at least \(c h_b^{-1}b^{-9/32}\). The number \(N\) of coordinates in this interval is binomial with mean \[\mathbb EN\ge c h_b^{-1}b^{23/32}\ge2b^{0.70}\] for sufficiently large \(b\), since \(23/32>0.70\). Its variance is at most its mean, so \[\mathbb P(N<b^{0.70}) \le\frac4{\mathbb EN} \le C h_b b^{-23/32}=O(b^{-1/20}).\] Thus a set of continuous \(F_b\)-mass \(1-O(b^{-1/20})\) satisfies the logarithmic eligibility condition with half its tolerance and the balanced-coordinate condition with half its interval width.

For each \(e\in\{0,1\}\) and \(u\in[0,1]\), \[\left|\frac{d}{du}\log\bigl(h_b\gamma_1(h_b(u-e))\bigr)\right| =h_b^2|u-e|\le h_b^2.\] The same bound holds for \(|(\log f_b)'|\), since its derivative is a weighted average of these two logarithmic derivatives. Integrating along the coordinates of a grid cell proves Equation (22). Rounding a continuous point down to its anchor changes \(\log F_b\) by at most \(\eta_b\) and every coordinate by less than \(p_b^{-1}\). Since \(\eta_b<\frac12b^{0.56}\) and \(p_b^{-1}<(2h_b^2)^{-1}\) for large \(b\), the stricter continuous event just considered rounds into \(E_b\). In addition, summing the first bound in Equation (22) over all cells gives \[e^{-\eta_b}\mathbb E_zF_b(t_z) \le\int_{[0,1]^b}F_b(t)\,dt \le e^{\eta_b}\mathbb E_zF_b(t_z).\] Applying the corresponding comparison on cells whose anchors lie in \(E_b\) gives the lower bound on their weighted grid mass. Its upper bound is the total grid mass. Equation (24) now proves both assertions in Equation (21).

Finally, the odds of a coordinate bit at \(t\) are \[ \frac{P_{b,t}(\varepsilon_j=0)}{P_{b,t}(\varepsilon_j=1)} =\exp\bigl(h_b^2(1/2-t_j)\bigr). \tag{25}\] On a balanced coordinate at an eligible anchor, each bit value has probability at least \(\alpha=(1+e)^{-1}\). Therefore \(P_{b,t_z}(\varepsilon)\le(1-\alpha)^{b^{0.70}}\) for every \(\varepsilon\). Equations (19) and (20) give \(F_b(t_z)/p_b\le e^{5b^{0.56}}\). Since \(0.56<0.70\), their product is at most \(e^{-c b^{0.70}}\) after decreasing an absolute \(c>0\) and increasing the absolute threshold. Equation (22) proves the same assertion at all points of the cell, again decreasing \(c\) if needed. ◻

Proof. We first select \(W\) and \(U_b\) when preceding data are given. For large \(b\), the bound on \(a\) implies \[5a^{0.56}\le5b^{0.56/0.9}\le b^{0.65},\] because \(0.56/0.9<0.65\). Thus \(g_0\) satisfies the cap in Lemma 4. Choose the columns \(w_j\) independently and uniformly from \(H\).

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

By Equation (25), at least \(b^{0.70}\) coordinates are selected into \(S\) with probability at least \(2\alpha\), where \(\alpha=(1+e)^{-1}\). Apply Chebyshev’s inequality to the number selected among these coordinates. Its mean is at least \(2\alpha b^{0.70}\), its variance is at most its mean, and \(b^{0.69}\) is at most half its mean for sufficiently large \(b\). Hence \[ \mathbb P\bigl(|S|<b^{0.69}\bigr)=O(b^{-0.70})=O(b^{-1/2}). \tag{29}\] For any fixed \(S\) with \(b^{0.69}\le|S|\le b\), its columns remain independent uniform elements of \(H\). Lemma 4 therefore shows, with failure probability \(O(b^{-1/2})\) over \(W\), that \[2^{-|S|}\sum_{\varepsilon\in\{0,1\}^S} g_0\left(y-\sum_{j\in S}\varepsilon_jw_j\right) \ge(1-Cb^{-1/10})\bar g_0\qquad(y\in H).\] The conclusion is simultaneous for every \(y\). In particular it allows \(y=x-\sum_{j\notin S}d_jw_j\), even though that offset involves the other columns of \(W\). There is no conditioning on those columns in applying the sampler to the selected ones.

Let \(q_W(z)\) be the mixture probability that either \(|S|<b^{0.69}\) or the displayed uniform sampler conclusion fails for its selected columns. Equation (29) and Lemma 4 imply \(\mathbb E_W q_W(z)\le Cb^{-1/2}\) for each eligible \(z\). The weighted average is therefore bounded by \[\mathbb E_W\mathbb E_{z\in G_b} F_b(t_z)\mathbf 1_{E_b}(z)q_W(z) \le Cb^{-1/2}\mathbb E_zF_b(t_z)\mathbf 1_{E_b}(z) \le C' b^{-1/2}.\] Fix one \(W\) for which the inner expectation is at most this last bound, and set \[U_b=\{z\in E_b:q_W(z)\le b^{-1/20}\}.\] Weighted Markov’s inequality gives the explicit discarded mass \[ \mathbb E_zF_b(t_z)\mathbf 1_{E_b\setminus U_b}(z) \le C' b^{-1/2+1/20}=C'b^{-9/20}. \tag{30}\] Together with Equation (21), this proves the last assertion of Equation (28). At every remaining anchor, average the uniform sampler conclusion over successful mixture components and use nonnegativity on the others. For all \(x\in H\) the result is at least \[(1-b^{-1/20})(1-Cb^{-1/10})\bar g_0 \ge(1-A b^{-1/100})\bar g_0,\] proving Equation (26).

It remains to choose \(C_b\). The following argument applies both to this \(U_b\) and, in the base version, to \(U_b=E_b\). Put \[M=\mathbb E_zF_b(t_z)\mathbf 1_{U_b}(z)=1+O(b^{-1/20}),\qquad d=\frac{|U_b|}{p_b^b}.\] The lower eligible weight gives \[ d\le M e^{-b\mu_b+b^{0.56}} \le2e^{-b\mu_b+b^{0.56}}. \tag{31}\] Choose a line \(C\subset G_b\) uniformly among one-dimensional linear subspaces. For any fixed nonzero \(u\in G_b\), \[\mathbb P_C(u\in C)=\frac{p_b-1}{p_b^b-1}.\] Consequently, for every \(z\in U_b\), the event \(\mathcal C_C(z)\) that \(z+C\) contains another point of \(U_b\) has probability at most \[ \mathbb P_C(\mathcal C_C(z)) \le(|U_b|-1)\frac{p_b-1}{p_b^b-1} \le2p_b d\le4e^{-2b^{0.56}}. \tag{32}\] The last inequality uses the upper bound in Equation (19).

For a fixed line, write \(S_C(x)=\sum_{c\in C}v_b(x-c)\) and \(g_C(x)=\max_{c\in C}v_b(x-c)\). The normalization in Equation (27) ensures \[\mathbb E_x S_C(x)=p_b\mathbb E_z v_b(z)=M.\] If a coset contains at most one usable anchor, its sum and maximum agree. Otherwise, charge their difference to all usable weights in that coset. This gives the pointwise bound \[0\le S_C(x)-g_C(x) \le\sum_{c\in C}v_b(x-c)\mathbf 1_{\mathcal C_C(x-c)}.\] Averaging first over \(x\) and then over \(C\) yields \[\begin{align*} \mathbb E_C\mathbb E_x(S_C(x)-g_C(x)) &\le\mathbb E_C\left[p_b\mathbb E_z v_b(z)\mathbf 1_{\mathcal C_C(z)}\right]\\ &=\mathbb E_zF_b(t_z)\mathbf 1_{U_b}(z)\mathbb P_C(\mathcal C_C(z))\\ &\le4M e^{-2b^{0.56}}. \tag{33}\end{align*}\] In particular the \(p_b^{-1}\) in \(v_b\) cancels the \(p_b\) translates in the coset sum; the estimate controls lost weight, not just the number of colliding cosets. Some line \(C_b\) thus satisfies \[M-4M e^{-2b^{0.56}}\le\bar g_b\le M.\] This proves the mean assertion, in fact with the stronger error \(O(b^{-1/20})\). Finally every usable anchor is eligible, so \(v_b(z)\le e^{5b^{0.56}}\) by Equations (19) and (20); the same bound holds for its coset maximum. Enlarging the absolute constants \(A,B\) completes both versions of the lemma. ◻

Proof. The integer vector \(k-z\) reduces to \(c\) modulo \(p_b\), proving \(\lambda\in L_b\). The remaining identities in Equation (34) follow from \(p_b t=k+\{p_b t\}\) and the chosen maximizing anchor. Adding an integer bit vector preserves \(L_b\). Since \(\tau\in[0,1)^b\), the residual coordinate bound follows. Apply Equations (22) and (23) at \(\tau\in Q_z\) to obtain the stated lower and upper estimates. ◻

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

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

Otherwise the two last-coordinate values are \(v\) and \(v+1\). Let the two slices have cardinalities \(k_1\) and \(k_2\), and let \(A\) and \(B\) be their intersection sets. Choose \(Z_q\) uniformly in a fixed fundamental parallelepiped of \(\Lambda_h\). Translation invariance gives \[|(A+\pi(vZ_q))\cap(B+\pi((v+1)Z_q))| =|A\cap(B+\pi(Z_q))|.\] This identity is valid even when \(v\) is not an integer: the products \(vZ_q\) and \((v+1)Z_q\) are formed in \(\mathbb R^m\) before projection. Only the relative shift must be Haar uniform. By Fubini, \[\mathbb E_{Z_q}|A\cap(B+\pi(Z_q))|=|A||B| \le L_*^{k_1+k_2-2}\prod_{l\in P}\eta_{a(l)}.\] Markov’s inequality bounds the probability of violating Equation (53) by \(1/L_*\). If either slice has measure zero the intersection has measure zero almost surely, which gives the same conclusion. A union bound over \(\mathcal P_q\) has total probability less than one, so one choice of \(Z_q\) works for all its patterns. Induction proves the result. ◻

Proof. Multiplication by \(k\) on \(\mathbb R^n/\Gamma\) maps \(\pi_\Gamma(K/k)\) onto \(\pi_\Gamma(K)\). Its image has measure at most \(k^n\) times the measure of the original set: partition a fundamental parallelepiped into \(k^n\) cells on which the map is injective. Consequently \[|\pi_\Gamma(K/k)|\ge k^{-n}(1-\delta)>\delta.\] For every point \(x\) of the torus, the sets \(\pi_\Gamma(K)\) and \(x-\pi_\Gamma(K/k)\) have measures summing to more than one and therefore intersect. Thus \(\pi_\Gamma(K)+\pi_\Gamma(K/k)\) is the whole torus. Finally, convexity gives \(K+K/k=(1+1/k)K\). Neither symmetry nor the inclusion \(0\in K\) is required. ◻

Proof of Theorem 1. All constants in the vertical construction, including its cutoff \(B\), are fixed first. For sufficiently large \(n\), put \(s=\log\log n\) and use Proposition 10 with \(b_1=\lceil s^2\rceil\). Retain its notation \(L,M,D,D_v,b_i,h_i\), and set \[R^2=\sum_{i=1}^{r+1}b_i h_i^2,\qquad m=n-D.\] Here \(D=O(s^2+1)\) and \(R\) is bounded by a fixed polynomial in \(s\). After passing to the affine coordinates of Lemma 2, there are at most \((Cm^2)^D\) horizontal bodies \(J_a\) such that every \(v\) with \(\|v\|\le R\) has a label satisfying \[ J_a\subset K_v,\qquad c_{\rm sec}\operatorname{vol}_n(K)\gamma_D(v) \le\operatorname{vol}_m(J_a)\le C_{\rm sec}\operatorname{vol}_n(K)\gamma_D(v). \tag{54}\]

Choose an absolute constant \(C_*\) later and put \[ \rho=C_*n\log n,\qquad D_h=\frac{\operatorname{vol}_n(K)}{\rho D_v},\qquad u_a=\frac{\operatorname{vol}_m(J_a)}{D_h}. \tag{55}\] For any vertical target \(y\), use its pattern from Proposition 10 and label each raw point \(l\) by a body contained in the section at \(y-Ml\). The residual bound permits Equation (54). With the chosen horizontal covolume, the normalized section volume is comparable to the corresponding normalized Gaussian weight multiplied by \(\rho\): \[c_{\rm sec}\rho D_v\gamma_D(y-Ml) \le u_{a(l)}\le C_{\rm sec}\rho D_v\gamma_D(y-Ml).\] Thus the total weight supplies the sum of the horizontal loads, while the atom bound controls each load separately. These estimates give \[ \sum_l u_{a(l)}\ge c_3\rho,\qquad \max_l u_{a(l)}\le U_n:=C\rho\exp(-c b_1^{0.70}), \tag{56}\] where \(c_3=c_{\rm sec}\kappa>0\) is absolute.

Three scale comparisons are needed. First, \[ \frac{U_n}{m} \le C'\exp\bigl(s-c's^{1.4}\bigr)\longrightarrow0. \tag{57}\] Second, every pattern has at most \(2^D\) points, so deleting those with \(u_{a(l)}<\sqrt m\) loses at most \[ 2^D\sqrt m=n^{1/2+o(1)}=o(\rho). \tag{58}\] Third, the logarithm of the number of labels is \(O(D\log m)=o(\sqrt m)\). These statements follow from \(D=O(s^2+1)\) and \(\log n=e^s\); all their constants are independent of \(K\). In particular the retained pattern is nonempty and has load at least \(c_3\rho/2\) for large \(n\).

Restrict the label list to \(\sqrt m\le u_a\le U_n\). Lemma 3 gives one lattice \(\Lambda_h\) of covolume \(D_h\) for which the hole sets \[U_a=(\mathbb R^m/\Lambda_h)\setminus\pi_{\Lambda_h}(J_a)\] satisfy \(|U_a|\le e^{-u_a/2}\) simultaneously. We next select one shear that works for every retained pattern, not a separate shear for each target.