Tower-type bounds for Roth's theorem with popular differences

Abstract

Green developed an arithmetic regularity lemma to prove a strengthening of Roth's theorem on arithmetic progressions in dense sets. It states that for every $\epsilon >0$ there is some $N_0(\epsilon )$ such that for every $N\ge N_0(\epsilon )$ and $A\subset [N]$ with $|A|=\alpha N$, there is some nonzero $d$ such that $A$ contains at least $({\alpha }^3-\epsilon )N$ three-term arithmetic progressions with common difference $d$. We prove that the minimum $N_0(\epsilon )$ in Green's theorem is an exponential tower of 2s of height on the order of $\log (1/\epsilon )$. Both the lower and upper bounds are new. It shows that the tower-type bounds that arise from the use of a regularity lemma in this application are quantitatively necessary.

29 pages