Cython helper functions for congruence subgroups¶
This file contains optimized Cython implementations of a few functions related
to the standard congruence subgroups . 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
be a positive integer and
a divisor of
. Let
be a divisor of
, and let
be the
matrix
. This function returns representatives for the orbit set
, where
acts on the left on
.
INPUT:
N
– intM
– int (divisor of)
t
– int (divisor of)
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
, that the group
is contained in
, and that
is contained in
.
ALGORITHM:
- Compute representatives for
inside of
:
- COSET EQUIVALENCE: Two right cosets represented by
and
of
in
are equivalent if and only if
as points of
, i.e.,
, and
as points of
.
- ALGORITHM to list all cosets:
- Compute the number of cosets.
- Compute a random element
of
.
- Check if x is equivalent to anything generated so far; if not, add x to the list.
- Continue until the list is as long as the bound computed in step (a).
- There is a bijection between
and
given by
. Consequently we obtain coset representatives for
by left multiplying by
each coset representative of
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
be a positive integer and
a divisor of
. Let
be a divisor of
, and let
be the
matrix
. This function returns representatives for the orbit set
, where
acts on the left on
.
INPUT:
N
– intM
– int (divisor of)
t
– int (divisor of)
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. Hereconsists of matrices that are of the form
and
.
COSET EQUIVALENCE: Two right cosets represented by
and
of
in
are equivalent if and only if
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
.
ALGORITHM: Given coset representatives for a finite index subgroup
of
we compute generators for
as follows. Let
be a set of coset representatives for
. Let
be defined by
and
, respectively. Define maps
as follows. If
, then there exists a unique
such that
. Let
. Likewise, there is a unique
such that
and we let
. Note that
and
are in
for all
. Then
is generated by
.
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] ]