Excluding affine configurations over a finite field

Excluding affine configurations over a finite field, Discrete Analysis 2023:21, 24 pp.

In 2016 a remarkable development took place in additive combinatorics, when Ernie Croot, Seva Lev and Péter Pál Pach posted a paper to arXiv using the polynomial method to obtain an exponential upper bound for the density of a subset of $\mathbb F_4^n$ that does not contain an arithmetic progression of length 3, and very shortly afterwards, Jordan Ellenberg and the author of this paper modified the proof to obtain a similar upper bound for $\mathbb F_3^n$, thereby obtaining the correct form for the upper bound in the famous cap-set problem.

The condition on a cap set can be expressed by saying that it is a subset $A$ of $\mathbb F_3^n$ that contains no triple $(x,y,z)$ of distinct elements such that $x+y+z=0$. That is, we impose on $A$ the condition that it contains no non-trivial solutions to the equation $x+y+z=0$, and the conclusion is that $A$ must have exponentially small density.

Once the question has been formulated that way, it is natural to wonder whether similar results can be proved for other linear equations. That is, for which sequences $(a_1,\dots,a_k)$ is it the case that if $A$ contains no non-trivial solutions to the equation $a_1x_1+\dots+a_kx_k=0$, then $A$ must have exponentially small density?

It is well known that even to enforce a density of $o(1)$ it is necessary that $a_1+\dots+a_k=0$, since otherwise one could for example take the set $A$ of all vectors $x$ for which the sum of their coordinates is equal to 1 (in $\mathbb F_3$). And in fact it turns out to be easy to modify the argument of Ellenberg and Gijswijt to show that if this condition is satisfied, and if the number of non-zero coefficients $a_i$ is at least 3, then $A$ must have exponentially small density. The argument also works with $\mathbb F_3$ replaced by an arbitrary finite field $\mathbb F$ (with an exponent that depends on the field).

A question one might then ask is what happens if one takes several equations instead of just one. That is the topic of this paper. Suppose, then, that $\mathbb F$ is a finite field and that for $i=1,2,\dots,m$ one has a linear equation

$$a_{i1}x_1+\dots+a_{ik}x_k=0$$
with $a_{i1}+\dots+a_{ik}=0$. Under what conditions on the $m\times k$ matrix $(a_{ij})$ must a subset $A$ of $\mathbb F^n$ have exponentially small density if there are no non-trivial solutions $(x_1,\dots,x_k)\in(\mathbb F^n)^k$ to the system of equations?

It is not immediately obvious what should count as a “non-trivial” solution here. The correct definition turns out to be that $(x_1,\dots,x_k)$ should not satisfy any linear relations that are not implied by the equations. For instance, in the simple case where $m=1$ and the equation is $x-2y+z=0$, the trivial solutions $x=y=z$ are ruled out, because the linear relations $x-y=0, y-z=0$ and $z-x=0$ hold for these solutions but are not implied by the equation $x-2y+z=0$.

The paper identifies a condition that it calls “tameness”, which roughly speaking captures the limit of known methods, and in particular of the slice-rank method, which was a modification due to Terence Tao of the approach of Ellenberg and Gijswijt. A system of linear equations is tame if for every system of equations that it implies, the number of variables is greater than twice the number of equations. For instance, the system that consists of the two equations $x+y+z-u-v-w=0$ and $x-y+z-u+v-w=0$ is not tame, because from it we can deduce $2y-2v=0$ (and therefore $y-v=0$ in odd characteristic), which is one equation in only two variables.

The paper shows that if a system of equations is tame, then a set that does not contain a non-trivial solution to the equations must be of exponentially small density. The proof is a non-trivial adaptation of the slice-rank method, but perhaps the main achievement of the paper is to identify the tameness condition in the first place, which captures the precise boundary (when the field has at least four elements – for $\mathbb F_2$ and $\mathbb F_3$ the tameness condition turns out not to be needed) between instances of the problem that can be solved using the slice-rank method and instances that cannot (or at least cannot without some unexpected new ingredient). It also makes precise the challenge of going beyond the current techniques: does there exists a non-tame system of linear equations that gives rise to an exponential upper bound? An answer would be a very interesting contribution to our understanding of the limitations of the polynomial method.

A related question that is still open is the following: does there exist a system of linear equations over $\mathbb F$ such that the maximum density of a subset of $\mathbb F^n$ that contains no non-trivial solutions to the equations is $o(1)$ but not exponentially small?