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 sufficiently 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)|
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
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) =
for any function f : Z/N Z C, where
f are the Fourier coefficients
f := En∈Z/N Zf(n)e(−αn).
We may thus write Λ(f, g, h) as
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,
Previous Page Next Page