126 1. Higher order Fourier analysis

By the Chinese remainder theorem, the two residue conditions d|n and

d |n + 2 can be combined to a single residue condition for n modulo the

least common multiple lcm(d, d ) of d and d . If d and d are both small,

e.g., d, d ≤ N

1/10,

then this least common multiple is much less than N,

and in such a case one can compute the inner sum very precisely; as it turns

out, the main term in this estimate is multiplicative in d, d , which allows

the outer sum to be estimated using the techniques of multiplicative number

theory (and in particular, using the theory of the Riemann zeta function).

Unfortunately, for the bulk of the above sum, d and d are instead compara-

ble to N, and the least common multiple is typically of size N

2,

and then it

becomes extraordinarily diﬃcult to estimate the inner sum (and hence the

entire sum).

However, if we truncate the divisor sum (1.62) to restrict d to a range

such as d ≤ N

1/10,

then the situation improves substantially. This leads to

expressions such as

(1.63) ν(n) :=

1

log R

⎛

⎝

d|n;dR

μ(d) log

R

d

⎞2

⎠

or, more generally,

(1.64) ν(n) := log R

⎛

⎝

d|n

μ(d)ψ

log d

log R

⎞2

⎠

for some cutoff function ψ, where R is a small power25 of N; the expression

(1.63) corresponds to the case ψ(x) := max(1 − x, 0). The presence of the

square is to ensure that ν is non-negative, and the presence of the

1

log R

is a

normalisation factor to ensure that ν has mean close to 1. Such expressions

were essentially introduced to Selberg (as part of what is now known as the

Selberg sieve), although the sieve weight factors ψ(

log d

log R

) are usually mod-

ified slightly for the Selberg sieve (see [GrTa2006] for further discussion).

The correlation properties of the particular expression (1.63) were studied

intensively by Goldston and Yıldırım (see e.g. [GoPiYi2008]), and have

particularly sharp estimates, although for applications discussed here, one

can work instead with a smoother choice of cutoff ψ, which makes the re-

quired correlation estimates on ν easier to prove (but with slightly worse

bounds). Indeed, the required linear forms and correlation conditions can

be verified for (1.64) (or more precisely, a variant of ν in which the W -trick

25The exact power of N that one sets R equal to will depend on the complexity of the linear

forms and correlation conditions one needs. For counting progressions of length three, for instance,

one can take R = N

1/10.