1.2. Roth’s theorem 37

It remains to verify that Et is good. For any K 0, we have (as t is good)

that

En∈[N](1Et+1/K − 1Et−1/K )

δ

1/K.

Applying Urysohn’s lemma, we can thus find a smooth function η : R →

R+

with η(t ) = 1 for t t − 1/K and η(t ) = 0 for t t + 1/K such that

En∈[N]|1Et (n) − η(Re e(−αn + θ))|

δ

1/K.

Using the Weierstrass approximation theorem, one can then approximate

η uniformly by O(1/K) on [−1, 1] by a polynomial of degree OK(1) and

coeﬃcients OK(1). This allows one to approximate 1Et in

L1

norm to an

accuracy of Oδ(1/K) by a function of Fourier complexity OK(1), and the

claim follows.

Corollary 1.2.9 (Correlation implies energy increment). Let f : [N] →

[0, 1], and let B be a factor generated by at most M atoms, each of which

is Fourier-measurable with growth function F. Suppose that we have the

correlation

|f − E(f|B),e(α·)

L2([N])

| ≥ δ

for some δ 0 and α ∈ R. Then there exists a refinement B generated

by at most 2M atoms, each of which is Fourier-measurable with a growth

function F depending only on δ, F, such that

(1.12) E(f|B )

2

L2([N])

− E(f|B)

2

L2([N])

δ2.

Proof. By Lemma 1.2.8, we can find a Fourier-measurable set E with some

growth function F depending on δ, such that

|f − E(f|B), 1E L2([N])| δ.

We let B be the factor generated by B and E. As 1E is measurable with

respect to B , we may project onto

L2(B

) and conclude that

|E(f|B ) − E(f|B), 1E L2([N])| δ.

By Cauchy-Schwarz, we thus have

E(f|B ) − E(f|B)

L2([N])

δ.

Squaring and using Pythagoras’ theorem, we obtain (1.12). The remaining

claims in the corollary follow from Exercise 1.2.10.

We can then iterate this corollary via an energy increment argument to

obtain

Proposition 1.2.10 (Weak arithmetic regularity lemma). Let f : [N] →

[0, 1], and let B be a factor generated by at most M atoms, each of which

is Fourier-measurable with growth function F. Let δ 0. Then there exists