# Random generation of subgroups of the modular group with a fixed isomorphism
type

Frédérique Bassino<EMAIL_ADDRESS>
Université Sorbonne Paris Nord, LIPN, CNRS UMR 7030, F-93430 Villetaneuse,
France Cyril Nicaud<EMAIL_ADDRESS>
LIGM, Univ Gustave Eiffel, CNRS, ESIEE Paris, F-77454, Marne-la-Vallée, France
Pascal Weil<EMAIL_ADDRESS>
CNRS, ReLaX, IRL 2000, Siruseri, India
Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400 Talence, France
LaBRI, Univ. Bordeaux, 351 cours de la Libération, 33400 Talence, France.

###### Abstract

We show how to efficiently count and generate uniformly at random finitely
generated subgroups of the modular group $\mathsf{PSL}_{2}(\mathbb{Z})$ of a
given isomorphism type. The method to achieve these results relies on a
natural map of independent interest, which associates with any finitely
generated subgroup of $\mathsf{PSL}_{2}(\mathbb{Z})$ a graph which we call its
silhouette, and which can be interpreted as a conjugacy class of free finite
index subgroups of $\mathsf{PSL}_{2}(\mathbb{Z})$.

##### Keywords

Combinatorial group theory; subgroups of the modular group; exact enumeration
problems; random generation problems.

##### AMS Classification

05A15 (exact enumeration problems); 05E16 (combinatorial aspects of groups and
algebras); 05C30 (enumeration in graph theory).

##  1 Introduction

The modular group $\mathsf{PSL}_{2}(\mathbb{Z})$ is a fundamental object in
the field of modular forms and hyperbolic geometry. It is well-known that
$\mathsf{PSL}_{2}(\mathbb{Z})$ is isomorphic to the free product of two cyclic
groups, of order 2 and 3 respectively. That is,

$\mathsf{PSL}_{2}(\mathbb{Z})=\langle a,b\mid a^{2}=b^{3}=1\rangle.$

The finitely generated subgroups of the modular group have been extensively
studied and classified, leading to deep connections with various areas of
mathematics, including number theory, algebraic geometry, and geometric group
theory. Much work has been devoted in particular to the combinatorial study of
the _finite index_ subgroups of $\mathsf{PSL}_{2}(\mathbb{Z})$: exact
enumeration results for the index $n$ subgroups (Dey, 1965 [5]; Stothers, 1978
[22]) and results on the asymptotic behavior of that number as $n$ tends to
infinity (Newmann, 1976 [18], Müller & Schlage-Puchta, 2004 [17] and others).
Here, we deal instead with _all_ finitely generated subgroups of
$\mathsf{PSL}_{2}(\mathbb{Z})$, without index restriction.

The main purpose of this paper is to present enumeration and random generation
results for finitely generated subgroups of $\mathsf{PSL}_{2}(\mathbb{Z})$ of
a given size and isomorphism type, where both measures are natural parameters.

Let us first make the notions underlying these results more explicit. Since
$\mathsf{PSL}_{2}(\mathbb{Z})$ is the free product of a copy of
$\mathbb{Z}_{2}$ and a copy of $\mathbb{Z}_{3}$, Kurosh’s theorem (see, e.g.,
[14, 15, 19]) states that any finitely generated subgroup $H$ of
$\mathsf{PSL}_{2}(\mathbb{Z})$ is isomorphic to a free product of $\ell_{2}$
copies of $\mathbb{Z}_{2}$, $\ell_{3}$ copies of $\mathbb{Z}_{3}$ and $r$
copies of $\mathbb{Z}$: the _isomorphism type_ of $H$ is the triple
$(\ell_{2},\ell_{3},r)$. It is a natural parameter, which generalizes the rank
in free groups.

Our results also refer to a notion of size for finitely generated subgroups of
$\mathsf{PSL}_{2}(\mathbb{Z})$, that we now explain: each finitely generated
subgroup $H$ of $\mathsf{PSL}_{2}(\mathbb{Z})$ can be represented uniquely by
a finite edge-labeled graph $\Gamma(H)$, called its _Stallings graph_.
Stallings graphs, and their effective construction, were first introduced by
Stallings [21] to represent finitely generated subgroups of free groups. The
idea of using finite graphs to represent subgroups of infinite, non-free
groups first appeared in work of Gersten and Short [8, 20], Arzhantseva and
Ol’shanskiĭ [2, 1], Gitik [9] and Kapovich [11]. Markus-Epstein [16] gave an
explicit construction associating a graph with each subgroup of an amalgamated
product of two finite groups, which is very close to the one used here. Here
we follow the definition and construction of Kharlampovich, Miasnikov and Weil
[12]. In a nutshell, the Stallings graph of a subgroup $H$ of
$\mathsf{PSL}_{2}(\mathbb{Z})$ is the fragment of the Schreier (or coset)
graph of $H$, spanned by the cycles at vertex $H$ reading a geodesic
representative of an element of $H$, see Section 2.1 for more details.

We take the number of vertices of $\Gamma(H)$ to be the _size_ of the subgroup
$H$. In particular, there are only finitely many subgroups of a given size and
we assume the uniform distribution on this finite set.

In [3] the authors counted the finitely generated subgroups of
$\mathsf{PSL}_{2}(\mathbb{Z})$ by size and they showed how to generate
uniformly at random a subgroup of a given size. They also computed the
expected value of the isomorphism type of a random subgroup as a function of
its size and proved a large deviations theorem for this isomorphism type. It
follows that randomly generating a size $n$ subgroup of
$\mathsf{PSL}_{2}(\mathbb{Z})$ will, with high probability, yield a subgroup
whose isomorphism type is close to the average value. In particular, this
algorithmic result does not help generate uniformly at random subgroups of a
given size and isomorphism type. The proof strategy to obtain these results
was based on counting Stallings graphs and using the classical tools of
analytic combinatorics [6], in particular the notion of exponential generating
series.

In this paper, we use a completely different enumeration method for finitely
generated subgroups of $\mathsf{PSL}_{2}(\mathbb{Z})$, to get a polynomial
time random generation algorithm for subgroups of
$\mathsf{PSL}_{2}(\mathbb{Z})$ of a given size and isomorphism type. It turns
out that we can proceed with direct computations and we therefore avoid
introducing generating series. More precisely the proofs rely on a combination
of graph decomposition techniques and combinatorial methods. As is classical
in the field, these methods are used on labeled graphs (graphs equipped with a
bijection from their vertex set to an initial segment of $\mathbb{N}$).

A key construction which occurs naturally in this approach is what we call the
_silhouetting_ of the Stallings graph of a finitely generated subgroup of
$\mathsf{PSL}_{2}(\mathbb{Z})$. It consists in a sequence of “simplifications”
of the graph, leading (except in extremal cases) to a uniform degree loop-free
graph, which represents a conjugacy class of finite index, free subgroups of
$\mathsf{PSL}_{2}(\mathbb{Z})$.

The operation of silhouetting is not just useful for our enumeration and
random generation purpose: it also has very interesting algebraic and
probabilistic properties. As an example of the former, we establish that
silhouetting preserves the free rank component of the isomorphism type of a
subgroup (Proposition 3.6). Probabilistic properties of the silhouetting
operation, and their use in proving asymptotic properties of finitely
generated subgroups of $\mathsf{PSL}_{2}(\mathbb{Z})$, are discussed in a
separate paper [4].

##### Organization of the paper

Readers can find in Sections 2.1 and 2.2 the precise definitions of the
Stallings graph of a subgroup of $\mathsf{PSL}_{2}(\mathbb{Z})$ and its
combinatorial type, and results from the literature relating this
combinatorial information with algebraic properties of the subgroup such as
its isomorphism type, its index or its freeness.

Section 3 introduces combinatorial operations on Stallings graphs. Iterating
these operations leads to so-called _silhouette_ graphs. The fine description
of these operations is first exploited in Section 4 to give exact counting
formulas for the number of subgroups of $\mathsf{PSL}_{2}(\mathbb{Z})$ of a
given combinatorial or isomorphism type.

In Section 3.3, we show that the iteration of the operations defined in
Section 4 is a confluent process (Proposition 3.4), which leads to defining
the _silhouette_ of a given graph or subgroup. It is interesting to note that
silhouetting preserves the free rank component of the isomorphism type of a
subgroup (Proposition 3.6).

Finally, Section 5 uses the operations from Section 3 in a different way to
design an algorithm (which includes a rejection algorithm component) to
efficiently generate uniformly at random a subgroup of a given size and
isomorphism type.

##  2 Preliminaries

We work with the following presentation of the modular group:

$\mathsf{PSL}_{2}(\mathbb{Z})=\langle a,b\mid a^{2}=b^{3}=1\rangle.$

The elements of $\mathsf{PSL}_{2}(\mathbb{Z})$ are represented by words over
the alphabet $\\{a,b,a^{-1},b^{-1}\\}$. Since $a^{-1}=a$ in
$\mathsf{PSL}_{2}(\mathbb{Z})$, we can eliminate the letter $a^{-1}$ from this
alphabet. Each element of $\mathsf{PSL}_{2}(\mathbb{Z})$ then has a unique
shortest (or _normal_ , or _geodesic_) representative, which is a freely
reduced word without factors in $\\{a^{2},b^{2},b^{-2}\\}$. That is, the
normal representatives are the words of length at most 1 and the words
alternating letters $a$ and letters in $\\{b,b^{-1}\\}$.

###  2.1 Stallings graph of a subgroup of $\mathsf{PSL}_{2}(\mathbb{Z})$

The _Schreier graph_ (or _coset graph_) of a subgroup $H$ of
$\mathsf{PSL}_{2}(\mathbb{Z})$ is the graph whose vertices are the cosets $Hg$
of $H$ ($g\in\mathsf{PSL}_{2}(\mathbb{Z})$), with an $a$-labeled edge from
$Hg$ to $Hga$ and a $b$-labeled edge from $Hg$ to $Hgb$, for every $g\in G$.
We think of $b$-edges as $2$-way edges, reading $b$ in the forward direction
and $b^{-1}$ in the backward direction. Since $a=a^{2}$, there is an $a$-edge
from vertex $v$ to vertex $v^{\prime}$ if and only there is one from
$v^{\prime}$ to $v$: as a result, we think of the $a$-edges as undirected
edges, that can be traveled in either direction, each time reading $a$. A path
in such an edge-labeled graph is called a _cycle_ if its initial vertex is
equal to its final vertex. The sequence of edge labels along a path $p$ spells
a word $w$ over alphabet $\\{a,b,b^{-1}\\}$, and we say that $w$ _labels the
path_ $p$, or that $p$ _reads_ $w$.

Note that a word is in $H$ if and only if it labels a cycle at vertex
$v_{0}=H$ in the Schreier graph of $H$. The _Stallings graph_ of $H$, written
$(\Gamma(H),v_{0})$, is defined to be the fragment of the Schreier graph of
$H$ spanned by the cycles at $v_{0}$ reading the geodesic representatives of
the elements of $H$, rooted at $v_{0}$: that is, the subgraph of the Schreier
graph of $H$ consisting of all the edges participating in a cycle at $v_{0}$
which reads a geodesic representation of an element of $H$, and of all the
vertices adjacent to these edges. In particular, a word is in $H$ if and only
if its geodesic representative labels a cycle in $\Gamma(H)$ at vertex
$v_{0}$. We refer the reader to Remark 2.2 and to [12] for more details on
these graphs. We note in particular that $H$ has a finite Stallings graph if
and only if it is finitely generated, and that $\Gamma(H)$ is efficiently
algorithmically computable if $H$ is given by a finite set of generators
(words on the alphabet $\\{a,b,b^{-1}\\}$) [12, 3].

###### Example 2.1

Figure 1 shows examples of Stallings graphs. To be more precise: the graphs in
Figure 1 are _labeled graphs_ , meaning that their vertices are labeled by an
initial segment of $\mathbb{N}$, see more details on this useful notion
further down in Section 2.3. The definition of Stallings graphs does not
entail labeling vertices — only designating a base vertex.

Nw=4,Nh=4 (n0)(0.0,-0.0)$1$(n1)(6.0,-14.0)2 (n2)(0.0,-28.0)3 (n3)(34,-0.0)4
(n4)(28,-14.0)5 (n5)(34.0,-28.0)6
(n0,n1)$b$(n1,n2)$b$(n2,n0)$b$[ELside=r](n3,n4)$b$[ELside=r](n4,n5)$b$[ELside=r](n5,n3)$b$[AHnb=0](n0,n3)$a$[AHnb=0](n1,n4)$a$[AHnb=0](n2,n5)$a$(m1)(72.0,-4.0)$1$(m2)(78.0,-14.0)2
(m3)(72.0,-24.0)3 (m4)(52,-4.0)4 (m5)(52,-24.0)5 (m6)(98.0,-14.0)6
(m1,m2)$b$(m2,m3)$b$(m3,m1)$b$[AHnb=0](m1,m4)$a$[ELside=r](m4,m5)$b$[AHnb=0](m5,m3)$a$[AHnb=0](m2,m6)$a$(m6)$b$(h1)(15.0,-40.0)$1$(h2)(45.0,-40.0)2
(h3)(75.0,-40.0)3 (h15)(105.0,-40.0)15 (h4)(15.0,-64.0)4 (h11)(15.0,-88.0)11
(h16)(105.0,-64.0)16 (h17)(105.0,-88.0)17 (h12)(45.0,-88.0)12
(h14)(75.0,-88.0)14 (h10)(60.0,-56.0)10 (h13)(30.0,-72.0)13
(h18)(90.0,-72.0)18 (h5)(4.0,-52.0)5 (h6)(4.0,-76.0)6 (h7)(-2.0,-86.0)7
(h8)(4.0,-96.0)8 (h9)(25.0,-96.0)9
(h2,h3)$b$(h3,h10)$b$(h10,h2)$b$(h14,h17)$b$[ELside=r](h17,h18)$b$[ELside=r](h18,h14)$b$(h11,h12)$b$[ELside=r](h12,h13)$b$[ELside=r](h13,h11)$b$[ELside=r](h1,h4)$b$(h4,h5)$b$(h5,h1)$b$(h6,h8)$b$(h8,h7)$b$(h7,h6)$b$(h15,h16)$b$[AHnb=0](h1,h2)$a$[AHnb=0](h3,h15)$a$[AHnb=0](h16,h17)$a$[AHnb=0](h12,h14)$a$[AHnb=0](h11,h4)$a$[AHnb=0](h6,h5)$a$[AHnb=0](h8,h9)$a$[AHnb=0](h10,h13)$a$[loopangle=140,AHnb=0](h7)$a$[loopangle=0](h9)$b$[loopangle=90,AHnb=0](h18)$a$
Figure 1: Top: the Stallings graphs of the subgroups $H=\langle
abab^{-1},babab\rangle$ and $K=\langle abab,b^{ab^{-1}}\rangle$ of
$\mathsf{PSL}_{2}(\mathbb{Z})$, where $g^{h}$ stands for $h^{-1}gh$. Bottom:
the Stallings graph of $L=\langle
b^{ab^{-1}ab},a^{bab},a^{(ab)^{3}},ab^{-1}abab^{-1},(ab)^{2}(ab^{-1})^{3}\rangle$.
In each case, the root is the vertex labeled 1.

$\sqcap$$\sqcup$

###### Remark 2.2

The definition of Stallings graphs given above is a generalization of that
introduced by Stallings in 1983 [21] for finitely generated subgroups of free
groups, and a particular instance of the definition first introduced by Gitik
[9] in 1996 under the name of geodesic core, and systematized by
Kharlampovich, Miasnikov and Weil [12] in 2017. Given a finitely presented
group $G=\langle A\mid R\rangle$, a language $L$ of representatives for $G$ (a
set of words over the alphabet $A\cup A^{-1}$) and a subgroup $H$, one
considers the fragment of the Schreier graph of $H$ spanned by the
$L$-representatives of the elements of $H$. It is effectively computable if
$G$ is equipped with an automatic structure [12] and $H$ is $L$-quasi-convex.
In the particular case where $G=\mathsf{PSL}_{2}(\mathbb{Z})$, we take $L$ to
be the language of normal forms. It is well-known that $G$ is automatic with
respect to this language, and that every finitely generated subgroup of
$\mathsf{PSL}_{2}(\mathbb{Z})$ is quasi-convex. The algorithm to compute the
Stallings graph of a subgroup, given a tuple of its generators, is quite
straightforward, we refer the reader to [3] for an outline. $\sqcap$$\sqcup$

It is immediate from the definition of Stallings graphs that $\Gamma(H)$ is
connected and that its $a$-edges (respectively, $b$-edges) form a partial,
injective map on the vertex set of the graph. Moreover, because
$a^{2}=b^{3}=1$, distinct $a$-edges are never adjacent to the same vertex: we
distinguish therefore $a$-loops and so-called _isolated $a$-edges_. Similarly,
if we have two consecutive $b$-edges, say, from $v_{1}$ to $v_{2}$ and from
$v_{2}$ to $v_{3}$, then $\Gamma(H)$ also has a $b$-edge from $v_{3}$ to
$v_{1}$. Thus each $b$-edge is either a loop, or an _isolated $b$-edge_, or a
part of a $b$-triangle. Finally, every vertex except maybe the root vertex is
adjacent to an $a$\- and to a $b$-edge.

A rooted edge-labeled graph satisfying these conditions is called
_$\mathsf{PSL}_{2}(\mathbb{Z})$ -reduced_ and it is not difficult to see that
every finite $\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graph is the Stallings
graph of a unique finitely generated subgroup of
$\mathsf{PSL}_{2}(\mathbb{Z})$. That is, the mapping
$H\mapsto(\Gamma(H),v_{0})$ is a bijection between finitely generated
subgroups of $\mathsf{PSL}_{2}(\mathbb{Z})$ and
$\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graphs.

An edge-labeled graph is said to be _$\mathsf{PSL}_{2}(\mathbb{Z})$
-cyclically reduced_ if every vertex is adjacent to an $a$\- and a $b$-edge
or, equivalently, if it is $\mathsf{PSL}_{2}(\mathbb{Z})$-reduced when rooted
at every one of its vertices. We also say that a finitely generated subgroup
of $\mathsf{PSL}_{2}(\mathbb{Z})$ is $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically
reduced if its Stallings graph is.

###### Example 2.3

The $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graphs $\Gamma$ with 1
or 2 vertices are represented in Figure 2.

Nw=4,Nh=4 (n0)(8.0,-5.0)
$\Delta_{1}$[loopangle=150,AHnb=0](n0)$a$[loopangle=30](n0)$b$(n0)(33.0,-3.0)
(n1)(53.0,-3.0)
$\Delta_{2}$[curvedepth=2](n0,n1)$b$[curvedepth=2,AHnb=0](n1,n0)$a$(n0)(73.0,-5.0)
(n1)(93.0,-5.0)
$\Delta_{3}$(n0,n1)$b$[AHnb=0,loopangle=90](n0)$a$[AHnb=0,loopangle=90](n1)$a$(n0)(113.0,-5.0)
(n1)(133.0,-5.0)
$\Delta_{4}$[AHnb=0](n0,n1)$a$[loopangle=90](n0)$b$[loopangle=90](n1)$b$
Figure 2: All $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graphs with at
most 2 vertices.

There is only one with 1 vertex, and three with 2 vertices. $\sqcap$$\sqcup$

###  2.2 Combinatorial type, isomorphism type of a subgroup of
$\mathsf{PSL}_{2}(\mathbb{Z})$

The _combinatorial type_ of a $\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graph
$\Gamma$ is the tuple $(n,k_{2},k_{3},\ell_{2},\ell_{3})$ where $n$ is the
number of vertices of $\Gamma$, $k_{2}$ and $k_{3}$ are the numbers of
isolated $a$\- and $b$-edges, and $\ell_{2}$ and $\ell_{3}$ are the numbers of
$a$\- and $b$-loops. We sometimes talk of the combinatorial type of a subgroup
to mean the combinatorial type of its Stallings graph, and we refer to $n$
(the number of vertices of a $\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graph) as
the _size_ of the graph or even the _size_ of the subgroup. See [3] for a
discussion of the possible combinatorial types.

Let us also record the following results (see, _e.g._ , [3, Lemma 2.3,
Propositions 2.7, 2.9, 8.18 and Section 8.2]).

###### Proposition 2.4

A subgroup $H\leq\mathsf{PSL}_{2}(\mathbb{Z})$ has finite index if and only if
its Stallings graph is $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced and
has combinatorial type of the form $(n,k_{2},0,\ell_{2},\ell_{3})$. It is free
if and only if its combinatorial type is of the form $(n,k_{2},k_{3},0,0)$.

Free $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced subgroups have even
size. Free and finite index subgroups are
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced and their size is a multiple
of $6$. The combinatorial type of a free and finite index subgroup is of the
form $(n,\frac{1}{2}n,0,0,0)$.

$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced subgroups are conjugates if
and only if the (unrooted) edge-labeled graphs underlying their Stallings
graphs are isomorphic.

By Kurosh’s classical theorem on subgroups of free groups (e.g., [15,
Proposition III.3.6]), a subgroup $H$ of $\mathsf{PSL}_{2}(\mathbb{Z})$ is
isomorphic to a free product of $r_{2}$ copies of $\mathbb{Z}_{2}$, $r_{3}$
copies of $\mathbb{Z}_{3}$ and a free group of rank $r$, for some non-negative
integers $r_{2},r_{3},r$. The triple $(r_{2},r_{3},r)$, which characterizes
$H$ up to isomorphism (but not up to an automorphism of
$\mathsf{PSL}_{2}(\mathbb{Z})$) is called the _isomorphism type_ of $H$. We
record the following connection between the combinatorial and the isomorphism
types of a subgroup [3, Proposition 2.9].

###### Proposition 2.5

Let $H$ be a subgroup of $\mathsf{PSL}_{2}(\mathbb{Z})$ of size at least $2$
and let $(n,k_{2},k_{3},\ell_{2},\ell_{3})$ be the combinatorial type of
$\Gamma(H)$.

If $\Gamma(H)$ is $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced, the
isomorphism type of $H$ is

$\left(\ell_{2},\ell_{3},1+\frac{n-2k_{3}-3\ell_{2}-4\ell_{3}}{6}\right).$

If $\Gamma(H)$ is not $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced, the
isomorphism type of $H$ is

$\displaystyle\left(\ell_{2},\ell_{3},\frac{1}{3}+\frac{n-2k_{3}-3\ell_{2}-4\ell_{3}}{6}\right)$
if the base vertex is adjacent to an $a$-edge
$\displaystyle\left(\ell_{2},\ell_{3},\frac{1}{2}+\frac{n-2k_{3}-3\ell_{2}-4\ell_{3}}{6}\right)$
if the base vertex is adjacent to a $b$-edge.

###  2.3 Labeled graphs

One of our objectives in this paper is to count subgroups by isomorphism type
or by combinatorial type. Since subgroups are in bijection with
$\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graphs (their Stallings graphs), it is
equivalent to count these graphs. For technical reasons, it is easier to count
_labeled graphs_ , that is, graphs whose vertex set is equipped with a
(labeling) bijection onto a set of the form $[n]=\\{1,\dots,n\\}$111It is
important to distinguish this notion of labeling, which injectively assigns an
integer to each vertex, from the edge labeling used so far, where each edge is
labeled by either the order 2 generator $a$ of $\mathsf{PSL}_{2}(\mathbb{Z})$,
or by its order 3 generator $b$ and each path is labeled by a word.. The
graphs in Figure 1 are in fact labeled graphs.

###### Example 2.6

The $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graphs $\Delta_{2}$ and
$\Delta_{3}$ in Example 2.3 admit two distinct labelings, while $\Delta_{1}$
and $\Delta_{4}$ have only one. We record here what we call the _preferred_
labeling of $\Delta_{2}$, where the $b$-edge goes from 1 to 2, see Figure 3.

Nw=4,Nh=4 (n0)(8.0,-3.0)1 (n1)(33.0,-3.0)2
[curvedepth=2](n0,n1)$b$[curvedepth=2,AHnb=0](n1,n0)$a$ Figure 3: The
preferred labeling of $\Delta_{2}$

$\sqcap$$\sqcup$

Since we are going to count graphs, rooted or not, labeled or not, it is
important to clarify that we consider these combinatorial objects up to
isomorphism. Concretely, if $\Gamma$ and $\Gamma^{\prime}$ are graphs, an
isomorphism from $\Gamma$ to $\Gamma^{\prime}$ is a pair of bijections
$\varphi=(\varphi_{V},\varphi_{E})$ from the vertex set of $\Gamma$ to the
vertex set of $\Gamma^{\prime}$ and from the edge set of $\Gamma$ to the edge
set of $\Gamma^{\prime}$, respectively, which preserve the incidence relation
(that is, if $\Gamma$ has an edge $e$ from vertex $v$ to vertex $w$, then
$\varphi_{E}(e)$ is an edge from $\varphi_{V}(v)$ to $\varphi_{V}(w)$. If
$\Gamma$ and $\Gamma^{\prime}$ are rooted, then $\varphi_{V}$ must also map
the root of $\Gamma$ to the root of $\Gamma^{\prime}$. If, finally, $\Gamma$
and $\Gamma^{\prime}$ are edge-labeled, then $\varphi_{E}$ must also preserve
these labels.

It is important to note that, an $n$-vertex
$\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graph admits exactly $n!$ distinct
labeling functions. Let indeed $v_{0}$ be the root of $\Gamma$ and let us fix
a total order on the alphabet $\\{a,b,b^{-1}\\}$. Assigning to each vertex $v$
the lexicographically least geodesic word labeling a path from $v_{0}$ to $v$,
yields a total order on the vertex set of $\Gamma$. A labeling of $\Gamma$ is
therefore equivalent to a permutation of $[n]$. Another way of formulating
this observation is that a $\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graph admits
no non-trivial automorphism.

##  3 The silhouetting operation on $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically
reduced graphs

We will see in Sections 4.1 and 5 that counting and randomly generating
subgroups of $\mathsf{PSL}_{2}(\mathbb{Z})$ reduces to counting and randomly
generating labeled $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graphs.
Before we embark on this task, we introduce a combinatorial construction on
this class of graphs.

More precisely, we define in Section 3.1 certain moves on a labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph, depending on its
geometry. They are used in Section 4.2 to count subgroups of
$\mathsf{PSL}_{2}(\mathbb{Z})$ and in Section 5 to randomly generate them.
They also bring to the fore an interesting structure associated with a
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph, which we call its
_silhouette_. Some of its algebraic and combinatorial properties are discussed
in Section 3.3.

Very roughly speaking, these moves “simplify” a labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph by first iteratively
removing all loops and the paths that lead to them, until we are left (except
in degenerate cases) with a graph which consists only of $b$-triangles and
paths connecting them. The process then “simplifies” these connecting paths so
that the resulting graph consists only of $b$-triangles connected by isolated
$a$-edges. As we know, such graphs represent conjugacy classes of free finite
index subgroups (see Proposition 2.4).

For technical reasons, we use the notion of _weakly labeled_ graphs [6,
Definition II.1]: if $\Gamma$ is a $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically
reduced graph of size $m$, a _weak labeling_ of $\Gamma$ is an injective map
from the vertex set of $\Gamma$ to $[n]$, where $n$ is an integer at least
equal to $m$. To lighten up notation, we often abusively identify the vertices
of a weakly labeled graph with their labels. We also abusively write
$\Delta_{i}$ ($i=1,2,3,4$) for any weakly labeled version of the graphs in
Example 2.3.

Observe that a weak labeling $\alpha$ of $\Gamma$ gives rise to a labeling of
$\Gamma$ by a uniquely defined order-preserving bijection from the range of
$\alpha$ to $[m]$. The labeled graph obtained this way is called the
_normalization_ 222This operation is called _reduction_ in [6, Section
II.2.1]. of $\Gamma$, denoted by $\operatorname{norm}(\Gamma)$.

###  3.1 Moves on a labeled $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced
graph

Here we define so-called $\lambda_{3}$-, $\lambda_{2,1}$-, $\lambda_{2,2}$-,
$\kappa_{3}$\- and _exceptional_ moves on weakly labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graphs333The denomination of
$\lambda_{3}$-move is chosen because these moves deal with loops labeled by
the order 3 generator $b$, which are counted by the parameter $\ell_{3}$.
Similar justifications hold for the moves that deal with $a$-loops (counted by
$\ell_{2}$) and with isolated $b$-edges (counted by $k_{3}$).. But for the
exceptional moves, each of these moves deletes vertices from the input graph
without changing their label, so that the resulting graph is, again, weakly
labeled.

In the following, $\Gamma$ is a weakly labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph with combinatorial
type $\bm{\tau}=(n,k_{2},k_{3},\ell_{2},\ell_{3})$.

#####  $\lambda_{3}$-moves

If $\Gamma$ has a $b$-loop at vertex $v$ (in fact, at the vertex labeled $v$)
and there is an isolated $a$-edge between $v$ and a distinct vertex $w$, then
the _$(\lambda_{3},v,w)$ -move_ consists in deleting vertex $v$ and the
adjacent edges, and adding an $a$-loop at vertex $w$. The resulting weakly
labeled graph $\Delta$ (see Figure 4) is
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced and has combinatorial type
$\bm{\tau}+\bm{\lambda}_{3}$, where $\bm{\lambda}_{3}=(-1,-1,0,1,-1)$.

Nw=4,Nh=4 (37,-12,40,20,12)
(n0)(20.0,-12.0)$w$(n1)(4.0,-12.0)$v$[AHnb=0](n0,n1)$a$[loopangle=180,loopdiam=6](n1)$b$(110,-12,40,20,12)
(n2)(93.0,-12.0)$w$[loopangle=180,loopdiam=6,AHnb=0](n2)$a$ Figure 4:
$(\lambda_{3},v,w)$-move

###### Lemma 3.1

Suppose that $n\geq 2$ and $\ell_{3}>0$. The $\lambda_{3}$-moves establish a
bijection from the set of pairs $(\Gamma,\ell)$ with $\Gamma$ a labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph of combinatorial type
$\bm{\tau}$ and $\ell$ a $b$-loop in $\Gamma$, to the set of triples
$(\Delta,\ell^{\prime},v)$ formed by a labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph $\Delta$ with
combinatorial type $\bm{\tau}+\bm{\lambda}_{3}$, an $a$-loop $\ell^{\prime}$
in $\Delta$ and an integer $v\in[n]$.

  * Proof.

Given a pair $(\Gamma,\ell)$ with $\Gamma$ a labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph of combinatorial type
$\bm{\tau}$ and $\ell$ a $b$-loop in $\Gamma$, we associate to it the triple
$(\Delta,v,w)$ — and we write
$(\Gamma,\ell)\longmapsto(\Delta,\ell^{\prime},v)$ — defined as follows: $v$
is the vertex carrying the loop $\ell$ in $\Gamma$; since $n>1$, $v$ is
adjacent to an isolated $a$-edge and we let $w$ be the other end of that
$a$-edge; finally, we let $\Delta^{\prime}$ be the weakly labeled graph
obtained from $\Gamma$ by a $(\lambda_{3},v,w)$-move,
$\Delta=\operatorname{norm}(\Delta^{\prime})$ and $\ell^{\prime}$ be the
$a$-loop in $\Delta$ at the vertex labeled $w$ in $\Delta^{\prime}$.

Conversely, let $\Delta$ be a labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph with combinatorial
type $\bm{\tau}+\bm{\lambda}_{3}$, let $\ell^{\prime}$ be an $a$-loop in
$\Delta$ and let $v\in[n]$. Let $\Delta^{\prime}$ be the weakly labeled graph
obtained from $\Delta$ by “making space for $v$”, that is, by incrementing the
labels of all the vertices greater than or equal to $v$. Finally, let $w$ be
the label of the vertex of $\Delta^{\prime}$ carrying the loop
$\ell^{\prime}$. Now let $\Gamma$ be the graph obtained from $\Delta^{\prime}$
by deleting the loop $\ell^{\prime}$ and adding vertex $v$, an isolated
$a$-edge between $v$ and $w$ and a $b$-loop at $v$: it is directly verified
that $\Gamma$ is properly labeled, of combinatorial type $\bm{\tau}$, and that
$(\Gamma,\ell)\longmapsto(\Delta,\ell^{\prime},v)$. $\sqcap$$\sqcup$

#####  $\lambda_{2}$-moves

Let $\Gamma$ be a weakly labeled $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically
reduced graphs of size $n\geq 3$ and let $v$ be a vertex carrying an $a$-loop.
Two situations occur, depending on whether $v$ sits on a $b$-triangle or not,
giving rise to two flavors of $\lambda_{2}$-moves.

If $v$ sits on a $b$-triangle, let $w$ and $w^{\prime}$ be the other
extremities of the $b$-edges ending and starting at $v$, respectively. Then
$w\neq w^{\prime}$ and $\Gamma$ has a (non-isolated) $b$-edge from
$w^{\prime}$ to $w$. The _$(\lambda_{2,1},v,w^{\prime})$ -move_ consists in
removing from $\Gamma$ vertex $v$ and the adjacent edges (the $a$-loop $\ell$
and two $b$-edges). The resulting graph $\Delta$ (see Figure 5) is
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced, it has an isolated $b$-edge
from $w^{\prime}$ to $w$ and combinatorial type
$\bm{\tau}+\bm{\lambda}_{2,1}$, where $\bm{\lambda}_{2,1}=(-1,0,1,-1,0)$.

If instead $v$ does not sit on a $b$-triangle, there exist vertices
$w,w^{\prime}$ such that $v,w,w^{\prime}$ are pairwise distinct, there is an
isolated $a$-edge between $w$ and $w^{\prime}$, and an isolated $b$-edge
between $v$ and $w$ (two directions are possible for that edge). The
_$(\lambda_{2,2},v\to w,w^{\prime})$ -move_ (respectively,
$(\lambda_{2,2},v\leftarrow w,w^{\prime})$, depending on the orientation of
the $b$-edge adjacent to $v$) consists in deleting from $\Gamma$ the vertices
$v$ and $w$ and the edges adjacent to them, and adding an $a$-loop
$\ell^{\prime}$ at $w^{\prime}$. The resulting graph $\Delta$ (see Figure 5)
is $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced and has combinatorial
type $\bm{\tau}+\bm{\lambda}_{2,2}$, where
$\bm{\lambda}_{2,2}=(-2,-1,-1,0,0)$.

Nw=4,Nh=4 (49,-12,40,20,12)
(n0)(33.0,-7.0)$w^{\prime}$(n00)(33.0,-17.0)$w$(n1)(21.0,-12.0)$v$(n00,n1)$b$(n1,n0)$b$(n0,n00)$b$[loopangle=180,loopdiam=6,AHnb=0](n1)$a$(112,-12,40,20,12)
(n2)(96.0,-7.0)$w^{\prime}$(n22)(96.0,-17.0)$w$(n2,n22)$b$(49,-42,40,20,12)
(n3)(32.0,-42.0)$w^{\prime}$(n4)(16.0,-42.0)$w$(n5)(0.0,-42.0)$v$[ELside=r](n4,n5)$b$[ELside=r,AHnb=0](n3,n4)$a$[loopangle=180,loopdiam=6,AHnb=0](n5)$a$(112,-42,40,20,12)
(n6)(96.0,-42.0)$w^{\prime}$[loopangle=180,loopdiam=6,AHnb=0](n6)$a$ Figure 5:
Above: $(\lambda_{2,1},v,w^{\prime})$-move. Below: $(\lambda_{2,2},v\leftarrow
w,w^{\prime})$-move

###### Lemma 3.2

Suppose that $n\geq 3$ and $\ell_{2}>0$.

  1. 1.

The $\lambda_{2,1}$-moves establish a bijection from the set of pairs
$(\Gamma,\ell)$ with $\Gamma$ a labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph of combinatorial type
$\bm{\tau}$ and $\ell$ an $a$-loop adjacent to a $b$-triangle in $\Gamma$, to
the set of triples $(\Delta,e,v)$ formed by a labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph $\Delta$ with
combinatorial type $\bm{\tau}+\bm{\lambda}_{2,1}$, an isolated $b$-edge $e$ in
$\Delta$ and an integer $v\in[n]$.

  2. 2.

Similarly, the $\lambda_{2,2}$-moves establish a bijection from the set of
pairs $(\Gamma,\ell)$ with $\Gamma$ a labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph of combinatorial type
$\bm{\tau}$ and $\ell$ an $a$-loop adjacent to an isolated $b$-edge in
$\Gamma$, to the set of 4-tuples $(\Delta,\ell^{\prime},v,w,\varepsilon)$
formed by a labeled $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph
$\Delta$ with combinatorial type $\bm{\tau}+\bm{\lambda}_{2,2}$, an $a$-loop
$\ell^{\prime}$ in $\Delta$, distinct integers $v,w\in[n]$ and some
$\varepsilon\in\\{-1,+1\\}$.

  * Proof.

Given a pair $(\Gamma,\ell)$ with $\Gamma$ a labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph of combinatorial type
$\bm{\tau}$ and $\ell$ an $a$-loop in $\Gamma$ adjacent to a $b$-triangle, we
associate to it the triple $(\Delta,e,v)$ — and we write
$(\Gamma,\ell)\longmapsto(\Delta,e,v)$ — defined as follows: $v$ is the vertex
carrying the loop $\ell$ in $\Gamma$; since $v$ is adjacent to a $b$-triangle
and we let $e$ be the $b$-edge in that triangle not adjacent to $v$ (going
from $w^{\prime}$ to $w$); finally, we let $\Delta^{\prime}$ be the weakly
labeled graph obtained from $\Gamma$ by a $(\lambda_{2,1},v,w^{\prime})$-move,
$\Delta=\operatorname{norm}(\Delta^{\prime})$ and $e$ be the isolated $b$-edge
in $\Delta$ starting at the vertex labeled $w^{\prime}$ in $\Delta^{\prime}$.

Conversely, let $\Delta$ be a labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph with combinatorial
type $\bm{\tau}+\bm{\lambda}_{2,1}$, let $e$ be an isolated $b$-edge in
$\Delta$ and let $v\in[n]$. Let $\Delta^{\prime}$ be the weakly labeled graph
obtained from $\Delta$ by “making space for $v$”, that is, by incrementing the
labels of all the vertices greater than or equal to $v$. Now let $\Gamma$ be
the graph obtained from $\Delta^{\prime}$ by adding a new vertex $v$,
completing $e$ to a $b$-triangle through vertex $v$: it is directly verified
that $\Gamma$ is properly labeled, of combinatorial type $\bm{\tau}$, and that
$(\Gamma,\ell)\longmapsto(\Delta,e,v)$. This completes the proof of the first
statement.

The second statement is proved in a similar fashion. Given a pair
$(\Gamma,\ell)$ with $\Gamma$ a labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph of combinatorial type
$\bm{\tau}$ and $\ell$ an $a$-loop adjacent to an isolated $b$-edge in
$\Gamma$, we associate with it a 4-tuple
$(\Delta,\ell^{\prime},v,w,\varepsilon)$ as in the statement, where $v$ is the
vertex carrying $\ell$, $w$ is the other extremity of the adjacent isolated
$b$-edge and $\varepsilon$ records whether a $(\lambda_{2,2},v\to
w,w^{\prime})$-move or a $(\lambda_{2,2},v\leftarrow w,w^{\prime})$ can be
performed. The converse mapping, reconstructing $(\Gamma,\ell)$ from
$(\Delta,\ell^{\prime},v,w,\varepsilon)$ follows the same steps as for
$\lambda_{2,1}$\- or $\lambda_{3}$-moves. $\sqcap$$\sqcup$

#####  $\kappa_{3}$-moves

Let $\Gamma$ be a weakly labeled $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically
reduced graph of size at least 4, and let $v,w,v^{\prime},w^{\prime}$ be
pairwise distinct vertices such that there is an isolated $b$-edge from $v$ to
$w$, and isolated $a$-edges connecting $v$ and $v^{\prime}$ on the one hand,
and $w$ and $w^{\prime}$ on the other. The _$\kappa_{3}$ -move_
$(\kappa_{3},v\to w,v^{\prime},w^{\prime})$ consists in deleting vertices $v$
and $w$ and the adjacent edges, and adding a new isolated $a$-edge between
$v^{\prime}$ and $w^{\prime}$. The resulting graph $\Delta$ (see Figure 6) is
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced and has combinatorial type
$\bm{\tau}+\bm{\kappa}_{3}$, where $\bm{\kappa}_{3}=(-2,-1,-1,0,0)$.

Nw=4,Nh=4 (37,-12,40,20,12)
(n0)(21.0,-07.0)$v^{\prime}$(n00)(21.0,-17.0)$w^{\prime}$(n1)(4.0,-07.0)$v$(n11)(4.0,-17.0)$w$[ELside=r](n1,n11)$b$[AHnb=0](n1,n0)$a$[AHnb=0](n00,n11)$a$(110,-12,40,20,12)
(n2)(94.0,-07.0)$v^{\prime}$(n22)(94.0,-17.0)$w^{\prime}$[AHnb=0](n2,n22)$a$
Figure 6: $(\kappa_{3},v\to w,v^{\prime},w^{\prime})$-move

Similarly to the other moves, we record the following lemma.

###### Lemma 3.3

Suppose that $n\geq 4$, $\ell_{2}=0$ and $k_{3}>0$. The $\kappa_{3}$-moves
establish a bijection from the set of pairs $(\Gamma,e)$ with $\Gamma$ a
labeled $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph of
combinatorial type $\bm{\tau}$ and $e$ an isolated $b$-edge, to the set of
triples $(\Delta,e^{\prime},v,w,\varepsilon)$ formed by a labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph $\Delta$ with
combinatorial type $\bm{\tau}+\bm{\kappa}_{3}$, an isolated $a$-edge
$e^{\prime}$ in $\Delta$, distinct integers $v,w\in[n]$ and some
$\varepsilon\in\\{-1,+1\\}$.

  * Proof.

The assumption that $\ell_{2}=0$ guarantees that every isolated $b$-edge is
adjacent to two isolated $a$-edges, and the fact that $n\geq 4$ guarantees
that these $a$-edges are distinct.

Now let $(\Gamma,e)$ be a pair formed by a labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph $\Gamma$ of
combinatorial type $\bm{\tau}$, and an isolated $b$-edge $e$ in $\Gamma$, say,
from vertex $v$ to vertex $w$. Let $v^{\prime}$ and $w^{\prime}$ be the other
extremities of the isolated $a$-edges adjacent to $v$ and $w$, respectively.
We associate with it the tuple $(\Delta,e^{\prime},v,w,\varepsilon)$ — and we
write $(\Gamma,e)\longmapsto(\Delta,e^{\prime},v,w,\varepsilon)$ — where
$\Delta^{\prime}$ is the weakly labeled graph obtained from $\Gamma$ by a
$(\kappa_{3},v\to w,v^{\prime},w^{\prime})$-move,
$\Delta=\operatorname{norm}(\Delta^{\prime})$, $e^{\prime}$ is the isolated
$a$-edge in $\Delta$ adjacent to the vertex labeled $v^{\prime}$ in
$\Delta^{\prime}$, $\varepsilon=1$ if $v^{\prime}<w^{\prime}$ and
$\varepsilon=-1$ if $v^{\prime}>w^{\prime}$.

Conversely, let $\Delta$ be a labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph with combinatorial
type $\bm{\tau}+\bm{\kappa}_{3}$, let $e^{\prime}$ be an isolated $a$-edge in
$\Delta$, connecting vertices $v^{\prime}$ and $w^{\prime}$, and let $v,w$ be
distinct integers in $[n]$. Let $\Delta^{\prime}$ be the weakly labeled graph
obtained from $\Delta$ by “making space for $v,w$”, that is, by incrementing
the labels of all the vertices greater than or equal to $\max(v,w)-1$ by 2
units, and those in $[\min(v,w),\max(v,w)-2]$ by 1 unit. Let then $\Gamma$ be
the graph obtained from $\Delta^{\prime}$ by deleting the $a$-edge
$e^{\prime}$; adding new vertices $v,w$ and a $b$-edge from $v$ to $w$; and
adding $a$-edges between $v$ and $\min(v^{\prime},w^{\prime})$ and between $w$
and $\max(v^{\prime},w^{\prime})$ if $\varepsilon=1$ — between $v$ and
$\max(v^{\prime},w^{\prime})$ and between $w$ and
$\min(v^{\prime},w^{\prime})$ if $\varepsilon=-1$. It is directly verified
that $\Gamma$ is properly labeled, of combinatorial type $\bm{\tau}$, and that
$(\Gamma,e)\longmapsto(\Delta,e^{\prime},v,w,\varepsilon)$. $\sqcap$$\sqcup$

##### Exceptional moves

Finally, we introduce three so-called _exceptional_ moves. The first can be
applied only to a weakly labeled version of the 1-vertex graph $\Delta_{1}$
that does not use label 1, turning it into $\Delta_{1}$ properly labeled.

The second can be applied only to a weakly labeled version of $\Delta_{3}$,
turning it into $\Delta_{1}$ (with its only vertex labeled 1). This move can
be seen as a degenerate version of a $\lambda_{2,2}$-move. Note that it
modifies the combinatorial type by the addition of $\bm{exc}=(-1,0,-1,-1,1)$,
the difference between the combinatorial types of $\Delta_{1}$ and
$\Delta_{3}$.

The last exceptional move can be applied to any weakly labeled version of
$\Delta_{2}$ different from the so-called preferred labeling (see Example
2.6), turning it to that preferred labeling.

###  3.2 Silhouette graphs

We can see the moves described in Section 3.1 as a rewriting system on weakly
labeled $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graphs, which we
show to be confluent (Section 3.3 below). The following definition will be
convenient: we say that a $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced
graph $\Gamma$ (weakly labeled or not) is a _silhouette graph_ if it is equal
to $\Delta_{1}$ or $\Delta_{2}$, or if it has combinatorial type
$(n,n/2,0,0,0)$ (where $n$ is a positive multiple of 6, see Proposition 2.4).
Observe that no move is defined on a silhouette graph of size at least 3,
whichever way it is weakly labeled.

Silhouette graphs play a foundational role in the recursive process for the
random generation of subgroups of $\mathsf{PSL}_{2}(\mathbb{Z})$ described in
Section 5. They also play a central role in [4].

###  3.3 Silhouetting a labeled $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically
reduced graph

In general, several moves can be applied to a weakly labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph $\Gamma$. Our next
proposition states that, however, the end result of a maximal sequence of
moves is independent of the choice of that maximal sequence.

###### Proposition 3.4

Let $\Gamma$ be a weakly labeled $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically
reduced graph $\Gamma$. If $\Delta$ and $\Delta^{\prime}$ are weakly labeled
graphs obtained from $\Gamma$, respectively, after maximal sequences of
$\lambda_{3}$-, $\lambda_{2,1}$-, $\lambda_{2,2}$\- and $\kappa_{3}$\- and
exceptional moves, then $\Delta=\Delta^{\prime}$.

  * Proof.

We proceed by induction on the number of vertices of $\Gamma$. The result is
immediate if no move is possible on $\Gamma$. If $\Gamma$ has 1 or 2 vertices,
either no move is possible, or only one exceptional move is possible, and the
result is again immediate.

Suppose now that $\Gamma$ has $n\geq 3$ vertices and that the sequences of
moves leading from $\Gamma$ to $\Delta$ and $\Delta^{\prime}$ start with the
same move (the same type of move, with the same parameters), taking $\Gamma$
to $\Gamma^{\prime}$. Since $\Gamma^{\prime}$ is a weakly labeled graph with
less than $n$ vertices, the announced result holds by induction.

Finally, suppose that the first moves from $\Gamma$ to $\Delta$ and $\Gamma$
to $\Delta^{\prime}$, say $m$ and $m^{\prime}$, are distinct. Note that since
$\Gamma$ has size at least 3, neither $m$ nor $m^{\prime}$ is an exceptional
move. Let $\Gamma_{1}$ (resp. $\Gamma^{\prime}_{1}$) be the weakly labeled
graph obtained from $\Gamma$ after the move $m$ (resp. $m^{\prime}$), so that
there exists a maximal sequence of moves from $\Gamma_{1}$ to $\Delta$ (resp.
$\Gamma^{\prime}_{1}$ to $\Delta^{\prime}$). Let us consider the possible
values of $m$ and $m^{\prime}$.

If $m=(\lambda_{3},v,w)$ and $m^{\prime}=(\lambda_{3},v^{\prime},w^{\prime})$,
there are two possibilities. If $\Gamma$ is a weakly labeled version of
$\Delta_{4}$ (so that $v=w^{\prime}$ and $v^{\prime}=w$), then $\Gamma_{1}$
and $\Gamma^{\prime}_{1}$ are weakly labeled versions of $\Delta_{1}$, so
$\Delta=\Gamma_{1}$, $\Delta^{\prime}=\Gamma^{\prime}_{1}$ and their
normalizations are equal. If instead $\Gamma$ is not a weakly labeled version
of $\Delta_{4}$, then $v,v^{\prime},w,w^{\prime}$ are pairwise distinct, and
the moves $m$ and $m^{\prime}$ _commute_ in the following sense: an
$m^{\prime}$-move is possible on $\Gamma_{1}$, leading to a weakly labeled
graph $\Gamma_{2}$; an $m$-move is possible on $\Gamma^{\prime}_{1}$, leading
to a weakly labeled graph $\Gamma^{\prime}_{2}$, and
$\Gamma_{2}=\Gamma^{\prime}_{2}$. Let $\Delta^{\prime\prime}$ be the graph
obtained from $\Gamma_{2}$ by a maximal sequence of moves. Since $\Gamma_{1}$
and $\Gamma^{\prime}_{1}$ are weakly labeled graphs with $n-1$ vertices, the
induction hypothesis shows that $\Delta=\Delta^{\prime\prime}$ and
$\Delta^{\prime}=\Delta^{\prime\prime}$, so that $\Delta=\Delta^{\prime}$.

We now verify that, similarly, other combinations of first moves $m$ and
$m^{\prime}$ also commute, leading to the same conclusion that the statement
in the proposition holds, except in a few degenerate cases that yield the same
conclusion by other arguments.

It is readily verified that any $\lambda_{3}$-move commutes with any
$\lambda_{2,1}$-move.

If $m=(\lambda_{3},v,w)$ and $m^{\prime}=(\lambda_{2,2},x\rightarrow
y,y^{\prime})$ (or $m^{\prime}=(\lambda_{2,2},x\leftarrow y,y^{\prime})$), we
again distinguish two cases. If $y^{\prime}=v$, then $y=w$ and $\Gamma$
consists of exactly three states $x,y,y^{\prime}$, with a $b$-edge between $x$
and $y$, an $a$-edge between $y$ and $y^{\prime}$, an $a$-loop at state $x$
and a $b$-loop at state $y^{\prime}$, see Figure 7.

Nw=5,Nh=5
(n0)(8.0,-3.0)$x$(n1)(33.0,-3.0)$y$(n2)(58.0,-3.0)$y^{\prime}$(n0,n1)$b$[AHnb=0](n1,n2)$a$[loopangle=180,loopdiam=6,AHnb=0](n0)$a$[loopangle=0,loopdiam=6](n2)$b$
Figure 7: Case where a $\lambda_{3}$\- and a $\lambda_{2,2}$-moves are
possible

Any maximal sequence of moves from $\Gamma$ leads to $\Delta_{1}$, where the
only vertex is labeled 1, and the announced statement holds. If instead
$y^{\prime}\neq v$, then $\Gamma$ has more than three states and the moves $m$
and $m^{\prime}$ commute.

If $m=(\lambda_{3},v,w)$ and $m^{\prime}=(\kappa_{3},x\rightarrow
y,x^{\prime},y^{\prime})$ (or $m^{\prime}=(\kappa_{3},x\leftarrow
y,x^{\prime},y^{\prime})$), there are again two possibilities. If $v\neq
x^{\prime},y^{\prime}$, then $m$ and $m^{\prime}$ modify disjoint parts of
$\Gamma$ and they clearly commute. If instead $v=x^{\prime}$, then $w=x$ — or
if, symmetrically, $v=y^{\prime}$ and $w=y$ —, see Figure 8, then a direct
verification shows the following: $m$ can be followed by a
$(\lambda_{2,2},w\rightarrow y,y^{\prime})$-move (or a
$(\lambda_{2,2},w\leftarrow y,y^{\prime})$-move, as the case may be), leading
to a graph where vertices $v,w,y$ have been deleted and $y^{\prime}$ carries
an $a$-loop; and $m^{\prime}$ can be followed by a
$(\lambda_{3},v,y^{\prime})$-move, leading to that same graph.

Nw=5,Nh=5
(n0)(8.0,-3.0)$v$(n1)(33.0,-3.0)$w$(n2)(58.0,-3.0)$y$(n3)(83.0,-3.0)$y^{\prime}$[loopangle=180,loopdiam=6](n0)$b$[AHnb=0](n0,n1)$a$(n1,n2)$b$[AHnb=0](n2,n3)$a$
Figure 8: Case where a $\lambda_{3}$\- and a $\kappa_{3}$-moves are possible

The only situation where two $\lambda_{2}$-moves do not commute is when they
are both $\lambda_{2,1}$-moves or both $\lambda_{2,2}$-moves, modifying
overlapping parts of $\Gamma$.

The first case arises if two $a$-loops sit on the same $b$-triangle, so that
$m=(\lambda_{2,1},v,w)$ and $m^{\prime}=(\lambda_{2,1},v^{\prime},w)$ are
possible, see Figure 9.

Nw=5,Nh=5
(n0)(8.0,-3.0)$v$(n1)(8.0,-19.0)$v^{\prime}$(n2)(25.0,-11.0)$w$(n3)(55.0,-3.0)$v$(n4)(55.0,-19.0)$v^{\prime}$(n5)(72.0,-11.0)$w$(n6)(92.0,-11.0)$w^{\prime}$[loopangle=180,loopdiam=6,AHnb=0](n0)$a$[loopangle=180,loopdiam=6,AHnb=0](n1)$a$[loopangle=0,loopdiam=6,AHnb=0](n2)$a$[loopangle=180,loopdiam=6,AHnb=0](n3)$a$[loopangle=180,loopdiam=6,AHnb=0](n4)$a$[ELside=r](n0,n1)$b$[ELside=r](n1,n2)$b$[ELside=r](n2,n0)$b$[ELside=r](n3,n4)$b$[ELside=r](n4,n5)$b$[ELside=r](n5,n3)$b$[AHnb=0](n5,n6)$a$
Figure 9: Cases where $\lambda_{2,1}$-moves interfere with each other

If $w$ also carries an $a$-loop (so that $\Gamma$ has 3 vertices), then
$\Delta=\Delta^{\prime}=\Delta_{1}$. Otherwise, an isolated $a$-edge connects
$w$ and a vertex $w^{\prime}$, distinct from $v,v^{\prime},w$, a
$(\lambda_{2,2},v^{\prime}\to w,w)$-move is possible (or some other
orientation of a $b$-edge between $v^{\prime}$ and $w$) after carrying out the
$m$-move and, together these two moves amount to deleting vertices $v$,
$v^{\prime}$ and $w$, and adding an $a$-loop at $w^{\prime}$.

In the second case, we have, say, $m=(\lambda_{2,2},x\rightarrow y,z)$ and
$m^{\prime}=(\lambda_{2,2},x^{\prime}\rightarrow y^{\prime},z^{\prime})$ (or
any other combination of directions for the $b$-edges between $x$ and $y$ on
one hand, and $x^{\prime}$ and $y^{\prime}$ on the other) satisfying
$y^{\prime}=z$ and $z^{\prime}=y$. Then $\Gamma$ has exactly 4 vertices, see
Figure 10,

Nw=5,Nh=5
(n0)(8.0,-3.0)$x$(n1)(33.0,-3.0)$y$(n2)(58.0,-3.0)$z$(n3)(83.0,-3.0)$x^{\prime}$[loopangle=180,loopdiam=6,AHnb=0](n0)$a$[loopangle=0,loopdiam=6,AHnb=0](n3)$a$(n0,n1)$b$[AHnb=0](n1,n2)$a$[ELside=r](n3,n2)$b$
Figure 10: Case where $\lambda_{2,2}$-moves interfere with each other

and applying either move to $\Gamma$ yields a weakly labeled version of
$\Delta_{3}$, on which one can only apply an exceptional move. It follows that
$\Delta=\Delta^{\prime}=\Delta_{1}$.

It is directly verified that any $\lambda_{2,1}$-move commutes with any
$\kappa_{3}$-move. Consider now the case where $m=(\lambda_{2,2},v\rightarrow
w,w^{\prime})$ and $m^{\prime}=(\kappa_{3},x\rightarrow
y,x^{\prime},y^{\prime})$ (or any other combination of directions for the
$b$-edges between $v$ and $w$, and between $x$ and $y$). If $w\neq x^{\prime}$
(and hence $w^{\prime}\neq x$), then $m$ and $m^{\prime}$ modify disjoint
parts of $\Gamma$ and clearly commute. If instead $w=x^{\prime}$ and
$w^{\prime}=x$ (see Figure 11),

Nw=5,Nh=5
(n0)(8.0,-3.0)$v$(n1)(33.0,-3.0)$w$(n2)(58.0,-3.0)$w^{\prime}$(n3)(83.0,-3.0)$y$(n4)(108.0,-3.0)$y^{\prime}$[loopangle=180,loopdiam=6,AHnb=0](n0)$a$(n0,n1)$b$[AHnb=0](n1,n2)$a$[ELside=r](n3,n2)$b$[AHnb=0](n3,n4)$a$
Figure 11: Case where a $\lambda_{2,2}$\- and a $\kappa_{3}$-moves are
possible

a direct verification shows that after applying either $m$ or $m^{\prime}$, a
$\lambda_{2,2}$-move can be applied (a $(\lambda_{2,2},x\rightarrow
y,y^{\prime})$-move can be applied to $\Gamma_{1}$ and a
$(\lambda_{2,2},v\rightarrow w,y^{\prime})$-move to $\Gamma^{\prime}_{1}$),
leading to the same weakly labeled graph with an $a$-loop at vertex
$y^{\prime}$: again $m$ and $m^{\prime}$ commute.

Similarly, suppose that $m=(\kappa_{3},v\rightarrow w,v^{\prime},w^{\prime})$
and $m^{\prime}=(\kappa_{3},x\rightarrow y,x^{\prime},y^{\prime})$ (or any
other combination of directions for the $b$-edges). We distinguish three
cases. If $x,x^{\prime},y,y^{\prime}\notin\\{v,v^{\prime},w,w^{\prime}\\}$,
then $m$ and $m^{\prime}$ clearly commute. If $(w,w^{\prime})=(x^{\prime},x)$
and $y\neq v^{\prime}$ (see Figure 12), then a $(\kappa_{3},x\rightarrow
y,v^{\prime},y^{\prime})$-move can be applied to $\Gamma_{1}$ and a
$(\kappa_{3},v\rightarrow w,v^{\prime},y^{\prime})$-move to
$\Gamma^{\prime}_{1}$, leading to the same weakly labeled graph (with an
$a$-edge between $v^{\prime}$ and $y^{\prime}$, and no vertices labeled
$x,y,v,w$).

Nw=5,Nh=5
(n0)(8.0,-3.0)$v^{\prime}$(n1)(33.0,-3.0)$v$(n2)(58.0,-3.0)$w$(n3)(83.0,-3.0)$w^{\prime}$(n4)(108.0,-3.0)$y$(n5)(133.0,-3.0)$y^{\prime}$[AHnb=0](n0,n1)$a$[AHnb=0](n2,n3)$a$[ELside=r](n2,n1)$b$(n3,n4)$b$[AHnb=0](n4,n5)$a$(n10)(58.0,-14.0)$v^{\prime}$(n11)(83.0,-14.0)$v$(n12)(83.0,-30.0)$w$(n13)(58.0,-30.0)$w^{\prime}$[AHnb=0](n10,n11)$a$[AHnb=0,ELside=r](n12,n13)$a$[ELside=r](n12,n11)$b$(n13,n10)$b$
Figure 12: Cases where two $\kappa_{3}$-moves are possible

If now $(w,w^{\prime})=(x^{\prime},x)$ and $y=v^{\prime}$ (so that
$y^{\prime}=v$), then $\Gamma$ has exactly four vertices, both $\Gamma_{1}$
and $\Gamma^{\prime}_{1}$ are weak labelings of $\Delta_{2}$, on which only an
exceptional move is defined, so that $\Delta=\Delta^{\prime}$.

This concludes the proof of the proposition. $\sqcap$$\sqcup$

If $\Gamma$ is a labeled $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced
graph, we define the _silhouette_ $\mathsf{silh}(\Gamma)$ of $\Gamma$ to be
the labeled graph resulting from the application of a maximal sequence of
moves, followed by a normalization: Proposition 3.4 guarantees that
$\mathsf{silh}(\Gamma)$ is well defined.

###### Example 3.5

Consider the three (labeled) Stallings graphs in Figure 1. The first is equal
to its own silhouette, and is also equal to the silhouette of the third. The
silhouette of the second graph is $\Delta_{2}$ (with its preferred labeling).
$\sqcap$$\sqcup$

The silhouetting operation preserves some important algebraic information
about a subgroup, namely the free rank component of its isomorphism type.

###### Proposition 3.6

Let $H$ be a $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced subgroup of
$\mathsf{PSL}_{2}(\mathbb{Z})$, with Stallings graph $\Gamma$ and isomorphism
type $(\ell_{2},\ell_{3},r)$. If $\mathsf{silh}(\Gamma)$ has isomorphism type
$(\ell_{2}^{\prime},\ell_{3}^{\prime},r^{\prime})$, then $r=r^{\prime}$. In
particular $\mathsf{silh}(\Gamma)=\Delta_{1}$ (respectively, $\Delta_{2}$) if
and only if $r=0$ (respectively, $r=1$).

  * Proof.

Let $\bm{\tau}$ be the combinatorial type of $\Gamma$. Proposition 2.5 shows
that the free rank $r$ in the isomorphism type of $H$ is a function of
$\bm{\tau}$; more precisely, if $\bm{\tau}=(n,k_{2},k_{3},\ell_{2},\ell_{3})$,
then $6(r-1)=n-2k_{3}-3\ell_{2}-4\ell_{3}=\varphi(\bm{\tau})$, and we observe
that $\varphi$ is a linear map.

By construction, $\mathsf{silh}(\Gamma)$ is obtained from $\Gamma$ by a
succession of $\lambda_{3}$-, $\lambda_{2,1}$-, $\lambda_{2,2}$-,
$\kappa_{3}$-moves and maybe one exceptional move (followed by normalization).
Each of these moves modifies the combinatorial type by adding to it the vector
$\bm{\lambda}_{3}$, $\bm{\lambda}_{2,1}$, $\bm{\lambda}_{2,2}$,
$\bm{\kappa}_{3}$ or $\bm{exc}$. Every one of these vectors lies in the kernel
of $\varphi$, so the free rank component of the isomorphism types of $\Gamma$
and $\mathsf{silh}(\Gamma)$ coincide.

It is immediate that this free rank component is 0 for $\Delta_{1}$, 1 for
$\Delta_{2}$ and $1+n/6\geq 2$ for each silhouette graph of size $n>2$. The
proposition follows immediately. $\sqcap$$\sqcup$

##  4 Counting subgroups by isomorphism and by combinatorial type

Our aim in this section is to count subgroups of a given size, under some
additional constraint: with a fixed isomorphism type or with a fixed
combinatorial type. Since each subgroup is uniquely represented by its
Stallings graph, _i.e._ , by a $\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graph,
this is equivalent to counting these graphs (up to isomorphism).

As noted in Section 2.3, an $n$-vertex $\mathsf{PSL}_{2}(\mathbb{Z})$-reduced
graph admits exactly $n!$ distinct labelings. As a result, our strategy to
count $n$-vertex $\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graphs will be to
count labeled $n$-vertex $\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graphs, and
then divide that count by $n!$. The same applies for the counting of
$n$-vertex $\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graphs of a particular
combinatorial type, or for $n$-vertex rooted
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graphs. Note that there is
no such easy correlation between the number of labeled and unlabeled (non-
rooted) cyclically reduced graphs, as counting is perturbed by the existence
of symmetries (automorphisms).

Thus our task reduces to counting labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graphs. It further reduces to counting
labeled $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graphs, as we
explain below.

###  4.1 Reduction to the count of labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graphs

If $\bm{\tau}=(n,k_{2},k_{3},\ell_{2},\ell_{3})$ is a tuple of integers, we
let $H(\bm{\tau})$ (respectively, $L(\bm{\tau})$, $s(\bm{\tau})$) be the
number of subgroups (respectively, labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graphs, labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graphs) of combinatorial
type $\bm{\tau}$.

###### Example 4.1

In view of Example 2.3, the non-zero values of $H$, $L$ and $s$ for tuples
$(n,k_{2},k_{3},\ell_{2},\ell_{3})$ where $n=1,2$ are as follows:

$\bullet$ $H(\bm{\tau})=L(\bm{\tau})=1$ for
$\bm{\tau}=(1,0,0,1,1),(1,0,0,1,0),(1,0,0,0,1)$ and $s(\bm{\tau})=1$ for
$\bm{\tau}=(1,0,0,1,1)$;

$\bullet$ $L(\bm{\tau})=4$ and $H(\bm{\tau})=s(\bm{\tau})=2$ for
$\bm{\tau}=(2,1,1,0,0),(2,0,1,2,0)$;

$\bullet$ $L(\bm{\tau})=2$ and $H(\bm{\tau})=s(\bm{\tau})=1$ for
$\bm{\tau}=(2,1,0,0,2)$;

$\bullet$ $L(\bm{\tau})=2$ and $H(\bm{\tau})=1$ for
$\bm{\tau}=(2,0,1,1,0),(2,1,0,0,1)$; $\sqcap$$\sqcup$

We first establish the connection between the parameters $H(\bm{\tau})$,
$L(\bm{\tau})$ and $s(\bm{\tau})$.

###### Proposition 4.2

Let $\bm{\tau}=(n,k_{2},k_{3},\ell_{2},\ell_{3})$ be a combinatorial type with
$n\geq 2$. The numbers $H(\bm{\tau})$, $L(\bm{\tau})$ and $s(\bm{\tau})$,
respectively of subgroups, labeled $\mathsf{PSL}_{2}(\mathbb{Z})$-reduced
graphs and labeled $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graphs of
combinatorial type $\bm{\tau}$ are related as follows.

$L(\bm{\tau})=n\cdot s(n,k_{2},k_{3},\ell_{2},\ell_{3})+(\ell_{2}+1)\cdot
s(n,k_{2},k_{3},\ell_{2}+1,\ell_{3})+(\ell_{3}+1)\cdot
s(n,k_{2},k_{3},\ell_{2},\ell_{3}+1)$
$H(\bm{\tau})=\frac{1}{n!}\,L(\bm{\tau}).$

  * Proof.

Let $(\Gamma,v)$ be a $\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graph with $n\geq
2$ vertices, such that $\Gamma$ is not
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced. Then $v$ is adjacent to an
$a$-edge but no $b$-edge, or the opposite. Adding a $b$-loop at $v$ in the
first case, an $a$-loop in the second case, yields a rooted
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph $(\Gamma^{\prime},v)$.
Conversely, if $\Gamma^{\prime}$ is $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically
reduced, we get $\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graphs either by
rooting $\Gamma^{\prime}$ at any one of its vertices, or by rooting
$\Gamma^{\prime}$ at a vertex that carries a loop and deleting that loop. The
first equality follows directly.

The second equality follows from the first since a size $n$
$\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graph has $n!$ distinct labelings (see
Section 2.3). $\sqcap$$\sqcup$

Based on Proposition 2.5, which relates the isomorphism type and the
combinatorial type of a subgroup, we get the following statement.

###### Proposition 4.3

Let $\bm{\sigma}=(\ell_{2},\ell_{3},r)$ be an isomorphism type and let
$k_{2}=\frac{1}{2}(n-\ell_{2})$.

The number of $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced subgroups of
size $n$ and isomorphism type $\bm{\sigma}$ is $n\cdot
s(n,k_{2},k_{3},\ell_{2},\ell_{3})$, where
$k_{3}=\frac{1}{2}(n-3\ell_{2}-4\ell_{3}-6r+6)$.

The number of non-$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced subgroups
of size $n$ and isomorphism type $\bm{\sigma}$, where the base vertex is
adjacent to an $a$-edge, is $(\ell_{3}+1)\cdot
s(n,k_{2},k_{3}^{\prime},\ell_{2},\ell_{3}+1)$, where
$k_{3}^{\prime}=\frac{1}{2}(n-3\ell_{2}-4\ell_{3}-6r+2)$.

The number of non-$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced subgroups
of size $n$ and isomorphism type $\bm{\sigma}$, where the base vertex is
adjacent to a $b$-edge, is $(\ell_{2}+1)\cdot
s(n,k_{2},k_{3}^{\prime\prime},\ell_{2}+1,\ell_{3})$, where
$k_{3}^{\prime\prime}=\frac{1}{2}(n-3\ell_{2}-4\ell_{3}-6r+4)$.

Propositions 4.2 and 4.3 effectively reduce the counting of subgroups to the
counting of labeled $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graphs
of a given combinatorial type, which is investigated in Section 4.2 below.

###  4.2 Counting labeled $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced
graphs

Let $\bm{\tau}=(n,k_{2},k_{3},\ell_{2},\ell_{3})$ be a combinatorial type. We
give (multi-)recurrence relations to compute $s(\bm{\tau})$ when $n>2$. For
$n\leq 2$, see Example 4.1.

The bijections established in Lemmas 3.1, 3.2 and 3.3 show the following.

###### Proposition 4.4

Let $\bm{\tau}=(n,k_{2},k_{3},\ell_{2},\ell_{3})$ be a combinatorial type such
that $n\geq 2$ and $\ell_{3}>0$. If $\Delta$ has combinatorial type
$\bm{\tau}+\bm{\lambda}_{3}$, then the set of labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graphs $\Gamma$ of
combinatorial type $\bm{\tau}$, such that a $\lambda_{3}$-move takes $\Gamma$
to $\Delta$, has $\frac{n\cdot(\ell_{2}+1)}{\ell_{3}}$ elements. More
generally,

$\displaystyle s(\bm{\tau})$
$\displaystyle=\frac{n\cdot(\ell_{2}+1)}{\ell_{3}}\
s(\bm{\tau}+\bm{\lambda}_{3}),\textrm{ that is:}$ $\displaystyle
s(n,k_{2},k_{3},\ell_{2},\ell_{3})$
$\displaystyle=\frac{n\cdot(\ell_{2}+1)}{\ell_{3}}\
s(n-1,k_{2}-1,k_{3},\ell_{2}+1,\ell_{3}-1).$ (1)

###### Proposition 4.5

Let $\bm{\tau}=(n,k_{2},k_{3},\ell_{2},\ell_{3})$ be a combinatorial type such
that $n\geq 3$ and $\ell_{2}>0$. If $\Delta$ has combinatorial type
$\bm{\tau}+\bm{\lambda}_{2,1}$ (resp. $\bm{\tau}+\bm{\lambda}_{2,2}$), then
the set of labeled $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graphs
$\Gamma$ of combinatorial type $\bm{\tau}$, such that a $\lambda_{2,1}$-move
(resp. a $\lambda_{2,2}$-move) takes $\Gamma$ to $\Delta$, has
$\frac{n\cdot(k_{3}+1)}{\ell_{2}}$ (resp. $2n\cdot(n-1)$) elements. More
generally,

$\displaystyle s(\bm{\tau})\enspace=\enspace$
$\displaystyle\frac{n\cdot(k_{3}+1)}{\ell_{2}}\
s(\bm{\tau}+\bm{\lambda}_{2,1})$ $\displaystyle+2n\cdot(n-1)\
s(\bm{\tau}+\bm{\lambda}_{2,2}),\textrm{ that is:}$ $\displaystyle
s(n,k_{2},k_{3},\ell_{2},\ell_{3})\enspace=\enspace$
$\displaystyle\frac{n\cdot(k_{3}+1)}{\ell_{2}}\
s(n-1,k_{2},k_{3}+1,\ell_{2}-1,\ell_{3})$ $\displaystyle+2n\cdot(n-1)\
s(n-2,k_{2}-1,k_{3}-1,\ell_{2},\ell_{3}).$ (2)

###### Proposition 4.6

Let $\bm{\tau}=(n,k_{2},k_{3},\ell_{2},\ell_{3})$ be a combinatorial type such
that $n\geq 4$, $\ell_{2}=0$ and $k_{3}>0$. If $\Delta$ has combinatorial type
$\bm{\tau}+\bm{\kappa}_{3}$, then the set of labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graphs $\Gamma$ of
combinatorial type $\bm{\tau}$, such that a $\kappa_{3}$-move takes $\Gamma$
to $\Delta$, has $\frac{2n\cdot(n-1)(k_{2}-1)}{k_{3}}$ elements. More
generally, if $\ell_{2}=0$, we have

$\displaystyle s(\bm{\tau})\enspace=\enspace$ $\displaystyle 2\
\frac{n\cdot(n-1)(k_{2}-1)}{k_{3}}\ s(\bm{\tau}+\bm{\kappa}_{3}),\textrm{ that
is:}$ $\displaystyle s(n,k_{2},k_{3},0,\ell_{3})\enspace=\enspace$
$\displaystyle 2\ \frac{n\cdot(n-1)(k_{2}-1)}{k_{3}}\
s(n-2,k_{2}-1,k_{3}-1,0,\ell_{3}).$ (3)

We can use Equations (1), (2) and (3) to compute the coefficient
$s(n,k_{2},k_{3},\ell_{2},\ell_{3})$, where $n\geq 3$: if one of $k_{3}$,
$\ell_{2}$ or $\ell_{3}$ is greater than zero, we can apply at least one of
these equations, thus reducing the first argument of the coefficients to
compute by 1 or 2.

More precisely, one may first iterate the use of Equation (1) until $n\leq 2$
or $\ell_{3}=0$. One can then use repeatedly Equation (2), thus reducing the
computation of $s(\bm{\tau})$ to the computation of a number of smaller
coefficients, until $n\leq 2$ or $\ell_{2}=0$ (note that Equation (2) never
increases $\ell_{3}$). Finally, if $n\geq 3$ and $\ell_{2}=\ell_{3}=0$, then
in fact $n\geq 4$ and one can use repeatedly Equation (3) until $n\leq 2$ or
$k_{3}=\ell_{2}=\ell_{3}=0$. The computation of the coefficients when $n\leq
2$ was done in Example 4.1. As for the coefficients of the form
$s(n,k_{2},0,0,0)$ ($n>2$), we note that they count the size $n$ labeled
silhouette graphs.

The latter numbers were computed in [3, Appendices A.3 and A.4] (see also the
computation by Stothers [23] of the number of finite index, free subgroups of
$\mathsf{PSL}_{2}(\mathbb{Z})$, that is, of subgroups whose Stallings graph is
a silhouette graph of size at least 3).

###### Proposition 4.7

Let $t_{2}$ (respectively, $t_{3}$) be given, for $n\geq 1$, by444What is
written $t_{2}(2n)$ (respectively, $t_{3}(3n)$, $s(6n,3n,0,0)$) here, is
written $t_{2}^{(0)}(2n)$ (respectively, $t_{3}^{\textsf{fr-fi}}(3n)$,
$g_{\textsf{pr}}^{\textsf{fr-fi}}(6n)$) in [3].

$\displaystyle t_{2}(2n)=\frac{(2n)!}{2^{n}\,n!}=\prod_{1\leq i\leq
n}(2i-1),\quad\textrm{and }$ $\displaystyle
t_{3}(3n)=\frac{(3n)!}{3^{n}\,n!}=\prod_{1\leq i\leq n}(3i-1)(3i-2).$

Then the number $s(6n,3n,0,0,0)$ of size $6n$ labeled silhouette graphs
($n\geq 1$) satisfies the following recurrence relation:

$\displaystyle s(6n,3n,0,0,0)$
$\displaystyle=t_{2}(6n)\,t_{3}(6n)-\sum_{m=1}^{n-1}t_{2}(6m)\,t_{3}(6m)\,s\big{(}6(n-m),3(n-m),0,0,0\big{)}.$

##  5 Random generation of subgroups of $\mathsf{PSL}_{2}(\mathbb{Z})$

Our objective in this section is to produce an algorithm which generates
uniformly at random subgroups of $\mathsf{PSL}_{2}(\mathbb{Z})$ with a given
size and isomorphism type.

As we saw in Example 4.1, there are exactly four size 1 subgroups, with
pairwise distinct combinatorial and isomorphism type: the trivial subgroup,
the subgroups generated by $a$ and $b$, respectively, and
$\mathsf{PSL}_{2}(\mathbb{Z})$ itself. We now concentrate on generating
subgroups of size at least $2$, and we assume that the parameters
$L(\bm{\tau})$ and $s(\bm{\tau})$ have been pre-computed for all types of
sufficient size.

Like in Section 4, generating uniformly at random a subgroup of a given
combinatorial or isomorphism type reduces to randomly generating a labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graph of a given combinatorial type
and, before that, to randomly generating a labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph of a given type.
Indeed, the label-forgetting map, from the set of labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graphs of combinatorial type
$\bm{\tau}=(n,k_{2},k_{3},\ell_{2},\ell_{3})$ to the set of
$\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graphs of type $\bm{\tau}$, is such
that the inverse image of each $\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graph of
type $\bm{\tau}$ contains exactly $n!$ elements (see the discussion at the end
of Section 2.3).

As we saw in Proposition 2.5, the isomorphism class of a
$\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graph is determined by its
combinatorial type, and a given size and isomorphism type arises for a finite
number of combinatorial types only. As a result, we only need to randomly
generate a $\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graph with a given
combinatorial type, and this starts with randomly generating a labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graphs of a given
combinatorial type.

We first deal with the particular case of labeled silhouette graphs, then
proceed to the general case of labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graphs and, finally, to
labeled $\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graphs.

###  5.1 Random labeled silhouette graphs

Let $n$ be a positive multiple of $6$. The procedure
$\mathtt{random\\_silhouette\\_graph}(n)$ to generate a size $n$ labeled
silhouette graph, summarized below, is well known (see [3] for instance). If
$s$ is a permutation on $n$ elements, we denote by $\mathsf{shuffle}(s)$ the
permutation $t^{-1}st$ where $t$ is a random permutation on $n$ elements.

1

2

3do

4 $s_{2}=\mathsf{shuffle}((1\ 2)\,(3\ 4)\ldots(n-1\ n))$

5 $s_{3}=\mathsf{shuffle}((1\ 2\ 3)\,(4\ 5\ 6)\ldots(n-2\ n-1\ n))$

6

7while  _The graph $\Gamma$ determined by $s_{2}$ and $s_{3}$ is not connected
_

Algorithm 1 $\mathtt{random\\_silhouette\\_graph}(n)$

Note that the random permutations $s_{2}$ and $s_{3}$ may well determine a
disconnected graph, but the proof of [3, Proposition 8.18] shows that this
happens with vanishing probability (precisely: with probability
$\frac{5}{36}n^{-1}+o(n^{-1})$). Therefore this algorithm (a rejection
algorithm) produces a silhouette graph after $k$ iterations, with
$\mathbb{E}(k)\sim 1$.

###  5.2 Random $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graphs

We exploit, again, the bijections established in Section 3.1, which we already
used to derive the recurrence relations in Section 4.2. This yields the
following algorithm, called
$\mathtt{random\\_cyclically\\_reduced\\_graph}(\bm{\tau})$, to randomly
generate a $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph of
combinatorial type $(\bm{\tau})$.

We use the following notation: if $v$ is an integer, $\mathsf{shift}_{v}$ is
the map defined on integers by $\mathsf{shift}_{v}(x)=x$ if $x<v$ and
$\mathsf{shift}_{v}(x)=x+1$ if $x\geq v$; if $v,w$ are distinct integers,
$\mathsf{shift}_{v,w}$ is the map defined on integers by
$\mathsf{shift}_{v,w}(x)=x$ if $x<\min(v,w)$, $\mathsf{shift}_{v,w}(x)=x+1$ if
$\min(v,w)\leq x<\max(v,w)-1$, and $\mathsf{shift}_{v,w}(x)=x+2$ if
$x\geq\max(v,w)-1$. Note that $\mathsf{shift}_{v}$ “pushes” all integers
greater than or equal to $v$ by one unit, so that the range of
$\mathsf{shift}_{v}$ misses $v$; similarly, the range of
$\mathsf{shift}_{v,w}$ misses $v$ and $w$.

We extend this notation to any graph $\Delta$ labeled by integers: if $v$ is
an integer, the graph $\mathsf{shift}_{v}(\Delta)$ is a relabeling of the
vertices of $\Delta$ using $\mathsf{shift}_{v}$ on each vertex label; if $v$
and $w$ are two distinct integers, the graph $\mathsf{shift}_{v,w}(\Delta)$ is
a relabeling of the vertices of $\Delta$ using $\mathsf{shift}_{v,w}$ on each
vertex label.

1

2if  _$\bm{\tau}=(1,0,0,1,1)$_ then

3 return the unique labeled $\Delta_{1}$

4if  _$\bm{\tau}=(2,1,1,0,0)$_ then

5 return any one of the two labeled $\Delta_{2}$

6if  _$\bm{\tau}=(2,0,1,2,0)$_ then

7 return any one of the two labeled $\Delta_{3}$

8if  _$\bm{\tau}=(1,0,0,1,1)$_ then

9 return the unique labeled $\Delta_{4}$

// At this stage $n$ is necessarily greater than 2

10 if  _$\bm{\tau}=(n,k_{2},k_{3},\ell_{2},\ell_{3})$ and $\ell_{3}>0$_ then

11
$\Delta=\mathtt{random\\_cyclically\\_reduced\\_graph}(\bm{\tau}+\bm{\lambda}_{3})$

12 $w=$ uniform random vertex with an $a$-loop $\ell^{\prime}$ in $\Delta$

13 $v=$ uniform random integer in $\\{1,\dots,n\\}$

14 return $\Gamma$ constructed from $\Delta$ by relabeling its vertices using
$\mathsf{shift}_{v}$, removing the $a$-loop $\ell^{\prime}$ at
$\mathsf{shift}_{v}(w)$, adding a new vertex labeled $v$ and a $b$-loop at
$v$, and adding an $a$-edge between $v$ and $\mathsf{shift}_{v}(w)$

15

16if  _$\bm{\tau}=(n,k_{2},k_{3},\ell_{2},0)$ and $\ell_{2}>0$_ then

17 $x=$ uniform integer in $[s(n,k_{2},k_{3},\ell_{2},0)]$

18 if  _$x\leq n\cdot(k_{3}+1)\cdot s(n-1,k_{2},k_{3}+1,\ell_{2}-1,0)$_ then

19
$\Delta=\mathtt{random\\_cyclically\\_reduced\\_graph}(\bm{\tau}+\bm{\lambda}_{2,1})$

20 $(w\xrightarrow{b}w^{\prime})=$ uniform random isolated $b$-edge in
$\Delta$

21 $v=$ uniform random integer in $\\{1,\dots,n\\}$

22 return $\Gamma$ constructed from $\Delta$ by relabeling its vertices using
$\mathsf{shift}_{v}$, adding a new vertex labeled $v$ and an $a$-loop at $v$,
and adding $b$-edges from $\mathsf{shift}_{v}(w^{\prime})$ to $v$ and from $v$
to $\mathsf{shift}_{v}(w)$

23

24 else

25
$\Delta=\mathtt{random\\_cyclically\\_reduced\\_graph}(\bm{\tau}+\bm{\lambda}_{2,2})$

26 $w^{\prime}=$ uniform random vertex with a $a$-loop $\ell^{\prime}$ in
$\Delta$

27 $(v,w)=$ uniform random pair of distinct integers in $\\{1,\dots,n\\}$

28 return $\Gamma$ constructed from $\Delta$ by removing the $a$-loop
$\ell^{\prime}$, relabeling the vertices of $\Delta$ using
$\mathsf{shift}_{v,w}$, adding new vertices labeled $v$ and $w$, an $a$-edge
between $w$ and $\mathsf{shift}_{v,w}(w^{\prime})$, a $b$-edge between $v$ and
$w$ (choosing orientation uniformly at random) and an $a$-loop at $v$

29

30

31if  _$\bm{\tau}=(n,k_{2},k_{3},0,0)$ and $k_{3}>0$_ then

32
$\Delta=\mathtt{random\\_cyclically\\_reduced\\_graph}(\bm{\tau}+\bm{\kappa}_{3})$

33 $(v^{\prime}\stackrel{{\scriptstyle\begin{subarray}{c}\\\\[-2.0pt]
a\end{subarray}}}{{-}}w^{\prime})=$ uniform random isolated $a$-edge in
$\Delta$

34 $(v,w)=$ uniform random pair of distinct integers in $\\{1,\dots,n\\}$

35 return $\Gamma$ constructed from $\Delta$ by removing the the $a$-edge
$e^{\prime}$, relabeling the vertices using $\mathsf{shift}_{v,w}$, adding a
$b$-edge between $v$ and $w$ (choosing its orientation uniformly at random)
and $a$-edges between $v$ and $\mathsf{shift}_{v,w}(v^{\prime})$, and between
$w$ and $\mathsf{shift}_{v,w}(w^{\prime})$, respectively

36

// At this stage $\ell_{2}=\ell_{3}=k_{3}=0$

37 return $\mathtt{random\\_silhouette\\_graph}(n)$

Algorithm 2 $\mathtt{random\\_cyclically\\_reduced\\_graph}(n)$

###### Theorem 5.1

Algorithm $\mathtt{random\\_cyclically\\_reduced\\_graph}$, described above,
produces, on input a combinatorial type $\bm{\tau}$, a random
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph of type $\bm{\tau}$.

  * Proof.

Let $\bm{\tau}=(n,k_{2},k_{3},\ell_{2},\ell_{3})$. We proceed by induction on
$n$. Note that Algorithm $\mathtt{random\\_cyclically\\_reduced\\_graph}$ is
recursive, and that, for any $\bm{\tau}$, only one of the outer if statements
(Lines 2, 2, 2, 2, 2, 2 and 2) holds. Moreover, the algorithm stops
immediately after the if statements of Lines 2, 2, 2, 2, and strictly
decreases the value of $n$ for the other ones. As a result, Algorithm
$\mathtt{random\\_cyclically\\_reduced\\_graph}$ stops on any input
$\bm{\tau}$ (which is a proper combinatorial type).

The statement of the theorem holds trivially if $n\leq 2$. Let us now assume
that $n>2$.

If $\ell_{3}>0$ (that is, if the condition of Line 2 holds), Lemma 3.1
describes a bijection between the set of pairs $(\Gamma,\ell)$, where $\Gamma$
is a $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph of combinatorial
type $\bm{\tau}$ and $\ell$ is a $b$-loop in $\Gamma$, and the set of triples
$(\Delta,\ell^{\prime},v)$ where $\Delta$ is a
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph of type
$\bm{\tau}+\bm{\lambda}_{3}$, $\ell^{\prime}$ is an $a$-loop in $\Delta$ and
$v\in[n]$. This bijection, between two finite sets, preserves uniformity. Thus
the first steps in this case (selecting uniformly at random $\Delta$,
$\ell^{\prime}$ and $v$) translate into the selection, uniformly at random, of
a pair $(\Gamma,\ell)$ where $\Gamma$ has combinatorial type $\bm{\tau}$ and
$\ell$ is one of the $\ell_{3}$ $b$-loops in $\Gamma$ (a number that depends
on $\bm{\tau}$ but not on $\Gamma$). Forgetting the $\ell$-component of this
pair yields a randomly chosen $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically
reduced graph of type $\bm{\tau}$.

The reasoning is exactly similar if the condition of Line 2 holds, relying on
Lemma 3.3.

For the condition of Line 2, we need to handle the two options, corresponding
to $\lambda_{2,1}$\- and $\lambda_{2,2}$-moves. The set of pairs
$(\Gamma,\ell)$, where $\Gamma$ is a $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically
reduced graph of combinatorial type $\bm{\tau}$ and $\ell$ is an $a$-loop in
$\Gamma$, is partitioned in two subsets $S_{1}$ and $S_{2}$: $(\Gamma,\ell)\in
S_{1}$ if $\ell$ is adjacent to a $b$-triangle, and $(\Gamma,\ell)\in S_{2}$
if $\ell$ is adjacent to an isolated $b$-edge. Lemma 3.2 describes the sets
$S_{1}$ and $S_{2}$ are in bijection with. This determines the cardinalities
of $S_{1}$ and $S_{2}$, which correspond precisely to the probability tested
at Line 2. The reasoning is then identical to Lines 2 and 2.

Finally, if none of these conditions holds (so that $\bm{\tau}$ is the
combinatorial type of a silhouette graph), the algorithm uses the return
command on Line 2 to produce a random silhouette graph, see Section 5.1.
$\sqcap$$\sqcup$

###  5.3 Random subgroups of $\mathsf{PSL}_{2}(\mathbb{Z})$

We show how to randomly generate subgroups of a given combinatorial type, and
then of a given size and isomorphism type.

#### Random generation for a given combinatorial type

Let $\bm{\tau}=(n,k_{2},k_{3},\ell_{2},\ell_{3})$ be a combinatorial type. The
formula for the number $L(\bm{\tau})$ of labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graphs of type $\bm{\tau}$, in
Proposition 4.2 above, suggests the following algorithm to draw uniformly at
random a labeled $\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graph of combinatorial
type $\bm{\tau}$.

  * (1)

Draw an integer $0\leq p<L(\bm{\tau})$ uniformly at random.

  * (2)

If $p<n\cdot s(\bm{\tau})$ and $q$ is the quotient of $p$ by $s(\bm{\tau})$
(so that $0\leq q<n$), draw uniformly at random a labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph with combinatorial
type $\bm{\tau}$ and root it at vertex $q+1$.

  * (3)

If $n\cdot s(\bm{\tau})\leq p<n\cdot s(\bm{\tau})+(\ell_{2}+1)\cdot
s(n,k_{2},k_{3},\ell_{2}+1,\ell_{3})$ and $q$ is the quotient of $p-n\cdot
s(\bm{\tau})$ by $s(n,k_{2},k_{3},\ell_{2}+1,\ell_{3})$ (so that $0\leq
q\leq\ell_{2}$), draw uniformly at random a labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph with combinatorial
type $(n,k_{2},k_{3},\ell_{2}+1,\ell_{3})$ (as in Section 5.2), delete the
$(q+1)$st $a$-loop (following the order of vertex labels) and root the graph
at the vertex where that loop used to be.

  * (4)

If $n\cdot s(\bm{\tau})+(\ell_{2}+1)\cdot
s(n,k_{2},k_{3},\ell_{2}+1,\ell_{3})\leq p$ and $q$ is the quotient of
$p-n\cdot s(\bm{\tau})-(\ell_{2}+1)\cdot s(n,k_{2},k_{3},\ell_{2}+1,\ell_{3})$
by $s(n,k_{2},k_{3},\ell_{2},\ell_{3}+1)$ (so that $0\leq q\leq\ell_{3}$),
draw uniformly at random a labeled $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically
reduced graph with combinatorial type $(n,k_{2},k_{3},\ell_{2},\ell_{3}+1)$
(as in Section 5.2), delete the $(q+1)$st $b$-loop (following the order of
vertex labels) and root the graph at the vertex where that loop used to be.

To draw uniformly at random a subgroup of combinatorial type $\bm{\tau}$, we
first draw a labeled $\mathsf{PSL}_{2}(\mathbb{Z})$-reduced graph of type
$\bm{\tau}$, and then forget the labeling.

###### Remark 5.2

To draw uniformly at random a $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically
reduced subgroup of combinatorial type $\bm{\tau}$, the algorithm is modified
as follows: in step (1), one draws an integer $p$ between 0 and $n\cdot
s(\bm{\tau})-1$; one then applies only step (2). $\sqcap$$\sqcup$

#### Random generation for a given size and isomorphism type

Now let $n$ be a positive integer and let $\bm{\sigma}=(\ell_{2},\ell_{3},r)$
be an isomorphism type. Let $k_{2}=\frac{1}{2}(n-\ell_{2})$,
$k_{3}=\frac{1}{2}(n-3\ell_{2}-4\ell_{3}-6r+6)$,
$k_{3}^{\prime}=\frac{1}{2}(n-3\ell_{2}-4\ell_{3}-6r+2)$ and
$k_{3}^{\prime\prime}=\frac{1}{2}(n-3\ell_{2}-4\ell_{3}-6r+4)$.

Proposition 4.3 suggests the following algorithm to draw uniformly at random a
subgroup of size $n$ and isomorphism type $\bm{\sigma}$.

  * (1)

Draw uniformly at random an integer $p$ between 0 and

$n\cdot s(n,k_{2},k_{3},\ell_{2},\ell_{3})+(\ell_{3}+1)\cdot
s(n,k_{2},k_{3}^{\prime},\ell_{2},\ell_{3}+1)+(\ell_{2}+1)\cdot
s(n,k_{2},k_{3}^{\prime\prime},\ell_{2}+1,\ell_{3})-1.$

  * (2)

If $p<n\cdot s(n,k_{2},k_{3},\ell_{2},\ell_{3})$, draw uniformly at random a
labeled rooted $\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph with
combinatorial type $(n,k_{2},k_{3},\ell_{2},\ell_{3})$.

  * (3)

If $n\cdot s(\bm{\tau})\leq p<n\cdot s(\bm{\tau})+(\ell_{3}+1)\cdot
s(n,k_{2},k_{3}^{\prime},\ell_{2},\ell_{3}+1)$ and $q$ is the quotient of
$p-n\cdot s(\bm{\tau})$ by $s(n,k_{2},k_{3}^{\prime},\ell_{2},\ell_{3}+1)$ (so
that $0\leq q\leq\ell_{3}$), draw uniformly at random a labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph with combinatorial
type $(n,k_{2},k_{3}^{\prime},\ell_{2},\ell_{3}+1)$, delete the $(q+1)$st
$b$-loop (following the order of vertex labels) and root the graph at the
vertex where that loop used to be.

  * (4)

If $n\cdot s(\bm{\tau})+(\ell_{3}+1)\cdot
s(n,k_{2},k_{3}^{\prime},\ell_{2},\ell_{3}+1)\leq p$ and $q$ is the quotient
of $p-n\cdot s(\bm{\tau})-(\ell_{3}+1)\cdot
s(n,k_{2},k_{3}^{\prime},\ell_{2},\ell_{3}+1)$ by
$s(n,k_{2},k_{3}^{\prime\prime},\ell_{2}+1,\ell_{3})$ (so that $0\leq
q\leq\ell_{2}$), draw uniformly at random a labeled
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced graph with combinatorial
type $(n,k_{2},k_{3},\ell_{2}+1,\ell_{3})$, delete the $(q+1)$st $a$-loop
(following the order of vertex labels) and root the graph at the vertex where
that loop used to be.

This algorithm can be modified as in Remark 5.2 to draw uniformly at random a
$\mathsf{PSL}_{2}(\mathbb{Z})$-cyclically reduced subgroup of a given
isomorphism type.

###  5.4 Implementation and complexity remarks

#### Two models of computation to measure complexity

For the complexity analysis, we consider two classical models: the _unit-cost
model_ (also known as _RAM model_) where each elementary operation, including
operations on integers, takes $O(1)$ time; and the _bit-cost_ model where an
integer $N$ is encoded using $O(\log N)$ space, the number of bits of its
representation, and where arithmetic operations are not performed in constant
time anymore. This is more realistic in our settings because we are led to
handling large integers. For instance, $O(n\log n)$ bits are required to
represent the number of size $n$ silhouette graphs (see [3, Proposition
8.18]). To simplify the discussion below, we use the following classical
notation: for any $\alpha\geq 0$, a non-negative sequence $u_{n}$ is in
$\widetilde{O}(n^{\alpha})$ if there exist constants $C,\beta>0$ such that
$u_{n}\leq C\,n^{\alpha}\log^{\beta}n$ for all $n$ sufficiently large.
Informally, it means that $u_{n}$ is in $O(n^{\alpha})$ “up to a poly-
logarithmic factor”. Note that, in the bit-cost model, adding or multiplying
two numbers encoded with at most $N$ bits costs $\widetilde{O}(N)$ time. It is
elementary for addition and a consequence of, for instance, Harvey and van der
Hoeven’s result [10] for multiplication. Comparing two numbers encoded with at
most $N$ bits costs $O(N)$ time.

In the unit-cost model, we consider that, for any positive integer $n$, we can
generate uniformly at random an integer in $[n]$ in $O(1)$ time. In the bit-
cost model, we consider that we can generate uniformly at random a bit value
of $\\{0,1\\}$ in $O(1)$ time. If $n$ is a positive integer encoded with $N$
bits, we can therefore produce an element of $[n]$ uniformly at random using a
rejection algorithm consisting in repeatedly generating a number made of $N$
independent random bits until the result is in $[n]$. The expected running
time of this algorithm is $O(N)$ as the expected number of attempts is at most
$2$.

#### Precomputing

Since the parameters $n$, $\ell_{2}$, $\ell_{3}$, $k_{2}$ and $k_{3}$ are non-
negative and satisfy $n=2k_{2}+\ell_{2}$ and $n\geq 2k_{3}+\ell_{3}$, there
are at most $n^{4}$ non-zero values for $s(n,k_{2},k_{3},\ell_{2},\ell_{3})$
for a given positive integer $n$. They can be computed recursively using
Equations (1), (2) and (3), the base cases being either trivial (for $n\geq
2$) or given by Proposition 4.7. This yields an $O(n^{4})$ time and space
algorithm in the unit-cost model and $\widetilde{O}(n^{5})$ time and space
algorithm in the bit-cost model.

#### Random generation

We assume in this section that all the required values of
$s(n,k_{2},k_{3},\ell_{2},\ell_{3})$ have been precomputed and are accessible
in time $O(1)$ in the unit-cost model, $\widetilde{O}(1)$ in the bit-cost
model.

Algorithm $\mathtt{random\\_cyclically\\_reduced\\_graph}$ was written with
the proof of Theorem 5.1 in mind. This is the reason why, in particular, it
calls for randomly choosing an integer $v$, or integers $v$ and $w$. One can
also choose $v=n$, or $v=n$ and $w=n-1$, that is, disregard the randomness of
the labeling of the graph we constuct, and add a very last step to the
algorithm, which relabels $\Gamma$ by a random permutation. This is a classic
trick in the literature on the random generation of labeled combinatorial
objects (see for instance [7, footnote on p. 12]).

In the unit-cost model, $\mathtt{random\\_silhouette\\_graph}$ runs in $O(n)$
average time, using the Fisher-Yates shuffling algorithm [13, p.145] and the
fact that the number of iterations in $\mathtt{random\\_silhouette\\_graph}$
is bounded in expectation, see Section 5.1. If we use the trick mentioned
above (relabeling the graph at the end), every call of the function
$\mathtt{random\\_cyclically\\_reduced\\_graph}$ is performed in $O(1)$. As
each call decreases the value of $n$ by at least $1$, Algorithm
$\mathtt{random\\_cyclically\\_reduced\\_graph}$ runs in $O(n)$ expected time.

In the bit-cost model, observe that $n$ is encoded using $O(\log n)$ bits, so
that all arithmetic operations on $n$, $\ell_{2}$, $\ell_{3}$, $k_{2}$,
$k_{3}$ are performed in $\widetilde{O}(1)$ time. The bottleneck for the
running time of the algorithm lies therefore in Lines 2-2, as generating $x$
and comparing $x$ with the threshold in Line 2 both cost $\widetilde{O}(n)$
time. The overall expected running time of the algorithm in the bit-cost model
is therefore $\widetilde{O}(n^{2})$.

This process (generating $x$ and comparing it with a theshold) can be improved
using the following idea. Assume that we have two large integers $s$ and $t$,
and the sum $s+t$ has already been computed. Let $z_{0}\cdots z_{N-1}$ be the
binary encoding of $s+t$ (with $z_{0}=1$). Let also $s_{0}\cdots s_{N-1}$ be
the binary encoding of $s$ (here $s_{0}$ may be 0). Generating $x$ in $[s+t]$
and comparing it to $s$, amounts to simulating a Bernoulli law of parameter
$\frac{s}{s+t}$ (in the bit-cost model). This is performed using Algorithm
$\mathtt{bernoulli\\_attempt}$, which generates a uniform random integer, say
$x$, between $0$ and $2^{N}-1$ bit by bit, halting as soon as we are
guaranteed that one of the three possible situations holds : $x\geq s+t$
(Failure), $x<s$ (True) and $s\leq x<s+t$ (False).

1 $smaller_{s+t}=\emptyset$

2 $smaller_{s}=\emptyset$

3 for  _$i\in\\{0,\ldots,N-1\\}$_ do

4 $bit$ = Uniform($\\{0,1\\}$)

5 if  _$smaller_{s+t}=\emptyset$_ then

6 if  _$bit >z_{i}$_ then return Failure

7 if  _$bit <z_{i}$_ then $smaller_{s+t}=\texttt{True}$

8

9 if  _$smaller_{s}=\emptyset$_ then

10 if  _$bit >s_{i}$_ then $smaller_{s}=\texttt{False}$

11 if  _$bit <s_{i}$_ then $smaller_{s}=\texttt{True}$

12

13 if  _$smaller_{s+t}\neq\emptyset$ and $smaller_{s}\neq\emptyset$_ then

14 return $smaller_{s}$

15

16if  _$smaller_{s+t}=\emptyset$_ then

return Failure // the generated number is $\geq s+t$

17

return False // the generated number is equal to $s$

Algorithm 3 $\mathtt{bernoulli\\_attempt}(x,y,N)$

The main algorithm to simulate the Bernoulli law of parameter $\frac{s}{s+t}$
consists in repeatedly calling $\mathtt{bernoulli\\_attempt}$ until the result
is not Failure. The analysis of the expected number of bits generated in the
process is straightforward, as $smaller_{s+t}$ and $smaller_{s}$ are
determined with probability $\frac{1}{2}$ at each iteration of the first loop:
the number of iterations required to determine each one of them is bounded
above by a geometric law of parameter $\frac{1}{2}$. Since $s+t>2^{N-1}$, the
expected number of calls to $\mathtt{bernoulli\\_attempt}$ is bounded above by
a constant. Hence the expected bit-cost complexity of our procedure to
simulate the Bernoulli law is $\widetilde{\mathcal{O}}(1)$.

To implement the announced improvement, we modify the precomputation step by
storing not only the values of $s(n,k_{2},k_{3},\ell_{2},\ell_{3})$, but also
their bit-lengths and the values $n\cdot(k_{3}+1)\cdot
s(n-1,k_{2},k_{3}+1,\ell_{2}-1,0)$ (used Line 2). Simulating a Bernoulli law
of parameter $n\cdot(k_{3}+1)\cdot
s(n-1,k_{2},k_{3}+1,\ell_{2}-1,0)/s(n,k_{2},k_{3},\ell_{2},\ell_{3})$ instead
of performing Lines 2 and 2, lowers the expected time complexity of
$\mathtt{random\\_cyclically\\_reduced\\_graph}$ to $\widetilde{O}(n)$.

###### Remark 5.3

When $\ell_{3}>0$, one can directly choose $\ell_{3}$ $a$-loops of the graph
$\Delta$ built at Line 2 to apply the inverse of a $\lambda_{3}$-move
$\ell_{3}$ times directly. This does not change the overall complexity of
$\mathtt{random\\_cyclically\\_reduced\\_graph}$ in both models of
computation. Similarly, if $\ell_{2}=\ell_{3}=0$ and $k_{3}=n/2$, the
generated graph is a cycle made of an alternation of $a$-transitions and
$b$-transitions, which could be generated directly without making several
recursive call. Again, this does not change the complexity. $\sqcap$$\sqcup$

## References

  * [1] G. N. Arzhantseva.  Generic properties of finitely presented groups and Howson’s theorem.  Comm. Algebra, 26(11):3783–3792, 1998.
  * [2] G. N. Arzhantseva and A. Y. Ol’shanskiĭ.  Generality of the class of groups in which subgroups with a lesser number of generators are free.  Mat. Zametki, 59(4):489–496, 1996.
  * [3] F. Bassino, C. Nicaud, and P. Weil.  Statistics of subgroups of the modular group.  Int. J. Algebra Comput., 31(8):1691–1751, 2021.
  * [4] F. Bassino, C. Nicaud, and P. Weil.  Silhouettes and generic properties of subgroups of the modular group.  In progress, 2023.
  * [5] I. M. S. Dey.  Schreier systems in free products.  Proc. Glasgow Math. Assoc., 7(2):61–79, 1965.
  * [6] P. Flajolet and R. Sedgewick.  Analytic combinatorics.  Cambridge University Press, 2009.
  * [7] P. Flajolet, P. Zimmermann, and B. Van Cutsem.  A calculus for the random generation of labelled combinatorial structures.  Theor. Comput. Sci., 132(2):1–35, 1994.
  * [8] S. M. Gersten and H. B. Short.  Rational subgroups of biautomatic groups.  Ann. of Math., 134(1):125–158, 1991.
  * [9] R. Gitik.  Nielsen generating sets and quasiconvexity of subgroups.  J. Pure Appl. Algebra, 112(3):287–292, 1996.
  * [10] D. Harvey and J. van der Hoeven.  Integer multiplication in time ${O}(n\log n)$.  Annals of Mathematics, 193(2):563–617, 2021.
  * [11] I. Kapovich.  Detecting quasiconvexity: algorithmic aspects.  In Geometric and computational perspectives on infinite groups (Minneapolis, MN and New Brunswick, NJ, 1994), volume 25 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 91–99. Amer. Math. Soc., Providence, RI, 1996.
  * [12] O. Kharlampovich, A. Miasnikov, and P. Weil.  Stallings graphs for quasi-convex subgroups.  J. Algebra, 488:442–483, 2017.
  * [13] D. E. Knuth.  The Art of Computer Programming, Volume II: Seminumerical Algorithms (third edition).  Addison-Wesley, 1989.
  * [14] A. G. Kurosh.  The theory of groups. Vol. II.  Chelsea Publishing Company, New York, N.Y., 1956.  Translated from the Russian and edited by K. A. Hirsch.
  * [15] R. C. Lyndon and P. E. Schupp.  Combinatorial group theory.  Springer-Verlag, 1977.
  * [16] L. Markus-Epstein.  Stallings foldings and subgroups of amalgams of finite groups.  Internat. J. Algebra Comput., 17(8):1493–1535, 2007.
  * [17] T. W. Müller and J.-C. Schlage-Puchta.  Classification and statistics of finite index subgroups in free products.  Adv. Math., 188(1):1–50, 2004.
  * [18] M. Newman.  Asymptotic formulas related to free products of cyclic groups.  Math. Comp., 30(136):838–846, 1976.
  * [19] J. J. Rotman.  An introduction to the theory of groups, volume 148 of Graduate Texts in Mathematics.  Springer-Verlag, New York, fourth edition, 1995.
  * [20] H. Short.  Quasiconvexity and a theorem of Howson’s.  In Group theory from a geometrical viewpoint (Trieste, 1990), pages 168–176. World Sci. Publ., River Edge, NJ, 1991.
  * [21] J. R. Stallings.  Topology of finite graphs.  Invent. Math., 71(3):551–565, 1983.
  * [22] W. W. Stothers.  The number of subgroups of given index in the modular group.  Proc. Roy. Soc. Edinburgh Sect. A, 78(1-2):105–112, 1977/78.
  * [23] W. W. Stothers.  Free subgroups of the free product of cyclic groups.  Math. Comp., 32(144):1274–1280, 1978.