Popular progression differences in vector spaces II

Popular progression differences in vector spaces II, Discrete Analysis 2019:16, 39 pp.

A central result in additive combinatorics, Roth’s theorem, asserts that for every $\delta>0$ there exists $n$ such that every set $A\subset\{1,2,\dots,n\}$ of size at least $\delta n$ contains an arithmetic progression of length 3. It was observed by Meshulam that Roth’s argument can be easily adapted to prove a similar result in the vector space $\mathbb F_p^n$. An averaging argument can then be used to prove that if $\{x,x+d,x+2d\}$ is an arithmetic progression of length 3 chosen at random in $\mathbb F_p^n$, then the probability that it is a subset of $A$ is at least a positive constant $c(\delta)$ that depends on $\delta$ only.

If $A$ is a randomly chosen set of density $\delta$, then the probability above is approximately $\delta^3$. Bergelson, Host and Kra noticed that although there are sets $A$ for which the probability is smaller than this, in all known examples there was at least one difference $d$ such that if $x$ is chosen randomly, then the probability that $\{x,x+d,x+2d\}\subset A$ is at least $\delta^3-o(1)$, so they conjectured that this was the case.

This conjecture was proved by Green using an arithmetic analogue of Szemer’edi’s regularity lemma that he had developed. However, the price that he had to pay for this strengthening of the vector space Roth theorem was that the dimension needed in order to guarantee the existence of such a “popular progression difference” $d$ was very high – a tower of height a power of $\epsilon^{-1}$ was needed to obtain a probability of $\delta^3-\epsilon$.

This tower-type bound is typical of proofs that use regularity lemmas. While it is known that the regularity lemmas themselves actually require tower-type bounds, it is less clear whether that is true of their many applications, and indeed there are several examples of results that were initially proved with bad bounds using regularity lemmas and then later reproved with different arguments and much better bounds. A major open problem is to determine whether tower-type bounds are needed for the triangle removal lemma. (The best known bound for this result, a tower of logarithmic height, is due to the first-named author.)

In a companion paper to this one, the authors proved that tower-type bounds are necessary for the theorem of Green mentioned above. More precisely, they obtained both an upper and lower bound for the dimension $n$, and both bounds were towers of height of order $\log(1/\epsilon)$. This was a very interesting contribution to the general question about applications of regularity lemmas, since it was the first time anybody had identified a non-trivial application of a regularity lemma for which it could be shown that a tower-type bound was necessary. (A possible definition of “non-trivial” here is a statement that does not easily imply a regularity lemma.)

In this paper, the authors continue their investigation. They define $n_p(\alpha,\beta)$ to be the smallest integer such that if $n$ is any larger integer and $A\subset\mathbb F_p^n$ has density at least $\alpha$, then there exists $d\ne 0$ such that a random arithmetic progression $\{x,x+d,x+2d\}$ in $\mathbb F_p^n$ with common difference $d$ has a probability at least $\beta$ of lying inside $A$. For every $p,\alpha,\beta$ with $\beta<\alpha^3$, $n_p(\alpha,\beta)$ is a tower of height depending on $p,\alpha$ and $\beta$, and in this paper the authors determine the height of the tower to a remarkable degree of precision (when $p\geq 19$). One of the reasons it is remarkable is that the dependence of this height on $\alpha$ and $\beta$ is far from obvious: there are three different regions, each with its own bound, and different arguments are needed for each one.