# Difference between revisions of "Kakeya problem"

Jump to: navigation, search

Define a Kakeya set to be a subset $A$ of $[3]^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, I also found $k_3=13$ and $k_4\le 27$. I suspect that, indeed, $k_4=27$ holds (meaning that in ${\mathbb F}_3^4$ one cannot get away with just $26$ elements), and I am very curious to know whether $k_5=53$: notice the pattern in

$3,7,13,27,53,\ldots$

we have the trivial inequalities

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

The Cartesian product of two Kakeya sets is another Kakeya set; this implies that $k_{n+m} \leq k_m k_n$. This implies that $k_n^{1/n}$ converges to a limit as n goes to infinity.

## General lower bounds

Dvir, Kopparty, Saraf, and Sudan showed that $k_n \geq 3^n / 2^n$.

We have

$k_n(k_n-1)\ge 3(3^n-1)$

since for each $d\in {\mathbb F}_3^r\setminus\{0\}$ there are at least three ordered pairs of elements of a Kakeya set with difference $d$. (I actually can improve the lower bound to something like $k_r\gg 3^{0.51r}$.)

For instance, we can use 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 [3]^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 [3]^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 [3]^{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$