# Difference between revisions of "Kakeya problem"

A Kakeya set in ${\mathbb F}_3^n$ is a subset $E\subset{\mathbb F}_3^n$ that contains an algebraic line in every direction; that is, for every $d\in{\mathbb F}_3^n$, there exists $e\in{\mathbb F}_3^n$ such that $e,e+d,e+2d$ all lie in $E$. Let $k_n$ be the smallest size of a Kakeya set in ${\mathbb F}_3^n$.

Clearly, we have $k_1=3$, and it is easy to see that $k_2=7$. Using a computer, it is not difficult to find that $k_3=13$ and $k_4\le 27$. Indeed, it seems likely that $k_4=27$ holds, meaning that in ${\mathbb F}_3^4$ one cannot get away with just $26$ elements.

## Basic Estimates

Trivially, we have

$k_n\le k_{n+1}\le 3k_n$.

Since the Cartesian product of two Kakeya sets is another Kakeya set, the upper bound can be extended to

$k_{n+m} \leq k_m k_n$;

this implies that $k_n^{1/n}$ converges to a limit as $n$ goes to infinity.

## Lower Bounds

From a paper of Dvir, Kopparty, Saraf, and Sudan it follows that $k_n\ge (3/2)^n$, but this is superseded by the estimates given below.

To each of the $(3^n-1)/2$ directions in ${\mathbb F}_3^n$ there correspond at least three pairs of elements in a Kakeya set, determining this direction. Therefore, $\binom{k_n}{2}\ge 3\cdot(3^n-1)/2$, and hence

$k_n\ge 3^{(n+1)/2}.$

One can derive essentially the same conclusion using the "bush" argument, as follows. Let $E\subset{\mathbb F}_3^n$ be a Kakeya set, considered as a union of $N := (3^n-1)/2$ lines in all different directions. Let $\mu$ be the largest number of lines that are concurrent at a point of $E$. The number of point-line incidences is at most $|E|\mu$ and at least $3N$, whence $|E|\ge 3N/\mu$. On the other hand, by considering only those points on the "bush" of lines emanating from a point with multiplicity $\mu$, we see that $|E|\ge 2\mu+1$. Comparing the two last bounds one obtains $|E|\gtrsim\sqrt{6N} \approx 3^{(n+1)/2}$.

A better bound follows by using the "slices argument". Let $A,B,C\subset{\mathbb F}_3^{n-1}$ be the three slices of a Kakeya set $E\subset{\mathbb F}_3^n$. Form a bipartite graph $G$ with the partite sets $A$ and $B$ by connecting $a$ and $b$ by an edge if there is a line in $E$ through $a$ and $b$. The restricted sumset $\{a+b\colon (a,b)\in G\}$ is contained in the set $-C$, while the difference set $\{a-b\colon (a,b)\in G\}$ is all of ${\mathbb F}_3^{n-1}$. Using an estimate from a paper of Katz-Tao, we conclude that $3^{n-1}\le\max(|A|,|B|,|C|)^{11/6}$, leading to $|E|\ge 3^{6(n-1)/11}$. Thus,

$k_n \ge 3^{6(n-1)/11}.$

## Upper Bounds

We have

$k_n\le 2^{n+1}-1$

since the set of all vectors in ${\mathbb F}_3^n$ such that at least one of the numbers $1$ and $2$ is missing among their coordinates is a Kakeya set.

This estimate can be improved using an idea due to Ruzsa (seems to be unpublished). Namely, let $E:=A\cup B$, where $A$ is the set of all those vectors with $r/3+O(\sqrt r)$ coordinates equal to $1$ and the rest equal to $0$, and $B$ is the set of all those vectors with $2r/3+O(\sqrt r)$ coordinates equal to $2$ and the rest equal to $0$. Then $E$, being of size just about $(27/4)^{r/3}$ (which is not difficult to verify using Stirling's formula), contains lines in a positive proportion of directions: for, a typical direction $d\in {\mathbb F}_3^n$ can be represented as $d=d_1+2d_2$ with $d_1,d_2\in A$, and then $d_1,d_1+d,d_1+2d\in E$. Now one can use the random rotations trick to get the rest of the directions in $E$ (losing a polynomial factor in $n$).

Putting all this together, we seem to have

$(3^{6/11} + o(1))^n \le k_n \le ( (27/4)^{1/3} + o(1))^n$

or

$(1.8207+o(1))^n \le k_n \le (1.8899+o(1))^n.$