35 The finite Kakeya problem

Let $F$ be a finite field.

Lemma 35.1

Every nonzero polynomial $p (x) \in F [x_{1}, \dots, x_{n}]$ of degree $d$ has at most $d q^{n - 1}$ roots in $F^{n}$ .

Proof ▶

We use induction on $n$ , with fact (1) above as the starting case $n = 1$ . Let us split $p (x)$ into summands according to the powers of $x_{n}$ ,

p (x) = g_{0} + g_{1} x_{n} + g_{2} x_{n}^{2} + \dots + g_{ℓ} x_{n}^{ℓ},

where $g_{i} \in F [x_{1}, \dots, x_{n - 1}]$ for $0 \leq i \leq ℓ \leq d$ , and $g_{ℓ}$ is nonzero. We write every $v \in F^{n}$ in the form $v = (a, b)$ with $a \in F^{n - 1}$ , $b \in F$ , and estimate the number of roots $p (a, b) = 0$ .

Case 1. Roots $(a, b)$ with $g_{ℓ} (a) = 0$ . Since $g_{ℓ} \neq 0$ and $\deg g_{ℓ} \leq d - ℓ$ , by induction the polynomial $g_{ℓ}$ has at most $(d - ℓ) q^{n - 2}$ roots in $F^{n - 1}$ , and for each $a$ there are at most $q$ different choices for $b$ , which gives at most $(d - ℓ) q^{n - 1}$ such roots for $p (x)$ in $F^{n}$ .

Case 2. Roots $(a, b)$ with $g_{ℓ} (a) \neq 0$ . Here $p (a, x_{n}) \in F [x_{n}]$ is not the zero polynomial in the single variable $x_{n}$ , it has degree $ℓ$ , and hence for each $a$ by (1) there are at most $ℓ$ elements $b$ with $p (a, b) = 0$ . Since the number of $a$ ’s is at most $q^{n - 1}$ we get at most $ℓ q^{n - 1}$ roots for $p (x)$ in this way.

Summing the two cases gives at most

(d - ℓ) q^{n - 1} + ℓ q^{n - 1} = d q^{n - 1}

roots for $p (x)$ , as asserted.

Lemma 35.2

For every set $E \subseteq F^{n}$ of size $| E | < (\binom{n + d}{d})$ there is a nonzero polynomial $p (x) \in F [x_{1}, \dots, x_{n}]$ of degree at most $d$ that vanishes on $E$ .

Proof ▶

Consider the vector space $V_{d}$ of all polynomials in $F [x_{1}, \dots, x_{n}]$ of degree at most $d$ . A basis for $V_{d}$ is provided by the monomials $x_{1}^{s_{1}} \dots x_{n}^{s_{n}}$ with $\sum s_{i} \leq d$ :

1, x_{1}, \dots, x_{n}, x_{1}^{2}, x_{1} x_{2}, \dots, x_{1}^{3}, \dots, x_{n}^{d} .

The following pleasing argument shows that the number of monomials $x_{1}^{s_{1}} \dots x_{n}^{s_{n}}$ of degree at most $d$ equals the binomial coefficient $(\binom{n + d}{d})$ . What we want to count is the number of $n$ -tuples $(s_{1}, \dots, s_{n})$ of nonnegative integers with $s_{1} + \dots + s_{n} \leq d$ . To do this, we map every $n$ -tuple $(s_{1}, \dots, s_{n})$ to the increasing sequence

s_{1} + 1 < s_{1} + s_{2} + 2 < \dots < s_{1} + \dots + s_{n} + n,

which determines an $n$ -subset of ${1, 2, \dots, d + n}$ . The map is bijective, so the number of monomials is $(\binom{n + d}{d})$ .

Next look at the vector space $F^{E}$ of all functions $f : E \to F$ ; it has dimension $| E |$ , which by assumption is less than $(\binom{n + d}{d}) = \dim V_{d}$ . The evaluation map $p (x) \mapsto (p (a))_{a \in E}$ from $V_{d}$ to $F^{E}$ is a linear map of vector spaces. We conclude that it has a nonzero kernel, containing as desired a nonzero polynomial that vanishes on $E$ .

Theorem 35.3 finite Kakeya problem

Let $K \subseteq F^{n}$ be a Kakeya set. Then

| K | \geq (\binom{| F | + n - 1}{n}) \geq \frac{| F |^{n}}{n!} .

Proof ▶

The second inequality is clear from the definition of binomial coefficients. For the first, set again $q = | F |$ and suppose for a contradiction that

| K | < (\binom{q + n - 1}{n}) = (\binom{n + q - 1}{q - 1}) .

By Lemma 35.2 there exists a nonzero polynomial $p (x) \in F [x_{1}, \dots, x_{n}]$ of degree $d \leq q - 1$ that vanishes on $K$ . Let us write

\begin{matrix} (1) & p (x) = p_{0} (x) + p_{1} (x) + \dots + p_{d} (x), \end{matrix}

where $p_{i} (x)$ is the sum of the monomials of degree $i$ ; in particular, $p_{d} (x)$ is nonzero. Since $p (x)$ vanishes on the nonempty set $K$ , we have $d > 0$ . Take any $v \in F^{n} ∖ {0}$ . By the Kakeya property for this $v$ there exists a $w \in F^{n}$ such that

p (w + t v) = 0 for all t \in F .

Here comes the trick: Consider $p (w + t v)$ as a polynomial in the single variable $t$ . It has degree at most $d \leq q - 1$ but vanishes on all $q$ points of $F$ , whence $p (w + t v)$ is the zero polynomial in $t$ . Looking at (1) above we see that the coefficient of $t^{d}$ in $p (w + t v)$ is precisely $p_{d} (v)$ , which must therefore be 0. But $v \in F^{n} ∖ {0}$ was arbitrary and $p_{d} (0) = 0$ since $d > 0$ , and we conclude that $p_{d} (x)$ vanishes on all of $F^{n}$ . Since

d q^{n - 1} \leq (q - 1) q^{n - 1} < q^{n},

Lemma 35.1, however, tells us that $p_{d} (x)$ must then be the zero polynomial — contradiction and end of the proof. □