Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 7 / 2 / Solution

A finite-field Kakeya set, also called a finite-field Besicovitch set, is a subset containing a complete affine line in a vector space $a+{\mathbb{F}}_{p}v$ in every nonzero direction $v$, with scalar multiples counted as the same direction. The line's translate may depend on the direction.

For odd $p$, take the union of the lines $y=mx-m^2/4$, $m\in {\mathbb{F}}_p$. Completing the square gives $x^2-y=(m/2-x{)}^2$. Thus that union is exactly $K_0=\{(x,y):x^2-y\text{ is a square, including zero}\}$. For each fixed $x$ there are $(p+1)/2$ such $y$, so $|K_0|=p(p+1)/2$. It contains every nonvertical slope. Add the vertical line $x=0$, whose overlap with $K_0$ has $(p+1)/2$ points. The tangent-line finite-field Kakeya construction consequently hasThe prime two is irrelevant to this asymptotic statement and can be handled by taking its whole plane.

For the high-dimensional lower bound, we give a direct polynomial method in combinatorics proof, which yields a stronger estimate. Suppose a finite-field Kakeya set $K\subseteq {\mathbb{F}}_p^n$ has fewer than $\left(\genfrac{}{}{0ex}{}{p+n-1}{n}\right)$ points. That binomial coefficient is the dimension of a bounded-total-degree polynomial space of polynomials of total degree at most $p-1$. Evaluation at the points of $K$ imposes fewer linear conditions than this dimension. By the rank-nullity theorem, there is a nonzero polynomial $P$ of total degree $d\le p-1$ vanishing on $K$.

For every nonzero $v$ choose the line $a_v+tv\subseteq K$. The polynomial $P(a_v+tv)$ in $t$ has degree at most $d<p$ and vanishes at all $p$ field elements, so it vanishes identically. Its coefficient of $t^d$ is the leading homogeneous polynomial part $P_d(v)$. Thus $P_d(v)=0$ for every nonzero $v$. The case $d=0$ is already impossible for a nonzero constant vanishing on a nonempty set; for $d>0$, the absence of a constant term in this homogeneous polynomial also gives $P_d(0)=0$.

A polynomial of degree less than $p$ in each variable cannot vanish at every point of ${\mathbb{F}}_p^n$ unless it is zero. To see this, induct on $n$: fix the first $n-1$ variables, apply the one-variable root bound in the last variable, then apply the induction hypothesis to each resulting coefficient polynomial. This forces $P_d=0$, contradicting the choice of the leading part. We have proved the finite-field Kakeya polynomial boundAt $n=15$ this implies the required bound with an explicit absolute constant:The argument is valid in every prime characteristic and does not invoke the lower bound as an unproved theorem.