1.2. Roth’s theorem 39
and hence by Pythagoras
E(f|Bk+1) − E(f|Bk)
Setting fstr := E(f|Bk), fsml := E(f|Bk+1)−E(f|Bk), fpsd := f −E(f|Bk+1),
we obtain the claim.
Remark 1.2.12. This result is essentially due to Green [Gr2005b] (though
not quite in this language). Earlier related decompositions are due to Bour-
gain [Bo1986] and to Green and Konyagin [GrKo2009]. The Szemer´edi
regularity lemma in graph theory can be viewed as the graph-theoretic ana-
logue of this Fourier-analytic result; see [Ta2006], [Ta2007] for further dis-
cussion. The double iteration required to prove Theorem 1.2.11 means that
the bounds here are quite poor (of tower-exponential type, in fact, when F
is exponential, which is typical in applications), much as in the graph theory
case; thus the use of this lemma, while technically quantitative in nature,
gives bounds that are usually quite inferior to what is known or suspected
to be true.
As with the equidistribution theorems from the previous sections, it is
crucial that the uniformity 1/F (M) for the pseudorandom component fpsd
is of an arbitrarily higher quality than the measurability of the structured
Much as the equidistribution theorems from the previous sections could
be used to prove multiple recurrence theorems, the arithmetic regularity
lemma can be used (among other things) to give a proof of Roth’s theorem.
We do so as follows. Let N be a large integer, and let A be a subset of [N]
with |A| ≥ δN for some δ 0. We consider the expression Λ(1A, 1A, 1A),
where Λ is the trilinear form
Λ(f, g, h) :=
f(n)g(n + r)h(n + 2r).
We will show that
(1.14) Λ(1A, 1A, 1A)
which implies that the number of all three-term arithmetic progressions in
A (including the degenerate ones with r = 0) is
For N suﬃciently
large depending on δ, this number is larger than the number N of degenerate
progressions, giving the theorem.
It remains to establish (1.14). We apply Theorem 1.2.11 with parameters
ε 0, F to be chosen later (they will depend on δ) to obtain a quantity M
and a decomposition
1A = fstr + fsml + fpsd