Counting elements of the congruence subgroup

Abstract

We obtain asymptotic formulas for the number of matrices in the congruence subgroup

$$\begin{align*}\Gamma_0(Q) = \left\{ A\in\operatorname{SL}_2({\mathbb Z}):~c \equiv 0 \quad\pmod Q\right\}, \end{align*}$$

which are of naive height at most X. Our result is uniform in a very broad range of values Q and X.

1 Introduction and the main result

Given an integer $Q\ge 1$ , we consider the congruence subgroup

$$\begin{align*}\Gamma_0(Q) = \left\{ A\in\operatorname{SL}_2({\mathbb Z}):~c \equiv 0 \quad\pmod Q\right\}, \end{align*}$$

where

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

We are interested in counting matrices $A\in \Gamma _0(Q) $ with entries of size at most

(1.1) $$ \begin{align} \|A\|_\infty = \max\{|a|, |b|, |c|, |d|\} \le X. \end{align} $$

The question is a natural generalization of the classical counting result of Newman [10] concerning matrices $A \in \operatorname {SL}_2({\mathbb Z})$ with

(1.2) $$ \begin{align} \|A\|_2 = a^2 + b^2 + c^2 + d^2\le X, \end{align} $$

and of Krieg [9] who counts matrices $A \in \operatorname {SL}_2({\mathbb Z})$ with respect to the $L^\infty $ -norm as (1.1). We note that both of these results correspond to $Q=1$ .

We note that while we can also use the $L^2$ -norm as in (1.2) to measure the “size” of $A\in \operatorname {SL}_2({\mathbb Z})$ , for us it is more convenient to use the $L^\infty $ -norm as in (1.1). However, our main purpose to have an asymptotic formula in a broad range of uniformity with respect to the size of Q compared to X.

Let

$$\begin{align*}\Gamma_0(Q,X)= \{A \in \Gamma_0(Q):~\|A\|_\infty \le X\}. \end{align*}$$

The question of investigating the cardinality $\# \Gamma _0(Q, X)$ has been raised in [3], where it is also shown that for $Q\le X$ , we have

$$\begin{align*}\# \Gamma_0(Q, X) = X^{2+o(1)} Q^{-1}. \end{align*}$$

We are interested in obtaining an asymptotic formula for the cardinality $\# \Gamma _0(Q,X)$ in a broad range of Q and X. Furthermore, our bound on error term relies on some results of Ustinov [14], which go beyond standard techniques.

We first give an asymptotic formula for $\# \Gamma _0(Q, X) $ with the main term expressed via sums of some standard arithmetic functions. For this, we also define

$$\begin{align*}F(Q,X) = 8 \left(F_1(Q,X) + F_2(Q,X)\right), \end{align*}$$

where

$$ \begin{align*} F_1(Q,X) & = \sum_{1 \le c \le X/Q} \frac{\varphi(cQ)}{cQ}, \cr F_2(Q,X) & = Q^{-1} \sum_{\substack{Q< x \le X\\ \gcd(x, Q) = 1}} \frac{\varphi(x)}{x} , \end{align*} $$

where as usual $\varphi (k)$ denotes the Euler function.

Theorem 1.1 Uniformly over an integer $Q\ge 1$ and a positive real $X\ge Q$ , we have

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

Next, we study the function $F(Q,X)$ . As indicated to us by one the referees, the sum $F_2(Q,X)$ has already been computed in [13]. When Q is fixed a much more general result is given in [11, Theorem 5.5A.1]. We have not, however, been able to locate references for an asymptotic formula for $F_1(Q,X)$ with the desired level of uniformity in Q, so we derive one in this paper (see 4.4). For this, we first recall the definition of the Dedekind function

$$\begin{align*}\psi(Q) = Q \prod_{\substack{p\mid Q\\ p~\mathrm{prime}}} \left(1+\frac{1}{p}\right). \end{align*}$$

Theorem 1.2 Uniformly over an integer $Q\ge 1$ and a positive real $X\ge Q$ , we have

$$\begin{align*}F(Q, X) = \frac{96}{\pi^2} \cdot \frac{X}{ \psi(Q)} + O\left(Q^{o(1)}\log X\right). \end{align*}$$

Combining Theorems 1.1 and 1.2, we obtain the following asymptotic formula.

Corollary 1.3 Uniformly over an integer $Q\ge 1$ and a positive real $X\ge Q$ ,

$$\begin{align*}\# \Gamma_0(Q, X) = \frac{96}{\pi^2} \cdot \frac{X^2}{ \psi(Q)} + O\left(X^{5/3+o(1)} Q^{-1} + X \log X\right). \end{align*}$$

We remark that the appearance of the Dedekind function $\psi (Q)$ in the denominator of the asymptotic formula for $\# \Gamma _0(Q, X)$ in Corollary 1.3 is not surprising as function itself appears in as the index of $\Gamma _0(Q)$ in $\operatorname {SL}_2({\mathbb Z})$ , that is,

$$\begin{align*}[\operatorname{SL}_2({\mathbb Z}): \Gamma_0(Q)] = \psi(Q) \end{align*}$$

(see [8, Proposition 2.5]).

Elementary estimates easily show that $\psi (Q) = Q^{1+o(1)}$ . Thus, Corollary 1.3 is nontrivial in an essentially full range of Q and X, namely for $Q \le X^{1-\varepsilon }$ for a fixed $\varepsilon> 0$ .

2 Preparations

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 [6, 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 [6, 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 [12, 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 [14] 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 [14], 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 [12] and also more recent works [1, 2, 4, 5, 7, 15].

3 Proof of Theorem 1.1

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 Proof of Theorem 1.2

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 [13]. We do this for the sake of completeness as [13] 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.

5 Comments

We presented our result, Corollary 1.3 as a direct consequence of Theorems 1.1 and 1.2 of very different nature with error terms of different strength. This makes it apparent that Theorem 1.1 is the bottleneck to further improvements of Corollary 1.3.

The methods of this work can also be used for counting elements of bounded norm of other congruence subgroup such as

$$\begin{align*}\Gamma(Q) = \left\{ \begin{bmatrix} a & b \cr c & d \cr \end{bmatrix} \in\operatorname{SL}_2({\mathbb Z}):~ a,d \equiv 1 \quad\pmod Q, \ b,c \equiv 0 \quad\pmod Q\right\} \end{align*}$$

and

$$\begin{align*}\Gamma_1(Q) = \left\{ \begin{bmatrix} a & b \cr c & d \cr \end{bmatrix} \in\operatorname{SL}_2({\mathbb Z}):~ a,d\equiv 1 \quad\pmod Q, \ c \equiv 0 \quad\pmod Q\right\}. \end{align*}$$

One can also adjust our approach to counting matrices of restricted size with respect to other natural matrix norms.