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.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.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.generators_helper(coset_reps, level)

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