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.
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:
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:
- 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).
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
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:
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 consists 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
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]
]