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

`‣ PrincipalCongruenceSubgroup` ( N ) | ( operation ) |

Returns the principal congruence subgroup \(\Gamma(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

`‣ CongruenceSubgroupGamma0` ( N ) | ( operation ) |

Returns the congruence subgroup \(\Gamma_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)>

`‣ CongruenceSubgroupGammaUpper0` ( N ) | ( operation ) |

Returns the congruence subgroup \(\Gamma^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)>

`‣ CongruenceSubgroupGamma1` ( N ) | ( operation ) |

Returns the congruence subgroup \(\Gamma_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)>

`‣ CongruenceSubgroupGammaUpper1` ( N ) | ( operation ) |

Returns the congruence subgroup \(\Gamma^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)>

`‣ 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)>

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.

`‣ 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

`‣ 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.

`‣ 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.

`‣ 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.

`‣ 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.

`‣ 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

The next three attributes store key properties of congruence subgroups.

`‣ 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

`‣ 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

`‣ 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)> ]

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

`‣ 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

`‣ 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

`‣ 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 ]

`‣ 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

generated by GAPDoc2HTML