Kakeya problem

Define a Kakeya set to be a subset A of [math]\displaystyle{ [3]^n \equiv ({\Bbb Z}/3{\Bbb Z})^n }[/math] that contains an algebraic line in every direction. Thus, for every [math]\displaystyle{ r \in ({\Bbb Z}/3{\Bbb Z})^n }[/math], there exists [math]\displaystyle{ a \in ({\Bbb Z}/3{\Bbb Z})^n }[/math] such that a, a+r, a+2r all lie in A. Let [math]\displaystyle{ k_n }[/math] be the smallest size of a Kakeya set in n dimensions.

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 26 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]

As to the general estimates, we have

[math]\displaystyle{ k_r(k_r-1)\ge 3(3^r-1) }[/math]

and, on the other hand,

[math]\displaystyle{ k_r\le 2^{r+1}-1 }[/math]:

the former 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 d, the latter due to the fact that the set of all vectors in [math]\displaystyle{ {\mathbb F}_3^r }[/math] such that at least one of the numbers 1 and 2 is missing among their coordinates is a Kakeya set. (I actually can improve the lower bound to something like [math]\displaystyle{ k_r\gg 3^{0.51r} }[/math].) Also, we have the trivial inequalities

[math]\displaystyle{ k_r\le k_{r+1}\le 3k_r }[/math];

can the upper bound be strengthened to [math]\displaystyle{ k_{r+1}\le 2k_r+1 }[/math]?

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

The Cartesian product of two Kakeya sets is another Kakeya set; this implies that [math]\displaystyle{ k_{r+s} \leq k_r k_s }[/math].