Effective Bounds for Restricted \(3\)-Arithmetic Progressions in \(\mathbb{F}_p^n\)

Effective bounds for restricted \(3\)-arithmetic progressions in \(\mathbb{F}_p^n\), Discrete Analysis 2024:16, 22 pp.

Roth’s theorem on arithmetic progressions, proved in 1953, states that for every \(\delta>0\) and every \(k\in\mathbb N\) there exists \(N\in\mathbb N\) such that every subset \(A\) of \(\{1,2,\dots,N\}\) of size at least \(\delta N\) contains an arithmetic progression of length 3. It has been generalized and modified in multiple directions. Famously, Szemerédi proved the corresponding result for progressions of arbitrary length in 1975.

Sticking with progressions of length 3, Meshulam adapted Roth’s proof to show that for every \(\delta>0\) there exists \(n\) such that every subset \(A\) of \(\mathbb F_3^n\) of size at least \(\delta 3^n\) contains an affine line, or equivalently a triple of distinct points \(x,y,z\) such that \(x+y+z=0\).

A result that implies both these two results is the \(k=3\) case of the density Hales-Jewett theorem, due to Furstenberg and Katznelson. It concerns dense subsets of \(\{0,1,2\}^n\). A combinatorial line in \(\{0,1,2\}^n\) is defined as follows. Let \(x\) be a sequence in \(\{0,1,2,*\}\), in which \(*\), a “wildcard” symbol, appears at least once. For \(i=0,1,2\), let \(x(i)\) be the sequence obtained by replacing all wildcard symbols by \(i\). A combinatorial line is any set \(\{x(0), x(1), x(2)\}\) that can be obtained in this way. The density Hales-Jewett theorem states that for every \(\delta>0\) there exists \(n\) such that every subset of \(\{0,1,2\}^n\) of size at least \(\delta 3^n\) contains a combinatorial line. (The full theorem is the obvious generalization of this one to subsets of \(\{0,1,\dots,k-1\}^n\) for general \(k\).)

There has been remarkable progress on quantitative aspects of Roth’s theorem and Meshulam’s variant of it, which is often referred to as the cap-set problem. Thanks to a breakthrough of Kelley and Meka, we now know that a bound on the density of the form \(\delta\geq\exp(-(\log n)^c)\) is sufficient to guarantee that a subset \(A\subset\{1,2,\dots,n\}\) is sufficient to guarantee that \(A\) contains an arithmetic progression of length 3, and that for the cap-set problem there exists \(\alpha<1\) such that the condition \(\delta\geq\alpha^n\) suffices for a set of density \(\delta\) to contain an affine line. However, until recently the best bound for the density Hales-Jewett theorem, proved by the first Polymath project in 2009, was of tower type.

To try to get some insight into what the difficulties are in obtaining better quantitative bounds for the density Hales-Jewett theorem, one can try to find problems that are of intermediate difficulty. And indeed, there is a very natural candidate: if we identify \(\{0,1,2\}\) with \(\mathbb F_3\), then every combinatorial line is in particular an affine line \(x,x+d,x+2d\) where \(d\) is a 01-vector. The converse of this is not true: a combinatorial line satisfies the additional condition that \(x\) is constant on the set of coordinates \(i\) such that \(d_i=1\). Therefore, one can hope that as a first step towards improving the bounds for combinatorial lines, one could try to improve them for arithmetic progressions in \(\mathbb F_3^n\) with common difference restricted to belong to \(\{0,1\}^n\).

That is not quite what is done in this paper, but the theorem proved is closely related, and it is the first time good bounds have been attained for any problem of cap-set type where the coordinates of the common difference are restricted. The authors consider arithmetic progressions in \(\mathbb F_p^n\) with common difference belonging to \(\{0,1,2\}^n\), and prove that for a set to contain one of these, a density of \(\frac{C}{(\log\log\log n)^c}\) suffices, where \(c>0\) and \(C\) depend only on \(p\).

The paper is part of a much larger project concerning constraint satisfiability problems and relies on a deep theorem proved by the authors in an earlier paper. Since this paper was written, the project has led to the remarkable result that the density Hales-Jewett theorem for combinatorial lines of length 3 holds for sets of density \((\log\log\log\log n)^{-c}\). (However, that result does not completely supersede the result of this paper since it needs four logs instead of three.)