2.1 Some bounds on Kloosterman sums

Let $\Re z$ denote the real part of a complex number  $z$ .

First we record the following explicit formula, see, for example, [Reference Iwaniec and Kowalski7, equation (12.39)].

Lemma 2.1. Let $q=p^{k}$ with $p$ being an odd prime and $k\geqslant 2$ , $k\in \mathbb{N}$ . Then for $\gcd (a,q)=1$ we have

$$\begin{eqnarray}{\mathcal{K}}(n,a;q)=\left\{\begin{array}{@{}ll@{}}\displaystyle 2\biggl(\frac{r}{p}\biggr)^{k}\Re \unicode[STIX]{x1D717}_{q}e\biggl(\frac{2r}{q}\biggr), & \text{if}~\biggl({\displaystyle \frac{na}{p}}\biggr)=1,\\ 0, & \text{if}~\biggl({\displaystyle \frac{na}{p}}\biggr)=-1,\end{array}\right.\end{eqnarray}$$

where $r$ is a solution of $r^{2}\equiv na\hspace{0.2em}{\rm mod}\hspace{0.2em}q$ , $(r/p)$ is the Legendre symbol, $\unicode[STIX]{x1D717}_{q}$ equals $1$ if $q\equiv 1\hspace{0.2em}{\rm mod}\hspace{0.2em}4$ and $i$ if $q\equiv 3\hspace{0.2em}{\rm mod}\hspace{0.2em}4$ .

Easy calculations show the following well-known fact (see also [Reference Liu, Shparlinski and Zhang14]).

One of our principal technical tools is the following estimate from [Reference Liu, Shparlinski and Zhang14] on the cancellations amongst Kloosterman sums.

Lemma 2.3. Let $q=p^{k}$ , $k\in \mathbb{N}$ be a power of an odd prime  $p$ . Then for any fixed constant $0<\unicode[STIX]{x1D706}<1$ and $q^{\unicode[STIX]{x1D706}}<N<q$ , there exist a constant $K_{0}(\unicode[STIX]{x1D706})$ depending only on $\unicode[STIX]{x1D706}$ and an absolute constant $c>0$ such that for any $k>K_{0}(\unicode[STIX]{x1D706})$ and $\unicode[STIX]{x1D70F}(\unicode[STIX]{x1D706})=c\unicode[STIX]{x1D706}^{3}$ we have

$$\begin{eqnarray}\mathop{\sum }_{1\leqslant n\leqslant N}{\mathcal{K}}(n,a;q)\ll _{\unicode[STIX]{x1D706}}Nq^{-\unicode[STIX]{x1D70F}(\unicode[STIX]{x1D706})}\end{eqnarray}$$

uniformly over odd primes $p$ and integers $a$ with $\gcd (a,p)=1$ , where the implied constant depends only on  $\unicode[STIX]{x1D706}$ .

2.2 Short exponential sums with special polynomials

The following bound is contained in the proof of [Reference Liu, Shparlinski and Zhang14, Theorem 1.2] (and in fact is in the core of this proof).

Lemma 2.4. Let $q=p^{k}$ , $k\in \mathbb{N}$ be a power of an odd prime  $p$ . For any fixed $\unicode[STIX]{x1D702}$ with $0<\unicode[STIX]{x1D702}<1$ being a fixed constant, there exists a constant $k_{0}(\unicode[STIX]{x1D702})>0$ such that for $q^{\unicode[STIX]{x1D702}}<N<q$ and the polynomial

(2.1) $$\begin{eqnarray}f(X)=\mathop{\sum }_{j=0}^{\lfloor k/s\rfloor }g(j)\unicode[STIX]{x1D6FE}^{j}p^{js}X^{j},\end{eqnarray}$$

where $\unicode[STIX]{x1D6FE}$ is an arbitrary integer with $\gcd (\unicode[STIX]{x1D6FE},p)=1$ ,

$$\begin{eqnarray}s=\biggl\lfloor\frac{\unicode[STIX]{x1D702}\log N}{3000\log p}\biggr\rfloor,\end{eqnarray}$$

$g(0)=1$ and $g(j)$ with $1\leqslant j\leqslant \lfloor k/s\rfloor$ are integers given by

$$\begin{eqnarray}g(j)\equiv \frac{1/2(1/2-1)\cdots (1/2-j+1)}{j!}\hspace{0.2em}{\rm mod}\hspace{0.2em}p^{k},\quad 0\leqslant g(j)<p^{k},\end{eqnarray}$$

and any $k>k_{0}(\unicode[STIX]{x1D702})$ , uniformly over integers $h$ with $\gcd (h,q)=1$ , we have

$$\begin{eqnarray}\mathop{\sum }_{n\leqslant N}e\biggl(\frac{hf(n)}{q}\biggr)\ll _{\unicode[STIX]{x1D702}}Nq^{-\unicode[STIX]{x1D70C}(\unicode[STIX]{x1D702})},\end{eqnarray}$$

where $\unicode[STIX]{x1D70C}(\unicode[STIX]{x1D702})=c\unicode[STIX]{x1D702}^{3}$ with some absolute constant $c>0$ and the implied constant depends only on  $\unicode[STIX]{x1D702}$ .

2.3 Vaughan identity

As usual, we use $\unicode[STIX]{x1D6EC}(n)$ to denote the von Mangoldt function

$$\begin{eqnarray}\unicode[STIX]{x1D6EC}(n)=\left\{\begin{array}{@{}ll@{}}\log \ell \quad & \text{if}~n~\text{is a power of a prime}~\ell ,\\ 0\quad & \text{otherwise.}\end{array}\right.\end{eqnarray}$$

We use the following result of Vaughan [Reference Vaughan24] in the form given by Davenport [Reference Davenport4, Ch. 24].

Lemma 2.5. For any complex-valued function $f(n)$ and any real numbers $1<U,V\leqslant X$ , we have

$$\begin{eqnarray}\mathop{\sum }_{n\leqslant X}\unicode[STIX]{x1D6EC}(n)f(n)\ll \unicode[STIX]{x1D6F4}_{1}+\unicode[STIX]{x1D6F4}_{2}\log (UV)+\unicode[STIX]{x1D6F4}_{3}\log X+|\unicode[STIX]{x1D6F4}_{4}|,\end{eqnarray}$$

where

$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D6F4}_{1} & = & \displaystyle \biggl|\mathop{\sum }_{n\leqslant U}\unicode[STIX]{x1D6EC}(n)f(n)\biggr|,\nonumber\\ \displaystyle \unicode[STIX]{x1D6F4}_{2} & = & \displaystyle \mathop{\sum }_{v\leqslant UV}\biggl|\mathop{\sum }_{s\leqslant X/v}f(sv)\biggr|,\nonumber\\ \displaystyle \unicode[STIX]{x1D6F4}_{3} & = & \displaystyle \mathop{\sum }_{v\leqslant V}\max _{w\geqslant 1}\biggl|\mathop{\sum }_{w\leqslant s\leqslant X/v}f(sv)\biggr|\nonumber\end{eqnarray}$$

and

$$\begin{eqnarray}\unicode[STIX]{x1D6F4}_{4}=\mathop{\sum }_{\substack{ uv\leqslant X \\ u>U,\,v>V}}\unicode[STIX]{x1D6EC}(u)\biggl(\mathop{\sum }_{d\mid v,\,d\leqslant V}\unicode[STIX]{x1D707}(d)\biggr)f(uv).\end{eqnarray}$$

3.1 Proof of Theorem 1.1

Note that due to the symmetry of the sum and the claimed bound with respect to $M$ and  $N$ , we can always assume that $M\geqslant N$ .

Let $1\leqslant s\leqslant k$ be a parameter to be determined. Write

$$\begin{eqnarray}S_{a,q}({\mathcal{A}},{\mathcal{B}};M,N)=\mathop{\sum }_{u,v=1}^{p^{s}}\,\mathop{\sum }_{\substack{ m\leqslant M \\ m\equiv u\hspace{0.2em}{\rm mod}\hspace{0.2em}p^{s}}}\,\mathop{\sum }_{\substack{ n\leqslant N \\ n\equiv v\hspace{0.2em}{\rm mod}\hspace{0.2em}p^{s}}}\unicode[STIX]{x1D6FC}_{m}\unicode[STIX]{x1D6FD}_{n}{\mathcal{K}}(mn,a;q).\end{eqnarray}$$

Then by Lemmas 2.1 and 2.2, we have

Now by Lemma 2.1, we derive

where $r_{m,n}$ is a solution to $r_{m,n}^{2}\equiv amn\hspace{0.2em}{\rm mod}\hspace{0.2em}q$ (the inequality holds for any choice of this solution). In particular, we see that

(3.1)

where

(3.2) $$\begin{eqnarray}T_{s}(u,v)=\mathop{\sum }_{\substack{ n\leqslant N \\ n\equiv v\hspace{0.2em}{\rm mod}\hspace{0.2em}p^{s}}}\,\left|\mathop{\sum }_{\substack{ m\leqslant M \\ m\equiv u\hspace{0.2em}{\rm mod}\hspace{0.2em}p^{s}}}\unicode[STIX]{x1D6FC}_{m}\biggl(\frac{r_{m,n}}{p}\biggr)^{k}\Re \unicode[STIX]{x1D717}_{q}e\biggl(\frac{2r_{m,n}}{q}\biggr)\right|.\end{eqnarray}$$

Note that $r_{m,n}^{2}\equiv amn\equiv auv\hspace{0.2em}{\rm mod}\hspace{0.2em}p$ , and thus the Legendre symbol $(r_{m,n}/p)$ depends only on $u$ and  $v$ . We now use the Cauchy inequality and derive

$$\begin{eqnarray}T_{s}(u,v)^{2}\leqslant (Np^{-s}+1)\mathop{\sum }_{\substack{ m_{1},m_{2}\leqslant M \\ m_{1}\equiv u\hspace{0.2em}{\rm mod}\hspace{0.2em}p^{s} \\ m_{2}\equiv u\hspace{0.2em}{\rm mod}\hspace{0.2em}p^{s}}}\,\left|\mathop{\sum }_{\substack{ n\leqslant N \\ n\equiv v\hspace{0.2em}{\rm mod}\hspace{0.2em}p^{s}}}e\biggl(\frac{2(r_{m_{1},n}-r_{m_{2},n})}{q}\biggr)\right|,\end{eqnarray}$$

with $r_{m_{i},n}$ being a solution of the congruence $r^{2}\equiv m_{i}na\hspace{0.2em}{\rm mod}\hspace{0.2em}q$ for $i=1,2$ .

Now we consider the inner sum over $n$ . Note that for $i=1,2$ , we have $\gcd (am_{i},q)=1$ , then we use the following argument, which is similar to that in [Reference Blomer and Milićević3, Reference Khan8] and [Reference Liu, Shparlinski and Zhang14]. In fact these ideas date back to earlier work of Postnikov [Reference Postnikov16, Reference Postnikov17] where they were used for polynomials, and then extended by Stepanov and Shparlinski [Reference Stepanov and Shparlinski22, Reference Stepanov and Shparlinski23] for algebraic functions.

By $n\equiv v\hspace{0.2em}{\rm mod}\hspace{0.2em}p^{s}$ , there exists $t\in \mathbb{Z}$ , such that

(3.3) $$\begin{eqnarray}n=v+p^{s}t.\end{eqnarray}$$

Now we have

$$\begin{eqnarray}r_{m_{i},n}^{2}\equiv am_{i}(v+p^{s}t)\equiv am_{i}v(1+\bar{v}p^{s}t)~\hspace{0.2em}{\rm mod}\hspace{0.2em}q,\end{eqnarray}$$

with $v\bar{v}\equiv 1\hspace{0.2em}{\rm mod}\hspace{0.2em}q$ . Note that $am_{i}v\equiv auv\hspace{0.2em}{\rm mod}\hspace{0.2em}p$ , then

$$\begin{eqnarray}\biggl(\frac{am_{i}v}{p}\biggr)=1.\end{eqnarray}$$

By the Hensel lifting, there exists an integer  $\unicode[STIX]{x1D714}$ , such that $0\leqslant \unicode[STIX]{x1D714}<p^{s}$ and

$$\begin{eqnarray}\unicode[STIX]{x1D714}^{2}\equiv auv\hspace{0.2em}{\rm mod}\hspace{0.2em}p^{s},\end{eqnarray}$$

and also for each $m_{i}$ there exists an integer $\unicode[STIX]{x1D714}_{m_{i}}$ such that

$$\begin{eqnarray}\unicode[STIX]{x1D714}_{m_{i}}^{2}\equiv am_{i}v\hspace{0.2em}{\rm mod}\hspace{0.2em}q\end{eqnarray}$$

and $\unicode[STIX]{x1D714}_{m_{i}}\equiv \unicode[STIX]{x1D714}\hspace{0.2em}{\rm mod}\hspace{0.2em}p^{s}$ for $i=1,2$ . Thus

$$\begin{eqnarray}r_{m_{i},n}^{2}\equiv am_{i}v\equiv \unicode[STIX]{x1D714}_{m_{i}}^{2}(1+\bar{v}p^{s}t)~\hspace{0.2em}{\rm mod}\hspace{0.2em}q.\end{eqnarray}$$

We remark that $\unicode[STIX]{x1D714}_{m_{i}}$ is determined by $a$ , $m_{i}$ and  $v$ , and does not depend on  $n$ . Consider $1+\bar{v}p^{s}t$ in the $p$ -adic field $\mathbb{Q}_{p}$ . By the Taylor expansion (see [Reference Koblitz9, Ch. IV.1]), we have

$$\begin{eqnarray}(1+\bar{v}p^{s}t)^{1/2}=1+\mathop{\sum }_{j=1}^{\infty }\binom{1/2}{j}\bar{v}^{j}p^{js}t^{j}\end{eqnarray}$$

for $s\geqslant 1$ with the coefficients

$$\begin{eqnarray}\binom{1/2}{j}=\frac{1/2(1/2-1)\cdots (1/2-j+1)}{j!},\quad j=1,2,\ldots ,\end{eqnarray}$$

which are $p$ -adic integers, since $p$ is an odd prime. Then we have

$$\begin{eqnarray}(1+\bar{v}p^{s}t)^{1/2}\equiv 1+\mathop{\sum }_{j=1}^{\lfloor k/s\rfloor }g(j)\bar{v}^{j}p^{js}t^{j}~\hspace{0.2em}{\rm mod}\hspace{0.2em}p^{k},\end{eqnarray}$$

where $g(j)$ with $1\leqslant j\leqslant \lfloor k/s\rfloor$ are integers given by

$$\begin{eqnarray}g(j)\equiv \binom{1/2}{j}\hspace{0.2em}{\rm mod}\hspace{0.2em}p^{k},\quad 0\leqslant g(j)<p^{k}.\end{eqnarray}$$

Thus we have two solutions to the quadratic congruence of $r_{m_{i},n}$ in the inner sum in (3.2).

$$\begin{eqnarray}r_{m_{i},n}\equiv \pm \unicode[STIX]{x1D714}_{m_{i}}f(t)\hspace{0.2em}{\rm mod}\hspace{0.2em}q,\end{eqnarray}$$

where the polynomial $f(X)$ is given by (2.1) as in Lemma 2.4 with $\unicode[STIX]{x1D6FE}=\bar{v}$ and $t$ is defined by (3.3).

Choosing the solution $r_{m_{i},n}\equiv \unicode[STIX]{x1D714}_{m_{i}}f(t)\hspace{0.2em}{\rm mod}\hspace{0.2em}q$ , then we have

(3.4) $$\begin{eqnarray}T_{s}(u,v)^{2}\leqslant (Np^{-s}+1)\mathop{\sum }_{\substack{ m_{1},m_{2}\leqslant M \\ m_{1}\equiv u\hspace{0.2em}{\rm mod}\hspace{0.2em}p^{s} \\ m_{2}\equiv u\hspace{0.2em}{\rm mod}\hspace{0.2em}p^{s}}}\,\left|\mathop{\sum }_{t\leqslant (N-v)/p^{s}}e\biggl(\frac{2(\unicode[STIX]{x1D714}_{m_{1}}-\unicode[STIX]{x1D714}_{m_{2}})f(t)}{q}\biggr)\right|.\end{eqnarray}$$

We now choose

(3.5) $$\begin{eqnarray}B(\unicode[STIX]{x1D706})=3000/\unicode[STIX]{x1D706}>3000\quad \text{and}\quad s=\biggl\lfloor\frac{\log N}{B(\unicode[STIX]{x1D706})\log p}\biggr\rfloor.\end{eqnarray}$$

Since $q^{\unicode[STIX]{x1D706}}<N\leqslant M<q=p^{k}$ , then we have $s\leqslant k/B(\unicode[STIX]{x1D706})$ . Hence,

(3.6) $$\begin{eqnarray}N/p^{s}\geqslant q^{\unicode[STIX]{x1D706}/2}\quad \text{and}\quad k-3s>k/2.\end{eqnarray}$$

In particular, we see from (3.6) that

$$\begin{eqnarray}Np^{-s}+1\ll Np^{-s}.\end{eqnarray}$$

Thus (3.4) can be simplified as

(3.7) $$\begin{eqnarray}T_{s}(u,v)^{2}\ll Np^{-s}\mathop{\sum }_{\substack{ m_{1},m_{2}\leqslant M \\ m_{1}\equiv u\hspace{0.2em}{\rm mod}\hspace{0.2em}p^{s} \\ m_{2}\equiv u\hspace{0.2em}{\rm mod}\hspace{0.2em}p^{s}}}\,\left|\mathop{\sum }_{t\leqslant (N-v)/p^{s}}e\biggl(\frac{2(\unicode[STIX]{x1D714}_{m_{1}}-\unicode[STIX]{x1D714}_{m_{2}})f(t)}{q}\biggr)\right|.\end{eqnarray}$$

Let $\text{ord}_{p}(n)$ denote the $p$ -adic order of integer  $n$ . For a fixed  $m_{1}$ , we claim that

$$\begin{eqnarray}\sharp \{m_{2}\leqslant M:m_{2}\equiv m_{1}\hspace{0.2em}{\rm mod}\hspace{0.2em}p^{s},\text{ord}_{p}(\unicode[STIX]{x1D714}_{m_{1}}-\unicode[STIX]{x1D714}_{m_{2}})\geqslant 3s\}\leqslant Mp^{-3s}+1.\end{eqnarray}$$

To see this, we note that $\text{ord}_{p}(\unicode[STIX]{x1D714}_{m_{1}}-\unicode[STIX]{x1D714}_{m_{2}})\geqslant 3s$ implies

$$\begin{eqnarray}\unicode[STIX]{x1D714}_{m_{1}}^{2}\equiv \unicode[STIX]{x1D714}_{m_{2}}^{2}\hspace{0.2em}{\rm mod}\hspace{0.2em}~p^{3s}.\end{eqnarray}$$

Since $\gcd (av,q)=1$ , then by the definition of $\unicode[STIX]{x1D714}_{m_{i}}$ , we have the congruence $m_{2}\equiv m_{1}\hspace{0.2em}{\rm mod}\hspace{0.2em}p^{3s}$ , which yields our claim.

We estimate the contribution of this case to $T_{s}(u,v)^{2}$ trivially as

$$\begin{eqnarray}Np^{-s}\mathop{\sum }_{\substack{ m_{1}\leqslant M \\ m_{1}\equiv u\hspace{0.2em}{\rm mod}\hspace{0.2em}p^{s}}}\mathop{\sum }_{\substack{ m_{2}\leqslant M \\ m_{2}\equiv m_{1}\hspace{0.2em}{\rm mod}\hspace{0.2em}p^{s} \\ \text{ord}_{p}(\unicode[STIX]{x1D714}_{m_{1}}-\unicode[STIX]{x1D714}_{m_{2}})\geqslant 3s}}\mathop{\sum }_{t\leqslant (N-v)/p^{s}}1\ll MN^{2}p^{-3s}(Mp^{-3s}+1).\end{eqnarray}$$

Hence, we only need to estimate the exponential sum

$$\begin{eqnarray}\mathop{\sum }_{t\leqslant (N-v)/p^{s}}e\biggl(\frac{2(\unicode[STIX]{x1D714}_{m_{1}}-\unicode[STIX]{x1D714}_{m_{2}})f(t)}{q}\biggr),\end{eqnarray}$$

with $\text{ord}_{p}(\unicode[STIX]{x1D714}_{m_{1}}-\unicode[STIX]{x1D714}_{m_{2}})<3s$ . After cancelling the power of $p$ , which divides factor $p^{3s-1}$ , we obtain a similar exponential sum of the type

$$\begin{eqnarray}\mathop{\sum }_{t\leqslant (N-v)/p^{s}}e\biggl(\frac{hf(t)}{p^{r}}\biggr),\end{eqnarray}$$

with $\gcd (h,q)=1$ and $r>k-3s$ . To bound this sum, we recall our choice (3.5) and thus the inequality (3.6). Hence we can apply Lemma 2.4 and obtain

$$\begin{eqnarray}\mathop{\sum }_{t\leqslant (N-v)/p^{s}}e\biggl(\frac{2(\unicode[STIX]{x1D714}_{m_{1}}-\unicode[STIX]{x1D714}_{m_{2}})f(t)}{q}\biggr)\ll Np^{-s}q^{-\unicode[STIX]{x1D70C}(\unicode[STIX]{x1D706}/2)},\end{eqnarray}$$

for $k\geqslant 2k_{0}(\unicode[STIX]{x1D706}/2)$ , where $k_{0}$ and $\unicode[STIX]{x1D70C}$ are the same as in Lemma 2.4. Inserting this bound to (3.7), we derive

$$\begin{eqnarray}\displaystyle T_{s}(u,v)^{2} & \ll & \displaystyle M^{2}N^{2}p^{-4s}q^{-\unicode[STIX]{x1D70C}(\unicode[STIX]{x1D706}/2)}+MN^{2}p^{-3s}(Mp^{-3s}+1)\nonumber\\ \displaystyle & = & \displaystyle M^{2}N^{2}p^{-4s}q^{-\unicode[STIX]{x1D70C}(\unicode[STIX]{x1D706}/2)}+M^{2}N^{2}p^{-6s}+MN^{2}p^{-3s}.\nonumber\end{eqnarray}$$

Then we have

$$\begin{eqnarray}T_{s}(u,v)\ll MNp^{-2s}q^{-\unicode[STIX]{x1D70C}(\unicode[STIX]{x1D706}/2)/2}+MNp^{-3s}+M^{1/2}Np^{-3s/2},\end{eqnarray}$$

which after the substitution in (3.1) yields

$$\begin{eqnarray}S_{a,q}({\mathcal{A}},{\mathcal{B}};M,N)\ll MNq^{-\unicode[STIX]{x1D70C}(\unicode[STIX]{x1D706}/2)/2}+MNp^{-s}+M^{1/2}Np^{s/2}.\end{eqnarray}$$

Note that the definition of $s$ implies that

$$\begin{eqnarray}\displaystyle s & {\geqslant} & \displaystyle \frac{\log N}{B(\unicode[STIX]{x1D706})\log p}-1=\frac{\unicode[STIX]{x1D706}\log N}{3000\log p}-1\nonumber\\ \displaystyle & = & \displaystyle \frac{\unicode[STIX]{x1D706}k\log N}{3000\log q}-1\geqslant \frac{\unicode[STIX]{x1D706}k\log N}{6000\log q}=\frac{\log N}{2B(\unicode[STIX]{x1D706})\log p},\nonumber\end{eqnarray}$$

provided that $k$ is large enough (we also recall that $q>M\geqslant N>q^{\unicode[STIX]{x1D706}}$ ). Hence

$$\begin{eqnarray}N^{1/(2B(\unicode[STIX]{x1D706}))}\leqslant p^{s}\leqslant N^{1/B(\unicode[STIX]{x1D706})},\end{eqnarray}$$

from which the result follows.

3.2 Proof of Corollary 1.2

Separating the summation over $m$ in dyadic ranges and slightly reducing the constant $c$ in the definition of $\unicode[STIX]{x1D717}(\unicode[STIX]{x1D706})$ , it is enough to show that for any $M_{1},M_{2}$ with

$$\begin{eqnarray}M_{2}\leqslant 2M_{1}\quad \text{and}\quad U\leqslant M_{1}<M_{2}\leqslant 2X/V,\end{eqnarray}$$

we have

(3.8) $$\begin{eqnarray}\mathop{\sum }_{m=M_{1}}^{M_{2}}\mathop{\sum }_{V\leqslant n\leqslant X/m}\unicode[STIX]{x1D6FC}_{m}\unicode[STIX]{x1D6FD}_{n}{\mathcal{K}}(mn,a;q)\ll _{\unicode[STIX]{x1D706}}Xq^{-\unicode[STIX]{x1D717}(\unicode[STIX]{x1D706})}.\end{eqnarray}$$

Let $L=\lfloor X/M_{1}\rfloor$ . Clearly we can assume that $L\geqslant V$ as otherwise the sum over $n$ is void and there is nothing to prove. In particular, we can assume that

$$\begin{eqnarray}L\geqslant q^{\unicode[STIX]{x1D706}}.\end{eqnarray}$$

By the orthogonality of exponential functions, we write

$$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{m=M_{1}}^{M_{2}}\,\mathop{\sum }_{V\leqslant n\leqslant X/m}\unicode[STIX]{x1D6FC}_{m}\unicode[STIX]{x1D6FD}_{n}{\mathcal{K}}(mn,a;q)\nonumber\\ \displaystyle & & \displaystyle \quad =\mathop{\sum }_{m=M_{1}}^{M_{2}}\,\mathop{\sum }_{V\leqslant n\leqslant L}\frac{1}{L}\mathop{\sum }_{z=0}^{L-1}\,\mathop{\sum }_{w=0}^{X/m}e(z(w-n)/L)\unicode[STIX]{x1D6FC}_{m}\unicode[STIX]{x1D6FD}_{n}{\mathcal{K}}(mn,a;q)\nonumber\\ \displaystyle & & \displaystyle \quad =\frac{1}{L}\mathop{\sum }_{z=0}^{L-1}\,\mathop{\sum }_{m=M_{1}}^{M_{2}}\mathop{\sum }_{w=0}^{X/m}e(zw/L)\mathop{\sum }_{V\leqslant n\leqslant L}\unicode[STIX]{x1D6FC}_{m}\unicode[STIX]{x1D6FD}_{n}e(-zn/L){\mathcal{K}}(mn,a;q).\nonumber\end{eqnarray}$$

Using that for $z=0,\ldots ,L-1$ we have

$$\begin{eqnarray}\mathop{\sum }_{w=0}^{X/m}e(zw/L)\ll \frac{L}{1+\min \{z,L-z\}},\end{eqnarray}$$

see [Reference Iwaniec and Kowalski7, Bound (8.6)], we now derive

(3.9) $$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{m=M_{1}}^{M_{2}}\,\mathop{\sum }_{V\leqslant n\leqslant X/m}\unicode[STIX]{x1D6FC}_{m}\unicode[STIX]{x1D6FD}_{n}{\mathcal{K}}(mn,a;q)\nonumber\\ \displaystyle & & \displaystyle \quad =\mathop{\sum }_{z=0}^{L-1}\frac{1}{1+\min \{z,L-z\}}\mathop{\sum }_{m=M_{1}}^{M_{2}}\,\mathop{\sum }_{V\leqslant n\leqslant L}\widetilde{\unicode[STIX]{x1D6FC}}_{z,m}\widetilde{\unicode[STIX]{x1D6FD}}_{z,n}{\mathcal{K}}(mn,a;q),\end{eqnarray}$$

with some weights $|\widetilde{\unicode[STIX]{x1D6FC}}_{z,m}|\leqslant 1$ and $|\widetilde{\unicode[STIX]{x1D6FD}}_{z,n}|\leqslant 1$ (in particular, $\widetilde{\unicode[STIX]{x1D6FD}}_{z,n}=\unicode[STIX]{x1D6FD}_{n}e(-zn/L)$ ). Thus, by Theorem 1.1 for every $z=0,\ldots ,L-1$ , for the double sum over $m$ and $n$ we have the bound

$$\begin{eqnarray}\mathop{\sum }_{m=M_{1}}^{M_{2}}\mathop{\sum }_{V\leqslant n\leqslant L}\widetilde{\unicode[STIX]{x1D6FC}}_{z,m}\widetilde{\unicode[STIX]{x1D6FD}}_{z,n}{\mathcal{K}}(mn,a;q)\ll M_{2}Lq^{-\unicode[STIX]{x1D70F}(\unicode[STIX]{x1D706})}\ll Xq^{-\unicode[STIX]{x1D70F}(\unicode[STIX]{x1D706})},\end{eqnarray}$$

which after substitution in (3.9) implies (3.8) and concludes the proof.

3.3 Proof of Theorem 1.3

Using partial summation, one can easily see that it is enough to estimate the sum

$$\begin{eqnarray}\widetilde{S}(X;a,q)=\mathop{\sum }_{n\leqslant X}\unicode[STIX]{x1D6EC}(n){\mathcal{K}}(n,a;q).\end{eqnarray}$$

We now apply Lemma 2.5 (with $f(n)={\mathcal{K}}(n,a;q)$ ) where we take $U=V=X^{1/3}$ , for which we need to estimate the sums:

$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D6F4}_{1} & = & \displaystyle \biggl|\mathop{\sum }_{n\leqslant U}\unicode[STIX]{x1D6EC}(n){\mathcal{K}}(n,a;q)\biggr|,\nonumber\\ \displaystyle \unicode[STIX]{x1D6F4}_{2} & = & \displaystyle \mathop{\sum }_{v\leqslant UV}\,\biggl|\mathop{\sum }_{s\leqslant X/v}{\mathcal{K}}(sv,a;q)\biggr|,\nonumber\\ \displaystyle \unicode[STIX]{x1D6F4}_{3} & = & \displaystyle \mathop{\sum }_{v\leqslant V}\max _{w\geqslant 1}\biggl|\mathop{\sum }_{w\leqslant s\leqslant X/v}{\mathcal{K}}(sv,a;q)\biggr|\nonumber\end{eqnarray}$$

and

$$\begin{eqnarray}\unicode[STIX]{x1D6F4}_{4}=\mathop{\sum }_{\substack{ uv\leqslant X \\ u>U,~v>V}}\unicode[STIX]{x1D6EC}(u)\biggl(\mathop{\sum }_{d\mid v,\,d\leqslant V}\unicode[STIX]{x1D707}(d)\biggr){\mathcal{K}}(uv,a;q).\end{eqnarray}$$

We note that by Lemma 2.2 we can always satisfy the coprimality conditions $\gcd (s,p)=\gcd (u,p)=\gcd (v,p)=1$ in the summation ranges.

Using the Weil bound (1.1), or its more precise version given in Lemma 2.1, we have

$$\begin{eqnarray}{\unicode[STIX]{x1D6F4}_{1}\ll }_{\unicode[STIX]{x1D700}}X^{1/3}q^{\unicode[STIX]{x1D700}/3}<Xq^{-\unicode[STIX]{x1D700}/3}.\end{eqnarray}$$

For $\unicode[STIX]{x1D6F4}_{2}$ , using Lemma 2.2, we write

$$\begin{eqnarray}\unicode[STIX]{x1D6F4}_{2}=\mathop{\sum }_{\substack{ v\leqslant UV \\ \gcd (v,p)=1}}\biggl|\mathop{\sum }_{s\leqslant X/v}{\mathcal{K}}(sv,a;q)\biggr|=\mathop{\sum }_{\substack{ v\leqslant UV \\ \gcd (v,p)=1}}\biggl|\mathop{\sum }_{s\leqslant X/v}{\mathcal{K}}(s,a\overline{v};q)\biggr|.\end{eqnarray}$$

Since $v\leqslant UV=X^{2/3}$ we have $X/v\geqslant X^{1/3}>q^{\unicode[STIX]{x1D700}/3}$ . Now Lemma 2.3 can be applied to the sum over  $s$ . Hence there exist constants $K_{1}(\unicode[STIX]{x1D700})>0$ and $\unicode[STIX]{x1D70F}_{1}(\unicode[STIX]{x1D700})>0$ such that

$$\begin{eqnarray}{\unicode[STIX]{x1D6F4}_{2}\ll }_{\unicode[STIX]{x1D700}}Xq^{-\unicode[STIX]{x1D70F}_{1}(\unicode[STIX]{x1D700})}\end{eqnarray}$$

holds uniformly for any odd prime $p$ and $k>K_{1}(\unicode[STIX]{x1D700})$ .

For $\unicode[STIX]{x1D6F4}_{3}$ , write the inner sum over $s$ into

$$\begin{eqnarray}\mathop{\sum }_{w\leqslant s\leqslant X/v}{\mathcal{K}}(sv,a;q)=\mathop{\sum }_{s\leqslant X/v}{\mathcal{K}}(sv,a;q)-\mathop{\sum }_{s<w}{\mathcal{K}}(sv,a;q).\end{eqnarray}$$

The contribution of the first sum on the right side can be bounded similarly as  $\unicode[STIX]{x1D6F4}_{2}$ . For the contribution of the second sum. If $w<q^{\unicode[STIX]{x1D700}/4}$ , then by the Weil bound we have

$$\begin{eqnarray}\mathop{\sum }_{s\leqslant w}{\mathcal{K}}(sv,a;q)\ll _{\unicode[STIX]{x1D700}}q^{\unicode[STIX]{x1D700}/3}.\end{eqnarray}$$

If $w\geqslant q^{\unicode[STIX]{x1D700}/4}$ , then Lemma 2.3 can be applied to the above sum. It follows from the above treatment that there exist constants $K_{2}(\unicode[STIX]{x1D700})>0$ and $\unicode[STIX]{x1D70F}_{2}(\unicode[STIX]{x1D700})>0$ such that

$$\begin{eqnarray}{\unicode[STIX]{x1D6F4}_{3}\ll }_{\unicode[STIX]{x1D700}}Xq^{-\unicode[STIX]{x1D70F}_{2}(\unicode[STIX]{x1D700})}\end{eqnarray}$$

holds uniformly for any odd prime $p$ and $k>K_{2}(\unicode[STIX]{x1D700})$ .

For $\unicode[STIX]{x1D6F4}_{4}$ , by Corollary 1.2 there exist constants $K_{3}(\unicode[STIX]{x1D700})>0$ and $\unicode[STIX]{x1D70F}_{3}(\unicode[STIX]{x1D700})>0$ such that

$$\begin{eqnarray}{\unicode[STIX]{x1D6F4}_{4}\ll }_{\unicode[STIX]{x1D700}}Xq^{-\unicode[STIX]{x1D70F}_{3}(\unicode[STIX]{x1D700})}\end{eqnarray}$$

holds uniformly for any odd prime $p$ and $k>K_{3}(\unicode[STIX]{x1D700})$ . It is also easy to see that for the functions $\unicode[STIX]{x1D70F}_{\unicode[STIX]{x1D708}}(\unicode[STIX]{x1D700})$ we can take $\unicode[STIX]{x1D70F}_{\unicode[STIX]{x1D708}}(\unicode[STIX]{x1D700})=c_{\unicode[STIX]{x1D708}}\unicode[STIX]{x1D700}^{3}$ for some absolute constants $c_{\unicode[STIX]{x1D708}}>0$ , for every $\unicode[STIX]{x1D708}=1,2,3$ .

Now the desired bound on $\widetilde{S}(X;a,q)$ and thus Theorem 1.3 follows from the above estimates.