Popular progression differences in vector spaces

Abstract

Green proved an arithmetic analogue of Szemerédi's celebrated regularity lemma and used it to verify a conjecture of Bergelson, Host, and Kra which sharpens Roth's theorem on three-term arithmetic progressions in dense sets. It shows that for every subset of ${\mathbb{F}}_p^n$ with $n$ sufficiently large, the density of three-term arithmetic progressions with some nonzero common difference is at least the random bound (the cube of the set density) up to an additive $\epsilon$. For a fixed odd prime $p$, we prove that the required dimension grows as an exponential tower of $p$'s of height $\Theta (\log (1/\epsilon ))$. This improves both the lower and upper bound, and is the first example of a result where a tower-type bound coming from applying a regularity lemma is shown to be necessary.

18 pages