1.7. Linear equations in primes 113
A model example to keep in mind of a candidate for a Roth-pseudoran-
dom measure is a random sparse measure of some small density 0 p 1,
in which each ν(n) is an independent random variable that equals 1/p with
probability p and 0 otherwise. The case p = 1/ log N can be thought of as
a crude model for the primes (cf. Cram´ er’s random model for the primes).
Recall that the form Λ(f, g, h) is controlled by the U
norm in the sense
that one has the inequality
|Λ(f, g, h)| ≤ f
whenever f, g, h: Z/NZ → C are bounded in magnitude by 1, and similarly
for permutations. Actually one has the slightly more precise inequality
|Λ(f, g, h)| ≤ f
as can easily be seen from the identity
(1.53) Λ(f, g, h) =
f g h
H¨ older’s inequality, and the Plancherel identity.
This suggests a strategy to establish the Roth-pseudorandomness of a
measure by showing that functions f dominated by that measure can be
norm by functions dominated instead by the uniform
measure 1. Indeed, we have
Lemma 1.7.3 (Criterion for Roth-pseudorandomness). Suppose we have a
measure ν with the following properties:
(i) (Control by
For any f, g, h: Z/NZ → R with the pointwise
bound |f|, |g|, |h| ≤ ν + 1, one has |Λ(f, g, h)| ≤ α( f u2(Z/NZ)) +
oN→∞(1), where α:
is a function with α(x) → 0 as
x → 0, and similarly for permutations.
(ii) (Approximation in
For any f : Z/NZ → R with the pointwise
bound 0 ≤ f ≤ ν, and any ε 0, there exists g : Z/NZ → R
with the pointwise bound 0 ≤ g ≤ 1 + on→∞;ε(1) such that f −
≤ ε + on→∞;ε(1).
Then ν is Roth-pseudorandom.
Proof. Let f : Z/NZ → C be such that 0 ≤ f ≤ ν and En∈Z/NZf ≥ δ. Let
ε 0 be a small number to be chosen later. We then use the decomposition
to split f = g + (f − g) with the above stated properties. Since
|En∈Z/NZf(n) − g(n)| ≤ f − g
≤ ε + on→∞;ε(1)