116 1. Higher order Fourier analysis
where B is the Bohr set
B := {n ∈ Z/NZ : e(nξ/N) − 1 ≤ ε for all ξ ∈ S}.
Clearly, if f is nonnegative, then g is also. Now we look at upper bounds
on g. Clearly,
g(n) ≤ Em1,m2∈Bν(n + m1 − m2)
so by Fourier expansion
g
L∞(Z/NZ)
≤
ξ∈Z/NZ
Em∈Be(ξB)2ˆ(ξ).
ν
Let us make the Fourierpseudorandomness assumption
(1.55) sup
ξ=0
ˆ(ξ) ν = oN→∞(1).
Evaluating the ξ = 0 term on the RHS separately, we conclude that
g
L∞(Z/NZ)
≤ 1 + oN→∞(
ξ∈Z/NZ
Em∈Be(ξB)2).
By Plancherel’s theorem we have
ξ∈Z/NZ
Em∈Be(ξB)2
= B/N.
From the Kronecker approximation theorem we have
B/N
(ε/10)S
(say). Finally, if we assume (1.54) we have S
ε−q.
Putting this all
together we obtain the pointwise bound
g ≤ 1 + oN→∞;q,ε(1).
Finally, we see how g approximates f. From Fourier analysis one has
ˆ(ξ) g =
ˆ(ξ)Em∈Be(ξB)2
f
and so
f − g
u2(Z/NZ)
= sup
ξ∈Z/NZ

ˆ(ξ)(1
f −
Em∈Be(ξB)2).
The frequencies ξ that lie outside ξ give a contribution of at most ε by the
definition of S, so now we look at the terms where ξ ∈ S. From the definition
of B and the triangle inequality we have
Em∈Be(ξB) − 1 ≤ ε
in such cases, while from the measure nature of ν we have

ˆ(ξ)
f ≤ En∈Z/NZν(n) = 1 + oN→∞(1).
Putting this all together, we obtain
f − g
u2(Z/NZ)
ε + oN→∞(1).