  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.
