1.2. Roth’s theorem 35

an

L1

closure and work with the wider class of Fourier measurable functions

as our structured class.

Definition 1.2.7 (Measurability). Let F :

R+

→

R+

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

˜

f

K

: [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

˜

f

K

:= 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

theorem).)

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

morally5

form a Boolean alge-

bra.

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.