112 1. Higher order Fourier analysis

Theorem 1.7.2 (Roth’s theorem in Z/NZ). Let N be odd. If f : Z/NZ →

R is a function obeying the pointwise bound 0 ≤ f ≤ 1 and the lower bound

En∈Z/NZf(n) ≥ δ 0, then one has Λ(f, f, f) ≥ c(δ) for some c(δ) 0,

where Λ(f, g, h) := En,r∈Z/NZf(n)g(n + r)h(n + 2r).

We assume this theorem as a “black box”, in that we will not care as

to how this theorem is proven. As noted in previous sections, this theorem

easily implies the existence of non-trivial arithmetic progressions of length

three in any subset A of [N/3] (say) with |A| ≥ δN, as long as N is suf-

ficiently large depending on δ, as it provides a non-trivial lower bound on

Λ(1A, 1A, 1A).

Now we generalise the above theorem. We view N as an (odd) parameter

going off to infinity, and use oN→∞(1) to denote any quantity that goes to

zero as N → ∞. We define a measure (or more precisely, a weight function)

to be a non-negative function ν : Z/NZ →

R+

depending on N, such that

En∈[N]ν(n) = 1 + oN→∞(1), thus ν is basically the density function of a

probability distribution on Z/NZ. We say that ν is Roth-pseudorandom if

for every δ 0 (independent of N) there exists cν(δ) 0 such that one has

the lower bound

Λ(f, f, f) ≥ cν(δ) + oN→∞;δ(1)

whenever f : Z/NZ → R is a function obeying the pointwise bound 0 ≤ f ≤

ν and the lower bound En∈Z/NZf ≥ δ, and oN→∞;δ(1) goes to zero as N →

∞ for any fixed δ. Thus, Roth’s theorem asserts that the uniform measure 1

is Roth-pseudorandom. Observe that if ν is Roth-pseudorandom, then any

subset A of [N/3] whose weighted density ν(A) := En∈Z/NZ1A(n)ν(n) is at

least δ will contain a non-trivial arithmetic progression of length three, if

N is suﬃciently large depending on δ, as we once again obtain a non-trivial

lower bound on Λ(1A, 1A, 1A) in this case. Thus it is of interest to establish

Roth-pseudorandomness for a wide class of measures.

Exercise 1.7.1. Show that if ν is Roth-pseudorandom, and η is another

measure which is “uniformly absolutely continuous” with respect to ν in the

sense that one has the bound η(A) ≤ f(ν(A)) + oN→∞(1) all A ⊂ Z/NZ

and some function f :

R+

→

R+

with f(x) → 0 as x → 0, then η is also

Roth-pseudorandom.

In view of the above exercise, the case of measures that are absolutely

continuous with respect to the uniform distribution is uninteresting: the

important case is instead when η is “singular” with respect to the uniform

measure, in the sense that it is concentrated on a set of density oN→∞(1)

with respect to uniform measure, as this will allow us to detect progressions

of length three in sparse sets.