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, 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\cdot(3^n-1)/2$, and hence

$k_n\gtrsim 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|$.

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$. 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\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}$.

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.

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, we seem to have

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

or

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