One of my favourite unsolved problems in mathematics is the Kakeya conjecture in geometric measure theory. This conjecture is descended from the

Kakeya needle problem. (1917) What is the least area in the plane required to continuously rotate a needle of unit length and zero thickness around completely (i.e. by 360^\circ)?

For instance, one can rotate a unit needle inside a unit disk, which has area \pi/4. By using a deltoid one requires only \pi/8 area.

In 1928, Besicovitch showed that that in fact one could rotate a unit needle using an arbitrarily small amount of positive area. This unintuitive fact was a corollary of two observations. The first, which is easy, is that one can translate a needle using arbitrarily small area, by sliding the needle along the direction it points in for a long distance (which costs zero area), turning it slightly (costing a small amount of area), sliding back, and then undoing the turn. The second fact, which is less obvious, can be phrased as follows. Define a Kakeya set in {\Bbb R}^2 to be any set which contains a unit line segment in each direction. (See this Java applet of mine, or the wikipedia page, for some pictures of such sets.)

Theorem. (Besicovitch, 1919) There exists Kakeya sets {\Bbb R}^2 of arbitrarily small area (or more precisely, Lebesgue measure).

In fact, one can construct such sets with zero Lebesgue measure. On the other hand, it was shown by Davies that even though these sets had zero area, they were still necessarily two-dimensional (in the sense of either Hausdorff dimension or Minkowski dimension). This led to an analogous conjecture in higher dimensions:

Kakeya conjecture. A Besicovitch set in {\Bbb R}^n (i.e. a subset of {\Bbb R}^n that contains a unit line segment in every direction) has Minkowski and Hausdorff dimension equal to n.

This conjecture remains open in dimensions three and higher (and gets more difficult as the dimension increases), although many partial results are known. For instance, when n=3, it is known that Besicovitch sets have Hausdorff dimension at least 5/2 and (upper) Minkowski dimension at least 5/2 + 10^{-10}. See my Notices article for a general survey of this problem (and its connections with Fourier analysis, additive combinatorics, and PDE), my paper with Katz for a more technical survey, and Wolff’s survey for a systematic treatment of the field (up to about 1998 or so).

In 1999, Wolff proposed a simpler finite field analogue of the Kakeya conjecture as a model problem that avoided all the technical issues involving Minkowski and Hausdorff dimension. If F^n is a vector space over a finite field F, define a Kakeya set to be a subset of F^n which contains a line in every direction.

Finite field Kakeya conjecture. Let E \subset F^n be a Kakeya set. Then E has cardinality at least c_n |F|^n, where c_n > 0 depends only on n.

This conjecture has had a significant influence in the subject, in particular inspiring work on the sum-product phenomenon in finite fields, which has since proven to have many applications in number theory and computer science. Modulo minor technicalities, the progress on the finite field Kakeya conjecture was, until very recently, essentially the same as that of the original “Euclidean” Kakeya conjecture.

Last week, the finite field Kakeya conjecture was proven using a beautifully simple argument by Zeev Dvir, using the polynomial method in algebraic extremal combinatorics. The proof is so short that I can present it in full here.

The polynomial method is used to control the size of various sets E by looking at one or more polynomials P which vanish on that set E. This philosophy of course closely resembles that of algebraic geometry, and indeed one could classify the polynomial method as a kind of “combinatorial algebraic geometry”. An important difference, though, is that in the combinatorial setting we work over fields that are definitely not algebraically closed; in particular, we are primarily interested in polynomials and their zero sets over finite fields. [Also, whereas algebraic geometry is more concerned with specific (and often highly structured) polynomials, the polynomial method requires that one consider rather generic (and usually quite high degree) polynomials.]

For instance, in high school we learn the following connection between one-dimensional sets E, and polynomials P(x) of one variable:

Factor theorem. Let F be a field, and d \geq 1 be an integer. Let F[x] denote the polynomials in one variable with coefficients in F.

  1. If P \in F[x] is a non-zero polynomial of degree at most d, then the set \{x \in F: P(x) = 0 \} has cardinality at most d.
  2. Conversely, given any set E \subset F of cardinality at most d, there exists a non-zero polynomial P \in F[x] of degree at most d that vanishes on E.

Thus, to obtain an upper bound on the size of a one-dimensional set E, it would suffice to exhibit a non-zero low-degree polynomial that vanishes on E; conversely, to lower bound the size of E, one would have to show that the only low-degree polynomial that vanishes on E is the zero polynomial. It is the latter type of observation which is of relevance to the finite field Kakeya problem.

There are analogues of both 1. and 2. above in higher dimensions. For instance, the Schwartz-Zippel lemma is a higher-dimensional analogue of 1, as is the combinatorial nullstellensatz of Alon, while Stepanov’s method exploits a higher-dimensional analogue of 2. (Bézout’s theorem from algebraic geometry also qualifies as a variant of 1.) These sorts of techniques and results are collectively referred to as the polynomial method in extremal algebraic combinatorics. For Dvir’s argument, we will need a very simple higher-dimensional version of 2. that comes from basic linear algebra, namely

Lemma. Let E \subset F^n be a set of cardinality less than \binom{n+d}{n} for some d \geq 0. Then there exists a non-zero polynomial P \in F[x_1,\ldots,x_n] on n variables of degree at most d which vanishes on E.

Proof. Let V be the vector space of polynomials in F[x_1,\ldots,x_n] of degree at most d. Elementary combinatorics reveals that V has dimension \binom{n+d}{n}. On the other hand, the vector space F^E of F-valued functions on E has dimension |E| < \binom{n+d}{d}. Hence the evaluation map P \mapsto (P(x))_{x \in E} from V to F^E is non-injective, and the claim follows. \Box

Dvir’s argument combines this lemma with

Proposition. Let P \in F[x_1,\ldots,x_n] be a polynomial of degree at most |F|-1 which vanishes on a Kakeya set E. Then P is identically zero.

Proof. Suppose for contradiction that P is non-zero. We can write P = \sum_{i=0}^d P_i, where 0 \leq d \leq |F|-1 is the degree of P and P_i is the i^{th} homogeneous component, thus P_d is non-zero. Since P vanishes on E, d cannot be zero.

Let v \in F^n \backslash \{0\} be an arbitrary direction. As E is a Kakeya set, E contains a line \{ x + tv: t \in F \} for some x = x_v \in F^n, thus P(x+tv) = 0 for all t \in F. The left-hand side is a polynomial in t of degree at most |F|-1, and thus vanishes identically by the factor theorem. In particular, the t^d coefficient of this polynomial, which is P_d(v), vanishes for any non-zero v. Since P_d is homogeneous of degree d > 0, P_d vanishes on all of F^n. Since P_d also has degree less than |F|, repeated application of the factor theorem for each variable in turn (or the Schwarz-Zippel lemma, which is much the same thing) shows that P_d = 0, a contradiction. \Box

Remark. The point here is that a low-degree polynomial which vanishes on a line must also vanish on the point at infinity where the line touches the hyperplane at infinity. Thus a polynomial which vanishes on a Kakeya set vanishes at the entire hyperplane at infinity. One can then divide out the defining polynomial for that hyperplane and repeat the process to conclude that the polynomial vanishes identically. \diamond

Combining the lemma and the proposition we obtain

Corollary. Every Kakeya set in F^n has cardinality at least \binom{|F|+n-1}{n}.

Since \binom{|F|+n-1}{n} = \frac{1}{n!} |F|^n + O_n( |F|^{n-1} ), this establishes the finite field Kakeya conjecture.

This bound seems to be quite tight. For instance, it gives the lower bound of \frac{|F|(|F|+1)}{2} for Kakeya sets in F^2 (which was already implicitly observed by Wolff). The best known lower bound currently in this case is \frac{|F|(|F|+1)}{2} + \frac{5}{14} |F| + O(1), due to Cooper (see also a related paper by Faber); in the other direction, an example of Mockenhaupt and myself shows that such sets can have cardinality \frac{|F|(|F|+1)}{2} + \frac{1}{2} |F| + O(1).

It now seems sensible to revisit other problems in extremal combinatorics over finite fields to see if the polynomial method can yield results there. Certainly close relatives of the Kakeya conjecture (e.g. the Nikodym set conjecture, or the Kakeya maximal function conjecture) should now be establishable by these methods. On the other hand, there are other problems (such as the sum-product problem, Szemerédi-Trotter type theorems, and distance set problems) which are sensitive to the choice of field F (and in particular, whether that field contains a subfield of index 2); see this paper of Bourgain, Katz, and myself for further discussion. It would be interesting to see if there are ways to adapt the polynomial method in order to detect the existence of subfields.

Unfortunately, the polynomial method is extremely dependent on the algebraic nature of the finite field setting and does not seem to extend directly to the Euclidean case (though there may be a chance that they may extend instead to certain problems in discrete combinatorial incidence geometry, such as the “joints” problem of Sharir, perhaps by using various embedding theorems). On the other hand, this result lends significant indirect support to the Euclidean Kakeya conjecture; in particular, the result morally rules out any “algebraic” counterexample to the Euclidean conjecture, since a highly algebraic example to this conjecture would likely be adaptable to the finite field setting. (The examples of zero measure Kakeya sets in the Euclidean plane have no finite field analogue, but they are non-algebraic in nature, and in particular take advantage of the multiple scales available in the Euclidean setting.)

[Update, Mar 24: Proof of proposition expanded.]

[Update, Mar 25: See also these posts by Izabella Laba and Quomodocumque.]