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]. Comparing the two last bounds 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 a 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]