## The Kakeya problem

The original Kakeya needle problem  is to  find the least amount of area required to continuously rotate a unit line segment in the (Euclidean) plane by a full rotation. Of course in a circle of diameter one we can continuously rotate a unit line segment by 360 degrees, but there are figures with smaller area than that (for example an equilateral triangle of height 1). In fact, perhaps surprisingly, it was shown by Besicovitch in 1928 that for any $\epsilon > 0$ there exists a planar set of area $\epsilon$ which solves the Kakeya needle problem. Any set which contains a unit segment in each direction is now called a Besicovitch set or a Kakeya set. Now the main open problem in real spaces is,

Do Kakeya sets in $\mathbb{R}^n$ have Hausdorff dimension equal to $n$?.

Since I don’t know enough analysis or topology to elaborate too much on that, I would stick to providing a link to some expositions on this problem and its connection to various areas of mathematics, see this and this. What I do know is combinatorics and linear algebra. And luckily there is an interesting variant of this problem over  finite fields.

In 1999 Wolff suggested a variation of this problem which asks for the smallest subset of $\mathbb F_q^n$ that contains a line in each direction, where $\mathbb F_q$ is the finite field of order $q$ (see this).  He conjectured that the size of the smallest set is bounded below by $c_nq^n$ where $c_n$ is constant that only depends on $n$.

This conjecture was finally settled by Zeev Dvir in 2008 (see [2]) as he showed that any Kakeya set in $\mathbb F_q^n$ has size at least ${q + n - 1 \choose n}$ (which is greater than or equal to $q^n/n!$ by a simple reasoning). What’s really interesting is that this problem remained unsolved even after a lot of effort by several prominent mathematicians, and ultimately the proof of Dvir turned out to be surprisingly elementary. Quoting Terence Tao [3]: “Results from basic algebraic geometry had been brought to bear on the finite field Kakeya conjecture in [74], but with only partial success. It was thus a great surprise when the conjecture was fully resolved by Dvir”

I will discuss this beautiful proof here. First, we would need this result on polynomial interpolation.

Lemma 1 Let $F$ be a field, let $n \geq 1$ be an integer, and $d \geq 0$. If $E \subseteq F^n$ has cardinality less than $\binom{d + n}{n}$ then there exists a non-zero polynomial $P \in F[x_1, \ldots, x_n]$ of degree at most $d$ such that $E \subseteq Z(P)[F]$, where $Z(P)[F]$ is the set of zeroes of $P$ in $F^n$.

Before proving this, let’s look at some applications which are well known results in geometry (take $n = 2$):

1. Every pair of points in $F^2$ is contained in a line.

2. Every set of five points in $F^2$ is contained in a (possibly degenerate) conic section.

Note that a line in $F^2$ is determined by a polynomial of degree $1$ in $F[x_1, \ldots, x_2]$, while a conic section is determined by a polynomial of degree $2$.

Proof . The polynomials with degree at most $d$ form a $\binom{d+n}{n}$ dimensional subspace $F_d[x_1, \ldots, x_n]$ of the infinite dimensional vector space $F[x_1, \ldots, x_n]$ (see this for a complete reasoning). Now look at the evaluation map from $F_d[x_1, \ldots, x_n]$ to $F^E$ for any given set $E \subseteq F^n$, which maps a polynomial $P$ to the tuple $(P(x))_{x \in E}$. Since the vector space $F^E$ has dimension $|E|$ , if $|E| < {d + n \choose n} = dim(F_d[x_1, \ldots, x_n])$ then the evaluation map has a non-trivial kernel, which means that there is a non-zero polynomial $P \in F_d[x_1, \ldots, x_n]$ that vanishes on all points of $E$.

Now the main result.

Theorem Let $F$ be a finite field of order $q$, let $n \geq 1$ be an integer, and let $E \subseteq F^n$ be a Kakeya set. Then $|E| \geq {q + n - 1 \choose n}$. In particular, we have $|E| \geq q^n/n!$.

Proof. Say $|E| < {q + n - 1 \choose n}$. By Lemma 1 there exists a non-zero polynomial $P \in F[x_1, \ldots, x_n]$ of degree $d$ at most $q-1$ which vanishes on $E$. For every direction $v \in F^n \setminus \{0\}$ there exists a line $L_v = \{x + tv : t \in F\}$ which is completely contained in $E$, i.e. the univariate polynomial $P(x + tv)$ vanishes for all $t$. Since degree of $P(x + tv)$ is less than $q$ but it has $q$ zeroes, it must be the zero polynomial.

If $P_{=d}$ is the homogeneous part of degree $d \leq q-1$ in $P$ then the argument above shows that $P_{=d}(v)$, which is the coefficient of $t^d$ in $P(x + tv)$, is zero for all $v \in F^n \setminus \{0\}$. This contradicts Lemma 1 in this post (or the Schwartz-Zippel lemma).

Note the similarity between this and the first proof of Schwartz-Zippel lemma discussed here. In fact Moshkovitz was inspired by Dvir’s proof to come up with that proof.

It should also be noted that this bound is not always sharp. For example, Blokhuis and Mazzocca showed in [1] that the exact bound for $n = 2$ and $q$ odd is $q(q+1)/2 + (q-1)/2$. Interestingly they also showed a weaker bound of $q^{n-1}/(n-1)!$ for general $n$. Later on Dvir, Kopparty, Saraf and Sudan improved the bound in general case to $q^n/2^n$ using polynomial multiplicities, something I will discuss in another blog post.

The proof of finite field Kakeya conjecture (now a theorem) can also be seen projectively by homogenization of the polynomial. But,

there is no known proof of this which doesn’t use the polynomial method.

I would end this with an interesting remark by Terence Tao on the proof by Dvir (see footnote at page 8 in [3]):

To illustrate the radical change in perspective that the polynomial method brought to this subject, it had previously been observed in that a Kakeya set could not be contained in the zero set of a low degree polynomial, by essentially the same argument as the one given above. However, this fact was deemed “far from a proof that the Kakeya conjecture is true”, due to ignorance of the polynomial method.

References
[1] Aart Blokhuis and Francesco Mazzocca. The finite field kakeya problem. In Building Bridges, pages 205–218, 2008. Available at http://link.springer.com/chapter/10.1007%2F978-3-540-85221-6_6
[2] Zeev Dvir. On the size of kakeya sets in finite fields. J. Amer. Math. Soc., 22:1093–1097, 2009. Available at http://www.ams.org/journals/jams/2009-22-04/S0894-0347-08-00607-3/
[3] Terence Tao. Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory. EMS Surv. Math. Sci., pages 1–46, 2014. Available at http://arxiv.org/abs/1310.6482.

Algebraic methods in discrete analogs of the Kakeya problem by Guth and Katz.
– Extensions to the method of multiplicities, with applications to Kakeya sets and mergers, by Dvir, Kopparty, Saraf and Sudan.
– The Kakeya set and maximal conjectures for algebraic varieties over finite fields by Jordan Ellenberg, Richard Oberlin and Terence Tao.
– Kakeya sets over non-archimedian lcoal rings
– Variants of the Kakeya problem over an algebraically closed field by Kaloyan Slavov.
A finite version of the Kakeya problem by Simeon Ball, Aart Blokhuis and Diego Domenzain.

* this post is a part of notes on the polynomial method that I am (was?) working on with Abhishek Khetan and Aditya Potukuchi