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.

  • $\begingroup$ The missing representatives are (0,1) for the coset of 1, and (1,0). $\endgroup$ – Max Horn Dec 19 '11 at 12:32
  • $\begingroup$ Actually, my comment (and my now deleted answer) is incorrect. Assuming you mean the group of matrices $\left(\begin{smallmatrix}a&b\\ c&d\end{smallmatrix}\right)$ for which $c$ is divisible by $N$, then of course $1\in\Gamma$ is in the coset represented by $(N,1)$ (and (0,1) is just another rep for that). Moreover, $(1,0)$ and $(1,N)$ also represent the same coset. $\endgroup$ – Max Horn Dec 19 '11 at 13:10
  • $\begingroup$ Does everything work for prime $N?$ $\endgroup$ – Igor Rivin Dec 19 '11 at 15:48
  • $\begingroup$ Yes, for prime $N$, we have that $R=Z/NZ$ is a finite field, in particular all elements are units, and it is well known that the projective line has the coset representatives $(1,1),\ldots,(1,N),(N,1)=(0,1)$. $\endgroup$ – Max Horn Dec 19 '11 at 17:30
  • $\begingroup$ The output by Sage is correct, I think it gives you representatives for the left quotient $\Gamma_0(N) \backslash \Gamma$. $\endgroup$ – François Brunault Dec 20 '11 at 22:21

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).


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...

  • 1
    $\begingroup$ The link is now broken. Just for the people who also have this question in the future. $\endgroup$ – mdave16 Apr 19 '17 at 11:15

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.


The quotient $\Gamma_0(N) \backslash \mathrm{SL}_2(\mathbf{Z})$ 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$.

The class of a matrix $\begin{pmatrix} \alpha & \beta \\ \gamma & \delta \end{pmatrix} \in \mathrm{SL}_2(\mathbf{Z})$ is mapped to $(c,d):=(\operatorname{gcd}(\gamma,N), \delta \mod{\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}$.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.