# Geometry and distribution of roots of $\mu^{2}\equiv D\bmod m$ with $D\equiv
1\bmod 4$

Zonglin Li111Funded by China Scholarship Council School of Mathematics,
University of Bristol, Bristol BS8 1UG, U.K.  Matthew Welsh222Supported by
EPSRC grant EP/S024948/1 Department of Mathematics, University of Maryland, MD
20742-5025, U.S.

(28 April 2023)

###### Abstract

We extend the geometric interpretation of the roots of the quadratic
congruence $\mu^{2}\equiv D\pmod{m}$ as the tops of certain geodesics in the
hyperbolic plane to the case when $D$ is square-free and $D\equiv 1\pmod{4}$.
This allows us to establish limit laws for the fine-scale statistics of the
roots using results by Marklof and the second author.

###### Contents

  1. 1 Introduction
  2. 2 Geodesics and roots of quadratic congruences
  3. 3 Congruence subgroups
  4. 4 Pair correlation density
  5. 5 Negative $D$

##  1 Introduction

The recent paper [11] by Marklof and the second author established limit laws
for the fine-scale distribution of the roots of the quadratic congruence
$\mu^{2}\equiv D\pmod{m}$, ordered by the modulus $m$, where $D$ is a square-
free positive integer and $D\not\equiv 1\pmod{4}$. This is achieved by
relating the roots (when $D>0$) to the tops of certain geodesics in the
Poincaré upper half-plane
$\mathbb{H}=\\{z\in\mathbb{C}:\operatorname{Im}z>0\\}$ and (when $D<0$) to
orbits of points, under the action of the modular group. Previous studies of
quadratic congruences by means of the spectral theory of automorphic forms
include the works of Bykovskii [3], Duke, Friedlander and Iwaniec [4], Hejhal
[5] and many others (see [11] for further context and references).

Geodesics in $\mathbb{H}$ are either vertical lines or semi-circles centred on
the real line, and in the latter case we say that a geodesic is positively
oriented if it is traced from left to right. Letting $z_{\bm{c}}$ denote the
top of a positively oriented geodesic $\bm{c}$, i.e. the point on $\bm{c}$
with the largest imaginary part, the correspondence established in [11] is
that for $D$ positive, square-free and $D\not\equiv 1\pmod{4}$, there is a
finite set of geodesics $\\{\bm{c}_{1},\dots,\bm{c}_{h}\\}$ such that

$z_{\gamma\bm{c}_{l}}\equiv\frac{\mu}{m}+\mathrm{i}\frac{\sqrt{D}}{m}\pmod{\Gamma_{\infty}}$
(1.1)

parametrizes all the roots $\mu\bmod m$ as $l$ varies over $1\leq l\leq h$ and
$\gamma$ varies over the double cosets
$\Gamma_{\infty}\backslash\operatorname{SL}(2,\mathbb{Z})/\Gamma_{\bm{c}_{l}}$
such that $\gamma\bm{c}_{l}$ is positively oriented. Here
$\Gamma_{\bm{c}_{l}}$ is the stabilizer in $\operatorname{SL}(2,\mathbb{Z})$
of the geodesic $\bm{c}_{l}$ (acting on $\mathbb{H}$ by fractional linear
transformations) and

$\Gamma_{\infty}=\left\\{\pm\begin{pmatrix}1&k\\\
0&1\end{pmatrix}:k\in\mathbb{Z}\right\\}$ (1.2)

is the stabilizer in $\operatorname{SL}(2,\mathbb{Z})$ of the boundary point
$\infty\in\partial\mathbb{H}$. Moreover, it is established that, for a fixed
root $\nu\bmod n$, the subset of the roots $\mu\bmod m$ satisfying $m\equiv
0\pmod{n}$ and $\mu\equiv\nu\pmod{n}$ is parametrized in the same way by (1.1)
with $\operatorname{SL}(2,\mathbb{Z})$ replaced by the congruence subgroups

$\Gamma_{0}(n)=\left\\{\begin{pmatrix}a&b\\\
c&d\end{pmatrix}\in\operatorname{SL}(2,\mathbb{Z}):c\equiv 0\pmod{n}\right\\}$
(1.3)

and a possibly different finite set of geodesics
$\\{\bm{c}_{1},\dots,\bm{c}_{h}\\}$.

In this paper, we extend this geometric realization of the roots to remove the
restriction $D\not\equiv 1\pmod{4}$, obtaining the following theorem.

######  Theorem 1.

Let $D>0$ be a square-free integer satisfying $D\equiv 1\pmod{4}$. Given $n>0$
and $\nu\bmod n$ with $\nu^{2}\equiv D\pmod{n}$, there exists a finite set of
geodesics $\\{\bm{c}_{1},\cdots,\bm{c}_{h}\\}$, having the following
properties:

  1. (i)

For any positive integer $m$ and $\mu\bmod m$ satisfying $\mu^{2}\equiv
D\pmod{m}$, $m\equiv 0\pmod{n}$, and $\mu\equiv\nu\pmod{n}$, there exists a
unique $k$ and a double coset
$\Gamma_{\infty}\gamma\Gamma_{\bm{c}_{k}}\in\Gamma_{\infty}\backslash\Gamma_{0}(n)/\Gamma_{\bm{c}_{k}}$
with $\gamma\bm{c}_{k}$ positively oriented such that

$z_{\gamma\bm{c}_{k}}\equiv\frac{\mu}{m}+\mathrm{i}\frac{\sqrt{D}}{m}\pmod{\Gamma_{\infty}}.$
(1.4)

  2. (ii)

Conversely, given $k$ and a double coset
$\Gamma_{\infty}\gamma\Gamma_{\bm{c}_{k}}\in\Gamma_{\infty}\backslash\Gamma_{0}(n)/\Gamma_{\bm{c}_{k}}$
with positively oriented $\gamma\bm{c}_{k}$, there exists a unique positive
integer $m$ and $\mu\bmod m$ satisfying $\mu^{2}\equiv D\pmod{m}$, $m\equiv
0\pmod{n}$, and $\mu\equiv\nu\pmod{n}$ such that (1.4) holds.

The main difficulty in the proof of Theorem 1 is that when $D\equiv
1\pmod{4}$, the quadratic order $\mathbb{Z}[\sqrt{D}]$ is not maximal; the
ring of integers of $\mathbb{Q}(\sqrt{D})$ with $D\equiv 1\pmod{4}$ is the
larger order $\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$. This complicates the
situation because not all ideals in $\mathbb{Z}[\sqrt{D}]$ are invertible, and
so do not correspond naturally with geodesics in $\mathbb{H}$. We resolve this
by simultaneously considering ideals (and their corresponding geodesics) from
the two orders $\mathbb{Z}[\sqrt{D}]$ and $\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$.
In fact, ideals in the two orders correspond to two complementary subsets of
roots, see Theorems 22 and 23 below.

Figure 1: Theoretical pair correlation total densities $\omega_{5}$ (left,
black curve) and $\omega_{17}$ (right, black curve) compared to their
experiments (gray histograms) with $N=10^{6}$.

Having Theorem 1, we may apply the results of [11] to study the fine-scale
distribution of these roots. Specifically, we let $\\{x_{j}\\}_{j=1}^{\infty}$
denote the sequence of normalized roots
$\frac{\mu}{m}\in\mathbb{T}=\mathbb{R}/\mathbb{Z}$ satisfying $m\equiv
0\pmod{n}$ and $\mu\equiv\nu\pmod{n}$ for a fixed root $\nu^{2}\equiv
D\pmod{n}$. Here we order by the modulus, with the ordering of the roots with
the same modulus being inconsequential. For example, with $D=5$, $n=1$ and
$\nu=0$, our sequence would begin

$\left\\{\frac{0}{1},\frac{1}{2},\frac{1}{4},\frac{3}{4},\frac{0}{5},\frac{5}{10},\frac{4}{11},\frac{7}{11},\dots\right\\}.$
(1.5)

We remark that it has been proved by Hooley [6] that these sequences (without
the congruence restrictions, i.e. for $n=1$, $\nu=0$) are uniformly
distributed mod $1$ if $D$ is not a perfect square. We also remark that the
uniform distribution of the subsequence with $m\equiv 0\pmod{n}$ was proved by
Iwaniec [7], where it was a crucial input to proving that the polynomial
$x^{2}+1$, for example, is infinitely often a product of at most two primes.

Having understood the uniform distribution of the sequence $\frac{\mu}{m}$, it
is natural to investigate its pseudo-randomness properties, in particular the
fine-scale statistics. An attractive example of such a statistic is the pair
correlation function $R_{N,\nu,n}^{2}(I)$, which for a finite interval
$I\subset\mathbb{R}$ is defined by

$R_{N,\nu,n}^{2}(I)=\frac{1}{N}\\#\\!\left\\{1\leq i\neq j\leq
N:x_{i}-x_{j}\in N^{-1}I+\mathbb{Z}\right\\}.$ (1.6)

Theorem 1 together with theorem $4.10$ in [11] shows the existence of a
limiting density function $\omega_{D,\nu,n}$ for the pair correlation
function.

######  Theorem 2.

Let $D>0$ be a square-free integer with $D\equiv 1\pmod{4}$ and $\nu\bmod n$
satisfy $\nu^{2}\equiv D\pmod{n}$. Then there exists an even and continuous
function $\omega_{D,\nu,n}:\mathbb{R}\to\mathbb{R}_{\geq 0}$ such that for any
bounded interval $I\subseteq\mathbb{R}$,

$\lim_{N\to\infty}R_{N,\nu,n}^{2}(I)=\int_{I}\omega_{D,\nu,n}(t)\,dt.$ (1.7)

Figure 2: Theoretical pair correlation partial densities
$\omega_{5,\mathcal{O}_{1}}$ (left, black curve) for $m\not\equiv 2\pmod{4}$
and $\omega_{5,\mathcal{O}_{2}}$ (right, black curve) for $m\equiv 2\pmod{4}$
compared to their experiments (gray histograms) with $N=10^{6}$.

As in [11], the methods in fact give an explicit expression for the density
functions $\omega_{D,\nu,n}$. Moreover, we provide a somewhat simplified
expression than that in [11], see section 4. The figures 1, 2 and 3 show plots
of the density functions $\omega_{D,\nu,n}$ together with numerical
experiments. For comparison, we remark that the pair correlation density for a
Poisson point process would be the constant function $\omega(t)=1$, while the
normalized eigenvalues of a large random matrix and (conjecturally) the zeros
of the Riemann zeta function have pair correlation density
$\omega(t)=1-(\frac{\sin\pi t}{\pi t})^{2}$.

In Figures 1, 2 and 3, the pair correlation total density
$\omega_{D}=\omega_{D,0,1}$ considers the sequence of all roots
$\frac{\mu}{m}$ of $\mu^{2}\equiv D\pmod{m}$, while the pair correlation
partial density $\omega_{D,\mathcal{O}_{1}}$ is for the subsequence of the
roots $\frac{\mu}{m}$ corresponding to ideals in the ring
$\mathcal{O}_{1}=\mathbb{Z}[\sqrt{D}]$, while the partial density
$\omega_{D,\mathcal{O}_{2}}$ is for the subsequence of the roots
$\frac{\mu}{m}$ corresponding to ideals in the ring
$\mathcal{O}_{2}=\mathbb{Z}[\tfrac{1+\sqrt{D}}{2}]$. An explicit condition on
the roots determining which subset they belong to is given in Lemma 4, and in
the case that $D\equiv 5\pmod{8}$, can be reduced to a congruence condition on
$m$, see Lemma 7.

We can in fact prove limit distributions for a wide variety of fine-scale
statistics in addition to the pair correlation. We let $\lambda$ be a Borel
probability measure on $\mathbb{T}$ and $X$ be a random variable distributed
according to $\lambda$. We then define the following random counting measure,
or random point process,

$\Xi_{N,\lambda,\nu,n}=\sum_{k\in\mathbb{Z}}\sum_{j=1}^{N}\delta_{N(x_{j}-X+k)},$
(1.8)

where $\delta_{y}$ is a Dirac measure at $y\in\mathbb{R}$. Given a non-
negative integer $k$ and $I\subseteq\mathbb{R}$, we further denote the
counting functions

$\mathcal{N}_{I,\nu,n}(x,N)=\\#\\!\left\\{1\leq j\leq N:x_{j}-x\in
N^{-1}I+\mathbb{Z}\right\\},$ (1.9)

so that

$\mathbb{P}(\Xi_{N,\lambda,\nu,n}(I)=k)=\lambda(\\{x\in\mathbb{T}:\mathcal{N}_{I,\nu,n}(x,N)=k\\}).$
(1.10)

The next theorem can be proved by applying theorem $2.1$ in [11].

Figure 3: Theoretical pair correlation partial densities
$\omega_{17,\mathcal{O}_{1}}$ (left, black curve) with either $m$ or
$\frac{D-\mu^{2}}{m}$ odd, and $\omega_{17,\mathcal{O}_{2}}$ (right, black
curve) with both $m$ and $\frac{D-\mu^{2}}{m}$ even compared to their
experiments (gray histograms) with $N=10^{6}$.

######  Theorem 3.

Let $D>0$ be a square-free integer with $D\equiv 1\pmod{4}$ and $\nu\bmod n$
satisfy $\nu^{2}\equiv D\pmod{n}$. Then there exists a random point process
$\Xi_{\nu,n}$ (depending only on $\nu,n$ and $D$) such that for any Borel
probability measure $\lambda$ absolutely continuous with respect to Lebesgue
measure,

$\lim_{N\to\infty}\Xi_{N,\lambda,\nu,n}=\Xi_{\nu,n}.$ (1.11)

In particular, given $k_{j}\in\mathbb{N}$ and bounded interval
$I_{j}\subseteq\mathbb{R}$, then

$\lim_{N\to\infty}\lambda(\\{x\in\mathbb{T}:N_{I_{j},\nu,n}(x,N)=k_{j},\forall\,1\leq
j\leq r\\})=\mathbb{P}(\Xi_{\nu,n}(I_{j})=k_{j},\forall\,1\leq j\leq r),$
(1.12)

which is a continuous function of the endpoints of $I_{j}$.

The problem becomes simpler when considering negative $D$. Our results still
hold by considering the fine-scale distribution of real parts of hyperbolic
lattice points instead of tops of geodesics, see [10, 12] and section 5 below.
Moreover, these are closely related to the study of the distribution of angles
in hyperbolic lattices, see [1, 2, 8, 13].

We start in section 2 by establishing the connection between the roots
$\frac{\mu}{m}$ and the tops of geodesics in the Poincaré upper half-plane
$\mathbb{H}$. The main result of this section is a proof of Theorem 1 in the
special case $n=1$ and $\nu=0$. This restriction is removed, and so Theorem 1
is proved, in section 3, where we investigate the orbits of geodesics under
the congruence subgroups (1.3). In section 4 we record some observations about
the explicit expression for the pair correlation obtained in [11], and we
close the paper in section 5 with some remarks on analogous results in the
case that $D$ is negative.

Acknowledgement. The authors would like to thank Jens Marklof for his valuable
suggestions and encouragement.

##  2 Geodesics and roots of quadratic congruences

A convenient model for the hyperbolic plane is the Poincaré upper half-plane

$\mathbb{H}=\\{x+\mathrm{i}y\in\mathbb{C}:y>0\\}$ (2.1)

equipped with the metric

$\differential s^{2}=\frac{1}{y^{2}}(\differential x^{2}+\differential
y^{2}).$ (2.2)

The special linear group $G=\operatorname{SL}(2,\mathbb{R})$, consisting of
$2\times 2$ matrices with real entries and determinant one, acts on
$\mathbb{H}$ by Möbius transformations

$g=\begin{pmatrix}a&b\\\ c&d\end{pmatrix}:z\mapsto\frac{az+b}{cz+d}.$ (2.3)

We can in fact identify the projective special linear group
$\operatorname{PSL}(2,\mathbb{R})=G/\\{\pm I\\}$ with the unit tangent bundle
$\mathrm{T}_{1}(\mathbb{H})$ of the hyperbolic plane via

$\pm g=\pm\begin{pmatrix}a&b\\\
c&d\end{pmatrix}\mapsto\left(\frac{a\mathrm{i}+b}{c\mathrm{i}+d},\frac{\mathrm{i}}{(c\mathrm{i}+d)^{2}}\right),$
(2.4)

where we have expressed $\mathrm{T}_{1}(\mathbb{H})$ as the set of pairs of
complex numbers $(z,w)$ with $z\in\mathbb{H}$ and $|w|=\operatorname{Im}z$ (so
$w$ has length $1$ with respect to the metric (2.2)). We will however work
with $G$ directly and only emphasize the difference between $G$ and
$\mathrm{T}_{1}(\mathbb{H})$ when there is a chance of confusion. We note that
the correspondence (2.4) is conveniently expressed in terms of the Iwasawa
coordinates:

$\begin{pmatrix}1&x\\\ 0&1\end{pmatrix}\begin{pmatrix}y^{\frac{1}{2}}&0\\\
0&y^{-\frac{1}{2}}\end{pmatrix}\begin{pmatrix}\cos\frac{\theta}{2}&-\sin\frac{\theta}{2}\\\
\sin\frac{\theta}{2}&\cos\frac{\theta}{2}\end{pmatrix}\mapsto\left(x+\mathrm{i}y,\mathrm{i}y\mathrm{e}^{-\mathrm{i}\theta}\right),$
(2.5)

so here $\theta$ measures the angle clockwise from vertical.

Geodesics in $\mathbb{H}$ are either vertical lines or semi-circles centred on
the real line. An oriented geodesic $\bm{c}\subset\mathbb{H}$ is parametrized
by

$\bm{c}=\left\\{g\begin{pmatrix}s&0\\\
0&s^{-1}\end{pmatrix}\mathrm{i}:s>0\right\\}$ (2.6)

for some $g\in G$. We let $\bm{c}_{0}$ denote the vertical geodesic through
$\mathrm{i}$, which corresponds to $g=I$ in (2.6). Any geodesic can be written
as $\bm{c}=g\bm{c}_{0}$ for some $g\in G$.

We say that a geodesic $\bm{c}$ as in (2.6) is positively oriented if the
backwards endpoint $\bm{c}^{-}$ corresponding to $s\to 0$ is less than the
forward endpoint $\bm{c}^{+}$ corresponding to $s\to\infty$, i.e. if the
geodesic is traced from left to right. In this case, we define the point
$z_{\bm{c}}\in\mathbb{H}$ to be the point on $\bm{c}$ with the largest
imaginary part, and we accordingly refer to it as the top of the geodesic. We
leave $z_{\bm{c}}$ undefined for vertical or negatively oriented geodesics.

We let $\Gamma=\operatorname{SL}(2,\mathbb{Z})$, and we denote by
$\Gamma_{\infty}$ the stabilizer in $\Gamma$ of the boundary point
$\infty\in\partial\mathbb{H}$. Explicitly,

$\Gamma_{\infty}=\Gamma\cap\left\\{\pm\begin{pmatrix}1&x\\\
0&1\end{pmatrix}:x\in\mathbb{R}\right\\}=\left\\{\pm\begin{pmatrix}1&n\\\
0&1\end{pmatrix}:n\in\mathbb{Z}\right\\}.$ (2.7)

For a geodesic $\bm{c}=g\bm{c}_{0}$, we let $\Gamma_{\bm{c}}$ be the
stabilizer of $\bm{c}$ in $\Gamma$, so

$\Gamma_{\bm{c}}=\Gamma\cap\left\\{\pm g\begin{pmatrix}s&0\\\
0&s^{-1}\end{pmatrix}g^{-1}:s>0\right\\}.$ (2.8)

If $\bm{c}$ projects to a closed geodesic on the surface
$\Gamma\backslash\mathbb{H}$, then $\Gamma_{\bm{c}}$ is infinite cyclic, up to
sign:

$\Gamma_{\bm{c}}=\left\\{\pm g\begin{pmatrix}\varepsilon^{k}&0\\\
0&\varepsilon^{-k}\end{pmatrix}g^{-1}:k\in\mathbb{Z}\right\\},$ (2.9)

for some $\varepsilon>1$, and the length of $\bm{c}$ in
$\Gamma\backslash\mathbb{H}$ is then $2\log\varepsilon$.

###  2.1 Roots and ideals

We recall that since $D\equiv 1\pmod{4}$, the quadratic order
$\mathbb{Z}[\sqrt{D}]$ is not maximal, i.e. it is not the ring of integers of
$\mathbb{Q}(\sqrt{D})$. As such, not all ideals in $\mathbb{Z}[\sqrt{D}]$ are
invertible. The following lemma gives a criterion to determine if an ideal is
invertible. Here $(\alpha_{1},\dots,\alpha_{k})$ denotes the ideal of a ring
(which will be made clear by the context) generated by the ring elements
$\alpha_{j}$.

######  Lemma 4.

Let $D>0$ be a square-free integer satisfying $D\equiv 1\pmod{4}$ and
$\mu\bmod m$ satisfy $\mu^{2}\equiv D\pmod{m}$. Then the ideal
$I=(m,\sqrt{D}+\mu)\subseteq\mathbb{Z}[\sqrt{D}]$ is invertible if and only if
either $m$ or $\frac{D-\mu^{2}}{m}$ is odd. Moreover, in this case the inverse
ideal of $I$ is given by $I^{-1}=\frac{1}{m}(m,\sqrt{D}-\mu)$.

Before the proof we make the following remarks: First, the parity of
$\frac{D-\mu^{2}}{m}$ is well-defined only if $m$ is even, so the phrase
“either $m$ or $\frac{D-\mu^{2}}{m}$ is odd” would be more correctly stated as
“either $m$ is odd or $m$ is even and $\frac{D-\mu^{2}}{m}$ is odd.” Second,
the proof of Proposition 5 below shows that any ideal
$I\subseteq\mathbb{Z}[\sqrt{D}]$ can be expressed as a rational integer
multiple of an ideal $(m,\sqrt{D}+\mu)$ as in the lemma.

###### Proof.

Let $\overline{I}$ denote the ideal
$(m,\sqrt{D}-\mu)\subseteq\mathbb{Z}[\sqrt{D}]$. We have

$\displaystyle I\overline{I}$
$\displaystyle=(m^{2},m(\sqrt{D}+\mu),m(\sqrt{D}-\mu),D-\mu^{2})$ (2.10)
$\displaystyle=m(m,\sqrt{D}+\mu,\sqrt{D}-\mu,(D-\mu^{2})/m)$
$\displaystyle=m(m,2\mu,\sqrt{D}-\mu,(D-\mu^{2})/m),$

so $m(m,2\mu,\frac{D-\mu^{2}}{m})\subseteq I\overline{I}\subseteq
m\mathbb{Z}[\sqrt{D}]$.

Now suppose that $p\neq 2$ divides all of $m,2\mu$ and $\frac{D-\mu^{2}}{m}$.
Then $p^{2}$ divides $D=m\frac{D-\mu^{2}}{m}+\mu^{2}$, which contradicts $D$
being square-free. It follows that if either $m$ or $\frac{D-\mu^{2}}{m}$ is
odd, then $\gcd(m,2\mu,\frac{D-\mu^{2}}{m})=1$, and so
$(m,2\mu,\frac{D-\mu^{2}}{m})=\mathbb{Z}[\sqrt{D}]$. Therefore
$I\overline{I}=m\mathbb{Z}[\sqrt{D}]$, i.e. $I^{-1}=\frac{1}{m}\overline{I}$.

Conversely, we assume $m$ and $\frac{D-\mu^{2}}{m}$ are even. Dividing (2.10)
by $m$, we obtain

$\displaystyle\frac{1}{m}I\overline{I}$
$\displaystyle=(m,2\mu,\mu+\sqrt{D},(D-\mu^{2})/m)$ (2.11)
$\displaystyle=(2,\mu+\sqrt{D})=(2,1+\sqrt{D})$

as $\mu$ is odd. Letting $I_{0}=(2,1+\sqrt{D})$, we have

$\displaystyle I_{0}^{2}$
$\displaystyle=(2,1+\sqrt{D})^{2}=(4,2+2\sqrt{D},1+D+2\sqrt{D})$ (2.12)
$\displaystyle=2(2,1+\sqrt{D},(D-1)/2)=2I_{0}$

since $\frac{D-1}{2}$ is even. As $I_{0}\neq(2)$, it is therefore not
invertible, so either $I$ or $\overline{I}$ is not invertible, and it follows
that neither are as they are conjugate. ∎

We now turn to the correspondence between roots and ideals.

######  Proposition 5.

Let $D\equiv 1\pmod{4}$ and let $I\subseteq\mathbb{Z}[\sqrt{D}]$ be an ideal
with no rational integer divisors greater than $1$. Then $I$ has a
$\mathbb{Z}$-basis $\\{\beta_{1},\beta_{2}\\}$, unique modulo the action of
$\Gamma_{\infty}$, with the form

$\begin{pmatrix}\beta_{1}\\\ \beta_{2}\end{pmatrix}=\begin{pmatrix}1&\mu\\\
0&m\\\ \end{pmatrix}\begin{pmatrix}\sqrt{D}\\\ 1\end{pmatrix},$ (2.13)

where $\mu^{2}\equiv D\pmod{m}$. Moreover, $I$ is invertible if and only if
either $m$ or $\frac{D-\mu^{2}}{m}$ is odd.

Conversely, given $\mu\bmod m$ such that $\mu^{2}\equiv D\pmod{m}$, the
sublattice of $\mathbb{Z}[\sqrt{D}]$ with $\mathbb{Z}$-basis
$\\{\beta_{1},\beta_{2}\\}$ given above is an ideal in $\mathbb{Z}[\sqrt{D}]$,
and this ideal is invertible if and only if either $m$ or
$\frac{D-\mu^{2}}{m}$ is odd.

###### Proof.

Any lattice $I\subseteq\mathbb{Z}[\sqrt{D}]$ has a unique basis
$\\{\beta_{1},\beta_{2}\\}$ in the Hermite normal form

$\begin{pmatrix}\beta_{1}\\\
\beta_{2}\end{pmatrix}=\begin{pmatrix}b_{1}&b_{2}\\\ 0&b_{3}\\\
\end{pmatrix}\begin{pmatrix}\sqrt{D}\\\ 1\end{pmatrix},$ (2.14)

where $b_{1}>0$ and $b_{2}>b_{3}\geq 0$. Left multiplying a matrix
$\gamma\in\Gamma_{\infty}$ on the basis is equivalent to adding multiples of
$b_{3}$ to $b_{2}$, so considering the basis modulo $\Gamma_{\infty}$ is the
same as considering $b_{2}\bmod{b_{3}}$.

Now, the sublattice $I$ is an ideal if and only if $\sqrt{D}I\subseteq I$, as
the quadratic order $\mathbb{Z}[\sqrt{D}]$ is generated by $\sqrt{D}$. The
basis of $\sqrt{D}I$ can be expressed by

$\displaystyle\begin{pmatrix}\sqrt{D}\beta_{1}\\\
\sqrt{D}\beta_{2}\end{pmatrix}$ $\displaystyle=\begin{pmatrix}b_{1}&b_{2}\\\
0&b_{3}\\\ \end{pmatrix}\begin{pmatrix}0&D\\\
1&0\end{pmatrix}\begin{pmatrix}b_{1}&b_{2}\\\
0&b_{3}\end{pmatrix}^{-1}\begin{pmatrix}\beta_{1}\\\ \beta_{2}\end{pmatrix}$
(2.15)
$\displaystyle=\frac{1}{b_{1}b_{3}}\begin{pmatrix}b_{2}b_{3}&-b_{2}^{2}+Db_{1}^{2}\\\
b_{3}^{2}&-b_{2}b_{3}\end{pmatrix}\begin{pmatrix}\beta_{1}\\\
\beta_{2}\end{pmatrix}.$

Hence $I$ is an ideal if and only if the entries of the matrix in the final
step are all integers. It is clear that we need $b_{1}\mid b_{2}$ and
$b_{1}\mid b_{3}$, so let $b_{2}=\mu b_{1}$ and $b_{3}=mb_{1}$. Moreover, $I$
not having rational integer divisors is equivalent to $b_{1}$, which we now
assume. From the top right entry, we obtain the constraint $\mu^{2}\equiv
D\pmod{m}$. Finally, with the assumption that $I=(m,\sqrt{D}+\mu)$ is
invertible in $\mathbb{Z}[\sqrt{D}]$, we have that either $m$ or
$\frac{D-\mu^{2}}{m}$ is odd by Lemma 4.

Conversely, suppose that $\mu\bmod m$ satisfies $\mu^{2}\equiv D\pmod{m}$.
Then (2.13) demonstrates that given the basis in the form above, the
sublattice $I$ satisfies $\sqrt{D}I\subseteq I$ as required. Moreover, if
either $m$ or $\frac{D-\mu^{2}}{m}$ is odd, Lemma 4 implies that $I$ is
invertible. ∎

We now turn to the roots that do not satisfy the invertibility condition of
Lemma 4. As it happens, these roots naturally correspond to ideals in the
maximal order $\mathbb{Z}[\tfrac{1+\sqrt{D}}{2}]$, where all ideals are
invertible.

######  Proposition 6.

Let $D\equiv 1\pmod{4}$ and let $J\subseteq\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$
be an ideal with no rational integer divisors greater than $1$. Then $J$ has a
$\mathbb{Z}$-basis $\\{\delta_{1},\delta_{2}\\}$, unique modulo the action of
$\Gamma_{\infty}$, with the form

$\begin{pmatrix}\delta_{1}\\\
\delta_{2}\end{pmatrix}=\begin{pmatrix}1&\frac{\mu-1}{2}\\\ 0&\frac{m}{2}\\\
\end{pmatrix}\begin{pmatrix}\frac{1+\sqrt{D}}{2}\\\ 1\end{pmatrix},$ (2.16)

where $\mu^{2}\equiv D\pmod{m}$ and both $m$ and $\frac{D-\mu^{2}}{m}$ are
even.

Conversely, given $\mu\bmod m$ such that $\mu^{2}\equiv D\pmod{m}$ and both
$m$ and $\frac{D-\mu^{2}}{m}$ are even, the sublattice of
$\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$ with $\mathbb{Z}$-basis
$\\{\delta_{1},\delta_{2}\\}$ given above is an ideal in
$\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$.

###### Proof.

As above, any lattice $J\subseteq\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$ has a
unique basis in Hermite normal form:

$\begin{pmatrix}\delta_{1}\\\
\delta_{2}\end{pmatrix}=\begin{pmatrix}b_{1}&b_{2}\\\ 0&b_{3}\\\
\end{pmatrix}\begin{pmatrix}\frac{1+\sqrt{D}}{2}\\\ 1\end{pmatrix},$ (2.17)

where $b_{1}>0$ and $b_{2}>b_{3}\geq 0$. The sublattice $J$ is an ideal if and
only if $\frac{1+\sqrt{D}}{2}J\subseteq J$. The basis of
$\frac{1+\sqrt{D}}{2}J$ can be expressed by

$\displaystyle\begin{pmatrix}\frac{1+\sqrt{D}}{2}\delta_{1}\\\
\frac{1+\sqrt{D}}{2}\delta_{2}\end{pmatrix}$
$\displaystyle=\begin{pmatrix}b_{1}&b_{2}\\\ 0&b_{3}\\\
\end{pmatrix}\begin{pmatrix}1&\frac{D-1}{4}\\\
1&0\end{pmatrix}\begin{pmatrix}b_{1}&b_{2}\\\
0&b_{3}\end{pmatrix}^{-1}\begin{pmatrix}\delta_{1}\\\ \delta_{2}\end{pmatrix}$
(2.18)
$\displaystyle=\frac{1}{b_{1}b_{3}}\begin{pmatrix}(b_{1}+b_{2})b_{3}&-(b_{1}+b_{2})b_{2}+\frac{D-1}{4}b_{1}^{2}\\\
b_{3}^{2}&-b_{2}b_{3}\end{pmatrix}\begin{pmatrix}\delta_{1}\\\
\delta_{2}\end{pmatrix}.$

As in the proof of Proposition 5, we need $b_{1}$ to divide both $b_{2}$ and
$b_{3}$ for the matrix to have integer entries, so we set $b_{2}=\nu b_{1}$
and $b_{3}=nb_{1}$, and as before we assume $b_{1}=1$.

From the top right entry, we obtain the quadratic congruence
$\nu^{2}+\nu\equiv\frac{D-1}{4}\pmod{n}$, which is equivalent to
$(2\nu+1)^{2}\equiv D\pmod{4}n$. Let $\mu=2\nu+1$ and $m=2n$, and note that
$\frac{D-\mu^{2}}{m}$ is even and $\mu^{2}\equiv D\pmod{m}$.

For the converse part, suppose that $\mu\bmod m$ satisfies $\mu^{2}\equiv
D\pmod{m}$ and both $m=2n$ and $\frac{D-\mu^{2}}{m}=2k$ are even. Further, we
set $\mu=2\nu+1$ as $m$ even implies $\mu$ is odd. We have
$4\nu^{2}+4\nu+1\equiv D\pmod{4n}$, so
$\nu^{2}+\nu\equiv\frac{D-1}{4}\pmod{n}$. From (2.16) it then follows that the
sublattice $J$ with basis $\\{\delta_{1},\delta_{2}\\}$ as above satisfies
$\frac{1+\sqrt{D}}{2}J\subseteq J$ as required. ∎

We record the following lemma, whose proof is obvious, that gives a simple
characterization of invertible ideals in the special case when $D\equiv
5\pmod{8}$.

######  Lemma 7.

Let $D\equiv 5\pmod{8}$ and $\mu\bmod m$ satisfy $\mu^{2}\equiv D\pmod{m}$.
Then $m$ is even and $\frac{D-\mu^{2}}{m}$ is odd if and only if $m\equiv
0\pmod{4}$. In particular, the ideal
$I=(m,\mu+\sqrt{D})\subseteq\mathbb{Z}[\sqrt{D}]$ is invertible if and only if
$m\not\equiv 2\pmod{4}$.

As $D\equiv 1\pmod{4}$ and $\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$ is the ring of
integers of the number field $\mathbb{Q}(\sqrt{D})$, we may define the narrow
class group of $\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$ in the usual way: the group
of fractional ideals of $\mathbb{Z}[\tfrac{1+\sqrt{D}}{2}]$ modulo ideals of
the form $\zeta\mathbb{Z}[\tfrac{1+\sqrt{D}}{2}]$ with
$\zeta\in\mathbb{Q}(\sqrt{D})$ totally positive. We recall that
$\zeta=a+b\sqrt{D}\in\mathbb{Q}(\sqrt{D})$ is said to be totally positive if
both $a+b\sqrt{D}>0$ and $a-b\sqrt{D}>0$.

We define the narrow class group of $\mathbb{Z}[\sqrt{D}]$ in the same way,
with the added restriction that the ideals are invertible. That is, the narrow
class group of $\mathbb{Z}[\sqrt{D}]$ is the group of invertible, fractional
ideals of $\mathbb{Z}[\sqrt{D}]$ modulo ideals of the form
$\xi\mathbb{Z}[\sqrt{D}]$ for some $\xi\in\mathbb{Q}(\sqrt{D})$ totally
positive. We let the narrow class numbers $h_{1}^{+}(D)$, respectively
$h_{2}^{+}(D)$, denote the order of the narrow class group in
$\mathbb{Z}[\sqrt{D}]$, respectively $\mathbb{Z}[\tfrac{1+\sqrt{D}}{2}]$.

We now use representatives of the narrow class groups to find new bases for
invertible ideals $I\subseteq\mathbb{Z}[\sqrt{D}]$ and ideals
$J\subseteq\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$. We fix representatives $I_{k}$,
$1\leq k\leq h_{1}^{+}(D)$ of the narrow class group of
$\mathbb{Z}[\sqrt{D}]$, so that given any invertible ideal
$I\subseteq\mathbb{Z}[\sqrt{D}]$, there exists a totally positive $\xi\in
I_{k}^{-1}$ such that $I=\xi I_{k}$.

To conveniently write a basis for $I$ using this equality, we embed
$\mathbb{Q}(\sqrt{D})$ inside $\mathbb{R}^{2}$ via

$a+b\sqrt{D}\mapsto(a+b\sqrt{D},a-b\sqrt{D}),$

so that $\mathbb{Z}[\sqrt{D}]$ and $\mathbb{Z}[\tfrac{1+\sqrt{D}}{2}]$ are
lattices in $\mathbb{R}^{2}$. For $\xi=a+b\sqrt{D}\in\mathbb{Q}(\sqrt{D})$, we
use the notation $\overline{\xi}=a-b\sqrt{D}$ to represent its conjugate.

According to this embedding, given a $\mathbb{Z}$-basis
$\\{\beta_{k1},\beta_{k2}\\}$ of $I_{k}$, we substitute

$\begin{pmatrix}\beta_{k1}\\\
\beta_{k2}\end{pmatrix}\rightarrow\mathfrak{B}_{k}=\begin{pmatrix}\beta_{k1}&\overline{\beta}_{k1}\\\
\beta_{k2}&\overline{\beta}_{k2}\end{pmatrix},$ (2.19)

and we may assume that $\det\mathfrak{B}_{k}>0$. Similarly, we write our basis
for $\mathbb{Z}[\sqrt{D}]$ as

$\begin{pmatrix}\sqrt{D}\\\
1\end{pmatrix}\rightarrow\begin{pmatrix}\sqrt{D}&-\sqrt{D}\\\
1&1\end{pmatrix}.$ (2.20)

In this notation, we have that the basis $\\{\xi\beta_{k1},\xi\beta_{k2}\\}$
of $\xi I_{k}$ corresponds to the matrix

$\begin{pmatrix}\xi\beta_{k1}&\overline{\xi}\overline{\beta}_{k1}\\\
\xi\beta_{k2}&\overline{\xi}\overline{\beta}_{k2}\end{pmatrix}=\mathfrak{B}_{k}\begin{pmatrix}\xi&0\\\
0&\overline{\xi}\end{pmatrix}.$ (2.21)

Let $\varepsilon_{1}>1$ be the generator of the group of totally positive
units of $\mathbb{Z}[\sqrt{D}]$, and we define

$\displaystyle\Gamma_{1;k}$
$\displaystyle=\left\\{\pm\mathfrak{B}_{k}\begin{pmatrix}\varepsilon_{1}^{s}&0\\\
0&\varepsilon_{1}^{-s}\end{pmatrix}\mathfrak{B}_{k}^{-1}:s\in\mathbb{Z}\right\\}$
(2.22)
$\displaystyle=\operatorname{SL}(2,\mathbb{Z})\cap\left\\{\pm\mathfrak{B}_{k}\begin{pmatrix}t&0\\\
0&t^{-1}\end{pmatrix}\mathfrak{B}_{k}^{-1}:t>0\right\\},$

since $I_{k}=\varepsilon I_{k}$ if and only if $\varepsilon$ is a unit of
$\mathbb{Z}[\sqrt{D}]$.

######  Proposition 8.

Let $D\equiv 1\pmod{4}$ and $\mu\bmod m$ satisfy $\mu^{2}\equiv D\pmod{m}$. If
either $m$ or $\frac{D-\mu^{2}}{m}$ is odd, then there exists a unique $1\leq
k\leq h_{1}^{+}(D)$ and a unique double coset
$\Gamma_{\infty}\gamma\Gamma_{1;k}\in\Gamma_{\infty}\backslash\operatorname{SL}(2,\mathbb{Z})/\Gamma_{1;k}$
such that

$\begin{pmatrix}1&\mu\\\ 0&m\end{pmatrix}\begin{pmatrix}\sqrt{D}&-\sqrt{D}\\\
1&1\end{pmatrix}=\gamma\mathfrak{B}_{k}\begin{pmatrix}\xi&0\\\
0&\overline{\xi}\end{pmatrix}$ (2.23)

for some totally positive $\xi$.

Conversely, if for
$\Gamma_{\infty}\gamma\Gamma_{1;k}\in\Gamma_{\infty}\backslash\operatorname{SL}(2,\mathbb{Z})/\Gamma_{1;k}$
there exists positive real numbers $\xi_{1}$, $\xi_{2}$ such that

$\gamma\mathfrak{B}_{k}\begin{pmatrix}\xi_{1}&0\\\
0&\xi_{2}\end{pmatrix}=\begin{pmatrix}1&*\\\ 0&*\\\
\end{pmatrix}\begin{pmatrix}\sqrt{D}&-\sqrt{D}\\\ 1&1\end{pmatrix},$ (2.24)

then in fact $\xi_{1}=\xi$ and $\xi_{2}=\overline{\xi}$ for some totally
positive $\xi\in I_{k}^{-1}$ and we have

$\gamma\mathfrak{B}_{k}\begin{pmatrix}\xi&0\\\
0&\overline{\xi}\end{pmatrix}=\begin{pmatrix}1&\mu\\\
0&m\end{pmatrix}\begin{pmatrix}\sqrt{D}&-\sqrt{D}\\\ 1&1\end{pmatrix},$ (2.25)

where $\mu\bmod m$ satisfies $\mu^{2}\equiv D\pmod{m}$ and either $m$ or
$\frac{D-\mu^{2}}{m}$ is odd.

###### Proof.

By Proposition 5, the left side of (2.23) gives a basis for an invertible
ideal $I\subseteq\mathbb{Z}[\sqrt{D}]$. Writing $I=\xi I_{k}$ for some $k$ and
totally positive $\xi\in\mathbb{Q}(\sqrt{D})$, we obtain another basis for $I$
as in (2.21). These bases must be related by some
$\gamma\in\operatorname{GL}(2,\mathbb{Z})$, giving (2.23). Furthermore, by
comparing the sign of determinants of both sides, we in fact have
$\gamma\in\Gamma=\operatorname{SL}(2,\mathbb{Z})$.

We note that considering $\mu$ as a residue class modulo $m$ is the same as
considering the coset $\gamma$ in $\Gamma_{\infty}\backslash\Gamma$. Moreover,
replacing $\xi$ up to multiplication by the group of totally positive units in
$\mathbb{Z}[\sqrt{D}]$ amounts to considering the coset $\gamma\Gamma_{1;k}$.
It follows that the double coset $\Gamma_{\infty}\gamma\Gamma_{1;k}$ is
uniquely determined.

Conversely, suppose that there exist positive real numbers $\xi_{1}$,
$\xi_{2}$ so that (2.24) holds. We let
$\\{\beta^{\prime}_{k1},\beta^{\prime}_{k2}\\}$ be a basis of $I_{k}^{-1}$ and
observe that via the embedding $\mathbb{Q}\to\mathbb{R}^{2}$, we may express
$(\xi_{1},\xi_{2})=c_{1}\beta^{\prime}_{k1}+c_{2}\beta^{\prime}_{k2}$ for some
real numbers $c_{1},c_{2}\in\mathbb{R}$. The claim that $\xi_{1}=\xi$ and
$\xi_{2}=\overline{\xi}$ for some totally positive $\xi\in I_{k}^{-1}$ is
equivalent to $c_{1},c_{2}$ being integers.

As $I_{k}^{-1}I_{k}=\mathbb{Z}[\sqrt{D}]$, we define integers $a_{kij}$ and
$b_{kij}$ by

$\beta^{\prime}_{ki}\beta_{kj}=a_{kij}+b_{kij}\sqrt{D}.$ (2.26)

This then yields

$\mathfrak{B}_{k}\begin{pmatrix}\xi_{1}&0\\\
0&\xi_{2}\end{pmatrix}=(c_{1}A_{k1}+c_{2}A_{k2})\begin{pmatrix}\sqrt{D}&-\sqrt{D}\\\
1&1\end{pmatrix},$ (2.27)

where

$A_{ki}=\begin{pmatrix}b_{ki1}&a_{ki1}\\\ b_{ki2}&a_{ki2}\end{pmatrix}.$
(2.28)

Hence,

$B_{k}\begin{pmatrix}c_{1}\\\
c_{2}\end{pmatrix}=\gamma^{-1}\begin{pmatrix}1\\\ 0\end{pmatrix},$ (2.29)

where

$B_{k}=\begin{pmatrix}b_{k11}&b_{k21}\\\ b_{k12}&b_{k22}\end{pmatrix}.$ (2.30)

That $c_{1}$ and $c_{2}$ are in fact integers now follows immediately from
Lemma 10, which we prove later. ∎

######  Lemma 9.

Let $M\in\mathrm{M}_{2}(\mathbb{Z})$. If the entries of $M\begin{pmatrix}a\\\
b\end{pmatrix}$ are coprime for any coprime integers $a$ and $b$, then
$M\in\operatorname{GL}(2,\mathbb{Z})$.

###### Proof.

As $M$ is a $2\times 2$ matrix with integer entries, it can be written in the
Smith normal form

$M=S_{1}\begin{pmatrix}\lambda_{1}&0\\\ 0&\lambda_{2}\end{pmatrix}S_{2},$
(2.31)

where $\lambda_{1},\lambda_{2}$ are non-negative integers and
$S_{1},S_{2}\in\operatorname{GL}(2,\mathbb{Z})$. By considering the first
column of the diagonal matrix, we have

$MS_{2}^{-1}\begin{pmatrix}1\\\ 0\end{pmatrix}=M\begin{pmatrix}a\\\
b\end{pmatrix}=\lambda_{1}S_{1}\begin{pmatrix}1\\\ 0\end{pmatrix},$ (2.32)

for some coprime integers $a$ and $b$. With the assumption on $M$, we must
have $\lambda_{1}=1$. By considering the second column, we similarly obtain
$\lambda_{2}=1$, and therefore, $M\in\operatorname{GL}(2,\mathbb{Z})$. ∎

######  Lemma 10.

For any $k$, we have $B_{k}=\begin{pmatrix}b_{k11}&b_{k21}\\\
b_{k12}&b_{k22}\end{pmatrix}\in\operatorname{GL}(2,\mathbb{Z})$.

###### Proof.

Let $a,b$ be any coprime integers. Then
$\xi^{\prime}=a\beta_{k1}^{\prime}+b\beta_{k2}^{\prime}$ is a primitive vector
in $I_{k}^{-1}$. Thus, the invertible ideal
$\xi^{\prime}I_{k}\subseteq\mathbb{Z}[\sqrt{D}]$ has no rational integer
divisors greater than $1$. By Proposition 5, $\xi^{\prime}I_{k}$ has a basis
of the form

$\begin{pmatrix}1&\mu^{\prime}\\\
0&m^{\prime}\end{pmatrix}\begin{pmatrix}\sqrt{D}&-\sqrt{D}\\\
1&1\end{pmatrix}=\gamma\mathfrak{B}_{k}\begin{pmatrix}\xi^{\prime}&0\\\
0&\overline{\xi^{\prime}}\end{pmatrix},$ (2.33)

arguing as we did in the proof of the first part of Proposition 8. By
considering the first column of (2.33), we have

$B_{k}\begin{pmatrix}a\\\ b\end{pmatrix}=\gamma^{-1}\begin{pmatrix}1\\\
0\end{pmatrix},$ (2.34)

for some $\gamma\in\operatorname{GL}(2,\mathbb{Z})$. As $a$ and $b$ are
arbitrary coprime integers, (2.34) shows that $B_{k}$ satisfies the condition
in Lemma 9. ∎

We now turn to ideals in $\mathbb{Z}[\tfrac{1+\sqrt{D}}{2}]$. For $1\leq l\leq
h_{2}^{+}(D)$, we fix representatives $J_{l}$ of the narrow class group of
$\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$. As before, for any ideal
$J\subseteq\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$ there exists a totally positive
$\zeta\in J_{l}^{-1}$ such that $J=\zeta J_{l}$. Using the embedding
$\mathbb{Q}(\sqrt{D})\to\mathbb{R}^{2}$, we associate a $\mathbb{Z}$-basis
$\\{\delta_{l1},\delta_{l2}\\}$ of $J_{l}$ with the matrix

$\begin{pmatrix}\delta_{l1}\\\
\delta_{l2}\end{pmatrix}\rightarrow\mathfrak{D}_{l}=\begin{pmatrix}\delta_{l1}&\overline{\delta}_{l1}\\\
\delta_{l2}&\overline{\delta}_{l2}\end{pmatrix},$ (2.35)

and as before we may assume $\det(\mathfrak{D}_{l})>0$. Thus, the basis
$\\{\zeta\delta_{l1},\zeta\delta_{l2}\\}$ of $\zeta J_{l}$ has basis matrix

$\begin{pmatrix}\zeta\delta_{l1}&\overline{\zeta}\overline{\delta}_{l1}\\\
\zeta\delta_{l2}&\overline{\zeta}\overline{\delta}_{l2}\end{pmatrix}=\mathfrak{D}_{l}\begin{pmatrix}\zeta&0\\\
0&\overline{\zeta}\end{pmatrix}.$ (2.36)

Letting $\varepsilon_{2}>1$ be the generator of the group of totally positive
units of $\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$. We define

$\displaystyle\Gamma_{2;l}$
$\displaystyle=\left\\{\pm\mathfrak{D}_{l}\begin{pmatrix}\varepsilon_{2}^{s}&0\\\
0&\varepsilon_{2}^{-s}\end{pmatrix}\mathfrak{D}_{l}^{-1}:s\in\mathbb{Z}\right\\}$
(2.37)
$\displaystyle=\operatorname{SL}(2,\mathbb{Z})\cap\left\\{\pm\mathfrak{D}_{l}\begin{pmatrix}t&0\\\
0&t^{-1}\end{pmatrix}\mathfrak{D}_{l}^{-1}:t>0\right\\},$

since $J_{l}=\varepsilon J_{l}$ if and only if $\varepsilon$ is a unit of
$\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$.

Using Proposition 6 in place of Proposition 5, we obtain the following
analogue of Proposition 8. We omit its proof as it is so similar to the proof
above.

######  Proposition 11.

Let $D\equiv 1\pmod{4}$ and suppose $\mu\bmod m$ satisfies $\mu^{2}\equiv
D\pmod{m}$. If both $m$ and $\frac{D-\mu^{2}}{m}$ are even, then there exists
a unique $1\leq l\leq h_{2}^{+}(D)$ and a unique double coset
$\Gamma_{\infty}\gamma\Gamma_{2;l}\in\Gamma_{\infty}\backslash\operatorname{SL}(2,\mathbb{Z})/\Gamma_{2;l}$
such that

$\begin{pmatrix}1&\frac{\mu-1}{m}\\\ 0&1\end{pmatrix}\begin{pmatrix}1&0\\\
0&\frac{m}{2}\end{pmatrix}\begin{pmatrix}\frac{1+\sqrt{D}}{2}&\frac{1-\sqrt{D}}{2}\\\
1&1\end{pmatrix}=\gamma\mathfrak{D}_{l}\begin{pmatrix}\zeta&0\\\
0&\overline{\zeta}\end{pmatrix}$ (2.38)

for some totally positive $\zeta$.

Conversely, if for
$\Gamma_{\infty}\gamma\Gamma_{2;l}\in\Gamma_{\infty}\backslash\operatorname{SL}(2,\mathbb{Z})/\Gamma_{2;l}$
there exists positive real numbers $\zeta_{1}$ and $\zeta_{2}$ such that

$\gamma\mathfrak{D}_{l}\begin{pmatrix}\zeta_{1}&0\\\
0&\zeta_{2}\end{pmatrix}=\begin{pmatrix}1&*\\\ 0&*\\\
\end{pmatrix}\begin{pmatrix}\frac{1+\sqrt{D}}{2}&\frac{1-\sqrt{D}}{2}\\\
1&1\end{pmatrix},$ (2.39)

then in fact $\zeta_{1}=\zeta$ and $\zeta_{2}=\overline{\zeta}$ for some
totally positive $\zeta\in J_{l}^{-1}$ and we have

$\gamma\mathfrak{D}_{l}\begin{pmatrix}\zeta&0\\\
0&\overline{\zeta}\end{pmatrix}=\begin{pmatrix}1&\frac{\mu-1}{m}\\\
0&1\end{pmatrix}\begin{pmatrix}1&0\\\
0&\frac{m}{2}\end{pmatrix}\begin{pmatrix}\frac{1+\sqrt{D}}{2}&\frac{1-\sqrt{D}}{2}\\\
1&1\end{pmatrix},$ (2.40)

where $\mu\bmod m$ satisfies $\mu^{2}\equiv D\pmod{m}$ and both $m$ and
$\frac{D-\mu^{2}}{m}$ are even.

###  2.2 Roots and geodesics

We define oriented geodesics $\bm{c}_{I_{k}}$ for $1\leq k\leq h_{1}^{+}(D)$,
and $\bm{c}_{J_{l}}$ for $1\leq l\leq h_{2}^{+}(D)$ in $\mathbb{H}$ by

$\bm{c}_{I_{k}}=\left\\{(\det\mathfrak{B}_{k})^{-\frac{1}{2}}\mathfrak{B}_{k}\begin{pmatrix}t&0\\\
0&t^{-1}\end{pmatrix}\mathrm{i}:t>0\right\\}$ (2.41)

and

$\bm{c}_{J_{l}}=\left\\{(\det\mathfrak{D}_{l})^{-\frac{1}{2}}\mathfrak{D}_{l}\begin{pmatrix}t&0\\\
0&t^{-1}\end{pmatrix}\mathrm{i}:t>0\right\\}.$ (2.42)

Recalling that the top $z_{\bm{c}}\in\mathbb{H}$ of a positively oriented
geodesic $\bm{c}$ is the point on $\bm{c}$ which has the largest imaginary
part on $\bm{c}$, we now interpret Propositions 8 and 11 geometrically as
follows.

######  Proposition 12.

Let $D\equiv 1\pmod{4}$ and let $\mu\bmod m$ satisfy $\mu^{2}\equiv
D\pmod{m}$. If either $m$ or $\frac{D-\mu^{2}}{m}$ is odd, then there exists a
unique $1\leq k\leq h_{1}^{+}(D)$ and a unique double coset
$\Gamma_{\infty}\gamma\Gamma_{1;k}\in\Gamma_{\infty}\backslash\Gamma/\Gamma_{1;k}$
such that

$z_{\gamma\bm{c}_{I_{k}}}\equiv\frac{\mu}{m}+\mathrm{i}\frac{\sqrt{D}}{m}\pmod{\Gamma_{\infty}}.$
(2.43)

Conversely, given $1\leq k\leq h_{1}^{+}(D)$ and a double coset
$\Gamma_{\infty}\gamma\Gamma_{1;k}$ such that $\gamma\bm{c}_{I_{k}}$ is
positively oriented, there exists a unique positive integer $m$ and a residue
class $\mu\bmod m$ with either $m$ or $\frac{D-\mu^{2}}{m}$ odd satisfying
(2.43).

###### Proof.

In the identification of $G/\\{\pm I\\}$ with the unit tangent bundle
$\mathrm{T}_{1}(\mathbb{H})$, the matrices

$\begin{pmatrix}*&*\\\
0&*\end{pmatrix}\begin{pmatrix}\cos\frac{\pi}{4}&-\sin\frac{\pi}{4}\\\
\sin\frac{\pi}{4}&\cos\frac{\pi}{4}\end{pmatrix}$ (2.44)

are identified with points in $\mathbb{H}$ whose tangent vectors point
horizontally to the right. The intersection, if it exists, of these matrices
with those of the form

$(\det\mathfrak{B}_{k})^{-\frac{1}{2}}\gamma\mathfrak{B}_{k}\begin{pmatrix}*&0\\\
0&*\end{pmatrix}$ (2.45)

is the point on $\gamma\bm{c}_{I_{k}}$ which has a right horizontal tangent
vector. Such a point exists exactly when $\gamma\bm{c}_{I_{k}}$ is positively
oriented, and its imaginary part is the largest on the geodesic
$\gamma\bm{c}_{I_{k}}$. Scaling and rewriting (2.23), we have

$(\det\mathfrak{B}_{k})^{-\frac{1}{2}}\gamma\mathfrak{B}_{k}\begin{pmatrix}t&0\\\
0&t^{-1}\end{pmatrix}=\begin{pmatrix}1&\frac{\mu}{m}\\\ 0&1\\\
\end{pmatrix}\begin{pmatrix}\left(\frac{\sqrt{D}}{m}\right)^{\frac{1}{2}}&0\\\
0&\left(\frac{\sqrt{D}}{m}\right)^{-\frac{1}{2}}\\\
\end{pmatrix}\begin{pmatrix}\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}\\\
\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\\\ \end{pmatrix},$

finishing the proof via Proposition 8. ∎

We also record the following proposition, which has a nearly identical proof,
the only difference being the rewriting

$\begin{pmatrix}1&\frac{\mu-1}{2}\\\
0&\frac{m}{2}\end{pmatrix}\begin{pmatrix}\frac{1+\sqrt{D}}{2}&\frac{1-\sqrt{D}}{2}\\\
1&1\end{pmatrix}\\\
=(\tfrac{1}{2}m\sqrt{D})^{\frac{1}{2}}\begin{pmatrix}1&\frac{\mu}{m}\\\
0&1\end{pmatrix}\begin{pmatrix}\left(\frac{\sqrt{D}}{m}\right)^{\frac{1}{2}}&0\\\
0&\left(\frac{\sqrt{D}}{m}\right)^{-\frac{1}{2}}\end{pmatrix}\begin{pmatrix}\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}\\\
\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\end{pmatrix}.$ (2.46)

######  Proposition 13.

Let $D\equiv 1\pmod{4}$ and let $\mu\bmod m$ satisfy $\mu^{2}\equiv D\pmod{m}$
with both $m$ and $\frac{D-\mu^{2}}{m}$ are even. Then there exists a unique
$1\leq l\leq h_{2}^{+}(D)$ and a unique double coset
$\Gamma_{\infty}\gamma\Gamma_{2;l}\in\Gamma_{\infty}\backslash\Gamma/\Gamma_{2;l}$
such that

$z_{\gamma\bm{c}_{J_{l}}}\equiv\frac{\mu}{m}+\mathrm{i}\frac{\sqrt{D}}{m}\pmod{\Gamma_{\infty}}.$
(2.47)

Conversely, given $1\leq l\leq h_{2}^{+}(D)$ and a double coset
$\Gamma_{\infty}\gamma\Gamma_{2;l}$ such that $\gamma\bm{c}_{J_{l}}$ is
positively oriented, there exists a unique positive integer $m$ and a residue
class $\mu\bmod m$ with both $m$ and $\frac{D-\mu^{2}}{m}$ even satisfying
(2.47).

##  3 Congruence subgroups

In the previous section, we considered the
$\Gamma=\operatorname{SL}(2,\mathbb{Z})$-orbits of geodesics. In this section,
we work with the orbits under the action of the congruence subgroups

$\Gamma_{0}(n)=\left\\{\begin{pmatrix}a&b\\\
c&d\end{pmatrix}\in\operatorname{SL}(2,\mathbb{Z}):c\equiv
0\pmod{n}\right\\}.$ (3.1)

We find below that given a fixed root $\nu\bmod n$, we can generate all roots
$\mu\bmod m$ satisfying $m\equiv 0\pmod{n}$ and $\mu\equiv\nu\pmod{n}$ as
follows: To obtain those roots for which either $m$ or $\frac{D-\mu^{2}}{m}$
is odd, we pick cosets $\Gamma_{0}(n)\gamma_{1;k}$ (depending on $n$ and
$\nu$) in $\Gamma_{0}(n)\backslash\Gamma$ and consider the
$\Gamma_{0}(n)$-orbits of the geodesics $\gamma_{1;k}\bm{c}_{I_{k}}$, and
similarly, for the remaining roots for which both $m$ and
$\frac{D-\mu^{2}}{m}$ are even, we choose coset representatives $\gamma_{2;l}$
(again depending on $n$ and $\nu$) for either $\Gamma_{0}(n)\backslash\Gamma$
or $\Gamma_{0}(\frac{n}{2})\backslash\Gamma$ (depending on the parity of $n$)
and correspondingly consider the $\Gamma_{0}(n)$-orbits or
$\Gamma_{0}(\frac{n}{2})$-orbits of the geodesics
$\gamma_{2;l}\bm{c}_{J_{l}}$.

We recall that $\\{\beta_{k1},\beta_{k2}\\}$ and
$\\{\beta^{\prime}_{k1},\beta_{k2}^{\prime}\\}$ are respectively bases of the
invertible ideals $I_{k}$ and $I_{k}^{-1}$ of $\mathbb{Z}[\sqrt{D}]$. We
further recall the integer coefficients $a_{kij},b_{kij}$ determined by
$\beta^{\prime}_{ki}\beta_{kj}=a_{kij}+b_{kij}\sqrt{D}$. Similarly, for
$\mathbb{Z}[\tfrac{1+\sqrt{D}}{2}]$, we have bases
$\\{\delta_{l1},\delta_{l2}\\}$ and
$\\{\delta^{\prime}_{l1},\delta_{l2}^{\prime}\\}$ of the ideals $J_{l}$ and
$J_{l}^{-1}$ respectively. Here, the analogous integer coefficients
$c_{lij},d_{lij}$ are determined by
$\delta^{\prime}_{li}\delta_{lj}=c_{lij}+d_{lij}\frac{1+\sqrt{D}}{2}$.

Finally, we recall the matrix $B_{k}$ defined in (2.30) and proven to be in
$\operatorname{GL}(2,\mathbb{Z})$ in Lemma 10. We similarly define

$D_{l}=\begin{pmatrix}d_{l11}&d_{l21}\\\ d_{l12}&d_{l22}\end{pmatrix},$ (3.2)

which can be seen to be in $\operatorname{GL}(2,\mathbb{Z})$ by the same
reasoning as in Lemma 10.

######  Corollary 14.

As $\gamma=\begin{pmatrix}*&*\\\ c&d\end{pmatrix}$ runs through the
representatives of the double coset
$\Gamma_{\infty}\backslash\Gamma/\Gamma_{1;k}$ such that
$\gamma\bm{c}_{I_{k}}$ is positively oriented,

$\begin{pmatrix}\mu\\\
m\end{pmatrix}=\det(B_{k})\gamma\begin{pmatrix}a_{k11}b_{k21}-a_{k21}b_{k11}&a_{k11}b_{k22}-a_{k21}b_{k12}\\\
a_{k12}b_{k21}-a_{k22}b_{k11}&a_{k12}b_{k22}-a_{k22}b_{k12}\end{pmatrix}\begin{pmatrix}c\\\
d\end{pmatrix}$ (3.3)

parametrizes all $\mu$ and $m$ satisfying $\mu^{2}\equiv D\pmod{m}$ with
either $m$ or $\frac{D-\mu^{2}}{m}$ odd.

Similarly, as $\gamma=\begin{pmatrix}*&*\\\ c&d\end{pmatrix}$ runs through the
representatives of the double coset
${\Gamma_{\infty}\backslash\Gamma/\Gamma_{2;l}}$ such that
$\gamma\bm{c}_{J_{l}}$ is positively oriented,

$\begin{pmatrix}\frac{\mu-1}{2}\\\
\frac{m}{2}\end{pmatrix}=\det(D_{l})\gamma\begin{pmatrix}c_{l11}d_{l21}-c_{l21}d_{l11}&c_{l11}d_{l22}-c_{l21}d_{l12}\\\
c_{l12}d_{l21}-c_{l22}d_{l11}&c_{l12}d_{l22}-c_{l22}d_{l12}\end{pmatrix}\begin{pmatrix}c\\\
d\end{pmatrix}$ (3.4)

parametrizes all $\mu$ and $m$ satisfying $\mu^{2}\equiv D\pmod{m}$ with both
$m$ and $\frac{D-\mu^{2}}{m}$ even.

###### Proof.

Starting with (3.3), let
$\xi=c_{1}\beta_{k1}^{\prime}+c_{2}\beta_{k2}^{\prime}$. By Proposition 8 and
(2.27), we have

$\displaystyle\gamma\mathfrak{B}_{k}\begin{pmatrix}\xi&0\\\
0&\overline{\xi}\end{pmatrix}$
$\displaystyle=\gamma(c_{1}A_{k1}+c_{2}A_{k2})\begin{pmatrix}\sqrt{D}&-\sqrt{D}\\\
1&1\end{pmatrix}$ (3.5) $\displaystyle=\begin{pmatrix}1&\mu\\\ 0&m\\\
\end{pmatrix}\begin{pmatrix}\sqrt{D}&-\sqrt{D}\\\ 1&1\end{pmatrix},$

where $\gamma=\begin{pmatrix}*&*\\\
c&d\end{pmatrix}\in\operatorname{SL}(2,\mathbb{Z})$. This yields

$\gamma(c_{1}A_{k1}+c_{2}A_{k2})=\gamma\begin{pmatrix}c_{1}b_{k11}+c_{2}b_{k21}&c_{1}a_{k11}+c_{2}a_{k21}\\\
c_{1}b_{k12}+c_{2}b_{k22}&c_{1}a_{k12}+c_{2}a_{k22}\end{pmatrix}=\begin{pmatrix}1&\mu\\\
0&m\\\ \end{pmatrix}.$ (3.6)

Considering the first column of (3.6), we obtain

$\gamma B_{k}\begin{pmatrix}c_{1}\\\
c_{2}\end{pmatrix}=\gamma\begin{pmatrix}c_{1}b_{k11}+c_{2}b_{k21}\\\
c_{1}b_{k12}+c_{2}b_{k22}\end{pmatrix}=\begin{pmatrix}1\\\ 0\end{pmatrix},$
(3.7)

which implies

$\displaystyle\begin{pmatrix}c_{1}\\\
c_{2}\end{pmatrix}=B_{k}^{-1}\gamma^{-1}\begin{pmatrix}1\\\ 0\end{pmatrix}$
$\displaystyle=\frac{1}{\det(B_{k})}\begin{pmatrix}b_{k22}&-b_{k21}\\\
-b_{k12}&b_{k11}\end{pmatrix}\begin{pmatrix}d\\\ -c\end{pmatrix}$ (3.8)
$\displaystyle=\det(B_{k})\begin{pmatrix}b_{k21}&b_{k22}\\\
-b_{k11}&-b_{k12}\end{pmatrix}\begin{pmatrix}c\\\ d\end{pmatrix}$

as $B_{k}\in\operatorname{GL}(2,\mathbb{Z})$ and
$\gamma^{-1}=\begin{pmatrix}d&*\\\ -c&*\end{pmatrix}$. Equating the second
column of (3.6), we conclude

$\begin{pmatrix}\mu\\\ m\end{pmatrix}=\gamma\begin{pmatrix}a_{k11}&a_{k21}\\\
a_{k12}&a_{k22}\end{pmatrix}\begin{pmatrix}c_{1}\\\
c_{2}\end{pmatrix}=\det(B_{k})\gamma\begin{pmatrix}a_{k11}&a_{k21}\\\
a_{k12}&a_{k22}\end{pmatrix}\begin{pmatrix}b_{k21}&b_{k22}\\\
-b_{k11}&-b_{k12}\end{pmatrix}\begin{pmatrix}c\\\ d\end{pmatrix}$ (3.9)

so the corollary holds.

The parametrization (3.4) follows by the same reasoning. ∎

Corollary 14 leads to Lemma 15 below, which says that the quadratic conditions
$m\equiv 0\pmod{n}$ and $\mu\equiv\nu\pmod{n}$ are invariant either under
$\Gamma_{0}(n)$ or $\Gamma_{0}(\frac{n}{2})$. By invariant, we mean that if
$\mu\bmod m$ satisfies the congruence conditions and corresponds to some
$\gamma$ via Propositions 12 or 13, then any root
$\mu^{\prime}\bmod{m^{\prime}}$ corresponding to some
$\gamma^{\prime}\in\Gamma_{0}(n)\gamma$ (or $\Gamma(\frac{n}{2})\gamma$, see
below) also satisfies the congruence conditions $m^{\prime}\equiv 0\pmod{n}$
and $\mu^{\prime}\equiv\nu\pmod{n}$.

######  Lemma 15.

Let $D\equiv 1\pmod{4}$ and let $\mu\bmod m$, $\nu\bmod n$ satisfy
$\mu^{2}\equiv D\pmod{m}$, $\nu^{2}\equiv D\pmod{n}$.

  1. (i)

Suppose that either $m$ or $\frac{D-\mu^{2}}{n}$ is odd. Then, the conditions
$m\equiv 0\pmod{n}$ and $\mu\equiv\nu\pmod{n}$ are invariant under
$\Gamma_{0}(n)$.

  2. (ii)

Suppose that both $m$ and $\frac{D-\mu^{2}}{n}$ are even. If either $n$ or
$\frac{D-\nu^{2}}{n}$ is odd, then the conditions $m\equiv 0\pmod{n}$ and
$\mu\equiv\nu\pmod{n}$ are invariant under $\Gamma_{0}(n)$. On other hand, if
both $n$ and $\frac{D-\nu^{2}}{n}$ are even, then the quadratic conditions
$m\equiv 0\pmod{n}$ and $\mu\equiv\nu\pmod{n}$ are invariant under
$\Gamma_{0}(\frac{n}{2})$.

###### Proof.

(i) First, we assume that either $m$ or $\frac{D-\mu^{2}}{2}$ is odd. By
Corollary 14, we can write

$\begin{pmatrix}\mu\\\ m\end{pmatrix}=\begin{pmatrix}a&b\\\
c&d\end{pmatrix}\begin{pmatrix}A&B\\\ C&D\end{pmatrix}\begin{pmatrix}c\\\
d\end{pmatrix}\quad\text{for some}\quad\gamma=\begin{pmatrix}a&b\\\
c&d\end{pmatrix}\in\operatorname{SL}(2,\mathbb{Z}).$ (3.10)

Given $\gamma_{0}=\begin{pmatrix}a^{\prime}&b^{\prime}\\\
nc^{\prime}&d^{\prime}\end{pmatrix}\in\Gamma_{0}(n)$, we have
$\gamma_{0}\gamma=\begin{pmatrix}a^{\prime}a+b^{\prime}c&a^{\prime}b+b^{\prime}d\\\
nc^{\prime}a+d^{\prime}c&nc^{\prime}b+d^{\prime}d\end{pmatrix}$ and

$\begin{pmatrix}\mu^{\prime}\\\
m^{\prime}\end{pmatrix}=\begin{pmatrix}a^{\prime}a+b^{\prime}c&a^{\prime}b+b^{\prime}d\\\
nc^{\prime}a+d^{\prime}c&nc^{\prime}b+d^{\prime}d\end{pmatrix}\begin{pmatrix}A&B\\\
C&D\end{pmatrix}\begin{pmatrix}nc^{\prime}a+d^{\prime}c\\\
nc^{\prime}b+d^{\prime}d\end{pmatrix}$ (3.11)

so $m^{\prime}\equiv d^{\prime 2}m\equiv 0\pmod{n}$ and
$\mu^{\prime}\equiv(1+nc^{\prime}b^{\prime})\mu+b^{\prime}d^{\prime}m\equiv\mu\pmod{n}$.

(iia) Now, we assume that both $m$ and $\frac{D-\mu^{2}}{2}$ are even. By
Corollary 14, we can write

$\begin{pmatrix}\frac{\mu-1}{2}\\\
\frac{m}{2}\end{pmatrix}=\begin{pmatrix}a&b\\\
c&d\end{pmatrix}\begin{pmatrix}A&B\\\ C&D\end{pmatrix}\begin{pmatrix}c\\\
d\end{pmatrix}\quad\text{for some}\quad\gamma=\begin{pmatrix}a&b\\\
c&d\end{pmatrix}\in\operatorname{SL}(2,\mathbb{Z}).$ (3.12)

Suppose that either $n$ or $\frac{D-\nu^{2}}{n}$ is odd, and we note that if
also $m\equiv 0\pmod{n}$ and $\mu\equiv\nu\pmod{n}$, then in fact $n$ is odd
since $\nu^{2}-D\equiv\mu^{2}-D\equiv 0\pmod{2n}$. Given
$\gamma_{0}=\begin{pmatrix}a^{\prime}&b^{\prime}\\\
nc^{\prime}&d^{\prime}\end{pmatrix}\in\Gamma_{0}(n)$, we have

$\begin{pmatrix}\frac{\mu^{\prime}-1}{2}\\\
\frac{m^{\prime}}{2}\end{pmatrix}=\begin{pmatrix}a^{\prime}a+b^{\prime}c&a^{\prime}b+b^{\prime}d\\\
nc^{\prime}a+d^{\prime}c&nc^{\prime}b+d^{\prime}d\end{pmatrix}\begin{pmatrix}A&B\\\
C&D\end{pmatrix}\begin{pmatrix}nc^{\prime}a+d^{\prime}c\\\
nc^{\prime}b+d^{\prime}d\end{pmatrix}$ (3.13)

so $\frac{m^{\prime}}{2}\equiv d^{\prime 2}\frac{m}{2}\equiv 0\pmod{n}$ and
$\frac{\mu^{\prime}-1}{2}\equiv(1+nc^{\prime}b^{\prime})\frac{\mu-1}{2}+b^{\prime}d^{\prime}\frac{m}{2}\equiv\frac{\mu-1}{2}\pmod{n}$
since $m\equiv 0\pmod{2n}$. This implies $m^{\prime}\equiv m\equiv 0\pmod{n}$
and $\mu^{\prime}\equiv\mu\equiv\nu\pmod{n}$.

(iib) Suppose that both $n$ and $\frac{D-\nu^{2}}{n}$ are even. Given
$\gamma_{0}=\begin{pmatrix}a^{\prime}&b^{\prime}\\\
\frac{n}{2}c^{\prime}&d^{\prime}\end{pmatrix}\in\Gamma_{0}(\frac{n}{2})$, we
have

$\begin{pmatrix}\frac{\mu^{\prime}-1}{2}\\\
\frac{m^{\prime}}{2}\end{pmatrix}=\begin{pmatrix}a^{\prime}a+b^{\prime}c&a^{\prime}b+b^{\prime}d\\\
\frac{n}{2}c^{\prime}a+d^{\prime}c&\frac{n}{2}c^{\prime}b+d^{\prime}d\end{pmatrix}\begin{pmatrix}A&B\\\
C&D\end{pmatrix}\begin{pmatrix}\frac{n}{2}c^{\prime}a+d^{\prime}c\\\
\frac{n}{2}c^{\prime}b+d^{\prime}d\end{pmatrix}.$ (3.14)

Multiplying both sides by the scalar $2$, the equality becomes

$\begin{pmatrix}\mu^{\prime}-1\\\
m^{\prime}\end{pmatrix}=\begin{pmatrix}a^{\prime}a+b^{\prime}c&a^{\prime}b+b^{\prime}d\\\
\frac{n}{2}c^{\prime}a+d^{\prime}c&\frac{n}{2}c^{\prime}b+d^{\prime}d\end{pmatrix}\begin{pmatrix}A&B\\\
C&D\end{pmatrix}\begin{pmatrix}nc^{\prime}a+2d^{\prime}c\\\
nc^{\prime}b+2d^{\prime}d\end{pmatrix}$ (3.15)

so $m^{\prime}\equiv d^{\prime 2}m\equiv 0\pmod{n}$ and
$\mu^{\prime}\equiv\mu+nc^{\prime}b^{\prime}\frac{\mu-1}{2}+b^{\prime}d^{\prime}m\equiv\mu\pmod{n}$.
∎

We now prove the existence of elements $\gamma_{1;k}$ and $\gamma_{2;l}$
(depending on $n$ and $\nu$) of $\Gamma$ referred to at the beginning of this
section. Specifically, these $\gamma_{1;k}$ and $\gamma_{2;l}$ should be so
that the tops $z_{\gamma_{1;k}\bm{c}_{1;k}}$ and
$z_{\gamma_{2;l}\bm{c}_{2;l}}$ have the form
$\frac{\mu}{m}+\mathrm{i}\frac{\sqrt{D}}{m}$ with $m\equiv 0\pmod{n}$ and
$\mu\equiv\nu\pmod{n}$. Lemma 15 then implies that the top of any positively
oriented geodesic in the same $\Gamma_{0}(n)$-orbit or
$\Gamma_{0}(\frac{n}{2})$-orbit as $\gamma_{1;k}$ or $\gamma_{2;l}$ also
satisfies these congruence conditions. We note that it is enough to show the
existence of ideal classes having the corresponding properties.

######  Lemma 16.

Let $D\equiv 1\pmod{4}$ and $\nu\bmod n$ satisfy $\nu^{2}\equiv D\pmod{n}$.
For any $1\leq k\leq h_{1}^{+}(D)$, there exists $I_{k,\nu,n}$, equivalent to
$I_{k}$ in the narrow class group of $\mathbb{Z}[\sqrt{D}]$, such that
$I_{k,\nu,n}$ has a basis given by $\begin{pmatrix}1&\mu\\\
0&m\end{pmatrix}\begin{pmatrix}\sqrt{D}\\\ 1\end{pmatrix}$ where $m\equiv
0\pmod{n}$ and $\mu\equiv\nu\pmod{n}$ with either $m$ or $\frac{D-\mu^{2}}{m}$
odd.

Similarly, for any $1\leq l\leq h_{2}^{+}(D)$, there exists $J_{l,\nu,n}$,
equivalent to $J_{l}$ in the narrow class group of
$\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$, such that $J_{l,\nu,n}$ has a basis given
by $\begin{pmatrix}1&\frac{\mu-1}{2}\\\
0&\frac{m}{2}\end{pmatrix}\begin{pmatrix}\frac{1+\sqrt{D}}{2}\\\
1\end{pmatrix}$ where $m\equiv 0\pmod{n}$ and $\mu\equiv\nu\pmod{n}$ with both
$m$ and $\frac{D-\mu^{2}}{m}$ even.

###### Proof.

We begin with the ideal $I_{k}$ of $\mathbb{Z}[\sqrt{D}]$, and in addition,
suppose that either $n$ or $\frac{D-\nu^{2}}{n}$ is odd. By Proposition 5,
$I=(n,\nu+\sqrt{D})$ is an invertible ideal of $\mathbb{Z}[\sqrt{D}]$. Let
$I_{0}=(m_{0},\mu_{0}+\sqrt{D})$ with $\mu_{0}^{2}\equiv D\pmod{m_{0}}$ be an
invertible ideal of $\mathbb{Z}[\sqrt{D}]$, equivalent to $I_{k}I^{-1}$ in the
narrow class group of $\mathbb{Z}[\sqrt{D}]$, such that $I_{0}$ is not
divisible by rational integers greater than $1$ and $\gcd(m_{0},n)=1$ (the
existence of such an ideal $I_{0}$ can be seen, for example, by observing that
the possible norms $m_{0}$ in the class of $I_{k}I^{-1}$ are given by the
values of a primitive binary quadratic form at coprime integers, see Corollary
14). As $m_{0}$ and $n$ are coprime, there exist integers $\overline{m}_{0}$
and $\overline{n}$ such that $m_{0}\overline{m}_{0}+n\overline{n}=1$. We have

$\displaystyle I_{0}I$
$\displaystyle=(m_{0}n,m_{0}\nu+m_{0}\sqrt{D},n\mu_{0}+n\sqrt{D},\mu_{0}\nu+D+(\mu_{0}+\nu)\sqrt{D})$
(3.16)
$\displaystyle=(m_{0}n,m_{0}n(\nu-\mu_{0}),m_{0}\overline{m}_{0}\nu+n\overline{n}\mu_{0}+\sqrt{D},\mu_{0}\nu+D+(\mu_{0}+\nu)\sqrt{D})$
$\displaystyle=(m_{0}n,m_{0}\overline{m}_{0}\nu+n\overline{n}\mu_{0}+\sqrt{D},\mu_{0}\nu+D-(\mu_{0}+\nu)(m_{0}\overline{m}_{0}\nu+n\overline{n}\mu_{0}))$
$\displaystyle=(m_{0}n,m_{0}\overline{m}_{0}\nu+n\overline{n}\mu_{0}+\sqrt{D}),$

because
$\mu_{0}\nu+D-(\mu_{0}+\nu)(m_{0}\overline{m}_{0}\nu+n\overline{n}\mu_{0})\equiv
0\pmod{m_{0}n}$. Set $I_{k,\nu,n}=I_{0}I=(m,\mu+\sqrt{D})$, where $m=m_{0}n$
and $\mu\equiv m_{0}\overline{m}_{0}\nu+n\overline{n}\mu_{0}\pmod{m}$, i.e.
$\mu\bmod m$ is obtained from $\nu\bmod n$ and $\mu_{0}\bmod m_{0}$ by the
Chinese remainder theorem.

Suppose now that both $n$ and $\frac{D-\nu^{2}}{n}$ are even. Let $s\geq 1$ be
the exponent such that $\frac{D-\nu^{2}}{2^{s}n}$ is odd. By Proposition 5,
$I^{\prime}=(n^{\prime},\nu+\sqrt{D})$ is an invertible ideal of
$\mathbb{Z}[\sqrt{D}]$, where $n^{\prime}=2^{s}n$. Let
$I_{0}=(m_{0},\mu_{0}+\sqrt{D})$ with $\mu_{0}^{2}\equiv D\pmod{m_{0}}$ be an
invertible ideal of $\mathbb{Z}[\sqrt{D}]$, equivalent to
$I_{k}(I^{\prime})^{-1}$ in the narrow class group of $\mathbb{Z}[\sqrt{D}]$,
such that $I_{0}$ is not divisible by rational integers greater than $1$ and
$\gcd(m_{0},n^{\prime})=1$. As $m_{0}$ and $n^{\prime}$ are coprime, there
exist integers $\overline{m}_{0}$ and $\overline{n}^{\prime}$ such that
$m_{0}\overline{m}_{0}+n^{\prime}\overline{n}^{\prime}=1$. Following the
similar calculation in (3.16), we set
$I_{k,\nu,n}=I_{0}I^{\prime}=(m,\mu+\sqrt{D})$, where $m=2^{s}m_{0}n$ and
$\mu\equiv
m_{0}\overline{m}_{0}\nu+n^{\prime}\overline{n}^{\prime}\mu_{0}\pmod{m}$.

We now turn to the ideal $J_{l}$ in $\mathbb{Z}[\tfrac{1+\sqrt{D}}{2}]$, and
we first suppose that both $n$ and $\frac{D-\nu^{2}}{n}$ are even. By
Proposition 6,
$J=(\frac{n}{2},\frac{\nu-1}{2}+\frac{1+\sqrt{D}}{2})=\frac{1}{2}(n,\nu+\sqrt{D})$
is an ideal of $\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$. Let
$J_{0}=\frac{1}{2}(m_{0},\mu_{0}+\sqrt{D})$, where $\mu_{0}^{2}\equiv
D\pmod{m_{0}}$ and $m_{0}\equiv 2\pmod{4}$, be an ideal of
$\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$, equivalent to $J_{l}J^{-1}$ in the narrow
class group of $\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$, such that $J_{0}$ is not
divisible by rational integers greater than 1 and
$\gcd(\frac{m_{0}}{2},\frac{n}{2})=1$ (the possible norms $\frac{m_{0}}{2}$
are given by values of a primitive binary quadratic form at coprime integers
in this case as well). As $\frac{m_{0}}{2}$ and $\frac{n}{2}$ are coprime,
there exist integers $\overline{m}_{0}$ and $\overline{n}$ such that
$\frac{1}{2}(m_{0}\overline{m}_{0}+n\overline{n})=1$. We have

$\displaystyle J_{0}J$
$\displaystyle=\frac{1}{4}(m_{0}n,m_{0}\nu+m_{0}\sqrt{D},n\mu_{0}+n\sqrt{D},\mu_{0}\nu+D+(\mu_{0}+\nu)\sqrt{D})$
(3.17)
$\displaystyle=\frac{1}{4}(m_{0}n,m_{0}n(\nu-\mu_{0})/2,m_{0}\overline{m}_{0}\nu+n\overline{n}\mu_{0}+2\sqrt{D},\mu_{0}\nu+D+(\mu_{0}+\nu)\sqrt{D})$
$\displaystyle=\frac{1}{4}(m_{0}n,m_{0}\overline{m}_{0}\nu+n\overline{n}\mu_{0}+2\sqrt{D},\mu_{0}\nu+D+(\mu_{0}+\nu)\sqrt{D})$
$\displaystyle=\frac{1}{2}(m_{0}n/2,(m_{0}\overline{m}_{0}\nu+n\overline{n}\mu_{0})/2+\sqrt{D}),$

because
$D+\mu_{0}\nu-(\mu_{0}+\nu)(m_{0}\overline{m}_{0}\nu+n\overline{n}\mu_{0})/2\equiv
0\pmod{m_{0}n}$. Set $J_{l,\nu,n}=J_{0}J=\frac{1}{2}(m,\mu+\sqrt{D})$, where
$m=\frac{m_{0}n}{2}$ and
$\mu\equiv(m_{0}\overline{m}_{0}\nu+n\overline{n}\mu_{0})/2\pmod{m}$.

Suppose now that either $n$ or $\frac{D-\nu^{2}}{n}$ is odd. As before, since
$m\equiv 0\pmod{n}$, $\mu\equiv\nu\pmod{n}$ and both $m$ and
$\frac{D-\mu^{2}}{m}$ are even, we have $n$ is odd. Furthermore, we may assume
that $\nu^{2}\equiv D\pmod{2n}$ by possibly replacing $\nu$ with $\nu+n$. Then
necessarily $\frac{D-\nu^{2}}{2n}$ is even, and by Proposition 6,
$J^{\prime}=\frac{1}{2}(2n,\nu+\sqrt{D})$ is an ideal of
$\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$. Let
$J_{0}=\frac{1}{2}(m_{0},\mu_{0}+\sqrt{D})$ with $\mu_{0}^{2}\equiv
D\pmod{m_{0}}$ be an ideal of $\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$, equivalent
to $J_{l}(J^{\prime})^{-1}$ in the narrow class group of
$\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$, such that $J_{0}$ is not divisible by
rational integers greater than 1 and $\gcd(\frac{m_{0}}{2},n)=1$. Following
the similar calculation in (3.17), we set
$J_{l,\nu,n}=J_{0}J^{\prime}=\frac{1}{2}(m,\mu+\sqrt{D})$, where $m=m_{0}n$
and $\mu\equiv m_{0}\overline{m}_{0}\nu/2+n\overline{n}\mu_{0}\pmod{m}$ with
$m_{0}\overline{m}_{0}/2+n\overline{n}=1$. ∎

The next two lemmas show that if two tops
$\frac{\mu_{j}}{m_{j}}+\mathrm{i}\frac{\sqrt{D}}{m_{j}}$ are in the same
$\operatorname{SL}(2,\mathbb{Z})$-orbit and satisfy the congruence conditions
$m_{1}\equiv m_{2}\equiv 0\pmod{n}$ and
$\mu_{1}\equiv\mu_{2}\equiv\nu\pmod{n}$, then in fact they are in the same
$\Gamma_{0}(n)$-orbit or $\Gamma_{0}(\frac{n}{2})$-orbit. This completes the
argument outlined at the beginning of this section.

######  Lemma 17.

Let $D\equiv 1\pmod{4}$ and $m_{1},m_{2}\in\mathbb{N}$. Let
$\mu_{1}\bmod{m_{1}}$ satisfy $\mu_{1}^{2}\equiv D\pmod{m_{1}}$ with either
$m_{1}$ or $\frac{D-\mu_{1}^{2}}{m_{1}}$ odd, and let $\mu_{2}\bmod{m_{2}}$
satisfy $\mu_{2}^{2}\equiv D\pmod{m_{2}}$ with either $m_{2}$ or
$\frac{D-\mu_{2}^{2}}{m_{2}}$ odd. Suppose that there is a root $\nu\bmod n$
of $\nu^{2}\equiv D\pmod{n}$, and suppose that $m_{1}\equiv m_{2}\equiv
0\pmod{n}$ and $\mu_{1}\equiv\mu_{2}\equiv\nu\pmod{n}$. If there exists
$\gamma\in\operatorname{SL}(2,\mathbb{Z})$ such that

$\begin{pmatrix}1&\mu_{1}\\\
0&m_{1}\end{pmatrix}\begin{pmatrix}\sqrt{D}&-\sqrt{D}\\\
1&1\end{pmatrix}\begin{pmatrix}\xi&0\\\
0&\overline{\xi}\end{pmatrix}=\gamma\begin{pmatrix}1&\mu_{2}\\\
0&m_{2}\end{pmatrix}\begin{pmatrix}\sqrt{D}&-\sqrt{D}\\\ 1&1\end{pmatrix}$
(3.18)

for some totally positive $\xi$, then $\gamma\in\Gamma_{0}(n)$.

###### Proof.

By Proposition 5, we may find two invertible ideals
$I_{1}=(m_{1},\mu_{1}+\sqrt{D})$ and $I_{2}=(m_{2},\mu_{2}+\sqrt{D})$ of
$\mathbb{Z}[\sqrt{D}]$ respectively corresponding to the roots
$\mu_{1}\bmod{m_{1}}$ and $\mu_{2}\bmod{m_{2}}$. We note that (3.18) implies
$\xi I_{1}=I_{2}$.

(i) If either $n$ or $\frac{D-\nu^{2}}{n}$ is odd, we may have an invertible
ideal $I$ of $\mathbb{Z}[\sqrt{D}]$ corresponding to the root $\nu\bmod n$ by
Proposition 5 as well. Due to the congruence conditions modulo $n$, we may
write

$\begin{pmatrix}1&\mu_{j}\\\ 0&m_{j}\end{pmatrix}=\begin{pmatrix}1&k_{j}\\\
0&n_{j}\end{pmatrix}\begin{pmatrix}1&\nu\\\ 0&n\end{pmatrix},$ (3.19)

where $n_{j}=\frac{m_{j}}{n}\in\mathbb{Z}$ and $k_{j}\in\mathbb{Z}$. This
implies $I_{j}\subseteq I$ so $I_{j}I^{-1}\subseteq\mathbb{Z}[\sqrt{D}]$ for
$j=1,2$. Let $\nu_{1}\bmod n_{1}$ correspond to the invertible ideal
$I_{1}I^{-1}$ of $\mathbb{Z}[\sqrt{D}]$. We have

$\begin{pmatrix}1&\mu_{1}\\\ 0&m_{1}\end{pmatrix}=\begin{pmatrix}1&k\\\
0&n\end{pmatrix}\begin{pmatrix}1&\nu_{1}\\\ 0&n_{1}\end{pmatrix}$ (3.20)

for some $k\in\mathbb{Z}$. Since $\xi
I_{1}I^{-1}=I_{2}I^{-1}\subseteq\mathbb{Z}[\sqrt{D}]$, then

$\begin{pmatrix}1&\nu_{1}\\\
0&n_{1}\end{pmatrix}\begin{pmatrix}\sqrt{D}&-\sqrt{D}\\\
1&1\end{pmatrix}\begin{pmatrix}\xi&0\\\
0&\overline{\xi}\end{pmatrix}=M\begin{pmatrix}\sqrt{D}&-\sqrt{D}\\\
1&1\end{pmatrix}$ (3.21)

for some integer matrix $M\in\mathrm{M}_{2}(\mathbb{Z})$. By comparing (3.18)
with (3.21), we conclude

$\begin{pmatrix}1&k\\\ 0&n\end{pmatrix}M=\gamma\begin{pmatrix}1&\mu_{2}\\\
0&m_{2}\end{pmatrix}$ (3.22)

so

$M=\frac{1}{n}\begin{pmatrix}n&-k\\\
0&1\end{pmatrix}\gamma\begin{pmatrix}1&\mu_{2}\\\
0&m_{2}\end{pmatrix}=\begin{pmatrix}*&*\\\ \frac{c}{n}&*\end{pmatrix}.$ (3.23)

Since the entries of $M$ are integers, then $n\mid c$, which means
$\gamma\in\Gamma_{0}(n)$.

(ii) If both $n$ and $\frac{D-\nu^{2}}{n}$ are even, then $m_{j}$ is even, and
since then $\frac{D-\mu_{j}^{2}}{m_{j}}$ is odd, we have $m_{j}\equiv
0\pmod{2n}$. Denote $J_{0}=(2,1+\sqrt{D})$ a non-invertible ideal of
$\mathbb{Z}[\sqrt{D}]$. Working in $\mathbb{Z}[\sqrt{D}]$, we obtain

$\displaystyle I_{j}J_{0}$
$\displaystyle=(2m_{j},2\mu_{j}+2\sqrt{D},m_{j}+m_{j}\sqrt{D},\mu_{j}+D+(\mu_{j}+1)\sqrt{D})$
(3.24)
$\displaystyle=(2m_{j},2\mu_{j}+2\sqrt{D},m_{j}+m_{j}\sqrt{D},D-\mu_{j}^{2})$
$\displaystyle=(2m_{j},2\mu_{j}+2\sqrt{D},m_{j}+m_{j}\sqrt{D},m_{j})$
$\displaystyle=2(m_{j}/2,\mu_{j}+\sqrt{D})$

where the third equality follows by $D-\mu_{j}^{2}=r_{j}m_{j}$ with odd
integer $r_{j}$. Since $4\mid m_{j}$, then both $\frac{m_{j}}{2}$ and
$\frac{D-\mu_{j}^{2}}{m_{j}/2}$ are even. Let $J_{j}$ be the ideal of
$\mathbb{Z}[\tfrac{1+\sqrt{D}}{2}]$ corresponding to the root
$\mu_{j}\bmod\frac{m_{j}}{2}$. Since

$\begin{pmatrix}1&\frac{\mu_{j}-1}{2}\\\
0&\frac{m_{j}}{4}\end{pmatrix}\begin{pmatrix}\frac{1+\sqrt{D}}{2}&\frac{1-\sqrt{D}}{2}\\\
1&1\end{pmatrix}=\frac{1}{2}\begin{pmatrix}1&\mu_{j}\\\
0&\frac{m_{j}}{2}\end{pmatrix}\begin{pmatrix}\sqrt{D}&-\sqrt{D}\\\
1&1\end{pmatrix},$ (3.25)

we have $J_{j}=\frac{1}{4}I_{j}J_{0}$. Let $J$ be the ideal of
$\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$ corresponding to the root $\nu\bmod n$. Due
to the congruence conditions modulo $n$, we have

$\begin{pmatrix}1&\frac{\mu_{j}-1}{2}\\\
0&\frac{m_{j}}{4}\end{pmatrix}=\begin{pmatrix}1&k_{j}\\\
0&\frac{n_{j}}{2}\end{pmatrix}\begin{pmatrix}1&\frac{\nu-1}{2}\\\
0&\frac{n}{2}\end{pmatrix},$ (3.26)

where $k_{j}\in\mathbb{Z}$ and $n_{j}=\frac{m_{j}}{n}$. This implies
$J_{j}\subseteq J$ so $J_{j}J^{-1}\subseteq\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$.
Let $\nu_{1}\bmod n_{1}$ correspond to the ideal $J_{1}J^{-1}$. Since
$J_{1}\subseteq J_{1}J^{-1}$, we have

$\begin{pmatrix}1&\frac{\mu_{1}-1}{2}\\\
0&\frac{m_{1}}{4}\end{pmatrix}=\begin{pmatrix}1&k\\\
0&\frac{n}{2}\end{pmatrix}\begin{pmatrix}1&\frac{\nu_{1}-1}{2}\\\
0&\frac{n_{1}}{2}\end{pmatrix}$ (3.27)

for some $k\in\mathbb{Z}$. As $\xi I_{1}=I_{2}$ and
$J_{j}=\frac{1}{4}I_{j}J_{0}$, we have $\xi
J_{1}J^{-1}=J_{2}J^{-1}\subseteq\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$, and so

$\begin{pmatrix}1&\frac{\nu_{1}-1}{2}\\\
0&\frac{n_{1}}{2}\end{pmatrix}\begin{pmatrix}\frac{1+\sqrt{D}}{2}&\frac{1-\sqrt{D}}{2}\\\
1&1\end{pmatrix}\begin{pmatrix}\xi&0\\\
0&\overline{\xi}\end{pmatrix}=M\begin{pmatrix}\frac{1+\sqrt{D}}{2}&\frac{1-\sqrt{D}}{2}\\\
1&1\end{pmatrix}.$ (3.28)

From a calculation similar to (3.25), the equation (3.18) implies

$\begin{pmatrix}1&\frac{\mu_{1}-1}{2}\\\
0&\frac{m_{1}}{2}\end{pmatrix}\begin{pmatrix}\frac{1+\sqrt{D}}{2}&\frac{1-\sqrt{D}}{2}\\\
1&1\end{pmatrix}\begin{pmatrix}\xi&0\\\
0&\overline{\xi}\end{pmatrix}=\gamma\begin{pmatrix}1&\frac{\mu_{2}-1}{2}\\\
0&\frac{m_{2}}{2}\end{pmatrix}\begin{pmatrix}\frac{1+\sqrt{D}}{2}&\frac{1-\sqrt{D}}{2}\\\
1&1\end{pmatrix}$ (3.29)

so this yields

$\begin{pmatrix}1&\frac{\mu_{1}-1}{2}\\\
0&\frac{m_{1}}{4}\end{pmatrix}\\!\begin{pmatrix}\frac{1+\sqrt{D}}{2}&\frac{1-\sqrt{D}}{2}\\\
1&1\end{pmatrix}\\!\begin{pmatrix}\xi&0\\\
0&\overline{\xi}\end{pmatrix}=\begin{pmatrix}1&0\\\
0&\frac{1}{2}\end{pmatrix}\gamma\begin{pmatrix}1&\frac{\mu_{2}-1}{2}\\\
0&\frac{m_{2}}{2}\end{pmatrix}\\!\begin{pmatrix}\frac{1+\sqrt{D}}{2}&\frac{1-\sqrt{D}}{2}\\\
1&1\end{pmatrix}$ (3.30)

for some integer matrix $M\in\mathrm{M}_{2}(\mathbb{Z})$. By comparing (3.28)
with (3.30), we conclude

$\begin{pmatrix}1&k\\\ 0&\frac{n}{2}\end{pmatrix}M=\begin{pmatrix}1&0\\\
0&\frac{1}{2}\end{pmatrix}\gamma\begin{pmatrix}1&\frac{\mu_{2}-1}{2}\\\
0&\frac{m_{2}}{2}\end{pmatrix}$ (3.31)

so

$M=\frac{2}{n}\begin{pmatrix}\frac{n}{2}&-k\\\
0&1\end{pmatrix}\begin{pmatrix}1&0\\\
0&\frac{1}{2}\end{pmatrix}\gamma\begin{pmatrix}1&\frac{\mu_{2}-1}{2}\\\
0&\frac{m_{2}}{2}\end{pmatrix}=\begin{pmatrix}*&*\\\
\frac{c}{n}&*\end{pmatrix}.$ (3.32)

As before, we have $n\mid c$ also and $\gamma\in\Gamma_{0}(n)$. ∎

######  Lemma 18.

Let $D\equiv 1\pmod{4}$ and let $m_{1},m_{2}$ be even. Let $\mu_{1}\bmod
m_{1}$ and $\mu_{2}\bmod m_{2}$ satisfy $\mu_{1}^{2}\equiv D\pmod{m_{1}}$ and
$\mu_{2}^{2}\equiv D\pmod{m_{2}}$ with both $\frac{D-\mu_{1}^{2}}{m_{1}}$ and
$\frac{D-\mu_{2}^{2}}{m_{2}}$ even. Suppose that there is a root $\nu\bmod n$
of $\nu^{2}\equiv D\pmod{n}$ such that $m_{1}\equiv m_{2}\equiv 0\pmod{n}$ and
$\mu_{1}\equiv\mu_{2}\equiv\nu\pmod{n}$, and suppose that there exists
$\gamma\in\operatorname{SL}(2,\mathbb{Z})$ such that

$\begin{pmatrix}1&\frac{\mu_{1}-1}{2}\\\
0&\frac{m_{1}}{2}\end{pmatrix}\begin{pmatrix}\frac{1+\sqrt{D}}{2}&\frac{1-\sqrt{D}}{2}\\\
1&1\end{pmatrix}\begin{pmatrix}\zeta&0\\\
0&\overline{\zeta}\end{pmatrix}=\gamma\begin{pmatrix}1&\frac{\mu_{2}-1}{2}\\\
0&\frac{m_{2}}{2}\end{pmatrix}\begin{pmatrix}\frac{1+\sqrt{D}}{2}&\frac{1-\sqrt{D}}{2}\\\
1&1\end{pmatrix}$ (3.33)

for some totally positive $\zeta$. (i) If $n$ is odd, then
$\gamma\in\Gamma_{0}(n)$. (ii) If $n$ is even, then
$\gamma\in\Gamma_{0}\\!\left(\frac{n}{2}\right)$.

###### Proof.

By Proposition 6, we may find $J_{1}$ and $J_{2}$ be two ideals of
$\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$ respectively corresponding to the roots
$\mu_{1}\bmod{m_{1}}$ and $\mu_{2}\bmod{m_{2}}$. We note that (3.33) implies
$\zeta J_{1}=J_{2}$.

(i) If $n$ is odd, then we may have an ideal $I$ of $\mathbb{Z}[\sqrt{D}]$
corresponding to the root $\nu\bmod n$ by Proposition 5. Since

$2\begin{pmatrix}1&\frac{\mu_{j}-1}{2}\\\
0&\frac{m_{j}}{2}\end{pmatrix}\begin{pmatrix}\frac{1+\sqrt{D}}{2}&\frac{1-\sqrt{D}}{2}\\\
1&1\end{pmatrix}=\begin{pmatrix}1&\mu_{j}\\\
0&m_{j}\end{pmatrix}\begin{pmatrix}\sqrt{D}&-\sqrt{D}\\\ 1&1\end{pmatrix},$
(3.34)

we have $2J_{j}$ is a (non-invertible) ideal of $\mathbb{Z}[\sqrt{D}]$. Due to
the congruence conditions modulo $n$, we may write

$\begin{pmatrix}1&\mu_{j}\\\ 0&m_{j}\end{pmatrix}=\begin{pmatrix}1&k_{j}\\\
0&n_{j}\end{pmatrix}\begin{pmatrix}1&\nu\\\ 0&n\end{pmatrix}$ (3.35)

where $n_{j}=\frac{m_{j}}{n}\in\mathbb{Z}$ and $k_{j}\in\mathbb{Z}$, and so
$2J_{j}\subseteq I$. Let $\nu_{1}\bmod n_{1}$ correspond to the ideal
$2J_{1}I^{-1}\subseteq\mathbb{Z}[\sqrt{D}]$. Then

$\begin{pmatrix}1&\mu_{1}\\\ 0&m_{1}\end{pmatrix}=\begin{pmatrix}1&k\\\
0&n\end{pmatrix}\begin{pmatrix}1&\nu_{1}\\\ 0&n_{1}\end{pmatrix}$ (3.36)

for some $k\in\mathbb{Z}$. Since
$\zeta(2J_{1})I^{-1}=2J_{2}I^{-1}\subseteq\mathbb{Z}[\sqrt{D}]$, then

$\begin{pmatrix}1&\nu_{1}\\\
0&n_{1}\end{pmatrix}\begin{pmatrix}\sqrt{D}&-\sqrt{D}\\\
1&1\end{pmatrix}\begin{pmatrix}\zeta&0\\\
0&\overline{\zeta}\end{pmatrix}=M\begin{pmatrix}\sqrt{D}&-\sqrt{D}\\\
1&1\end{pmatrix}$ (3.37)

for some integer matrix $M\in\mathrm{M}_{2}(\mathbb{Z})$. By comparing (3.33)
with (3.37), we conclude

$\begin{pmatrix}1&k\\\ 0&n\end{pmatrix}M\begin{pmatrix}1&1\\\
0&2\end{pmatrix}^{-1}=\gamma\begin{pmatrix}1&\frac{\mu_{2}-1}{2}\\\
0&\frac{m_{2}}{2}\end{pmatrix},$ (3.38)

so

$M=\frac{1}{n}\begin{pmatrix}n&-k\\\
0&1\end{pmatrix}\gamma\begin{pmatrix}1&\frac{\mu_{2}-1}{2}\\\
0&\frac{m_{2}}{2}\end{pmatrix}\begin{pmatrix}1&1\\\
0&2\end{pmatrix}=\begin{pmatrix}*&*\\\ \frac{c}{n}&*\end{pmatrix}.$ (3.39)

As before, we conclude $\gamma\in\Gamma_{0}(n)$.

(ii) If $n$ is even, then let the ideal $J$ of
$\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$ correspond to the root $\nu\bmod n$ by
Proposition 6. We now may write

$\begin{pmatrix}1&\frac{\mu_{j}-1}{2}\\\
0&\frac{m_{j}}{2}\end{pmatrix}=\begin{pmatrix}1&k_{j}\\\
0&\frac{n_{j}}{2}\end{pmatrix}\begin{pmatrix}1&\frac{\nu-1}{2}\\\
0&\frac{n}{2}\end{pmatrix},$ (3.40)

where $n_{j}=\frac{2m_{j}}{n}\in\mathbb{Z}$ and $k_{j}\in\mathbb{Z}$. This
implies $J_{j}\subseteq J$ so
$J_{j}J^{-1}\subseteq\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$ for $j=1,2$. Let
$\nu_{1}\bmod n_{1}$ be the root corresponding to the ideal $J_{1}J^{-1}$.
Then

$\begin{pmatrix}1&\frac{\mu_{1}-1}{2}\\\
0&\frac{m_{1}}{2}\end{pmatrix}=\begin{pmatrix}1&k\\\
0&\frac{n}{2}\end{pmatrix}\begin{pmatrix}1&\frac{\nu_{1}-1}{2}\\\
0&\frac{n_{1}}{2}\end{pmatrix}$ (3.41)

for some $k\in\mathbb{Z}$. Since $\zeta
J_{1}J^{-1}=J_{2}J^{-1}\subseteq\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$,

$\begin{pmatrix}1&\frac{\nu_{1}-1}{2}\\\
0&\frac{n_{1}}{2}\end{pmatrix}\begin{pmatrix}\frac{1+\sqrt{D}}{2}&\frac{1-\sqrt{D}}{2}\\\
1&1\end{pmatrix}\begin{pmatrix}\zeta&0\\\
0&\overline{\zeta}\end{pmatrix}=M\begin{pmatrix}\frac{1+\sqrt{D}}{2}&\frac{1-\sqrt{D}}{2}\\\
1&1\end{pmatrix}$ (3.42)

holds for some integer matrix $M\in\mathrm{M}_{2}(\mathbb{Z})$. By comparing
(3.33) with (3.42), we conclude

$\begin{pmatrix}1&k\\\
0&\frac{n}{2}\end{pmatrix}M=\gamma\begin{pmatrix}1&\frac{\mu_{2}-1}{2}\\\
0&\frac{m_{2}}{2}\end{pmatrix},$ (3.43)

so

$M=\frac{2}{n}\begin{pmatrix}\frac{n}{2}&-k\\\
0&1\end{pmatrix}\gamma\begin{pmatrix}1&\frac{\mu_{2}-1}{2}\\\
0&\frac{m_{2}}{2}\end{pmatrix}=\begin{pmatrix}*&*\\\
\frac{2c}{n}&*\end{pmatrix}.$ (3.44)

As $\frac{n}{2}\mid c$, the claim
$\gamma\in\Gamma_{0}\\!\left(\frac{n}{2}\right)$ has proven. ∎

Fixed a root $\nu\bmod n$, we have now established that the tops
$\frac{\mu}{m}+\mathrm{i}\frac{\sqrt{D}}{m}$ with $\mu\equiv 0\pmod{n}$ and
$\mu\equiv\nu\pmod{n}$ are exactly obtained from the $\Gamma_{0}(n)$-orbits of
the geodesics $\gamma_{1;k}\bm{c}_{I_{k}}$ for $1\leq k\leq h_{1}$ if $m$ or
$\frac{D-\mu^{2}}{m}$ is odd; otherwise, they come from either the
$\Gamma_{0}(n)$-orbits (when $n$ is odd) or the
$\Gamma_{0}(\frac{n}{2})$-orbits (when $n$ is even) of the geodesics
$\gamma_{2;l}\bm{c}_{J_{l}}$ for $1\leq l\leq h_{2}$. We now consider the
length of these geodesics projected to $\Gamma_{0}(n)\backslash\mathbb{H}$ or
$\Gamma_{0}(\frac{n}{2})\backslash\mathbb{H}$. This amounts to understanding
the stabilizers of these geodesics in $\Gamma_{0}(n)$ or
$\Gamma_{0}(\frac{n}{2})$, and we begin by recording a couple of basic facts
about the relation between the totally positive fundamental units
$\varepsilon_{1}$ and $\varepsilon_{2}$ of $\mathbb{Z}[\sqrt{D}]$ and
$\mathbb{Z}[\tfrac{1+\sqrt{D}}{2}]$.

######  Proposition 19.

Let $\varepsilon_{1}$ and $\varepsilon_{2}$ be totally positive fundamental
units of $\mathbb{Z}[\sqrt{D}]$ and $\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$
respectively.

  1. (i)

If $D\equiv 1\pmod{8}$, then $\varepsilon_{1}=\varepsilon_{2}$.

  2. (ii)

If $D\equiv 5\pmod{8}$, then either $\varepsilon_{1}=\varepsilon_{2}$ or
$\varepsilon_{1}=\varepsilon_{2}^{3}$.

###### Proof.

Set $\varepsilon_{2}=a+b\frac{1+\sqrt{D}}{2}$ with $a,b\in\mathbb{Z}$.

(i) We have $\operatorname{N}(\varepsilon_{2})=a^{2}+ab-b^{2}\frac{D-1}{4}=1$,
and since $D\equiv 1\pmod{8}$, we know $\frac{D-1}{4}$ is even. If $b$ is odd,
then $a(a+b)$ is even and so is $\operatorname{N}(\varepsilon_{2})$, a
contradiction. Hence, $b$ is even, so $\varepsilon_{2}\in\mathbb{Z}[\sqrt{D}]$
as required.

(ii) Now, in the case that $D\equiv 5\pmod{8}$, if $b$ is even, then
$\varepsilon_{1}=\varepsilon_{2}$ as before. Suppose that $b$ is odd, so
$\varepsilon_{2}\not\in\mathbb{Z}[\sqrt{D}]$, that is,
$\varepsilon_{1}\neq\varepsilon_{2}$. As $a^{2}+ab-b^{2}\frac{D-1}{4}=1$,

$\displaystyle\varepsilon_{2}^{2}$
$\displaystyle=a^{2}+ab(1+\sqrt{D})+b^{2}\tfrac{D-1}{4}+b^{2}\tfrac{1+\sqrt{D}}{2}$
(3.45) $\displaystyle=1-ab+b^{2}\tfrac{D-1}{2}+b(b+2a)\tfrac{1+\sqrt{D}}{2}.$

Since $b(b+2a)$ is odd, $\varepsilon_{2}^{2}\not\in\mathbb{Z}[\sqrt{D}]$ so
$\varepsilon_{1}\neq\varepsilon_{2}^{2}$. Now,

$\displaystyle\varepsilon_{2}^{3}$
$\displaystyle=a-a^{2}b+ab^{2}(D-1)+b^{3}\tfrac{D-1}{4}+b\left(1+2a^{2}+2ab+b^{2}\tfrac{D+1}{2}\right)\tfrac{1+\sqrt{D}}{2}$
(3.46) $\displaystyle=(a+ab^{2}D-b)+b(3+b^{2}D)\tfrac{1+\sqrt{D}}{2}.$

As $b$ is odd, $b(3+b^{2}D)$ is even. This implies
$\varepsilon_{2}^{3}\in\mathbb{Z}[\sqrt{D}]$ and so
$\varepsilon_{1}=\varepsilon_{2}^{3}$. ∎

We now turn to the stabilizers of the geodesics $\gamma_{1;k}\bm{c}_{I_{k}}$
and $\gamma_{2;l}\bm{c}_{I_{l}}$ in $\Gamma_{0}(n)$ or
$\Gamma_{0}(\frac{n}{2})$. These will have a generator of the form

$\gamma_{1;k}\mathfrak{B}_{k}\begin{pmatrix}\varepsilon_{1}^{j_{1}}&0\\\
0&\varepsilon_{1}^{-j_{1}}\end{pmatrix}\mathfrak{B}_{k}\gamma_{1;k}^{{}_{1}},\
\gamma_{2;l}\mathfrak{D}_{l}\begin{pmatrix}\varepsilon_{2}^{j_{2}}&0\\\
0&\varepsilon_{2}^{-j_{2}}\end{pmatrix}\mathfrak{D}_{l}^{-1}\gamma_{2;l}^{-1},$
(3.47)

where $j_{1}$ and $j_{2}$ are the smallest positive integers so that these
matrices are in $\Gamma_{0}(n)$ or $\Gamma_{0}(\frac{n}{2})$. We note that the
length of the projections of these geodesics to
$\Gamma_{0}(n)\backslash\mathbb{H}$ or
$\Gamma_{0}(\frac{n}{2})\backslash\mathbb{H}$ is then
$2j_{1}\log\varepsilon_{1}$, $2j_{2}\log\varepsilon_{2}$. The following lemmas
show that $j_{1}$ and $j_{2}$ are equal to $1$.

######  Lemma 20.

For any $k$, we have

$\gamma_{1;k}\mathfrak{B}_{k}\begin{pmatrix}\varepsilon_{1}&0\\\
0&\varepsilon_{1}^{-1}\end{pmatrix}\mathfrak{B}_{k}^{-1}\gamma_{1;k}^{-1}\in\Gamma_{0}(n).$
(3.48)

Similarly, for any $l$, we have

$\gamma_{2;l}\mathfrak{D}_{l}\begin{pmatrix}\varepsilon_{2}&0\\\
0&\varepsilon_{2}^{-1}\end{pmatrix}\mathfrak{D}_{l}^{-1}\gamma_{2;l}^{-1}\in\Gamma_{0}(n)$
(3.49)

if $n$ is odd; otherwise (if $n$ is even),

$\gamma_{2;l}\mathfrak{D}_{l}\begin{pmatrix}\varepsilon_{2}&0\\\
0&\varepsilon_{2}^{-1}\end{pmatrix}\mathfrak{D}_{l}^{-1}\gamma_{2;l}^{-1}\in\Gamma_{0}(\tfrac{n}{2}).$
(3.50)

###### Proof.

Let $\gamma$ denote the matrix in (3.48). From the definition of
$\gamma_{1;k}$, we have that

$\gamma_{1;k}\mathfrak{B}_{k}\begin{pmatrix}\xi&0\\\
0&\overline{\xi}\end{pmatrix}=\begin{pmatrix}1&\mu\\\
0&m\end{pmatrix}\begin{pmatrix}\sqrt{D}&-\sqrt{D}\\\ 1&1\end{pmatrix}$ (3.51)

for some totally positive $\xi$ and root $\mu\bmod m$ satisfying $m\equiv
0\pmod{n}$ and $\mu\equiv\nu\pmod{n}$. Therefore

$\gamma\begin{pmatrix}1&\mu\\\
0&m\end{pmatrix}\begin{pmatrix}\sqrt{D}&-\sqrt{D}\\\
1&1\end{pmatrix}=\begin{pmatrix}1&\mu\\\
0&m\end{pmatrix}\begin{pmatrix}\sqrt{D}&-\sqrt{D}\\\
1&1\end{pmatrix}\begin{pmatrix}\varepsilon_{1}&0\\\
0&\varepsilon_{1}^{-1}\end{pmatrix}.$ (3.52)

Applying Lemma 17 in the case that $m_{1}=m_{2}=m$ and $\mu_{1}=\mu_{2}=\mu$,
we conclude that $\gamma\in\Gamma_{0}(n)$.

The other claims in the lemma follow similarly using Lemma 18. ∎

The inclusion (3.50) raises the question of whether or not the matrix is in
fact in $\Gamma_{0}(n)$ instead of just $\Gamma_{0}(\frac{n}{2})$. As the
answer is useful in what follows, we record the following lemma.

######  Lemma 21.

Suppose that $n$ is even. Then we have
$\gamma_{2;l}\mathfrak{D}_{l}\begin{pmatrix}\varepsilon_{2}&0\\\
0&\varepsilon_{2}^{-1}\end{pmatrix}\mathfrak{D}_{l}^{-1}\gamma_{2;l}^{-1}\in\Gamma_{0}(n)$
if and only if $\varepsilon_{1}=\varepsilon_{2}$.

Before proving this lemma, we remark that in view of Proposition 19,
$\varepsilon_{1}=\varepsilon_{2}^{3}$ implies $D\equiv 5\pmod{8}$, which,
since $n$ is even, so we may then assume $n\equiv 2\pmod{4}$.

###### Proof.

We let $\gamma$ denote the matrix in question, so

$\gamma\begin{pmatrix}1&\frac{\mu-1}{2}\\\
0&\frac{m}{2}\end{pmatrix}\begin{pmatrix}\tfrac{1+\sqrt{D}}{2}&\tfrac{1-\sqrt{D}}{2}\\\
1&1\end{pmatrix}=\begin{pmatrix}1&\frac{\mu-1}{2}\\\
0&\frac{m}{2}\end{pmatrix}\begin{pmatrix}\tfrac{1+\sqrt{D}}{2}&\tfrac{1-\sqrt{D}}{2}\\\
1&1\end{pmatrix}\begin{pmatrix}\varepsilon_{2}&0\\\
0&\varepsilon_{2}^{-1}\end{pmatrix},$ (3.53)

where $m\equiv 0\pmod{n}$ and $\mu\equiv\nu\pmod{n}$. When
$\varepsilon_{1}=\varepsilon_{2}^{3}$, we must have $m\equiv n\pmod{2n}$. We
write $\varepsilon_{2}=a+b\sqrt{D}$ and recall that
$\varepsilon_{1}=\varepsilon_{2}$ if $b$ is even and
$\varepsilon_{1}=\varepsilon_{2}^{3}$ if $b$ is odd. We have

$\begin{pmatrix}\tfrac{1+\sqrt{D}}{2}&\tfrac{1-\sqrt{D}}{2}\\\
1&1\end{pmatrix}\begin{pmatrix}\varepsilon_{2}&0\\\
0&\varepsilon_{2}^{-1}\end{pmatrix}\begin{pmatrix}\tfrac{1+\sqrt{D}}{2}&\tfrac{1-\sqrt{D}}{2}\\\
1&1\end{pmatrix}^{-1}=\begin{pmatrix}*&*\\\ b&*\end{pmatrix},$ (3.54)

so $\gamma=\begin{pmatrix}*&*\\\ \frac{bm}{2}&*\end{pmatrix}$ and the lemma
follows. ∎

Putting the results of this section so far together, we obtain the following
theorems. Here we use the notation $\Gamma_{1;k}^{\prime}$ for the stabilizer
in $\Gamma_{0}(n)$ of the geodesic $\gamma_{1;k}\bm{c}_{I_{k}}$, so
$\Gamma_{1;k}^{\prime}=\gamma_{1;k}\Gamma_{1;k}\gamma_{1;k}^{-1}$, recalling
the notation $\Gamma_{1;k}$ of section 2. Similarly, we use
$\Gamma_{2;l}^{\prime}=\gamma_{2;l}\Gamma_{2;l}\gamma_{2;l}^{-1}$ to denote
the stabilizer of $\gamma_{2;l}\bm{c}_{J_{l}}$ in $\Gamma_{0}(n)$ if $n$ is
odd and in $\Gamma_{0}(\frac{n}{2})$ if $n$ is even.

######  Theorem 22.

Let $D>0$ be a square-free integer satisfying $D\equiv 1\pmod{4}$. Given a
fixed positive integer $n$ and $\nu\bmod n$ with $\nu^{2}\equiv D\pmod{n}$,
there exists a finite set of closed geodesics
$\\{\gamma_{1;1}\bm{c}_{I_{1}},\cdots,\gamma_{1;h_{1}}\bm{c}_{I_{h_{1}}}\\}$
all with the same length in $\Gamma_{0}(n)\backslash\mathbb{H}$, having the
following properties:

  1. (i)

For any positive integer $m$ and $\mu\bmod m$ satisfying $\mu^{2}\equiv
D\pmod{m}$ with $m\equiv 0\pmod{n}$ and $\mu\equiv\nu\pmod{n}$ and with either
$m$ or $\frac{D-\mu^{2}}{m}$ is odd, then there exists a unique $k$ and a
double coset
$\Gamma_{\infty}\gamma\Gamma_{1;k}^{\prime}\in\Gamma_{\infty}\backslash\Gamma_{0}(n)/\Gamma_{1;k}^{\prime}$
such that

$z_{\gamma\gamma_{1;k}\bm{c}_{I_{k}}}\equiv\frac{\mu}{m}+\mathrm{i}\frac{\sqrt{D}}{m}\pmod{\Gamma_{\infty}}.$
(3.55)

  2. (ii)

Conversely, given $k$ and a double coset
$\Gamma_{\infty}\gamma\Gamma_{1;k}^{\prime}\in\Gamma_{\infty}\backslash\Gamma_{0}(n)/\Gamma_{1;k}^{\prime}$
with positively oriented $\gamma\gamma_{1;k}\bm{c}_{I_{k}}$, there exists a
unique positive integer $m$ and a residue class $\mu\bmod m$ satisfying (3.55)
with $\mu^{2}\equiv D\pmod{m}$, $m\equiv 0\pmod{n}$, $\mu\equiv\nu\pmod{n}$
and either $m$ or $\frac{D-\mu^{2}}{m}$ being odd.

######  Theorem 23.

Let $D>0$ be a square-free integer satisfying $D\equiv 1\pmod{4}$. Given a
fixed positive integer $n$ and $\nu\bmod n$ with $\nu^{2}\equiv D\pmod{n}$,
there exists a finite set of closed geodesics
$\\{\gamma_{2;1}\bm{c}_{J_{1}},\cdots,\gamma_{2;h_{2}}\bm{c}_{J_{h_{2}}}\\}$,
having the following properties:

  1. (i)

For any positive integer $m$ and $\mu\bmod m$ satisfying $\mu^{2}\equiv
D\pmod{m}$ with $m\equiv 0\pmod{n}$ and $\mu\equiv\nu\pmod{n}$ and with $m$
and $\frac{D-\mu^{2}}{m}$ both even, then there exists a unique $l$ and a
double coset
$\Gamma_{\infty}\gamma\Gamma_{2;l}^{\prime}\in\Gamma_{\infty}\backslash\Gamma_{0}(n)/\Gamma_{2;l}^{\prime}$
if $n$ is odd or in
${\Gamma_{\infty}\backslash\Gamma_{0}(\frac{n}{2})/\Gamma_{2;l}^{\prime}}$ if
$n$ is even such that

$z_{\gamma\gamma_{2;l}\bm{c}_{J_{l}}}\equiv\frac{\mu}{m}+\mathrm{i}\frac{\sqrt{D}}{m}\pmod{\Gamma_{\infty}}.$
(3.56)

  2. (ii)

Conversely, given $l$ and a double coset
$\Gamma_{\infty}\gamma\Gamma_{2;l}^{\prime}\in\Gamma_{\infty}\backslash\Gamma_{0}(n)/\Gamma_{2;l}^{\prime}$
if $n$ is odd or
$\Gamma_{\infty}\backslash\Gamma_{0}(\frac{n}{2})/\Gamma_{2;l}^{\prime}$ if
$n$ is even such that $\gamma\gamma_{2;l}\bm{c}_{J_{l}}$ is positively
oriented, there exists a unique positive integer $m$ and a residue class
$\mu\bmod m$ satisfying (3.56) with $\mu^{2}\equiv D\pmod{m}$, $m\equiv
0\pmod{n}$, $\mu\equiv\nu\pmod{n}$ and both $m$ and $\frac{D-\mu^{2}}{m}$
being even.

To combine Theorems 22 and 23, we break the $\Gamma_{0}(\frac{n}{2})$-orbits
appearing in Theorem 23 when $n$ is even into a union of orbits under the
subgroup $\Gamma_{0}(n)$. In this way, we obtain a uniform acting group,
$\Gamma_{0}(n)$, as stated in Theorem 1 and as needed to apply the results of
[11].

We first look at the index
$\left[\Gamma_{0}(\frac{n}{2}):\Gamma_{0}(n)\right]$. The well-known formula

$\left[\operatorname{SL}(2,\mathbb{Z}):\Gamma_{0}(n)\right]=n\prod_{p\mid
n}\left(1+\frac{1}{p}\right)$ (3.57)

implies

$\left[\Gamma_{0}\\!\left(\tfrac{n}{2}\right):\Gamma_{0}(n)\right]=\begin{cases}2&\text{if
}n\equiv 0\pmod{4}\\\ 3&\text{if }n\equiv 2\pmod{4}.\end{cases}$ (3.58)

In the case that $n\equiv 0\pmod{4}$, we have distinct cosets $\Gamma_{0}(n)$
and $\Gamma_{0}(n)\gamma_{0}^{\prime}$, say, and in the case that $n\equiv
2\pmod{4}$, we include $\Gamma_{0}(n)\gamma_{0}^{\prime\prime}$ as the third
coset.

Given the geodesic $\gamma_{2;l}\bm{c}_{J_{l}}$, one may ask whether the
geodesics
$\gamma_{2;l}\bm{c}_{J_{l}},\gamma_{0}^{\prime}\gamma_{2;l}\bm{c}_{J_{l}}$ and
$\gamma_{0}^{\prime\prime}\gamma_{2;l}\bm{c}_{J_{l}}$ are
$\Gamma_{0}(n)$-equivalent. Geometrically, this is asking about the splitting
behaviour of the geodesic $\gamma_{2;l}\bm{c}_{J_{l}}$ as it lifts from the
surface $\Gamma_{0}(\frac{n}{2})\backslash\mathbb{H}$ to the surface
$\Gamma_{0}(n)\backslash\mathbb{H}$, see figures 4 and 5.

$\Gamma_{0}(n)\backslash\mathbb{H}$
:$\Gamma_{0}(\frac{n}{2})\backslash\mathbb{H}$ :(a) totally split(b) inert
Figure 4: A mapping from $\Gamma_{0}(n)\backslash\mathbb{H}$ to
$\Gamma_{0}(\frac{n}{2})\backslash\mathbb{H}$ when $n\equiv 0\pmod{4}$. (a)
Two single geodesics are projected to a single geodesic with length
$2\log\varepsilon_{2}$. (b) A double geodesic is projected to a single
geodesic,

Let
$\gamma_{s}=\gamma_{2;l}\mathfrak{D}_{l}\begin{pmatrix}\varepsilon_{2}&0\\\
0&\varepsilon_{2}^{-1}\end{pmatrix}\mathfrak{D}_{l}^{-1}\gamma_{2;l}^{-1}$ be
the generator of the stabilizer of $\gamma_{2;l}\bm{c}_{J_{l}}$ in
$\Gamma_{0}(\frac{n}{2})$. Considering $n\equiv 0\pmod{4}$ first, we have
$\gamma_{s;l}^{2}\in\Gamma_{0}(n)$, and $\gamma_{2;l}\bm{c}_{J_{l}}$ is
$\Gamma_{0}(n)$-equivalent to $\gamma_{0}^{\prime}\gamma_{2;l}\bm{c}_{J_{l}}$
if and only if $\gamma_{s}\not\in\Gamma_{0}(n)$. Geometrically, if
$\gamma_{s}\in\Gamma_{0}(n)$, then the geodesic in
$\Gamma_{0}(\frac{n}{2})\backslash\mathbb{H}$ lifts to two geodesics in
$\Gamma_{0}(n)\backslash\mathbb{H}$, case (a) in Figure 4, and if
$\gamma_{s}\not\in\Gamma_{0}(n)$ then the geodesic lifts to a single geodesic,
case (b) in Figure 4. However, in this case ($n\equiv 0\pmod{4}$) we may
assume $D\equiv 1\pmod{8}$, and so by Lemma 21 and Proposition 19,
$\gamma_{s}\in\Gamma_{0}(n)$ and so case (b) does not occur.

Now if $n\equiv 2\pmod{4}$, using Proposition 19 and the same calculation as
in the proof of Lemma 21 with $\varepsilon_{2}$ replaced by
$\varepsilon_{2}^{3}$, we have $\gamma_{s}^{3}\in\Gamma_{0}(n)$. These
calculations show in addition that either $\gamma_{s}\in\Gamma_{0}(n)$ or
$\gamma_{s},\gamma_{s}^{2}\not\in\Gamma_{0}(n)$. The first case corresponds to
case (c) in Figure 5 and the second corresponds to case (d), and we note that
more complicated behaviour, like that illustrated in case (e), does not occur.
The cases (c) and (d) correspond to $\varepsilon_{1}=\varepsilon_{2}$ and
$\varepsilon_{1}=\varepsilon_{2}^{3}$.

$\Gamma_{0}(n)\backslash\mathbb{H}$
:$\Gamma_{0}(\frac{n}{2})\backslash\mathbb{H}$ :(c) totally split(d) inert(e)
split Figure 5: A mapping from $\Gamma_{0}(n)\backslash\mathbb{H}$ to
$\Gamma_{0}(\frac{n}{2})\backslash\mathbb{H}$ when $n\equiv 2\pmod{4}$. (c)
Three single geodesics are projected to a single geodesic with length
$2\log\varepsilon_{2}$. (d) A triple geodesic with length
$2\log\varepsilon_{2}^{3}$ is projected to a single geodesic. (e) A single
geodesic and a double geodesic are projected to a single geodesic.

We now combine Theorems 22 and 23 to prove our main result, Theorem 1.

###### Proof of Theorem 1.

Define the number

$s=\begin{cases}1&\text{if $D\equiv 5\pmod{8}$ and
$\varepsilon_{1}=\varepsilon_{2}^{3}$,}\\\ 2&\text{if $D\equiv 1\pmod{8}$ and
$n\equiv 0\pmod{4}$,}\\\ 3&\text{otherwise.}\end{cases}$ (3.59)

Let $\\{\bm{c}_{1},\cdots,\bm{c}_{h}\\}$ be a finite set of closed geodesics
where $h=h_{1}+sh_{2}$. If $s=1$, then set

$\bm{c}_{k}=\begin{cases}\gamma_{1;k}\bm{c}_{I_{k}}&1\leq k\leq h_{1},\\\
\gamma_{2;k-h_{1}}\bm{c}_{J_{k-h_{1}}}&h_{1}+1\leq k\leq
h_{1}+h_{2}.\end{cases}$ (3.60)

If $s=2$, then
$\Gamma_{0}(\frac{n}{2})=\Gamma_{0}(n)\cup\Gamma_{0}(n)\gamma_{0}^{\prime}$
for some $\gamma_{0}^{\prime}\in\Gamma_{0}(\frac{n}{2})$ and set

$\bm{c}_{k}=\begin{cases}\gamma_{1;k}\bm{c}_{I_{k}}&1\leq k\leq h_{1},\\\
\gamma_{2;k-h_{1}}\bm{c}_{J_{k-h_{1}}}&h_{1}+1\leq k\leq h_{1}+h_{2},\\\
\gamma_{0}^{\prime}\gamma_{2;k-h_{1}-h_{2}}\bm{c}_{J_{k-h_{1}-h_{2}}}&h_{1}+h_{2}+1\leq
k\leq h_{1}+2h_{2}.\end{cases}$ (3.61)

Otherwise $s=3$, we have
$\Gamma_{0}(\frac{n}{2})=\Gamma_{0}(n)\cup\Gamma_{0}(n)\gamma_{0}^{\prime}\cup\Gamma_{0}(n)\gamma_{0}^{\prime\prime}$
for some
$\gamma_{0}^{\prime},\gamma_{0}^{\prime\prime}\in\Gamma_{0}(\frac{n}{2})$ and
set

$\bm{c}_{k}=\begin{cases}\gamma_{1;k}\bm{c}_{I_{k}}&1\leq k\leq h_{1},\\\
\gamma_{2;k-h_{1}}\bm{c}_{J_{k-h_{1}}}&h_{1}+1\leq k\leq h_{1}+h_{2},\\\
\gamma_{0}^{\prime}\gamma_{2;k-h_{1}-h_{2}}\bm{c}_{J_{k-h_{1}-h_{2}}}&h_{1}+h_{2}+1\leq
k\leq h_{1}+2h_{2},\\\
\gamma_{0}^{\prime\prime}\gamma_{2;k-h_{1}-2h_{2}}\bm{c}_{J_{k-h_{1}-2h_{2}}}&h_{1}+2h_{2}+1\leq
k\leq h_{1}+3h_{2}.\end{cases}$ (3.62)

Define

$\Gamma_{k}=\begin{cases}\Gamma_{1;k}^{\prime}&1\leq k\leq h_{1},\\\
\Gamma_{2;k-h_{1}-s^{\prime}h_{2}}^{\prime}&h_{1}+s^{\prime}h_{2}+1\leq k\leq
h_{1}+sh_{2},0\leq s^{\prime}<s.\end{cases}$ (3.63)

The claims in Theorem 1 now follow from Theorems 22 and 23. ∎

##  4 Pair correlation density

We recall from theorem $4.10$ in [11] that the pair correlation density is
given by the even and continuous function

$w(v)=\frac{1}{\mathrm{vol}_{\mathbb{H}}(\Gamma\backslash\mathbb{H})}\sum_{k,l=1}^{h}\sum_{\begin{subarray}{c}\gamma\in\Gamma_{\bm{c}_{k}}\backslash\Gamma/\Gamma_{\bm{c}_{l}}\\\
\gamma\bm{c}_{l}\neq\bm{c}_{k},\overline{\bm{c}}_{k}\end{subarray}}\frac{1}{v^{2}}H_{\text{sgn}(g_{k}^{-1}\gamma
g_{l}(0))}(q,v/\kappa_{\Gamma}),$ (4.1)

where $\kappa_{\Gamma}$ is the total length of the geodesics divided by
$2\pi\mathrm{vol}_{\mathbb{H}}(\Gamma\backslash\mathbb{H})$ and
$q=q(\gamma,l_{1},l_{2})=\frac{r+1}{r-1}$ with $r$ the cross-ratio

$r=\frac{((\gamma\bm{c}_{l_{2}})^{+}-c_{l_{1}}^{-})((\gamma\bm{c}_{l_{2}})^{-}-\bm{c}_{l_{1}}^{+})}{((\gamma\bm{c}_{l_{2}})^{+}-\bm{c}_{l_{1}}^{+})((\gamma\bm{c}_{l_{2}})^{-}-\bm{c}_{l_{1}}^{-})},$
(4.2)

and

$H_{+}(q,v)=\begin{cases}0&\text{if }q<-1\\\ 0&\text{if }|q|<1\text{ and
}v<\sqrt{2-2q}\\\ h_{q}(s_{1}(q,v))-h_{q}(s_{2}(q,v))&\text{if }|q|<1\text{
and }v>\sqrt{2-2q}\\\ h_{q}(s_{1}(q,v))-h_{q}(-q+\sqrt{q^{2}-1})&\text{if
}q>1,\end{cases}$ (4.3)

and

$H_{-}(q,v)=\begin{cases}0&\text{if }q<-1\text{ and }|v|<\sqrt{2-2q}\\\
h_{q}(s_{1}(q,v))-h_{q}(s_{2}(q,v))&\text{if }q<-1\text{ and
}|v|>\sqrt{2-2q}\\\ h_{q}(s_{1}(q,v))-h_{q}(s_{2}(q,v))&\text{if }|q|<1\text{
and }v<-\sqrt{2-2q}\\\ 0&\text{if }|q|<1\text{ and }v>-\sqrt{2-2q}\\\
h_{q}(-q-\sqrt{q^{2}-1})-h_{q}(s_{2}(q,v))&\text{if }q>1,\end{cases}$ (4.4)

with

$y(q,v)=\sqrt{v^{2}+q^{2}-1},$ (4.5) $s_{1}(q,v)=\frac{-q+y(q,v)}{v+1},\qquad
s_{2}(q,v)=v-q-y(q,v),$ (4.6)

and

$h_{q}(s)=\log\frac{s+q}{1-s^{2}}.$ (4.7)

We can simplify $H_{\pm}(q,v)$ as follows. Starting with

$h_{q}(s_{1}(q,v))=\log\frac{\left(v+1\right)\left(vq+y(q,v)\right)}{2\left(qy(q,v)-q^{2}+v+1\right)},$
(4.8)

we multiply the numerator and the denominator by $qy(q,v)+q^{2}-v-1$, which
yields

$\left(qy(q,v)-q^{2}+v+1\right)\left(qy(q,v)+q^{2}-v-1\right)=\left(q^{2}-1\right)\left(v+1\right)^{2},$
(4.9)

and

$\left(vq+y(q,v)\right)\left(qy(q,v)+q^{2}-v-1\right)=\left(q^{2}-1\right)\left(v+1\right)\left(y(q,v)+q\right).$
(4.10)

We obtain

$h_{q}(s_{1}(q,v))=\log\frac{y(q,v)+q}{2},$ (4.11)

which is clearly an even function.

As

$h_{q}(s_{2}(q,v))=\log\frac{v-y(q,v)}{2\left((v-q)y(q,v)-(v-q)^{2}-vq+1\right)},$
(4.12)

we multiply by the factor $(v-q)y(q,v)+(v-q)^{2}+vq-1$, which gives

$\left(1-s_{2}^{2}(q,v)\right)\left((v-q)y(q,v)+(v-q)^{2}+vq-1\right)=2\left(1-q^{2}\right)\left(v^{2}-1\right),$
(4.13)

and

$\left(v-y(q,v)\right)\left((v-q)y(q,v)+(v-q)^{2}+vq-1\right)=\left(1-q^{2}\right)\left(y(q,v)-q\right).$
(4.14)

Therefore,

$h_{q}(s_{2}(q,v))=\log\frac{y(q,v)-q}{2\left(v^{2}-1\right)},$ (4.15)

which is an even function as well.

Now

$\displaystyle h_{q}(s_{1}(q,v))-h_{q}(s_{2}(q,v))$
$\displaystyle=\log\frac{\left(y(q,v)+q\right)\left(v^{2}-1\right)}{y(q,v)-q}$
(4.16) $\displaystyle=2\log(q+\sqrt{v^{2}+q^{2}-1})$

and

$h_{q}(-q\pm\sqrt{q^{2}-1})=\log\frac{q\pm\sqrt{q^{2}-1}}{2},$ (4.17)

so we can rewrite

$H_{+}(q,v)=\begin{cases}0&\text{if }q<-1\\\ 0&\text{if }|q|<1\text{ and
}v<\sqrt{2-2q}\\\ 2\log(q+\sqrt{v^{2}+q^{2}-1})&\text{if }|q|<1\text{ and
}v>\sqrt{2-2q}\\\ \log((q+\sqrt{v^{2}+q^{2}-1})(q-\sqrt{q^{2}-1}))&\text{if
}q>1,\end{cases}$ (4.18)

and

$\\!H_{-}(q,v)=\begin{cases}0&\text{if }q<-1\text{ and }|v|<\sqrt{2-2q}\\\
2\log(q+\sqrt{v^{2}+q^{2}-1})&\text{if }q<-1\text{ and }|v|>\sqrt{2-2q}\\\
0&\text{if }|q|<1\text{ and }v>-\sqrt{2-2q}\\\
2\log(q+\sqrt{v^{2}+q^{2}-1})&\text{if }|q|<1\text{ and }v<-\sqrt{2-2q}\\\
\log((q+\sqrt{v^{2}+q^{2}-1})(q-\sqrt{q^{2}-1}))&\text{if }q>1.\end{cases}$
(4.19)

$0$$1$$r$(a+) $1<r<\infty,$$\qquad\,1<q<\infty.$

$0$$r$$1$(b+) $0<r<1,$$\quad\;\;\,-\infty<q<-1.$

$0$$r$$1$(c+) $-\infty<r<0,$$\qquad\;\;\,-1<q<1.$

$0$$-1$$-r$(a-) $1<r<\infty,$$\qquad\,1<q<\infty.$

$0$$-r$$-1$(b-) $0<r<1$,$\quad\;\;\,-\infty<q<-1.$

$0$$-1$$-r$(c-) $-\infty<r<0,$$\qquad\;\;\,-1<q<1.$

Figure 6: The six standard configurations

With these expressions, it is clear to see that $H_{\pm}(q,v)$ are even
functions of $v$ for a fixed $|q|>1$. However, for $|q|<1$ these are not even
functions of $v$. That the sum (4.1) is even (which of course follows
immediately from the definition of the pair correlation) can be made manifest
as follows: Any pair of geodesics in $\mathbb{H}$ that do not share an
endpoint in $\partial\mathbb{H}$ can be brought by an element of
$\operatorname{SL}(2,\mathbb{R})$ into one of the six standard forms
illustrated in Figure 6. The cases with $|q|<1$ are (c+) and (c-), the sign
corresponding the whether the pair contributes to $H_{+}$ or $H_{-}$, see
[11]. The evenness of the sum (4.1) then follows from the fact that the terms
corresponding to (c+) are in $q$-preserving bijection with those corresponding
to (c-).

Such a bijection is given by
$\Gamma_{\bm{c}_{l_{1}}}\gamma\Gamma_{\bm{c}_{l_{2}}}\mapsto\Gamma_{\bm{c}_{l_{2}}}\gamma^{-1}\Gamma_{\bm{c}_{l_{1}}}$.
Indeed, if there is $g_{1}\in\operatorname{SL}(2,\mathbb{R})$ so that the
geodesics $g_{1}\bm{c}_{l_{1}}$ and $g_{2}\gamma\bm{c}_{l_{2}}$ are as in (c+)
with $g_{1}\bm{c}_{l_{1}}$ vertical, then $g_{1}\gamma$ brings the geodesics
$\bm{c}_{l_{2}}$ and $\gamma^{-1}\bm{c}_{l_{1}}$ to the form (c+), however
with $g_{2}\gamma^{-1}\bm{c}_{l_{1}}$ vertical. The geodesics can then be
brought to the form (c-), with $\bm{c}_{l_{2}}$ mapping to vertical, as
required, by an application of the transformation $x\mapsto\frac{-rx+r}{x-r}$,
which can be seen to preserve the cross-ratio $r$ and hence $q$.

##  5 Negative $D$

In this final section, we briefly sketch analogous results in the case that
$D$ is negative. The negative setting is simpler in the sense that we consider
$\Gamma$-orbits of points in $\mathbb{H}$ instead of the tops of geodesics,
and their statistical distribution has been thoroughly studied. However,
algebraically the $D<0$ setting is almost identical with the following
modification: instead of embedding $\mathbb{Q}(\sqrt{D})$ into a two-
dimensional real subspace of $\mathbb{C}^{2}$ via $(\xi,\overline{\xi})$ as in
the real case, we embed $\mathbb{Q}(\sqrt{D})$ inside $\mathbb{R}^{2}$ by

$a+b\sqrt{D}\mapsto(a,b\sqrt{|D|}).$

The first embedding is transformed into the second by the matrix
$P=\begin{pmatrix}-\frac{\mathrm{i}}{2}&\frac{1}{2}\\\
\frac{\mathrm{i}}{2}&\frac{1}{2}\end{pmatrix}$. Since

$\begin{pmatrix}\sqrt{D}&-\sqrt{D}\\\
1&1\end{pmatrix}P=\begin{pmatrix}\sqrt{|D|}&0\\\ 0&1\end{pmatrix}$ (5.1)

and

$P^{-1}\begin{pmatrix}\xi&0\\\
0&\overline{\xi}\end{pmatrix}P=\begin{pmatrix}\operatorname{Re}\xi&-\operatorname{Im}\xi\\\
\operatorname{Im}\xi&\operatorname{Re}\xi\end{pmatrix},$ (5.2)

then rewriting (2.23), we have

$\begin{pmatrix}1&\mu\\\ 0&m\end{pmatrix}\begin{pmatrix}\sqrt{|D|}&0\\\
0&1\end{pmatrix}=\gamma\widetilde{\mathfrak{B}}_{k}\begin{pmatrix}\operatorname{Re}\xi&-\operatorname{Im}\xi\\\
\operatorname{Im}\xi&\operatorname{Re}\xi\end{pmatrix},$ (5.3)

where

$\widetilde{\mathfrak{B}}_{k}=\mathfrak{B}_{k}P=\begin{pmatrix}\operatorname{Im}\beta_{k1}&\operatorname{Re}\beta_{k1}\\\
\operatorname{Im}\beta_{k2}&\operatorname{Re}\beta_{k2}\end{pmatrix}.$ (5.4)

We note that the matrix on the right of (5.3) stabilizes the point
$\mathrm{i}\in\mathbb{H}$, as opposed to stabilizing the geodesic
$\\{\mathrm{i}y:y>0\\}\subset\mathbb{H}$ in the real setting.

The left side of (5.3) yields

$\begin{pmatrix}1&\mu\\\ 0&m\end{pmatrix}\begin{pmatrix}\sqrt{|D|}&0\\\
0&1\end{pmatrix}\mathrm{i}=\frac{\mu}{m}+\mathrm{i}\frac{\sqrt{|D|}}{m},$
(5.5)

and the right side of (5.3) yields

$\gamma\begin{pmatrix}\operatorname{Im}\beta_{k1}&\operatorname{Re}\beta_{k1}\\\
\operatorname{Im}\beta_{k2}&\operatorname{Re}\beta_{k2}\end{pmatrix}\begin{pmatrix}\operatorname{Re}\xi&-\operatorname{Im}\xi\\\
\operatorname{Im}\xi&\operatorname{Re}\xi\end{pmatrix}\mathrm{i}=\gamma\frac{\xi\beta_{k1}}{\xi\beta_{k2}}=\gamma
z_{I_{k}},\;\text{where}\;z_{I_{k}}=\frac{\beta_{k1}}{\beta_{k2}}.$ (5.6)

Therefore, $\gamma z_{I_{k}}=\frac{\mu}{m}+\mathrm{i}\frac{\sqrt{|D|}}{m}$.
With a similar construction as in the positive $D$ case, we have the following
analogue of Theorem 22.

######  Theorem 24.

Let $D<0$ be a square-free integer satisfying $D\equiv 1\pmod{4}$ and $h_{1}$
be the class number of $\mathbb{Z}[\sqrt{D}]$. Given $n>0$ and $\nu\bmod n$
with $\nu^{2}\equiv D\pmod{n}$, there exists a finite set of points
$\\{z_{I_{1}},\cdots,z_{I_{h_{1}}}\\}$ in $\mathbb{H}$ with the following
properties:

  1. (i)

For $m\in\mathbb{N}$, let $\mu\bmod m$ satisfy $\mu^{2}\equiv D\pmod{m}$ such
that $m\equiv 0\pmod{n}$ and $\mu\equiv\nu\pmod{n}$. If either $m$ or
$\frac{D-\mu^{2}}{m}$ is odd, then there exists a unique $k$ and a double
coset
$\Gamma_{\infty}\gamma\Gamma_{1;k}\in\Gamma_{\infty}\backslash\Gamma_{0}(n)/\Gamma_{1;k}$
such that

$\gamma
z_{I_{k}}\equiv\frac{\mu}{m}+\mathrm{i}\frac{\sqrt{|D|}}{m}\pmod{\Gamma_{\infty}}.$
(5.7)

  2. (ii)

Conversely, given $k$ and a double coset
$\Gamma_{\infty}\gamma\Gamma_{1;k}\in\Gamma_{\infty}\backslash\Gamma_{0}(n)/\Gamma_{1;k}$,
there exists a unique positive integer $m$ and a residue class $\mu\bmod m$
satisfying (5.7) and either $m$ or $\frac{D-\mu^{2}}{m}$ being odd.

In the same way, we obtain the analogue of Theorem 23.

######  Theorem 25.

Let $D<0$ be a square-free integer satisfying $D\equiv 1\pmod{4}$ and $h_{2}$
be the class number of $\mathbb{Z}[\frac{1+\sqrt{D}}{2}]$. Given $n>0$ and
$\nu\bmod n$ with $\nu^{2}\equiv D\pmod{n}$, there exists a finite set of
points $\\{z_{J_{1}},\cdots,z_{J_{h_{2}}}\\}$ in $\mathbb{H}$ with the
following properties:

  1. (i)

For even $m\in\mathbb{N}$, let $\mu\bmod m$ satisfy $\mu^{2}\equiv D\pmod{m}$
and $\frac{D-\mu^{2}}{m}$ even such that $m\equiv 0\pmod{n}$ and
$\mu\equiv\nu\pmod{n}$. If $n$ is odd (resp. $n$ is even), then there exists a
unique $l$ and a double coset
$\Gamma_{\infty}\gamma\Gamma_{2;l}\in\Gamma_{\infty}\backslash\Gamma_{0}(n)/\Gamma_{2;l}$
(resp. $\Gamma_{\infty}\backslash\Gamma_{0}(\frac{n}{2})/\Gamma_{2;l}$) such
that

$\gamma
z_{J_{l}}\equiv\frac{\mu}{m}+\mathrm{i}\frac{\sqrt{D}}{m}\pmod{\Gamma_{\infty}}.$
(5.8)

  2. (ii)

Conversely, given $l$ and a double coset
$\Gamma_{\infty}\gamma\Gamma_{J;l}\in\Gamma_{\infty}\backslash\Gamma_{0}(n)/\Gamma_{2;l}$
(resp. ${\Gamma_{\infty}\backslash\Gamma_{0}(\frac{n}{2})/\Gamma_{2;l}}$),
there exists a unique even positive integer $m$ and a residue class $\mu\bmod
m$ satisfying (5.8) and $\frac{D-\mu^{2}}{m}$ being even.

Combining these two theorems, we obtain the analogue of Theorem 1.

######  Theorem 26.

Let $D<0$ be a square-free integer satisfying $D\equiv 1\pmod{4}$. Given $n>0$
and $\nu\bmod n$ with $\nu^{2}\equiv D\pmod{n}$, there exists a finite set of
points $\\{z_{1},\cdots,z_{h}\\}$ in $\mathbb{H}$ with the following
properties:

  1. (i)

For $m\in\mathbb{N}$, let $\mu\bmod m$ satisfy $\mu^{2}\equiv D\pmod{m}$ such
that $m\equiv 0\pmod{n}$ and $\mu\equiv\nu\pmod{n}$. Then there exists a
unique $k$ and a double coset
$\Gamma_{\infty}\gamma\Gamma_{k}\in\Gamma_{\infty}\backslash\Gamma_{0}(n)/\Gamma_{k}$
such that

$\gamma
z_{k}\equiv\frac{\mu}{m}+\mathrm{i}\frac{\sqrt{D}}{m}\pmod{\Gamma_{\infty}}.$
(5.9)

  2. (ii)

Conversely, given $k$ and a double coset
$\Gamma_{\infty}\gamma\Gamma_{k}\in\Gamma_{\infty}\backslash\Gamma_{0}(n)/\Gamma_{k}$,
there exists a unique positive integer $m$ and a residue class $\mu\bmod m$
satisfying (5.9).

Now, to obtain the analogues of Theorems 1.7 and 3, we can apply the results
of [10] instead of those in [11]. The paper [10] studies the distribution of
real parts of an orbit of a point in $\mathbb{H}$ (and higher-dimensional
hyperbolic space). This is referred to as the ”cuspidal” observer case of the
distribution of angles in hyperbolic lattices, which has been studied in [1,
2, 9, 12, 13] and others. The pair correlation in this setting is computed in
[8] and [10], giving a form similar to the one obtained here and in [11].

## References

  * [1] Florin P. Boca, Vicentiu Pasol, Alexandru A. Popa, and Alexandru Zaharescu.  Pair correlation of angles between reciprocal geodesics on the modular surface.  Algebra Number Theory, 8(4):999–1035, 2014.
  * [2] Florin P. Boca, Alexandru A. Popa, and Alexandru Zaharescu.  Pair correlation of hyperbolic lattice angles.  International Journal of Number Theory, 10(8):1955–1989, 2014.
  * [3] Victor A. Bykovskii.  Spectral decompositions of certain automorphic functions and their number-theoretic applications.  Journal of Soviet Mathematics, 36(1):8–21, 1987.
  * [4] W. Duke, J. Friedlander, and H. Iwaniec.  Equidistribution of roots of a quadratic congruence to prime moduli.  The Annals of Mathematics, 141(2):423–441, 1995.
  * [5] Dennis A. Hejhal.  Roots of quadratic congruences and eigenvalues of the non-Euclidean Laplacian.  The Selberg trace formula and related topics, Contemporary Mathematics, 53:227–339, 1986.
  * [6] Christopher Hooley.  On the number of divisors of quadratic polynomials.  Acta Mathematica, 110:97–114, 1963.
  * [7] Henryk Iwaniec.  Almost-primes represented by quadratic polynomials.  Inventiones Mathematicae, 47(2):171–188, 1978.
  * [8] Dubi Kelmer and Alex Kontorovich.  On the pair correlation density for hyperbolic angles.  Duke Mathematical Journal, 164(3):473–509, 2015.
  * [9] Christopher Lutsko.  Directions in orbits of geometrically finite hyperbolic subgroups.  Mathematical Proceedings of the Cambridge Philosophical Society, 171:277–316, 2020.
  * [10] Jens Marklof and Ilya Vinogradov.  Directions in hyperbolic lattices.  Journal für die reine und angewandte Mathematik (Crelles Journal), 2018(740):161–186, 2018.
  * [11] Jens Marklof and Matthew Welsh.  Fine-scale distribution of roots of quadratic congruences, 2021(See arXiv:2105.02854).  Duke Mathematical Journal to appear.
  * [12] Morten S. Risager and Zeév Rudnick.  On the statistics of the minimal solution of a linear Diophantine equation and uniform distribution of the real part of orbits in hyperbolic spaces.  Spectral analysis in geometry and number theory, Contemporary Mathematics, 484:187–194, 2009.
  * [13] Morten S. Risager and Anders Södergren.  Angles in hyperbolic lattices: the pair correlation density.  Transactions of the American Mathematical Society, 369(4):2807–2841, 2017.