# Kakeya problem

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

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$?