Simple proofs for Furstenberg sets over finite fields

Simple proofs for Furstenberg sets over finite fields, Discrete Analysis 2021:22, 16 pp.

A Kakeya set in $\mathbb R^2$ is a subset that contains a unit line segment in every direction. A well-known result of Besicovitch states that there are Kakeya sets of measure zero. This has led to numerous further results and some fascinating open problems.

The fact that a set has measure zero means that it is in a certain sense small, but one can still investigate more precise notions of smallness, such as Hausdorff dimension. It can be shown that from this perspective Kakeya sets must be large, in the sense that they must have maximal Hausdorff dimension – that is, dimension 2. We thus have a pretty clear picture of how large a Kakeya set needs to be.

However, as soon as the dimension increases, that is no longer true. By considering the Cartesian product of a 2-dimensional example with a line segment, one sees immediately that a 3-dimensional Kakeya set can have measure zero, but it is a long-standing open problem to determine whether it must have Hausdorff dimension 3. An argument of Thomas Wolff reached a natural barrier of 5/2, a much more difficult argument of Nets Katz, Izabella Łaba and Terence Tao broke through the barrier, reaching a very slightly higher dimension, though their bound was for the upper Minkowski dimension, which in general can be larger, and the current state of the art is due to Nets Katz and Joshua Zahl, who have proved a lower bound for the Hausdorff dimension that is also strictly bigger than 5/2.

In order to prove results about the Kakeya problem, it is natural to consider unions of “tubes” – that is, to replace line segments by thin cylinders and then to let the width of the cylinders tend to zero. Part of the difficulty with the Kakeya problem is that the size of the intersection of two cylinders can be large if the angle between them is small. For this reason, Thomas Wolff had the idea that it might be better to tackle a natural finite-field analogue of the Kakeya problem first, since in a vector space over a finite field, the ways that two lines can intersect are much more restricted, and this leads to a cleaner problem. The precise question asked was how large a subset of $\mathbb F_q^n$ can be if it contains a line in every direction, and roughly speaking a bound of $n^\alpha$ in that problem corresponds to a Hausdorff dimension of $\alpha$. (Here one normally imagines $n$ as constant and $q$ as tending to infinity.)

The finite-field Kakeya problem became a notable open problem in its own right until Zeev Dvir, one of the authors of this paper, discovered a remarkably simple proof, using the polynomial method, that the size of such a set must be at least $c_nq^n$. (Very recently, Boris Bukh and Ting-Wei Chao obtained a lower bound that matches the known upper bound, so we now know that the minimum density is $2^{-(n-1)}$ up to lower-order terms.) Thus, a finite-field Kakeya set has “full dimension”. While it does not seem to be possible to use Dvir’s method to make further headway on the Kakeya problem in the Euclidean setting, the proof has been extremely influential and has led to many further results in combinatorial geometry.

This paper concerns a natural generalization of finite-field Kakeya sets, where the role of lines is played by higher-dimensional affine subspaces. More precisely, Dvir’s proof also gives a lower bound for the size of a set $A$ such that for every direction it intersects some line in that direction in at least $m$ points. A $(k,m)$-Furstenberg set is defined to be a set $S$ such that for every $k$-dimensional subspace $V\subset\mathbb F_q^n$ there is some translate $V+x$ such that $|S\cap(V+x)|\geq m$, and this paper concerns lower bound for the sizes of Furstenberg sets.

Jordan Ellenberg and Daniel Erman obtained a lower bound of the form $C_{n,k}m^{n/k}$, using sophisticated methods from algebraic geometry. This paper uses a much more elementary approach and obtains an improved constant (of $2^{-n}$).

The basic idea is to prove the result by induction. The key idea for doing this, which may well be useful in other places, is that of min-entropy: if $X$ is a random variable taking values in $\mathbb F_q^n$, then this is defined to be $H_\infty^q(X)=-\log_q(\max_x\mathbb P[X=x])$. For example, if $X$ is uniformly distributed over a set of size $q^r$, then $H_\infty^q(X)=r$ (so for such distributions it is proportional to the usual entropy), and in general the min-entropy is small if there is some value $x$ that is taken with high probability by $X$.

Note that if $X$ is uniformly distributed over a $(k,m)$ Furstenberg set $S\subset\mathbb F_q^n$ and $\phi:\mathbb F_q^n\to\mathbb F_q^{n-k}$ is a surjective linear map, then the min-entropy of $\phi(X)$ is at most $-\log_q(m/|S|)=\log_q(|S|/m)$, since by hypothesis there must exist $y\in\mathbb F_q^{n-k}$ such that $|S\cap\phi^{-1}(y)|\geq m$.

This observation shows that the $(k,m)$-Furstenberg property is closely related to the min-entropy of projections of random variables, and the authors use it to reformulate the problem of lower bounds for the sizes of $(k,m)$-Furstenberg sets as an equivalent question about min-entropy. The key step in their argument is to show that for any random variable $X$ taking values in $\mathbb F_q^n$ there is some surjective linear map $\psi:\mathbb F_q^n\to\mathbb F_q^{n-1}$ such that $H_\infty^q(\psi(X))$ is not much smaller than $H_\infty^q(X)$. By iterating, they obtain a map $\phi:\mathbb F_p^n\to\mathbb F_p^{n-k}$ with a similar property. This, combined with the upper bound $H_\infty^q(\phi(X))\leq\log_q(|S|/m)$, gives the desired lower bound for $|S|$.

When $q$ is large, the authors also obtain a much stronger bound using a very different argument. Observe that if $A$ is any subset of $\mathbb F_q^n$ of size $mq^{n-k}$, then by the pigeonhole principle it intersects at least one translate of every $k$-dimensional subspace in a set of size $m$ – in other words, it is a $(k,m)$-Furstenberg set. Remarkably, if $\epsilon>0$ and $q$ is sufficiently large as a function of $n$ and $\epsilon$, every $(k,m)$-Furstenberg set has size at least $(1-\epsilon)mq^{n-k}$, so up to a good approximation, whether or not a set is a $(k,m)$-Furstenberg set depends only on its cardinality.

The proof of this result relies on another natural generalization of Dvir’s finite-field Kakeya theorem. That result says that a set that contains a line in every direction must contain at least a $2^{-n}$ proportion of all points. Using an averaging argument, the authors deduce from it that a set that contains a translate of every $k$-dimensional subspace must contain at least a $2^{-n}$ proportion of all $(k-1)$-dimensional affine subspaces. Combining this with the observation that the incidence matrix of points and $(k-1)$-dimensional affine subspaces has good quasirandomness properties, they obtain the desired lower bound on the size of Furstenberg sets.

More details can be found in the paper, or in the following talk given by one of the authors.