Recent work connected with the Kakeya problem

Thomas Wolff Department of Mathematics 253-37 Caltech Pasadena, Ca 91125 USA wolff@cco.caltech.edu

A \underline{Kakeya set} in ℝ^{n} is a compact set E ⊂ ℝ^{n} containing a unit line segment in every direction, i.e.

∀e ∈ S^{n−1}∃x ∈ ℝ^{n} : x + te ∈ E ∀t ∈ [−\frac{1}{2}, \frac{1}{2}]  (1)

where S^{n−1} is the unit sphere in ℝ^{n}. This paper will be mainly concerned with the following issue, which is still poorly understood: what metric restrictions does the property (1) put on the set E?

The original Kakeya problem was essentially whether a Kakeya set as defined above must have positive measure, and as is well-known, a counterexample was given by Besicovitch in 1920. A current form of the problem is as follows:

\underline{Open question 1}: Must a Kakeya set in ℝ^{n} have Hausdorff dimension n?

When n = 2, the answer is yes; this was proved by Davies [19] in 1971. Recent work on the higher dimensional question began with [7]. If dimE denotes the Hausdorff dimension then the bound dimE ≥ \frac{n+1}{2} can be proved in several ways and may have been known prior to [7], although the author has not been able to find a reference. The recent work [7], [60] has led to the small improvement dimE ≥ \frac{n+2}{2}. We will discuss this in section 2 below.

Question 1 appears quite elementary, but is known to be connected to a number of basic open questions in harmonic analysis regarding estimation of oscillatory integrals. This is a consequence of C. Fefferman’s solution of the disc multiplier problem [23] and work of Cordoba (e.g. [18]) and Bourgain (e.g. [7], [9], [10]). We will say something about these interrelationships in section 4. There is also a long history of applications of Kakeya sets to construct counterexamples in pointwise convergence questions; we will not discuss this here, but see e.g. [25] and [54].

For various reasons it is better to look also at a more quantitative formulation in terms of a maximal operator. If δ > 0, e ∈ S^{n−1}, a ∈ ℝ^{n} then we define

T δ_{e}(a) = \{x ∈ ℝ^{n} : |(x − a) · e| ≤ \frac{1}{2}, |(x − a)^{⊥}| ≤ δ\}

where x^{⊥} = x − (x · e)e. Thus T δ_{e}(a) is essentially the δ-neighborhood of the unit line segment in the e direction centered at a. If f : ℝ^{n} → ℝ then we define its Kakeya maximal function fδ^{∗} : S^{n−1} → ℝ via

fδ^{∗}(e) = sup_{a∈ℝ^{n}} \frac{1}{|T δ_{e}(a)|} ∫_{Tδ_{e}(a)} |f|

This definition is due to Bourgain [7]. It is one of several similar maximal functions that have been considered, going back at least to [18].

\underline{Open question 2}: Is there an estimate

∀ϵ > 0∃Cϵ : ∥fδ^{∗}∥_{L^{n}(S^{n−1})} ≤ Cϵδ^{−ϵ}∥f∥_{n}∀f  (2)

Roughly speaking, this question is related to question 1 in the same way as the Hardy-Littlewood maximal theorem is related to Lebesgue’s theorem on points of density. As was observed by Bourgain [7], an affirmative answer to question 2 implies an affirmative answer to question 1; see Lemma 1.6 below. Once again, when n = 2 it is well known that the answer to question 2 is affirmative, [18] and [7]. In higher dimensions, partial results are known parallelling the results on question 1.

Questions 1 and 2 clearly have a combinatorial side to them, and the point of view we will adopt here is to try to approach the combinatorial issues directly using ideas from the combinatorics literature. In this connection let us mention a basic principle in graph theory (the “Zarankiewicz problem”; see [5], [24], [40] for this and generalizations): fix s and suppose that {a_{ij}}_{i=1 j=1}^{n m} is an n × m (0, 1) matrix with no s × s submatrix of 1’s. Then there is a bound

|\{(i, j) : a_{ij} = 1\}| ≤ C_{s} min(mn^{1− \frac{1}{s}} + n, nm^{1− \frac{1}{s}} + m)  (3)

To see the relationship between this sort of bound and Kakeya, just note that if {ℓ_{j}}_{j=1}^{m} are lines and {p_{i}}_{i=1}^{n} are points, then the “incidence matrix”

a_{ij} = \{ \begin{matrix}1 & if p_{i} ∈ ℓ_{j} \\ 0 & if p_{i} ∉ ℓ_{j} \end{matrix}

will contain no 2×2 submatrix of 1’s, since two lines intersect in at most one point. Much of what we will say below will have to do with attempts to modify this argument, and also more sophisticated arguments in incidence geometry (e.g. [17]) to make them applicable to “continuum” problems such as Kakeya.

There are several difficulties with such an approach. It is sometimes unclear whether applying the combinatorial techniques in the continuum should be simply a matter of extra technicalities or whether new phenomena should be expected to occur, and furthermore many of the related discrete problems are regarded as being very difficult. A classical example is the Erdos unit distance problem (see [17] and [40]) and other examples will be mentioned in section 3.

Of course, much work has been done in the opposite direction, applying harmonic analysis techniques to questions of a purely geometrical appearance. A basic example is the spherical maximal theorem of Stein [51], and various Strichartz type inequalities as well as the results on the distance set problem in [22], [11] are also fairly close to the subject matter of this paper. However, we will not present any work of this nature here.

The paper is organized as follows. In section 1 we discuss the two dimensional Kakeya problem, in section 2 we discuss the higher dimensional Kakeya problem and in section 3 we discuss analogous problems for circles in the plane. Finally in section 4 we discuss the Fefferman construction and a related construction of Bourgain [9] which connects the Kakeya problem also to estimates of Dirichlet series. Section 4 contains several references to the recent literature on open problems regarding oscillatory integrals, but it is not a survey. Further references are in [10], [58], and especially [52].

We have attempted to make the presentation self-contained insofar as is possible. In particular we will present some results and arguments which are known or almost known but for which there is no easy reference.

The author is grateful for the opportunity to speak at the conference and to publish this article.

List of notation [α]: greatest integer less than or equal to α. p′: conjugate exponent to p, i.e. p′ = \frac{p}{p−1}. D(x, r): the disc with center x and radius r. |E|: Lebesgue measure or cardinality of the set E, depending on the context. E^{c}: complement of E. dimE: Hausdorff dimension of E. H_{s}(E): s-dimensional Hausdorff content of E, i.e. H_{s}(E) = inf(∑_{j} r_{j}^{s} : E ⊂ ∪_{j}D(x_{j}, r_{j})) T δ_{e}(a): δ-tube in the e direction centered at a, as defined in the introduction. Sometimes we will also use the notation T δ_{e}; this means any tube of the form T δ_{e}(a) for some a ∈ ℝ^{n}. C(x, r): circle in ℝ^{2} (or sphere in ℝ^{n}) with center x and radius r. Cδ(x, r): annular region {y ∈ ℝ^{n} : r − δ < |y − x| < r + δ}. x ≲ y: x ≤ Cy for a suitable constant C.

1. The two dimensional case We will start by proving the existence of measure zero Kakeya sets using a variant on

the original construction which is quick and is easy to write out in closed form; to the author’s knowledge the earliest reference for this approach is Sawyer [42]. A discussion of various other possible approaches to the construction may be found in [21].

For expository reasons, we make the following definitions.

A \underline{G-set} is a compact set E ⊂ ℝ^{2} which is contained in the strip \{(x, y) : 0 ≤ x ≤ 1\}, such that for any m ∈ [0, 1] there is a line segment contained in E connecting x = 0 to x = 1 with slope m, i.e.

∀m ∈ [0, 1]∃b ∈ ℝ : mx + b ∈ E ∀x ∈ [0, 1]

If ℓ = {(x, y) : y = mx + b} is a nonvertical line, δ > 0, then Sδ_{ℓ} =^{def} {(x, y) : 0 ≤ x ≤ 1 and |y − (mx + b)| ≤ δ}.

\underline{Remark 1.1} It is clear that existence of G-sets with measure zero will imply existence of Kakeya sets with measure zero. Note also that if ℓ is a line with slope m then Sδ_{ℓ} will contain segments connecting x = 0 to x = 1 with any given slope between m − 2δ and m + 2δ.

We now describe the basic construction, which leads to the slightly weaker conclusion (Lemma 1.2) that there are G-sets with measure < ϵ for any ϵ > 0. It can be understood in terms of the usual sliding triangle picture: start from a right triangle with vertices (0, 0), (0, −1) and (1, 0); this is clearly a G-set. Subdivide it in N “1st stage” triangles by subdividing the vertical side in N equal intervals. Leave the top triangle alone and slide the others upward so that their intersections with the line x = 0 all coincide. Next, for each of the 1st stage triangles, subdivide it in N 2nd stage triangles, leave the top triangle in each group alone and slide the N − 1 others upward until the intersections of the N triangles in the group with the line x = \frac{1}{N} all coincide. Now repeat at abscissas \frac{2}{N}, \frac{3}{N}, …, \frac{N−1}{N}.

Now we make this precise. Fix a large integer N and let A_{N} be all numbers in [0, 1) whose base N expansion terminates after N digits, i.e.

a ∈ A_{N} ⇔ a = ∑_{j=1}^{N} \frac{a_{j}}{N^{j}} with a_{j} ∈ \{0, 1, … N − 1\}

To each a ∈ A_{N} we associate the line segment ℓ_{a} connecting the y axis to the line x = 1 with slope a and y intercept − ∑_{j=1}^{N} \frac{(j−1)a_{j}}{N^{j+1}} . Thus

ℓ_{a} = \{(t, ϕ_{a}(t)) : 0 ≤ t ≤ 1\}, where ϕ_{a}(t) = ∑_{j=1}^{N} \frac{(Nt − j + 1)a_{j}}{N^{j+1}}

\underline{Lemma 1.1} For each t ∈ [0, 1] there are an integer k ∈ \{1, …, N\} and a set of N^{k−1} intervals each of length 2N^{−k}, whose union contains the set {ϕ_{a}(t) : a ∈ A_{N}}.

\underline{Proof} Choose k so that \frac{k−1}{N} ≤ t ≤ \frac{k}{N}. Define a, b ∈ A_{N} to be equivalent if a_{j} = b_{j} when j ≤ k − 1. There are N^{k−1} equivalence classes, and if a and b are equivalent then

|ϕ_{a}(t) − ϕ_{b}(t)| = | ∑_{j≥k} \frac{(Nt − j + 1)(a_{j} − b_{j})}{N^{j+1}}|

≤ ∑_{j≥k} \frac{max(j − k, 1)|a_{j} − b_{j}|}{N^{j+1}}

≤ \frac{N − 1}{N^{k+1}} ∑_{j≥k} \frac{max(j − k, 1)}{N^{j−k}}

≤ 2\frac{N − 1}{N^{k+1}} < \frac{2}{N^{k}}

when N is large. □

\underline{Lemma 1.2} Let N be sufficiently large. Then there is a G-set E ⊂ [0, 1]×[−1, 1] which intersects every vertical line in measure ≤ \frac{4}{N}, in particular |E| ≤ \frac{4}{N}.

\underline{Proof} We let

E_{N} = ∪_{a∈A_{N}} S_{ℓ_{a}}^{N^{−N}}

Then E_{N} contains segments with all slopes between 0 and 1, by Remark 1.1. If t ∈ [0, 1], then by Lemma 1.1 there is k ∈ {1, …, N} such that the intersection of E with the line x = t is contained in the union of N^{k−1} intervals of length 2N^{−k} + 2N^{−N} ≤ 4N^{−k}. The lemma follows. □

Existence of measure zero Kakeya sets now follows by a standard limiting argument, most easily carried out via the following lemma.

\underline{Lemma 1.3}: For every G-set E and every ϵ > 0, η > 0, there is another G-set F, which is contained in the ϵ-neighborhood of E and has measure < η.

\underline{Proof} Let δ be small, let \{m_{j}\} = \{jδ\}_{j=0}^{[ \frac{1}{δ}]} and for each j, fix a line segment ℓ_{j} = {(x, y) : 0 ≤ x ≤ 1, y = m_{j}x + b_{j}} ⊂ E with slope m_{j} connecting x = 0 to x = 1 and form the parallelogram Sδ_{ℓ_{j}}. Let A_{j} be the affine map from [0, 1] × [−1, 1] on Sδ_{ℓ_{j}}, A_{j}(x, y) = (x, m_{j}x + b_{j} + δy) and consider F = ∪_{m}A_{m}(E_{N}) for a large enough N; here E_{N} is as in Lemma 1.2. A_{j} maps segments with slope μ to segments with slope m + δμ so F is a G-set. Clearly it is contained in the δ-neighborhood of E. Furthermore A_{j} contracts areas by a factor δ so |A_{j}(E_{N})| ≤ 4\frac{δ}{N} for each j, hence |F | ≲ \frac{1}{N}. □

\underline{Corollary 1.4} There are Kakeya sets with measure zero.

\underline{Proof} We construct a sequence \{F_{n}\}_{n=0}^{∞} of G-sets, and a sequence of numbers \{ϵ_{n}\}_{n=0}^{∞} converging to zero such that the following properties hold when n ≥ 1; here F (ϵ) =^{def} {x : dist(x, F) < ϵ\} is the ϵ-neighborhood of F and \overline{E} is the closure of E.

(i) F_{n}(ϵ_{n}) ⊂ F_{n−1}(ϵ_{n−1})

(ii) |\overline{F_{n}(ϵ_{n})}| < 2^{−n}.

Namely, we take F_{0} to be any G-set, and we set ϵ_{0} = 1. If n ≥ 1 and if F_{n−1} and ϵ_{n−1} have been constructed then we obtain F_{n} by applying Lemma 1.3 with ϵ = ϵ_{n−1} and η = 2^{−n}. Since F_{n} is compact, (i) and (ii) will then hold provided ϵ_{n} is sufficiently small.

The set ∩_{n}\overline{F_{n}(ϵ_{n})} is then a G-set with measure zero. □

\underline{Remarks} 1.2. The construction above easily gives the following variant (used e.g. in [23]): with δ = \frac{1}{10}N^{−N}, there is a family of disjoint δ-tubes \{T δ_{e_{j}}(x_{j})\}_{j=1}^{M} ⊂ ℝ^{2} where

M ≈ δ^{−1} with the property that the union of the translated tubes T δ_{e_{j}}(x_{j} + 2e_{j}) has measure ≲ \frac{1}{N}.

Namely, a calculation shows that if a, b ∈ A and a < b then ϕ_{a}(1) < ϕ_{b}(1), i.e. the ordering of the intersection points between the ℓ_{a} and the line x = 1 is the same as the ordering of slopes. Hence if we regard ℓ_{a} as extended to a complete line, then no two ℓ_{a}’s intersect in the region x > 1, and in fact in the region x > 2 any two of them are at least N^{−N} apart. Now for each a ∈ A_{N} we form the rectangle R_{a} with length 1, width \frac{1}{5}N^{−N}, axis along the line ℓ_{a} and bottom right corner on the line x = 1. Clearly R_{a} ⊂ S_{a}, so ∪_{a}R_{a} is small by Lemma 1.2. On the other hand, if R_{a} is translated to the right along its axis by distance 2 then the resulting rectangles are disjoint. We may therefore take {T δ_{e_{j}}(x_{j})} to be the set of translated rectangles.

1.3. Analogous statements in higher dimensions may be obtained using dummy variables.

Measure zero Kakeya sets in ℝ^{n} may be constructed by taking the product of a Kakeya set in ℝ^{2} with a closed disc of radius \frac{1}{2} in ℝ^{n−2} (or for that matter with any Kakeya set in ℝ^{n−2}), and a family of roughly δ^{−(n−1)} disjoint T δ_{e}(a)’s such that the union of the tubes T δ_{e}(a + 2e) has small measure may be obtained by taking the products of the tubes in Remark 1.2 with a family of δ^{−(n−2)} disjoint δ-discs in ℝ^{n−2}.

We now discuss the positive results on questions 1 and 2 in dimension two. Proposition 1.5 was first stated and proved in [7] although a similar result for a related maximal function was proved earlier in [18].

We will work with restricted weak type estimates instead of with L^{p} estimates; this is known to be equivalent except for the form of the δ^{−ϵ} terms.^{1} We will say (see e.g. [53]) that an operator T has restricted weak type norm ≤ A, written

∥T f∥_{q,∞} ≤ A∥f∥_{p,1}

if |\{x : |T χ_{E}(x)| ≥ λ\}| ≤ (\frac{A|E|^{\frac{1}{p}}}{λ})^{q} for all sets E with finite measure and all λ ∈ (0, 1]; here χ_{E} is the characteristic function of E.

\underline{Proposition 1.5} The restricted weak type (2, 2) norm of the Kakeya maximal operator

f → fδ^{∗} in ℝ^{2} is ≲ (log \frac{1}{δ})^{\frac{1}{2}} .

More explicitly, suppose that E ⊂ ℝ^{2} and λ ∈ (0, 1]. Let f = χ_{E}, and let Ω = {e ∈

S^{1} : fδ^{∗}(e) ≥ λ}. Then

|Ω| ≲ log \frac{1}{δ} \frac{|E|}{λ^{2}}

\underline{Proof} Let θ(e, f) be the unoriented angle subtended by the directions e and f, i.e. θ(e, f) = arccos(e · f). We start by mentioning two trivial but important facts. First, in ℝ^{n}, the intersection of the tubes T δ_{e}(a) and T δ_{f}(b) satisfies

diam(T δ_{e}(a) ∩ T δ_{f}(b)) ≲ \frac{δ}{θ(e, f) + δ}  (4)

for any a and b and therefore also

|T δ_{e}(a) ∩ T δ_{f}(b)| ≲ \frac{δ^{n}}{θ(e, f) + δ}  (5)

Next, if Ω is a set on the unit sphere S^{n−1} ⊂ ℝ^{n} and if δ > 0 then the δ-entropy Nδ(Ω) (maximum possible cardinality M for a δ-separated subset {e_{j}}_{j=1}^{M} ⊂ Ω) satisfies

Nδ(Ω) ≳ \frac{|Ω|}{δ^{n−1}}  (6)

Now we assume n = 2 and give the proof of the proposition. Fix a δ-separated {e_{j}}_{j=1}^{M} ⊂ Ω, where M ≳ \frac{|Ω|}{δ}. For each j, there is a tube T_{j} = T δ_{e_{j}}(a_{j}) with |T_{j} ∩ E| ≥ λ|T_{j}| ≈ λδ. Thus

Mλδ ≲ ∑_{j} |T_{j} ∩ E|

1We work with restricted weak type estimates for expository reasons only. We believe this makes the results more transparent; however, it is well known that actually ∥fδ^{∗}∥_{L^{2}(S^{1})} ≲ (log\frac{1}{δ})^{\frac{1}{2}} ∥f∥_{2}. The latter estimate is proved in [7] and also follows from the proof below, plus duality, as in [18].

= ∫_{E} ∑_{j} χ_{T_{j}}
≤ |E|^{\frac{1}{2}} ∥ ∑_{j} χ_{T_{j}}∥_{2}
= |E|^{\frac{1}{2}} (∑_{j,k} |T_{j} ∩ T_{k}|)^{\frac{1}{2}}

≲ |E|^{\frac{1}{2}} (∑_{j,k} \frac{δ^{2}}{θ(e_{j}, e_{k}) + δ})^{\frac{1}{2}}

For fixed k the sum over j is ≲ ∑_{j:|j−k|≤ \frac{C}{δ}} \frac{δ^{2}}{|j−k|δ+δ} ≲ δlog \frac{1}{δ}. We conclude that Mλδ ≲

|E|^{\frac{1}{2}} (Mδlog \frac{1}{δ})^{\frac{1}{2}} which gives the result since M ≳ \frac{|Ω|}{δ}. □

Now we show how to pass to the Hausdorff dimension statement. The next result is Lemma 2.15 in [7].

\underline{Lemma 1.6} Assume an estimate in ℝ^{n}

∥fδ^{∗}∥_{q,∞} ≤ Cδ^{−α}∥f∥_{p,1}  (7)

Then Kakeya sets have dimension at least n − pα.

\underline{Proof} Fix s < n − pα. Let E be a Kakeya set and for each e ∈ S^{n−1}, fix a point x_{e} such that x_{e} + te ∈ E when t ∈ [−\frac{1}{2}, \frac{1}{2}]. We have to bound H_{s}(E) from below, so fix a covering of E by discs D_{j} = D(x_{j}, r_{j}). We can evidently suppose all r_{j}’s are ≤ 1.

Let Σ_{k} = {j : 2^{−k} ≤ r_{j} ≤ 2^{−(k−1)}}, ν_{k} = |Σ_{k}| and E_{k} = E ∩ (∪{D_{j} : j ∈ Σ_{k}}). Also let D̃_{j} = D(x_{j}, 2r_{j}), and Ẽ_{k} = ∪{D̃_{j} : j ∈ Σ_{k}}.

Then ∪_{k}E_{k} = E, so for each e the pigeonhole principle implies |\{t ∈ [−\frac{1}{2}, \frac{1}{2}] : x_{e} + te ∈ E_{k}\}| ≥ \frac{c}{k^{2}} for some k = k_{e}, where c = \frac{6}{π^{2}} . By the pigeonhole principle again, we can find a fixed k so that k = k_{e} when e ∈ Ω, where Ω ⊂ S^{n−1} has measure ≥ \frac{c}{k^{2}} . With this k, we note that Ẽ_{k} contains a disc of radius 2^{−k} centered at each point of E_{k}; it follows easily that if e ∈ Ω then |T_{e}^{2^{−k}}(x_{e}) ∩ Ẽ_{k}| ≳ k^{−2}|T_{e}^{2^{−k}}(x_{e})|. With f = χẼ_{k} we therefore have

|{e : f_{2^{−k}}^{∗}(e) ≥ C^{−1}k^{−2}}| ≳ k^{−2}

On the other hand, by the assumption (7)

|\{e : f_{2^{−k}}^{∗}(e) ≥ C^{−1}k^{−2}\}| ≲ (k^{2}2^{kα}|Ẽ_{k}|^{\frac{1}{p}})^{q}

and |Ẽ_{k}| ≲ ν_{k}2^{−kn}. So (k^{2}2^{kα}(ν_{k}2^{−kn})^{\frac{1}{p}})^{q} ≳ k^{−2}, or equivalently ν_{k} ≳ k^{− \frac{2}{p} (1+ \frac{1}{q})}2^{k(n−pα)}. Letting ϵ = n − pα − s > 0, we have ∑_{j} r_{j}^{s} ≳ ν_{k}2^{−ks} ≳ k^{−2p(1+ \frac{1}{q})}2^{kϵ} ≥constant. □.

Applying this with p = n = 2 we see that Proposition 1.5 implies Davies’ theorem that Kakeya sets in ℝ^{2} have dimension 2. Likewise it follows that yes on question 2 for a given n will imply yes on question 1 for the same n.

\underline{Remark 1.4} It is clear that the logarithmic factor in Proposition 1.5 cannot be dropped entirely, since then the above argument would show that measure zero Kakeya sets could not exist. In fact it has been known for a long time that the exponent \frac{1}{2} cannot be improved, and U. Keich [29] recently showed that even a higher order improvement is not possible in Proposition 1.5 or in its corollary on L^{p} for p > 2. On the other hand, a number of related questions concerning logarithmic factors have been solved only recently or are still open. In particular we should mention the results of Barrionuevo [2] and Katz [26],[27] on the question of maximal functions defined using families of directions in the plane.

\underline{Remark 1.5} An interesting open question in ℝ^{2} is the following one, which arose from work of Furstenburg.

For a given α ∈ (0, 1], suppose that E is a compact set in the plane, and for each e ∈ S^{1} there is a line ℓ_{e} with direction e such that dim(ℓ_{e} ∩ E) ≥ α. Then what is the smallest possible value for dimE?

Easy results here are that dimE ≥ max(2α, \frac{1}{2} + α) and that there is an example with dimE = \frac{1}{2} + \frac{3}{2}α. We give proofs below. Several people have unpublished results on this question and it is unlikely that the author was the first to observe these bounds; in all probability they are due to Furstenburg and Katznelson.

The analogous discrete question is solved by the following result due to Szemeredi and Trotter [56] (see also [17], [40]).

Suppose we are given n points {p_{i}} and k lines {ℓ_{j}} in the plane. Define a line and point to be \underline{incident}, p ∼ ℓ, if p lies on ℓ. Let I = \{(i, j) : p_{i} ∼ ℓ_{j}\}. Then |I| ≲ (kn)^{\frac{2}{3}} + k + n, and this bound is sharp.

We note that the weaker bound |I| ≲ (kn)^{\frac{3}{4}} +k+n follows from (3) and was known long before [56]. To see the analogy with the Hausdorff dimension question, reformulate the Szemeredi-Trotter bound as follows: if each line is incident to at least μ points (μ >> 1), then (since |I| ≥ kμ)

n ≳ min(μ^{\frac{3}{2}} k^{\frac{1}{2}} , μk)  (8)

Now assume say^{2} that E has a covering by n discs D_{i} of radius δ. Consider a set of k ≈ δ^{−1} δ-separated directions {e_{j}}. For each j the line ℓ_{e_{j}} will intersect D_{i} for at least δ^{−α} values of i. We now pretend that we can replace points by the discs D_{i} in Szemeredi-Trotter and apply (8) with μ = δ^{−α}, k = δ^{−1}. Since k ≥ μ we would obtain n ≳ δ^{− \frac{1}{2} − \frac{3}{2} α}, i.e. that the bound dimE ≥ \frac{1}{2} + \frac{3}{2}α should hold.

2In this heuristic argument we ignore the distinction between Hausdorff and Minkowski dimension.

In one situation to be discussed in section 3, it turns out that this kind of heuristic argument can be justified leading to a theorem in the continuum. In other situations such as the present one, it seems entirely unclear whether this should be the case or not, but still the discrete results suggest plausible conjectures.

If correct the bound dimE ≥ \frac{1}{2} + \frac{3}{2}α would be best possible by essentially the same example (due to Erdos, see [40]) that shows the Szemeredi-Trotter bound is sharp.

We start by recalling that if {n_{j}} is a sequence of integers which increases sufficiently rapidly, and if α ∈ (0, 1) then the set

T =^{def} \{x ∈ (\frac{1}{4}, \frac{3}{4}) : ∀j∃p, q ∈ ℤ : q ≤ n_{j}^{α} and |x − \frac{p}{q}| ≤ n_{j}^{−2}\}

has Hausdorff dimension α. This is a version of Jarnik’s theorem - see [21], p. 134, Theorem 8.16(b).

It follows that the set

T′ = \{t : \frac{1 − t}{t\sqrt{2}} ∈ T \}

also has dimension α.

For fixed n, consider the set of all line segments ℓ_{jk} connecting a point (0, \frac{j}{n}) to a point (1, \frac{k}{n} \sqrt{2}), where j and k are any integers between 0 and n − 1. Thus ℓ_{jk} = \{(x, ϕ_{jk}(x)) : 0 ≤ x ≤ 1\} where ϕ_{jk}(x) = (1 − x)\frac{j}{n} + x\frac{k}{n} \sqrt{2}. It follows using e.g. [32], p. 124, example 3.2 that every number in [0, 1] differs by ≲ n^{−2}(log n)^{2} from the slope of one of the ℓ_{jk}’s,

so the set G_{n} =^{def} ∪_{jk}S_{ℓ_{jk}}^{n^{−2}(log n)^{3}} is a G-set.

Define

Q_{n} = \{t : \frac{1 − t}{t\sqrt{2}} is a rational number \frac{p}{q} ∈ (\frac{1}{4}, \frac{3}{4}) with denominator q ≤ n^{α}\}

If t ∈ Q_{n}, then let S(t) =^{def} \{ϕ_{jk}(t)\}_{j,k=0}^{n−1}. For any j and k we have (t\sqrt{2})^{−1}ϕ_{jk}(t) = \frac{pj+qk}{qn},

a rational with denominator qn. We conclude that |S(t)| ≲ qn ≤ n^{1+α}, hence | ∪ (S(t) : t ∈ Q_{n})| ≲ n^{1+3α} and

(∗) The set \{(x, y) ∈ G_{n} : |x − t| ≤ \frac{1}{n^{2}} for some t ∈ Q_{n}\} is contained in the union of ≲ n^{1+3α} discs of radius n^{−2}(log n)^{3}.

Now we let {n_{j}} increase rapidly and will recursively construct compact sets F_{j} such that F_{j+1} ⊂ F_{j}, each F_{j} is a G-set and the set {(x, y) ∈ F_{j} : x ∈ T′} is contained in the union of n_{j}^{1+3α} log n_{j} discs of radius n_{j}^{−2}(log n_{j})^{3}. Namely, let F_{0} be any G-set. If F_{j} has been constructed it will be of the form

∪_{i=1}^{M}Sδ_{ℓ_{i}}

for a certain δ, where ℓ_{i} = {(x, m_{i}x + b_{i}) : 0 ≤ x ≤ 1} for suitable m_{i} and b_{i}, and every number in [0, 1] is within δ of one of the m_{i}. As in the proof of Lemma 1.3 we let A_{i}(x, y) = (x, m_{i}x + δy + b_{i}). We make n_{j+1} sufficiently large and define

F_{j+1} = ∪_{i=1}^{M}A_{i}(G_{n_{j+1}})

Clearly F_{j+1} ⊂ F_{j}, and it follows as in Lemma 1.3 that the resulting set is a G-set. The covering property is also essentially obvious from (∗) provided n_{j+1} is large enough, say log(n_{j+1}) >> M.

Let F = ∩_{j}F_{j}, and let E = {(x, y) ∈ F : x ∈ T′}. Then the covering property in the construction of F_{j} implies that dimE ≤ \frac{1}{2}(1 + 3α). On the other hand F is a G-set, and if ℓ is a line segment contained in F, then dim(ℓ ∩ E) =dimT′ ≥ α. This completes the construction.

We now discuss the bound dimE ≥ max(2α, \frac{1}{2} + α). The bound dimE ≥ 2α can be derived from Proposition 1.5 by an argument like the proof of Lemma 1.6; we will omit this. To prove the bound dimE ≥ \frac{1}{2} + α (which corresponds to the easy |I| ≲ (kn)^{\frac{3}{4}} + k + n under the above heuristic argument) fix a compact set E and for each e ∈ S^{1} a line ℓ_{e} which intersects E in dimension ≥ α. Let {D_{j}} = {D(x_{j}, r_{j})} be a covering. Fix β_{1} < β < α; we have to bound ∑_{j} r_{j}^{\frac{1}{2} +β_{1}} from below. As in the proof of Lemma 1.6 we let Σ_{k} = {j : 2^{−k} ≤ r_{j} ≤ 2^{−(k−1)}}, ν_{k} = |Σ_{k}| and E_{k} = E ∩ (∪{D_{j} : j ∈ Σ_{k}}). We start by choosing a number k and a subset Ω ⊂ S^{1} with measure ≳ \frac{1}{k^{2}} such that if e ∈ Ω then H_{β}(ℓ_{e} ∩ E_{k}) ≥ C^{−1}k^{−2}, using the pigeonhole principle as in the proof of Lemma 1.6. Let γ = \frac{2}{β}. Since H_{β}(I) ≤ |I|^{β} for any interval I, it follows that for a suitable numerical constant C, and for any e ∈ Ω there are \underline{two} intervals I_{e}^{±} on ℓ_{e} which are C^{−1}k^{−γ}- separated and such that H_{β}(E_{k} ∩ I_{e}^{±}) ≳ k^{−2}. Let {e_{i}}_{i=1}^{M} be a 2^{−k}-separated subset of Ω with M ≳ \frac{2^{k}}{k^{2}} (see (6)) and define

T = {(j_{+}, j_{−}, i) ∈ Σ_{k} × Σ_{k} × {1, …, M} : I_{e_{i}}^{+} ∩ E_{k} ∩ D_{j_{+}} ≠ ∅, I_{e_{i}}^{−} ∩ E_{k} ∩ D_{j_{−}} ≠ ∅} (9)

We will count T in two different ways.

First fix j_{+} and j_{−} and consider how many values of i there can be with (j_{+}, j_{−}, i) ∈ T . We will call such a value of i \underline{allowable}. If the distance between D_{j_{+}} and D_{j_{−}} is small compared with k^{−γ} then there is no allowable i, since the distance between I_{e_{i}}^{+} and I_{e_{i}}^{−} is always ≥ C^{−1}k^{−γ}. On the other hand if the distance between D_{j_{+}} and D_{j_{−}} is ≳ k^{−γ}, then because the {e_{i}} are 2^{−k}-separated, it follows that there are ≲ k^{γ} i’s such that ℓ_{e_{i}} intersects both D_{j_{+}} and D_{j_{−}}. Hence in either case there are ≲ k^{γ} allowable i’s. Summing over j_{+} and j_{−} we conclude that

|T | ≲ k^{γ}ν_{k}^{2}  (10)

On the other hand, for any fixed i, the lower bound H_{β}(E_{k} ∩ I_{e_{i}}^{+}) ≳ k^{−2} implies there are ≳ k^{−γ}2^{kβ} values of j_{+} such that I_{e_{i}}^{+} ∩ E_{k} ∩ D_{j_{+}} ≠ ∅ and similarly with + replaced by −. So |T | ≳ M(k^{−γ}2^{kβ})^{2}. Comparing this bound with (10) we conclude that

ν_{k} ≳ k^{− \frac{3}{2} γ}2^{kβ}\sqrt{M}
≳ k^{−(1+ \frac{3}{2} γ)}2^{( \frac{1}{2} +β)k}
≳ 2^{( \frac{1}{2} +β_{1})k}

and therefore ∑_{j∈Σ_{k}} r_{j}^{\frac{1}{2} +β_{1}} ≥ constant. □

2.The higher dimensional case

We will first make a few remarks about the corresponding problem over finite fields, which is the following:

Let 𝔽_{q} be the field with q elements and let V be an n-dimensional vector space over 𝔽_{q}. Let E be a subset of V which contains a line in every direction, i.e.

∀e ∈ V \{0}∃a ∈ V : a + te ∈ E ∀t ∈ 𝔽_{q}

Does it follow that |E| ≥ C_{n}^{−1}q^{n}?

Of course C_{n} should be independent of q. One could ask instead for a bound like ∀ϵ > 0∃C_{nϵ} : |E| ≥ C_{nϵ}^{−1}q^{n−ϵ} or could restrict to the case of prime fields 𝔽_{p} or fields with bounded degree over the prime field.

So far as I have been able to find out this question has not been considered, and the simple result below corresponds to what is known in the Euclidean case.

\underline{Proposition 2.1} In the above situation |E| ≥ C_{n}^{−1}q^{\frac{n+2}{2}}

We give the proof since it is based on the same idea as the ℝ^{n} proof but involves no technicalities.

First consider the case n = 2, which is analogous to Proposition 1.5. We will actually prove the following more general statement, which we need below: suppose (with dimV = 2) that E contains at least \frac{q}{2} points on a line in each of m different directions. Then

|E| ≳ mq  (11)

To prove (11), let {ℓ_{j}}_{j=1}^{m} be the lines. Any two distinct ℓ_{j}’s intersect in a point. Accordingly

\frac{1}{2}qm ≤ ∑_{j} |E ∩ ℓ_{j}|
≤ |E|^{\frac{1}{2}} (∑_{jk} |ℓ_{j} ∩ ℓ_{k}|)^{\frac{1}{2}}
= |E|^{\frac{1}{2}} (m(m − 1 + q))^{\frac{1}{2}}
≤ |E|^{\frac{1}{2}} (mq)^{\frac{1}{2}}

where we used that m ≤ q + 1. It follows that |E| ≳ mq. Taking m = q + 1 we obtain the two dimensional case of Proposition 2.1.

Now assume n ≥ 3. Then E contains \frac{q^{n}−1}{q−1} ≈ q^{n−1} lines \{ℓ_{j}\}. Fix a number μ and define a \underline{high multiplicity line} to be a line ℓ_{k} with the following property: for at least \frac{q}{2} of the q points x ∈ ℓ_{k}, the set {j : x ∈ ℓ_{j}} has cardinality at least μ + 1. Consider two cases: (i) no high multiplicity line exists (ii) a high multiplicity line exists.

In case (i) we define Ẽ = {x ∈ E : x belongs to ≤ μ ℓ_{j}’s}. Then Ẽ intersects each ℓ_{j} in at least \frac{q}{2} points, by definition of case (i). Each point of Ẽ belongs to at most μ ℓ_{j}’s so we may conclude that

|E| ≥ |Ẽ|
≥ μ^{−1} ∑_{j} |Ẽ ∩ ℓ_{j}|
≳ μ^{−1}q · q^{n−1}

In case (ii), let {Π_{i}} be an enumeration of the 2- planes containing ℓ_{k}. By definition of high multiplicity line there are at least \frac{μq}{2} lines ℓ_{j}, j ≠ k, which intersect ℓ_{k}. Each one of them is contained in a unique Π_{i}, and contains q − 1 points of Π_{i} which do not lie on ℓ_{k}. Let L_{i} be the set of lines ℓ_{j} which are contained in a given Π_{i}. Then by (11) we have |E ∩ Π_{i} ∩ (V \ℓ_{k})| ≳ q|L_{i}|. The sets Π_{i} ∩ (V \ℓ_{k}) are pairwise disjoint so we can sum over i to get |E| ≳ q ∑_{i} |L_{i}| ≥ \frac{q^{2}μ}{2}.

If we take μ to be roughly q^{\frac{n−2}{2}} we obtain |E| ≳ q^{\frac{n+2}{2}} in either case (i) or (ii), hence the result. □

\underline{Remark 2.1} General finite fields do not always resemble the Euclidean case in this sort of problem. For example, the Szemeredi-Trotter theorem is easily seen to be false (e.g.

[5] p. 75). A counterexample involving one line in each direction as in remark 1.5 may be obtained in the following way: let q = p^{2} with p prime, let α be a generator of 𝔽_{q} over 𝔽_{p} and in the two dimensional vector space V over 𝔽_{q}, let ℓ_{jk} be the line connecting (0, j) to (1, kα). Here j and k are in 𝔽_{p}. This is a set of p^{2} lines containing one line in each direction other than the vertical. For given t ∈ 𝔽_{q}, let S_{t} = {y ∈ 𝔽_{q} : (t, y) ∈ ∪_{jk}ℓ_{jk}}. If t is such that α\frac{t}{1−t} ∈ 𝔽_{p} then it is easily seen that S_{t} coincides with (1 − t)F_{p}, and if t = 1 then S_{t} = α𝔽_{p}. This gives p “bad” values of t such that S_{t} has cardinality p. Let E = ∪_{t}{(t, y) : y ∈ S_{t}}, where the union is taken over the bad values of t. Then {ℓ_{jk}} and E give a configuration of p^{2} lines and p^{2} points with p^{3} incidences, matching the trivial upper bound from (3).

In the ℝ^{n} context, arguments like the proof of Proposition 2.1 can still be used, except that one has to work with tubes instead of lines and measure instead of cardinality, and take into account such issues as that the size of the intersection of two tubes will depend on the angle of intersection via (4). This was perhaps first done by Cordoba (e.g. [18] - see the proof of Proposition 1.5 above). We will present here the “bush” argument from [7], p. 153-4 which shows the following:

\underline{Proposition 2.2} ∥fδ^{∗}∥_{n+1,∞} ≤ C_{n}δ^{− \frac{n−1}{n+1}} ∥f∥_{\frac{n+1}{2} ,1}

\underline{Proof} Using (6), we see that what must be shown is the following: if \{T δ_{e_{j}}\}_{j=1}^{M} are

tubes with δ-separated directions, E is a set and |E ∩ T_{e_{j}}| ≥ λ|T δ_{e_{j}}|, then

|E| ≳ δ^{\frac{n−1}{2}} λ^{\frac{n+1}{2}} \sqrt{M}  (12)

To this end we fix a number μ (“multiplicity”) and consider the following two possibilities

(i) (low multiplicity) No point of E belongs to more than μ tubes T δ_{e_{j}}.

(ii) (high multiplicity) Some point a ∈ E belongs to more than μ tubes T δ_{e_{j}}.

In case (i) it is clear that |E| ≳ μ^{−1} ∑_{j} |E ∩ T δ_{e_{j}}|, hence

|E| ≳ μ^{−1}Mλδ^{n−1}  (13)

In case (ii) we fix a point a as indicated and may assume that a belongs to T δ_{e_{j}} when

j ≤ μ + 1. If C_{0} is a suitably large fixed constant, then |T δ_{e_{j}} ∩ D(a, C_{0}^{−1}λ)| ≤ \frac{λ}{2}|T δ_{e_{j}}|. Accordingly, for j ≤ μ + 1, we have

|E ∩ T δ_{e_{j}} ∩ D(a, C_{0}^{−1}λ)^{c}| ≥ \frac{λ}{2}|T δ_{e_{j}}| ≳ λδ^{n−1}

If j, k ≤ μ then T δ_{e_{j}} ∩ T δ_{e_{k}} contains a and has diameter ≲ \frac{δ}{θ(e_{j},e_{k})} by (4). It follows

that if θ(e_{j}, e_{k}) ≥ C_{1} \frac{δ}{λ} for a suitably large C_{1}, then the sets E ∩ T δ_{e_{j}} ∩ D(a, C_{0}^{−1}λ)^{c} and E ∩ T δ_{e_{k}} ∩ D(a, C_{0}^{−1}λ)^{c} are disjoint. We conclude that

|E| ≳ N · λδ^{n−1}

where N is the maximum possible cardinality for a C_{1} \frac{δ}{λ}-separated subset of \{e_{j}\}_{j=1}^{μ+1}. Since the {e_{j}} are δ- separated, we have N ≳ λ^{n−1}μ and therefore

|E| ≳ λ^{n}δ^{n−1}μ  (14)

We conclude that for any given μ either (13) or (14) must hold. Taking μ ≈ λ^{−( \frac{n−1}{2} )}\sqrt{M} we get (12). □

\underline{Further remarks}: 2.2. Bourgain [7] also gave an additional argument leading to an improved result which implies dim(Kakeya)≥ \frac{n+1}{2} + ϵ_{n}, where ϵ_{n} is given by a certain inductive formula (in particular ϵ_{3} = \frac{1}{3}). A more efficient argument was then given by the author [60], based on considering families of tubes which intersect a line instead of a point as in the bush argument; this is the continuum analogue of the proof of Proposition 2.1. It gives the following bound:

∀ϵ∃Cϵ : ∥fδ^{∗}∥_{q} ≤ Cϵδ^{−( \frac{n}{p} −1)−ϵ}∥f∥_{p}  (15)

where p = \frac{n+2}{2} and q = (n − 1)p′. This is the estimate on L^{p} which would follow by interpolation with the trivial ∥fδ^{∗}∥_{∞} ≲ δ^{−(n−1)}∥f∥_{1} if the bound (2) could be proved. In particular, it implies the dimension of Kakeya sets is ≥ \frac{n+2}{2}. Other proofs of estimates like (15) have also recently been given by Katz [28] and Schlag [45]. However in every dimension n ≥ 3 it is unknown whether (15) holds for any p > \frac{n+2}{2} and whether dim(Kakeya)> \frac{n+2}{2}.

2.3. Proposition 2.2 is also a corollary of the L^{\frac{n+1}{2}} → L^{n+1} estimate for the x-ray transform due to Drury and Christ [20],[18] (see also [39], [16] for related results). Conversely, a refinement of the argument which proves (15) can be used to prove the estimate on L^{\frac{n+2}{2}} which would follow from (2) and the result of [20] by interpolation, at least in the three dimensional case. See [62].

2.4. We briefly discuss some other related problems. The classical problem of Nikodym sets has been shown to be formally equivalent to the Kakeya problem by Tao [58]; we refer to his paper for further discussion. Another classical problem is the problem of (n, 2) sets: suppose that E is a set in ℝ^{n} which contains a translate of every 2-plane. Does it follow that E has positive measure? At present this is known only when n = 3 [33] or n = 4 [7]. The argument in [7], section 4 shows the following: suppose that (2) can be proved in dimension n − 1, or more precisely that a slightly weaker result can be proved, namely that for some p and q there is an estimate

∥fδ^{∗}∥_{L^{q}(S^{n−2})} ≲ δ^{−α}∥f∥_{L^{p}(ℝ^{n−1})} with α < \frac{1}{p}  (16)

Then (n, 2)-sets have positive measure.

However, note that (16) would imply by Lemma 1.6 that Kakeya sets in ℝ^{n−1} have dimension ≥ n − 2. In fact if an estimate (16) is true for every n then one could answer question 1 affirmatively by an argument based on the fact that the direct product of Kakeya sets is Kakeya. It may therefore be unlikely that the (n, 2)-sets problem can be solved without a full understanding of the Kakeya problem. However, the most recent results on it are those of [1].

2.5. If one considers curves instead of lines, then it is known that much less can be expected to be true. This first results in this direction are in [8]; see also [10], [35] and [49].

\underline{Added in proof} Bourgain recently improved on the results discussed here in sufficiently high dimensions, by showing that the dimension of a Kakeya set in ℝ^{n} is greater than αn for suitable explicit α > \frac{1}{2}. We refer to his forthcoming paper for the details.

\underline{3. Circles}

In this section we will discuss some analogous problems about circles in the plane, or (essentially equivalent) fine estimates for the wave equation in 2 + 1 dimensions. These problems are much better understood than the Kakeya problem and yet they present some of the same difficulties.

A prototype result due to Bourgain [6] and Marstrand [34] independently is that

(∗): A set in ℝ^{2} which contains circles with arbitrary centers must have positive measure.

Bourgain proved a stronger result which has the same relation to (∗) as question 2 does to question 1. Namely, define a maximal function

Mf(x) = sup_{r} ∫ |f(x + re^{iθ})|\frac{dθ}{2π}

Then ∥Mf∥_{L^{p}(ℝ^{2})} ≲ ∥f∥_{L^{p}(ℝ^{2})}, p > 2. As is well-known, this maximal function was introduced by Stein [51] and he proved the analogous inequality in dimensions n ≥ 3; the range of p is then p > \frac{n}{n−1}. Stein’s proof was based partly on the Plancherel theorem and Bourgain’s argument in the two dimensional case also used the Plancherel theorem, whereas Marstrand’s argument was purely geometric. We will discuss some further developments of the latter approach.

A variant on the Kakeya construction due to Besicovitch-Rado [4] and Kinney [30] shows the following:

(∗∗) There are compact sets in the plane with measure zero containing circles of every radius between 1 and 2.

We will call such sets BRK sets. The distinction between (∗) and (∗∗) can be understood in terms of parameter counting: a set as in (∗∗) is a subset of a 2-dimensional space containing a 1-parameter family of 1-dimensional objects, so whether it has positive measure or not can be expected to be a borderline question. This is analogous to the question of Kakeya sets which also contain n − 1-parameter families of 1-dimensional objects. On the other hand a set as in (∗) contains a 2- parameter family of 1-dimensional objects in a 2-dimensional space.

A further related remark is that analogous constructions with other 1-parameter families of circles have been done by Talagrand [57]. For example, he shows that for any smooth curve γ there are sets of measure zero containing circles centered at all points of γ.

It is natural to ask whether the dimension of a BRK set must be 2 or not. This question also has a maximal function version; the relevant maximal function is the following Mδ: if f : ℝ^{2} → ℝ then Mδf : [\frac{1}{2}, 2] → ℝ,

Mδf(r) = sup_{x} \frac{1}{|Cδ(x, r)|} ∫_{Cδ(x,r)} |f|  (17)

One shows analogously to Lemma 1.6 that a bound (for some p < ∞)

∀ϵ∃Cϵ : ∥Mδf∥_{L^{p}([ \frac{1}{2} ,2])} ≤ Cϵδ^{−ϵ}∥f∥_{p}  (18)

will imply that BRK sets have dimension 2. Note that existence of measure zero BRK sets implies the δ^{−ϵ} factor is needed. This is similar to the situation with the two dimensional Kakeya problem. However in contrast to the latter problem it is not possible to take p = 2 in (18). In fact p must be at least 3; this is seen by considering the standard example f = indicator function of a rectangle with dimensions δ × \sqrt{δ}.

\underline{Remark 3.1} Sets in ℝ^{n} with measure zero containing spheres of all radii may be shown to exist for n ≥ 3 also, and the maximal function (17) may be defined in ℝ^{n}. However, in that case the questions mentioned above are essentially trivial, since the correct estimate for the maximal function is an L^{2} → L^{2} estimate, is easy and implies that sets containing spheres with all radii have dimension n. Namely, the estimate

∥Mδf∥_{2} ≲ (log\frac{1}{δ})^{\frac{1}{2}} ∥f∥_{2}  (19)

can be proved analogously to Proposition 1.5 and is also closely related to some of the Strichartz inequalities for the wave equation (cf. [41]), due to the fact that spherical means correspond roughly to solutions of the initial value problem □u = 0, u(·, 0) = f, \frac{∂u}{∂t}(·, 0) = 0 after taking \frac{n−1}{2} derivatives. These remarks are from [31]. From a certain point of view, the “reason” why the higher dimensional case is easier is the following: if |r − s| ≈ 1 then

|Cδ(x, r) ∩ Cδ(y, s)| ≈ \{ \begin{matrix}δ^{\frac{n+1}{2}} & if C(x, r) and C(y, s) are tangent \\ δ^{2} & if C(x, r) and C(y, s) are sufficiently transverse \end{matrix} (20)

making the first possibility “worse” than the second in ℝ^{2} but not in higher dimensions.

We now consider only the two dimensional case and will formulate a discrete analogy like the analogy between the Szemeredi-Trotter theorem and the question mentioned in Remark 1.5. The relevant problem in discrete geometry is

Given N circles {C_{i}} in the plane, no three tangent at a point, how many pairs (i, j) can there be such that C_{i} is tangent to C_{j}?

For technical reasons we always interpret “tangent” as meaning “internally tangent”, i.e. a circle C(x, r) is “tangent” to C(y, s), written C(x, r)||C(y, s), iff |x − y| = |r − s|.

We will call this the tangency counting problem. We’re not aware of any literature specifically about this problem, but known techniques in incidence geometry (related to the Szemeredi-Trotter theorem) can be adapted to it without difficulty. One obtains the following bounds for I =^{def} {(i, j) : C_{i}||C_{j}}.

(i) (easy) |I| ≲ N^{\frac{5}{3}} . This follows from the fact that the incidence matrix

a_{ij} = \{ \begin{matrix}1 & if C_{i}||C_{j} \\ 0 & otherwise \end{matrix}

contains no 3 × 3 submatrix of 1’s (essentially a theorem of Appolonius: there are at most two circles which are internally tangent to three given circles at distinct points) and therefore contains at most O(N^{\frac{5}{3}} ) 1’s by (3).

(ii) (more sophisticated) ∀ϵ > 0 ∃Cϵ < ∞ : |I| ≲ N^{\frac{3}{2} +ϵ}. This follows readily from the techniques of Clarkson, Edelsbrunner, Guibas, Sharir and Welzl [17]. We will not discuss their work here; we just note that they prove the analogous N^{\frac{3}{2} +ϵ} bound in the three dimensional unit distance problem: in our notation, given {(x_{i}, r_{i})}_{i=1}^{N} ⊂ ℝ^{2} × ℝ, there are ≲ N^{\frac{3}{2} +ϵ} pairs (i, j) with |x_{i} − x_{j}|^{2} + (r_{i} − r_{j})^{2} = 1.

There is no reason to think that the bound (ii) should be sharp.^{3} However, (ii) leads to a sharp result on the BRK sets problem and a proof of the maximal inequality (18) with p = 3. The heuristic argument is the following: assume we know a bound ≲ N^{α} in the tangency counting problem, where α ≥ \frac{3}{2}. Let E be a BRK set and consider its δ-neighborhood Eδ. Let \{r_{j}\}_{j=1}^{M} be a maximal δ-separated subset of [\frac{1}{2}, 2]; then M ≈ \frac{1}{δ}

3It may be more natural to consider a slightly different formulation of the problem: drop the assumption that no three circles are tangent at a point, and consider the number of points where two are tangent instead of the number of tangencies. With this reformulation, a standard example involving circles with integer center and radius shows that the exponent \frac{4}{3} would be best possible as in the unit distance problem.

and Eδ contains an annulus Cδ(x_{j}, r_{j}) for each j. By (20), we should have to a first approximation |Cδ(x_{j}, r_{j})∩Cδ(x_{k}, r_{k})| ≈ δ^{\frac{3}{2}} if C(x_{j}, r_{j}) and C(x_{i}, r_{i}) intersect tangentially and |Cδ(x_{j}, r_{j})∩Cδ(x_{k}, r_{k})| ≈ δ^{2} if they intersect transversally. Accordingly we would get ∑_{jk} |Cδ(x_{j}, r_{j}) ∩ Cδ(x_{k}, r_{k})| ≲ δ^{−α} · δ^{\frac{3}{2}} + δ^{−2} · δ^{2} ≲ δ^{\frac{3}{2} −α}, and then the argument in the proof of Proposition 1.5 shows that |Eδ| ≳ δ^{\frac{1}{2} (α− \frac{3}{2} )}, so one expects dimE ≥ 2 − \frac{1}{2}(α − \frac{3}{2}).

It turns out that it is possible to make this argument rigorous and to obtain a corresponding result ((18) with p = 3) for the maximal operator. The first lemma below keeps track of the intersection of two annuli in terms of their degree of tangency; it is of course quite standard and is used in one form or another in most papers in the area, e.g. [6] and [34]. The second lemma is due to Marstrand ([34], Lemma 5.2), although he formulated it slightly differently. It gives a quantitative meaning to the theorem of Appolonius used in the proof of the N^{\frac{5}{3}} tangency bound.

We introduce the following notation: if C(x, r) and C(y, s) are circles then

d((x, r), (y, s)) = |x − y| + |r − s|
Δ((x, r), (y, s)) = ||x − y| − |r − s||

Note that Δ vanishes precisely when the circles are “tangent.” In Lemmas 3.1 and 3.2 below, we assume that all circles C(x, r) etc. have centers in D(0, \frac{1}{4}) and radii between \frac{1}{2} and 2.

\underline{Lemma 3.1} Assume that x ≠ y. Let d = d((x, r), (y, s)), Δ = Δ((x, r), (y, s)), and e = sgn(r − s)\frac{y−x}{|y−x|}, ζ = y + re. Then

(a)Cδ(x, r) ∩ Cδ(y, s) is of measure ≲ δ · \frac{δ}{\sqrt{(δ+Δ)(δ+d)}}.

(b) Cδ(x, r) ∩ Cδ(y, s) is contained in a disc centered at ζ with radius ≲ \sqrt{\frac{Δ+δ}{d+δ}}.

\underline{Proof} We use the following fact: if μ > 0, ϵ > 0 then the set \{x ∈ [−π, π] : | cos x−μ| ≤ ϵ\} is (i) contained in the union of two intervals of length ≲ \frac{ϵ}{\sqrt{|1−μ|}} and (ii) contained in

an interval of length ≲ \sqrt{|1 − μ| + ϵ} centered at 0.

To prove the lemma, we use complex notation and may assume that x = 0, r = 1, y is on the positive real axis and s < 1. Note that then e = 1. If d ≤ 4δ then the lemma is trivial, and if y < \frac{d}{2} − δ then y + s < 1 − 2δ so that Cδ(0, 1) ∩ Cδ(y, s) = ∅. So we can assume that d ≥ 4δ and y ≥ \frac{d}{2} − δ ≥ \frac{d}{4}.

If z ∈ Cδ(0, 1) ∩ Cδ(y, s) then clearly |z − e^{iθ}| ≤ δ for some θ ∈ [−π, π]. It suffices to show that the set of θ which can occur here is contained in two intervals of length ≲ \frac{δ}{\sqrt{(δ+Δ)(δ+d)}} and in an interval of length ≲ \sqrt{\frac{Δ+δ}{d+δ}} centered at 0.

The point e^{iθ} must belong to C_{2δ}(y, s), i.e. ||e^{iθ} − y| − s| < 2δ and therefore, since ||e^{iθ} − y| + s| ≈ 1,

||e^{iθ} − y|^{2} − s^{2}| ≲ δ

We can express this as

| cos θ − \frac{1 + y^{2} − s^{2}}{2y} | ≲ \frac{δ}{y} ≲ \frac{δ}{d}

Let μ = \frac{1+y^{2}−s^{2}}{2y}, ϵ = C \frac{δ}{d}. Then μ is positive, and |1 − μ| = \frac{|s^{2}−(1−y)^{2}|}{2y} ≈ \frac{|1−s−y|}{2y} ≈ \frac{Δ}{d}.

Apply fact (ii) in the first paragraph. The set of possible θ is therefore contained in an

interval of length ≲ \sqrt{\frac{Δ+δ}{d}} centered at 0. This proves (b), since we are assuming d ≥ δ. Estimate (a) follows from (b) if Δ ≤ δ. If Δ ≥ δ, then fact (i) in the first paragraph gives the additional property that θ must be contained in the union of two intervals of length

≲ \frac{δ/d}{\sqrt{Δ/d}} ≈ \frac{δ}{\sqrt{(δ+Δ)(δ+d)}}. □

\underline{Lemma 3.2} (Marstrand’s 3-circle lemma) For a suitable numerical constant C_{0}, assume that ϵ, t, λ ∈ (0, 1) satisfy C_{0} \frac{ϵ}{t} ≤ λ^{2}. Fix three circles C(x_{i}, r_{i}), 1 ≤ i ≤ 3. Then for δ ≤ ϵ the set

\overline{Ω}_{ϵtλ} =^{def} \{(x, r) ∈ ℝ^{2} × ℝ : Δ((x, r), (x_{i}, r_{i})) < ϵ ∀i,
d((x, r), (x_{i}, r_{i})) > t ∀i, Cδ(x, r) ∩ Cδ(x_{i}, r_{i}) ≠ ∅ ∀i,
dist(Cδ(x, r) ∩ Cδ(x_{i}, r_{i}), Cδ(x, r) ∩ Cδ(x_{j}, r_{j})) ≥ λ ∀i, j : i ≠ j}

is contained in the union of two ellipsoids in ℝ^{3} each of diameter ≲ \frac{ϵ}{λ^{2}} and volume ≲ \begin{matrix}ϵ & ^{3} \\ λ & ^{3} \end{matrix} .

\underline{Proof} This will be based on the inverse function theorem. We remark that the sketch of proof given in [61] is inaccurate.

We will actually work with a slightly different set, namely, with

Ω_{ϵtλ} = {(x, r) ∈ ℝ^{2} × ℝ : Δ((x, r), (x_{i}, r_{i})) < ϵ ∀i, d((x, r), (x_{i}, r_{i})) > t ∀i,
|e_{i}(x, r) − e_{j}(x, r)| ≥ λ ∀i, j : i ≠ j}

where e_{i}(x, r) = sgn(r − r_{i})\frac{x_{i}−x}{|x_{i}−x|}. This is sufficient since by Lemma 3.1 (b), Ω_{ϵt \frac{λ}{2}} will

contain \overline{Ω}_{ϵtλ} provided C_{0} is sufficiently large.

If e_{1}, …, e_{4} are unit vectors in ℝ^{2} which are contained in an arc of length μ, then the reader will convince herself or himself that

|(e_{1} − e_{2}) ∧ (e_{3} − e_{4})| ≲ μ|e_{1} − e_{2}| |e_{3} − e_{4}|  (21)

and furthermore if e_{1}, e_{2}, e_{3} are unit vectors in ℝ^{2} then

|(e_{1} − e_{2}) ∧ (e_{1} − e_{3})| ≈ |e_{1} − e_{2}| |e_{2} − e_{3}| |e_{3} − e_{1}|  (22)

Here ∧ is wedge product, (a, b) ∧ (c, d) = ad − bc.

Consider the map G : ℝ^{2} × ℝ → ℝ^{3} defined by

G(x, ρ) = ( \begin{matrix}|x − x_{1}| − |r − r_{1}| \\ |x − x_{2}| − |r − r_{2}| \\ |x − x_{3}| − |r − r_{3}| \end{matrix} )

Fix (ξ, ρ) ∈ Ω_{ϵtλ}. Observe that

DG(ξ, ρ) ≃ ( \begin{matrix}e_{1}(ξ, ρ) & −1 \\ e_{2}(ξ, ρ) & −1 \\ e_{3}(ξ, ρ) & −1 \end{matrix} )  (23)

where “≃” means that the two matrices are equal after each row of the matrix on the right hand side is multiplied by an appropriate choice of ±1.

We can assume that |e_{1}(ξ, ρ) − e_{3}(ξ, ρ)| ≥ |e_{1}(ξ, ρ) − e_{2}(ξ, ρ)| ≥ |e_{2}(ξ, ρ) − e_{3}(ξ, ρ)|. Let μ = |e_{1}(ξ, ρ) − e_{3}(ξ, ρ)|, ν = |e_{2}(ξ, ρ) − e_{3}(ξ, ρ)|; then we have μ ≥ ν ≳ λ and also |e_{1}(ξ, ρ) − e_{2}(ξ, ρ)| ≈ μ. It follows by (22) that | det DG(ξ, ρ)| ≈ μ^{2}ν. Furthermore, all entries in the cofactor matrix of DG(ξ, ρ) are easily seen to be ≲ μ. Let E(ξ, ρ) = {(x, r) ∈ ℝ^{2} × ℝ : |DG(ξ, ρ)(x − ξ, r − ρ)| < Aϵ} for an appropriate large constant A which should be chosen before C_{0}. Then the preceding considerations imply E(ξ, ρ) is an ellipsoid with

diam(E(ξ, ρ)) ≲ \frac{ϵ}{μν}  (24)
|E(ξ, ρ)| ≲ \frac{ϵ^{3}}{μ^{2}ν}  (25)

We claim that if (x, r) ∈ E then DG(x, r)DG(ξ, ρ)^{−1} = I +E, where I is the 3×3 identity matrix and E is a matrix with norm ≤ \frac{1}{100}, say.

A matrix calculation shows that each entry of (DG(x, r) − DG(ξ, ρ))DG(ξ, ρ)^{−1} has the form (detDG(ξ, ρ))^{−1}(e_{i}(x, r) − e_{i}(ξ, ρ)) ∧ (e_{j}(ξ, ρ) − e_{k}(ξ, ρ)) for appropriate i, j, k. We will show below that

|e_{i}(x, r) − e_{i}(ξ, ρ)| ≲ \frac{ϵ}{tν}  (26)

If we assume this then the claim may be proved as follows. (26) implies in particular that all the vectors e_{i}(x, r) and e_{j}(ξ, ρ) belong to an arc of length ≲ μ. Accordingly, using (21),

| det DG(ξ, ρ)^{−1}(e_{i}(x, r) − e_{i}(ξ, ρ)) ∧ (e_{j}(ξ, ρ) − e_{k}(ξ, ρ))|
≲ μ| det DG(ξ, ρ)^{−1}| |e_{i}(x, r) − e_{i}(ξ, ρ)| |e_{j}(ξ, ρ) − e_{k}(ξ, ρ)|
≲ μ · (μ^{2}ν)^{−1} · \frac{ϵ}{tν} · μ
≤ \frac{ϵ}{tν^{2}}

which is small.

To prove (26) we abbreviate e_{i} = e_{i}(ξ, ρ). Fix i and let e_{i}^{∗} ∈ ℝ^{2} be a unit vector perpendicular to e_{i}. If we define j and k via {i, j, k} = {1, 2, 3}, then a little linear algebra shows that e_{i}^{∗} = α(e_{i} −e_{j})+β(e_{i} −e_{k}) with |α|+|β| ≲ ν^{−1}. Furthermore, if we let (v_{1}, v_{2}, v_{3}) = DG(ξ, ρ)(x−ξ, r −ρ), then by (23) we have |(e_{i} −e_{j})·(x−ξ)| = |v_{i} ±v_{j}| ≤ 2ϵ and similarly |(e_{i} − e_{k}) · (x − ξ)| ≤ 2ϵ. We conclude that |e_{i}^{∗} · (x − ξ)| ≲ \frac{ϵ}{ν}, hence |e_{i}^{∗} · (x − x_{i})| ≲ \frac{ϵ}{ν} since x_{i} − ξ is parallel to e_{i}. Also |x − x_{i}| ≥ \frac{t}{2} by (24), so

|e_{i}^{∗} · \frac{x − x_{i}}{|x − x_{i}|}| ≲ \frac{ϵ}{tν}

This implies that for an appropriate choice of ±

|e_{i}(x, r) ± e_{i}| ≲ \frac{ϵ}{tν}  (27)

Note though that r − r_{i} and |x − x_{i}| are nonzero on E(ξ, ρ): this follows from (24), since ϵ is small compared with t so that |ξ −x_{i}| ≈ t ≈ |ρ−r_{i}|. So (x, r) → e_{i}(x, r) is a continuous function on E(ξ, ρ) and therefore the sign in (27) is independent of (x, r). So (26) holds and the claim is proved.

If A is large enough then the claim implies via the usual proof of the inverse function theorem that G is a diffeomorphism from a subset of E(ξ, ρ) onto a disc of radius 2ϵ, say. In particular, E(ξ, ρ) must contain a point (x, r) with G(x, r) = 0. Then C(x, r) is internally tangent to each C(x_{i}, r_{i}); note that by (26) and the bound on the diameter of E, we have (x, r) ∈ Ω_{ϵ_{\frac{t}{2}} \frac{λ}{2}} and furthermore, by the claim E(x, r) and E(ξ, ρ) are comparable

ellipsoids (each is contained in a fixed dilate of the other). Appolonius’ theorem implies there are only two possibilities for the circle C(x, r), and we have just seen that (ξ, ρ) must be contained in one of the two E(x, r)’s and that they have the proper dimensions. □

\underline{Proposition 3.3} For any p < \frac{8}{3} there is an estimate

∥Mδf∥_{q} ≤ Cδ^{− \frac{1}{2} ( \frac{3}{p} −1)}∥f∥_{p}, q = 2p′

This implies by the proof of Lemma 1.6 that BRK sets have dimension ≥ 2 − \frac{1}{2}(\frac{3}{p} − 1) for any p < \frac{8}{3}, i.e. dimension ≥ \frac{11}{6}. Proposition 3.3 was proved (in generalized form) in [31]; it is the partial result which corresponds to the bound (i) in the tangency counting problem. The sharp result ((18) with p = 3) incorporating the technique from [17] is proved in [61].

\underline{Proof} This will be similar to the proof of the \frac{1}{2} +α bound in remark 1.5. The p = 1 case is trivial^{4} so it suffices to prove the following restricted weak type bound at the endpoint:

|\{r ∈ [\frac{1}{2}, 2] : Mδχ_{E}(r) > λ\}| ≤ C(\frac{|E|}{δ^{\frac{1}{6}} λ^{\frac{8}{3}}} )^{\frac{6}{5}}  (28)

We may assume in proving (28) that the diameter of the set E is less than one. Consequently in defining Mδf we may restrict the point x to the disc D(0, \frac{1}{4}). Thus it suffices to prove the following.

Assume that λ ∈ (0, 1] and there are M 3δ-separated values r_{j} ∈ [\frac{1}{2}, 2] and points x_{j} ∈ D(0, \frac{1}{4}) such that |E ∩ Cδ(x_{j}, r_{j})| ≥ λ|Cδ(x_{j}, r_{j})|. Then

Mδ ≤ C(\frac{|E|}{δ^{\frac{1}{6}} λ^{\frac{8}{3}}} )^{\frac{6}{5}}  (29)

We can assume that M is large; for M smaller than any fixed constant (29) holds because M ≠ 0 implies |E| ≳ λδ.

To prove (29) we let μ (“multiplicity”) be the smallest number with the following property: there are at least \frac{M}{2} values of j such that

|E ∩ Cδ(x_{j}, r_{j}) ∩ \{x : |\{i : x ∈ Cδ(x_{i}, r_{i})\}| ≤ μ\}| ≥ \frac{λ}{2}|Cδ(x_{j}, r_{j})|  (30)

The main estimate is

μ ≲ M^{\frac{1}{6}} λ^{− \frac{5}{3}}  (31)

Before proving (31) we introduce some more notation, as follows. For any t ∈ [δ, 1] and ϵ ∈ [δ, 1], let

a(t, ϵ) = C_{1}^{−1}(\frac{δ}{ϵ})^{α}(\frac{Mδ}{t} + \frac{t}{Mδ})^{−α}

Here α is a sufficiently small positive constant, and C_{1} is a positive constant (easily shown to exist) which is large enough that

∑_{l≥0^{k≥0}} a(2^{k}δ, 2^{l}δ) < 1  (32)

4The p = 2 case was also known prior to [31]; it follows from results of Pecher [41].

for all M and δ. Let \overline{λ}(t, ϵ) = a(t, ϵ)\frac{λ}{2}, \overline{μ}(t, ϵ) = a(t, ϵ)μ, \overline{M}(t, ϵ) = a(t, ϵ)\frac{M}{2} . Also, for each i, j ∈ {1, …, M} let

Δ_{ij} = max(δ, | |x_{i} − x_{j}| − |r_{i} − r_{j}| |)  (33)

and for each j ∈ {1, …, M}, t ∈ [δ, 1], ϵ ∈ [δ, 1], let

S_{t,ϵ}(x_{j}, r_{j}) =^{def} {i : Cδ(x_{j}, r_{j}) ∩ Cδ(x_{i}, r_{i}) ≠ ∅, t ≤ |r_{i} − r_{j}| ≤ 2t
and ϵ ≤ Δ_{ij} ≤ 2ϵ}

A_{t,ϵ}(x_{j}, r_{j}) =^{def} \{x ∈ Cδ(x_{j}, r_{j}) : |\{i ∈ S_{t,ϵ}(x_{j}, r_{j}) : x ∈ Cδ(x_{i}, r_{i})\}| ≥ \overline{μ}(t, ϵ)\}

\underline{Lemma 3.4} There are numbers t ∈ [δ, 1] and ϵ ∈ [δ, 1] with the following property

There are ≥ \overline{M}(t, ϵ) values of j such that |A_{tϵ}(x_{j}, r_{j})| ≥ \overline{λ}(t, ϵ)|Cδ(x_{j}, r_{j})|

\underline{Proof} This is a routine pigeonhole argument. By the minimality of μ there are at least \frac{M}{2} values of j such that |Ẽ_{j}| ≥ \frac{λ}{2}|Cδ(x_{j}, r_{j})| where

Ẽ_{j} = E ∩ Cδ(x_{j}, r_{j}) ∩ {x : |{i : x ∈ Cδ(x_{i}, r_{i})}| ≥ μ}

For any such j and any x ∈ Ẽ_{j}, (32) implies there are t = 2^{k}δ and ϵ = 2^{l}δ such that x ∈ A_{tϵ}(x_{j}, r_{j}). Consequently, using (32) again, for any such j there are t = 2^{k}δ and ϵ = 2^{l}δ such that

|A_{tϵ}(x_{j}, r_{j})| ≥ \overline{λ}(t, ϵ)|Cδ(x_{j}, r_{j})|  (34)

By (32) once more, there must be a choice of t and ϵ such that (34) holds for at least \overline{M}(t, ϵ) values of j. This finishes the proof.

We fix once and for all a pair (t, ϵ) for which the conclusion of Lemma 3.4 is valid, and will drop the t, ϵ subscripts when convenient, i.e. will denote \overline{λ}(t, ϵ) by \overline{λ}, etc. We split the proof of (31) into two cases:

(i) \overline{λ} ≥ C_{2}\sqrt{\frac{ϵ}{t}}

(ii) \overline{λ} ≤ C_{2}\sqrt{\frac{ϵ}{t}}

where C_{2} is a sufficiently large constant.

In case (i), which is the main case, we let S be the set of M circles in (29), and let \overline{S} be the set of at least \overline{M} circles in Lemma 3.4. Let Q be the set of all quadruples (j, j_{1}, j_{2}, j_{3}) with C(x_{j}, r_{j}) ∈ \overline{S}, C(x_{j_{i}}, r_{j_{i}}) ∈ S for i = 1, 2, 3 and such that j_{i} ∈ S_{t,ϵ}(x_{j}, r_{j}) for each i ∈ \{1, 2, 3\} and furthermore dist(Cδ(x_{j}, r_{j})∩Cδ(x_{j_{i}}, r_{j_{i}}), Cδ(x_{j}, r_{j})∩Cδ(x_{j_{k}}, r_{j_{k}})) ≥ C_{3}^{−1}\overline{λ} for all i, k ∈ {1, 2, 3} with i ≠ k. Here C_{3} is a suitable constant which should be chosen before C_{2}.

We will make two different estimates on the cardinality of Q. On the one hand, the diameter bound in Lemma 3.2 implies that for fixed j_{1}, j_{2}, j_{3} there are ≲ \frac{ϵ}{δ} \overline{λ}^{−2} values of j such that (j, j_{1}, j_{2}, j_{3}) ∈ Q. Also it follows from the definition of Q that there are ≲ Mmin(M, \frac{t}{δ})^{2} possible choices for (j_{1}, j_{2}, j_{3}) : there are at most M choices for j_{1}, and once j_{1} is fixed there are ≲ min(M, \frac{t}{δ}) possibilities for each of j_{2} and j_{3}, since |r_{j_{1}} − r_{j_{i}}| ≤ |r_{j_{1}} − r_{j}| + |r_{j} − r_{j_{i}}| ≤ 4t for i = 2 or 3. We conclude that

|Q| ≲ \frac{ϵ}{δ} \overline{λ}^{−2}Mmin(M, \frac{t}{δ})^{2}  (35)

On the other hand, if we fix j with C(x_{j}, r_{j}) ∈ \overline{S} then (provided C_{3} has been chosen large enough) we can find three subsets F_{1}, F_{2}, F_{3} of A_{t,ϵ}(x_{j}, r_{j}) such that dist(F_{l}, F_{m}) ≥ 2C_{3}^{−1}\overline{λ}, l ≠ m, and |F_{l}| ≳ δ\overline{λ} for each l. For fixed l, we let S_{l} be those indices i ∈ S_{t,ϵ}(x_{j}, r_{j}) such that F_{l} ∩ Cδ(x_{i}, r_{i}) ≠ ∅. The sets Cδ(x_{i}, r_{i}), i ∈ S_{l} must cover F_{l} at least \overline{μ} times. So

∑_{i∈S_{l}} |F_{l} ∩ Cδ(x_{i}, r_{i})| ≳ \overline{μ}\overline{λ}δ

For each fixed i we have |F_{l} ∩ Cδ(x_{i}, r_{i})| ≲ δ^{2}_{\sqrt{tϵ}} by Lemma 3.1(a). Consequently

|S_{l}| ≳ δ^{−1}\overline{μ}\overline{λ}\sqrt{tϵ}  (36)

It is easy to see using Lemma 3.1(b) that if i_{l} ∈ S_{l} for l = 1, 2, 3 then (j, i_{1}, i_{2}, i_{3}) ∈ Q. So

|Q| ≳ \overline{M}(δ^{−1}\overline{μ}\overline{λ}\sqrt{tϵ})^{3}

If we compare this with (35) we obtain

\overline{μ}^{3} ≲ \frac{δ^{2}}{t^{\frac{3}{2}} ϵ^{\frac{1}{2}}} \overline{λ}^{−5}min(M, \frac{t}{δ})^{2} \frac{M}{\overline{M}}

or equivalently

μ^{3} ≲ M^{\frac{1}{2}} λ^{−5} · \{ \begin{matrix}a(t, ϵ)^{−9}(\frac{δ}{ϵ})^{\frac{1}{2}} (\frac{t}{δM})^{\frac{1}{2}} & if M ≥ \frac{t}{δ} \\ a(t, ϵ)^{−9}(\frac{δ}{ϵ})^{\frac{1}{2}} (\frac{Mδ}{t})^{\frac{3}{2}} & if M ≤ \frac{t}{δ} \end{matrix}

The expression in the brace is bounded by a constant by the definition of a(t, ϵ), provided α < \frac{1}{18}. So we have proved (31) in case (i).

In case (ii), we fix j with C(x_{j}, r_{j}) ∈ \overline{S} and make the trivial estimate |S_{tϵ}(x_{j}, r_{j})| ≲ min(M, \frac{t}{δ}). It follows that

\overline{μ}\overline{λ}δ ≲ ∑_{i∈S_{tϵ}(x_{j},r_{j})} |Cδ(x_{j}, r_{j}) ∩ Cδ(x_{i}, r_{i})|

≲ min(M, \frac{t}{δ})\begin{matrix}δ & 2 \\ √ & \overline{tϵ} \end{matrix}

where we used Lemma 3.1(a). Thus \overline{μ} ≲ \overline{λ}^{−1}\sqrt{\frac{t}{ϵ}} min(\frac{Mδ}{t} , 1). Using the hypothesis (ii) we therefore have

\overline{μ} ≲ \overline{λ}^{− \frac{5}{3}} (\frac{t}{ϵ})^{\frac{1}{6}} min(\frac{Mδ}{t} , 1)

i.e.

μ ≲ λ^{− \frac{5}{3}} M^{\frac{1}{6}} · \{ \begin{matrix}a(t, ϵ)^{− \frac{8}{3}} (\frac{δ}{ϵ})^{\frac{1}{6}} (\frac{t}{δM})^{\frac{1}{6}} & if M ≥ \frac{t}{δ} \\ a(t, ϵ)^{− \frac{8}{3}} (\frac{δ}{ϵ})^{\frac{1}{6}} (\frac{Mδ}{t})^{\frac{5}{6}} & if M ≤ \frac{t}{δ} \end{matrix}

The expression in the brace is bounded by a constant provided α < \frac{1}{16}, so we have proved (31).

\underline{Completion of proof of Proposition 3.3} Let Ẽ = \{i : x ∈ Cδ(x_{i}, r_{i})| ≤ μ\} With notation as above we have

|E| ≥ |Ẽ| ≥ μ^{−1} ∑_{j} |Ẽ ∩ Cδ(x_{j}, r_{j})|
≳ μ^{−1}Mλδ
≳ λ^{\frac{8}{3}} M^{\frac{5}{6}} δ

by (31). Consequently (Mδ)^{\frac{5}{6}} ≲ \frac{|E|}{δ^{\frac{1}{6}} λ^{\frac{8}{3}}} and the proposition is proved. □

\underline{Further remarks} 3.2. We mention some other recent related work. Schlag [43] found an essentially optimal L^{p} → L^{q} estimate in the context of Bourgain’s theorem. If we define

Mδf(x) = sup_{1≤r≤2} \frac{1}{|Cδ(x, r)|} ∫_{Cδ(x,r)} |f|

then there is an estimate

∀ϵ∃Cϵ∥Mδf∥_{5} ≲ Cϵδ^{−ϵ}∥f∥_{\frac{5}{2}}

and modulo δ^{−ϵ} factors all possible L^{p} → L^{q} bounds for Mδ follow by interpolation from this one. Alternate proofs and further related results are in [46], [61] and [44]. On the other hand a number of endpoint questions remain open. The best known is the restricted weak type (2, 2) version of Bourgain’s theorem.

3.3. A more central open question is the so-called local smoothing conjecture [48],

[36] in 2 + 1 dimensions. See section 4 below. This is a problem “with cancellation” and likely not susceptible to purely combinatorial methods without additional input. On the other hand, it would imply (18) with p = 4 via the Sobolev embedding theorem and is therefore close to including some of the results of [17]. This means perhaps that a proof not involving any combinatorics would have to contain a significant new idea.

3.4. One can give a discrete heuristic for the Kakeya problem analogous to the one for the BRK sets problem. What follows is an observation of Schlag and the author.

There is a substantial literature on incidence problems for lines in ℝ^{3}; these problems appear to be quite difficult and are largely open. One relevant paper is Sharir [47], where the following problem is considered:

Let \{ℓ_{j}\}_{j=1}^{N} be lines in ℝ^{3} and define a \underline{joint} to be a point where three noncoplanar ℓ_{j}’s intersect. Then how many joints can there be?

If J is the set of joints then as is discussed in [47] the natural conjecture is |J | ≲ N^{\frac{3}{2}} , which would be sharp by taking ≈ \sqrt{N} planes parallel to each of three given planes and considering the lines formed by intersecting two of the planes; any point where three planes intersect will be a joint. The “easy” bound in this problem is |J | ≲ N^{\frac{7}{4}} which is proved in [14] using a suitable version of (3). The bound ∀ϵ∃Cϵ : |J | ≤ CϵN^{\frac{23}{14} +ϵ} is proved in [47] using similar techniques to [17].

The heuristic is that a bound |J | ≲ N^{α} should imply that (in ℝ^{3}) dim(Kakeya)≥ \frac{α}{α−1}. Namely, define a μ-fold point in an arrangement of N lines to be a point where at least μ lines intersect with (say) no more than half of these lines belonging to any given 2-plane. Then any bound of the form |J | ≲ N^{α} leads to a corresponding bound |P_{μ}| ≲ (\frac{N log μ}{μ})^{α} where P_{μ} is the set of μ-fold points. This may be seen (rigorously) as follows: let P_{μ} be the set of μ- fold points in the arrangement. Let A be a large constant and take a random sample of the N lines according to the following rule: each line belongs to the sample independently and with probability \frac{A log μ}{μ}. Then with high probability the sample has cardinality ≲ \frac{N log μ}{μ}. Furthermore, it is not hard to show that any point of P_{μ} will be a joint for the lines in the sample with probability at least 1 − μ^{−B}, where B is large if A is large. It follows that with high probability at least half the points of P_{μ} will be joints for the sample, hence |P_{μ}| ≲ (\frac{N log μ}{μ})^{α}.

Now the heuristic part of the argument: suppose we have a Kakeya set E with (say, Minkowski) dimension β. Fix δ and take a δ-separated set of directions and a line segment in each direction contained in E; this gives an arrangement of ≈ δ^{−2} lines {ℓ_{j}}. Let Eδ be the δ-neighborhood of E; thus |Eδ| ≈ δ^{β}, so Eδ is made up of roughly δ^{−β} δ-discs. A typical point in the δ-neighborhood of E should belong to roughly δ^{−(3−β)} δ-neighborhoods of ℓ_{j}’s, since otherwise the “low multiplicity” arguments discussed e.g. in section 2 would show easily that |Eδ| >> δ^{β}. Hence if we ignore the distinction between points and δ-discs then we are dealing with an arrangement of δ^{−2} lines with δ^{−β} δ^{−(3−β)}-fold points. We conclude that up to logarithmic factors

δ^{−β} ≲ (\begin{matrix}δ & −2 \\ δ & −(3−β) \end{matrix} )^{α}

i.e. β ≥ \frac{α}{α−1}.

Under this heuristic the result of [47] would correspond to an improvement over \frac{5}{2} on Kakeya, and the fact that the joints problem is open would seem to indicate that questions 1 and 2 are quite difficult even on a combinatorial level, if in fact the answers are affirmative. In this connection, we note that Schlag [45] has proved an analogue of the 3-circle lemma in this context and has used it to give an alternate proof of the result dim(Kakeya)≥ \frac{7}{3} (originally due to Bourgain [7]) which corresponds to the result from [14] via \frac{7}{3} = \frac{7/4}{7/4−1}. However, it is not easy to put the argument of [47] into the continuum and the author believes that in contrast to the situation considered in [61] it may not be possible to do this in a reasonably straightforward way.

A further remark is that special cases of the three dimensional Kakeya problem correspond to results analogous to [61] with circles replaced by families of curves satisfying the cinematic curvature condition from [48]. For example, the case of sets invariant by rotations around an axis is a problem of this type as is discussed in [31].

4. Oscillatory integrals and Kakeya It seemed appropriate to include a discussion of the basic open problems in harmonic

analysis connected with Kakeya, but we will not attempt a complete survey and will not say anything about the proofs of the deeper results. We will just state some well-known open problems and show how they lead to questions 1 and 2.

Let f̂ be the Fourier transform and if m is a given function, then let T_{m}f be the corresponding multiplier operator,

T̂_{m}f = mf̂

Two longstanding problems in L^{p} harmonic analysis are the following:

\underline{Restriction problem}: is there an estimate

∥f̂dσ∥_{p} ≲ ∥f∥_{L^{p}(dσ)}  (37)

for all p > \frac{2n}{n−1}, where σ is surface measure on the unit sphere S^{n−1} ⊂ ℝ^{n}?

\underline{Bochner-Riesz problem}: let mδ be a smooth cutoff to a δ-neighborhood of S^{n−1}, i.e.

mδ(ξ) = ϕ(δ^{−1}(1 − |ξ|))

where ϕ ∈ C_{0}^{∞}(ℝ) is supported in (−\frac{1}{2}, \frac{1}{2}). Then is there an estimate

∀ϵ∃Cϵ : ∥T_{mδ}f∥_{p} ≤ δ^{−ϵ}∥f∥_{p}  (38)

when p ∈ [\frac{2n}{n+1}, \frac{2n}{n−1}]?

Both these problems can be formulated in a number of different ways; the formulations we have given are not the original ones but are well-known to be equivalent to them. In fact it would also be equivalent to prove (37) in the weaker form ∥f̂dσ∥_{p} ≲ ∥f∥_{∞}, p > \frac{2n}{n−1}. This is a consequence of the Stein-Nikisin theory as is pointed out in [7], section 6.

A third problem of more recent vintage [48] is

\underline{Local smoothing} Let u be the solution of the initial value problem for the wave equation in n space dimensions,

□u = 0, u(·, 0) = f, \frac{∂u}{∂t}(·, 0) = 0

Then is there an estimate

∀ϵ > 0∃Cϵ : ∥u∥_{L^{p}(ℝ^{n}×[1,2])} ≤ Cϵ∥f∥_{p,ϵ}  (39)

when p ∈ [2, \frac{2n}{n−1}]? Here ∥ · ∥_{p,ϵ} is the inhomogeneous L^{p} Sobolev norm with ϵ derivatives.

In all these problems it is well-known that the exponent \frac{2n}{n−1} would be optimal. See [52]. For example, in the last problem this may be seen by considering focussing solutions where f is spread over a δ-neighborhood of the unit sphere and u(·, t) is mostly concentrated on a δ-disc when t ∈ (1, 1 + δ).

When n = 2, estimate (37) was proved by Fefferman and Stein and then (38) by Carleson and Sjolin, in the early 1970’s (see [52]). Estimate (39) is open even when n = 2 however; the known partial results on L^{4}(ℝ^{2}) correspond to loss of \frac{1}{8} derivatives ([36]; an improvement to loss of \frac{1}{8} − ϵ derivatives appears implicit in [12], p. 60). In general dimensions, the following implications are known.

(39) ⇒ (38) ⇒ (37) ⇒ (2)

The first implication is due to Sogge, the second which is deeper is due to Tao [58], and Carbery [13] had shown earlier that the second implication can be reversed in a slightly different context (replace spheres by paraboloids). We refer to [58] for further discussion. Here though we will only be concerned with the last implication which makes the connection with the Kakeya problem. Essentially this is due to Fefferman [23], another relevant reference is [3] and the result as presented here is from [10]. A basic open problem in the area is to what extent the last implication can be reversed. An alternate proof of the two dimensional Carleson-Sjolin result along these lines was given by Cordoba [18]. In three or more dimensions, progress on this problem was initiated by Bourgain (see [10]) who obtained a numerology between partial results which however does not show that (2) would imply (37). For a recent improvement in the numerology see [38] and [59].

A problem of a somewhat different nature is

\underline{Montgomery’s conjecture} Assume T ≤ N^{2}. Consider a Dirichlet series,

D(s) = ∑_{n=1}^{N} a_{n}n^{is}

where ∥{a_{n}}∥_{ℓ^{∞}} ≤ 1. Let T be a 1-separated subset of [0, T]. Then

∀ϵ∃Cϵ : ∑_{t∈T} |D(t)|^{2} ≤ Nϵ(N + |T |)N

An easy consequence (or reformulation) would be that

∀ϵ∃Cϵ : ∫_{E} |D(t)|^{2}dt ≤ Nϵ(N + |E|)N  (40)

if E ⊂ [0, T] with the stated hypotheses on T and D(s). This is an estimate on the measure of the set of large values of D(s) and would also imply estimates of L^{p} norms with p > 2. See [9] and e.g. [37] for these remarks as well as some discussion of the relationship between (40) and open problems in analytic number theory. Estimate (40) can perhaps be thought of as an analogue of (37) where the oscillatory sum operator {a_{n}} → D(s) replaces the extension operator f → f̂dσ. Bourgain [9] showed that (40) is again related to the Kakeya problem.

In the rest of this article, we will discuss implications of this type, i.e.

oscillatory integral estimates ⇒ Kakeya estimates

We first show that (37) implies (2), and will record the corresponding implications between partial results. Let us recall the results that would follow from (37) using Holder’s inequality and interpolation with the trivial bound ∥f̂dσ∥_{∞} ≤ ∥f∥_{L^{1}(dσ)}, say

∥f̂dσ∥_{q} ≲ ∥f∥_{L^{p}(dσ)}, p < \frac{2n}{n − 1}, q > \frac{n + 1}{n − 1}p′  (41)

This bound for p ≤ 2 (plus its endpoint version where q = \frac{n+1}{n−1}p′) is a well-known theorem proved by Stein and Tomas in the 1970’s and the case p = q < 2\frac{n+1}{n−1} + ϵ for suitable ϵ > 0 was proved more recently by Bourgain [7] using considerations related to question 2. See [52] and [10].

\underline{Proposition 4.1} Assume (41) holds for a given p ≥ 2 and q ≥ 2. Then, with r = (\frac{q}{2})′ and s = (\frac{p}{2})′, the restricted weak type (r, s) norm of the Kakeya maximal operator is ≲ δ^{−2( \frac{n}{r} −1)}. Consequently the Hausdorff dimension of Kakeya sets is ≥ 2r − n = \frac{2q}{q−2} − n. In particular (37) implies (2).

\underline{Proof} First let \{T_{j}\}_{j=1}^{N}, T_{j} = T δ_{e_{j}}(a_{j}) be any collection of δ-tubes with δ-separated directions e_{j}. Let T̃_{j} = {x ∈ ℝ^{n} : δ^{2}x ∈ T_{j}} be the dilation of T_{j} by a factor δ^{−2}, and let χ_{j} and χ̃_{j} be the characteristic functions of T_{j} and T̃_{j} respectively. Let C_{j} be a spherical cap with radius ≈ δ centered at e_{j}, e.g. C_{j} = {e ∈ S^{n−1} : e · e_{j} ≥ 1 − C^{−1}δ^{2}} where C is a suitable constant. Take a bump function supported in C_{j}, say ϕ_{j} ∈ C_{0}^{∞}(C_{j}) with ∥ϕ_{j}∥_{∞} = 1, ϕ_{j} ≥ 0 and ∥ϕ_{j}∥_{1} ≈ δ^{n−1}, and let ψ_{j}(ξ) = e^{2πiξ·δ^{−2}a_{j}}ϕ_{j}(ξ). If x ∈ T̃_{j}, then the integral

{ \atop ψ_{j}dσ}(x) = ∫_{S^{n−1}} ψ_{j}(ξ)e^{−2πiξ·x}dξ = e^{−2πie_{j}·(x−δ^{−2}a_{j})} ∫_{C_{j}} ϕ_{j}(ξ)e^{−2πi(ξ−e_{j})·(x−δ^{−2}a_{j})}dξ

defining { \atop ψ_{j}dσ}(x) involves no cancellation, so

|{ \atop ψ_{j}dσ}| ≳ δ^{n−1}χ̃_{j}  (42)

Now consider the function f = ∑_{j} ϵ_{j}ψ_{j} where the ϵ_{j} are random ±1’s. Since the supports of the ψ_{j} are disjoint we have

∥f∥_{L^{p}(S^{n−1})} ≲ (Nδ^{n−1})^{\frac{1}{p}}

and therefore, by the assumption (41),

∥f̂dσ∥_{q} ≲ (Nδ^{n−1})^{\frac{1}{p}}  (43)

for any choice of ±. On the other hand, if we let 𝔼 denote expectation with respect to the choices of ±, then by Khinchin’s inequality and (42)

𝔼(|f̂dσ|^{q}) ≳ δ^{q(n−1)}(∑_{j} χ̃_{j})^{\frac{q}{2}}

pointwise. If we integrate this inequality and compare with (43) we obtain

δ^{q(n−1)}∥ ∑_{j} χ̃_{j}∥\frac{q}{2} ; \frac{q}{2} ≲ (Nδ^{n−1})^{\frac{q}{p}}

Rescaling by δ^{2}, then taking \frac{q}{2}th roots,

δ^{2(n−1)− \frac{4n}{q}} ∥ ∑_{j} χ_{j}∥_{\frac{q}{2}} ≲ (Nδ^{n−1})^{\frac{2}{p}}

Now let E be a set, f = χ_{E} and

Ω = {e : fδ^{∗}(e) ≥ λ}

Let {e_{j}}_{j=1}^{N} be a maximal δ-separated subset of Ω and for each j choose a δ-tube T_{j} as above with |E ∩ T_{j}| ≥ λ|T_{j}|. Then

Nλδ^{n−1} ≤ ∑_{j} |T_{j} ∩ E|
≲ |E|^{1− \frac{2}{q}} ∥ ∑_{j} χ_{j}∥_{\frac{q}{2}}
≲ |E|^{1− \frac{2}{q}} (Nδ^{n−1})^{\frac{2}{p}} δ^{−2(n−1)+ \frac{4n}{q}}

Using (6) this implies that

|Ω|^{1− \frac{2}{p}} ≲ λ^{−1}|E|^{1− \frac{2}{q}} δ^{−2(n−1)+ \frac{4n}{q}}

i.e. |Ω|^{\frac{1}{s}} ≲ λ^{−1}|E|^{\frac{1}{r}} δ^{−2( \frac{n}{r} −1)} which is the bound that was claimed. The dimension statement in the proposition then follows from Lemma 1.6, and the last statement also follows by letting p → \frac{2n}{n−1} and using well-known formal arguments. □

\underline{Remarks} 4.1. The original Fefferman construction was of course a counterexample; essentially he showed

If the disc multiplier were bounded on L^{p} with p ≠ 2, then families of tubes with the property in Remark 1.2 could not exist.

The paper [3] applies the argument from [23] to the restriction problem in the above way but the result is again formulated as a counterexample. The formulation as an implication concerning the maximal function is from [10].

4.2. We present another application of the Fefferman construction which shows the following.

\underline{Claim} For any n ≥ 2, p > 2, K < ∞, there are solutions of □u = f in n space dimensions, with ∥f∥_{∞} ≤ 1, suppf ⊂ D(0, 100) × [0, 1], and

∫_{2}^{3} ∥\frac{∂u}{∂t}(·, t)∥_{L^{p}(ℝ^{n})}dt > K  (44)

The analogous statement with the x-gradient replacing the t-derivative can be proved in a similar way. The statement can be understood as follows: the energy estimate for the wave equation implies via Duhamel’s principle that ∥∇u(·, t)∥_{2} ≲ ∥f∥_{2} if say t ∈ (2, 3) and f is supported in ℝ^{n} × [0, 1]. The claim says that there can be no such estimate in L^{p}, p > 2, even if one is willing to average in t as in (39) and to restrict to bounded f with compact support. The claim was proved by the author after discussions with S. Klainerman but it is very close to the surface given [23]. The analogous statement for the initial value problem is essentially that (39) fails if the W^{pϵ} norm is replaced by the L^{p} norm on the right hand side; this is a formal consequence of [23] as was probably first observed by Sogge.

The construction below by no means rules out an estimate with loss of ϵ derivatives. In fact the estimate ∫_{2}^{3} ∥\frac{∂u}{∂t}(·, t)∥_{L^{p}(ℝ^{n})}^{p}dt ≲ ∥f∥_{p,ϵ}^{p} with 2 < p ≤ \frac{2n}{n−1} and any ϵ > 0 would follow from (39) via Duhamel.

\underline{Proof of the claim} If x ∈ ℝ^{n} then we will use the notation x = (x_{1}, \overline{x}), \overline{x} ∈ ℝ^{n−1}. For an appropriate constant C and any small enough δ there is a solution of □u = f

with

∥f∥_{∞} ≤ 1, suppf ⊂ \{(x, t) : 0 ≤ t ≤ 1, 0 ≤ x_{1} ≤ 1, |\overline{x}| ≤ δ\}

and

|\frac{∂u}{∂t}| ≥ C^{−1} when 2 ≤ t ≤ 3, x ∈ Y^{t}  (45)

where Y^{t} is a subset of \{x ∈ ℝ^{n} : 2 ≤ x_{1} ≤ 3, |\overline{x}| ≤ δ\} with measure ≥ C^{−1}δ^{n−1}.

This is essentially just the fact that there are high frequency solutions of the wave equation travelling in a single direction tangent to the light cone, which implies we can find f with the indicated support and such that u restricted to 2 ≤ t ≤ 3 is also mostly concentrated where |\overline{x}| ≲ δ. The conclusion then corresponds to conservation of energy.

A rigorous argument can be based on the explicit choice

f(x, t) = e^{2πiN(x_{1}−t)}ϕ(x_{1})ψ(δ^{−1}\overline{x})χ(t)

where N is very large, ϕ, ψ, χ are fixed nonnegative C_{0}^{∞} functions, ψ(0) = 1, suppψ ⊂ D(0, 1), suppϕ =suppχ = [0, 1] and ϕ and χ are strictly positive on (0, 1). Let u be the corresponding solution of the wave equation. Then u is given by the formula

u(x, t) = ∫ e^{2πix·ξ} \frac{sin(2π(t − s)|ξ|)}{2π|ξ|}e^{−2πiNs}ϕ̂(ξ_{1} − N)δ^{n−1}ψ̂(δ\overline{ξ})χ(s)dξds

One can differentiate for t and then evaluate the resulting integral precisely enough to obtain (45) in the region |x_{1} − t| ≤ \frac{1}{2}, |\overline{x}| ≤ C^{−1}δ. We omit the details.

If E is a set in space-time then we will use the notation E^{t} = {x ∈ ℝ^{n} : (x, t) ∈ E}. By Remarks 1.2 and 1.3 we can find disjoint δ-tubes {T_{j}}_{j=1}^{M} in ℝ^{n} (M ≈ δ^{−(n−1)}) such that the tubes T̃_{j} obtained by translating the T_{j}’s by 2 units along their axes are all contained in a set with small measure a(δ). Let Π_{j} = T_{j} × [0, 1] ⊂ ℝ^{n} × ℝ, and let Π̃_{j} = T̃_{j} × [2, 3]. By the first step of the proof there are functions u_{j} and f_{j}, □u_{j} = f_{j}, with f_{j} supported on Π_{j}, ∥f_{j}∥_{∞} ≤ 1, and |\frac{∂u_{j}}{∂t} | ≥ const on a subset Y_{j} ⊂ Π̃_{j} which satisfies |Y_{j}^{t}| ≈ δ^{n−1} for each t ∈ (2, 3). Let Z = ∪_{j}Y_{j}; then |Z^{t}| ≲ a(δ) for any t ∈ (2, 3).

Let {ϵ_{j}} be random ±1’s. Consider the functions u = ∑_{j} ϵ_{j}u_{j}, f = ∑_{j} ϵ_{j}f_{j}, which satisfy □u = f. The Π_{j}’s are disjoint, so ∥f∥_{∞} ≤ 1 for any choice of ϵ_{j}’s. On the other hand, by Holder’s and Khinchin’s inequalities, for any fixed t ∈ (2, 3) we have

𝔼 (∫_{Z^{t}} |\frac{∂u}{∂t}(x, t)|^{p}dx)^{\frac{2}{p}} ) ≳ a(δ)^{−(1− \frac{2}{p})}𝔼 (∫_{Z^{t}} |\frac{∂u}{∂t}(x, t)|^{2}dx))
= a(δ)^{−(1− \frac{2}{p})} ∫_{Z^{t}} ∑_{j} |\frac{∂u_{j}}{∂t} (x, t)|^{2}dx
≳ a(δ)^{−(1− \frac{2}{p})} ∑_{j} |Y_{j}^{t}| ≈ a(δ)^{−(1− \frac{2}{p})}

which shows there can be no estimate of the form

(∫_{2}^{3} ∥\frac{∂u}{∂t}(·, t)∥_{L^{p}(ℝ^{n})}^{2}dt)^{\frac{1}{2}} ≤ C∥f∥_{∞}

with p > 2 when f has support in D(0, 100) × [0, 1]. We then also obtain (44), since an estimate to L_{t}^{1}(L_{x}^{p}) would imply an estimate to L_{t}^{2}(L_{x}^{q}) (\frac{1}{q} = \frac{1}{2}(\frac{1}{2} + \frac{1}{p})) by interpolation with the energy estimate to L_{t}^{∞}(L_{x}^{2}). □

We now discuss the argument from [9] relating (40) to (2). Bourgain showed there that Montgomery’s conjecture if true would imply Kakeya sets have full dimension and a bound like (2) with a different L^{p} exponent. We reworked the argument a bit for expository reasons and in order to obtain the precise result (40)⇒(2).

The logic is that (40) implies a Kakeya type statement for arithmetic progressions, which in turn implies (2) for all n. Thus the implication (40) ⇒ (2) follows by combining Propositions 4.2 and 4.3 below.

If ν ∈ (0, 1), β ∈ ℝ, then we denote

P δ_{ν}(β) = {x ∈ [0, 1] : |x − (jν + β)| < δ for some j ∈ ℤ}

i.e. P δ_{ν}(β) is the δ-neighborhood of the arithmetic progression with modulus ν which contains β, intersected with [0, 1].

\underline{Proposition 4.2} Assume the conjecture (40). Then for any ϵ there is Cϵ such that the following holds.

(∗) Fix η ∈ (0, 1), δ ∈ (0, η). Let E ⊂ [0, 1] be such that

∀ν ∈ Y ∃β ∈ ℝ : |P δ_{ν}(β) ∩ E| ≥ λ|P δ_{ν}(β)|  (46)

where λ ∈ (0, 1] satisfies λ ≥ Cϵ(\frac{δ^{2}}{η})^{−ϵ}·η, and where Y is a subset of (\frac{η}{2}, η) with |Y | ≥ \frac{η}{100}. Then

|E| ≥ Cϵ^{−1}(\frac{δ^{2}}{η})ϵλ

\underline{Proof} This will be formally similar to the proof of Proposition 4.1 if one makes the analogy

line segment ⟷ arithmetic progression

spherical cap ⟷ interval of integers

\underline{Claim 1}: Let N and T be as in (40) and let ϵ_{0} be a suitable constant. Then, for ν ∈ [\frac{N}{2} , N] and β ∈ ℝ, the Dirichlet series

d(s) = ∑_{n:|n−[ν]|≤ϵ_{0} \frac{N}{\sqrt{T}}} e^{−i \frac{β}{[ν]} (n−[ν])}n^{is}  (47)

satisfies

|d(s)| ≳ \frac{N}{\sqrt{T}}

when s ≤ T and dist(s, 2πνℤ + β) ≤ \sqrt{T}.

\underline{Proof} This is the “short sum” construction in [9]. Assume at first that ν ∈ ℤ. The Taylor expansion of the logarithm function shows that n^{is} = ν^{is}e^{is( \frac{n−ν}{ν} +O( \frac{n−ν}{ν})^{2})}), so that e^{−i \frac{β}{ν} (n−ν)}n^{is} = ν^{is}e^{i(n−ν)) \frac{s−β}{ν} +isO(( \frac{n−ν}{ν})^{2})}. Thus the sum (47) involves no cancellation and the bound follows immediately. The general case (i.e. ν ∉ ℤ) follows by replacing ν by [ν] and noting that this does not significantly affect the hypothesis on s, since if dist(s, 2πνℤ + β) ≤ \sqrt{T} then dist(s, 2π[ν]ℤ + β) ≤ \sqrt{T} + C \frac{T}{N} ≲ \sqrt{T}.

We therefore define P̃_{ν}(β) = \{x ∈ [0, T] : dist(s, 2πνℤ + β) ≤ \sqrt{T} \}. We also fix a number ϵ > 0 and let Cϵ be a suitable constant.

\underline{Claim 2} Assume (40) and let E be a subset of [0, T] with the following property: there is a set Y ⊂ [\frac{N}{2} , N] with |Y | ≥ \frac{N}{100}, such that for any ν ∈ Y there is β = β(ν) ∈ ℝ such that |E ∩ P̃_{ν}(β)| ≥ λ|P̃_{ν}(β)|. Then

|E| ≥ Cϵ^{−1}N^{−ϵ}T λ  (48)

provided λ ≥ CϵNϵ \frac{N}{T}.

\underline{Proof} Let ϵ_{0} be as in claim 1, choose a maximal 2ϵ_{0} \frac{N}{\sqrt{T}} + 1-separated subset \{ν_{j}\}_{j=1}^{M} ⊂ Y, denote P̃_{j} = P̃_{ν_{j}}(β_{j}) and let χ_{j} be the characteristic function of P̃_{j}. Construct Dirichlet series d_{j}(s) = ∑_{n:|n−[ν_{j}]|≤ϵ_{0} \frac{N}{\sqrt{T}}} a_{n}n^{is} via claim 1 so that |d_{j}(s)|^{2} ≳ \frac{N^{2}}{T} χ_{j}. Let D(s) = ∑_{j} ϵ_{j}d_{j}(s) where the ϵ_{j} are random ±1’s. By Khinchin’s inequality

𝔼(|D(s)|^{2}) ≳ \frac{N^{2}}{T} ∑_{j=1}^{M} χ_{j}  (49)

pointwise. On the other hand the coefficient intervals for the d_{j} are disjoint so for any choice of ±1, D(s) will be a Dirichlet series with coefficients bounded by 1. Integrating (49) over E and using (40), we obtain

\frac{N^{2}}{T} ∑_{j=1}^{M} |E ∩ P̃_{j}| ≲ 𝔼(∫_{E} |D(s)|^{2})
≲ Nϵ(N + |E|)N

We have M ≈ \sqrt{T}, and for each j we have |E∩P̃_{j}| ≥ λ\frac{T ^{\frac{3}{2}}}{N}. So we obtain T λ ≲ Nϵ(N+|E|). Under the stated hypothesis on λ this implies (48).

Proposition 4.2 follows from claim 2 by rescaling: set T = δ^{−2} and N = ηδ^{−2}, and make the change of variables x → T x, ν → T ν. □

\underline{Proposition 4.3} If (∗) holds then (2) holds in all dimensions n.

\underline{Proof} We first observe that (∗) implies a generalization of itself via a well-known formal argument (one of the arguments in the Stein-Nikisin theory, see [50], p. 146). Namely, drop the hypothesis |Y | ≥ \frac{η}{100}. Then, with the other hypotheses unchanged,

|E| ≳ λ\frac{|Y |}{η}(\frac{δ^{2}}{η})ϵ  (50)

To prove (50), let ρY be the dilation of Y by ρ. One can find numbers \{ρ_{j}\}_{j=1}^{M} ⊂ (\frac{1}{2}, 2),

where M ≈ \frac{η}{|Y |}, so that Ỹ =^{def} ∪_{j}ρ_{j}Y satisfies |Ỹ | ≥ \frac{η}{10}. Let Ẽ = ∪_{j}ρ_{j}E. Then Ẽ satisfies

(46) when ν ∈ Ỹ so |Ẽ| ≳ λ(\frac{δ^{2}}{η})ϵ, hence |E| ≳ λM^{−1}(\frac{δ^{2}}{η})ϵ which is (50).

Now we consider the Kakeya problem, and will give without detailed proof a few reductions made in [7], p. 152.

A. In order to prove (2) it suffices to prove the following inequality: let E be a set in ℝ^{n}, let Ω be a subset of S^{n−1} with |Ω| ≥ \frac{1}{2}, and assume that for any e ∈ Ω there is a tube

T δ_{e}(a) such that |T δ_{e}(a) ∩ E| ≥ λ|T δ_{e}(a)|. Then

∀ϵ > 0∃Cϵ : |E| ≥ Cϵ^{−1}δϵλ^{n}  (51)

To make this reduction one first observes that (2) is equivalent to the corresponding restricted weak type statement,

|\{e ∈ S^{n−1} : fδ^{∗}(e) ≥ λ\}| ≲ δ^{−ϵ} \frac{|E|}{λ^{n}}  (52)

where f = χ_{E}, and then uses the above argument from [50] to reduce (52) to the case where the left hand side is ≥ \frac{1}{2}. Furthermore, if |E ∩ T δ_{e}(a)| ≥ λ|T δ_{e}(a)| even for one choice of e and a then clearly |E| ≳ λδ^{n−1}. It follows that in proving (51) we can assume λ ≥ δ.

B. We define Q to be the unit cube [0, 1) × … × [0, 1). Let N be an integer to be fixed below, such that \frac{1}{N} < δ. If ν ∈ ℤ^{n}, then we define Q_{ν} to be the cube [\frac{ν_{1}}{N} , \frac{ν_{1}+1}{N}) × … × [\frac{ν_{n}}{N} , \frac{ν_{n}+1}{N}). When we refer below to a \frac{1}{N} -cube we always mean a cube which is of the form Q_{ν} for some ν ∈ ℤ^{n}. In proving (51) we can assume that E is contained in Q; this follows easily since the tubes T δ_{e}(a) have diameter ≲ 1. Furthermore we can assume that E is a union of \frac{1}{N} -cubes; see [7].

C. It is easy to see that fδ^{∗}(e′) ≤ Cfδ^{∗}(e) if |e − e′| ≤ δ, since any tube T δ_{e′}(b) can be

covered by a bounded number of tubes of the form T δ_{e}(a). Accordingly if Ω is as in A., C_{1} is a constant, and if dist(e, Ω) ≤ C_{1}δ then there is a such that |T δ_{e}(a) ∩ E| ≥ C^{−1}λ|T δ_{e}(a)| where C depends on C_{1}.

In proving (51) we may assume that

|Ω ∩ \{e ∈ S^{n−1} : e_{1} ≥ \frac{1}{2}\}|

is bounded below by a constant depending on n only, since we can always achieve this by an appropriate choice of coordinates. In addition, as indicated above we may assume λ ≥ δ, and we may certainly assume that ϵ is small. Fix integers N and B satisfying the following relations:

B^{−1}N^{2nϵ} ≈ λ and \frac{B}{N} ≈ δ  (53)

Then N ≈ (δλ)^{\frac{−1}{1−2nϵ}}, so that

Nδ is large, N ≤ δ^{−3}, B is large, and BN^{−n} ≤ B^{−1}  (54)

Define a map Φ : ℝ^{n} → ℝ via

Φ(x) = \frac{[Nx_{1}]}{N} + \frac{[Nx_{2}]}{N^{2}} + … + \frac{[Nx_{n−1}]}{N^{n−1}} + \frac{Nx_{n}}{N^{n}}

Then Φ maps Q into [0, 1). We make a few additional remarks about the definition:

(i) Note the distinguished role played by the last coordinate.

(ii) Φ maps \frac{1}{N} -cubes on intervals of length N^{−n}, hence if E is a union of \frac{1}{N} -cubes then |Φ(E)| = |E|.

(iii) Suppose that x ∈ ℝ^{n}. Then x belongs to a unique \frac{1}{N} -cube Q_{ν}. Define τ(x) (“tower over x”) via

τ(x) = ∪(Q_{μ} : μ_{j} = ν_{j} when j < n and |μ_{n} − ν_{n}| ≤ B)

Then, for any x, Φ maps τ(x) on an interval of length \frac{2B+1}{N^{n}}.

(iv) Suppose that w = (\frac{k_{1}}{N} , …, \frac{k_{n}}{N}) where the \{k_{j}\} are \underline{integers}. Set ν(w) = ∑_{j} \frac{k_{j}}{N^{j}}. Then Φ maps any arithmetic progression {x + jw}_{j∈ℤ} to an arithmetic progression in ℝ with modulus ν(w).

A \underline{lattice vector} will be by definition a vector in ℝ^{n} of the form

w = (\frac{k_{1}}{N} , …, \frac{k_{n}}{N})

where the \{k_{j}\} are integers with k_{1} ∈ (\frac{N}{2B} , \frac{N}{B}) and \sqrt{∑_{j} k_{j}^{2}} ≤ 2k_{1}. Thus any lattice

vector w satisfies |w| ≈ \frac{1}{B}. We note that if e ∈ S^{n−1} satisfies e_{1} ≥ \frac{1}{2} then |e − \frac{w}{|w|}| ≲ δ for approximately \frac{N}{B} lattice vectors w, namely all the lattice vectors w = \frac{k}{N} which correspond to integer vectors k such that |k − te| ≲ 1 for some t with t ≈ \frac{N}{B}. Accordingly, for an appropriate constant A there are ≳ (\frac{N}{B})^{n} lattice vectors w such that dist(\frac{w}{|w|}, Ω) ≤ Aδ. We denote this set of lattice vectors by Λ.

If w ∈ Λ, then we will abuse our notation slightly and denote the tube T δ_{\frac{w}{|w|}} (a) by T δ_{w}(a).

By C. above, for each w ∈ Λ we can choose a ∈ ℝ^{n} so that |T δ_{w}(a) ∩ E| ≳ λ|T δ_{w}(a)|. It then follows by an averaging argument^{5} that there is a′ ∈ ℝ^{n} such that

|E ∩ (∪_{j=1}^{B}τ(a′ + jw))| ≳ λ| ∪_{j=1}^{B} τ(a′ + jw)|  (55)

∫_{Tδ_{w}(a)∩E} |σ_{x}|dx ≥ λm|T δ_{w}(a)| ≈ λm|T̃ δ_{w}(a)|, so (55) holds for suitable a′ ∈ T̃ δ_{w}(a).

5Namely: let m be the measure of the set ∪_{j=1}^{B}τ(a′ + jw); m is clearly independent of a′, and furthermore if x ∈ ℝ^{n} is given then the measure of the set σ_{x} = {a′ : x ∈ ∪_{j=1}^{B}τ(a′ + jw)}| is also comparable to m. If x ∈ T δ_{w}(a) then, since \frac{B}{N} ≲ δ and |w| ≲ \frac{1}{B}, the set σ_{x} will be contained in T̃ δ_{w}(a), the dilation of T δ_{w}(a) by a suitable fixed constant. It follows that ∫_{T̃δ_{w}(a)} |E ∩ (∪_{j=1}^{B}τ(a′ + jw))|da′ ≥

Now set ρ = \frac{B}{4N^{n}}. By (iv) above, the image of the progression a′, a′ + w, ⋯ a′ + Bw under Φ is an arithmetic progression β, β+ν(w), ⋯, β+Bν(w). By (iii), Φ(∪_{j=1}^{B}τ(a′+jw)) is a union of intervals containing the points of this progression, with the length of each interval being less than ρ and comparable to ρ. Since E and ∪_{j=1}^{B}τ(a′ + jw) are unions of \frac{1}{N} -cubes, (55) and (ii) then imply that |Φ(E) ∩ P_{ν}^{ρ}(β)| ≳ λ|P_{ν}^{ρ}(β)|. We conclude:

If ν = ν(w) for some w ∈ Λ, then there is β such that

|P_{ν}^{ρ}(β) ∩ E| ≳ λ|P_{ν}^{ρ}(β)|  (56)

Let Y = {ν ∈ ℝ : |ν − ν(w)| ≤ N^{−n} for some w ∈ Λ}. It follows easily that (56) continues to hold (for suitable β) for any ν ∈ Y. Note that Y ⊂ (\frac{1}{2B} , \frac{2}{B}) (because of the requirement \frac{N}{2B} ≤ k_{1} ≤ \frac{N}{B}) and also |Y | ≳ B^{−n}, since the set \{ν(w) : w ∈ Λ\} is N^{−n}-separated and has cardinality ≳ (\frac{N}{B})^{n}.

Now λ is large compared with B^{−1} · (B(BN^{−n})^{2})^{−ϵ} by (53), (54), so we can apply (50) with η = B^{−1}, δ = BN^{−n}, and with \frac{|Y |}{η} ≳ B^{−(n−1)}. We conclude that |Φ(E)| ≳ λB^{−(n−1)}(B^{3}N^{−2n})ϵ. Again using (53) and (54), we obtain |Φ(E)| ≳ λ^{n}N^{−2n^{2}ϵ} ≥ λ^{n}δ^{6n^{2}ϵ}. But E is a union of \frac{1}{N} -cubes so |E| = |Φ(E)|, and since ϵ is arbitrary this proves (51). □

References

[1] D. Alvarez, Berkeley thesis, 1997, and to appear.

[2] J. Barrionuevo, \underline{A note on the Kakeya maximal operator}, Math. Research Letters 3(1996), 61-65.

[3] W. Beckner, A. Carbery, S. Semmes, F. Soria, \underline{A note on restriction of the Fourier}

\underline{transform to spheres}, Bull. London Math. Soc. 21(1989), 394-398.

[4] A.S. Besicovitch, R. Rado, \underline{A plane set of measure zero containing circumferences} \underline{of every radius}, J. London Math. Soc. 43 (1968), 717-719.

[5] B. Bollobas, Graph Theory: an introductory course, Graduate Texts in Mathematics vol. 63, Springer-Verlag, 1979.

[6] J. Bourgain, \underline{Averages in the plane over convex curves and maximal operators}, J. Analyse Math. 47(1986), 69-85.

[7] J. Bourgain, \underline{Besicovitch type maximal operators and applications to Fourier}

\underline{analysis}, Geometric and Functional Analysis 1 (1991), 147-187.

[8] J. Bourgain, \underline{L^{p} estimates for oscillatory integrals in several variables}, Geometric and Functional Analysis 1(1991), 321-374.

[9] J. Bourgain, \underline{On the distribution of Dirichlet sums}, J. Anal. Math. 60(1993), 21-32.

[10] J. Bourgain, \underline{Some new estimates for oscillatory integrals}, in Essays on Fourier analysis in honor of Elias M. Stein, ed. C. Fefferman, R. Fefferman, S. Wainger, Princeton University Press, 1994.

[11] J. Bourgain, \underline{Hausdorff dimension and distance sets}, Israel J. Math 87(1994), 193-201.

[12] J. Bourgain, \underline{Estimates for cone multipliers}, Operator Theory: Advances and Applications, 77 (1995), 41-60.

[13] A. Carbery, \underline{Restriction implies Bochner-Riesz for paraboloids}, Proc. Cambridge Phil. Soc. 111(1992), 525-529.

[14] B. Chazelle, H. Edelsbrunner, L. J. Guibas, R. Pollack, R. Seidel, M. Sharir, J. Snoeyink, \underline{Counting and cutting cycles of lines and rods in space}, Comput. Geom. Theory Appls. 1(1992), 305- 323.

[15] M. Christ, \underline{Estimates for the k- plane transform}, Indiana Univ. Math. J. 33(1984), 891-910.

[16] M. Christ, J. Duoandikoetxea, J. L. Rubio de Francia, \underline{Maximal operators related}

\underline{to the Radon transform and the Calderon- Zygmund method of rotations}, Duke Math. J. 53(1986),189-209.

[17] K. L. Clarkson, H. Edelsbrunner, L. J. Guibas, M. Sharir, E. Welzl, \underline{Combinatorial}

\underline{complexity bounds for arrangements of curves or spheres}, Discrete Comput. Geom. 5(1990), 99-160.

[18] A. Cordoba, \underline{The Kakeya maximal function and spherical summation multi}\underline{pliers}, Amer. J. Math. 99 (1977), 1-22.

[19] R. O. Davies, \underline{Some remarks on the Kakeya problem}, Proc. Cambridge Phil. Soc. 69(1971), 417-421.

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

[21] K. J. Falconer, The geometry of fractal sets, Cambridge University Press, 1985.

[22] K. J. Falconer, \underline{On the Hausdorff dimension of distance sets}, Mathematika 32(1985), 206-212.

[23] C. Fefferman, \underline{The multiplier problem for the ball}, Ann. Math. 94(1971), 330-336.

[24] R. L. Graham, B. L. Rothschild, J. H. Spencer, Ramsey Theory, 2nd edition, Wiley-Interscience, 1990.

[25] M. de Guzman, Real variable methods in Fourier Analysis, North-Holland, 1981.

[26] N. Katz, \underline{A counterexample for maximal operators over a Cantor set of directions}, Math. Research Letters 3(1996), 527-536.

[27] N. Katz, \underline{Remarks on maximal operators over arbitrary sets of directions}, to appear.

[28] N. Katz, to appear.

[29] U. Keich, to appear

[30] J. R. Kinney, \underline{A thin set of circles}, Amer. Math. Monthly 75 (1968), 1077-1081.

[31] L. Kolasa, T. Wolff, \underline{On some variants of the Kakeya problem}, Pac. J. Math., to appear.

[32] L. Kuipers, H. Niederreiter, Uniform Distribution of Sequences, Wiley-Interscience, 1974.

[33] J. M. Marstrand, \underline{Packing planes in ℝ^{3}}, Mathematika 26(1979), 180-183.

[34] J. M. Marstrand, \underline{Packing circles in the plane}, Proc. London Math. Soc. 55 (1987), 37-58.

[35] W. Minicozzi, C. Sogge, \underline{Negative results for Nikodym maximal functions} \underline{and related oscillatory integrals in curved space}, to appear.

[36] G. Mockenhoupt, A. Seeger, C. Sogge, \underline{Wave front sets and Bourgain’s circular} \underline{maximal theorem}, Ann. Math. 134 (1992), 207-218.

[37] H. L. Montgomery, Ten lectures on the interface between analytic number theory and harmonic analysis, CBMS Regional Conference Series in Mathematics, vol. 84, American Mathematical Society, 1994.

[38] A. Moyua, A. Vargas, L. Vega, \underline{Schrodinger maximal functions and restriction} \underline{properties of the Fourier transform}, International Math. Res. Notices no. 16 (1996), 793-815.

[39] D. M. Oberlin, E. M. Stein, \underline{Mapping properties of the Radon transform}, Indiana Univ. Math. J. 31(1982), 641-650.

[40] J. Pach, P. Agarwal, Combinatorial Geometry, Wiley-Interscience, 1995.

[41] H. Pecher, \underline{Nonlinear small data scattering for the wave and Klein-Gordon} \underline{equation}, Math. Z. 185 (1984), 261-270.

[42] E. Sawyer, \underline{Families of plane curves having translates in a set of measure zero}, Mathematika 34 (1987), 69-76.

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

[44] W. Schlag, \underline{A geometric proof of the circular maximal theorem}, Duke Math. J., to appear.

[45] W. Schlag, \underline{A geometric inequality with applications to the Kakeya problem in} \underline{three dimensions}, Geometric and Functional Analysis, to appear.

[46] W. Schlag, C. Sogge, \underline{Local smoothing estimates related to the circular maximal} \underline{theorem}, Math. Research Letters 4(1997), 1-15.

[47] M. Sharir, \underline{On joints in arrangements of lines in space}, J. Comb. Theory A 67(1994), 89-99.

[48] C. Sogge, \underline{Propagation of singularities and maximal functions in the plane}, Inv. Math. 104 (1991), 349-376.

[49] C. Sogge, \underline{Concerning Nikodym-type sets in 3-dimensional curved space}, to appear.

[50] E. M. Stein, \underline{On limits of sequences of operators}, Ann. Math. 74(1961), 140-170.

[51] E. M. Stein, \underline{Maximal functions: spherical means}, Proc. Nat. Acad. Sci. USA 73(1976), 2174-2175.

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

[53] E. M. Stein, G. L. Weiss, Introduction to Fourier analysis on Euclidean spaces, Princeton University Press, 1971.

[54] E. M. Stein, N. J. Weiss, \underline{On the convergence of Poisson integrals}, Trans. Amer. Math. Soc. 140(1969), 34-54.

[55] L. Szekely, \underline{Crossing numbers and hard Erdos problems in discrete geometry}, Comb. Prob. Comput. 6(1997), 353-358.

[56] E. Szemeredi, W. T. Trotter Jr., \underline{Extremal problems in discrete geometry}, Combinatorica 3(1983), 381-392.

[57] M. Talagrand, \underline{Sur la measure de la projection d’un compact et certaines familles} \underline{de cercles}, Bull. Sci. Math. (2) 104 (1980), 225-231.

[58] T. Tao, \underline{The Bochner-Riesz conjecture implies the restriction conjecture}, to appear.

[59] T. Tao, A. Vargas, L. Vega, \underline{A bilinear approach to the restriction and Kakeya} \underline{conjectures}, to appear.

[60] T. Wolff, \underline{An improved bound for Kakeya type maximal functions}, Revista Math. Iberoamericana 11 (1995), 651-674.

[61] T. Wolff, \underline{A Kakeya type problem for circles}, Amer. J. Math. 119(1997), 985-1026.

[62] T. Wolff, \underline{A mixed norm estimate for the x-ray transform}, to appear in Revista Math. Iberoamericana.