The Finite Field Kakeya problem

Kakeya Set

A set $K\subset {\mathbb{F}}_q^n$ is called a Kakeya set if it contains a line in every direction. In other words, for every vector $a\in {\mathbb{F}}_q^n\setminus \{0\}$, there is a vector $b$ so that the line $\{at+b\mid t\in {\mathbb{F}}_q\}$ is contained in $K$.

The Finite Field Kakeya problem

A Kakeya set $K\subset {\mathbb{F}}_q^n$ has at least $c_n{q}^n$ elements, for $c_n=(10n{)}^{-n}$.

Proof Suppose that $K\subset {\mathbb{F}}_q^n$ is a Kakeya set with $|K|<(10n{)}^{-n}{q}^n$. By the parameter counting argument, there is a non-zero polynomial $P$ that vanishes on $K$ with $\text{Deg }P\le n|K{|}^{1/n}<q$. We write $P$ as a sum of two pieces — the terms of highest degree plus the terms of lower degree. If $D$ is the degree of $P$, then we have $P=P_D+Q$, where $P_D$ is homogeneous of degree $D$ and $\text{Deg }Q<D$, and where $P_D$ is non-zero. Let $a$ be any non-zero vector in ${\mathbb{F}}_q^n$. Choose $b$ so that the line $\{at+b\mid t\in {\mathbb{F}}_q\}$ is contained in $K$. Consider the polynomial in one variable $R(t):=P(at+b)$. The polynomial $R$ vanishes for each $t\in {\mathbb{F}}_q$. It has degree $\le D<q$. By the vanishing lemma, $R$ is the zero polynomial. In other words, every coefficient of $R$ is zero. But the coefficient of $t^D$ in $R$ is exactly $P_D(a)$. So we see that $P_D(a)$ vanishes for all $a\in {\mathbb{F}}_q^n\setminus \{0\}$! Since $P_D$ is homogeneous of degree $D\ge 1$, $P_D$ also vanishes at $0$, and so $P_D$ vanishes at every point of ${\mathbb{F}}_q^n$. Since $D<q$, Lemma 2.10 implies that $P_D$ is the zero polynomial. This gives a contradiction. $\square$

Remark

Every line in ${\mathbb{F}}^n$ can be extended to a projective line in $\mathbb{P}{\mathbb{F}}^n$ by adding one point at infinity. If $a\ne 0$, then the line $\{at+b\mid t\in \mathbb{F}\}$ in ${\mathbb{F}}^n$ extends to include the point at infinity in the equivalence class $(a,0)$. Similarly, if $P\in {\text{Poly}}_D({\mathbb{F}}^n)$, then the zero set of $P$, $Z(P)\subset {\mathbb{F}}^n$, can be naturally extended to $\mathbb{P}{\mathbb{F}}^n$ as follows: if $0\ne a\in {\mathbb{F}}_q^n$, then the point at infinity $(a,0)$ lies in $Z(P)$ if and only if $P_D(a)=0$. In the proof of finite field Kakeya, we showed that if a line $l\subset {\mathbb{F}}^n$ lies in the zero set of a polynomial $P$ of degree $<q$, then the point of $l$ at infinity also lies in $Z(P)$. We can think of this as a version of the vanishing lemma in projective space.

Finite field Kakeya without polynomials

Proposition

Suppose $s\le q$. If $l_1,\cdots ,l_s$ are lines in ${\mathbb{F}}_q^n$, then their union has cardinality at least $(1/2)qs$. In particular, if $K\subset {\mathbb{F}}_q^n$ is a Kakeya set, then $|K|\ge (1/2)q^2.$

Bush method

If $l_1,\cdots ,l_M$ are lines in ${\mathbb{F}}_q^n$, then the number of points in their union is at least $(1/2)q{M}^{\frac{1}{2}}$. If $K\subset {\mathbb{F}}_q^n$ is a Kakeya set, then $|K|\ge (1/2)q^{\frac{n+1}{2}}.$

Hairbrush method

Suppose that $l_1,\cdots ,l_M$ are lines in ${\mathbb{F}}_q^n$, and suppose that at most $q+1$ of the lines lie in any plane. Then their union has cardinality at least $(1/3)q^{3/2}{M}^{1/2}$. If $K\subset {\mathbb{F}}_q^n$ is a Kakeya set, then $|K|\ge (1/2)q^{\frac{n+2}{2}}.$

Remark

Compared to bush method, we get better bound by hairbrush method as we take the restriction of having at most $q+1$ lines in any plane into consideration. Instead of considering lines through a point(which the bound comes from geometric property independent of property of Kskeya set), we consider planes through a line.