We describe efficient algorithms for working with subgroups of . Operations discussed include join and meet, congruence testing, congruence closure, subgroup testing, cusp enumeration, supergroup lattice, generators and coset enumeration, and constructing a group from a list of generators.

Introduction

The set of linear fractional transformations of the form

(1)

known as Möbius transformations, has several interesting properties. First, the composition of functions of this form is still of the same form, as

Since the coefficients appearing in the composition are exactly those of the product of the two matrices and , it is most convenient to represent transformations of the form (1) by the matrix . A matrix and any nonzero scalar multiple of itself represent the same Möbius transformation, so we can consider only matrices with determinant 1 without loss of generality. Since the product of two matrices with determinant 1 also has determinant 1, such a set of matrices (or Möbius transformations) forms a group, where the group operation is matrix multiplication (or composition). If we further restrict the coefficients , , , and in (1) to be integers, the resulting group is known as . Now, if the matrix is in , then is also in and represents the same Möbius transformation. For this reason, we consider , known as the modular group, which is with each matrix identified with its negative. That is,

It is possible to show that every transformation in the modular group can be obtained as a combination of the two fundamental transformations

with corresponding matrices and . Another way of stating this fact is that is generated by and .

For example, the matrix may be obtained as the product .

The modular group is important because of the existence of modular functions, which are functions that have simple transformation laws under the action of the modular group. A prototypical modular function is the modular discriminant function, which may be defined for by

Since this product has zeros at every rational number, the real axis becomes a natural boundary of the domain of . Using the methods of analysis, it is possible to show that

(2)

for every matrix in the modular group. Two observations are in order concerning the transformation formula (2). First, as

we see that the transformed value of still has a positive imaginary part, so it still lies in the domain of . Second, the values of where ranges over the whole upper half-plane are related to the values of where is restricted to the region shaded blue here.

This region is known as the fundamental domain for . This is because the transformations and can be used to bring any point in into this region, and no two points inside it differ by a Möbius transformation in . The transformation pairs the left edge with the right edge, while the transformation pairs the arc from to with the arc from to .

Subgroups of the Modular Group

In the theory of modular functions one often wants to know what transformations leave a given function unchanged. For example,

will not be unchanged by all the transformations in , since the numerator does not have a transformation formula under all elements of . However, if is in and is divisible by 5, then

Thus, we are naturally led to the subgroup of given by

The package ModularSubgroups.m addresses the computational problem of working with such subgroups of the modular group. However, only certain subgroups of can be identified by congruence conditions on their entries, as is the case with . Such subgroups are called congruence subgroups and are discussed more later. For this reason, we need a better way to represent subgroups. The key to this lies in the matrices and . Since and generate
, and are also generators. However, it can be shown that is the free product of and ; that is, every matrix in can be written uniquely as a word in and as long as no two consecutive ’s appear and no three consecutive ’s appear in the word. This last condition is necessary because of the relations , where (the identity matrix) should be thought of as the empty word.

A subgroup of the modular group is said to have finite index (in ) if can be written as a disjoint union

of left cosets , where the left coset is defined as . In this way, the group is partitioned into several “copies” of , and the number of copies of that fit inside is called the index . If is a finite index subgroup of with index and left cosets (with a distinguished coset ), the matrices and permute the left cosets when acting by multiplication on the left; that is, we have equations

where and should be viewed as some permutations of the set , that is, elements of the symmetric group .

This identification of the matrices and as permutations gives rise to the permutation representation of , which we use to represent any subgroup of with finite index. Specifically, a subgroup is identified by: (1) its index ; (2) the permutation ; and (3) the permutation . The permutations and are not arbitrary. The following two conditions are necessary and sufficient for a given to appear as the representation of some group .

(1) in , where is the identity in . This condition arises from the fact that as matrices, we have .

(2) and generate a transitive subgroup of , or equivalently, the Schreier cosets graph discussed later is connected. This condition arises because the matrix sends the coset to the coset , hence the action of on the left cosets “connects” all of the cosets together.

If these two conditions are satisfied, the group may be identified as , where the condition needs to be evaluated after thinking of as a permutation by converting and into their corresponding permutations.

Since our representation of by two permutations and involves an arbitrary ordering of the nontrivial cosets , two different representations and represent the same group precisely when there is a relabeling of the indices in the permutations of that simultaneously converts into and into . For, example the two representations

represent the same group, as the relabeling converts to .

Another important combinatorial object attached to a subgroup of finite index is the Farey symbol for , as described in [1]. This symbol directly encodes a fundamental domain for as well as the edge-pairing matrices for this fundamental domain. Equivalently, it encodes independent generators for . However, since the equivalence of two representations of by two different Farey symbols is not as straightforward to detect, the permutation representation as described was chosen for the underlying representation for .

Congruence Subgroups

A subgroup of is called a congruence subgroup if it contains the principal congruence subgroup of level ,

for some natural number . If this is the case, we can describe as those matrices whose entries satisfy certain congruences modulo . For example, two families of congruence subgroups are and , which are defined as

Recently in [2], Hsu gave a simple test for determining if a given subgroup of is a congruence subgroup, based on a presentation for . This algorithm is implemented here and generalized to compute the congruence closure of a subgroup , which is the smallest congruence subgroup that contains .

Schreier Cosets Graphs

The Schreier cosets graph of is of fundamental importance to several of the algorithms in the package. Given a subgroup with index and permutations and , the Schreier coset graph is the connected graph with vertices and labeled edges

Such a graph has the property of being folded. A graph is said to be folded if every vertex has at most one edge of a given orientation and label incident with it. If there is a vertex with two or more edges of the same label and orientation, then the graph is said to be unfolded. One property of the Schreier cosets graph is that the subgroup of the modular group consists of all words in and such that, when starting at vertex 1, the path that follows word must terminate at vertex 1. For example, take the subgroup with the following Schreier cosets graph.

The word , which corresponds to the matrix

is in as the path traced out by is given by ( must be read right to left since we are dealing with left cosets). Since the graph is folded, the process of tracing a path given by a word in and is deterministic. The group corresponding to this Schreier cosets graph turns out to be a congruence subgroup, and its defining congruences are given in Example 1.

Examples

All of these examples were tested in Mathematica 10.

Set the directory to be able to load the package and then evaluate the Needs.

Subgroups of the modular group are maintained in the container , and the names of the functions that operate on these groups start with a lower case “m” in order to avoid possible conflicts with built-in symbols. The matrices mS, mO, mT, mR of the package are set as follows.

Example 1: Describing Congruence Subgroups

Here is the group from the section on Schreier cosets graphs. The permutations are listed so that and , where and are the last two arguments of the mGroup container.

This group turns out to be a congruence subgroup of level 3, and it consists of those matrices that are congruent modulo 3 to one of the following matrices.

So, for example, the group has the description

Example 2: Congruence Subgroups from Generating Sets

The group generated by and is of finite index only for . Similarly, the group generated by and is of finite index only for .

Example 3: Subgroups of Index 7

There are two conjugacy classes of congruence subgroups of index 7, which we define here by
their generators.

In the printed form of the group :

1. is the index of in .
2. is the genus of the compact surface .
3. is the number of cusps of , namely, the size of .
4. is the number of fixed points of order 2 of in .
5. is the number of fixed points of order 3 of in .

These numbers are related by .

They are indeed not conjugate.

The intersection of these two groups turns out to have index 28, while the group generated by these two groups turns out to be the full modular group.

A fundamental domain may be obtained with mDomain.

The edge pairings for this fundamental domain are given in the Farey symbol. Edges between two rational numbers with the same integer label are paired together, while edges with the label ● or ○ are paired with themselves.

The matrices returned by mGenerators are the matrices responsible for pairing the edges in this way.

Example 4: Congruence Subgroups

The congruence closure of a subgroup is the smallest congruence subgroup that contains . We first start with the congruence subgroup of index 7 from the previous example and a non-congruence subgroup of index 9.

Its congruence closure is the theta subgroup.

One can also compute the congruence closure of a group by joining it with the principal congruence subgroup of the same level, but the package uses a much more efficient method. Membership in the groups , , and can be tested with , , and , respectively. The function mFromMember constructs the internal representation of the group given the group’s membership function.

We also have the following property, since g itself is congruence.

Next, we compute the congruence closure for the group given in Example 1.1 of [2]. It turns out to be the full modular group.

Example 5: Generators for

First get the principal congruence subgroup of level 5, which has index 60.

Generators may be computed quickly from this permutation representation, and we can also efficiently reconstruct the group from a list of generators.

Example 6: Supergroup Lattice

We will graph the supergroup lattice for the principal congruence subgroup of level 4. The mSupergroups function is used to make the supergroup lattice. The index of each group (in )
is displayed in the lattice, and the actual group is displayed as a tooltip. Every subgroup of whose matrices can be described by congruence conditions modulo 4 appears somewhere on this lattice.

Example 7: Cusps for a Subgroup

If is a subgroup of the modular group, then every matrix in acts on (the set of rational numbers with included) and partitions into equivalence classes. We say that two rational numbers and are equivalent under if there is an element of that sends to . The set of equivalence classes of under the action of is known as the cusps for , and there are finitely many cusps if has finite index in the modular group. The width of a cusp with respect to is defined to be the index of the stabilizer of inside the stabilizer of .

Let g and h be the subgroups

Here is a list of inequivalent cusps of h and their widths.

Here we reduce a list of random cusps to one of these four. The frequency of each cusp in the list should be proportional to its width.

The intersection of g and h may be computed.

Of course, the implementation in the package is more efficient.

Example 8: Non-congruence Subgroups from Caranica

If denotes the total number of subgroups of the modular group of index , then with so that it is possible to show that

and that

Since the radius of convergence of the power series is zero, this differential equation must be treated formally as a recurrence relation for the coefficients of . See Section 1 of [3] for details.

Caranica [4, Table 3.1] has computed the conjugacy classes of non-congruence subgroups of index 9. However, this table incorrectly claims that there are 11 conjugacy classes. In fact, there are 108 non-congruence subgroups of index 9 and 12 conjugacy classes. Vidal [5] has given a formula for the generating function of the total number of conjugacy classes of subgroups (congruence or not) of a given index.

Fortunately, the Farey symbols for the claimed groups are provided by Caranica, so we can recover the source of the error. First we verify that there are indeed 11 conjugacy classes of non-congruence subgroups in the table.

This is the group that is missing from the table.

Example 9: Fundamental Domains and Univalent Functions

The Mathematica built-in function KleinInvariantJ is invariant under and takes each complex value exactly once inside a fundamental domain for . A plot of this function and an outline of its fundamental domain are shown.

The upper half-plane, which is parameterized by , has been mapped into the unit disk, which is parameterized by , by the relation .

The hue of the color plotted at a point in the disk is the argument of the complex number , where is the point in the upper half-plane corresponding to .

Similarly, the built-in function DedekindEta can be used to construct such a function for , which is a congruence subgroup of of index 3. A plot of this function and a fundamental domain for are shown next.

Here is a similar construction for . This plots the fundamental domain for in the half-plane.

In the disk, such a region becomes a diamond shape. A univalent function on must be invariant under the generators of ; that is, , and such a function is provided by the built-in function ModularLambda.

In this case, the zero of occurs on this diamond where the colors coalesce. In the previous example, the zeros of are not visible in this way because they occur on the boundary of the
disk.

A Description of the Algorithms

Many operations on subgroups of the modular group depend on operations on graphs. Several of the algorithms used here encounter unfolded graphs, and we use the efficient folding algorithm described in [6] to implement Stallings’s folding process, which converts any graph to a folded graph.

As described in the introduction, it is straightforward to convert a group described by the permutations and to the Schreier cosets graph. In order to reverse this procedure, it is necessary that each edge labeled either have the same initial and terminal vertex or be part of a three-cycle. Similarly, each edge labeled needs to occur in either a loop or a two-cycle. All of the graphs used here have this property. However, when building a group from a list of a generators, we may encounter a folded graph in which some vertex does not have valence four. Such graphs do not correspond to subgroups of of finite index. Let us illustrate the folding procedure on the following graph.

Such a graph represents the subgroup that is generated by the two words and , since, except for the trivial cycles induced by the relations , these are the only cycles in the graph. Whenever there are two edges and incident at the same vertex with the same orientation and label, causing the graph to be unfolded, the edge may be deleted and the vertex may be merged with without changing the subgroup represented by the graph. The progression of the graph folding procedure shown is left to right, top to bottom, with the edges to be deleted shown between graphs.

The subgroup of represented by the final folded graph has index three and is determined by the permutations and . This is also known as the theta subgroup. The reader is urged to work through the folding process for the group generated by and to see that it does not have finite index in . The starting graph is shown here.

It is useful to have a notion of a standard representation (in terms of the permutations and ) of a group whereby two groups are the same if and only if their permutations and are identical. This can be accomplished by visiting the coset first (denoted by the index 1 in the permutations). Once we have visited a coset , we then recursively visit the coset (assuming this has not been visited yet), and once this trip has returned to the coset , we visit the coset (also assuming this coset has not been visited yet). The standard labels for the indices for the nontrivial cosets may then be determined by the order in which that coset was visited.

In the case of testing a matrix for membership in a group , write as a word in and , then set and check if . Specifically, for a given matrix whose entries in the left column are non-negative, multiply on the left by the matrices

until the left column contains a zero. The variable holds the current coset, so every time is multiplied by , for example, needs to be updated to .

Given the membership function on matrices for a group, we construct the group coset by coset. Assume that has index at least three in . If , start with the four cosets ; otherwise, start with the three cosets . Proceed by adding either one or three cosets to at a time. If is such that:

1. and , then add the coset to .
2. and , then add the cosets , , to .

Where there is no such coset satisfying either of these conditions, we have found all of the cosets of . A naive implementation of this procedure would have worst-case running time , where is the index of the resulting group. The worst-case running time may be reduced to by keeping track of which cosets actually need to be checked.

We may compute coset representatives, generators, and a Farey symbol in operations for a subgroup of index . This works as follows. Let be the graph corresponding to a subgroup of index . First, the graph is cut into a tree so that the coset labeled is given by the resulting unique path from the vertex 1 to the vertex . Any time a cut is made or a fixed point is encountered, the corresponding matrix is added to the list of generators. Finally, after the cosets and generators are computed and the cuts have been recorded, the Farey symbol is computed by a clockwise traversal of the tree.

The cusps of a given subgroup are also important. The action of on the upper half-plane is given by

and this action extends to . The equivalence classes of under the action of , namely , are finite, and we may choose a representative for each one as follows. The stabilizer of in is generated by (or ). Therefore, any two cusps (say and for ) are equivalent under whenever there is an integer such that ; that is, and belong to the same cycle of the permutation . The width of a cusp can then be defined as the length of the cycle (of ) that contains the coset .

Joining and intersecting two groups is surprisingly simple. To compute the group that is generated by and , we can form the graph for . Then, for each generator of , merge the vertices in corresponding to the cosets and . This will in general result in a unfolded graph, which we can then fold and convert back to a permutation representation. In order to compute the permutation representations for the intersection of and , first find the orbit of under the action of and in terms of cosets of the form . A permutation representation of may then be obtained by the action of and on the cosets in this orbit of .

It is also straightforward to check if two groups are the same or conjugate, or if one group is contained in another. To test if two groups and are the same, we employ a strategy similar to the process for standardizing the representation. The cosets of and are visited simultaneously, starting with the pair . If we are currently visiting the pair , then we visit the pairs and as described in the standardization process. If the two paths ever become out of sync, that is, if cosets are visited in a different order, then we know the groups are not the same; otherwise the two paths will return back to and we know that and are the same. Checking if and are conjugate can be accomplished by the same procedure. We need to check if the path stays in sync when starting at some pair for .

The congruence functions use the list of relations of Hsu [2]. Recall that the congruence closure of a group is the smallest congruence subgroup that contains . We compute the congruence closure of as follows. Hsu gives a list of relations that are satisfied if and only if is a congruence subgroup. Let be the list of the permutations where is a relation in Hsu’s list. If contains a non-identity permutation , this represents an obstacle to being a congruence subgroup. Let denote the level of , which is defined as the order of the permutation . As it is known that contains , the set of relations for is also satisfied by . Let be any permutation in and an index of any coset in . Since must act trivially on the cosets of and is a subgroup of , the group obtained from by merging cosets and must also be contained in . Therefore, merging the cosets and of for all and must give .

Conclusion

We have described an efficient package for manipulating and constructing subgroups of the modular group. It is hoped that this will further interest in these groups and facilitate research dealing with these subgroups.

Acknowledgments

The author would like to thank Junxian Li of the University of Illinois at Urbana-Champaign for many helpful discussions on improvements and corrections to initial implementations of the algorithms.

References

[1]	C. A. Kurth and L. Long, “Computations with Finite Index Subgroups of Using Farey Symbols.” arxiv.org/abs/0710.1835.
[2]	T. Hsu, “Identifying Congruence Subgroups of the Modular Group,” Proceedings of the American Mathematical Society, 124(5), 1996 pp. 1351–1359. www.ams.org/journals/ proc/1996-124-05/S0002-9939-96-03496-X/S0002-9939-96-03496-X.pdf.
[3]	A. Lubotzky, “Counting Finite Index Subgroups,” London Mathematical Society Lecture Note Series 212: Groups ’93 Galway/St Andrews, Vol. 2 (C. M. Campbell, E. F. Robertson, T. C. Hurley, S. J. Tobin, and J. J. Ward, eds.), Cambridge: Cambridge University Press, 1995 pp. 368–404.
[4]	C. C. Caranica, “Algorithms Related to Subgroups of the Modular Group,” Ph.D. thesis, Louisiana State University, 2009. etd.lsu.edu/docs/available/etd-07092009-200839/unrestricted/Caranica_diss.pdf.
[5]	S. A. Vidal, “Sur la classification et le dénombrement des sous-groupes du groupe modulaire et de leurs classes de conjugaison,” Publications IRMA, 66(II), 2006 pp. 1–35. Preprint: arxiv.org/abs/math.CO/0702223.
[6]	N. W. M. Touikant, “A Fast Algorithm for Stallings’ Folding Process,” International Journal of Algebra and Computation, 16(6), 2006 pp. 1031–1045. doi:10.1142/S0218196706003396.
D. Schultz, “Manipulating Subgroups of the Modular Group,” The Mathematica Journal, 2016. dx.doi.org/doi:10.3888/tmj.18-4.

About the Author

Daniel Schultz is a postdoctoral researcher at Pennsylvania State University who is interested in modular functions and automorphic forms in general.

Daniel Schultz
Pennsylvania State University Department of Mathematics
University Park
State College, PA 16802
dps23@psu.edu