Sharp density bounds on the finite field Kakeya problem

Sharp density bounds on the finite field Kakeya problem, Discrete Analysis 2021:26, 9 pp.

A subset $A$ of the vector space $\mathbb F_p^n$ is called a finite-field Kakeya set if it contains a line in every direction. That is, for every $x\in\mathbb F_p^n\setminus\{0\}$ there exists $a\in\mathbb F_p^n$ such that the line $\{a+tx:t\in\mathbb F_p\}$ is contained in $A$.

Such sets are a natural analogue of Kakeya sets in $\mathbb R^n$, which are, again, sets that contain a line in every direction. Besicovitch showed that Kakeya sets in $\mathbb R^2$, and hence in $\mathbb R^n$ for any $n\geq 2$, can have measure zero. However, it is a major unsolved problem to determine the smallest possible Hausdorff dimension of such a set (or indeed other commonly used dimensions such as the box-counting dimension). When $n=2$ it is known that the dimension must be 2, so in a certain sense Kakeya sets cannot be too small, and it is conjectured that this is true for all $n$, but that is not known for any $n$ greater than 2.

In 1999 Thomas Wolff suggested that a useful discrete analogue of the Kakeya problem would be to look at the minimum density of finite-field Kakeya sets. If one pursues the analogy, one finds that a density of $p^{-\alpha}$ (and thus a cardinality of $p^{n-\alpha}$) in the finite-field case should roughly correspond to a Hausdorff dimension of $n-\alpha$ in the Euclidean case. This problem is cleaner than the Euclidean problem, because it avoids issues that arise with pairs of lines that are almost parallel. Nevertheless, it too appeared to be hard, so the hope was that it would be a good intermediate question.

Wolff’s problem was solved in 2008 by Zeev Dvir, who came up with a remarkably short argument based on polynomials. (Very roughly, if a set $A$ is small, then one can find a non-trivial polynomial in $n$ variables of degree $d<p$ that vanishes on $A$. However, if $A$ is a Kakeya set, then it can be shown quite easily that the degree-$d$ part of the polynomial does vanish, which is a contradiction.) Unfortunately, this argument appears not to shed much light on the Euclidean case, but it has nevertheless been extremely influential, and has inspired many further results.

The lower bound obtained by Dvir was roughly $p^n/n!$ – here one thinks of $n$ as constant and $p$ as tending to infinity, so this is within a constant of the size of $\mathbb F_p^n$. Subsequent work has improved this to about $(p/2)^n$, while in the other direction there is a construction that gives an upper bound of about $p^n/2^{n-1}$. These results were obtained in 2008-9, so the factor 2 between the two bounds has been present for over a decade.

This paper finally closes the gap to $1+o(1)$ by improving the lower bound by a factor of $2+o(1)$. The main ideas that make this improvement possible are mostly present in the earlier proofs, but their implementations here are quite different. One of these ideas is to consider not just the vanishing of polynomials but the multiplicity of the vanishing, and another is to consider polynomials that belong to a less obvious space of polynomials than simply the space of all polynomials of degree less than $p$. Provided the dimension of the space of polynomials exceeds the number of independent linear constraints imposed by the requirement that a polynomial should vanish with certain multiplicities at the points of the Kakeya set, there will be a polynomial in the space that vanishes in the required way, and if the multiplicities are chosen appropriately, one can arrive at a suitable lower bound for the size of the Kakeya set. Another essential idea in this paper, which was introduced in a different context by Ruixiang Zhang, is to require the vanishing conditions (defined in terms of Hasse derivatives, which are discussed in the paper) to depend on the lines that go through the points in the Kakeya set.