Translative covering densities of order n log n

Proof. If |x|\le a, the \mu-measure of normals with |u\cdot x|>1 is at most one by rotational invariance and (2.4). The probability that there is no such Poisson normal is therefore at least \exp(-1). Integrating over aB gives \mathbb E|K|\ge\exp(-1)\omega_n a^n. On the other hand, |K|\le\omega_n b^n<3\omega_n a^n. Thus X=|K|/(\omega_n a^n) has 0\le X\le3 and \mathbb E X\ge\exp(-1). Writing p=\mathbb P(X>2v), we have \mathbb E X\le2v(1-p)+3p, which proves the claim.□

Proof. We prove the localization and rounding assertions first, then count the resulting lists. All dimension thresholds in the proof are uniform for 1\le R\le n^2.

Averaging the full multiset of centers. Give each center an index (t,\ell)\in T\times\Lambda, at position t+\ell. Distinct indices remain distinct even if they have the same position. This multiset is locally finite because T is finite and \Lambda is discrete. Write \rho=|T|/\det\Lambda, and let F be a fundamental parallelepiped of \Lambda. For every nonnegative integrable function f,

Indeed, Tonelli’s theorem permits the sums to be interchanged with the integral. For each t, the sets F-t-\ell, \ell\in\Lambda, partition \mathbb R^n up to null sets. This proves the identity without any restriction on the shape or size of F.

Put \beta=b+4\eta. Call a point y\in\mathbb R^n unrounded-good if there is no center occurrence at distance less than r_-, at most C_{\mathrm{loc}}R occurrences have distance at most \beta, and

Let G be this periodic measurable set. These conditions respectively exclude short residuals, bound the number of relevant residuals, and bound their total radial cost. Using the full ball ensures that every index entering a rounded test is counted before rounding.

For a uniform point modulo \Lambda, the expected number of occurrences in its open r_--ball is at most

for large n. Hence the first condition fails with probability at most 1/200. Also

for large n, so the expected outer count is at most 3R/(2v). For the weighted condition, polar integration gives the exact identity

Equation (3.9) therefore bounds the expected weighted sum by 5R/(2v). Markov’s inequality bounds the two remaining failure probabilities by 3/2000 and 5/2000, respectively. Consequently

One window with both required bounds. For z uniform modulo \Lambda, let M(z) count all center occurrences in z+B_{D+b+4\eta}. Equations (3.9) and (3.1) imply

Moreover, periodicity and Fubini’s theorem give

Both expressions concern the entire Euclidean window, including all its overlapping period copies. Markov’s inequality gives

The sum is less than one. Fix a slide z outside these two exceptional events, and retain every occurrence in z+B_{D+b+4\eta}. There are at most N_n such occurrences, and at least half of z+B_D lies in G.

Rounding and transferring coverage. Translate this window and the retained centers by -z, and round every center coordinatewise to the nearest point of h_n\mathbb Z^n, using a fixed rule for ties. Each center moves a distance at most

The rounded centers belong to \mathcal Q_n; enumerate them as an ordered list P, retaining all repeated entries.

We check that every y\in B_D with y+z\in G belongs to G_P. Every unrounded residual has length at least r_-, so every rounded one has length at least r_--\delta_n\ge r_--2\eta. A rounded residual of length at most b+3\eta comes from an unrounded residual of length at most

Thus at most C_{\mathrm{loc}}R rounded indices are relevant. This strict separation of the two outer radii ensures that every index entering a rounded test was counted before rounding.

The function w_a is globally Lipschitz on [0,\infty) with constant 2n/a. Its derivative has absolute value 2nr/a^2\le2n/a for 0<r<a, and it is constant for r>a. If r and r' are the unrounded and rounded lengths of a relevant residual, then

where the last step uses w_a(r)\ge1. Summing over the relevant indices, all of which were included in (3.10), gives

This verifies (3.2)–(3.4). In particular, |G_P|\ge|B_D|/2 and P\in\mathcal F_n.

Now assume that the original periodic arrangement covers by K. For any point of z+B_D, every center whose translate of K contains that point lies in z+B_{D+b} because K\subseteq bB. Such a center was retained. Moving it by at most \delta_n changes the residual norm by at most \delta_n and each scalar product with a unit normal by at most \delta_n. Hence its rounded translate of K^+ contains the translated point of B_D. This proves (3.7) for every point of the closed window.

Counting the lists. Write J_n=|\mathcal Q_n|. A containing cube gives

Since b=a(1+1/n), \eta=n^{-4}, and 1\le R\le n^2,

This proves the first bound in (3.6). Counting ordered lists allows all multiplicities and gives

The two preceding estimates give the second bound in (3.6). Finally, (3.8) follows directly from the definition of G_P and w_a\ge1.□

Proof. We first record one-dimensional estimates, then prove the overlap and common-intersection bounds. Constants with a subscript a below may change from line to line, but depend only on a.

One-cap probabilities and radial costs. Write t_*=1/a, e_i=x_i/|x_i|, and \tau_i=(1+\epsilon_i)/|x_i|. For a unit vector e, let

where k_n is the normalization constant. Substitution of z=1-v^2, using 1\le1/v\le1/t, gives

Consequently,

These exact inequalities avoid dimension-dependent prefactors in ratios of cap probabilities.

All the thresholds satisfy

for sufficiently large n, and hence belong to the fixed interval J=[t_*/2,(1+t_*)/2]\subset(0,1). Since M=(2F_n(t_*))^{-1}, we have c_i=F_n(\tau_i)/F_n(t_*). The logarithmic derivative in (4.5) is bounded by C_an on J. This proves c_i\le C_a, while the lower radial bound proves c_i\ge n^{-C_{a,A}}. More explicitly, putting \delta_i=[1-|x_i|^2/a^2]_+, elementary algebra gives

Integrating (4.5) therefore gives -\log c_i\le C_a(1+n\delta_i), after increasing the starting dimension so that Qn^{-3}\le1. As s_i=\max(\log2,-\log c_i), this proves (4.1). The additive constant is needed even when c_i\ge1/2.

The overlap bound. Consider two ordinary half caps with thresholds \tau,\upsilon drawn from our list and with axis angle \theta\in[0,\pi]. Put t=(\tau+\upsilon)/2. If \theta<\pi, adding their two defining inequalities shows that their intersection lies in the half cap along the angle bisector with threshold

The intersection is empty if \theta=\pi or q\ge1, so suppose q<1. Let f(z)=\log(1-z^2). Its second derivative is bounded in absolute value on J, whence

Furthermore,

using t\ge t_*/2 and \tan(\theta/2)\ge\theta/2. Apply the upper bound in (4.4) to F_n(q) and the lower bound to both terms in the following denominator:

Indeed, q^{-1}\le2/t_*, and n(\tau-\upsilon)^2=O_{a,A,Q}((\log n)^2/n)\to0 by (4.6). This last fact is the benefit of the thin shell. The argument does not require q\in J, so it also applies when the bisector threshold approaches 1.

For projective angle \phi=\angle(x_i,x_j), the four pairs of signed half caps have ordinary angles \phi or \pi-\phi\ge\phi. Summing (4.7) over these four disjoint sign choices and using c_i=2MF_n(\tau_i) gives

By (4.1), c_i/\bar c_i\le\max(1,2C_a), so clipping the denominator costs only a constant. Independently, the trivial intersection bound gives

To see this, order the clipped intensities as \bar c_i\le\bar c_j. If \bar c_i<1/2, use \mu(C_i\cap C_j)\le c_i=\bar c_i; otherwise both clipped intensities equal 1/2, and use c_i\le C_a. The minimum of the two bounds is at most their geometric mean. Together with

this proves (4.2).

Projective angle satisfies the triangle inequality, as the quotient of spherical distance under antipodal identification. The inequality \sqrt{x+y}\le\sqrt x+\sqrt y shows that \sqrt{|s_i-s_j|} also satisfies it. Thus d is a pseudometric; distinct labels, including repeated caps, may have distance zero.

A common intersection. Set r=r(S) and m_S=|S|, and choose an index attaining the minimum defining r. By the triangle inequality, each axis in S has projective angle at most 2\sqrt{r/n} from e_0=e_{i_0}. Since F_n is strictly decreasing, the raw-minimum anchor has the largest threshold: \tau_0=\tau_{i_0}\ge\tau_i. Orient each axis so that its ordinary angle \phi_i with e_0 equals its projective angle, and write

where v_i is a unit tangent vector. For \phi_i=0, its choice is immaterial.

We use the elementary bound

for a uniform W\in S^{d-1}, d\ge2, any unit v, and h\ge0. Here is a proof. Rotational invariance reduces to X=W_1. Integrating the derivative of x^{2j-1}(1-x^2)^{(d-1)/2} on [-1,1] shows that

Odd moments vanish. The exponential series therefore gives \mathbb{E} e^{zX}\le e^{z^2/(2d)}; applying Markov’s inequality with z=-dh proves (4.8).

Conditionally on u\cdot e_0=t, a uniform sphere point has the form u=te_0+\sqrt{1-t^2}\,W, with W uniform on the tangent sphere S^{n-2}. Put

By (4.8) and a union bound, with conditional probability at least 1/2 one has W\cdot v_i\ge-h for every i\in S. For large enough n, \cos\Phi\ge1/2 and \tau_0+\delta\in J, because r\le B_0\log n and m_S\le n^2. On that tangent event, whenever t>\tau_0+\delta,

Thus all these points lie in every double cap. Integration over the axial coordinate gives

where the last step follows from (4.5) on J. Finally,

Absorb the fixed factors into L=L(a) and use c_{i_0}\ge\bar c_{i_0} to obtain (4.3). If r=0, then \Phi=\delta=0, and the same proof applies.□

Proof. Each half cap has angular radius \arccos\tau_i. Since

the estimate \tau_i\ge1/a-C_a/n shows that its radius is strictly less than 2\sqrt\varepsilon for large n. Every pair of signed axes is at ordinary angle at least the projective angle. The spherical triangle inequality therefore excludes a point in any pair of half caps at projective separation greater than 4\sqrt\varepsilon.□

Proof. Set \zeta=1/10 and R_*=B_0\log n; we will choose B_0 after the constants governing the row estimate. Define

For each final block S, we will choose a common subset of intensity e^{-\ell(S)}\bar c_{i(S)}. Thus \ell(S) is the logarithmic loss assigned to that block. The merger condition below keeps the total loss at most \zeta m, while terminality will control the number of nearby blocks with small loss.

Constructing the partition. Start with the singleton partition. Whenever a subfamily of at least two current blocks has union W satisfying

replace that entire subfamily by W. The subfamily may have any size. Each merger decreases the number of blocks, so this procedure terminates after at most m-1 mergers. Every resulting block satisfies

and no subfamily of at least two terminal blocks satisfies (5.7).

The anchor i(S) need not attain the minimum defining r(S). Applying the triangle inequality through an index that does attain it gives

For singletons this holds with both sides zero. By (5.2) and atomlessness, choose E_S\subseteq\bigcap_{i\in S}C_i of exactly the measure

For singletons this choice is possible because \bar c_i\le c_i. Thus q_S=s_{i(S)}+\ell(S)\ge\log2. Different blocks have different anchor labels, and hence

This proves (5.4). For n\ge3, (5.8) and m\le n^2 give

Consequently (5.3) holds with K=L(B_0+3). Also

which proves (5.5). It remains to control the overlap rows.

What terminality implies. We claim that a constant C_{\mathrm{ct}}=C_{\mathrm{ct}}(L,\zeta) bounds the number of blocks satisfying

by C_{\mathrm{ct}}(1+t+u), provided that z\in I, t,u\ge0, and

This is a count of blocks, including blocks with coinciding anchors in pseudometric distance.

Let h be the number of such blocks and let W be their union, of size N. If h\le1 there is nothing to prove. Otherwise choose one of their anchors, say i(S_0). For every i\in S\subseteq W, (5.9) gives

As i(S_0)\in W, it follows that

Choose a fixed integer N_0\ge2 so large that L\log N\le\zeta N/2 for all N\ge N_0. If

then N\ge h implies

The whole subfamily could then be merged, contradicting terminality. Since 1+D_*\le8(1+t+u), the claim follows, for example with C_{\mathrm{ct}}=1+N_0+16L/\zeta. Here the logarithm being absorbed is \log N, the logarithm of the number of original labels in the union; the block sizes need not be comparable.

Estimating a row. The elementary intersection bound and (5.1) give, respectively,

For the first inequality, use \mu(E_S\cap E_T)\le\min(\lambda_S,\lambda_T) and discard the factors 1+\lambda_S,1+\lambda_T in the denominator. For the second, use E_S\subseteq C_{i(S)} and (5.10).

Fix S. For k\ge0, put in the kth bin those T\ne S for which e^{-(k+1)}<w_{ST}\le e^{-k}; zero weights can be omitted. Writing Q=q_S+k+1\ge1, the two bounds above imply

where A_1=(\log C_0+2)/c_0. Indeed, taking logarithms in (5.14) gives

Now set

If Q\le\delta R_*, apply the terminality count with z=i(S), t=A_1Q, and u=2Q. The number of blocks in the kth bin is at most

where C_1=C_{\mathrm{ct}}(A_1+3). These constants are independent of B_0. Choose B_0\ge\max\{1,6/\delta\}, and increase n_1 so that R_*\ge4/\delta for n\ge n_1.

First suppose q_S\le\delta R_*/4, and put J=\lfloor\delta R_*/2\rfloor. For 0\le k\le J we have q_S+k+1\le\delta R_*, so (5.16) bounds the total weight in these bins by

Every remaining weight is at most e^{-(J+1)}\le e^{-\delta R_*/2}, and there are at most n^2 of them. Their sum is therefore at most

Since q_S\ge\log2, this proves

in the present case. If q_S>\delta R_*/4, the simpler bound (5.13) gives

Thus (5.17) holds for every block after enlarging C_3. Summing it and applying (5.4) proves (5.6).□

Proof. We first recall Harris’s correlation inequality for product Bernoulli measures [5], together with its elementary proof. Increasing functions of independent Bernoulli variables have nonnegative covariance. Indeed, induction on the number of variables and conditioning on the last variable reduce the additional covariance term to p(1-p)(f_1-f_0)(g_1-g_0)\ge0, where f_b,g_b are the corresponding conditional means. Thus an increasing event B and a decreasing event F satisfy

Write B_i=\{I_i=1\}, p_i=\mathbb{P}(B_i), and p_{ij}=\mathbb{P}(B_i\cap B_j). For each i, let F_i be the event that none of the earlier B_j with H_i\cap H_j=\varnothing occurs, and let G_i exclude the remaining earlier events. If some earlier avoidance event has probability zero, the conclusion is immediate. Otherwise all the conditional probabilities below are defined. Since F_i uses only coordinates outside H_i, it is independent of B_i. It is also decreasing. A conditional union bound and (6.2) therefore give

The first inequality uses \mathbb{P}(G_i\mid F_i)\le1. Multiplying the successive avoidance probabilities and using 1-x\le e^{-x} yields

This remains valid when an intermediate lower bound above is negative.

Attach to each index i a private independent Bernoulli variable of parameter q, and require it as part of B_i. The new mean is qm, and its ordered off-diagonal sum is q^2\Delta_{\mathrm{off}}. The original zero event implies the new zero event, so (6.3) bounds its probability by \exp(-qm+q^2\Delta_{\mathrm{off}}/2). Since \Delta^*=m+\Delta_{\mathrm{off}}, choosing q=m/\Delta^*\in(0,1] proves (6.1). The proof retains every index even when two supports coincide.□

Proof. Write \tau=\mu(\Omega)>0. Conditional on N=\Pi(\Omega), the points are independent with law \mu/\tau and are almost surely distinct. If k=|I_\alpha|, the Poisson factorial moment \mathbb{E}(N)_k=\tau^k gives

In particular, no factorial divides the activity, even for repeated slot sets.

We apply Lemma 6.1 to cell-occupation indicators. Fix \delta>0. Form the Boolean atoms generated by all the slot sets and subdivide each positive-measure atom into finitely many measurable cells of measure at most \delta, using nonatomicity. After omitting null cells, this gives a finite partition \mathcal P_\delta that respects every slot. Modifications on the common null set do not affect the Poisson process. For C\in\mathcal P_\delta, set

These variables are independent and

For each \alpha, retain every injective assignment of cells f:I_\alpha\to\mathcal P_\delta with f(i)\subseteq E_{\alpha i}. Its indicator is \prod_iX_{f(i)}. Let Y_\delta be the sum over these indexed assignments. Different assignments remain different indices even when their underlying cell sets agree.

The following estimate controls all cell collisions. For a fixed list F_1,\ldots,F_r of unions of cells, let Q_\delta(F_1,\ldots,F_r) be the sum of \prod_{v=1}^rp_{C_v} over distinct cells C_v\subseteq F_v. Then

Indeed, the unconstrained sum factors over the slots, and (6.6), followed by telescoping the product, bounds its difference from \prod_v\mu(F_v) by the first term. The weight of assignments with C_v=C_w is at most

A union bound proves (6.7). Empty products are 1, and the estimate also holds if a set has measure zero. Applying it to each slot list gives

It remains to identify the finite dependency sum and the limiting event. For two internally injective assignments f and g, the complete set of equalities f(i)=g(j) is a unique partial matching M. Their Bernoulli supports intersect precisely when M\ne\varnothing. For fixed \alpha,\beta,M, identify the slots paired by M and leave the other slots as singletons. Assign to each resulting class its slot set, or the intersection of its two slot sets. Denote these sets by (F_v)_v. Requiring distinct cells for these classes excludes exactly the unintended equalities. Thus the contribution with exact matching M is Q_\delta((F_v)_v), and its limit is

All sums are finite. Estimate (6.7) therefore shows that the ordered dependency sum, including identical assignment pairs, satisfies

Identical assignments give the full identity matching; other full matchings caused by repeated slots remain separate terms.

Finally, couple the cell variables with the original process. The probability that any cell contains two or more points is at most

Outside this event, point injections and occupied-cell injections are in bijection, simultaneously for every witness type. Hence

Apply Lemma 6.1 and let \delta\downarrow0, using (6.8) and (6.9). The identity-matching contribution makes the limiting denominator positive. This proves (6.5).□

Proof. Write h_{ij}=\mu(E_i\cap E_j)/(\lambda_i\lambda_j). For the self sum, fix the off-diagonal edges P of a partial matching between two copies of the slot list. Regard P as a directed graph on the common label set. Every vertex has total degree d_P(i)\in\{0,1,2\}, since its in-degree and out-degree are at most one. A diagonal loop is available exactly at the vertices of degree zero. Since h_{ii}=\lambda_i^{-1}, summing the compatible loop choices gives

Here \delta_i^{-1}\le \delta_i^{-d_P(i)/2} at each incident vertex. This includes directed paths and cycles; Figure 2 illustrates the permitted incidences. Summing over P and dropping the requirement of distinct right endpoints bounds the remaining sum by \prod_i(1+\sum_{j\ne i}w_{ij}). The empty matching contributes 1, proving (6.10).

For two lists, drop all matching restrictions and sum over nonempty subsets of cross edges. With the analogous nonnegative weights h_{ij}, the result is at most \prod_{i,j}(1+h_{ij})-1\le e^{\sum_{i,j}h_{ij}}-1. This proves (6.11).□

Proof. Apply Lemma 4.1 with shell parameter 10 and perturbation bound 3. Its affinity and common-intersection estimates supply the hypotheses of Proposition 5.1; the common-intersection constant is available before the radius multiplier in that proposition is fixed. Apply the proposition separately to each list, making all choices before sampling \Pi. The budget (5.5) gives

Together with (5.6) and (6.10), it also gives the self bound in (6.12), after choosing C_*.

To check the cross estimate, write \bar c_{\alpha i}=\min\{\mu(C_{\alpha i}),1/2\} and let i(S) be the anchor of a block. Lemma 4.1 and Proposition 5.1 provide fixed exponents P_0,P_1>0 such that

Apply the affinity estimate to each two-element list of anchor residuals; this does not require the union of the two full lists to have at most n^2 entries. It gives

There are at most n^4 block pairs. Choose H after these constants, so that cH^2>9+2P_1+P_0. For sufficiently large n, the angular hypothesis gives \rho_{\alpha\beta}\le n^{-4}. Equation (6.11) now gives D_{\alpha\beta}\le2n^{-4}\nu_\alpha\nu_\beta, which implies (6.13). At cross angles greater than 4\sqrt\varepsilon, Corollary 4.2 makes every cross-slot intersection empty, and the diagram is zero.

Finally, the point assigned to a block lies in every cap belonging to that block. A positive injection count thus hits every residual cap.□

Proof. Condition on Y=y with 0<|y-p|\le L, and write u=(y-p)/|y-p|. If the event in the statement occurs, the component of Z-q perpendicular to u has length at most L\sin\xi. Both orientations allowed by the projective angle therefore lie in the same cylinder around the affine line q+\mathbb Ru. The projection of B_D onto the direction u has length 2D. Every perpendicular slice of the cylinder has (n-1)-dimensional volume at most \omega_{n-1}(L\sin\xi)^{n-1}. Thus the allowed points Z have volume at most 2D\omega_{n-1}(L\sin\xi)^{n-1}. Divide by |G| and then average over Y.

To obtain the last inequality, use the slicing identity

Indeed, restrict the integral to |t|\le n^{-1/2} and use \log(1-1/n)\ge-1/(n-1). In particular, \omega_{n-1}/\omega_n\le\sqrt n.□

Proof. Sample M_n points independently and uniformly from G. For independent sampled points Y,Z, take the union in Lemma 7.1 over all N^2 ordered pairs of center labels. Since b+3\eta\le2 for sufficiently large n, this gives

All relevant labels are included even though the relevant lists vary with Y and Z. Repeated centers only repeat events in this union.

Set t_n=H\sqrt{\log n/n}. Multiply the right side of (7.4), with \sin t_n\le t_n, by \binom{M_n}{2}. The logarithm of the resulting bound is at most

which tends to -\infty. Thus the probability that any pair of sampled points is t_n-bad tends to zero, uniformly in the pattern. For \xi=4\sqrt\varepsilon, the inequality \sin\xi\le4\sqrt\varepsilon instead bounds (7.4) by f_n. The expected fraction of these bad unordered pairs is at most f_n. Markov’s inequality shows that this fraction exceeds 10f_n with probability at most 1/10. Consequently both conclusions hold with probability at least 9/10-o(1)>0. The sampled points are distinct almost surely because uniform measure on G has no atoms. Fix a successful list. No independence between the two separation properties is needed.□

Proof. Fix P\in\mathcal F_n and its deterministic good set G_P. At each y\in G_P, Proposition 3.1 gives

for its relevant residuals x_i=y-p_i. If this list is empty at any point of G_P, that point lies in none of the balls p+(b+3\eta)B, so the probability in (7.5) is zero. We may assume all these lists are nonempty. For the range of R in the proposition, m_y\le n^2 once n is sufficiently large.

For each relevant residual, define the cutting cap

Lemma 4.1, applied with radial loss 10\log n/n and a fixed perturbation bound, gives

Consequently

All assumptions of Corollary 6.4 therefore hold uniformly in y and P. Fix its constants A,C_* and H for this value of A_0.

The list-length estimate in Proposition 3.1 gives N\le n^{k_0}\exp(\lambda_0n) for a fixed k_0, uniformly in the present range of R. Apply Lemma 7.2 to G_P with the just-fixed H. At each of the resulting M=M_n targets, choose the block partition and measurable witness sets from Corollary 6.4. Denote its injection count by Z_y, its activity by \nu_y, and the diagram sums by D_{yz}. The corollary gives

Every pair of distinct selected targets satisfies D_{yz}\le n^{-3}\nu_y\nu_z. Moreover, D_{yz}=0 unless the pair is 4\sqrt\varepsilon-bad. Our use of “at most” in the definition of badness makes both angular interfaces strict on its complement.

All choices so far depend only on P and its targets. In particular, the witness sets are chosen before the Poisson process; their activities are deterministic intensities. There is no need to choose witness sets measurably at every point of G_P, since only the finite selected list is used. If Z_y>0, every relevant residual is cut by a slab of the process, and the other centers are too far from y to contain it in a translate of K^+. Thus Z_y>0 certifies a hole.

Divide the possible values of -\log\nu_y in [0,AR] into intervals of length \log2. At most

bins suffice. A largest bin has m\ge M/Q targets and, for some \nu>0, all its activities belong to [\nu,2\nu]. There are at most 10f_n\binom M2 bad unordered pairs in the full list. Hence the chosen bin contains at most

bad ordered pairs with distinct indices. This bound allows the bin to contain every bad pair; no independence between bin membership and angles is asserted.

Apply Proposition 6.2 to the witnesses in this bin. Its numerator is at least m^2\nu^2. By (7.8) and (7.9), its denominator before the factor 2 is at most

The first term counts diagonal pairs. Among distinct pairs, only the coarse bad pairs contribute. Coverage forces Z_y=0 at every target of the bin, so

Now choose

Uniformly for 1\le R\le c_0n\log n, we have \log Q=O(\log n) and, for sufficiently large n,

The first term inside the parentheses in (7.10) is therefore at most \exp(-n\log n/32). By (7.3), the second is \exp(-\gamma n+O(\log n)). Since \gamma is fixed, their sum is at most \exp(-\gamma n+O(\log n)); absorbing the fixed factor 8 gives (7.5).

The order of the choices is fixed throughout: the geometric parameters come first, then the cap and block constants and H, then c_0, and finally the dimension threshold. Every estimate is uniform over the retained finite class. In particular, the auxiliary target selection introduces no dependence on the realization of \Pi.□

Proof of Theorem 1.1. Use the deterministic class \mathcal F_n from Proposition 3.1, with R=c n\log n. That proposition and Proposition 7.3 give

The error bounds are uniform over this finite class. Since \gamma>\lambda_0, the negative term dominates. Lemma 2.1 therefore guarantees a realization for which |K|>2v\omega_n a^n and no retained pattern covers B_D by translates of K^+.

Suppose that K+\Lambda+T=\mathbb R^n with |T|/\det\Lambda\le\rho_0. Proposition 3.1 would give a retained pattern covering B_D by K^+, a contradiction. Every covering thus has center intensity greater than \rho_0. Taking the infimum of its density yields

where Proposition A.1 supplies the equality. The realization is a centrally symmetric convex body, as observed after (2.6). Choose one for each n\ge n_0.□

Proof. Theorem 1.1 gives the lower bound already among centrally symmetric bodies, and \theta_T\le\theta_L transfers it to lattice coverings. Rogers’ bound (1.3) supplies the translative upper bound. The companion single-lattice theorem [10, Theorem 1.1] gives \theta_L(K)\le Cn\log n for every convex body and every n\ge2, which supplies the two lattice upper bounds.□

Proof. Fix the successful body K in the proof of Theorem 1.1, and put R=c n\log n. It satisfies |K|>2v\omega_na^n, and no periodic covering by K has center intensity at most \rho_0=R/(2v\omega_na^n).

Enumerate the rational points of \operatorname{int}K as q_1,q_2,\ldots and set

These are centrally symmetric rational polytopes contained in \operatorname{int}K, and they increase with j. Their union is \operatorname{int}K: every interior point lies inside a sufficiently small simplex with rational vertices in \operatorname{int}K, and all its vertices eventually occur in the enumeration. Continuity of volume from below, together with the fact that the boundary of a convex body has measure zero, gives |P_j|\to|K|. Choose j so that |P_j|>2v\omega_na^n; in particular, this P_j has nonempty interior.

Every periodic covering by P_j is a covering by K, because P_j\subset K. Its center intensity therefore exceeds \rho_0. Taking the infimum of the covering densities and using Proposition A.1 yields

This argument uses both inclusion and the retained volume margin.□

Proof. Fix a successful finite normal list U=(u_1,\ldots,u_m) from the proof of Theorem 1.1. The class \mathcal F_n is finite and independent of U. For each P\in\mathcal F_n, select a point y_P\in B_D outside all of its translates of K^+(U). For every center p in that list, either |y_P-p|>b+3\eta, or one of the normals satisfies

Each required inequality is strict. There are finitely many patterns, centers, and chosen certificates, so all these inequalities persist under a sufficiently small simultaneous perturbation of the normals. Empty patterns need no certificates.

The strict volume test persists as well. If U' is a list of unit normals with |u_j-u'_j|\le\delta for every j, then

Indeed, if x\in K(U), then |x|\le b and |u'_j\cdot x|\le1+b\delta; scaling by (1+b\delta)^{-1} proves the first inclusion. Interchanging U and U' proves the second. Volumes therefore converge as \delta\to0.

Rational unit vectors are dense in S^{n-1} for n\ge2, by the stereographic parametrization

and approximation of its omitted pole. Approximate all normals closely enough to preserve the holes and the strict volume test. The localization argument applies to every finite normal list, so the resulting rational list yields the same lower bound.□

Proof. Choose r>0 with K\subset Q_r, and let X be a locally finite covering center set. For a\in\mathbb R^n and L>0, the finite set

covers a+Q_L by translates of K. Indeed, if y\in a+Q_L and y=k+x with k\in K and x\in X, then x=y-k\in a+Q_{L+r}. This holds on the boundary as well. Repeating S with periods 2L\mathbb Z^n covers all of \mathbb R^n because the cubes a+Q_L+2Lz cover it. Reducing S modulo this lattice gives

Writing R=L+r, we obtain, for every a and every R>r,

This proves the required lower bound for both centered cube conventions.

For the ball conventions, fix L>0 and put \beta=\sqrt n(L+r). Integrate (A.1) over a\in z+B_{R-\beta}, where R>\beta. Any counted center belongs to z+B_R, and each such center is counted on a set of a of volume at most (2(L+r))^n. Tonelli’s theorem therefore gives

Consequently, uniformly in z,

First let R\to\infty with L fixed, and then let L\to\infty. This proves the lower bound for the ball lower densities and hence also for the upper densities. No comparison of a ball with just one containing or contained cube is needed.

For the reverse inequality, consider a periodic center set X=\Lambda+T with distinct cosets. Let F be a bounded half-open fundamental parallelepiped of \Lambda and choose d>0 with F\subset Q_d\cap B_d. For each fixed t\in T, the cells t+\lambda+F partition space up to null boundaries. For R>d and W_R=Q_R or B_R, the cells based at points of t+\Lambda in z+W_R contain z+W_{R-d} up to a null set and are contained in z+W_{R+d}. Thus

Divide by \vol(W_R) and sum over the distinct cosets. Every stated center-count intensity is therefore |T|/\det\Lambda, uniformly in z; the corresponding covering density is V|T|/\det\Lambda. The finite constant d may depend on the lattice; no bound uniform over lattices is needed. Since periodic center sets are locally finite, restricting each unrestricted infimum to these competitors proves the reverse inequality.□