1.2. Roth’s theorem 29

It remains to prove Proposition 1.2.3. There are two main steps. The

first relies heavily on the fact that the progressions only have length three,

and is proven via Fourier analysis:

Proposition 1.2.4 (Lack of progressions implies correlation with a linear

phase). Let δ 0, let N be suﬃciently large depending on δ, let A ⊂ [N]

be such that |A| = δ N for some δ ≥ δ, with A containing no arith-

metic progressions of length three. Then there exists α ∈ R/Z such that

|En∈[N](1A(n) − δ )e(−αn)|

δ2.

Proof. In order to use Fourier analysis, it will be convenient to embed [N]

inside a cyclic group Z/N Z, where N is equal to (say) 2N + 1; the exact

choice here is only of minor importance, though it will be convenient to take

N to be odd. We introduce the trilinear form

Λ(f, g, h) := En,r∈Z/N Zf(n)g(n + r)h(n + 2r)

for any functions f, g, h: Z/N Z → C; we then observe that the quantity

Λ(1A, 1A, 1A) = En,r∈Z/N Z1A(n)1A(n + r)1A(n + 2r)

(extending 1A by zero outside of [N]) is equal to the number of arithmetic

progressions n, n + r, n + 2r in A (counting the degenerate progressions in

which r = 0, and also allowing for r to be negative), divided by the nor-

malising factor of (N

)2.

On the other hand, by hypothesis, A contains

no non-degenerate arithmetic progressions of length three, and clearly has

|A| ≤ N degenerate progressions; thus we have

(1.8) Λ(1A, 1A, 1A) 1/N.

On the other hand, from the Fourier inversion formula on the cyclic group

Z/N Z we may write

f(n) =

α∈

1

N

Z/Z

ˆ(α)e(αn)

f

for any function f : Z/N Z → C, where

ˆ(α)

f are the Fourier coeﬃcients

ˆ(α)

f := En∈Z/N Zf(n)e(−αn).

We may thus write Λ(f, g, h) as

α1,α2,α3∈

1

N

Z/Z

ˆ(α1)ˆ(α2)ˆ(α3)

f g h

(1.9) En,r∈Z/N Ze(α1n + α2(n + r) + α3(n + 2r)).

Now observe that we have the identity

αn − 2α(n + r) + α(n + 2r) = 0,