Kakeya problem over finite fields

Remarks

This is Dvir's theorem, which answered the finite field analogue of the Kakeya problem asked by Thomas Wolff. The proof uses the polynomial method. If $\abs{K} < \binom{q + n - 1}{n}$, the number of monomials of degree at most $q - 1$ in $n$ variables, then some nonzero polynomial $P$ of degree $d \le q - 1$ vanishes on $K$. Let $P_d$ be the top-degree homogeneous part of $P$. Restricting $P$ to a line $y + t x$ inside $K$ gives a polynomial in $t$ of degree at most $d < q$ with $q$ roots, so it is zero. Its coefficient of $t^d$ is $P_d(x)$, so $P_d(x) = 0$. So $P_d$ vanishes on all of $\F_q^n$, which is impossible for a nonzero polynomial of degree less than $q$ in each variable.

For $n = 1$ the bound gives $\abs{K} \ge q$, and indeed $K$ must be the whole line $\F_q$. For $n = 2$ it gives $\abs{K} \ge q(q + 1)/2$.

Going deeper

For a student

Dvir's proof is a few lines long and made the polynomial method a standard tool in combinatorics. The idea is that a set too small cannot avoid being the zero set of a low-degree polynomial, while lines in all directions force the polynomial to vanish identically. The constant $1/n!$ has since been improved, but the order $q^n$ is optimal. The finite field result does not solve the Euclidean Kakeya conjecture, whose difficulty comes from the multiscale structure of $\R^n$.