Proof of Proposition 2.1.

We scale the problem by $\delta ^{-1}$ , so that the $\delta $ -atoms are now $1$ -atoms and the $\delta $ -tubes are now $1$ -tubes in $[0,\delta ^{-1}]^d$ . This will be more convenient to work with.

For any $a \in A$ and any $t\in T$ , let $\chi _a(x)$ and $\chi _t(x)$ , respectively, be smooth bump functions approximating the indicator functions for the atom a and the tube t. Now let $f(x) := \sum _{a\in A} w(a)\chi _a(x)$ and $g(x) := \sum _{t\in T} \chi _t(x)$ . In this notation,

$$ \begin{align*}\mathcal{I}(A,T) \sim \int_{[0,\delta^{-1}]^d} f(x)g(x)\,dx. \end{align*} $$

Since f and g are Lebesgue integrable functions, their Fourier transforms are well defined. Furthermore, since they are all bounded and supported on compact sets, they are $L_p$ functions for all p. It follows that Plancherel’s theorem holds: $\int f(x)g(x)\,dx = \int \hat {f}(\xi )\overline {\hat {g}(\xi )}\,d\xi $ . Decompose the above into high and low frequency parts:

$$ \begin{align*} \mathcal{I}(A,T) \sim \int \hat{f} \, \overline{\hat{g}}\, \eta + \int \hat{f} \, \overline{\hat{g}} \, (1-\eta), \end{align*} $$

where $\eta $ is a smooth function taking value $1$ on the ball of radius $\rho := \delta ^{-\alpha /d}S^{-1}$ and supported on a ball of radius $2\rho $ .

Low frequency case: Assume $\mathcal {I}(A,T) \lesssim \int \hat {f}\,\overline {\hat {g}}\, \eta $ . By Plancherel (and using that $\eta ^2 \approx \eta $ ),

$$ \begin{align*} \mathcal{I}(A,T) \lesssim \int (\,f \ast h) (g \ast h), \end{align*} $$

where $\overline {\hat {h}} = \eta $ . Roughly speaking, convolution with h thickens atoms and tubes by a factor of $\rho ^{-1}$ . For each atom $a \in A$ , the function $\chi _a \ast h$ is approximately $w(a) \rho ^d$ on the thickened $\rho ^{-1}$ -atom around a. Similarly, for each tube $t \in T$ , the function $\chi _t \ast h$ is approximately $\rho ^{d-1}$ on the thickened $\rho ^{-1}$ -tube around t.

Outside of these $\rho ^{-1}$ -atoms and $\rho ^{-1}$ -tubes, the functions $f\ast h$ and $g\ast h$ are rapidly decaying. Since $S = \delta ^{-\alpha /d} \rho ^{-1}$ , the tails of both functions are negligible outside the S-atoms $A^S$ and S-tubes $T^S$ . It follows that

$$ \begin{align*}\mathcal{I}(A,T) \lesssim \int (\,f \ast h) (g \ast h) \lesssim \rho^{d-1} \mathcal{I}(A^S,T^S) \lesssim \delta^{-\alpha} S^{1-d} \mathcal{I}(A^S,T^S). \end{align*} $$

High frequency case: Assume that $\mathcal {I}(A,T) \lesssim \int \hat {f}\,\overline {\hat {g}}\, (1-\eta )$ . Using the Cauchy–Schwarz inequality,

(2-2) $$ \begin{align} \int \hat{f}(\xi)\overline{\hat{g}(\xi)} (1-\eta(\xi))\,d\xi \leq \bigg(\int |\hat{f}(\xi)|^2 \,d\xi\bigg)^{1/2} \bigg(\int |\hat{g}(\xi)|^2 (1-\eta(\xi))^2 \,d\xi\bigg)^{1/2}. \end{align} $$

By Parseval’s identity, the first term on the right-hand side can be evaluated as

$$ \begin{align*}\bigg(\int |\hat{f}(\xi)|^2 \,d\xi\bigg)^{1/2} = \bigg(\int |f(x)|^2 \,dx\bigg)^{1/2} \sim \bigg(\sum_{a\in A} w(a)^2\bigg)^{1/2}.\end{align*} $$

We now estimate the second term on the right-hand side of Equation (2-2). Cover the d-dimensional unit sphere $S^{d-1} := \{ x \in \mathbb {R}^d : \|x\| = 1 \}$ with small $(d-1)$ -dimensional $\delta $ -balls. These will be called $\delta $ -caps and are used to sort tubes in T by direction. Let $T_\theta $ be the set of all tubes from T in the direction of $\delta $ -cap $\theta $ , and let $g_\theta = \sum _{t \in T_\theta } \chi _t$ . Then we need to estimate

$$ \begin{align*} \int |\hat{g}(\xi)|^2 (1-\eta(\xi))^2 \,d\xi = \int \bigg|\sum_\theta \hat{g_\theta}(\xi)\bigg|^2 (1-\eta(\xi))^2 \,d\xi. \end{align*} $$

We apply Cauchy–Schwarz to the sum over $\theta $ . The advantage is that for fixed $\xi $ , there are not many values of $\theta $ for which $\hat {g_\theta }(\xi )$ is nonzero.

For each $t \in T_\theta $ , we have that $\hat {\chi _t}$ is mostly supported on a $1\times \cdots \times 1 \times \delta $ slab orthogonal to $\theta $ and decays quickly outside. We call this slab $\theta ^\perp $ . Due to the rapidly decaying tails, the contribution of $\hat {g_\theta }$ outside the dilated slab $\delta ^{-\alpha /d}\theta ^\perp $ is of the order $\delta ^{B}$ for some positive B, and is therefore negligible.

Thus, the term $\hat {g_\theta }(\xi )$ is only nonzero if $\xi $ belongs to $\delta ^{-\alpha /d} \theta ^\perp $ . We may assume that $|\xi | \geq \rho $ , as $1-\eta (\xi )$ is otherwise zero. For such a large $\xi $ , simple geometric arguments show that $\xi $ belongs to $\delta ^{-\alpha /d} \theta ^\perp $ for at most $\lesssim \delta ^{-\alpha /d} \rho ^{-1} \delta ^{-(d-2)} = S\delta ^{-(d-2)}$ different $\theta $ values. Then Cauchy–Schwarz yields

$$ \begin{align*} (1-\eta(\xi))^2\bigg|\sum_\theta \hat{g_\theta}(\xi)\bigg|^2 \lesssim S\delta^{-(d-1)} \sum_{\theta} |\hat{g_\theta}(\xi)|^2.\end{align*} $$

Again using Parseval’s identity, it follows that

$$ \begin{align*}&\int |\hat{g}(\xi)|^2 (1-\eta(\xi))^2 \,d\xi \lesssim S\delta^{-(d-2)} \sum_\theta \int |\hat{g_\theta}(\xi)|^2 \,d\xi\\ &\quad= S\delta^{-(d-2)} \sum_\theta \int |g_\theta(x)|^2 \,dx = S\delta^{-(d-1)}|T|.\end{align*} $$

Substituting into Equation (2-2) yields

$$ \begin{align*}\mathcal{I}(A,T) \lesssim \bigg(S\delta^{-(d-1)}|T|\sum_{a\in A}w(a)^2\bigg)^{1/2}. \end{align*} $$

Proof of Theorem 1.4.

We treat $\epsilon $ and d as constants, so in what follows, $\lesssim $ is written to mean $\lesssim _{\epsilon ,d}$ . We fix W and proceed by induction on $\delta $ . Namely, we have to prove the statement for all $\delta \in (0,W^{-1})$ . There are two base cases because when we apply the induction hypothesis, it will be for a smaller value of both W and $\delta ^{-1}$ .

The first base case will be when $\delta $ is very close to $W^{-1}$ , namely, when $\delta ^{-(1-c_1\epsilon )} \leq W$ for some small fixed $c_1$ (we choose $c_1<1/(d-1)$ which assists in the following calculation). Assuming $\delta ^{-(1-c_1\epsilon )} \leq W$ , Equation (1-4) gives

$$ \begin{align*} k \geq C_1(\epsilon,d) W^{d - ({d-1-\epsilon})/({1-c_1\epsilon})}> C_1(\epsilon,d) W.\end{align*} $$

Since the distribution of atoms permits $|T_k(A)|$ to be nonzero only if $k\lesssim W$ , we can choose $C_1({\epsilon },d)$ large enough so that $|T_k(A)| = 0$ , and Equation (1-5) holds trivially.

The other base case is when W is very small, say smaller than some constant $c_2$ . In this case, $|T_k(A)| \leq c_2^{2d}$ trivially, so Equation (1-5) holds for a suitable choice of $C_2(\epsilon ,d)$ .

We move on to the induction step. Assume the result holds for all $\delta '> K\delta $ and $W^{{\prime}{-1}}> KW^{-1}$ , where K is sufficiently small ( $K = 2$ will work). Assume Equation (1-4) holds.

First, we split up $[0,1]^d$ into $D^d$ sub-cubes or cells, where $D = \delta ^{-c_1^2 \epsilon ^2}$ . Let a tubelet be the intersection of a k-rich $\delta $ -tube with one of these cells. (A tubelet looks like a section of a $\delta $ -tube of length $D^{-1}$ .) To each tubelet t we associate a weight $w(t)$ which is the number of atoms from A intersecting t, and a multiplicity $m(t)$ which is the number of k-rich tubes containing the tubelet t. (A tubelet is ‘contained’ in a tube if all the atoms on the tubelet also intersect the tube. A tubelet may lie on up to $D^{d-1} k$ -rich tubes.) From here on, we often abbreviate $T_k = T_k(A)$ . With this notation, it is evident that

$$ \begin{align*} k|T_k| = \mathcal{I}(A,T_k) = \sum_{\text{tubelets }t} w(t)m(t). \end{align*} $$

It is also clear that

$$ \begin{align*}\sum_{\text{tubelets }t} m(t) = D|T_k|,\end{align*} $$

so by the pigeonhole principle, a positive proportion of the incidences come from tubelets t with $w(t) \gtrsim k/D$ (with an appropriate subsumed constant). We henceforth assume that the weights of all tubelets are at least $k/D$ .

Now we treat separately two cases: $k \lesssim D$ and $k \gtrsim D$ . The reason is that we will later apply the induction hypothesis to estimate the number of $k/D$ -rich tubelets, and the induction hypothesis only holds if $k/D$ is greater than some constant.

Case $1$ : $k\lesssim D$ . Since $D = \delta ^{-c_1^2\epsilon ^2}$ , it follows that $\delta ^{-\epsilon }k^{-3} \gtrsim 1$ . Now let us count the tubes that are at least $2$ -rich. For each pair of atoms $a,a'\in A$ , there are $\operatorname {\mathrm {dist}}(a,a')^{-(d-1)}$ tubes passing through both (where $\operatorname {\mathrm {dist}}(a,a')$ is the distance between the centres of atoms a and $a'$ ). It follows that

$$ \begin{align*}|T_k(A)| \leq |T_{\geq 2}(A)| = \sum_{\substack{{a,a' \in A} \\ {a \neq a'}}} \operatorname{\mathrm{dist}}(a,a')^{-(d-1)}.\end{align*} $$

By the grid-like configuration, we may assume that the atoms are exactly arranged in a d-dimensional integer grid (scaled down by a factor of W). At worst, this affects the above sum by a small multiplicative constant. We also lose no generality by considering only the case where $a'$ is the atom with centre at the origin. Thus, it follows that

$$ \begin{align*} \sum_{\substack{{a,a' \in A} \\ {a \neq a'}}} \operatorname{\mathrm{dist}}(a,a')^{-(d-1)} \sim |A|W^{d-1} \cdot \sum_{\substack{{\mathbf{n} \in (\mathbb{Z} \cap [0,W])^d} \\ {\mathbf{n} \neq 0}}} \| \mathbf{n}\| ^{-(d-1)}. \end{align*} $$

Given $x \in [0,W]$ , we have $\|\mathbf {n}\| \in [x,2x)$ for $\sim _d x^d$ values of $\mathbf {n}$ . Incorporating this into a dyadic sum, one obtains the desired

$$ \begin{align*} |T_k(A)| \lesssim_d |A|W^{d-1} \cdot \sum_{x \text{ dyadic}}^W x \lesssim \delta^{-\epsilon}\frac{|A|^2}{k^3}. \end{align*} $$

Case $2$ : $k \gtrsim D$ . We want to apply Proposition 2.1, but to do so globally is wasteful of the strong spacing assumptions on A, so the bound will be prohibitively weak.

If we consider any maximal set of distinct $D\delta $ -tubes in $[0,1]^d$ , then each $\delta $ -tube is contained in one of these $D\delta $ -tubes. Indeed, this partitions the set of all $\delta $ -tubes into the $D\delta $ -tubes which contain them. The rationale for this partitioning is that in each $D\delta $ -tube, the tubelets behave like weighted atoms. There are $(D\delta )^{-2(d-1)}$ such $D\delta $ -tubes.

Given one of these $D\delta $ -tubes $\tau $ , we ‘stretch’ it in all nonaxis directions by a factor of $D^{-1}\delta ^{-1}$ , so it becomes $[0,1]^d$ . Each tubelet in $\tau $ that runs parallel to $\tau $ becomes a $D^{-1}$ -atom, and each k-rich $\delta $ -tube in $\tau $ becomes a $D^{-1}$ -tube. Furthermore, each new atom has a weight, which is the same as the weight of the corresponding tubelet. Call this set of new weighted $D^{-1}$ -atoms $\mathbb {A}_\tau $ and the set of new $D^{-1}$ -tubes $\mathbb {T}_\tau $ . For the case $d=2$ , this procedure is indicated in Figure 1.

Figure 1 After ‘stretching’, the incidences between tubelets and $\delta $ -tubes inside a $D\delta $ -tube become incidences between weighted $D^{-1}$ -atoms and $D^{-1}$ -tubes.

For each $D\delta $ -tube $\tau $ , we count the incidences arising from tubelets that lie on, and are parallel to, $\tau $ . By the stretching procedure above (see Figure 1), this is equal to $\mathcal {I}(\mathbb {A}_\tau , \mathbb {T}_\tau )$ . It follows that

$$ \begin{align*}\mathcal{I}(A,T_k) = \sum_{\tau} \mathcal{I}(\mathbb{A}_\tau, \mathbb{T}_\tau).\end{align*} $$

Applying Proposition 2.1 in each $D\delta $ -tube $\tau $ using a thickening factor $S = \delta ^{-c_1^3\epsilon ^3}$ and $\delta ^{-\alpha } = S^\epsilon $ , and then applying Cauchy–Schwarz,

(3-1) $$ \begin{align} k|T_k| = \mathcal{I}(A,T_k) &= \sum_{\tau} \mathcal{I}(\mathbb{A}_\tau, \mathbb{T}_\tau) \nonumber \\ &\lesssim \sum_{\tau}\bigg(SD^{d-1}|\mathbb{T}_\tau|\sum_{a\in \mathbb{A}_\tau} w(a)^2\bigg)^{1/2} + S^{1-d+\epsilon} \sum_\tau \mathcal{I}(\mathbb{A}_\tau^S, \mathbb{T}_\tau^S) \nonumber \\ &\leq (SD^{d-1})^{1/2} \bigg(\sum_\tau |\mathbb{T}_\tau|\bigg)^{1/2} \bigg(\sum_\tau \sum_{a\in \mathbb{A}_\tau} w(a)^2\bigg)^{1/2} + S^{1-d+\epsilon} \mathcal{I}(A^S,T_k^S) \nonumber \\ &= (SD^{d-1})^{1/2} |T_k|^{1/2} \bigg(\sum_\tau \sum_{a\in \mathbb{A}_\tau} w(a)^2\bigg)^{1/2} + S^{1-d+\epsilon} \mathcal{I}(A^S,T_k^S). \end{align} $$

We now have two cases based on which term in Equation (3-1) dominates.

First suppose the second term dominates. Since there is at most one atom in each $W^{-1}$ -cell, all thickened $S\delta $ -atoms in $A^S$ have weight one, and hence $|A^S|= |A|$ . Also, the weights of tubes in $T^S$ are trivially bounded above by $S^{2(d-1)}$ , the maximum number of $\delta $ -tubes contained in an $S\delta $ -tube. If $\tilde {T}_k^S$ is the underlying set of unweighted tubes, then

(3-2) $$ \begin{align} \mathcal{I}(A^S,T_k^S) \lesssim S^{2(d-1)}\mathcal{I}(A^S,\tilde{T}_k^S). \end{align} $$

To have $k|T_k| \lesssim S^{1-d}\mathcal {I}(A^S,T_k^S)$ , a positive proportion of these incidences must be supported on $S\delta $ -tubes that are at least $S^{d-1}k$ -rich in atoms from $A^S$ . Furthermore, Equation (1-4) implies that

$$ \begin{align*}S^{d-1}k \geq S^{d-1} C_1(\epsilon,d)\delta^{d-1-\epsilon}|A| \geq C_1(\epsilon,d)(S\delta)^{d-1-\epsilon}|A^S| \cdot S^\epsilon,\end{align*} $$

so we can apply the induction hypothesis for any richness $k' \geq S^{d-1}k$ . Standard dyadic summing of the induction hypothesis implies that

(3-3) $$ \begin{align} \mathcal{I}(A^S,\tilde{T}_k^S) \lesssim C_2(\epsilon,d\,) (S\delta)^{-\epsilon} \frac{|A|^2}{(S^{d-1}k)^2}. \end{align} $$

Then combining Equations (3-1), (3-2) and (3-3) yields

$$ \begin{align*} k|T_k| \lesssim S^{1-d} C_2(\epsilon,d) \delta^{-\epsilon} \frac{|A|^2}{k^2}, \end{align*} $$

and rearranging closes the induction, as the $S^{1-d}$ term subsumes the multiplicative constants.

Now assume the first term in Equation (3-1) dominates. After rearranging, this implies that

(3-4) $$ \begin{align} |T_k| \lesssim \frac{SD^{d-1}(\sum_\tau \sum_{a\in \mathbb{A}_\tau} w(a)^2)}{k^2}. \end{align} $$

Notice that the bracketed term in the numerator is a sum over all tubelets. A suitable bound on this quantity will complete the proof.

Having already partitioned $[0,1]^d$ into $D^{d}$ cells, we now estimate the contribution from tubelets in each cell. For any of these cells $\mathcal {C}$ , let $A_{\mathcal {C}}$ be the set of atoms from A that lie in $\mathcal {C}$ and let $T_{\mathcal {C}}$ be the set of tubelets in $\mathcal {C}$ .

If we enlarge each cell $\mathcal {C}$ to $[0,1]^d$ , then the $\delta $ -atoms become $D\delta $ -atoms that satisfy the spacing conditions for applying the induction hypothesis. This technically assumes that $D < W$ ; the reverse case is simple and discussed at the end of the proof. Each tubelet t is now a $D\delta $ -tube, and the richness of this tube, denoted by $r(t)$ , is the weight of the corresponding tubelet. Recall that these weights all exceed $k/D$ . For any $m> k/D$ , using Equation (1-4),

$$ \begin{align*}m &> C_1(\epsilon,d) \delta^{d-1-\epsilon}|A| D^{-1} \\ & > C_1(\epsilon,d)(\delta D)^{d-1-\epsilon} (D^{-d}|A|) \\ & = C_1(\epsilon,d)(\delta D)^{d-1-\epsilon} |A_{\mathcal{C}}|, \end{align*} $$

so the induction hypothesis in Equation (1-5) can be used in any cell $\mathcal {C}$ to bound $|T_m(A_{\mathcal {C}})|$ . We get

$$ \begin{align*} \sum_{\tau} \sum_{a\in \mathbb{A}_\tau} w(a)^2 &= \sum_{\mathcal{C}} \sum_{t\in T_{\mathcal{C}}} r(t)^2 \\&=\sum_{\mathcal{C}} \sum_{\substack{{m \text{ dyadic}} \\ {m= k/D}}}^{k} m^2 |T_m(A_{\mathcal{C}})| \\&\leq \sum_{\mathcal{C}} \sum_{\substack{{m \text{ dyadic}} \\ {m= k/D}}}^{k} C_2(\epsilon,d)(D\delta)^{-\epsilon} (|A|D^{-d})^2 m^{-1} \\&\lesssim D^d \cdot C_2(\epsilon,d) (D\delta)^{-\epsilon} (|A|D^{-d})^2 \cdot(D/k). \end{align*} $$

Substituting this into Equation (3-4), and recalling that $S = \delta ^{-c_1^3\epsilon ^3}$ and $D = \delta ^{-c_1^2\epsilon ^2}$ ,

$$ \begin{align*} |T_k(A)| \leq C_2(\epsilon,d) \delta^{-\epsilon}|A|^2 k^{-3},\end{align*} $$

closing the induction and completing the proof.□

Proof. Since $|A| \leq \delta ^{1-d}$ , Theorem 1.4 can be applied and

$$ \begin{align*}|T_k(A)| \leq C_2(\epsilon/2,d) \delta^{-\epsilon/2} \cdot \frac{|A|^2}{k^3}\end{align*} $$

holds for all k. The number of pairs of atoms that both lie on a tube that is at least $k_0$ -rich is given by

$$ \begin{align*}\sum_{\substack{{k \text{ dyadic}} \\ {k \geq k_0}}}k^2 |T_k(A)| \leq 2C_2(\epsilon/2,d) \delta^{-\epsilon/2}\frac{|A|^2}{k_0}.\end{align*} $$

Choosing $k_0 = 10 C_2(\epsilon /2,d)\delta ^{-\epsilon /2}$ , it follows that $\gtrsim _{\epsilon ,d}|A|^2$ pairs of atoms lie together only on tubes that are less than $k_0$ -rich. A $\delta $ -tube can have at most $k_0^2$ of these pairs lying on it so there are $\gtrsim _{\epsilon ,d} |A|^2/k_0^2 \sim \delta ^\epsilon |A|^2$ tubes that are at least $2$ -rich, completing the proof.