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