###### Abstract

Hooley proved that if $f\in\mathbb{Z}[X]$ is irreducible of degree $\geq 2$,
then the fractions $\\{r/n\\}$, $0<r<n$ with $f(r)\equiv 0{\text{\rm\
(mod~{}$n$)}}$, are uniformly distributed in $]0,1[$. In this paper we study
such problems for reducible polynomials of degree $2$ and $3$ and for finite
products of linear factors. In particular, we establish asymptotic formulas
for exponential sums over these normalized roots.

title = Exponential sums with reducible polynomials, author = Cécile Dartyge
and Greg Martin, plaintextauthor = Cecile Dartyge and Greg Martin, keywords =
exponential sums, equidistribution of polynomial roots, year=2019, number=15,
received=11 July 2018, revised=19 April 2019, published=13 November 2019,
doi=10.19086/da.10793,

[classification=text]

##  1 Introduction

Let $f(X)$ be a polynomial of degree at least $2$ with integer coefficients,
and let $h$ be a nonzero integer. We consider for $x\geq 1$ the exponential
sums

$S(f,x,h)=\sum_{n\leq x}\sum_{\begin{subarray}{c}{r{\text{\rm\
(mod~{}$n$)}}}\\\ {f(r)\equiv 0{\text{\rm\
(mod~{}$n$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{hr}{n}\Big{)}$ (1)

with the standard notation $\mathrm{e}(t)=\exp(2i\pi t)$; our interest is in
fixed $f$ and $h$ while $x$ tends to infinity. In the case $h=1$ we will write
simply $S(f,x)$. Hooley [11, Theorem 1] proved that if $f$ is irreducible,
then $S(f,x,h)=o(x)$ when $x\rightarrow\infty$. By Weyl’s criterion, this
implies that the fractions $r/n$, where $0<r<n$ and $f(r)\equiv 0{\text{\rm\
(mod~{}$n$)}}$, are uniformly distributed in $]0,1[$. The condition that $\deg
f\geq 2$ is necessary in this result, as the roots of a linear polynomial are
not equidistributed in $]0,1[$. For example, if $f(n)=n+b$, the exponential
term in equation (1) is $\mathrm{e}(-hb/n)=1+O(1/n)$ for fixed $h$ and $b$,
and then $S(f,x,h)=x+O(\log x)$. In general, when $f(n)=an+b$ one can
similarly obtain a formula of the form $S(f,x,h)=xC(f,h)+o(x)$ for some
constant $C(f,h)$.

When $f(n)=n^{2}-D$ with $D$ not a square, Hooley [10] obtained (using a
different method) the more precise bound $S(f,x,h)\ll_{f,h}x^{3/4}\log x$. The
exponent $3/4$ in this result was improved to $2/3$ via the theory of
automorphic forms by Hejhal [8], Bykovski [2], and Zavorotny [21]. A variant
of this problem is the distribution of the fractions $r/p$, where $0<r<p$ and
$f(r)\equiv 0{\text{\rm\ (mod~{}$p$)}}$, for primes $p$. Duke, Friedlander,
and Iwaniec [5] proved that for $f(X)=aX^{2}+2bX+c$ with $ac-b^{2}>0$, we have

$\sum_{p\leq x}\sum_{\begin{subarray}{c}{0\leq r<p}\\\ {f(r)\equiv
0{\text{\rm\
(mod~{}$p$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{hr}{p}\Big{)}=o(\pi(x)).$

In all of the above results, the polynomial $f$ is assumed to be irreducible;
what can we say about the sums $S(f,x,h)$ when $f$ is reducible? In this paper
we examine reducible polynomials of degree $2$ and $3$ (in which case $f$ has
at least one linear factor) and on polynomials that factor completely into
linear factors. The hope is to obtain, not just an upper bound, but an actual
asymptotic formula for $S(f,x,h)$, analogously to the situation described
above where $f$ is itself linear.

For example, Sitar and the second author [15] obtained a general bound for
reducible quadratic polynomials $f$ with discriminant $D$:

$S(f,x,h)\ll\sqrt{D}\prod_{p\mid h}\Big{(}1+\frac{7}{\sqrt{p}}\Big{)}x(\log
x)^{\sqrt{2}-1}(\log\log x)^{5/2}.$ (2)

Since the number of summands of $S(f,x,h)$ has order $x\log x$ in this case, a
consequence is that the the fractions $r/n$, where $0<r<n$ and $f(r)\equiv
0{\text{\rm\ (mod~{}$n$)}}$, are uniformly distributed in $]0,1[$ for
reducible quadratic polynomials. However, this bound is still large enough to
disguise a potential asymptotic main term of size $x$ caused by the roots of
the linear factors of $f$.

In our first theorem, which is proved in Section 3, we provide such an
asymptotic formula for exponential sums with reducible quadratics:

######  Theorem 1.

Let $a,b,c,d$ be fixed integers with $ac\not=0$, $(a,b)=(c,d)=1$, and $ad\neq
bc$, and set $f(n)=(an+b)(cn+d)$. Then for any nonzero integer $h$, there
exists $C(f,h)\in\mathbb{C}$ such that for any $\varepsilon>0$, we have

$S(f,x,h)=xC(f,h)+O(x^{4/5+\varepsilon}),$ (3)

where the implicit constant depends on $f$, $h$, and $\varepsilon$. When
$(h,ad-bc)=1$, the error term in equation (3) can be improved to
$O(x^{3/4+\varepsilon})$.

The proof of this theorem provides an explicit but complicated formula for
$C(f,h)$ (see equation (13) below). In the particular case $h=1$, we obtain
$S(f,x)=xC(f,1)+O(x^{4/5+\varepsilon})$ with

$C(f,1)=\Big{(}\frac{\mu(a)}{a}+\frac{\mu(c)}{c}\Big{)}\frac{6}{\pi^{2}}\prod_{p\mid
ac}\Big{(}1-\frac{1}{p^{2}}\Big{)}^{-1}.$

(Note in particular that it is possible for $C(f,1)$ to equal $0$, namely if
neither $a$ nor $c$ is squarefree; in such a case, Theorem 1 is technically an
upper bound rather than an asymptotic formula. The analogous pedantic comment
applies to Theorem 4 below.)

Our second result handles the case $f(n)=n(n^{2}+1)$. In Section 4 we will
prove:

######  Theorem 2.

For $f(n)=n(n^{2}+1)$, we have

$S(f,x)=\frac{3x}{4}\prod_{p\equiv 1{\text{\rm\
(mod~{}$4$)}}}\Big{(}1-\frac{2}{p^{2}}\Big{)}+O\Big{(}\frac{x(\log\log
x)^{7/2}}{(\log x)^{1-1/\sqrt{2}}}\Big{)}.$

It is also possible to generalize Theorem 2 to $S(f,x,h)$ for a general
nonzero integer $h$, as in the work of Hooley, though we do not do so here. It
is likely possible to extend Theorem 2 to general products of two polynomials
$f_{1}f_{2}$ with $f_{1}$ linear and $f_{2}$ irreducible quadratic by adapting
some ideas of [18] or [1]. However, such a generalization with a general
$f_{2}$ in place of $n^{2}+1$ is not straightforward; the case where $f_{2}$
has positive discriminant seems more difficult.

The next result, which we prove in Sections 5 and 6.1, handles in detail a
special product of three linear polynomials:

######  Theorem 3.

For $f(n)=n(n+1)(2n+1)$, we have

$S(f,x)=x\prod_{p\geq
3}\Big{(}1-\frac{2}{p^{2}}\Big{)}+O\Big{(}\frac{x(\log\log x)^{6}}{(\log
x)^{2}}\Big{)}.$

It was clear that this result could be generalized to arbitrary products of
three linear polynomials. However, after reading an earlier version of this
manuscript, the anonymous referee pointed out that the method can be extended
to give an asymptotic formula for $S(f,x,h)$ when $f$ is the product of four
linear polynomials, as well as a nontrivial upper bound for $S(f,x,h)$ when
$f$ is a product of any number of linear polynomials. We prove the following
result in Sections 6.2 and 7:

######  Theorem 4.

Let $h$ be a nonzero integer, let $k\geq 3$ be an integer, and let
$f(n)=\prod_{i=1}^{k}(a_{i}n+b_{i})$ where the coefficients
$a_{1},b_{1},\ldots,a_{k},b_{k}$ are integers satisfying $(a_{j},b_{j})=1$ for
all $1\leq i\leq k$ and $a_{i}b_{j}\neq a_{j}b_{i}$ for all $1\leq i<j\leq k$.

  1. (i)

If $k=3$ or $k=4$, then there exists $C(f,h)\in\mathbb{C}$ such that

$S(f,x,h)=C(f,h)x+O\big{(}x(\log x)^{k-5}(\log\log x)^{6}\big{)}.$

  2. (ii)

If $k\geq 5$, then $S(f,x,h)\ll x(\log x)^{k-5}(\log\log x)^{6}$.

In both cases, the implicit constants depend on $f$ and $h$.

As the number of fractions $r/n$, where $0<r<n$ and $f(r)\equiv 0{\text{\rm\
(mod~{}$n$)}}$, for all $n\leq x$ has order of magnitude $x(\log
x)^{\kappa-1}$, where $\kappa$ is the number of distinct irreducible factors
of $f$, these theorems all imply that the appropriate sequences of fractions
are uniformly distributed in $]0,1[$.

It is also worth remarking that it is only for convenience that we hypothesize
that the linear factors in Theorems 1 and 4 are not proportional to one
another. Indeed, more generally consider a polynomial $f=g^{2}h$: the roots of
$f$ modulo squarefree integers $n$ are unaffected by the repeated factor
$g^{2}$, while if $p^{2}\mid n$ then the roots of $g^{2}{\text{\rm\
(mod~{}$n$)}}$ form arithmetic progressions with common difference $n/p$, and
thus their contribution to the exponential sum $S(f,x,h)$ vanishes completely.

Before proceeding to the proofs of our theorems, we establish in the next
section a lemma that is used repeatedly throughout the paper. We adopt the
following notation and conventions throughout this paper: when $a$ and $b$ are
relatively prime integers, $\bar{a}_{b}$ will denote an integer such that
$\bar{a}_{b}a\equiv 1{\text{\rm\ (mod~{}$b$)}}$. Furthermore, when the context
will be clear, we will also use the simplified notation $\bar{a}$ for this
multiplicative inverse of $a$ to the implied modulus $b$, which is often the
denominator of the fraction in whose numerator $\bar{a}$ appears. The letter
$p$ usually denotes a prime number. We adopt the convention throughout that
$\mathrm{e}(t)=\exp(2i\pi t)$ unless $t$ contains an expression of the form
$\frac{\bar{a}}{b}$ where $(a,b)>1$, in which case $\mathrm{e}(t)=0$. For
example, the expression $\sum_{0\leq n\leq
p-1}\mathrm{e}(\frac{\bar{n}\overline{(n-1)}}{p})$ is to be interpreted as
$0+0+\sum_{2\leq n\leq
p-1}\mathrm{e}(\frac{\bar{n}_{p}\overline{(n-1)}_{p}}{p})$.

##  2 Exponential sums involving multiplicative inverses

We begin by establishing the following lemma on exponential sums (a slight
variation of a result of Hooley [12, Lemma 3]), which is the crucial tool of
our paper.

######  Lemma 1.

For any $y<z$, $q\geq 2$, $t\in\mathbb{Z}$ and $(m,q)=1$ we have

$\sum_{\begin{subarray}{c}{y<n\leq z}\\\ {(n,q)=1}\\\ {n\equiv u{\text{\rm\
(mod~{}$m$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{t\bar{n}_{q}}{q}\Big{)}=\frac{z-y}{mq}\mu\Big{(}\frac{q}{(q,t)}\Big{)}\frac{\varphi(q)}{\varphi(q/(t,q))}+O\big{(}\sqrt{q(t,q)}\cdot\tau(q)\log
q\big{)}.$

In particular,

$\sum_{\begin{subarray}{c}{y<n\leq z}\\\
{(n,q)=1}\end{subarray}}\mathrm{e}\Big{(}\frac{t\bar{n}_{q}}{q}\Big{)}=\frac{z-y}{q}\mu\Big{(}\frac{q}{(q,t)}\Big{)}\frac{\varphi(q)}{\varphi(q/(t,q))}+O\big{(}\sqrt{q(t,q)}\cdot\tau(q)\log
q\big{)}.$ (4)

(While we have written the statement of the lemma, for ease of reference, with
explicit subscripts on the multiplicative inverses $\bar{n}_{q}$ and explicit
coprimality conditions of summation, we immediately revert to our conventions
of suppressing these notational signals.)

###### Proof.

We begin by collecting the summands according to the value of $n{\text{\rm\
(mod~{}$q$)}}$, which we then detect using a further additive character:

$\displaystyle\sum_{\begin{subarray}{c}{y<n\leq z}\\\ {n\equiv u{\text{\rm\
(mod~{}$m$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{t\bar{n}}{q}\Big{)}$
$\displaystyle=\sum_{a{\text{\rm\
(mod~{}$q$)}}}\mathrm{e}\Big{(}\frac{t\bar{a}}{q}\Big{)}\sum_{\begin{subarray}{c}{y<n\leq
z}\\\ n\equiv a{\text{\rm\ (mod~{}$q$)}}\\\ {n\equiv u{\text{\rm\
(mod~{}$m$)}}}\end{subarray}}1$ $\displaystyle=\sum_{a{\text{\rm\
(mod~{}$q$)}}}\mathrm{e}\Big{(}\frac{t\bar{a}}{q}\Big{)}\sum_{\begin{subarray}{c}{y<n\leq
z}\\\ {n\equiv u{\text{\rm\
(mod~{}$m$)}}}\end{subarray}}\frac{1}{q}\sum_{h=0}^{q-1}\mathrm{e}\Big{(}\frac{h(n-a)}{q}\Big{)}$
$\displaystyle=\frac{1}{q}\sum_{h=0}^{q-1}\bigg{(}\sum_{a{\text{\rm\
(mod~{}$q$)}}}\mathrm{e}\Big{(}\frac{t\bar{a}-ha}{q}\Big{)}\bigg{)}\bigg{(}\sum_{\begin{subarray}{c}{y<n\leq
z}\\\ {n\equiv u{\text{\rm\
(mod~{}$m$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{hn}{q}\Big{)}\bigg{)},$
(5)

with the convention $\mathrm{e}(t\bar{a}/q)=0$ if $(a,q)>1$ as mentioned in
the end of the introduction. The $h=0$ summand contributes the main term:

$\displaystyle\frac{1}{q}\bigg{(}\sum_{a{\text{\rm\
(mod~{}$q$)}}}\mathrm{e}\Big{(}\frac{t\bar{a}}{q}\Big{)}\bigg{)}\bigg{(}\sum_{\begin{subarray}{c}{y<n\leq
z}\\\ {n\equiv u{\text{\rm\ (mod~{}$m$)}}}\end{subarray}}1\bigg{)}$
$\displaystyle=\frac{1}{q}\bigg{(}\mu\Big{(}\frac{q}{(q,t)}\Big{)}\frac{\varphi(q)}{\varphi(q/(t,q))}\bigg{)}\bigg{(}\frac{z-y}{m}+O(1)\bigg{)}$
$\displaystyle=\frac{z-y}{qm}\mu\Big{(}\frac{q}{(q,t)}\Big{)}\frac{\varphi(q)}{\varphi(q/(t,q))}+O(1),$

since the first sum on the left-hand side is a complete Ramanujan sum which
has been evaluated classically (see [16, equation (4.7)]). As for the summands
where $h\neq 0$, the first inner sum on the right-hand side of equation (5) is
a complete Kloosterman sum, which was shown by Hooley [9, Lemma 2] (using
Weil’s bounds for exponential sums) to be $\ll\sqrt{q(t,q)}\cdot\tau(q)$;
therefore

$\displaystyle\frac{1}{q}\sum_{h=1}^{q-1}\bigg{(}\sum_{a{\text{\rm\
(mod~{}$q$)}}}$
$\displaystyle\mathrm{e}\Big{(}\frac{t\bar{a}-ha}{q}\Big{)}\bigg{)}\bigg{(}\sum_{\begin{subarray}{c}{y<n\leq
z}\\\ {n\equiv u{\text{\rm\
(mod~{}$m$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{hn}{q}\Big{)}\bigg{)}$
$\displaystyle\ll\sqrt{q(t,q)}\cdot\tau(q)\cdot\frac{1}{q}\sum_{h=1}^{q-1}\bigg{|}\sum_{\begin{subarray}{c}{y<n\leq
z}\\\ {n\equiv u{\text{\rm\
(mod~{}$m$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{hn}{q}\Big{)}\bigg{|}$
$\displaystyle=\sqrt{q(t,q)}\cdot\tau(q)\cdot\frac{1}{q}\sum_{h=1}^{q-1}\bigg{|}\sum_{(y-u)/m<\lambda\leq(z-u)/m}\mathrm{e}\Big{(}\frac{h(m\lambda+u)}{q}\Big{)}\bigg{|}$
$\displaystyle=\sqrt{q(t,q)}\cdot\tau(q)\cdot\frac{1}{q}\sum_{\eta=1}^{q-1}\bigg{|}\mathrm{e}\Big{(}\frac{\eta\bar{m}u}{q}\Big{)}\sum_{(y-u)/m<\lambda\leq(z-u)/m}\mathrm{e}\Big{(}\frac{\eta\lambda}{q}\Big{)}\bigg{|},$

since $(m,q)=1$ and thus the change of variables $\eta=hm$ permutes the
nonzero residue classes modulo $q$. This last sum is a geometric series and is
consequently $\ll\|\eta/q\|^{-1}$, where $\|u\|$ is the distance from $u$ to
the nearest integer. Therefore we have the following bound for these summands:

$\ll\sqrt{q(t,q)}\cdot\tau(q)\cdot\frac{2}{q}\sum_{\eta=1}^{q/2}\frac{q}{\eta}\ll\sqrt{q(t,q)}\cdot\tau(q)\log
q,$

as required. ∎

##  3 Reducible quadratics (Theorem 1)

Throughout this section, we consider $f(n)=(an+b)(cn+d)$ with $a,b,c,d$ as in
Theorem 1. All implicit constants in this section may depend on $f$, $h$, and
(where appropriate) $\varepsilon$.

Define $\Delta=ad-bc$. The simultaneous congruences $an+b\equiv cn+d\equiv
0{\text{\rm\ (mod~{}$p$)}}$ have a solution only when
$-b\bar{a}\equiv-d\bar{c}{\text{\rm\ (mod~{}$p$)}}$, or equivalently when
$p\mid\Delta$. We start with the case $(h,ac\Delta)=1$; in the following
section we indicate how to deal with the general case.

###  3.1 The case $(ac\Delta,h)=1$

We begin by handling some coprimality problem between the denominators $n$ and
$\Delta$.

######  Lemma 2.

We may write

$S(f,x,h)=\sum_{\begin{subarray}{c}{g\mid\Delta}\\\
{(g,ac)=1}\end{subarray}}\mu^{2}(g)\sum_{\begin{subarray}{c}{m\leq x/g}\\\
{(m,\Delta)=1}\end{subarray}}\sum_{\begin{subarray}{c}{r{\text{\rm\
(mod~{}$mg$)}}}\\\ {(ar+b)(cr+d)\equiv 0{\text{\rm\
(mod~{}$mg$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{hr}{mg}\Big{)}.$

###### Proof.

First we sort by $g=(n,\Delta)$:

$S(f,x,h)=\sum_{g\mid\Delta}\sum_{\begin{subarray}{c}{m\leq x/g}\\\
{(m,\Delta/g)=1}\end{subarray}}\sum_{\begin{subarray}{c}{r{\text{\rm\
(mod~{}$mg$)}}}\\\ {(ar+b)(cr+d)\equiv 0{\text{\rm\
(mod~{}$mg$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{hr}{mg}\Big{)}.$

If $p\mid g\mid\Delta$ and $p\mid a$ then $p\mid c$ as well, in which case
$(ax+b)(cx+d)\equiv bd\not\equiv 0{\text{\rm\ (mod~{}$p$)}}$ and there are no
roots modulo $p$. Similarly, if $p\mid(g,c)$, then $f$ has no root modulo $p$.
Thus we can add the condition of summation $(g,ac)=1$.

We can also assume that $p^{2}\nmid mg$ for every $p\mid\Delta$. Indeed, if
$mg=qp^{2}$ for such a prime $p$, and if $r$ is a root of $(ax+b)(cx+d)$
modulo $qp^{2}$, then both $ar+b\equiv 0{\text{\rm\ (mod~{}$p$)}}$ and
$cr+d\equiv 0{\text{\rm\ (mod~{}$p$)}}$ since $p\mid\Delta$; and then all of
$r+qp$, $r+2qp$, …, $r+(p-1)qp$ are roots of $(ax+b)(cx+d)$ modulo $qp^{2}$,
since

$\begin{split}f(r+\lambda qp)&\equiv(ar+b)(cr+d)+\lambda
qp(a(cr+d)+b(ar+b))\equiv 0{\text{\rm\ (mod~{}$qp^{2}$)}}.\end{split}$

The exponential sum over these roots $r$, $r+qp$, …, $r+(p-1)qp$ vanishes
(here we use the assumption $(h,\Delta)=1$, so that $p\nmid h$), which
justifies omitting these terms.

In particular, we may assume that $g$ is squarefree (whence the introduction
of the factor $\mu^{2}(g)$) and that $(m,g)=1$ (which combines with the
existing condition $(m,\Delta/g)=1$ to yield simply $(m,\Delta)=1$),
completing the proof. ∎

Next we separate the congruence conditions between the two factors of $f$.

######  Lemma 3.

Suppose that $g\mid\Delta$ is squarefree, $(g,c)=1$, and $(m,\Delta)=1$. The
roots of $(ar+b)(cr+d)\equiv 0{\text{\rm\ (mod~{}$mg$)}}$ are in one-to-one
correspondence with the factorizations $k\ell=m$ with $(k,\ell)=1$, $(k,a)=1$,
and $(\ell,c)=1$. The root $r$ corresponds to the solution of the system of
congruences

$\begin{split}ar+b&\equiv 0{\text{\rm\ (mod~{}$k$)}}\\\ cr+d&\equiv
0{\text{\rm\ (mod~{}$\ell$)}}\\\ r&\equiv r_{g}{\text{\rm\ (mod~{}$g$)}},\\\
\end{split}$

where $r_{g}$ is the residue class $r_{g}\equiv-d\bar{c}{\text{\rm\
(mod~{}$g$)}}$.

###### Proof.

It is straightforward to check that the factorization corresponding to a root
$r$ of $(ar+b)(cr+d)\equiv 0{\text{\rm\ (mod~{}$mg$)}}$ is $k=(ar+b,m)$ and
$\ell=(cr+d,m)$, and that this correspondence is the inverse function to the
correspondence described in the statement of the lemma. ∎

By the Chinese remainder theorem, the solution of the system of congruences
given in Lemma 3 can be written as

$r=-b\bar{a}_{k}\ell\bar{\ell}_{k}g\bar{g}_{k}-d\bar{c}_{\ell}k\bar{k}_{\ell}g\bar{g}_{\ell}+r_{g}k\bar{k}_{g}\ell\bar{\ell}_{g}.$

We thus obtain

$\begin{split}S(f,x,h)&=\\!\\!\\!\sum_{\begin{subarray}{c}{g\mid\Delta}\\\
{(g,ac)=1}\end{subarray}}\\!\\!\\!\mu^{2}(g)\sum_{\begin{subarray}{c}{m\leq
x/g}\\\
{(m,\Delta)=1}\end{subarray}}\\!\\!\\!\\!\\!\\!\\!\sum_{\begin{subarray}{c}{k\ell=m}\\\
{(k,\ell)=1}\\\
{(k,a)=(\ell,c)=1}\end{subarray}}\\!\\!\\!\\!\\!\\!\\!\mathrm{e}\Big{(}\frac{-hb\bar{a}_{k}\ell\bar{\ell}_{k}g\bar{g}_{k}-hd\bar{c}_{\ell}k\bar{k}_{\ell}g\bar{g}_{\ell}+hr_{g}k\bar{k}_{g}\ell\bar{\ell}_{g}}{mg}\Big{)}\\\
&=\sum_{\begin{subarray}{c}{g\mid\Delta}\\\
{(g,ac)=1}\end{subarray}}\mu^{2}(g)\sum_{\begin{subarray}{c}{k\ell\leq x/g}\\\
{(k,\ell)=1}\\\ {(k,a)=(\ell,c)=1}\\\
{(k\ell,\Delta)=1}\end{subarray}}\mathrm{e}\Big{(}\frac{-hb\bar{a}_{k}\bar{\ell}_{k}\bar{g}_{k}}{k}\Big{)}\mathrm{e}\Big{(}\frac{-hd\bar{c}_{\ell}\bar{k}_{\ell}\bar{g}_{\ell}}{\ell}\Big{)}\mathrm{e}\Big{(}\frac{hr_{g}\bar{k}_{g}\bar{\ell}_{g}}{g}\Big{)}.\end{split}$

We split this into two sums $S(f,x)=S_{1}(x)+S_{2}(x)$, where
$k\leq\sqrt{x/g}$ in $S_{1}(x)$ and $k>\sqrt{x/g}$ in $S_{2}(x)$.

In $S_{1}(x)$, we use the standard “inversion formula” (obtained with Bézout’s
identity) for $(u,v)=1$,

$\frac{\bar{u}}{v}+\frac{\bar{v}}{u}\equiv\frac{1}{uv}{\text{\rm\
(mod~{}$1$)}}.$ (6)

This formula, used on the second exponential factor in the inner sum above,
allows us to move $\ell$ out of the denominators of the exponential terms and
write $S_{1}(x)$ as

$\sum_{\begin{subarray}{c}{g\mid\Delta}\\\
{(g,ac)=1}\end{subarray}}\mu^{2}(g)\sum_{\begin{subarray}{c}{k\leq\sqrt{x/g}}\\\
{(k,a\Delta)=1}\end{subarray}}\sum_{\begin{subarray}{c}{\ell\leq x/gk}\\\
{(\ell,k)=(\ell,c\Delta)=1}\end{subarray}}\mathrm{e}\Big{(}\frac{-hb\bar{a}_{k}\bar{\ell}_{k}\bar{g}_{k}}{k}\Big{)}\mathrm{e}\Big{(}\frac{hd\bar{\ell}_{cgk}}{cgk}\Big{)}\mathrm{e}\Big{(}\frac{-hd}{cgk\ell}\Big{)}\mathrm{e}\Big{(}\frac{hr_{g}\bar{k}_{g}\bar{\ell}_{g}}{g}\Big{)}.$

Next we remark that $\mathrm{e}(-d/cgk\ell)=1+O(1/gk\ell)$. This effect of
this error term is sufficiently small:

$\begin{split}S_{1}(x)&=\sum_{\begin{subarray}{c}{g\mid\Delta}\\\
{(g,ac)=1}\end{subarray}}\mu^{2}(g)\sum_{\begin{subarray}{c}{k\leq\sqrt{x/g}}\\\
{(k,a\Delta)=1}\end{subarray}}\sum_{\begin{subarray}{c}{\ell\leq x/gk}\\\
{(\ell,k)=(\ell,c\Delta)=1}\end{subarray}}\mathrm{e}\Big{(}\frac{(-bcg\bar{a}_{k}\bar{g}_{k}+d+ckr_{g}\bar{k}_{g})h\bar{\ell}_{cgk}}{cgk}\Big{)}\\\
&\qquad{}+O((\log x)^{2}),\\\ \end{split}$

since $\bar{\ell}_{k}\equiv\bar{\ell}_{cgk}{\text{\rm\ (mod~{}$k$)}}$ and
$\bar{\ell}_{g}\equiv\bar{\ell}_{cgk}{\text{\rm\ (mod~{}$g$)}}$. (We remind
the reader that the implicit constants in this section may depend on $f$, $h$,
and $\varepsilon$.)

We rewrite the inner sum over $\ell$ as

$\sum_{\begin{subarray}{c}{\ell\leq x/gk}\\\
{(\ell,ck\Delta)=1}\end{subarray}}\mathrm{e}\Big{(}\frac{\frac{\Delta}{g}(-bcg\bar{a}_{k}\bar{g}_{k}+d+ckr_{g}\bar{k}_{g})h\bar{\ell}_{ck\Delta}}{ck\Delta}\Big{)},$
(7)

and then apply equation (4) with $q=ck\Delta$ and $t=ht^{\prime}$, where
$t^{\prime}=\frac{\Delta}{g}(-bcg\bar{a}_{k}\bar{g}_{k}+d+ckr_{g}\bar{k}_{g})$.
Since $d+ckr_{g}\bar{k}_{g}\equiv d+cr_{g}\equiv 0{\text{\rm\ (mod~{}$g$)}}$,
we see that $t^{\prime}$ is a multiple of $\Delta$ but is relatively prime to
both $c$ and $k$. We thus obtain

$\begin{split}S_{1}(x)&=x\sum_{\begin{subarray}{c}{g\mid\Delta}\\\
{(g,ac)=1}\end{subarray}}\mu^{2}(g)\sum_{\begin{subarray}{c}{k\leq\sqrt{x/g}}\\\
{(k,ac\Delta)=1}\end{subarray}}\frac{\mu\big{(}\frac{ck}{(ck,h)}\big{)}}{cg\Delta
k^{2}}\frac{\varphi(ck\Delta)}{\varphi(ck/(ck,h))}\\\
&\qquad{}+O\Big{(}\sum_{\begin{subarray}{c}{g\mid\Delta}\\\
{(g,ac)=1}\end{subarray}}\mu^{2}(g)\sum_{\begin{subarray}{c}{k\leq\sqrt{x/g}}\\\
{(k,a\Delta)=1}\end{subarray}}(k(k,h))^{1/2+\varepsilon}\Big{)}.\end{split}$

In the previous formula we could insert the condition $(c,k)=1$ in the main
term, because the fact that $(h,c)=1$ means that $\mu(ck/(ck,h))=0$ if
$(c,k)>1$. The error term is $O(x^{3/4+\varepsilon})$. Let $T_{1}(x)$ denote
the main term. By the coprimality conditions among $a,c,\Delta,k$, we get

$T_{1}(x)=x\sum_{\begin{subarray}{c}{g\mid\Delta}\\\
{(g,ac)=1}\end{subarray}}\frac{\mu^{2}(g)\mu\big{(}\frac{c}{(c,h)}\big{)}}{cg\Delta}\frac{\varphi(c\Delta)}{\varphi\big{(}\frac{c}{(c,h)}\big{)}}\sum_{\begin{subarray}{c}{k\leq\sqrt{x/g}}\\\
{(k,ac\Delta)=1}\end{subarray}}\frac{\mu\big{(}\frac{k}{(k,h)}\big{)}}{k^{2}}\frac{\varphi(k)}{\varphi\big{(}\frac{k}{(k,h)}\big{)}}.$

Let $\lambda_{h}$ denote the function in the inner sum over $k$:

$\lambda_{h}(k)=\frac{\mu\big{(}\frac{k}{(k,h)}\big{)}}{k^{2}}\frac{\varphi(k)}{\varphi\big{(}\frac{k}{(k,h)}\big{)}}.$

Note that $\lambda_{h}(k)$ is a multiplicative function of $k$. When $p\nmid
h$, we have $\lambda_{h}(p)=-1/p^{2}$ and $\lambda_{h}(p^{\nu})=0$ for
$\nu\geq 2$. When $p\mid h$, if $v_{p}(h)$ is the $p$-adic valuation of $h$,
we have:

$\lambda_{h}(p^{\nu})=\begin{cases}\frac{\varphi(p^{\nu})}{p^{2\nu}}&\text{if
}\nu\leq v_{p}(h)\\\ -\frac{1}{p^{\nu+1}}&\text{if }\nu=v_{p}(h)+1\\\
0&\text{if }\nu\geq v_{p}(h)+2;\end{cases}$

in particular, $|\lambda_{h}(p^{\nu})|\leq p^{v_{p}(h)}/p^{2\nu}$ always,
which implies that $|\lambda_{h}(n)|\leq h/n^{2}\ll 1/n^{2}$ since $h$ is
fixed. We deduce that

$\sum_{\begin{subarray}{c}{k\leq\sqrt{x/g}}\\\
{(k,ac\Delta)=1}\end{subarray}}\lambda_{h}(k)=\sum_{(k,ac\Delta)=1}\lambda_{h}(k)+O(hx^{-1/2+\varepsilon}),$

from which we obtain $T_{1}(x)=C_{1}(h,a,c,\Delta)x$ with

$\begin{split}C_{1}(h,a,c,\Delta)&=\frac{6}{\pi^{2}}\frac{\mu\big{(}\frac{c}{(c,h)}\big{)}\varphi(c\Delta)}{c\Delta\varphi\big{(}\frac{c}{(c,h)}\big{)}}\prod_{\begin{subarray}{c}{p\mid\Delta}\\\
{(p,ac)=1}\end{subarray}}\left(1+\frac{1}{p}\right)\\\ &\prod_{p\mid
ahc\Delta}\Big{(}1-\frac{1}{p^{2}}\Big{)}^{-1}\prod_{\begin{subarray}{c}{p\mid
h}\\\
{(p,ac\Delta)=1}\end{subarray}}\Big{(}1+\frac{1}{p}-\frac{2}{p^{v_{p}(h)+1}}\Big{)}.\\\
\end{split}$ (8)

In the particular case $h=1$, this gives

$S_{1}(x)=\frac{6x}{\pi^{2}}\frac{\mu(c)}{c}\prod_{p\mid
ac}\Big{(}1-\frac{1}{p^{2}}\Big{)}^{-1}+O(x^{3/4+\varepsilon}).$

In this last computation, we have used the fact that if $p\mid(c,\Delta)$,
then $p\mid a$. In the same way, we derive the asymptotic formula

$S_{2}(x)=C_{1}(h,c,a,\Delta)x+O(x^{3/4+\varepsilon})$ (9)

which, when $h=1$, simplies to

$S_{2}(x)=\frac{6x}{\pi^{2}}\frac{\mu(a)}{a}\prod_{p\mid
ac}\Big{(}1-\frac{1}{p^{2}}\Big{)}^{-1}+O(x^{3/4+\varepsilon}).$

This finishes the proof of Theorem 1 in the case $(h,ac\Delta)=1$.

###  3.2 The case $(h,ac\Delta)\neq 1$

The main difference when dealing with the case $(h,ac\Delta)\neq 1$ is that we
lose some cancellation observed in the proof of Lemma 2. We use the notation
$m\mid n^{\infty}$ to indicate that $p\mid m\Rightarrow p\mid n$, and we sort
the summands according to the prime factors they share with $(h,ac\Delta)$:

$S(f,x,h)=\sum_{\delta\mid(h,ac\Delta)^{\infty}}\sum_{\begin{subarray}{c}{n\leq
x/\delta}\\\
{(n,(h,ac\Delta))=1}\end{subarray}}\sum_{\begin{subarray}{c}{0\leq r<\delta
n}\\\ {f(r)\equiv 0{\text{\rm\ (mod~{}$\delta
n$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{hr}{\delta n}\Big{)}.$ (10)

Since $\deg f=2$, the number of roots of $f(r)\equiv 0{\text{\rm\
(mod~{}$\delta n$)}}$ is less than $2^{\omega(\delta n)}$. Defining
$B=x^{1/5-\varepsilon}$ for some sufficiently small $\varepsilon>0$, we split
this sum as $S(f,x,h)=S_{>}(x,h)+S_{\leq}(x,h)$, where $\delta>B$ in
$S_{>}(x,h)$ and $\delta\leq B$ in $S_{\leq}(x,h)$. When $\delta$ is large, a
trivial upper bound is sufficient:

$\begin{split}S_{>}(x,h)&\ll x\log
x\sum_{\begin{subarray}{c}{\delta\mid(h,ac\Delta)^{\infty}}\\\
{\delta>B}\end{subarray}}\frac{2^{\omega(\delta)}}{\delta}\\\ &\ll x\log
x\sum_{\begin{subarray}{c}{\delta\mid(h,ac\Delta)^{\infty}}\end{subarray}}\frac{\delta^{\varepsilon_{1}}}{\delta}\bigg{(}\frac{\delta}{B}\bigg{)}^{1-2\varepsilon_{1}}=\frac{x\log
x}{B^{1-2\varepsilon_{1}}}\prod_{p\mid(h,ac\Delta)}\Big{(}1-\frac{1}{p^{\varepsilon_{1}}}\Big{)}^{-1}.\\\
\end{split}$ (11)

When $\delta$ is not large, we adapt the method of the previous section. Since
$(n,\delta)=1$, we have by the Chinese remainder theorem:

$S_{\leq}(x,h)=\sum_{\begin{subarray}{c}{\delta\mid(h,ac\Delta)^{\infty}}\\\
{\delta\leq B}\end{subarray}}\sum_{\begin{subarray}{c}{n\leq x/\delta}\\\
{(n,(h,ac\Delta))=1}\end{subarray}}\bigg{(}\sum_{\begin{subarray}{c}{0\leq
r_{0}<\delta}\\\ {f(r_{0}n)\equiv 0{\text{\rm\
(mod~{}$\delta$)}}}\end{subarray}}e\Big{(}\frac{hr_{0}}{\delta}\Big{)}\bigg{)}\bigg{(}\sum_{\begin{subarray}{c}{0\leq
r_{1}<n}\\\ {f(r_{1}\delta)\equiv 0{\text{\rm\
(mod~{}$n$)}}}\end{subarray}}e\Big{(}\frac{hr_{1}}{n}\Big{)}\bigg{)}.$

In order to suppress the dependence of $n$ in the summation in $r_{0}$, we
split this sum according to $n$ modulo $\delta$:

$\begin{split}S_{\leq}(x,h)&=\sum_{\begin{subarray}{c}{\delta\mid(h,ac\Delta)^{\infty}}\\\
{\delta\leq B}\end{subarray}}\sum_{\begin{subarray}{c}{0\leq\alpha<\delta}\\\
{(\alpha,\delta)=1}\end{subarray}}\bigg{(}\sum_{\begin{subarray}{c}{0\leq
r_{0}<\delta}\\\ {f(r_{0}\alpha)\equiv 0{\text{\rm\
(mod~{}$\delta$)}}}\end{subarray}}e\Big{(}\frac{hr_{0}}{\delta}\Big{)}\bigg{)}\\\
&\qquad{}\times\bigg{(}\sum_{\begin{subarray}{c}{n\leq x/\delta}\\\
{(n,(h,ac\Delta))=1}\\\ {n\equiv\alpha{\text{\rm\
(mod~{}$\delta$)}}}\end{subarray}}\sum_{\begin{subarray}{c}{0\leq r_{1}<n}\\\
{f(r_{1}\delta)\equiv 0{\text{\rm\
(mod~{}$n$)}}}\end{subarray}}e\Big{(}\frac{hr_{1}}{n}\Big{)}\bigg{)}.\\\
\end{split}$

Let $G(\alpha,\delta)$ denote the above sum over $r_{0}$ and
$H(\alpha,\delta)$ the double sum over $n$ and $r_{1}$, so that

$S_{\leq}(x,h)=\sum_{\begin{subarray}{c}{\delta\mid(h,ac\Delta)^{\infty}}\\\
{\delta\leq B}\end{subarray}}\sum_{\begin{subarray}{c}{0\leq\alpha<\delta}\\\
{(\alpha,\delta)=1}\end{subarray}}G(\alpha,\delta)H(\alpha,\delta).$ (12)

It is convenient to notice now that the number of summands in the sum defining
$G(\alpha,\delta)$ is at most the number of roots of $f(r){\text{\rm\
(mod~{}$\delta$)}}$, and hence that sum is bounded by a constant depending on
$f$: indeed, a bound for that number of roots by Sitar and the second author
[15, Lemma 3.4] implies that

$|G(\alpha,\delta)|\leq\Delta^{1/2}2^{\omega(\delta)}\leq\Delta^{1/2}2^{\omega(ac\Delta)}.$

We handle the term $H(\alpha,\delta)$ in the same way as in the previous
section. We write $\Delta=\Delta_{1}\Delta_{2}$ with $(\Delta_{1},h)=1$ and
$\Delta_{2}\mid(h,\Delta)^{\infty}$. A version of Lemma 2 with $\Delta_{1}$ in
place of $\Delta$ gives

$H(\alpha,\delta)=\sum_{\begin{subarray}{c}{g\mid\Delta_{1}}\\\ {(g,ac)=1}\\\
\end{subarray}}\mu^{2}(g)\sum_{\begin{subarray}{c}{m\leq x/g\delta}\\\
{(m,\Delta)=1}\\\ {gm\equiv\alpha{\text{\rm\
(mod~{}$\delta$)}}}\end{subarray}}\sum_{\begin{subarray}{c}{0\leq r_{1}<mg}\\\
{f(r_{1}\delta)\equiv 0{\text{\rm\
(mod~{}$mg$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{hr_{1}}{mg}\Big{)}.$

The corresponding sum $S_{1}(x)$ is then of type

$\begin{split}S_{1}(x)&=\sum_{\begin{subarray}{c}{g\mid\Delta_{1}}\\\
{(g,ac)=1}\end{subarray}}\mu^{2}(g)\sum_{\begin{subarray}{c}{k\leq\sqrt{x/\delta
g}}\\\ {(k,a\Delta)=1}\end{subarray}}\sum_{\begin{subarray}{c}{\ell\leq
x/gk\delta}\\\ {(\ell,k)=(\ell,c\Delta)=1}\\\ {gk\ell\equiv\alpha{\text{\rm\
(mod~{}$\delta$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{(-bcg\bar{a}_{k}\bar{g}_{k}+d+ckr_{g}\bar{k}_{g})h\bar{\ell}_{cgk}}{cgk}\Big{)}\\\
&\qquad{}+O((\log x)^{2}).\end{split}$

Since $(\alpha,\delta)=1$, the condition $gk\ell\equiv\alpha{\text{\rm\
(mod~{}$\delta$)}}$ implies that $(g,\delta)=1$. The analogue of equation (7)
is now

$\Sigma_{1}:=\sum_{\begin{subarray}{c}{\ell\leq x/gk}\\\
{(\ell,ck\Delta)=1}\\\ {gk\ell\equiv\alpha{\text{\rm\
(mod~{}$\delta$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{\frac{\Delta_{1}}{g}(-bcg\bar{a}_{k}\bar{g}_{k}+d+ckr_{g}\bar{k}_{g})h\bar{\ell}_{ck\Delta}}{ck\Delta_{1}}\Big{)},$

in which the only real difference from before is the congruence
$gk\ell\equiv\alpha{\text{\rm\ (mod~{}$\delta$)}}$. Let $\delta_{2}$ be the
least common multiple $\delta_{2}=[\delta,\Delta_{2}]$; we still have
$(\delta_{2},ck\Delta_{1})=1$. The two conditions $g\ell
k\equiv\alpha{\text{\rm\ (mod~{}$\delta$)}}$ and $(\ell,\Delta_{2})=1$ can be
expressed using congruences modulo $\delta_{2}$:

$\Sigma_{1}=\sum_{\begin{subarray}{c}{0\leq\beta<\delta_{2}/\delta}\\\
{(\alpha\bar{k}_{\delta}+\delta\beta,\delta_{2})=1}\end{subarray}}\sum_{\begin{subarray}{c}{\ell\leq
x/gk}\\\ {(\ell,ck\Delta_{1})=1}\\\
{\ell\equiv\alpha\bar{k}_{\delta}+\beta\delta{\text{\rm\
(mod~{}$\delta_{2}$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{\frac{\Delta_{1}}{g}(-bcg\bar{a}_{k}\bar{g}_{k}+d+ckr_{g}\bar{k}_{g})h\bar{\ell}_{ck\Delta}}{ck\Delta_{1}}\Big{)}.$

We apply Lemma 1 in the same way as in the case $(\Delta,h)=1$ to obtain:

$S_{\leq}(x,h)=xC(h,a,c,\Delta_{1})\sum_{\begin{subarray}{c}{\delta\mid(h,ac\Delta)^{\infty}}\\\
{\delta\leq B}\end{subarray}}\sum_{\begin{subarray}{c}{0\leq\alpha<\delta}\\\
{(\alpha,\delta)=1}\end{subarray}}\frac{G(\alpha,\delta)}{\delta^{2}}+O\Big{(}x^{3/4+\varepsilon}\sum_{\begin{subarray}{c}{\delta\mid(h,ac\Delta)^{\infty}}\\\
{\delta\leq B}\end{subarray}}\delta^{1/4}\Big{)}.$

If we open the sum $G(\alpha,\delta)$ and exchange the order of summation with
$\alpha$, we find Ramanujan sums:

$\begin{split}\sum_{\begin{subarray}{c}{0\leq\alpha<\delta}\\\
{(\alpha,\delta)=1}\end{subarray}}G(\alpha,\delta)&=\sum_{\begin{subarray}{c}{0\leq
r_{0}<\delta}\\\ {f(r_{0})\equiv 0{\text{\rm\
(mod~{}$\delta$)}}}\end{subarray}}\sum_{\begin{subarray}{c}{0\leq\alpha<\delta}\\\
{(\alpha,\delta)=1}\end{subarray}}\mathrm{e}\Big{(}\frac{hr_{0}\bar{\alpha}}{\delta}\Big{)}\\\
&=\sum_{\begin{subarray}{c}{0\leq r_{0}<\delta}\\\ {f(r_{0})\equiv
0{\text{\rm\
(mod~{}$\delta$)}}}\end{subarray}}\mu\Big{(}\frac{\delta}{(hr_{0},\delta)}\Big{)}\frac{\varphi(\delta)}{\varphi\Big{(}\frac{\delta}{(hr_{0},\delta)}\Big{)}}.\end{split}$

Since $G(\alpha,\delta)\ll 1$ as previously remarked, the sum over $\delta$ in
the main term converges as $B$ tends to $\infty$ (note that the sum is not
over all integers $\delta$ but rather only those integers with prime factors
in a fixed finite set, which is a very sparse sequence), and the error
resulting from replacing the finite sum over $\delta$ with the infinite series
is $\ll x/B^{1-\varepsilon}$. In the error term, the $\delta^{1/4}$ roughly
comes from the summation of the $k^{1/2}$ with $k\leq(x/g\delta)^{1/2}$ and
with a trivial summation of the sum over $\alpha$. This error term is
$O(x^{3/4+\varepsilon}B^{1/4})$.

This ends the proof of Theorem 1, with

$C(f,h)=C(h,a,c,\Delta_{1})\sum_{\begin{subarray}{c}{\delta\mid(h,ac\Delta)^{\infty}}\end{subarray}}\frac{1}{\delta^{2}}\sum_{\begin{subarray}{c}{0\leq
r_{0}<\delta}\\\ {f(r_{0})\equiv 0{\text{\rm\
(mod~{}$\delta$)}}}\end{subarray}}\mu\Big{(}\frac{\delta}{(hr_{0},\delta)}\Big{)}\frac{\varphi(\delta)}{\varphi\Big{(}\frac{\delta}{(hr_{0},\delta)}\Big{)}},$
(13)

where $C(h,a,c,\Delta_{1})$ is as in equation (8).

##  4 Linear times an irreducible quadratic (Theorem 2)

In this section we prove Theorem 2 concerning the polynomial
$f(t)=t(t^{2}+1)$.

###  4.1 First step: splitting $S(f,x)$

Since $(n,n^{2}+1)=1$ we can write $S(f,x)$ as a sort of convolution, as in
the previous section. The following lemma is elementary:

######  Lemma 4.

Let $g(t)$ be a polynomial with integer coefficients with $g(0)=\pm 1$, and
let $m$ be a positive integer. The roots of $rg(r)\equiv 0{\text{\rm\
(mod~{}$m$)}}$ are in one-to-one correspondence with the factorizations
$k\ell=m$ with $(k,\ell)=1$ and corresponding roots $v$ of $g(v)\equiv
0{\text{\rm\ (mod~{}$m$)}}$. The root $r$ corresponds to the solution modulo
$m$ of the system of congruences

$\begin{split}r&\equiv 0{\text{\rm\ (mod~{}$k$)}}\\\ r&\equiv v{\text{\rm\
(mod~{}$\ell$)}}.\\\ \end{split}$

We have by Lemma 4

$S(f,x)=\sum_{n\leq x}\sum_{\begin{subarray}{c}{k\ell=n}\\\
{(k,\ell)=1}\end{subarray}}\sum_{\begin{subarray}{c}{0\leq v<\ell}\\\
{v^{2}+1\equiv 0{\text{\rm\
(mod~{}$\ell$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{\bar{k}v}{\ell}\Big{)}.$

Let $y_{1}=x^{1/3}(\log x)^{-A}$ and $y_{2}=x^{1/3}(\log x)^{B}$ with $A,B>0$
to be chosen. We split the sum $S(x)$ into three parts according to the size
of $k$: $S(f,x)=S_{1}(x)+S_{2}(x)+S_{3}(x)$ with

$\displaystyle S_{1}(x)$ $\displaystyle=\sum_{y_{2}<k\leq
x}\sum_{\begin{subarray}{c}{\ell\leq x/k}\\\
{(k,\ell)=1}\end{subarray}}\sum_{\begin{subarray}{c}{0\leq v<\ell}\\\
{v^{2}+1\equiv 0{\text{\rm\
(mod~{}$\ell$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{\bar{k}v}{\ell}\Big{)}$
$\displaystyle S_{2}(x)$ $\displaystyle=\sum_{y_{1}<k\leq
y_{2}}\sum_{\begin{subarray}{c}{\ell\leq x/k}\\\
{(k,\ell)=1}\end{subarray}}\sum_{\begin{subarray}{c}{0\leq v<\ell}\\\
{v^{2}+1\equiv 0{\text{\rm\
(mod~{}$\ell$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{\bar{k}v}{\ell}\Big{)}$
$\displaystyle S_{3}(x)$ $\displaystyle=\sum_{1\leq k\leq
y_{1}}\sum_{\begin{subarray}{c}{\ell\leq x/k}\\\
{(k,\ell)=1}\end{subarray}}\sum_{\begin{subarray}{c}{0\leq v<\ell}\\\
{v^{2}+1\equiv 0{\text{\rm\
(mod~{}$\ell$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{\bar{k}v}{\ell}\Big{)}.$

We shall see momentarily that in $S_{1}(x)$, it is possible to use equation
(4) in the same way as in the proof of Theorem 1; the main term in our
asymptotic formula for $S(f,x)$ arises from this sum. This approach works only
when $k$ is sufficiently large (or $\ell$ sufficiently small), which is to say
when $k$ is slightly bigger than $x^{1/3}$. This is our motivation for the
choice of $y_{2}$.

The converse is true for $S_{3}(x)$, in which $\ell$ is the largest parameter.
In this case we use the fact that the second factor is quadratic. We can apply
a lemma of Gauss on the correspondence of the roots of $n^{2}+1\equiv
0{\text{\rm\ (mod~{}$\ell$)}}$ and certain representations $\ell=r^{2}+s^{2}$
as the sum of two squares. This approach works when $k=o(x^{1/3})$, which is
why we choose $y_{1}$ close to $x^{1/3}$.

The remaining range $k\in{}]y_{1},y_{2}]$ is covered by a direct application
of Hooley’s result [11]. Since $y_{1}$ and $y_{2}$ are close together,
Hooley’s general bound applied to the irreducible polynomial $X^{2}+1$ is
sufficient.

###  4.2 The first two sums

In the sum $S_{1}(x)$, the variable $k$ is large and thus we arrange for some
cancellation in the sum over this variable:

$S_{1}(x)=\sum_{\ell<x/y_{2}}\sum_{\begin{subarray}{c}{0\leq v<\ell}\\\
{v^{2}+1\equiv 0{\text{\rm\
(mod~{}$\ell$)}}}\end{subarray}}\sum_{\begin{subarray}{c}{y_{2}<k\leq
x/\ell}\\\
{(k,\ell)=1}\end{subarray}}\mathrm{e}\Big{(}\frac{\bar{k}v}{\ell}\Big{)}.$

Let $\varrho(m)$ denote the number of roots modulo $m$ of the polynomial
$n^{2}+1$:

$\varrho(m)=\\#\\{0\leq v<m\colon v^{2}+1\equiv 0{\text{\rm\
(mod~{}$m$)}}\\}.$ (14)

For any $\ell<x/y_{2}$ and any $0\leq v<\ell$ with $v^{2}+1\equiv 0{\text{\rm\
(mod~{}$\ell$)}}$, we apply equation (4) to bound the inner sum in $k$:

$\begin{split}S_{1}(x)&=\sum_{\ell\leq x/y_{2}}\sum_{\begin{subarray}{c}{0\leq
v<\ell}\\\ {v^{2}+1\equiv 0{\text{\rm\
(mod~{}$\ell$)}}}\end{subarray}}\Big{(}\Big{(}\frac{x/\ell-
y_{2}}{\ell}\Big{)}\mu(\ell)+O(\sqrt{\ell}\cdot\tau(\ell)\log\ell)\Big{)}\\\
&=x\sum_{\ell\leq
x/y_{2}}\frac{\mu(\ell)\varrho(\ell)}{\ell^{2}}-y_{2}\sum_{\ell\leq
x/y_{2}}\frac{\mu(\ell)}{\ell}+O\Big{(}\sum_{\ell\leq
x/y_{2}}\sqrt{\ell}\cdot\tau(\ell)\varrho(\ell)\log\ell\Big{)}\\\
&=x\prod_{p}\Big{(}1-\frac{\varrho(p)}{p^{2}}\Big{)}+O(y_{2}x^{\varepsilon}+(x/y_{2})^{3/2}(\log
x)^{5}).\\\ &=x\prod_{p}\Big{(}1-\frac{\varrho(p)}{p^{2}}\Big{)}+O(x(\log
x)^{5-B}).\end{split}$

In the third equality above, we used the calculation

$\begin{split}\sum_{\ell\leq
x/y_{2}}\sqrt{\ell}\cdot\tau(\ell)\varrho(\ell)\log\ell&\ll\Big{(}\frac{x}{y_{2}}\Big{)}^{3/2}\log
x\sum_{\ell\leq x/y_{2}}\frac{\tau(\ell)\varrho(\ell)}{\ell}\\\
&\ll\Big{(}\frac{x}{y_{2}}\Big{)}^{3/2}\log x\prod_{p\leq
x/y_{2}}\Big{(}1+\sum_{k=1}^{\infty}\frac{\tau(p^{k})\varrho(p^{k})}{p^{k}}\Big{)},\end{split}$

followed by the fact that $\varrho(p^{k})\leq 2$ for all prime powers $p^{k}$.
(We could in fact replace the exponent $5-B$ by $2-3B/2$, using the fact that
$\varrho(p^{k})=0$ if $p\equiv 3{\text{\rm\ (mod~{}$4$)}}$, but that
improvement is not significant for our purposes.)

In the sum $S_{2}(x)$, the variable $k$ is in a crucial range (corresponding
to when the size of $k$ is close to $\sqrt{\ell}$) where the methods for both
$S_{1}(x)$ and $S_{3}(x)$ fail. The bound for $S_{2}(x)$ will be a direct
consequence of the work of Hooley:

######  Lemma 5.

Let $P(X)\in\mathbb{Z}[X]$ be an irreducible polynomial of degree $n\geq 2$.
If $hk\not=0$ then we have

$\sum_{\begin{subarray}{c}{\ell\leq x}\\\
{(\ell,k)=1}\end{subarray}}\sum_{\begin{subarray}{c}{v{\text{\rm\
(mod~{}$\ell$)}}}\\\ {P(v)\equiv 0{\text{\rm\
(mod~{}$\ell$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{h\bar{k}v}{\ell}\Big{)}\ll_{h,P}x\frac{(\log\log
x)^{(n^{2}+1)/2}}{(\log x)^{\delta_{n}}},$

where $\delta_{n}=(n-\sqrt{n})/{n!}$.

The case $k=1$ is [11, Theorem 1]; the proof can be adapted with no difficulty
for all $k\in\mathbb{N}$ and provides then a result that is uniform in $k$.
The dependence on $h$ in this result of Hooley is due only to the appearance
of $(h,\ell)$ in certain intermediate computations.

We apply this lemma with $P(X)=X^{2}+1$ and replacing $x$ by $x/k$:

$\begin{split}S_{2}(x)&\ll\sum_{y_{1}\leq k\leq
y_{2}}\frac{x}{k}\frac{(\log\log x)^{5/2}}{(\log x)^{1-1/\sqrt{2}}}\ll
x\frac{(\log\log x)^{7/2}}{(\log x)^{1-1/\sqrt{2}}},\end{split}$

using the fact that $\log(y_{2}/y_{1})\ll\log\log x$.

###  4.3 The sum $S_{3}(x)$

In this section we use the special shape of the polynomial $n^{2}+1$ to find
an upper bound for $S_{3}(x)$. Following the ideas of the two articles of
Hooley [10, 12] concerning $\tau(n^{2}+1)$ and $P^{+}(n^{2}+1)$ (the number of
divisors of $n^{2}+1$ and the largest prime factor of $n^{2}+1$,
respectively), we employ the Gauss correspondence between the roots of
$v^{2}+1\equiv 0{\text{\rm\ (mod~{}$\ell$)}}$ and certain representations of
$\ell=r^{2}+s^{2}$ as the sum of two squares. Indeed for such integers $r,s$
with $(rs,\ell)=1$, we have $(\bar{r}s)^{2}+1\equiv 0{\text{\rm\
(mod~{}$\ell$)}}$. The parameter $\bar{k}$ in the exponential gives rise to
some coprimality problems. The first author [3] resolved such a difficulty
when $k$ is squarefree; in equation (15) we will use an elegant formula of Wu
and Xi [20] to handle the general case.

As in the proof of Theorem 1, in the following argument the condition
$k_{2}=(k,r^{\infty})$ means that $p\mid k_{2}\Rightarrow p\mid r$ and
$(k/k_{2},r)=1$.

######  Lemma 6.

For $\ell>1$, there is a one-to-one correspondence between the representations
of $\ell$ by the form $\ell=r^{2}+s^{2}$ with $(r,s)=1$, $r>0,s>0$ and the
solutions of the congruence $v^{2}+1\equiv 0{\text{\rm\ (mod~{}$\ell$)}}$.
This bijection is given by:

$\frac{v}{\ell}=\frac{\bar{s}}{r}-\frac{s}{r(r^{2}+s^{2})}{\text{\rm\
(mod~{}$1$)}}.$

For $k\geq 1$, $k=k_{1}k_{2}$ with $k_{2}=(k,r^{\infty})$ we have

$\frac{\bar{k}v}{\ell}=\frac{-r\overline{k_{2}(r^{2}+s^{2})}}{k_{1}s}+\frac{r}{ks(r^{2}+s^{2})}-\frac{r\overline{k_{1}s(r^{2}+s^{2})}}{k_{2}}{\text{\rm\
(mod~{}$1$)}}.$ (15)

The first part of this lemma is proved in detail in the book of Smith [19,
Art. 86], while equation (15) is [20, Lemma 7.4].

By this lemma, still using the notation $k=k_{1}k_{2}$, we have

$S_{3}(x)=\sum_{\begin{subarray}{c}{k_{1}k_{2}\leq y_{1}}\\\
{(k_{1},k_{2})=1}\end{subarray}}\sum_{\begin{subarray}{c}{r^{2}+s^{2}\leq
x/(k_{1}k_{2})}\\\ {(r,s)=1,\,r>0,\,s>0}\\\
{(k_{1}k_{2},r^{\infty})=k_{2}}\end{subarray}}\mathrm{e}\Big{(}\frac{-r\overline{k_{2}(r^{2}+s^{2})}}{k_{1}s}+\frac{r}{ks(r^{2}+s^{2})}-\frac{r\overline{k_{1}s(r^{2}+s^{2})}}{k_{2}}\Big{)}.$

First we remove the term $\mathrm{e}\big{(}{r}/{ks(r^{2}+s^{2})}\big{)}$:
since

$\mathrm{e}\Big{(}\frac{r}{ks(r^{2}+s^{2})}\Big{)}=1+O\Big{(}\frac{1}{ksr}\Big{)},$

replacing this term by $1$ results in a corresponding error in $S_{3}(x)$ that
is $O((\log x)^{4})$.

Following the notation of several authors, we denote by $(k_{1}s)^{\flat}$ and
$(k_{1}s)^{\sharp}$ the squarefree and squarefull part, respectively, of
$k_{1}s$. Since $((k_{1}s)^{\flat},(k_{1}s)^{\sharp})=1$, we can use the
Chinese remainder theorem as in the proof of Theorem 1:

$\frac{1}{k_{1}s}\equiv\frac{\overline{(k_{1}s)^{\sharp}}}{(k_{1}s)^{\flat}}+\frac{\overline{(k_{1}s)^{\flat}}}{(k_{1}s)^{\sharp}}{\text{\rm\
(mod~{}$1$)}}.$

Inserting this in $S_{3}(x)$, we obtain

$S_{3}(x)=\sum_{\begin{subarray}{c}{k_{1}k_{2}\leq y_{1}}\\\
{(k_{1},k_{2})=1}\end{subarray}}\sum_{\begin{subarray}{c}{r^{2}+s^{2}\leq
x/(k_{1}k_{2})}\\\ {(r,s)=1,r>0,s>0}\\\
{(k_{1}k_{2},r^{\infty})=k_{2}}\end{subarray}}K(r)W(r)+O((\log x)^{4}),$ (16)

with

$\displaystyle K(r)$
$\displaystyle=\mathrm{e}\Big{(}\frac{-r\overline{k_{2}(r^{2}+s^{2})(k_{1}s)^{\sharp}}}{(k_{1}s)^{\flat}}\Big{)}$
$\displaystyle W(r)$
$\displaystyle=\mathrm{e}\Big{(}\frac{-r\overline{k_{2}(r^{2}+s^{2})(k_{1}s)^{\flat}}}{(k_{1}s)^{\sharp}}-\frac{r\overline{k_{1}s(r^{2}+s^{2})}}{k_{2}}\Big{)}.$

Let $S_{4}(x)$ denote the contribution to $S_{3}(x)$ of the $k_{1},k_{2},r,s$
such that $(k_{1}s)^{\sharp}>(\log x)^{45}$ or $k_{2}>(\log x)^{5}$, and
$S_{5}(x)$ the remaining contribution, that is, the contribution of the
$k_{1},k_{2},r,s$ such that $k_{2}\leq(\log x)^{5}$ and
$(k_{1}s)^{\sharp}\leq(\log x)^{45}$.

First we prove that

$S_{4}(x)\ll x(\log x)^{-3}.$ (17)

We remark that if $m^{2}$ is the largest square divisor of $(k_{1}s)^{\sharp}$
then $m^{2}\geq((k_{1}s)^{\sharp})^{2/3}$. We deduce that when
$(k_{1}s)^{\sharp}>(\log x)^{45}$, there exists $m>(\log x)^{15}$ such that
$m^{2}\mid(k_{1}s)^{\sharp}$. We can write this divisor in the following way:
$m^{2}=u^{2}v^{2}w^{2}$ with $u^{2}\mid k_{1}$, $v^{2}\mid s$, and
$w\mid(k_{1},s)$. Thus we have $\max\\{u^{2},v^{2},w^{2}\\}\geq m^{2/3}$ and
there exists $d>(\log x)^{5}$ such that $d^{2}\mid k_{1}$ or $d^{2}\mid s$ or
$d\mid(k_{1},s)$. In the first case (when $d^{2}\mid k_{1}$), the contribution
of the $k_{1},k_{2},r,s$ is less than

$\sum_{(\log x)^{5}<d\leq
y_{1}}\sum_{d^{2}k_{1}k_{2}<y_{1}}\sum_{\max\\{r,s\\}\ll
x^{1/2}/(d^{2}k_{1}k_{2})^{1/2}}1\ll x(\log x)^{-3}.$

Similarly, in the second case (when $d^{2}\mid s$), we have a contribution
less than

$\sum_{k_{1}k_{2}<y_{1}}\sum_{r\ll(x/k_{1}k_{2})^{1/2}}\sum_{(\log
x)^{5}<d}\sum_{s\ll x^{1/2}/(d^{2}k_{1}^{1/2}k_{2}^{1/2})}1\ll x(\log
x)^{-3}.$

Finally the contribution of the terms with $d\mid(k_{1},s)$ is less than

$\sum_{d>(\log x)^{5}}\sum_{dk_{1}k_{2}\leq
y_{1}}\sum_{\max\\{r,ds\\}\ll(x/dk_{1}k_{2})^{1/2}}1\ll x(\log x)^{-3}.$

It remains to evaluate the contribution to $S_{4}(x)$ of the terms where
$k_{2}>(\log x)^{5}$. Since $k_{2}=(k_{1}k_{2},r^{\infty})$, we have
$q(k_{2})\mid r$ where $q(k_{2})=\prod_{p\mid k_{2}}p$ is the squarefree
kernel of $k_{2}$. Thus, the contribution of $r$ is bounded by
$x^{1/2}/(q(k_{2})(k_{1}k_{2})^{1/2})$, and then the corresponding summation
of all the $k_{1},k_{2},r,s$ with $k_{2}>(\log x)^{5}$ is less than

$\sum_{(\log
x)^{5}<k_{2}<y_{1}}\sum_{k_{2}k_{1}<y_{1}}\frac{x}{k_{1}k_{2}q(k_{2})}\ll
x(\log x)^{-3}\sum_{k_{2}\geq 1}\frac{1}{q(k_{2})k_{2}^{1/5}}\ll x(\log
x)^{-3}.$

The rest of this section is devoted to the sum $S_{5}(x)$, which can be
written as

$S_{5}(x)=\sum_{\begin{subarray}{c}{k_{1}k_{2}\leq y_{1}}\\\
{(k_{1},k_{2})=1}\\\ {k_{2}\leq(\log
x)^{5}}\end{subarray}}\sum_{\begin{subarray}{c}{r^{2}+s^{2}\leq
x/(k_{1}k_{2})}\\\ {r,s>0,(r,s)=1}\\\ {q(k_{2})\mid r}\\\ {(k_{1},r)=1}\\\
{(k_{1}s)^{\sharp}\leq(\log x)^{45}}\end{subarray}}K(r)W(r).$

If we replace $r$ by $q(k_{2})r^{\prime}$, the sum over $r^{\prime}$ has the
shape

$S_{R}=\sum_{r^{\prime}<R,\,(r^{\prime},s)=1}K(r^{\prime}q(k_{2}))W(r^{\prime}q(k_{2}))$

for some quantity $R=R(s,k_{1},k_{2})\ll x^{1/2}/(q(k_{2})\sqrt{k_{1}k_{2}})$.
It is then standard to complete the sum:

$S_{R}=\frac{1}{k_{1}k_{2}s}\sum_{h=1}^{k_{1}k_{2}s}\bigg{(}\sum_{\begin{subarray}{c}{a=1}\\\
{(a,s)=1}\end{subarray}}^{k_{1}k_{2}s}K(aq(k_{2}))W(aq(k_{2}))\mathrm{e}\Big{(}\frac{ah}{k_{1}k_{2}s}\Big{)}\bigg{)}\bigg{(}\sum_{r^{\prime}<R}\mathrm{e}\Big{(}{-}\frac{hr^{\prime}}{k_{1}k_{2}s}\Big{)}\bigg{)}.$

As before, the inner sum over $r^{\prime}$ is geometric and is
$\ll\min\big{\\{}R,\|{h}/{k_{1}k_{2}s}\|^{-1}\big{\\}}$. Let $S_{a}$ denote
the inner sum over the variable $a$, which is a complete sum. Applying the
Chinese remainder theorem many times, we have:

$S_{a}=\prod_{p\mid(k_{1}s)^{\flat}}\Big{(}\sum_{a{\text{\rm\
(mod~{}$p$)}}}K_{p}(a)\mathrm{e}(ha/p)\Big{)}\prod_{p^{\nu}\|k_{2}(k_{1}s)^{\sharp}}\Big{(}\sum_{a{\text{\rm\
(mod~{}$p^{\nu}$)}}}W_{p^{\nu}}(a)\mathrm{e}(ha/p^{\nu})\Big{)},$

where

$K_{p}(a)=\mathrm{e}\Big{(}\frac{-aq(k_{2})\overline{k_{2}(a^{2}q(k_{2})^{2}k_{2}^{2}(k_{1}s/p)^{2}+s^{2})}}{p}\Big{)}.$

and $W_{p\nu}$ is an exponential term modulo $p^{\nu}$ whose argument is a
similar rational function in $a$. Since $k_{2}(k_{1}s)^{\sharp}\leq(\log
x)^{50}$, a trivial bound for the sums on the $a{\text{\rm\
(mod~{}$p^{\nu}$)}}$ when $p^{\nu}\mid k_{2}(k_{1}s)^{\sharp}$ is sufficient,
yielding

$\displaystyle S_{a}$
$\displaystyle\ll\prod_{p\mid(k_{1}s)^{\flat}}\Big{|}\sum_{a{\text{\rm\
(mod~{}$p$)}}}K_{p}(a)\mathrm{e}(ha/p)\Big{|}\prod_{p^{\nu}\|k_{2}(k_{1}s)^{\sharp}}p^{\nu}$
$\displaystyle\ll(\log
x)^{50}\prod_{p\mid(k_{1}s)^{\flat}}\Big{|}\sum_{a{\text{\rm\
(mod~{}$p$)}}}K_{p}(a)\mathrm{e}(ha/p)\Big{|}.$

(It is in fact possible to find in [20, Appendix B] a useful nontrivial bound
for the sums that we have estimated trivially.)

Since $(k_{1}s)^{\flat}$ is squarefree, we can apply Weil’s bound for
exponential sums of a rational function. The formulation we use is a
particular case derived from [4, equation (3.5.2)].

######  Lemma 7.

Let $\mathbb{P}^{1}(\mathbb{F}_{p})$ be the projective line on
$\mathbb{F}_{p}$, and let
$f\colon\mathbb{P}^{1}(\mathbb{F}_{p})\rightarrow\mathbb{P}^{1}(\mathbb{F}_{p})$
be a nonconstant rational function. For all
$u\in\mathbb{P}^{1}(\mathbb{F}_{p})$, let $v_{u}(f)$ be the order of the pole
of $f$ at $u$ if $f(u)=\infty$ and $v_{u}(f)=0$ otherwise. Then we have

$\Big{|}\sum_{\begin{subarray}{c}{u\in\mathbb{P}^{1}(\mathbb{F}_{p})}\\\
{f(u)\not=\infty}\end{subarray}}\mathrm{e}\Big{(}\frac{f(u)}{p}\Big{)}\Big{|}\leq\sum_{v_{u}(f)\not=0}(1+v_{u}(f))p^{1/2}$
(18)

Since $K_{p}(a)e(ha/p)$ has at most $3$ poles (including the pole at
$\infty$), which are simple, we have

$\Big{|}\sum_{a{\text{\rm\ (mod~{}$p$)}}}K_{p}(a)\mathrm{e}(ha/p)\Big{|}\leq
6\sqrt{p},$

from which we deduce that

$|S_{a}|\leq 6^{\omega((k_{1}s)^{\flat})}\sqrt{k_{1}s}(\log x)^{50}.$

Returning to $S_{R}$, we have obtained

$S_{R}\ll\frac{R}{k_{1}k_{2}s}6^{\omega((k_{1}s)^{\flat})}\sqrt{k_{1}s}(\log
x)^{50}+6^{\omega((k_{1}s)^{\flat})}\sqrt{k_{1}s}(\log x)^{51},$

which gives the following upper bound for $S_{5}(x)$:

$\begin{split}S_{5}(x)&\ll(\log
x)^{51}\sum_{\begin{subarray}{c}{k_{1}k_{2}\leq y_{1}}\\\ {k_{2}\leq(\log
x)^{5}}\end{subarray}}\sum_{s\ll\sqrt{x/(k_{1}k_{2})}}6^{\omega((k_{1}s)^{\flat})}\Big{(}\frac{\sqrt{x}}{q(k_{2})\sqrt{k_{1}k_{2}s}}+\sqrt{k_{1}s}\Big{)}\\\
&\ll x^{3/4}y_{1}^{3/4}(\log x)^{63}.\\\ \end{split}$

If we take $y_{1}=x^{1/3}(\log x)^{-100}$ we obtain $S_{5}\ll x(\log
x)^{-12}$, which is enough for the proof of Theorem 2.

##  5 Three linear factors (Theorem 3)

In this section we consider one of the simplest cases of a product of three
linear factors, namely the case $f(n)=n(n+1)(2n+1)$. Since
$(n,(n+1)(2n+1))=(n+1,2n+1)=1$, our exponential sum is now

$\displaystyle S(f,x)$ $\displaystyle=\sum_{n\leq
x}\sum_{\begin{subarray}{c}{r{\text{\rm\ (mod~{}$n$)}}}\\\ {f(r)\equiv
0{\text{\rm\ (mod~{}$n$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{r}{n}\Big{)}$
$\displaystyle=\sum_{n_{1}n_{2}n_{3}\leq
x}\sum_{\begin{subarray}{c}{r{\text{\rm\ (mod~{}$n_{1}n_{2}n_{3}$)}}}\\\
{n_{1}\mid r}\\\ {r+1\equiv 0{\text{\rm\ (mod~{}$n_{2}$)}}}\\\ {2r+1\equiv
0{\text{\rm\
(mod~{}$n_{3}$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{r}{n_{1}n_{2}n_{3}}\Big{)};$

note that the inner sum has one term when $n_{1}$, $n_{2}$, and $n_{3}$ are
pairwise coprime and $n_{3}$ is odd, and no terms otherwise.

Let $y_{2}=x^{1/3}(\log x)^{B}$ with $B>0$ to be specified. As in the previous
sections we split the sum $S(f,x)$, writing $S(f,x)=\sum_{i=1}^{4}S_{i}(x)$
where

$\displaystyle S_{1}(x)$
$\displaystyle=\sum_{\begin{subarray}{c}n_{1}n_{2}n_{3}\leq x\\\
n_{1}>y_{2}\end{subarray}}\sum_{\begin{subarray}{c}{r{\text{\rm\
(mod~{}$n_{1}n_{2}n_{3}$)}}}\\\ {n_{1}\mid r}\\\ {r+1\equiv 0{\text{\rm\
(mod~{}$n_{2}$)}}}\\\ {2r+1\equiv 0{\text{\rm\
(mod~{}$n_{3}$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{r}{n_{1}n_{2}n_{3}}\Big{)}$
$\displaystyle S_{2}(x)$
$\displaystyle=\sum_{\begin{subarray}{c}n_{1}n_{2}n_{3}\leq x\\\ n_{1}\leq
y_{2}\\\ n_{2}>y_{2}\end{subarray}}\sum_{\begin{subarray}{c}{r{\text{\rm\
(mod~{}$n_{1}n_{2}n_{3}$)}}}\\\ {n_{1}\mid r}\\\ {r+1\equiv 0{\text{\rm\
(mod~{}$n_{2}$)}}}\\\ {2r+1\equiv 0{\text{\rm\
(mod~{}$n_{3}$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{r}{n_{1}n_{2}n_{3}}\Big{)}$
$\displaystyle S_{3}(x)$
$\displaystyle=\sum_{\begin{subarray}{c}n_{1}n_{2}n_{3}\leq x\\\
n_{1},n_{2}\leq y_{2}\\\
n_{3}>y_{2}\end{subarray}}\sum_{\begin{subarray}{c}{r{\text{\rm\
(mod~{}$n_{1}n_{2}n_{3}$)}}}\\\ {n_{1}\mid r}\\\ {r+1\equiv 0{\text{\rm\
(mod~{}$n_{2}$)}}}\\\ {2r+1\equiv 0{\text{\rm\
(mod~{}$n_{3}$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{r}{n_{1}n_{2}n_{3}}\Big{)}$
$\displaystyle S_{4}(x)$
$\displaystyle=\sum_{\begin{subarray}{c}n_{1}n_{2}n_{3}\leq x\\\
n_{1},n_{2},n_{3}\leq
y_{2}\end{subarray}}\sum_{\begin{subarray}{c}{r{\text{\rm\
(mod~{}$n_{1}n_{2}n_{3}$)}}}\\\ {n_{1}\mid r}\\\ {r+1\equiv 0{\text{\rm\
(mod~{}$n_{2}$)}}}\\\ {2r+1\equiv 0{\text{\rm\
(mod~{}$n_{3}$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{r}{n_{1}n_{2}n_{3}}\Big{)}.$

###  5.1 The first three sums

Using a method similar to Section 2 above, the solution $r$ of the congruences
in the above sums can be written as

$r=n_{1}\big{(}{-}\overline{(n_{1}n_{3})}_{n_{2}}n_{3}-\overline{(2n_{1}n_{2})}_{n_{3}}n_{2}\big{)},$

and therefore the exponential summand in the $S_{i}(x)$ becomes

$\mathrm{e}\Big{(}\frac{r}{n_{1}n_{2}n_{3}}\Big{)}=\mathrm{e}\Big{(}\frac{-\overline{n_{1}n_{3}}}{n_{2}}-\frac{\overline{2n_{1}n_{2}}}{n_{3}}\Big{)}.$
(19)

For $S_{1}(x)$ this gives:

$S_{1}(x)=\sum_{\begin{subarray}{c}{n_{2}n_{3}\leq x/y_{2}}\\\
{(2n_{2},n_{3})=1}\end{subarray}}\sum_{y_{2}<n_{1}\leq
x/(n_{2}n_{3})}\mathrm{e}\Big{(}\frac{\bar{n}_{1}(n_{3}\overline{(n_{3})}_{n_{2}}-n_{2}\overline{(2n_{2})}_{n_{3}})}{n_{2}n_{3}}\Big{)}.$

We apply equation (4) with
$t=n_{3}\overline{(n_{3})}_{n_{2}}-n_{2}\overline{(2n_{2})}_{n_{3}}$. In this
case $(t,n_{2}n_{3})=1$ and we obtain:

$S_{1}(x)=\sum_{\begin{subarray}{c}{n_{2}n_{3}\leq x/y_{2}}\\\
{(2n_{2},n_{3})=1}\end{subarray}}\bigg{(}\Big{(}\frac{x/(n_{2}n_{3})-y_{2}}{n_{2}n_{3}}\Big{)}\mu(n_{2}n_{3})+O(\sqrt{n_{2}n_{3}}\cdot\tau(n_{2}n_{3})\log
x)\bigg{)}.$

The error term is $O\big{(}(x/y_{2})^{3/2}(\log x)^{5}\big{)}$ which is
sufficiently small if $B$ is large enough, and therefore

$\begin{split}S_{1}(x)&=x\sum_{(2n_{2},n_{3})=1}\frac{\mu(n_{2})\mu(n_{3})}{n_{2}^{2}n_{3}^{2}}+O(y_{2}x^{\varepsilon})+O\big{(}(x/y_{2})^{3/2}(\log
x)^{5}\big{)}\\\
&=x\frac{6}{\pi^{2}}\sum_{n_{2}}\frac{\mu(n_{2})}{n_{2}^{2}}\prod_{p|2n_{2}}\Big{(}1-\frac{1}{p^{2}}\Big{)}^{-1}+O\big{(}(x/y_{2})^{3/2}(\log
x)^{5}\big{)}\\\ &=x\frac{6}{\pi^{2}}\prod_{p\geq
3}\Big{(}1-\frac{1}{p^{2}-1}\Big{)}+O\big{(}(x/y_{2})^{3/2}(\log
x)^{5}\big{)}.\end{split}$

We handle the sum $S_{2}(x)$ in the same way, but this time summing first over
$n_{2}$ instead of $n_{1}$. Applying the inversion formula (6), we can rewrite
equation (19) in the following way:

$\begin{split}\mathrm{e}\Big{(}\frac{r}{n_{1}n_{2}n_{3}}\Big{)}&=\mathrm{e}\Big{(}\frac{\bar{n}_{2}}{n_{1}n_{3}}-\frac{1}{n_{1}n_{2}n_{3}}-\frac{\overline{2n_{1}n_{2}}}{n_{3}}\Big{)}\\\
&=\mathrm{e}\Big{(}\frac{\bar{n}_{2}(1-\overline{(2n_{1})}_{n_{3}}n_{1})}{n_{1}n_{3}}\Big{)}+O\Big{(}\frac{1}{n_{1}n_{2}n_{3}}\Big{)}.\end{split}$

The error term $O(1/n_{1}n_{2}n_{3})$ yields a contribution to $S_{2}(x)$ that
is less than $O((\log x)^{3})$. Then we apply equation (4):

$S_{2}(x)=\sum_{\begin{subarray}{c}{n_{1}n_{3}\leq x/y_{2}}\\\ {n_{1}\leq
y_{2}}\\\
{(2n_{1},n_{3})=1}\end{subarray}}\bigg{(}\Big{(}\frac{x}{n_{1}n_{3}}-y_{2}\Big{)}\frac{\mu(n_{1}n_{3})}{n_{1}n_{3}}+O(\sqrt{n_{1}n_{3}}\cdot\tau(n_{1}n_{3})\log
x)\bigg{)}.$

We finish in the same way as for $S_{1}(x)$, obtaining the same asymptotic
formula.

For $S_{3}(x)$ the corresponding method is to write

$\mathrm{e}\Big{(}\frac{r}{n_{1}n_{2}n_{3}}\Big{)}=\mathrm{e}\Big{(}\frac{\bar{n}_{3}(1-\overline{(n_{1})}_{n_{2}}2n_{1})}{2n_{1}n_{2}}\Big{)}+O\Big{(}\frac{1}{n_{1}n_{2}n_{3}}\Big{)},\
$

and then after applying equation (4)

$S_{3}(x)=\sum_{\begin{subarray}{c}{n_{1}n_{2}\leq x/y_{2}}\\\
{\max\\{n_{1},n_{2}\\}\leq y_{2}}\\\
{(n_{1},n_{2})=1}\end{subarray}}\Big{(}\Big{(}\frac{x}{n_{1}n_{2}}-y_{2}\Big{)}\frac{\mu(2n_{1}n_{2})}{2n_{1}n_{2}}+O(\sqrt{n_{1}n_{2}}\cdot\tau(n_{1}n_{2})\log
x)\Big{)}.$

The corresponding main term this time is

$S_{3}(x)=x\sum_{(n_{1},n_{2})=1}\frac{\mu(2n_{1}n_{2})}{2n_{1}^{2}n_{2}^{2}}=-\frac{4x}{\pi^{2}}\prod_{p\geq
3}\Big{(}1-\frac{1}{p^{2}-1}\Big{)}+O\big{(}(x/y_{2})^{3/2}(\log
x)^{5}\big{)}.$

Summing these contributions of $S_{1}(x)$, $S_{2}(x)$, and $S_{3}(x)$ in the
decomposition at the start of this section, we deduce that

$\displaystyle S(f,x)$ $\displaystyle=\frac{8x}{\pi^{2}}\prod_{p\geq
3}\Big{(}1-\frac{1}{p^{2}-1}\Big{)}+O\big{(}|S_{4}(x)|+(x/y_{2})^{3/2}(\log
x)^{5}\big{)}$ $\displaystyle=x\prod_{p\geq
3}\Big{(}1-\frac{2}{p^{2}}\Big{)}+O\big{(}|S_{4}(x)|+x/(\log
x)^{3B/2-5}\big{)}.$

###  5.2 The sum $S_{4}(x)$

It remains to handle $S_{4}(x)$. Let $y_{1}=x^{1/3}(\log x)^{-A}$ with $A>0$
to be specified. Let $I$ denote the interval $I=[y_{1},y_{2}]$. First we
remark that the number of summands for which
$\min\\{n_{1},n_{2},n_{3}\\}<y_{1}$ is $\ll y_{1}y_{2}^{2}$, and hence

$S_{4}(x)=\sum_{\begin{subarray}{c}{n_{1}n_{2}n_{3}\leq x}\\\
{n_{1},n_{2},n_{3}\in I}\end{subarray}}\sum_{\begin{subarray}{c}{r{\text{\rm\
(mod~{}$n_{1}n_{2}n_{3}$)}}}\\\ {n_{1}\mid r}\\\ {r+1\equiv 0{\text{\rm\
(mod~{}$n_{2}$)}}}\\\ {2r+1\equiv 0{\text{\rm\
(mod~{}$n_{3}$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{r}{n_{1}n_{2}n_{3}}\Big{)}+O\Big{(}\frac{x}{(\log
x)^{A-2B}}\Big{)}.$

We introduce a new parameter $z=\exp(\log x/(10\log\log x))$. We now write
$n_{2}=a_{2}b_{2}$, $n_{3}=a_{3}b_{3}$ with $P^{+}(a_{2}a_{3})\leq
z<P^{-}(b_{2}b_{3})$ where $P^{+}(n)$ and $P^{-}(n)$ are, respectively, the
largest and smallest prime factors of $n$. Using two more parameters $v$ and
$w$, we split $S_{4}(x)$ as $S_{4}(x)=S_{5}(x)+S_{6}(x)+S_{7}(x)+O(x(\log
x)^{2B-A})$, where $\max(a_{2},a_{3})\leq v$ in $S_{5}(x)$,
$\max(a_{2},a_{3})>w$ in $S_{6}(x)$, and finally $v<\max\\{a_{2},a_{3}\\}\leq
w$ in $S_{7}(x)$.

In $S_{5}(x)$, since $a_{2},a_{3}$ are small we have:

$\begin{split}S_{5}(x)&\leq\sum_{a_{2},a_{3}\leq v}\sum_{n_{1},a_{2}b_{2}\in
I}\sum_{b_{3}\leq x/(n_{1}n_{2}a_{3})}1\\\ &\ll\frac{x}{\log
z}\sum_{a_{2},a_{3}\leq v}\sum_{n_{1},a_{2}b_{2}\in
I}\frac{1}{n_{1}n_{2}a_{3}}\ll\frac{x(\log v)^{2}(\log\log x)^{2}}{(\log
z)^{2}}.\\\ \end{split}$ (20)

The $(\log z)^{2}$ above comes from the sieving conditions on $b_{2}$ and
$b_{3}$. In particular, we have used the following inequality

$\sum_{y_{1}/a_{2}\leq b_{2}\leq y_{2}/a_{2}}\frac{1}{b_{2}}\ll\frac{\log\log
x}{\log z},$ (21)

which can be derived by partial summation from [1, Proposition 1]. The bound
(20) is sufficiently small when $(\log v)(\log\log x)=o(\log z)$ (we will
eventually choose $v$ to be a power of $\log x$). We remark that this step is
the main obstacle to having an upper bound less than $x/(\log x)^{2}$ in the
error term in Theorem 3.

For $S_{6}(x)$, we estimate each summand trivially by $1$; therefore we may
assume that $a_{3}>w$ is abnormally large (the bound when $a_{2}>w$ is exactly
the same) and that $n_{2}$ is unrestricted. Following some ideas of Hooley
[12], we note that if $a_{3}>w$, then either $\omega(a_{3})\geq\log w/(2\log
z)$, or else there exists $d>w^{1/4}$ such that $d^{2}\mid a_{3}$. We
therefore have (ignoring here the condition that $b_{3}$ has no small prime
factors)

$\begin{split}S_{6}(x)&\leq\sum_{n_{1},n_{2}\in
I}\sum_{w^{1/4}<d<y_{2}}\sum_{b_{3}\leq
x/(n_{1}n_{2}d^{2})}1+\sum_{n_{1},n_{2}\in
I}\sum_{\begin{subarray}{c}{a_{3}<y_{2}}\\\ {\omega(a_{3})\geq(\log w)/2\log
z}\end{subarray}}\sum_{b_{3}\leq x/(n_{1}n_{2}a_{3})}1\\\
&\ll\sum_{n_{1},n_{2}\in
I}\sum_{d>w^{1/4}}\frac{x}{n_{1}n_{2}d^{2}}+\sum_{n_{1},n_{2}\in
I}\sum_{a_{3}\leq y_{2}}\frac{x2^{\omega(a_{3})-\log w/(2\log
z)}}{n_{1}n_{2}a_{3}}\\\ &\ll\frac{x(\log\log x)^{2}}{w^{1/4}}+x2^{-\log
w/(2\log z)}(\log\log x)^{2}(\log x)^{2}.\\\ \end{split}$ (22)

It remains to handle the term $S_{7}(x)$. We begin in the same way as for
$S_{1}(x)$:

$S_{7}(x)=\sum_{\begin{subarray}{c}a_{2}b_{2},a_{3}b_{3}\in I\\\
P^{+}(a_{2}a_{3})\leq z<P^{-}(b_{2}b_{3})\\\ v<\max(a_{2},a_{3})\leq
w\end{subarray}}\sum_{n_{1}\leq
x/(n_{2}a_{3}b_{3})}\mathrm{e}\Big{(}\frac{\bar{n}_{1}(a_{3}b_{3}\overline{(a_{3}b_{3})}_{n_{2}}-n_{2}\overline{(2n_{2})}_{a_{3}b_{3}})}{n_{2}a_{3}b_{3}}\Big{)}.$
(23)

Unfortunately, equation (4) is not sufficient here. Since $a_{3}$ is not too
small and $b_{3}$ is not too big, the denominator has three factors not too
small and we can apply the recent work of Wu and Xi [20] on the $q$-analog of
the van der Corput method. Such an approach was initiated by Heath–Brown [7]
and developed by Graham and Ringrose [6], and more recently by Irving [13, 14]
and by Wu and Xi [20], where the arithmetic exponent pairs are obtained when
the denominator has good factorization properties. As in the proof of Theorem
2, we denote by $n^{\sharp}$ and $n^{\flat}$ the squarefull and squarefree
parts of the integer $n$; and we write

$\mathrm{e}\Big{(}\frac{\bar{n}_{1}(a_{3}b_{3}\overline{(a_{3}b_{3})}_{n_{2}}-n_{2}\overline{(2n_{2})}_{a_{3}b_{3}})}{n_{2}a_{3}b_{3}}\Big{)}=K(n_{1})W(n_{1}),$

with

$\begin{split}K(n_{1})&=\mathrm{e}\Big{(}\frac{\bar{n}_{1}\overline{(n_{2}a_{3}b_{3})^{\sharp}}[a_{3}b_{3}\overline{(a_{3}b_{3})}_{n_{2}}-n_{2}\overline{(2n_{2})}_{a_{3}b_{3}}]}{(n_{2}a_{3}b_{3})^{\flat}}\Big{)},\\\
W(n_{1})&=\mathrm{e}\Big{(}\frac{\bar{n}_{1}\overline{(n_{2}a_{3}b_{3})^{\flat}}[a_{3}b_{3}\overline{(a_{3}b_{3})}_{n_{2}}-n_{2}\overline{(2n_{2})}_{a_{3}b_{3}}]}{(n_{2}a_{3}b_{3})^{\sharp}}\Big{)}.\\\
\end{split}$

######  Lemma 8.

Uniformly for any integers $\alpha,A,N,\delta\in\mathbb{N}$,
$q=q_{1}q_{2}q_{3}$ squarefree integer such that $(\alpha\delta,q)=1$ and any
rational function $R$ with integer coefficients, we have

$\begin{split}\sum_{\begin{subarray}{c}{A<n\leq A+N}\\\
{(n,q)=1}\end{subarray}}\mathrm{e}\Big{(}\frac{\alpha\bar{n}}{q}+\frac{R(n)}{\delta}\Big{)}&\ll
N^{1/2}q_{3}^{1/2}+N^{3/4}q_{2}^{1/4}\\\
&\qquad{}+N^{3/4}q_{1}^{1/8}\delta^{1/4}3^{\omega(q_{1})}\Big{(}\frac{N}{q_{1}}+\log(q_{1}\delta)\Big{)}^{1/4}.\\\
\end{split}$

We emphasize that the implicit constant above is absolute, and in particular
does not depend on $R$: we handle the contribution of this term $R(n)/\delta$
quite trivially. In our application, the denominator $\delta$ is small, so the
prospects for cancellation are modest in any case.

We prove Lemma 8 in the next section; assuming the lemma for the moment, we
can complete the proof of Theorem 3. We apply Lemma 8 to the inner sum in
equation (23) with $q=n_{2}^{\flat}b_{3}^{\flat}a_{3}^{\flat}$ and
$\delta=n_{2}^{\sharp}b_{3}^{\sharp}a_{3}^{\sharp}$, where
$N=x/(n_{2}a_{3}b_{3})$. After doing so, by positivity we may again assume
that $v<a_{3}\leq w$ (the bound when $v<a_{2}\leq w$ is exactly the same) and
ignore all restrictions upon $n_{2}$. We obtain

$S_{7}(x)\ll\sum_{n_{2}\in I}\sum_{\begin{subarray}{c}{a_{3}b_{3}\in I}\\\
{v<a_{3}\leq
w}\end{subarray}}\Big{\\{}\sqrt{\frac{x}{n_{2}a_{3}b_{3}}}\sqrt{a_{3}^{\flat}}+\Big{(}\frac{x}{n_{2}a_{3}b_{3}}\Big{)}^{3/4}(b_{3}^{\flat})^{1/4}\\\
+\Big{(}\frac{x}{n_{2}a_{3}b_{3}}\Big{)}^{3/4}(n_{2}^{\flat})^{1/8}(n_{2}^{\sharp}a_{3}^{\sharp}b_{3}^{\sharp})^{1/4}3^{\omega(n_{2}^{\flat})}\Big{(}\frac{x}{n_{2}n_{2}^{\flat}a_{3}b_{3}}+\log
x\Big{)}^{1/4}\Big{\\}}.$

We now have to compute all the different sums:

$S_{7}(x)\ll\sqrt{x}y_{2}\sqrt{w}(\log
z)^{-1}+(xy_{2})^{3/4}v^{-1/4}+x^{23/24+\varepsilon}.$ (24)

Theorem 3 now follows from the estimates (20), (22), and (24) upon taking
$w=x^{1/24}$, $v=(\log x)^{4B}$, $B=10$, and $A=30$, for example.

##  6 Short exponential sums

###  6.1 Proof of Lemma 8

In this section we prove Lemma 8, which will complete the proof of Theorem 3.
This lemma is in fact a variant of a particular case of a result of Wu and Xi
[20, Theorem 3.1 and Proposition 3.2]. While we do not need to introduce
significant new ideas, the results of [20] cannot be applied directly in our
context because we need a more precise version of the function
$N^{\varepsilon}$ in our error bounds. Careful attention to their paper
reveals that it is possible to adapt some arguments to replace this
$N^{\varepsilon}$ by a quantity of the type $C^{\omega(q_{1})}(\log
N)^{\alpha}$. In many circumstances such a refinement is not necessary, but
for us it is important due to the very restricted range of the factor $a_{3}$.

For brevity we will write $J={}]A,A+N]$, $W(n)=\mathrm{e}(R(n)/\delta)$, and

$E(J)=\sum_{\begin{subarray}{c}{n\in
J}\end{subarray}}\mathrm{e}\Big{(}\frac{\alpha\bar{n}}{q}\Big{)}W(n)$

for the sum to be estimated. We begin by remarking that we may assume that
$q_{2}<N$ and $q_{3}<N$, for otherwise the lemma is trivial. For any function
$\Psi$ and any $h\in\mathbb{Z}$ we define

$\Delta_{h}(\Psi)(n)=\Psi(x)\overline{\Psi(x+h)}.$

######  Lemma 9.

Let $q=q_{1}q_{2}$ with $(q_{1},q_{2})=1$, $J={}]A,A+N]$ an interval and
$\Psi_{i}\colon\mathbb{Z}/q_{i}\mathbb{Z}\rightarrow\mathbb{C}$. Then for
$1\leq L\leq N/q_{2}$, we have

$\Big{|}\sum_{n\in
J}\Psi_{1}(n)\Psi_{2}(n)\Big{|}^{2}\ll\|\Psi_{2}\|_{\infty}\Big{(}L^{-1}N^{2}+L^{-1}N\sum_{0<|\ell|\leq
L}\Big{|}\sum_{\begin{subarray}{c}{n\in J}\\\ {n+\ell q_{2}\in
J}\end{subarray}}\Delta_{\ell q_{2}}(\Psi_{1})(n)\Big{|}\Big{)}.$

This formula, which Wu and Xi call an $A$-process by analogy with the
$A$-process of the classical van der Corput method, follows from the proof of
[20, Lemma 3.1].

We apply this lemma with

$\psi_{1}(n)=\mathrm{e}\Big{(}\frac{\alpha\bar{q}_{3}\bar{n}}{q_{1}q_{2}}\Big{)}W(n),\quad\psi_{2}(n)=\mathrm{e}\Big{(}\frac{\alpha\overline{q_{1}q_{2}}\bar{n}}{q_{3}}\Big{)}.$

Writing $L_{3}=[N/q_{3}]$ (which is at least $1$), this gives (see also the
beginning of the proof of [20, Theorem 3.1])

$|E(J)|^{2}\ll L_{3}^{-1}N^{2}+L_{3}^{-1}N\sum_{0<|\ell_{3}|\leq
L_{3}}|U(\ell_{3})|,$ (25)

with

$U(\ell_{3})=\sum_{n\in
J(\ell_{3})}\mathrm{e}\Big{(}\frac{\alpha\bar{q}_{3}(\bar{n}-\overline{(n+\ell_{3}q_{3})})}{q_{1}q_{2}}\Big{)}W(n)\overline{W(n+\ell_{3}q_{3})}$

where $J(\ell_{3})$ is some interval contained in $J$. Note that we may write
$U(\ell_{3})=\sum_{n\in J}\Psi_{3}(n)\Psi_{4}(n)$ where

$\begin{split}\psi_{3}(n)&=\mathrm{e}\Big{(}\frac{\alpha\bar{q}_{2}\bar{q}_{3}(\bar{n}-\overline{(n+\ell_{3}q_{3})})}{q_{1}}\Big{)}W(n)\overline{W(n+\ell_{3}q_{3})}{\bf
1}_{J(\ell_{3})}(n),\\\
\psi_{4}(n)&=\mathrm{e}\Big{(}\frac{\alpha\bar{q}_{1}\bar{q}_{3}(\bar{n}-\overline{(n+\ell_{3}q_{3})})}{q_{2}}\Big{)},\end{split}$
(26)

where ${\bf 1}_{J(\ell_{3})}$ is the indicator function of $J(\ell_{3})$. We
again apply Lemma 9 to each $U(\ell_{3})$, writing $L_{2}=[N/q_{2}]$ (which
again is at least $1$); we have written $\psi_{3}(n)$ as in equation (26) so
as to make this choice of $L_{2}$ valid even when the length of $J(\ell_{3})$
is much smaller than $N$. We obtain

$|U(\ell_{3})|^{2}\ll L_{2}^{-1}N^{2}+L_{2}^{-1}N\sum_{0<|\ell_{2}|\leq
L_{2}}|U(\ell_{2},\ell_{3})|,$ (27)

with now

$U(\ell_{2},\ell_{3})=\sum_{n\in
J(\ell_{2},\ell_{3})}\mathrm{e}\Big{(}\frac{F(n)}{q_{1}}\Big{)}\widetilde{W}(n),$

where $J(\ell_{2},\ell_{3})$ is some interval contained in $J(\ell_{3})$, and

$\displaystyle F(n)$
$\displaystyle=\alpha\overline{q_{2}q_{3}}\big{[}\bar{n}-\overline{(n+\ell_{3}q_{3})}-\overline{(n+\ell_{2}q_{2})}+\overline{(n+\ell_{2}q_{2}+\ell_{3}q_{3})}\,\big{]},$
(28) $\displaystyle\widetilde{W}(n)$
$\displaystyle=W(n)\overline{W(n+\ell_{3}q_{3})}\overline{W(n+\ell_{2}q_{2})}W(n+\ell_{2}q_{2}+\ell_{3}q_{3}).$

Then we complete the above sum over $n\in J(\ell_{2},\ell_{3})$:

$\begin{split}U(\ell_{2},\ell_{3})&=\frac{1}{q_{1}\delta}\sum_{a=1}^{q_{1}\delta}\mathrm{e}\Big{(}\frac{F(a)}{q_{1}}\Big{)}\widetilde{W}(a)\sum_{h=1}^{q_{1}\delta}\sum_{n\in
J(\ell_{2},\ell_{3})}\mathrm{e}\Big{(}\frac{h(a-n)}{q_{1}\delta}\Big{)}\\\
&\ll\frac{N}{q_{1}\delta}\Big{|}\sum_{a=1}^{q_{1}\delta}\mathrm{e}\Big{(}\frac{F(a)}{q_{1}}\Big{)}\widetilde{W}(a)\Big{|}+\sum_{1\leq
h<q_{1}\delta}\frac{1}{h}\sum_{a=1}^{q_{1}\delta}\mathrm{e}\Big{(}\frac{F(a)}{q_{1}}\Big{)}\widetilde{W}(a)\mathrm{e}\Big{(}\frac{ha}{q_{1}\delta}\Big{)}.\end{split}$

We denote by $\Sigma_{a}(h)$ the inner sum on $a$ in the second term and
perform the same manipulations as for the sums $S_{a}$ in the proof of Theorem
2, resulting in

$\begin{split}\Sigma_{a}(h)&=\sum_{a=1}^{q_{1}\delta}\mathrm{e}\Big{(}\frac{F(a)}{q_{1}}\Big{)}\widetilde{W}(a)\mathrm{e}\Big{(}\frac{ha}{q_{1}\delta}\Big{)}\\\
&=\sum_{u=1}^{\delta}\widetilde{W}(q_{1}u)\mathrm{e}\Big{(}\frac{hu}{\delta}\Big{)}\prod_{p|q_{1}}\sum_{v=1}^{p}\mathrm{e}\Big{(}\frac{F(v\delta
q_{1}/p)+hv}{p}\Big{)}.\end{split}$ (29)

The function $F$ in equation (28) can be rewritten in the following way, with
$\lambda=\alpha\overline{q_{2}q_{3}}$:

$F(n)=\frac{\lambda
G(n)}{n(n+\ell_{2}q_{2})(n+\ell_{3}q_{3})(n+\ell_{2}q_{2}+\ell_{3}q_{3})},$

where $G(n)$ is a polynomial with constant term
$\ell_{2}q_{2}\ell_{3}q_{3}(\ell_{2}q_{2}+\ell_{3}q_{3})$ (the exception being
when $p\mid(\ell_{2}q_{2}+\ell_{3}q_{3})$, in which case we actually have
$F(n)=2\lambda\ell_{2}q_{2}\ell_{3}q_{3}/(n(n+\ell_{2}q_{2})(n+\ell_{3}q_{3}))$).
If $p\nmid\ell_{2}\ell_{3}$, the function $F(v\delta q_{1}/p)+hv$ of $v$ has
at most $5$ poles, each pole being simple (including the pole at $\infty$);
this is most clearly seen from the definition (28) of $F(n)$. Then by Lemma 7
we have

$\Big{|}\sum_{v=1}^{p}\mathrm{e}\Big{(}\frac{F(v\delta
q_{1}/p)+hv}{p}\Big{)}\Big{|}\leq 10\sqrt{p}$

when $p\nmid\ell_{2}\ell_{3}$. We deduce from equation (29) that

$|\Sigma_{a}(h)|\leq\sum_{u=1}^{\delta}\prod_{\begin{subarray}{c}p\mid
q_{1}\\\
p\nmid\ell_{2}\ell_{3}\end{subarray}}10\sqrt{p}\prod_{\begin{subarray}{c}p\mid
q_{1}\\\ p\mid\ell_{2}\ell_{3}\end{subarray}}p\leq
10^{\omega(q_{1})}\delta\sqrt{q_{1}}(q_{1},\ell_{2}\ell_{3})^{1/2}.$

Then

$\sum_{\ell_{2}\leq
L_{2}}|U(\ell_{2},\ell_{3})|\ll\delta\sqrt{q_{1}}\Big{(}\log
q_{1}+\frac{N}{q_{1}}\Big{)}10^{\omega(q_{1})}\sum_{\ell_{2}\leq
L_{2}}(q_{1},\ell_{2}\ell_{3})^{1/2}.$ (30)

For the sum on $\ell_{2}$ we have for any $\ell_{3}\leq L_{3}$:

$\sum_{\ell_{2}\leq L_{2}}(q_{1},\ell_{2}\ell_{3})^{1/2}\leq\sum_{d\mid
q_{1}}\sqrt{d}(\ell_{3},q_{1}/d)^{1/2}\sum_{\ell_{2}\leq
L_{2}/d}1\ll\tau(q_{1})L_{2}(q_{1},\ell_{3})^{1/2}.$ (31)

Inserting this bound into equation (30) and tracing the results back through
equations (27) and (25) results in

$E(J)\ll
NL_{3}^{-1/2}+NL_{2}^{-1/4}+N^{3/4}\Big{(}\frac{N}{q_{1}\delta}+\log(q_{1}\delta)\Big{)}^{1/4}q_{1}^{1/8}\delta^{1/4}10^{\omega(q_{1})/4}\tau(q_{1})^{3/4}.$

It remains to replace $L_{2}$ by $[N/q_{2}]$ and $L_{3}$ by $[N/q_{3}]$, and
to observe that

$10^{\omega(q_{1})/4}\tau(q_{1})^{3/4}=80^{\omega(q_{1})/4}\leq
3^{\omega(q_{1})},$

to finish the proof of Lemma 8.

###  6.2 Generalization of Lemma 8, the $A^{k}$-process

In this section, we indicate how to iterate the ideas of the proof of Lemma 8
to obtain bounds for short exponential sums whose denominator can be
decomposed into $k+1$ factors. This generalization relies on techniques from
two important papers of Irving [13, 14]; again, our contribution here consists
mainly in replacing a factor of $N^{\varepsilon}$ by a more precise error
term.

Essentially, we would like to apply Lemma 9 consecutively $k$ times. Irving
has given a precise formulation of this iteration; to enounce his result, we
need to introduce some notation corresponding to the iterates of the
$\Delta_{h}(\Psi)$ used in the previous section. For any complex-valued
function $f$, define

$f(n;h_{1},\ldots,h_{k})=\prod_{S\subset\\{1,\ldots,k\\}}f\big{(}n+\sum_{s\in
S}h_{s}\big{)}^{\sigma(S)},$

where $\sigma(S)$ denotes that the complex conjugate is taken when $\\#S$ is
odd. With this notation, we may quote [14, Lemma 2.2]:

######  Lemma 10.

Let $k\in\mathbb{N}$ and $q_{0},\dots,q_{k}\in\mathbb{N}$. For each $0\leq
i\leq k$, let $f_{i}\colon\mathbb{Z}\rightarrow\mathbb{C}$ be a function with
period $q_{i}$ such that $f_{i}(n)\ll 1$. Set $q=q_{0}\cdots q_{k}$ and
$f(n)=\prod_{i=0}^{k}f_{i}(n)$. If $I$ is any interval of length at most $N$,
then

$\Big{|}\sum_{n\in
I}f(n)\Big{|}^{2^{k}}\ll_{k}\sum_{j=1}^{k}N^{{2^{k}}-2^{k-j}}q_{k-j+1}^{2^{k-j}}\\\
+N^{2^{k}-k-1}\frac{q}{q_{0}}\sum_{0<|h_{1}|\leq
N/q_{1}}\cdots\sum_{0<|h_{k}|\leq N/q_{k}}\Big{|}\sum_{n\in
I(h_{1},\ldots,h_{k})}f_{0}(n;q_{1}h_{1},\ldots,q_{k}h_{k})\Big{|},$ (32)

where $I(h_{1},\ldots,h_{k})$ is a subinterval of $I$.

We also quote the following combinatorial lemma [13, Lemma 4.5]:

######  Lemma 11.

Let $p\geq 3$ be prime and $h_{1},\ldots,h_{k}\in\mathbb{F}_{p}$. Suppose that
for every $b\in\mathbb{F}_{p}$, the number of subsets
$S\subset\\{1,\dots,k\\}$ with $b=\sum_{s\in S}h_{s}$ is even. Then some
$h_{i}$ must equal $0$.

We are now prepared to establish our generalization of Lemma 8.

######  Lemma 12.

Uniformly for any integers $\alpha,A,N$, any positive integers $\delta,k$, any
positive integers $q_{0},\cdots,q_{k}$ such that $q=q_{0}\cdots q_{k}$ is
squarefree and coprime to $\alpha\delta$, and any rational function $R$ with
integer coefficients,

$\begin{split}\sum_{\begin{subarray}{c}{A<n\leq A+N}\\\
{(n,q)=1}\end{subarray}}&\mathrm{e}\Big{(}\frac{\alpha\bar{n}}{q}+\frac{R(n)}{\delta}\Big{)}\ll_{k}\sum_{j=1}^{k}N^{1-1/2^{j}}q_{j}^{1/2^{j}}\\\
&+N^{1-1/2^{k}}q_{0}^{1/2^{k+1}}\delta^{1/2^{k}}(2^{k+2}+4)^{\omega(q_{0})/2^{k}}\Big{(}\Big{(}\frac{N}{q_{0}}\Big{)}^{1/2^{k}}+(\log
q)^{1/2^{k}}\Big{)}.\end{split}$

###### Proof.

We apply Lemma 10 with

$f(n)=\mathrm{e}\Big{(}\frac{\alpha\bar{n}}{q}\Big{)}W(n)=\mathrm{e}\Big{(}\frac{\alpha\bar{n}\overline{(q/q_{0})}}{q_{0}}+\frac{R(n)}{\delta}\Big{)}\prod_{i=1}^{k}\mathrm{e}\Big{(}\frac{\alpha\bar{n}\overline{(q/q_{i})}}{q_{i}}\Big{)},$

where as in the previous section $W(n)=\mathrm{e}(R(n)/\delta)$. Our desire at
this point is to apply Weil’s bound to the sums over $n$ that arise from
equation (32). After the same manipulations as in the proof of Lemma 8, the
analogue of equation (29) is now

$\begin{split}\Sigma_{a}(m)&=\sum_{u=1}^{\delta}W(aq_{0};q_{1}h_{1},\ldots,q_{k}h_{k})\mathrm{e}\Big{(}\frac{mu}{\delta}\Big{)}\\\
&\times\prod_{p|q_{0}}\sum_{v=1}^{p}\mathrm{e}\Big{(}\frac{mv+\sum_{S\subset\\{1,\ldots,k\\}}(-1)^{\\#S}\alpha\overline{(v\delta
q_{0}/p+\sum_{s\in S}h_{s}q_{s})}}{p}\Big{)}.\\\ \end{split}$ (33)

In order to apply Weil’s bound (Lemma 7), we need to confirm that the argument
of the exponential is nonconstant modulo $p$ (even if $p\mid m$).

Note that the numerator in equation (33) can be written as

$mv+\sum_{S\subset\\{1,\ldots,k\\}}(-1)^{\\#S}\alpha\overline{(v\delta
q_{0}/p+\sum_{s\in S}h_{s}q_{s})}\\\ =mv+\alpha\sum_{t{\text{\rm\
(mod~{}$p$)}}}\overline{(v\delta
q_{0}/p+t)}\sum_{\begin{subarray}{c}S\subset\\{1,\ldots,k\\}\\\ \sum_{s\in
S}h_{s}q_{s}\equiv t{\text{\rm\ (mod~{}$p$)}}\end{subarray}}(-1)^{\\#S}$ (34)

When $p\nmid h_{1}\cdots h_{k}$ (so that indeed $p\nmid h_{1}q_{1}\cdots
h_{s}q_{s}$), Lemma 11 implies that at least one of the inner sums on the
right-hand side of equation (34) has an odd number of terms, and in particular
(by considering its parity) is nonzero. In particular, the numerator in
equation (33) is nonconstant, and thus Lemma 7 can be applied.

The number of poles of this numerator is at most $2^{k}+1$. When $p\nmid
h_{1}\cdots h_{k}$, Lemma 7 implies that the corresponding sum is less than
$2(2^{k}+1)\sqrt{p}$. We deduce that
$\Sigma_{a}(m)\ll\delta(2^{k+1}+2)^{\omega(q_{0})}\sqrt{q_{0}}(q_{0},h_{1}\cdots
h_{k})^{1/2}$. The proof concludes with quite similar computations to those in
the proof of Lemma 8, with the function $\tau(q_{1})$ from equation (31)
replaced by $\sum_{d_{1}\cdots d_{k}\mid q_{0}}1/\sqrt{d_{1}\cdots d_{k}}\ll
2^{\omega(q_{0})}$. ∎

##  7 Product of $k$ linear factors

This section is devoted to the proof of Theorem 4. We will skip some details
when the arguments are similar to the previous proofs. All implicit constants
in this section may depend on $f$ and $h$.

Define $A=\prod_{1\leq i<j\leq k}(a_{i}b_{j}-a_{j}b_{i})\prod_{i=1}^{k}a_{i}$.
The first step follows the beginning of the proof of Theorem 1 in Section 3.2.
However, since $f$ has more than two linear factors, the discussions related
to the greatest common divisor of $A$, $h$, and the denominators $n$ are more
delicate. This is why in our splitting analogous of (10), the summation of
$\delta$ will be for $\delta\mid(hA)^{\infty}$ instead of
$\delta\mid(h,A)^{\infty}$. We keep the notations
$S(f,x,h)=S_{>}(x,h)+S_{\leq}(x,h)$, where in $S_{>}(x,h)$ the parameter
$\delta\mid(hA)^{\infty}$ exceeds $B$, but now with $B=(\log x)^{10k}$ instead
of $x^{1/5-\varepsilon}$. We bound $S_{>}(x,h)$ by $x(\log
x)^{k-1}B^{-1+\varepsilon}$ with $\varepsilon>0$ arbitrarily small as in
equation (11) (indeed $\varepsilon=1/10$ will suffice for us).

For $S_{\leq}(x,h)$, however, an analogous version of equation (12) is not
sufficient. This is due to the fact that a trivial summation on $\delta<B$
would bring a factor $B>(\log x)^{k}$ into our error terms, and we can win
only a factor $(\log x)^{4}$ in an error term (denoted by
$T_{5}^{(1)}(r,\delta)$ later in this section) arising from certain
denominators $n$ that are the product of several divisors of the same size.

Nevertheless, we still begin by applying the Chinese remainder theorem as in
Section 3.2:

$S_{\leq}(f,x,h)=\sum_{\begin{subarray}{c}{\delta\mid(Ah)^{\infty}}\\\
{\delta\leq B}\end{subarray}}\sum_{\begin{subarray}{c}{0\leq r<\delta}\\\
{f(r)\equiv 0{\text{\rm\ (mod~{}$\delta$)}}}\end{subarray}}T(r,\delta),$ (35)

with now

$T(r,\delta)=\sum_{\begin{subarray}{c}{n\leq x/\delta}\\\
{(n,Ah)=1}\end{subarray}}\sum_{\begin{subarray}{c}{0\leq r_{1}<n}\\\
{f(r_{1}\delta)\equiv 0{\text{\rm\
(mod~{}$n$)}}}\end{subarray}}\mathrm{e}\Big{(}\frac{hr_{1}}{n}+\frac{hr\bar{n}}{\delta}\Big{)}.$

The number of roots $r$ in equation (35) is $O(A^{\omega(\delta)})$ (see
Nagell [17, p. 90, Theorem 54] for an even more precise result) and thus
$O(1)$ with our conventions for implicit constants. Since our polynomial $f$
is the product of $k$ linear functions, generalizations of Lemma 3 and
equation (6) allow us to write

$\begin{split}T(r,\delta)&=\sum_{\begin{subarray}{c}{m_{1}\cdots m_{k}\leq
x/\delta}\\\ {(m_{1}\cdots
m_{k},Ah)=1}\end{subarray}}\sum_{\begin{subarray}{c}{0\leq r_{1}<m_{1}\cdots
m_{k}}\\\ {m_{i}\mid f_{i}(r_{1}\delta)\,(1\leq i\leq
k)}\end{subarray}}\mathrm{e}\Big{(}\frac{hr_{1}}{m_{1}\cdots
m_{k}}+\frac{hr\overline{m_{1}\cdots m_{k}}}{\delta}\Big{)},\end{split}$

where $(m_{i},m_{j})=1$ for all $1\leq i<j\leq k$ and

$r_{1}\equiv-\bar{\delta}\sum_{i=1}^{k}\bar{a}_{i}b_{i}\prod_{\begin{subarray}{c}{j=1}\\\
{j\not=i}\\\ \end{subarray}}m_{j}\overline{(\prod_{\begin{subarray}{c}{j=1}\\\
{j\not=i}\\\ \end{subarray}}m_{j}})_{m_{i}}{\text{\rm\ (mod~{}$m_{1}\cdots
m_{k}$)}},$

so that

$\mathrm{e}\Big{(}\frac{hr_{1}}{m_{1}\cdots
m_{k}}\Big{)}=\prod_{i=1}^{k}\mathrm{e}\Big{(}\frac{-h\bar{\delta}\bar{a}_{i}b_{i}\overline{\prod_{\begin{subarray}{c}{j=1}\\\
{j\not=i}\\\ \end{subarray}}m_{j}}}{m_{i}}\Big{)}.$ (36)

We set $y=x^{1/3}(\log x)^{10k}$ and write
$T(r,\delta)=T_{1}(r,\delta)+T_{2}(r,\delta)$, where the sum
$T_{2}(\alpha,\delta)$ contains precisely those summands for which
$\max\\{m_{1},\ldots,m_{k}\\}>y$.

We decompose $T_{2}(r,\delta)=S_{1}+\cdots+S_{k}$ into $k$ sums, where each
$S_{i}$ is defined by the conditions $m_{i}>y$ and $m_{j}\leq y$ for $j<i$. In
each $S_{i}$, we use the inversion formula (6) and apply Lemma 1 as in the
proof of Theorem 3. This yields an asymptotic formula of the shape
$S_{i}=xC_{i}(f,h,\delta)+O((x/y)^{3/2}\sqrt{\delta}(\log x)^{k})$ for some
constants $C_{i}(f,h,\delta)$ similar to the constants found in Section 3.2 in
the proof of Theorem 1.

These contributions comprise the main term in Theorem 4 when $k=3$ and $k=4$.
It remains to find an upper bound for $T_{1}(r,\delta)$. This upper bound will
be $o(x)$ only for $k=3$ and $k=4$, which allows for our asymptotic formula in
those cases; for $k\geq 5$ it provides only a nontrivial upper bound as stated
in Theorem 4.

We split the sum $T_{1}(r,\delta)$ into $k!$ subsums according to the ordering
of the $m_{i}$. Let $T_{1}^{(1)}(r,\delta)$ denote the subsum of
$T_{1}(r,\delta)$ with the additional condition that $m_{1}\geq
m_{2}\geq\cdots\geq m_{k}$; the estimate we find for this subsum will hold for
all $k!$ subsums. We would like to deal with $T_{1}^{(1)}(r,\delta)$ simply by
applying Lemma 12; however, this lemma is not efficient enough when $m_{3}$ is
close to $m_{1}$. Consequently, we make one more splitting
$T_{1}^{(1)}(r,\delta)=T_{3}^{(1)}(r,\delta)+T_{4}^{(1)}(r,\delta)$, where
$T_{3}^{(1)}(r,\delta)$ consists of the terms for which $m_{3}\leq m_{1}(\log
x)^{-k4^{k}}$.

Concentrating first on $T_{3}^{(1)}(r,\delta)$, we do dyadic splittings in all
$k$ variables, writing $T_{3}^{(1)}(r,\delta)$ as $O(\log^{k}x)$ subsums
$S(M_{1},\ldots,M_{k})$ that are restricted to $m_{i}$ satisfying
$M_{i}<m_{i}\leq 2M_{i}$ for all $1\leq i\leq k$; here the bounds $M_{i}$ are
powers of $2$, satisfying $2^{k}M_{1}\cdots M_{k}\leq x$, such that $M_{1}\leq
y$ while $2M_{i}\leq y$ for $2\leq i\leq k$. The ordering of the $m_{i}$ also
implies that $M_{1}\geq M_{2}\geq\cdots\geq M_{k}$.

By the inversion formula (6), we can eliminate the variable $m_{1}$ in the
denominator in equation (36):

$\mathrm{e}\Big{(}{-}\frac{hb_{1}\overline{a_{1}\delta m_{2}\cdots
m_{k}}}{m_{1}}\Big{)}=\mathrm{e}\Big{(}\frac{hb_{1}\overline{m_{1}}}{a_{1}\delta
m_{2}\cdots m_{k}}\Big{)}\mathrm{e}\Big{(}\frac{hb_{1}}{a_{1}\delta
m_{1}\ldots m_{k}}\Big{)},$

The second exponential term above is $1+O(1/\delta M_{1}\cdots M_{k})$ and can
be replaced by $1$ with an admissible error. Thus we have, for some $\lambda$
depending on $m_{2},\ldots,m_{k},\delta,r,f$ but not on $m_{1}$,

$S(M_{1},\ldots,M_{k})\\\ =\sum_{\begin{subarray}{c}{M_{i}<m_{i}\leq
2M_{i}}\,(2\leq i\leq k)\\\ (m_{2}\cdots
m_{k},Ah)=1\end{subarray}}\sum_{\begin{subarray}{c}{M_{1}<m_{1}\leq 2M_{1}}\\\
{\max\\{m_{2},\cdots,m_{k}\\}\leq m_{1}\leq x/(m_{1}\cdots m_{2})}\\\
{(m_{1},Ahm_{2}\cdots
m_{k})=1}\end{subarray}}\mathrm{e}\Big{(}\frac{\lambda\overline{m_{1}}}{a_{1}\delta
m_{2}\cdots m_{k}}\Big{)}+E,$

where $E$ is a sufficiently small error term. Next we separate the squarefree
and the squarefull parts of this denominator. With the same notation as in the
proof of Theorem 3, we obtain a formula of the shape

$\mathrm{e}\Big{(}\frac{\lambda\overline{m_{1}}}{a_{1}m_{2}\cdots
m_{k}}\Big{)}=\mathrm{e}\Big{(}\frac{\alpha\overline{m_{1}}}{(a_{1}m_{2}\cdots
m_{k})^{\flat}}+\frac{R(n)}{\delta(a_{1}m_{2}\cdots m_{k})^{\sharp}}\Big{)}.$

Writing $q^{\sharp}=(a_{1}m_{2}\cdots m_{k})^{\sharp}$, we find that Lemma 12
gives the estimate

$S(M_{1},\ldots,M_{k})\ll x\sum_{j=3}^{k}(M_{j}/M_{1})^{1/2^{j-2}}\\\
+x(\delta q^{\sharp})^{1/2^{k}}(\log x)^{2^{k}+3}\big{(}M_{2}^{-1/2^{k}}+(\log
x)^{1/2^{k}}M_{2}^{1/2^{k+1}}M_{1}^{-1/2^{k}}\big{)}.$

Since $M_{k}\leq\cdots\leq M_{3}\leq M_{1}(\log x)^{-k4^{k}}$, this estimate
saves enough powers of $\log x$ to compensate for the number of subsums and
the summation over $\delta$; we obtain a bound for $T_{3}^{(1)}(r,\delta)$
that is admissible for Theorem 4.

It remains to handle $T_{4}^{(1)}(r,\delta)$, where a direct application of
Lemma 12 is not sufficient. We will proceed as in the sum $S_{4}(x)$ in
Section 5.2. Recalling that $m_{1}\geq m_{2}\geq\cdots\geq m_{k}$, we let
$\ell\in\\{2,\ldots,k\\}$ be the largest index such that $m_{\ell}>m_{1}(\log
x)^{-k4^{k}}$. For $2\leq i\leq\ell$, we factor $m_{i}=c_{i}d_{i}$ with
$P^{+}(c_{i})\leq z<P^{-}(d_{i})$ where $z=\exp(\log x/(800k\log\log x))$. We
also introduce the parameters $w=x^{1/(50k)}$ and $v=(\log x)^{10k4^{k}}$.

Let $T_{6}^{(1)}(r,\delta)$ be the analogue of the sum $S_{6}(x)$ in Section
5.2, which is the contribution of the $(m_{1},\ldots,m_{k})$ such that
$c_{i}>w$ for some $i\in\\{2,\ldots,\ell\\}$. With a computation similar to
the one in equation (22), we find:

$T_{6}^{(1)}(r,\delta)\ll\frac{x(\log x)^{k}}{w^{1/4}}+x2^{-{\log w}/(2\log
z)}(\log x)^{k}\ll x{(\log x)^{k-8\log 2}},$

where the final estimate is sufficient since $8\log 2>5$.

We next examine $T_{7}^{(1)}(r,\delta)$, the analogue of $S_{7}(x)$ in Section
5.2, corresponding to the case where there is at most one
$i\in\\{2,\ldots,\ell\\}$ with $c_{i}\leq v$. Without lost of generality we
can suppose that $c_{2}\leq v$ and $c_{i}\in[v,w]$ for all $3\leq i\leq\ell$.
We introduce some dyadic splittings, similar to those in our treatment of
$T^{(1)}_{3}(r,\delta)$, of $T_{7}^{(1)}(r,\delta)$ into $O((\log x)^{k})$
sums $S_{7}(M_{1},\ldots,M_{k})$ with $M_{i}<c_{i}d_{i}\leq 2M_{i}$ for $2\leq
i\leq\ell$ and $M_{i}<m_{i}\leq 2M_{i}$ for
$i\in\\{1\\}\cup\\{\ell+1,\ldots,k\\}$. We apply Lemma 12 with $k$ replaced by
$k+\ell-4$ and with the parameters

$\displaystyle N$ $\displaystyle=2M_{1},$ $\displaystyle q_{0}$
$\displaystyle=c_{2}d_{2},$ $\displaystyle q_{1}$
$\displaystyle=d_{3},\,q_{2}=d_{4},\,\ldots,\,q_{\ell-2}=d_{\ell},$
$\displaystyle q_{\ell-1}$
$\displaystyle=m_{\ell+1},\,q_{\ell}=m_{\ell+2},\,\ldots,\,q_{k-2}=m_{k},$
$\displaystyle q_{k-1}$
$\displaystyle=c_{3},\,q_{k}=c_{4},\,\dots,\,q_{k+\ell-4}=c_{\ell}.$

With the notations $q^{\sharp}=(a_{1}m_{2}\cdots m_{k})^{\sharp}$ and
$k_{1}=k+\ell-4$, Lemma 12 gives

$\begin{split}S_{7}&(M_{1},\ldots,M_{k})\\\
&=\mathop{\sum\nolimits^{*\\!\\!}}_{m_{2},\ldots,m_{k}}\bigg{[}\sum_{j=1}^{\ell-2}M_{1}^{1-1/2^{j}}d_{j+2}^{1/2^{j}}+\sum_{j=\ell-1}^{k-2}M_{1}^{1-1/2^{j}}m_{j+2}^{1/2^{j}}+\sum_{j=k-1}^{k+\ell-4}M_{1}^{1-1/2^{j}}c_{j-k+4}^{1/2^{j}}\\\
&\qquad{}+M_{1}^{1-1/2^{k_{1}}}M_{2}^{1/2^{k_{1}+1}}(\delta
q^{\sharp})^{1/2^{k_{1}}}(2^{k_{1}}+4)^{\omega(m_{2})/2^{k_{1}}}\bigg{(}\Big{(}\frac{M_{1}}{M_{2}}\Big{)}^{1/2^{k_{1}}}+(\log
x)^{1/2^{k_{1}}}\bigg{)}\bigg{]},\\\ \end{split}$

where the asterisk on the sum indicates that the $m_{j}$ and the $c_{j},d_{j}$
satisfy the previously indicated conditions. At this point, computations
analogous to those at the end of Section 5.2 give a bound for
$T_{7}^{(1)}(r,\delta)$ that is sufficiently small.

Finally, we examine $T_{5}^{(1)}(r,\delta)$, the analogue of $S_{5}(x)$ in
Section 5.2, corresponding to the case where $c_{i}\leq v$ for at least two
indices $i\in\\{2,\ldots,\ell\\}$. The estimation of this part of the sum is
where we fail to obtain an asymptotic formula for $S(f,x,h)$ when $k\geq 5$.

Without loss of generality we can suppose that $c_{2}\leq v$ and $c_{3}\leq
v$. If we define $I(m_{1})=[m_{1}/(\log x)^{k4^{k}},m_{1}]$, then

$T_{5}^{(1)}(r,\delta)\ll\sum_{m_{1}\leq y}\sum_{m_{5},\ldots,m_{k}\leq
m_{1}}\sum_{c_{2},c_{3}\leq v}\sum_{\begin{subarray}{c}{c_{2}d_{2}\in
I(m_{1})}\\\ {c_{3}d_{3}\in
I(m_{1})}\end{subarray}}\sum_{\begin{subarray}{c}{m_{4}\leq x/(\delta
m_{1}c_{2}d_{2}c_{3}d_{3}m_{5}\cdots m_{k})}\\\ {m_{4}\leq
m_{1}}\end{subarray}}1.$

(In this line, the sum over $m_{5},\ldots,m_{k}$ does not occur if $k=3$ or
$k=4$; in fact, the case $k=3$ is handled exactly in the same way as in the
estimation of $S_{5}(x)$ in Section 5.2.) We use equation (21) for the sum
over the sifted variables $d_{2}$, $d_{3}$, gaining an additional factor of
$(\log z)^{2}$ in the estimate:

$T_{5}^{(1)}(r,\delta)\ll\frac{x(\log\log x)^{2}(\log x)^{k-3}}{\delta(\log
z)^{2}}\ll x\delta^{-1}(\log\log x)^{4}(\log x)^{k-5}.$ (37)

Since the number of roots $r$ is bounded uniformly in $\delta$ and
$\sum_{\delta\mid(Ah)^{\infty}}\delta^{-1}\ll 1$, we see that the bound (37)
is sufficiently small. This completes the proof of Theorem 4.

## Acknowledgments

The authors are very grateful to Zhizhong Huang for all his remarks on a
preliminary version of this manuscript. We also express our deep gratitude to
the anonymous referee, both for a close and detailed reading of the manuscript
which substantially improved the final version, and for suggesting Theorem 4
and providing the outline of the proof. The second author was supported in
part by a Natural Sciences and Engineering Research Council of Canada
Discovery Grant.

## References

  * [1] A. Balog, V. Blomer, C. Dartyge, and G. Tenenbaum.  Friable values of binary forms.  Comment. Math. Helv., 87:639–667, 2012.
  * [2] V. A. Bykovski.  Spectral expansion of certain automorphic functions and its number-theoretical applications.  Proc. Steklov Inst. (LOMI), 134:15–33, 1984.
  * [3] C. Dartyge.  Le plus grand facteur premier de $n^{2}+1$ où $n$ est presque premier.  Acta Arithmetica, 76(3):199–226, 1996.
  * [4] P. Deligne.  Application de la formule des traces aux sommes trigonométriques, volume 569.  Lectures Notes in Math. Springer, 1977.
  * [5] W. Duke, J. B. Friedlander, and H. Iwaniec.  Equidistribution of roots of a quadratic congruence to prime moduli.  Annals of Math., 141:423–441, 1995.
  * [6] S.W. Graham and C. J. Ringrose.  Lower bounds for least quadratic nonresidues.  In Analytic number theory (Allerton Park, IL, 1989), 85:269–309, 1990.
  * [7] D. R. Heath-Brown.  Hybrid bounds for Dirichlet $L$-functions.  Invent. Math., 47:149–170, 1978.
  * [8] D. A. Hejhal.  Sur certaines séries de Dirichlet dont les pôles sont sur les lignes critiques.  C. R. Acad. Sci. Paris Sér. A, 287:383–385, 1978.
  * [9] C. Hooley.  An asymptotic formula in the theory of numbers.  Proc. London Math. Soc. (3), 7:396–413, 1957.
  * [10] C. Hooley.  On the number of divisors of quadratic polynomials.  Acta Mathematica, 110(1):97–114, 1963.
  * [11] C. Hooley.  On the distribution of the roots of polynomial congruences.  Mathematika, 11:39–49, 1964.
  * [12] C. Hooley.  On the greatest prime factor of a quadratic polynomial.  Acta Mathematica, 117:281–299, 1967.
  * [13] A. J. Irving.  The divisor function in arithmetic progressions to smooth moduli.  Int. Math. Res. Not. IMRN, 15:6675–6698, 2015.
  * [14] A. J. Irving.  Estimates for character sums and Dirichlet $l$-functions to smooth moduli.  Int. Math. Res. Not. IMRN, 15:4602–4633, 2016.
  * [15] G. Martin and S. Sitar.  Erdös Turán with a moving target, equidistribution of roots of reducible quadratics and diophantine quadruples.  Mathematika, 57:1–29, 2011.
  * [16] H. L. Montgomery and R. C. Vaughan.  Multiplicative number theory. I. Classical theory, volume 97 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 2007.
  * [17] T. Nagell.  An introduction to number theory.  Wiley, 1951.
  * [18] R. J. Lemke Oliver.  Almost-primes represented by quadratic polynomials.  Acta Arithmetica, 151:241–261, 2012.
  * [19] H. J. S. Smith.  Report on the Theory of Numbers, volume I.  Chelsea, 1965.
  * [20] J. Wu and P. Xi.  Arithmetic exponent pairs for algebraic trace functions and applications.  Preprint, arXiv:1603.07060.
  * [21] N. I. Zavorotny.  On the number of Divisors of a Quadratic Polynomial.  1984\.

[cecile] Cécile Dartyge
Institut Élie Cartan de Lorraine
BP 70239, 54506 Vandœuvre-lès-Nancy Cedex, France
cecile.dartygeuniv-lorrainefr
https://www.iecl.univ-lorraine.fr/ Cecile.Dartyge/ [greg] Greg Martin
Department of Mathematics
University of British Columbia
Room 121, 1984 Mathematics Road
Vancouver, BC, Canada V6T 1Z2
gergmathubcca
http://www.math.ubc.ca/ gerg/