# Difference between revisions of "Kakeya problem"

Define a Kakeya set to be a subset $A$ of $^n\equiv{\mathbb F}_3^n$ that contains an algebraic line in every direction; that is, for every $d\in{\mathbb F}_3^n$, there exists $a\in{\mathbb F}_3^n$ such that $a,a+d,a+2d$ all lie in $A$. 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.

## General lower bounds

Trivially,

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

Since the Cartesian product of two Kakeya sets is another Kakeya set, we have

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

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

From a paper of Dvir, Kopparty, Saraf, and Sudan it follows that $k_n \geq 3^n / 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, etermining this direction. Therefore, $\binom{k_n}2\ge 3(3^n-1)/2\ltmath\gt, and hence :\ltmath\gtk_n\gtsym \sqrt{3^{(n+1)/2}}$

One can get essentially the same conclusion using the "bush" argument. There are $N := (3^n-1)/2$ different directions. Take a line in every direction, let E be the union of these lines, and let $\mu$ be the maximum multiplicity of these lines (i.e. the largest number of lines that are concurrent at a point). On the one hand, from double counting we see that E has cardinality at least $3N/\mu$. On the other hand, by considering the "bush" of lines emanating from a point with multiplicity $\mu$, we see that E has cardinality at least $2\mu+1$. If we minimise $\max(3N/\mu, 2\mu+1)$ over all possible values of $\mu$ one obtains approximately $\sqrt{6N} \approx 3^{(n+1)/2}$ as a lower bound of |E|, which is asymptotically better than $(3/2)^n$.

Or, we can use the "slices" argument. Let $A, B, C \subset ({\Bbb Z}/3{\Bbb Z})^{n-1}$ be the three slices of a Kakeya set E. We can form a graph G between A and B by connecting A and B by an edge if there is a line in E joining A and B. The restricted sumset $\{a+b: (a,b) \in G \}$ is essentially C, while the difference set $\{a-b: (a-b) \in G \}$ is all of $({\Bbb Z}/3{\Bbb Z})^{n-1}$. Using an estimate from this paper of Katz-Tao, we conclude that $3^{n-1} \leq \max(|A|,|B|,|C|)^{11/6}$, leading to the bound $|E| \geq 3^{6(n-1)/11}$, which is asymptotically better still.

## General 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.

Question: can the upper bound be strengthened to $k_{n+1}\le 2k_n+1$?

Another construction uses the "slices" idea and a construction of Imre Ruzsa. Let $A, B \subset ^n$ be the set of strings with $n/3+O(\sqrt{n})$ 1's, $2n/3+O(\sqrt{n})$ 0's, and no 2's; let $C \subset ^n$ be the set of strings with $2n/3+O(\sqrt{n})$ 2's, $n/3+O(\sqrt{n})$ 0's, and no 1's, and let $E = \{0\} \times A \cup \{1\} \times B \cup \{2\} \times C$. From Stirling's formula we have $|E| = (27/4 + o(1))^{n/3}$. Now I claim that for most $t \in ^{n-1}$, there exists an algebraic line in the direction (1,t). Indeed, typically t will have $n/3+O(\sqrt{n})$ 0s, $n/3+O(\sqrt{n})$ 1s, and $n/3+O(\sqrt{n})$ 2s, thus $t = e + 2f$ where e and f are strings with $n/3 + O(\sqrt{n})$ 1s and no 2s, with the 1-sets of e and f being disjoint. One then checks that the line $(0,f), (1,e), (2,2e+2f)$ lies in E.

This is already a positive fraction of directions in E. 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, I think we have

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

or

$(1.8207\ldots+o(1))^n \leq k_n \leq (1.88988+o(1))^n$