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 derive essentially the same conclusion using the "bush" argument, as follows. Let [math]\displaystyle{ E\subset{\mathbb F}_3^n }[/math] be a Kakeya set, considered as a union of [math]\displaystyle{ N := (3^n-1)/2 }[/math] lines in all different directions. Let [math]\displaystyle{ \mu }[/math] be the largest number of lines that are concurrent at a point of [math]\displaystyle{ E }[/math]. The number of point-line incidences is at most [math]\displaystyle{ |E|\mu }[/math] and at least [math]\displaystyle{ 3N }[/math], whence [math]\displaystyle{ |E|\ge 3N/\mu }[/math]. On the other hand, by considering only those points on the "bush" of lines emanating from a point with multiplicity [math]\displaystyle{ \mu }[/math], we see that [math]\displaystyle{ |E|\ge 2\mu+1 }[/math]. Minimizing [math]\displaystyle{ \max\{3N/\mu, 2\mu+1\} }[/math] over all possible values of [math]\displaystyle{ \mu }[/math] one obtains [math]\displaystyle{ |E|\gtrsim\sqrt{6N} \approx 3^{(n+1)/2} }[/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\subset{\mathbb F}_3^n }[/math]. Form a bipartite graph [math]\displaystyle{ G }[/math] with the partite sets [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] through [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]. Thus,

[math]\displaystyle{ k_n \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 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]