Computing coset representatives for quotients of congruence subgroups
Given two congruence subgroups $\Gamma$ and $\Gamma'$ with $\Gamma' \leq \Gamma$, how does one find coset representatives for $\Gamma / \Gamma'$?
Note that we know how many cosets are necessary, as \begin{equation*} [\mathrm{SL}(2, \mathbb{Z}) : \Gamma] [\Gamma : \Gamma'] = [\mathrm{SL}(2, \mathbb{Z}) : \Gamma'], \end{equation*} and computing the two indices in $\mathrm{SL}(2, \mathbb{Z})$ is (presumably) known. I assume that we are studying sufficiently standard congruence subgroups that we can compute their indices in the full modular group.
I also assume that we can produce a set of generators for $\Gamma$. Note that this will always exist, as $\Gamma$ has finite index in $\mathrm{SL}(2, \mathbb{Z})$ and $\mathrm{SL}(2, \mathbb{Z})$ is finitely generated. In practice this is also known for sufficiently standard congruence subgroups.
Let us say that $[\Gamma : \Gamma'] = N$ and that \begin{equation*} \Gamma = \langle \gamma_1, \ldots, \gamma_\ell \rangle. \end{equation*} To produce a set of coset representatives for $\Gamma / \Gamma'$, we will walk the tree of products $\prod \gamma_i$ until walking further yields nothing new.
Algorithm 1: Deliberate Walk
Algorithm 1: Deliberate Walk
============================
set gens := [gamma_1, ..., gamma_ell] # group generators
set queue := [id] # where id is the identity matrix
set coset_reps := []
while queue not empty:
g = queue.pop(0) # remove first element from queue
if g not represented by coset_reps: # (see below)
coset_reps.append(g)
for gen in gens:
queue.append(gen * g)
return coset_reps
Note that $g_1$ and $g_2$ represent the same coset, i.e. $g_1 \Gamma' = g_2 \Gamma'$, exactly when $g_2^{-1} g_1 \in \Gamma'$. Thus to determine if $g$ gives a new coset, in practice one computes these products and determines if they are in $\Gamma'$. In pseudocode:
Subalgorithm: same_coset
========================
##
# Returns if g1 and g2 represent same coset of Gammaprime
##
define same_coset(g1, g2, Gammaprime):
return g2^(-1) * g1 in Gammaprime
Subalgorithm: new_coset
=======================
##
# Returns if g represents new coset not in coset_rep_list
##
define new_coset(g, coset_rep_list, Gammaprime):
for coset_rep in coset_rep_list:
if same_coset(g, coset_rep, Gammaprime):
return false
return true
In one sense, this algorithm is very naive. It walks through the complete tree of generators in every direction and stops when each branch hits previously seen cosets. The order is a breadth-first walk. This is guaranteed to find a complete set of coset representatives.
To see this, suppose $g$ is a representative for a coset not found. Then $g$ can be written as a product in the generators $\gamma_i$, say \begin{equation*} g = \prod_k \gamma_{i_k} = \gamma_{i_1} \gamma_{i_2} \cdots \gamma_{i_K}. \end{equation*} Here, each $\gamma_{i_k}$ is one of the generators for $\Gamma$, and this is an ordered product.
Consider the multiplicands in reverse order, \begin{equation} \gamma_{i_{K}}, \gamma_{i_{K-1}}, \ldots, \gamma_{i_1}.\label{terms} \end{equation} This corresponds to the walk through the generator tree, taking the corresponding generator branch at each step, beginning at the identity and then taking the $\gamma_{i_K}$ branch. As the algorithm terminated, there exists is a maximal $n$ such that the first product of the first $n$ terms in \eqref{terms} multiply to a found coset representative $g_0$.
If $n = K$, then we are done: $g$ actually represents the same coset as $g_0$.
But if $n < K$, then we note that each of the products $\gamma_i g_0$ were considered in the tree walking algorithm, and are thus either chosen coset representatives or equivalent to other coset representatives. Thus $n$ cannot be less than $K$.
Sage implementation
def new_coset(g1, coset_reps, Gprime):
"""
Returns whether `g1` is not represented already in `coset_reps`.
"""
for crep in coset_reps:
if g1^(-1) * crep in Gprime:
return False
return True
def coset_reps_for_congruence_quotient(Gprime, G=Gamma(1)):
"""
Return left coset representatives for G/Gprime.
"""
if not Gprime.is_subgroup(G):
raise ValueError("Gprime is not a subgroup of G")
gens = G.generators()
identity_mat = G(identity_matrix(2))
queue = [identity_mat]
coset_reps = []
while queue:
g = queue.pop(0)
if new_coset(g, coset_reps, Gprime):
coset_reps.append(g)
for gen in gens:
queue.append(gen * g)
return coset_reps
Let's check this with a few examples. Let's experiment with $\Gamma_0(8)$ and $\Gamma_0(4)$ first.
sage: Gprime = Gamma0(8)
sage: G = Gamma0(4)
sage: Gprime.index()
12
Let's generate coset reps for $\Gamma_0(8)$ inside $\mathrm{SL}(2, \mathbb{Z})$ first, and compare to sage's computed coset representatives.
sage: coset_reps_for_congruence_quotient(Gprime)
[
[1 0] [ 0 -1] [ 1 -1] [-1 0] [ 2 -1] [-1 0] [ 3 -1] [ 1 -1]
[0 1], [ 1 0], [ 1 0], [ 1 -1], [ 1 0], [ 2 -1], [ 1 0], [ 2 -1],
[-1 0] [ 4 -1] [-2 1] [-1 0]
[ 3 -1], [ 1 0], [ 1 -1], [ 4 -1]
]
sage: list(Gprime.farey_symbol().coset_reps())
[
[1 0] [ 4 -1] [ 3 -1] [ 2 -1] [ 1 -1] [ 3 -1] [ 2 -1] [-1 0]
[0 1], [ 1 0], [ 1 0], [ 1 0], [ 1 0], [ 4 -1], [ 3 -1], [ 3 -1],
[ 1 -1] [-1 0] [ 0 -1] [-1 0]
[ 2 -1], [ 2 -1], [ 1 -1], [ 1 -1]
]
Note that Gprime.coset_reps() returns a list of right representatives, but
the Farey symbol methods produce left representatives. Let's match up the
cosets:
sage: for idx1, mycrep in enumerate(coset_reps_for_congruence_quotient(Gprime)):
....: for idx2, screp in enumerate(Gprime.farey_symbol().coset_reps()):
....: if mycrep^(-1) * screp in Gprime:
....: print(idx1, idx2)
0 0
1 10
2 4
3 11
4 3
5 9
6 2
7 8
8 7
9 1
10 6
11 5
Thus this gives an equivalent (but rearranged) set of coset representatives for $\Gamma_0(8)$ inside $\mathrm{SL}(2, \mathbb{Z})$.
Now let's examine coset representatives for $\Gamma_0(8)$ inside $\Gamma_0(4)$.
sage: Gprime.index() / G.index()
2
sage: coset_reps_for_congruence_quotient(Gprime, G)
[
[1 0] [ 3 -1]
[0 1], [ 4 -1]
]
This is the correct order. Let's also try this on some larger set.
sage: basegroup = Gamma1(17)
sage: subgroup = Gamma1(17*4*5)
sage: subgroup.index() / basegroup.index()
288
sage: print(len(coset_reps_for_congruence_quotient(subgroup, basegroup)))
288
This last computation took a few seconds, but it seems alright. If the basegroup has a very large number of generators, then this becomes rather slow as the tree becomes very wide, very quickly.
Candidate second algorithm
A second algorithm, albeit a very naive algorithm, would be to choose random elements until the right number of cosets has been found. There will be lots of duplicated work as this is a coupon collector problem. I note that sage doesn't currently implement random elements for general congruence subgroups, so that would also be necessary.
Nonetheless, this works pretty well in practice. Here is an example for generating coset reps for $\Gamma_0(8)$ in $\mathrm{SL}(2, \mathbb{Z})$.
def random_coset_reps(subgroup):
"""
Find a set of coset representatives for `subgroup` in SL2Z randomly.
"""
basegroup = Gamma(1)
num = subgroup.index()
identity_mat = basegroup(identity_matrix(2))
coset_reps = [identity_mat]
while len(coset_reps) < num:
g = basegroup.random_element()
if new_coset(g, coset_reps, subgroup):
coset_reps.append(g)
return coset_reps
Running this gives1 1Note this is random, and repeated runs will give different coset evaluations.
sage: random_coset_reps(Gamma0(8))
[
[1 0] [-93 74] [-95 -6] [-12 -83] [-43 64] [-64 -71]
[0 1], [-44 35], [-79 -5], [-13 -90], [-41 61], [-73 -81],
[-42 71] [46 19] [-25 87] [-15 -56] [23 8] [ 25 -26]
[ 55 -93], [29 12], [-23 80], [-19 -71], [66 23], [ 26 -27]
]
sage: len(_)
12
These are pretty terrible looking coset representatives, but they are functional. For congruence subgroups, you want a random element function. One way to generate a random element in $\Gamma_0(N)$ is to generate a random bottom row of a matrix and then to find a suitable top row.
def random_element_in_Gamma0(N):
"""
Returns a random element in Gamma0(N).
"""
while True:
bound = N*N
c = N * randrange(-bound, bound + 1)
d = randrange(-bound, bound + 1)
g, mb, a = xgcd(c, d)
if g != 1:
continue
b = -mb
return Gamma0(N)([[a, b], [c, d]])
Suitable adjustments can be made for a desired congruence subgroup. This can be used to find random coset representatives subgroups of $\Gamma_0(N)$ (though in principle it may be necessary to increase the possible range of coefficients — I didn't think about this).
def random_coset_reps_Gamma0N(subgroup, N):
"""
Find a set of coset representatives for `subgroup` in Gamma0(N) randomly.
"""
basegroup = Gamma0(N)
num = subgroup.index() / basegroup.index()
identity_mat = basegroup(identity_matrix(2))
coset_reps = [identity_mat]
while len(coset_reps) < num:
g = random_element_in_Gamma0(N)
if new_coset(g, coset_reps, subgroup):
coset_reps.append(g)
return coset_reps
Running a few times with $\Gamma_0(4)/\Gamma_0(8)$ gives
sage: random_coset_reps_Gamma0N(Gprime, 4)
[
[1 0] [ 1 0]
[0 1], [-4 1]
]
sage: random_coset_reps_Gamma0N(Gprime, 4)
[
[1 0] [1 0]
[0 1], [4 1]
]
The cosets can sometimes be different. On a less trivial example:
sage: random_coset_reps_Gamma0N(Gamma0(4*5*6), 4)
[
[1 0] [ -7 1] [ 3 1] [ -1 0] [ 7 -1] [ -5 2] [-3 1]
[0 1], [-36 5], [-28 -9], [-28 -1], [-48 7], [-28 11], [ 8 -3],
[15 2] [ 1 0] [ 1 0] [ 1 0] [17 5] [ 11 1] [ 5 1]
[52 7], [-44 1], [-32 1], [64 1], [44 13], [-56 -5], [44 9],
[ 13 -2] [ 3 -1] [ 1 3] [ 23 5] [ 7 -3] [1 1] [ 7 1]
[-32 5], [ 40 -13], [ -4 -11], [-60 -13], [-16 7], [8 9], [48 7],
[-13 1] [ -9 1] [-29 5] [ -3 -1] [1 0] [ 1 0]
[-40 3], [-64 7], [-64 11], [-44 -15], [4 1], [-20 1],
[-23 4] [ 7 -1] [ 13 -4] [-19 4] [ -3 2] [ -5 1]
[-52 9], [64 -9], [ 36 -11], [ 52 -11], [-20 13], [ 64 -13],
[-25 -4] [11 3] [ 5 -1] [-15 7] [ 11 3] [-11 2]
[-56 -9], [40 11], [-24 5], [ 32 -15], [-48 -13], [-28 5],
[-11 -4] [-11 4] [ 9 -2] [ 5 -2] [ 9 2] [ 19 2]
[ 36 13], [-36 13], [32 -7], [-12 5], [-32 -7], [-48 -5],
[21 2] [ -7 -1] [ -3 1]
[52 5], [-20 -3], [-28 9]
]
Info on how to comment
To make a comment, please send an email using the button below. Your email address won't be shared (unless you include it in the body of your comment). If you don't want your real name to be used next to your comment, please specify the name you would like to use. If you want your name to link to a particular url, include that as well.
bold, italics, and plain text are allowed in comments. A reasonable subset of markdown is supported, including lists, links, and fenced code blocks. In addition, math can be formatted using
$(inline math)$or$$(your display equation)$$.Please use plaintext email when commenting. See Plaintext Email and Comments on this site for more. Note also that comments are expected to be open, considerate, and respectful.