38 1. Higher order Fourier analysis

an extension B of B generated by OM,δ(1) atoms, each of which is Fourier-

measurable with growth function F depending on F,δ, such that

(1.13) |f − E(f|B ),e(α·) L2([N])| δ

for all α ∈ R.

Proof. We initially set B equal to B. If (1.13) already holds, then we

are done; otherwise, we invoke Corollary 1.2.9 to increase the “energy”

E(f|B )

2

L2

by

δ2,

at the cost of possibly doubling the number of atoms

in B , and also altering the growth function somewhat. We iterate this pro-

cedure; as the energy E(f|B )

2

L2

is bounded between zero and one, and

increases by δ2 at each step, the procedure must terminate in O(1/δ2)

steps, at which point the claim follows.

It turns out that the power of this lemma is amplified if we iterate one

more time, to obtain

Theorem 1.2.11 (Strong arithmetic regularity lemma). Let f : [N] → [0, 1],

let ε 0, and let F :

R+

→

R+

be an arbitrary function. Then we can

decompose f = fstr + fsml + fpsd and find 1 ≤ M = Oε,F (1) such that

(i) (Nonnegativity) fstr,fstr + fsml take values in [0, 1], and fsml,fpsd

have mean zero;

(ii) (Structure) fstr is Fourier-measurable with a growth function FM

that depends only on M;

(iii) (Smallness) fsml has an

L2

norm of at most ε; and

(iv) (Pseudorandomness) One has |En∈[N]fpsd(n)e(−αn)| ≤ 1/F (M)

for all α ∈ R.

Proof. We recursively define a sequence M1 M2 . . . by setting M1 := 1

and Mk+1 := Mk + F (Mk) + 1 (say). Applying Proposition 1.2.10 (starting

with the trivial factor B1), one can then find a nested sequence of refinements

B1 ⊂ B2 ⊂ . . . , such that

|f − E(f|Bk),e(α·) L2([N])| 1/Mk

for all k ≥ 1 and α ∈ R, and such that each Bk consists of Ok(1) atoms

that are Fourier-measurable with some growth function depending on Mk

(note that this quantity dominates k and M1,...,Mk−1 by construction). By

Pythagoras’ theorem, the energies E(f|Bk)

2

L2([N])

are monotone increasing

between 0 and 1, so by the pigeonhole principle there exists k =

O(1/ε2)

such that

E(f|Bk+1)

2

L2([N])

− E(f|Bk)

2

L2([N])

≤

ε2