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 there exists a planar set of area 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 have Hausdorff dimension equal to ?.
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 that contains a line in each direction, where is the finite field of order (see this). He conjectured that the size of the smallest set is bounded below by where is constant that only depends on .
This conjecture was finally settled by Zeev Dvir in 2008 (see ) as he showed that any Kakeya set in has size at least (which is greater than or equal to 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 : “Results from basic algebraic geometry had been brought to bear on the finite field Kakeya conjecture in , 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 be a field, let be an integer, and . If has cardinality less than then there exists a non-zero polynomial of degree at most such that , where is the set of zeroes of in .
Before proving this, let’s look at some applications which are well known results in geometry (take ):
Every pair of points in is contained in a line.
Every set of five points in is contained in a (possibly degenerate) conic section.
Note that a line in is determined by a polynomial of degree in , while a conic section is determined by a polynomial of degree .
Proof . The polynomials with degree at most form a dimensional subspace of the infinite dimensional vector space (see this for a complete reasoning). Now look at the evaluation map from to for any given set , which maps a polynomial to the tuple . Since the vector space has dimension , if then the evaluation map has a non-trivial kernel, which means that there is a non-zero polynomial that vanishes on all points of .
Now the main result.
Theorem Let be a finite field of order , let be an integer, and let be a Kakeya set. Then . In particular, we have .
Proof. Say . By Lemma 1 there exists a non-zero polynomial of degree at most which vanishes on . For every direction there exists a line which is completely contained in , i.e. the univariate polynomial vanishes for all . Since degree of is less than but it has zeroes, it must be the zero polynomial.
If is the homogeneous part of degree in then the argument above shows that , which is the coefficient of in , is zero for all . 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  that the exact bound for and odd is . Interestingly they also showed a weaker bound of for general . Later on Dvir, Kopparty, Saraf and Sudan improved the bound in general case to 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 ):
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.
 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
 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/
 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.