1.2. Roth’s theorem 39

and hence by Pythagoras

E(f|Bk+1) − E(f|Bk)

2

L2([N])

≤

ε2.

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

component fstr.

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) :=

1

N 2

n∈[N] r∈[−N,N]

f(n)g(n + r)h(n + 2r).

We will show that

(1.14) Λ(1A, 1A, 1A)

δ

1,

which implies that the number of all three-term arithmetic progressions in

A (including the degenerate ones with r = 0) is

δ

N

2.

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