A subgroup of finite index of a finitely generated group
is completely
described by the action of a set of generators of
on the right cosets
. After some arbitrary choice of numbering one
can identify the action of generators as elements of a symmetric group acting
transitively (and satisfying the relations of the relators in G). As
has a very simple presentation as a central extension of a free
product of cyclic groups, one can easily design algorithms from this point of
view.
The generators of used in this module are named as follows
,
,
,
which are defined by
Those generators satisfy the following relations
In particular not all four are needed to generate the whole group . Three couples which generate
are of particular
interest:
Part of these functions are based on Chris Kurth’s KFarey package [Kur08]. For tests see the file sage.modular.arithgroup.tests.
REFERENCES:
[AtSD71] | A. O. L. Atkin and H. P. F. Swinnerton-Dyer, “Modular forms on noncongruence subgroups”, Proc. Symp. Pure Math., Combinatorics (T. S. Motzkin, ed.), vol. 19, AMS, Providence 1971 |
[Hsu96] | Tim Hsu, “Identifying congruence subgroups of the modular group”, Proc. AMS 124, no. 5, 1351-1359 (1996) |
[Hsu97] | Tim Hsu, “Permutation techniques for coset representations of modular subgroups”, in L. Schneps (ed.), Geometric Galois Actions II: Dessins d’Enfants, Mapping Class Groups and Moduli, volume 243 of LMS Lect. Notes, 67-77, Cambridge Univ. Press (1997) |
[Go09] | Alexey G. Gorinov, “Combinatorics of double cosets and fundamental domains for the subgroups of the modular group”, preprint Arxiv 0901.1340 |
[KSV11] | (1, 2, 3, 4) Ian Kiming, Matthias Schuett and Helena Verrill, “Lifts of projective congruence groups”, J. London Math. Soc. (2011) 83 (1): 96-120, http://dx.doi.org/10.1112/jlms/jdq062. Arxiv version: Arxiv 0905.4798. |
[Kul91] | Ravi Kulkarni “An arithmetic geometric method in the study of the subgroups of the modular group”, American Journal of Mathematics 113 (1991), no 6, 1053-1133 |
[Kur08] | (1, 2) Chris Kurth, “K Farey package for Sage” |
[KuLo] | Chris Kurth and Ling Long, “Computations with finite index subgroups
of ![]() |
[Ve] | Helena Verrill, “Fundamental domain drawer”, Java program, http://www.math.lsu.edu/~verrill/ |
TODO:
modular Farey symbols
computation of generators of a modular subgroup with a standard surface group presentation. In other words, compute a presentation of the form
where the elements and
are hyperbolic and
are parabolic
(
) or elliptic elements (
).
computation of centralizer.
generation of modular (even) subgroups of fixed index.
AUTHORS:
Construct a subgroup of from the action of generators on its
right cosets.
Return an arithmetic subgroup knowing the action, given by permutations, of at least two standard generators on the its cosets. The generators considered are the following matrices:
An error will be raised if only one permutation is given. If no arguments
are given at all, the full modular group is returned.
INPUT:
EXAMPLES:
sage: G = ArithmeticSubgroup_Permutation(S2="(1,2)(3,4)",S3="(1,2,3)")
sage: G
Arithmetic subgroup with permutations of right cosets
S2=(1,2)(3,4)
S3=(1,2,3)
L=(1,4,3)
R=(2,4,3)
sage: G.index()
4
sage: G = ArithmeticSubgroup_Permutation(); G
Arithmetic subgroup with permutations of right cosets
S2=()
S3=()
L=()
R=()
sage: G == SL2Z
True
Some invalid inputs:
sage: ArithmeticSubgroup_Permutation(S2="(1,2)")
Traceback (most recent call last):
...
ValueError: Need at least two generators
sage: ArithmeticSubgroup_Permutation(S2="(1,2)",S3="(3,4,5)")
Traceback (most recent call last):
...
ValueError: Permutations do not generate a transitive group
sage: ArithmeticSubgroup_Permutation(L="(1,2)",R="(1,2,3)")
Traceback (most recent call last):
...
ValueError: Wrong relations between generators
sage: ArithmeticSubgroup_Permutation(S2="(1,2,3,4)",S3="()")
Traceback (most recent call last):
...
ValueError: S2^2 does not equal to S3^3
sage: ArithmeticSubgroup_Permutation(S2="(1,4,2,5,3)", S3="(1,3,5,2,4)")
Traceback (most recent call last):
...
ValueError: S2^2 = S3^3 must have order 1 or 2
The input checks can be disabled for speed:
sage: ArithmeticSubgroup_Permutation(S2="(1,2)",S3="(3,4,5)", check=False) # don't do this!
Arithmetic subgroup with permutations of right cosets
S2=(1,2)
S3=(3,4,5)
L=(1,2)(3,5,4)
R=(1,2)(3,4,5)
Bases: sage.modular.arithgroup.arithgroup_generic.ArithmeticSubgroup
A subgroup of defined by the action of generators on its
coset graph.
The class stores the action of generators on right cosets
of a finite index subgroup
. In particular the action of
on the cosets is on right.
TEST:
sage: s2 = PermutationGroupElement('(1,2)(3,4)(5,6)')
sage: s3 = PermutationGroupElement('(1,3,5)(2,4,6)')
sage: G = ArithmeticSubgroup_Permutation(S2=s2, S3=s3)
sage: G.S2() == s2
True
sage: G.S3() == s3
True
sage: G == ArithmeticSubgroup_Permutation(L=G.L(), R=G.R())
True
sage: G == ArithmeticSubgroup_Permutation(L=G.L(), S2=G.S2())
True
sage: G == ArithmeticSubgroup_Permutation(L=G.L(), S3=G.S3())
True
sage: G == ArithmeticSubgroup_Permutation(R=G.R(), S2=G.S2())
True
sage: G == ArithmeticSubgroup_Permutation(R=G.R(), S3=G.S3())
True
sage: G == ArithmeticSubgroup_Permutation(S2=G.S2(), S3=G.S3())
True
sage: G = ArithmeticSubgroup_Permutation(S2='',S3='')
sage: TestSuite(G).run()
sage: S2 = '(1,2)(3,4)(5,6)'
sage: S3 = '(1,2,3)(4,5,6)'
sage: G = ArithmeticSubgroup_Permutation(S2=S2, S3=S3)
sage: TestSuite(G).run()
Return the action of the matrix as a permutation of cosets.
EXAMPLES:
sage: G = ArithmeticSubgroup_Permutation(S2="(1,2)",S3="(1,2,3)")
sage: G.L()
(1,3)
Return the action of the matrix as a permutation of cosets.
EXAMPLES:
sage: G = ArithmeticSubgroup_Permutation(S2="(1,2)",S3="(1,2,3)")
sage: G.R()
(2,3)
Return the action of the matrix as a permutation of cosets.
EXAMPLES:
sage: G = ArithmeticSubgroup_Permutation(S2="(1,2)",S3="(1,2,3)")
sage: G.S2()
(1,2)
Return the action of the matrix as a permutation of cosets.
EXAMPLES:
sage: G = ArithmeticSubgroup_Permutation(S2="(1,2)",S3="(1,2,3)")
sage: G.S3()
(1,2,3)
Returns the smallest congruence subgroup containing self. If self is congruence, this is just self, but represented as a congruence subgroup data type. If self is not congruence, then it may be larger.
In practice, we use the following criterion: let be the generalised
level of self. If this subgroup is even, let
, else let
. Then any congruence subgroup containing self contains
(a generalisation of Wohlfahrt’s theorem due to Kiming, Verrill and
Schuett). So we compute the image of self modulo
and return the
preimage of that.
EXAMPLE:
sage: Gamma1(3).as_permutation_group().congruence_closure()
Congruence subgroup of SL(2,Z) of level 3, preimage of:
Matrix group over Ring of integers modulo 3 with 2 generators (
[1 2] [1 1]
[0 1], [0 1]
)
sage: sage.modular.arithgroup.arithgroup_perm.HsuExample10().congruence_closure() # long time (11s on sage.math, 2012)
Modular Group SL(2,Z)
Return the right (or left) coset graph.
INPUT:
EXAMPLES:
sage: G = ArithmeticSubgroup_Permutation(S2="(1,2)",S3="()")
sage: G
Arithmetic subgroup with permutations of right cosets
S2=(1,2)
S3=()
L=(1,2)
R=(1,2)
sage: G.index()
2
sage: G.coset_graph()
Looped multi-digraph on 2 vertices
Return the generalised level of this subgroup.
The generalised level of a subgroup of the modular group is the least common multiple of the widths of the cusps. It was proven by Wohlfart that for even congruence subgroups, the (conventional) level coincides with the generalised level. For odd congruence subgroups the level is either the generalised level, or twice the generalised level [KSV11].
EXAMPLES:
sage: G = Gamma(2).as_permutation_group()
sage: G.generalised_level()
2
sage: G = Gamma0(3).as_permutation_group()
sage: G.generalised_level()
3
Returns the index of this modular subgroup in the full modular group.
EXAMPLES:
sage: G = Gamma(2)
sage: P = G.as_permutation_group()
sage: P.index()
6
sage: G.index() == P.index()
True
sage: G = Gamma0(8)
sage: P = G.as_permutation_group()
sage: P.index()
12
sage: G.index() == P.index()
True
sage: G = Gamma1(6)
sage: P = G.as_permutation_group()
sage: P.index()
24
sage: G.index() == P.index()
True
Test whether the group is normal
EXAMPLES:
sage: G = Gamma(2).as_permutation_group()
sage: G.is_normal()
True
sage: G = Gamma1(2).as_permutation_group()
sage: G.is_normal()
False
Return the underlying permutation group.
The permutation group returned is isomorphic to the action of the
generators (element of order two),
(element of order 3),
(parabolic element) and
(parabolic element) on right cosets (the
action is on the right).
EXAMPLE:
sage: import sage.modular.arithgroup.arithgroup_perm as ap
sage: ap.HsuExample10().perm_group()
Permutation Group with generators [(1,2)(3,4)(5,6)(7,8)(9,10), (1,4)(2,5,9,10,8)(3,7,6), (1,7,9,10,6)(2,3)(4,5,8), (1,8,3)(2,4,6)(5,7,10)]
Given an element x of , compute the permutation of the
cosets of self given by right multiplication by x.
EXAMPLE:
sage: import sage.modular.arithgroup.arithgroup_perm as ap
sage: ap.HsuExample10().permutation_action(SL2Z([32, -21, -67, 44]))
(1,4,6,2,10,5,3,7,8,9)
Returns a random element in this subgroup.
The algorithm uses a random walk on the Cayley graph of stopped
at the first time it reaches the subgroup after at least
initial_steps steps.
INPUT:
EXAMPLES:
sage: G = ArithmeticSubgroup_Permutation(S2='(1,3)(4,5)',S3='(1,2,5)(3,4,6)')
sage: all(G.random_element() in G for _ in xrange(10))
True
Relabel the cosets of this modular subgroup in a canonical way.
The implementation of modular subgroup by action of generators on cosets depends on the choice of a numbering. This function provides canonical labels in the sense that two equal subgroups whith different labels are relabeled the same way. The default implementation relabels the group itself. If you want to get a relabeled copy of your modular subgroup, put to False the option inplace.
ALGORITHM:
We give an overview of how the canonical labels for the modular subgroup
are built. The procedure only uses the permutations and
that
define the modular subgroup and can be used to renumber any
transitive action of the symmetric group. In other words, the algorithm
construct a canonical representative of a transitive subgroup in its
conjugacy class in the full symmetric group.
1. The identity is still numbered and set the curent vertex to be
the identity.
2. Number the cycle of the current vertex belongs to: if the
current vertex is labeled
then the numbering in such way that the
cycle becomes
).
3. Find a new current vertex using the permutation .
If all vertices are relabeled then it’s done, otherwise go to step 2.
EXAMPLES:
sage: S2 = "(1,2)(3,4)(5,6)"; S3 = "(1,2,3)(4,5,6)"
sage: G1 = ArithmeticSubgroup_Permutation(S2=S2,S3=S3); G1
Arithmetic subgroup with permutations of right cosets
S2=(1,2)(3,4)(5,6)
S3=(1,2,3)(4,5,6)
L=(1,4,5,3)
R=(2,4,6,3)
sage: G1.relabel(); G1
Arithmetic subgroup with permutations of right cosets
S2=(1,2)(3,4)(5,6)
S3=(1,2,3)(4,5,6)
L=(1,4,5,3)
R=(2,4,6,3)
sage: S2 = "(1,2)(3,5)(4,6)"; S3 = "(1,2,3)(4,5,6)"
sage: G2 = ArithmeticSubgroup_Permutation(S2=S2,S3=S3); G2
Arithmetic subgroup with permutations of right cosets
S2=(1,2)(3,5)(4,6)
S3=(1,2,3)(4,5,6)
L=(1,5,6,3)
R=(2,5,4,3)
sage: G2.relabel(); G2
Arithmetic subgroup with permutations of right cosets
S2=(1,2)(3,4)(5,6)
S3=(1,2,3)(4,5,6)
L=(1,4,5,3)
R=(2,4,6,3)
sage: S2 = "(1,2)(3,6)(4,5)"; S3 = "(1,2,3)(4,5,6)"
sage: G3 = ArithmeticSubgroup_Permutation(S2=S2,S3=S3); G3
Arithmetic subgroup with permutations of right cosets
S2=(1,2)(3,6)(4,5)
S3=(1,2,3)(4,5,6)
L=(1,6,4,3)
R=(2,6,5,3)
sage: G4 = G3.relabel(inplace=False)
sage: G4
Arithmetic subgroup with permutations of right cosets
S2=(1,2)(3,4)(5,6)
S3=(1,2,3)(4,5,6)
L=(1,4,5,3)
R=(2,4,6,3)
sage: G3 is G4
False
TESTS:
sage: S2 = "(1,2)(3,6)(4,5)"
sage: S3 = "(1,2,3)(4,5,6)"
sage: G = ArithmeticSubgroup_Permutation(S2=S2,S3=S3)
sage: H = G.relabel(inplace=False)
sage: G is H
False
sage: G._S2 is H._S2 or G._S3 is H._S3 or G._L is H._L or G._R is H._R
False
sage: G.relabel(inplace=False) is H
True
sage: H.relabel(inplace=False) is H
True
sage: G.relabel(); G
Arithmetic subgroup with permutations of right cosets
S2=(1,2)(3,4)(5,6)
S3=(1,2,3)(4,5,6)
L=(1,4,5,3)
R=(2,4,6,3)
sage: G.relabel(inplace=False) is G
True
Bases: sage.modular.arithgroup.arithgroup_perm.ArithmeticSubgroup_Permutation_class
An arithmetic subgroup defined by two permutations, giving the
action of four standard generators
by right multiplication on the coset representatives .
EXAMPLES:
Construct a noncongruence subgroup of index 7 (the smallest possible):
sage: a2 = SymmetricGroup(7)([(1,2),(3,4),(6,7)]); a3 = SymmetricGroup(7)([(1,2,3),(4,5,6)])
sage: G = ArithmeticSubgroup_Permutation(S2=a2, S3=a3); G
Arithmetic subgroup with permutations of right cosets
S2=(1,2)(3,4)(6,7)
S3=(1,2,3)(4,5,6)
L=(1,4,7,6,5,3)
R=(2,4,5,7,6,3)
sage: G.index()
7
sage: G.dimension_cusp_forms(4)
1
sage: G.is_congruence()
False
Convert some standard congruence subgroups into permutation form:
sage: G = Gamma0(8).as_permutation_group()
sage: G.index()
12
sage: G.is_congruence()
True
sage: G = Gamma0(12).as_permutation_group()
sage: print G
Arithmetic subgroup of index 24
sage: G.is_congruence()
True
The following is the unique index 2 even subgroup of :
sage: w = SymmetricGroup(2)([2,1])
sage: G = ArithmeticSubgroup_Permutation(L=w, R=w)
sage: G.dimension_cusp_forms(6)
1
sage: G.genus()
0
Return coset representatives.
EXAMPLES:
sage: G = ArithmeticSubgroup_Permutation(S2="(1,2)(3,4)",S3="(1,2,3)")
sage: c = G.coset_reps()
sage: len(c)
4
sage: [g in G for g in c]
[True, False, False, False]
Return the list of cusp widths of the group.
EXAMPLES:
sage: G = Gamma(2).as_permutation_group()
sage: G.cusp_widths()
[2, 2, 2]
sage: G.cusp_widths(exp=True)
{2: 3}
sage: S2 = "(1,2)(3,4)(5,6)"
sage: S3 = "(1,2,3)(4,5,6)"
sage: G = ArithmeticSubgroup_Permutation(S2=S2,S3=S3)
sage: G.cusp_widths()
[1, 1, 4]
sage: G.cusp_widths(exp=True)
{1: 2, 4: 1}
sage: S2 = "(1,2)(3,4)(5,6)"
sage: S3 = "(1,3,5)(2,4,6)"
sage: G = ArithmeticSubgroup_Permutation(S2=S2,S3=S3)
sage: G.cusp_widths()
[6]
sage: G.cusp_widths(exp=True)
{6: 1}
Return True if this is a congruence subgroup.
ALGORITHM:
Uses Hsu’s algorithm [Hsu96]. Adapted from Chris Kurth’s implementation in KFarey [Kur08].
EXAMPLES:
Test if is congruence:
sage: a = ArithmeticSubgroup_Permutation(L='',R='')
sage: a.index()
1
sage: a.is_congruence()
True
This example is congruence – it’s Gamma0(3) in disguise:
sage: S2 = SymmetricGroup(4)
sage: l = S2((2,3,4))
sage: r = S2((1,3,4))
sage: G = ArithmeticSubgroup_Permutation(L=l,R=r)
sage: print G
Arithmetic subgroup with permutations of right cosets
S2=(1,2)(3,4)
S3=(1,4,2)
L=(2,3,4)
R=(1,3,4)
sage: G.is_congruence()
True
This one is noncongruence:
sage: import sage.modular.arithgroup.arithgroup_perm as ap
sage: ap.HsuExample10().is_congruence()
False
Returns True if this subgroup contains the matrix .
EXAMPLES:
sage: G = Gamma(2).as_permutation_group()
sage: G.is_even()
True
Returns True if this subgroup does not contain the matrix .
EXAMPLES:
sage: G = Gamma(2).as_permutation_group()
sage: G.is_odd()
False
Return the number of cusps of this arithmetic subgroup.
EXAMPLES:
sage: G = ArithmeticSubgroup_Permutation(S2="(1,2)(3,4)(5,6)",S3="(1,2,3)(4,5,6)")
sage: G.ncusps()
3
Returns the number of orbits of elliptic points of order 2 for this arithmetic subgroup.
EXAMPLES:
sage: G = ArithmeticSubgroup_Permutation(S2="(1,4)(2)(3)",S3="(1,2,3)(4)")
sage: G.nu2()
2
Returns the number of orbits of elliptic points of order 3 for this arithmetic subgroup.
EXAMPLES:
sage: G = ArithmeticSubgroup_Permutation(S2="(1,4)(2)(3)",S3="(1,2,3)(4)")
sage: G.nu3()
1
Return a list of the odd subgroups of index 2 in , where
is this subgroup. (Equivalently, return the liftings of
to
.)
See also
one_odd_subgroup(), which returns just one of the odd subgroups (which is much quicker than enumerating them all).
ALGORITHM:
If has an element of order 4, then there are no index 2 odd
subgroups, so return the empty set.
If has no elements of order 4, then the permutation
is
a combination of 2-cycles with no fixed points on
.
We construct the permutation
of
which has a 4-cycle
for each 2-cycle
in
S2. Similarly, we construct a permutation
which has
a 6-cycle
for each 3-cycle
in
,
and a 2-cycle
for each fixed point
of
.
Then the permutations and
satisfy
where
is the order 2
permutation interchanging
and
for each
. So the subgroup
corresponding to these permutations is an index 2 odd subgroup of
.
The other index 2 odd subgroups of are obtained from the
pairs
where
is an element
of the group generated by the 2-cycles
.
Studying the permutations in the first example below gives a good illustration of the algorithm.
EXAMPLES:
sage: G = sage.modular.arithgroup.arithgroup_perm.HsuExample10()
sage: [G.S2(), G.S3()]
[(1,2)(3,4)(5,6)(7,8)(9,10), (1,8,3)(2,4,6)(5,7,10)]
sage: X = G.odd_subgroups()
sage: for u in X: print [u.S2(), u.S3()]
[(1,2,11,12)(3,4,13,14)(5,6,15,16)(7,8,17,18)(9,10,19,20), (1,8,3,11,18,13)(2,4,6,12,14,16)(5,7,10,15,17,20)(9,19)]
[(1,2,11,12)(3,4,13,14)(5,6,15,16)(7,8,17,18)(9,10,19,20), (1,18,13,11,8,3)(2,4,6,12,14,16)(5,7,10,15,17,20)(9,19)]
[(1,2,11,12)(3,4,13,14)(5,6,15,16)(7,8,17,18)(9,10,19,20), (1,8,13,11,18,3)(2,4,6,12,14,16)(5,7,10,15,17,20)(9,19)]
[(1,2,11,12)(3,4,13,14)(5,6,15,16)(7,8,17,18)(9,10,19,20), (1,18,3,11,8,13)(2,4,6,12,14,16)(5,7,10,15,17,20)(9,19)]
A projective congruence subgroup may have noncongruence liftings, as the example of illustrates (see [KSV11]):
sage: X = Gamma0(6).as_permutation_group().odd_subgroups(); Sequence([[u.S2(), u.S3()] for u in X],cr=True)
[
[(1,3,13,15)(2,4,14,16)(5,7,17,19)(6,10,18,22)(8,12,20,24)(9,11,21,23), (1,2,3,13,14,15)(4,5,6,16,17,18)(7,8,9,19,20,21)(10,11,12,22,23,24)],
[(1,3,13,15)(2,4,14,16)(5,7,17,19)(6,10,18,22)(8,12,20,24)(9,11,21,23), (1,14,15,13,2,3)(4,5,6,16,17,18)(7,8,9,19,20,21)(10,11,12,22,23,24)],
[(1,3,13,15)(2,4,14,16)(5,7,17,19)(6,10,18,22)(8,12,20,24)(9,11,21,23), (1,2,3,13,14,15)(4,17,6,16,5,18)(7,8,9,19,20,21)(10,11,12,22,23,24)],
[(1,3,13,15)(2,4,14,16)(5,7,17,19)(6,10,18,22)(8,12,20,24)(9,11,21,23), (1,14,15,13,2,3)(4,17,6,16,5,18)(7,8,9,19,20,21)(10,11,12,22,23,24)],
[(1,3,13,15)(2,4,14,16)(5,7,17,19)(6,10,18,22)(8,12,20,24)(9,11,21,23), (1,2,3,13,14,15)(4,5,6,16,17,18)(7,20,9,19,8,21)(10,11,12,22,23,24)],
[(1,3,13,15)(2,4,14,16)(5,7,17,19)(6,10,18,22)(8,12,20,24)(9,11,21,23), (1,14,15,13,2,3)(4,5,6,16,17,18)(7,20,9,19,8,21)(10,11,12,22,23,24)],
[(1,3,13,15)(2,4,14,16)(5,7,17,19)(6,10,18,22)(8,12,20,24)(9,11,21,23), (1,2,3,13,14,15)(4,17,6,16,5,18)(7,20,9,19,8,21)(10,11,12,22,23,24)],
[(1,3,13,15)(2,4,14,16)(5,7,17,19)(6,10,18,22)(8,12,20,24)(9,11,21,23), (1,14,15,13,2,3)(4,17,6,16,5,18)(7,20,9,19,8,21)(10,11,12,22,23,24)]
]
sage: [u.is_congruence() for u in X]
[True, False, False, True, True, False, False, True]
Subgroups of large index may take a very long time:
sage: len(GammaH(11,[-1]).as_permutation_group().odd_subgroups()) # long time (up to 51s on sage.math, 2012)
2048
Return an odd subgroup of index 2 in , where
is this
subgroup. If the optional argument random is False (the default),
this returns an arbitrary but consistent choice from the set of index 2
odd subgroups. If random is True, then it will choose one of these
at random.
For details of the algorithm used, see the docstring for the related function odd_subgroups(), which returns a list of all the index 2 odd subgroups.
EXAMPLES:
Starting from we get back
:
sage: G = Gamma(4).as_permutation_group()
sage: print G.is_odd(), G.index()
True 48
sage: Ge = G.to_even_subgroup()
sage: Go = Ge.one_odd_subgroup()
sage: print Go.is_odd(), Go.index()
True 48
sage: Go == G
True
Strating from we get a different group:
sage: G = Gamma(6).as_permutation_group()
sage: print G.is_odd(), G.index()
True 144
sage: Ge = G.to_even_subgroup()
sage: Go = Ge.one_odd_subgroup()
sage: print Go.is_odd(), Go.index()
True 144
sage: Go == G
False
An error will be raised if there are no such subgroups, which occurs if and only if the group contains an element of order 4:
sage: Gamma0(10).as_permutation_group().one_odd_subgroup()
Traceback (most recent call last):
...
ValueError: Group contains an element of order 4, hence no index 2 odd subgroups
Testing randomness:
sage: G = Gamma(6).as_permutation_group().to_even_subgroup()
sage: G1 = G.one_odd_subgroup(random=True) # random
sage: G1.is_subgroup(G)
True
Return the subgroup generated by self and -Id. Since self is even, this is just self. Provided for compatibility.
EXAMPLE:
sage: G = Gamma0(4).as_permutation_group()
sage: H = G.to_even_subgroup()
sage: H == G
True
Returns a 4-tuple (coset_reps, gens, l, s2) where coset_reps is
a list of coset representatives of the subgroup, gens a list of
generators, l and s2 are list that corresponds to the action of
the matrix and
on the cosets.
EXAMPLES:
sage: G = ArithmeticSubgroup_Permutation(S2='(1,2)(3,4)',S3='(1,2,3)')
sage: reps,gens,l,s=G.todd_coxeter_l_s2()
sage: reps
[
[1 0] [ 0 -1] [1 2] [1 1]
[0 1], [ 1 0], [0 1], [0 1]
]
sage: gens
[
[1 3] [ 1 0] [ 2 -3]
[0 1], [-1 1], [ 1 -1]
]
sage: l
[3, 1, 0, 2]
sage: s
[1, 0, 3, 2]
sage: S2 = SL2Z([0,-1,1,0])
sage: L = SL2Z([1,1,0,1])
sage: reps[0] == SL2Z([1,0,0,1])
True
sage: all(reps[i]*S2*~reps[s[i]] in G for i in xrange(4))
True
sage: all(reps[i]*L*~reps[l[i]] in G for i in xrange(4))
True
Returns a 4-tuple (coset_reps, gens, l, s2) where coset_reps is
a list of coset representatives of the subgroup, gens a list of
generators, l and s2 are list that corresponds to the action of
the matrix and
on the cosets.
EXAMPLES:
sage: G = ArithmeticSubgroup_Permutation(S2='(1,2)(3,4)',S3='(1,2,3)')
sage: reps,gens,l,s=G.todd_coxeter_l_s2()
sage: reps
[
[1 0] [ 0 -1] [1 2] [1 1]
[0 1], [ 1 0], [0 1], [0 1]
]
sage: gens
[
[1 3] [ 1 0] [ 2 -3]
[0 1], [-1 1], [ 1 -1]
]
sage: l
[3, 1, 0, 2]
sage: s
[1, 0, 3, 2]
sage: S2 = SL2Z([0,-1,1,0])
sage: L = SL2Z([1,1,0,1])
sage: reps[0] == SL2Z([1,0,0,1])
True
sage: all(reps[i]*S2*~reps[s[i]] in G for i in xrange(4))
True
sage: all(reps[i]*L*~reps[l[i]] in G for i in xrange(4))
True
Returns a 4-tuple (coset_reps, gens, s2, s3) where coset_reps
are coset representatives of the subgroup, gens is a list of
generators, s2 and s3 are the action of the matrices and
on the list of cosets.
The so called Todd-Coxeter algorithm is a general method for coset enumeration for a subgroup of a group given by generators and relations.
EXAMPLES:
sage: G = ArithmeticSubgroup_Permutation(S2='(1,2)(3,4)',S3='(1,2,3)')
sage: G.genus()
0
sage: reps,gens,s2,s3=G.todd_coxeter_s2_s3()
sage: g1,g2 = gens
sage: g1 in G and g2 in G
True
sage: g1
[-1 0]
[ 1 -1]
sage: g2
[-1 3]
[-1 2]
sage: S2 = SL2Z([0,-1,1,0])
sage: S3 = SL2Z([0,1,-1,1])
sage: reps[0] == SL2Z([1,0,0,1])
True
sage: all(reps[i]*S2*~reps[s2[i]] in G for i in xrange(4))
True
sage: all(reps[i]*S3*~reps[s3[i]] in G for i in xrange(4))
True
An example of an index 10 arithmetic subgroup studied by Tim Hsu.
EXAMPLE:
sage: import sage.modular.arithgroup.arithgroup_perm as ap
sage: ap.HsuExample10()
Arithmetic subgroup with permutations of right cosets
S2=(1,2)(3,4)(5,6)(7,8)(9,10)
S3=(1,8,3)(2,4,6)(5,7,10)
L=(1,4)(2,5,9,10,8)(3,7,6)
R=(1,7,9,10,6)(2,3)(4,5,8)
An example of an index 18 arithmetic subgroup studied by Tim Hsu.
EXAMPLE:
sage: import sage.modular.arithgroup.arithgroup_perm as ap
sage: ap.HsuExample18()
Arithmetic subgroup with permutations of right cosets
S2=(1,5)(2,11)(3,10)(4,15)(6,18)(7,12)(8,14)(9,16)(13,17)
S3=(1,7,11)(2,18,5)(3,9,15)(4,14,10)(6,17,12)(8,13,16)
L=(1,2)(3,4)(5,6,7)(8,9,10)(11,12,13,14,15,16,17,18)
R=(1,12,18)(2,6,13,9,4,8,17,7)(3,16,14)(5,11)(10,15)
Bases: sage.modular.arithgroup.arithgroup_perm.ArithmeticSubgroup_Permutation_class
TESTS:
sage: G = ArithmeticSubgroup_Permutation(S2="(1,2,3,4)",S3="(1,3)(2,4)")
sage: G
Arithmetic subgroup with permutations of right cosets
S2=(1,2,3,4)
S3=(1,3)(2,4)
L=(1,2,3,4)
R=(1,4,3,2)
sage: TestSuite(G).run()
Return the list of cusp widths.
INPUT:
exp - boolean (default: False) - if True, return a dictionnary with keys the possible widths and with values the number of cusp with that width.
EXAMPLES:
sage: G = Gamma1(5).as_permutation_group()
sage: G.cusp_widths()
[1, 1, 5, 5]
sage: G.cusp_widths(exp=True)
{1: 2, 5: 2}
Test whether self is a congruence group, i.e.~whether or not it
contains the subgroup for some
.
For odd groups, we first test whether the group generated by and
is congruence, and then use a theorem of Kiming, Schuett and
Verrill [KSV11], which shows that an odd subgroup is congruence if and
only if it contains
where
is twice its generalised
level (the least common multiple of its cusp widths). We can therefore
proceed by calculating the index of the subgroup of
generated by the gens of self, and checking whether or not it
has the same index as self.
EXAMPLES:
sage: GammaH(11,[4]).as_permutation_group().is_congruence()
True
The following example (taken from [KSV11]) shows that it may be the
case that G is not congruence, even if its image in
is congruence:
sage: S2 = "(1,3,13,15)(2,4,14,16)(5,7,17,19)(6,10,18,22)(8,12,20,24)(9,11,21,23)"
sage: S3 = "(1,14,15,13,2,3)(4,5,6,16,17,18)(7,8,9,19,20,21)(10,11,12,22,23,24)"
sage: G = ArithmeticSubgroup_Permutation(S2=S2,S3=S3)
sage: G.is_congruence()
False
sage: G.to_even_subgroup().is_congruence()
True
In fact G is a lifting to of the group
:
sage: G.to_even_subgroup() == Gamma0(6)
True
Test whether the group is even.
EXAMPLES:
sage: G = ArithmeticSubgroup_Permutation(S2="(1,6,4,3)(2,7,5,8)",S3="(1,2,3,4,5,6)(7,8)")
sage: G.is_even()
False
Test whether the group is odd.
EXAMPLES:
sage: G = ArithmeticSubgroup_Permutation(S2="(1,6,4,3)(2,7,5,8)",S3="(1,2,3,4,5,6)(7,8)")
sage: G.is_odd()
True
Returns the number of cusps.
EXAMPLES:
sage: G = ArithmeticSubgroup_Permutation(S2="(1,2,3,4)",S3="(1,3)(2,4)")
sage: G.ncusps()
1
sage: G = Gamma1(3).as_permutation_group()
sage: G.ncusps()
2
Return the number of irregular cusps.
The cusps are associated to cycles of the permutations or
.
The irregular cusps are the one which are stabilised by
.
EXAMPLES:
sage: S2 = "(1,3,2,4)(5,7,6,8)(9,11,10,12)"
sage: S3 = "(1,3,5,2,4,6)(7,9,11,8,10,12)"
sage: G = ArithmeticSubgroup_Permutation(S2=S2,S3=S3)
sage: G.nirregcusps()
3
Return the number of regular cusps of the group.
The cusps are associated to cycles of or
. The irregular cusps
correspond to the ones which are not stabilised by
.
EXAMPLES:
sage: G = Gamma1(3).as_permutation_group()
sage: G.nregcusps()
2
Return the number of elliptic points of order 2.
EXAMPLES:
sage: G = ArithmeticSubgroup_Permutation(S2="(1,2,3,4)",S3="(1,3)(2,4)")
sage: G.nu2()
0
sage: G = Gamma1(2).as_permutation_group()
sage: G.nu2()
1
Return the number of elliptic points of order 3.
EXAMPLES:
sage: G = ArithmeticSubgroup_Permutation(S2="(1,2,3,4)",S3="(1,3)(2,4)")
sage: G.nu3()
2
sage: G = Gamma1(3).as_permutation_group()
sage: G.nu3()
1
Returns the group with added in it.
EXAMPLES:
sage: G = Gamma1(3).as_permutation_group()
sage: G.to_even_subgroup()
Arithmetic subgroup with permutations of right cosets
S2=(1,3)(2,4)
S3=(1,2,3)
L=(2,3,4)
R=(1,4,2)
sage: H = ArithmeticSubgroup_Permutation(S2 = '(1,4,11,14)(2,7,12,17)(3,5,13,15)(6,9,16,19)(8,10,18,20)', S3 = '(1,2,3,11,12,13)(4,5,6,14,15,16)(7,8,9,17,18,19)(10,20)')
sage: G = H.to_even_subgroup(relabel=False); G
Arithmetic subgroup with permutations of right cosets
S2=(1,4)(2,7)(3,5)(6,9)(8,10)
S3=(1,2,3)(4,5,6)(7,8,9)
L=(1,5)(2,4,9,10,8)(3,7,6)
R=(1,7,10,8,6)(2,5,9)(3,4)
sage: H.is_subgroup(G)
True
Given a word in the format output by sl2z_word_problem(), convert it back
into an element of .
EXAMPLES:
sage: from sage.modular.arithgroup.arithgroup_perm import eval_sl2z_word
sage: eval_sl2z_word([(0, 1), (1, -1), (0, 0), (1, 3), (0, 2), (1, 9), (0, -1)])
[ 66 -59]
[ 47 -42]
Given an element of , express it as a word in the generators L =
[1,1,0,1] and R = [1,0,1,1].
The return format is a list of pairs (a,b), where a = 0 or 1 denoting L or R respectively, and b is an integer exponent.
See also the function eval_sl2z_word().
EXAMPLES:
sage: from sage.modular.arithgroup.arithgroup_perm import eval_sl2z_word, sl2z_word_problem
sage: m = SL2Z([1,0,0,1])
sage: eval_sl2z_word(sl2z_word_problem(m)) == m
True
sage: m = SL2Z([0,-1,1,0])
sage: eval_sl2z_word(sl2z_word_problem(m)) == m
True
sage: m = SL2Z([7,8,-50,-57])
sage: eval_sl2z_word(sl2z_word_problem(m)) == m
True
Given a word as a list of 2-tuples (index,power) and permutations
p1 and p2 return the product of p1 and p2 that corresponds
to w.
EXAMPLES:
sage: import sage.modular.arithgroup.arithgroup_perm as ap
sage: S2 = SymmetricGroup(4)
sage: p1 = S2('(1,2)(3,4)')
sage: p2 = S2('(1,2,3,4)')
sage: ap.word_of_perms([(1,1),(0,1)], p1, p2) == p2 * p1
True
sage: ap.word_of_perms([(0,1),(1,1)], p1, p2) == p1 * p2
True