Proof. For the first inequality, note that

$$ \begin{align*}\widehat{\mathcal{Q}}_{\delta}(\xi) = \frac{1}{\delta^d} \int_{Q(0,\delta)} e^{-2\pi i x\cdot \xi} \,dx = \prod_{j=1}^d \frac{1}{\delta} \int_{-\delta/2}^{\delta/2} e^{-2\pi i x_j \xi_j} \,dx_j = \prod_{j=1}^d \frac{\sin(\pi\delta \xi_j)}{\pi\delta \xi_j}\end{align*} $$

(where the j-th term in the product is $1$ if $\xi _j = 0$ ). It follows from the Taylor expansion of $\sin (\cdot )$ that $|x - \sin (x)| \leq C |x|^3$ for some $C>0$ and all $x\in [-1, 1]$ . As the sine function is bounded, we conclude there is some constant $C_1> 0$ (depending on d) for which

$$ \begin{align*}|1 - \widehat{\mathcal{Q}}_{\delta}(\xi)| = \bigg|1 - \prod_{j=1}^d \frac{\sin(\pi\delta \xi_j)}{\pi\delta \xi_j}\bigg| \leq C_1 \sum_{j=1}^d (\delta \xi_j)^2 = C_1 \delta^2 \|\xi\|^2\end{align*} $$

holds for all $\delta>0$ , $\xi \in \mathbb {R}^d$ .

For the second inequality, we use the estimate

$$ \begin{align*} \big|\widehat{\sigma}^{(m-1)}_{U}(\xi)\big| \leq K \|\pi_U \xi\|^{-(m-1)/2}, \end{align*} $$

where $\pi _U \xi $ is the orthogonal projection of $\xi $ onto U and K is an absolute constant. This estimate follows from

$$ \begin{align*}\widehat{\sigma}^{(m-1)}_{U}(\xi) = \int_{\mathbb{R}^d} e^{-2\pi i x\cdot \xi} \,d\sigma^{(m-1)}_{U}(x) = \int_{U} e^{-2\pi i x\cdot \pi_U\xi} \,d\sigma^{(m-1)}_{U}(x)\end{align*} $$

and the well-known asymptotic bound $|\widehat {\sigma }_{\mathbb {R}^m}^{(m-1)}(\xi )| = O(\|\xi \|^{-(m-1)/2})$ for the unit sphere on $\mathbb {R}^m$ (see, for instance, Chapter VIII, Section 3 in Stein’s book [Reference Stein19]). For any $\xi \in \mathbb {R}^d\setminus \{0\}$ , we then have that

$$ \begin{align*} \int_{\textrm{O}(\mathbb{R}^d)} |\widehat{\sigma}^{(m-1)}_{TV}(\xi)|^2 \,d\mu(T) &\leq \int_{\textrm{O}(\mathbb{R}^d)} K^2 \|\pi_{TV} \xi\|^{-(m-1)} \,d\mu(T) \\ &= K^2 \int_{\textrm{O}(\mathbb{R}^d)} \|\pi_{V} (T^{-1}\xi)\|^{-(m-1)} \,d\mu(T) \\ &= K^2 \|\xi\|^{-(m-1)} \int_{\mathbb{S}^{d-1}} \|\pi_{\mathbb{R}^m} y\|^{-(m-1)} \,d\sigma^{(d-1)}_{\mathbb{R}^d}(y), \end{align*} $$

where we performed the change of variables $y = T^{-1} \xi /\|\xi \|$ .

It now suffices to show that the last integral above is finite, which we will do by induction on $d \geq m$ . In the base case where $d=m$ , the integral is clearly equal to $1$ since the projection operator $\pi _{\mathbb {R}^m}$ is the identity. If $d \geq m+1$ , parameterize $\mathbb {S}^{d-1}$ by

$$ \begin{align*}y = (z \sin\theta,\, \cos\theta) \quad \text{for } z\in \mathbb{S}^{d-2}, \theta \in [0, \pi]; \end{align*} $$

denoting by $\omega _{d-1}$ (resp. $\omega _{d-2}$ ) the total Lebesgue measure of the unit sphere of $\mathbb {R}^d$ (resp. $\mathbb {R}^{d-1}$ ), this change of variables gives

$$ \begin{align*}\omega_{d-1} \,d\sigma^{(d-1)}_{\mathbb{R}^d}(y) = \omega_{d-2} (\sin\theta)^{d-2} \,d\sigma^{(d-2)}_{\mathbb{R}^{d-1}}(z) \,d\theta.\end{align*} $$

We then obtain

$$ \begin{align*} \int_{\mathbb{S}^{d-1}} &\|\pi_{\mathbb{R}^m} y\|^{-(m-1)} \,d\sigma^{(d-1)}_{\mathbb{R}^d}(y) \\ &= \frac{1}{\omega_{d-1}} \int_{0}^{\pi} \int_{\mathbb{S}^{d-2}} \big(\sin\theta \,\|\pi_{\mathbb{R}^m} z\|\big)^{-(m-1)} \omega_{d-2} (\sin\theta)^{d-2} \,d\sigma^{(d-2)}_{\mathbb{R}^{d-1}}(z) \,d\theta \\ &= \frac{\omega_{d-2}}{\omega_{d-1}} \bigg(\int_{0}^{\pi} (\sin\theta)^{d-m-1} \,d\theta\bigg) \int_{\mathbb{S}^{d-2}} \|\pi_{\mathbb{R}^m} z\|^{-(m-1)} \,d\sigma^{(d-2)}_{\mathbb{R}^{d-1}}(z) \\ &\leq \frac{\omega_{d-2} \pi}{\omega_{d-1}} \int_{\mathbb{S}^{d-2}} \|\pi_{\mathbb{R}^m} z\|^{-(m-1)} \,d\sigma^{(d-2)}_{\mathbb{R}^{d-1}}(z), \end{align*} $$

and the desired bound follows by induction.

Proof. Let $(v_1, \dots , v_k)$ be a fixed permutation of the points of P. We will work a bit more generally and show that a bound as in the statement of the lemma holds for

$$ \begin{align*}\bigg| \int_{\mathbb{R}^d} \int_{\textrm{O}(\mathbb{R}^d)} f_1(x + T v_1) \cdots f_{k-1}(x + T v_{k-1}) \big( f_k(x + T v_k) - f_k * \mathcal{Q}_{\delta}(x + T v_k) \big) \,d\mu(T) \,dx \bigg|\end{align*} $$

whenever $f_1,\, \dots ,\, f_k:\, Q(0, R) \rightarrow [-1, 1]$ are measurable functions. By our telescoping sum trick, this immediately implies the result.

We first exploit the translation invariance of the problem in order to simplify the argument later on. Let $U \subset \mathbb {R}^d$ denote the $(k-2)$ -dimensional affine hyperplane spanned by $v_1, \dots , v_{k-1}$ , and let $\pi _U v_k$ be the orthogonal projection of $v_k$ onto U (so $\pi _U v_k$ is the point in U which is closest to $v_k$ ). By translating all points in P by $-\pi _U v_k$ , we may assume that U contains the origin (being thus a subspace of $\mathbb {R}^d$ ) and that $v_k$ belongs to its orthogonal complement $U^{\perp }$ . Note that $v_k \neq 0$ since the points in P are affinely independent, and $U^{\perp }$ has dimension $d-k+2 \geq 2$ ; these are the two properties we will need in the proof which require the assumption that P is admissible.

Let $H := \textrm{Stab}^{\textrm{O}(\mathbb {R}^d)}(U)$ denote the subgroup of orthogonal transformations which act trivially on the subspace U and let $\nu _H$ be the Haar measure on H. Let $G := f_k - f_k * \mathcal {Q}_{\delta }$ and, for a given $T\in \textrm{O}(\mathbb {R}^d)$ , define the function $F_T:\, Q(0, R) \rightarrow [-1, 1]$ by

$$ \begin{align*}F_T(x) = \prod_{i=1}^{k-1} f_i(x + Tv_i).\end{align*} $$

The integrand on the expression we wish to bound can then be written more succinctly as $F_T(x) G(x + T v_k)$ . By symmetry of the Haar measure $\mu $ , we conclude that

$$ \begin{align*} \int_{\textrm{O}(\mathbb{R}^d)} F_T(x) \, G(x + T v_k) \,d\mu(T) &= \int_{H} \int_{\textrm{O}(\mathbb{R}^d)} F_{TS}(x) \, G(x + TS v_k) \,d\mu(T) \,d\nu_H(S) \\ &= \int_{\textrm{O}(\mathbb{R}^d)} \int_{H} F_T(x) \, G(x + TS v_k) \,d\nu_H(S) \,d\mu(T), \end{align*} $$

where we have used that $F_{TS} = F_T$ for all $S\in H$ , since by definition, $Sv_i = v_i$ for all $1\leq i\leq k-1$ . Using this identity, we conclude that the expression we wish to bound is at most

(2) $$ \begin{align} \bigg|\int_{\textrm{O}(\mathbb{R}^d)} \bigg(\int_{\mathbb{R}^d} \int_{H} F_T(x) \, G(x + TS v_k) \,d\nu_H(S) \,dx\bigg) d\mu(T) \bigg|. \end{align} $$

Now we concentrate on the expression inside the parenthesis in (2) for some fixed $T\in \textrm{O}(\mathbb {R}^d)$ . We claim that, when S is distributed according to the Haar measure on H, the variable $y := TS(v_k/\|v_k\|)$ is uniformly distributed on the unit sphere of the subspace $TU^{\perp }$ . This follows from the fact that $v_k/\|v_k\|$ is on the unit sphere of $U^{\perp }$ , and $H := \textrm{Stab}^{\textrm{O}(\mathbb {R}^d)}(U)$ is isomorphicFootnote ⁵ to the orthogonal group of $U^{\perp }$ . Denoting by $\sigma ^{(d-k+1)}_{TU^{\perp }}$ the normalized surface measure on the unit sphere of $TU^{\perp }$ , we can then write the expression inside the parenthesis in (2) as

$$ \begin{align*} \int_{\mathbb{R}^d} \int_{\mathbb{R}^d} F_T(x) &\,G(x + \|v_k\|y) \,d\sigma^{(d-k+1)}_{TU^{\perp}}(y) \,dx \\ &= \int_{\mathbb{R}^d} F_T(x) \int_{\mathbb{R}^d} e^{2\pi i x\cdot \xi} \,\widehat{G}(\xi) \,\widehat{\sigma}^{(d-k+1)}_{TU^{\perp}}(-\|v_k\|\xi) \,d\xi \,dx \\ &= \int_{\mathbb{R}^d} \widehat{F}_T(-\xi) \,\widehat{G}(\xi) \,\widehat{\sigma}^{(d-k+1)}_{TU^{\perp}}(-\|v_k\|\xi) \,d\xi. \end{align*} $$

Integrating over $T\in \textrm{O}(\mathbb {R}^d)$ and applying Cauchy-Schwarz to the inner integral, we conclude that (2) is at most

$$ \begin{align*} \int_{\textrm{O}(\mathbb{R}^d)} &\|\widehat{F}_T\|_2 \bigg( \int_{\mathbb{R}^d} |\widehat{G}(\xi)|^2 \,|\widehat{\sigma}^{(d-k+1)}_{TU^{\perp}}(\|v_k\|\xi)|^2 \,d\xi \bigg)^{1/2} d\mu(T) \\ &= \int_{\textrm{O}(\mathbb{R}^d)} \|F_T\|_2 \bigg( \int_{\mathbb{R}^d} |\widehat{f}_k(\xi)|^2 \,|1 - \widehat{\mathcal{Q}}_{\delta}(\xi)|^2 \,|\widehat{\sigma}^{(d-k+1)}_{TU^{\perp}}(\|v_k\|\xi)|^2 \,d\xi \bigg)^{1/2} d\mu(T), \end{align*} $$

where we have used Parseval’s Identity and the convolution identity.

Since $|F_T(x)| \leq |f_1(x + Tv_1)|$ pointwise, it follows that $\|F_T\| \leq \|f_1\|_2$ for all $T \in \textrm{O}(\mathbb {R}^d)$ . Using this inequality and applying Cauchy-Schwarz to the outer integral, we see that the expression above is at most

(3) $$ \begin{align} \|f_1\|_2 \bigg( \int_{\textrm{O}(\mathbb{R}^d)} \int_{\mathbb{R}^d} |\widehat{f}_k(\xi)|^2 \,|1 - \widehat{\mathcal{Q}}_{\delta}(\xi)|^2 \,|\widehat{\sigma}^{(d-k+1)}_{TU^{\perp}}(\|v_k\|\xi)|^2 \,d\xi \,d\mu(T) \bigg)^{1/2}. \end{align} $$

Finally, the double integral in (3) can be bounded using the Fourier estimates given in Lemma 3, as we now show. Divide the integral over $\mathbb {R}^d$ into two parts, corresponding to the bounded region where $\|\xi \| \leq (\delta \|v_k\|)^{-1/2}$ and the unbounded region where $\|\xi \|> (\delta \|v_k\|)^{-1/2}$ . For the bounded region, we note that $|\widehat {\sigma }^{(d-k+1)}_{TU^{\perp }}(\xi )| \leq 1$ for all $T\in \textrm{O}(\mathbb {R}^d)$ , $\xi \in \mathbb {R}^d$ and use the first inequality in Lemma 3 to obtain

$$ \begin{align*} \int_{\textrm{O}(\mathbb{R}^d)} \int_{\|\xi\| \leq (\delta \|v_k\|)^{-1/2}} &|\widehat{f}_k(\xi)|^2 \,|1 - \widehat{\mathcal{Q}}_{\delta}(\xi)|^2 \,|\widehat{\sigma}^{(d-k+1)}_{TU^{\perp}}(\|v_k\|\xi)|^2 \,d\xi \,d\mu(T) \\ &\leq \int_{\textrm{O}(\mathbb{R}^d)} \int_{\|\xi\| \leq (\delta \|v_k\|)^{-1/2}} |\widehat{f}_k(\xi)|^2 \big(C_1 \delta^2 \|\xi\|^2\big)^2 \,d\xi \,d\mu(T) \\ &\leq C_1^2 \delta^2 \|v_k\|^{-2} \|f_k\|_2^2. \end{align*} $$

For the unbounded region, we use the simple estimate $|\widehat {\mathcal {Q}}_{\delta }(\xi )| \leq \|\mathcal {Q}_{\delta }\|_1 = 1$ and the second inequality in Lemma 3 to conclude that

$$ \begin{align*} \int_{\textrm{O}(\mathbb{R}^d)} \int_{\|\xi\|> (\delta \|v_k\|)^{-1/2}} &|\widehat{f}_k(\xi)|^2 \,|1 - \widehat{\mathcal{Q}}_{\delta}(\xi)|^2 \,|\widehat{\sigma}^{(d-k+1)}_{TU^{\perp}}(\|v_k\|\xi)|^2 \,d\xi \,d\mu(T) \\ &\leq \int_{\|\xi\| > (\delta \|v_k\|)^{-1/2}} 4 |\widehat{f}_k(\xi)|^2 \,\int_{\textrm{O}(\mathbb{R}^d)} |\widehat{\sigma}^{(d-k+1)}_{TU^{\perp}}(\|v_k\|\xi)|^2 \,d\mu(T) \,d\xi \\ &\leq 4 \left\|f_k\right\|_2^2 \sup_{\|\xi\| > (\delta \|v_k\|)^{-1/2}} \int_{\textrm{O}(\mathbb{R}^d)} |\widehat{\sigma}^{(d-k+1)}_{TU^{\perp}}(\|v_k\|\xi)|^2 \,d\mu(T) \\ &\leq 4C_2 \,(\delta \|v_k\|^{-1})^{(d-k+1)/2} \|f_k\|_2^2. \end{align*} $$

Summing the bounds obtained for both regions shows that, for $d \geq k$ and $0 < \delta \leq 1$ , we can bound expression (3) by

$$ \begin{align*}\big(C_1^2 \|v_k\|^{-2} + 4C_2 \|v_k\|^{-(d-k+1)/2}\big)^{1/2} \delta^{1/4} \|f_1\|_2 \|f_k\|_2,\end{align*} $$

and the inequality in the statement of the lemma follows. Since this last bound depends continuously on the positioning of the points of P (which gives the value of $\|v_k\|$ ), the claim that the obtained constant $C_P$ can be made uniform inside a neighborhood of P also follows.

Proof. Denote the closed unit ball of $L^{\infty }(Q(0, R))$ by $\mathcal {B}_{\infty }$ . Since $\mathcal {B}_{\infty }$ endowed with the weak $^*$ topology is metrizable (see e.g., [Reference Megginson15, Corollary 2.6.20]), it suffices to prove that $I_P$ is sequentially continuous (i.e., that $I_P(f_i) \xrightarrow {i \rightarrow \infty } I_P(f)$ whenever $f_i \xrightarrow {i \rightarrow \infty } f$ ).

Suppose then $(f_i)_{i \geq 1} \subset \mathcal {B}_{\infty }$ is a sequence weak $^*$ converging to $f \in \mathcal {B}_{\infty }$ . It follows that, for every $x \in Q(0, R)$ and every $\delta> 0$ , we have

$$ \begin{align*} f_i * \mathcal{Q}_{\delta}(x) = \delta^{-d} \int_{Q(x, \delta)} f_i(y) \,dy \,\xrightarrow{i \rightarrow \infty}\, \delta^{-d} \int_{Q(x, \delta)} f(y) \,dy = f * \mathcal{Q}_{\delta}(x). \end{align*} $$

Since $f * \mathcal {Q}_{\delta }$ and each $f_i * \mathcal {Q}_{\delta }$ are Lipschitz with the same constant (depending only on $\delta $ , as $\|f\|_{\infty }$ , $\|f_i\|_{\infty } \leq 1$ ) and $Q(0, R)$ is bounded, this easily implies that

$$ \begin{align*}\|f_i * \mathcal{Q}_{\delta} - f * \mathcal{Q}_{\delta}\|_{\infty} \rightarrow 0 \hspace{3mm} \text{as } i \rightarrow \infty.\end{align*} $$

In particular, it follows that $\lim _{i \rightarrow \infty } I_P(f_i * \mathcal {Q}_{\delta }) = I_P(f * \mathcal {Q}_{\delta })$ .

Since P is admissible, by the Counting Lemma (Lemma 4), we have

$$ \begin{align*}|I_P(f * \mathcal{Q}_{\delta}) - I_P(f)|, \hspace{2mm} |I_P(f_i * \mathcal{Q}_{\delta}) - I_P(f_i)| \leq C_P \delta^{1/4} R^d \hspace{3mm} \text{for all } i \geq 1.\end{align*} $$

Choosing $i_0(\delta ) \geq 1$ sufficiently large so that

$$ \begin{align*}|I_P(f_i * \mathcal{Q}_{\delta}) - I_P(f * \mathcal{Q}_{\delta})| \leq C_P \delta^{1/4} R^d \hspace{5mm} \text{for all } i \geq i_0(\delta),\end{align*} $$

we conclude that

$$ \begin{align*} |I_P(f) - I_P(f_i)| &\leq |I_P(f) - I_P(f * \mathcal{Q}_{\delta})| + |I_P(f * \mathcal{Q}_{\delta}) - I_P(f_i * \mathcal{Q}_{\delta})| \\ & \hspace{1cm} + |I_P(f_i * \mathcal{Q}_{\delta}) - I_P(f_i)| \\ &\leq 3 C_P \delta^{1/4} R^d \hspace{5mm} \text{for all } i \geq i_0(\delta). \end{align*} $$

Since $\delta> 0$ is arbitrary, this implies that $\lim _{i \rightarrow \infty } I_P(f_i) = I_P(f)$ , as wished.

Proof. We will use the fact that the constant $C_P$ promised in the Counting Lemma can be made uniform inside a small neighborhood of P; more precisely, there is $r> 0$ and a constant $\tilde {C}_P> 0$ such that

$$ \begin{align*}|I_{P'}(A) - I_{P'}(A * \mathcal{Q}_{\rho})| \leq \tilde{C}_P \rho^{1/4} R^d \hspace{5mm} \text{for all } \rho \in (0, 1]\end{align*} $$

holds for all $P' \in \mathcal {B}(P, r)$ , $R> 0$ and (measurable) $A \subseteq Q(0, R)$ .

Fix constants $R \geq 1$ and $\delta , \rho \in (0, 1]$ with $\delta < \rho $ . For any set $A \subseteq Q(0, R)$ and any points $x,\, y \in Q(0, R)$ with $\|x - y\| \leq \delta $ , we have that

$$ \begin{align*} |A * \mathcal{Q}_{\rho}(x) - A * \mathcal{Q}_{\rho}(y)| &= \frac{\big| \textrm{vol}(A \cap Q(x,\, \rho)) - \textrm{vol}(A \cap Q(y,\, \rho)) \big|}{\rho^d} \\ &\leq \frac {\textrm{vol}(Q(x,\, \rho) \setminus Q(y,\, \rho))}{\rho^d} \\ &\leq \frac{\rho^d - (\rho - \delta)^d}{\rho^d}. \end{align*} $$

Noting that $A * \mathcal {Q}_{\rho }$ is supported on $Q(0, R+\rho ) \subseteq Q(0, 2R)$ , we conclude from our telescoping sum trick that

$$ \begin{align*}|I_{P'}(A * \mathcal{Q}_{\rho}) - I_P(A * \mathcal{Q}_{\rho})| \leq k \frac{\rho^d - (\rho - \delta)^d}{\rho^d} (2R)^d\end{align*} $$

whenever $\|P' - P\|_{\infty } \leq \delta $ .

Now take $\rho \in (0, 1]$ small enough so that $\tilde {C}_P \rho ^{1/4} \leq \varepsilon /4$ , and for this value of $\rho $ , take $0 < \delta < \min \{r,\, \rho \}$ small enough so that

$$ \begin{align*}(\rho - \delta)^d \geq \Big(1 - \frac{\varepsilon}{2^{d+1} k}\Big) \rho^d.\end{align*} $$

Then, for any configuration $P' \in \mathcal {B}(P,\, \delta )$ and any set $A \subseteq Q(0, R)$ , we obtain

$$ \begin{align*} |I_{P'}(A) - I_P(A)| &\leq |I_{P'}(A) - I_{P'}(A * \mathcal{Q}_{\rho})| + |I_{P'}(A * \mathcal{Q}_{\rho}) - I_P(A * \mathcal{Q}_{\rho})| \\ & \hspace{1cm} + |I_P(A * \mathcal{Q}_{\rho}) - I_P(A)| \\ &\leq \tilde{C}_P \rho^{1/4} R^d + k \frac{\rho^d - (\rho - \delta)^d}{\rho^d} (2R)^d + \tilde{C}_P \rho^{1/4} R^d \\ &\leq \frac{\varepsilon}{4} R^d + k \frac{\varepsilon}{2^{d+1} k} (2R)^d + \frac{\varepsilon}{4} R^d = \varepsilon R^d, \end{align*} $$

as desired.

Proof. Suppose, for contradiction, that the result is false. Then, there exist $\varepsilon> 0$ , $R> 0$ and a sequence $(A_i)_{i \geq 1}$ of subsets of $Q(0, R)$ , each of density at least $\mathbf {m}_{Q(0, R)}(P) + \varepsilon $ , which satisfy $\lim _{i \rightarrow \infty } I_P(A_i) = 0$ .

The unit ball $\mathcal {B}_{\infty }$ of $L^{\infty }(Q(0, R))$ is weak $^*$ compact by the Banach-Alaoglu Theorem, and it is also metrizable in this topology (see [Reference Megginson15, Chapter 2.6]). By possibly restricting to a subsequence, we may then assume that $(A_i)_{i \geq 1}$ converges in the weak $^*$ topology of $L^{\infty }(Q(0, R))$ ; let us denote its limit by $A \in \mathcal {B}_{\infty }$ . It is clear that $0 \leq A \leq 1$ almost everywhere, and

$$ \begin{align*}\frac{1}{R^d} \int_{Q(0, R)} A(x) \,dx = \lim_{i \rightarrow \infty} \frac{1}{R^d} \int_{Q(0, R)} A_i(x) \,dx \geq \mathbf{m}_{Q(0, R)}(P) + \varepsilon.\end{align*} $$

By weak $^*$ continuity of $I_P$ (Lemma 5), we also have $I_P(A) = \lim _{i \rightarrow \infty } I_P(A_i) = 0$ .

Now, let $B := \big \{x \in Q(0, R):\, A(x) \geq \varepsilon \big \}$ . Since

$$ \begin{align*}\varepsilon B(x) \leq A(x) < \varepsilon + B(x) \hspace{3mm} \text{for a.e. } x \in Q(0, R),\end{align*} $$

we conclude that $I_P(B) \leq \varepsilon ^{-k} I_P(A) = 0$ and

$$ \begin{align*}d_{Q(0, R)}(B)> \frac{1}{R^d} \int_{Q(0, R)} A(x) \,d\sigma(x) - \varepsilon \geq \mathbf{m}_{Q(0, R)}(P).\end{align*} $$

But this set B contradicts (WS) (or Lemma 2), finishing the proof.

Proof. Take $R_1> 0$ large enough so that $\mathbf {m}_{Q(0, R_1)}(P) \leq \mathbf {m}_{\mathbb {R}^d}(P) + \varepsilon /4$ (see Lemma 1). We will show that the conclusion of the theorem holds for $R_0 = 4 d R_1/\varepsilon $ and some constant $c> 0$ to be chosen later.

Suppose $R \geq 4 d R_1/\varepsilon $ , and let $A \subseteq Q(0, R)$ be a set of density

$$ \begin{align*}d_{Q(0, R)}(A) \geq \mathbf{m}_{Q(0, R)}(P) + \varepsilon.\end{align*} $$

Since $\mathbf {m}_{Q(0, R_1)}(P) \leq \mathbf {m}_{\mathbb {R}^d}(P) + \varepsilon /4 \leq \mathbf {m}_{Q(0, R)}(P) + \varepsilon /4,$ we have that

$$ \begin{align*}\textrm{vol}(A) = \textrm{vol}\big(A \cap Q(0, R)\big) \geq \big(\mathbf{m}_{Q(0, R_1)}(P) + 3\varepsilon/4\big) R^d.\end{align*} $$

Let $K := \lfloor R/R_1 \rfloor $ , and note that

$$ \begin{align*}K^d R_1^d> \bigg( 1 - \frac{R_1}{R} \bigg)^d R^d \geq \bigg( 1 - \frac{d R_1}{R} \bigg) R^d.\end{align*} $$

By our assumption on R, we conclude that $K^d R_1^d \geq (1 - \varepsilon /4) R^d$ , and thus

$$ \begin{align*} \textrm{vol}\big(A \cap Q(0, K R_1)\big) &\geq \textrm{vol}(A) - \textrm{vol}\big(Q(0, R) \setminus Q(0, K R_1)\big) \\ &\geq \big(\mathbf{m}_{Q(0, R_1)}(P) + \varepsilon/2\big) K^d R_1^d. \end{align*} $$

Partitioning the cube $Q(0, K R_1)$ into $K^d$ cubes of side length $R_1$ , by averaging, we conclude that at least $\varepsilon K^d/4$ of these cubes $Q(x, R_1)$ satisfy

(4) $$ \begin{align} \textrm{vol}\big(A \cap Q(x, R_1)\big) \geq \big(\mathbf{m}_{Q(0, R_1)}(P) + \varepsilon/4\big) R_1^d. \end{align} $$

By Lemma 7, there is some $c_0> 0$ (depending on $R_1$ and $\varepsilon $ but not on A or R) such that $I_P(A \cap Q(x, R_1)) \geq c_0$ holds for each one of the cubes in the partition satisfying (4); summing up all these values, we conclude that

$$ \begin{align*}I_P(A) \geq \frac{\varepsilon K^d}{4} c_0> \frac{\varepsilon c_0}{4} \bigg(\frac{R}{R_1} - 1\bigg)^d \geq \frac{\varepsilon c_0}{4} \frac{1}{(2R_1)^d} R^d,\end{align*} $$

finishing the proof for $c = \varepsilon c_0/(2^{d+2} R_1^d)$ .

Proof. Let $R_0$ , $c> 0$ be the constants promised in the Supersaturation Theorem applied to P and with $\varepsilon $ substituted by $\varepsilon /3$ . Up to substituting $R_0$ by some larger constant, we may also assume that $\mathbf {m}_{Q(0, R)}(P) \leq \mathbf {m}_{\mathbb {R}^d}(P) + \varepsilon /3$ for all $R \geq R_0$ (see Lemma 1).

Suppose $A \subseteq \mathbb {R}^d$ satisfies $\overline {d} \big (\mathcal {Z}_{\delta }(\varepsilon )[A]\big ) \geq \mathbf {m}_{\mathbb {R}^d}(P) + \varepsilon $ for some $0 < \delta \leq 1$ . Since

$$ \begin{align*} \limsup_{R\rightarrow \infty} d_{Q(0,R)} \big(\mathcal{Z}_{\delta}(\varepsilon)[A \cap Q(0,R)]\big) &= \limsup_{R\rightarrow \infty} d_{Q(0,R)} \big(\mathcal{Z}_{\delta}(\varepsilon)[A]\big) \\ &= \overline{d} \big(\mathcal{Z}_{\delta}(\varepsilon)[A]\big) \geq \mathbf{m}_{\mathbb{R}^d}(P) + \varepsilon, \end{align*} $$

there must exist some $R \geq R_0$ such that

$$ \begin{align*}d_{Q(0,R)} \big(\mathcal{Z}_{\delta}(\varepsilon)[A \cap Q(0,R)]\big) \geq \mathbf{m}_{\mathbb{R}^d}(P) + 2\varepsilon/3.\end{align*} $$

Denoting $A' := A\cap Q(0,R)$ , we may then assume that $A' \subseteq Q(0, R)$ satisfies

(5) $$ \begin{align} d_{Q(0, R)} \big(\mathcal{Z}_{\delta}(\varepsilon)[A']\big) \geq \mathbf{m}_{Q(0, R)}(P) + \varepsilon/3 \end{align} $$

for some $R \geq R_0$ , and wish to show that $A'$ (and hence A) contains a copy of P if $\delta> 0$ is small enough depending on P and $\varepsilon $ .

By the Supersaturation Theorem, inequality (5) implies that $I_P \big (\mathcal {Z}_{\delta }(\varepsilon )[A']\big ) \geq c R^d$ . Since $A' * \mathcal {Q}_{\delta }(x) \geq \varepsilon \cdot \mathcal {Z}_{\delta }(\varepsilon )[A'](x)$ for all $x \in \mathbb {R}^d$ , we obtain from the Counting Lemma that

$$ \begin{align*} I_P(A') \geq I_P(A' * \mathcal{Q}_{\delta}) - C_P \delta^{1/4} R^d &\geq \varepsilon^{|P|} I_P \big(\mathcal{Z}_{\delta}(\varepsilon)[A']\big) - C_P \delta^{1/4} R^d \\ &\geq \big(\varepsilon^{|P|} c - C_P \delta^{1/4}\big) R^d. \end{align*} $$

Taking $\delta> 0$ small enough for this last expression to be positive, we conclude that $I_P(A')> 0$ , and so $A'$ contains a copy of P as wished.

Proof. Fix $\varepsilon> 0$ and choose R large enough so that

$$ \begin{align*}\min_{1 \leq i \leq n} (R - \textrm{diam}\, P_i)^d \geq (1 - \varepsilon) R^d.\end{align*} $$

For each $1 \leq i \leq n$ , let $A_i \subseteq Q(0, R - \textrm{diam}\, P_i)$ be a set which avoids $P_i$ and satisfies $d_{Q(0, R - \textrm{diam}\, P_i)}(A_i)> \mathbf {m}_{\mathbb {R}^d}(P_i) - \varepsilon $ (this is possible by Lemma 1). We then construct the R-periodic set $A_i' := A_i + R \mathbb {Z}^d$ , which also avoids $P_i$ and has density

$$ \begin{align*}d(A_i') = \frac{(R - \textrm{diam}\, P_i)^d}{R^d} d_{Q(0, R - \textrm{diam}\, P_i)}(A_i)> \mathbf{m}_{\mathbb{R}^d}(P_i) - 2\varepsilon.\end{align*} $$

Since each set $A_i'$ is periodic with the same fundamental domain $Q(0, R)$ , it follows that the average of $d\big (\bigcap _{i=1}^n (x_i + A_i')\big )$ over independent translates $x_1, \dots , x_n \in Q(0, R)$ is equal to $\prod _{i=1}^n d(A_i')$ . There must then exist some $x_1, \dots , x_n \in Q(0, R)$ for which

$$ \begin{align*}d\bigg(\bigcap_{i=1}^n (x_i + A_i')\bigg) \geq \prod_{i=1}^n d(A_i')> \prod_{i=1}^n (\mathbf{m}_{\mathbb{R}^d}(P_i) - 2\varepsilon).\end{align*} $$

Since $\bigcap _{i=1}^n (x_i + A_i')$ avoids each of the configurations $P_i$ and $\varepsilon> 0$ was arbitrary, the desired lower bound follows.

Proof. We have already seen that

$$ \begin{align*}\mathbf{m}_{\mathbb{R}^d}(t_1 P_1,\, t_2 P_2,\, \dots,\, t_n P_n) \geq \prod_{i=1}^n \mathbf{m}_{\mathbb{R}^d}(t_i P_i) = \prod_{i=1}^n \mathbf{m}_{\mathbb{R}^d}(P_i)\end{align*} $$

always holds, so it suffices to show that $\mathbf {m}_{\mathbb {R}^d}(t_1 P_1,\, t_2 P_2,\, \dots ,\, t_n P_n)$ is no larger than $\prod _{i=1}^n \mathbf {m}_{\mathbb {R}^d}(P_i) + \varepsilon $ whenever $\varepsilon> 0$ and the ratios between consecutive scales $t_i$ are large enough. We shall proceed by induction, with the case $n = 1$ being trivial.

Let $n \geq 2$ and suppose the theorem holds for configurations $P_1, \dots , P_{n-1}$ . Fix $0 < \varepsilon \leq 1$ and let $t_1,\, \dots ,\, t_{n-1}> 0$ be dilation parameters for which

$$ \begin{align*}\mathbf{m}_{\mathbb{R}^d}(t_1 P_1,\, \dots,\, t_{n-1} P_{n-1}) \leq \prod_{i=1}^{n-1} \mathbf{m}_{\mathbb{R}^d}(P_i) + \varepsilon;\end{align*} $$

now, take $R_0> 0$ large enough so that

$$ \begin{align*}\mathbf{m}_{Q(0, R)}(t_1 P_1,\, \dots,\, t_{n-1} P_{n-1}) \leq \mathbf{m}_{\mathbb{R}^d}(t_1 P_1,\, \dots,\, t_{n-1} P_{n-1}) + \varepsilon\end{align*} $$

holds for all $R \geq R_0$ (this quantity exists by Lemma 1).

If $A \subseteq \mathbb {R}^d$ is a measurable set avoiding $t_1 P_1,\, \dots ,\, t_{n-1} P_{n-1}$ , then clearly

(6) $$ \begin{align} d_{Q(x, R)}(A) \leq \mathbf{m}_{Q(0, R)}(t_1 P_1,\, \dots,\, t_{n-1} P_{n-1}) \hspace{5mm} \text{for all } x \in \mathbb{R}^d,\, R> 0. \end{align} $$

Moreover, if A also avoids $t_n P_n$ for some $t_n> 0$ , then $A/t_n$ avoids $P_n$ and so by Corollary 1, there is some $\delta _0> 0$ (depending only on $P_n$ and $\varepsilon $ ) for which

(7) $$ \begin{align} \overline{d}\big(\mathcal{Z}_{\delta}(\varepsilon)[A/t_n]\big) \leq \mathbf{m}_{\mathbb{R}^d}(P_n) + \varepsilon \hspace{5mm} \text{for all } \delta \leq \delta_0. \end{align} $$

Suppose now that $t_n \geq R_0/\delta _0$ and let $A \subseteq \mathbb {R}^d$ be any measurable set avoiding $t_1 P_1,\, \dots ,\, t_n P_n$ . We conclude from (6) that

$$ \begin{align*} d_{Q(x,\, t_n \delta_0)}(A) &\leq \mathbf{m}_{Q(0,\, t_n \delta_0)}(t_1 P_1,\, \dots,\, t_{n-1} P_{n-1}) \\ &\leq \mathbf{m}_{\mathbb{R}^d}(t_1 P_1,\, \dots,\, t_{n-1} P_{n-1}) + \varepsilon \\ &\leq \prod_{i=1}^{n-1} \mathbf{m}_{\mathbb{R}^d}(P_i) + 2\varepsilon \end{align*} $$

holds for all $x \in \mathbb {R}^d$ , and from (7), we have

$$ \begin{align*}\overline{d}\big(\mathcal{Z}_{t_n \delta_0}(\varepsilon)[A]\big) = \overline{d}\big(\mathcal{Z}_{\delta_0}(\varepsilon)[A/t_n]\big) \leq \mathbf{m}_{\mathbb{R}^d}(P_n) + \varepsilon.\end{align*} $$

This means that the density of A inside cubes $Q(x, t_n \delta _0)$ of side length $t_n \delta _0$ is at most $\varepsilon $ (when $x \notin \mathcal {Z}_{t_n \delta _0}(\varepsilon )[A]$ ) except at a set of upper density at most $\mathbf {m}_{\mathbb {R}^d}(P_n) + \varepsilon $ , when it is instead no more than $\prod _{i=1}^{n-1} \mathbf {m}_{\mathbb {R}^d}(P_i) + 2\varepsilon $ . Taking averages, we conclude that

$$ \begin{align*}\overline{d}(A) \leq \varepsilon + \big( \mathbf{m}_{\mathbb{R}^d}(P_n) + \varepsilon \big) \bigg( \prod_{i=1}^{n-1} \mathbf{m}_{\mathbb{R}^d}(P_i) + 2\varepsilon \bigg) \leq \prod_{i=1}^n \mathbf{m}_{\mathbb{R}^d}(P_i) + 6\varepsilon\end{align*} $$

(where we used that $0 < \varepsilon \leq 1$ ). This inequality finishes the proof.

Proof of Theorem 2.

Suppose $A \subset \mathbb {R}^d$ is a measurable set not satisfying the conclusion of the theorem; thus, there is a sequence $(t_j)_{j \geq 1}$ tending to infinity such that A does not contain a copy of any $t_j P$ . This implies that $\overline {d}(A) \leq \mathbf {m}_{\mathbb {R}^d}(t_1 P,\, t_2 P, \dots ,\, t_n P)$ for all $n \in \mathbb {N}$ . By taking a suitably fast-growing subsequence, we may then use Theorem 4 to obtain (say) $\overline {d}(A) \leq 2 \mathbf {m}_{\mathbb {R}^d}(P)^n$ for any fixed $n \geq 1$ . Since $\mathbf {m}_{\mathbb {R}^d}(P) < 1$ ,Footnote ⁶ this implies that $\overline {d}(A) = 0$ , as wished.

Proof. Assume, by dilation invariance, that $t_1 = 1$ , and note that it suffices to show the convergence above with $\mathbf {m}_{\mathbb {R}^d}$ replaced by $\mathbf {m}_{Q(0, R)}$ for every fixed $R> 0$ . We will then fix an arbitrary $R> 0$ and prove that $\mathbf {m}_{Q(0, R)}(P,\, t_2 P,\, \dots ,\, t_n P) \rightarrow \mathbf {m}_{Q(0, R)}(P)$ as $t_2,\, t_3,\, \dots ,\, t_n \rightarrow 1$ .

Let $(v_1, v_2, \dots , v_k)$ be an ordering of the points of P, and consider the continuous function $g_P:\, (\mathbb {R}^d)^k \times \textrm{O}(\mathbb {R}^d) \rightarrow \mathbb {R}$ given by

$$ \begin{align*}g_P(x_1,\, \dots,\, x_k,\, T) := \sum_{j=2}^k \| (x_j - x_1) - T (v_j - v_1) \|.\end{align*} $$

Note that $\min _{T \in \textrm{O}(\mathbb {R}^d)} g_P(x_1,\, \dots ,\, x_k,\, T) = 0$ if and only if $(x_1, \dots , x_k)$ is congruent to $(v_1, \dots , v_k)$ .

Fix some $\varepsilon> 0$ and let $A \subset Q(0, R)$ be a measurable set which avoids P and has density $d_{Q(0, R)}(A) \geq \mathbf {m}_{Q(0, R)}(P) - \varepsilon $ . By inner regularity, we know there exists a compact set $\widetilde {A} \subseteq A$ with $d_{Q(0, R)}(\widetilde {A}) \geq \mathbf {m}_{Q(0, R)}(P) - 2\varepsilon $ . Denote by $\gamma $ the minimum of the continuous function $g_P$ on the compact set $\widetilde {A}^k \times \textrm{O}(\mathbb {R}^d)$ ; since $\widetilde {A}$ avoids P, it follows that $\gamma> 0$ .

We will now prove that $\widetilde {A}$ also avoids $t P$ whenever t is sufficiently close to 1, say when $|t-1| < \gamma /(k \cdot \textrm{diam}\, P)$ . Indeed, for all $x_1, \dots , x_k \in \widetilde {A}$ and all $T \in \textrm{O}(\mathbb {R}^d)$ , by the triangle inequality, we have that

$$ \begin{align*} \sum_{j=2}^k \| (x_j - x_1) - T (t v_j - t v_1) \| &\geq \sum_{j=2}^k \big| \|(x_j - x_1) - T (v_j - v_1)\| - |t-1| \|v_j - v_1\| \big| \\ &> \sum_{j=2}^k \| (x_j - x_1) - T (v_j - v_1) \| - k \cdot |t-1| \,\textrm{diam}\, P \\ &\geq \gamma - k \cdot |t-1| \,\textrm{diam}\, P, \end{align*} $$

which is positive if $|t-1| < \gamma /(k \cdot \textrm{diam}\, P)$ . In particular, we see that

$$ \begin{align*}\mathbf{m}_{Q(0, R)}(P,\, t_2 P,\, \dots,\, t_n P) \geq d_{Q(0, R)}(\widetilde{A}) \geq \mathbf{m}_{Q(0, R)}(P) - 2\varepsilon\end{align*} $$

whenever $|t_j - 1| < \gamma /(k \cdot \textrm{diam}\, P)$ for $2 \leq j \leq n$ . Since we clearly have that $\mathbf {m}_{Q(0, R)}(P,\, t_2 P,\, \dots ,\, t_n P) \leq \mathbf {m}_{Q(0, R)}(P)$ , the result follows.

Proof. For the sake of better readability, we will prove the result in the case of only one forbidden configuration; the n-variable version easily follows from the same argument. Fix some $\varepsilon> 0$ and let $R_1 \geq 1$ be large enough so that

$$ \begin{align*}\mathbf{m}_{\mathbb{R}^d}(P') \leq \mathbf{m}_{Q(0, R)}(P') \leq \mathbf{m}_{\mathbb{R}^d}(P') + \varepsilon\end{align*} $$

holds for all $P' \in \mathcal {B}(P, 1)$ and all $R \geq R_1$ (this value exists by Lemma 1).

Let $R \geq R_1$ and let $A \subset Q(0, R)$ be a compact P-avoiding set with density

$$ \begin{align*}d_{Q(0, R)}(A) \geq \mathbf{m}_{Q(0, R)}(P) - \varepsilon.\end{align*} $$

Proceeding exactly as we did in the proof of the last lemma, we conclude that A also avoids all $P'$ close enough to P; for all such configurations, we then have

$$ \begin{align*}\mathbf{m}_{Q(0, R)}(P') \geq d_{Q(0, R)}(A) \geq \mathbf{m}_{Q(0, R)}(P) - \varepsilon \geq \mathbf{m}_{\mathbb{R}^d}(P) - \varepsilon.\end{align*} $$

Since $\mathbf {m}_{Q(0, R)}(P') \leq \mathbf {m}_{\mathbb {R}^d}(P') + \varepsilon $ whenever $P' \in \mathcal {B}(P, 1)$ , this implies that $\mathbf {m}_{\mathbb {R}^d}(P') \geq \mathbf {m}_{\mathbb {R}^d}(P) - 2\varepsilon $ for all $P'$ close enough to P.

Now, we suppose that P is admissible, and let $R_0$ , $c> 0$ be the constants promised by the Supersaturation Theorem (Theorem 3). Let $R \geq \max \{R_0, R_1\}$ . By equicontinuity (Lemma 6), there is some $\delta> 0$ for which the inequality

(8) $$ \begin{align} |I_{P'}(A) - I_P(A)| < c R^d \hspace{5mm} \text{for all } P' \in \mathcal{B}(P, \delta) \end{align} $$

holds whenever $A \subset Q(0, R)$ is a measurable set; fix such a value of $\delta $ .

If $P' \in \mathcal {B}(P, \delta )$ and $A \subset Q(0, R)$ is a measurable set avoiding $P'$ , we conclude from inequality (8) that $I_P(A) < c R^d$ . By the Supersaturation Theorem, this implies that $d_{Q(0, R)}(A) < \mathbf {m}_{Q(0, R)}(P) + \varepsilon $ , and thus (by optimizing over A), we conclude that $\mathbf {m}_{Q(0, R)}(P') \leq \mathbf {m}_{Q(0, R)}(P) + \varepsilon $ . It follows that

$$ \begin{align*}\mathbf{m}_{\mathbb{R}^d}(P') \leq \mathbf{m}_{Q(0, R)}(P') \leq \mathbf{m}_{Q(0, R)}(P) + \varepsilon \leq \mathbf{m}_{\mathbb{R}^d}(P) + 2\varepsilon\end{align*} $$

whenever $P' \in \mathcal {B}(P, \delta )$ , finishing the proof.

Proof. It is clear that $\mathbf {m}_{\mathbb {R}^d}(t_1 P,\, t_2 P,\, \dots ,\, t_n P) \leq \mathbf {m}_{\mathbb {R}^d}(t_1 P) = \mathbf {m}_{\mathbb {R}^d}(P)$ always holds, and we saw in Lemma 8 that

$$ \begin{align*}\mathbf{m}_{\mathbb{R}^d}(t_1 P,\, t_2 P,\, \dots,\, t_n P) \geq \prod_{i=1}^n \mathbf{m}_{\mathbb{R}^d}(t_i P) = \mathbf{m}_{\mathbb{R}^d}(P)^n.\end{align*} $$

Moreover, Lemma 9 implies that $\mathbf {m}_{\mathbb {R}^d}(P)$ is an accumulation point of the set $\mathcal {M}_n(P)$ , and (since P is admissible) Theorem 4 implies the same about $\mathbf {m}_{\mathbb {R}^d}(P)^n$ . The result follows from continuity of the function

$$ \begin{align*}(t_1,\, t_2,\, \dots,\, t_n) \mapsto \mathbf{m}_{\mathbb{R}^d}(t_1 P,\, t_2 P,\, \dots,\, t_n P),\end{align*} $$

which is an immediate consequence of Theorem 5.

Proof. For each integer $i \geq 1$ , let $A_i \subseteq Q(0, i)$ be a P-avoiding set with density $d_{Q(0, i)}(A_i) \geq \mathbf {m}_{Q(0, i)}(P) - 2^{-i}$ . Denote the unit ball of $L^{\infty }(\mathbb {R}^d)$ by $\mathcal {B}_{\infty }$ ; by the Banach-Alaoglu Theorem, $\mathcal {B}_{\infty }$ is weak $^*$ compact. By restricting to a subsequence if necessary, we may then assume that $(A_i)_{i \geq 1}$ converges to some element $\widetilde {A} \in \mathcal {B}_{\infty }$ in the weak $^*$ topology of $L^{\infty }(\mathbb {R}^d)$ . Denote by $A := \textrm{supp}\, \widetilde {A}$ the support of $\widetilde {A}$ .Footnote ⁷

We will first prove that $I_P(A) = 0$ . Fix some $R> 0$ and (for notational convenience) denote the indicator function of the cube $Q(0, R)$ by $\chi _R$ . Writing $\chi _R A_i$ for the pointwise product of $\chi _R$ and the indicator function of $A_i$ , one easily sees from the definition that $(\chi _R A_i)_{i \geq 1}$ converges to $\chi _R \widetilde {A}$ in the weak $^*$ topology of $L^{\infty }(Q(0, R))$ . As P is admissible, the counting function $I_P$ is weak $^*$ continuous (by Lemma 5) and thus, $I_P(\chi _R \widetilde {A}) = \lim _{i \rightarrow \infty } I_P(\chi _R A_i) = 0$ . We now proceed as in the proof of Lemma 7 to show that $I_P(\textrm{supp}\, \chi _R \widetilde {A}) = 0$ as well: first, approximate $I_P(\textrm{supp}\, \chi _R \widetilde {A})$ by $I_P(B_{\varepsilon })$ , where $B_{\varepsilon } := \{x \in Q(0, R):\, \widetilde {A}(x) \geq \varepsilon \}$ and $\varepsilon> 0$ is a sufficiently small constant (depending on R), and then note that $I_P(B_{\varepsilon }) \leq \varepsilon ^{-|P|} I_P(\chi _R \widetilde {A}) = 0$ for all $\varepsilon> 0$ . Since $\textrm{supp}\, \chi _R \widetilde {A} = A \cap Q(0, R)$ up to zero-measure sets and $R> 0$ is arbitrary, we conclude that $I_P(A) = 0$ as wished.

Next we prove that $d(A) = \mathbf {m}_{\mathbb {R}^d}(P)$ . Since $I_P(A) = 0$ , it follows from Lemma 2 that $\overline {d}(A) \leq \mathbf {m}_{\mathbb {R}^d}(P)$ , and so it suffices to show that

(9) $$ \begin{align} \liminf_{R \rightarrow \infty} d_{Q(0, R)}(A) \geq \mathbf{m}_{\mathbb{R}^d}(P). \end{align} $$

Fix some arbitrary $\varepsilon> 0$ and take $R_0 \geq 2$ large enough so that $(R_0 + 2\textrm{diam}\, P)^d < (1 + \varepsilon /4) R_0^d$ . For any given $R \geq R_0$ , take a P-avoiding set $B_R \subseteq Q(0, R)$ with

$$ \begin{align*}d_{Q(0, R)}(B_R)> \mathbf{m}_{Q(0, R)}(P) - \varepsilon/4 \geq \mathbf{m}_{\mathbb{R}^d}(P) - \varepsilon/4.\end{align*} $$

For all $i \geq R$ , define $A_i' := B_R \cup (A_i \setminus Q(0, R + 2\textrm{diam}\, P))$ ; note that $A_i'$ avoids P and

$$ \begin{align*} \textrm{vol}(A_i') &= \textrm{vol}(A_i) - \textrm{vol}\big(A_i \cap \big( Q(0, R + 2\textrm{diam}\, P) \setminus Q(0, R) \big)\big) \\ &\hspace{1cm} - \textrm{vol}(A_i \cap Q(0, R)) + \textrm{vol}(B_R) \\ &\geq \textrm{vol}(A_i) - \big((R + 2\textrm{diam}\, P)^d - R^d\big) + \textrm{vol}(B_R) - \textrm{vol}(A \cap Q(0, R)) \\ &\hspace{1cm} + \textrm{vol}(A \cap Q(0, R)) - \textrm{vol}(A_i \cap Q(0, R)) \\ &\geq \big(\mathbf{m}_{Q(0, i)}(P) - 2^{-i}\big) i^d - \frac{\varepsilon R^d}{4} + \big(d_{Q(0, R)}(B_R) - d_{Q(0, R)}(A)\big) R^d \\ &\hspace{1cm} + \int_{Q(0, R)} \big(A(x) - A_i(x)\big) \,dx \\ &\geq \big(\mathbf{m}_{Q(0, i)}(P) - 2^{-i}\big) i^d - \frac{\varepsilon R^d}{2} + \big(\mathbf{m}_{\mathbb{R}^d}(P) - d_{Q(0, R)}(A)\big) R^d \\ &\hspace{1cm} + \int_{Q(0, R)} \big(\widetilde{A}(x) - A_i(x)\big) \,dx. \end{align*} $$

Since $\textrm{vol}(A_i') \leq \mathbf {m}_{Q(0, i)}(P)\, i^d$ for all $i \geq R$ and $\int _{Q(0, R)} \big (\widetilde {A}(x) - A_i(x)\big ) \,dx> -\varepsilon $ for all sufficiently large i, we conclude that for large enough i, we have

$$ \begin{align*}d_{Q(0, R)}(A)> \mathbf{m}_{\mathbb{R}^d}(P) - \frac{i^d}{2^i R^d} - \frac{\varepsilon}{2} - \frac{\varepsilon}{R^d} > \mathbf{m}_{\mathbb{R}^d}(P) - \varepsilon,\end{align*} $$

proving inequality (9).

Finally, since $I_P(A) = 0$ , it follows from Lemma 2 that we can remove a zero-measure subset of A in order to remove all copies of P without changing its density. The theorem follows.

Proof. The first three items follow easily from the addition formula (11). Indeed, fix some orthonormal basis $\{Y_i:\, 1\leq i\leq \dim \mathscr {H}_n^{d+1}\}$ of $\mathscr {H}_n^{d+1}$ . Then,

$$ \begin{align*} \big|P_n^d(x\cdot y)\big| &= \bigg|\int_{\textrm{O}(d+1)} P_n^d(Rx\cdot Ry) \,d\mu(R)\bigg| \\ &= \frac{1}{\dim \mathscr{H}_n^{d+1}} \bigg|\int_{\textrm{O}(d+1)} \sum_{i=1}^{\dim \mathscr{H}_n^{d+1}} Y_i(Rx) Y_i(Ry) \,d\mu(R)\bigg|, \end{align*} $$

which by the triangle inequality followed by Cauchy-Schwarz is at most

$$ \begin{align*} \frac{1}{\dim \mathscr{H}_n^{d+1}} \sum_{i=1}^{\dim \mathscr{H}_n^{d+1}} &\bigg(\int_{\textrm{O}(d+1)} Y_i(Rx)^2 \,d\mu(R)\bigg)^{1/2} \bigg(\int_{\textrm{O}(d+1)} Y_i(Ry)^2 \,d\mu(R)\bigg)^{1/2} \\ &= \frac{1}{\dim \mathscr{H}_n^{d+1}} \sum_{i=1}^{\dim \mathscr{H}_n^{d+1}} \bigg(\int_{\mathbb{S}^d} Y_i(z)^2 \,d\sigma(z)\bigg) = 1, \end{align*} $$

proving $(i)$ . Item $(ii)$ follows from the chain of equalities

$$ \begin{align*} \mathrm{{proj}}_n f(x) &= \sum_{i=1}^{\dim \mathscr{H}_n^{d+1}} \bigg(\int_{\mathbb{S}^d} f(y) Y_i(y) \,d\sigma(y)\bigg) Y_i(x) \\ &= \int_{\mathbb{S}^d} \bigg(\sum_{i=1}^{\dim \mathscr{H}_n^{d+1}} Y_i(x) Y_i(y)\bigg) f(y) \,d\sigma(y) \\ &= \dim \mathscr{H}_n^{d+1} \int_{\mathbb{S}^d} P_n^d(x \cdot y) f(y) \,d\sigma(y). \end{align*} $$

To prove item $(iii)$ , note that

$$ \begin{align*} \int_{\mathbb{S}^d} P_n^d(x \cdot y) &P_n^d(x \cdot z) \,d\sigma(x) \\ &= \frac{1}{(\dim \mathscr{H}_n^{d+1})^2} \int_{\mathbb{S}^d} \sum_{i, j = 1}^{\dim \mathscr{H}_n^{d+1}} Y_i(x) Y_i(y) Y_j(x) Y_j(z) \,d\sigma(x) \\ &= \frac{1}{(\dim \mathscr{H}_n^{d+1})^2} \sum_{i, j = 1}^{\dim \mathscr{H}_n^{d+1}} \bigg(\int_{\mathbb{S}^d} Y_i(x) Y_j(x) \,d\sigma(x)\bigg) Y_i(y) Y_j(z) \\ &= \frac{1}{(\dim \mathscr{H}_n^{d+1})^2} \sum_{i=1}^{\dim \mathscr{H}_n^{d+1}} Y_i(y) Y_i(z), \end{align*} $$

which equals the right-hand side of (13) by definition.

Finally, the last item immediately follows from the more precise asymptotic bound given in [Reference Szegő21, Theorem 8.21.6].

Proof. Denote by $\nu _e$ the Haar measure on $\textrm{Stab}(e)$ , and assume without loss of generality that u coincides with the north pole e. By symmetry, the expression we wish to bound may then be written as

$$ \begin{align*} \bigg| \int_{\textrm{O}(\mathbb{R}^{d+1})} f(Re) h(Rv) \,d\mu(R) \bigg| &= \bigg| \int_{\textrm{O}(\mathbb{R}^{d+1})} f(Re) \bigg( \int_{\textrm{Stab}(e)} h(RSv) \,d\nu_e(S) \bigg) \,d\mu(R) \bigg|, \end{align*} $$

where $h = g - g * \textrm{Cap}_{\delta }$ .

Write $t_0 := e \cdot v$ . Note that when $S \in \textrm{Stab}(e)$ is distributed uniformly according to $\nu _e$ , the point $Sv$ is uniformly distributed on $\mathbb {S}^{d-1}_{t_0} := \{ y \in \mathbb {S}^d: e \cdot y = t_0 \}$ . Denote by $\sigma _{t_0}^{(d-1)}$ the uniform probability measure on $\mathbb {S}^{d-1}_{t_0}$ (that is, the unique one which is invariant under the action of $\textrm{Stab}(e)$ ). Making the change of variables $y = Sv$ , we see that

(14) $$ \begin{align} \int_{\textrm{Stab}(e)} h(RSv) \,d\nu_e(S) = \int_{\mathbb{S}^{d-1}_{t_0}} h(Ry) \,d\sigma_{t_0}^{(d-1)}(y) = h * \sigma_{t_0}^{(d-1)}(Re). \end{align} $$

The expression we wish to bound is then equal to

$$ \begin{align*}\bigg| \int_{\textrm{O}(\mathbb{R}^{d+1})} f(Re) \,h * \sigma_{t_0}^{(d-1)}(Re) \,d\mu(R) \bigg| = \bigg| \int_{\mathbb{S}^d} f(x) \,h * \sigma_{t_0}^{(d-1)}(x) \,d\sigma(x) \bigg|.\end{align*} $$

Using Parseval’s Identity, we can rewrite the right-hand side of the last equality as

$$ \begin{align*} \bigg| \sum_{n=0}^{\infty} \int_{\mathbb{S}^d} \mathrm{{proj}}_n f(x) &\,\mathrm{{proj}}_n (h * \sigma_{t_0}^{(d-1)}) (x) \,d\sigma(x) \bigg| \\ &\leq \sum_{n=0}^{\infty} \int_{\mathbb{S}^d} |\mathrm{{proj}}_n f (x)| \, |(\widehat{\sigma}_{t_0}^{(d-1)})_n| \, |\mathrm{{proj}}_n h (x)| \,d\sigma(x) \\ &\leq \sum_{n=0}^{\infty} |(\widehat{\sigma}_{t_0}^{(d-1)})_n| \, \|\mathrm{{proj}}_n f\|_2 \, \|\mathrm{{proj}}_n h\|_2, \end{align*} $$

where we used Theorem 9 and then Cauchy-Schwarz. As $h = g - g * \textrm{Cap}_{\delta }$ , the expression above is equal to

$$ \begin{align*} &\sum_{n=0}^{\infty} |(\widehat{\sigma}_{t_0}^{(d-1)})_n| \, |1 - (\widehat{\textrm{Cap}}_{\delta})_n| \, \|\mathrm{{proj}}_n f\|_2 \, \|\mathrm{{proj}}_n g\|_2 \\ &\hspace{5mm} = \sum_{n=0}^{\infty} |P^d_n(t_0)| \bigg| 1 - \frac{1}{\sigma(\textrm{Cap}_{\delta})} \int_{\textrm{Cap}(e, \delta)} P^d_n(e \cdot y) \,d\sigma(y) \bigg| \|\mathrm{{proj}}_n f\|_2 \, \|\mathrm{{proj}}_n g\|_2. \end{align*} $$

Fix some $\varepsilon> 0$ . Since $t_0 \in [-1 + \gamma ,\, 1 - \gamma ]$ (by hypothesis), from Theorem 8, we obtain that $|P^d_n(t_0)| \leq \varepsilon /2$ holds for all $n \geq N(\varepsilon , \gamma )$ , while

$$ \begin{align*}\bigg| 1 - \frac{1}{\sigma(\textrm{Cap}_{\delta})} \int_{\textrm{Cap}(e, \delta)} P^d_n(e \cdot y) \,d\sigma(y) \bigg| \leq \max_{-1 \leq t \leq 1} \big|1 - P^d_n(t)\big| = 2\end{align*} $$

always holds. Moreover, since each $P^d_n$ is a polynomial satisfying $P^d_n(1) = 1$ , we can choose $\delta _0 = \delta _0(\varepsilon , \gamma )> 0$ small enough so that $|1 - P^d_n(e \cdot y)| \leq \varepsilon $ holds whenever $n < N(\varepsilon , \gamma )$ and $y \in \textrm{Cap}(e, \delta _0)$ . This implies that the last sum is at most

$$ \begin{align*}\sum_{n=0}^{\infty} \varepsilon \|\mathrm{{proj}}_n f\|_2 \, \|\mathrm{{proj}}_n g\|_2 \leq \varepsilon \|f\|_2 \|g\|_2\end{align*} $$

whenever $\delta \leq \delta _0(\varepsilon , \gamma )$ , finishing the proof.

Proof. Up to congruence, we may assume $P \subset \mathbb {S}^d$ . Similarly to what we did in the Euclidean setting, we will first obtain a uniform upper bound for

$$ \begin{align*}\bigg| \int_{\textrm{O}(\mathbb{R}^{d+1})} f_1(Tv_1) \cdots f_{k-1}(Tv_{k-1}) \big( f_k(Tv_k) - f_k * \textrm{Cap}_{\delta} (Tv_k) \big) \,d\mu(T) \bigg|,\end{align*} $$

valid whenever $0 \leq f_1, \dots , f_k \leq 1$ are measurable functions and $(v_1, v_2, \dots , v_k)$ is a permutation of the points of P.

Denote by $G := \textrm{Stab}^{\textrm{O}(\mathbb {R}^{d+1})}(v_1, \dots , v_{k-2})$ the stabilizer of the first $k-2$ points of P, and by $H := \textrm{Stab}^{\textrm{O}(\mathbb {R}^{d+1})}(v_1, \dots , v_{k-2}, v_{k-1}) = \textrm{Stab}^{G}(v_{k-1})$ the stabilizer of the first $k-1$ points of P. We can then bound the expression above by

(15) $$ \begin{align} \int_{\textrm{O}(\mathbb{R}^{d+1})} \bigg| \int_G f_{k-1}(TSv_{k-1}) \big( f_k(TSv_k) - f_k * \textrm{Cap}_{\delta} (TSv_k) \big) \,d\mu_G(S) \bigg| \,d\mu(T), \end{align} $$

where $\mu _G$ denotes the normalized Haar measure on G.

Denote $\ell := d-k+2 \geq 2$ . Since P is nondegenerate, we see that $G \simeq \textrm{O}(\mathbb {R}^{\ell +1})$ and that both $Gv_{k-1}$ and $Gv_k$ are spheres of dimension $\ell $ . Morally, we should then be able to apply the last lemma (with $d = \ell $ , $f = f_{k-1}(T\cdot )$ and $g = f_k(T\cdot )$ ) and easily conclude. However, the convolution in expression (15) above happens in $\mathbb {S}^d$ , while that on the last lemma would happen in $\mathbb {S}^{\ell }$ ; in particular, if $k \geq 3$ so that $\ell < d$ , all of the mass on the average defined by the convolution in (15) lies outside of the $\ell $ -dimensional sphere $Gv_k$ , so this argument cannot work. We will have to work harder to conclude.

Note that since $Gv_k$ is an $\ell $ -dimensional sphere while $Hv_k$ is an $(\ell -1)$ -dimensional sphere (which happens because P is nondegenerate), it follows that there is a point $\xi \in Gv_k$ which is fixed by H; this point will work as the north pole of $Gv_k$ .

It will be more convenient to work on the canonical unit sphere $\mathbb {S}^{\ell }$ instead of the $\ell $ -dimensional sphere $Gv_k \subset \mathbb {S}^d$ . We shall then restrict ourselves to the $(\ell +1)$ -dimensional affine hyperplane $\mathcal {H}$ determined by $\mathcal {H} \cap \mathbb {S}^d = Gv_k$ , and place coordinates on it to identify $\mathcal {H}$ with $\mathbb {R}^{\ell +1}$ and $Gv_k$ with $\mathbb {S}^{\ell }$ , noting that G then acts as $\textrm{O}(\mathbb {R}^{\ell +1})$ . More formally, let $r> 0$ be the radius of $Gv_k$ in $\mathbb {R}^{d+1}$ so that $Gv_k$ is isometric to $r \mathbb {S}^{\ell }$ ; take such an isometry $\psi : Gv_k \rightarrow r \mathbb {S}^{\ell }$ , and define $e \in \mathbb {S}^{\ell }$ by $e := \psi (\xi )/r$ . Now, we construct a map $\phi : G \rightarrow \textrm{O}(\mathbb {R}^{\ell +1})$ defined by

$$ \begin{align*}\phi(S) \psi(x) = \psi(Sx) \hspace{5mm} \text{for all } x \in Gv_k\end{align*} $$

for each $S \in G$ . It is easy to check that this map is well-defined and gives an isomorphism between G and $\textrm{O}(\mathbb {R}^{\ell +1})$ , satisfying $\phi (H) = \textrm{Stab}^{\textrm{O}(\mathbb {R}^{\ell +1})}(e)$ .

For each fixed $T \in \textrm{O}(\mathbb {R}^{d+1})$ , define the functions $g_T, h_T: \mathbb {S}^{\ell } \rightarrow [-1, 1]$ by

$$ \begin{align*} &g_T(Re) := f_{k-1}(T \phi^{-1}(R) v_{k-1}) \hspace{3mm} \text{and} \\ &h_T(Re) := f_k(T \phi^{-1}(R) \xi) - f_k * \textrm{Cap}_{\delta}(T \phi^{-1}(R) \xi), \end{align*} $$

for all $R \in \textrm{O}(\mathbb {R}^{\ell +1})$ . These functions are indeed well-defined on $\mathbb {S}^{\ell }$ since $\textrm{Stab}^G(v_{k-1}) = \textrm{Stab}^G(\xi ) = \phi ^{-1}(\textrm{Stab}^{\textrm{O}(\mathbb {R}^{\ell +1})}(e))$ . Note that $h_T$ can also be written as a function of $x \in \mathbb {S}^{\ell }$ by making use of the isometry $\psi ^{-1}:\, r \mathbb {S}^{\ell }\rightarrow Gv_k$ :

$$ \begin{align*}h_T(x) = f_k(T \psi^{-1}(rx)) - f_k * \textrm{Cap}_{\delta}(T \psi^{-1}(rx)).\end{align*} $$

Denote by $u := \psi (v_k)/r$ the point in $\mathbb {S}^{\ell }$ corresponding to $v_k$ . Making the change of variables $R = \phi (S)$ , we obtain

$$ \begin{align*} \int_G f_{k-1}(TSv_{k-1}) &\big( f_k(TSv_k) - f_k * \textrm{Cap}_{\delta} (TSv_k) \big) \,d\mu_G(S) \\ &= \int_{\textrm{O}(\mathbb{R}^{\ell+1})} g_T(Re) \,h_T(Ru) \,d\mu_{\ell+1}(R) \\ &= \int_{\textrm{O}(\mathbb{R}^{\ell+1})} g_T(Re) \bigg( \int_{\textrm{Stab}(e)} h_T(RSu) \,d\nu_e(S) \bigg) \,d\mu_{\ell+1}(R), \end{align*} $$

where we write $\textrm{Stab}(e)$ for $\textrm{Stab}^{\textrm{O}(\mathbb {R}^{\ell +1})}(e)$ and $\nu _e$ for its Haar measure. Working as we did to obtain equation (14), we see that the expression in parentheses is equal to $h_T * \sigma _{e \cdot u}^{(\ell -1)}(Re)$ , where $\sigma _{e \cdot u}^{(\ell -1)}$ is the uniform probability measure on the $(\ell -1)$ -sphere $\textrm{Stab}(e) u = \{y \in \mathbb {S}^{\ell }: e \cdot y = e \cdot u\}$ (and the convolution now takes place in $\mathbb {S}^{\ell }$ with e as the north pole). Making the change of variables $x = Re$ , we then see that the expression above is equal to

$$ \begin{align*}\int_{\textrm{O}(\mathbb{R}^{\ell+1})} g_T(Re) \,h_T * \sigma_{e \cdot u}^{(\ell-1)}(Re) \,d\mu_{\ell+1}(R) = \int_{\mathbb{S}^{\ell}} g_T(x)\, h_T * \sigma_{e \cdot u}^{(\ell-1)}(x) \,d\sigma^{(\ell)}(x).\end{align*} $$

We conclude that the expression (15) we wish to bound is equal to

$$ \begin{align*} \int_{\textrm{O}(\mathbb{R}^{d+1})} \bigg| \int_{\mathbb{S}^{\ell}} g_T(x) \,h_T * \sigma_{e \cdot u}^{(\ell-1)}(x) \,&d\sigma^{(\ell)}(x) \bigg| \,d\mu_{d+1}(T) \\ &\leq \int_{\textrm{O}(\mathbb{R}^{d+1})} \|h_T * \sigma_{e \cdot u}^{(\ell-1)}\|_2 \,d\mu_{d+1}(T) \\ &\leq \bigg( \int_{\textrm{O}(\mathbb{R}^{d+1})} \|h_T * \sigma_{e \cdot u}^{(\ell-1)}\|_2^2 \,d\mu_{d+1}(T) \bigg)^{1/2}, \end{align*} $$

where we applied Cauchy-Schwarz twice.

Let us now compute $e \cdot u$ , which will be necessary for bounding $\|h_T * \sigma _{e \cdot u}^{(\ell -1)}\|_2^2$ . From the identity

$$ \begin{align*}\|re - ru\|_{\mathbb{R}^{\ell+1}}^2 = \|\psi^{-1}(re) - \psi^{-1}(ru)\|_{\mathbb{R}^{d+1}}^2 = \|\xi - v_k\|_{\mathbb{R}^{d+1}}^2,\end{align*} $$

we conclude that $r^2(2 - 2\, e \cdot u) = 2 - 2\, \xi \cdot v_k$ , and so

$$ \begin{align*}e \cdot u = (\xi \cdot v_k - (1 - r^2))/r^2 \notin \{-1,\, 1\}\end{align*} $$

depends only on the ordering $(v_1, \dots , v_k)$ of P and not on our later choices (note that this value depends continuously on the points $v_1, \dots , v_k$ and so is bounded away from $\{-1,\, 1\}$ uniformly over all configurations $P'$ close enough to P).

Now fix an arbitrary $\varepsilon> 0$ . By Parseval’s Identity and Theorem 9, we have that

$$ \begin{align*} \|h_T * \sigma_{e \cdot u}^{(\ell-1)}\|_2^2 &= \sum_{n=0}^{\infty} \|\mathrm{{proj}}_n (h_T * \sigma_{e \cdot u}^{(\ell-1)})\|_2^2 \\ &= \sum_{n=0}^{\infty} |(\widehat{\sigma}_{e \cdot u}^{(\ell-1)})_n|^2 \,\|\mathrm{{proj}}_n h_T\|_2^2 \\ &= \sum_{n=0}^{\infty} P^{\ell}_n(e \cdot u)^2 \,\|\mathrm{{proj}}_n h_T\|_2^2. \end{align*} $$

Since $e \cdot u \notin \{-1,\, 1\}$ is a constant depending only on P, by Theorem 8, there exists $N = N(\varepsilon , P) \in \mathbb {N}$ such that $|P^{\ell }_n(e \cdot u)| \leq \varepsilon $ for all $n> N$ (by that same theorem, this value of N can be made robust to small perturbations of the value $e \cdot u$ , which corresponds to small perturbations of the configuration P). Using that $|P^{\ell }_n(t)| \leq 1$ for all $-1 \leq t \leq 1$ , we conclude that

$$ \begin{align*}\|h_T * \sigma_{e \cdot u}^{(\ell-1)}\|_2^2 \leq \sum_{n=0}^{N} \|\mathrm{{proj}}_n h_T\|_2^2 + \sum_{n> N} \varepsilon^2 \|\mathrm{{proj}}_n h_T\|_2^2.\end{align*} $$

The second term on the right-hand side of the inequality above is upper bounded by $\varepsilon ^2 \|h_T\|_2^2 \leq \varepsilon ^2$ , so let us concentrate on the first term.

By identities (12) and (13), we have

$$ \begin{align*} \|\mathrm{{proj}}_n h_T\|_2^2 &= \int_{\mathbb{S}^{\ell}} \bigg( \dim \mathscr{H}_n^{\ell+1} \int_{\mathbb{S}^{\ell}} h_T(y) P_n^{\ell}(x \cdot y) \,d\sigma(y) \bigg)^2 \,d\sigma(x) \\ & = (\dim \mathscr{H}_n^{\ell+1})^2 \int_{\mathbb{S}^{\ell}} \int_{\mathbb{S}^{\ell}} h_T(y) h_T(z) \bigg( \int_{\mathbb{S}^{\ell}} P_n^{\ell}(x \cdot y) P_n^{\ell}(x \cdot z) \,d\sigma(x) \bigg) \,d\sigma(y) \,d\sigma(z) \\ & = \dim \mathscr{H}_n^{\ell+1} \int_{\mathbb{S}^{\ell}} \int_{\mathbb{S}^{\ell}} h_T(y) h_T(z) \,P_n^{\ell}(y \cdot z) \,d\sigma(y) \,d\sigma(z). \end{align*} $$

Since $|P_n^{\ell }(y \cdot z)| \leq 1$ for all $y, z \in \mathbb {S}^{\ell }$ , we conclude that

$$ \begin{align*} \int_{\textrm{O}(d+1)} &\|\mathrm{{proj}}_n h_T\|_2^2 \,d\mu_{d+1}(T) \\ &= \dim \mathscr{H}_n^{\ell+1} \int_{\mathbb{S}^{\ell}} \int_{\mathbb{S}^{\ell}} \bigg( \int_{\textrm{O}(d+1)} h_T(y) h_T(z) \,d\mu_{d+1}(T) \bigg) P_n^{\ell}(y \cdot z) \,d\sigma(y) \,d\sigma(z) \\ &\leq \dim \mathscr{H}_n^{\ell+1} \int_{\mathbb{S}^{\ell}} \int_{\mathbb{S}^{\ell}} \bigg| \int_{\textrm{O}(d+1)} h_T(y) h_T(z) \,d\mu_{d+1}(T) \bigg| \,d\sigma(y) \,d\sigma(z). \end{align*} $$

We now divide this last double integral on the sphere into two parts, depending on whether or not $y \cdot z$ is close to the extremal points $1$ or $-1$ . Thus, for some parameter $0 < \gamma < 1$ to be chosen later, we write the double integral as

Since $-1 \leq h_T \leq 1$ , the first term is at most

To bound the second term, note that for fixed $y, z \in \mathbb {S}^{\ell }$ , we have

$$ \begin{align*} \int_{\textrm{O}(d+1)} &h_T(y) h_T(z) \,d\mu_{d+1}(T) \\ &= \int_{\textrm{O}(d+1)} \big(f_k(T\widetilde{y}) - f_k * \textrm{Cap}_{\delta}(T\widetilde{y}) \big) \big(f_k(T\widetilde{z}) - f_k * \textrm{Cap}_{\delta}(T\widetilde{z}) \big) \,d\mu_{d+1}(T), \end{align*} $$

where $\widetilde {y} := \psi ^{-1}(ry)$ and $\widetilde {z} := \psi ^{-1}(rz)$ . Moreover, we have

$$ \begin{align*}\|ry - rz\|_{\mathbb{R}^{\ell+1}}^2 = \|\widetilde{y} - \widetilde{z}\|_{\mathbb{R}^{d+1}}^2 \implies \widetilde{y} \cdot \widetilde{z} = 1 - r^2(1 - y \cdot z);\end{align*} $$

thus, whenever $|y \cdot z| \leq 1-\gamma $ , we have $|\widetilde {y} \cdot \widetilde {z}| \leq 1-r^2\gamma $ . Using Lemma 12 (with $f = f_k - f_k * \textrm{Cap}_{\delta }$ , $g = f_k$ and $\gamma $ substituted by $r^2\gamma $ ), we conclude that the second term is bounded by $c_{d, r^2\gamma }(\delta )$ .

Taking stock of everything, we obtain

$$ \begin{align*} \int_{\textrm{O}(d+1)} &\|h_T * \sigma_{e \cdot u}^{(\ell-1)}\|_2^2 \,d\mu_{d+1}(T) \\ &\leq \varepsilon^2 + \sum_{n=0}^N \dim \mathscr{H}_n^{\ell+1} \big( 2 \sigma^{(\ell)} \big(\textrm{Cap}_{\mathbb{S}^{\ell}}(e, \sqrt{2\gamma})\big) + c_{d, r^2\gamma}(\delta) \big) \end{align*} $$

for any $0 < \gamma < 1$ . Choosing $\gamma $ small enough depending on $\ell $ , $\varepsilon $ and N, and then choosing $\delta $ small enough depending on d, $r^2\gamma $ , $\varepsilon $ and N (so ultimately only on $\varepsilon $ and P), we can bound the right-hand side above by $4\varepsilon ^2$ ; the expression (15) is then bounded by $2 \varepsilon $ in this case.

For such small values of $\delta $ , we thus conclude from our telescoping sum trick (explained in Section 2.1) that $|I_P(A) - I_P(A * \textrm{Cap}_{\delta })| \leq 2k\varepsilon $ , proving the desired inequality since $\varepsilon> 0$ is arbitrary. The claim that the upper bound can be made uniform inside some neighborhood of P follows from analyzing our proof.

Proof. Denote the closed unit ball of $L^{\infty }(\mathbb {S}^d)$ by $\mathcal {B}_{\infty }$ , and let $(f_i)_{i \geq 1} \subset \mathcal {B}_{\infty }$ be a sequence weak $^*$ converging to $f \in \mathcal {B}_{\infty }$ . It will suffice to show that $\left (I_P(f_i)\right )_{i \geq 1}$ converges to $I_P(f)$ .

Note that, for every $x \in \mathbb {S}^d$ , $\delta> 0$ , we have

$$ \begin{align*} f_i * \textrm{Cap}_{\delta}(x) = &\frac{1}{\sigma(\textrm{Cap}_{\delta})} \int_{\textrm{Cap}(x, \delta)} f_i(y) \,d\sigma(y) \\ &\xrightarrow{i \rightarrow \infty} \frac{1}{\sigma(\textrm{Cap}_{\delta})} \int_{\textrm{Cap}(x, \delta)} f(y) \,d\sigma(y) = f * \textrm{Cap}_{\delta}(x). \end{align*} $$

Since $f * \textrm{Cap}_{\delta }$ and each $f_i * \textrm{Cap}_{\delta }$ are Lipschitz with the same constant (depending only on $\delta $ ) and $\mathbb {S}^d$ is compact, this easily implies that

$$ \begin{align*}\|f_i * \textrm{Cap}_{\delta} - f * \textrm{Cap}_{\delta}\|_{\infty} \rightarrow 0 \hspace{3mm} \text{as } i \rightarrow \infty.\end{align*} $$

In particular, we conclude $\lim _{i \rightarrow \infty } I_P(f_i * \textrm{Cap}_{\delta }) = I_P(f * \textrm{Cap}_{\delta })$ .

Since P is admissible, by the spherical Counting Lemma, we have

$$ \begin{align*}|I_P(f * \textrm{Cap}_{\delta}) - I_P(f)| \leq \eta_P(\delta) \hspace{3mm} \text{and} \hspace{3mm} |I_P(f_i * \textrm{Cap}_{\delta}) - I_P(f_i)| \leq \eta_P(\delta) \hspace{3mm} \text{for all } i \geq 1.\end{align*} $$

Choosing $i_0(\delta ) \geq 1$ sufficiently large so that

$$ \begin{align*}|I_P(f_i * \textrm{Cap}_{\delta}) - I_P(f * \textrm{Cap}_{\delta})| \leq \eta_P(\delta) \hspace{5mm} \text{for all } i \geq i_0(\delta),\end{align*} $$

we conclude that

$$ \begin{align*} |I_P(f) - I_P(f_i)| &\leq |I_P(f) - I_P(f * \textrm{Cap}_{\delta})| + |I_P(f * \textrm{Cap}_{\delta}) - I_P(f_i * \textrm{Cap}_{\delta})| \\ & \hspace{1cm} + |I_P(f_i * \textrm{Cap}_{\delta}) - I_P(f_i)| \\ &\leq 3 \eta_P(\delta) \hspace{5mm} \text{for all } i \geq i_0(\delta). \end{align*} $$

Since $\delta> 0$ is arbitrary and $\eta _P(\delta ) \rightarrow 0$ as $\delta \rightarrow 0$ , this finishes the proof.

Proof. We will use the fact that the function $\eta _P$ obtained in the Counting Lemma can be made uniform inside a small ball centered on P. In other words, there is $r> 0$ and a function $\eta _P': (0, 1] \rightarrow (0, 1]$ with $\lim _{t \rightarrow 0} \eta _P'(t) = 0$ such that

$$ \begin{align*}|I_Q(A) - I_Q(A * \textrm{Cap}_{\rho})| \leq \eta_P'(\rho) \quad \text{for all } Q \in \mathcal{B}(P, r), A \subseteq \mathbb{S}^d. \end{align*} $$

Now, for a given $\rho> 0$ and all $0 < \delta < \rho $ , we see from the triangle inequality that

$$ \begin{align*}\|x - y\| \leq \delta \implies \textrm{Cap}(x,\, \rho - \delta) \subset \textrm{Cap}(x,\, \rho) \cap \textrm{Cap}(y,\, \rho),\end{align*} $$

and so $\sigma \big (\textrm{Cap}(x,\, \rho ) \setminus \textrm{Cap}(y,\, \rho )\big ) \leq \sigma (\textrm{Cap}_{\rho }) - \sigma (\textrm{Cap}_{\rho - \delta })$ . This implies that, for any set $A \subseteq \mathbb {S}^d$ and any $x,\, y \in \mathbb {S}^d$ with $\|x - y\| \leq \delta $ , we have

$$ \begin{align*} |A * \textrm{Cap}_{\rho}(x) - A * \textrm{Cap}_{\rho}(y)| &= \frac{\big| \sigma(A \cap \textrm{Cap}(x,\, \rho)) - \sigma(A \cap \textrm{Cap}(y,\, \rho)) \big|}{\sigma(\textrm{Cap}_{\rho})} \\ &\leq \frac{\sigma \big(\textrm{Cap}(x,\, \rho) \setminus \textrm{Cap}(y,\, \rho)\big)}{\sigma(\textrm{Cap}_{\rho})} \\ &\leq \frac{\sigma(\textrm{Cap}_{\rho}) - \sigma(\textrm{Cap}_{\rho - \delta})}{\sigma(\textrm{Cap}_{\rho})}. \end{align*} $$

By our telescoping sum trick, whenever $\|Q - P\|_{\infty } \leq \delta $ , we conclude that

$$ \begin{align*}|I_Q(A * \textrm{Cap}_{\rho}) - I_P(A * \textrm{Cap}_{\rho})| \leq k \frac{\sigma(\textrm{Cap}_{\rho}) - \sigma(\textrm{Cap}_{\rho - \delta})}{\sigma(\textrm{Cap}_{\rho})}.\end{align*} $$

Take $\rho> 0$ small enough so that $\eta _P'(\rho ) \leq \varepsilon /3$ , and for this value of $\rho $ take $0 < \delta < r$ small enough so that $\sigma (\textrm{Cap}_{\rho - \delta }) \geq (1 - \varepsilon /3k) \,\sigma (\textrm{Cap}_{\rho })$ . Then, for any $Q \in \mathcal {B}(P,\, \delta )$ and any measurable set $A \subseteq \mathbb {S}^d$ , we have

$$ \begin{align*} |I_Q(A) - I_P(A)| &\leq |I_Q(A) - I_Q(A * \textrm{Cap}_{\rho})| + |I_Q(A * \textrm{Cap}_{\rho}) - I_P(A * \textrm{Cap}_{\rho})| \\ & \hspace{1cm} + |I_P(A * \textrm{Cap}_{\rho}) - I_P(A)| \\ &\leq \eta_P'(\rho) + k \frac{\sigma(\textrm{Cap}_{\rho}) - \sigma(\textrm{Cap}_{\rho - \delta})}{\sigma(\textrm{Cap}_{\rho})} + \eta_P'(\rho) \\ &\leq \frac{\varepsilon}{3} + k \frac{\varepsilon}{3k} + \frac{\varepsilon}{3} = \varepsilon, \end{align*} $$

as wished.

Proof. Suppose, for contradiction, that the result is false; then, there exist some $\varepsilon> 0$ and some sequence $(A_i)_{i \geq 1}$ of sets, each of density at least $\mathbf {m}_{\mathbb {S}^d}(P) + \varepsilon $ , which satisfy $\lim _{i \rightarrow \infty } I_P(A_i) = 0$ .

Note that the unit ball $\mathcal {B}_{\infty }$ of $L^{\infty }(\mathbb {S}^d)$ is weak $^*$ compact and also metrizable in this topology (see [Reference Megginson15, Chapter 2.6]). By possibly restricting to a subsequence, we may then assume that $(A_i)_{i \geq 1}$ converges in the weak $^*$ topology of $L^{\infty }(\mathbb {S}^d)$ ; let us denote its limit by $A \in \mathcal {B}_{\infty }$ . It is clear that $0 \leq A \leq 1$ almost everywhere, and $\int _{\mathbb {S}^d} A(x) \,d\sigma (x) = \lim _{i \rightarrow \infty } \sigma (A_i) \geq \mathbf {m}_{\mathbb {S}^d}(P) + \varepsilon $ . By weak $^*$ continuity of $I_P$ (Lemma 14), we also have $I_P(A) = \lim _{i \rightarrow \infty } I_P(A_i) = 0$ .

Now let $B := \{x \in \mathbb {S}^d:\, A(x) \geq \varepsilon \}$ . Since

$$ \begin{align*}\varepsilon B(x) \leq A(x) < \varepsilon + B(x) \quad \text{for a.e. } x \in \mathbb{S}^d,\end{align*} $$

we conclude that $I_P(B) \leq \varepsilon ^{-|P|} I_P(A) = 0$ and

$$ \begin{align*}\sigma(B)> \int_{\mathbb{S}^d} A(x) \,d\sigma(x) - \varepsilon \geq \mathbf{m}_{\mathbb{S}^d}(P).\end{align*} $$

But this set B contradicts Lemma 11, finishing the proof.

Proof. By the Supersaturation Theorem, we know that

$$ \begin{align*}\sigma \big(\mathcal{Z}_{\delta}(\varepsilon)[A]\big) \geq \mathbf{m}_{\mathbb{S}^d}(P) + \varepsilon \implies I_P \big(\mathcal{Z}_{\delta}(\varepsilon)[A]\big) \geq c(\varepsilon)\end{align*} $$

holds for all $\delta> 0$ . By the Counting Lemma, we then have

$$ \begin{align*} I_P(A) \geq I_P(A * \textrm{Cap}_{\delta}) - \eta_P(\delta) &\geq \varepsilon^{|P|} I_P \big(\mathcal{Z}_{\delta}(\varepsilon)[A]\big) - \eta_P(\delta) \\ &\geq \varepsilon^{|P|} c(\varepsilon) - \eta_P(\delta). \end{align*} $$

Since $\eta _P(\delta ) \rightarrow 0$ as $\delta \rightarrow 0$ , there is some $\delta _0> 0$ such that for all $\delta \leq \delta _0$ , we can conclude $I_P(A)> 0$ ; this implies that A contains a copy of P.

Proof. We will use the same notation for both a collection of caps and the set of points on $\mathbb {S}^d$ which belong to (at least) one of these caps. The desired packing $\mathcal {P}$ will be constructed in several steps, starting with $\mathcal {P}_0 := \{\textrm{Cap}(e, \varepsilon )\}$ .

Now, suppose $\mathcal {P}_{i-1}$ has already been constructed (and is finite) for some $i \geq 1$ and let us construct $\mathcal {P}_i$ . Define

$$ \begin{align*}\mathcal{C}_i := \big\{ \textrm{Cap} \big( x,\, \min\{\varepsilon,\, \textrm{dist}(x, \mathcal{P}_{i-1})\} \big):\, x\in \mathbb{S}^d \setminus \mathcal{P}_{i-1} \big\},\end{align*} $$

and note that $\mathcal {C}_i$ is a covering of $\mathbb {S}^d \setminus \mathcal {P}_{i-1}$ by caps of positive radii (since $\mathcal {P}_{i-1}$ is closed on $\mathbb {S}^d$ ). By the Vitali Covering Lemma, there is a countable subcollection

$$ \begin{align*}\mathcal{Q}_i = \bigcup_{j=1}^{\infty} \{\textrm{Cap}(x_j, r_j)\} \subset \mathcal{C}_i\end{align*} $$

of disjoint caps in $\mathcal {C}_i$ such that $\mathbb {S}^d \setminus \mathcal {P}_{i-1} \subseteq \bigcup _{j=1}^{\infty } \textrm{Cap}(x_j, 5r_j)$ . In particular,

$$ \begin{align*}1 - \sigma(\mathcal{P}_{i-1}) = \sigma(\mathbb{S}^d \setminus \mathcal{P}_{i-1}) \leq \sum_{j=1}^{\infty} \sigma(\textrm{Cap}(x_j, 5r_j)) \leq K_d \,\sigma(\mathcal{Q}_i),\end{align*} $$

where we denote $K_d := \sup _{r> 0} \sigma (\textrm{Cap}_{5r})/\sigma (\textrm{Cap}_r) < \infty $ . Taking $N_i \in \mathbb {N}$ such that

$$ \begin{align*}\sum_{j=1}^{N_i} \sigma(\textrm{Cap}(x_j, r_j)) \geq \sigma(\mathcal{Q}_i) - \frac{1 - \sigma(\mathcal{P}_{i-1})}{2 K_d},\end{align*} $$

we see that $\mathcal {P}_i' := \{\textrm{Cap}(x_j, r_j):\, 1 \leq j \leq N_i\} \subset \mathbb {S}^d \setminus \mathcal {P}_{i-1}$ satisfies

$$ \begin{align*}\sigma(\mathcal{P}_i') \geq \frac{1 - \sigma(\mathcal{P}_{i-1})}{2 K_d}.\end{align*} $$

Now, set $\mathcal {P}_i := \mathcal {P}_{i-1} \cup \mathcal {P}_i'$ ; this is a finite cap packing with

$$ \begin{align*} 1 - \sigma(\mathcal{P}_i) = 1 - \sigma(\mathcal{P}_{i-1}) - \sigma(\mathcal{P}_i') &\leq (1 - \sigma(\mathcal{P}_{i-1})) \bigg(1 - \frac{1}{2 K_d}\bigg) \\ &\leq (1 - \sigma(\textrm{Cap}_{\varepsilon})) \bigg(1 - \frac{1}{2 K_d}\bigg)^i \end{align*} $$

(where the last inequality follows by induction). Taking $n \geq 1$ large enough so that $(1 - \sigma (\textrm{Cap}_{\varepsilon })) \Big (1 - \frac {1}{2 K_d}\Big )^n < \varepsilon $ , we see that $\mathcal {P} := \mathcal {P}_n$ satisfies all requirements.

Proof. If $A \subset \mathbb {S}^d$ is a set which avoids $P_1, \dots , P_n$ , then for every $x \in \mathbb {S}^d$ , the set $A \cap \textrm{Cap}(x, \rho ) \subseteq \textrm{Cap}(x, \rho )$ also avoids $P_1, \dots , P_n$ . Since $\mathbb {E}_{x \in \mathbb {S}^d}[d_{\textrm{Cap}(x, \rho )}(A)] = \sigma (A)$ , there must exist some $x \in \mathbb {S}^d$ such that

$$ \begin{align*}d_{\textrm{Cap}(x, \rho)}(A \cap \textrm{Cap}(x, \rho)) = d_{\textrm{Cap}(x, \rho)}(A) \geq \sigma(A);\end{align*} $$

optimizing over A, we conclude that $\mathbf {m}_{\textrm{Cap}(x, \rho )}(P_1,\, \dots ,\, P_n) \geq \mathbf {m}_{\mathbb {S}^d}(P_1,\, \dots ,\, P_n)$ .

For the opposite direction, let $\gamma \leq \varepsilon /4$ be small enough so that $\sigma (\textrm{Cap}_{\rho + \gamma }) \leq (1 + \varepsilon /4)\, \sigma (\textrm{Cap}_{\rho })$ . By Lemma 16, we know there is a cap packing

$$ \begin{align*}\mathcal{P} = \{\textrm{Cap}(x_i, \rho_i):\, 1 \leq i \leq N\}\end{align*} $$

of $\mathbb {S}^d$ with $\sigma (\mathcal {P}) \geq 1 - \gamma $ and $0 < \rho _1, \dots , \rho _N \leq \gamma $ . Now, let $t_0> 0$ be small enough so that $\sigma (\textrm{Cap}_{\rho _i - 2t_0}) \geq (1 - \varepsilon /4)\, \sigma (\textrm{Cap}_{\rho _i})$ for all $1 \leq i \leq N$ ; note that $t_0$ will ultimately depend only on $\varepsilon $ and  $\rho $ .

Fixing any configurations $P_1, \dots , P_n \subset \mathbb {S}^d$ of diameter at most $t_0$ , let $A \subset \textrm{Cap}(x, \rho )$ be a set which avoids all of them. We shall construct a set $\widetilde {A} \subset \mathbb {S}^d$ which also avoids $P_1, \dots , P_n$ , and which satisfies $\sigma (\widetilde {A})> d_{\textrm{Cap}(x, \rho )}(A) - \varepsilon $ ; this will finish the proof.

For each $1 \leq i \leq N$ , denote $\widetilde {\rho }_i := \rho _i - 2t_0 < \gamma $ . We have that

$$ \begin{align*} \sigma(A) &= \int_{\mathbb{S}^d} d_{\textrm{Cap}(y, \widetilde{\rho}_i)}(A) \,d\sigma(y) \\ &= \int_{\textrm{Cap}(x,\, \rho + \widetilde{\rho}_i)} d_{\textrm{Cap}(y, \widetilde{\rho}_i)}(A) \,d\sigma(y) \\ &\leq \int_{\textrm{Cap}(x,\, \rho)} d_{\textrm{Cap}(y, \widetilde{\rho}_i)}(A) \,d\sigma(y) + \sigma(\textrm{Cap}_{\rho + \widetilde{\rho}_i}) - \sigma(\textrm{Cap}_{\rho}). \end{align*} $$

Since $\widetilde {\rho }_i < \gamma $ , dividing by $\sigma (\textrm{Cap}_{\rho })$ , we obtain

$$ \begin{align*} \mathbb{E}_{y \in \textrm{Cap}(x, \rho)} \left[ d_{\textrm{Cap}(y, \widetilde{\rho}_i)}(A) \right] &\geq \frac{\sigma(A)}{\sigma(\textrm{Cap}_{\rho})} - \frac{\sigma(\textrm{Cap}_{\rho + \widetilde{\rho}_i}) - \sigma(\textrm{Cap}_{\rho})}{\sigma(\textrm{Cap}_{\rho})} \\ &> d_{\textrm{Cap}(x, \rho)}(A) - \frac{\varepsilon}{4}. \end{align*} $$

There must then exist $y_i \in \textrm{Cap}(x,\, \rho )$ for which $d_{\textrm{Cap}(y_i, \widetilde {\rho }_i)}(A)> d_{\textrm{Cap}(x, \rho )}(A) - \varepsilon /4$ ; fix one such $y_i$ for each $1 \leq i \leq N$ , and let $T_{y_i \rightarrow x_i} \in \textrm{O}(\mathbb {R}^{d+1})$ be any rotation taking $y_i$ to $x_i$ (and thus taking $\textrm{Cap}(y_i,\, \widetilde {\rho }_i)$ to $\textrm{Cap}(x_i,\, \widetilde {\rho }_i)$ ).

We claim that the set

$$ \begin{align*}\widetilde{A} := \bigcup_{i=1}^N T_{y_i \rightarrow x_i} (A \cap \textrm{Cap}(y_i,\, \widetilde{\rho}_i))\end{align*} $$

satisfies our requirements. Indeed, we have

$$ \begin{align*} \sigma(\widetilde{A}) = \sum_{i=1}^N \sigma(A \cap \textrm{Cap}(y_i,\, \widetilde{\rho}_i)) &= \sum_{i=1}^N d_{\textrm{Cap}(y_i, \widetilde{\rho}_i)}(A) \cdot \sigma(\textrm{Cap}_{\widetilde{\rho}_i}) \\ &> \sum_{i=1}^N \left( d_{\textrm{Cap}(x, \rho)}(A) - \frac{\varepsilon}{4} \right) \cdot \left( 1 - \frac{\varepsilon}{4} \right) \sigma(\textrm{Cap}_{\rho_i}) \\ &\geq \left( d_{\textrm{Cap}(x, \rho)}(A) - \frac{\varepsilon}{2} \right) \sigma(\mathcal{P}) \\ &> d_{\textrm{Cap}(x, \rho)}(A) - \varepsilon. \end{align*} $$

Moreover, since $\textrm{diam}\,(P_j) \leq t_0$ and the caps $\textrm{Cap}(x_i,\, \widetilde {\rho }_i)$ are (at least) $2t_0$ -distant from each other, we see that any copy of $P_j$ in $\widetilde {A} \subset \bigcup _{i=1}^N \textrm{Cap}(x_i,\, \widetilde {\rho }_i)$ must be entirely contained in one of the the caps $\textrm{Cap}(x_i,\, \widetilde {\rho }_i)$ . But then it should also be contained (after rotation by $T_{y_i \rightarrow x_i}^{-1}$ ) in $A \cap \textrm{Cap}(y_i,\, \widetilde {\rho }_i)$ ; this shows that $\widetilde {A}$ does not contain copies of $P_j$ for any $1 \leq j \leq N$ , since A does not, and we are done.