2.1 Notation and some elementary estimates

We recall that the notations $U = O(V)$ , $U \ll V$ and $ V\gg U$ are equivalent to $|U|\leqslant c V$ for some positive constant c, which throughout this work, is absolute.

Furthermore, we write $U \asymp V$ to express that $V \ll U \ll V$ .

We also write $U= V^{o(1)}$ if for all $\varepsilon>0$ , there exists a constant $c(\varepsilon )>0$ such that $ |U| \leq c(\varepsilon ) V^\varepsilon $ as $V\to \infty $ .

The letter p always denotes a prime number.

For an integer $k \ge 1$ , we denote by $\mu (k)$ , $\tau (k),$ and $\varphi (k)$ , the Möbius function, the number of integer positive divisors, and the Euler function of k, respectively, for which we use the well-known bound

(2.1) $$ \begin{align} \tau(k) = k^{o(1)} \qquad\mbox{and}\qquad \varphi(k) \gg \frac{k}{\log \log (k+2)}, \end{align} $$

as $k \to \infty $ (see [Reference Hardy and Wright6, Theorems 317 and 328]).

As usual, we define

$$\begin{align*}\operatorname{sign} u = \begin{cases} -1, & \text{if } u < 0,\cr 0, & \text{if } u =0,\cr 1, & \text{if } u>0. \end{cases} \end{align*}$$

For positive integers u and v, using the Möbius function $\mu (e)$ and the inclusion–exclusion principle to detect the co-primality condition and then interchanging the order of summation, we obtain

(2.2) $$ \begin{align} \begin{aligned} \sum_{\substack{1\le c \le v\\ \gcd(c,u) = 1}} 1 & =\sum_{e\mid u}\mu (e) \left\lfloor\frac{v}{e}\right\rfloor = v \sum_{e\mid u}\frac{\mu (e)}{e} +O\left( \sum_{e\mid u}|\mu (e)|\right)\cr & = v \frac{\varphi(u)}{u} +O\left( \tau(u)\right) = v \frac{\varphi(u)}{u} +O\left(u^{o(1)}\right) \end{aligned} \end{align} $$

(see [Reference Hardy and Wright6, Equation (16.1.3)]).

2.2 Modular hyperbolas

Here, we need some results on the distribution of points on the modular hyperbola

(2.3) $$ \begin{align} uv \equiv 1 \quad\pmod q, \end{align} $$

where $q \ge 1$ is an arbitrary integer.

We start with a very well-known case counting the number $N(q;U,V)$ of solutions in a rectangular domain $(u,v) \in [1, U]\times [1,V]$ . For example, such a result has been recorded in [Reference Shparlinski12, Theorem 13] (we note that the restriction $U,V\le q$ is not really necessary).

Lemma 2.1 For any $U,V\ge 1$ , we have

$$\begin{align*}N(q;U,V)= \frac{\varphi(q)}{q^2} UV + O\left(q^{1/2+ o(1)}\right). \end{align*}$$

Next, we recall a result of Ustinov [Reference Ustinov14] on the number $T_f(q; Z,U)$ of points $(u,v)$ on the modular hyperbola (2.3) with variables run through a domain of the form

$$\begin{align*}Z< u \le Z+U \qquad\mbox{and}\qquad 0 \le v \le f(u), \end{align*}$$

where f is a positive function with a continuous second derivative.

Namely, a special case of [Reference Ustinov14], where we have also used (2.1) to estimate various divisor sums, can be formulated as follows.

Let

$$ \begin{align*} \mathcal{T}_f(q,Z,U) = \{(u,v) \in \mathbb{Z}^2 :~ Z < u \le Z+U, \ 0 &< v \le f(u), \cr & uv \equiv 1 \quad\pmod q \}, \end{align*} $$

and let

$$\begin{align*}T_f(q,Z,U) = \# \mathcal{T}_f(q,Z,U). \end{align*}$$

Lemma 2.2 Assume that the function $f:{\mathbb R}\to {\mathbb R}_{\geq 0}$ has a continuous second derivative on $[Z,Z+U]$ such that for some $L>0 $ , we have

$$\begin{align*}\left|f"(u)\right| \asymp \frac{1}{L}, \qquad u \in [Z,Z+U]. \end{align*}$$

Then we have the estimate

$$\begin{align*}T_f(q; Z,U) = \frac{1}{q} \sum_{\substack{Z < u \le Z + U\\ \gcd(u,q) = 1}} f(u)+ O\left(\left(U L^{-1/3} + L^{1/2} + q^{1/2}\right)(qU)^{o(1)}\right). \end{align*}$$

For other results on the distribution of points on modular hyperbolas, we refer to the survey [Reference Shparlinski12] and also more recent works [Reference Baier1, Reference Browning and Haynes2, Reference Chan4, Reference Garaev and Shparlinski5, Reference Humphries7, Reference Ustinov15].

3.1 Separating contributions to the main term and to the error term

It is easy to see that there are only $O(X)$ matrices in $\operatorname {SL}_2({\mathbb Z}; X)$ with $abcd=0$ . We now consider the following eight sets for different choices of the signs of a, $c,$ and d:

$$\begin{align*}\Gamma_0^{\alpha, \gamma, \delta}(Q,X)= \{A\in \Gamma_0(Q,X):~ \operatorname{sign} a = \alpha, \ \operatorname{sign} c = \gamma,\ \operatorname{sign} d = \delta\}, \end{align*}$$

with $\alpha , \gamma , \delta \in \{-1,1\}$ .

Now observe that $\Gamma _0(Q,X)$ is preserved under the bijections

$$\begin{align*}\begin{bmatrix} a & b \cr c & d \cr \end{bmatrix} \mapsto \begin{bmatrix} -a & b \cr c &- d \cr \end{bmatrix} \end{align*}$$

and

$$\begin{align*}\begin{bmatrix} a & b \cr c & d \cr \end{bmatrix} \mapsto \begin{bmatrix} a & -b \cr -c & d \cr \end{bmatrix}. \end{align*}$$

This means

$$\begin{align*}\# \Gamma_0^{1,1,1}(Q,X) = \# \Gamma_0^{\alpha, \gamma, \alpha} \end{align*}$$

and

$$\begin{align*}\# \Gamma_0^{-1,1,1}(Q,X) = \# \Gamma_0^{-\alpha, \gamma, \alpha} \end{align*}$$

for all pairs $\alpha ,\gamma \in \{-1,1\}$ .

Thus

(3.1) $$ \begin{align} \# \Gamma_0(Q,X) = 4 \cdot (\# \Gamma_0^{1, 1, 1 }(Q,X) + \# \Gamma_0^{1, 1, -1 }(Q,X)) + O(X). \end{align} $$

3.2 Preliminary counting of $\Gamma _0^{1, 1, 1 }(Q,X)$

Writing $cQ$ instead of c, we need to count the number of solutions to the equation

$$\begin{align*}ad = 1 + bcQ, \qquad 1 \le a, |b|,d\le X, \ 1 \le c \le X/Q. \end{align*}$$

We first do this for a fixed c and then sum up over all $c \le X/Q$ .

First, we consider the values $a \le cQ$ . We note that setting

$$\begin{align*}b = \frac{ad -1}{cQ} \end{align*}$$

for a solution $(a,d)$ to the congruence

$$\begin{align*}ad \equiv 1 \quad\pmod {cQ} \qquad 1 \le a \le cQ, \ 1 \le d\le X, \end{align*}$$

we have $b \le X$ . Hence, we see from Lemma 2.1 (and then recalling that $cQ \le X$ ) that for every $c \in [1, X/Q]$ , there are

(3.2) $$ \begin{align} \begin{aligned} G_{1}(c) & = \frac{\varphi(cQ)}{(cQ)^2} cQ X + O\left(\left(cQ\right)^{1/2 + o(1)}\right)\cr & = \frac{\varphi(cQ)}{cQ} X + O\left(X^{1/2 + o(1)}\right) \end{aligned} \end{align} $$

such matrices

$$\begin{align*}\begin{bmatrix} a & b \cr cQ & d \cr \end{bmatrix} \in \Gamma_0^{1,1,1}(Q,X). \end{align*}$$

Next, we count the contribution $G_{2}(c)$ from matrices $A\in \Gamma _0^{1,1,1}(Q,X)$ with $a> cQ$ . To do this, we recall the notation of Section 2.2 and then parameterize this set using a modular hyperbola as follows.

Lemma 3.1 Fix $1 \leq c \leq X/Q$ , $0 < U \leq X - cQ$ and define

$$\begin{align*}f_c(x) = \frac{cQX+1}{x}.\end{align*}$$

Then the map

$$\begin{align*}{\mathcal T}_{f_c}(cQ,cQ,U) \to \Gamma_0^{1,1,1}(Q,X)\end{align*}$$

given by

$$\begin{align*}(x,y) \mapsto \begin{bmatrix} x & (xy-1)/cQ \cr cQ & y \cr \end{bmatrix} \end{align*}$$

is well-defined, injective and its image is exactly the set of those $A\in \Gamma _0^{1,1,1}(Q,X)$ with $cQ < a \leq cQ + U$ and bottom left entry equal to $cQ$ .

Proof For $(x,y) \in {\mathcal T}_{f_c}(cQ,cQ,U)$ , we have that $(xy-1)/cQ \in \mathbb {Z}$ and

$$\begin{align*}0 < y \leq f_c(X), \end{align*}$$

which is equivalent to

$$\begin{align*}\frac{-1}{cQ} < (xy - 1)/cQ \leq X. \end{align*}$$

As $x> cQ \geq 1$ and $y>0$ , this is actually equivalent to

$$\begin{align*}1 \leq (xy - 1)/cQ \leq X.\end{align*}$$

We also need to check that $1 \leq y \leq X$ . This follows since

$$\begin{align*}0<y \leq f_c(x) = \frac{cQX+1}{x} < \frac{cQX+1}{cQ} = X+\frac{1}{cQ} \leq X+1. \end{align*}$$

Thus, indeed, $(x,y)$ is mapped to an element of $\Gamma _0^{1,1,1}(Q,X)$ with the desired properties. Conversely, suppose that $A \in \Gamma _0^{1,1,1}(Q,X)$ with $a>cQ$ and bottom left entry equal to $cQ$ . As $ad \equiv 1 \ \ \pmod {cQ}$ , we have $1 \leq x,y \leq X$ such that

$$\begin{align*}A = \begin{bmatrix} x & (xy-1)/cQ \cr cQ & y \cr \end{bmatrix}.\end{align*}$$

Also by definition (the lower bound holds as $x>cQ\geq 1$ )

$$\begin{align*}1 \leq \frac{xy - 1}{cQ} \leq X,\end{align*}$$

which means

$$\begin{align*}0 < \frac{cQ+1}{x} \leq y \leq \frac{cQX + 1}{x} = f_c(x)\end{align*}$$

and so indeed $(x,y) \in \mathcal {T}(f_c, cQ, U)$ .

We partition the interval $(cQ,X]$ into $I \ll \log X$ dyadic intervals of the form $(Z_i, Z_i+U_i]$ with

$$\begin{align*}Z_i = 2^{i-1} cQ \qquad\mbox{and}\qquad U_i \le Z_i, \qquad i =1, \ldots, I, \end{align*}$$

(in fact $U_i = Z_i$ , except maybe for $i=I$ ) and note that

(3.3) $$ \begin{align} 2^{I} cQ \asymp X. \end{align} $$

We now write

(3.4) $$ \begin{align} G_{2}(c) = \sum_{i=1}^I T_{f_c}\left(cQ, Z_i, U_i \right), \end{align} $$

where $f_c(x)$ is as in Lemma 3.1.

Next, for each $i =1, \ldots , I$ , we use Lemma 2.2 with $q = cQ$ and use that

$$\begin{align*}\left|f"(x)\right|\asymp \frac{cQ X}{Z_i^3} \asymp \frac {X}{ 2^{3i} (cQ)^2} \end{align*}$$

for $x \in (Z_i, Z_i+U_i]$ . Therefore, we conclude that

(3.5) $$ \begin{align} T_{f_c}\left(cQ, Z_i , U_i\right) = M_{i}(c) + O\left(E_{i}(c) X^{o(1)}\right), \end{align} $$

where

$$ \begin{align*} &M_{i}(c) = \frac{1}{cQ} \sum_{\substack{Z_i < x \le Z_i+ U_i\\ \gcd(x, cQ) = 1}} f_c (x),\cr & E_{i}(c)=2^{i} cQ \left( \frac {X}{ 2^{3i} (cQ)^2} \right)^{1/3} + \left( \frac{ 2^{3i} (cQ)^2}{X} \right)^{1/2} +X^{1/2}. \end{align*} $$

Combing the main terms $M_{i}(c)$ , $i =1, \ldots , I$ , together and recalling (3.4), we obtain

(3.6) $$ \begin{align} G_{2}(c) = \mathsf M(c) + O\left(\mathsf E(c) X^{o(1)}\right), \end{align} $$

where

$$\begin{align*}\mathsf M(c) = \frac{1}{ cQ} \sum_{\substack{cQ< x \le X\\ \gcd(x, |c|Q) = 1}} f_c (x) \end{align*}$$

and

$$ \begin{align*} \mathsf E(c) & = \sum_{i=1}^I \left(2^{i} cQ \left( \frac {X}{ 2^{3i} (cQ)^2} \right)^{1/3} + \left( \frac{ 2^{3i} (cQ)^2}{X} \right)^{1/2} + \left(cQ\right)^{1/2}\right)\cr & = \sum_{i=1}^I \left( \left(cQX\right)^{1/3} + 2^{3i/2} cQ X^{-1/2} + \left(cQ\right)^{1/2}\right)\cr & = \left( \left(cQX\right)^{1/3} + 2^{3I/2} cQ X^{-1/2} + \left(cQ\right)^{1/2}\right)X^{o(1)}. \end{align*} $$

Recalling (3.3) and using $cQ \le X$ , we obtain

$$\begin{align*}\mathsf E(c) \le \left(X^{2/3} + (cQ)^{-1/2} X\right) X^{o(1)}, \end{align*}$$

which after the substitution in (3.6) yields

(3.7) $$ \begin{align} G_{2}(c) = \mathsf M(c) + O\left( \left(X^{2/3} + (cQ)^{-1/2} X\right) X^{o(1)}\right). \end{align} $$

3.3 Asymptotic formula for $\Gamma _0^{1, 1, 1 }(Q,X)$

From the equations (3.2) and (3.7), we obtain

(3.8) $$ \begin{align} \# \Gamma_0^{1,1,1}(Q,X) = \sum_{1 \le c \le X/Q} \left(G_1(c) + G_2(c)\right) = \mathbf{M} + O\left(\mathbf{E}\right), \end{align} $$

where

$$ \begin{align*} \mathbf{M} & = \sum_{1 \le c \le X/Q} \left( \frac{\varphi(cQ)}{cQ} X + \frac{1}{ cQ} \sum_{\substack{cQ< x \le X\\ \gcd(x, cQ) = 1}} f_c (x)\right)\cr & = X F_1(Q,X) + \sum_{1 \le c \le X/Q} \frac{1}{ cQ} \sum_{\substack{cQ< x \le X\\ \gcd(x, cQ) = 1}} f_c (x) \end{align*} $$

and

$$\begin{align*}\mathbf{E} = \sum_{1 \le c \le X/Q} \left(X^{2/3} + (cQ)^{-1/2} X\right) X^{o(1)} = X^{5/3+o(1)} Q^{-1}. \end{align*}$$

We also note that

$$ \begin{align*} \frac{1}{ cQ} \sum_{\substack{cQ< x \le X\\ \gcd(x, cQ) = 1}} f_c (x) & = \sum_{1 \le c \le X/Q} \sum_{\substack{cQ< x \le X\\ \gcd(x, cQ) = 1}} \frac{cQ X + 1}{cQx} \cr & = X \sum_{1 \le c \le X/Q} \sum_{\substack{cQ< x \le X\\ \gcd(x, cQ) = 1}} \frac{1}{x} + O\left(X^{o(1)}\right). \end{align*} $$

Change the order of summation, we write

$$\begin{align*}\sum_{1 \le c \le X/Q} \sum_{\substack{cQ< x \le X\\ \gcd(x, cQ) = 1}} \frac{1}{x} = \sum_{\substack{Q< x \le X\\ \gcd(x, Q) = 1}} \frac{1}{x} \sum_{\substack{c< x/Q\\ \gcd(x, c) = 1}} 1. \end{align*}$$

Hence, recalling (2.2), we derive that

$$ \begin{align*} \sum_{1 \le c \le X/Q} \frac{1}{ cQ} \sum_{\substack{cQ< x \le X\\ \gcd(x, cQ) = 1}} f_c (x) & = Q^{-1} \sum_{\substack{Q< x \le X\\ \gcd(x, Q) = 1}} \frac{\varphi(x)}{x} +O\left(X^{o(1)}\right)\cr & = F_2(Q,X) + O\left(X^{o(1)}\right). \end{align*} $$

Thus, we see from (3.8) that

(3.9) $$ \begin{align} \# \Gamma_0^{1,1,1}(Q,X) = X\left( F_1(Q,X) + F_2(Q,X)\right) + O\left(X^{5/3+o(1)} Q^{-1}\right). \end{align} $$

3.4 Counting $\Gamma ^{-1,1,1}(Q,X) $

Recalling (3.1), we see that it remains to count $\Gamma _0^{-1, 1, 1 }(Q,X)$ . One can use a similar argument, but in fact, we show that

(3.10) $$ \begin{align} \# \Gamma^{-1,1,1}(Q,X) =\# \Gamma^{1,1,1}(Q,X) + O\left(\mathbf{E} + X\right), \end{align} $$

where the error term $\mathbf {E} = O(X^{5/3+o(1)} Q^{-1} )$ is the same as obtained above.

Thus, we wish to count matrices of the form

$$\begin{align*}A = \begin{bmatrix} x & (xy-1)/cQ \cr cQ & y \cr \end{bmatrix}, \end{align*}$$

where $xy \equiv 1 \ \ \pmod {cQ}$ , $-X\leq x \leq -1$ , $1 \leq y \leq X$ , $1 \leq cQ \leq X$ and $-X \leq (xy-1)/cQ \leq -1$ .

Without loss of generality, we can assume that $X \not \in {\mathbb Z}$ . Then, we consider the following two cases.

Case I: $x> -cQ$ . Note that for any $x,y$ with $xy \equiv 1 \ \ \pmod {cQ}$ , $-cQ < x \leq -1$ and $1 \leq y \leq X$ , we have

$$\begin{align*}\frac{-cQX - 1}{cQ} < \frac{xy-1}{cQ} \leq \frac{-2}{cQ}, \end{align*}$$

and so

$$\begin{align*}\leq \frac{xy-1}{cQ} \leq -1. \end{align*}$$

Thus, indeed, the corresponding A is in $\Gamma _0^{-1,1,1}(Q,X)$ . Note that since $0<x + cQ \leq cQ$ and $-X \leq (xy-1)/cQ + y \leq X $ , we have that

$$\begin{align*}\begin{bmatrix} 1 & 1\\ 0 & 1 \cr \end{bmatrix} A = \begin{bmatrix} x + cQ & (xy-1)/cQ + y \cr cQ & y \cr \end{bmatrix} \in \Gamma_0^{1,1,1}(Q,X). \end{align*}$$

So in fact, the number of such matrices A is exactly $G_1(c)$ as computed in (3.2) in the $\Gamma _0^{1,1,1}(Q,X)$ case.

Case II: $-X<x \leq -cQ$ . Let

$$\begin{align*}\widetilde{f}_c(x) = \frac{-cQX + 1}{x}. \end{align*}$$

We now need an analogue of Lemma 3.1. While the argument is very similar to that of the proof of Lemma 3.1, there are some differences, so we prefer to present it in full detail.

Lemma 3.2 Fix $1 \leq c \leq X/Q$ , $0 < U \leq X - cQ$ . Then the map

$$\begin{align*}\mathcal{T}_{\widetilde{f}_c}(cQ, -X, U) \to \Gamma_0^{-1,1,1}(Q,X)\end{align*}$$

given by

$$\begin{align*}(x,y) \mapsto A= \begin{bmatrix} x & (xy-1)/cQ \cr cQ & y \cr \end{bmatrix}\end{align*}$$

is well-defined, injective and its image is exactly the set of those $A\in \Gamma _0^{-1,1,1}(Q,X)$ with $-X < x \leq -X + U$ and bottom left entry equal to $cQ$ .

Proof Let $(x,y) \in \mathcal {T}_{\widetilde {f}_c}(cQ, -X, U) $ . Thus, by definition,

$$\begin{align*}0<y \leq \frac{-cQX+1}{x}.\end{align*}$$

As $x<-cQ$ , we have that

$$\begin{align*}\frac{-cQX+1}{x} = \frac{cQX-1}{-x} \leq \frac{cQX-1}{cQ} < X\end{align*}$$

and so indeed $y \leq X$ . Moreover, as $x<0$ , we have

$$\begin{align*}1 \geq \frac{1}{cQ}> \frac{xy - 1}{cQ} \geq -X. \end{align*}$$

So indeed this mapping has range inside $\Gamma _0^{-1,1,1}(Q,X)$ . Conversely, suppose

$$\begin{align*}A = \begin{bmatrix} x & b \cr cQ & y \cr \end{bmatrix} \end{align*}$$

is in $\Gamma _0^{-1,1,1}(Q,X)$ with $-X <x \leq -X + U$ . Then $-X \leq b \leq 0$ is an integer, thus ${xy \equiv 1 \ \ \pmod {cQ}}$ and

$$\begin{align*}\leq \frac{xy-1}{cQ} \leq 0.\end{align*}$$

Thus, as $x<0,$ we have

$$\begin{align*}\frac{-cQX + 1}{x} \geq y. \end{align*}$$

Thus

$$\begin{align*}0 < y \leq \widetilde{f}_c(x)\end{align*}$$

and so indeed $(x,y) \in \mathcal {T}_{\widetilde {f}_c}(cQ, -X, U)$ as desired.

We now fix c with $1 \leq c \leq X/Q$ and observe now that by Lemma 3.2, for any $Z \in [-X,0)$ and $0 < U \leq |Z|$ , we have that $T_{\widetilde {f}_c}(cQ, Z, U)$ has the main term

$$ \begin{align*} \frac{2}{cQ} \sum_{\substack{Z < x \le Z + U\\ \gcd(x,q) = 1}} \widetilde{f}_c(x) &= \frac{2}{cQ} \sum_{\substack{Z < x \le Z + U\\ \gcd(x,q) = 1}} \frac{-cQX + 1}{x} \cr &=\frac{2}{cQ} \sum_{\substack{-Z - U \leq x < -Z \cr \gcd(x',q) = 1}} \frac{cQX - 1}{x} \cr &= \frac{2}{cQ} \sum_{\substack{-Z - U \leq x < -Z \cr \gcd(x,q) = 1}} f_c(x) \cr &= \frac{2}{cQ} \sum_{\substack{|Z| - U \leq x < |Z| \cr \gcd(x,q) = 1}} f_c(x), \end{align*} $$

where we recall $f_c(x) = (cQX-1)/x$ as used in Lemma 3.1. But this is precisely the same main term as for $T_{f_c}(cQ, |Z| - U, U)$ except for the boundary terms ( $x = -Z-U, -Z$ ) which contribute only $O(X)$ (uniformly in Q as $|(cQX-1)/x \leq (cQX-1)/cQ \leq X$ ). Thus, recalling (3.4), (3.5), and (3.6), we see that for each admissible c, we obtain the contribution to $\# \Gamma ^{-1,1,1}(Q,X)$ , which is asymptotic to $G_2(c)$ . Now observe that $\widetilde {f}_c(x) = - f_c(x)$ and so $|\widetilde {f}^{\prime \prime }_c(x)| = |f^{\prime \prime }_c(-x)|$ which means that the error terms we obtain from applying Lemma 2.2 to $\widetilde {f}_c$ are the same as those obtained for $f_c$ (we have $x \in [-X, -cQ]$ and before we had $x \in [cQ, X]$ ). Thus, if we sum over c and proceed as before, we see that the error term is at most $O\left (\mathbf {E} + X\right )$ which implies (3.10).

3.5 Concluding the proof

Substituting (3.10) in (3.1) implies

$$\begin{align*}\# \Gamma_0(Q,X) = 8\# \Gamma_0^{1, 1, 1 }(Q,X) +O(X^{5/3+o(1)} Q^{-1} + X). \end{align*}$$

Recalling (3.9), we conclude the proof.

4.1 Approximating $F_1(Q,X)$

For convenience, we let

$$\begin{align*}G(Q,X) = \sum_{1 \le n \le X} \frac{\varphi(Qn)}{Qn}. \end{align*}$$

So

(4.1) $$ \begin{align} F_1(Q,X) = G(Q,Q^{-1}X). \end{align} $$

We now define the function

$$\begin{align*}h(n) = \mu(n)/n. \end{align*}$$

Lemma 4.1 We have

$$\begin{align*}G(Q,X) =\frac{\varphi(Q)}{Q} \sum_{\substack{n \leq X\\ \gcd(n,Q) = 1}} h(n) \left \lfloor \frac{X}{n} \right\rfloor. \end{align*}$$

Proof Observe that for any integer $n \ge 1$ ,

$$\begin{align*}\varphi(Qn) = Qn \prod_{p\mid Qn} \left(1-p^{-1}\right) \qquad\mbox{and}\qquad \varphi(Q)n = Qn \prod_{p\mid Q} \left(1-p^{-1}\right). \end{align*}$$

Hence

$$\begin{align*}\frac{\varphi(Qn)}{\varphi(Q)n} = \prod_{\substack{p \mid n\\ \gcd(p,Q) = 1}} \left(1 - p^{-1}\right). \end{align*}$$

Thus, we derive

$$ \begin{align*} \frac{Q}{\varphi(Q)} G(Q,X) &= \sum_{n \leq X} \prod_{\substack{p \mid n\\ \gcd(p,Q) = 1}} \left(1 - p^{-1}\right) = \sum_{n \leq X} \sum_{\substack{d \mid n\\ \gcd(d,Q) = 1}} \frac{\mu(d)}{d} \cr &= \sum_{\substack{d \leq X\\ \gcd(d,Q) = 1}} \sum_{\substack{n \leq X\\ d \mid n}} \frac{\mu(d)}{d} = \sum_{\substack{d \leq X\\ \gcd(d,Q) = 1}} \frac{\mu(d)}{d} \left\lfloor \frac{X}{d} \right\rfloor, \end{align*} $$

which completes the proof.

We now see from Lemma 4.1 that

$$ \begin{align*} G(Q,X) &= \frac{\varphi(Q)}{Q} X \sum_{\substack{n \leq X\\ \gcd(n,Q) = 1}} \frac{h(n)}{n} + O\left(\frac{\varphi(Q)}{Q} \sum_{n \leq X}| h(n) | \right) \cr &= \frac{\varphi(Q)}{Q} X \sum_{\substack{n \leq X\\ \gcd(n,Q) = 1}} \frac{h(n)}{n} + O\left( \ \frac{\varphi(Q)}{Q} \log X \right) .\end{align*} $$

Using that

$$\begin{align*}\sum_{n>X} \frac{|h(n)|}{n} \le \sum_{n>X} \frac{1}{n^2}= O\left(X^{-1}\right), \end{align*}$$

we write

(4.2) $$ \begin{align} G(Q,X) = \frac{\varphi(Q)}{Q} X \sum_{\substack{n = 1\\ \gcd(n,Q) = 1}}^\infty \frac{h(n)}{n} + O\left( \frac{\varphi(Q)}{Q} \log X \right). \end{align} $$

Note that

$$ \begin{align*} \sum_{\substack{n \geq 1\\ \gcd(n,Q) = 1}} \frac{h(n)}{n} &= \prod_{\gcd(p,Q) = 1} \left(1 - \frac{1}{p^2}\right) = \prod_{p} \left(1 - \frac{1}{p^2}\right) \prod_{p\mid Q} \left( 1 - \frac{1}{p^2} \right)^{-1} \cr & = \frac{6}{\pi^2} \prod_{p\mid Q} \left( 1 - \frac{1}{p^2} \right)^{-1} = \frac{6}{\pi^2} \cdot \frac{Q}{\varphi(Q)} \cdot \frac{Q}{\psi(Q)}. \end{align*} $$

Thus, we see from (4.2) that

(4.3) $$ \begin{align} G(Q,X) =\frac{6Q}{\pi^2 \psi(Q)} X+ O\left( \frac{\varphi(Q)}{Q}\log X \right) \end{align} $$

and so by (4.1), we derive

(4.4) $$ \begin{align} F_1(Q,X) = G(Q,Q^{-1}X) =\frac{6}{\pi^2 \psi(Q)} X+O\left( \frac{\varphi(Q)}{Q} \log X \right). \end{align} $$

4.2 Approximating $F_2(Q,X)$

We can now easily recover an estimate for $F_2(Q,X)$ originally derived in [Reference Suryanarayana13]. We do this for the sake of completeness as [Reference Suryanarayana13] is not easily available. Let

$$\begin{align*}\delta_d(n) = \begin{cases} 1, & \text{if}\ d \mid n,\cr 0, & \text{if}\ d \nmid n, \end{cases} \end{align*}$$

be the characteristic function of the set of integer multiplies of an integer $d\ne 0$ . Then

$$ \begin{align*} \sum_{\substack{n \leq X\\ \gcd(n,Q)=1}} \frac{\varphi(n)}{n} &= \sum_{n \leq X} \prod_{p\mid Q} \left(1 - \delta_p(n)\right) \frac{\varphi(n)}{n} = \sum_{n \leq X} \sum_{d\mid Q} \mu(d)\delta_d(n) \frac{\varphi(n)}{n} \cr &= \sum_{d\mid Q} \mu(d) \sum_{n \leq X/d} \frac{\varphi(dn)}{dn} = \sum_{d\mid Q} \mu(d) G(d, X/d). \end{align*} $$

We can now use (4.3) and then the multiplicativity of $\psi (d)$ to obtain

$$ \begin{align*} \sum_{\substack{n \leq X\\ \gcd(n,Q)=1}} \frac{\varphi(n)}{n} &= \frac{6}{\pi^2}X \sum_{d\mid Q} \mu(d)\frac{1}{\psi(d)} + O\left(\sum_{d\mid Q} |\mu(d)| \frac{\varphi(d)}{d} \log X \right) \cr &= \frac{6}{\pi^2} X \prod_{p\mid Q} \left(1 - \frac{1}{\psi(p)}\right) + O\left( 2^{\omega(Q)} \log X \right) \cr \end{align*} $$

since

$$\begin{align*}\sum_{d\mid Q} |\mu(d)| \frac{\varphi(d)}{d} \le \sum_{d\mid Q} |\mu(d)| = 2^{\omega(Q)}, \end{align*}$$

where $\omega (Q)$ is the number of prime divisors of Q.

A simple computation shows that

$$\begin{align*}\prod_{p\mid Q} \left(1 - \frac{1}{\psi(p)}\right) = \prod_{p\mid Q} \left(1 - \frac{1}{p+1}\right) = \prod_{p\mid Q} \frac{1}{1+p^{-1}} = \frac{Q}{\psi(Q)}. \end{align*}$$

Therefore

$$ \begin{align*}\frac{1}{Q} \sum_{\substack{n \leq X\\ \gcd(n,Q)=1}} \frac{\varphi(n)}{n} = \frac{6}{\pi^2} \frac{X}{\psi(Q)} + O\left(2^{\omega(Q)} Q^{-1} \log X \right). \end{align*} $$

Therefore, using that $2^{\omega (Q)} \le \tau (Q) = Q^{o(1)}$ , we obtain

(4.5) $$ \begin{align} \begin{aligned} F_2(Q,X) & = \frac{6}{\pi^2} \frac{X - Q}{\psi(Q)} + O\left(Q^{-1+o(1)} \log X \right)\cr & = \frac{6}{\pi^2} \frac{X }{\psi(Q)} + O\left( 1+Q^{-1+o(1)} \log X \right) , \end{aligned} \end{align} $$

whence $\psi (Q) \ge Q$ .

4.3 Concluding the proof

Combining the bounds (4.4) and (4.5), we obtain the desired result.