EDINBURGH LECTURE NOTES ON THE KAKEYA PROBLEM

TERENCE TAO

1. Overview

This lecture series will be concerned primarily with various aspects of the Kakeya problem. This is not exactly a single problem, but rather a collection of related questions, all trying to quantify the following informal question:

To what extent can “lines” in different directions overlap each other?

Of course, as phrased above this question is extremely vague. Firstly, one has to specify the ambient space (R^{n}, or perhaps a discretized lattice Z^{n}, or perhaps a finite space such as (Z/pZ)^{n}, or maybe a curved manifold). Then one has to specify what one means by “lines” (not just lines, but also line segments, tubes^{1} and even arithmetic progressions are possible), and exactly what assumptions are given on the (finite or infinite) collection of lines regarding their distinctness of directions. Finally, one has to specify how one quantifies the overlap (by the measure or dimension of the union of the lines? Or by some sort of L^{p} estimate on the multiplicity function? Or counting the number of (transverse) intersections? etc.).

This may seem like a very large number of problems, but of course they are all closely related, and a technique which is useful for one of the problems is generally useful for most of the others. It is perhaps best to think of these problems as a spectrum, ranging from the “easiest” model problems (the finite field model, the Minkowski dimension problem) to the most quantitative versions (the maximal function problem, as well as refinements such as x-ray estimates, bilinear extensions, Furstenburg variants, etc.). The problems at the latter end of the spectrum tend to be more technical, and sometimes it is difficult to implement the arguments which work at the easy end. Unfortunately, these are also the questions which are most relevant to applications to oscillatory integrals and PDE (and possibly also to number theory and ergodic theory, although the connections here are quite tenuous). We will not discuss applications much in these series of lectures, as these will be covered in Tony’s lectures, or in other surveys [54], [9], [55], [46], [48], [7], [59].

1There are also many other important sets than lines to consider, such as planes, circles, light rays, geodesics on manifolds, etc. These problems are also relevant to many questions in analysis, and use similar technique methods, though there appears to be less of a literature on these problems. Certainly I believe that one could fairly easily transfer some of the recent arguments for lines to these other kinds of geometric objects. However, due to lack of space I will not discuss these variants in these lecture notes.

The lecture series is organized as follows. In the first lecture we state the standard formulations of the Kakeya problem, and discuss their inter-relationships. Using the two-dimensional case as an example (this being the only case where the Kakeya problem is almost completely solved) we show how one can start at the easy end of the spectrum (where the arguments are quite simple) and then work our way up to the useful end (using the same arguments, but with more technicalities).

In the second lecture and third lectures, we turn to the higher-dimensional problem, for which we only have partial progress. In the second lecture, we describe the “geometric” method of attack on the Kakeya problem, which exploits basic facts in incidence geometry (e.g. every two intersecting lines determine a unique plane) to obtain constraints on how various lines can be incident to each other. This approach seems to work best in low dimensions, but this may perhaps be because we have not fully utilized higher-dimensional incidence geometry (e.g. Schubert calculus) enough. One can use discrete incidence combinatorics results such as the Szemerédi-Trotter theorem as a model, but as we shall see there appear to be substantial technical difficulties in migrating these discrete results to the more “continuous” setting of the Kakeya problem.

In the third lecture we describe the “arithmetic” method of attack on the Kakeya problem, which exploits the analogy between lines and arithmetic progressions, and reduces matters to questions about arithmetic combinatorics (e.g. the relationship between the size of A+B and A−B for finite sets A, B of integers). This approach seems to work best in high dimensions (in fact it can be viewed as a limiting case of the Kakeya problem as n → ∞). It seems plausible that one could make further progress on this problem by adapting the latest tools and arguments from arithmetic combinatorics (e.g. the recent work by Gowers on arithmetic progressions). It has also been possible to combine^{2} the geometric and arithmetic approaches to obtain some further progress, though the advances one obtains by doing so have so far been rather modest in comparison to the effort expended to combine these techniques.

These lectures (which are an expanded version of a similar lecture series given [48] at an IPAM workshop in May 2001) are not meant as an exhaustive survey of the field, nor will they present much new material. More detailed surveys can be found in [54], [59], [9]. (I also have some more informal (and much less thorough) surveys in [46], [28], [48]).

2. What is the Kakeya problem?

To begin with, we work in the setting of R^{n}, which is the most standard setting, though as we shall see the finite field setting is technically simpler while maintaining most (but not all) of the essential features of the problem.

2Of course, there could be a third, completely different technique to approach these problems.

We remark that oscillatory integral (i.e. Fourier) techniques do not appear to be very useful, due to the sparseness of all the sets involved. Indeed, the associated oscillatory integral estimates are actually more difficult than the Kakeya estimates, and one typically uses the latter to obtain progress on the former, rather than vice versa.

Let n ≥ 2. A Besicovitch set is defined as a (compact) subset of R^{n} which contains a unit line segment^{3} in every direction. These sets can have measure zero (see Besicovitch [4]). Originally, Besicovitch was led to constructing such sets from the Kakeya needle problem: what is the smallest amount of area needed to rotate a unit line segment (a needle) around in the plane? Based on the above construction it is easy to show that one can rotate a needle completely using arbitrarily small area.

Besicovitch’s example in the plane was somewhat complicated. A modern version of such a set can be found, e.g. in [44]; we will briefly discuss the example later.

While the example of Besicovitch had Lebesgue measure 0, it still had Minkowski and Hausdorff dimension 2. The Kakeya set conjecture asserts that in fact all Besicovitch sets have dimension n.

Let us pause to recall the various definitions of dimension.

Definition 2.1. The upper Minkowski dimension (or box packing dimension) \overline{dim}(E) of a set E ⊂ R^{n} is defined as the infimum of all exponents d such that for any 0 < δ ≪ 1, the set E can be covered by O(δ^{−d}) balls of radius δ.

Definition 2.2. The lower Minkowski dimension \underline{dim}(E) is the infimum of all exponents d such that there exists arbitrarily small 0 < δ ≪ 1 for which the set E can be covered by O(δ^{−d}) balls of radius δ.

Definition 2.3. The Hausdorff dimension dim_{H}(E) is defined as the infimum of all exponents d such that for any 0 < δ ≪ 1, the set E can be covered by a countable collection of balls B(x_{i}, r_{i}) of radius r_{i} ≤ δ such that ∑_{i} r_{i}^{d} ≲ 1.

Clearly dim_{H}(E) ≤ \underline{dim}(E) ≤ \overline{dim}(E), so that the Minkowski forms of the Kakeya conjecture are easier than the Hausdorff.

Partial progress on the Kakeya conjecture comes in the form of estimates like \overline{dim}(E) ≥ d, \underline{dim}(E) ≥ d or dim_{H}(E) ≥ d for arbitrary Besicovitch sets E, where d = d(n) is some quantity between 0 and n. For instance, it is trivial that \overline{dim}(E), \underline{dim}(E), dim_{H}(E) ≥ 1, since every Besicovitch set E contains at least one line segment. This is of course not the best possible lower bound.

By themselves, the Minkowski and Hausdorff forms of the Kakeya conjecture are only mathematical curiosities. However, there is a more quantitative version of the conjecture which is much better suited for applications.

3Actually, one can replace unit line segment with a line segment of arbitrary length, or even with infinite lines (though one must of course then discard the compactness assumption); this does not significantly affect the dimension problems. One can also impose reasonable measurability conditions on the Besicovitch set (e.g. that it is a Borel set, and the map from directions to line segments is Borel). However, we shall quickly see that these technical issues will disappear when we move to a quantitative, discretized setting. In particular, the most useful versions of the Kakeya problems are all discretized, and issues such as measurability become moot.

Fix 0 < δ ≪ 1. For any function f on R^{n} and direction ω ∈ S^{n−1}, define the Kakeya maximal function

f^{∗}(ω) = sup_{T:T//ω} \frac{1}{|T |} ∫_{T} |f|,

where^{4} T ranges over all 1 × δ tubes which are oriented in the direction ω. This operator naturally arises in harmonic analysis in connection with directional differentiation and the x-ray transform.

Clearly ∥f^{∗}∥_{∞} ≲ ∥f∥_{∞}. One can ask whether the maximal function is also bounded on L^{p} uniformly in δ. If one applies the Kakeya maximal function to a characteristic function of a δ-neighborhood of Besicovitch’s construction, one can show that the L^{p} bound must grow at least logarithmically in δ. Also by testing f to be a characteristic function of a δ-ball, we see that the L^{p} norm of the maximal function must be at least δ^{n/p−1} for 1 ≤ p ≤ n. This leads to the Kakeya maximal function conjecture that

∥f^{∗}∥_{L^{p}(S^{n−1})} ⪅ δ^{n/p−1}∥f∥_{p}  (1)

for all 1 ≤ p ≤ n, where we use A ⪅ B to denote the inequality A ≤ C_{ε}δ^{−ε}B for all ε > 0.

This inequality is trivial for p = 1; the objective is to make p as large as possible. This conjecture was first formulated explicitly in this form by Bourgain [6] in 1991, although variants of it were considered earlier by Cordoba [11], [12], Christ, Rubio de Francia, Duoandikoetxea [10], Stein [43] and others. One can also consider the (L^{p}, L^{q}) mapping problem, but this is not too different from the (L^{p}, L^{p}) problem^{5}.

3. Relationships between the Hausdorff, Minkowski, and maximal form of the conjectures

It is clear that the maximal function conjecture is related to the other two problems - indeed, any small-dimensional Besicovitch set could be used to construct a counterexample to L^{p} boundedness of the Kakeya maximal function. To make the connection more precise we need some notation.

Fix 0 < δ ≪ 1. Unless indicated otherwise, a tube will be a 1 × δ tube. We say that a family of tubes T is direction-separated if any two of them differ in orientation by ≳ δ (so that no two are essentially parallel). Note that a direction-separated family of tubes can have cardinality at most δ^{1−n}. We say that a direction-separated family of tubes T is saturated if |T| ≈ δ^{1−n}. If 0 < λ ≤ 1, we define a λ-shading Y of T to be an assignment Y (T) to every tube T ∈ T such that Y (T) ⊆ T is a subset of T of density λ:

|Y (T)| = λ|T |.

4If E is a finite (i.e. discrete) set, we use |E| to denote the cardinality of E, otherwise we use |E| to denote the measure of E. The choice of notation will always be clear from context.

5More precisely, it amounts to generalizing (2) below to unsaturated sets T, with the right-hand side replaced by λ^{p}δ^{n−p}(|T|δ^{n−1})^{p/q}.

In particular, the only^{6} 1-shading of T is the assignment Y (T) = T. We call ⋃_{T ∈T} Y (T) the shadow of the shading Y.

Proposition 3.1. The Kakeya maximal function estimate at exponent p is equivalent to the estimate

| ⋃_{T ∈T} Y (T)| ⪆ λ^{p}δ^{n−p}  (2)

holding for all 0 < λ ≤ 1, all saturated direction-separated T, and all λ-shadings Y (T).

Observe that the p = 1 case of (2) is trivial (since the right-hand side is then the volume of a single set Y (T)); the task is to make p as high as possible, ideally at the optimal level of p = n.

Proof

Exercise 1. Show that (1) implies (2), by applying (1) to the shadow of Y.

The converse implication ((2) implying (1)) is a little more sophisticated, and comes in several steps^{7}. First we observe that we may partition space into δ-cubes and assume without loss of generality that f is constant on each cube (since we could replace f by its average on each cube without effectively changing f^{∗}). Then, one uses some discretization to show that (1) will be implied by the estimate^{8}

( ∑_{T ∈T} | ∫_{T} f|^{p})^{1/p} ⪅ δ^{n− \frac{n−1}{p}} ∥f∥_{p}

for all f ∈ L^{p} and all saturated direction-separated collections T of tubes. Using some “restricted weak-type” interpolation, this estimate will be implied by the statement that

|{T ∈ T : |T ∩ E| ≳ λ|T |}| ⪅ λ^{−p}δ^{1−2n+p}|E|

for all sets E which are unions of δ-cubes, and all 0 < λ ≤ 1 (actually by the hypothesis on E it suffices to do this for λ > δ).

Denoting the set on the left by T′, we can define a λ-shading Y on T′ by setting Y (T) to be an appropriate subset of |T ∩ E|. Then E contains the shadow of Y, so it will suffice to prove

| ⋃_{T ∈T′} Y (T)| ⪆ λ^{p}δ^{1−2n+p}|T′|  (3)

for all families T′ of direction-separated tubes (not necessarily saturated), and all λ-shadings Y of T′.

6We always consider set of measure zero to be negligible.

7As this argument is a little technical, the reader who is impatient to get to the heart of the Kakeya problem may skip the following sketch.

8Don’t be concerned about the strange powers of δ coming out here. If, as in the previous section, you test these inequalities with the example of f being the characteristic function of a δ-ball (so that E is a δ-ball, all the tubes T go through that ball, λ ∼ δ, and the λ-shading essentially assigns the ball E to each tube T), then one sees that all the powers of δ arise naturally.

Exercise 2. Make the above steps rigorous.

This is already very close to (2), which is essentially (3) specialized to the saturated case. To finish the application one has to use the Stein-Nikishin-Pisier “factorization theory” (see [42]) exploiting the rotation invariance of the problem. The idea is that if T′ is a non-saturated family of direction separated tubes, then by taking about δ^{1−n}/|T′| random rotations of T, moving each random rotation to a separate region of space, and then taking their union, one can end up with a family of about δ^{1−n} tubes which has a large probability of containing a saturated direction-separated family of tubes. (The key point being that if |T′| ≪ δ^{1−n}, then any random tube has only a |T′|/δ^{1−n} chance of being essentially parallel to a tube in T.) By applying (2) to this larger family one can obtain (3). See [6], [7].

Thus the maximal conjecture, like the other two conjectures, limits the extent to which lines or tubes in distinct directions can be compressed together.

We have just seen that the estimate (2) is equivalent to the maximal function problem. It also implies progress on the dimension problems.

Exercise 3. Fix 1 ≤ p ≤ n. Suppose we only knew (2) in the case λ = 1 (in other words, we knew that

| ⋃_{T ∈T} T | ⪆ δ^{n−p}

for all saturated direction-separated collections T). Show that this implies that Besicovitch sets have lower Minkowski dimension at least p. (Hint: to prove that a set E has lower Minkowski dimension at least p, it suffices to show that the δ-neighbourhood N_{δ}(E) of E has volume ⪆ δ^{n−p} for all 0 < δ ≪ 1).

Of course, once one obtains a lower bound for the lower Minkowski dimension, this automatically implies a bound on the upper Minkowski dimension. But in some cases it is possible to prove a bound on the upper Minkowski dimension without saying anything new for the lower Minkowski. We will return to this point later, but the key distinction between the two dimensions is that to bound the upper Minkowski dimension from below by p, it is not necessary to obtain the lower bounds |N_{δ}(E)| ⪆ δ^{n−p} for all 0 < δ ≪ 1; it will suffice for each 0 < δ ≪ 1 to find a δ ≤ ρ ≤ δ^{0.001} (say) such that |N_{ρ}(E)| ⪆ ρ^{n−p}. In the language of (2), this becomes

|N_{ρ}( ⋃_{T ∈T} T)| ⪆ ρ^{n−p}.

In other words, we permit the tubes T to be compressed into a small space at scale δ, so long as we show that at some coarser scale ρ there is much less compression.

Now suppose we only knew (2) when λ ≈ 1. Then (2) implies (but is not quite equivalent to) Besicovitch sets having Hausdorff dimension at least p, at least assuming some reasonable measurability properties of the Besicovitch set.

We sketch the argument as follows^{9} The apparent difficulty is that the definition of Hausdorff dimension uses balls at infinitely many scales, which can be arbitrarily small, and it is not clear how to select a specific scale δ with which one can work with. However, this can be overcome by the dyadic pigeonhole principle (a trick which we shall encounter repeatedly). Let E be a Besicovitch set. For each direction ω on the unit sphere, let l_{ω} be the line segment corresponding to ω. We shall (rather reasonably) assume that the map ω → l_{ω} is measurable. This gives a measurable map

Φ : S^{n−1} × [0, 1] → E

which maps (ω, t) to the point on l_{ω} at distance t from one endpoint.

We can cover E by balls B(x_{i}, r_{i}) of arbitrarily small radius such that ∑_{i} r_{i}^{d+ε} ≲ 1 for some arbitrarily small ε > 0. We can assume that these radii are dyadic (i.e. powers of two).

For each dyadic δ, let E_{δ} denote the union of all the balls B(x_{i}, r_{i}) with r_{i} = δ, thus from the above we see that |E_{δ}| ⪅ δ^{n−d}. The sets Φ^{−1}(E_{δ}) cover S^{n−1} × [0, 1]. Since this set has measure O(1), we see from the pigeonhole principle that there exists a dyadic radius δ ≪ 1 such that |Φ^{−1}(E_{δ})| ≳ δ^{ε}. Fix this δ.

By a discretization, and unraveling Φ, we can find a maximal δ-separated set Ω of directions such that

\frac{1}{|Ω|} ∑_{ω∈Ω} |l_{ω} ∩ E_{δ}| ≈ 1.

By the pigeonhole principle again this means that there is a refinement^{10} Ω′ of Ω such that |l_{ω} ∩ E_{δ}| ≈ 1. Thickening the lines l_{ω} into tubes we thus obtain a saturated direction-separated family T of tubes and a λ-shading Y for some λ ≈ 1 whose shadow is contained in E_{δ}. From this it is easy to see that (2) implies the dimension bound.

To summarize the results of this section: the maximal conjecture is equivalent to the estimate (2) holding for all λ. To prove the Hausdorff conjecture at dimension p it suffices^{11} to prove (2) for λ ≈ 1, while to prove the lower Minkowski conjecture at dimension p it suffices to prove (2) for λ = 1. (To prove the upper Minkowski conjecture is the easiest, because we only need λ = 1 and we are allowed to go up to a coarser scale δ ≤ ρ ≤ δ^{0.001} if necessary.)

9Again, the reader who is uninterested in technicalities should skip this.

10We define a refinement A of B to be any subset A ⊆ B with |A| ≈ |B|.

11Indeed, the argument sketched above shows that one only needs λ ≳ (log 1/δ)^{−1−ε}. It is possible to improve this to λ ≳ (log log 1/δ)^{−1−ε} by refining the dyadic range of scales further, to a hyper-dyadic range of scales; see [8]. This is useful for applying some of the deeper results in arithmetic combinatorics such as Heath-Brown’s density estimate for sets without arithmetic progressions of length 3. It is also possible that the Hausdorff bound could be proven without using this dyadic pigeonholing discretization argument, instead using more “continuous” arguments (e.g.

exploiting a hypothesis such as Borel measurability, as was recently done for the Erdos ring problem [16]). However, since we are really after the maximal function formulation (for applications), this type of finessing of the Hausdorff problem may not be as useful for applications.

Another equivalent (dual) formulation of (1) is

∥ ∑_{T ∈T} χ_{T} ∥_{p′} ⪅ δ^{1− \frac{n}{p}} ,  (4)

where 1/p + 1/p′ := 1; this is easily obtained from (1) by linearizing the maximal function, discretizing, and using duality. This form is more directly useful for applications to restriction theorems and similar problems, and is also useful for phrasing a certain “bilinear” variant of the Kakeya maximal problem (we will return to this issue later).

4. The finite field model

We now consider a finite field model of the Kakeya problem. Algebraically, this model has most of the features of the Kakeya problem, but several analytical features are missing, such as multiple scales, the distinction between small and large angles, as well as any notion of ordering (unlike R, finite fields are not ordered). As such, the model is not perfect, but it does have the advantage of eliminating a large number of technicalities, in particular those having to do with small angles or small separations. Unfortunately there is no really useful direct link between the finite field model and the real line model (because there are no good homomorphisms between R and finite fields); the model is only an analogy. For more detail on the Kakeya problem for finite fields see [54], [35].

Let F be a finite field (e.g. F = Z/pZ for some large prime p); we are interested in the case when |F | is very large; also to avoid degenerate situations we assume that F has characteristic at least 2. In this section we adopt the notation that A ⪅ B if A ≤ C_{ε}|F |^{ε}B for all ε > 0 (i.e. |F | plays the role of 1/δ), with C_{ε} independent of |F | of course.

Instead of working in R^{n}, we work in F^{n}, the n-dimensional vector space (or module) over F. A line in F^{n} is a set of the form l = {x+tv : t ∈ F } where x ∈ F^{n} and v ∈ F^{n}\0. The element v should really be thought of as an element of P F^{n−1}, the projective space of F^{n}\0 modulo dilations, and is referred to as the direction of the line.

A Besicovitch set in F^{n} is a set which contains a line in every direction.

Exercise 4. Show that the set

{(x, t) ∈ F^{2} : x + t^{2} is a square, or t = 0}

is a Besicovitch set in F^{n} of cardinality \frac{1}{2}|F |^{2} + |F | − \frac{1}{2}.

If F = Z/pZ, then one can identify F with the points {0, 1/p, …, (p − 1)/p} in the obvious manner. The set F^{n} is then essentially a maximal 1/|F |-separated subset of the unit cube. If one takes the lines in F^{n} and thickens them by δ := 1/|F |, one obtains a set somewhat like a δ × 1 tube, except that due to the differences between multiplication in F and multiplication and R, these tubes are often far more disconnected. Nevertheless, there is a clear analogy between these finite Besicovitch sets, and the saturated families of direction-separated tubes from the previous section.

The Kakeya set conjecture for finite fields asserts that |E| ≈ |F |^{n} for all Besicovitch sets E in F^{n}. This is the finite field analogue of the lower Minkowski conjecture on R^{n}. It is equivalent to the statement that^{12}

| ⋃_{l∈L} l| ⪆ |F |^{n}

whenever L is a collection of lines in different directions which is saturated in the sense that |L| ≈ |F |^{n−1}.

One can similarly formulate an analogue of (2), namely that

| ⋃_{l∈L} Y (l)| ⪆ (λ|F |)^{p}  (5)

whenever L is a saturated collection of lines in different directions, and Y (l) is a subset of l of cardinality λ|l| = λ|F |, for some |F |^{−1} ≤ λ ≤ 1 (the case λ < |F |^{−1} being vacuous). Clearly, this bound (5) (specialized to the λ = 1 case) is equivalent to the assertion that Besicovitch sets in F^{n} have cardinality ⪆ |F |^{p}.

One can also rephrase (5) in the language of incidence combinatorics. Suppose that P is a collection of points in F^{n}, and L is a collection of lines. Let I := I(P, L) := {(p, l) ∈ P × L : p ∈ l} denote the set of incidences between the points and lines.

Exercise 5. Show that (5) holds if and only if one has the bound

|I| ⪅ |L||P |^{1/p}  (6)

for all saturated collections L of lines in different directions, and all sets P of points. (Hint: to derive (5) from (6), set P equal to ⋃_{l∈L} Y (l). To derive (6) from (5), pigeonhole the lines l ∈ L into dyadic pigeonholes depending on the cardinality of l ∩ P. For all the lines for which |l ∩ P | ∼ λ|l|, apply (5), and then sum).

Note that (6) is trivial for p = 1; the challenge is to get p as large as possible, ideally up to n (which is best possible).

The bound (6) is sharp in one particular instance, when P is a single point and L is the set of all lines going through that point. In the extreme case p = n it is also sharp when P is all of F^{n} and L is arbitrary. However, this does not mean that (6) is always the best possible bound. As comparison, let us recall the famous Szemerédi-Trotter theorem, which is set in R^{2} rather than F^{n}, which asserts (in our language) that

|I| ≲ |L|^{2/3}|P |^{2/3} + |P | + |L|  (7)

12It is in fact possible that one could replace ⪆ by ∼, i.e. there may be no logarithmic loss at all in the estimates. This is true in two dimensions, for instance; the example in Exercise 4, which achieves a compression factor of about 2 is extremely close to being sharp. In the continuous case we know from the Besicovitch example that some sort of logarithmic loss is necessary.

for arbitrary collections of points P and lines L (where L need not be pointing in different directions). The most interesting factor on the right-hand side is |L|^{2/3}|P |^{2/3}; the “trivial” factors |P | and |L| reflect the rather uninteresting degenerate cases when all the points lie on one line, or all the lines go through one point^{13}.

The estimate (7) is quite sharp for all values of |P | and |L|. The corresponding sharp analogue for finite fields is not known (and it would be very interesting to find out!); the problem is that the Szemerédi-Trotter theorem uses very heavily the ordered structure of the reals (in particular, the fact that a line divides a plane into two half-planes) - and this fact is not available in the finite field model. (It also seems difficult to extend the Szemerédi-Trotter theorem to the continuous R^{2} setting, but for reasons having to do with small separations rather than due to lack of ordering). This raises the following problem:

Incidence Problem For fixed values of |P | and |L|, with the lines in L constrained to point in different directions, what is the largest possible value of |I(P, L)|?

This is of course going beyond (6), as it acknowledges that the right-hand side of (6) is not always the best possible bound. It is a good finite field model for the Kakeya problem, in that techniques which have given useful bounds on |I(P, L)| have also yielded useful progress on the R^{n} Kakeya problems.

5. Incidence combinatorics attacks on the finite field problem

We now show how incidence combinatorics methods can be used to make progress on the Kakeya problem, starting with the finite field model where the analysis is easiest.

The paradigm for this type of argument runs as follows:

• Given points P and lines L in different directions, consider all configurations of a certain shape consisting of a (small) number of points and lines which are incident to each other in a certain way.

• Using basic combinatorial tools such as Cauchy-Schwarz, the pigeonhole principle, and random sampling methods to obtain a lower bound for the number of such configurations.

• Using basic facts in incidence geometry (e.g. two points determine a line), obtain an upper bound for the number of such configurations.

• Combine the two bounds to obtain an upper bound for |I|.

By Cauchy-Schwarz we mean the following.

13It is easy to eliminate these trivial factors, simply by assuming by fiat that |I| ≫ |P | and |I| ≫ |L|. The former condition says that, on the average, every point is incident to at least two lines; we refer to this as the bilinear condition. The latter condition says that, on average, every line is incident to at least two points; we refer to this as the two ends condition. These conditions have analogues in the continuous case which are quite useful for dealing with the issues of small angles and small separations respectively; see below.

Exercise 6. If P, L are two finite sets with some relation p ∼ l between elements p ∈ P, l ∈ L, then

|\{(p, l, l′) ∈ P × L × L : p ∼ l, p ∼ l′\}| ≥ \frac{|\{(p, l) ∈ P × L : p ∼ l\}|^{2}}{|P |} .  (8)

Show that this estimate is sharp whenever |{(p, l) ∈ P × L : p ∼ l}| is a multiple of |P |.

In other words, once one has lots of links p ∼ l, one necessarily has a lot of double links^{14} p ∼ l, l′.

Now consider the set of all “angles”, by which we mean a triple (p, l, l′) ∈ P ×L×L with p ∈ l and p ∈ l′. From (8) we see that the number of angles is at least |I|^{2}/|P |. On the other hand, since any two distinct lines intersect in at most one point, the total number of angles is at most |L|^{2} + |I| (the latter contribution coming from the degenerate angles for which l = l′). Thus we have

|I| ≤ |P |^{1/2}|L| + |P |.  (9)

.

Exercise 7. Modify the above argument, using “two distinct points determine a unique line” instead of “two distinct lines intersect in at most one point”, and counting “line segments” {(p, p′, l) ∈ P × P × L : p, p′ ∈ L}, to show that

|I| ≤ |L|^{1/2}|P | + |L|.  (10)

(These estimates (9), (10) are standard, see e.g. [5]. Observe that points and lines are duals in two dimensions, which explains the symmetry).

The estimates (9), (10) are true in all dimensions, but as we shall see, they are only really very efficient when n = 2. (The point is that when n > 2, then most pairs of lines don’t intersect at all. Similarly, most pairs of points, while still determining a line of course, will rarely determine a line in L). Also, they do not utilize the fact that L points in different directions.

Exercise 8. Use (9) to show that (6) holds with p = 2 in any dimension. Use (10) to show that (6) holds with p = (n + 1)/2 in any dimension. (Use the trivial estimates |L| ∼ |F |^{n−1}, |P | ≤ |F |^{n}, |I| ≤ |L||F |.) In particular, the Kakeya conjectures for finite fields are true in two dimensions.

Taking the geometric mean of (9) and (9) gives

|I| ≲ |P |^{3/4}|L|^{3/4} + |P | + |L|,  (11)

which compares poorly with the corresponding estimate (7) in the plane. It seems a natural question to ask if (11) can be improved; this is the finite field analogue of what can be called the Furstenburg set problem, which we shall discuss a little later. A model case occurs when |P | = |L| = |F | - the question is then whether a set of |F | lines and |F | points can have substantially less than |F |^{3/2} incidences. The Szemerédi-Trotter theorem suggests this can be improved, perhaps to |F |^{4/3}.

14This can of course be generalized to create longer chains of links. See e.g. [25].

However, in the case that F contains a subfield G of index 2 (e.g. if |F | = p^{2} for some prime p, and G is the subfield with |G| = p), then there is an easy counterexample, setting P := G × G and L equal to the lines with slope and intercept in G; this already shows that there are some substantial differences between finite fields and reals, at least when the finite field contains a “1/2-dimensional” subfield G.

More generally, if F contains any set G with

G| ≈ |G + G| ≈ |G · G| ≈ |F |^{1/2}  (12)

(where A + B := {a + b : a ∈ A, b ∈ B} and A · B := {ab : a ∈ A, b ∈ B}, then one can show that (11) is sharp, by an appropriate choice of P and L.

Exercise 9. Find this choice of P and L. (The answer is in [17]. A hint: one can take P to be a Cartesian product).

Interestingly, it turns out that this statement has a converse: if (11) cannot be improved in the case |P | = |L| = |F |, then there exists a subset G obeying (12). See [47], [27].

It seems reasonable to think of G as an “approximate sub-ring” of F with “dimension” 1/2. As such, the question of whether such a G exists is the finite field analogue of the Erdös ring problem - whether there exists a sub-ring of the reals of Hausdorff dimension 1/2. Recently [16] this question has been answered in the negative assuming that the subring is a Borel set (an earlier construction of Davies - assuming the Continuum Hypothesis! - shows that such sub-rings can exist if the Borel assumption is dropped), however this argument does not seem to extend to the finite field setting, because the Borel property is used in an essential way. (A key step is the following observation, which has no useful finite field analogue: if E ⊂ R is Borel, then either E − E contains an open interval, or E is meager).

The case F = Z/pZ seems particularly interesting: does there exist a set G in F of cardinality ≈ \sqrt{p} which behaves like a sub-ring in the sense that |G + G| ≈ |G| and |G · G| ≈ |G|? I suspect the answer is no, though the proof would presumably be quite difficult as it would need to find some exploitable property that Z/pZ obeyed, but finite fields such as F_{p^{2}} did not.

Let us now consider ways to improve upon the estimates (10), (9). To simplify matters let us just consider the Kakeya set problem^{15} - we let P ⊆ F^{n} be a Besicovitch set and consider lower bounds on |P |. In this case we have |L| ∼ |F |^{n−1} and |I| = |L||F | ∼ |F |^{n}. The bounds (9), (10) give |P | ≳ |F |^{2} and |P | ≳ |F |^{(n+1)/2} respectively.

In three dimensions n = 3, these bounds were first improved by Bourgain [6], who obtained the bound |P | ≳ |F |^{7/3}. We shall prove this via an argument of Schlag [40] (Bourgain’s original argument is arranged quite differently, but follows the same basic principle). The basic incidence geometry fact is the following threedimensional observation:

15The arguments below do of course extend to proving estimates such as (6), but require a little more bookkeeping. See for instance [35].

Given three distinct lines l_{1}, l_{2}, l_{3} in F^{3}, there can be at most O(|F |) lines l in different directions which intersect all three lines l_{1}, l_{2}, l_{3} in distinct places.

Note that if l_{1}, l_{2}, l_{3} are coplanar, then there are O(|F |^{2}) lines which intersect all three, but at most O(|F |) of them at a time will point in different directions.

To exploit this, we define a fork to be a configuration

(l, l_{1}, l_{2}, l_{3}, p_{1}, p_{2}, p_{3}) ∈ L^{4} × P^{3}

where p_{i} ∈ l ∩ l_{i} for i = 1, 2, 3, the lines l, l_{1}, l_{2}, l_{3} are distinct, and the points p_{1}, p_{2}, p_{3} are distinct. The above geometric fact implies that the number of forks is at most O(|F |^{7}) (since there are O(|F |^{2}) choices for each of l_{1}, l_{2}, l_{3}, and then O(|F |) choices for l. The points p_{i} are then completely determined).

On the other hand, we claim that the number of forks is at least O(|F |^{5}(|F |^{3}/|P |)^{3}); combining these two estimates gives the claim |P | ≳ |F |^{7/3}.

We explain this informally. Recall that there are ∼ |F |^{3} incidences |I|, to be shared among |P | points. Thus we expect each point to be incident to ∼ |F |^{3}/|P | lines. We can assume that |F |^{3}/|P | ≫ 1 since we are done otherwise. Now we pick a line l and three distinct points p_{1}, p_{2}, p_{3} on l; there are about |F |^{5} ways to do so. Then we pick l_{1}, l_{2}, l_{3} incident to p_{1}, p_{2}, p_{3} respectively, and distinct from l; there are ∼ (|F |^{3}/|P |)^{3} ways to do this, and we are done.

Exercise 10. Make the above argument rigorous. (Probably one will have to apply the dyadic pigeonhole principle to the set of incidences).

It seems likely that this argument can be improved, and extended to higher dimensions, though the incidence geometry facts required begin to become a little complicated. However, there is another argument of Wolff [51] (which we phrase using the formulation of Katz, as reproduced in [35]) which gives a superior bound of |P | ≳ |F |^{(n+2)/2} for all dimensions n ≥ 2, and it is based on the following incidence geometry fact:

Given two intersecting lines l_{1}, l_{2} in F^{2}, there are at most O(|F |) lines l in different directions which intersect both l_{1} and l_{2} in distinct places.

The point being that l is constrained to lie in the 2-plane containing l_{1} and l_{2}, which has only O(|F |) possible directions available to it.

To exploit this, we define a triangle to be a configuration

(l_{1}, l_{2}, l_{3}, p_{12}, p_{23}, p_{31}) ∈ L^{3} × P^{3}

where l_{1}, l_{2}, l_{3} are distinct, p_{12}, p_{23}, p_{31} are distinct, and p_{ij} ∈ l_{i} ∩ l_{j} for ij = 12, 23, 31.

Recall that we defined an angle to be a triplet (p, l, l′) with p ∈ l, l′ and l distinct from l′. Denote the number of angles by V: from Cauchy-Schwarz we had V ≳ |F |^{2n}/|P |.

From the above geometric fact we see that the number of triangles is at most V |F |, since after specifying one angle of the triangle there are only O(|F |) possible choices for the opposite side of the triangle, which then determines everything.

On the other hand, the number of triangles is ≳ (V |F |)^{2}/(|F |^{n−1}|P |). To see this, define a pointed angle to be a configuration (p, l, l′, p′), where (p, l, l′) is an angle and p′ ∈ l′ is distinct from p. The number of such pointed angles is ∼ V |F |.

Now observe that a triangle is nothing more than^{16} a pair (p_{1}, l_{1}, l′_{1}, p′_{1}), (p_{2}, l_{2}, l′_{2}, p′_{2}) of pointed angles for which l_{1} = l_{2} and p′_{1} = p′_{2}. Since the number of possible pairs (l, p′) is at most |F |^{n−1}|P |, the claim then follows from an appropriate use of (8).

Combining the lower and upper bounds for the number of triangles we obtain V |F | ≲ |F |^{n−1}|P |; combining this with the lower bound on V we obtain |P | ≳ |F |^{(n+2)/2} as desired^{17}.

One might think that one could continue these lines of argument, and use increasingly sophisticated incidence geometry statements to obtain further progress on the problem. Remarkably, however, Wolff’s estimate (which dates back to 1995) is the best known estimate one can obtain from this incidence geometry paradigm. It seems likely to me that one can do better than this estimate in higher dimensions n > 3 (though in high dimensions Wolff’s estimate has already been surpassed by other, more “arithmetic” techniques). However, as we shall now discuss, there is an obstruction to improving the bound |P | ≳ |F |^{5/2} in three dimensions.

Let L be a collection of lines, not necessarily pointing in different directions. We say that L obeys the Wolff axiom if every 2-plane contains at most O(|F |) lines in L. Note that this Wolff axiom is automatically obeyed if the lines in L point in different directions. Define a generalized Besicovitch set to be a set of the form ⋃_{l∈L} l, where L is a collection of O(|F |^{n−1}) lines obeying the Wolff axiom. Thus every Besicovitch set is a generalized Besicovitch set, but not vice versa.

Exercise 11. Explain why the Wolff/Katz argument above extends to generalized Besicovitch sets (i.e. all generalized Besicovitch sets have cardinality ≳ |F |^{(n+2)/2}.

16Actually this is not quite true, because this includes some degenerate triangles, but those cases turn out to be negligible. See [35] for the rigorous argument.

17Readers who are familiar with Wolff’s original argument in [51] (see also the finite field version in [54]) may be surprised to see how different Katz’s argument above appears from Wolff’s, as it deals with triangles instead of “hairbrushes”. However, a more careful inspection of the two arguments reveals that they do indeed use the same fundamental incidence geometry fact, and the only real distinction in the arguments comes from reshuffling the combinatorics around. It is instructive to try to connect the two viewpoints and thus gain a deeper understanding of this (n + 2)/2 argument.

However, if F contains a subfield G of index 2, then it is possible to find a generalized Besicovitch set of cardinality exactly |F |^{5/2} in F^{3}. Indeed, one can take the example of the Heisenberg group

P := \{(z_{1}, z_{2}, z_{3}) ∈ F^{3} : Im(z_{3}) = Im(z_{1}\overline{z}_{2})\},

where z ↦ \overline{z} is the unique non-trivial involution on F which preserves G, and Im(z) := (z + \overline{z})/2.

Exercise 12. Show that P is indeed a generalized Besicovitch set of cardinality ∼ |F |^{5/2}.

Thus, if one wants to improve the bound on Besicovitch sets in three dimensions to better than |F |^{5/2}, one either has to (a) ensure that F does not contain “halfdimensional sub-fields” G or similar objects (which brings us back to the “approximate subring” problem mentioned earlier), or (b) go beyond the Wolff axiom and really use the fact that the lines in L point in different directions. As mentioned earlier, approach (a) is very interesting but we appear to be stuck on that problem for now. Approach (b) is feasible by using more arithmetic arguments (see below), but it is difficult to come up with a purely incidence theoretic statement in three dimensions about the lines L which really use the distinct directions property and not just the Wolff axiom. On the other hand, this Heisenberg example does not extend particularly well to higher dimensions, and it is still possible that incidence geometry alone will be able to improve upon the |F |^{(n+2)/2} bound here.

6. Passing from finite fields to the continuous problem

We leave finite fields for the moment, and turn back to the continuous problem. As we shall see, all the arguments developed in the finite field model can be transferred over to the continuous setting (but with some additional technicalities, having to do with small angles, small separations, and other manifestations of multiple scales). On the other hand, there are also some techniques in the continuous case which have no analogue in the finite setting - primarily methods exploiting the interplay between multiple scales such as scale δ and scale \sqrt{δ}. In light of the Szemerédi-Trotter theorem, one would also expect to use techniques in the continuous case which exploit the ordering of R (e.g. cell decomposition methods). Curiously, however, all attempts to do so for the Kakeya problem have so far been unsuccessful (although cell methods are quite useful for analogues of Kakeya problems for circles, see [30], [39], [38], [53], [58]). Thus the finite field model is a useful, but not perfect, model for the continuous problem.

To illustrate the transference technique, we begin with the simplest argument, namely the estimate (9), which ultimately gave the bound (6) for p ≤ 2. We recall that the method of proof there involved the counting of angles. Let us now attack (2) using this idea. Our situation is that we have a saturated, direction-separated collection T of tubes, and a λ-shading Y. The analogue of an angle would be a triple in the set

A := {(x, T, T′) ∈ R^{n} × T × T : x ∈ Y (T) ∩ Y (T′)}.

Let |A| denote the measure of A (using counting measure for the T components and Lebesgue measure for the R^{n} component). Since

|{(x, T) ∈ R^{n} × T : x ∈ Y (T)}| = ∑_{T ∈T} |Y (T)| ∼ δ^{1−n}λδ^{n−1} = λ

and the vertices x of angles must lie in ⋃_{T ∈T} Y (T), we see from (8) that

|A| ≳ \frac{λ^{2}}{| ⋃_{T ∈T} Y (T)|}.

Now we need an upper bound on A. In the finite field case we used the fact that any two distinct lines intersect in at most one point. The analogue in the continuous case is trickier. We can write

|A| = ∑_{T,T′∈T} |Y (T) ∩ Y (T′)|.

If T and T′ are transverse (intersecting at angle ∼ 1), then |T ∩ T′| ≲ δ^{n}, but if the angle of intersection is small, the measure of the intersection can be higher. More precisely, we have

|T ∩ T′| ≲ δ^{n}/|dir(T) − dir(T′)|

where dir(T) denotes the direction of T. Thus we have

|Y (T) ∩ Y (T′)| ≲ min(λδ^{n−1}, δ^{n}/|dir(T) − dir(T′)|).

Thus there is a slight singularity when T and T′ are nearly parallel. But on the other hand, since T is direction-separated, there are fewer pairs of parallel tubes T, T′ than transverse tubes. More precisely, for any angle θ, the number of pairs T, T′ with |dir(T) − dir(T′)| ∼ θ is O(δ^{1−n}(θ/δ)^{n−1}). Thus we have

|A| ≲ ∑_{θ dyadic} min(λδ^{n−1}, δ^{n}/θ)δ^{1−n}(θ/δ)^{n−1}.

The left-hand side computes^{18} to ≈ δ^{2−n} (the θ = 1 term is dominant). Combining this with the lower bound for A we obtain

| ⋃_{T ∈T} Y (T)| ⪆ λ^{2}δ^{n−2}

which gives (2) for p = 2. In particular, this resolves all the Kakeya conjectures in two dimensions (though as we shall see there are still one or two problems remaining open in 2D). As a historical remark, the maximal function estimate in two dimensions was obtained by Cordoba [12], [13], while the dimensional versions were obtained by Davies [14].

To summarize, the finite field argument extends to the continuous case, but a new difficulty arises because small angles create larger intersections than large angles; there is no analogue of this phenomenon in the finite field model. This problem of course plagues many of the other arguments given in the previous section (see for instance the amount of space devoted to “narrow hairbrushes” in [51]). On the other hand, from the above example (and from other examples in the literature) we learn that the large angle case θ ∼ 1 is the most important^{19}. This heuristic can be made rigorous by means of the bilinear reduction (see e.g. [49], the idea dates back at least to the “bi-orthogonality theory” of Fefferman, Cordoba, and others). The starting point is the dual formulation (1) of (2):

18The ≈ instead of ∼ arises only in 2 dimensions, when the powers of θ exactly cancel and one picks up a logarithmic factor. In terms of Besicovitch sets in R^{2}, this suggests that the δ-neighbourhood of a Besicovitch set could be as small as O(1/ log(1/δ)) (but no smaller). This begins to explain Besicovitch’s example of a measure-zero Besicovitch set (in which there are intersections at all angles, and these intersections are in some sense “uniformly distributed” in order not to lose anything in the Cauchy-Schwarz inequality (8)). The optimal bound of O(1/ log(1/δ))

was obtained by Keich [29].

∥ ∑_{T ∈T} χ_{T} ∥_{p′} ⪅ δ^{1− \frac{n}{p}} .

At this stage it is not clear how to separate the small angle and large angle portions of this estimate. However, this can be resolved by squaring (or “bilinearizing” the estimate:

∥ ∑_{T,T′∈T} χ_{T} χ_{T′}∥_{p′/2} ⪅ δ^{2(1− \frac{n}{p})}.  (13)

Now we see can isolate the large-angle intersections:

∥ ∑_{T,T′∈T:|dir(T)−dir(T′)|∼1} χ_{T} χ_{T′}∥_{p′/2} ⪅ δ^{2(1− \frac{n}{p})}.  (14)

It may appear that (14) is strictly weaker than (13), however the two estimates are actually equivalent. We sketch the argument as follows. We can restrict ourselves to the p > 2 case, since everything has already been proven for p = 2. By rescaling (14) anisotropically (squishing the unit ball into a 1 × θ tube) and redefining δ, we obtain

∥ ∑_{T,T′∈T:|dir(T)−dir(T′)|∼θ;|dir(T)−ω|≲θ} χ_{T} χ_{T′}∥_{p′/2} ⪅ (δ/θ)^{2(1− \frac{n}{p})}θ^{2(n−1)/p′}.

for any δ ≲ θ ≲ 1. Summing up over a θ-separated set of ω, we obtain

∥ ∑_{T,T′∈T:|dir(T)−dir(T′)|∼θ} χ_{T} χ_{T′}∥_{p′/2} ⪅ (δ/θ)^{2(1− \frac{n}{p})}θ^{2(n−1)/p′}θ^{−2(n−1)/p′},

and then by summing in θ one obtains (13).

Exercise 13. Make the above arguments rigorous.

The reduction from (13) to (14) morally entails that we can forget about small angle interactions and only deal with large ones. In practice, one still has to deal with small angles occasionally; the rule of thumb is that in configurations involving more than one angle, the reduction to (14) allows one to assume the largest angle is ∼ 1, but doesn’t say what happens to the other angles (see e.g. [49], [31] for some examples). Also it is sometimes a little cumbersome to translate (14) back into language like (2).

19In the finite field case this corresponds to the observation that the case |I| ≫ |P | is the most important (since one always will be losing a factor of |P | + |L| in bounding |I| anyway), so that every point is on the average incident to two or more lines. Thus pairs of intersecting lines are generally distinct (and hence transverse, in the finite field model).

Just as the |P | ≳ |F |^{2} argument could be transferred to the continuous setting to prove (2) for p = 2, the |P | ≳ |F |^{(n+1)/2} argument can similarly be transferred. A naive approach would be to try to count the space of line segments

S := {(x, x′, T) ∈ R^{n} × R^{n} × T : x, x′ ∈ T }.

It is easy to get the lower bound of |S| ≳ δ^{1−n}(λδ^{n−1})^{2}, however an upper bound gets a little tricky because when x and x′ are close then there are too many tubes T which intersect both. To get around this “small separations” problem it is better to work with

S̃ := {(x, x′, T) ∈ R^{n} × R^{n} × T : x, x′ ∈ T, |x − x′| ≳ λ}.

The lower bound is still valid for S̃. Now for each x and x′ with |x − x′| ≳ λ, the number of tubes T which intersect both at most O(λ^{1−n}). Applying this we obtain

δ^{1−n}(λδ^{n−1})^{2} ≲ λ^{1−n}| ⋃_{T ∈T} Y (T)|^{2},

which translates to (2) for p = (n + 1)/2. (This result was first obtained in [10], [15]; see also [6]).

This argument shows that, just as small angles were a problem for the p = 2 argument, small separations become a nuisance for the p = (n + 1)/2 argument. Fortunately, there is a standard device to eliminate most of the difficulty. Developed by Wolff [51], it is known as the two ends reduction.

This reduction allows one to assume that the sets Y (T) obey the estimate

|Y (T) ∩ B(x, r)| ⪅ r^{σ}λ|T |  (15)

for some σ > 0 and all balls B(x, r) - in other words, the Y (T) must spread out over more than one end of the tube, and the average separation between two points in Y (T) is ≈ 1. For if too many of the sets Y (T) disobeyed this estimate, then they would cluster in an r × δ tube rather than a 1 × δ tube. One could then rescale in a favorable manner. (This trick has since been used to good effect in other problems such as L^{p} estimates for averages along curves. The idea is also related to the powerful induction on scales strategy developed by Wolff, Bourgain, and others to handle oscillatory integral operators).

Exercise 14. Let 0 < σ ≪ 1. Show that for any set Y (T) ⊆ T with |Y (T)| = λ|T |, there exists a radius λ^{C} ⪅ r ≲ 1, a ball B(x, r), and a set Y′(T) ⊆ Y (T) ∩ B(x, r) such that

λ|T | ≥ |Y′(T)| ⪆ r^{σ}λ|T |

and

|Y′(T) ∩ B(x′, r′)| ⪅ (r′/r)^{σ}|Y′(T)|

for all balls B(x′, r′). (Hint: set Y′(T) = Y (T)∩B(x, r), and choose the ball B(x, r) to maximize the quantity |Y′(T)|/r^{σ}). Use the above fact, a dyadic pigeonholing, and a rescaling by r to show that if one showed (2) under the assumption (15), then one automatically had (2) in general, but with an additional factor of δ^{Cσ} on the right-hand side. (Thus if σ can be chosen arbitrarily small, this error can be absorbed into the ⪆ notation).

The two-ends condition makes many estimates easier to prove, mainly because the right-hand side of (2) is no longer sharp. For instance:

Exercise 15. Assuming the two-ends condition (15), repeat the proof of (2) for p = (n + 1)/2 and obtain the improvement

| ⋃_{T ∈T} Y (T)| ⪆ λδ^{(n−1)/2}

(note that the previous argument only gave λ^{(n+1)/2}δ^{(n−1)/2}).

The two-ends and bilinear reductions eliminate many technical obstacles to obtaining continuous Kakeya estimates, although there are still some problems (for instance, it is difficult to use both reductions simultaneously. Also, just as with the bilinear reduction, if there are multiple separations, the two-ends reduction generally only allows one to assume that the largest separation is ∼ 1).

In particular, the arguments of Bourgain, Schlag, and Wolff all extend to the continuous case (in fact, their original papers [6], [40], [51] addressed only the continuous case).

The two-ends and bilinear reductions touch upon what may be an important point in the Kakeya problem, which is that one may need to supplement measure and cardinality information with dimensional information. For instance, we assume no structure on our shadings Y (T) other than the measure-theoretic statement |Y (T)| = λ|T |. However, the two-ends reduction then imposes a further restriction on Y (T), which is reminiscent of a dimension bound on T. In the sharp case when λ = δ^{σ}, the estimate (15) is essentially saying that Y (T) is a δ-neighbourhood of a σ-dimensional set living on the axis of T. The bilinear reduction can also be used to impose a similar dimensional constraint on the directions of T′ in the generalization (3) of (2). These ideas have not yet been fully explored; see [24] for some examples of this type of philosophy.

This does bring up an important variant of the Kakeya problem, which one might call the Furstenburg set problem, which we define as follows. Following [52], [54], we define a β-set to be a (compact Borel) subset E of R^{n} such that, for each direction ω ∈ S^{n−1}, there exists a unit line segment l_{ω} parallel to ω and a β-dimensional (in the sense of Hausdorff dimension) subset E_{ω} ⊂ l_{ω} in l_{ω} such that E_{ω} ⊂ E. Thus 1-sets are basically Besicovitch sets. The Furstenburg set problem then asks for the best lower bounds on β-sets are. This is the continuous analogue of the Incidence Problem mentioned earlier. The analogue of this for (2) is the problem of obtaining the best possible lower bounds on | ⋃_{T ∈T} Y (T)|, assuming that |Y (T)| ≈ δ^{−β}δ^{n} and that

|Y (T) ∩ B(x, r)| ⪅ (r/δ)^{β}δ^{n}

for all balls B(x, r) and all T ∈ T (i.e. Y (T) is essentially the δ-neighbourhood of a β-dimensional set).

Even in two dimensions, the Furstenburg problem remains unsolved. In [54] the best lower bounds are max(β + 1/2, 2β) and the best upper bounds are 3β/2 + 1/2 (see also [56], and more recent work by Bennett and Vargas). It turns out that this problem is in fact connected to (a quantitative version of) the Erdos ring problem; see [27]. Since the Erdos ring problem (in set form, but not in discretized form) has recently been solved in [16], there may be some hope of progress on the Furstenburg problem also, although the argument in [16] does not seem to directly transfer over to discretized settings.

Because of the usefulness of the two-ends reduction, it seems that progress on even the two-dimensional Furstenburg problem should lead to some new results (or at least some insights) into the higher-dimensional Kakeya problem. I don’t have any rigorous way to formulate such a statement, though.

In a vaguely similar spirit to the Furstenburg problem is the Kakeya maximal function problem for a fixed number of arbitrary directions, possibly arranged in a set of given dimension such as a Cantor set. There has recently been some activity in this area (see [2], [23], and recent work by Bennett and Vargas), using very similar techniques (in particular, induction on scales methods).

The Fursternburg problem is also connected to several other geometric combinatorics questions, such as the Falconer distance set problem (see e.g. [56], [27]), but we will not devote space to this problem here.

7. Arithmetic methods

We now discuss arithmetic approaches to the Kakeya problem, which in higher dimensions seem to be more effective than the incidence geometry methods in the previous sections. For simplicity we shall stick to the finite field model; the arguments here can be extended to the continuous case but the extension does not really require any new ideas beyond those indicated above.

The incidence geometry methods do not fully exploit the hypothesis that the lines L point in different directions. One way to use this hypothesis further is to use not just incidence geometry, but also affine geometry - the geometry of ratios of lengths.

A typical result (which is based on an argument in [25]) is

Proposition 7.1. Let P ⊆ F^{n} be a Besicovitch set, where F has characteristic greater than 3. Then |P | ≳ |F |^{(4n+3)/7}.

This is superior to previous bounds such as |P | ≳ |F |^{(n+2)/2} for n > 8.

Proof Let L be the direction-separated set of lines associated with the Besicovitch set P, thus every line in L is contained in P. Define a quadrilateral to be any configuration

(x_{1}, x_{2}, x_{3}, x_{4}, l_{12}, l_{23}, l_{34}, l_{41}) ∈ P^{4} × L^{4}

where the x_{i} are all distinct, the l_{ij} are all distinct, and x_{i}, x_{j} ∈ l_{ij} for ij = 12, 23, 34, 41. Let Q be the set of all quadrilaterals.

Once again, we obtain upper and lower bounds for Q. The difference is that our technique for obtaining upper bounds for Q will be arithmetic rather than incidencetheoretic.

To obtain a lower bound we first count half-quadrilaterals^{20}

(x_{0}, x_{1}, x_{2}, l_{01}, l_{02}) ∈ P^{3} × L^{2}

with everything distinct and x_{i}, x_{j} ∈ l_{ij} for ij = 01, 02. The number of halfquadrilaterals is about |F |^{2} times the number of angles, which by (8) is ≳ |F |^{2}|F |^{2n}/|P |. Now, a quadrilateral is essentially two half-quadrilaterals whose x_{1} and x_{2} points match, so by another application of (8) we get

|Q| ≳ (|F |^{2}|F |^{2n}/|P |)^{2}/|P |^{2}.

(There is a slight issue with degenerate quadrilaterals, but this can be easily dealt with).

To obtain the lower bound make the following observation. Let q be a quadrilateral, and define the pivot points p_{1}, p_{2}, p_{3} of q by

p_{1} := \frac{1}{2}x_{1} + \frac{1}{2}x_{2}; p_{2} := 2x_{2} − x_{3}; p_{3} := \frac{1}{3}x_{3} + \frac{2}{3}x_{4};

note these points are well-defined for char(F) > 3. Observe that p_{1}, p_{2}, p_{3} lie on l_{12}, l_{23}, l_{34} respectively. In particular they lie in P, and so the number of triples (p_{1}, p_{2}, p_{3}) is O(|P |^{3}).

On the other hand, we note the simple arithmetic identity

x_{1} − x_{4} = 2p_{1} − \frac{1}{2}p_{2} − \frac{3}{2}p_{3}.

Thus, x_{1} − x_{4} is completely determined by p_{1}, p_{2}, p_{3}. But x_{1} − x_{4} determines the direction of l_{14}, which (since lines in L point in different directions) determines l_{14} uniquely. This gives at most O(|F |) choices for x_{1} (say), which if p_{1}, p_{2}, p_{3} are fixed are enough to determine the rest of the quadrilateral. Hence we have

|Q| ≤ |P |^{3}|F |.

Combining the two estimates we obtain the desired bound.

This argument seems ripe for improvement - perhaps vary the choice of pivot points, or consider an object slightly more complex than a quadrilateral - but it is quite difficult to improve upon the (4n+3)/7 result in high dimensions. (An improvement to (4n+5)/7 is possible, basically by exploiting the Wolff axiom more; see [28], [26]). There is also a potential difficulty in extending this argument from Besicovitch sets to incidence bounds, because once one leaves the case of Besicovitch sets, it becomes more difficult to make rigorous such statements such as “if x_{1}, x_{2} are in P, and p_{1} = \frac{1}{2}x_{1} + \frac{1}{2}x_{2}, then p_{1} is in P ”. This is because P now only contains a fraction of the line l_{12} rather than all of the line, and it might appear that one now has to invoke the theory of arithmetic progress of length three on sparse sets (see e.g. [22]). Fortunately, one can finesse this issue by making the pivots slide much more flexibly up and down the quadrilateral, and indeed one can prove (6) for p = (4n + 3)/7 (and perhaps beyond, although this bound is currently the best known for n > 8); see [28], [26].

20After a while, one can learn to get these lower bounds rather quickly by using the heuristic that the extremal case comes when the incidence graph connecting P and L is suitably “random”, and then using Cauchy-Schwarz etc. as necessary to make this rigorous. This heuristic occasionally gives the wrong answer, but is usually a pretty good guide.

The sheer number of possible variants of the argument in Proposition 7.1 may seem daunting. One can use a “slicing argument” of Bourgain to rephrase the problem in a simpler, more purely arithmetical setting. (This slicing argument seems to cost one or two dimensions in the estimates, but in the high dimensional limit n → ∞ it appears to be reasonably efficient).

To motivate matters let us briefly return to the continuous case, and review an 1969 example by Kahane of a Besicovitch set in R^{2} of measure zero. Let C be the Cantor set

C := {∑_{i=1}^{∞} a_{i}4^{−i} : a_{i} ∈ {0, 1}}.

Observe that C + 2C = [0, 1] (ignoring sets of measure zero); this corresponds to the fact that every number in [0, 1] has a base 4 expansion, and the digits {0, 1, 2, 3} are equal to {0, 1} + 2{0, 1}.

Now draw a line segment in R^{2} connecting every point of −C × {0} to every point of 2C × {1}. By construction every such line segment will have a (vertical) slope in C + 2C. From the preceding remarks we thus see that the union E of all these line segments thus contains a line segment of every vertical slope from 0 to 1. Thus E is essentially a Besicovitch set (perhaps after taking four rotated copies of E and taking their union).

It can be shown (but not here) that E has measure zero. By Fubini’s theorem, this is the same as saying that the slices E ∩ (R × {t}) have one-dimensional measure zero for almost every t. Of course, such slices are only non-empty when 0 ≤ t ≤ 1, and in that case the slice is essentially the set

(1 − t)(−2C) + tC.

The point is then that this set is usually measure zero (basically any time the base 4 digits of (1 − t)/t are randomly distributed).

From this slicing argument, we see (informally) that if we can find two sets A, B in R^{n−1} such that A − B is “large” but (1 − t)A + tB is “small” for most t, then we can create something like a small Besicovitch set. Thus one way to get lower bounds on Besicovitch set is to show that one cannot have A − B too large while keeping the slices (1 − t)A + tB small.

Let us return to the finite field setting and make this precise, working for simplicity with the Kakeya set problem rather than the incidence problem. Let P ⊆ F^{n} be a Besicovitch set of some size |P | ∼ |F |^{d}; the idea is to get a lower bound on d. We parameterize points x ∈ F^{n} by (\underline{x}, x_{n}) ∈ F^{n−1} × F. For any t ∈ F, let A_{t} denote the slice

A_{t} := \{\underline{x} ∈ F^{n−1} : (\underline{x}, t) ∈ P \}.

Thus the sets A_{t} have cardinality |F |^{d−1} on the average. To simplify the discussion let us pretend that |A_{t}| ≲ |F |^{d−1} for all t ∈ F (in practice this is only true for a large fraction of the t, by e.g. Chebyshev’s inequality, which usually suffices).

Consider all the lines in P which are not parallel to the hyperplane {x_{n} = 0}; there are ∼ |F |^{n−1} of these, all pointing in different directions. Each of these lines connects a point in A_{0} × {0} to a point A_{1} × {1}; thus generating a pair in A_{0} × A_{1}. Note that this pair uniquely determines the line (two points determine a line). Let G ⊆ A_{0} ×A_{1} denote the set of all pairs (x, y) which can be obtained in this manner, thus |G| ∼ |F |^{n−1}.

If we let π_{−1} : F^{n−1} × F^{n−1} → F^{n−1} be the subtraction map

π_{−1} : (x, y) ↦ x − y

then π_{−1} is injective on G (because the lines point in different directions), thus

|π_{−1}(G)| ∼ |F |^{n−1}.

On the other hand, if we let π_{r}(G) be the maps

π_{r} : (x, y) ↦ x + ry

and π_{∞} : (x, y) ↦ y, then for all r = F ∪ {∞}\{−1} we see that π_{r}(G) is contained in (1 + r)A_{1/(1+r)} (or A_{0}, if r = ∞), and hence

|π_{r}(G)| ≲ |F |^{d−1}.

To summarize, we have a set G in the “plane” F^{n−1} × F^{n−1}, whose projection in the π_{−1} direction is large but all the other projections are small. This situation should become untenable if d is too small. For instance, from the trivial bound

G ⊆ π_{0}(G) × π_{1}(G)

we have

|F |^{n−1} ≤ |F |^{d−1}|F |^{d−1}

and hence d ≥ (n + 1)/2 (which we have already obtained); note that indeed the arguments are essentially the same because we again used that two points determine a unique line).

In [8] Bourgain connected these ideas with the work of Gowers [20] on the Balog-Szemerédi theorem [1] in additive combinatorics. We will not go into detail here, but suffice to say that these results allow one to control the size of one projection π_{−1}(G) non-trivially in terms of several other projections. For instance, for finite sets G Bourgain showed the bound

|π_{−1}(G)| ≤ max(|π_{0}(G)|, |π_{1}(G)|, |π_{∞}(G)|)^{2−σ}

for σ = 1/13; this was later improved to σ = 1/6 [25]. This gives the bounds d − 1 ≥ \frac{13}{25}(n − 1) + 1 and d − 1 ≥ \frac{6}{11}(n − 1) respectively. The arguments are purely combinatorial and are based on such arithmetic identities as

(a − b) = (a − b′) − (a′ − b′) + (a′ − b)

and

a + b = c + d ⟺ a − d = c − b.

We reproduce a typical example of the arguments below.

Proposition 7.2. [25] Suppose char(F) > 3. For any G ⊆ F^{n−1} × F^{n−1}, we have

|π_{−1}(G)| ≲ max(|π_{0}(G)|, |π_{1}(G)|, |π_{2}(G)|, |π_{∞}(G)|)^{7/4}.

In particular we have d ≥ (4n + 3)/7 again.

Proof Let

N := max(|π_{0}(G)|, |π_{1}(G)|, |π_{2}(G)|, |π_{∞}(G)|).

Our task is to show |π_{−1}(G)| ≤ N^{7/4}. Without loss of generality we may assume that π_{−1} is injective on G (since otherwise we could just remove some redundant elements of G.

Define a vertical line segment to be a pair (g_{1}, g_{2}) ∈ G×G such that π_{0}(g_{1}) = π_{0}(g_{2}). (The notation comes from depicting π_{0}(G), π_{∞}(G) as one-dimensional sets, so that G ⊂ π_{0}(G) × π_{∞}(G) becomes a two-dimensional set and π_{0} is the projection to the first co-ordinate). Let V denote the space of all vertical line segments. From (8) we have

|V | ≥ |G|^{2}/|π_{0}(G)| ≥ |G|^{2}/N.

Now define a trapezoid to be a pair ((g_{1}, g_{2}), (g_{3}, g_{4})) ∈ V × V of vertical line segments such that π_{∞}(g_{1}) = π_{∞}(g_{3}) and π_{2}(g_{2}) = π_{2}(g_{4}), and let T denote the space of all trapezoids. From (8) again, we have a lower bound for the cardinality of T:

|T | ≥ \frac{|V |^{2}}{|π_{∞}(G)||π_{2}(G)|} ≥ |V |^{2}/N^{2} ≥ |G|^{4}/N^{4}.  (16)

On the other hand, we can obtain an upper bound for the cardinality of T as follows. Consider the map f : T → π_{1}(G) × π_{1}(G) × π_{∞}(G) defined by

f((g_{1}, g_{2}), (g_{3}, g_{4})) := (π_{1}(g_{1}), π_{1}(g_{2}), π_{∞}(g_{4}));

one could refer to these three numbers as the pivots of the trapezoid.

We claim that this map f from trapezoids to pivots is one-to-one. At first glance, this seems unlikely, as T has four degrees of freedom with respect to F^{n−1} (G has 2 degrees of freedom, hence V has 2 ∗ 2 − 1 = 3, hence T has 2 ∗ 3 − 2 = 4) and f only specifies three of these four degrees. However, we can use the injectivity of π_{−1} to recover the fourth degree of freedom. Specifically, we take advantage of the identity

π_{−1}(g_{3}) = −2π_{1}(g_{1}) + 4π_{1}(g_{2}) − 2π_{∞}(g_{4})  (17)

for all ((g_{1}, g_{2}), (g_{3}, g_{4})) ∈ T, to conclude that the quantity f((g_{1}, g_{2}), (g_{3}, g_{4})) determines π_{−1}(g_{3}), which then determines g_{3} by injectivity of π_{−1}. From some straightforward linear algebra one can then check that f((g_{1}, g_{2}), (g_{3}, g_{4})) determines all of ((g_{1}, g_{2}), (g_{3}, g_{4})), or in other words that f is one-to-one. Hence

|T | ≤ |π_{1}(G)||π_{1}(G)||π_{∞}(G)| ≤ N^{3}.

Combining this with (16) we obtain the desired bound.

Exercise 16. Convince yourself that the argument above is essentially the same as the one given in Proposition 7.1, just rephrased in a different language.

It is thus of interest to learn more about the relationship between the cardinalities |π_{r}(G)| for various values of r. This brings us squarely into the realm of arithmetic combinatorics; see for instance the survey [37], which is concerned with questions such as the relative sizes of A + B and A − B.

Ideally, one would like for every ε, to have an estimate of the form

|π_{−1}(G)| ≤ max(|π_{r_{0}}(G)|, …, |π_{r_{k}}(G)|)^{1+ε}  (18)

for some rational numbers r_{0}, …, r_{k} ≠ −1 (counting ∞ as a rational number) depending on ε, assuming that the characteristic of F was sufficiently large. One might term this the arithmetic Kakeya conjecture; it would imply the finite field Kakeya set conjecture (in the sense that Besicovitch sets have cardinality ≳ |F |^{n−ε} as long as char(F) is sufficiently large depending on ε), and would also imply the Minkowski set formulations of the Kakeya conjecture in R^{n}. The arithmetic Kakeya conjecture also has the advantage that it is essentially independent of the ambient field F or the dimension n − 1; the space F^{n−1} could be replaced by any other abstract abelian group of sufficiently high torsion. See [8]. However, it might be the case that the arithmetic Kakeya conjecture could be false, while the other Kakeya conjectures are still true^{21}, so I am unsure as to whether this is necessarily the best way to attack the Kakeya problem.

In the converse direction, it is known that one cannot obtain the arithmetic Kakeya conjecture with a fixed, bounded number of projections π_{r}. For instance, we have the following example of Ruzsa (private communication):

Proposition 7.3. There exists an abelian group Z and a set G ⊆ Z × Z such that

|π_{0}(G)|, |π_{1}(G)|, |π_{∞}(G)| ≲ N

but

|π_{−1}(G)| ≳ N^{log(27)/ log(27/4)} = N^{2−0.274018...}.

where N is an arbitrarily large number.

21The problem is that the number of projections k is fixed (allowed to depend only on ε), whereas in the finite field problem the number of slices is |F |. This already may cause the arithmetic approach to lose a dimension or so in the estimates, though this is not so significant in higher dimensions. Perhaps the more serious objection is that this approach does not try to utilize the geometric structure of F^{n−1}, treating it instead as an abstract abelian group. (For an explanation of why all torsion-free abelian groups are equivalent for the purposes of additive combinatorics, see [37]).

This is fairly close to the upper bound of N^{2−0.1666...} obtained in [25]. (The estimate in Proposition 7.2 gives N^{2−0.25}, but it requires control on |π_{2}(G)| as well).

Proof Let m be a large integer. We take Z = Z^{3m}, the space of 3m-tuples of integers. Let A ⊂ Z denote the space of 3m-tuples t which consist of 2m zeroes and m ones; clearly

N := |A| = \frac{(3m)!}{m!(2m)!} ≈ (27/4)^{m}.

Now let G ⊂ A × A denote the space of pairs (t_{1}, t_{2}) of 3m-tuples, such that the m ones in t_{1} occupy a completely disjoint set of co-ordinates than the m ones in t_{2}. Thus

|G| = \frac{(3m)!}{m!m!m!} ≈ (27)^{m} = N^{log(27)/ log(27/4)}.

One can easily check that π_{0}, π_{1}, π_{∞} all map G to a space isomorphic to A, and so we are done.

More generally, one can manufacture a large range of interesting examples by starting with an abelian group Z_{0}, and a probability distribution μ supported on a finite subset of Z_{0}×Z_{0}, such that π_{−1} is injective on the support of μ. One can then set G to be the set of m-tuples in (Z_{0} × Z_{0})^{m} ≡ Z_{0}^{m} × Z_{0}^{m} whose values in Z_{0} × Z_{0} statistically match the probability distribution μ. One can then compute the cardinality G and its various projections using the law of large numbers (basically one gets the (exponentiated negative) entropy of μ or its projections, raised to the power m). In the Ruzsa example above, Z_{0} is the integers, and μ is the uniform distribution on the three-point set {(0, 0), (0, 1), (1, 0)}. (These examples supercede the somewhat cruder examples in [25]).

It is of interest to see what the lowest ε is for which one can have a bound of the form (18), since each bound of this form automatically gives the finite field Kakeya set conjecture (and Minkowski set conjecture) for d ≥ (n−1)/(1+ε)+1. The trivial bound is ε = 1; this was improved by Bourgain [8] to ε = 12/13 = 0.923077 …, then the argument in [25] (reproduced in Proposition 7.2) gave ε = 3/4 = 0.75.

The current “world record” is ε = .67514 … [26] (although this requires a huge number of projections; to get with δ of 0.67514 … requires exp(exp(C log(1/δ)^{2}) projections with our current argument). The arguments are quite involved, involving in some sense an iteration of the argument in [25]; we refer the interested reader to [28], [26] for more discussion. Very briefly, the idea is to focus on the vertical line segments V in Proposition 7.2. V lives in a three-parameter space, but by taking a slice we can make it two-parameter, and then one can look at various projections π_{r} of this slice. One then applies estimates such as Proposition 7.2 to get some cardinality bounds on this slice on V, hence on V itself, hence on G. This allows one to use one estimate of the form (18) to prove another. This can be iterated, converging to some fixed ε between 0 and 1 (alas, the iteration doesn’t go all the way down to zero).

The dimension bounds thus obtained improve upon Wolff’s bound in 7 and higher dimensions, but are inferior in lower dimensions. It should however be possible to pursue this method further, although it seems quite ambitious to get ε all the way down to 0. Perhaps some new combinatorial ideas are needed to make significantly more progress, though.

8. Hybrid techniques

The geometric techniques seem most effective in low dimensions, while the arithmetic techniques are most effective in high dimensions. This seems to be because the geometric methods rely on the two-dimensional case, in which everything is OK by Córdoba’s argument, whereas the arithmetic methods rely on slices of the Besicovitch set instead of the full Besicovitch set, thus potentially losing a dimension or so.

A few recent results have combined both techniques to obtain some new results. For instance, Córdoba’s two-dimensional argument implies, informally speaking, that lines in a plane in different directions only overlap by ⪅ 1 on the average. A corollary of this is the following: if L is a collection of lines in F^{n} in different directions, then given a line l and a point p not on that line, there should be at most ⪅ 1 lines in L connecting p with l, since any such line must lie in the plane generated by p and l. This is better than the trivial bound of O(|F |), and can be used for instance to shave a dimension or two off of the (4n + 3)/7 bound in Proposition 7.1.

Exercise 17. Try this! (It’s not too hard to get (4n + 4)/7 this way. With a lot more effort one can get (4n + 5)/7; see [26].

Another hybrid result is in [24], which has improved Wolff’s bound of 5/2 in the three-dimensional case very slightly, to 5/2 + 10^{−10}, but the argument only works in the upper Minkowski problem because it relies on having multiple scales to work with. We sketch the idea as follows.

Let 0 < δ ≪ 1, and let T be a saturated direction-separated collection of δ × 1 tubes. Wolff’s argument gives

| ⋃_{T ∈T} T | ⪆ δ^{1/2}.

If we can improve this by an epsilon, then we are done, so let’s assume

| ⋃_{T ∈T} T | ≈ δ^{1/2}.  (19)

Let δ ≪ ρ ≪ 1 be an intermediate scale between δ and 1 (we will eventually take ρ := \sqrt{δ}). Every δ × 1 tube in T is contained in a ρ × 1 tube, so we can create a collection T_{ρ} of ρ × 1 tubes such that every tube in T is essentially contained in a tube in T_{ρ}. We can discard duplicate tubes in T_{ρ} (counting two tuples as duplicate if they are contained within bounded dilates of each other).

Since T contains tubes in every direction (up to uncertainty δ), T_{ρ} must also contain tubes in every direction (up to uncertainty ρ). In particular, |T_{ρ}| ⪆ ρ^{−2}, and T_{ρ} contains a saturated direction-separated set of ρ × 1 tubes, hence

| ⋃_{T_{ρ}∈T_{ρ}} T_{ρ}| ⪆ ρ^{1/2}.

If we can improve this by an epsilon, then this will lift the upper Minkowski dimension of our underlying Besicovitch set (but not the lower Minkowski or Hausdorff). Thus we may assume that

| ⋃_{T_{ρ}∈T_{ρ}} T_{ρ}| ≈ ρ^{1/2}.  (20)

This turns out to force |T_{ρ}| ≈ ρ^{−2}; if there are too many tubes T_{ρ} then Wolff’s argument can be modified^{22} to increase the size of ⋃_{T_{ρ}∈T_{ρ}} T_{ρ}.

Because |T_{ρ}| ≈ ρ^{−2}, we see that each ρ × 1 tube tube T_{ρ} should contain ≈ δ^{−2}/ρ^{−2} tubes in T on the average. Call this collection T[T_{ρ}]. Of course, the tubes in T[T_{ρ}] are still direction separated, but their directions must point within O(ρ) of the direction of T_{ρ}. Thus, if we rescale T_{ρ} anisotropically to the unit tube, then T[T_{ρ}] becomes a saturated, direction-separated family of δ/ρ × 1 tubes. One can once again apply Wolff’s argument, then undo the rescaling to conclude that

| ⋃_{T ∈T[T_{ρ}]} T | ⪆ (δ/ρ)^{1/2}ρ^{2}.  (21)

Thus turns out to fit very nicely with the previous bounds (19), (20). (The bound (20) says that the typical point in the Besicovitch set lies in about ρ^{−1/2} tubes T_{ρ} in T_{ρ}. The estimate (21) says that inside a single tube T_{ρ}, a typical point in the Besicovitch set lies in at most (δ/ρ)^{−1/2} tubes T in T[T_{ρ}]. This fits with (19), which says that the typical point in the Besicovitch set lies in about δ^{−1/2} tubes T in T). Because of this nice fit, we can in fact also change ⪆ to ≈ in (21) (perhaps after discarding a small number of tubes in T or T_{ρ}).

There is another, more subtle consequence of the three bounds (19), (20), (21). Let B(x, ρ) be a typical ρ-ball contained in ⋃_{T_{ρ}∈T_{ρ}} T_{ρ}. This ball is contained in about ρ^{−1/2} tubes T_{ρ}. For each such tube T_{ρ}, let E[T_{ρ}] denote the set

E[T_{ρ}] := ⋃_{T ∈T[T_{ρ}]} T.

Then a typical point in E[T_{ρ}]∩B(x, ρ) lies in at most (δ/ρ)^{−1/2} tubes in T[T_{ρ}]. On the other hand, we want a typical point in the Besicovitch set to lie in exactly δ^{−1/2} tubes in T. The only way to reconcile these facts if the ρ^{−1/2} sets E[T_{ρ}] ∩ B(x, ρ) have extremely high overlap - they must essentially be the same set. However, if we choose ρ := \sqrt{δ}, then an inspection of the geometry shows that E[T_{ρ}] ∩ B(x, ρ) is essentially invariant under translations by O(ρ) in the direction of T_{ρ}. So the

22This is not trivial, however, and requires an “x-ray” variant of the maximal estimate (2), where instead of having one tube in every direction, one has (say) m tubes in every direction, and then one wants a bound on the right which grows in m. See [52], [31]. The main idea is to consider larger objects than tubes, namely “plates”.

Result  Dimension Value of p
Minkowski n = 3  5/2 + 10^{−10}  Katz-Łaba-Tao 1999 [24]
Minkowski n = 4  3 + 10^{−10}  Łaba-Tao 2000 [32]
Minkowski 23 ≥ n ≥ 5 (2 − \sqrt{2})(n − 4) + 3 Katz-Tao 2000 [26]
Minkowski n > 23  (n − 1)/α + 1  Katz-Tao 2000 [26]
Hausdorff n = 3, 4  (n − 2)/2 + 2  Wolff 1995 [51]
Hausdorff n ≥ 5  (2 − \sqrt{2})(n − 4) + 3 Katz-Tao 2000 [26]
Maximal 8 ≥ n ≥ 3 (n − 2)/2 + 2  Wolff 1995 [51]
Maximal n ≥ 9  4(n − 1)/7 + 1  Katz-Tao 2000 [26]
Finite field n = 3, 4  (n − 2)/2 + 2  Wolff 1995 [51], [54]
Finite field 23 ≥ n ≥ 5 (2 − \sqrt{2})(n − 4) + 3 Katz-Tao 2000 [26]
Finite field n > 23  (n − 1)/α + 1  Katz-Tao 2000 [26]

Figure 1. Current state of progress on the upper Minkowski, Hausdorff, and maximal Kakeya conjectures in R^{n} for n ≥ 3, as well as the finite field Besicovitch set problem. α = 1.675 … is the largest root of α^{3} − 4α + 2 = 0. The maximal estimates also extend to (6) without difficulty.

sets E[T_{ρ}]∩B(x, ρ), being independent of T_{ρ}, contain many translation invariances, and in fact must be invariant in a whole plane’s worth of directions. This creates a useful property which we call “graininess”. There is also a related companion property called “planiness” which we can similarly derive, which states that all the ρ-tubes through a point must essentially lie on a plane. By using graininess and planiness we can in some sense “factor out” a dimension from the three-dimensional problem, which allows us to boost the arithmetic argument (which in three dimensions ordinarily gives a bound of 2 + σ for some small σ ≪ 1) to 5/2 + σ. This allows us, in the final analysis, to boost one of (19) or (20) by a very small quantity, say 10^{−10}. For the full (and rather lengthy) details, see [24].

We summarize the best known results on the various Kakeya problems in Figure 8.

9. Related problems

The ideas and techniques used for the Kakeya problem have also been applied to other problems of a similar flavor. We briefly discuss some of these.

Kolasa, Wolff, Schlag, and Sogge have studied Kakeya-type problems in which lines are replaced by circles in the plane, building upon earlier work of Marstrand, Besicovitch, Rado, and Kinney. Several new issues arise, notably the fact that circles can be tangent to each other and thus have a quite large intersection in the δ-discretized model; this cannot be so easily eliminated by the bilinear reduction. A key combinatorial tool (already developed for discrete analogues of these problems by Szemeredi, Trotter, Clarkson, et al.) is the cell decomposition, in which one selects r circles at random for some relatively small r, uses them to divide the plane into about r^{2} pieces or “cells”, works on each piece separately, and then adds up. The reason this can be advantageous is that each circle will usually only visit about r of these cells, although there are additional difficulties coming from the fact that circles can be tangent to the walls of the cells. Thanks to this tool, the circular maximal functions in the plane have been understood quite satisfactorily (similar to how Kakeya maximal functions are satisfactorily understood in two dimensions). For a survey of this topic (which is already rather immense), see [54].

Wolff, Erdogan, and Christ have studied Kakeya problems in which the line segments are restricted to be light rays, or have slopes restricted to some generic curve in S^{n−1}. Such operators are related to some general classes of Fourier integral operators (as studied by Greenleaf, Seeger, Oberlin, and others), but are completely non-oscillatory in nature and so one expects to be able to prove good estimates for them directly without appeal to FIO theory. The techniques here are partly based on such geometric arguments as the brush argument, but also use some related developments of Christ, Wright, and myself on averaging operators along curves (in which some Kakeya techniques are combined with “iterated T T^{∗}” methods). See [18], [57], [50], …. The hypothesis that the line segments point in different directions can be modified, e.g. to make the line segments extend to reach every point in a ball; this variant of the Kakeya problem is known as the Nikodym problem, but is essentially equivalent to the Kakeya one [45].

There are natural analogues of the Kakeya problem in which line segments are replaced with higher-dimensional spaces such as k-planes. Early work in this direction is by Christ in 1984; there were some improvements by Bourgain [6] but this is still largely an undeveloped area, and it is likely that many of the arguments above will transfer to the k-plane case. It may well be that one needs to progress on the k-plane problem in order to advance on the original Kakeya problem.

Another problem in this area is the Falconer distance set conjecture, which asserts that if a set E has Hausdorff dimension 1 in the plane, then its distance set {|x−y| : x, y ∈ E} has dimension 1 in the real line. This conjecture has both Kakeya-type aspects and oscillatory integral aspects, and is closely related to the Furstenburg set problem as well as the Erdös ring problem - does there exist sub-rings of R of dimension 1/2? See [56], [27].

One can also try to replace lines by other curves, such as geodesics on a Riemannian manifold. Counter-examples by Bourgain [7] (for curves) and Sogge and Minicozzi [33] (for geodesics) show that some of the above results do not transfer to the general curve case, but it is unclear how generic this phenomenon is, and what can be salvaged from this.

10. Conclusion

As you can see, despite all the progress in the last few years, there is still much work to be done. We have many tools and techniques, but it is certainly possible that a completely different type of argument might be able to bring some dramatic progress on the problem. There may be some ideas coming from quite different fields - combinatorics, number theory, perhaps even algebraic geometry - which might yield an unexpectedly simple resolution to an obstruction in the Kakeya problem.

There are many problems to pursue, let me just repeat a couple mentioned earlier which I think are reasonably accessible, and would lead to further progress in the field:

• In four dimensions, there are several arguments which show that Besicovitch sets have dimension at least three, (or have cardinality at least |F |^{3}, in the finite field case). This has been improved (to great effort) to 3 + 10^{−10}, but only for the upper Minkowski dimension. Is it possible to do any better than this?

• In three dimensions, Wolff’s argument gives a dimension bound of 5/2. This has been improved (to great effort) to 5/2 + 10^{−10}, but only for the upper Minkowski dimension. Is it possible to do any better than this? (It may be that improvement on the Furstenburg problem in two dimensions is needed before one can get an improvement here in three dimensions).

• In Z/pZ, does there exist a set G of cardinality ≈ \sqrt{p} such that G + G and G·G also has cardinality ≈ \sqrt{p}? This is directly related to any improvement over (10), (9); see [47]. The recent resolution of the Erdos ring problem [16] may be helpful, although the argument does not seem to directly transfer over.

• Is it possible to lower the ε in (18)? The current “world record” is ε = 0.67514 . . .. (I believe that the techniques pushed in [26] will not extend much beyond the golden ratio ε = 0.618 …, though ε = 2/3 = 0.66667 … seems feasible. A completely different combinatorial argument may be required; this paradigm of getting lower and upper bounds for the number of configurations of a certain combinatorial shape may be misleading).

• There has been almost no work on the k-plane problem since Bourgain’s paper [6] in 1991. It should be possible to improve on these results dramatically, especially in the finite field case where there are no technicalities concerning non-transverse intersections, etc. The 2-plane problem seems particularly relevant to Kakeya, since 2-planes arise all over the place in our current arguments.

• As Figure 8 shows, there is some disparity between the results on the “easy” end of the spectrum (finite fields, Minkowski) and the “useful” end (maximal functions, etc.). One should be able to resolve the technical obstructions preventing the former results from being transferred to the latter; this may clarify the relationship between the problems.

• In the plane R^{2}, the Szemerédi-Trotter theorem gives a very sharp bound for the number of incidences between points and lines. This ought to lead to progress on the Furstenburg problem in two dimensions, but the issue of small separations seems to cause a serious difficulty. Nevertheless, the proof techniques used in the Szemerédi-Trotter theorem (notably the cell decomposition and crossing number inequalities, both of which utilize the ordering of R) should be useful in the Kakeya problem in Euclidean spaces; so far they have made no real appearance in the arguments.

References

[1] A. Balog, E. Szemerédi, A statistical theorem of set addition, Combinatorica, 14 (1994), 263–268.

[2] J. Barrionuevo, A note on the Kakeya maximal operator, Math. Res. Lett. 3 (1996), 61–65.

[3] W. Beckner, A. Carbery, S. Semmes, F. Soria, A note on restriction of the Fourier transform to spheres., Bull. London Math. Soc. 21 (1989), no. 4, 394–398.

[4] A. Besicovitch, On Kakeya’s problem and a similar one, Mat. Zeit. 27 (1928), 312-320.

[5] B. Bollobas, Extremal Graph Theory, Academic Press, London 1978.

[6] J. Bourgain, Besicovitch-type maximal operators and applications to Fourier analysis, Geom. and Funct. Anal. 22 (1991), 147–187.

[7] J. Bourgain, Some new estimates on oscillatory integrals, Essays in Fourier Analysis in honor of E. M. Stein, Princeton University Press (1995), 83–112.

[8] J. Bourgain, On the dimension of Kakeya sets and related maximal inequalities, Geom. Funct. Anal. 9 (1999), no. 2, 256–282.

[9] J. Bourgain, Harmonic analysis and combinatorics: How much may they contribute to each other?, Mathematics: Frontiers and perspectives, IMU/Amer. Math. Society 2000, 13–32.

[10] M. Christ, J. Duoandikoetxea, and J. L. Rubio de Francia, Maximal operators associated to the Radon transform and the Calderón-Zygmund method of rotations, Duke Math. J. 53 (1986), 189-209.

[11] A. Córdoba, Geometric Fourier analysis, Ann. Inst. Fourier (Grenoble) 32 (1982), no. 3, 215–226.

[12] A. Córdoba, Maximal functions, covering lemmas and Fourier multipliers, Harmonic analysis in Euclidean spaces (Proc. Sympos. Pure Math., Williams Coll., Williamstown, Mass., 1978), Part 1, pp. 29–50, Proc. Sympos. Pure Math., XXXV, Part, Amer. Math. Soc., Providence, R.I., 1979.

[13] A. Córdoba, The Kakeya maximal function and the spherical summation multipliers, Amer. J. Math. 99 (1977), 1–22.

[14] R.O. Davies, Some remarks on the Kakeya problem, Proc. Cambridge Phil. Soc. 69 (1971), 417–421.

[15] S. Drury, L^{p} estimates for the x-ray transform, Ill. J. Math. 27 (1983), 125–129.

[16] G. Edgar, C. Miller, Borel subrings of the reals, preprint.

[17] G. Elekes, On the number of sums and products, Acta Arith. 81 (1997), 365–367.

[18] M. Erdogan. Mixed norm estimates for the X-ray transform restricted to a rigid well-curved line complex in a R^{4} and R^{5}, preprint.

[19] C. Fefferman, The multiplier problem for the ball, Ann. of Math. 94 (1971): 330–336.

[20] T. Gowers, A new proof of Szemerédi’s theorem for arithmetic progressions of length four, GAFA 8 (1998), 529–551.

[21] T. Gowers, A new proof of Szemerédi’s theorem, GAFA 11 (2001), 465–588.

[22] D. Heath-Brown, Integer sets containing no arithmetic progressions, J. London Math. Soc. (2) 35 (1987), 385-394.

[23] N. Katz, Remarks on maximal operators over arbitrary sets of directions, Bull. London Math. Soc. 31 (1999), 700–710.

[24] N. Katz, I. Łaba, T. Tao, An improved bound for the Minkowski dimension of Besicovitch sets in R^{3}, Annals of Math. 152 (2000), 383-446.

[25] N. Katz, T. Tao: Bounds on arithmetic projections, and applications to the Kakeya conjecture, Math Res. Letters 6 (1999), 625–630.

[26] N. Katz, T. Tao, New bounds for the Kakeya problems, to appear, Journal d’Analyse de Jerusalem.

[27] N. Katz, T. Tao, Some connections between the Falconer and Furstenburg conjectures, New York J. Math. 7 (2001), 148–187.

[28] N. Katz, T. Tao, Recent progress on the Kakeya conjecture, to appear, Publicacions Matematiques, (El Escorial Proceedings)

[29] U. Keich, On L^{p} bounds for Kakeya maximal functions and the Minkowski dimension in R^{2}, Bull. London Math. Soc. 31 (1999), 213–221.

[30] L. Kolasa, T. Wolff, On some variants of the Kakeya problem, Pacific J. Math 190 (1999), 111–154.

[31] I. Łaba, T. Tao: An x-ray estimate in R^{n}, to appear, Revista Iberoamericana.

[32] I. Łaba, T. Tao: An improved bound for the Minkowski dimension of Besicovitch sets in medium dimension, GAFA 11 (2001), 773-806.

[33] W. P. Minicozzi II, C. D. Sogge, Negative results for Nikodym maximal functions and related oscillatory integrals in curved space, Math. Res. Lett. 4 (1997), 221-237.

[34] G. Mockenhaupt, A. Seeger, C.D. Sogge, Wave front sets, local smoothing and Bourgain’s circular maximal theorem., Ann. of Math. 136 (1992), 207–218.

[35] G. Mockenhaupt, T. Tao, Kakeya and restriction phenomena for finite fields, submitted, Duke Math. J.

[36] K. Rogers, The finite field Kakeya problem, Amer. Math. Monthly, Oct 2001, 756–759.

[37] I. Ruzsa, Sums of finite sets, Number Theory: New York Seminar; Springer-Verlag (1996), D.V. Chudnovsky, G.V. Chudnovsky and M.B. Nathanson editors.

[38] W. Schlag, A generalization of Bourgain’s circular maximal theorem, J. Amer. Math. Soc. 10 (1997), 103-122.

[39] W. Schlag, A geometric proof of the circular maximal theorem, Duke Math. J., 93 (1998), 503–533.

[40] W. Schlag, A geometric inequality with applications to the Kakeya problem in three dimensions, Geometric and Functional Analysis 8 (1998), 606–625.

[41] C. D. Sogge, Concerning Nikodym-type sets in 3-dimensional curved space, preprint.

[42] E. M. Stein, On limits of sequences of operators, Ann. of Math. 74 (1961): 140-170.

[43] E. M. Stein, Some problems in harmonic analysis, Harmonic analysis in Euclidean spaces (Proc. Sympos. Pure Math., Williams Coll., Williamstown, Mass., 1978), Part 1, pp. 3–20.

[44] E. M. Stein, Harmonic Analysis, Princeton University Press, 1993.

[45] T. Tao, The Bochner-Riesz conjecture implies the Restriction conjecture, Duke Math J. 96 (1999), 363-376.

[46] T. Tao, From rotating needles to stability of waves: emerging connections between combinatorics, analysis, and PDE, Notices Amer. Math. Soc. 48 (2001), 294-303.

[47] T. Tao, Finite field analogues of the Erdos, Falconer, and Furstenburg problems, unpublished preprint.

[48] T. Tao, The restriction and Kakeya conjectures, unpublished lecture notes, IPAM March 2001.

[49] T. Tao, A. Vargas, L. Vega, A bilinear approach to the restriction and Kakeya conjectures, J. Amer. Math. Soc. 11 (1998), pp. 967–1000.

[50] T. Tao, J. Wright, L^{p} improving estimates for averages along curves, submitted.

[51] T. Wolff, An improved bound for Kakeya type maximal functions, Revista Mat. Iberoamericana. 11 (1995). 651–674.

[52] T. Wolff, A mixed norm estimate for the x-ray transform, Revista Mat. Iberoamericana. 14 (1998), 561-600.

[53] T. Wolff, A Kakeya type problem for circles, Amer. J. Math. 119 (1997), 985–1026.

[54] T. Wolff, Recent work connected with the Kakeya problem, Prospects in mathematics (Princeton, NJ, 1996), 129–162, Amer. Math. Soc., Providence, RI, 1999.

[55] T. Wolff, Maximal averages and packing of one-dimensional sets, Proceedings of the International Congress of Mathematics, Berlin 1998 Vol II, 755–764.

[56] T. Wolff, Decay of circular means of Fourier transforms of measures, Internat. Math. Res. Notices 10 (1999), 547–567.

[57] T. Wolff, A sharp bilinear cone restriction estimate, Ann. of Math. 153 (2001), 661–698.

[58] T. Wolff, Local smoothing type estimates on L^{p} for large p, Geom. Funct. Anal. 10 (2000), 1238–1288.

[59] T. Wolff, Lecture notes in harmonic analysis, preprint.

Department of Mathematics, UCLA, Los Angeles CA 90095-1555

E-mail address: tao@math.ucla.edu