8
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ The missing representatives are (0,1) for the coset of 1, and (1,0). $\endgroup$
    – Max Horn
    Dec 19, 2011 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, 2011 at 13:10
  • $\begingroup$ Does everything work for prime $N?$ $\endgroup$
    – Igor Rivin
    Dec 19, 2011 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, 2011 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$ Dec 20, 2011 at 22:21

5 Answers 5

3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

(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}$.

$\endgroup$
5
  • $\begingroup$ Let $N=9$, and let $M_1=\begin{pmatrix} 1 & 1 \\ 3 & 4 \end{pmatrix}$, and let $M_2=\begin{pmatrix} A & B \\ 9C & D \end{pmatrix} \in \Gamma_0(9)$, where $D \equiv 2 \mod{3}$. No matter if we consider left cosets or right cosets, then the map is not well defined, because $M_1M_2=\begin{pmatrix} A+9c & B+D \\ 3A+36C & 3B+4D \end{pmatrix}$, and $M_2M_1=\begin{pmatrix} A+3B & A+4B \\ 9C+3D & 9C+4D \end{pmatrix}$, and we have: $$M_1 \mapsto (3, 1),$$ $$M_1M_2 \mapsto (3, 2),$$ $$M_2M_1 \mapsto (3, 2),$$ so two different represntatives do not send to a unique element. $\endgroup$ Mar 27, 2022 at 13:45
  • 1
    $\begingroup$ @Tirelessandhardworking I see, the definition of the map $\begin{pmatrix} \alpha & \beta \\ \gamma & \delta \end{pmatrix} \mapsto (c,d)$ is incorrect. One should first find $u \in (\mathbb{Z}/N\mathbb{Z})^\times$ such that $\gamma u \equiv \mathrm{gcd}(\gamma,N) \bmod{N}$, and multiply $\delta$ by $u$ accordingly. $\endgroup$ Mar 27, 2022 at 17:17
  • $\begingroup$ Thank you. The map is impressive and the excercise was interesting. I verified that the map is well-defined, injective and surjective. I read also the answer by user "Max Horn", and now I can see some relations between his answer and your answer (the relation about "projective line", and the role of $u$ and $(c, d)$), but yet I can not understand where the "congruence mod $\frac{N}{c}$ over $d$" emerged form? $\endgroup$ Mar 27, 2022 at 19:33
  • $\begingroup$ @Tirelessandhardworking I think I came up with the formula starting with the description of $\Gamma_1(N) \backslash \mathrm{SL}_2(\mathbf{Z})$ as the set of pairs $(u,v) \in (\mathbf{Z}/N\mathbf{Z})^2$ such that $u,v$ generate $\mathbf{Z}/N\mathbf{Z}$, which is easier. Then one can work out the orbit a given pair $(u,v)$ under $(\mathbf{Z}/N\mathbf{Z})^\times$. But this doesn't really give an intuition. Anyway, thank you very much for pointing the error. $\endgroup$ Mar 28, 2022 at 11:13
  • $\begingroup$ Thanks for the time you've spent to me. I appreciate that. Finally I found the "correspondence" between your answer and his answer, and that was just a very simple congruence excercise. I think I understood everything. Thanks for everything, specially for your kindness and your generousity dear Francois Brunault. $\endgroup$ Mar 28, 2022 at 11:42
1
$\begingroup$

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

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

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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