# Kakeya problem

Define a Kakeya set to be a subset $A$ of $^r\equiv{\mathbb F}_3^r$ that contains an algebraic line in every direction; that is, for every $d\in{\mathbb F}_3^r$, there exists $a\in{\mathbb F}_3^r$ such that $a,a+d,a+2d$ all lie in $A$. Let $k_r$ be the smallest size of a Kakeya set in ${\mathbb F}_3^r$.

Clearly, we have $k_1=3$, and it is easy to see that $k_2=7$. Using a computer, I also found $k_3=13$ and $k_4\le 27$. I suspect that, indeed, $k_4=27$ holds (meaning that in ${\mathbb F}_3^4$ one cannot get away with just $26$ elements), and I am very curious to know whether $k_5=53$: notice the pattern in

$3,7,13,27,53,\ldots$

As to the general estimates, we have

$k_r(k_r-1)\ge 3(3^r-1)$

and, on the other hand,

$k_r\le 2^{r+1}-1$:

the former since for each $d\in {\mathbb F}_3^r\setminus\{0\}$ 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 ${\mathbb F}_3^r$ 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 $k_r\gg 3^{0.51r}$.) Also, we have the trivial inequalities

$k_r\le k_{r+1}\le 3k_r$;

can the upper bound be strengthened to $k_{r+1}\le 2k_r+1$?

Dvir, Kopparty, Saraf, and Sudan showed that $k_r \geq 3^r / 2^r$.

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