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:
  
    Example  
    
    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).
  
    Example  
    
    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).
  
    Example  
    
    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).
  
    Example  
    
    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).
  
    Example  
    
    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).
  
    Example  
    
    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.
  
    Example  
    
    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.
  
    Example  
    
    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.
  
    Example  
    
    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.
  
    Example  
    
    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(ℤ).
  
    Example  
    
    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.
  
    Example  
    
    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.
  
    Example  
    
    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.
  
    Example  
    
    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.
  
    Example  
    
    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.
  
    Example  
    
    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(ℤ).
  
    Example  
    
    gap> Index(G_2,G_8);
    32