# mixedmath

Explorations in math and programming
David Lowry-Duda

# 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]
]


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