Cosets representatives of congruence subgroups

Question

I came across Shimura (1971) notes about cosets representatives of the congruence subgroups $ \Gamma_0(N) $. He firstly proves that its index in the modular group $\Gamma$ is

\begin{equation} [\Gamma : \Gamma_0(N)]=N \cdot \prod_{p|N} (1+p^{-1} ) \end{equation}

Then he comes up with a sets of cosets representatives for $\Gamma_0(N)$ in $\Gamma$ made in this way: we first choose pairs $(c,d)$ of positive integers such that

\begin{equation} (c,d)=1, \qquad d|N, \qquad 0 < c \le N/d \end{equation}

then for each pairs we fix integers $a,b$ such that $ad-bc=1$. Our list of cosets representatives is made of the matrices with such entries.

However, let us take for example $N=12$ when we know the index is 24 and thus this is the cardinality of the set of cosets representatives. Using the rule above, I only find 22 cosets representatives, namely the ones corresponding to the following $(c,d)$ pairs: $$(1,1),(2,1),\dots,(12,1),(1,2),(3,2),(5,2),(1,3),(2,3),(4,3),(1,4),(3,4),(1,6),(1,12).$$

I also tried to run SAGE and it gives me 24 cosets representatives but they seem redundant, for example $[[1, 0] [2, 1]]$ and $[[1, 2][2, 5]]$ are listed as different cosets representatives, but

$$\begin{pmatrix} 1 & 0 \\ 2 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}=\begin{pmatrix} 1 & 2 \\ 2 & 5 \end{pmatrix}$$

and thus it seems to me that these 2 matrices belong in fact to the same coset.

Something is clearly wrong, I hope you can help me.

Answer 1

Here is another attempt, this time hopefully with a correct answer. First off, the problem gets worse for e.g. N=24, where the index is 48, yet we only get 44 coset representatives.

For $N=12$, representatives for the two missing cosets are for example $(1,9)=(5,9)=(7,3)=(11,3)$ and $(1,8)=(5,4)=(7,8)=(11,4)$ (here with equality I mean that the pairs represent the same coset).

To find these, I first claim that there is a natural bijection beween $\Gamma/\Gamma_0(N)$ and the "projective line" $P^1(R)$, where $R:=\mathbb{Z}/N\mathbb{Z}$, which consists of the "1-dimensional subspaces of $R^2$". That is, subsets of $R^2$ of the form $(c,d) \cdot R^\times$ and of size $\lvert R^\times \rvert$. Indeed, it is easy to very that $\Gamma$ acts transitively (say, from the right) on $P^1(R)$, and the stabilizer of $(0,1)\cdot R^\times$ then equals $\Gamma_0(N)$. The claim follows.

Thus we just have to find representatives for the orbits $A:=(c,d)\cdot R^\times$ of $P^1(R)$. If $d$ is a unit, we can divide by $d$ and thus we certainly can choose the pairs $(c,1)$ as one type of coset representative. It remains to consider the pairs $(c,d)$ where $d$ is not a unit. Note that we may choose $1\leq c,d\leq N$ such that $gcd(c,d)=1$ (for either the gcd is invertible mod $N$, and so we can divide it out; or else it is a non-unit $x$, but then $x\cdot R^\times$ is strictly smaller than $R^\times$, and so $A$ is not an element of $P^1(R)$).

Looking at the formula you give (and attribute to Shimura), this is exactly what happens there: The element $d$ is either 1, or else $gcd(d,N)\neq 1$, in which case $d$ corresponds to a non-unit of $R$; one can in fact show that the $R^\times$-orbits (action by multiplication) on $R$ have the divisors of $N$ as representants.

However, the formula you describe is then to restrictive on what values for $c$ are used. Unfortunately, I cannot tell you a good closed formula as alternative right now, but with the above description, it is still relatively easy to compute representatives for all orbits: Let $d$ vary as described, but then do not only consider $c\leq N/d$, but rather study the orbits of $Stab_{R^\times}(d)$ on $R$ to find all possible values for $c$. In our example $N=12$, for example, the orbits of $R^\times$ on $R$ are $[ [ 0 ], [ 1, 5, 7, 11 ], [ 2, 10 ], [ 3, 9 ], [ 4, 8 ], [ 6 ] ]$. The stabilizer of e.g. $d=3$ is the subgroup of $R^\times$ containing $1$ and $5$. Its orbits on $R$ are $[ [ 0 ], [ 1, 5 ], [ 2, 10 ], [ 3 ], [ 4, 8 ], [ 6 ], [ 7, 11 ], [ 9 ] ]$. Hence we get the pairs $(1,3), (2,3), (4,3), (7,3)$ as the desired coset representatives with $d=3$. (The other values for $c$ are not allowed, as then $gcd(c,d)\neq 1$, which means that $(c,d)\cdot R^\times$ will be too small).

Answer 2

(2022.03.27, edited after Tireless and hardworking's remark.)

The quotient $\Gamma_0(N) \backslash \mathrm{SL}_2(\mathbf{Z})$ (right cosets) is in bijection with the set of pairs $(c,d)$ where $c$ is a positive divisor of $N$ and $1 \leq d \leq \frac{N}{c}$ satisfies $\operatorname{gcd}(d,c,\frac{N}{c})=1$.

To get the image of a matrix $M = \begin{pmatrix} \alpha & \beta \\ \gamma & \delta \end{pmatrix} \in \mathrm{SL}_2(\mathbf{Z})$, first find $u \in (\mathbf{Z}/N\mathbf{Z})^\times$ such that $\gamma u \equiv \operatorname{gcd}(\gamma,N) \bmod{N}$. Then $M$ is mapped to $(c,d):=(\operatorname{gcd}(\gamma,N), \delta u \bmod{\frac{N}{c}})$. It is a good exercice to check that this gives a well-defined and bijective map.

To get an explicit matrix representative associated to $(c,d)$, first find an integer $1 \leq \delta \leq N$ such that $\delta \equiv d \mod{\frac{N}{c}}$ and $\operatorname{gcd}(\delta,c)=1$, then find integers $\alpha,\beta \in \mathbf{Z}$ such that $\alpha \delta- \beta c=1$, and you get your representative $\begin{pmatrix} \alpha & \beta \\ c & \delta \end{pmatrix}$.

Answer 3

Not exactly an answer to "what is wrong with Shimura", but check out http://modular.math.washington.edu/edu/Fall2003/252/lectures/09-19-03/index.html and the referred to work by Helena Verrill...

Answer 4

As Max points out in his answer, one is just looking for a complete list of (representatives for) elements of the projective line $\mathbf{P}^1(\mathbf{Z}/N\mathbf{Z})$. Here are some maybe useful observations:

(*) If $\gcd(N,M) = 1$ the natural map $\phi:\mathbf{P}^1(\mathbf{Z}/NM\mathbf{Z}) \to \mathbf{P}^1(\mathbf{Z}/N\mathbf{Z}) \times \mathbf{P}^1(\mathbf{Z}/M\mathbf{Z})$ is bijective.

If one has an element of $([a:b],[c:d]) \in \mathbf{P}^1(\mathbf{Z}/N\mathbf{Z}) \times \mathbf{P}^1(\mathbf{Z}/M\mathbf{Z})$ in order to find $[e:f] = \phi^{-1}(([a:b],[c:d])$ one just needs to solve the congruences $e \equiv a \pmod N$, $e \equiv c \pmod M$, $f \equiv b \pmod N$ and $f \equiv d \pmod M$ for $e,f \in \mathbf{Z}$.

This reduces the problem to the case where $N = p^\ell$ is a power of a prime number $p$. Here one observes:

(**) $|\mathbf{P}^1(\mathbf{Z}/p^\ell\mathbf{Z})| = (p+1)p^{\ell-1}$, and a complete list of representatives is as follows: {$[1:x] \mid x \in p\mathbf{Z}/{p^\ell}\mathbf{Z}$} together with {$[(a + p^\ell\mathbf{Z})+y:1] \mid 0 \le a < p, y \in p\mathbf{Z}/{p^\ell}\mathbf{Z}$}.

From this point of view, one sees the problem(s) with the original list of representatives provided by the OP; e.g., in the list (1,1),(2,1),...,(12,1),(1,2),(3,2),(5,2),(1,3),(2,3),(4,3),(1,4),(3,4),(1,6),(1,12) there are only three pairs (e,f) for which

$$\phi([e:f]) = ([1:1],?) \in \mathbf{P}^1(\mathbf{Z}/4\mathbf{Z}) \times \mathbf{P}^1(\mathbf{Z}/3\mathbf{Z})$$

-- namely (1,1), (5,1), and (9,1) -- and only three pairs (e,f) for which

$$\phi([e:f]) = ([1:0],?) \in \mathbf{P}^1(\mathbf{Z}/4\mathbf{Z}) \times \mathbf{P}^1(\mathbf{Z}/3\mathbf{Z})$$

-- namely (1,4), (3,4) and (1,12) -- and in each case there should be 4 = $|\mathbf{P}^1(\mathbf{Z}/3\mathbf{Z})|$ such pairs. Max's answer listed the missing pairs, of course.

Answer 5

Thank you guys, summing up: the algorithm described in my first message is wrong, but the algorithm Max describes works, even though a closed, nice formula is not available (yet). Maybe one can obtain it by looking for different types of representatives, like SAGE does. I checked out the link Igor gives and the algorithm described for constructing a fundamental domain works also for our purpose but is very "computational" while i was looking for something easier, something a human could do much faster than computing lots of matrices products. I also checked the Kulkarni's paper Verrill refers to, but it is of no help.