# Cython helper functions for congruence subgroups¶

Cython helper functions for congruence subgroups

This file contains optimized Cython implementations of a few functions related to the standard congruence subgroups $$\Gamma_0, \Gamma_1, \Gamma_H$$. These functions are for internal use by routines elsewhere in the Sage library.

sage.modular.arithgroup.congroup_pyx.degeneracy_coset_representatives_gamma0(N, M, t)

Let $$N$$ be a positive integer and $$M$$ a divisor of $$N$$. Let $$t$$ be a divisor of $$N/M$$, and let $$T$$ be the $$2 \times 2$$ matrix $$(1, 0; 0, t)$$. This function returns representatives for the orbit set $$\Gamma_0(N) \backslash T \Gamma_0(M)$$, where $$\Gamma_0(N)$$ acts on the left on $$T \Gamma_0(M)$$.

INPUT:

• N – int
• M – int (divisor of $$N$$)
• t – int (divisor of $$N/M$$)

OUTPUT:

list – list of lists [a,b,c,d], where [a,b,c,d] should be viewed as a 2x2 matrix.

This function is used for computation of degeneracy maps between spaces of modular symbols, hence its name.

We use that $$T^{-1} \cdot (a,b;c,d) \cdot T = (a,bt; c/t,d)$$, that the group $$T^{-1} \Gamma_0(N) T$$ is contained in $$\Gamma_0(M)$$, and that $$\Gamma_0(N) T$$ is contained in $$T \Gamma_0(M)$$.

ALGORITHM:

1. Compute representatives for $$\Gamma_0(N/t,t)$$ inside of $$\Gamma_0(M)$$:
• COSET EQUIVALENCE: Two right cosets represented by $$[a,b;c,d]$$ and $$[a',b';c',d']$$ of $$\Gamma_0(N/t,t)$$ in $${\rm SL}_2(\ZZ)$$ are equivalent if and only if $$(a,b)=(a',b')$$ as points of $$\mathbf{P}^1(\ZZ/t\ZZ)$$, i.e., $$ab' \cong ba' \pmod{t}$$, and $$(c,d) = (c',d')$$ as points of $$\mathbf{P}^1(\ZZ/(N/t)\ZZ)$$.
• ALGORITHM to list all cosets:
1. Compute the number of cosets.
2. Compute a random element $$x$$ of $$\Gamma_0(M)$$.
3. Check if x is equivalent to anything generated so far; if not, add x to the list.
4. Continue until the list is as long as the bound computed in step (a).
1. There is a bijection between $$\Gamma_0(N)\backslash T \Gamma_0(M)$$ and $$\Gamma_0(N/t,t) \backslash \Gamma_0(M)$$ given by $$T r \leftrightarrow r$$. Consequently we obtain coset representatives for $$\Gamma_0(N)\backslash T \Gamma_0(M)$$ by left multiplying by $$T$$ each coset representative of $$\Gamma_0(N/t,t) \backslash \Gamma_0(M)$$ found in step 1.

EXAMPLES:

sage: from sage.modular.arithgroup.all import degeneracy_coset_representatives_gamma0
sage: len(degeneracy_coset_representatives_gamma0(13, 1, 1))
14
sage: len(degeneracy_coset_representatives_gamma0(13, 13, 1))
1
sage: len(degeneracy_coset_representatives_gamma0(13, 1, 13))
14

sage.modular.arithgroup.congroup_pyx.degeneracy_coset_representatives_gamma1(N, M, t)

Let $$N$$ be a positive integer and $$M$$ a divisor of $$N$$. Let $$t$$ be a divisor of $$N/M$$, and let $$T$$ be the $$2 \times 2$$ matrix $$(1,0; 0,t)$$. This function returns representatives for the orbit set $$\Gamma_1(N) \backslash T \Gamma_1(M)$$, where $$\Gamma_1(N)$$ acts on the left on $$T \Gamma_1(M)$$.

INPUT:

• N – int
• M – int (divisor of $$N$$)
• t – int (divisor of $$N/M$$)

OUTPUT:

list – list of lists [a,b,c,d], where [a,b,c,d] should be viewed as a 2x2 matrix.

This function is used for computation of degeneracy maps between spaces of modular symbols, hence its name.

ALGORITHM:

Everything is the same as for degeneracy_coset_representatives_gamma0(), except for coset equivalence. Here $$\Gamma_1(N/t,t)$$ consists of matrices that are of the form $$(1,*; 0,1) \bmod N/t$$ and $$(1,0; *,1) \bmod t$$.

COSET EQUIVALENCE: Two right cosets represented by $$[a,b;c,d]$$ and $$[a',b';c',d']$$ of $$\Gamma_1(N/t,t)$$ in $${\rm SL}_2(\ZZ)$$ are equivalent if and only if

$a \cong a' \pmod{t}, b \cong b' \pmod{t}, c \cong c' \pmod{N/t}, d \cong d' \pmod{N/t}.$

EXAMPLES:

sage: from sage.modular.arithgroup.all import degeneracy_coset_representatives_gamma1
sage: len(degeneracy_coset_representatives_gamma1(13, 1, 1))
168
sage: len(degeneracy_coset_representatives_gamma1(13, 13, 1))
1
sage: len(degeneracy_coset_representatives_gamma1(13, 1, 13))
168

sage.modular.arithgroup.congroup_pyx.generators_helper(coset_reps, level, Mat2Z)

Helper function for generators of Gamma0, Gamma1 and GammaH.

These are computed using coset representatives, via an “inverse Todd-Coxeter” algorithm, and generators for $${\rm SL}_2(\ZZ)$$.

ALGORITHM: Given coset representatives for a finite index subgroup $$G$$ of $${\rm SL}_2(\ZZ)$$ we compute generators for $$G$$ as follows. Let $$R$$ be a set of coset representatives for $$G$$. Let $$S, T \in {\rm SL}_2(\ZZ)$$ be defined by $$(0,-1; 1,0)$$ and $$(1,1,0,1)$$, respectively. Define maps $$s, t: R \to G$$ as follows. If $$r \in R$$, then there exists a unique $$r' \in R$$ such that $$GrS = Gr'$$. Let $$s(r) = rSr'^{-1}$$. Likewise, there is a unique $$r'$$ such that $$GrT = Gr'$$ and we let $$t(r) = rTr'^{-1}$$. Note that $$s(r)$$ and $$t(r)$$ are in $$G$$ for all $$r$$. Then $$G$$ is generated by $$s(R)\cup t(R)$$.

There are more sophisticated algorithms using group actions on trees (and Farey symbols) that give smaller generating sets – this code is now deprecated in favour of the newer implementation based on Farey symbols.

EXAMPLES:

sage: Gamma0(7).generators(algorithm="todd-coxeter") # indirect doctest
[
[1 1]  [-1  0]  [ 1 -1]  [1 0]  [1 1]  [-3 -1]  [-2 -1]  [-5 -1]
[0 1], [ 0 -1], [ 0  1], [7 1], [0 1], [ 7  2], [ 7  3], [21  4],

[-4 -1]  [-1  0]  [ 1  0]
[21  5], [ 7 -1], [-7  1]
]


#### Previous topic

Farey Symbol for arithmetic subgroups of $${\rm PSL}_2(\ZZ)$$