The Recursive Structures of Manin Symbols over $\mathbb{Q}$, Cusps and Elliptic Points on X₀ (N)

Abstract

Firstly, we present a more explicit formulation of the complete system $D(N)$ of representatives of Manin’s symbols over $\mathbb{Q}$, which was initially given by Shimura. Then, we establish a bijection between $D(M)\times D(N)$ and $D(MN)$ for $(M,N)=1$, which reveals a recursive structure between Manin’s symbols of different levels. Based on Manin’s complete system $\mathsf{\Pi }(N)$ of representatives of cusps on $X_0(N)$ and Cremona’s characterization of the equivalence between cusps, we establish a bijection between a subset $C(N)$ of $D(N)$ and $\mathsf{\Pi }(N)$, and then establish a bijection between $C(M)\times C(N)$ and $C(MN)$ for $(M,N)=1$. We also provide a recursive structure for elliptical points on $X_0(N)$. Based on these recursive structures, we obtain recursive algorithms for constructing Manin symbols over $\mathbb{Q}$, cusps, and elliptical points on $X_0(N)$. This may give rise to more efficient algorithms for modular elliptic curves. As direct corollaries of these recursive structures, we present a recursive version of the genus formula and prove constructively formulas of the numbers of $D(N)$, cusps, and elliptic points on $X_0(N)$.

1. Introduction

In his seminal monograph [1] (Chapter 1, Proposition 1.43), G. Shimura defined a complete set $D(N)$ of representatives for the projective line ${\mathbb{P}}^1(\mathbb{Z}/N\mathbb{Z})$ over $\mathbb{Z}/N\mathbb{Z}$ to be all couples $\{c,d\}$ of positive integers satisfying

$$(\ast )(c,d)=1,d|N,1⩽c⩽N/d(orcinanysetofrepresentativesfor\mathbb{Z}modulo(N/d)),$$

where $(c,d)$ denote the greatest common divisor of integers c and d.

Let $[x]$ be the greatest integer less than or equal to x. For two integers $a,b$ with $b\ne 0$, define

$${[\frac{a}{b}]}^{\prime }=\left\{\begin{array}{c}\frac{a}{b}-1\mathrm{if}b|a,\hfill \\ [\frac{a}{b}]\mathrm{otherwise},\hfill \end{array}\right.$$

then $1⩽a-b{[\frac{a}{b}]}^{\prime }⩽b$. In this paper, we define

$$\begin{array}{c}\hfill D(N)=\{(c,d):c,d\in \mathbb{Z},c,d⩾1,c|N,(c,d)=1and\\ \hfill (c,d-\frac{N}{c}({[\frac{cd}{N}]}^{\prime }-n))⩾2for0⩽n<{[\frac{cd}{N}]}^{\prime }\}.\end{array}$$

(1)

We then establish a bijection between $D(M)\times D(N)$ and $D(MN)$ for $(M,N)=1$ in Section 2. This result gives a recursive algorithm to construct the projective line ${\mathbb{P}}^1(\mathbb{Z}/N\mathbb{Z})$ over $\mathbb{Z}/N\mathbb{Z}$.

Let $\mathsf{\Pi }(N)=\{[\delta ;a\mathrm{mod}(\delta ,N{\delta }^{-1})]:a,\delta \in \mathbb{Z},\delta ⩾1,\delta |N,1⩽a⩽(\delta ,N{\delta }^{-1})\}$. In [2] (Proposition 2.2), Manin proved that there exists a bijection between $\mathsf{\Pi }(N)$ and the set of cusps on $X_0(N)$. Based on Manin’s result and Cremona’s characterization (See Proposition 3), we identify $\mathsf{\Pi }(N)$ with

$$\begin{array}{c}\hfill C(N)=\{(c,d):c,d\in \mathbb{Z},1⩽c⩽N,c|N,(c,d)=1\mathrm{and}\\ \hfill (c,d-(c,N{c}^{-1}){[\frac{d}{(c,N{c}^{-1})}]}^{\prime }+\frac{Nn}{c})⩾2\mathrm{for}0⩽n<\frac{c(c,N{c}^{-1})}{N}{[\frac{d}{(c,N{c}^{-1})}]}^{\prime }\},\end{array}$$

(2)

which is a subset of $D(N)$. In Section 3, we establish a bijection between $C(N_1{N}_2)$ and $C(N_1)\times C(N_2)$ for $(N_1,N_2)=1$. This result gives a recursive algorithm to construct the complete set of representatives of ${\mathsf{\Gamma }}_0(N)$-inequivalent cusps.

Define

$$\begin{array}{cc}\hfill E_2(N)& =\{(1,d):(1,d)\in D(N),1+d^2\equiv 0(\mathrm{mod}N)\},\hfill \\ \hfill E_3(N)& =\{(1,d):(1,d)\in D(N),1-d+d^2\equiv 0(\mathrm{mod}N)\}.\hfill \end{array}$$

(3)

Then, there exist bijections between $E_2(N),E_3(N)$ and complete sets of representatives of ${\mathsf{\Gamma }}_0(N)$-inequivalent elliptic points of order 2 and 3, respectively. In Section 4, we establish bijections between $E_2(N_1{N}_2)$ and $E_2(N_1)\times E_2(N_2),E_3(N_1{N}_2)$ and $E_3(N_1)\times E_3(N_2)$, for $(N_1,N_2)=1$. These results give a recursive algorithm for constructing the complete set $E_3(N)$ and $E_2(N)$ of ${\mathsf{\Gamma }}_0(N)$-inequivalent elliptic points of order 2, 3.

The elements in ${\mathbb{P}}^1(\mathbb{Z}/N\mathbb{Z})$ are called Manin symbols [3] (Section 2.2) and there exists a bijection between the set of right cosets of ${\mathsf{\Gamma }}_0(N)$ in $SL(2,\mathbb{Z})$ and ${\mathbb{P}}^1(\mathbb{Z}/N\mathbb{Z})$ [2] (Proposition 2.4). An important step in the modular elliptic algorithm is to construct a complete set of representatives for the projective line ${\mathbb{P}}^1(\mathbb{Z}/N\mathbb{Z})$ and a complete set of representatives of ${\mathsf{\Gamma }}_0(N)$-inequivalent cusps [3] (Chapter II). The recursive structure of $D(N),C(N),E_2(N)$ and $E_3(N)$ may give rise to a more efficient modular elliptic algorithm.

As direct corollaries of these recursive structures, we present a recursive version of the genus formula and elementary proofs of formulas of the numbers $\mu (N)$, $v_{\infty }(N)$, $v_2(N)$ and $v_3(N)$ of $D(N)$, $C(N)$, $E_2(N)$, $E_3(N)$. Note that Schoeneberg’s proof and Shimura’s proof for formulas of $\mu (N)$, $v_{\infty }(N)$, $v_2(N)$ and $v_3(N)$ use the theory of quadratic fields, see [4] (Chapter IV, Section 8) and [1] (Chapter 1, Proposition 1.43). Their proofs may make these formulas hard to approach when compared with our proofs.

2. The Recursive Structure of Manin Symbols over $\mathbb{Q}$

We firstly give some necessary notations and facts, for details, see [3].

Definition 1.

(a)

$D_2(N)=\{(c,d):c,d\in \mathbb{Z},(c,d,N)=1\}$;

(b)

$\forall (c_1,d_1),(c_2,d_2)\in D_2(N),$ define $(c_1,d_1)\sim (c_2,d_2)$ if $c_1{d}_2\equiv d_1{c}_2(\mathrm{mod}N)$, then ∼ is an equivalence relation on $D_2(N)$;

(c)

$\forall (c,d)\in D_2(N)$, define $(c:d)=\left\{(c^{\prime },d^{\prime }):(c^{\prime },d^{\prime })\in D_2(N),(c^{\prime },d^{\prime })\sim (c,d)\right\}$;

(d)

$\mathcal{D}(N)=D_2(N)/\sim =\{(c:d):(c,d)\in D_0(N)\}$;

(e)

$D_1(N)=\{(c,d):c,d\in \mathbb{Z},c,d⩾1,c|N,(c,d,\frac{N}{c})=1,cd⩽N\}$;

(g)

$D(N)$ is defined in (1);

(g)

$\mu (N)$, $v_{\infty }(N)$, $v_2(N)$ and $v_3(N)$ are the numbers of elements in $D(N),C(N),E_2(N)$ and $E_3(N)$, respectively.

As pointed out by a referee, the index $\mu (N)$ of ${\mathsf{\Gamma }}_0(N)$ in $SL(2,\mathbb{Z})$ is called the Dedekind psi function, usually denoted $\psi (N)$, see [5,6]. Here, we follow Shimura’s notations in [1] (Proposition 1.43).

Lemma 1.

Let $c,d,h\in \mathbb{Z}$, $(c,d,h)=1$,$c,d⩾1$ and $d⩽h$, then there exists an integer k such that $(c,d+hk)=1$ and $0⩽k<c$.

Proof. 

If $c=1$, take $k=0$ then $(c,d+hk)=1$. Thus, let $c⩾2$ in the following. Let $c=p_1^{{\alpha }_1}\cdots p_s^{{\alpha }_s}$ be the standard factorization of c. The proof is by induction on the numbers of distinct prime divisors in c. Suppose that $c=p_1^{{\alpha }_1}$. Assume that $(p_1^{{\alpha }_1},d)⩾2$ and $(p_1^{{\alpha }_1},d+h)⩾2$ then $p_1|d$ and $p_1|(d+h)$. Thus, $p_1|d$ and $p_1|h$, this contradicts with $(c,d,h)=1$, and hence $(c,d+hk)=1$ for some $0⩽k⩽1<c$.

Let $c_1=p_1^{{\alpha }_1}\cdots p_{s-1}^{{\alpha }_{s-1}}$. By the induction hypothesis, there exists an integer $k_1$ such that $(c_1,d+h{k}_1)=1$ and $0⩽k_1<c_1$. Then, $(c_1,d+h{k}_1+h{c}_1)=1$. Assume that $(p_s^{{\alpha }_s},d+h{k}_1)⩾2$ and $(p_s^{{\alpha }_s},d+h{k}_1+h{c}_1)⩾2$ then $p_s|(d+h{k}_1)$ and $p_s|(d+h{k}_1+h{c}_1)$. Thus, $p_s|h{c}_1$ and hence $p_s|h$ by $(p_s,c_1)=1$. Therefore, $p_s|d$. This contradicts with $(c,d,h)=1$ and hence $(c,d+h{k}_1)=1$ or $(c,d+h{k}_1+h{c}_1)=1$. Take $k=k_1$ or $k=c_1+k_1$, then $(c,d+hk)=1$ for some $0⩽k_1⩽k⩽c_1+k_1<2c_1⩽c$. This completes the proof by the induction principle.    □

Corollary 1.

Let $a,b,c\in \mathbb{Z}$, $(a,b,c)=1$, then the equation $ax+by+cyz=1$ has solutions in $\mathbb{Z}$.

Lemma 2.

There exists a bijection between $D(N)$ and $D_1(N)$.

Proof. 

Let $(c,d)\in D(N)$. Define $d_n=d-\frac{N}{c}{[\frac{cd}{N}]}^{\prime }+\frac{Nn}{c}$ for all $n\in \mathbb{Z}$. Then, $1⩽d_0⩽\frac{N}{c}$ and $(c,d_0,\frac{N}{c})=1$ by $(c,d)=1$. Thus $(c,d_0)\in D_1(N)$. Define $\mathsf{\Phi }:D(N)\to D_1(N)$ by sending $(c,d)$ to $(c,d_0)$.

Let $(u,v)\in D(N)$ such that $\mathsf{\Phi }(c,d)=\mathsf{\Phi }(u,v)$. Define $v_n=v-\frac{N}{u}{[\frac{uv}{N}]}^{\prime }+\frac{Nn}{u}$ for all $n\in \mathbb{Z}$. Then, $c=u$ and $d_0=v_0$. Thus, $d_n=v_n$ for all $n\in \mathbb{Z}$. Let $e={[\frac{cd}{N}]}^{\prime }$ and $w={[\frac{cv}{N}]}^{\prime }$. Then, $d=d_e$ and $v=v_w$. Suppose that $e<w$ then $(c,d_e)=1$ by $(c,d)=1$ but $(c,d_e)⩾2$ by $(c,v)\in D(N)$ and $d_e=v_e$, a contradiction and thus $e⩾w$. $e⩽w$ holds by a similar proof and thus $e=w$ and $(c,d)=(u,v)$. Therefore, $\mathsf{\Phi }$ is an injection from $D(N)$ to $D_1(N)$.

Let $(c,d_0)\in D_1(N)$. By Lemma 1, there exists an integer k such that $(c,d_0+\frac{Nk}{c})=1$ and $0⩽k⩽c-1$. Let $0⩽k_0⩽k$ such that $(c,d_0+\frac{N{k}_0}{c})=1$ and $(c,d_0+\frac{Nn}{c})=1$ for all $0⩽n<k_0$. Define $d=d_0+\frac{N{k}_0}{c}$. Then, $(c,d)\in D(N)$ and $\mathsf{\Phi }((c,d))=(c,d_0)$. Therefore, $\mathsf{\Phi }$ is a surjection from $D(N)$ to $D_1(N)$.    □

Lemma 3.

There exists a bijection between $\mathcal{D}(N)$ and $D(N)$, i.e., $D(N)$ is a complete system of the representatives of elements of $\mathcal{D}(N)$.

Proof. 

Define $\mathsf{\Phi }:D(N)\to \mathcal{D}(N)$ by the natural map, i.e., $\mathsf{\Phi }((c,d))=(c:d)$.

Let $(c:d)\in \mathcal{D}(N)$. Then, $(c,d,N)=1$. Define $c_1=(c,N)$, $d_0$ to be the unique solution of the congruence equation $\frac{c}{c_1}x\equiv d(\mathrm{mod}\frac{N}{c_1})$ such that $1⩽d_0⩽\frac{N}{c_1}$. Then, there exists an integer y such that $\frac{c}{c_1}{d}_0+\frac{N}{c_1}y=d$. Assume that there exists a prime p such that $p|(c_1,d_0,\frac{N}{c_1})$. Then, $p|d$ and $p|(c,N)$, this contradicts with $(c,d,N)=1$, and thus $(c_1,d_0,\frac{N}{c_1})=1$. Hence, $(c_1,d_0)\in D_1(N)$. Then, there exists the unique $(c_1,d_1)\in D(N)$ which corresponds to $(c_1,d_0)$. Hence, $(c_1,d_1)\in (c:d)$, i.e., $\mathsf{\Phi }((c_1,d_1))=(c:d)$.

Assume that $(c_1,d_1),(c_2,d_2)\in D(N)$ such that $\mathsf{\Phi }((c_1,d_1))=\mathsf{\Phi }((c_2,d_2))$. Then, $(c_1:d_1)=(c_2:d_2)$ and thus there exists an integerk such that $c_1{d}_2-c_2{d}_1=Nk$. Thus, $c_1|c_2{d}_1$ by $c_1|N$ and $c_2|c_1{d}_2$ by $c_2|N$. Hence, $c_1|c_2$ by $(c_1,d_1)=1$ and $c_2|c_1$ by $(c_2,d_2)=1$. Therefore, $c_1=c_2$ and $d_1=d_2$ by $d_1\equiv d_2(\mathrm{mod}\frac{N}{c_1})$ and the definition of $D(N)$. Thus, $\mathsf{\Phi }$ is a bijection between $\mathcal{D}(N)$ and $D(N)$. This completes the proof.    □

Theorem 1.

Let $M,N\in \mathbb{Z},M,N⩾1$, $(M,N)=1$. Then, there exists a bijection between $D(M)\times D(N)$ and $D(MN)$.

Proof. 

Let $(a,b)\in D(M)$ and $(c,d)\in D(N)$. Assume that there exists a prime p such that $p|(ac,bN+dM-\frac{MN}{ac}{[\frac{ac(bN+dM)}{MN}]}^{\prime },\frac{MN}{ac})$. Then, $p|ac,p|\frac{M}{a}\frac{N}{c}$ and

$$p|bN+dM-\frac{MN}{ac}{[\frac{ac(bN+dM)}{MN}]}^{\prime }.$$

Then $p|a,p|\frac{M}{a}$ or $p|c,p|\frac{N}{c}$ by $(M,N)=1$,$a|M,c|N$. If $p|a,p|\frac{M}{a}$ then $p|bN$ and thus $p|N$ by $(a,b)=1$, which contradicts with $(M,N)=1$. The case of $p|c,p|\frac{N}{c}$ is tackled in a similar way. Therefore $(ac,bN+dM-\frac{MN}{ac}{[\frac{ac(bN+dM)}{MN}]}^{\prime },\frac{MN}{ac})=1$ and

$$(ac,bN+dM-\frac{MN}{ac}{[\frac{ac(bN+dM)}{MN}]}^{\prime })\in D_1(MN).$$

Define $e=ac$, $f=bN+dM-\frac{MN}{ac}({[\frac{ac(bN+dM)}{MN}]}^{\prime }-k)$ for some k such that

$$(ac,bN+dM-\frac{MN}{ac}({[\frac{ac(bN+dM)}{MN}]}^{\prime }-n))⩾2$$

for all $0⩽n<k$. Then $(e,f)\in D(MN)$. Define $\mathsf{\Phi }:D(M)\times D(N)\to D(MN)$ by sending $((a,b),(c,d))$ to $(e,f)$.

Assume that $\mathsf{\Phi }((a,b),(c,d))=\mathsf{\Phi }((a_1,b_1),(c_1,d_1))$ for some $(a,b),(a_1,b_1)\in D(M)$ and $(c,d),(c_1,d_1)\in D(N)$. Then

$$(ac,bN+dM-\frac{MN}{ac}({[\frac{ac(bN+dM)}{MN}]}^{\prime }-k))$$

$$=(a_1{c}_1,b_{1}N+d_{1}M-\frac{MN}{a_1{c}_1}({[\frac{a_1{c}_1(b_{1}N+d_{1}M)}{MN}]}^{\prime }-k_1)).$$

Thus, $ac=a_1{c}_1$ and

$$bN+dM-\frac{MN}{ac}({[\frac{ac(bN+dM)}{MN}]}^{\prime }-k)$$

$$=b_{1}N+d_{1}M-\frac{MN}{a_1{c}_1}({[\frac{a_1{c}_1(b_{1}N+d_{1}M)}{MN}]}^{\prime }-k_1).$$

Hence, $a=a_1$, $c=c_1$ by $(M,N)=1$, $a|M,a_1|M,c|N,c_1|N$. Therefore,

$$bN+dM-\frac{MN}{ac}({[\frac{ac(bN+dM)}{MN}]}^{\prime }-k)$$

$$=b_{1}N+d_{1}M-\frac{MN}{ac}({[\frac{ac(b_{1}N+d_{1}M)}{MN}]}^{\prime }-k_1).$$

Thus $d\equiv d_1(\mathrm{mod}\frac{N}{c})$ and $b\equiv b_1(\mathrm{mod}\frac{M}{a})$ by $(M,N)=1$. Hence $b=b_1$, $d=d_1$. Then $((a,b),(c,d))=((a_1,b_1),(c_1,d_1))$.

Let $(e,f)\in D(MN)$. Then $e|MN$, $(e,f)=1\mathrm{and}(e,f-\frac{MN}{e}({[\frac{ef}{MN}]}^{\prime }-n))⩾2for0⩽n<{[\frac{ef}{MN}]}^{\prime }$. Let $a=(e,M)$, $c=(e,N)$, then $e=ac$, $a|M$ and $c|N$. Let $x_0,y_0,z_0$ be a particular solution of the equation

$$Nx+My+\frac{MN}{ac}z=f$$

(4)

then $x=\frac{M}{a}X+x_0,y=\frac{N}{c}Y+y_0,z=-cX-aY+z_0$ are solutions of $(4)$ for all integers $X,Y$. Take $b_1=x_0-\frac{M}{a}{[\frac{a{x}_0}{M}]}^{\prime },d_1=y_0-\frac{N}{c}{[\frac{c{y}_0}{N}]}^{\prime }$, then

$$N{b}_1+M{d}_1+\frac{MN}{ac}(c{[\frac{a{x}_0}{M}]}^{\prime }+a{[\frac{c{y}_0}{N}]}^{\prime }+z_0)=f,1⩽b_1⩽\frac{M}{a},1⩽d_1⩽\frac{N}{c}.$$

Then, $(a,b_1,\frac{M}{a})=1$ by $a|M,(e,f)=1$ and $(c,d_1,\frac{N}{c})=1$ by $c|N,(e,f)=1$. Hence, $(a,b_1)\in D_1(M),(c,d_1)\in D_1(N)$. Let $(a,b)\in D(M)$ and $(c,d)\in D(N)$ which correspond to $(a,b_1)$ and $(c,d_1)$, respectively. Then $b=b_1+\frac{M}{a}{k}_1$ and $d=d_1+\frac{N}{c}{k}_2$ for some $k_1,k_2$. Then $Nb+Md+\frac{MN}{ac}(c{[\frac{a{x}_0}{M}]}^{\prime }+a{[\frac{c{y}_0}{N}]}^{\prime }-c{k}_1-a{k}_2+z_0)=f$. Then $(e,f)=\mathsf{\Phi }((a,b),(c,d))$.

Thus, $\mathsf{\Phi }$ is a bijection between $D(M)\times D(N)$ and $D(MN)$.    □

Proposition 1.

Let p be a prime and l a positive integer. Then

$$(a)D(p^l)=\{(1,d):1⩽d⩽p^l\}\cup \{(p^l,1)\}\cup$$

$$\{(p^{\alpha },kp+d):1⩽\alpha ⩽l-1,1⩽d⩽p-1,0⩽k⩽p^{l-\alpha -1}-1\};$$

$$(b)\mu (p^l)=p^l(1+\frac{1}{p});$$

$$(c)\mu (N)=N{\prod }_{p|N}\left(1+\left(\frac{1}{p}\right)\right).$$

Proof. 

(c) is immediately from (b) and Theorem 1.   □

$D(MN)$ can be constructed using Algorithm 1.

Algorithm 1: $D(MN)$

(1) Construct $D(p^l)$ by Proposition 1(a); (2) Given $D(M)$ and $D(N)$ for $(M,N)=1$, $D(MN)$ is constructed as follows. For all $(a,b)\in D(M)$,$(c,d)\in D(N)$, define $e=ac$, $f=bN+dM-\frac{MN}{ac}({[\frac{ac(bN+dM)}{MN}]}^{\prime }-k)$ for some $k\in \mathbb{Z}$ such that $(e,f)=1$ and $(ac,bN+dM-\frac{MN}{ac}({[\frac{ac(bN+dM)}{MN}]}^{\prime }-n))⩾2$ for all $0⩽n<k$. Then, $(e,f)\in D(MN)$ and all elements in $D(MN)$ are constructed if all pairs in $D(M)\times D(N)$ are processed.

3. The Recursive Structure of Cusps

In order to describe the cusps on $X_0(N)$, Ju. I. Manin in [2] introduced the set $\mathsf{\Pi }(N)$, which consists of pairs of the form $[\delta ;a\mathrm{mod}(\delta ,N{\delta }^{-1})]$. Here, $\delta$ runs through all positive divisors of N, and the second coordinate of the pair runs through any invertible class of residues modulo the greatest common divisor of $\delta$ and $N{\delta }^{-1}$. If $(\delta ,N{\delta }^{-1})=1$ we sometimes put simply 1 in place of the second coordinate.

Proposition 2.

Let $\delta |N,u,v\in \mathbb{Z}$; $(u,v\delta )=(v,N{\delta }^{-1})=1$. The map $\mathbb{Q}\cup \{i\infty \}\to \mathsf{\Pi }(N)$ of the form $\frac{u}{v\delta }\mapsto [\delta ;uv\mathrm{mod}(\delta ,N{\delta }^{-1})]$ gives an isomorphism of the set of cusps on $X_0(N)$ with $\mathsf{\Pi }(N)$.

Proof. 

See Proposition 2.2 in [2].    □

In [3], (Proposition 2.2.3), J. E. Cremona gives the following characterization of cusps of $X_0(N)$.

Proposition 3.

For $j=1,2$ let ${\alpha }_j=p_j/q_j$ be cusps written in the lowest terms. The following are equivalent:

(a)

${\alpha }_2=M({\alpha }_1)$ for some $M\in {\mathsf{\Gamma }}_0(N)$;

(b)

$q_2\equiv u{q}_1(\mathrm{mod}N)$ and $u{p}_2\equiv p_1(\mathrm{mod}(q_1,N))$, with $(u,N)=1$;

(c)

$s_1{q}_2\equiv s_2{q}_1(\mathrm{mod}(q_1{q}_2,N))$, where $s_j$ satisfies $p_j{s}_j\equiv 1(\mathrm{mod}{q}_j)$.

Definition 2.

(a)

$C_1(N)=\{(c,d):c,d\in \mathbb{Z},1⩽c⩽N,c|N,1⩽d⩽(c,N{c}^{-1}),(c,d,N{c}^{-1})=1\},$

(b)

$C(N)isdefinedin(2).$

Lemma 4.

There exists a bijection between $C_1(N)$ and $C(N)$.

Proof. 

It holds by $C_1(N)\subseteq D_1(N)$, $C(N)\subseteq D(N)$ and Lemma 2.    □

Lemma 5.

There exists a bijection between ${\mathsf{\Gamma }}_0(N)\setminus \mathbb{Q}\cup \{i\infty \}$ and $C_1(N)$.

Proof. 

Let ${\gamma }_i=\left(\begin{array}{cc}{a}_i\hfill & b_i\hfill \\ c_i\hfill & d_i\hfill \end{array}\right),{\gamma }_j=\left(\begin{array}{cc}{a}_j\hfill & b_j\hfill \\ c_j\hfill & d_j\hfill \end{array}\right)\in {SL}_2(\mathbb{Z})$ such that $(c_i,d_i),(c_j,d_j)\in D(N)$ for $1⩽i<j⩽\mu (N)$ then ${\mathrm{SL}}_2(\mathbb{Z})={\mathsf{\Gamma }}_0(N){\gamma }_1\cup \cdots \cup {\mathsf{\Gamma }}_0(N){\gamma }_{\mu (N)}$ and ${\mathsf{\Gamma }}_0(N){\gamma }_i\ne {\mathsf{\Gamma }}_0(N){\gamma }_j$. $\forall c,a\in \mathbb{Z},(c,a)=1,c⩾1$, let $\left(\begin{array}{cc}a\hfill & b\hfill \\ c\hfill & d\hfill \end{array}\right)\in {\mathrm{SL}}_2(\mathbb{Z})$ for some $a,b$. Then there exists $\gamma \in {\mathsf{\Gamma }}_0(N),1⩽i⩽\mu (N)$ such that $\left(\begin{array}{cc}a\hfill & b\hfill \\ c\hfill & d\hfill \end{array}\right)=\gamma {\gamma }_i$. Thus, $\left(\begin{array}{cc}a\hfill & b\hfill \\ c\hfill & d\hfill \end{array}\right)(\infty )=\gamma {\gamma }_i(\infty )$, $\gamma (\frac{a_i}{c_i})=\frac{a}{c}$ and ${\mathsf{\Gamma }}_0(N)\frac{a}{c}={\mathsf{\Gamma }}_0(N)\frac{a_i}{c_i}$. Then, ${\mathsf{\Gamma }}_0(N)\setminus \mathbb{Q}\cup \{i\infty \}=\{{\mathsf{\Gamma }}_0(N)\frac{a_i}{c_i}:1⩽i⩽\mu (N)\}$. Define $\mathsf{\Phi }:{\mathsf{\Gamma }}_0(N)\setminus \mathbb{Q}\cup \{i\infty \}\to C_1(N)$ by

$${\mathsf{\Gamma }}_0(N)\frac{a}{c}\mapsto (c_i,d_i-(c_i,c_i^{-1}N){\left[d_i{(c_i,c_i^{-1}N)}^{-1}\right]}^{\prime }),{\mathsf{\Gamma }}_0(N)·i\infty \mapsto (N,1).$$

By Proposition 3, ${\mathsf{\Gamma }}_0(N)\frac{a_i}{c_i}={\mathsf{\Gamma }}_0(N)\frac{a_j}{c_j}$ if $c_i{d}_j\equiv c_j{d}_i(\mathrm{mod}(c_i{c}_j,N))$. Then, $c_i{d}_j=c_j{d}_i+(c_i{c}_j,N)h$ for some $h\in \mathbb{Z}$. Thus, $c_i=c_j$ by $c_i|N$, $c_j|N$, $(c_i,d_i)=1$ and $(c_j,d_j)=1$. Hence, $c_i{d}_j\equiv c_j{d}_i(\mathrm{mod}(c_i{c}_j,N))$ if $d_i\equiv d_j(\mathrm{mod}(c_i,c_i^{-1}N))$. Therefore, $\mathsf{\Phi }$ is a bijection between ${\mathsf{\Gamma }}_0(N)\setminus \mathbb{Q}\cup \{i\infty \}$ and $C_1(N)$.    □

Lemma 6.

There exists a bijection between ${\mathsf{\Gamma }}_0(N)\setminus \mathbb{Q}\cup \{i\infty \}$ and $C(N)$.

Proof. 

It is immediately from Lemmas 4 and 5.    □

Lemma 7.

Let $(N_1,N_2)=1$. Then, there exists a bijection between $C_1(N_1{N}_2)$ and $C_1(N_1)\times C_1(N_2)$.

Proof. 

Let $(c,d)\in C_1(N_1{N}_2)$ then $c|N_1{N}_2,d⩽(c,N_1{N}_2{c}^{-1}),(d,c,N_1{N}_2{c}^{-1})=1$. Let $c_1=(c,N_1),c_2=(c,N_2)$ then $c=c_1{c}_2,(c_1,c_2)=1$ and $(d,c_1{c}_2,N_1{c}_1^{-1}{N}_2{c}_2^{-1})=1$. Thus, $(d,(c_1,N_1{c}_1^{-1}))=1$, $(d,(c_2,N_2{c}_2^{-1}))=1$ by $(c,N_1{N}_2{c}^{-1})=(c_1,N_1{c}_1^{-1})(c_2,N_2{c}_2^{-1})$. Let $d_1=d-(c_1,N_1{c}_1^{-1}){[d{(c_1,N_1{c}_1^{-1})}^{-1}]}^{\prime }$ and $d_2=d-(c_2,N_2{c}_2^{-1}){[d{(c_2,N_2{c}_2^{-1})}^{-1}]}^{\prime }$ then $(d_1,(c_1,N_1{c}_1^{-1}))=1$ and $(d_2,c_2,N_2{c}_2^{-1})=1$. Thus, $(c_1,d_1)\in C_1(N_1)$ and $(c_2,d_2)\in C_1(N_2)$. Define $\mathsf{\Phi }:C_1(N_1{N}_2)\to C_1(N_1)\times C_2(N_2)$ by $(c,d)\mapsto ((c_1,d_1),(c_2,d_2))$.

For any $((c_1,d_1),(c_2,d_2))\in C_1(N_1)\times C_1(N_2)$, let $c=c_1{c}_2$ there exists an integer d such that $d\equiv d_1(\mathrm{mod}(c_1,N_1{c}_1^{-1}))$, $d\equiv d_2(\mathrm{mod}(c_2,N_2{c}_2^{-1}))$ and

$$1⩽d⩽(c_1,N_1{c}_1^{-1})(c_2,N_2{c}_2^{-1})=(c,N_1{N}_2{c}^{-1})$$

by $((c_1,N_1{c}_1^{-1}),(c_2,N_2{c}_2^{-1}))=1$. Thus $(c,d)\in C_1(N_1{N}_2)$ and hence $\mathsf{\Phi }$ is a surjective map.

Let $\mathsf{\Phi }((c,d))=\mathsf{\Phi }((c^{\prime },d^{\prime }))$. Then, $((c_1,d_1),(c_2,d_2))=((c_1^{\prime },d_1^{\prime }),(c_2^{\prime },d_2^{\prime }))$, $(c_1,d_1)=(c_1^{\prime },d_1^{\prime })$ and $(c_2,d_2)=(c_2^{\prime },d_2^{\prime })$. Thus, $c_1=c_1^{\prime },c_2=c_2^{\prime },d_1=d_1^{\prime }$ and $d_2=d_2^{\prime }$. Hence, $c=c_1{c}_2=c_1^{\prime }{c}_2^{\prime }=c^{\prime }$ and $d=d^{\prime }$ by $d\equiv d_1(\mathrm{mod}(c_1,N_1{c}_1^{-1}))$, $d\equiv d_2(\mathrm{mod}(c_2,N_2{c}_2^{-1}))$, $d^{\prime }\equiv d_1^{\prime }(\mathrm{mod}(c_1,N_1{c}_1^{-1}))$ and $d^{\prime }\equiv d_2^{\prime }(\mathrm{mod}(c_2,N_2{c}_2^{-1}))$. Therefore, $\mathsf{\Phi }$ is an injective map. Then $\mathsf{\Phi }$ is a bijection between $C_1(N_1{N}_2)$ and $C_1(N_1)\times C_1(N_2)$.    □

Theorem 2.

Let $(N_1,N_2)=1$. Then, there exists a bijection between $C(N_1{N}_2)$ and $C(N_1)\times C(N_2)$.

Proof. 

It is immediately from Lemmas 4 and 7.    □

Proposition 4.

Let p be a prime and l a positive integer. Then,

(a)

$C(p^l)=\{(1,1),(p^l,1)\}\cup$$\{(p^{\alpha },kp+d):1⩽\alpha ⩽l-1,1⩽d⩽p-1,0⩽k⩽p^{min\{\alpha ,l-\alpha \}-1}-1\};$

(b)

$v_{\infty }(p^l)=\left\{\begin{array}{c}(p+1)p^{\frac{l}{2}-1}if2|l,\hfill \\ 2p^{\frac{l-1}{2}}otherwise;\hfill \end{array}\right.$

(c)

$v_{\infty }(N)={\prod }_{p|N}{v}_{\infty }(p^l).$

Proof. 

(c) is immediately from (b) and Theorem 2.    □

$C(N)$ can be constructed using Algorithm 2.

Algorithm 2: $C(N)$

(1) Construct $C(p^l)$ by Proposition 4(a); (2) Let $N=N_1{N}_2$ for $(N_1,N_2)=1$. Given $C(N_1)$ and $C(N_2)$. $C(N)$ is constructed as follows. For all $(c_1,d_1)\in C(N_1)$,$(c_2,d_2)\in C(N_2)$, define $c=c_1{c}_2$. Determinate $d_0$ such that $d_0\equiv d_1(\mathrm{mod}(c_1,N_1{c}_1^{-1}))$, $d_0\equiv d_2(\mathrm{mod}(c_2,N_2{c}_2^{-1}))$ and $$1⩽d_0⩽(c_1,N_1{c}_1^{-1})(c_2,N_2{c}_2^{-1}).$$ Determinate $d=d_0+\frac{Nk}{c}$ such that $(c,d)=1$ and $(c,d_0+\frac{Nn}{c})⩾2\mathrm{for}0⩽n<k$. Then, $(c,d)\in C(N_1{N}_2)$ and all elements in $C(N_1{N}_2)$ are constructed if all pairs in $C(N_1)\times C(N_2)$ are processed.

4. The Recursive Structure of Elliptic Points of ${\mathit{X}}_{\mathbf{0}}(\mathit{N})$

Let $\rho =\frac{-1+\sqrt{3}i}{2}$. $E_2(N)$ and $E_3(N)$ are defined in (3). Then,

$$\{\frac{-d+i}{1+d^2}:(1,d)\in E_2(N)\}and\{\frac{1-2d+\sqrt{3}i}{2\left(1-d+d^2\right)}:(1,d)\in E_3(N)\}$$

are complete sets of representatives of ${\mathsf{\Gamma }}_0(N)$-inequivalent elliptic points of order 2, 3, respectively.

Theorem 3.

Let $N_1,N_2\in \mathbb{Z},N_1,N_2⩾1$ and $(N_1,N_2)=1$. Then

(a)

there exists a bijection between $E_3(N_1)\times E_3(N_2)$ and $E_3(N_1{N}_2)$;

(b)

there exists a bijection between $E_2(N_1)\times E_2(N_2)$ and $E_2(N_1{N}_2)$.

Proof. 

(a) Let $(1,d_1)\in E_3(N_1)$ and $(1,d_2)\in E_3(N_2)$. Let d be the unique integer such that $d\equiv d_1(\mathrm{mod}{N}_1)$,$d\equiv d_2(\mathrm{mod}{N}_2)$ and $1⩽d⩽N_1{N}_2$ then $d^2-d+1\equiv 0(\mathrm{mod}{N}_1{N}_2)$.

Hence, $(1,d)\in E_3(N_1{N}_2)$. Define

$$\mathsf{\Phi }:E_3(N_1)\times E_3(N_2)\to E_3(N_1{N}_2),((1,d_1),(1,d_2))\mapsto (1,d).$$

Then, $\mathsf{\Phi }$ is a bijection between $E_3(N_1)\times E_3(N_2)$ and $E_3(N_1{N}_2)$. The proof of (b) is similar to that of (a) and omitted.    □

Proposition 5.

Let $p\in \mathbb{Z}$ be a prime and $l\in \mathbb{Z},l⩾1$. Then

$$v_2(p^l)=\left\{\begin{array}{c}0ifp\equiv 3(\mathrm{mod}4)or4|p^l,\hfill \\ 1ifp=2,\hfill \\ 2ifp\equiv 1(\mathrm{mod}4).\hfill \end{array}\right.$$

Proof. 

Let $(1,d)\in E_2(p^l)$ then $d^2+1\equiv 0(\mathrm{mod}{p}^l)$. Since the system of two equations $x^2+1\equiv 0(\mathrm{mod}p)$ and $2x\equiv 0(\mathrm{mod}p)$ has a common solution if $p=2$, the number of solutions of $x^2+1\equiv 0(\mathrm{mod}{p}^l)$ is equal to that of $x^2+1\equiv 0(\mathrm{mod}p)$ if $p\ne 2$. The cases of $p=2$ or $4|p^l$ are trivial and we then let $p⩾3$ in the following. Then, $x^2+1\equiv 0(\mathrm{mod}p)$ has a solution if $\left(\frac{-1}{p}\right)=1$ if $p\equiv 1(\mathrm{mod}4)$ by $\left(\frac{-1}{p}\right)={(-1)}^{\frac{p-1}{2}}$. In addition, $x^2+1\equiv 0(\mathrm{mod}p)$ has two and only two solutions if it is solvable. This completes the proof.    □

Proposition 6.

Let $p\in \mathbb{Z}$ be a prime and $l\in \mathbb{Z},l⩾1$. Then

$$v_3(p^l)=\left\{\begin{array}{c}0ifp\equiv 2(\mathrm{mod}3)or9|p^l,\hfill \\ 1ifp=3,\hfill \\ 2ifp\equiv 1(\mathrm{mod}3).\hfill \end{array}\right.$$

Proof. 

Let $(1,d)\in E_3(p^l)$ then $d^2-d+1\equiv 0(\mathrm{mod}{p}^l)$. Since the system of two equations $x^2-x+1\equiv 0(\mathrm{mod}p)$ and $2x-1\equiv 0(\mathrm{mod}p)$ has a common solution if $p=3$, the number of solutions of $x^2-x+1\equiv 0(\mathrm{mod}{p}^l)$ is equal to that of $x^2-x+1\equiv 0(\mathrm{mod}p)$ if $p\ne 3$. The cases of $p=2,3$ or $9|p^l$ are trivial and we then let $p⩾5$ in the following. $x^2-x+1\equiv 0(\mathrm{mod}p)$ has a solution if $y^2+3\equiv 0(\mathrm{mod}p)$ has a solution by taking $x=\frac{y+1}{2}$ and substituting $p-y$ for y when $y\equiv 0(\mathrm{mod}2)$. Then, $x^2-x+1\equiv 0(\mathrm{mod}p)$ has a solution if $\left(\frac{-3}{p}\right)=1$ if $p\equiv 1(\mathrm{mod}3)$ by

$$\left(\frac{-3}{p}\right)=\left(\frac{3}{p}\right)\left(\frac{-1}{p}\right),\left(\frac{3}{p}\right)={(-1)}^{\frac{p-1}{2}}\left(\frac{p}{3}\right),\left(\frac{-1}{p}\right)={(-1)}^{\frac{p-1}{2}}$$

and $\left(\frac{-3}{p}\right)=\left(\frac{p}{3}\right)$. In addition, $x^2-x+1\equiv 0(\mathrm{mod}p)$ has two and only two solutions if it is solvable. This completes the proof.    □

The following results are well-known, see Proposition 1.43 in [1]. However, our proof is elementary and constructive.

Corollary 2.

(1)

$v_2(N)=\left\{\begin{array}{cc}0\hfill & if4|N,\\ {\prod }_{p|N}\left(1+\left(\frac{-1}{p}\right)\right)\hfill & otherwise.\end{array}\right.$

(2)

$v_3(N)=\left\{\begin{array}{cc}0\hfill & if4|N,\\ {\prod }_{p|N}\left(1+\left(\frac{-3}{p}\right)\right)\hfill & otherwise.\end{array}\right.$

Proof. 

It is immediately from Theorem 4, Propositions 5 and 6.    □

Corollary 3.

Let $g(N)$ be the genus of the modular curve $X_0(N)$. Then, for any $(N_1,N_2)=1$,

$$g(N_1{N}_2)=1+\frac{\mu (N_1)\mu (N_2)}{12}-\frac{v_2(N_1)v_2(N_2)}{4}-\frac{v_3(N_1)v_3(N_2)}{3}-\frac{v_{\infty }(N_1)v_{\infty }(N_2)}{2}.$$

Proof. 

It is immediately from Theorems 1–3 and the formula for the genus of $X_0(N)$

$$g(N)=1+\frac{\mu (N)}{12}-\frac{v_2(N)}{4}-\frac{v_3(N)}{3}-\frac{v_{\infty }(N)}{2}.$$

   □

$E_3(N)$ can be constructed using Algorithm 3.

Algorithm 3: $E_3(N)$

(1) Construct $E_3(p^l)$ by general method; (2) Let $N=N_1{N}_2$ for $(N_1,N_2)=1$. Given $E_3(N_1)$ and $E_3(N_2)$. $E_3(N)$ is constructed as follows. For all $(1,d_1)\in E_3(N_1)$, $(1,d_2)\in E_3(N_2)$, Determinate d such that $$d\equiv d_1(\mathrm{mod}{N}_1),d\equiv d_2(\mathrm{mod}{N}_2)and1⩽d⩽N.$$ Then, $(1,d)\in E_3(N)$ and all elements in $E_3(N)$ are constructed if all pairs in $E_3(N_1)\times E_3(N_2)$ are processed.

5. Concluding Remarks

In [7], Stein mentioned that another approach to list ${\mathbb{P}}^1(\mathbb{Z}/N\mathbb{Z})$ is to use that

$${\mathbb{P}}^1(\mathbb{Z}/N\mathbb{Z})\cong \prod _{p|N}{\mathbb{P}}^1(\mathbb{Z}/p^{v_p}\mathbb{Z}),$$

where $v_p=\mathrm{or}{\mathrm{d}}_p(N)$, and that it is relatively easy to enumerate the elements of ${\mathbb{P}}^1(\mathbb{Z}/p^n\mathbb{Z})$ for a prime power $p^n$. However, this approach had never been implemented by anyone as far as I know. Thus, Algorithm 1 in this paper could be regarded as an explicit implementation of Stein’s ideas. All the algorithms described in this paper have been implemented in Wolfram Language, for these Wolfram programs, see [8]. We plan to rewrite these programs in the free open-source computer algebra system SAGE and incorporate them into Stein’s program [9] or Walker’s program [10].