# On Sárközy’s theorem for shifted primes

Ben Green  Mathematical Institute
Radcliffe Observatory Quarter
Woodstock Road
Oxford OX2 6GG
England<EMAIL_ADDRESS>
###### Abstract.

Suppose that $A\subset\\{1,\dots,N\\}$ has no two elements differing by $p-1$,
$p$ prime. Then $|A|\ll N^{1-c}$.

The author is supported by a Simons Investigator grant and is grateful to the
Simons Foundation for their continued support.

###### Contents

  1. I Introduction
    1. 1 Introduction
    2. 2 Non-negative trigonometric polynomials
    3. 3 Sketch of the construction and plan of the paper
  2. II An approximant for the primes
    1. 4 Definition of the approximant
    2. 5 Proof of the Fourier approximation property
    3. 6 Completed approximants
  3. III Preliminaries to the main construction
    1. 7 Zeroes and density estimates
    2. 8 Periodic functions and Ramanujan series
    3. 9 Triple correlations of Ramanujan series
    4. 10 Triple correlations with characters
    5. 11 Damping characters
    6. 12 An archimedean construction
  4. IV The main construction
    1. 13 Construction of the damping term
    2. 14 Further bounds on correlations
    3. 15 The main construction and completion of the proof
  5. V Appendices
    1. A Postnikov character formula
    2. B Various estimates for arithmetic functions
    3. C Dirichlet characters
    4. D An exponential sum estimate
    5. E An explicit estimate for the $\Gamma$-function

##  Part I Introduction

###  1\. Introduction

Let $\delta(N)$ denote the relative density of the largest set
$A\subset\\{1,\dots,N\\}$ not containing two elements $a,a^{\prime}$ differing
by $p-1$, $p$ a prime (that is to say, $\delta(N)=\frac{|A|}{N}$). A well-
known 1978 result of Sárközy [30] is that
$\lim_{N\rightarrow\infty}\delta(N)=0$, that is to say the set
$\\{p-1:p\;\mbox{prime}\\}$ is a _set of recurrence_. In fact, Sárközy’s work
establishes a bound

$\delta(N)\ll(\log\log N)^{-2-o(1)}.$

This was subsequently improved by Lucier [15], who proved that

$\delta(N)\ll(\log\log N)^{-\omega(N)}$

for some function $\omega(N)\rightarrow\infty$. In 2010 Ruzsa and Sanders [29]
made a substantial advance on the problem by establishing that

$\delta(N)\ll e^{-c(\log N)^{1/4}}.$

The exponent of $\frac{1}{4}$ here was recently improved to $\frac{1}{3}$ by
Wang [36]. This is the best bound currently in the literature.

Ruzsa and Sanders remark in their paper that, even assuming the Generalised
Riemann Hypothesis (GRH), the best bound that seems to be available using
their methods is $\delta(N)\ll e^{-c(\log N)^{1/2}}$. They repeat a 1982
question of Ruzsa [27], asking whether a bound of the shape $\delta(N)\ll
N^{-c}$ can be proven under such an assumption. Our main result in this paper
is a bound of this strength, without any unproven hypothesis.

######  Theorem 1.1.

Let $A\subset\\{1,\dots,N\\}$ be a set such that $A-A$ contains no number of
the form $p-1$, $p$ a prime. Then $|A|\ll N^{1-c}$ for some $c>0$.

We remark that essentially the same arguments would prove the analogous result
with $p+1$ replacing $p-1$, and that trivial examples show that no such result
is possible for $p+a$ with any fixed $a$ other than $\pm 1$.

We do not give an explicit value for $c$, but one could be obtained from our
arguments using forthcoming explicit zero-density estimates of Thorner and
Zaman [35]. The value of $c$ thus obtained would certainly be extremely small.

If one assumes GRH, it is possible to establish Theorem 1.1 with any
$c<\frac{1}{12}$. Moreover, the argument simplifies dramatically (it is less
than one third the length of the unconditional one). The interested reader may
find a writeup of this argument in [8].

We will give an outline of our method for proving Theorem 1.1 in the next
section. The key new development is that we eschew the density increment
strategy common to all of the works cited above, and instead study the so-
called _van der Corput_ property, which is strictly stronger than that of
being a set of recurrence, directly.

Let us recall what the van der Corput property for the shifted primes is. For
each $N$, set

$\gamma(N):=\inf_{T\in\mathscr{T}_{N}}a_{0},$

where $\mathscr{T}_{N}$ denotes the collection of all cosine polynomials

$T(x)=a_{0}+\sum_{p\leqslant N}a_{p-1}\cos(2\pi(p-1)x)$

where $a_{i}\in\mathbf{R}$ and which satisfy $T(0)=1$, $T(x)\geqslant 0$ for
all $x$. The van der Corput property is that $\gamma(N)\rightarrow 0$ as
$N\rightarrow\infty$. We note that the van der Corput property may be
formulated in different ways, and the above formulation is due to Kamae and
Mendès France [13] and Ruzsa [26]. Montgomery’s _Ten Lectures_ [18, Chapter 2]
provides a good discussion.

We will show the following result.

######  Theorem 1.2.

We have $\gamma(N)\ll N^{-c}$ for some absolute constant $c>0$. That is, there
is a cosine polynomial

$T(x)=a_{0}+\sum_{p\leqslant N}a_{p-1}\cos(2\pi(p-1)x)$

where $a_{i}\in\mathbf{R}$, $T(0)=1$, $T(x)\geqslant 0$ for all $x$ and
$a_{0}\ll N^{-c}$.

One may of course define the quantities $\delta(N)$ and $\gamma(N)$ with
respect to an arbitrary set, rather than just for the shifted primes. In this
general setting, roughly speaking we have $\delta\lessapprox\gamma$. More
precisely, it follows from [18, Chapter 2, Lemma 1] that one has
$\delta(N)\leqslant(1+\frac{H}{N})\gamma(H)$, so in particular
$\delta(N)\leqslant 2\gamma(N)$. We will give a self-contained proof of this
latter fact (for shifted primes, but the argument is general) in Section 2.
Bourgain [2] gave an example showing that inequalities in the opposite
direction do not hold in general, that is to say being a van der Corput set is
strictly stronger than being a recurrent set. See also [16] for related
material.

We now revert to the specific setting of the shifted primes. Regarding
previous results in the direction of Theorem 1.2, Kamae and Mendès France
showed that the shifted primes have the van der Corput property, but gave no
explicit bounds. Currently, the best-known upper bound for $\gamma(N)$ seems
to be that of Slijepčević [31], who showed that $\gamma(N)\leqslant(\log
N)^{-1+o(1)}$.

Finally, we note that the best-known lower bound for $\delta(N)$ is rather
small, though not as small as one might naïvely guess. This is a result of
Ruzsa [28], who showed that

$\delta(N)\geqslant\frac{1}{N}e^{(\log 2+o(1))\frac{\log N}{\log\log N}}.$
(1.1)

Note that this is asymptotically smaller than $N^{-1+\varepsilon}$ for any
$\varepsilon>0$, and one would expect this to be the true behaviour of
$\delta(N)$. In fact, (1.1) may be close to the true bound. I believe (and see
[31]) that no better lower bound is known for $\gamma(N)$.

Proving upper bounds of this strength is surely hopeless. Indeed, if one could
show that $\delta(N)<N^{-1/2-c}$ for some $c>0$ then, taking $A$ to be the
multiples of $q$ up to $q^{2-c^{\prime}}$, one sees that there is a prime
$p\leqslant q^{2-c^{\prime}}$ congruent to $1(\operatorname{mod}\,q)$. Such a
bound is beyond what is currently known, even on GRH.

_Acknowledgements._ The initial impetus for thinking about the van der Corput
property came after the author became aware that the Lovász $\theta$-function
can be used to show that any set $A\subset\mathbf{Z}/q\mathbf{Z}$ of size
$>\sqrt{q}$ contains two elements differing by a square
$(\operatorname{mod}\,q)$, where $q$ is any product of distinct primes
$1(\operatorname{mod}\,4)$. This connection was also observed by Naslund [20],
who says it was known to Ruzsa (unpublished). I thank Zachary Chase for
interesting conversations on this topic and for presenting Lovász’s paper to
me in an easily digestible form which made the connection to the van der
Corput property clear. I would also like to thank Ofir Gorodetsky, Lasse
Grimmelt, Emmanuel Kowalski, Valeriya Kovaleva, James Maynard, Eric Naslund,
Joni Teräväinen and Jesse Thorner for various helpful comments and
correspondence.

_Notation._ In this section we introduce notation which is _global_ to the
paper, most of which is standard. There will be many further pieces of
notation of a more local nature which we will introduce later on.

Our use of asymptotic notation such as $O()$, $o()$, $\ll$ and $\gg$ is
standard in analytic number theory. Sometimes we will add subscripts to this
notation; thus, for example, $O_{B}(1)$ means a constant depending only on
some parameter $B$. We will use the rougher notation $X\lessapprox Y$ to mean
$X\ll N^{o(1)}Y$, where here $N$ is a global parameter throughout the paper
(we are interested in subsets of $\\{1,\dots,N\\}$). We write $X=\tilde{O}(Y)$
to mean the same thing. Often, but not always, the $N^{o(1)}$ term will be
just a fixed power of $\log N$. We will remind the reader of this notation
when we first use it.

We will use the following standard arithmetic functions: the Möbius function
$\mu$, Euler’s totient function $\phi$, the von Mangoldt function $\Lambda$,
and its restriction to primes $\Lambda^{\prime}$ (that is, the proper prime
powers $p^{i}$, $i\geqslant 2$, are removed from the support). Given positive
integers $a,b$ we write $(a,b)$ for their gcd and $[a,b]$ for their lcm.

A slightly unusual notation we will use is to write $\operatorname{denom}(x)$
for the denominator of the rational number $x$ when written in lowest terms,
or in other words the least positive integer $q$ such that $qx\in\mathbf{Z}$.
The quantity $\operatorname{denom}(x)$ is well-defined for
$x\in\mathbf{Q}/\mathbf{Z}$, which is the context in which we will use it.

Given $\theta\in\mathbf{R}$, we write $e(\theta)=e^{2\pi i\theta}$ and
$\|\theta\|$ for the distance from $\theta$ to the nearest integer. There is
no other use for $\|\cdot\|$ in the paper, so we do not need a more pedantic
notation such as $\|\cdot\|_{\mathbf{R}/\mathbf{Z}}$.

If $q$ is a positive integer, we write
$c_{q}(n):=\sum_{a\in(\mathbf{Z}/q\mathbf{Z})^{*}}e(\frac{an}{q})$, the
Ramanujan sum.

If $p$ is a prime and $n$ is a non-zero integer, we write $v_{p}(n)$ to be the
power of $p$ dividing $n$, and extend this to a function
$v_{p}:\mathbf{Q}\setminus\\{0\\}\rightarrow\mathbf{Z}$ in the usual way,
defining $v_{p}(\frac{a}{b}):=v_{p}(a)-v_{p}(b)$. We will, by a slight abuse
of notation, define $v_{p}$ on $(\mathbf{Z}/p^{n}\mathbf{Z})\setminus\\{0\\}$
by taking $v_{p}(x)=v_{p}(\overline{x})$ for any $\overline{x}\in\mathbf{Z}$
projecting to $x$ under the natural map.

In several later sections of the paper we make considerable use of the
notation $F^{+}(n):=F(n+1)$, $F^{-}(n):=F(n-1)$. Whilst I acknowledge that
this is a somewhat unattractive and nonstandard piece of notation, it is
essential in order to keep expressions manageable later on.

Finally, in a number of sections we will see the constant $M$, whose
definition may be found at (11.3) and which takes the value $M=7\cdot
3^{6}\cdot 2^{22993}$. The precise value of this constant is not especially
important provided that it is large enough, but we choose to fix a value for
definiteness.

###  2\. Non-negative trigonometric polynomials

Rather than work with the van der Corput property as defined in the
introduction directly, we instead deduce bounds on $\delta(N)$ and $\gamma(N)$
from the following proposition, which encodes a property easily seen to be
equivalent to the van der Corput property.

######  Proposition 2.1.

Suppose that there is a function $\Psi:\mathbf{Z}\rightarrow\mathbf{R}$ and
$\delta_{1},\delta_{2}>0$ with the following properties:

  1. (1)

$\Psi(n)$ is supported on the set $\\{p-1:\mbox{$p$ prime}\\}$;

  2. (2)

$\sum_{n=1}^{N}\Psi(n)\cos(2\pi n\theta)\geqslant-\delta_{1}N$, for all
$\theta\in\mathbf{R}/\mathbf{Z}$;

  3. (3)

$\sum_{n=1}^{N}\Psi(n)\geqslant\delta_{2}N$.

Then $\delta(N)\leqslant\frac{2\delta_{1}}{\delta_{1}+\delta_{2}}$ and
$\gamma(N)\leqslant\frac{\delta_{1}}{\delta_{1}+\delta_{2}}$. Conversely,
there is a function $\Psi$ satisfying (1), (2) and (3) above and such that
$\gamma(N)=\frac{\delta_{1}}{\delta_{1}+\delta_{2}}$.

_Remarks._ An immediate corollary of this is that $\delta(N)\leqslant
2\gamma(N)$.

We remark that no specific properties of the set $\\{p-1:\mbox{$p$ prime}\\}$
are used in this section; the arguments and conclusions apply to recurrence
and van der Corput properties of general sets.

###### Proof of Proposition 2.1.

We begin with the first two statements, the bounds on $\delta(N)$ and
$\gamma(N)$. We will use Fourier analysis $(\operatorname{mod}\,2N)$. Suppose
that $A\subset\\{1,\dots,N\\}$ does not contain any elements differing by
$p-1$, where $p\leqslant N$ is a prime. Then it does not contain any elements
differing modulo $2N$ by by $p-1$, $p\leqslant N$ a prime.

Now we have

$\displaystyle(\delta_{1}$ $\displaystyle+\delta_{2})N|A|^{2}$
$\displaystyle\leqslant\sum_{r\in\mathbf{Z}/2N\mathbf{Z}}|\sum_{n=1}^{N}1_{A}(n)e(\frac{rn}{2N})|^{2}\big{(}\delta_{1}N+\Re\sum_{x=1}^{N}\Psi(x)e(\frac{rx}{2N})\big{)},$
(2.1)

since the term with $r=0$ is $\geqslant(\delta_{1}+\delta_{2})|A|^{2}N$ by (3)
and all other terms are non-negative by (2). On the other hand, we have

$\sum_{r\in\mathbf{Z}/2N\mathbf{Z}}|\sum_{n=1}^{N}1_{A}(n)e(\frac{rn}{2N})|^{2}=2N\\!\\!\\!\\!\\!\\!\sum_{m\equiv
n(\mbox{\scriptsize mod}\,2N)}\\!\\!\\!\\!\\!1_{A}(m)1_{A}(n)=2N|A|,$ (2.2)

whilst

$\displaystyle\sum_{r\in\mathbf{Z}/2N\mathbf{Z}}$
$\displaystyle|\sum_{n=1}^{N}1_{A}(n)e(\frac{rn}{2N})|^{2}\sum_{x=1}^{N}\Psi(x)e(\frac{rx}{2N})$
$\displaystyle=2N\sum_{m=1}^{N}\sum_{n=1}^{N}\sum_{x=1}^{N}1_{m-n+x\equiv
0(\mbox{\scriptsize mod}\,2N)}1_{A}(m)1_{A}(n)\Psi(x)=0,$

because $\Psi$ is supported on $p-1$, $p$ prime, and $A$ does not contain two
elements differing by such a number $(\operatorname{mod}\,2N)$.

Taking real parts and combining this with (2.1), (2.2) gives
$(\delta_{1}+\delta_{2})|A|^{2}N\leqslant 2\delta_{1}N^{2}|A|$, from which we
obtain $|A|\leqslant\frac{2\delta_{1}}{\delta_{1}+\delta_{2}}N$, as required.

For the van der Corput property, consider

$T(x):=(\delta_{1}N+\sum_{n=1}^{N}\Psi(n))^{-1}(\delta_{1}N+\sum_{n=1}^{N}\Psi(n)\cos(2\pi
nx)).$

It is clear that $T(0)=1$, $T(x)\geqslant 0$ for all $x$ and finally

$a_{0}=\frac{\delta_{1}N}{\delta_{1}N+\sum_{n=1}^{N}\Psi(n)}\leqslant\frac{\delta_{1}}{\delta_{1}+\delta_{2}},$

which shows that indeed
$\gamma(N)\leqslant\frac{\delta_{1}}{\delta_{1}+\delta_{2}}$.

Finally we turn to the converse statement. Suppose we have a cosine polynomial
$T(x)=a_{0}+\sum_{p\leqslant N}a_{p-1}\cos(2\pi(p-1)x)$ where
$a_{i}\in\mathbf{R}$, $T(0)=1$, $T(x)\geqslant 0$ for all $x$ and
$a_{0}=\gamma(N)$. Define $\Psi(n)$ to be $a_{p-1}$ if $n=p-1$, $p\leqslant N$
a prime, and $0$ otherwise. Then property (1) is satisfied. Since
$T(x)=a_{0}+\sum_{n\leqslant N}\Psi(n)\cos(2\pi nx)$, the assumption that
$T(x)\geqslant 0$ implies (2), with $\delta_{1}:=\frac{a_{0}}{N}$. The
assumption that $T(0)=1$ implies (3), with $\delta_{2}:=\frac{1-a_{0}}{N}$.
The claim follows. ∎

From this, we see that Theorem 1.1 and Theorem 1.2 are both consequences of
the following result (which is in fact equivalent to Theorem 1.2).

######  Theorem 2.2.

There are absolute constants $0<\kappa_{2}<\kappa_{1}$ and a function
$\Psi:\mathbf{Z}\rightarrow\mathbf{R}$ with the following properties:

  1. (1)

$\Psi(n)$ is supported on the set $\\{p-1:\mbox{$p$ prime, $p\leqslant
N$}\\}$;

  2. (2)

$\sum_{n=1}^{N}\Psi(n)\cos(2\pi\theta n)\geqslant-N^{1-\kappa_{1}}$, for all
$\theta\in\mathbf{R}/\mathbf{Z}$;

  3. (3)

$\sum_{n=1}^{N}\Psi(n)\geqslant N^{1-\kappa_{2}}$.

The proof of this result occupies the rest of the paper.

###  3\. Sketch of the construction and plan of the paper

####  3.1. Sketch of the construction

The main business of the paper is the construction of the function $\Psi$ in
Proposition 2.1.

The construction is complicated, so we begin by explaining roughly where it
comes from. The starting point is to observe that

$\Psi_{0}(n):=\Lambda^{\prime}(n+1)\Lambda^{\prime}(n-1)\tau(n)^{2}(1-\frac{|n|}{N})_{+}$
(3.1)

ought to have something like the desired properties, where $\Lambda^{\prime}$
is the von Mangoldt function restricted to primes, and $\tau$ is the divisor
function. To see why, consider how one would expect this function to behave on
progressions $n\equiv a(\operatorname{mod}\,p)$, where $p$ is a prime of
moderate size. The $\Lambda^{\prime}(n+1)$ term will be uniformly distributed
across $a\not\equiv-1(\operatorname{mod}\,p)$, whilst the
$\Lambda^{\prime}(n-1)$ term will be uniformly distributed where $a\not\equiv
1(\operatorname{mod}\,p)$. Thus one expects, assuming that
$\Lambda^{\prime}(n+1)$ and $\Lambda^{\prime}(n-1)$ behave suitably
independently, that $\Lambda^{\prime}(n-1)\Lambda^{\prime}(n+1)$ is uniformly
distributed where $a\not\equiv\pm 1(\operatorname{mod}\,p)$. The symmetry
about 0 here guarantees that the exponential sum of
$\Lambda^{\prime}(n+1)\Lambda^{\prime}(n-1)$ at points $\frac{r}{p}$ ought to
be essentially real-valued. The divisor function $\tau(n)$ has roughly twice
the weight on $a\equiv 0(\operatorname{mod}\,p)$ as it does on each of the
other values of $a$ (for each divisor $d$ of $n/p$, we get both $d$ and $pd$
as divisors of $n$). Very roughly, this leads one to expect that $\Psi_{0}(n)$
has total weight proportional to $\nu(a)$ on $n\equiv
a(\operatorname{mod}\,p)$, where $\nu(0)=4$, $\nu(\pm 1)=0$ and $\nu(a)=1$ for
all other $a$. This weight has exponential sum at $\frac{r}{p}$ which is both
real _and_ positive, which is a very helpful step towards proving (2).
Moreover, by considering the multiplicative behaviour of the functions
concerned, one can hope for a similar statement at points $\frac{b}{q}$, $q$
squarefree. Finally, the tent function $(1-\frac{|n|}{N})_{+}$ has non-
negative Fourier transform (the Fejér kernel) and so one might expect
$\Psi_{0}$ to satisfy something like property (2).

Unfortunately, we cannot make any aspect of the preceding discussion rigorous.
Indeed, the function $\Lambda^{\prime}(n+1)\Lambda^{\prime}(n-1)$ may, for all
we know, be essentially zero (this is the twin prime conjecture) and so
certainly understanding the asymptotics of its exponential sum is hopeless.

Our actual construction of $\Psi$ is inspired by (3.1) but includes various
truncated and modified versions of the arithmetic functions involved as well
as some extra terms. Roughly, we will construct it as a product

$\Psi(n):=\Lambda^{\prime}(n+1)\Lambda_{Q}(n-1)H_{Q}(n)D_{Q^{\prime}}(n)E(n)w(n).$
(3.2)

Here, $Q,Q^{\prime}$ are certain parameters to be specified later, with
$Q^{\prime}<Q$. Let us give a very brief overview of what each of these terms
are and their purpose.

The $\Lambda_{Q}$ term is a kind of Fourier-truncation of the von Mangoldt
function given by

$\Lambda_{Q}(n):=\sum_{q\leqslant Q}\frac{\mu(q)}{\phi(q)}c_{q}(n),$ (3.3)

where $c_{q}(n):=\sum_{a\in(\mathbf{Z}/q\mathbf{Z})^{*}}e(\frac{an}{q})$ is a
Ramanujan sum. This function models the expected distribution of $\Lambda$ on
progressions but is much easier to analyse than $\Lambda$ itself. It was used
by Heath-Brown [10] to give an alternative proof of the ternary Goldbach
conjecture.

The factor $H_{Q}$ behaves (somewhat) like a Fourier-truncated truncated
version of $\tau^{2}$. It is defined as

$H_{Q}(n):=\sum_{q\leqslant
Q}\eta(q)c_{q}(n)\quad\mbox{where}\quad\eta(q):=\mu^{2}(q)\prod_{p|q}\frac{3}{p+3}.$
(3.4)

Thus one should think of $\Lambda^{\prime}(n+1)\Lambda_{Q}(n-1)H_{Q}(n)$ as a
kind of Fourier-truncated variant of the function
$\Lambda(n+1)\Lambda(n-1)\tau(n)^{2}$ discussed at the beginning of the
section. We discussed, on a heuristic level, the distribution of this latter
function in progressions of small modulus (prime, in the discussion, but we
need the general case), and a similar heuristic discussion applies to
$\Lambda(n+1)\Lambda_{Q}(n-1)H_{Q}(n)$. This still assumes that $\Lambda$ is
well-distributed in progression of small modulus, where “small” means up to a
power of $N$. Unfortunately, nothing like this is known to be true: possible
zeros near to $\Re s=1$ of Dirichlet $L$-functions $L(s,\chi)$ can
significantly skew the distribution.

To account for these irregularities we introduce the term $D_{Q^{\prime}}$,
which we call a _damping term_. This term has the form

$D_{Q^{\prime}}(n)=\sum_{r\leqslant
Q^{\prime}}\sum_{b\in\mathbf{Z}/r^{3}\mathbf{Z}}\alpha_{b,r}r^{\frac{5}{6}}1_{r|n}e(\frac{bn}{r^{3}}),$

where the $\alpha_{b,r}$ are non-negative real numbers summing to $1$. (There
is some scope for varying the choice of the numbers $\frac{5}{6}$ and $3$, but
it is crucial that $\frac{5}{6}<1$.) Its role is essentially to ensure that
the irregularities in distribution just discussed still lead to non-negative
Fourier coefficients.

The construction of $D_{Q^{\prime}}(n)$ is rather complicated. It is defined
in Section 13 as an infinite series (13.7), but this definition depends on
material developed in several earlier sections. Roughly, the main
contributions to the $\alpha_{b,r}$ come from characters $\chi$ which have
zeroes particularly close to $\Re s=1$. The need for the twists by
$e(\frac{bn}{r^{3}})$ arises because of the properties of Dirichlet characters
to prime power moduli with large exponent, in particular the fact that these
can behave like additive characters on large subgroups.

The function $E(n)$ is either the constant function $1$ or an indicator
$1_{q_{1}|n}$. The latter case arises, essentially, when there is an
exceptional character $\chi_{1}$ of conductor $q_{1}$, that is to say a
character such that $L(s,\chi)$ has a zero very close to $s=1$.

Finally, $w(n)$ is an “archimedean” factor. The tent function
$w(n)=(1-\frac{|n|}{N})_{+}$ turns out not to work, essentially because one
needs the exponential sum of $n^{\rho-1}w(n)$ to be pointwise dominated by
that of $w(n)$, for $\rho$ a possible zero of some $L(s,\chi)$. This is not
the case for the tent function, since the exponential sum of $w(n)$ in that
case (the Fejér kernel) has zeroes. We are instead forced to make a much more
elaborate construction using properties of the function
$W(x)=x^{-\frac{1}{2}}e^{-x}$, whose Fourier transform has a relatively slow
and controlled decay.

####  3.2. Plan of the paper

The main business of the paper is to properly define $\Psi$ as given by (3.2)
and to show that it satisfies the conclusions of Theorem 2.2. This is a
lengthy task.

Part II of the paper may be read independently of the rest of the paper and
may plausibly be useful elsewhere. In this section we construct another
approximant $\Lambda_{\sharp,Q,\sigma_{0}}$ to $\Lambda$. Unlike
$\Lambda_{Q}$, this approximant sees possible nontrivial zeroes with
$\Re\rho\geqslant 1-\sigma_{0}$ up to height $Q$ of all Dirichlet
$L$-functions $L(s,\chi)$ with $\chi$ of conductor $\leqslant Q$. Including
this information about zeros makes $\Lambda_{\sharp,Q,\sigma_{0}}$ a more
complicated object than $\Lambda_{Q}$, but it allows us to rigorously show
that exponential sums $\sum_{n\leqslant
N}(\Lambda(n)-\Lambda_{\sharp,Q,\sigma_{0}}(n))e(n\theta)$ enjoy a _power
saving_ $\lessapprox NQ^{-\frac{1}{6}}$ over the trivial bound of $N$,
uniformly in $\theta$. This allows us to reduce matters to the analysis of,
instead of $\Psi$, the modification $\Psi^{\prime}$ in which $\Lambda(n+1)$ is
replaced by $\Lambda_{\sharp,Q,\sigma_{0}}(n+1)$, for suitable $Q,\sigma_{0}$.

Part III of the paper assembles various preliminaries for the main argument.
In Section 7, we describe some zero-density estimates and their consequences.
The material here is similar to what one would find in a proof of Linnik’s
theorem on the least prime in a progression, which is not surprising since
Theorem 1.1 is easily seen to imply that the progression
$1(\operatorname{mod}\,q)$ contains a prime of size $q^{O(1)}$. What we need
here is a little stronger than what is required for Linnik’s theorem, where
the modulus is fixed. Our main reference is Bombieri’s book [1].

Section 8 discusses periodic functions on $\mathbf{Z}$, their rational Fourier
expansions, and the notion of positivity. It also introduces some of the key
examples and functions in the paper such as $H_{Q}$ as described above.

Section 9 and the related Section 10 are rather long and technical, though
crucial to the paper. They are concerned with passing between truncated series
$\sum_{q\leqslant Q}\alpha(q)c_{q}(n)$, which are good for Fourier analysis,
and untruncated series such as $\sum_{q|Q!}\alpha(q)c_{q}(n)$, which are much
easier to understand combinatorially. Section 9 concerns triple products of
such series and their shifts, and in Section 10 characters are introduced as
well. Despite the technical nature of these sections, the statement of the
main result of Section 9, Proposition 9.1, is self-contained and potentially
applicable in other contexts.

Section 11 develops material necessary for the construction of the damping
term $D_{Q^{\prime}}$. A crucial input here is the Postnikov character formula
which, due to the lack of a reference suitable for our purposes, is developed
from first principles in Appendix A.

Section 12 constructs the archimedean weight $w(n)$, modelled on
$x^{-\frac{1}{2}}e^{-x}$. The main result here, Proposition 12.1, is self-
contained and is also potentially of some use elsewhere.

Finally, we come to Part IV, where the function $\Psi$ is rigorously
constructed and shown to have the desired properties. The construction of the
damping function $D_{Q^{\prime}}$ is probably the most conceptually
interesting part of this analysis. The fully detailed definition of $\Psi$ is
given in Definition 15.1, and finally in the rest of that section it is shown
that $\Psi$ satisfies Theorem 2.2.

_Some comments for the reader._ I have endeavoured to make key intermediate
results self-contained where possible, so that it is possible to understand
the basic structure of the argument without reading all the proofs. There are
a very large number of hyperlinks in the paper to facilitate recall of key
definitions and intermediate results. Consequently, I recommend that anyone
interested in reading the paper use a suitable PDF viewer rather than the
printed version.

##  Part II An approximant for the primes

The objective of this part of the paper is define certain approximants
$\Lambda_{\sharp}$ to the von Mangoldt function $\Lambda$ which are very close
to it in Fourier space. The definition (which requires a little setting up)
may be found in Definition 4.4, and the key result is Proposition 4.6. Recall
that $N$ is a large integer, a global parameter in the paper, and that
$X\lessapprox Y$ means that $X\ll N^{o(1)}Y$.

###  4\. Definition of the approximant

We adopt the following fairly standard convention in analytic number theory:
$\rho$ denotes a nontrivial zero of some $L$-function, and we write
$\rho=\beta+i\gamma$; somewhat less standardly, we always write
$\sigma:=1-\beta$, thus $\Re\rho=1-\sigma$.

######  Definition 4.1.

Let $Q$ be a positive real parameter, and let $\sigma_{0}>0$. Write
$\Xi_{Q}(\sigma_{0})\subset\mathbf{C}$ for the multiset consisting of all
$\rho=\beta+i\gamma=1-\sigma+i\gamma$ with $\sigma\leqslant\sigma_{0}$ and
$|\gamma|\leqslant Q$ which are zeros of some Dirichlet $L$-function
$L(s,\chi)$ with conductor at most $Q$.

_Remarks._ Later on we will fix $\sigma_{0}=\frac{1}{48}$, a convenient but
not optimal choice which works for all our arguments.

When we say that $\Xi_{Q}(\sigma_{0})$ is a multiset, we mean the following.
If $\rho$ occurs as a zero of multiplicity $r_{i}$ for primitive Dirichlet
characters $\chi_{i}$, $i=1,\dots,m$, then $\rho$ should appear in
$\Xi_{Q}(\sigma_{0})$ with multiplicity $r_{1}+\dots+r_{m}$. Conjecturally,
every $\rho$ is a simple zero of a unique $L(s,\chi)$ (and so
$\Xi_{Q}(\sigma_{0})$ is simply a set) but this is not known. In fact
$\Xi_{Q}(\sigma_{0})$ is conjecturally _empty_ if $\sigma_{0}<\frac{1}{2}$. If
$\rho\in\Xi_{Q}(\sigma_{0})$, we write $\chi_{\rho}$ for the primitive
Dirichlet character associated to it.

Suppose $\psi$ is a Dirichlet character (not necessarily primitive) to modulus
$r$. Recall that the _Gauss sum_ $\tau(\psi)$ is defined by

$\tau(\psi):=\sum_{b\in(\mathbf{Z}/r\mathbf{Z})^{*}}\psi(b)e(\frac{b}{r}).$

The following three definitions are important ones in the paper.

######  Definition 4.2.

Let $\chi$ be a primitive Dirichlet character to modulus $q$. Let $r$ be a
positive integer and let $b\in(\mathbf{Z}/r\mathbf{Z})^{*}$. Then if $q|r$ we
define

$c_{\chi}(b,r):=\frac{1}{\phi(r)}\chi(b)\mu(\frac{r}{q})\overline{\chi(\frac{r}{q})}\overline{\tau(\chi)},$
(4.1)

and set $c_{\chi}(b,r)=0$ if $q\nmid r$.

######  Definition 4.3.

Let $\chi$ be a primitive Dirichlet character to modulus $q$. Then we define

$F_{\chi,Q}(n):=\sum_{\begin{subarray}{c}q|r\\\ \frac{r}{q}\leqslant
Q\end{subarray}}\sum_{b\in(\mathbf{Z}/r\mathbf{Z})^{*}}c_{\chi}(b,r)e(\frac{bn}{r}),$
(4.2)

where $c_{\chi}$ is as given in (4.1).

Finally, we can define the approximants $\Lambda_{\sharp}$ themselves.

######  Definition 4.4.

If $n$ is a positive integer, define

$\Lambda_{\sharp,Q,\sigma_{0}}(n):=\Lambda_{Q}(n)-\sum_{\rho\in\Xi_{Q}(\sigma_{0})}n^{\rho-1}F_{\chi_{\rho},Q}(n).$
(4.3)

_Remarks._ As we progress with our analysis we will understand more about why
these are relevant definitions. For instance, we will see in Lemma 6.2 that
$F_{\chi,Q}$ can be thought of as a kind of “Fourier-truncated” version of
$\overline{\chi}$ restricted to numbers with no prime factors $\leqslant Q$.

When $\chi=\chi_{0}$, the (primitive) prinicipal character, we have
$c_{\chi}(b,r)=\frac{\mu(r)}{\phi(r)}$ and so

$F_{\chi_{0},Q}(n)=\Lambda_{Q}(n),$ (4.4)

where $\Lambda_{Q}$ is the approximant (3.3). Given this, it is possible and
often convenient to write

$\Lambda_{\sharp,Q,\sigma_{0}}(n)=\sum_{\rho\in\Xi_{Q}^{*}(\sigma_{0})}\varepsilon_{\rho}n^{\rho-1}F_{\chi_{\rho},Q}(n).$
(4.5)

Here, we set $\Xi_{Q}^{*}(\sigma_{0})=\Xi_{Q}(\sigma_{0})\cup\\{1\\}$ and we
adopt the convention that $\chi_{1}$ is the principal character (of which $1$
is of course a pole, not a zero), and $\varepsilon_{\rho}=-1$ or $1$ according
as $\rho$ is a zero or a pole (i.e. $\rho=1$).

I am not aware of $\Lambda_{\sharp,Q,\sigma_{0}}$ having appeared previously
in the literature. Teräväinen [34, Definition 5.2] makes a vaguely related
definition (but only using the zeros of $\zeta$), and there is some similarity
with the work of Pintz [22, 23] on the exceptional set for the Goldbach
problem.

As a final remark, we note that on the assumption of GRH we have
$\Lambda_{\sharp,Q,\sigma_{0}}=\Lambda_{Q}$ for all $\sigma_{0}<\frac{1}{2}$,
since $\Xi_{Q}(\sigma_{0})$ is empty.

######  Lemma 4.5.

$\Lambda_{\sharp,Q,\sigma_{0}}$ is real-valued.

###### Proof.

One may check using $\tau(\overline{\chi})=\chi(-1)\overline{\tau(\chi)}$ that
$c_{\overline{\chi}}(b,r)=\overline{c_{\chi}(-b,r)}$ and thus that

$F_{\overline{\chi},Q}=\overline{F_{\chi,Q}}.$ (4.6)

Suppose that $\rho\in\Xi_{Q}(\sigma_{0})$, thus $L(\rho,\chi_{\rho})=0$. Then
$L(\overline{\rho},\overline{\chi_{\rho}})=0$ (note that
$L(s,\chi)=\overline{L(\overline{s},\overline{\chi})}$, since both sides are
meromorphic and they agree for $\Re(s)>1$). That is,
$\overline{\rho}\in\Xi_{Q}(\sigma_{0})$ and
$\chi_{\overline{\rho}}=\overline{\chi_{\rho}}$ . It follows from this and
(4.6) that
$n^{\rho-1}F_{\chi_{\rho},Q}(n)=\overline{n^{\overline{\rho}-1}F_{\chi_{\overline{\rho}},Q}(n)}$,
thus the summands in (4.3) come in conjugate pairs. ∎

Finally we state the key Fourier approximation property.

######  Proposition 4.6.

Suppose that $\sigma_{0}\leqslant\frac{1}{9}$ and that $Q\leqslant
N^{\sigma_{0}}$. Then we have

$|\sum_{n\leqslant
N}(\Lambda(n)-\Lambda_{\sharp,Q,\sigma_{0}}(n))e(n\theta)|\lessapprox
NQ^{-\frac{1}{6}}$

and

$|\sum_{n\leqslant
N}(\Lambda^{\prime}(n)-\Lambda_{\sharp,Q,\sigma_{0}}(n))e(n\theta)|\lessapprox
NQ^{-\frac{1}{6}}$

uniformly for $\theta\in\mathbf{R}/\mathbf{Z}$.

Here, note that the second statement (which is the one we will need later on)
follows easily from the first, since $\sum_{n\leqslant
N}|\Lambda(n)-\Lambda^{\prime}(n)|\lessapprox N^{\frac{1}{2}}$.

###  5\. Proof of the Fourier approximation property

The business of this section is to prove Proposition 4.6. The basic idea will
be to consider the cases of $\theta$ close to a rational with small
denominator (the “major arcs”) and $\theta$ not close to a rational with small
denominator (the “minor arcs”) separately. In other words, we use the circle
method. The heart of the argument begins in Subsection 5.3 below.

We will need various ingredients in the proof, which we assemble now before
moving on to the main argument.

####  5.1. Zero-density estimates

We have the following result, sometimes known as a grand log-free zero-density
estimate.

######  Proposition 5.1.

We have, uniformly for $\alpha\geqslant\frac{4}{5}$,

$\\#\\{\rho\in\Xi_{Q}(\frac{1}{5}):\Re\rho\geqslant\alpha\\}\ll
Q^{8(1-\alpha)}.$ (5.1)

Here, zeroes are counted with multiplicity.

This follows from [12, Theorem 1] (with any constant larger than $6$ in place
of $8$). That zeroes are counted with multiplicity is not explicitly stated
there (or indeed in many results of this type) but the proofs do give this.
Any result of this general type (that is, a “log-free” zero-density estimate
over all moduli) would be suitable for our purposes. Jutila (_ibid._)
describes some previous results of this type and remarks that the first such
estimates were due to work of Fogels [5] and Gallagher [6], and can be found
explicitly in the latter paper.

_Remark._ In Section 7, we will need more refined estimates coming from the
phenomenon of “exceptional zero repulsion”; see Proposition 7.5.

A consequence of Proposition 5.1 this is the following convergence result.

######  Lemma 5.2.

Suppose that $Q\leqslant N^{\frac{1}{9}}$. Then
$\sum_{\rho\in\Xi_{Q}(\frac{1}{5})}N^{\Re\rho-1}\ll 1$.

###### Proof.

For $k\geqslant 1$, write $\Xi^{(k)}_{Q}$ for the multiset of all
$\rho\in\Xi_{Q}(\frac{1}{5})$ for which $k-1<(1-\Re\rho)\log Q\leqslant k$. By
Proposition 5.1, $|\Xi_{Q}^{(k)}|\ll e^{8k}$ for all $k$. Summing over $k$, we
obtain

$\sum_{\rho\in\Xi_{Q}}N^{\Re\rho-1}\ll\sum_{k\geqslant 1}N^{-\frac{k-1}{\log
Q}}e^{8k}\leqslant\sum_{k\geqslant 1}e^{-9k}e^{8k}\ll 1.$

∎

####  5.2. Exponential sum estimates

We will need the following estimate for exponential sums twisted by
$n^{\rho-1}=n^{\beta}e^{i\gamma\log n}$. This is material of a standard type,
but it seems hard to locate a usable reference in the literature.

######  Proposition 5.3.

Suppose that $\rho=\beta+i\gamma$, where $\frac{1}{2}\leqslant\beta\leqslant
1$ and $|\gamma|\leqslant N^{1/2}$. Then we have

$\sum_{n\leqslant N}n^{\rho-1}e(\theta n)\ll
N^{\beta}\min\big{(}1,(1+|\gamma|)N^{-1}\|\theta\|^{-1},|\gamma|^{-1/2}\big{)}.$
(5.2)

The proof will require the following two well-known estimates for exponential
sums.

######  Lemma 5.4 (Kuzmin–Landau).

Let $I\subset\mathbf{R}$ be a bounded interval. Let $f:I\rightarrow\mathbf{R}$
be continuously differentiable such that $f^{\prime}$ is monotonic and
$\|f^{\prime}(t)\|\geqslant\lambda$ on $I$. Then

$\sum_{n\in I\cap\mathbf{Z}}e(f(n))\ll\lambda^{-1}.$

###### Proof.

See [33, Part I, Theorem 6.7]. Recall that here $\|\theta\|$ is the distance
to the nearest integer.∎

######  Lemma 5.5 (van der Corput).

Let $I\subset\mathbf{R}$ be a bounded interval. Let $f:I\rightarrow\mathbf{R}$
be twice continuously differentiable with
$\lambda\leqslant|f^{\prime\prime}(x)|\leqslant\alpha\lambda$. Then

$\sum_{n\in I\cap\mathbf{Z}}e(f(n))\ll\alpha|I|\lambda^{1/2}+\lambda^{-1/2}.$

###### Proof.

See the comments after the proof of Theorem 6.7 in [33, Part I] for the exact
version we state here. See also [33, Theorem 6.5], which would suffice for our
purposes but it slightly less explicit about the dependence on $\alpha$.∎

###### Proof of Proposition 5.3.

Since $e(\theta n)$ is periodic, we may assume
$0\leqslant|\theta|\leqslant\frac{1}{2}$ throughout, and hence that
$\|\theta\|=|\theta|$. Set

$S(\gamma,\theta,N):=\sum_{n\leqslant N}n^{i\gamma}e(\theta
n)=\sum_{n\leqslant N}e(\frac{\gamma}{2\pi}\log n+\theta n).$

From the identity

$n^{\beta-1}=N^{\beta-1}-(\beta-1)\int^{N}_{n}x^{\beta-2}dx$

we see that

$\sum_{n\leqslant N}n^{\rho-1}e(\theta
n)=N^{\beta-1}S(\gamma,\theta,N)-(\beta-1)\int^{N}_{1}x^{\beta-2}S(\gamma,\theta,x)dx.$
(5.3)

Now (5.2) consists of three bounds. The first one, that the sum is $\ll
N^{\beta}$, is essentially trivial:

$|\sum_{n\leqslant N}n^{\rho-1}|\leqslant\sum_{n\leqslant
N}|n^{\rho-1}|=\sum_{n\leqslant N}n^{\beta-1}\ll N^{\beta}.$

(Note that the implied constant _is_ uniform in $\beta$ in the range
$\frac{1}{2}\leqslant\beta\leqslant 1$.)

For the second estimate in (5.2), we apply the Kuzmin-Landau bound (Lemma 5.4)
with $f(t)=\frac{\gamma}{2\pi}\log t+\theta t$, we see that if
$M:=\frac{|\gamma|}{|\theta|}$ then

$\sum_{M\leqslant n\leqslant x}n^{i\gamma}e(\theta n)\ll|\theta|^{-1}.$

Estimating the contribution from $M\leqslant\frac{|\gamma|}{|\theta|}$
trivially using $|n^{i\gamma}e(\theta n)|\leqslant 1$ gives
$S(\gamma,\theta,x)\ll(1+|\gamma|)|\theta|^{-1}$. Substituting into (5.3)
gives the second estimate in (5.2).

For the third estimate in (5.2), suppose that $I\subset[2^{j},2^{j+1}]$ is
some interval. Apply the van der Corput bound (Lemma 5.5) on this interval
with $f(t)=\frac{\gamma}{2\pi}\log t+\theta t$. Since
$f^{\prime\prime}(t)=-\frac{\gamma}{2\pi t^{2}}$ we can take
$\lambda=2^{-2j-2}|\frac{\gamma}{2\pi}|$, $\alpha=4$ and obtain the estimate

$\sum_{n\in I}n^{i\gamma}e(n\theta)\ll|\gamma|^{1/2}+2^{j}|\gamma|^{-1/2}.$

Summing over $j$ gives

$S(\gamma,\theta,x)\ll|\gamma|^{1/2}\log N+N|\gamma|^{-1/2},$

uniformly for $x\leqslant N$. Substituting this into (5.3) gives

$\sum_{n\leqslant N}n^{\rho-1}e(\theta n)\ll
N^{\beta}|\gamma|^{-1/2}+|\gamma|^{1/2}N^{\beta-1}\log N,$

which certainly implies the stated bound if $|\gamma|\leqslant N^{1/2}$ (in
fact the weaker condition $|\gamma|\leqslant\frac{N}{\log N}$ would suffice).∎

####  5.3. Minor arcs estimates

We now come to the heart of the proof of Proposition 4.6. We look first at the
minor arcs, obtaining estimates for those $\theta$ not close to a rational
with small denominator. Recall that the notation $X\lessapprox Y$ means
$|X|\leqslant N^{o(1)}Y$; in this section, the $N^{o(1)}$ terms are just fixed
powers of $\log N$, but this is not important for our purposes in this paper.

The following is our key minor arc estimate, which we phrase in the
contrapositive.

######  Lemma 5.6.

Suppose that $\sigma_{0}\leqslant\frac{1}{5}$ and that
$\max(Q,\frac{1}{\delta})\leqslant N^{\frac{1}{8}}$. Suppose that, for some
$\theta\in\mathbf{R}/\mathbf{Z}$,

$|\sum_{n\leqslant
N}\Lambda_{\sharp,Q,\sigma_{0}}(n)e(n\theta)|\geqslant\delta N.$

Then there is some $r\neq 0$, $|r|\lessapprox\delta^{-3}$, such that $\|\theta
r\|\lessapprox\delta^{-3}N^{-1}$.

###### Proof.

From the definition (4.3) of $\Lambda_{\sharp,Q,\sigma_{0}}$ (or, more
precisely, from (4.5)) it follows that

$\sum_{\rho\in\Xi_{Q}^{*}(\sigma_{0})}|\sum_{n\leqslant
N}n^{\rho-1}F_{\chi_{\rho},Q}(n)e(n\theta)|\geqslant\delta N.$

Recall that we set $\Xi_{Q}^{*}(\sigma_{0})=\Xi_{Q}(\sigma_{0})\cup\\{1\\}$
and we adopt the convention that $\chi_{1}$ is the principal character. By
Lemma 5.2 it follows that there is some $\rho\in\Xi_{Q}^{*}(\sigma_{0})$ such
that

$|\sum_{n\leqslant N}n^{\rho-1}F_{\chi_{\rho},Q}(n)e(\theta n)|\gg\delta
N^{\beta},$

where $\beta=\Re\rho$. Fix this $\rho$ and, for notational brevity, write
$\chi=\chi_{\rho}$. As usual, write $\rho=\beta+i\gamma$, and let $q$ be the
conductor of $\chi$. Note that $q\leqslant Q$ (or else $\rho$ would not appear
in $\Xi^{*}_{Q}(\sigma_{0})$) and also that $|\gamma|\leqslant Q$.
Substituting in the definition (4.2) of $F_{\chi,Q}(n)$ and using the triangle
inequality, we obtain

$\sum_{\begin{subarray}{c}q|r\\\ r/q\leqslant
Q\end{subarray}}\sum_{b\in(\mathbf{Z}/r\mathbf{Z})^{*}}|c_{\chi}(b,r)||\sum_{n\leqslant
N}n^{\rho-1}e((\theta+\frac{b}{r})n)|\gg\delta N^{\beta}.$ (5.4)

From the definition (4.1) of $c_{\chi}(b,r)$ and the basic bound

$|\tau(\chi)|^{2}=q.$ (5.5)

for the Gauss sum of a primitive character $\chi$ we have

$|c_{\chi}(b,r)|\leqslant\frac{q^{1/2}}{\phi(r)}.$ (5.6)

Also, $c_{\chi}(b,r)$ is supported where $(q,r/q)=1$ (and where $r/q$ is
squarefree). Therefore from (5.4) we have

$q^{1/2}\sum_{\begin{subarray}{c}q|r\\\ r/q\leqslant Q\\\
(q,r/q)=1\end{subarray}}\frac{1}{\phi(r)}\sum_{b\in(\mathbf{Z}/r\mathbf{Z})^{*}}\big{|}\sum_{n\leqslant
N}n^{\rho-1}e((\theta+\frac{b}{r})n)\big{|}\gg\delta N^{\beta}.$ (5.7)

Now we use Proposition 5.3 to get an upper bound on

$S:=\sum_{b\in(\mathbf{Z}/r\mathbf{Z})^{*}}|\sum_{n\leqslant
N}n^{\rho-1}e((\theta+\frac{b}{r})n)|.$

For the (at most two) values of $b$ with
$\|\theta+\frac{b}{r}\|\leqslant\frac{1}{r}$, we use the first and third
bounds in (5.2), to get a contribution of $\ll
N^{\beta}\min(1,|\gamma|)^{-\frac{1}{2}}$. For all other values of $b$ we
instead use the second bound in (5.2), obtaining a contribution of

$\ll
N^{\beta-1}(1+|\gamma|)\sum_{\begin{subarray}{c}b\in(\mathbf{Z}/r\mathbf{Z})^{*}\\\
\|\theta+\frac{b}{r}\|\geqslant\frac{1}{r}\end{subarray}}\|\theta+\frac{b}{r}\|^{-1}\ll
N^{\beta-1}(1+|\gamma|)r\log r,$

uniformly in $\theta$. Now since $|\gamma|\leqslant Q$, $r\leqslant Q^{2}$ and
$Q\leqslant N^{\frac{1}{8}}$, this is dominated by the bound
$N^{\beta}\min(1,|\gamma|^{-\frac{1}{2}})$, and so

$S\ll N^{\beta}\min(1,|\gamma|^{-\frac{1}{2}}).$ (5.8)

Since

$q^{1/2}\sum_{\begin{subarray}{c}q|r\\\ r/q\leqslant Q\\\
(q,r/q)=1\end{subarray}}\frac{1}{\phi(r)}\leqslant\frac{q^{1/2}}{\phi(q)}\sum_{k\leqslant
Q}\frac{1}{\phi(k)}\ll\frac{q^{1/2}}{\phi(q)}\log Q,$

comparing with (5.8) and (5.7) gives

$\frac{q^{1/2}\log Q}{\phi(q)}\min(1,|\gamma|^{-\frac{1}{2}})\gg\delta.$

Using $\phi(q)\gtrapprox q$ and $q\geqslant 1$, and considering the cases
$|\gamma|\leqslant 1$ and $|\gamma|\geqslant 1$ separately, this gives

$q^{-\frac{1}{2}}(1+|\gamma|)^{-1}\gtrapprox\delta^{2},$ (5.9)

an inequality we will use shortly.

Returning to (5.7), and dropping the conditions $q|r$ and $(q,r/q)=1$, we have

$\sum_{r\leqslant
Q^{2}}\frac{1}{\phi(r)}\sum_{b\in(\mathbf{Z}/r\mathbf{Z})^{*}}\big{|}\sum_{n\leqslant
N}n^{\rho-1}e((\theta+\frac{b}{r})n)\big{|}\gg\delta
N^{\beta}q^{-\frac{1}{2}}.$

By the first and second estimates in (5.2), this implies

$\displaystyle\sum_{r\leqslant
Q^{2}}\frac{1}{\phi(r)}\sum_{b\in(\mathbf{Z}/r\mathbf{Z})^{*}}\min(N,\|\theta+\frac{b}{r}\|^{-1})$
$\displaystyle\gg\delta Nq^{-\frac{1}{2}}(1+|\gamma|)^{-1}$
$\displaystyle\gtrapprox\delta^{3}N,$ (5.10)

where the second step follows from (5.9).

By Dirichlet’s theorem, we may write

$\theta=\frac{a}{d}+\eta,\quad\mbox{where}\quad d\leqslant
2Q^{2},\quad|\eta|\leqslant\frac{1}{2dQ^{2}},$

with $\frac{a}{d}$ in lowest terms. If $\frac{a}{d}\neq-\frac{b}{r}$, this
means that

$\|\theta+\frac{b}{r}\|\geqslant\|\frac{a}{d}+\frac{b}{r}\|-\frac{1}{2dQ^{2}}\geqslant\frac{1}{dr}-\frac{1}{2dQ^{2}}\geqslant\frac{1}{2rd}.$

Hence, if $r\neq d$ then we we have

$\sum_{b\in(\mathbf{Z}/r\mathbf{Z})^{*}}\|\theta+\frac{b}{r}\|^{-1}\ll
dr+r\log r\ll Q^{4},$

and so the contribution to the left-hand side of (5.10) from $r\neq d$ will be
bounded above by $Q^{4}\sum_{r\leqslant Q^{2}}\frac{1}{\phi(r)}\lessapprox
Q^{4}$. By our choice of parameters, this is negligible compared to
$\delta^{3}N$. Thus the bulk of the contribution to the left-hand side of
(5.10) comes from $r=d$, that is to say

$\frac{1}{\phi(d)}\sum_{b\in(\mathbf{Z}/d\mathbf{Z})^{*}}\min(N,\|\theta+\frac{b}{d}\|^{-1})\gtrapprox\delta^{3}N.$
(5.11)

Now

$\sum_{\begin{subarray}{c}b\in(\mathbf{Z}/d\mathbf{Z})^{*}\\\
b\neq-a\end{subarray}}\|\theta+\frac{b}{d}\|^{-1}\ll d\log d\lessapprox
Q^{2}.$

Therefore the bulk of the contribution to the left-hand side of (5.11) comes
from $b=-a$, and so

$\frac{1}{\phi(d)}\min(N,\|\theta-\frac{a}{d}\|^{-1})\gtrapprox\delta^{3}N.$

This implies both $d\lessapprox\delta^{-3}$ and $\|\theta
d\|\lessapprox\delta^{-3}N^{-1}$, that is to say the two statements claimed.
This completes the proof. ∎

Combining Lemma 5.6 with standard minor arc estimates for the von Mangoldt
function confirms Proposition 4.6 unless $\theta$ is close to a rational with
small denominator (that is, in the minor arc case), as the following corollary
shows.

######  Corollary 5.7.

Suppose that $\sigma_{0}<\frac{1}{5}$ and that
$\max(Q,\frac{1}{\delta})\leqslant N^{\frac{1}{8}}$. Suppose that, for some
$\theta\in\mathbf{R}/\mathbf{Z}$,

$|\sum_{n\leqslant
N}(\Lambda(n)-\Lambda_{\sharp,Q,\sigma_{0}}(n))e(n\theta)|\geqslant\delta N.$

Then there is some $r\neq 0$, $|r|\lessapprox\delta^{-3}$, such that $\|\theta
r\|\lessapprox\delta^{-3}N^{-1}$.

###### Proof.

One of $|\sum_{n\leqslant N}\Lambda(n)e(\theta n)|$ and $|\sum_{n\leqslant
N}\Lambda_{\sharp,Q,\sigma_{0}}(n)e(\theta n)|$ is at least
$\frac{\delta}{2}N$, by the triangle inequality. In the latter case, the
conclusion follows immediately from Lemma 5.6. Suppose, then, that we are in
the former case, so

$|\sum_{n\leqslant N}\Lambda(n)e(\theta n)|\geqslant\frac{\delta}{2}N.$ (5.12)

In [4, Chapter 25] it is shown that if $|\theta-\frac{a}{q}|\leqslant q^{-2}$
then

$\sum_{n\leqslant N}\Lambda(n)e(\theta
n)\ll(\frac{N}{q^{1/2}}+N^{4/5}+N^{1/2}q^{1/2})\log^{4}N.$ (5.13)

Let $X=c\delta^{2}N\log^{-8}N$ for some $c>0$ which we will specify shortly.
By Dirichlet’s theorem, there is some $q\leqslant X$ such that
$|\theta-\frac{a}{q}|\leqslant\frac{1}{qX}\leqslant\frac{1}{q^{2}}$. By the
assumption that $\delta\geqslant N^{-\frac{1}{8}}$ (which is a comfortable
one, but stronger than necessary) and that $N$ is sufficiently large, the
middle term in (5.13) is $\leqslant\delta N/6$. By the choice of $X$ (if $c$
is small enough) the last term in (5.13) is also $\leqslant\delta N/6$. It
follows from these observations that if (5.12) holds then the first term in
(5.13) is $\geqslant\delta N/6$, which implies that $q\lessapprox\delta^{-2}$.
Note also that $\|\theta q\|\leqslant X^{-1}\lessapprox\delta^{-2}N^{-1}$.
Thus the conclusion of Corollary 5.7 holds in this case also (in fact with
slightly superior exponents). ∎

####  5.4. Major arc estimates

In this section, we handle the cases of Proposition 4.6 not covered by
Corollary 5.7. The main result is the following.

######  Lemma 5.8 (Major arcs).

Suppose that $\sigma_{0}\leqslant\frac{1}{9}$ and that $Q\leqslant
N^{\sigma_{0}}$. Suppose that there is some $d\leqslant Q^{\frac{1}{2}}$ such
that $\|\theta d\|\leqslant Q^{\frac{1}{2}}N^{-1}$. Then

$\sum_{n\leqslant N}(\Lambda(n)-\Lambda_{\sharp,Q,\sigma_{0}}(n))e(\theta
n)\lessapprox NQ^{-\frac{1}{4}}.$ (5.14)

Before proceeding to the proof, let us see how Corollary 5.7 and Lemma 5.8
together imply Proposition 4.6.

###### Proof of Proposition 4.6.

Let $\varepsilon>0$ be arbitrary. Let
$\delta=Q^{-\frac{1}{6}}N^{\varepsilon}$, and suppose that for some $\theta$
we have

$|\sum_{n\leqslant
N}(\Lambda(n)-\Lambda_{\sharp,Q,\sigma_{0}}(n))e(n\theta)|\geqslant\delta N.$

Then, by Corollary 5.7, there is some $r\neq 0$, $|r|\lessapprox\delta^{-3}$,
such that $\|\theta r\|\lessapprox\delta^{-3}N^{-1}$. If $N$ is big enough in
terms of $\varepsilon$, $|r|\leqslant Q^{\frac{1}{2}}$ and $\|\theta
r\|\leqslant Q^{\frac{1}{2}}N^{-1}$, so we are in a position to apply Lemma
5.8, and this tells us that $NQ^{-\frac{1}{4}}\gtrapprox\delta N$, which is a
contradiction for $N$ sufficiently large in terms of $\varepsilon$. Since
$\varepsilon$ was arbitrary, Proposition 4.6 follows.∎

To prove Lemma 5.8, we will need some preliminaries on Dirichlet characters
and on the coefficients $c_{\chi}$ as defined in (4.1). In particular, we will
see why these coefficients play a key role in the paper. Here and in what
follows, $\operatorname{cond}(\chi)$ means the conductor of the primitive
Dirichlet character $\chi$.

######  Lemma 5.9.

Let $r$ be an integer and $b\in(\mathbf{Z}/r\mathbf{Z})^{*}$. Then

$e(-\frac{bn}{r})=\sum_{\chi:\operatorname{cond}(\chi)|r}c_{\chi}(b,r)1_{(n,r)=1}\chi(n),$
(5.15)

where the sum is over all primitive Dirichlet characters $\chi$.

###### Proof.

For any character $\psi$ to modulus $r$ we have

$\sum_{t\in(\mathbf{Z}/r\mathbf{Z})^{*}}\psi(t)e(\frac{bt}{r})=\overline{\psi(b)}\tau(\psi).$
(5.16)

By [11, Lemma 3.1], if $\psi$ is induced by a primitive character $\chi$ with
conductor $q$ then

$\tau(\psi)=\mu(\frac{r}{q})\chi(\frac{r}{q})\tau(\chi).$

Therefore by orthogonality of characters, and writing
$\sum_{\psi(\mbox{\scriptsize mod}\,r)}$ for the sum over all $\phi(r)$
Dirichlet characters to modulus $r$, we have

$\displaystyle e(-\frac{bn}{r})$
$\displaystyle=\frac{1}{\phi(r)}\sum_{\psi(\mbox{\scriptsize
mod}\,r)}\big{(}\overline{\sum_{t\in(\mathbf{Z}/r\mathbf{Z})^{*}}\psi(t)e(\frac{bt}{r})}\big{)}\psi(n)$
$\displaystyle=\frac{1}{\phi(r)}\sum_{\psi(\mbox{\scriptsize
mod}\,r)}\psi(b)\overline{\tau(\psi)}\psi(n)$
$\displaystyle=\frac{1}{\phi(r)}\sum_{\begin{subarray}{c}\chi:\operatorname{cond}(\chi)|r\\\
\mbox{\scriptsize$\chi$
primitive}\end{subarray}}\chi(b)\mu(\frac{r}{q})\overline{\chi(\frac{r}{q})}\overline{\tau(\chi)}1_{(n,r)=1}\chi(n).$

To get the last line, for each $\psi$ we consider the primitive character
$\chi$ which induces it, noting that the induced character $\psi$ to modulus
$r$ is then $1_{(n,r)=1}\chi(n)$. The result follows immediately by the
definition of $c$, namely (4.1).∎

We will also need a version of the explicit formula. If $\chi$ is a primitive
Dirichlet character, denote by $Z(\chi)$ the multiset of nontrivial zeros of
$L(s,\chi)$ in the strip $0<\Re s<1$, together with the pole at $1$ if $\chi$
is principal. Note that $\Xi^{*}_{Q}(\sigma_{0})$ is then the disjoint union
of the (multi-)sets $Z(\chi)\cap\Xi^{*}_{Q}(\sigma_{0})$, as $\chi$ ranges
over all primitive $\chi$ with $\operatorname{cond}(\chi)\leqslant Q$; this
follows from the definition of $\Xi_{Q}(\sigma_{0})$, Definition 4.1.

######  Lemma 5.10.

Suppose $\sigma_{0}\leqslant\frac{1}{2}$. Let $\psi$ be a Dirichlet character
(not necessarily primitive) to some modulus $r$, $r\leqslant Q\leqslant x$,
and let $\chi$ be the primitive character inducing $\psi$. Then

$\sum_{n\leqslant x}\Lambda(n)\psi(n)=\sum_{\rho\in
Z(\chi)\cap\Xi^{*}_{Q}(\sigma_{0})}\varepsilon_{\rho}\frac{x^{\rho}}{\rho}+\tilde{O}(x^{1-\sigma_{0}}+\frac{x}{Q}).$
(5.17)

Here, $\varepsilon_{1}=1$ and $\varepsilon_{\rho}=-1$ when $\rho$ is a zero.

Recall that $\tilde{O}(Y)$ means a quantity that is bounded in magnitude by
$N^{o(1)}Y$.

###### Proof.

This is a standard result (for instance, it appears as [32, Exercise 45
(iv)]), but it is not straightforward to find a completely quotable reference.
First, we observe that one may quickly reduce to the primitive case
$\psi=\chi$. Indeed, the sums over $\rho$ are the same since $L(s,\chi)$ and
$L(s,\psi)$ have the same nontrivial zeros (as they differ only by a finite
product of terms $1-p^{-s}$), whilst on the other hand $\sum_{n\leqslant
x}\Lambda(n)\psi(n)$ and $\sum_{n\leqslant x}\Lambda(n)\chi(n)$ differ by
$\ll\log^{2}x$, as explained in the displayed equation following [4, Chapter
19, equation (12)].

Suppose, then, that $\psi=\chi$ is primitive. Suppose first that $\chi$ is not
the principal character $1$. Then [4, Chapter 19, equations (13) to (15)]
state that

$\sum_{n\leqslant
x}\Lambda(n)\chi(n)=-\sideset{}{{}^{*}}{\sum}_{|\Im\rho|\leqslant
Q}\frac{x^{\rho}}{\rho}+O(\frac{x(\log rx)^{2}}{Q}+x^{1/4}\log x).$ (5.18)

Here the sum is over all zeros of $L(s,\chi)$ in the critical strip $0<\Re
s<1$, and the asterisk denotes that if $\chi$ is real has a simple real zero
$\beta_{1}$ with $\beta_{1}\geqslant 1-\frac{c}{\log Q}$, then
$\rho=1-\beta_{1}$ is omitted from the sum. To derive (5.17), we must remove
the contribution of the zeros $\rho$ with $0<\Re\rho<1-\sigma_{0}$, which do
not lie in $\Xi_{Q}$. To estimate this, divide the set of such $\rho$ into
sets $\Omega_{k}$, $k=0,1,\dots$, where $2^{k}\leqslant|\Im\rho|\leqslant
2^{k+1}$, and the set $\Omega_{*}$ where $|\Im\rho|\leqslant 1$. By standard
estimates for the number of zeros (see, for example, [4, Chapter 16]) we have
$|\Omega_{k}|\lessapprox 2^{k}$, and $|\Omega_{*}|\lessapprox 1$. If
$\rho\in\Omega_{k}$, $|\frac{x^{\rho}}{\rho}|\ll 2^{-k}x^{1-\sigma_{0}}$, so
$\sum_{\rho\in\Omega_{k}}|\frac{x^{\rho}}{\rho}|\lessapprox x^{1-\sigma_{0}}$.
If $\rho\in\Omega_{*}$, we have $|\frac{x^{\rho}}{\rho}|\ll
x^{1-\sigma_{0}}\log Q$ (since $\frac{1}{|\rho|}\ll\log Q$ for all the zeros
under consideration). Summing the contributions from $\Omega_{*}$ and all the
$\Omega_{k}$ with $k\leqslant\log_{2}X$, we obtain the stated result.

Suppose now that $\chi$ is the principal character. Here, (5.18) still holds
provided we remember to include a main term of $x$ coming from the simple pole
of $\zeta$, as follows from [4, Chapter 18, equations (9) and (10)]. ∎

We turn now to the proof of Lemma 5.8 itself.

###### Proof of Lemma 5.8.

Recall the definition of $\Lambda_{\sharp,Q,\sigma_{0}}$ in the form (4.5),
viz

$\Lambda_{\sharp,Q,\sigma_{0}}(n)=\sum_{\rho\in\Xi_{Q}^{*}(\sigma_{0})}\varepsilon_{\rho}n^{\rho-1}F_{\chi_{\rho},Q}(n),$
(5.19)

where (Definition 4.3)

$F_{\chi,Q}(n):=\sum_{\begin{subarray}{c}\operatorname{cond}(\chi)|r\\\
r\leqslant
Q\operatorname{cond}(\chi)\end{subarray}}\sum_{b\in(\mathbf{Z}/r\mathbf{Z})^{*}}c_{\chi}(b,r)e(\frac{bn}{r}),$

with $c_{\chi}$ defined in (4.1), and $\operatorname{cond}(\chi)$ denotes the
conductor of $\chi$.

Write $\theta=-\frac{a}{d}+\eta$ with $d$ as in the statement of Lemma 5.8.
Replacing $d$ by a divisor of itself if necessary, we may assume that
$\frac{a}{d}$ is in lowest terms. By the assumptions of Lemma 5.8,

$|\eta|\leqslant\frac{Q^{\frac{1}{2}}}{dN}<\frac{1}{2Q^{3}}.$ (5.20)

Multiplying (5.19) through by $e(n\theta)$, summing over $N$ and interchanging
the order of summation, we obtain

$\displaystyle\sum_{n\leqslant N}$
$\displaystyle\Lambda_{\sharp,Q,\sigma_{0}}(n)e(\theta n)$
$\displaystyle=\sum_{r\leqslant
Q^{2}}\sum_{b\in(\mathbf{Z}/r\mathbf{Z})^{*}}\sum_{\begin{subarray}{c}\rho\in\Xi_{Q}^{*}(\sigma_{0})\\\
q_{\rho}|r\\\ r/q_{\rho}\leqslant
Q\end{subarray}}\varepsilon_{\rho}c_{\chi_{\rho}}(b,r)\sum_{n\leqslant
N}n^{\rho-1}e((\frac{b}{r}-\frac{a}{d}+\eta)n).$ (5.21)

Here, we have written $q_{\rho}:=\operatorname{cond}(\chi_{\rho})$ for
brevity.

We claim that the contribution from $\frac{b}{r}\neq\frac{a}{d}$ is
$\lessapprox Q^{5}$, which can be subsumed into the right hand side of the
desired bound (5.14) because of the assumption that $Q\leqslant
N^{\frac{1}{9}}$. To prove this claim, we use the second bound in (5.2), the
fact that $|\Im\rho|\leqslant Q$, and the trivial bound
$|c_{\chi_{\rho}}(b,r)|\leqslant 1$ to see that this contribution is bounded
by

$Q\sum_{\begin{subarray}{c}r\leqslant Q^{2}\\\
b\in(\mathbf{Z}/r\mathbf{Z})^{*}\\\
\frac{b}{r}\neq-\frac{a}{d}\end{subarray}}\|\frac{b}{r}-\frac{a}{d}+\eta\|^{-1}\sum_{\rho\in\Xi_{Q}^{*}(\sigma_{0})}N^{\Re\rho-1}\ll
Q\sum_{\begin{subarray}{c}r\leqslant Q^{2}\\\
b\in(\mathbf{Z}/r\mathbf{Z})^{*}\\\
\frac{b}{r}\neq-\frac{a}{d}\end{subarray}}\|\frac{b}{r}-\frac{a}{d}+\eta\|^{-1},$

where the inequality follows from Lemma 5.2. Now if
$\frac{b}{r}\neq-\frac{a}{d}$ then
$\|\frac{b}{r}-\frac{a}{d}+\eta\|\geqslant\frac{1}{rd}-|\eta|>\frac{1}{2}Q^{-3}$,
since $r\leqslant Q^{2}$, $d<Q$ and $|\eta|\leqslant(2Q^{3})^{-1}$ by (5.20).
Since the different $\frac{b}{r}$ are $Q^{-4}$-separated,

$\sum_{\begin{subarray}{c}r\leqslant Q^{2}\\\
b\in(\mathbf{Z}/r\mathbf{Z})^{*}\\\
\frac{b}{r}\neq-\frac{a}{d}\end{subarray}}\|\frac{b}{r}-\frac{a}{d}+\eta\|^{-1}\ll
Q^{4}\log Q.$

Thus the contribution of $\frac{b}{r}\neq-\frac{a}{d}$ to (5.21) is $\ll
Q^{5}\log Q\lessapprox Q^{5}$, as claimed. It therefore follows from (5.21)
that

$\sum_{n\leqslant N}\Lambda_{\sharp,Q,\sigma_{0}}(n)e(\theta
n)=\sum_{\rho\in\Xi_{Q}^{*}(\sigma_{0})}\varepsilon_{\rho}c_{\chi_{\rho}}(a,d)\sum_{n\leqslant
N}n^{\rho-1}e(\eta n)+\tilde{O}(Q^{5}).$ (5.22)

(Note that the conditions $q_{\rho}|d$ and $d/q_{\rho}\leqslant Q$ are
redundant, since $c_{\chi_{\rho}}(a,d)=0$ unless the first is satisfied, and
$d\leqslant Q^{\frac{1}{2}}$ implies the second is automatically satisfied.)

Now we look at the Fourier transform of the von Mangoldt function $\Lambda$
itself. The key input is the explicit formula, Lemma 5.10. We want to twist
this by $e(\eta n)$ for small $\eta$, which can be done by partial summation.
Specifically, observe that

$e(\eta n)=e(\eta N)-2\pi i\eta\int^{N}_{n}e(\eta t)dt.$

Multiplying by $\Lambda(n)\psi(n)$, summing over $n\leqslant N$, interchanging
the order of integration and summation and substituting $t=Nu$ gives

$\displaystyle\sum_{n\leqslant N}\Lambda(n)\psi(n)e(\eta n)=e(\eta N)$
$\displaystyle\sum_{n\leqslant N}\Lambda(n)\psi(n)-$ $\displaystyle-2\pi i\eta
N\int^{1}_{0}e(\eta Nu)du\sum_{n\leqslant Nu}\Lambda(n)\psi(n).$

Applying the explicit formula (5.17) and using the identity

$\int^{1}_{0}x^{\rho-1}e(\eta Nx)dx=\frac{1}{\rho}e(\eta N)-2\pi i\eta
N\int^{1}_{0}\frac{x^{\rho}}{\rho}e(\eta Nx)dx$

(which may be established by integration by parts) we obtain

$\displaystyle\sum_{n\leqslant N}\Lambda(n)\psi(n)e(\eta n)$
$\displaystyle=\sum_{\rho\in
Z(\psi)\cap\Xi^{*}_{Q}(\sigma_{0})}\varepsilon_{\rho}N^{\rho}\int^{1}_{0}x^{\rho-1}e(\eta
Nx)dx+\tilde{O}((1+|\eta N|)(N^{1-\sigma_{0}}+\frac{N}{Q}))$
$\displaystyle=\sum_{\rho\in
Z(\psi)\cap\Xi^{*}_{Q}(\sigma_{0})}\varepsilon_{\rho}N^{\rho}\int^{1}_{0}x^{\rho-1}e(\eta
Nx)dx+\tilde{O}(NQ^{-\frac{1}{2}})$ (5.23)

by the assumption that $Q\leqslant N^{\sigma_{0}}$, and since $|\eta|\leqslant
Q^{\frac{1}{2}}N^{-1}$.

We want to approximate the integral here by a sum, to which end we use the
crude approximation

$\int^{b}_{a}w(x)dx=\frac{1}{N}\sum_{aN\leqslant
n<bN}w(\frac{n}{N})+O(\frac{1}{N}(\|w\|_{L^{\infty}(a,b)}+\|w^{\prime}\|_{L^{\infty}(a,b)})),$

valid for any interval $[a,b]$ of length at most $1$ and for any
differentiable function $w:(a,b)\rightarrow\mathbf{C}$ with bounded
derivative. We take $w(x):=x^{\rho-1}e(\eta Nx)$ and
$[a,b]=[N^{-\frac{1}{2}},1]$. Then $\|w\|_{L^{\infty}(a,b)}\leqslant
N^{\frac{1}{2}-\frac{1}{2}\beta}$ (where $\rho=\beta+i\gamma$) and
$\|w^{\prime}\|_{L^{\infty}(a,b)}\ll
N^{1-\frac{1}{2}\beta}(1+|\gamma|)+|\eta|N\cdot
N^{\frac{1}{2}-\frac{1}{2}\beta}\ll
N^{1-\frac{1}{2}\beta}Q+Q^{\frac{1}{2}}N^{\frac{1}{2}-\frac{1}{2}\beta}\ll
N^{1-\frac{1}{2}\beta}Q$, so we get

$\int^{1}_{N^{-\frac{1}{2}}}x^{\rho-1}e(\eta
Nx)dx=N^{-\rho}\sum_{N^{\frac{1}{2}}\leqslant n<N}n^{\rho-1}e(\eta
n)+O(N^{-\frac{1}{2}\beta}Q).$

Since also

$|\int^{N^{-\frac{1}{2}}}_{0}x^{\rho-1}e(\eta
Nx)dx|\leqslant\int^{N^{-\frac{1}{2}}}_{0}|x|^{\beta-1}dx\ll
N^{-\frac{1}{2}\beta}$

and

$|N^{-\rho}\sum_{1\leqslant n<N^{\frac{1}{2}}}n^{\rho-1}e(\eta n)|\leqslant
N^{-\beta}\sum_{1\leqslant n<N^{\frac{1}{2}}}|n|^{\beta-1}\ll
N^{-\frac{1}{2}\beta},$

we have

$\int^{1}_{0}x^{\rho-1}e(\eta Nx)dx=N^{-\rho}\sum_{n=1}^{N}n^{\rho-1}e(\eta
n)+O(N^{-\frac{1}{2}\beta}Q).$

Now (5.23) implies that

$\displaystyle\sum_{n\leqslant N}\Lambda(n)$ $\displaystyle\psi(n)e(\eta
n)=\sum_{\rho\in
Z(\psi)\cap\Xi^{*}_{Q}(\sigma_{0})}\varepsilon_{\rho}\sum_{n=1}^{N}n^{\rho-1}e(\eta
N)+$ $\displaystyle+O\big{(}Q\sum_{\rho\in
Z(\psi)\cap\Xi^{*}_{Q}(\sigma_{0})}N^{\frac{1}{2}\beta}\big{)}+\tilde{O}(NQ^{-\frac{1}{2}}).$
(5.24)

To estimate the first error term, we use the zero-density bound
$|Z(\psi)\cap\Xi^{*}_{Q}(\sigma_{0})|\leqslant 1+|\Xi_{Q}(\sigma_{0})|\ll Q$
(which follows from Proposition 5.1, since $\sigma_{0}\leqslant\frac{1}{8}$).
This shows that the total error term in (5.24) is
$\tilde{O}(N^{\frac{1}{2}}Q^{2}+NQ^{-\frac{1}{2}})=\tilde{O}(NQ^{-\frac{1}{2}})$
since $Q<N^{\frac{1}{5}}$.

Now (5.15) gives

$e(-\frac{an}{d})=\sum_{\chi:\operatorname{cond}(\chi)|d}c_{\chi}(a,d)1_{(n,d)=1}\chi(n),$

where the sum is over primitive $\chi$. Recalling that
$\theta=-\frac{a}{d}+\eta$, it follows that

$\displaystyle\sum_{n\leqslant N}\Lambda(n)e(n\theta)$
$\displaystyle=\sum_{\chi:\operatorname{cond}(\chi)|d}c_{\chi}(a,d)\sum_{\begin{subarray}{c}n\leqslant
N\\\ (n,d)=1\end{subarray}}\Lambda(n)\chi(n)e(\eta n)$
$\displaystyle=\sum_{\chi:\operatorname{cond}(\chi)|d}c_{\chi}(a,d)\sum_{n\leqslant
N}\Lambda(n)\chi(n)e(\eta n)+\tilde{O}(Q^{\frac{1}{4}}),$

where for the second bound we have used $\sum_{n\leqslant N:(n,d)\neq
1}\Lambda(n)\lessapprox 1$ and the bound

$\sum_{\chi:\operatorname{cond}(\chi)|d}|c_{\chi}(a,d)|\leqslant\phi(d)\frac{d^{\frac{1}{2}}}{\phi(d)}\leqslant
Q^{\frac{1}{4}},$ (5.25)

which follows from (5.6) and the assumption that $d\leqslant Q^{\frac{1}{2}}$.
Substituting into (5.24) (with $\psi=\chi$, and using the fact that the total
error term in (5.24) is $\tilde{O}(NQ^{-\frac{1}{2}})$ as explained after
(5.24)) gives

$\displaystyle\sum_{n\leqslant N}\Lambda(n)e(\theta
n)=\sum_{\begin{subarray}{c}\rho\in\Xi_{Q}^{*}(\sigma_{0})\\\
\operatorname{cond}(\chi_{\rho})|d\end{subarray}}\varepsilon_{\rho}$
$\displaystyle c_{\chi_{\rho}}(a,d)\sum_{n=1}^{N}n^{\rho-1}e(\eta n)$
$\displaystyle+\tilde{O}(Q^{\frac{1}{4}}+NQ^{-\frac{1}{2}}\sum_{\chi:\operatorname{cond}(\chi)|d}|c_{\chi}(a,d)|).$

Using (5.25) again, we see that the error term is
$\tilde{O}(NQ^{-\frac{1}{4}})$. Note also that, in the sum over $\rho$, the
condition that $\operatorname{cond}(\chi_{\rho})|d$ can be omitted since
$c_{\chi}(a,d)=0$ when $\operatorname{cond}(\chi)\nmid d$.

Comparing with (5.22), and since $Q<N^{\frac{1}{6}}$, the proof of Lemma 5.8
is complete. ∎

###  6\. Completed approximants

Recall (Definition 4.3) the definition

$F_{\chi,Q}(n)=\sum_{r\leqslant
qQ}\sum_{b\in(\mathbf{Z}/r\mathbf{Z})^{*}}c_{\chi}(b,r)e(\frac{bn}{r}),$ (6.1)

where here $q:=\operatorname{cond}(\chi)$.

If one relaxes the constraint on $r$ here, say to $r|R!$ for some $R>Q$, we
get an object which we call a “completed” approximant $\tilde{F}_{\chi,R}$.
These completed approximants are much easier to understand combinatorially,
and in fact provide the motivation for studying the truncated objects such as
$F_{\chi,Q}$. The interplay between completed and truncated approximants is a
key theme in this paper, and this section is devoted to the basic properties
of completed approximants.

######  Definition 6.1.

Suppose that $\chi$ is a primitive Dirichlet character to modulus $q$. Let $R$
be some parameter. Then we define

$\tilde{F}_{\chi,R}(n):=\sum_{r|R!}\sum_{b\in(\mathbf{Z}/r\mathbf{Z})^{*}}c_{\chi}(b,r)e(\frac{bn}{r}).$
(6.2)

At this point we introduce the functions $\Lambda_{\mathbf{Z}/p\mathbf{Z}}$
defined, for prime $p$, by

$\Lambda_{\mathbf{Z}/p\mathbf{Z}}(n):=\left\\{\begin{array}[]{ll}0&\mbox{if
$p|n$}\\\ (1-\frac{1}{p})^{-1}&\mbox{if $(p,n)=1$}\end{array}\right.$ (6.3)

These functions will feature quite heavily in the paper. The notation
$\Lambda_{\mathbf{Z}/p\mathbf{Z}}$ is (somewhat) standard, and reflects the
fact that $\Lambda_{\mathbf{Z}/p\mathbf{Z}}$ is the most natural
$(\operatorname{mod}\,p)$ analogue of the von Mangoldt function. Observe that,
for $p$ prime,

$1-\frac{1}{p-1}c_{p}(n)=1+\frac{\mu(p)}{\phi(p)}c_{p}(n)=\Lambda_{\mathbf{Z}/p\mathbf{Z}}(n),$
(6.4)

where here (recall) the definition of the Ramanujan sum
$c_{r}(n):=\sum_{b\in(\mathbf{Z}/r\mathbf{Z})^{*}}e(\frac{bn}{r})$.

######  Lemma 6.2.

Let $Q,R\geqslant 1$ be parameters. Let $\chi$ be a primitive Dirichlet
character with conductor $q$. Then

$\tilde{F}_{\chi,R}(n)=(\prod_{p\leqslant
R}(1-\frac{1}{p})^{-1})\overline{\chi}(n)1_{(n,R!)=1}=\frac{q}{\phi(q)}\overline{\chi}(n)\prod_{\begin{subarray}{c}p\nmid
q\\\ p\leqslant R\end{subarray}}\Lambda_{\mathbf{Z}/p\mathbf{Z}}(n)$ (6.5)

and

$F_{\chi,Q}(n)=\frac{q}{\phi(q)}\overline{\chi}(n)\sum_{\begin{subarray}{c}r\leqslant
Q\\\ (r,q)=1\end{subarray}}\frac{\mu(r)}{\phi(r)}c_{r}(n).$ (6.6)

###### Proof.

Recall the definition of $c_{\chi}$, given in Definition 4.3. In particular
$c_{\chi}(b,r)$ is supported where $q|r$ and where $r/q$ is squarefree and
coprime to $q$. Consider the definition (6.2). To begin with, fix $r$ (with
$q|r$ and $r/q$ squarefree) and look at the inner sum over $b$. We have
$r=qr^{\prime}$, with $r^{\prime}$ squarefree and coprime to $q$. We may write
$\frac{b}{r}=\frac{a}{q}+\frac{b^{\prime}}{r^{\prime}}$, where
$a\in(\mathbf{Z}/q\mathbf{Z})^{*}$ and
$b^{\prime}\in(\mathbf{Z}/r^{\prime}\mathbf{Z})^{*}$. Note that $b\equiv
ar^{\prime}(\operatorname{mod}\,q)$ and therefore
$\chi(b)=\chi(a)\chi(r^{\prime})$, and so

$c_{\chi}(b,r)=\frac{1}{\phi(q)}\chi(a)\overline{\tau(\chi)}\frac{\mu(r^{\prime})}{\phi(r^{\prime})}.$

Therefore we may factor

$\sum_{b\in(\mathbf{Z}/r\mathbf{Z})^{*}}c_{\chi}(b,r)e(\frac{bn}{r})=E_{1}E_{2}$

where

$E_{1}:=\frac{\overline{\tau(\chi)}}{\phi(q)}\sum_{a\in(\mathbf{Z}/q\mathbf{Z})^{*}}\chi(a)e(\frac{an}{q}),\quad
E_{2}:=\frac{\mu(r^{\prime})}{\phi(r^{\prime})}\sum_{b^{\prime}\in(\mathbf{Z}/r^{\prime}\mathbf{Z})^{*}}e(\frac{b^{\prime}n}{r^{\prime}}).$
(6.7)

Now it is easy to see (and we have already used in this in (5.16)) that
$\sum_{a\in(\mathbf{Z}/q\mathbf{Z})^{*}}\chi(a)e(\frac{an}{q})=\overline{\chi(n)}\tau(\chi)$
if $(n,q)=1$. If $\chi$ is _primitive_ , as here, the condition $(n,q)=1$ can
be dropped since both sides of the expression vanish, as explained in [11,
Section 3.4]. Therefore, using (5.5),
$E_{1}=\frac{q}{\phi(q)}\overline{\chi(n)}$. We may write $E_{2}$ more
succinctly as $\frac{\mu(r^{\prime})}{\phi(r^{\prime})}c_{r^{\prime}}(n)$.
Summarising, we have

$\sum_{b\in(\mathbf{Z}/r\mathbf{Z})^{*}}c_{\chi}(b,r)e(\frac{bn}{r})=\frac{q}{\phi(q)}\overline{\chi(n)}\frac{\mu(r^{\prime})}{\phi(r^{\prime})}c_{r^{\prime}}(n)$
(6.8)

(where $r=qr^{\prime}$ with $(r^{\prime},q)=1$).

The expression (6.6) follows immediately from the definition (6.1) of
$F_{\chi,Q}$, summing (6.8) over $r^{\prime}\leqslant Q$ (and coprime to $q$).

To obtain (6.5), we recall the definition (6.2) of $\tilde{F}_{\chi,R}$, and
instead sum (6.8) over all $r|R!$. We obtain

$\tilde{F}_{\chi,R}(n)=\frac{q}{\phi(q)}\overline{\chi(n)}\sum_{\begin{subarray}{c}r^{\prime}|R!\\\
(r^{\prime},q)=1\end{subarray}}\frac{\mu(r^{\prime})}{\phi(r^{\prime})}c_{r^{\prime}}(n).$
(6.9)

(We will use this equation in its own right in Section 10.)

Using the multiplicativity property $c_{ab}(n)=c_{a}(n)c_{b}(n)$ when
$(a,b)=1$, as well as (6.4), we see that sum over $r^{\prime}$ factors as

$\prod_{\begin{subarray}{c}p\leqslant R\\\ p\nmid
q\end{subarray}}\big{(}1+\frac{\mu(p)}{\phi(p)}c_{p}(n)\big{)}=\prod_{\begin{subarray}{c}p\leqslant
R\\\ p\nmid q\end{subarray}}\Lambda_{\mathbf{Z}/p\mathbf{Z}}(n),$

from which (6.5) follows. ∎

To conclude this section, let us record explicitly what happens in the case
$\chi=\chi_{0}$, the principal character. Recall from (4.4) that in this case,
$F_{\chi_{0},Q}$ is in fact equal to $\Lambda_{Q}$, the classical approximant
defined in (3.3). It is therefore natural to write $\tilde{\Lambda}_{R}$
instead of $\tilde{F}_{\chi_{0},R}$ for the corresponding completed
approximant, thus

$\tilde{\Lambda}_{R}(n):=\sum_{q|R!}\frac{\mu(q)}{\phi(q)}c_{q}(n).$ (6.10)

The special case $\chi=\chi_{0}$ of Lemma 6.2 is then the statement that

$\tilde{\Lambda}_{R}(n)=\prod_{p\leqslant
R}\Lambda_{\mathbf{Z}/p\mathbf{Z}}(n),$ (6.11)

which is a normalised characteristic function of the almost primes at level
$R$ (that is, numbers all of whose prime factors are $>R$). This statement
also follows rather directly from (6.4) and multiplicativity.

####  6.1. Pointwise bounds

An application of the above expressions are pointwise bounds for the
$F_{\chi,Q}$. We first prove a general fact about what we will later call
Ramanujan series.

######  Lemma 6.3.

Suppose that

$f(n)=\sum_{r\leqslant Q}v(r)c_{r}(n).$ (6.12)

Then

$f(n)=\sum_{\begin{subarray}{c}d|n\\\ d\leqslant
Q\end{subarray}}\lambda_{d}\quad\mbox{where}\quad\frac{\lambda_{d}}{d}=\sum_{\begin{subarray}{c}d|r\\\
r\leqslant Q\end{subarray}}\mu(\frac{r}{d})v(r).$ (6.13)

###### Proof.

With $\lambda_{d}$ as defined in (6.13) we have

$\sum_{\begin{subarray}{c}d|n\\\ d\leqslant
Q\end{subarray}}\lambda_{d}=\sum_{\begin{subarray}{c}d|n\\\ d\leqslant
Q\end{subarray}}d\sum_{\begin{subarray}{c}d|r\\\ r\leqslant
Q\end{subarray}}\mu(\frac{r}{d})v(r)=\sum_{r\leqslant
Q}v(r)\sum_{d|(r,n)}d\mu(\frac{r}{d}).$ (6.14)

On the other hand,

$1_{d|n}=\frac{1}{d}\sum_{a\in\mathbf{Z}/d\mathbf{Z}}e(\frac{an}{d})=\frac{1}{d}\sum_{r|d}c_{r}(n),$

and so by Möbius inversion we have

$\sum_{d|(r,n)}d\mu(\frac{r}{d})=c_{r}(n).$

Substituting into (6.14) gives the claimed result. ∎

_Remark._ The sum $\sum_{d|n:d\leqslant Q}\lambda_{d}$ is a kind of sieve
weight. Conversely, any such weight can be expressed in the form (6.12), with
$v(r)=\sum_{d\leqslant Q:r|d}\frac{\lambda_{d}}{d}$, a straightforward
exercise we leave to the reader.

######  Corollary 6.4.

We have $|F_{\chi,Q}(n)|\ll\tau(n)\log^{3}Q$ pointwise. Consequently,

$|\Lambda_{\sharp,Q,\sigma_{0}}(n)|\ll\tau(n)\log^{3}Q(\sum_{\rho\in\Xi_{Q}^{*}(\sigma_{0})}n^{\Re\rho-1}).$
(6.15)

###### Proof.

Set $f(n):=\sum_{r\leqslant Q:(r,q)=1}\frac{\mu(r)}{\phi(r)}c_{r}(n)$.
Applying Lemma 6.3 with $v(r)=\frac{\mu(r)}{\phi(r)}1_{(r,q)=1}$, we obtain
$f(n)=\sum_{d|n:d\leqslant Q}\lambda_{d}$ with

$\frac{\lambda_{d}}{d}=\sum_{\begin{subarray}{c}d|r\\\ r\leqslant Q\\\
(r,q)=1\end{subarray}}\frac{\mu(\frac{r}{d})\mu(r)}{\phi(r)}=\frac{\mu(d)}{\phi(d)}\sum_{\begin{subarray}{c}k\leqslant
Q/d\\\ (dk,q)=1\\\ (d,k)=1\end{subarray}}\frac{\mu^{2}(k)}{\phi(k)}.$

(Here, of course, we wrote $r=dk$, noting further that the sum is supported
where $r$ is squarefree, which means that $d$ and $k$ are coprime.) It follows
that

$|\lambda_{d}|\leqslant\frac{d}{\phi(d)}\sum_{k\leqslant
Q}\frac{1}{\phi(k)}\ll\log^{2}Q.$

Thus $|f(n)|\leqslant\tau(n)\log^{2}Q$, from which the stated bound follows
immediately using (6.6). (We could, of course, easily save almost two powers
of log by using less crude bounds on $\frac{m}{\phi(m)}$ if we wanted to.)

The bound (6.15) is immediate from this and the definition (Definition 4.4) of
$\Lambda_{\sharp,Q,\sigma_{0}}$. ∎

##  Part III Preliminaries to the main construction

###  7\. Zeroes and density estimates

In this section we assemble some more sophisticated zero-density estimates
needed for the main construction. Recall the definition (Definition 4.1) of
the multiset $\Xi_{Q}(\sigma_{0})$. One main aim of this section will be to
show the existence of a “good scale” $T$ at which any exceptional zero in
$\Xi_{T}(\sigma_{0})$ (that is, a real zero of a real $L(s,\chi)$ very close
to $s=1$) has fairly small modulus. The key result of this section is
Proposition 7.7.

The manipulations in this section are rather similar to those in the standard
proof of Linnik’s theorem as presented, for example, in [11, Section 18.4].
The main difference here is that we need to consider characters to all moduli
$q\leqslant Q$, rather than just a single $q$, which means we must appeal to
more general zero-density estimates.

Let us recall some facts about zeroes of $L$-functions. In this section
$\lambda_{1},\lambda_{2},\lambda_{3},\lambda_{4}$ are fixed absolute positive
constants. Once again we adopt the standard convention in analytic number
theory of writing, for a nontrivial zero $\rho$ of some $L$-function,
$\rho=\beta+i\gamma$. Somewhat less standardly, we always write
$\sigma:=1-\beta$, thus $\Re\rho=1-\sigma$.

Let us recall some standard facts about zeros. The first is the Landau-Page
theorem, in the form stated at the beginning of [1, Section 6].

######  Proposition 7.1.

There is an absolute, computable constant $\lambda_{1}\in(0,1]$ such that the
following is true for any parameter $Q\geqslant 10$: with possibly one
exception, all $\rho\in\Xi_{Q}(\frac{1}{2})$ satisfy
$\sigma\geqslant\frac{\lambda_{1}}{\log Q}$. The exception, if it exists, is a
simple real zero of $L(s,\chi_{*})$ for some real Dirichlet character
$\chi_{*}$ of conductor $q_{*}\leqslant Q$. This zero, if it exists, is called
the _exceptional zero_ at scale $Q$.

The second is a result of Landau.

######  Proposition 7.2.

Suppose that $\chi_{1},\chi_{2}$ are distinct real characters modulo
$q_{1},q_{2}$, with real zeros at $1-\sigma_{1},1-\sigma_{2}$ respectively.
Then

$\max(\sigma_{1},\sigma_{2})\geqslant\frac{\lambda_{1}}{\log q_{1}q_{2}}.$

Using these facts together, we can locate scales $Q$ at which (essentially)
any exceptional zero has relatively small modulus.

######  Proposition 7.3.

Let $\kappa\in(0,1)$ be given. Then for any $X\geqslant 10^{1/\kappa}$, and
for either $Q=X$ or $Q=X^{\kappa}$, at least one of the following holds:

  1. (1)

(first case) all zeroes in $\Xi_{Q}(\frac{1}{2})$ satisfy
$\sigma\geqslant\frac{\lambda_{1}\kappa}{2\log Q}$;

  2. (2)

(second case) there is an exceptional zero at scale $Q$, but its modulus
$q_{*}$ satisfies $q_{*}<Q^{\kappa}$.

_Remarks._ To avoid confusion, for the time being we call these the first and
second cases rather than the unexceptional and exceptional cases since the
first case does not strictly preclude an exceptional zero at scale $Q$ in the
sense of Proposition 7.1; there could be a zero with
$\frac{\lambda_{1}\kappa}{2\log Q}\leqslant\sigma<\frac{\lambda_{1}}{\log Q}$.

Proposition 7.3 is very closely related to, for example, [19, Corollary 11.9].

###### Proof of Proposition 7.3.

Consider first of all the scale $Q=X$. If there is no exceptional zero at this
scale (in the sense of Proposition 7.1) then we are in case (1) and indeed we
have the stronger bound $\sigma\geqslant\frac{\lambda_{1}}{\log Q}$. Suppose
then that there is an exceptional zero $\rho_{*}=1-\sigma_{*}$ at this scale.
If $\sigma_{*}\geqslant\frac{\lambda_{1}\kappa}{2\log Q}$ then we are again in
case (1). If $q_{*}\leqslant Q^{\kappa}$ then we are in case (2). Suppose,
then, that $X^{\kappa}<q_{*}\leqslant X$ and
$\sigma_{*}<\frac{\lambda_{1}\kappa}{2\log X}$.

Now consider the scale $Q=X^{\kappa}$. By analogous reasoning, we are done
unless there is an exceptional zero $\rho^{\prime}_{*}$ at this scale, with
$X^{\kappa^{2}}<q^{\prime}_{*}\leqslant X^{\kappa}$ and
$\sigma^{\prime}_{*}<\frac{\lambda_{1}\kappa}{2\log X^{\kappa}}$.

Since $q^{\prime}_{*}\leqslant X^{\kappa}<q_{*}$, the zeros
$\rho_{*},\rho^{\prime}_{*}$ correspond to distinct characters. By Landau’s
result we obtain

$\frac{\lambda_{1}\kappa}{2\log
X^{\kappa}}\geqslant\max(\sigma_{*},\sigma^{\prime}_{*})\geqslant\frac{\lambda_{1}}{\log
q_{*}q^{\prime}_{*}}>\frac{\lambda_{1}}{\log X^{2}},$

a contradiction. ∎

We quote the following two results from [1]. Here, $\lambda_{2},\lambda_{3}$
are computable absolute constants.

######  Proposition 7.4.

Let $Q\geqslant 10$. We have, uniformly in $\alpha$,

$\\#\\{\rho\in\Xi_{Q}(\frac{1}{2}):\Re\rho\leqslant\alpha\\}\leqslant\lambda_{2}Q^{\lambda_{3}(1-\alpha)}.$
(7.1)

###### Proof.

This is the first statement in [1, Théorème 14], where it is noted that the
argument leads to explicit constants if desired. ∎

######  Proposition 7.5.

Let $Q\geqslant 10$. If there is an exceptional zero ($\rho_{*}$) at scale $Q$
then we have the stronger bound

$\\#\\{\rho\in\Xi_{Q}(\frac{1}{2}):\rho\neq\rho_{*},\Re\rho\leqslant\alpha\\}\leqslant\lambda_{2}(\sigma_{*}\log
Q)Q^{\lambda_{3}(1-\alpha)}.$ (7.2)

###### Proof.

This is the second statement in [1, Théorème 14]. ∎

_Remark._ Note that Proposition 7.4 is a grand log-free zero density estimate
and as such is the same as Proposition 5.1, except that in the latter we gave
an explicit exponent of $8$ in place of $\lambda_{3}$. In this section, the
implied constant $\lambda_{2}$ is also important, and moreover we must pair
Proposition 7.4 with Proposition 7.5, which is usually called _exceptional
zero repulsion_.

Explicit (large) values for $\lambda_{2},\lambda_{3}$ are obtained in
forthcoming work of Thorner and Zaman [35]. Using these, the exponent in
Theorem 1.1 could be made explicit if desired, but it would be extremely
small.

Let $M$ be the explicit absolute constant specified in (11.3), that is to say
$M=7\cdot 3^{6}\cdot 2^{22993}$.

######  Proposition 7.6.

There is an absolute constant $B$ such that the following holds for any
parameter $Q\geqslant 10$.

  * •

If there is no exceptional zero at scale $Q$,

$4M\sum_{\rho\in\Xi_{Q}(\frac{1}{2})}Q^{-B\sigma}\leqslant 1;$ (7.3)

  * •

If there is an exceptional zero $\rho_{*}$ at scale $Q$,

$Q^{-B\sigma_{*}}+2M\sum_{\rho\in\Xi_{Q}(\frac{1}{2})\setminus\\{\rho_{*}\\}}Q^{-B\sigma}\leqslant
1.$ (7.4)

###### Proof.

Let $\lambda_{4}\in(0,1)$ be a constant such that

$e^{-x}+\lambda_{4}\lambda_{2}x<1$ (7.5)

for all $x$ with $0<x<\lambda_{1}$ (a choice which works is
$\lambda_{4}:=\min(\frac{1}{2\lambda_{2}},\frac{1}{2\lambda_{1}\lambda_{2}})$).

_Unexceptional case._ Choose $k_{0}$ such that

$\lambda_{2}\sum_{k\geqslant
k_{0}}e^{-2^{k-1}}\leqslant\frac{\lambda_{4}}{4M}.$

Set

$S_{k}:=\\{\rho\in\Xi_{Q}(\frac{1}{2}):2^{k}\leqslant B\sigma\log
Q<2^{k+1}\\}.$

For all $\rho$, the fact that we are in the unexceptional case means that
$\sigma\log Q\geqslant\lambda_{1}$, so with $B$ chosen suitably (that is
$B\lambda_{1}>2^{k_{0}}$), $S_{k}$ is only nonempty for $k\geqslant k_{0}$.
From (7.1) we have

$|S_{k}|\leqslant\lambda_{2}Q^{\frac{\lambda_{3}2^{k+1}}{B\log
Q}}=\lambda_{2}e^{\frac{\lambda_{3}2^{k+1}}{B}}.$

Therefore

$\displaystyle\sum_{\rho\in\Xi_{Q}(\frac{1}{2})}Q^{-B\sigma}$
$\displaystyle=\sum_{k\geqslant k_{0}}\sum_{\rho\in
S_{k}}Q^{-B\sigma}\leqslant\sum_{k\geqslant k_{0}}|S_{k}|e^{-2^{k}}$
$\displaystyle\leqslant\lambda_{2}\sum_{k\geqslant
k_{0}}e^{\frac{\lambda_{3}}{B}2^{k+1}-2^{k}}\leqslant\lambda_{2}\sum_{k\geqslant
k_{0}}e^{-\frac{2^{k}}{2}},$

which is at most $\frac{1}{4M}$ by the choice of $k_{0}$. Here, in the
penultimate step, we also assumed that $B\geqslant 4\lambda_{3}$.

_Exceptional case._ We proceed essentially as before, but now defining

$S_{k}:=\\{\rho\neq\rho_{*}:2^{k}\leqslant B\sigma\log Q<2^{k+1}\\}.$

Once again, if $B$ is chosen suitably, $S_{k}$ is only nonempty for
$k\geqslant k_{0}$. From (7.2), we have

$|S_{k}|\leqslant\lambda_{2}(\sigma_{*}\log
Q)Q^{\frac{\lambda_{3}2^{k+1}}{B\log Q}}=\lambda_{2}(\sigma_{*}\log
Q)e^{\frac{\lambda_{3}}{B}2^{k+1}}.$

Much as before,

$\sum_{\rho\neq\rho_{*}}Q^{-B\sigma}\leqslant\lambda_{2}(\sigma_{*}\log
Q)\sum_{k\geqslant
k_{0}}e^{-\frac{2^{k}}{2}}\leqslant\frac{1}{4M}\lambda_{2}\lambda_{4}(\sigma_{*}\log
Q).$

However, by the choice of $\lambda_{4}$, and with $x:=\sigma_{*}\log
Q\leqslant\lambda_{1}$ in (7.5),

$\lambda_{2}\lambda_{4}(\sigma_{*}\log Q)<1-Q^{-\sigma_{*}}.$

This confirms the desired inequality.∎

Let us finish by stating the consequence of all this that we will need in the
what follows. In the following, the exponents $\frac{1}{120}$ and $10^{-6}$
are what turn out to be convenient later; it would be possible to specify any
positive values for them, at the expense of making $c$ smaller.

######  Proposition 7.7.

Let $M:=7\cdot 3^{6}\cdot 2^{22993}$. There is an absolute constant $c>0$ with
the following property. Suppose that $\sigma_{0}\leqslant\frac{1}{8}$. Let $N$
be a large integer. Then there is $T$, $N^{c}\leqslant T\leqslant
N^{\frac{1}{120}}$, such that if we list the zeros of $\Xi_{T}(\sigma_{0})$
(with multiplicity) in order of decreasing real part as
$\rho_{1},\dots,\rho_{J}$, (at least) one of the following holds, where
$\sigma_{j}:=1-\Re\rho_{j}$:

  1. (1)

We have

$\sum_{j=1}^{J}N^{-\frac{1}{16}\sigma_{j}}\leqslant\frac{1}{2M};$ (7.6)

  2. (2)

$\rho_{1}$ is a simple, real zero of a real character $\chi_{1}$ of conductor
$q_{1}\leqslant T^{10^{-6}}$, and

$N^{-\frac{1}{16}\sigma_{j}}+2M\sum_{j=2}^{J}N^{-\frac{1}{16}\sigma_{j}}\leqslant
1.$ (7.7)

Moreover,

$J\ll T.$ (7.8)

###### Proof.

Set $b:=\min(\frac{1}{16B},\frac{\lambda_{1}\kappa}{32\log(4M)})$. Apply
Proposition 7.3 with $X:=N^{b}$ and $\kappa:=10^{-6}$ and let $T=Q=X$ or
$X^{\kappa}$ as in the conclusion of that proposition. Then either (first
case) we have

$\sigma_{1}\geqslant\frac{\lambda_{1}\kappa}{2\log
T}\geqslant\frac{\lambda_{1}\kappa}{2\log X}$ (7.9)

or (second case) there is an exceptional zero $\rho_{1}$ at scale $T$, with
modulus $q_{1}\leqslant T^{\kappa}$.

Now apply Proposition 7.6 with $Q=T$. Suppose we are in the first case. If
there is no exceptional zero at scale $T$ we apply (7.3), which gives

$\sum_{j=1}^{J}N^{-\frac{1}{16}\sigma_{j}}\leqslant\sum_{j=1}^{J}T^{-B\sigma_{j}}\leqslant\frac{1}{4M}.$

If there is an exceptional zero at scale $T$ (which must be $\rho_{1}$) then
we must instead apply (7.4). Ignoring the term with the exceptional zero, as
above this gives

$\sum_{j=2}^{J}N^{-\frac{1}{16}\sigma_{j}}\leqslant\frac{1}{4M}.$ (7.10)

Moreover, by the lower bound (7.9) on $\sigma_{1}$ we have

$N^{-\frac{1}{16}\sigma_{1}}\leqslant N^{-\frac{\lambda_{1}\kappa}{32\log
X}}=e^{-\frac{\lambda_{1}\kappa}{32b}}\leqslant\frac{1}{4M}$

by the choice of $b$. Adding this to (7.10) gives (7.6) in this case as well.

Now suppose we are in the second case (of Proposition 7.3, thus $\rho_{1}$ is
exceptional with modulus $q_{1}\leqslant T^{\kappa}$). Applying (7.4) gives,
since $b\leqslant\frac{1}{16B}$,

$N^{-\frac{1}{16}\sigma_{j}}+2M\sum_{j=2}^{J}N^{-\frac{1}{16}\sigma_{j}}\leqslant
T^{-B\sigma_{1}}+2M\sum_{j=2}^{J}T^{-B\sigma_{j}}\leqslant 1.$

This is (7.7), so we have indeed shown that one of (1), (2) holds.

Finally, (7.8) follows immediately from (5.1) and the assumption that
$\sigma_{0}\leqslant\frac{1}{8}$. ∎

Finally, we will require the following well-known bound.

######  Lemma 7.8 (Page’s bound).

We have $\sigma_{1}\gg q_{1}^{-1/2}(\log q_{1})^{-2}\gg q_{1}^{-1}$.

###### Proof.

See [19, Corollary 11.12]. Note that the implied constant here can be made
explicit if desired; one has Siegel’s much stronger bound
$\sigma_{1}\gg_{\varepsilon}q_{1}^{-\varepsilon}$ for any $\varepsilon>0$ (see
[19, Theorem 11.14]), but here the implied constant is not explicit when
$\varepsilon<\frac{1}{2}$.∎

###  8\. Periodic functions and Ramanujan series

In this section we set out some basic nomenclature for periodic functions
$f:\mathbf{Z}\rightarrow\mathbf{C}$ and for certain special periodic functions
which we shall call Ramanujan series (following, for example, [25], and
inspired by [24]), and we will prove some basic lemmas that will be needed
later.

####  8.1. Basic nomenclature and definitions

_Periodic functions. Rational Fourier series._ The first key observation is
that any periodic function $f:\mathbf{Z}\rightarrow\mathbf{C}$ has a (unique)
_rational Fourier series_ , that is to say we may write

$f(n)=\sum_{\lambda\in\mathbf{Q}/\mathbf{Z}}f^{\wedge}(\lambda)e(\lambda n)$
(8.1)

for certain $f^{\wedge}(\lambda)\in\mathbf{C}$, which we call the rational
Fourier coefficients of $f$, and with this sum being supported on just
finitely many $\lambda$. To see the existence of such a series, simply observe
that

$1_{n\equiv b(\mbox{\scriptsize
mod}\,r)}=\frac{1}{r}\sum_{x\in\mathbf{Z}/r\mathbf{Z}}e(-\frac{xb}{r})e(\frac{xn}{r}).$
(8.2)

Any periodic function may be written as a finite linear combination of basic
functions like this.

_Norms, support and averages._ If $f$ is a periodic function with rational
Fourier coefficients $f^{\wedge}(\lambda)$ then we write

$\|f\|^{\wedge}_{\infty}:=\max_{\lambda}|f^{\wedge}(\lambda)|\quad\mbox{and}\quad\|f\|^{\wedge}_{1}:=\sum_{\lambda}|f^{\wedge}(\lambda)|.$

We also define the support $\operatorname{s}(f)$ to be the largest denominator
of any $\lambda$ for which $f^{\wedge}(\lambda)\neq 0$ (when $\lambda$ is
written in lowest terms).

If $f:\mathbf{Z}\rightarrow\mathbf{C}$ is a periodic function then we write
$\operatorname{Av}f$ for the average of $f$ (which is well-defined, either as
the average of $f$ over any period, or as
$\lim_{X\rightarrow\infty}X^{-1}\sum_{x=1}^{X}f(x)$).

We have the orthogonality relation that $\operatorname{Av}e(\lambda
n)=1_{\lambda=0}$, and so from (8.1) we see that
$f^{\wedge}(\lambda)=\operatorname{Av}f(n)e(-\lambda n)$. In particular the
rational Fourier expansion of a function is unique, and also

$\|f\|^{\wedge}_{\infty}\leqslant\operatorname{Av}|f|.$ (8.3)

_Positivity._ We will say that a periodic function $f$ is _Fourier-positive_
if $f^{\wedge}$ is real and non-negative. If
$f,g:\mathbf{Z}\rightarrow\mathbf{C}$ are two periodic functions then we write
$g\prec f$ to mean that $|g^{\wedge}(\lambda)|\leqslant f^{\wedge}(\lambda)$
for all $\lambda\in\mathbf{Q}/\mathbf{Z}$. In particular, $f$ must be Fourier-
positive for this notation to apply. We will use this notation fairly
extensively throughout the paper.

A simple example of a Fourier-positive function is, for any fixed $r$, the
function $f(n):=1_{r|n}$, which is Fourier positive by (8.2) (with $b=0$).
Note that for this function we have

$\|1_{r|n}\|^{\wedge}_{\infty}=\frac{1}{r},\quad\|1_{r|n}\|^{\wedge}_{1}=1,\quad\operatorname{s}(1_{r|n})=r.$
(8.4)

_Ramanujan series._ We say that a periodic function $f$ in the form (8.1) is a
_Ramanujan series_ if $f^{\wedge}(\lambda)$ is supported where
$\operatorname{denom}(\lambda)$ is squarefree, and if it depends only on
$\operatorname{denom}(\lambda)$. Equivalently, we have an expansion

$f(n)=\sum_{q=1}^{\infty}\alpha(q)\sum_{a\in(\mathbf{Z}/q\mathbf{Z})^{*}}e(\frac{an}{q})=\sum_{q=1}^{\infty}\alpha(q)c_{q}(n),$
(8.5)

supported on finitely many squarefree $q$.

####  8.2. Simple properties

Here are some simple properties of positivity which we will use several times.

######  Proposition 8.1.

We have the following statements concerning periodic functions from
$\mathbf{Z}$ to $\mathbf{C}$.

  1. (1)

If $F,G$ are Fourier-positive then so are $F+G$, $FG$ and $tF$ for
$t\in\mathbf{R}_{\geqslant 0}$;

  2. (2)

If $(F_{i})_{i\in I}$ is a finite collection of Fourier-positive functions
then any non-negative linear combination $\sum_{i\in I}t_{i}F_{i}$ is Fourier
positive, where $t_{i}\in\mathbf{R}_{\geqslant 0}$;

  3. (3)

If $F\prec G$ then $\overline{F}\prec\overline{G}$ and $tF\prec tG$ for
$t\in\mathbf{R}_{\geqslant 0}$;

  4. (4)

If $F^{\prime}_{1}\prec F_{1}$ and $F^{\prime}_{2}\prec F_{2}$ then
$F^{\prime}_{1}+F^{\prime}_{2}\prec F_{1}+F_{2}$ and
$F^{\prime}_{1}F^{\prime}_{2}\prec F_{1}F_{2}$;

  5. (5)

If $F^{\prime}\prec F$ and if $G$ is positive then $F^{\prime}G\prec FG$. In
particular, this holds if $G(n)=e(\lambda n)$.

  6. (6)

If $F$ has $M$ as a period, $F^{\wedge}$ is supported on rationals $\lambda$
with $\operatorname{denom}(\lambda)|M$;

  7. (7)

If $F^{\prime},F$ have $M$ as a period, then $F^{\prime}\prec F$ if and only
if

$|\sum_{n\in\mathbf{Z}/M\mathbf{Z}}F^{\prime}(n)e(-\frac{an}{M})|\leqslant\sum_{n\in\mathbf{Z}/M\mathbf{Z}}F(n)e(-\frac{an}{M})$

for all $a\in\mathbf{Z}/M\mathbf{Z}$.

###### Proof.

(1) and (2) are straightforward. For the first statement in (3), note that
$\overline{F}^{\wedge}(\lambda)=\overline{F^{\wedge}(-\lambda)}$, so

$|\overline{F}^{\wedge}(\lambda)|=|F^{\wedge}(-\lambda)|\leqslant
G^{\wedge}(-\lambda)=\overline{G^{\wedge}(-\lambda)}=\overline{G}^{\wedge}(\lambda),$

the last step since $G^{\wedge}$ is real-valued (since $F\prec G$). The second
statement in (3) is clear. For (4), we use the formula

$(b_{1}b_{2})^{\wedge}(\lambda)=\sum_{\begin{subarray}{c}\lambda_{1},\lambda_{2}\in\mathbf{Q}/\mathbf{Z}\\\
\lambda_{1}+\lambda_{2}=\lambda(\mbox{\scriptsize
mod}\,1)\end{subarray}}b_{1}^{\wedge}(\lambda_{1})b_{2}^{\wedge}(\lambda_{2}),$
(8.6)

valid for any pair of periodic functions
$b_{1},b_{2}:\mathbf{Z}\rightarrow\mathbf{C}$. Applying this first with
$b_{i}=F^{\prime}_{i}$ and then with $b_{i}=F_{i}$, we obtain

$\displaystyle|(F^{\prime}_{1}F^{\prime}_{2})^{\wedge}(\lambda)|$
$\displaystyle\leqslant\sum_{\begin{subarray}{c}\lambda_{1},\lambda_{2}\in\mathbf{Q}/\mathbf{Z}\\\
\lambda_{1}+\lambda_{2}=\lambda(\mbox{\scriptsize
mod}\,1)\end{subarray}}|F_{1}^{\prime\wedge}(\lambda_{1})||F_{2}^{\prime\wedge}(\lambda_{2})|$
$\displaystyle\leqslant\sum_{\begin{subarray}{c}\lambda_{1},\lambda_{2}\in\mathbf{Q}/\mathbf{Z}\\\
\lambda_{1}+\lambda_{2}=\lambda(\mbox{\scriptsize
mod}\,1)\end{subarray}}F_{1}^{\wedge}(\lambda_{1})F_{2}^{\wedge}(\lambda_{2})=(F_{1}F_{2})^{\wedge}(\lambda),$

which is the multiplicative part of (4). The additive part of (4) is
straightforward. For (5), it suffices in view of (3) and (4) and the fact that
any Fourier-positive $G$ is a non-negative linear combination of $e(\lambda
n)$s to check the case $G(n)=e(\lambda n)$. To see this, observe that
$|(F^{\prime}G)^{\wedge}(\xi)|=|(F^{\prime})^{\wedge}(\xi-\lambda)|\leqslant
F(\xi-\lambda)=(FG)^{\wedge}(\xi)$, for all $\xi\in\mathbf{Q}/\mathbf{Z}$.
Item (6) follows from (8.2) and the uniqueness of rational Fourier series.
Finally, for (7) we note that
$\sum_{n\in\mathbf{Z}/M\mathbf{Z}}F(n)e(-\frac{an}{M})=MF^{\wedge}(\frac{a}{M})$,
so under the stated assumption we have
$|(F^{\prime})^{\wedge}(\frac{a}{M})|\leqslant F^{\wedge}(\frac{a}{M})$ for
all $a\in\mathbf{Z}/M\mathbf{Z}$. By item (6),
$|(F^{\prime})^{\wedge}(\lambda)|\leqslant F^{\wedge}(\lambda)$ for all
$\lambda\in\mathbf{Q}/\mathbf{Z}$. ∎

Next, some simple properties concerning norms and the support.

######  Lemma 8.2.

Suppose that $f:\mathbf{Z}\rightarrow\mathbf{C}$ is a periodic function. Then
the norms $\|f\|^{\wedge}_{1}$, $\|f\|^{\wedge}_{\infty}$ are invariant under
shifts: in particular
$\|f^{+}\|^{\wedge}_{\bullet}=\|f\|^{\wedge}_{\bullet}=\|f^{-}\|^{\wedge}_{\bullet}$
for both norms, where $f^{+}(n)=f(n+1)$ and $f^{-}(n)=f(n-1)$.

###### Proof.

This follows immediately from
$(f^{\pm})^{\wedge}(\lambda)=e(\pm\lambda)f^{\wedge}(\lambda)$, which follows
from the definition (8.1). ∎

######  Lemma 8.3.

Suppose that $b_{1},b_{2}:\mathbf{Z}\rightarrow\mathbf{C}$ are periodic
functions. Then

$\|b_{1}b_{2}\|^{\wedge}_{1}\leqslant\|b_{1}\|^{\wedge}_{1}\|b_{2}\|^{\wedge}_{1}.$
(8.7)
$\|b_{1}b_{2}\|^{\wedge}_{\infty}\leqslant\|b_{1}\|^{\wedge}_{\infty}\|b_{2}\|^{\wedge}_{1}$
(8.8)

If $b_{1},b_{2}$ have coprime periods then we have the stronger bound

$\|b_{1}b_{2}\|^{\wedge}_{\infty}=\|b_{1}\|^{\wedge}_{\infty}\|b_{2}\|^{\wedge}_{\infty}.$
(8.9)

Finally, we have

$\operatorname{s}(b_{1}b_{2})\leqslant\operatorname{s}(b_{1})\operatorname{s}(b_{2}).$
(8.10)

###### Proof.

The bounds (8.7), (8.8) are immediate from (8.6). For (8.9), suppose that the
periods of $b_{1},b_{2}$ are $M_{1},M_{2}$ respectively, and that
$M_{1},M_{2}$ are coprime. By Proposition 8.1 (6),
$b_{i}^{\wedge}(\lambda_{i})$ is supported where
$\operatorname{denom}(\lambda_{i})$ divides $M_{i}$. Now if
$\frac{a_{1}}{M_{1}}+\frac{a_{2}}{M_{2}}\equiv\frac{a^{\prime}_{1}}{M_{1}}+\frac{a^{\prime}_{2}}{M_{2}}(\operatorname{mod}\,1)$
then, clearing denominators and using the coprimality of $M_{1},M_{2}$, we see
that $a_{1}\equiv a^{\prime}_{1}(\operatorname{mod}\,M_{1})$ and $a_{2}\equiv
a^{\prime}_{2}(\operatorname{mod}\,M_{2})$, so
$\frac{a_{1}}{M_{1}}\equiv\frac{a^{\prime}_{1}}{M_{1}}(\operatorname{mod}\,1)$
and
$\frac{a_{2}}{M_{2}}\equiv\frac{a^{\prime}_{2}}{M_{2}}(\operatorname{mod}\,1)$.
It follows that, in (8.6), all the sums $\lambda_{1}+\lambda_{2}$ with
$\lambda_{i}\in\operatorname{Supp}(b_{i}^{\wedge})$ are distinct, and so for
each $\lambda$ there is at most one choice of $\lambda_{1},\lambda_{2}$ with
$b_{1}^{\wedge}(\lambda_{1}),b_{2}^{\wedge}(\lambda_{2})\neq 0$, and so (8.9)
follows. Finally, (8.10) is clear from (8.6). ∎

We remark on the case of Dirichlet characters, which will arise several times
in the paper.

######  Lemma 8.4.

Suppose that $\chi$ is a primitive Dirichlet character to modulus $q$. Then
$\|\chi\|^{\wedge}_{\infty}\leqslant q^{-\frac{1}{2}}$ and
$\|\chi\|^{\wedge}_{1}\leqslant q^{\frac{1}{2}}$.

###### Proof.

The second statement follows from the first, because $\chi$ is $q$-periodic
and so its rational Fourier series is supported on rationals with denominator
$q$. By Fourier analysis on $\mathbf{Z}/q\mathbf{Z}$ we have
$\chi(n)=\sum_{a\in\mathbf{Z}/q\mathbf{Z}}\gamma(a)e(an/q)$, where
$\gamma(a):=\sum_{x\in\mathbf{Z}/q\mathbf{Z}}\chi(x)e(-ax/q)$. By [11,
equation (3.12)] and the remarks following it,
$\gamma(a)=\overline{\chi}(a)\tau(\chi)$, where $\tau(\chi)$ is the Gauss sum,
which has modulus $\sqrt{q}$ by [11, Lemma 3.1]. The first statement of the
lemma follows. ∎

Let us also record basic bounds on the Fourier norms of the functions
$F_{\chi,Q}$ and $\Lambda_{Q}$, which are crucial in the paper.

######  Lemma 8.5.

Let $\chi$ be a primitive character to modulus $q$. We have

$\|F_{\chi,Q}\|^{\wedge}_{1}\leqslant Qq^{\frac{1}{2}}.$ (8.11)

In particular,

$\|\Lambda_{Q}\|^{\wedge}_{1}\leqslant Q.$ (8.12)

###### Proof.

From the definition (4.1) and the evaluation (5.5) for Gauss sums, we have the
bound $|c_{\chi}(b,r)|\leqslant q^{\frac{1}{2}}\phi(r)^{-1}$. Recall the
definition (4.2) of $F_{\chi,Q}$. Summing over the $\phi(r)$ values of
$b\in(\mathbf{Z}/r\mathbf{Z})^{*}$, and then summing over all $r$ such that
$q|r$ and $\frac{r}{q}\leqslant Q$, the result follows.

The second statement (8.12) is immediate upon taking $\chi=\chi_{0}$, the
prinicipal character, and recalling (4.4). ∎

####  8.3.
$\Lambda_{\mathbf{Z}/p\mathbf{Z}},\tau^{2}_{\mathbf{Z}/p\mathbf{Z}}$ and their
properties

The following two types of periodic function will play an important role in
the paper. For $p$ a prime, write (as in (6.3))

$\Lambda_{\mathbf{Z}/p\mathbf{Z}}(n):=\left\\{\begin{array}[]{ll}0&\mbox{if
$p|n$}\\\ \frac{p}{p-1}&\mbox{if $(p,n)=1$}.\end{array}\right.$ (8.13)

and

$\tau^{2}_{\mathbf{Z}/p\mathbf{Z}}(n):=\left\\{\begin{array}[]{ll}\frac{4p}{p+3}&\mbox{if
$p|n$}\\\ \frac{p}{p+3}&\mbox{if $(p,n)=1$}.\end{array}\right.$ (8.14)

The definitions are chosen so
$\operatorname{Av}\Lambda_{\mathbf{Z}/p\mathbf{Z}}=\operatorname{Av}\tau^{2}_{\mathbf{Z}/p\mathbf{Z}}=1$.

The function $\Lambda_{\mathbf{Z}/p\mathbf{Z}}$, which is somewhat standard,
was already briefly discussed in Section 6. The notation
$\tau^{2}_{\mathbf{Z}/p\mathbf{Z}}$ is not standard; this is supposed to
remind the reader that this function behaves somewhat like a
$(\operatorname{mod}\,p)$ analogue of the squared divisor function $\tau^{2}$,
as discussed in subsection 3.1, albeit normalised to have average value $1$.

It is easily checked that the rational Fourier series of
$\Lambda_{\mathbf{Z}/p\mathbf{Z}},\tau^{2}_{\mathbf{Z}/p\mathbf{Z}}$ are

$\Lambda_{\mathbf{Z}/p\mathbf{Z}}(n)=1-\frac{1}{p-1}\sum_{r\in(\mathbf{Z}/p\mathbf{Z})^{*}}e(\frac{rn}{p})=1-\frac{1}{p-1}c_{p}(n)$
(8.15)

and

$\tau^{2}_{\mathbf{Z}/p\mathbf{Z}}(n)=1+\frac{3}{p+3}\sum_{r\in(\mathbf{Z}/p\mathbf{Z})^{*}}e(\frac{rn}{p})=1+\frac{3}{p+3}c_{p}(n),$
(8.16)

so in particular both are Ramanujan series. Moreover,
$\tau^{2}_{\mathbf{Z}/p\mathbf{Z}}$ is Fourier-positive, though
$\Lambda_{\mathbf{Z}/p\mathbf{Z}}$ is not.

Let us also note the following for future use.

######  Lemma 8.6.

We have

$\|\Lambda_{\mathbf{Z}/p\mathbf{Z}}\|^{\wedge}_{\infty}=1,\qquad\|\Lambda_{\mathbf{Z}/p\mathbf{Z}}\|^{\wedge}_{1}=2$
(8.17)

and

$\|\tau^{2}_{\mathbf{Z}/p\mathbf{Z}}\|^{\wedge}_{\infty}=1,\qquad\|\tau^{2}_{\mathbf{Z}/p\mathbf{Z}}\|^{\wedge}_{1}\leqslant
4.$ (8.18)

The following simple lemma plays a critical role in our paper. Here, recall,
we use the notation $f^{+}(n)=f(n+1)$, $f^{-}(n)=f(n-1)$.

######  Lemma 8.7.

For every prime $p$,
$\Lambda_{\mathbf{Z}/p\mathbf{Z}}^{+}\Lambda_{\mathbf{Z}/p\mathbf{Z}}^{-}\tau^{2}_{\mathbf{Z}/p\mathbf{Z}}$
is Fourier-positive. Also, we have the bound

$\|\Lambda_{\mathbf{Z}/p\mathbf{Z}}^{+}\Lambda_{\mathbf{Z}/p\mathbf{Z}}^{-}\tau^{2}_{\mathbf{Z}/p\mathbf{Z}}\|^{\wedge}_{\infty}\leqslant
1+O(p^{-2}).$ (8.19)

###### Proof.

Set
$u_{p}:=(1-\frac{1}{p})^{2}(1+\frac{3}{p})\Lambda_{\mathbf{Z}/p\mathbf{Z}}^{+}\Lambda_{\mathbf{Z}/p\mathbf{Z}}^{-}\tau^{2}_{\mathbf{Z}/p\mathbf{Z}}$.
Then one may check that

$u_{p}(n)=\left\\{\begin{array}[]{ll}0&\mbox{if $n\equiv\pm
1(\operatorname{mod}\,p)$}\\\ 4&\mbox{if $n\equiv
0(\operatorname{mod}\,p)$}\\\ 1&\mbox{otherwise}.\end{array}\right.$

If $p\neq 2$ we may compute the discrete Fourier transform
$\hat{u}_{p}(k):=p^{-1}\sum_{n\in\mathbf{Z}/p\mathbf{Z}}u_{p}(n)e(-kn/p)$ as
follows:

$\hat{u}_{p}(k)=\left\\{\begin{array}[]{ll}\frac{1}{p}(3-2\cos\frac{2\pi
k}{p})&k\neq 0\\\ 1+\frac{1}{p}&k=0.\end{array}\right.$ (8.20)

Note that $\hat{u}_{p}(k)$ is real and positive, indeed
$\hat{u}_{p}(0)=1+\frac{1}{p}$ and $\hat{u}_{p}(k)\geqslant\frac{1}{p}$.

By Fourier inversion in $\mathbf{Z}/p\mathbf{Z}$,

$u_{p}(n)=1+\frac{1}{p}+\frac{1}{p}\sum_{k\neq 0}(3-2\cos\frac{2\pi
k}{p})e(\frac{kn}{p}),$

and so $u_{p}$ is Fourier-positive. When $p=2$ one may check that
$\hat{u}_{2}(0)=\hat{u}_{2}(1)=2$ and so these inequalities also hold.

Multiplying through by $(1-\frac{1}{p})^{-2}(1+\frac{3}{p})^{-1}$, we see that

$\|\Lambda_{\mathbf{Z}/p\mathbf{Z}}^{+}\Lambda_{\mathbf{Z}/p\mathbf{Z}}^{-}\tau^{2}_{\mathbf{Z}/p\mathbf{Z}}\|^{\wedge}_{\infty}\leqslant(1-\frac{1}{p})^{-2}(1+\frac{3}{p})^{-1}\max(1+\frac{1}{p},\frac{5}{p})=1+O(p^{-2}),$

which is (8.19). ∎

Products of the $\Lambda_{\mathbf{Z}/p\mathbf{Z}}$ and of the
$\tau^{2}_{\mathbf{Z}/p\mathbf{Z}}$ will be important in the paper. In fact,
we have already seen $\prod_{p\leqslant
R}\Lambda_{\mathbf{Z}/p\mathbf{Z}}(n)$; it is the same thing as
$\tilde{\Lambda}_{R}(n)$, the normalised characteristic function of the
$R$-almost primes, as defined in (6.10). Let us record this observation here
explicitly:

$\tilde{\Lambda}_{R}(n)=\prod_{p\leqslant
R}\Lambda_{\mathbf{Z}/p\mathbf{Z}}(n).$ (8.21)

The product of the $\tau^{2}_{\mathbf{Z}/p\mathbf{Z}}$ is not something we
have seen yet, but it and its truncation are equally important in the paper.

######  Definition 8.8.

Let $R$ be a parameter. Then we define

$\tilde{H}_{R}(n):=\prod_{p\leqslant R}\tau^{2}_{\mathbf{Z}/p\mathbf{Z}}(n),$

where $\tau^{2}_{\mathbf{Z}/p\mathbf{Z}}$ is defined as in (8.14).

By (8.16) and the multiplicativity of Ramanujan sums, $\tilde{H}_{R}(n)$ is a
Ramanujan series

$\tilde{H}_{R}(n)=\sum_{q|R!}\eta(q)\sum_{a\in(\mathbf{Z}/q\mathbf{Z})^{*}}e(\frac{an}{q}).$

Here, for $q|R!$ we have

$\eta(q):=\left\\{\begin{array}[]{ll}\prod_{p|q}\frac{3}{p+3}&\mbox{if $q$ is
squarefree}\\\ 0&\mbox{otherwise}.\end{array}\right.$

We also introduce the truncated version of $\tilde{H}$.

######  Definition 8.9.

Let $Q$ be a parameter. Then we define

$H_{Q}(n):=\sum_{q\leqslant
Q}\eta(q)\sum_{a\in(\mathbf{Z}/q\mathbf{Z})^{*}}e(\frac{an}{q}).$

This is an important function in the paper, as described in Subsection 3.1. We
have $\eta(q)\leqslant\frac{3^{\omega(q)}}{q}\leqslant q^{-1+o(1)}$, where
$\omega(q)$ is the number of distinct prime factors of $q$. Therefore we have
the bound

$\|H^{\wedge}_{Q}\|_{1}\leqslant Q^{1+o(1)}.$ (8.22)

####  8.4. A class of periodic functions

It turns out that the functions $\Lambda_{Q}$ and $H_{Q}$ belong to a certain
class of periodic functions on $\mathbf{Z}$ which has nice closure properties
under shifts and pointwise multiplication. This fact will be important later
in the paper.

######  Definition 8.10.

Let $X\geqslant 1$ be an integer and $B\geqslant 0$ a real parameter. Then we
denote by $\mathscr{C}_{B}(X)$ the class of periodic
$f:\mathbf{Z}\rightarrow\mathbf{C}$ such that $f^{\wedge}(\lambda)$ is
supported on $\lambda$ with $\operatorname{denom}(\lambda)$ squarefree and at
most $X$, and such that if $q=\operatorname{denom}(\lambda)$ then
$|f^{\wedge}(\lambda)|\leqslant\tau(q)^{B}/q$.

######  Lemma 8.11.

We have $\Lambda_{Q},H_{Q}\in\mathscr{C}_{2}(Q)$.

###### Proof.

For $\Lambda_{Q}$ (defined in (3.3)), this is just a case of checking that
$|\frac{\mu(q)}{\phi(q)}|\leqslant\frac{\tau(q)^{2}}{q}$, which is true by
some distance since
$\frac{1}{\phi(q)}=\prod_{p|q}\frac{1}{p-1}\leqslant\prod_{p|q}\frac{2}{p}=\frac{\tau(q)}{q}$.

For $H_{Q}$, we must show that $\eta(q)\leqslant\tau(q)^{2}/q$. Noting that
when $q$ is squarefree we have $\prod_{p|q}3=\tau(q)^{\frac{\log 3}{\log
2}}<\tau(q)^{2}$ gives this bound immediately. ∎

It is clear from the definition that $\mathscr{C}_{B}(X)$ is closed under
shifts, that is to say if $f(n)\in\mathscr{C}_{B}(X)$ then
$f(n+h)\in\mathscr{C}_{B}(X)$. Slightly less obvious is the fact that these
classes are (weakly) closed under taking products, which is the content of
Lemma 8.12 below. Here, for $\lambda\in\mathbf{R}_{>0}$ we write
$\lambda\mathscr{C}_{B}(X)$ for those series of the form $\lambda f$,
$f\in\mathscr{C}_{B}(X)$.

######  Lemma 8.12.

Suppose that $f_{1}\in\mathscr{C}_{B_{1}}(X_{1})$ and
$f_{2}\in\mathscr{C}_{B_{2}}(X_{2})$. Then
$f_{1}f_{2}\in(\log^{O_{B_{1},B_{2}}(1)}X_{1})\mathscr{C}_{B_{1}+2B_{2}+3}(X_{1}X_{2})$.

To prove this result we will need a counting result, Lemma 8.13 below, about
denominators of sums of fractions (when written in lowest terms).

Suppose that $q,r$ are squarefree and that $(a,q)=(b,r)=1$, and set

$d:=\operatorname{denom}(\frac{a}{q}+\frac{b}{r})=\frac{qr}{(ar+bq,qr)}.$

Then $\frac{qr}{(q,r)^{2}}|d|[q,r]$ (and in particular $d$ is squarefree).

######  Lemma 8.13.

Suppose that $q,r$ are squarefree and that $b\in(\mathbf{Z}/r\mathbf{Z})^{*}$.
Then

$\\#\\{a\in(\mathbf{Z}/q\mathbf{Z})^{*}:\operatorname{denom}(\frac{a}{q}+\frac{b}{r})=d\\}\leqslant\frac{d(q,r)}{r}.$

###### Proof.

If $d\nmid[q,r]$ then the left-hand side is empty and the result is trivial.
Suppose, then, that $d|[q,r]$. The denominator condition is equivalent to
$(ar+bq,qr)=qr/d$, and so is contained in the condition $ar+bq\equiv
0(\operatorname{mod}\,qr/d)$. Dividing through by $(q,r)$ and setting
$r^{\prime}:=r/(q,r)$, $q^{\prime}:=q/(q,r)$ (thus $q^{\prime},r^{\prime}$ are
coprime) and $t:=qr/d(q,r)=[q,r]/d$, this condition is equivalent to

$ar^{\prime}+bq^{\prime}\equiv 0(\operatorname{mod}\,t).$ (8.23)

If this condition is satisfied, $t$ must be coprime to $r^{\prime}$. Indeed if
$p|(t,r^{\prime})$ then $p|bq^{\prime}=(ar^{\prime}+bq^{\prime})-ar^{\prime}$.
But this is impossible since both $b$ and $q^{\prime}$ are coprime to
$r^{\prime}$. Moreover, since $t|[q,r]=qr^{\prime}$, it follows that $t|q$.

Returning to (8.23), as $a$ ranges over $\mathbf{Z}/q\mathbf{Z}$ then so does
$ar^{\prime}$, and so we simply need an upper bound for the number of
solutions $(\operatorname{mod}\,q)$ to a fixed congruence $x\equiv
c(\operatorname{mod}\,t)$, where $t|q$. Such an upper bound is $q/t$, and the
lemma follows. ∎

###### Proof of Lemma 8.12.

Suppose that $\lambda=\frac{a}{q}\in\mathbf{Q}/\mathbf{Z}$ is in lowest terms.
Then

$\displaystyle(f_{1}f_{2})^{\wedge}(\frac{a}{q})=\sum_{\begin{subarray}{c}q_{1}\leqslant
X_{1}\\\ q_{2}\leqslant
X_{2}\end{subarray}}\sum_{\begin{subarray}{c}a_{1}\in(\mathbf{Z}/q_{1}\mathbf{Z})^{*}\\\
a_{2}\in(\mathbf{Z}/q_{2}\mathbf{Z})^{*}\\\
\frac{a_{1}}{q_{1}}+\frac{a_{2}}{q_{2}}\equiv\frac{a}{q}(\mbox{\scriptsize
mod}\,1)\end{subarray}}f_{1}^{\wedge}(\frac{a_{1}}{q_{1}})f_{2}^{\wedge}(\frac{a_{2}}{q_{2}})$
$\displaystyle\leqslant\sum_{\begin{subarray}{c}q_{1}\leqslant X_{1}\\\
\mu^{2}(q_{1})=1\end{subarray}}\frac{\tau(q_{1})^{B_{1}}}{q_{1}}\sum_{d|q_{1}q}\frac{\tau(d)^{B_{2}}}{d}\\#\\{a_{1}\in(\mathbf{Z}/q_{1}\mathbf{Z})^{*}:\operatorname{denom}(\frac{a_{1}}{q_{1}}-\frac{a}{q})=d\\}.$

By Lemma 8.13, this is bounded above by

$\sum_{\begin{subarray}{c}q_{1}\leqslant X_{1}\\\
\mu^{2}(q_{1})=1\end{subarray}}\frac{\tau(q_{1})^{B_{1}}}{q_{1}}\sum_{d|q_{1}q}\tau(d)^{B_{2}}\frac{(q_{1},q)}{q}\leqslant\frac{\tau(q)^{B_{2}+1}}{q}\\!\\!\\!\sum_{\begin{subarray}{c}q_{1}\leqslant
X_{1}\\\
\mu^{2}(q_{1})=1\end{subarray}}\\!\\!\frac{\tau(q_{1})^{B_{1}+B_{2}+1}(q_{1},q)}{q_{1}}.$

Here, we used the rather crude bound

$\sum_{d|q_{1}q}\tau(d)^{B_{2}}\leqslant\tau(q_{1}q)\max_{d|q_{1}q}\tau(d)^{B_{2}}\leqslant\tau(q_{1}q)^{B_{2}+1}\leqslant\tau(q_{1})^{B_{2}+1}\tau(q)^{B_{2}+1}.$

The result now follows from Lemma B.2. ∎

####  8.5. The functions $\Phi_{r,b}$

We now turn to a different example of a Fourier-positive function, which will
feature heavily later on since they are important in constructing the damping
function $D$.

Let $r$ be any positive integer, and let $b\in\mathbf{Z}/r^{3}\mathbf{Z}$.
Then we define

$\Phi_{r,b}(x):=r^{\frac{5}{6}}1_{r|x}e(\frac{bx}{r^{3}}).$ (8.24)

_Remark._ Here, the constants $\frac{5}{6}$ and $3$ are convenient choices
which work for our later arguments. Any $0<c<1<C$ with $c$ sufficiently close
to $1$ and $C$ sufficiently large would work, though the exponent in the main
theorem would be affected.

The functions $\Phi_{r,b}$ are of course periodic. They are also Fourier
positive, since both $1_{r|x}$ and $e(\frac{bx}{r^{3}})$ are. Indeed,

$\Phi_{r,b}(n)=r^{-\frac{1}{6}}\sum_{t=0}^{r-1}e((\frac{t}{r}+\frac{b}{r^{3}})n).$
(8.25)

Note in particular that

$\|\Phi_{r,b}\|^{\wedge}_{1}=r^{\frac{5}{6}}$ (8.26)

and

$\operatorname{s}(\Phi_{r,b})\leqslant r^{3}.$ (8.27)

###  9\. Triple correlations of Ramanujan series

We turn now to a key technical result concerning the relationship between
certain products of translated Ramanujan series (as defined in (8.5)) and
their truncations. Here is the main result.

######  Proposition 9.1.

Let $h_{1},h_{2},h_{3}$ be distinct integers with $\max_{i}|h_{i}|\leqslant
H$. Consider three Ramanujan series

$f_{i}(n)=\sum_{q}\alpha_{i}(q)c_{q}(n),$

$i=1,2,3$, such that $\alpha_{i}(q)$ is supported on finitely many squarefrees
and satisfies the bound $|\alpha_{i}(q)|\leqslant\tau^{B}(q)/q$, where $\tau$
is the divisor function and $B$ is some parameter. Consider also their
truncations

$f_{i,X_{i}}(n):=\sum_{q\leqslant X_{i}}\alpha_{i}(q)c_{q}(n),$

where $X_{1},X_{2},X_{3}$ are some thresholds. Set
$X:=\min(X_{1},X_{2},X_{3})$. Consider the correlations

$F(n):=f_{1}(n+h_{1})f_{2}(n+h_{2})f_{3}(n+h_{3})$

and the truncated correlations

$F_{X_{1},X_{2},X_{3}}(n):=f_{1,X_{1}}(n+h_{1})f_{2,X_{2}}(n+h_{2})f_{3,X_{3}}(n+h_{3}).$

Then

$\|F-F_{X_{1},X_{2},X_{3}}\|^{\wedge}_{\infty}\ll_{B,\varepsilon}H^{3}X^{\varepsilon-1},$
(9.1)

for every $\varepsilon>0$.

_Remark._ Most likely, this proposition could be extended to products of an
arbitrary number of $f_{i}$ (rather than just 3) but we do not need any such
extension in this paper.

We need the following lemma in the proof.

######  Lemma 9.2.

Let $m_{1},m_{2}$ be distinct, nonzero integers. Let $r$ be a positive integer
and suppose that $b\in(\mathbf{Z}/r\mathbf{Z})^{*}$. Let $q_{1},q_{2}$ be
squarefree, and suppose that $P$ is an integer with $P|[q_{1},q_{2}]r$. Then

$\sum_{\begin{subarray}{c}a_{1}\in(\mathbf{Z}/q_{1}\mathbf{Z})^{*}\\\
a_{2}\in(\mathbf{Z}/q_{2}\mathbf{Z})^{*}\\\ a_{1}q_{2}r+a_{2}q_{1}r\equiv
bq_{1}q_{2}(\mbox{\scriptsize{mod}}\,P(q_{1},q_{2}))\end{subarray}}e(\frac{m_{1}a_{1}}{q_{1}}+\frac{m_{2}a_{2}}{q_{2}})\leqslant|m_{1}m_{2}(m_{1}-m_{2})|\tau(P)^{2}.$

###### Proof.

Set $q^{\prime}_{1}=q_{1}/(q_{1},q_{2})$,
$q^{\prime}_{2}=q_{2}/(q_{1},q_{2})$, $d:=P/(P,r)$ and $r^{\prime}:=r/(P,r)$.
The congruence $a_{1}q_{2}r+a_{2}q_{1}r\equiv
bq_{1}q_{2}(\operatorname{mod}\,P(q_{1},q_{2}))$ is equivalent to
$a_{1}q^{\prime}_{2}r+a_{2}q^{\prime}_{1}r\equiv
b[q_{1},q_{2}](\operatorname{mod}\,P)$. Moreover, since $(P,r)$ divides both
$P$ and $r$, if the congruence has a solution at all then
$b[q_{1},q_{2}]=v(P,r)$ for some $v$, and so the congruence is equivalent to
$a_{1}q^{\prime}_{2}r^{\prime}+a_{2}q^{\prime}_{1}r^{\prime}\equiv
v(\operatorname{mod}\,d)$. Note that $r^{\prime}$ is coprime to $d$, so the
congruence is equivalent to $a_{1}q^{\prime}_{2}+a_{2}q^{\prime}_{1}\equiv
u(\operatorname{mod}\,d)$, where
$u:=v(r^{\prime})^{-1}(\operatorname{mod}\,d)$. Thus our task is to show that

$S:=\sum_{\begin{subarray}{c}a_{1}\in(\mathbf{Z}/q_{1}\mathbf{Z})^{*}\\\
a_{2}\in(\mathbf{Z}/q_{2}\mathbf{Z})^{*}\\\
a_{1}q^{\prime}_{2}+a_{2}q^{\prime}_{1}\equiv
u(\mbox{\scriptsize{mod}}\,d)\end{subarray}}e(\frac{m_{1}a_{1}}{q_{1}}+\frac{m_{2}a_{2}}{q_{2}})\leqslant|m_{1}m_{2}(m_{1}-m_{2})|\tau(P)^{2}.$
(9.2)

We claim that $d|[q_{1},q_{2}]$. To see this, recall that $P|[q_{1},q_{2}]r$.
Therefore $d=P/(P,r)$ divides $[q_{1},q_{2}]r/(P,r)=[q_{1},q_{2}]r^{\prime}$.
However, $d$ and $r^{\prime}$ are coprime, so indeed $d|[q_{1},q_{2}]$.

Detecting the congruence $a_{1}q^{\prime}_{2}+a_{2}q^{\prime}_{1}\equiv
u(\operatorname{mod}\,d)$ using additive characters mod $d$, the sum to be
estimated is then

$S=\frac{1}{d}\sum_{\lambda(\mbox{\scriptsize mod}\,d)}e(-\frac{\lambda
u}{d})\\!\\!\\!\\!\\!\sum_{\begin{subarray}{c}a_{1}\in(\mathbf{Z}/q_{1}\mathbf{Z})^{*}\\\
a_{2}\in(\mathbf{Z}/q_{2}\mathbf{Z})^{*}\end{subarray}}e(\frac{m_{1}a_{1}}{q_{1}}+\frac{m_{2}a_{2}}{q_{2}}+\frac{\lambda(a_{1}q^{\prime}_{2}+a_{2}q^{\prime}_{1})}{d}).$
(9.3)

Set $t:=[q_{1},q_{2}]/d$ (so $t$ is an integer, by the above discussion) and
observe that

$\frac{q^{\prime}_{2}}{d}=\frac{q_{1}q^{\prime}_{2}}{dq_{1}}=\frac{[q_{1},q_{2}]/d}{q_{1}}=\frac{t}{q_{1}},$

and similarly $q^{\prime}_{1}/d=t/q_{2}$. Using these expressions, the sum
(9.3) can be rewritten as

$S=\frac{1}{d}\sum_{\lambda(\mbox{\scriptsize mod}\,d)}e(-\frac{\lambda
u}{d})\\!\\!\\!\\!\\!\sum_{a_{1}\in(\mathbf{Z}/q_{1}\mathbf{Z})^{*}}\\!\\!\\!\\!\\!e(\frac{a_{1}(m_{1}+\lambda
t)}{q_{1}})\\!\\!\\!\\!\\!\sum_{a_{2}\in(\mathbf{Z}/q_{2}\mathbf{Z})^{*}}\\!\\!\\!\\!\\!e(\frac{a_{2}(m_{2}+\lambda
t)}{q_{2}}).$ (9.4)

Now we use the inequality

$|\sum_{a\in(\mathbf{Z}/q\mathbf{Z})^{*}}e(\frac{an}{q})|\leqslant(q,n),$

which is a standard bound for Ramanujan sums (see [11, equation (3.5)] or [9,
Section 16.6]). Substituting into (9.4) gives

$|S|\leqslant\frac{1}{d}\sum_{\lambda(\mbox{\scriptsize
mod}\,d)}(q_{1},m_{1}+\lambda t)(q_{2},m_{2}+\lambda t).$ (9.5)

Suppose that $p$ is prime and that $p|(q_{1},m_{1}+\lambda t)$. Then certainly
$p|q_{1}$. If $p|t$, then we must have $p|m_{1}$. It follows that either
$p|\frac{q_{1}}{(q_{1},t)}$, or else $p|m_{1}$, and so (since $q_{1}$ is
squarefree)

$(q_{1},m_{1}+\lambda t)\leqslant|m_{1}|(\frac{q_{1}}{(q_{1},t)},m_{1}+\lambda
t).$ (9.6)

Note moreover that since $t|[q_{1},q_{2}]=q^{\prime}_{2}q_{1}$ we have
$t|q^{\prime}_{2}(q_{1},t)$, and hence
$\frac{q_{1}}{(q_{1},t)}=\frac{[q_{1},q_{2}]}{q^{\prime}_{2}(q_{1},t)}$
divides $\frac{[q_{1},q_{2}]}{t}=d$. Therefore (9.6) implies

$(q_{1},m_{1}+\lambda t)\leqslant|m_{1}|(d,m_{1}+\lambda t).$

Similarly,

$(q_{2},m_{2}+\lambda t)\leqslant|m_{2}|(d,m_{2}+\lambda t).$

Substituting into (9.5) gives

$|S|\leqslant\frac{|m_{1}m_{2}|}{d}\sum_{\lambda(\mbox{\scriptsize
mod}\,d)}(d,m_{1}+\lambda t)(d,m_{2}+\lambda t).$ (9.7)

Now since $t=[q_{1},q_{2}]/d$ and $[q_{1},q_{2}]$ is squarefree, $t$ is
coprime to $d$. Therefore it follows from (9.7) that

$|S|\leqslant\frac{|m_{1}m_{2}|}{d}\sum_{s(\mbox{\scriptsize
mod}\,d)}(d,s)(d,s+h),$ (9.8)

where $h:=m_{2}-m_{1}\neq 0$. Without loss of generality, $h>0$.

Now for any $s$, $(d,s)$ and $(d,s+h)$ are both divisors of $d$, and any
common factor of them must divide $h$. If $(d,s)=d_{1}$ and $(d,s+h)=d_{2}$
then $s\equiv 0(\operatorname{mod}\,d_{1})$ and
$s\equiv-h(\operatorname{mod}\,d_{2})$, which is a congruence condition
(possibly not satisfiable) mod $[d_{1},d_{2}]$. Note that
$[d_{1},d_{2}]=d_{1}d_{2}/(d_{1},d_{2})\geqslant d_{1}d_{2}/h$. Therefore, for
a fixed choice of $d_{1},d_{2}$, the number of such $s$ is at most
$d/[d_{1},d_{2}]\leqslant hd/d_{1}d_{2}$. It follows that

$\displaystyle\sum_{s(\mbox{\scriptsize mod}\,d)}(d,s)(d,$ $\displaystyle
s+h)=$
$\displaystyle=\sum_{d_{1},d_{2}|d}d_{1}d_{2}\\#\\{s\in\mathbf{Z}/d\mathbf{Z}:(d,s)=d_{1},(d,s+h)=d_{2}\\}$
$\displaystyle\leqslant\sum_{d_{1},d_{2}|d}d_{1}d_{2}\frac{hd}{d_{1}d_{2}}=hd\tau(d)^{2}.$

Substituting into (9.8) gives $|S|\leqslant h|m_{1}m_{2}|\tau(d)^{2}$, which
immediately implies the lemma.∎

######  Corollary 9.3.

Let $m_{1},m_{2}$ be distinct nonzero integers. Let $r$ be a positive integer
and suppose that $b\in(\mathbf{Z}/r\mathbf{Z})^{*}$. Suppose that
$q_{1},q_{2}$ are squarefree. Then, uniformly in $q_{3}$,

$\sum_{\begin{subarray}{c}a_{1}\in(\mathbf{Z}/q_{1}\mathbf{Z})^{*}\\\
a_{2}\in(\mathbf{Z}/q_{2}\mathbf{Z})^{*}\\\
\operatorname{denom}(\frac{a_{1}}{q_{1}}+\frac{a_{2}}{q_{2}}-\frac{b}{r})=q_{3}\end{subarray}}e(\frac{m_{1}a_{1}}{q_{1}}+\frac{m_{2}a_{2}}{q_{2}})\leqslant|m_{1}m_{2}(m_{1}-m_{2})|\tau(r[q_{1},q_{2}])^{3}.$

###### Proof.

The condition
$\operatorname{denom}(\frac{a_{1}}{q_{1}}+\frac{a_{2}}{q_{2}}-\frac{b}{r})=q_{3}$
is equivalent to
$(a_{1}q_{2}r+a_{2}q_{1}r-bq_{1}q_{2},q_{1}q_{2}r)=\frac{rq_{1}q_{2}}{q_{3}}$
(note it can only be satisfied if $q_{3}|rq_{1}q_{2}$, which implies
$q_{3}|r[q_{1},q_{2}]$ since $q_{3}$ is squarefree).

We may detect this condition by Möbius inversion, specifically the version in
Lemma B.5. Taking $m=a_{1}q_{2}r+a_{2}q_{1}r-bq_{1}q_{2}$, $n=rq_{1}q_{2}$ and
$\Delta=rq_{1}q_{2}/q_{3}$ in that lemma gives

$\displaystyle
1_{\operatorname{denom}(\frac{a_{1}}{q_{1}}+\frac{a_{2}}{q_{2}}-\frac{b}{r})=q_{3}}=1_{(a_{1}q_{2}r+a_{2}q_{1}r-bq_{1}q_{2},rq_{1},q_{2})=\frac{rq_{1}q_{2}}{q_{3}}}$
$\displaystyle\qquad=\sum_{\frac{rq_{1}q_{2}}{q_{3}}|d|rq_{1}q_{2}}\mu(\frac{d}{rq_{1}q_{2}/q_{3}})1_{a_{1}q_{2}r+a_{2}q_{1}r\equiv
bq_{1}q_{2}(\mbox{\scriptsize mod}\,d)}$
$\displaystyle\qquad=\sum_{\frac{r[q_{1},q_{2}]}{q_{3}}|P|r[q_{1},q_{2}]}\mu(\frac{P}{r[q_{1},q_{2}]/q_{3}})1_{a_{1}q_{2}r+a_{2}q_{1}r\equiv
bq_{1}q_{2}(\mbox{\scriptsize mod}\,P(q_{1},q_{2}))},$

where $P:=d/(q_{1},q_{2})$ (which is an integer). Multiplying this by
$e(\frac{m_{1}a_{1}}{q_{1}}+\frac{m_{2}a_{2}}{q_{2}})$ and applying Lemma 9.2
for each value of $P$ (of which there are at most $\tau([q_{1},q_{2}]r)$)
gives the result. ∎

######  Lemma 9.4.

Let $B\geqslant 0$ and $X\geqslant 1$ be parameters and let $r\geqslant 1$ be
an integer. Then

$\sum_{\begin{subarray}{c}\max(q_{1},q_{2},q_{3})\geqslant X\\\
\mu^{2}(q_{1})=\mu^{2}(q_{2})=\mu^{2}(q_{3})=1\\\ q_{1}|rq_{2}q_{3}\\\
q_{2}|rq_{1}q_{3}\\\
q_{3}|rq_{1}q_{2}\end{subarray}}\frac{\tau(q_{1})^{B}}{q_{1}}\frac{\tau(q_{2})^{B}}{q_{2}}\frac{\tau(q_{3})^{B}}{q_{3}}\ll_{B,\varepsilon}r^{\varepsilon}X^{\varepsilon-1}.$
(9.9)

###### Proof.

By symmetry it suffices to handle the sum over those $q_{1},q_{2},q_{3}$ for
which $q_{1}$ is biggest (and hence $q_{1}\geqslant X$). The condition
$q_{1}|rq_{2}q_{3}$ implies that $\frac{q_{1}}{(q_{1},rq_{2})}|q_{3}$, and so
in particular $q_{3}\geqslant\frac{q_{1}}{(q_{1},rq_{2})}$.

Given $q_{1},q_{2}$, since $q_{3}|rq_{1}q_{2}$ there are at most
$\tau(rq_{1}q_{2})\leqslant\tau(r)\tau(q_{1})\tau(q_{2})$ choices for $q_{3}$.
It also follows that, for each permissible $q_{3}$,
$\tau(q_{3})\leqslant\tau(r)\tau(q_{1})\tau(q_{2})$. It follows that the LHS
of (9.9) is bounded above by

$\displaystyle\tau(r)^{B+1}\sum_{\begin{subarray}{c}q_{1}\geqslant X\\\
q_{2}\leqslant q_{1}\\\ \mu^{2}(q_{1})=\mu^{2}(q_{2})=1\end{subarray}}$
$\displaystyle\frac{\tau(q_{1})^{2B+1}\tau(q_{2})^{2B+1}}{q_{1}q_{2}\frac{q_{1}}{(q_{1},rq_{2})}}$
$\displaystyle=\sum_{\begin{subarray}{c}q_{1}\geqslant X\\\
\mu^{2}(q_{1})=1\end{subarray}}\frac{\tau(q_{1})^{2B+1}}{q_{1}^{2}}\sum_{\begin{subarray}{c}q_{2}\leqslant
q_{1}\\\
\mu^{2}(q_{2})=1\end{subarray}}\frac{\tau(q_{2})^{2B+1}(q_{1},rq_{2})}{q_{2}}.$

By Lemma B.2 (noting that
$(q_{1},rq_{2})=(q_{1},r)(\frac{q_{1}}{(q_{1},r)},q_{2})$, and taking
$h=\frac{q_{1}}{(q_{1},r)}$ in that lemma), the inner sum is
$\ll(q_{1},r)\tau(q_{1})^{2B+2}\log^{O_{B}(1)}q_{1}$. Therefore the LHS of
(9.9) is bounded above by

$\tau(r)^{B+1}\sum_{\begin{subarray}{c}q_{1}\geqslant X\\\
\mu^{2}(q_{1})=1\end{subarray}}\frac{(q_{1},r)\tau(q_{1})^{4B+3}\log^{O_{B}(1)}q_{1}}{q_{1}^{2}}$

By Lemma B.3 (and a further application of the divisor bound
$\tau(r)\ll_{\varepsilon}r^{\varepsilon}$) this is indeed bounded above by
$\ll_{B,\varepsilon}r^{\varepsilon}X^{\varepsilon-1}$, which is what we wanted
to prove. ∎

###### Proof of Proposition 9.1.

From the definitions of $F$ and $F_{X_{1},X_{2},X_{3}}$ in the statement of
the proposition one may check that

$\displaystyle(F-F_{X_{1},X_{2},X_{3}})^{\wedge}$
$\displaystyle(\lambda)=\sum_{\max(\frac{q_{1}}{X_{1}},\frac{q_{2}}{X_{2}},\frac{q_{3}}{X_{3}})>1}\alpha(q_{1})\alpha(q_{2})\alpha(q_{3})\times$
$\displaystyle\times\\!\\!\\!\\!\\!\\!\sum_{\begin{subarray}{c}a_{i}\in(\mathbf{Z}/q_{i}\mathbf{Z})^{*}\\\
\frac{a_{1}}{q_{1}}+\frac{a_{2}}{q_{2}}+\frac{a_{3}}{q_{3}}\equiv\lambda(\mbox{\scriptsize
mod}\,1)\end{subarray}}e(\frac{h_{1}a_{1}}{q_{1}}+\frac{h_{2}a_{2}}{q_{2}}+\frac{h_{3}a_{3}}{q_{3}}).$
(9.10)

Using this, we will show first that

$|(F-F_{X_{1},X_{2},X_{3}})^{\wedge}(\lambda)|\ll_{B,\varepsilon}H^{3}\operatorname{denom}(\lambda)^{\varepsilon}X^{\varepsilon-1}.$
(9.11)

This statement is substantial progress towards Proposition 9.1. To handle the
case where $\operatorname{denom}(\lambda)$ is large, however, we need an
additional argument using (9.11) and Lemma 8.12.

We turn to the proof of (9.11). Suppose that $\lambda=\frac{b}{r}$ with $b,r$
coprime. If
$\frac{a_{1}}{q_{1}}+\frac{a_{2}}{q_{2}}+\frac{a_{3}}{q_{3}}\equiv\lambda(\operatorname{mod}\,1)$
then $q_{1}|rq_{2}q_{3}$, $q_{2}|rq_{1}q_{3}$ and $q_{3}|rq_{1}q_{2}$.
Therefore the RHS of (9.10) may be rewritten as $e(h_{3}b/r)$ times

$\sum_{\begin{subarray}{c}\max(\frac{q_{1}}{X_{1}},\frac{q_{2}}{X_{2}},\frac{q_{3}}{X_{3}})>1\\\
q_{1}|rq_{2}q_{3}\\\ q_{2}|rq_{1}q_{3}\\\
q_{3}|rq_{1}q_{2}\end{subarray}}\alpha(q_{1})\alpha(q_{2})\alpha(q_{3})\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\sum_{\begin{subarray}{c}a_{1}\in(\mathbf{Z}/q_{1}\mathbf{Z})^{*}\\\
a_{2}\in(\mathbf{Z}/q_{2}\mathbf{Z})^{*}\\\
\operatorname{denom}(\frac{a_{1}}{q_{1}}+\frac{a_{2}}{q_{2}}-\frac{b}{r})=q_{3}\end{subarray}}\\!\\!\\!\\!\\!\\!\\!\\!e(\frac{(h_{1}-h_{3})a_{1}}{q_{1}}+\frac{(h_{2}-h_{3})a_{2}}{q_{2}}).$

Note that the summation over $a_{3}$ has disappeared since $a_{3}$ is uniquely
determined by $a_{1},q_{1},a_{2},q_{2}$, and the condition
$\operatorname{denom}(\frac{a_{1}}{q_{1}}+\frac{a_{2}}{q_{2}}-\frac{b}{r})=q_{3}$
guarantees that this $a_{3}$ is coprime to $q_{3}$. Since $h_{1},h_{2},h_{3}$
are distinct, the inner sum is exactly of the type considered in Corollary
9.3, and by that result it is bounded by $O(H^{3}\tau(r[q_{1},q_{2}])^{3})$.
It follows that

$|(F-F_{X_{1},X_{2},X_{3}})^{\wedge}(\lambda)|\ll
H^{3}\tau(r)^{3}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\sum_{\begin{subarray}{c}\max(\frac{q_{1}}{X_{1}},\frac{q_{2}}{X_{2}},\frac{q_{3}}{X_{3}})>1\\\
q_{1}|rq_{2}q_{3}\\\ q_{2}|rq_{1}q_{3}\\\
q_{3}|rq_{1}q_{2}\end{subarray}}\\!\\!\\!|\alpha(q_{1})\alpha(q_{2})\alpha(q_{3})|\tau([q_{1},q_{2}])^{3}.$

By assumption, $|\alpha(q)|\leqslant\tau(q)^{B}/q$ for all $q$, and $\alpha$
is supported on squarefrees, and so this is bounded above by

$O(H^{3}\tau(r)^{3})\sum_{\begin{subarray}{c}\max(q_{1},q_{2},q_{3})\geqslant
X\\\ \\\ \mu^{2}(q_{1})=\mu^{2}(q_{2})=\mu^{2}(q_{3})=1\\\
q_{1}|rq_{2}q_{3}\\\ q_{2}|rq_{1}q_{3}\\\
q_{3}|rq_{1}q_{2}\end{subarray}}\frac{\tau(q_{1})^{B+3}}{q_{1}}\frac{\tau(q_{2})^{B+3}}{q_{2}}\frac{\tau(q_{3})^{B+3}}{q_{3}}.$

Applying Lemma 9.4 and the divisor bound gives the claimed bound (9.11).

Now we supply the further arguments necessary to handle the case where
$\operatorname{denom}(\lambda)$ is large. Fix some $\lambda$ and write
$r:=\operatorname{denom}(\lambda)$. Then (9.11) gives

$|(F-F_{r,r,r})^{\wedge}(\lambda)|\ll_{B,\varepsilon}H^{3}r^{\varepsilon-1}.$
(9.12)

Now $F_{r,r,r}$ is the product of three functions in the class
$\mathscr{C}_{B}(r)$, as defined in Definition 8.10. By (two applications of)
Lemma 8.12, $F_{r,r,r}\in(\log^{O_{B}(1)}r)\mathscr{C}_{5B+6}(r^{3})$, which
means that

$|F_{r,r,r}^{\wedge}(\lambda)|\ll_{B,\varepsilon}r^{\varepsilon-1}.$

Together with (9.12), this implies that

$|F^{\wedge}(\lambda)|\ll_{B,\varepsilon}H^{3}r^{\varepsilon-1}.$

The same bound also applies to $F_{X_{1},X_{2},X_{3}}^{\wedge}(\lambda)$,
simply by replacing the $\alpha_{i}$ in the definition of $F$ by
$\alpha^{\prime}_{i}(n):=\alpha_{i}(n)1_{n\leqslant X_{i}}$. By the triangle
inequality (and recalling that $r=\operatorname{denom}(\lambda)$) it follows
that

$|(F-F_{X_{1},X_{2},X_{3}})^{\wedge}(\lambda)|\ll_{B,\varepsilon}H^{3}\operatorname{denom}(\lambda)^{\varepsilon-1}.$
(9.13)

We now have the desired bound
$|(F-F_{X_{1},X_{2},X_{3}})^{\wedge}(\lambda)|\ll_{B,\varepsilon}H^{3}X^{\varepsilon-1}$
in all cases: if $\operatorname{denom}(\lambda)\leqslant X$, apply (9.11),
whilst if $\operatorname{denom}(\lambda)>X$, apply (9.13).

This completes the proof of Proposition 9.1.∎

###  10\. Triple correlations with characters

In this section we build upon the previous section by introducing characters.
The main result of the section (and the only one we will need elsewhere) is
the following.

######  Proposition 10.1.

Let $Q,R$ be parameters and suppose that $1\leqslant Q\leqslant
Q_{1},Q_{2},Q_{3}\leqslant R$. Let $\chi$ be a primitive Dirichlet character
of conductor $q\leqslant R$. Then we have

$\|F^{+}_{\chi,Q_{1}}\Lambda_{Q_{2}}^{-}H_{Q_{3}}-\tilde{F}^{+}_{\chi,R}\tilde{\Lambda}^{-}_{R}\tilde{H}_{R}\|^{\wedge}_{\infty}\ll
R^{o(1)}Q^{-\frac{1}{4}}.$

The reader may want to take the opportunity to recall the definitions of the
various objects appearing here, which may be located as follows:

  * •

$F_{\chi,Q}$ is a key object of the paper whose definition is given in
Definition 4.3. It has an alternative expression given in (6.6);

  * •

$\tilde{F}_{\chi,R}$ is a “completed” version of $F$, defined in Definition
6.1 and with an alternative expression in (6.5);

  * •

$\Lambda_{Q}$ is a classical approximant to the van Mangoldt function, defined
in (3.3);

  * •

$\tilde{\Lambda}_{R}$ is the completed version of this, defined in (6.10) and
with an alternative expression in (8.21), which exhibits it as a normalised
characteristic function of the $R$-almost primes;

  * •

$H_{Q}$ is another key object in the paper, defined in Definition 8.9, and to
be thought of as a kind of proxy for the square of the divisor function;

  * •

$\tilde{H}_{R}$ is a completed version of this, defined in Definition 8.8.

Finally, recall that $f^{+}(n):=f(n+1)$ and $f^{-}(n):=f(n-1)$, and that the
basic properties of periodic functions and their Fourier series (and in
particular the notation $\|\cdot\|_{\infty}^{\wedge}$) are laid out in Section
8.

For the rest of the section we regard $\chi$ and its conductor $q$ as fixed,
with $q\leqslant R$. Write (see Appendix C) $\chi=\prod_{p|q}\chi_{p}$, where
$\chi_{p}$ is a Dirichlet character of conductor $p^{\beta_{p}}$, where
$q=\prod_{p|q}p^{\beta_{p}}$.

We divide the proof of Proposition 10.1 into two parts, according to whether
or not $q\geqslant Q^{\frac{1}{2}}$.

####  10.1. The case of large conductor

In this section we give some estimates which imply Proposition 10.1 when
$q\geqslant Q^{\frac{1}{2}}$. Recall the definition (8.13) of
$\Lambda_{\mathbf{Z}/p\mathbf{Z}}$. It is also convenient to introduce the
local factors $\chi_{\mathbf{Z}/p\mathbf{Z}}$ defined by
$\chi_{\mathbf{Z}/p\mathbf{Z}}=\frac{p}{p-1}\chi_{p}$ if $p|q$, and
$\chi_{\mathbf{Z}/p\mathbf{Z}}=\Lambda_{\mathbf{Z}/p\mathbf{Z}}$ if $p\nmid
q$. Then (6.5), (6.10) can be written in the form

$\tilde{F}_{\chi,R}=\prod_{p\leqslant
R}\overline{\chi}_{\mathbf{Z}/p\mathbf{Z}},\qquad\tilde{\Lambda}_{R}=\prod_{p\leqslant
R}\Lambda_{\mathbf{Z}/p\mathbf{Z}}.$ (10.1)

Our first estimate deals with the completed terms in Proposition 10.1.

######  Lemma 10.2.

We have
$\|\tilde{F}^{+}_{\chi,R}\tilde{\Lambda}_{R}^{-}\tilde{H}_{R}\|^{\wedge}_{\infty}\ll\tau(q)^{16}q^{-\frac{1}{2}}$.

###### Proof.

By (10.1) and (8.9), we have

$\|\tilde{F}^{+}_{\chi,R}\tilde{\Lambda}_{R}^{-}\tilde{H}_{R}\|^{\wedge}_{\infty}\leqslant\prod_{p\leqslant
R}\|f_{p}\|^{\wedge}_{\infty}.$ (10.2)

where
$f_{p}:=\overline{\chi}_{\mathbf{Z}/p\mathbf{Z}}^{+}\Lambda_{\mathbf{Z}/p\mathbf{Z}}^{-}\tau^{2}_{\mathbf{Z}/p\mathbf{Z}}$.
When $p\nmid q$ we have
$\chi_{\mathbf{Z}/p\mathbf{Z}}=\Lambda_{\mathbf{Z}/p\mathbf{Z}}$, and so for
these $p$ we have $\|f_{p}\|^{\wedge}_{\infty}\leqslant 1+O(p^{-2})$ by
(8.19). The product over $p$ of all these contributions is $O(1)$.

When $p|q$,
$f_{p}=\frac{p}{p-1}\overline{\chi}_{p}^{+}\Lambda_{\mathbf{Z}/p\mathbf{Z}}^{-}\tau^{2}_{\mathbf{Z}/p\mathbf{Z}}$,
and so by (8.8) we have

$\|f_{p}\|^{\wedge}_{\infty}\leqslant\frac{p}{p-1}\|\chi_{p}\|^{\wedge}_{\infty}\|\Lambda_{\mathbf{Z}/p\mathbf{Z}}^{-}\tau^{2}_{\mathbf{Z}/p\mathbf{Z}}\|^{\wedge}_{1}.$
(10.3)

By Lemma 8.4 we have

$\|\chi_{p}\|^{\wedge}_{\infty}\leqslant p^{-\beta_{p}/2}.$ (10.4)

By (8.7) and (8.17), (8.18) we have
$\|\Lambda_{\mathbf{Z}/p\mathbf{Z}}^{-}\tau^{2}_{\mathbf{Z}/p\mathbf{Z}}\|^{\wedge}_{1}\leqslant
8$. Substituting this and (10.4) into (10.3), and using the crude bound
$\frac{p}{p-1}\leqslant 2$, we obtain $\|f_{p}\|^{\wedge}_{\infty}\leqslant
16p^{-\beta_{p}/2}$.

Taking products over $p$, we see that the right-hand side of (10.2) is bounded
by $\ll 16^{\omega(q)}q^{-1/2}$, where $\omega(q)$ denotes the number of
distinct prime factors of $q$, which implies the claimed bound.∎

The second result of this section, which is a little harder, deals with the
uncompleted terms in Proposition 10.1.

######  Lemma 10.3.

Suppose that $1\leqslant Q_{1},Q_{2},Q_{3}\leqslant R$. Then

$\|F^{+}_{\chi,Q_{1}}\Lambda_{Q_{2}}^{-}H_{Q_{3}}\|^{\wedge}_{\infty}\ll\tau(q)^{O(1)}(\log^{O(1)}R)q^{-\frac{1}{2}}.$
(10.5)

###### Proof.

Introduce

$f_{Q}(n)=\sum_{\begin{subarray}{c}r\leqslant Q\\\
(r,q)=1\end{subarray}}\frac{\mu(r)}{\phi(r)}c_{r}(n).$ (10.6)

(Of course, this definition depends on $q$, but we are regarding $q$ as fixed
throughout the section and so suppress the dependence to keep the notation
manageable.) By (6.6) we have

$F_{\chi,Q}=\frac{q}{\phi(q)}\overline{\chi}f_{Q}.$ (10.7)

Consider the definition of $\Lambda_{Q}$, viz

$\Lambda_{Q}(n)=\sum_{r\leqslant Q}\frac{\mu(r)}{\phi(r)}c_{r}(n).$ (10.8)

Since the sum is supported where $r$ is squarefree, each $r$ in the sum may be
written uniquely as $r=dr^{\prime}$ where $d|q$ and $(r^{\prime},q)=1$. By the
multiplicative property $c_{r}(n)=c_{d}(n)c_{r^{\prime}}(n)$ the contribution
from a particular value of $d$ (to the sum over $r$ in (10.8))) is then

$\frac{\mu(d)}{\phi(d)}c_{d}(n)\sum_{\begin{subarray}{c}r^{\prime}\leqslant
Q/d\\\
(r^{\prime},q)=1\end{subarray}}\frac{\mu(r^{\prime})}{\phi(r^{\prime})}c_{r^{\prime}}(n).$

It follows that

$\Lambda_{Q}=\sum_{d|q}\frac{\mu(d)}{\phi(d)}c_{d}f_{Q/d}.$ (10.9)

(Note, here and in what follows, $c_{d}$ is the Ramanujan sum considered as a
function.)

Now we expand $F_{\chi,Q_{1}}^{+}\Lambda_{Q_{2}}^{-}$ using (10.7) and (10.9),
obtaining

$F^{+}_{\chi,Q_{1}}\Lambda^{-}_{Q_{2}}=\frac{q}{\phi(q)}\sum_{d|q}\frac{\mu(d)}{\phi(d)}\overline{\chi}^{+}c_{d}^{-}f_{Q_{1}}^{+}f_{Q_{2}/d}^{-}.$
(10.10)

Recall from Definition 8.9 that $H_{Q_{3}}=\sum_{r\leqslant
Q_{3}}\eta(r)c_{r}$ where $\eta(r)=\prod_{p|r}\frac{3}{p+3}$ and $r$ is
restricted to squarefrees. Summing according to $e:=(r,q)$, we see that
$H_{Q}=\sum_{e|q}\eta(e)c_{e}h_{Q_{3}/e}$, where

$h_{Y}:=\sum_{\begin{subarray}{c}r^{\prime}\leqslant Y\\\
(r^{\prime},q)=1\end{subarray}}\eta(r^{\prime})c_{r^{\prime}}.$ (10.11)

Thus from (10.10) we obtain

$F^{+}_{\chi,Q_{1}}\Lambda^{-}_{Q_{2}}H_{Q_{3}}=\frac{q}{\phi(q)}\sum_{d,e|q}\frac{\mu(d)}{\phi(d)}\eta(e)\overline{\chi}^{+}c_{d}^{-}c_{e}f_{Q_{1}}^{+}f_{Q_{2}/d}^{-}h_{Q_{3}/e}.$
(10.12)

Consider first the term $f^{+}_{Q_{1}}f^{-}_{Q_{2}/d}h_{Q_{3}/e}$. The three
functions $f_{Q_{1}}$, $f_{Q_{2}/d}$ and $h_{Q_{3}/e}$ all lie in the class
$\mathscr{C}_{2}(R)$, as defined in Definition 8.10, by a trivial modification
of the proof of Lemma 8.11. Since this class is invariant under shifts, it
follows by two applications of Lemma 8.12 that