Search

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](https://arxiv.org/abs/2108.00074), 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.

Rank bounds for design matrices with block entries and geometric applications, Discrete Analysis 2018:5, 24 pp. It is not hard to prove, when the statement is suitably formulated, that if $A$ is a random matrix, then it is not possible to reduce the rank of $A$ by changing only a few entries. However, it is remarkably hard to find an explicit example of such a matrix. It turns out that explicit examples would have major applications in theoretical computer science, and therefore the matrix-rigidity problem is a central question in the area. In order to make progress on this problem, one can ask a more basic question: are there any combinatorial conditions on a matrix that guarantee that it has a high rank? An interesting condition has recently been identified that does not solve the matrix-rigidity problem but that does have several applications, in particular to combinatorial geometry. Roughly speaking, the condition is that there should not be many non-zero entries in any row or too few non-zero entries in any column, and for any two rows the number of columns for which the entries in both rows are non-zero is small. Such matrices are known as _design matrices_, since the conditions resemble those for a design, though they are significantly looser. The proof that such matrices have high rank uses a beautiful technique called _matrix scaling_. The rough idea is to multiply rows and columns by non-zero scalars until the entries are of broadly the same magnitude, and then to show that the matrix $A^*A$ is dominated by its diagonal. From this it follows fairly easily that $A^*A$ has high rank, and therefore that $A$ does as well. The argument can be found in [a paper of Barak, Dvir, Wigderson and Yehudayoff](https://arxiv.org/pdf/1009.4375.pdf) that this paper generalizes. Such rank bounds are useful, because there are several problems in combinatorial geometry that lead naturally to design matrices. For example, the Sylvester-Gallai theorem and its generalizations concern families of points and collinearity relations between them. If the points are $v_1,\dots,v_n$, then one can write them as column vectors and put them together to form a matrix $M$. Three of the points will be collinear if there is a linear dependence amongst the columns of this matrix with three non-zero coefficients, or equivalently a vector $w$ with three non-zero entries such that $Mw=0$. Under suitable hypotheses, one can use such vectors $w$ to create a design matrix and apply rank bounds on the design matrix to deduce combinatorial consequences about the set of points $v_1,\dots,v_n$. The generalization in this paper concerns design matrices whose entries are themselves matrices, or "blocks". Rank bounds are proved for such matrices, which lead to new applications in combinatorial geometry. One of these applications is to the following question. Let $T$ be a set of triples of elements of $\{1,2,\dots,n\}$ and let $V(T)$ be the variety of all sequences $(v_1,\dots,v_n)$ of points in $\mathbb C^d$ such that for every triple $\{i,j,k\}\in T$ the three points $v_i, v_j$ and $v_k$ are collinear. Given a (non-singular) sequence $V\in V(T)$, how many degrees of freedom does it have? A trivial lower bound is 8, resulting from the fact that projective transformations preserve collinearity. The authors prove a general result that has as a consequence that if every pair $\{i,j\}$ belongs to exactly one triple in $T$ and no line contains more than half the points of $V$, then the number of degrees of freedom of $V$ is at most 15. A more precise statement, as well as other interesting applications, can be found in the paper.

We study questions in incidence geometry where the precise position of points is ‘blurry’ (for example due to noise, inaccuracy or error). Thus lines are replaced by narrow tubes, and more generally affine subspaces are replaced by their small neighborhood. We show that the presence of a sufficiently large number of approximately collinear triples in a set of points in ${\mathbb{C}}^d$ implies that the points are close to a low dimensional affine subspace. This can be viewed as a stable variant of the Sylvester–Gallai theorem and its extensions. Building on the recently found connection between Sylvester–Gallai type theorems and complex locally correctable codes (LCCs), we define the new notion of stable LCCs, in which the (local) correction procedure can also handle small perturbations in the Euclidean metric. We prove that such stable codes with constant query complexity do not exist. No impossibility results were known in any such local setting for more than two queries.

We study the rank of complex sparse matrices in which the supports of different columns have small intersections. The rank of these matrices, called design matrices, was the focus of a recent work by Barak et al. [Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes. Proceedings of the 43rd annual ACM symposium on Theory of computing, STOC 11, (ACM, NY 2011), 519–528] in which they were used to answer questions regarding point configurations. In this work, we derive near-optimal rank bounds for these matrices and use them to obtain asymptotically tight bounds in many of the geometric applications. As a consequence of our improved analysis, we also obtain a new, linear algebraic, proof of Kelly’s theorem, which is the complex analog of the Sylvester–Gallai theorem.