Kakeya problem

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

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

General lower bounds

Trivially,

[math]\displaystyle{ k_n\le k_{n+1}\le 3k_n }[/math].

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

[math]\displaystyle{ k_{n+m} \leq k_m k_n }[/math];

this implies that [math]\displaystyle{ k_n^{1/n} }[/math] converges to a limit as [math]\displaystyle{ n }[/math] goes to infinity.

From a paper of Dvir, Kopparty, Saraf, and Sudan it follows that [math]\displaystyle{ k_n \geq 3^n / 2^n }[/math], but this is superseded by the estimates given below.

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

[math]\displaystyle{ k_n\gtrsim 3^{(n+1)/2}. }[/math]

One can get essentially the same conclusion using the "bush" argument. There are [math]\displaystyle{ N := (3^n-1)/2 }[/math] different directions. Take a line in every direction, let E be the union of these lines, and let [math]\displaystyle{ \mu }[/math] 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 [math]\displaystyle{ 3N/\mu }[/math]. On the other hand, by considering the "bush" of lines emanating from a point with multiplicity [math]\displaystyle{ \mu }[/math], we see that E has cardinality at least [math]\displaystyle{ 2\mu+1 }[/math]. If we minimise [math]\displaystyle{ \max(3N/\mu, 2\mu+1) }[/math] over all possible values of [math]\displaystyle{ \mu }[/math] one obtains approximately [math]\displaystyle{ \sqrt{6N} \approx 3^{(n+1)/2} }[/math] as a lower bound of [math]\displaystyle{ |E| }[/math].

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

General upper bounds

We have

[math]\displaystyle{ k_n\le 2^{n+1}-1 }[/math]

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

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

Putting all this together, we seem to have

[math]\displaystyle{ (3^{6/11} + o(1))^n \le k_n \le ( (27/4)^{1/3} + o(1))^n }[/math]

or

[math]\displaystyle{ (1.8207\ldots+o(1))^n \le k_n \le (1.88988+o(1))^n. }[/math]