Goto Chapter: Top 1 2 3 4 5 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

2 Construction of congruence subgroups
 2.1 Construction of congruence subgroups
 2.2 Properties of congruence subgroups
 2.3 Attributes of congruence subgroups
 2.4 Operations for congruence subgroups

2 Construction of congruence subgroups

The package Congruence provides functions to construct several types of canonical congruence subgroups in SL_2(ℤ), and also intersections of a finite number of such subgroups. They will return a matrix group in the category IsCongruenceSubgroup, which is defined as a subcategory of IsMatrixGroup, and which will have a distinguishing property determining whether it is a congruence subgroup of one of the canonical types, or an intersection of such congruence subgroups (if it can not be reduced to one of the canonical congruence subgroups). To start to work with the package, you need first to load it as follows:


gap> LoadPackage("congruence");
-----------------------------------------------------------------------------
Loading  Congruence 1.1.0 (Congruence subgroups of SL(2,Integers))
by Ann Dooms (http://homepages.vub.ac.be/~andooms),
   Eric Jespers (http://homepages.vub.ac.be/~efjesper),
   Alexander Konovalov (http://www.cs.st-andrews.ac.uk/~alexk/), and
   Helena Verrill (http://www.math.lsu.edu/~verrill).
-----------------------------------------------------------------------------
true

2.1 Construction of congruence subgroups

2.1-1 PrincipalCongruenceSubgroup
‣ PrincipalCongruenceSubgroup( N )( operation )

Returns the principal congruence subgroup Γ(N) of level N in SL_2(ℤ).

This subgroup consists of all matrices of the form


                         [1+N*a    N*b]
                         [  N*c  1+N*d]

where a,b,c,d are integers. The returned group will have the property IsPrincipalCongruenceSubgroup (2.2-1).


gap> G_8:=PrincipalCongruenceSubgroup(8);
<principal congruence subgroup of level 8 in SL_2(Z)>
gap> IsGroup(G_8);
true
gap> IsMatrixGroup(G_8);
true
gap> DimensionOfMatrixGroup(G_8);
2
gap> MultiplicativeNeutralElement(G_8);
[ [ 1, 0 ], [ 0, 1 ] ]
gap> One(G);
[ [ 1, 0 ], [ 0, 1 ] ]
gap> [[1,2],[3,4]] in G_8;
false
gap> [[1,8],[8,65]] in G_8;
true
gap> SL_2:=SL(2,Integers);
SL(2,Integers)
gap> IsSubgroup(SL_2,G_8);
true

2.1-2 CongruenceSubgroupGamma0
‣ CongruenceSubgroupGamma0( N )( operation )

Returns the congruence subgroup Γ_0(N) of level N in SL_2(ℤ).

This subgroup consists of all matrices of the form


                         [a    b]
                         [N*c  d]

where a,b,c,d are integers. The returned group will have the property IsCongruenceSubgroupGamma0 (2.2-2).


gap> G0_4:=CongruenceSubgroupGamma0(4);
<congruence subgroup CongruenceSubgroupGamma_0(4) in SL_2(Z)>

2.1-3 CongruenceSubgroupGammaUpper0
‣ CongruenceSubgroupGammaUpper0( N )( operation )

Returns the congruence subgroup Γ^0(N) of level N in SL_2(ℤ).

This subgroup consists of all matrices of the form


                         [a  N*b]
                         [c    d]

where a,b,c,d are integers. The returned group will have the property IsCongruenceSubgroupGammaUpper0 (2.2-3).


gap> GU0_2:=CongruenceSubgroupGammaUpper0(2);
<congruence subgroup CongruenceSubgroupGamma^0(2) in SL_2(Z)>

2.1-4 CongruenceSubgroupGamma1
‣ CongruenceSubgroupGamma1( N )( operation )

Returns the congruence subgroup Γ_1(N) of level N in SL_2(ℤ).

This subgroup consists of all matrices of the form


                         [1+N*a      b]
                         [  N*c  1+N*d]

where a,b,c,d are integers. The returned group will have the property IsCongruenceSubgroupGamma1 (2.2-4).


gap> G1_6:=CongruenceSubgroupGamma1(6);
<congruence subgroup CongruenceSubgroupGamma_1(6) in SL_2(Z)>

2.1-5 CongruenceSubgroupGammaUpper1
‣ CongruenceSubgroupGammaUpper1( N )( operation )

Returns the congruence subgroup Γ^1(N) of level N in SL_2(ℤ).

This subgroup consists of all matrices of the form


                         [1+N*a    N*b]
                         [    c  1+N*d]

where a,b,c,d are integers. The returned group will have the property IsCongruenceSubgroupGammaUpper1 (2.2-5).


gap> GU1_4:=CongruenceSubgroupGammaUpper1(4);
<congruence subgroup CongruenceSubgroupGamma^1(4) in SL_2(Z)>

2.1-6 IntersectionOfCongruenceSubgroups
‣ IntersectionOfCongruenceSubgroups( G1, G2, ..., GN )( function )
‣ Intersection( G1, G2, ..., GN )( function )

Returns the intersection of its arguments, which can be congruence subgroups or their intersections, constructed with the same function. It is not necessary for the user to use IntersectionOfCongruenceSubgroups, since it will be called automatically from Intersection.

The returned group will have the property IsIntersectionOfCongruenceSubgroups (2.2-6).

The list of congruence subgroups that form the intersection can be obtained using DefiningCongruenceSubgroups (2.3-3). Note, that when the intersection appears to be one of the canonical congruence subgroups, the package will recognize this and will return a canonical subgroup of the appropriate type.


gap> I:=IntersectionOfCongruenceSubgroups(G0_4,GU1_4);
<principal congruence subgroup of level 4 in SL_2(Z)>
gap> J:=IntersectionOfCongruenceSubgroups(G0_4,G1_6);
<intersection of congruence subgroups of resulting level 12 in SL_2(Z)>

2.2 Properties of congruence subgroups

A congruence subgroup constructed by one of the five above listed functions will have certain properties determining its type. These properties will be used for method selection by Congruence algorithms. Note that they do not provide an actual test whether a certain matrix group is a congruence subgroup or not.

2.2-1 IsPrincipalCongruenceSubgroup
‣ IsPrincipalCongruenceSubgroup( G )( property )

For a congruence subgroup G in the category IsCongruenceSubgroup, returns true if G was constructed by PrincipalCongruenceSubgroup (2.1-1) (or reduced to one as a result of an intersection) and returns false otherwise.


gap> IsPrincipalCongruenceSubgroup(G_8);
true
gap> IsPrincipalCongruenceSubgroup(G0_4);
false
gap> IsPrincipalCongruenceSubgroup(I);
true

2.2-2 IsCongruenceSubgroupGamma0
‣ IsCongruenceSubgroupGamma0( G )( property )

For a congruence subgroup G in the category IsCongruenceSubgroup, returns true if G was constructed by CongruenceSubgroupGamma0 (2.1-2) (or reduced to one as a result of an intersection) and returns false otherwise.

2.2-3 IsCongruenceSubgroupGammaUpper0
‣ IsCongruenceSubgroupGammaUpper0( G )( property )

For a congruence subgroup G in the category IsCongruenceSubgroup, returns true if G was constructed by CongruenceSubgroupGammaUpper0 (2.1-3) (or reduced to one as a result of an intersection) and returns false otherwise.

2.2-4 IsCongruenceSubgroupGamma1
‣ IsCongruenceSubgroupGamma1( G )( property )

For a congruence subgroup G in the category IsCongruenceSubgroup, returns true if G was constructed by CongruenceSubgroupGamma1 (2.1-4) (or reduced to one as a result of an intersection) and returns false otherwise.

2.2-5 IsCongruenceSubgroupGammaUpper1
‣ IsCongruenceSubgroupGammaUpper1( G )( property )

For a congruence subgroup G in the category IsCongruenceSubgroup, returns true if G was constructed by CongruenceSubgroupGammaUpper1 (2.1-5) (or reduced to one as a result of an intersection) and returns false otherwise.

2.2-6 IsIntersectionOfCongruenceSubgroups
‣ IsIntersectionOfCongruenceSubgroups( G )( property )

For a congruence subgroup G in the category IsCongruenceSubgroup, returns true if G was constructed by IntersectionOfCongruenceSubgroups (2.1-6) and without being one of the canonical congruence subgroups, otherwise it returns false.


gap> IsIntersectionOfCongruenceSubgroups(I);
false
gap> IsIntersectionOfCongruenceSubgroups(J);
true

2.3 Attributes of congruence subgroups

The next three attributes store key properties of congruence subgroups.

2.3-1 LevelOfCongruenceSubgroup
‣ LevelOfCongruenceSubgroup( G )( attribute )

Stores the level of the congruence subgroup G. The (arithmetic) level of a congruence subgroup G is the smallest positive number N such that G contains the principal congruence subgroup of level N.


gap> LevelOfCongruenceSubgroup(G_8);
8
gap> LevelOfCongruenceSubgroup(G1_6);
6
gap> LevelOfCongruenceSubgroup(I);
4
gap> LevelOfCongruenceSubgroup(J);
12

2.3-2 IndexInSL2Z
‣ IndexInSL2Z( G )( attribute )

Stores the index of the congruence subgroup G in SL_2(ℤ).


gap> IndexInSL2Z(G_8);
384
gap> G_2:=PrincipalCongruenceSubgroup(2);
<principal congruence subgroup of level 2 in SL_2(Z)>
gap> IndexInSL2Z(G_2);
12
gap> IndexInSL2Z(GU1_4);
12

2.3-3 DefiningCongruenceSubgroups
‣ DefiningCongruenceSubgroups( G )( attribute )

Returns: list of congruence subgroups

For an intersection of congruence subgroups, returns the list of congruence subgroups forming this intersection. For a canonical congruence subgroup returns a list of length one containing that subgroup.


gap> DefiningCongruenceSubgroups(J);
[ <congruence subgroup CongruenceSubgroupGamma_0(4) in SL_2(Z)>,
  <congruence subgroup CongruenceSubgroupGamma_1(6) in SL_2(Z)> ]
gap> P:=PrincipalCongruenceSubgroup(6);
<principal congruence subgroup of level 6 in SL_2(Z)>
gap> Q:=PrincipalCongruenceSubgroup(10); 
<principal congruence subgroup of level 10 in SL_2(Z)>
gap> G:=IntersectionOfCongruenceSubgroups(Q,P);  
<principal congruence subgroup of level 30 in SL_2(Z)>
gap> DefiningCongruenceSubgroups(G);
[ <principal congruence subgroup of level 30 in SL_2(Z)> ] 

2.4 Operations for congruence subgroups

Congruence installs several special methods for operations already available in GAP.

2.4-1 Random
‣ Random( G )( operation )
‣ Random( G, m )( operation )

For a congruence subgroup G in the category IsCongruenceSubgroup, returns random element. In the two-argument form, the second parameter will control the absolute value of randomly selected entries of the matrix.


gap> Random(G_2) in G_2;
true
gap> Random(G_8,2) in G_8;
true

2.4-2 \in
‣ \in( m, G )( operation )

It is easy to implement the membership test for congruence subgroups and their intersections.


gap> \in([ [ 21, 10 ], [ 2, 1 ] ],G_2);
true
gap> \in([ [ 21, 10 ], [ 2, 1 ] ],G_8);
false

2.4-3 CanEasilyCompareCongruenceSubgroups
‣ CanEasilyCompareCongruenceSubgroups( G, H )( operation )

For congruence subgroups G,H in the category IsCongruenceSubgroup, returns true if G and H are of the same type listed in PrincipalCongruenceSubgroup (2.1-1) --> CongruenceSubgroupGammaUpper1 (2.1-5) and have the same LevelOfCongruenceSubgroup (2.3-1) or if G and H are of the type IntersectionOfCongruenceSubgroups (2.1-6) and the groups from DefiningCongruenceSubgroups (2.3-3) are in one to one correspondence, otherwise it returns false.


gap> CanEasilyCompareCongruenceSubgroups(G_8,I);
false

2.4-4 IsSubset
‣ IsSubset( G, H )( operation )

Congruence provides methods for IsSubset for congruence subgroups. IsSubset returns true if H is a subset of G. These methods make it possible to use IsSubgroup operation for congruence subgroups.


gap> IsSubset(G_2,G_8);
true
gap> IsSubset(G_8,G_2);
false
gap> f:=[PrincipalCongruenceSubgroup,CongruenceSubgroupGamma1,CongruenceSubgroupGammaUpper1,CongruenceSubgroupGamma0,CongruenceSubgroupGammaUpper0];;
gap> g1:=List(f, t -> t(2));;
gap> g2:=List(f, t -> t(4));;
gap> for g in g2 do
> Print( List( g1, x -> IsSubgroup(x,g) ), "\n");
> od;
[ true, true, true, true, true ]
[ false, true, false, true, false ]
[ false, false, true, false, true ]
[ false, false, false, true, false ]
[ false, false, false, false, true ]

2.4-5 Index
‣ Index( G, H )( operation )

If a congruence subgroup H is a subgroup of a congruence subgroup G, we can easily compute the index of H in G, since we know the index of both subgroups in SL_2(ℤ).


gap> Index(G_2,G_8);
32

 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 Bib Ind

generated by GAPDoc2HTML