\documentstyle[amssymb,amsfonts,12pt,psfig]{article} % need psfig
\input MathMacro.tex 
\newcommand{\eqn}[1]{(\ref{#1})}
\newcommand{\is}{$I^{s}\;$}
\newcommand{\mbf}[1]{\mbox{\boldmath ${#1}$}}
\newcommand{\bc}{\begin{center}}
\newcommand{\ec}{  \end{center}}
\newcommand{\page}{\vfil \break}
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{  \end{itemize}}
\newcommand{\benum}{\begin{enumerate}}
\newcommand{\eenum}{  \end{enumerate}}
\newcommand{\bd}{\begin{description}}
\newcommand{\ed}{  \end{description}}
\def\rp{{r^\prime}}
\def\rpt{{\tilde r^\prime}}
\def\rtil{{\tilde r}}
\def\qtil{{\tilde q}}
\def\kp{{k^\prime}}
\def\kt{{\tilde{k}}}
\def\qp{{q^\prime}}
\def\pp{{p^\prime}}
\def\qpt{{\tilde q^\prime}}
\def\R{{\hbox{\bf R}}}
\def\C{{\hbox{\bf C}}}
\def\rn{{\R^n}}
\def\Z{{\hbox{\bf Z}}}
\def\dimsup{{\overline{\rm dim}}}
\def\eps{{\varepsilon}}
\def\implies{{\Rightarrow}}
\def\RR{{\frak R}}
\def\emph#1{{\it #1}}
% \newcommand{\lesssim}{\mbox{$\,\stackrel{\textstyle{<}}{\sim}\,$}}

\renewcommand {\theequation}{\thesection.\arabic{equation}}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{remark}{Remark}[section]

\begin{document}
\Large
\vskip 1in
\bc
{\bf \LARGE  Recent progress on the Kakeya conjecture}

\bigskip

\bigskip

\bigskip

\bigskip

Nets Katz (University of Washington St. Louis)\\

\bigskip

Terence Tao (UCLA)\\

\bigskip

\ 

\bigskip
{\tt www.math.ucla.edu/$\sim$tao/preprints } (in preparation)
\ec

\page

\noindent
What is the Kakeya conjecture?

\bi

\item The Kakeya conjecture comes in three levels of strength.  From weakest to strongest, they are: the Minkowski Kakeya set conjecture, the Hausdorff Kakeya set conjecture, and the Kakeya maximal conjecture.

\item Let $n \geq 2$.  A \emph{Besicovitch set} is defined as a subset of $\R^n$ which contains a unit line segment in every direction.  These sets can have measure zero (Besicovitch, 1918).

\item The \emph{Kakeya set conjecture} states that all Besicovitch sets have dimension $n$.  

\item There are two versions of the Kakeya set conjecture, depending on whether one uses the Minkowski or Hausdorff dimension.

\item To formulate the maximal conjecture we need to discretize.  Let $0 < \delta \ll 1$, and let $\Omega$ be a maximal $\delta$-separated set of directions on the sphere $S^{n-1}$.  For each $\omega \in \Omega$, let $T_\omega$ be a $\delta \times 1$ tube in the direction $\omega$ in the ball.

\item The \emph{Kakeya maximal conjecture} states that
$$ \| \sum_{\omega \in \Omega} \chi_{T_\omega} \|_{p'} \leq C_{\eps,p} \delta^{1-\frac{n}{p}+\eps}$$
holds for all $p \leq n$ and $\eps > 0$.  The right-hand side is easily seen to be sharp (take all the $T_\omega$ passing through a point).  The conjecture is trivial when $p=1$; the difficulty is to make $p$ large.  It is easy to show that if the Kakeya maximal conjecture is true for some $p$, then Besicovitch sets must have Minkowski and Hausdorff dimension at least $p$.

\item These conjectures have application to various problems in harmonic analysis, number theory, and PDE, but we will not discuss these here.

\ei

\page

Equivalent formulations

\bi

\item These three conjectures can be phrased in terms of counting overlap of partial subsets of tubes.

\item Let $\delta$, $\Omega$, $T_\omega$ be as before.  Let $0 < \lambda \leq 1$, and for each $T_{\omega}$ let $\tilde T_\omega$ be a subset of $T_\omega$ of volume $\lambda |T_\omega|$.  Let $1 \leq p \leq n$.

\item The statement that Besicovitch sets have Minkowski dimension at least $p$ is equivalent to the estimate
$$ | \bigcup_{\omega \in \Omega} \tilde T_\omega| \geq c_{p,\eps} \delta^{n-p+\eps}$$
for all $\eps > 0$ and $\lambda = 1$ (so that $\tilde T_\omega = T_\omega$).

\item The corresponding statement for the Hausdorff dimension is roughly equivalent to
$$ | \bigcup_{\omega \in \Omega} \tilde T_\omega| \geq c_{p,\eps} \delta^{n-p+\eps}$$
for all $\eps > 0$ and $\lambda = \log(1/\delta)^{-c})$ for some small absolute constant $c>0$.

\item The Kakeya maximal conjecture at dimension $p$ is equivalent to
$$| \bigcup_{\omega \in \Omega} \tilde T_\omega | \geq c_{\eps,p} 
\lambda^p \delta^{n-p+\eps}$$
for all $\eps > 0$ and $0 < \lambda \leq 1$.

\ei

\page

\psfig{figure=kakeya-types.eps,height=5in,width=6in}

\page

Progress on Kakeya as of 1991:

\bi

\item  The Minkowski and Hausdorff Kakeya set conjectures were proven in two dimensions by Davies, and in higher dimensions the lower bound of $(n+1)/2$ was obtained by Drury.

\item  The maximal conjecture were proven in two dimensions by Fefferman, C\'ordoba, and Str\"omberg, and in higher dimensions the conjectures were proven at $(n+1)/2$ by Christ, Duandikotxea, and Rubio de Francia.

\item For the two-dimensional arguments the key observation is that two tubes widely separated in angle can only intersect in a small ball.  For the $(n+1)/2$ arguments the key observation is that two small balls widely separated in distance can only have one tube through them.

\item In 1991 Bourgain showed that one could improve $(n+1)/2$ to $(n+1)/2 + \eps_n$ for the Minkowski Kakeya set, Hausdorff Kakeya set, and maximal conjectures.

\ei

\page

Progress on Kakeya as of early 2000:

\bi

\item In 1995 Wolff improved the exponent $(n+1)/2$ to $(n+2)/2$ for the Minkowski Kakeya set, Hausdorff Kakeya set, and maximal conjectures.  The main observation was that given any two intersecting tubes, the set of tubes that intersect both of them in different places essentially lie in a 2-plane, and so one can then use 2-dimensional arguments to extract a small gain.

\item In 1998 Bourgain gave a very different-looking argument, based on the combinatorics of sums and differences, which gave an exponent of $(13n+12)/25$ for the Minkowski and Hausdorff dimensions, and an exponent of $(1/2 + \eps)n$ for the maximal conjecture.  The first two results improve upon Wolff's arguments in 27 and higher dimensions.

\item By combining Bourgain's argument with some rescaling arguments, we were able to improve Wolff's bound of 5/2 in three dimensions to $5/2 + 10^{-10}$ for the Minkowski dimension only (Katz, Laba, T., 1999).  One can similarly improve $(n+2)/2$ to $(n+2)/2 + \eps_n$ for the Minkowski dimension in all dimensions (Laba, T., 2000)

\item Also, by improving Bourgain's arguments one can replace $(13n+12)/25$ by
$(6n+5)/11$ for the Hausdorff dimension, and $(4n+3)/7$ for the Minkowski dimension (Katz, T., 1999).

\ei

\page

Best exponents as of early 2000:

\bi

\item Minkowski, $3 \leq n \leq 8$: $(n+2)/2 + 10^{-10}$
\item Minkowski, $n > 8$: $(4n+3)/7$
\item Hausdorff, $3 \leq n \leq 12$: $(n+2)/2$
\item Hausdorff, $n > 12$: $(6n+5)/11$.
\item Maximal, $n \leq C$: $(n+2)/2$
\item Maximal, $n > C$: $(1/2 + \eps)n$

\ei

\page

In the last few months we have found some ideas which lead to the following improvements as of June 2000:

\bi

\item Minkowski, $3 \leq n \leq 4$: $(n+2)/2 + 10^{-10}$
\item Minkowski, $5 \leq n \leq 8$: $(4n+5)/7$
\item Minkowski, $9 \leq n \leq 28$: $(17n+17)/29$
\item Minkowski, $29 \leq n \leq 54$: $(10n+9)/17$
\item Minkowski, $n > 54$: $\frac{62}{59+\sqrt{2117}}(n-1) + 1$
\item Hausdorff, $3 \leq n \leq 6$: $(n+2)/2$
\item Hausdorff, $n > 6$: $(2-\sqrt{2})(n-1) + 1$.
\item Maximal, $3 \leq n \leq 8$: $(n+2)/2$
\item Maximal, $n > 8$: $(4n+3)/7$.
\ei

This is still a work in progress.

\page

Slicing

\bi

\item Much of the recent progress on the Kakeya problem has come by using a slicing technique of Bourgain's to reduce matters to an arithmetic problem.

\item Suppose we are interested in the Minkowski problem, i.e. that of finding lower bounds for the measure of the set
$$ E = \bigcup_{\omega \in \Omega} T_\omega.$$
Assume that $E$ has measure approximately $\delta^{n-p}$.  We then seek lower bounds on $p$.

\item We may assume that the directions $\omega$ are within $1/10$ of the vertical direction $e_n$.  We may normalize the tubes to have the form
$$ T_\omega := \{ (\underline{x}, x_n) \in \R^{n-1} \times \R: 0 \leq x_n \leq 1; \underline{x} = x_\omega + v_\omega x_n + O(\delta) \}$$
where $x_\omega \in \R^{n-1}$ and $(1,v_\omega)$ is parallel to $\omega$.

\item Now consider three slices in arithmetic progression, such as
$$ A' := \{ (\underline{x}, x_n) \in E: x_n = 0 \}$$
$$ B' := \{ (\underline{x}, x_n) \in E: x_n = 1 \}$$
$$ C' := \{ (\underline{x}, x_n) \in E: x_n = 1/2 \}.$$

\item Generically we expect $A'$, $B'$, $C'$ to have measure $\delta^{n-p}$.  (One can always arrange this to be true by a random rescaling).  This basically means that $A'$, $B'$, $C'$ are the union of about $\delta^{1-p}$ finitely overlapping $\delta$-disks.  Let $A$, $B$, $C$ be the centers of these disks; thus $A$, $B$, $C$ are $\delta$-separated sets of cardinality about $N:= \delta^{1-p}$.

\item Each tube $T_\omega$ intersects $A$, $B$, $C$ in a point.  In particular, each $T_\omega$ is associated to a point in $A \times B$.  Because the tubes point in different directions, each tube corresponds to a different point in $A \times B$.  Let $G$ be the collection of all such points; this is a subset of $A \times B$ of cardinality about $\delta^{1-n}$.

\psfig{figure=slices.eps,height=5in,width=6in}

\item Since $A$ and $B$ have cardinality $N$, we thus have a trivial bound of
$\# G \leq N^2$.  This leads to the classical lower bound of $(n+1)/2$ for the Minkowski dimension.

\item Because the tubes all point in different directions, we see that the map
$$ -: (a,b) \mapsto a-b$$
is one-to-one on $G$.  So $-$ has large range (about $\delta^{1-n}$) on $G$.

\item On the other hand, for every $(a,b) \in G$, the midpoint of $a,b$ essentially lies in $C$.  So the map
$$ +: (a,b) \mapsto a+b$$
has range at most $N$ in $G$.

\item It is well known in combinatorics that the size of a sum-set is somewhat related to the size of a difference set, in that if one is large, then the other must be, and conversely.  The connection comes from such arithmetic identities as
$$ a+b = c+d \iff a-d = c-b.$$
Thus collisions between sums imply collisions between differences.  Since the sum set of $G$ is very small, one therefore expects some non-trivial bound on the difference set.  

\item In 1998 Bourgain used some combinatorial ideas from the work of Gowers on arithmetic progressions of length four to show that $G$ is in fact bounded by $N^{2 - 1/13}$, improving upon the trivial bound of $N^2$.  This translates to a bound $p \geq (13n + 12)/25$.

\item In 1999 Nets Katz and I improved this bound to $N^{2-1/6}$, which corresponds to $p \geq (6n + 5)/11$.

\item These techniques also apply to the Hausdorff problem.  In this situation one does not have the full tubes $T_\omega$ to work with, but only a subset $\tilde T_\omega$ of density about $\log(1/\delta)^{-c}$.  In principle, this could cause difficulty when trying to choose three good slices in arithmetic progression.  However, there are results of Heath-Brown and Szemer\'edi which show that any subset of $\{1, \ldots, N\}$ of density at least $\log(N)^{-c}$ contains a non-trivial arithmetic progression of length three.

\ei

\page

More slices!

\bi

\item One could of course use more than three slices in the above argument.  For instance, one could introduce the slice 
$$ D' := \{ (\underline{x}, x_n) \in E: x_n = 2/3 \}$$
which is the union of about $N$ $\delta$-disks.  Let $D$ be the set of those centers.  Using $D$, one sees that the map
$$ +_2: (a,b): \mapsto a+2b$$
also has small range, about $N$ in fact.  In fact, one can use as many slices as desired to show that essentially all arithmetic maps other than - have small range.

\item In 1999 Nets and I showed that if $A$, $B$ have cardinality $N$, the map $-$ is one-to-one on $G$, and $+$, $+_2$ have range at most $N$ on $G$, then $\# G \leq N^{2 - 1/4}$.  This corresponds to a bound of $(4n+3)/7$ on the Minkowski dimension.  It does not directly give a bound on the Hausdorff dimension because it is unknown whether a density of $\log(N)^{-c}$ guarantees a non-trivial subset affinely equivalent to $\{0, 1/2, 2/3, 1\}$.

\item The argument is as follows.  Define a \emph{trapezoid} to be four points $x,y,z,w$ in $G$ such that $x,y$ have the same $A$-projection, $y,z$ have the same $B$-projection, $z,w$ have the same $A$-projection, and $w,x$ have the same $D$-projection.  

\psfig{figure=trapezoid.eps,height=5in,width=6in}

\item This trapezoid is determined by four elements of $G$, but there are four constraints between these elements.  One can use this to bound the number of such trapezoids from below by $(\# G)^4/N^4$.  (One can prove this rigorously by two applications of the Cauchy-Schwarz inequality).

\item On the other hand, this trapezoid is determined by the $C$-projections of $x,y$ and the $B$-projection of $w$.  If one fixes these three projections, then there is ostensibly still one degree of freedom - but this freedom moves $z$ in the direction of constant -.  Since - is one-to-one on $G$, the claim follows.  In particular, the number of trapezoids is bounded above by $N^3$.

\psfig{figure=move_slices.eps,height=5in,width=6in}

\item Putting the two bounds together we obtain the desired bound $\# G \leq N^{2 - 1/4}$.

\ei

\page

Eliminating slices

\bi

\item The above $(4n+3)/7$ argument also works in a slice-free setting.

\item Let $E = \bigcup_{\omega \in \Omega} T_\omega$.  If $E$ has measure $\delta^{n-p}$, then $E$ is the union of about $\delta^{-p}$ $\delta$-balls.

\item Define a \emph{quadrilateral} to be four tubes $T_1$, $T_2$, $T_3$, $T_4$ in $E$ such that $T_i$ intersects $T_{i+1}$ in a $\delta$-ball for $i=1,2,3,4$ (with $T_5 := T_1$).  The total number of 4-tuples of tubes is $\delta^{4(1-n)}$, but there are four constraints, and so the total number of quadrilaterals is bounded below by $\delta^{4(1-n)} / \delta^{-4p}$.  (Again, this can be proven by Cauchy-Schwarz).  Let $x_i$ be the center of the ball where $T_i$ and $T_{i+1}$ intersect.

\item A quadrilateral is mostly determined by the three points (which are usually in $E$):
$$  \frac{1}{2} x_1 + \frac{1}{2} x_2, 2x_2 - x_3, \frac{2}{3} x_3 + \frac{1}{3} x_4.$$
Given these three points, one can determine $x_1 - x_4$ as a linear combination.  This determines the tube $T_4$, because the tubes point in different directions.  Thus $x_4$ (for instance) has only one degree of freedom, and once this degree is specified one can reconstruct the entire quadrilateral.  Thus the number of quadrilaterals is bounded by $\delta^{-3p} \delta^{-1}$.

\psfig{figure=quad.eps,height=5in,width=6in}

\item Combining these bounds gives the same bound $(4n+3)/7$ as previously.

\item This argument is more robust than the slice argument as one has less of a need to seek arithmetic progressions.  One can modify it so as to make it work for the Hausdorff and maximal function problems.

\ei

\page

Two-dimensional theory

\bi

\item One can use the two-dimensional theory of Fefferman, C\'ordoba, and Str\"omberg to improve the $(4n+3)/7$ to $(4n+5)/7$, similar to how Wolff improved $(n+1)/2$ to $(n+2)/2$.

\item The idea is as follows.  In each two-dimensional plane, the Kakeya conjecture is true, which means that the tubes in a plane essentially have bounded overlap.

\item As a consequence of this, we have the following: given a tube, and a point not on that tube, there essentially exists a bounded number of tubes which are intersect both.  (This improves on the trivial bound of $\delta^{-1}$).

\item Inserting this into the above argument at appropriate places one obtains the $(4n+5)/7$ improvement for the Minkowski dimension (and quite possibly for the Hausdorff and maximal function problems).  This matches Wolff's $(n+2)/2$ result in four dimensions, and is new for $n \geq 5$.

\ei

\page

Iteration

\bi

\item The above methods give bounds of roughly $4n/7$ for large $n$.  (The distinction between using slices or not using slices is only relevant in small dimension).  This can be improved by iteration methods.  We sketch the basic idea as follows.

\item Recall that in the slice formulation, we have sets $A, B$ of cardinality $N$ and a subset $G \subset A \times B$ such that $-$ is one-to-one, and all other arithmetic projections ($+$, $+_2$, etc.) have range about $N$.

\item We now pass to a subset of $G$.  Let $L$ denote the affine transformation
$$ L(a,b) := (2a+\nu, b-a-\nu)$$
where $\nu$ is an arbitrary parameter.  Note that $L(a,b)$ has the same value of $+$ as $(a,b)$.

\item Let $G'$ denote the set 
$$ G' := \{ (a,b) \in G: L(a,b) \in G\}.$$
For most values of $\nu$, $G'$ is empty.  However, there are several values of $\nu$ where $G'$ is fairly large, because $+$ has small range on $G$.

\item Also, arithmetic projections $(a,b) \mapsto a$, $(a,b) \mapsto b$, $(a,b) \mapsto a+2b$, etc. (but not $+: (a,b) \mapsto a+b$!) tend to have very small range on $G'$ (much smaller than $N$).  The reason is that $G'$ is already a bit smaller than $G$, and many elements in $G'$ have the same projection.  For instance, in the following figure, the elements $(a,b)$ and $(a',b')$ are in $G'$ and have the same $B$-projection.  Because there are many trapezoids in $G$, this configuration occurs fairly often. 

\psfig{figure=iterate.eps,height=5in,width=6in}

\item Thus $G'$ is like a miniature version of $G$: most of its arithmetic projections are small, and $-$ is still one-to-one on $G'$.  One can then apply an existing estimate (such as the $N^{2-1/4}$ estimate proven earlier) to $G'$, which eventually leads to a new estimate on $G$.

\item One can iterate this indefinitely; however this approach converges to the estimate $\# G \leq N^{1 + \sqrt{2}/2} = N^{1.707\ldots}$, which is a slight improvement over $N^{2-1/4} = N^{1.75}$.

\item This technique is reasonably robust, and applies to the Hausdorff as well as the Minkowski dimensions.  (It may also apply to the maximal function problem).

\ei

\page

Trapezopipeds

\bi

\item A further improvement to $N^{2 - 3/10} = N^{1.7}$ can be obtained by replacing the trapezoids with a variant which we call ``trapezopipeds''.  Basically, a trapezopiped is a set of 8 points in $G \subset A \times B$ which looks like this:

\psfig{figure=trapezopiped.eps,height=6in,width=5in}

\item Since the slopes are fixed, there are basically five degrees of freedom for a trapezopiped (two for a corner, and then three for the sides).  So it would appear that one could have as many as $N^5$ trapezopipeds.

\item However, there can be at most $N^3$.  The reason is that three carefully chosen projections will determine the $-$ of the far corner $x$, which (by the one-to-one-ness of $-$) will determine that far corner $x$, which by some further linear algebra will determine the $-$ of the opposite corner $y$, which (again using the one-to-one-ness of $-$) determines the opposite corner $y$, and this is enough to determine everything.

\item A naive lower bound of the number of trapezopipeds (using the fact that there are 8 elements of $G$ and 11 independent constraints) gives $(\# G)^8 / N^{11}$, but this only recovers the existing $N^{2-1/4}$ bound.  However, one can use ideas similar to the iteration ideas to improve this to $(\# G)^{10} / N^{14}$, and this gives the improved $N^{2-3/10}$ result.

\item There seem to be other ways to combine these ideas; we have yet not exhausted them all.  By combining all the above ideas together, the best bound on $\# G$ that we can currently obtain (as of June 2000) is $N^{\frac{59 + \sqrt{2117}}{62}} = N^{1.6937\ldots}$.

\ei

\end{document}
