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
Previous Page Next Page