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 sufficiently 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.
Previous Page Next Page