Kakeya Sets over Finite Fields

This chapter uses the counting lemma (2.2), in both its plain and its multiplicity form; the Schwartz–Zippel lemma (2.6) and its multiplicity form (2.8); and the properties of Hasse derivatives along lines (Lemma 2.5). The bridge between counting and zeros is the restriction of a polynomial to the lines that a Kakeya set contains.

4.1 The problem

Kakeya (1917) asked for the least area of a planar region in which a unit segment can be rotated through a full turn; Besicovitch (1928) showed that the area can be made arbitrarily small, and indeed that there are sets of measure zero in $\mathbb R^n$ containing a unit segment in every direction. The Kakeya conjecture asserts that such sets nevertheless have Hausdorff dimension $n$. It is proved for $n=2$ and open for $n\ge3$, and it is connected to central questions in harmonic analysis and partial differential equations.

Wolff (1999) proposed a finite-field model of the problem.

Definition 4.1. A set $K\subseteq\mathbb F_q^n$ is a Kakeya set if it contains a line in every direction: for every $\mathbf b\in\mathbb F_q^n\setminus\{\mathbf 0\}$ there is $\mathbf a\in\mathbb F_q^n$ with $\{\mathbf a+t\mathbf b:t\in\mathbb F_q\}\subseteq K$.

Wolff conjectured that a Kakeya set has at least $c_nq^n$ points, with $c_n>0$ depending only on $n$, and this was proved by Dvir (2009) with $c_n=1/n!$ after a decade in which the best bounds had the form $q^{\gamma n}$ with $\gamma<1$ (Wolff 1999; Mockenhaupt and Tao 2004). The multiplicity refinement of Saraf and Sudan (2008) and Dvir, Kopparty, Saraf, and Sudan (2013) raised $c_n$ to $2^{-n}$ up to lower-order terms, which is within a factor of about $2$ of the best constructions.

4.2 Dvir's theorem

Theorem 4.2 (Dvir 2009). Every Kakeya set $K\subseteq\mathbb F_q^n$ satisfies

$$|K|\ge\binom{q+n-1}{n}\ge\frac{q^n}{n!}.$$

Proof. Suppose $|K|<\binom{q-1+n}{n}$. By Lemma 2.2(a) there is a nonzero polynomial $P\in\mathbb F_q[\mathbf x]$ of degree $d\le q-1$ vanishing on $K$. Since $K\ne\emptyset$ (it contains lines), $P$ is not a nonzero constant, so $d\ge1$. Let $P_d$ be the top homogeneous part of $P$.

Let $\mathbf b\ne\mathbf 0$ and choose $\mathbf a$ with the line $\{\mathbf a+t\mathbf b\}$ contained in $K$. The univariate polynomial $P(\mathbf a+t\mathbf b)$ has degree at most $d\le q-1$ and vanishes at all $q$ points $t\in\mathbb F_q$, so by Lemma 2.5(v) it is the zero polynomial. In particular its coefficient of $t^d$ vanishes, and by Lemma 2.5(vi) that coefficient is $P_d(\mathbf b)$. Thus $P_d(\mathbf b)=0$ for every $\mathbf b\ne\mathbf 0$; and $P_d(\mathbf 0)=0$ since $P_d$ is homogeneous of positive degree. So $P_d$ vanishes on all of $\mathbb F_q^n$.

But $P_d$ is a nonzero polynomial of degree $d\le q-1<q$, so by Lemma 2.6 it has at most $dq^{n-1}<q^n$ zeros in $\mathbb F_q^n$. This is a contradiction. The inequality $\binom{q+n-1}{n}=\frac{(q+n-1)\cdots q}{n!}\ge\frac{q^n}{n!}$ is clear. ∎

The argument uses only one line per direction and only the fact that a line has $q$ points; it does not use that the lines are in different directions except through the conclusion that $P_d$ vanishes everywhere. The same proof gives more.

Corollary 4.3 (Dvir 2009). Let $1\le k\le q$ and suppose $K\subseteq\mathbb F_q^n$ contains, for every direction $\mathbf b\ne\mathbf 0$, at least $k$ points of some line in direction $\mathbf b$. Then $|K|\ge\binom{k+n-1}{n}$.

Proof. If $|K|<\binom{k-1+n}{n}$, a nonzero $P$ of degree $d\le k-1$ vanishes on $K$, with $d\ge1$. For each $\mathbf b\ne\mathbf 0$ the restriction $P(\mathbf a+t\mathbf b)$ to the corresponding line has degree at most $d\le k-1$ and at least $k$ roots, so is zero, and $P_d(\mathbf b)=0$ as before. Then $P_d$ vanishes on $\mathbb F_q^n$ with degree $d\le k-1\le q-1$, contradicting Lemma 2.6. ∎

4.3 The method of multiplicities

Dvir's bound has the right order $q^n$ but the constant $1/n!$ is far from the truth. The loss occurs at one place: the polynomial is required to vanish at each point of $K$, which costs one linear condition per point, and the degree it can then be given is $d\approx(n!\,|K|)^{1/n}$; the argument then needs $d<q$. Suppose instead the polynomial is required to vanish to order $m$ at each point. This costs $\binom{m+n-1}{n}\approx m^n/n!$ conditions per point, so the degree becomes $d\approx(n!\,|K|)^{1/n}\,m$, apparently no better. But the restriction to a line now vanishes to order $m$ at each of $q$ points, so it is zero as soon as $d<mq$ rather than $d<q$. The two factors of $m$ cancel, the factor $n!$ remains, and nothing has been gained.

The gain comes from a second observation. If $P$ vanishes to order $m$ on $K$, then every Hasse derivative $P^{(\mathbf i)}$ with $|\mathbf i|<m$ vanishes to order $m-|\mathbf i|$ on $K$ (Lemma 2.5(iii)), and the same restriction argument applied to $P^{(\mathbf i)}$ shows that $(P_d)^{(\mathbf i)}$ vanishes on every direction, provided $d-|\mathbf i|<(m-|\mathbf i|)q$. Thus $P_d$ vanishes on all of $\mathbb F_q^n$ not merely to order $1$ but to order roughly $(mq-d)/(q-1)$, and the multiplicity Schwartz–Zippel lemma (2.8) then forces $d\gtrsim mq^2/(2q-1)$, rather than $d\ge q$. Since $\binom{d+n}{n}/\binom{m+n-1}{n}\to(d/m)^n$ as $m\to\infty$, the bound on $|K|$ becomes $(q^2/(2q-1))^n$, and the $n!$ has disappeared.

The following lemma packages the restriction argument.

Lemma 4.4. Let $K\subseteq\mathbb F_q^n$ be a Kakeya set, and let $0\ne P\in\mathbb F_q[\mathbf x]$ have degree $d$ and vanish to order at least $m$ at every point of $K$. Let $\mathbf i\in\mathbb N^n$ satisfy

$$d-|\mathbf i|<(m-|\mathbf i|)\,q.$$

Then $(P_d)^{(\mathbf i)}(\mathbf b)=0$ for every $\mathbf b\in\mathbb F_q^n\setminus\{\mathbf 0\}$.

Proof. If $|\mathbf i|\ge m$, the hypothesis gives $d-|\mathbf i|<0$, so by Lemma 2.5(ii) both $P^{(\mathbf i)}$ and $(P_d)^{(\mathbf i)}$ have negative degree, i.e. are zero, and there is nothing to prove. Assume $|\mathbf i|<m$. Fix $\mathbf b\ne\mathbf 0$ and $\mathbf a$ with $\{\mathbf a+t\mathbf b\}\subseteq K$. Let $R=P^{(\mathbf i)}$ and $Q(t)=R(\mathbf a+t\mathbf b)\in\mathbb F_q[t]$. By Lemma 2.5(ii), $\deg R\le d-|\mathbf i|$, so $\deg Q\le d-|\mathbf i|$. By Lemma 2.5(iii), $R$ vanishes to order at least $m-|\mathbf i|$ at every point of $K$, hence at every point $\mathbf a+t\mathbf b$, $t\in\mathbb F_q$; by Lemma 2.5(iv), $\operatorname{mult}(Q,t)\ge m-|\mathbf i|$ for every $t\in\mathbb F_q$. If $Q\ne0$, Lemma 2.5(v) gives $(m-|\mathbf i|)q\le\sum_t\operatorname{mult}(Q,t)\le\deg Q\le d-|\mathbf i|$, contrary to hypothesis. So $Q=0$, and in particular the coefficient of $t^{d-|\mathbf i|}$ in $Q$ is zero. By Lemma 2.5(vi) applied to $R$ with $e=d-|\mathbf i|$, that coefficient is $R_e(\mathbf b)$, where $R_e$ is the homogeneous part of $R$ of degree $e$; and by Lemma 2.5(ii), $R_e=(P_d)^{(\mathbf i)}$. ∎

4.4 The Dvir–Kopparty–Saraf–Sudan bound

Theorem 4.5 (Dvir, Kopparty, Saraf, and Sudan 2013). Every Kakeya set $K\subseteq\mathbb F_q^n$ satisfies

$$|K|\ge\Big(\frac{q^2}{2q-1}\Big)^n=\Big(\frac{q}{2-1/q}\Big)^n>\frac{q^n}{2^n}.$$

Proof. Fix an integer $m\ge1$ and let $d=d(m)$ be the largest integer with $d<\dfrac{mq^2}{2q-1}$, so that $d\ge\dfrac{mq^2}{2q-1}-1$. We claim

$$|K|\binom{m+n-1}{n}\ge\binom{d+n}{n}.\tag{4.1}$$

Suppose not. By Lemma 2.2(b) there is a nonzero $P$ of degree $d'\le d$ vanishing to order at least $m$ at every point of $K$. Note $d'\le d<mq^2/(2q-1)<mq$, so $mq-d'>0$; put

$$m'=\Big\lceil\frac{mq-d'}{q-1}\Big\rceil\ge1.$$

For every $\mathbf i$ with $|\mathbf i|\le m'-1$ we have $|\mathbf i|<\frac{mq-d'}{q-1}$, i.e. $|\mathbf i|(q-1)<mq-d'$, i.e. $d'-|\mathbf i|<(m-|\mathbf i|)q$. Lemma 4.4 (applied to $P$, of degree $d'$) therefore gives $(P_{d'})^{(\mathbf i)}(\mathbf b)=0$ for all $|\mathbf i|\le m'-1$ and all $\mathbf b\ne\mathbf 0$: the polynomial $P_{d'}$ vanishes to order at least $m'$ at every nonzero point of $\mathbb F_q^n$. At the origin, $P_{d'}$ is a nonzero homogeneous polynomial of degree $d'$, so $\operatorname{mult}(P_{d'},\mathbf 0)=d'$ exactly.

Apply Lemma 2.8 to $P_{d'}$ with $S=\mathbb F_q$:

$$m'(q^n-1)+d'\le\sum_{\mathbf x\in\mathbb F_q^n}\operatorname{mult}(P_{d'},\mathbf x)\le d'q^{n-1},$$

so $m'(q^n-1)\le d'(q^{n-1}-1)$. If $m'>d'$ this would give $q^n-1<q^{n-1}-1$, which is absurd; so $m'\le d'$, and then $m'q^n\le d'q^{n-1}+(m'-d')\le d'q^{n-1}$, i.e.

$$m'q\le d'.\tag{4.2}$$

Now $m'\ge\dfrac{mq-d'}{q-1}$, so (4.2) gives $q(mq-d')\le d'(q-1)$, i.e. $mq^2\le d'(2q-1)$, i.e. $d'\ge\dfrac{mq^2}{2q-1}$. This contradicts $d'\le d<\dfrac{mq^2}{2q-1}$, and proves (4.1).

From (4.1),

$$|K|\ge\frac{\binom{d+n}{n}}{\binom{m+n-1}{n}}=\prod_{j=1}^n\frac{d+j}{m+j-1}.$$

As $m\to\infty$ with $d=d(m)$, each factor tends to $q^2/(2q-1)$, because $d/m\to q^2/(2q-1)$. Since (4.1) holds for every $m$, $|K|$ is at least the limit, $(q^2/(2q-1))^n$. Finally $q^2/(2q-1)=q/(2-1/q)>q/2$. ∎

Remark 4.6. The proof gives slightly more than the limit: for every $m\ge1$, $|K|\ge\prod_{j=1}^n\frac{d(m)+j}{m+j-1}$, and one may take the maximum over $m$. For large $q$ and fixed $n$ the improvement is negligible.

Remark 4.7. The two ingredients that distinguish this proof from Dvir's are the passage from $P$ to its derivatives $P^{(\mathbf i)}$ in Lemma 4.4, which converts vanishing of $P$ on $K$ to high-order vanishing of $P_{d'}$ everywhere, and the multiplicity Schwartz–Zippel lemma, which converts high-order vanishing everywhere into a lower bound on the degree. Neither ingredient is specific to Kakeya sets; the first uses only that $K$ contains lines, the second only that $\mathbb F_q^n$ is a grid. Saraf and Sudan (2008) obtained the intermediate bound $q^n/2.6^n$ with the first ingredient alone, using the ordinary Schwartz–Zippel lemma for the derivatives; the second ingredient is what gives the clean constant.

The same argument applies to sets containing only a fraction of each line.

Corollary 4.8. Let $2\le k\le q$ and suppose $K\subseteq\mathbb F_q^n$ contains, for every $\mathbf b\ne\mathbf 0$, at least $k$ points of some line in direction $\mathbf b$. Then

$$|K|\ge\Big(\frac{kq}{k+q-1}\Big)^n.$$

Proof. Repeat the proof of Theorem 4.5 with $d$ the largest integer below $\dfrac{mkq}{k+q-1}$. In Lemma 4.4 the restriction $Q$ now has at least $k$ points of multiplicity $\ge m-|\mathbf i|$, so $Q=0$ whenever $d'-|\mathbf i|<(m-|\mathbf i|)k$, i.e. whenever $|\mathbf i|<\dfrac{mk-d'}{k-1}$, and $P_{d'}$ vanishes to order $m'=\lceil(mk-d')/(k-1)\rceil$ at every nonzero point. Inequality (4.2) is unchanged, since it comes from Lemma 2.8 over $\mathbb F_q^n$; combining $m'q\le d'$ with $m'\ge(mk-d')/(k-1)$ gives $q(mk-d')\le d'(k-1)$, i.e. $d'\ge\dfrac{mkq}{k+q-1}$, a contradiction. The limit $m\to\infty$ gives the bound. ∎

For $k=q$ this is Theorem 4.5; for $k=\delta q$ with $\delta$ fixed it gives $|K|\ge(\delta q/(1+\delta-1/q))^n$, which improves on Corollary 4.3's $\binom{\delta q+n-1}{n}\approx(\delta q)^n/n!$ for large $n$.

4.5 Small cases and the plane

How sharp are these bounds? The trivial upper bound is $|K|\le q^n$, and the union of one line per direction has at most $q\cdot\frac{q^n-1}{q-1}<2q^n$ points, so the question is the constant. Constructions of Kakeya sets of size $2^{-(n-1)}q^n+O(q^{n-1})$ for odd $q$ are known (Saraf and Sudan 2008; Dvir 2012, §4), so Theorem 4.5 is within a factor of $2+o(1)$ of the truth for fixed $n$ as $q\to\infty$. Whether the constant is $2^{-n}$ or $2^{-(n-1)}$ or something between is open for $n\ge3$.

In the plane the problem is solved. Blokhuis and Mazzocca (2008) proved that for odd $q$ the minimum size of a Kakeya set in $\mathbb F_q^2$ is exactly

$$\frac{q(q+1)}{2}+\frac{q-1}{2}=\frac{q^2+2q-1}{2},$$

attained by a construction based on a conic. Dvir's bound $\binom{q+1}{2}=q(q+1)/2$ is thus below the truth by exactly $(q-1)/2$, and is asymptotically sharp in the plane, whereas the multiplicity bound $q^4/(2q-1)^2\approx q^2/4$ is weaker there; the multiplicity method wins only in higher dimension, where the $n!$ matters. The following values were computed by exhaustive search over all choices of one line per direction (Appendix A):

One Kakeya set of size $17$ in $\mathbb F_5^2$ found by the search is the union of the six lines $y=0$, $y=x$, $y=2x+1$, $y=3x+2$, $y=4x+4$, and $x=0$; its points are $(0,0)$, $(0,1)$, $(0,2)$, $(0,3)$, $(0,4)$, $(1,0)$, $(1,1)$, $(1,3)$, $(2,0)$, $(2,2)$, $(2,3)$, $(3,0)$, $(3,1)$, $(3,2)$, $(3,3)$, $(4,0)$, and $(4,4)$, of which six lie on one of the lines, nine on two, and two, $(0,0)$ and $(4,4)$, on three. Chapter 7 solves the variant in which each of the $q+1$ lines may miss one point, and shows that Dvir's bound falls short of the truth by the same $(q-1)/2$ there.

In three dimensions the comparison reverses for moderate $q$. Dvir gives $\binom{q+2}{3}\approx q^3/6$; DKSS gives $q^6/(2q-1)^3\approx q^3/8$; and for $n=5$ DKSS overtakes Dvir already at $q=5$ ($165$ against $126$). For $q=101$ and $n=5$ the two bounds are $9.66\times10^7$ and $3.37\times10^8$ against $q^n\approx1.05\times10^{10}$; the constructions give about $2^{-4}q^5\approx6.6\times10^8$. The exact minimum is unknown in every case with $n\ge3$.