Kakeya problem

Define a Kakeya set to be a subset [math]\displaystyle{ A }[/math] of [math]\displaystyle{ [3]^n\equiv{\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, I also found [math]\displaystyle{ k_3=13 }[/math] and [math]\displaystyle{ k_4\le 27 }[/math]. I suspect that, indeed, [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), and I am very curious to know whether [math]\displaystyle{ k_5=53 }[/math]: notice the pattern in

[math]\displaystyle{ 3,7,13,27,53,\ldots }[/math]

we have the trivial inequalities

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

The Cartesian product of two Kakeya sets is another Kakeya set; this implies that [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 n goes to infinity.

General lower bounds

Dvir, Kopparty, Saraf, and Sudan showed that [math]\displaystyle{ k_n \geq 3^n / 2^n }[/math].

We have

[math]\displaystyle{ k_n(k_n-1)\ge 3(3^n-1) }[/math]

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

For instance, we can use 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 |E|, which is asymptotically better than [math]\displaystyle{ (3/2)^n }[/math].

Or, we can use the "slices" argument. Let [math]\displaystyle{ A, B, C \subset ({\Bbb Z}/3{\Bbb Z})^{n-1} }[/math] 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 [math]\displaystyle{ \{a+b: (a,b) \in G \} }[/math] is essentially C, while the difference set [math]\displaystyle{ \{a-b: (a-b) \in G \} }[/math] is all of [math]\displaystyle{ ({\Bbb Z}/3{\Bbb Z})^{n-1} }[/math]. Using an estimate from this paper of Katz-Tao, we conclude that [math]\displaystyle{ 3^{n-1} \leq \max(|A|,|B|,|C|)^{11/6} }[/math], leading to the bound [math]\displaystyle{ |E| \geq 3^{6(n-1)/11} }[/math], which is asymptotically better still.

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.

Question: can the upper bound be strengthened to [math]\displaystyle{ k_{n+1}\le 2k_n+1 }[/math]?

Another construction uses the "slices" idea and a construction of Imre Ruzsa. Let [math]\displaystyle{ A, B \subset [3]^n }[/math] be the set of strings with [math]\displaystyle{ n/3+O(\sqrt{n}) }[/math] 1's, [math]\displaystyle{ 2n/3+O(\sqrt{n}) }[/math] 0's, and no 2's; let [math]\displaystyle{ C \subset [3]^n }[/math] be the set of strings with [math]\displaystyle{ 2n/3+O(\sqrt{n}) }[/math] 2's, [math]\displaystyle{ n/3+O(\sqrt{n}) }[/math] 0's, and no 1's, and let [math]\displaystyle{ E = \{0\} \times A \cup \{1\} \times B \cup \{2\} \times C }[/math]. From Stirling's formula we have [math]\displaystyle{ |E| = (27/4 + o(1))^{n/3} }[/math]. Now I claim that for most [math]\displaystyle{ t \in [3]^{n-1} }[/math], there exists an algebraic line in the direction (1,t). Indeed, typically t will have [math]\displaystyle{ n/3+O(\sqrt{n}) }[/math] 0s, [math]\displaystyle{ n/3+O(\sqrt{n}) }[/math] 1s, and [math]\displaystyle{ n/3+O(\sqrt{n}) }[/math] 2s, thus [math]\displaystyle{ t = e + 2f }[/math] where e and f are strings with [math]\displaystyle{ n/3 + O(\sqrt{n}) }[/math] 1s and no 2s, with the 1-sets of e and f being disjoint. One then checks that the line [math]\displaystyle{ (0,f), (1,e), (2,2e+2f) }[/math] 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

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

or

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