write a proof to this problem:
The special linear group $\mathrm{SL}(2, \mathbb{Z})$ over $\mathbb{Z}$ is the multiplicative group consisting of all $2 \times 2$ matrices with entries in $\mathbb{Z}$ and determinant $1$; that is,
			\[
			\mathrm{SL}(2, \mathbb{Z}) = \left\{ \begin{pmatrix} a & b \\ c & d \end{pmatrix} : a, b, c, d \in \mathbb{Z} \text{ and } ad - bc = 1 \right\}.
			\]
			Let $G$ be the quotient group $\mathrm{SL}(2, \mathbb{Z})/\{\pm I\}$, where $I$ is the $2 \times 2$ identity matrix. Find with proof the number of subgroups of $G$ of index $m$ for each $m \in \{2, 3, 4, 5, 6\}$.
where the answer is {1, 2, 2, 1, 8} repsectivey, the elements of OEIS sequence A121350 (reference as 7). also make sure to include that i used this paper:
arXiv:2307.01826v1 [math.NT] 4 Jul 2023
ON COMPUTING FINITE INDEX SUBGROUPS OF PSL2(Z)
NICOLAS MAYORGA URUBURU, ARIEL PACETTI, AND LEANDRO VENDRAMIN ´
Abstract. We present a method to compute finite index subgroups of PSL2(Z). Our strategy follows
Kulkarni’s ideas, the main contribution being a recursive method to compute bivalent trees as well as their
automorphism group. As a concrete application, we compute all subgroups of index up to 20. We then use
this database to produce tables with several arithmetical properties.
1. Introduction
Let PSL2(Z) be the modular group, obtained as the quotient of the set of all two by two matrices with
integral entries of determinant 1 modulo the subgroup {± (
1 0
0 1 )}. It is a classical problem that of determining
all subgroups of PSL2(Z) of a given finite index. In a remarkable article Newman ([13]) computed the number
of subgroups of index up to a hundred (including the asymptotic behavior of the counting function). The
group SL2(Z) acts on the set of subgroups by conjugation, and it is also a natural problem that of determining
the subgroups (or their number) up to SL2(Z)-equivalence. Similarly, the group GL2(Z) acts on PSL2(Z)
so the same sort of questions for GL2(Z)-equivalence classes can be considered. In [16] the author gave a
method to compute the number of SL2(Z)-equivalence classes, whose sequence corresponds to the integer
sequence A121350 (see https://oeis.org/A121350).
From a computational point of view, it is challenging to actually compute tables of subgroups of PSL2(Z)
(modulo conjugation). To our knowledge, it was Kulkarni (in [9]) the first one who actually proposed an
algorithm to compute them. In the aforementioned article (in Appendix 1) he even gives a list of subgroups
of index up to 6 (for these small indexes, there are only a few of them). Let us give some details on Kulkarni’s
approach, which also shows the relevance of the problem.
Let H∗ = {z ∈ C | Im z > 0}∪ {∞}∪Q denote the extended complex upper half plane. The group SL2(Z)
acts on H∗ by M¨oebius transformations. Since the matrix  −1 0
0 −1

acts trivially, we get a well defined action
of the modular group PSL2(Z). The typical fundamental domain T for the action of PSL2(Z) on H∗
is the
hyperbolic triangle with vertices ρ = exp(2πi/6), ρ
2 and ∞. The half-plane H has an extra transformation
ι (as a real variety) given by ι(z) = −z. This allows to extend the action of PSL2(Z) on H∗
to an action of
PGL2(Z) on H∗ given by

a b
c d
· z =
(
az+b
cz+d
if ad − bc = 1,
az+b
cz+d
if ad − bc = −1.
The hyperbolic triangle F with vertices ρ, i and ∞ (see Figure 1) is a fundamental domain for the action of
PGL2(Z) on H∗
. Clearly T = F ∪ι(F). Following [9] in the present article we use the following terminology.
Definition 1.1. The points of H in the orbit of i (resp. in the orbit of ρ) by the action of GL2(Z) are called
even or red vertices (resp. odd or blue vertices). The points in the orbit of SL2(Z) · ∞ are called cusps.
The PGL2(Z)-translates of the triangle F provide a tessellation of H. The hyperbolic geodesic of F joining
i with ∞ (resp. joining ρ with ∞) is called an even edge (resp. odd edge) and so is all of its translates by
GL2(Z). The hyperbolic geodesic of F joining i with ρ is of finite length. Its GL2(Z)-translates are called
f-edges.
2010 Mathematics Subject Classification. 11F06, 05C85.
Key words and phrases. Bi-valent graphs, Subgroups of the modular group.
N.M.U. was partially supported by a Conicet grant, AP was partially supported by the Portuguese Foundation for Science and
Technology (FCT) within project UIDB/04106/2020 (CIDMA), L.V. was supported by project OZR3762 of Vrije Universiteit
Brussel.

ρ
i
F
f
Figure 1. Fundamental domain for PGL2(Z).
Let ∆ be a finite index subgroup of PSL2(Z). Then a fundamental domain for its action is given by the
union of translates of T . A key idea introduced by Kulkarni in [9] was to replace the fundamental domain
T by
(1) D = F ∪ ι(S · F),
where S =

0 −1
1 0 
. In this way, any fundamental domain obtained as the union of translates of D will have
no f-edges on its border. Furthermore, if the fundamental domain has nice properties, the set of f-edges
inside the fundamental domain form a graph with an orientation on it. It is expected that the subgroup ∆
could be recover (up to conjugation) from the graph. This allowed Kulkarni to give three different ways to
describe a finite index subgroup:
(1) Via the graph of f-edges on the quotient ∆\H, what Kulkarni called a bipartite cuboid graph.
(2) Via removing from the whole graph of f-edges those vertices having valence 2 and making some cuts
to the graph in order to get a tree, what Kulkarni called a tree diagram.
(3) Via listing the cusps appearing on a “special” fundamental domain, and listing how the paths going
throw them are glued together. This was called a Farey symbol by Kulkarni.
For theoretical purposes, the first approach is the best one, as on the one hand it contains all the information needed to recover the subgroup and on the other one it is in bijection with the set conjugacy classes
of subgroups. However, the second one is better for computational purposes (which is the goal of the present
article) since the tree has a smaller number of edges.
In [1, §3.1] the authors gave an alternative method to describe a finite-index subgroup of PSL2(Z),
following the ideas introduced by Millington in [12]. Roughly speaking, if ∆ is a subgroup of PSL2(Z) of
index d, then PSL2(Z) acts by left multiplication on right coset representatives of ∆\PSL2(Z) (in particular
the action of each element of PSL2(Z) is given by a permutation of Sd). To describe the action completely
it is enough to determine the permutations attached to a set of generators of PSL2(Z), for example the
permutation attached the matrix S introduced before and the one attached to the matrix T = ( 1 1
0 1 ) (the
usual translation matrix). This way of representing a subgroup is also called a “passport” in the literature.
The method was extended in [15], where a table containing the permutations attached to all subgroups (up
to GL2(Z)-equivalence) of index up to 12 (and up to index 18 in electronic format) is given. Stromberg’s
computations were extended in different ways (including computing tables of modular forms) in [3] and [4].
The purpose of the present article is to provide an algorithm to compute finite index subgroups (up
to SL2(Z) and GL2(Z) equivalence) via computing tree diagrams. A bi-valent tree is a tree whose set of
valences has two elements. Our main contribution (of interest on its own) is to provide a recursive algorithm
to construct bi-valent trees. Along the way we prove interesting properties of the automorphism group of a
bi-valent tree (see Theorem 3.8) which is crucial to speed up the algorithms used to computed tree diagrams.
Since our final goal is to provide tables of finite index subgroups of PSL2(Z) (up to both SL2(Z) and
GL2(Z) equivalence) we also provide the needed algorithms to construct the subgroup attached to a tree
diagram (as well as its passport representation). Most of these algorithms are already part of the literature.
Our humble contribution is to include missing details (that appeared while writing the code) regarding

“boundary issues” as well as correcting a few mistakes. Of particular interest is the algorithm to construct
the generalized Farey symbol attached to a tree diagram (see Theorem 4.7). Although such an algorithm
plays a crucial role in [9], somehow there is no description of such an algorithm in the article, so we take the
opportunity to present it here, and prove its correctness.
Our algorithms are implemented in the computer software GAP [6]. The code can be downloaded from
https://github.com/vendramin/subgroups with DOI 10.5281/zenodo.8113635. The GitHub repository
contains some precomputed data as well as a tutorial (with examples) on how to use the code. The package
depends on the packages: Yags for graph theory, [5] for some calculations related to generalized Farey
symbols, and HomAlgTools for speeding up recursive functions.
The article is organized as follows: Section 2 contains a quick review of Kulkarni’s main results used
in the present article. It includes some definitions (used during the article) as well as the correspondence
between subgroups and some particular fundamental domains (called special polygons). This result justifies
our computation of tree diagrams. Section 3 contains the main recursive algorithm to compute bi-valent
trees as well as their automorphism group. Although our trees have valence {1, 3}, the proven results hold
for any tree with valence set {1, n}, n being arbitrary. Of particular interest is Theorem 3.8, which describes
the automorphism group of a bi-valent tree as a semi-direct product of two other ones. The section includes
algorithms used to add an orientation and a coloring on the set of external vertices to a bi-valent tree.
Section 4 contains the definition of a generalized Farey symbol (g.F.s. for short), which consists of the
set of cusps of a special polygon. As previously mentioned, a given g.F.s. together with the gluing of the
sides allow to give an alternative description of a finite index subgroup of PSL2(Z). This section contains
an algorithm to compute a g.F.s. attached to a tree diagram (Theorem 4.7), providing a way to go from
the second description to the third one. A tree diagram together with a g.F.s. is called a Kulkarni diagram.
The same section contains different algorithms to, given a Kulkarni diagram corresponding to a subgroup
∆, compute arithmetic information of the quotient curve ∆\H∗
(like cusp representatives and width of the
cusps, genus, ramification points, etc) as well as information of the subgroup ∆ itself (including a reduction
algorithm needed to solve the word problem, and finding a set of coset representatives).
Section 5 contains the definition of a passport and algorithms to compute the passport attached to a
Kulkarni diagram (to compare with other tables in the literature). At last, Section 6 contains some tables
and interesting facts that can be deduced from the data we computed.
It should be clear to the reader how Kulkarni’s article crucially influenced our work, so we strongly
recommend they to look at the article [9] which contains more details on the correspondences between tree
diagrams, Farey symbols and bipartite cuboid graphs.
2. A quick guide to Kulkarni’s approach
Recall the following definition from [9, §4.1].
Definition 2.1. A bipartite cuboid graph is a finite graph whose vertex set is divided into two disjoint
subsets V0 (the red ones) and V1 (the blue ones) such that
(1) every vertex in V0 has valence 1 or 2,
(2) every vertex in V1 has valence 1 or 3,
(3) there is a prescribed cyclic order on the edges incident at each vertex of valence 3 in V1,
(4) every edge joins a vertex in V0 with a vertex in V1.
Let ∆ be a finite index subgroup of PSL2(Z). The quotient H∗\∆ is a compact oriented real surface, with
a tessellation given by the translates of D. The graph of f-edges of the surface is an example of a cuboid
graph, where V0 corresponds to the red vertices (i.e. the translates of i) while V1 corresponds to the blue
vertices (the translates of ρ).
We will only use bipartite cuboid graphs twice on the present article: once in Example 2.8, to prove that
two non-isomorphic tree diagrams provide conjugated subgroups and also while computing the generalized
Farey symbol attached to a tree diagram. In contrast to a bipartite cuboid graph, the notion of a tree diagram
appears while working with a fundamental domain (a special polygon) for the quotient. The advantage of
this approach is that we do not need to glue its edges together, it is enough to store which/how edges get
identified. In this way we can work with a tree instead of a graph.
3
Definition 2.2. A special polygon is a convex hyperbolic polygon P whose boundary ∂P is a union of even
and odd edges, satisfying the following properties:
(1) The even edges in ∂P come in pairs, each pair forming a complete hyperbolic geodesic called even
line.
(2) The odd edges in ∂P come in pairs. The edges in each pair meet at an odd vertex, making and
internal angle of 2π
3
.
(3) There exists an involution on the edges of ∂P so that no edge is carried into itself.
(4) The involution sends an odd edge into another odd edge, making an internal angle of 2π
3
between
themselves.
(5) Let e1, e2 be two even edges in ∂P forming a even line. Then either e1 is paired to e2, or else {e1, e2}
form a free side of ∂P and this free side is paired to another such free side of ∂P.
(6) 0 and ∞ are two of the vertices of P.
Remark 2.3. Note that any special polygon has a canonical orientation induced from the “counterclockwise”
orientation of H. The action of SL2(Z) on a special polygon preserves the orientation (since it corresponds to
a holomorphic function). However, the action of the matrix  −1 0
0 1 
has the effect of reversing the orientation
of our special polygon. The choice of the opposite orientation corresponds to the action by ι on H. The
choice of the counterclockwise orientation or its inverse accounts for the difference between equivalence
classes of subgroups up to SL2(Z) conjugation or up to GL2(Z) conjugation. This will prove crucial later
(see Remark 2.6).
Theorem 2.4 (Kulkarni). A special polygon is a fundamental domain for the subgroup ∆ generated by
the side-pairing transformations and these transformations form an independent set of generators for ∆.
Conversely every subgroup ∆ of finite index in PSL2(Z) admits a special polygon as a fundamental domain.
Proof. See page 1055 of [9].
A special polygon is the union of translates of D, so as explained before, we can look at its tree of f-edges.
Properties (4) and (5) of a special polygon imply that the end points of the f-edges tree will be points that
are one of:
• the intersection of two odd edges, or
• the intersection of two even edges paired together, or
• the intersection of two even edges forming a free side.
Any vertex of the tree has valence 1 (corresponding to an end point), 2 or 3. To avoid redundant
information on the tree, one can remove the vertices having valence 2, obtaining the so called tree diagrams.
A great advantage of the tree diagram is that its number of vertices tends to be much smaller than that
of the original bipartite cuboid graph. Remark 2.3 implies that the vertices with valence 3 have a natural
orientation.
Definition 2.5. A tree diagram is a tree with at least one edge such that
(1) all internal vertices are of valence 3,
(2) there is a prescribed cyclic order on the edges incident at each internal vertex (orientation),
(3) the terminal vertices are partitioned into two possibly empty subsets R and B (red and blue vertices),
(4) there is an involution ι on R.
By Bv(n, 3) we will denote the set of tree diagrams with n internal vertices.
Example 2.6. It is not true in general that if T is a tree diagram, and we consider the tree diagram
where the orientation at all internal vertices are inverted (by considering the inverse of the permutation)
we get isomorphic tree diagrams. For example, the following planar (with the anti-clockwise orientation)
tree diagrams in Bv(2, 3) are not isomorphic. They correspond to two subgroups of PSL2(Z) which are not
isomorphic via conjugation under SL2(Z), but are isomorphic under conjugation by GL2(Z).

The way to relate a tree diagram with a bipartite cuboid graph as follows: remove from the bipartite
cuboid graphs all vertices of valence 2 (connecting the remaining endings) and make some cuts to the graph
so that it becomes a tree (see [9, §4.4] for details). Conversely, given a tree diagram, color blue all of its
internal vertices (i.e. they are odd vertices) and keep the coloring of the tree diagram on the external vertices.
If two consecutive vertices of the tree are blue, enlarge the tree by adding one extra vertex and paint it with
red color. Finally, we need to glue together the identified external vertices: identify two external vertices v
and w in R if ι(v) = w, where ι is the involution of R. It is not hard to verify that the resulting graph is a
bipartite cuboid graph.
Remark 2.7. Following Kulkarni’s notation, the way we encode the involution ι is as follows: if v is a vertex
fixed by ι then we just save its color. Otherwise, there exists w 6= v such that ι(v) = w. In this case, we add
a label to each of the two vertices.
As will be described in Section 4, there is a finite-to-one surjective map between the set of tree diagrams
and the set of conjugacy classes of finite index subgroups of PSL2(Z). This map unfortunately is not injective.
Example 2.8. Consider the following tree diagrams with anti-clockwise orientation:
1
1
1
1
These two tree diagrams are not isomorphic: the right tree satisfies that if we move from a red vertex
(following the orientation) we end on a free one, while this is not true for the left one. The bipartite cuboid
graph attached to each one of them are the following:
3 5
4
1 2
3
6
3
′ 4
′
4
′
1
′ 2
′
5
′
6
′
where the edges labeled with the same name are glued together. The two new graphs are isomorphic under
the map

1 2 3 4 5 6
2
′ 1
′ 6
′ 5
′ 3
′ 4
′

.
It is easy to verify that this map preserves orientations.
This is the first example where two non-isomorphic tree diagrams give conjugated subgroups (corresponding to subgroups of index 6). However, it seems that for larger index subgroups (when there are many
free sides) the number of tree diagrams is much larger than the number of SL2(Z)-classes of subgroups, for
example there are 28 tree diagrams corresponding to subgroups of order 9 while only 14 SL2(Z)-equivalence
classes. See the data in Table 6.1.
Remark 2.9. Working with bipartite cuboid graphs has the advantage that their isomorphism classes are
in bijection with SL2(Z) conjugacy classes of subgroups of PSL2(Z), but as already mentioned, has the
disadvantage that it implies working with much larger graphs (which are not trees in general).
Let T be a tree diagram and ι its involution. The set of its external vertices is naturally decomposed as
the disjoint union of three sets
(2) Ve(T) = B ∪ R0 ∪ R1,
where B are the blue vertices, R0 are the red vertices fixed by the involution, and R1 are the red vertices
not fixed by the involution (an even set). Let b = |B| (its cardinality), r = |R0| and f =
|R1|
2
. The main
goal of the next section is to provide an algorithm to compute (equivalence classes of) tree diagrams with
parameters (b, r, f).
5
3. Bi-valent trees
Definition 3.1. A bi-valent tree is a tree satisfying that the valence function on vertices takes at most two
different values.
Clearly the valence function on any tree with at least three vertices must take at least two different values,
hence the valence function on a bi-valent tree with at least three vertices takes precisely two different values.
Definition 3.2. Let T be any bi-valent tree. The set of external vertices (resp. internal vertices) that we
denote by Ve (resp. Vi) is the set of vertices of T having valence 1 (resp. having valence > 1).
Denote by Bv(m, n) the set of bi-valent trees (up to isomorphism) with valences set {1, n} made of m
internal vertices.
Example 3.3. There is a unique bi-valent tree T in Bv(2, 3) given by the graph shown in Figure 2.
4
1 2
5
3 6
Figure 2. Unique tree in Bv(2, 3).
Its adjacency matrix equals


0 1 1 1 0 0
1 0 0 0 1 1
1 0 0 0 0 0
1 0 0 0 0 0
0 1 0 0 0 0
0 1 0 0 0 0


,
where the red block is precisely the adjacency matrix of the internal vertices.
Lemma 3.4. Let T be a bi-valent tree, satisfying that the valence of any vertex belongs to the set {1, n} for
some n > 1. Then
|Ve| = (n − 2)|Vi
| + 2.
Proof. By induction on the size |Vi
|. If |Vi
| = 1 then there must be n external vertices (all joined to the
unique internal one), hence the result. Suppose that m = |Vi
| > 1 and that the result holds for all bi-valent
trees with at most m−1 internal vertices. Let v, w be internal vertices joined by an edge (such a pair always
exists because m > 1). Cut the tree into two disjoint trees T1, T2, by removing the edge (v, w) and add to
each of the new trees an external edge joining v (respectively w). Now each tree is again a bi-valent tree,
say with r and s internal vertices (so r + s = m). The inductive hypothesis implies that
|Ve(T1)| = |Vi(T1)|(n − 2) + 2 and |Ve(T2)| = |Vi(T2)|(n − 2) + 2.
But |Vi(T )| = |Vi(T1)| + |Vi(T2)| and |Ve(T )| = |Ve(T1)| + |Ve(T2)| − 2 (because we add a new external vertex
to both T1 and T2), hence the result.
The lemma implies that if T ∈ Bv(m, n) then its number of vertices equals
|V (T )| = (n − 1)m + 2.
3.1. Automorphisms of bi-valent trees. Let T be a bi-valent tree, and let Ti = (Vi
, Ei) be the sub-tree
of internal vertices, namely the tree whose set of vertices Vi = Vi(T ) is the set of internal vertices of T , and
whose set of edges Ei
is the set of all edges of T between internal vertices. Given an automorphism σ of
Aut(T ), it makes sense to restrict σ to the subgraph Ti
, giving a sequence
(3) 1 −→ Aute −→ Aut(T )
Res
−→ Aut(Ti),
6
where Res is the restriction map (a group morphism) and Aute is (by definition) its kernel. It turns out that
the sequence (3) is exact and furthermore it splits. Before proving these facts we need a characterization of
the subgroup Aute.
Recall that given two vertices of a tree, there exists a unique reduced path joining them, so there is a
natural definition of distance between vertices. For latter purposes, if the bi-valent tree T has at least three
vertices, we denote by
Φ: Ve → Vi
,
the function which assigns to an external vertex v the unique internal vertex which is at distance one from
it. Let v ∈ Ve be an external vertex, and let Two(v) be the set of external vertices at distance at most 2
from v. Since v ∈ Two(v), Two(v) 6= ∅. Consider the following function
m: Ve → [1, . . . , n], m(v) = | Two(v)|.
For 1 ≤ i ≤ n, let
V
(i)
e
:= {v ∈ Ve | m(v) = i}.
Then we can decompose the set of external vertices as the disjoint union of the sets V
(i)
e . For i ∈ [1, . . . , n],
define
r(i) = max{|S| : S ⊆ V
(i)
e
and d(v, w) 6= 2 for all v, w ∈ S}.
Lemma 3.5. There is a non-canonical group isomorphism:
Aute ≃
Yn
i=1
S
r(i)
i
,
where Si denotes the symmetric group on i elements.
Proof. Let σ ∈ Aut(T ) be an automorphism in the kernel of the restriction map and let v ∈ V
(i)
e be an
external vertex. Let w = Φ(v) the the internal vertex adjacent to v. Since σ is in the kernel of the restriction
map, σ(w) = w. Then σ(v) is an external vertex which is also adjacent to w (since any automorphism
preserves distances). In particular, σ(v) ∈ Two(v) ⊆ V
(i)
e and σ induces a permutation of the elements of
Two(v) (a set with i elements). By definition, there exists elements w1, . . . , wr(i) such that the set V
(i)
e can
be written as the disjoint union
V
(i)
e =
rG
(i)
j=1
Two(wj ),
so the action of σ on V
(i)
e can be represented as r(i) permutations on Si
. It is clear that such map is bijective,
i.e. permutations on the (disjoint union of the) sets Two(wj ) induce an automorphism of the tree T which
fixes all internal vertices.
Let T and T
′ be two bi-valent trees in Bv(m, n). For the purposes of the present article, an endomorphism
between T and T
′
is a bijective map between both the set of vertices of T to the set of vertices of T
′ and
between the set of edges of T to the set of edges of T
′
(with the usual compatibility condition). We denote
by End(T, T ′
) the set of all such maps.
For computational purposes, all trees considered will have its set of edges labeled by positive integers.
This provides a total order on the graph’s set of vertices.
Definition 3.6. Let T and T
′ be two trees with a total order on their set of vertices. We say that a map
σ ∈ End(T, T ′
) is 2-ordered if it satisfies that for all pair of external vertices v, w ∈ Ve(T ) at distance two,
it holds that if v < w then σ(v) < σ(w).
Proposition 3.7. Let T and T
′
be bi-valent trees in Bv(m, n) with a total order on its set of vertices. Let
Ti (resp. T
′
i
) be the sub-tree of inner vertices of T (resp. T
′
i
be the sub-tree of inner vertices of T
′
). Let
φ: Ti → T
′
i
be a morphism of graphs. Then φ can be extended in a unique way to a 2-ordered morphism
ψ of End(T, T ′
). Furthermore, if Ti = T
′
i and T = T
′
, the natural map ψ: Aut(Ti) → Aut(T ) is a group
morphism.
Proof. To avoid confusion, we denote by val the valence function on either tree T or T
′ and by vali the valence
function on their sub-tree of internal vertices. Let v ∈ Ve(T ) be any external vertex and let w = Φ(v) be
7
the internal vertex adjacent to it. Since T is bi-valent and w ∈ Ti
, val(w) = n and vali(w) < n (because v
is not in the internal sub-tree). The map φ preserves valences (since it is a morphism from Ti to T
′
i
) hence
vali(φ(w)) < n and so it must be joined to an external edge v
′ of T
′
. The two sets Two(v) and Two(v
′
) have
the same cardinality (equal to n − vali(w)). Clearly any extension of φ must send the elements of Two(v)
to the ones in Two(v
′
), and since both sets are ordered sets, there exists a unique bijection between them
preserving the order, providing the required extension.
When T = T
′ and Ti = T
′
i
, a priori the map ψ: Aut(Ti) → Aut(T ) is only a map of sets, but since the
composition of two 2-ordered maps is a 2-ordered map, and from the uniqueness of the extension, the map
ψ is actually a group morphism.
Theorem 3.8. The sequence
(4) 1 −→ Aute −→ Aut(T )
Res
−→ Aut(Ti) −→ 1,
is exact. Furthermore, the map Res has a section ψ: Aut(Ti) → Aut(T ), hence Aut(T ) ≃ Aute ⋊ Aut(Ti).
Proof. The existence of the section ψ follows from Proposition 3.7, providing the surjectivity of the map
Res. The last statement is a well known fact of split short exact sequences of groups.
Recall that two graphs G1 and G2 are isomorphic if and only if their adjacency matrices are conjugated
by a permutation matrix. The advantage of working with bi-valent trees is that the sub-tree of inner vertices
determines its isomorphism class uniquely (so instead of computing with matrices of size (n − 1)|Vi
| + 2
times (n − 1)|Vi
| + 2, we can work with matrices of size |Vi
| × |Vi
|, where {1, n} is the valuation set). In our
applications (to construct subgroups of PSL2(Z)) n will be 3, so will roughly speaking half the size of our
matrices.
Corollary 3.9. Two bi-valent trees T and T
′ are isomorphic if and only if their internal vertices sub-trees
Ti and T
′
i
are isomorphic.
Proof. Clearly, if φ: T → T
′
is an isomorphism of graphs, its restriction to Ti gives an isomorphism between
Ti and T
′
i
. Conversely, let φ be an isomorphism between Ti and T
′
i
. By Proposition 3.7, the map φ extends
to a morphism between T and T
′
, hence the statement.
3.2. Algorithm to compute bi-valent trees. Let m ≥ 1 and n > 1 be positive integers. Lemma 3.4
implies that any element of Bv(m, n) has m(n − 2) + 2 external vertices. Trees will be represented by their
adjacency matrix, with the convention that on a tree with m(n − 2) + 2 vertices, the first m labels are for
the internal vertices and the remaining ones for the external vertices.
Definition 3.10. Let T ∈ Bv(m, n) and let v ∈ Ve(T ). The extension of T at v, that will be denoted by
Ext(T, v), is the tree obtained by adding n−1 new vertices v1, . . . , vn−1 to the set of vertices of T , and n−1
edges to the set of edges of T , joining v with vi for each i = 1, . . . , n − 1.
It is clear from its definition that if T ∈ Bv(m, n) and v ∈ Ve(T ) then Ext(T, v) ∈ Bv(m + 1, n).
Lemma 3.11. Let T ∈ Bv(m, n) with m > 1. Then there exists v ∈ Ve such that | Two(v)| = n − 1.
Proof. Recall the definition of the map Φ: Ve → Vi
, which assigns to an external vertex v its adjacent internal
vertex. If v ∈ Ve, then | Two(v)| = |Φ
−1
(Φ(v))|. Clearly,
|Ve| =
X
v∈Vi
|Φ
−1
(v)|.
If all sets Two(v) have cardinality smaller than n − 1, then |Φ
−1
(v)| ≤ n − 2, so
|Ve| ≤ (n − 2)|Vi
| < (n − 2)|Vi
| + 2 = |Ve|,
a contradiction.
Theorem 3.12. The following algorithm gives a set of representatives of isomorphism classes of elements
in Bv(m, n) for m ≥ 1, n > 1:
1: if m = 1 then
8
2: return 0 1 ··· 1
1 0 ··· 0
.
.
.
.
.
.
.
.
.
.
.
.
1 0 ··· 0
!
(an (n + 1) × (n + 1) matrix)
3: end if
4: S ← ∅
5: for T ∈ Bv(m − 1, n) do
6: for v ∈ Ve(T ) do
7: S ← S ∪ Ext(T, v)
8: end for
9: end for
10: Remove isomorphic elements from S.
11: return S
Proof. If m = 1, the tree has a unique internal vertex, hence n external ones (joined to the internal vertex).
In particular, there is only one possible tree whose adjacency matrix is the given one.
Assume now that m > 1. If T ∈ Bv(m, n), by Lemma 3.11, there exists a vertex v ∈ Ve(T ) such that
Two(v) has exactly n − 1 elements. Let w = Φ(v) be the internal vertex adjacent to v. Let T
′ be the
tree obtained from T by removing all vertices of Two(v), as well as the edges joining w with elements of
Two(v). Then T
′ ∈ Bv(m − 1, n) and clearly T is isomorphic to Ext(T
′
, w). In particular, T is obtained
from extending an element of Bv(m − 1, n) by an external vertex, so T is isomorphic to an element of S.
Actually, the previous algorithm can be improved since clearly if v, w are two external vertices of a bivalent tree T at distance 2 (or equivalently w ∈ Two(v)), then the extension of T by v is isomorphic to the
extension of T by w. More generally:
Proposition 3.13. Let T ∈ Bv(m, n), let v, w ∈ Ve and let ϕ ∈ Aut(T ) be such that ϕ(v) = w. Then ϕ
induces an isomorphism ϕ˜: Ext(T, v) → Ext(T, w).
Proof. Let H = Ext(T, v) and G = Ext(T, w). Recall that H is obtained by adding n − 1 vertices to T , say
v1, . . . , vn−1, and G is obtained by adding n − 1 vertices to T , say w1, . . . , wn−1. Let ˜ϕ: H → G be the map
given by
ϕ˜(v) = (
ϕ(v), if v ∈ T,
wi
, if v = vi
.
It can easily be verified that ˜ϕ is a well-defined isomorphism between the two trees.
Remark 3.14. In the particular case when w ∈ Two(v), the previous map corresponds precisely to the flip
isomorphism in Aute (the kernel of the restriction map) sending v ↔ w and fixing all other elements.
Define an equivalence relation on Ve by determining that v ∼ w if there exists σ ∈ Aute such that
σ(v) = w. The notation [Ve/∼] will be used to denote any set of representatives for the equivalent classes.
Then we have the following improvement of Theorem 3.12.
Theorem 3.15. The following algorithm gives the elements in Bv(m, n) for m ≥ 1, n > 1, up to isomorphism:
1: if m = 1 then
2: return 0 1 ··· 1
1 0 ··· 0
.
.
.
.
.
.
.
.
.
.
.
.
1 0 ··· 0
!
(an (n + 1) × (n + 1) matrix)
3: end if
4: S ← ∅
5: for T ∈ Bv(m − 1, n) do
6: for v ∈ [Ve(T )/∼] do
7: S ← S ∪ Ext(T, v)
8: end for
9: end for
10: Remove isomorphic elements from S.
11: return S
9
The last step of the algorithm is done by checking whether two elements of S have isomorphic sub-trees of
inner vertices or not.
3.3. Orientations on bi-valent trees. Recall that the set of vertices on a bi-valent tree is the union of
the external vertices Ve (those with valence one) with the internal ones Vi (those having valence greater than
one).
Definition 3.16. An orientation on a bi-valent tree T ∈ Bv(m, n) is an orientation on its set of internal
vertices, i.e. give for each vertex v ∈ Vi an ordering of the set (of size n) consisting of vertices adjacent to v.
The way we represent an orientation algorithmically is by adding to each internal vertex v ∈ Vi an ncycle permutation σv. Thus a bi-valent tree with an orientation is a pair consisting of the adjacency matrix
together with a list of n-cycles indexed by the internal vertices.
Example 3.17. Let T the unique tree (up to isomorphisms) in Bv(2, 3) (from Example 3.3). Since T is
already presented as a planar graph, an orientation is given by the anti-clockwise choice at each vertex (as
mentioned in Remark 2.3), namely
4
1 2
5
3 6
Figure 3. Unique oriented tree in Bv(2, 3) except isomorphism.
We represent this orientation of T by the 3-cycles σ1 = (2, 3, 4) and σ2 = (1, 5, 6).
Definition 3.18. Let T ∈ Bv(m, n) be a bi-valent tree with an orientation and let p = {v1, . . . , vn} be a
path between two external vertices. We say that the path p is well oriented if for each internal vertex vi
in
the path p it holds that σvi
(vi−1) = vi+1 (i.e. the orientation on the vertex v sends the vertex of the path
prior to v to the subsequent one).
Remark 3.19. If n = 3 (i.e. all vertices have valence 1 or 3, which is the case we are really interested in), a
path is well oriented on a vertex vi
if and only if the 3-cycle σvi
equals (vi−1, vi+1, w), where w is the third
vertex adjacent to vi
.
Lemma 3.20. Let T ∈ Bv(m, n) be a bi-valent tree with an orientation. Let v ∈ Ve be an external vertex.
Then there exists a unique w ∈ Ve and a unique reduced and well oriented path p between v and w.
Proof. Let v1 be the internal vertex adjacent to v, and let v2 = σv1
(v), the unique choice so that the path
{v, v1, v2} is well oriented. If v2 is an external vertex, then the path {v, v1, v2} is a well oriented path
between external vertices. Otherwise, let v3 = σv2
(v1) (once again this is the unique choice so that the path
{v, v1, v2, v3} is well oriented) and continue this process. Since the number of vertices is finite, either at some
point we reach an external vertex, or we get a “period”, i.e. there exist i < j such that vi = vj . Since T is a
tree, the only way to get a path starting and ending at the same vertex is that there exists an index t, with
i < t < j such that vt−1 = vt+1, i.e. vt+1 = σvt
(vt−1) = vt−1, which cannot happen since the orientation at
the vertex vt is an n-cycle (so has no fixed points).
Definition 3.21. Let T ∈ Bv(m, n) be an oriented bi-valent tree and let v ∈ Ve be an external vertex. A
vertex w ∈ Ve is to the right of v if there exists a reduced and well oriented path p from v to w. Analogously,
a vertex w ∈ Ve is to the left of v if there exists a reduced and well oriented path from w to v.
In particular, we can define the function
(5) r : Ve → Ve, r(v) = w (vertex to the right of v).
Respectively, we have a function l: Ve → Ve sending v to the vertex to the left of v. Recall our definition of
the map Φ: Ve → Vi which assigns to an external vertex the internal one adjacent to it.
10
Algorithm 3.22. Let T ∈ Bv(m, n) a bi-valent tree with an orientation and v be an external vertex. The following algorithm computes the value of the function r at an external vertex v:
1: a ← v
2: b ← Φ(v)
3: c ← σb(a)
4: while c ∈ Vi do
5: a ← b
6: b ← c
7: c ← σb(a)
8: end while
9: return c
Lemma 3.23. Let T ∈ Bv(m, n) be a bi-valent tree with an orientation, and let v ∈ Ve be an external vertex.
Then
Ve = {r
i
(v) : 0 ≤ i < |Ve|}.
Proof. Let R(v) = {v = v1, v2, . . . , vN } be the set of external vertices to the right of each other (so r(vN ) = v).
Let pi be the reduced and well oriented path between vi and vi+1 for i = 1, . . . , N − 1 and pN the reduced
and well oriented path between vN and v1. Each path is made of edges, so let E˜ be the union of all the
(directed) edges appearing in pi for any 1 ≤ i ≤ N and let V˜ be the set of vertices of elements of E˜. Suppose
we prove that for each v ∈ V˜ which is an internal vertex of V it holds that its n adjacent elements are also
in V˜ , then it must be the case that V˜ = V . The reason is that given any w ∈ V , there is a unique reduced
path joining v to w. By our assumption, all edges of the path are elements of E˜, so w ∈ V˜ as claimed.
To prove the stated property, note that since r(vN ) = v, the compositum pN ◦ · · · ◦ p1 is a path between
v1 and v1, hence is the trivial path, i.e. in this walk there is a complete cancellation of edges. In particular,
if a directed edge lies in E˜, the edge with the opposite direction must also be a member of E˜.
Let b ∈ V˜ be an internal vertex which is part of a path pi
, say {a, b, c} is part of pi
. Since paths are well
oriented, σb(a) = c. The complete cancellation property implies that the (directed) edge (b, a) is part of
some path pj (for 1 ≤ j ≤ N), i.e. {σ
−1
b
(a), b, a} appears in the path pj (because pj is also well oriented).
This proves that if (a, b) ∈ E˜ then (σ
−1
b
(a), b) also belong to E˜. Repeating the argument, (σ
−i
b
(a), b) ∈ E˜
for all 1 ≤ i ≤ n, and since σb is an n-cycle, all these edges are different hence all the vertices adjacent to b
are in V˜ .
Remark 3.24. As mentioned before, we are mainly interested in the case n = 3. The way we compute
representatives for elements in Bv(m, 3) with an orientation is the following: start with a set of isomorphism
classes representatives S for Bv(m, 3) as described in Theorem 3.15. Given an element T ∈ S, compute for
each internal vertex the two possible orientations, and store the resulting bi-valent trees with an orientation.
This produces a set whose number of elements is 2|Vi|
times the size of S.
One can do better by the following observation: if v is an internal vertex adjacent to two external vertices
w1, w2, then the two possible orientations at the vertex v are isomorphic (via the isomorphism sending
w1 ↔ w2 and fixing the other vertices). For this reason, our code just picks one orientation for each internal
vertex adjacent to two exterior ones. This trivial improvement gives in practice a huge saving.
3.4. Coloring external vertices. Recall from Definition 2.5 that a tree diagram is an element T of Bv(m, 3)
(for some m) with an orientation and a particular coloring on the set Ve (the external vertices of T). Let
b, r, f be non-negative integers such that b+r+ 2f = m+ 2 = |Ve|. A coloring on Ve with parameters (b, r, f)
is equivalent to a decomposition of the set Ve as a disjoint union of the form
Ve = B ∪ R0 ∪i Fi
,
(as in (2)) where
(1) the set B has b vertices; its vertices are the blue ones,
(2) the set R0 has r vertices; its vertices are the red ones fixed by the involution ι, and
(3) each set Fi has two red vertices, and the involution ι sends one to the other. The union of the sets
Fi equals R1 in (2). It is a set of size 2f corresponding to the “free sides”.
11
Given T ∈ Bv(m, 3) with an orientation, the way to compute all possible coloring with parameters (b, r, f)
is first to compute all possible subsets B of Ve of size b, and for each choice, compute all possible choices of
the subset R0 of r elements on its complement. The complement S = Ve \ (B ∪ R0) has then 2f-elements.
A way of decomposing the set S as a disjoint union of f subsets of size 2 will be called a 2-partition.
Problem 3.25. Given a set S with 2f elements, how to compute its 2-partitions?
Definition 3.26. Let n be a positive integer. A 2n-tuple (v1, . . . , v2n) of integers is ordered if it satisfies
the following two properties:
• The sub-tuple (v1, v3, . . . , v2n−1) made of the odd entries is ordered.
• For any odd index i, 1 ≤ i ≤ 2n − 1, vi < vi+1.
Similarly, we say that an element of S2f is ordered if so is the 2f-tuple it represents.
Let S = {1, . . . , 2f} and let P denote the set of ordered 2f-tuples made of elements of S. In particular,
the coordinates of elements of S are all different. Let Ψ: P → {2-partitions} be the map given by
(6) Ψ(v1, . . . , v2f ) = {v1, v2} ∪ · · · ∪ {v2f−1, v2f }.
Lemma 3.27. With the previous notation, the map Ψ is bijective.
Proof. Injectivity: let (v1, . . . , v2f ) and (w1, . . . , w2f ) be elements of P such that
Ψ(v1, . . . , v2f ) = Ψ(w1, . . . , w2f ).
Then {{v1, v2}, . . . , {v2f−1, v2f }} = {{w1, w2}, . . . , {w2f−1, w2f }}, say {v1, v2} = {wi
, wi+1} for some odd
index i. The second condition of an ordered tuple implies that v1 < v2 and wi < wi+1 so v1 = wi and
v2 = wi+1. Repeating this argument it follows that the set of odd entries of the first tuple must equal the
set of odd entries of the second one, and since both sets are ordered, the tuples must be the same.
Surjectivity: let S =
Sf
i=1{v2i−1, v2i} be a 2-partition. Clearly we can order each set so that v2i−1 < v2i
for all values of i, and we can also order the sets so that v2i−1 < v2i+1 for all i = 1, . . . , f − 1. By definition,
the tuple (v1, . . . , v2f ) is ordered (so is an element of P).
Proposition 3.28. Let T ∈ Bv(m, 3) be a bi-valent tree with an orientation, and let (b, r, f) be non-negative
integers satisfying that b + r + 2f = m + 2. The following algorithm computes all possible coloring on Ve
with parameters (b, r, f):
1: C ← ∅
2: for B ⊆ Ve, |B| = b do
3: R = Ve \ B
4: for R0 ⊆ R, |R0| = r do
5: R1 = R \ R0
6: for σ ∈ SR1 do
7: if σ is ordered then
8: C ← C ∪ (B, R0, Ψ(σ))
9: end if
10: end for
11: end for
12: end for
13: return C
Let T be a tree diagram coming from a subgroup ∆ of PSL2(Z). Then
(7) [PSL2(Z) : ∆] = 3m + b,
where m is the number of internal vertices of T and b is the number of blue external vertices (see for example
the proposition in page 1078 of [9]). This implies that there are finitely many triples (b, r, f) corresponding
to index d-subgroups of PSL2(Z).
Proposition 3.29. Let d be positive integer. The following algorithm computes all possible triples (b, r, f)
attached to index d subgroups of PSL2(Z):
1: M ← ∅
12
2: for ⌈
d−2
4
⌉ ≤ m ≤ ⌊ d
3
⌋ do
3: b ← d − 3m
4: for j = 0, . . . , ⌊
m−b
2
⌋ + 1 do
5: M ← M ∪ {(b, m + 2 − b − 2j, j)}
6: end for
7: end for
8: return M
Proof. Let ∆ be a subgroup of PSL2(Z) of index d, and let m + 2 be the number of cusps belonging to a
special polygon. The formula d = 3m + b together with the fact that the number of odd vertices cannot
exceed the number of cusps, give the restriction
3m ≤ d ≤ 4m + 2.
This completes the proof.
Combining the different algorithms described in the present section, we can compute given a positive
integer d the set of non-equivalent tree diagrams corresponding to subgroups of index d in PSL2(Z).
4. Tree diagrams, generalized Farey symbols and subgroups
As explained in the introduction, our tree diagram is obtained as the tree of f-edges of a special polygon.
It is a natural question how to recover information of the special polygon that is missing in the tree diagram.
For example, how can we compute it set of cusps? (note that since the special polygon attached to a subgroup
is not unique, the answer will also not be unique).
As explained in [9], the cusps of a special polygon form what is called a generalized Farey symbol, since if
a
b
and c
d
are two consecutive cusps of a special polygon then |ad − bc| = 1.
Definition 4.1. A generalized Farey symbol (g.F.s. for short) is an expression of the form
{−∞, c2, c3, . . . , cn, ∞}
where
(1) c2 and cn are integers, and some ci = 0,
(2) ci =
ai
bi
are rational numbers in their reduced forms and ordered according to their magnitudes, such
that
|aibi+1 − biai+1| = 1, i = 2, 3, . . . , n − 1.
Remark 4.2. Our definition is a little different from Kulkarni’s one. The elements −∞ and ∞ are identified
as points on the polygon, so they correspond to the same point at infinity, but for algorithmic purposes it is
better to represent them as different elements. In particular, we will represent −∞ by the fraction −1
0
and
∞ by 1
0
. This is consistent with the GAP package developed in [5] for computing with generalized Farey
symbols.
Any path between two cusps (members of a g.F.s.) will necessarily go through an end point of a tree
diagram. As suggested in [9], one can add the information of the vertex color to the g.F.s. forming what is
called a Farey symbol.
Definition 4.3. A Farey symbol is an expression of the form:
{−∞
p1
c2
p2
c3
p3
c4
p4
· · ·
· · ·
cn
pn
∞}
where
• {−∞, c2, . . . , cn, ∞} is a g.F.s.,
• each symbol pi
is one of ◦, • or a number label, depending on whether the line on the boundary that
joins ci with ci+1 is even, odd or a free side (in which case the same label is used for its matching
line).
13
Definition 4.4. Let T be a tree diagram, and let v, w be two external vertices next to each other (i.e. one
is to the left or right of the other). Define the bipartite distance between v and w (denoted by bd(v, w))
as the distance between v and w in the tree obtained from T while constructing the bipartite cuboid graph
before identifying the glued vertices.
Lemma 4.5. Let T be a tree diagram, and let v, w be external vertices next to each other. Let d denote the
distance between v and w on the tree T. Then
(8) bd(v, w) = 2d − 2 +



0, if v and w are both even (red),
2, if v and w are both odd (blue),
1, otherwise.
Proof. Since T is a tree, there is a unique reduced path between v and w, and since the distance between
v and w is d, the path goes through d − 1 internal vertices. The bipartite graph is obtained by adding an
extra (red) vertex between each pair of internal vertices, giving an extra d− 2 steps. At last, if either ending
point is odd (i.e. blue), we need to add an extra vertex next to it.
Proposition 4.6. Let T be a tree diagram, and let v, w be external vertices next to each other. Let x = a
b
,
y and z =
c
d
be three consecutive cusps of a special polygon attached to T satisfying that v is between x and
y and that w is between y and z. Then
(9) bd(v, w) = 2|ad − bc| +



0, if v and w are both even (red),
2, if v and w are both odd (blue),
1, otherwise.
Proof. Since everything is invariant under the action of SL2(Z), we can assume that y is the infinity cusp.
Then x and z are both integers (i.e. b = d = 1) with c < a. The tessellation of the upper part of our special
polygon then is one of the following:
• If v and w are both even (red) then it looks like Figure 4A. Note that
2(a − c) = bd(v, w)
(since there are two f-edges between consecutive red vertical lines).
• If v and w are both odd (blue) then the tessellation looks like Figure 4B. Note that 2(a − c) + 2 =
bd(v, w) (since there are two f-edges between consecutive blue vertical lines).
• If v and w have different colors (say v is blue and w is red) then the tessellation looks like Figure 4C.
Note that 2(a − c) + 1 = bd(v, w).
c c + 1 a − 1 a
v · · · w
(A) Case v and w even.
c a
v w
· · ·
(B) Case v and w odd.
c a − 1 a
v
· · · w
(C) Case v odd and w even.
Figure 4. Relation between the distance and the crossed product.

From equations (8) and (9) it follows that if x =
a
b
, y and z =
c
d
are three consecutive cusps with v
between x and y and w between y and z, then
(10) |ad − bc| = d(v, w) − 1.
These relations determine the g.F.s. uniquely (up to SL2(Z)-equivalence).
Theorem 4.7. Let T be a tree diagram, and Ve = {v1, . . . , vm} denote the set of external colored vertices.
Assume that the set Ve is ordered, i.e. vi+1 is to the right of vi for 1 ≤ i ≤ m (with the convention that vm+1 =
v1). The following algorithm computes a g.F.s. attached to T:
14
1: F ← { −1
0
,
0
1
}.
2: if m = 2 then
3: return F ∪ { 1
0
}.
4: else
5: d ← d(v1, v2).
6: F ← F ∪ { 1
d−1
}.
7: for i = 2, . . . , m − 2 do
8: d ← d(vi
, vi+1).
9: α ← Num(F[i + 1]).
10: β ← Den(F[i + 1]).
11: γ ← Num(F[i]).
12: δ ← Den(F[i]).
13: (
y
x ) ←

α −β
γ −δ
−1

1−d
−1

.
14: F ← F ∪
n
x
y
o
.
15: end for
16: end if
17: return F ∪
1
0
	
.
Proof. Up to SL2(Z)-equivalence, we can always assume that the first cusp (to the left of v1) equals ∞ and
the next one equals 0. Since the number of cusps equals the number of external vertices, if there are only
two such cusps, we are done. Suppose that there are at least three cusps, say  −1
0
,
0
1
,
a
b
	
, for some positive
integers a, b. The integers a, b satisfy the relations:
(
| − b + 0 · a| = d(v1, v2) − 1,
0 · b − a = −1,
where the second condition comes from (10). Then a = 1 and b = d(v1, v2) − 1. If we constructed the first
elements of our g.F.s., say  −1
0
,
0
1
, x1, . . . , xi
	
, with xi−1 =
α
β
and xi =
γ
δ
, the next element xi+1 =
X
Y
is a
solution of the system
(
|αY − βX| = d(vi
, vi−1) − 1,
γY − δX = −1.
The fact that xi+1 > xi−1 together with the fact that both the numerators and denominators of xi−1 and
xi+1 are positive integers (because i ≥ 2) imply that |αY − βX| = −αY + βX.
Definition 4.8. A Kulkarni diagram is an object consisting of a tree diagram, together with a choice of a
g.F.s. (denoted by G) attached to it.
The particular choice of the g.F.s. is not important, a different choice will correspond to another subgroup
of PSL2(Z) which is conjugate (by a matrix in SL2(Z)) to it. The elements of G will be called cusps.
4.1. Some important algorithms. The purpose of the present section is to gather together some algorithms to compute with Kulkarni diagrams as well as with its attached subgroup ∆. The most important
algorithms are that of computing generators for ∆, and an algorithm to determine whether an element
g ∈ PSL2(Z) belongs to ∆ or not (crucial to compute the passport attached to a Kulkarni diagram).
To make statements more clear, we will use the following notation: K denotes a Kulkarni diagram,
G = {−∞, c2, . . . , cm+2, ∞} denotes its g.F.s. and ∆ the subgroup attached to it. As proven in [9, Theorem
6.1], the group ∆ has a set of generators {α1, . . . , αm+2} indexed by the elements of G, representing how the
paths in the boundary of a special polygon are glued together.
Algorithm 4.9 (Generator of a cusp). Let K be a kulkarni diagram, Ve = {v1, . . . , vm+2} be its set of (external) colored and ordered vertices and let G be its underlying g.F.s. Given a cusp ck ∈ G, the following algorithm computes the generator corresponding to the cusp ck:
1: a ← Num(ck+1).
2: b ← Den(ck+1).
3: c ← Num(ck).
1
4: d ← Den(ck).
5: if vk is “even” then
6: g ←

ab+cd −c
2−a
2
b
2+d
2 −ab−cd 
.
7: else if vk is “odd” then
8: g ←

ab+cb+cd −c
2−ac−a
2
b
2+bd+d
2 −ab−ad−cd 
;
9: else
10: vk is identified with some vj
11: a
′ ← Num(cj+1).
12: b
′ ← Den(cj+1).
13: c
′ ← Num(cj ).
14: d
′ ← Den(cj ).
15: g ←

a
′
b+c
′d −c
′
c−a
′a
d
′d+b
′
b −ab′−cd′

.
16: end if
17: return g.
Proof. See [9, Theorem 6.1].
Algorithm 4.10 (Cusps representatives). Let K be a Kulkarni diagram and let Ve = {v1, . . . , vm+2} be its
set of (external) colored and ordered vertices. The following algorithm computes the subgroup of Sm+2 whose
orbits correspond to equivalent cusps:
1: S ← ∅.
2: for vk ∈ Ve do
3: if vk is “even” or “odd” then
4: S ← S ∪ {(k, k + 1)}.
5: else
6: vk is identified with some vj
7: S ← S ∪ {(k, j + 1),(k + 1, j)}
8: end if
9: end for
10: return hSi.
Proof. Clear from the gluing of the border paths.
Let C1, . . . , Ct be the cusp representatives of the Kulkarni diagram K, i.e. each set Ci
is made of elements
of G which are in the i-th orbit under the action of the group S computed using Algorithm 4.10.
Problem 4.11. How to compute W(Ci), the width of Ci?
As before, let G = {c1 = −∞, c2, c3, . . . , cm+2, cm+3 = ∞}. Let d: G → Z be the function
(11) d(ci) = |ai−1bi+1 − ai+1bi−1|,
where ai (resp. bi) is the numerator (resp. denominator) of the cusp ci
, and the indices are taken “in a
cyclic order” (i.e. cm+3 = c1).
Algorithm 4.12 (Width of a cusp). Let K be a Kulkarni diagram, Ve = {v1, . . . , vm+2} be its colored and
ordered external vertices and let ci1
, . . . , cir
be the cusps belonging to the class C. The following algorithm
computes the width of C:
1: W ← 0
2: for j = 1, . . . , r do
3: e ← 0
4: if vij−1 is “odd” then
5: e ← e + 1
6: end if
7: if vij
is “odd” then
8: e ← e + 1
9: end if
16
10: W ← W + d(cij
) + e/2
11: end for
12: return W
Proof. See the proposition of page 1079 in [9].
4.2. The word problem. The classical solution to determine whether an element g ∈ PSL2(Z) belongs
to ∆ (the subgroup attached to the Kulkarni diagram K) is to produce a “reduction algorithm” modulo
elements of ∆. Based on the article [11], in [10] (Algorithm, page 13) the authors give such an algorithm.
The problem with the stated method is that it has some “border” conditions which are not clearly stated,
so we take the opportunity to add to it the missing details. If a and b are integers, we denote by quo(a, b)
the cusp a
b
, with the usual convention that −∞ = −1
0
and ∞ = 1
0
.
Theorem 4.13 (Reduction). Let K be a Kulkarni diagram, let ∆ be its attached group, G be its g.F.s. and let
C denote the vector consisting of the coloring on G. Let g ∈ PSL2(Z) be any element. The following algorithm
(Reduction) gives a reduced element in the coset ∆g:
1: N ← |G|
2: if g[2, 1] = 0 then
3: case ← 1
4: else if g[2, 2] = 0 then
5: case ← 2
6: else
7: case ← “generic”
8: end if
9: if case = “generic” then
10: if g[1, 2]/g[2, 2] > g[1, 1]/g[2, 1] then
11: x ← Reduction  −g[1,2] g[1,1]
−g[2,2] g[2,1] 
12: return 
−x[1,2] x[1,1]
−x[2,2] x[2,1] 
13: end if
14: else if case = 1 then
15: if g[1, 1] > 0 then
16: if g[1, 2]/g[2, 2] < 0 then
17: x ← Reduction 
g[1,2] −g[1,1]
g[2,2] −g[2,1] 
18: return 
−x[1,2] x[1,1]
−x[2,2] x[2,1] 
19: end if
20: else
21: if g[1, 2]/g[2, 2] > G[N − 1] then
22: g ← −g
23: else
24: x ← Reduction  −g[1,2] g[1,1]
−g[2,2] g[2,1] 
25: return 
−x[1,2] x[1,1]
−x[2,2] x[2,1] 
26: end if
27: end if
28: else if case = 2 then
29: if g[1, 2] > 0 then
30: if g[1, 1]/g[2, 1] > 0 then
31: x ← Reduction  −g[1,2] g[1,1]
−g[2,2] g[2,1] 
32: return 
−x[1,2] x[1,1]
−x[2,2] x[2,1] 
33: else
34: g ← −g
35: end if
17
36: else
37: if g[1, 1]/g[2, 1] > G[N − 1] then
38: x ← Reduction 
g[1,2] −g[1,1]
g[2,2] −g[2,1] 
39: return 
−x[1,2] x[1,1]
−x[2,2] x[2,1] 
40: end if
41: end if
42: end if
43: a ← quo(g[1, 2], g[2, 2])
44: b ← quo(g[1, 1], g[2, 1])
45: if a ∈ G and b ∈ G then
46: return g
47: else
48: if case = 1 then
49: c ← N
50: else if case = 2 then
51: c ← 2
52: else if b ∈ G then
53: c ← Position(G, b)
54: else
55: l ← G ∪ {b}
56: Sort(l)
57: c ← P osition(l, b)
58: end if
59: end if
60: if not C[c − 1] = “odd” then
61: y ← CuspGenerators(G[c − 1])
62: else
63: m ← (Num(G[c − 1]) + Num(G[c]))/(Den(G[c − 1]) + Den(G[c]))
64: if g[2, 1] = 0 or b > m then
65: y ← CuspGenerator(G[c − 1])
66: else
67: y ← CuspGenerators(G[c − 1])−1
68: end if
69: end if
70: return Reduction(y ∗ g)
Proof. Let g =

a b
c d 
, and let α = quo(a, c), β = quo(b, d) be the cusps corresponding to the first and the
second column. The boundary issues appear when either α or β are the infinity cusp (depending also on
whether they correspond to the −∞ or the ∞ cusp). The first case corresponds to α = ∞, the second case
to β = ∞ and the remaining ones to the “generic” case. In [10] the authors start assuming that β < α
(following their main reference [11]). If we multiply the matrix g on the right by S =

0 1
−1 0 
has the effect
of interchanging α ↔ β, so in case α < β we reduce the matrix gS and multiply the reduced matrix by S to
the right. Multiplication by S sends

a b
c d
→

−b a
−d c
.
This justifies the steps 10 − 12 of the algorithm. In the non-generic cases, this idea might not be enough to
get the “right” reduction step (as explained in [11], the idea behind the algorithm is to shorten a distance).
Suppose that |α| = ∞ (so we are in the first case), then the border condition is the following:
• If α = ∞ and β is positive, we reduce g.
• If α = ∞ and β is negative, we reduce −gS (i.e. instead of considering the pair (∞, β) we work with
(β, −∞)).
• If α = −∞ and β is not larger than all elements of G, we reduce gS (i.e. (β, −∞)).

• If α = −∞ and β is larger than all elements of G, we reduce −g (i.e. (∞, β)).
Similarly, when |β| = ∞ (the second case), the border condition is the following:
• If β = −∞ and α is no larger than all elements of G, we reduce g.
• If β = −∞ and α is larger than all elements of G, we reduce −gS (i.e. we replace the pair (α, −∞)
by (∞, α)).
• If β = ∞ and α < 0, we reduce −g (replacing (α, ∞) by (α, −∞)).
• If β = ∞ and α > 0, we reduce gS (replacing (α, ∞) by (∞, α)).
In all the above cases, we end up in a situation where β < α. The rest of the algorithm mimics the one
presented in [10].
Let g ∈ PSL2(Z) and let g
′ =

a b
c d 
be its reduction (i.e. the output of the last algorithm).
Theorem 4.14. With the previous notation, an element g ∈ PSL2(Z) belongs to ∆ if and only if one of the
following is true:
(1) g
′ = ± (
1 0
0 1 ),
(2) (
b
d
,
a
c
) is a free side paired with (0, ∞),
(3) g
′ = ±

0 −1
1 0 
, and 0 and ∞ are adjacent vertices with an even pairing between them.
Proof. See [11, Theorem 3.2].
The last two results provide a solution to the word problem, namely determining whether an element
α ∈ PSL2(Z) belongs to ∆ or not. We end this section with an algorithm to compute coset representatives
for ∆\PSL2(Z).
Proposition 4.15 (Coset representatives). Let K be a Kulkarni diagram, let ∆ be the attached group and
G be its g.F.s. Let C be the vector made of the coloring of G. The following algorithm gives a complete set
of representatives for ∆\PSL2(Z):
1: N ← |G|
2: T ← (
1 1
0 1 )
3: reps ← ∅
4: for i = 1, . . . , N − 1 do
5: if i = 1 then
6: w ← | Num(G[N − 1]) ∗ Den(G[2]) − Den(G[N − 1]) ∗ Num(G[2])|
7: else
8: w ← | Num(G[i − 1]) ∗ Den(G[i + 1]) − Den(G[i − 1]) ∗ Num(G[i + 1])|
9: end if
10: A ←

− Num(G[i]) Num(G[i+1])
− Den(G[i]) Den(G[i+1]) 
11: if C[i] = “odd” then
12: reps ← reps ∪ {A ∗ T
−1}
13: end if
14: for j ∈ [0, . . . , w − 1] do
15: reps ← reps ∪ {A ∗ T
j}
16: end for
17: end for
18: return reps
Proof. The result is stated in §5.3 of [10], although there is a minor mistake on it (which is why we present
a proof). Let F be the hyperbolic triangle with vertices ρ, i, ∞ as in Figure 1 and let P be the special
polygon attached to T with cusps the g.F.s. of K. If ci =
ai
bi
and ci+1 =
ai+1
bi+1
are two consecutive vertices of
the special polygon attached to K (so they are two consecutive cusps), then the matrix
A =

−ai ai+1
−bi bi+1
sends the line joining ∞ and 0 to the line joining ci to ci+1 (note that the sign in the first column is missing
in [10]). The image under A−1 of P then contains the cusp A−1
· ci−1 (a positive integer) next to ∞ next to

F
T (F)
T
j
(F)
· · ·
(A) Both even.
F · · ·
(B) Left even, right odd.
ιF · · ·
(C) Left odd, right even.
ι(F)
T
w(ιF)
· · ·
(D) Both odd.
Figure 5. Representatives near the infinity cusp.
the cusp 0. If ci−1 =
ai−1
bi−1
, then
A
−1
· ci−1 = w = |ai−1bi+1 − bi−1ai+1|.
Suppose that the line joining ci and ci+1 is even, then the translates of F appearing in A−1P are either of
the form
• T
j
(F ∪ T ι(F)) if the line joining ci to ci−1 is also even (so they are translates of a fundamental
domain for PSL2(Z)), where 0 ≤ j ≤ w − 1 (see Figure 5A),
• T
j
(F ∪ T ι(F)), where 0 ≤ j ≤ w − 1 together with T
wF (see Figure 5B) if the line joining ci to
ci−1 is odd. Note that the “other” part of the fundamental domain will appear while considering
the cusp ci−1, so we do not add it to the list to avoid repetitions.
In this case it is clear that the hyperbolic triangles in the special polygon P containing the infinity point are
the translates by A ∗ T
j of F (together with T ι(F)) for 0 ≤ j ≤ w − 1.
Suppose otherwise that the line joining ci and ci+1 is odd. Then the translates of F appearing in A−1P
belong to one of the following two cases:
• T
−1
(T ι(F)) together with T
j
(F ∪ T ι(F)), where 0 ≤ j ≤ w − 1 (see Figure 5C) if the line joining
ci to ci−1 is even. Note that we must add the first element as it was excluded from the opposite
situation (namely left side even and right one odd).
• T
−1
(T ι(F)) together with T
wF and T
j
(F ∪ T ι(F)) for 0 ≤ j ≤ w − 1 (see Figure 5D). Once again,
to avoid repetitions, we do not add the representative T
wF.
In this second case the hyperbolic triangles in the special polygon P containing the infinity point are the
translates of A ∗ T
j
for −1 ≤ j ≤ w − 1 of F (together with T ι(F)).
4.3. Relation with geometry. From a finite index subgroup ∆ of PSL2(Z) one can construct the algebraic
curve given by the quotient C∆ := ∆\H∗
. Most of the geometric invariants of C∆ can be read from the
Kulkarni diagram K. Define the following quantities:
• e2 = |{“red” vertices fixed by the involution in R}| = |R0|.
• e3 = |{“blue” vertices in Ve}|.
• t = the number of orbits of the group obtained as the output of Algorithm 4.10.
• d = [PSL2(Z) : ∆].
Then in [9, §7] it is proven that the curve C∆ satisfies the following properties:
(1) the number of branch points of H → C∆ of order 2 equals e2,
(2) the number of branch points of H → C∆ of order 3 equals e3,
(3) the number of inequivalent cusps of C∆ equals t, and
(4) the following formula holds:
2g(C∆) + t − 1 =
1
2
|{“red” vertices non-fixed by the involution in R}| = f,
where g(C∆) is the genus of C∆.
In particular, the colored set Ve contains enough information to compute g(C∆).
20
5. Passports and equivalence classes of subgroups
Let G a group and H be a subgroup of index d. Let X = {g1, . . . , gd} be a set of left coset representatives
for G/H. Without loss of generality, we can assume that g1 ∈ H. Then
G =
G
d
i=1
giH.
There is a natural well known homomorphism of groups
θH : G −→ SX ≃ Sd
g 7−→ σg,
where σg is the automorphism of X satisfying that g · giH = σg(gi) · H for all i. The morphism θH has
important properties (see for example [7, Theorems 5.3.1 and 5.3.2]), namely:
• It determines the subgroup H (with our choice it is precisely the group of elements in G fixing g1).
• Any conjugate of H by an element of G equals the group of elements in G fixing gi for some 1 ≤ i ≤ d.
• If we denote by HN the biggest normal subgroup of G contained in H (also known as the normal
core of H in G), then it coincides with Ker(θH).
• If we denote by Σ = Im θH ≤ Sd (that is isomorphic to G/HN ) then Σ acts transitively on Sd.
Recall the following well known result on groups.
Proposition 5.1. Let G be a group, and let H, K be two index d subgroups of G. H is conjugated to K by
an element of G if and only if there exists σ ∈ Sd such that θH = σθKσ
−1
.
Proof. The proof is similar to that of [7, Theorem 5.3.3], although in such statement the author considers
only faithful representations. Start supposing that there exists g ∈ G such that K = gHg−1
. If {h1, . . . , hd}
is a set of left coset representatives for H then {gh1g
−1
, . . . , ghdg
−1} is a set of left coset representatives for
K. Let t ∈ G such that t(hi
· H) = hj · H, then
gtg−1
(ghig
−1
) · K = (ghjg
−1
) · K.
Thus if σ denotes the element of Sd given by left multiplication by g, we get that σθKσ
−1 = θH for the
chosen set of representatives.
Conversely, suppose that there exists σ ∈ Sd such that θH = σθKσ
−1
. Without loss of generality (after
reordering the left coset representatives of K), we can furthermore assume that θH = θK and that the first
coset representative for H lies in H. In particular, if h ∈ H, θH(h)(1) = 1. Then θK(h)(1), so if k1 is the
first left coset representative for K, h(k1 · K) = k1 · K, so h ∈ k1Kk−1
1
and H ⊆ k1Kk−1
1
. Since both groups
have the same index in G, they must be equal.
For a general group G and a subgroup H, it is hard to describe the map θH, but if G has a small (and
known) number of generators, then it is enough to compute the permutation corresponding to each generator.
This is indeed the case for G = PSL2(Z), which is generated by the elements
(12) S =

0 −1
1 0 
, T =

1 1
0 1
.
Then the pair (θH (S), θH(T )) ∈ Sd × Sd up to simultaneous conjugation determines the SL2(Z)-equivalence
class of H. It is also useful to compute the permutation corresponding to the element R = ST (which is the
composition of the two other permutations), as it is an element of order 3 in PSL2(Z) (with together with
S generates the group).
Definition 5.2. A passport is a tuple (σS , σR, σT ) in S
3
d
up to simultaneous conjugation satisfying that
• σ
2
S = 1,
• σ
3
R = 1,
• σSσT = σR,
• Σ = hσS , σRi is transitive.
An important result of Millington ([12, Theorem 1]) implies that the the passport contains a lot of
arithmetic information of the curve H\H.
21
Theorem 5.3. There is a one-to-one correspondence between subgroups H of index d in PSL2(Z) and
equivalence classes of passports (σS , σR, σT ). Furthermore, keeping the previous notation,
(1) e2 and e3 are the number of elements fixed by the permutations σS and σR respectively,
(2) σT has t disjoint cycles (where t equals the number of cusps).
(3) Let d1, . . . , dt be the lengths of the disjoint cycle decomposition of σT (so d =
Pt
i=1 di). Then
{d1, . . . , dt} equals the set (with repetitions) {w(C1), . . . , w(Ct)} of cusp widths.
Using the algorithms described in the previous section, it is easy to give an algorithm to, given a Kulkarni
diagram K together with an element κ ∈ PSL2(Z), compute the permutation σκ: use the algorithm of
Proposition 4.15 to compute a set {g1, . . . , gd} of left coset representative for ∆\PSL2(Z). For each 1 ≤ i ≤ d,
use Theorem 4.14 to determine the unique j in {1, . . . , d} such that g
−1
j κgi belongs to ∆. Then σκ(i) = j.
This algorithm is implemented in our GAP package to compute the passport attached to a Kulkarni diagram.
5.1. Congruence subgroups. Recall the following well known definition.
Definition 5.4. A subgroup ∆ of SL2(Z) is called a congruence subgroup if there exists a positive integer
N such that the group
Γ(N) = a b
c d
∈ SL2(Z) : N | b, N | c, a ≡ 1 (mod N), d ≡ 1 (mod N)

,
is contained in ∆. If such N does not exist, we say that the subgroup is a non-congruence subgroup. The
subgroup Γ(N) is known as the main congruence subgroup of level N.
The main interest in congruence subgroups is that they have many endomorphisms (given by the Hecke
operators). In particular, if ∆ is a congruence subgroup, then the curve C∆ is defined over a cyclotomic
extension, and its Jacobian is isogenous to abelian varieties having very special properties (they are what is
called of GL2-type, see for example [14]).
Definition 5.5. Let K be a Kulkarni diagram and {C1, . . . , Ct} be the set of inequivalent cusps. The
generalized level of K is defined to be the least common multiple of {W(C1), . . . , W(Ct)}.
Proposition 5.6. If ∆ is a congruence subgroup of generalized level N, then Γ(N) ⊆ ∆.
Proof. See [17, Theorem 2].
For completeness, we include the following algorithm due to Hsu for determining whether a group ∆ is a
congruence group or not.
Theorem 5.7. Let ∆ a subgroup of PSL2(Z) and let
σL = θ∆ (( 1 1
0 1 )), σR = θ∆ (( 1 0
1 1 )).
Let N = e·m be the order of L, where e is a power of 2 and m is an odd positive integer. Then the following algorithm determines whether ∆ is a congruence subgroup or not:
1: if e = 1 then
2: if σ
2
Rσ
−(N+1)/2
L = 1 then
3: return true
4: end if
5: else if m = 1 then
6: z ← min{x ∈ N : N | 1 − 5x}
7: τ ← σ
20
L σ
z
Rσ
−4
L
σ
−1
R
8: if [τ, σLσ
−1
R σL] = τ
−2 and [σR, τ] = σ
24
R and (τσ5
RσLσ
−1
R σL)
3 = 1 then
9: return true
10: end if
11: else
12: z ← min{x ∈ N : e | 1 − 5x}
13: c ← Solve (
x ≡ 0 mod e
x ≡ 1 mod m
22
n #K(n) SL2(Z)-classes GL2(Z)-classes
2 1 1 1
3 2 2 2
4 2 2 2
5 1 1 1
6 9 8 8
7 8 6 4
8 8 7 6
9 54 14 12
10 101 27 19
11 80 26 16
12 440 80 63
13 790 133 73
14 770 170 106
15 3184 348 213
16 6540 765 428
17 6582 1002 533
18 28958 2176 1277
19 61072 4682 2410
20 68920 6931 3679
Table 6.1. Number of Kulkarni diagram vs SL2 and GL2 conjugacy classes.
14: d ← Solve (
x ≡ 1 mod e
x ≡ 0 mod m
15: a ← σ
c
L
16: b ← σ
c
R
17: l ← σ
d
L
18: r ← σ
d
R
19: s ← l
20r
z
l
−4
r
−1
20: if [a, r] = 1 and (ab−1a)
4 = 1 and (ab−1a)
2 = (b
−1a)
3 = (b
2a
−(m+1)/2
)
3 and [s, lr−1
l] = s
−2 and
[r, s] = r
24 and (lr−1
l)
2 = (sr5
lr−1
l)
3
then
21: return true
22: end if
23: end if
24: return false
Proof. See [8, Theorem 2.4] and §3 of loc. cit. for the implementation.
6. Some numerical data
We have systematically run our algorithm to compute Kulkarni diagrams for subgroups up to index
20. For each of them, we computed the number of conjugacy classes for SL2 and GL2-subgroups. The
results are presented in Table 6.1. Note that the number of Kulkarni diagrams grows much faster than
the real number of equivalent classes of subgroups. To our knowledge this is a phenomena that was not
observed before (since in the article published by Kulkarni only subgroups with small index are computed).
As mentioned in the introduction, all these information can be downloaded from the GitHub repository
https://github.com/vendramin/subgroups.
In Table 6.2 we give all the information obtained from each SL2(Z)-equivalence class for subgroups up to
index 7 (as it might be useful to the reader). Some information phenomena obtained from our database:
• Among all subgroups (up to SL2(Z)-equivalence), there are 90 congruence ones (from a total of 16381
subgroups), i.e. congruence groups are very rare even for small indices.
• Up to index 20, there are 2410 groups corresponding to curves of genus 1 (from a total of 16381
subgroups).
23
• There are only 9 non-conjugate subgroups whose curve has genus 2. They all correspond to subgroups
of index 18 (as the example found in [1]).
Let us state some properties regarding the genus 2 curves. Here is a list of their Kulkarni diagrams
together with their passports:
(1) The tree diagram equals
4
3
2
1
3
4
1
2
, the g.F.s. equals {∞, 0, 1,
4
3
,
3
2
,
5
3
, 2, 3, ∞} and its passport
equals
• σS = (1, 5)(2, 8)(3, 15)(4, 9)(6, 12)(7, 16)(10, 14)(11, 17)(13, 18),
• σR = (1, 8, 4)(2, 15, 7)(3, 18, 14)(5, 12, 9)(6, 16, 11)(10, 17, 13),
• σT = (1, 2, 3, 13, 14, 15, 16, 17, 18, 10, 11, 12, 4, 5, 6, 7, 8, 9).
(2) The tree diagram equals
3
4
3
1
4
2
1
2
, the g.F.s. equals {∞, 0, 1,
4
3
,
3
2
,
5
3
, 2, 3, ∞} and its passport
equals
• σS = (1, 5)(2, 8)(3, 15)(4, 18)(6, 12)(7, 16)(9, 13)(10, 14)(11, 17),
• σR = (1, 8, 4)(2, 15, 7)(3, 18, 14)(5, 12, 9)(6, 16, 11)(10, 17, 13),
• σT = (1, 2, 3, 4, 5, 6, 7, 8, 18, 10, 11, 12, 13, 14, 15, 16, 17, 9).
(3) The tree diagram equals
4
2
3
1
3
4
1
2
, the g.F.s. equals {∞, 0, 1,
4
3
,
3
2
,
5
3
, 2, 3, ∞} and its passport
equals
• σS = (1, 5)(2, 8)(3, 15)(4, 10)(6, 12)(7, 16)(9, 14)(11, 17)(13, 18),
• σR = (1, 8, 4)(2, 15, 7)(3, 18, 14)(5, 12, 9)(6, 16, 11)(10, 17, 13),
• σT = (1, 2, 3, 13, 4, 5, 6, 7, 8, 10, 11, 12, 14, 15, 16, 17, 18, 9).
(4) The tree diagram equals
3
4
3
1
2
4
1
2
, the g.F.s. equals {∞, 0, 1,
4
3
,
3
2
,
5
3
, 2, 3, ∞} and its passport
equals
• σS = (1, 5)(2, 8)(3, 15)(4, 14)(6, 12)(7, 16)(9, 13)(10, 18)(11, 17),
• σR = (1, 8, 4)(2, 15, 7)(3, 18, 14)(5, 12, 9)(6, 16, 11)(10, 17, 13),
• σT = (1, 2, 3, 10, 11, 12, 13, 18, 4, 5, 6, 7, 8, 14, 15, 16, 17, 9).
(5) The tree diagram equals
3
1
4
3
4
2
1
2
, the g.F.s. equals {∞, 0, 1,
4
3
,
3
2
,
5
3
, 2, 3, ∞} and its passport
equals
• σS = (1, 10)(2, 8)(3, 15)(4, 18)(5, 13)(6, 12)(7, 16)(9, 14)(11, 17),
• σR = (1, 8, 4)(2, 15, 7)(3, 18, 14)(5, 12, 9)(6, 16, 11)(10, 17, 13),
• σT = (1, 2, 3, 4, 10, 11, 12, 14, 15, 16, 17, 5, 6, 7, 8, 18, 9, 13).
(6) The tree diagram equals
2
1
4
3
3
4
1
2
, the g.F.s. equals {∞, 0, 1,
4
3
,
3
2
,
5
3
, 2, 3, ∞} and its passport
equals
• σS = (1, 10)(2, 8)(3, 15)(4, 13)(5, 14)(6, 12)(7, 16)(9, 18)(11, 17),
• σR = (1, 8, 4)(2, 15, 7)(3, 18, 14)(5, 12, 9)(6, 16, 11)(10, 17, 13),
• σT = (1, 2, 3, 9, 14, 15, 16, 17, 4, 10, 11, 12, 18, 5, 6, 7, 8, 13).
(7) The tree diagram equals
4
3
4
3
1
2
1
2
, the g.F.s. equals {∞, 0, 1,
4
3
,
3
2
,
5
3
, 2, 3, ∞} and its passport
equals
• σS = (1, 14)(2, 8)(3, 15)(4, 18)(5, 10)(6, 12)(7, 16)(9, 13)(11, 17),
• σR = (1, 8, 4)(2, 15, 7)(3, 18, 14)(5, 12, 9)(6, 16, 11)(10, 17, 13),
• σT = (1, 2, 3, 4, 14, 15, 16, 17, 9, 10, 11, 12, 13, 5, 6, 7, 8, 18).
(8) The tree diagram equals 3
2
4
3
2
1
1
4
, the g.F.s. equals {∞, 0,
1
2
, 1,
3
2
, 2, 3, 4, ∞} and its passport
equals
24
• σS = (1, 7)(2, 10)(3, 14)(4, 17)(5, 18)(6, 11)(8, 13)(9, 15)(12, 16),
• σR = (1, 10, 6)(2, 14, 9)(3, 17, 13)(4, 18, 16)(5, 11, 7)(8, 15, 12),
• σT = (1, 2, 3, 4, 5, 6, 7, 18, 12, 13, 14, 15, 16, 17, 8, 9, 10, 11).
(9) The tree diagram equals 3
4
2
3
2
1
1
4
, the g.F.s. equals {∞, 0,
1
2
, 1,
3
2
, 2, 3, 4, ∞} and its passport
equals
• σS = (1, 7)(2, 10)(3, 14)(4, 17)(5, 16)(6, 11)(8, 13)(9, 15)(12, 18),
• σR = (1, 10, 6)(2, 14, 9)(3, 17, 13)(4, 18, 16)(5, 11, 7)(8, 15, 12),
• σT = (1, 2, 3, 4, 12, 13, 14, 15, 18, 5, 6, 7, 16, 17, 8, 9, 10, 11).
The order of the image of θ∆ in each case equals 1008, 258048, 486, 4896, 258048, 648, 258048, 4896, 4896
respectively. Furthermore, the fourth, the eighth one and the ninth ones are isomorphic to PGL2(F17). Then
this three groups must be the ones found by Atkin and Swinnerton-Dyer in [1, Table 1] (corresponding to a
curve defined over the cubic field with generating polynomial x
3 − 3x + 1).
Recall that the modular curve attached to a congruence subgroup has many endomorphisms (corresponding to the so called Hecke operators), while modular curves for non-congruence subgroups tend to not have
endomorphisms at all (there are no Hecke operators in the new part, as proved in [2]). In particular, for
each of the previous genus 2 curves, if there is no contribution from smaller levels, one expects the Jacobian
to be absolutely simple when the subgroup is a non-congruence one.
The third one and the seventh groups are congruence ones, hence they do have many endomorphisms.
Let us study what happens for the remaining seven ones. Here is an elementary result to determine whether
a group is contained in a larger (proper) subgroup of PSL2(Z) in terms of the passport representation.
Lemma 6.1. Let ∆ be a subgroup of PSL2(Z) of index d, with coset representatives {µ1, . . . , µd}. Let σS ,
σT be its permutation representation. Then there exists a subgroup ∆˜ of PSL2(Z) of index n (with d | n)
containing ∆ if and only if the set {µ1, . . . , µd} can be written as a disjoint union of n sets each of them
with d
n
elements satisfying that σS and σT preserve the partition.
Proof. If there exists such a subgroup ∆, let ˜ {g1, . . . , gn} be coset representatives for ∆˜ \PSL2(Z) and
{h1, . . . , h d
n
} be coset representatives for ∆\∆, so that ˜ {hjgi} are representatives for ∆\PSL2(Z). In particular, the set of representatives for ∆\PSL2(Z) can be written as the disjoint union
(13) [n
i=1
{h1gi
, . . . , h d
n
gi}.
Let ν be any element of PSL2(Z). If ∆˜ giν = ∆˜ gj then the sets
{∆h1giν, . . . , ∆h d
n
giν} and {∆h1gj , . . . , ∆h d
n
gj}
must be the same, so σS and σT preserve the partition (13).
Reciprocally, let {g1, . . . , gd} be coset representatives of ∆\PSL2(Z), and let θ∆ : PSL2(Z) → Sd be as
before (identifying the set {g1, . . . , gd} with the set {1, . . . , d}). Assume that g1 ∈ ∆, so that ∆ corresponds
precisely to the elements of PSL2(Z) whose image under θ∆ fix 1.
By hypothesis (after relabeling the indexes if necessary) the set {1, . . . , d} can be written as the disjoint
union of the n sets {1, . . . ,
d
n
} ∪. . .∪ {d−
d
n + 1, . . . , d}, and our representation θ∆ induces a morphism θf∆ of
PSL2(Z) onto Sn (via the action on the previous sets). Let ∆ the set of elements of PSL ˜
2(Z) that preserve
the set {1, . . . ,
d
n
}. Clearly ∆ contains ∆, and the index of ˜ ∆ on PSL ˜
2(Z) is n because the image of θ∆ is a
transitive group (so the same holds for θf∆).
Let us compute for each of our genus 2 subgroups ∆ their “old” part. If there exists a subgroup ∆ with ˜
index 9 in PSL2(Z), then the lemma implies that our set of 18 elements can be split into 9 sets of size 2,
which are preserved under the action of PSL2(Z). Note that σT is an 18-cycle in all cases. Suppose that
such a partition exists, and that {a, b} is a pair of elements of it. Since σT acts transitively, there exists
i such that b = σ
i
T
(a). Applying σ
i
T
to the pair {a, b} we obtain the pair {σ
i
T
(a), σi
T
(b)} = {b, σ2i
T
(a)}, so
a = σ
2i
T
(a), hence i = 9. In particular, the partition must be of the form {a, σ9
T
(a)} for a varying in the set
25
{1, . . . , 18}. Then we are led to verify whether the permutation σS preserves this partition or not. Consider
each of the nine cases separately.
(1) We obtain the partition:
{1, 10}{2, 11}{3, 12}{4, 13}{5, 14}{6, 15}{7, 16}{8, 17}{9, 18}.
Clearly the element σS preserves the partition, so this contains the subgroup of index 9 with passport
σS = (1, 5)(2, 8)(3, 6)(4, 9) and σR = (1, 8, 4)(2, 6, 7)(3, 9, 5). It matches the 12th element in the
GitHub repository of subgroups of index 9. It is easy to verify that it corresponds to a genus 1 curve.
In particular, the Jacobian of the curve is isogenous to the product of two elliptic curves.
(2) A similar computation as the previous one proves that this second group is contained in an index 9
subgroup with the same passport as the previous case. Once again, the surface is isogenous to the
product of two elliptic curves.
(3) In this case, the partition obtained from σT is not compatible with the permutation σS, hence the
group is not contained in a group of index 9 (recall that this group is a congruence one).
(4) The group is not contained in an index 9 subgroup because once again the partition is not compatible
with the action of σS .
(5) The group is contained in a group of index 9 with the same passport as the first two cases.
(6) In this case, the group is contained in a subgroup of index 9, with passport σS = (2, 8)(3, 6),
σR = (1, 8, 4)(2, 6, 7)(3, 9, 5). Such a group corresponds to a curve of genus zero.
(7) The group is contained in a group of index 9 with the same passport as the first two cases.
(8) The group is not contained in an index 9 subgroup because the partition is not compatible with the
action of σS .
(9) The group is not contained in an index 9 subgroup because the partition is not compatible with the
action of σS .
Although the unique subgroup of index 2 has genus zero, a similar computation shows that the groups
1, 3, 6 are contained in the subgroup of index 2, while the other ones are not.
Verifying which groups are contained in subgroups of index 6, we see that the only ones are the first
one (contained in the subgroup with passport σS = (1, 5)(2, 3)(4, 6) and σR = (1, 3, 4)) and the sixth one,
contained in the subgroup with passport σS = (1, 4)(2, 5)(3, 6) and σR = (1, 5, 3)(2, 6, 4), corresponding to
the last subgroup of index 6 in the GitHub repository (see also Table 6.2). Such a group corresponds to a
curve of genus one, hence the surface attached to it is isogenous to the product of two elliptic curves as well.
We deduce that the only possible absolutely simple surface from the list of index 18 subgroups are the ones
corresponding to the groups 6, 8 and 9 which match the ones found by Atkin and Swinnerton-Dyer (defined
over a cubic field), while all other ones are isogenous to the product of two elliptic curves.
References
[1] A. O. L. Atkin and H. P. F. Swinnerton-Dyer. Modular forms on noncongruence subgroups. In Combinatorics (Proc.
Sympos. Pure Math., Vol. XIX, Univ. California, Los Angeles, Calif., 1968),, pages 1–25. ,, 1971.
[2] G. Berger. Hecke operators on noncongruence subgroups. C. R. Acad. Sci. Paris S´er. I Math., 319(9):915–919, 1994.
[3] D. Berghaus, H. Monien, and D. Radchenko. On the computation of modular forms on noncongruence subgroups, 2022.
[4] D. Berghaus, H. Monien, and D. Radchenko. A database of modular forms on noncongruence subgroups, 2023.
[5] A. Dooms, E. Jespers, and A. Konovalov. From Farey symbols to generators for subgroups of finite index in integral group
rings of finite groups. J. K-Theory, 6(2):263–283, 2010.
[6] The GAP Group. GAP – Groups, Algorithms, and Programming, Version 4.12.2, 2022.
[7] M. Hall, Jr. The theory of groups. Chelsea Publishing Co., New York, 1976. Reprinting of the 1968 edition.
[8] T. Hsu. Identifying congruence subgroups of the modular group. Proc. Amer. Math. Soc., 124(5):1351–1359, 1996.
[9] R. S. Kulkarni. An arithmetic-geometric method in the study of the subgroups of the modular group. Amer. J. Math.,
113(6):1053–1133, 1991.
[10] C. A. Kurth and L. Long. Computations with finite index subgroups of PSL2(Z) using Farey symbols. In Advances in
algebra and combinatorics, pages 225–242. World Sci. Publ., Hackensack, NJ, 2008.
[11] M. L. Lang, C.-H. Lim, and S. P. Tan. An algorithm for determining if a subgroup of the modular group is congruence.
Journal of The London Mathematical Society-second Series, 51:491–502, 1995.
[12] M. H. Millington. Subgroups of the classical modular group. J. London Math. Soc. (2), 1:351–357, 1969.
[13] M. Newman. Asymptotic formulas related to free products of cyclic groups. Math. Comp., 30(136):838–846, 1976.
26
Index Kulkarni Graph g.F.S. Passport Genus e2 e3 Cusps & Width Generators Congruence
2 {∞, 0, ∞} (1, 2),(),(1, 2) 0 0 2 ({∞, 0}, 2)  −1 −1
1 0 
,

0 −1
1 −1

Yes
3 {∞, 0, 1, ∞} (),(1, 3, 2),(1, 3, 2) 0 3 0 ({∞, 0, 1}, 3)
0 −1
1 0 
,

1 −1
2 −1

,

1 −2
1 −1

Yes
3
3
3
{∞, 0, 1, ∞} (2, 3),(1, 3, 2),(1, 2) 0 1 0 ({∞, 0}, 2),({1}, 2)
0 −1
1 0 
,

2 −1
1 0 
Yes
4 {∞, 0, 1, ∞} (2, 3),(2, 4, 3),(1, 2, 4, 3) 0 2 1 ({∞, 0, 1}, 4)  −1 −1
1 0 
,

1 −1
2 −1

,

1 −2
1 −1

Yes
4
3
3
{∞, 0, 1, ∞} (1, 2)(3, 4),(2, 4, 3),(1, 2, 3) 0 0 1 ({∞, 0}, 3),({2}, 3)  −1 −1
1 0 
,

2 −1
1 0 
Yes
5 {∞, 0, 1, ∞} (1, 2)(3, 4),(2, 5, 4),(1, 2, 5, 3, 4) 0 1 2 ({∞, 0, 1}, 5)  −1 −1
1 0 
,

1 −1
3 −2

,

1 −2
1 −1

Yes
6 {∞, 0, 1, ∞} (1, 2)(3, 4)(56),(2, 6, 4),(1, 2, 5, 6, 3, 4) 0 0 3 ({∞, 0, 1}, 6)  −1 −1
1 0 
,

1 −1
3 −2

,

1 −3
1 −2

Yes
6 {∞, 0, 1, 2, ∞} (1, 5),(1, 5, 3)(2, 6, 4),(1, 2, 6, 4, 5, 3) 0 4 0 ({∞, 0, 1, 2}, 6)

0 −1
1 0 
,

1 −1
2 −1

,

3 −5
2 −3

,

2 −5
1 −2
 Yes
6
5
5
{∞, 0, 1, 2, ∞} (2, 5)(4, 6),(1, 5, 3)(2, 6, 4),(1, 2, 4, 5, 3) 0 2 0 ({∞, 0, 1, }, 5),({2}, 5)

0 −1
1 0 
,

1 −1
2 −1

,

3 −4
1 −1
 Yes
6
4
4
{∞, 0, 1, 2, ∞} (2, 5)(3, 6),(1, 5, 3)(2, 6, 4),(1, 2, 3)(4, 5, 6) 0 2 0 ({∞, 0, }, 3),({1, 2}, 3)

0 −1
1 0 
,

3 −1
1 0 
,

3 −5
2 −3

,

2 −5
1 −2
 Yes
6 3 3 {∞, 0, 1, 2, ∞} (1, 6)(2, 5),(1, 5, 3)(2, 6, 4),(1, 2)(3, 6, 4, 5) 0 2 0 ({∞}, 2)({0, 1, 2}, 4) (
1 2
0 1 ),

1 −1
2 −1

,

3 −5
2 −3

,

2 −5
1 −2
 Yes
6
5
5
3
3
{∞, 0, 1, 2, ∞} (1, 3)(2, 5)(4, 6),(1, 5, 3)(2, 6, 4),(1, 2, 4, 5) 0 0 0
({∞, 1}, 4)({0}, 1)
({2}, 4) (
1 0
1 1 ),

3 −4
1 −1

Yes
6
3
4
3
4
{∞, 0, 1, 2, ∞} (1, 6)(2, 5)(3, 4),(1, 5, 3)(2, 6, 4),(1, 2)(3, 6)(4, 5) 0 0 0
({∞}, 2)({0, 2}, 2)
({1}, 2) (
1 2
0 1 ),

3 −2
2 −1

Yes
6
4
3
3
4
{∞, 0, 1, 2, ∞} (1, 4)(2, 5)(3, 6),(1, 5, 3)(2, 6, 4),(1, 2, 3, 4, 5, 6) 1 0 0 ({∞, 0, 1, 2}, 6) (
2 1
1 1 ),

3 −1
1 0 
Yes
7 {∞, 0, 1, 2, ∞} (1, 2)(3, 6),(2, 6, 4)(3, 7, 5),(1, 2, 3, 7, 5, 6, 4) 0 3 1 ({∞, 0, 1, 2}, 7)
 −1 −1
1 0 
,

1 −1
2 −1

,

3 −5
2 −3

,

2 −5
1 −2
 Yes
7 {∞, 0, 1, 2, ∞} (2, 6)(3, 4),(1, 6, 4)(2, 7, 5),(1, 2, 7, 5, 6, 3, 4) 0 3 1 ({∞, 0, 1, 2}, 7)

0 −1
1 0 
,

1 −1
3 −2

,

3 −5
2 −3

,

2 −5
1 −2
 Yes
7
5
5
{∞, 0, 1, 2, ∞} (1, 2)(3, 6)(5, 7),(2, 6, 4)(3, 7, 5),(1, 2, 3, 5, 6, 4) 0 1 1 ({∞, 0, 1, }, 6)({2}, 6)
 −1 −1
1 0 
,

1 −1
2 −1

,

3 −4
1 −1
 No
7
4
4
{∞, 0, 1, 2, ∞} (1, 2)(3, 6)(4, 7),(2, 6, 4)(3, 7, 5),(1, 2, 3, 4)(5, 6, 7) 0 1 1 ({∞, 0, }, 4)({1, 2}, 4)
 −1 −1
1 0 
,

3 −1
1 0 
,

3 −5
2 −3
 No
7
4 4
{∞, 0, 1, 2, ∞} (1, 2)(3, 6)(4, 5),(2, 6, 4)(3, 7, 5),(1, 2, 3, 7, 4)(5, 6) 0 1 1 ({∞, 0, 2}, 5)({1}, 5)
 −1 −1
1 0 
,

3 −2
2 −1

,

2 −5
1 −2
 No
7
5
5
{∞, 0, 1, 2, ∞} (2, 6)(3, 4)(5, 7),(1, 6, 4)(2, 7, 5),(1, 2, 5, 6, 3, 4) 0 1 1 ({∞, 0, 1, }, 6)({2}, 6)

0 −1
1 0 
,

1 −1
3 −2

,

3 −4
1 −1
 No
Table 6.2. Table of Subgroups up to index 7 with all the computed information.
[14] G. Shimura. Introduction to the arithmetic theory of automorphic functions, volume 11 of Publications of the Mathematical
Society of Japan. Princeton University Press, Princeton, NJ, 1994. Reprint of the 1971 original, Kanˆo Memorial Lectures,
1.
[15] F. Str¨omberg. Noncongruence subgroups and Maass waveforms. J. Number Theory, 199:436–493, 2019.
[16] S. A. Vidal. Sur la classification et le denombrement des sous-groupes du groupe modulaire et de leurs classes de conjugaison,
2007.
[17] K. Wohlfahrt. An extension of F. Klein’s level concept. Illinois J. Math., 8:529–535, 1964.
(N. Mayorga) FAMAF-CIEM, Universidad Nacional de Cordoba. C.P:5000, C ´ ordoba, Argentina. ´
Email address: <PRESIDIO_ANONYMIZED_EMAIL_ADDRESS>
(A. Pacetti) Center for Research and Development in Mathematics and Applications (CIDMA), Department of
Mathematics, University of Aveiro, 3810-193 Aveiro, Portugal
Email address: <PRESIDIO_ANONYMIZED_EMAIL_ADDRESS>
(L. Vendramin) Department of Mathematics, Vrije Universiteit Brussel, Pleinlaan 2, 1050 Brusse
i reference this as [8]. also, i empirically checked this in GAP using a program.