In this post I would like to make some technical notes on a standard reduction used in the (Euclidean, maximal) Kakeya problem, known as the two ends reduction. This reduction (which takes advantage of the approximate scale-invariance of the Kakeya problem) was introduced by Wolff, and has since been used many times, both for the Kakeya problem and in other similar problems (e.g. by Jim Wright and myself to study curved Radon-like transforms). I was asked about it recently, so I thought I would describe the trick here. As an application I give a proof of the ${d=\frac{n+1}{2}}$ case of the Kakeya maximal conjecture.

As discussed in the previous post, the Kakeya maximal function conjecture in ${{\mathbb R}^n}$ can be formulated as follows:

Conjecture 1 (Kakeya maximal function conjecture) If ${0 < \delta < 1}$, ${1 \leq d \leq n}$, and ${T_1,\ldots,T_N}$ is a collection of ${\delta \times 1}$ tubes oriented in a ${\delta}$-separated set of directions, then

$\displaystyle \| \sum_{i=1}^N 1_{T_i} \|_{L^{d/(d-1)}({\mathbb R}^n)} \ll_\epsilon (\frac{1}{\delta})^{\frac{n}{d}-1+\epsilon} \ \ \ \ \ (1)$

for any ${\epsilon > 0}$.

A standard duality argument shows that (1) is equivalent to the estimate

$\displaystyle \sum_{i=1}^N \int_{T_i} F \ll_\epsilon (\frac{1}{\delta})^{\frac{n}{d}-1+\epsilon} \|F\|_{L^d({\mathbb R}^n)}$

for arbitrary non-negative measurable functions ${F}$; breaking ${F}$ up into level sets via dyadic decomposition, this estimate is in turn equivalent to the estimate

$\displaystyle \sum_{i=1}^N |E \cap T_i| \ll_\epsilon (\frac{1}{\delta})^{\frac{n}{d}-1+\epsilon} |E|^{1/d} \ \ \ \ \ (2)$

for arbitrary measurable sets ${E}$. This estimate is then equivalent to the following:

Conjecture 2 (Kakeya maximal function conjecture, second version) If ${0 < \delta, \lambda < 1}$, ${1 \leq d \leq n}$, ${T_1,\ldots,T_N}$ is a collection of ${\delta \times 1}$ tubes oriented in a ${\delta}$-separated set of directions, and ${E}$ is a measurable set such that ${|E \cap T_i| \geq \lambda |T_i|}$ for all ${i}$, then

$\displaystyle |E| \gg_\epsilon (N \delta^{n-1}) \lambda^d \delta^{n-d+\epsilon}$

for all ${\epsilon > 0}$.

Indeed, to deduce (2) from Conjecture 2 one can perform another dyadic decomposition, this time based on the dyadic range of the densities ${|E \cap T_i|/|T_i|}$. Conversely, (2) implies Conjecture 2 in the case ${N \delta^{n-1} \sim 1}$, and the remaining case ${N \delta^{n-1} \ll 1}$ can then be deduced by the random rotations trick (discussed in this earlier post).

We can reformulate the conjecture again slightly:

Conjecture 3 (Kakeya maximal function conjecture, third version) Let ${0 < \delta, \lambda < 1}$, ${1 \leq d \leq n}$, and ${T_1,\ldots,T_N}$ is a collection of ${\delta \times 1}$ tubes oriented in a ${\delta}$-separated set of directions with ${N \sim \delta^{1-n}}$. For each ${1 \leq i \leq N}$, let ${E_i \subset T_i}$ be a set with ${|E_i| \geq \lambda |T_i|}$. Then

$\displaystyle |\bigcup_{i=1}^N E_i| \gg_\epsilon \lambda^d \delta^{n-d+\epsilon}$

for all ${\epsilon > 0}$.

We remark that (the Minkowski dimension version of) the Kakeya set conjecture essentially corresponds to the ${\lambda=1}$ case of Conjecture 3, while the Hausdorff dimension can be shown to be implied by the case where ${\lambda \gg \frac{1}{\log^2 1/\delta}}$ (actually any lower bound here which is dyadically summable in ${\delta}$ would suffice). Thus, while the Kakeya set conjecture is concerned with how small one can make unions of tubes ${T_i}$, the Kakeya maximal function conjecture is concerned with how small one can make unions of portions ${E_i}$ of tubes ${T_i}$, where the density ${\lambda}$ of the tubes are fixed.

A key technical problem in the Euclidean setting (which is not present in the finite field case), is that the portions ${E_i}$ of ${T_i}$ may be concentrated in only a small portion of the tube, e.g. they could fill up a ${\delta \times \lambda}$ subtube, rather than being dispersed uniformly throughout the tube. Because of this, the set ${\bigcup_{i=1}^N E_i}$ could be crammed into a far tighter space than one would ideally like. Fortunately, the two ends reduction allows one to eliminate this possibility, letting one only consider portions ${E_i}$ which are not concentrated on just one end of the tube or another, but occupy both ends of the tube in some sense. A more precise version of this is as follows.

Definition 4 (Two ends condition) Let ${E}$ be a subset of ${{\mathbb R}^n}$, and let ${\epsilon > 0}$. We say that ${E}$ obeys the two ends condition with exponent ${\epsilon}$ if one has the bound

$\displaystyle |E \cap B(x,r)| \ll_\epsilon r^\epsilon |E|$

for all balls ${B(x,r)}$ in ${{\mathbb R}^n}$ (note that the bound is only nontrivial when ${r \ll 1}$).

Informally, the two ends condition asserts that ${E}$ cannot concentrate in a small ball; it implies for instance that the diameter of ${E}$ is ${\gg_\epsilon 1}$.

We now have

Proposition 5 (Two ends reduction) To prove Conjecture 3 for a fixed value of ${d}$ and ${n}$, it suffices to prove it under the assumption that the sets ${E_i}$ all obey the two ends condition with exponent ${\epsilon}$, for any fixed value of ${\epsilon > 0}$.

The key tool used to prove this proposition is

Lemma 6 (Every set has a large rescaled two-ends piece) Let ${E \subset {\mathbb R}^n}$ be a set of positive measure and diameter ${O(1)}$, and let ${0 < \epsilon < n}$. Then there exists a ball ${B(x,r)}$ of radius ${r = O(1)}$ such that

$\displaystyle |E \cap B(x,r)| \gg r^\epsilon |E|$

and

$\displaystyle |E \cap B(x',r')| \ll (r'/r)^\epsilon |E \cap B(x,r)|$

for all other balls ${B(x',r')}$.

Proof: Consider the problem of maximising the quantity ${|E \cap B(x,r)| / r^\epsilon}$ among al balls ${B(x,r)}$ of radius at most the diameter of ${E}$. On the one hand, this quantity can be at least ${\gg |E|}$, simply by taking ${B(x,r)}$ equal to the smallest ball containing ${E}$. On the other hand, using the trivial bound ${|E \cap B(x,r)| \leq |B(x,r)| \ll r^n}$ we see that the quantity ${|E \cap B(x,r)| / r^\epsilon}$ is bounded. Thus the supremum of the ${|E \cap B(x,r)| / r^\epsilon}$ is finite. If we pick a ball ${B(x,r)}$ which comes within a factor of ${2}$ (say) of realising this supremum then the claim easily follows. (Actually one can even attain the supremum exactly by a compactness argument, though this is not necessary for our applications.) $\Box$

One can view the quantity ${r}$ in the above lemma as describing the “width” of the set ${E}$; this is the viewpoint taken for instance in my paper with Jim Wright.

Now we prove Proposition 5.

Proof: Suppose Conjecture 3 has already been proven (assuming the two ends condition with exponent ${\epsilon}$) for some value of ${d,n}$, and some small value of ${\epsilon}$. Now suppose we have the setup of Conjecture 3 without the two-ends condition.

The first observation is that the claim is easy when ${\lambda \ll \delta}$. Indeed, in this case we can just bound ${|\bigcup_{i=1}^N E_i|}$ from below the volume ${\lambda |T_i| \sim \lambda \delta^{n-1}}$ of a single tube. So we may assume that ${\lambda}$ is much greater than ${\delta}$.

Let ${\epsilon > 0}$ be arbitrary. We apply Lemma 6 to each ${E_i}$, to find a ball ${B(x_i,r_i)}$ such that

$\displaystyle |E_i \cap B(x_i,r_i)| \gg r_i^\epsilon |E_i| \ \ \ \ \ (3)$

and

$\displaystyle |E_i \cap B(x',r')| \ll (r'/r_i)^\epsilon |E_i \cap B(x_i,r_i)|$

for all ${B(x',r')}$. From (3) and the fact that ${|E_i| = \lambda |T_i| \gg \lambda \delta^{n-1} \gg \delta^n}$, as well as the trivial bound ${|E_i \cap B(x_i,r_i)| \leq |B(x_i,r_i)| \ll r_i^n}$, we obtain the lower bound ${r_i \gg \delta^{1+O(\epsilon)}}$. Thus there are only about ${O(\log \frac{1}{\delta})}$ possible dyadic ranges ${\rho \leq r_i \leq 2\rho}$. Using the pigeonhole principle (refining the number ${N}$ of tubes by a factor of ${\log \frac{1}{\delta}}$), we may assume that there is a single ${\delta^{1+O(\epsilon)} \leq \rho \ll 1}$ such that all of the ${r_i}$ lie in the same dyadic range ${[\rho, 2\rho]}$.

The intersection of ${T_i}$ with ${B(x_i,r_i)}$ is then contained in a ${\delta \times O(\rho)}$ tube ${\tilde T_i}$, and ${\tilde E_i := E_i \cap \tilde T_i}$ occupies a fraction

$\displaystyle |\tilde E_i|/|\tilde T_i| \gg r_i^\epsilon |E_i|/|\tilde T_i| \gg \delta^{O(\epsilon)} \lambda / \rho$

of ${\tilde T_i}$. If we then rescale each of the ${\tilde E_i}$ and ${\tilde T_i}$ by ${O( 1/\rho )}$, we can locate subsets ${E'_i}$ of ${O(\delta/\rho) \times 1}$-tubes ${T'_i}$ of density ${\gg \delta^{O(\epsilon)} \lambda/\rho}$. These tubes ${T'_i}$ have cardinality ${\delta^{1-n + O(\epsilon)}}$ (the loss here is due to the use of the pigeonhole principle earlier) and occupy a ${\delta}$-separated set of directions, but after refining these tubes a bit we may assume that they instead occupy a ${\delta/\rho}$-separated set of directions, at the expense of cutting the cardinality down to ${\delta^{O(\epsilon)} (\delta/\rho)^{1-n}}$ or so. Furthermore, by construction the ${E'_i}$ obey the two-ends condition at exponent ${\epsilon}$. Applying the hypothesis that Conjecture 3 holds for such sets, we conclude that

$\displaystyle |\bigcup_i E'_i| \gg_\epsilon \delta^{O(\epsilon)} [\lambda/\rho]^d [\delta/\rho]^{n-d},$

which on undoing the rescaling by ${1/\rho}$ gives

$\displaystyle |\bigcup_i \tilde E_i| \gg_\epsilon \delta^{O(\epsilon)} \lambda^d \delta^{n-d}.$

Since ${\epsilon > 0}$ was arbitrary, the claim follows. $\Box$

To give an idea of how this two-ends reduction is used, we give a quick application of it:

Proposition 7 The Kakeya maximal function conjecture is true for ${d \leq \frac{n+1}{2}}$.

Proof: We use the “bush” argument of Bourgain. By the above reductions, it suffices to establish the bound

$\displaystyle |\bigcup_{i=1}^N E_i| \gg_\epsilon \lambda^{\frac{n+1}{2}} \delta^{\frac{n-1}{2} - \epsilon}$

whenever ${N \sim \delta^{1-n}}$, and ${E_i \subset T_i}$ are subsets of ${\delta \times 1}$ tubes ${T_i}$ in ${\delta}$-separated directions with density ${\lambda}$ and obeying the two-ends condition with exponent ${\epsilon}$.

Let ${\mu}$ be the maximum multiplicity of the ${E_i}$, i.e. ${\mu := \| \sum_{i=1}^N 1_{E_i} \|_{L^\infty({\mathbb R}^n)}}$. On the one hand, we clearly have

$\displaystyle |\bigcup_{i=1}^N E_i| \geq \frac{1}{\mu} \| \sum_{i=1}^N 1_{E_i} \|_{L^1({\mathbb R}^n)} \gg \frac{1}{\mu} \lambda N \delta^{n-1} \gg \frac{\lambda}{\mu}.$

This bound is good when ${\mu}$ is small. What if ${\mu}$ is large? Then there exists a point ${x_0}$ which is contained in ${\mu}$ of the ${E_i}$, and hence also contained in (at least) ${\mu}$ of the tubes ${T_i}$. These tubes form a “bush” centred at ${x_0}$, but the portions of that tube near the centre ${x_0}$ of the bush have high overlap. However, the two-ends condition can be used to finesse this issue. Indeed, that condition ensures that for each ${E_i}$ involved in this bush, we have

$\displaystyle |E_i \cap B(x_0,r)| \leq \frac{1}{2} |E_i|$

for some ${r \sim 1}$, and thus

$\displaystyle |E_i \backslash B(x_0,r)| \geq \frac{1}{2} |E_i| \gg \lambda \delta^{n-1}.$

The ${\delta}$-separated nature of the tubes ${T_i}$ implies that the maximum overlap of the portion ${T_i \backslash B(x_0,r)}$ of the ${\mu}$ tubes in the bush away from the origin is ${O(1)}$, and so

$\displaystyle |\bigcup_i E_i \backslash B(x_0,r)| \gg \mu \lambda \delta^{n-1}.$

Thus we have two different lower bounds for ${\bigcup_i E_i}$, namely ${\frac{\lambda}{\mu}}$ and ${\mu \lambda \delta^{n-1}}$. Taking the geometric mean of these bounds to eliminate the unknown multiplicity ${\mu}$, we obtain

$\displaystyle |\bigcup_i E_i| \gg \lambda \delta^{(n-1)/2},$

which certainly implies the desired bound since ${\lambda \leq 1}$. $\Box$

Remark 1 Note that the two-ends condition actually proved a better bound than what was actually needed for the Kakeya conjecture, in that the power of ${\lambda}$ was more favourable than necessary. However, this gain disappears under the rescaling argument used in the proof of Proposition 5. Nevertheless, this does illustrate one of the advantages of employing the two-ends reduction; the bounds one gets upon doing so tend to be better (especially for small values of ${\lambda}$) than what one would have had without it, and so getting the right bound tends to be a bit easier in such cases. Note though that for the Kakeya set problem, where ${\lambda}$ is essentially ${1}$, the two-ends reduction is basically redundant.

Remark 2 One technical drawback to using the two-ends reduction is that if at some later stage one needs to refine the sets ${E_i}$ to smaller sets, then one may lose the two-ends property. However, one could invoke the arguments used in Proposition 5 to recover this property again by refining ${E_i}$ further. One may then lose some other property by this further refinement, but one convenient trick that allows one to take advantage of multiple refinements simultaneously is to iteratively refine the various sets involved and use the pigeonhole principle to find some place along this iteration where all relevant statistics of the system (e.g. the “width” ${r}$ of the ${E_i}$) stabilise (here one needs some sort of monotonicity property to obtain this stabilisation). This type of trick was introduced by Wolff and has been used in several subsequent papers, for instance in this paper of myself and Izabella Laba.