1.2. Roth’s theorem 35
closure and work with the wider class of Fourier measurable functions
as our structured class.
Definition 1.2.7 (Measurability). Let F :
be a function. We
say that a function f : [N] → C is Fourier measurable with growth function
F if, for every K 1, one can find a function fK : [N] → C of Fourier
complexity at most F(K) such that En∈[N]|f(n) − fK(n)| ≤ 1/K.
A subset A of [N] is Fourier measurable with growth function F if 1A is
Fourier measurable with this growth function.
Exercise 1.2.8. Show that every interval [a, b] in [N] is Fourier measur-
able with some growth function F independent of N. (Hint: Apply Fej´er
summation to the Fourier series of 1[a,b].)
Exercise 1.2.9. Let f be a Fourier-measurable function with some growth
function F, which is bounded in magnitude by A. Show that for every
K 1, one can find a function
: [N] → C which also is bounded in mag-
nitude by A, and of Fourier complexity OA,F(K)(1), such that En∈[N]|f(n)−
f K(n)| 1/K. (Hint: Start with the approximating function fK from Def-
inition 1.2.7, which is already bounded in magnitude by F(K), and then set
:= P (fK , fK) where P (z, z) is a polynomial bounded in magnitude by A
on the ball of radius F(K) which is close to the identity function on the ball
of radius A (such a function can be constructed via the Stone-Weierstrass
Exercise 1.2.10. Show that if f, g : [N] → C are bounded in magnitude by
A, and are Fourier measurable with growth functions F, then f + g, f, and
fg are Fourier measurable with some growth function F depending only on
A and F.
Conclude that if E, F ⊂ [N] are Fourier-measurable with growth func-
tion F, then [N]\E, E ∪ F , and E ∩ F are Fourier-measurable with some
growth function F depending only on F.
We thus see that Fourier-measurable sets
form a Boolean alge-
Now we make a key observation (cf. [ReTrTuVa2008]):
Lemma 1.2.8 (Correlation with a Fourier character implies correlation with
a Fourier-measurable set). Let f : [N] → C be bounded in magnitude by 1,
and suppose that |En∈[N]f(n)e(−αn)| ≥ δ for some δ 0. Then there exists
a Fourier-measurable set E ⊂ [N] with some growth function F depending
on δ, such that |En∈[N]f(n)1E(n)| δ.
5Again, we can formalise this assertion once we pass to the ultralimit; we leave this formali-
sation to the interested reader.