26 1. Higher order Fourier analysis

(ii) (Pequi is equidistributed) There exists a standard subtorus T of

Td,

such that Pequi takes values in T and is totally equidistributed on

[N]m

in this torus.

(iii) (Prat is rational) The coeﬃcients αi,rat of Prat are standard rational

elements of Td. In particular, there is a standard positive integer

q such that qPrat = 0 and Prat is periodic with period q.

Proof. This is implicitly in [GrTa2011]; the result is phrased using the

language of single-scale equidistribution, but this easily implies the ultralimit

version.

1.2. Roth’s theorem

We now give a basic application of Fourier analysis to the problem of count-

ing additive patterns in sets, namely the following famous theorem of Roth

[Ro1953]:

Theorem 1.2.1 (Roth’s theorem). Let A be a subset of the integers Z whose

upper density

δ(A) := lim sup

N→∞

|A ∩ [−N, N]|

2N + 1

is positive. Then A contains infinitely many arithmetic progressions a, a +

r, a + 2r of length three, with a ∈ Z and r 0.

This is the first non-trivial case of Szemer´ edi’s theorem [Sz1975], which

is the same assertion but with length three arithmetic progressions replaced

by progressions of length k for any k.

As it turns out, one can prove Roth’s theorem by an application of linear

Fourier analysis by comparing the set A (or more precisely, the indicator

function 1A of that set, or of pieces of that set) against linear characters

n → e(αn) for various frequencies α ∈ R/Z. There are two extreme cases to

consider (which are model examples of a more general dichotomy between

structure and randomness, as discussed in [Ta2008]). One is when A is

aligned almost completely with one of these linear characters, for instance,

by being a Bohr set of the form

{n ∈ Z : αn − θ

R/Z

ε}

or, more generally, of the form

{n ∈ Z : αn ∈ U}

for some multi-dimensional frequency α ∈

Td

and some open set U. In

this case, arithmetic progressions can be located using the equidistribution

theory from Section 1.1. At the other extreme, one has Fourier-uniform or

Fourier-pseudorandom sets, whose correlation with any linear character is