  Green proved an arithmetic analogue of Szemer\'edi'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.
