%~Mouliné par MaN_auto v.0.27.3 2023-10-17 11:36:34 \documentclass[AHL,Unicode,longabstracts,published]{cedram} \usepackage{dsfont} \usepackage{overpic} \usepackage{comment} % \AtBeginDocument{ \newtheorem{claim}[cdrthm]{Claim} \newtheorem{subclaim}[cdrthm]{Subclaim} % \newtheorem{innerthmrep}{Theorem}\newenvironment{thmrep}[1] { \renewcommand\theinnerthmrep{#1}\innerthmrep} {\endinnerthmrep}} \newcommand{\ind}{\mathds{1}} \newcommand{\noopsort}[1]{} \newcommand{\PSL}{\mathrm{PLS}} \newcommand{\bbR}{\mathbb{R}} \newcommand{\bbN}{\mathbb{N}} \newcommand{\bbZ}{\mathbb{Z}} \newcommand{\bbH}{\mathbb{H}} \newcommand{\bbP}{\mathbb{P}} \newcommand{\bbC}{\mathbb{C}} \newcommand{\bbE}{\mathbb{E}} \DeclareMathOperator{\Poisson}{Poisson} \newcommand{\Hom}{\mathrm{Hom}} \newcommand{\IRS}{\mathrm{IRS}} \newcommand{\Sub}{\mathrm{Sub}} \newcommand{\Stab}{\mathrm{Stab}} \newcommand{\Aut}{\mathrm{Aut}} \newcommand{\clN}{\mathcal{N}} \newcommand{\clT}{\mathcal{T}} \newcommand{\clA}{\mathcal{A}} \newcommand{\clK}{\mathcal{K}} \newcommand{\clD}{\mathcal{D}} \newcommand{\clBS}{\mathcal{BS}} \newcommand{\clH}{\mathcal{H}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \graphicspath{{./figures/}} \newcommand*{\mk}{\mkern -1mu} \newcommand*{\Mk}{\mkern -2mu} \newcommand*{\mK}{\mkern 1mu} \newcommand*{\MK}{\mkern 2mu} %\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red} \newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}} \newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}} \newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}} \newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}} \let\oldtilde\tilde \renewcommand*{\tilde}[1]{\mathchoice{\widetilde{#1}}{\widetilde{#1}}{\oldtilde{#1}}{\oldtilde{#1}}} \let\oldhat\hat \renewcommand*{\hat}[1]{\mathchoice{\widehat{#1}}{\widehat{#1}}{\oldhat{#1}}{\oldhat{#1}}} \let\oldforall\forall \renewcommand*{\forall}{\mathrel{\oldforall}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title[Statistics of finite degree covers of torus knot complements]{Statistics of finite degree covers of torus knot complements} \alttitle{Statistiques des revêtements de degré fini des compléments de nœuds toriques} \subjclass{20E07, 22E40, 57M50} \keywords{Subgroup growth, random covers, torus knots} \author[\initial{E.} \lastname{Baker}]{\firstname{Elizabeth} \lastname{Baker}} \address{University of Copenhagen,\\ Pioneer Centre\\ for Artificial Intelligence (P1AI),\\ Øster Voldgade 3,\\ 1350 København, Denmark} \email{elba@di.ku.dk} \author[\initial{B.} \lastname{Petri}]{\firstname{Bram} \lastname{Petri}} \address{Sorbonne Université\\ and Université Paris Cité,\\ CNRS, IMJ-PRG,\\ F-75005 Paris, France} \email{bram.petri@imj-prg.fr} \begin{abstract} In the first part of this paper, we determine the asymptotic subgroup growth of the fundamental group of a torus knot complement. In the second part, we use this to study random finite degree covers of torus knot complements. We determine their Benjamini--Schramm limit and the linear growth rate of the Betti numbers of these covers. All these results generalise to a larger class of lattices in $\PSL(2,\bbR)\times \bbR$. As a by-product of our proofs, we obtain analogous limit theorems for high index random subgroups of non-uniform Fuchsian lattices with torsion. \end{abstract} \begin{altabstract} Dans la première partie de cet article, nous déterminons la croissance de sous-groupes asymptotique des groupes fondamentaux des compléments des n{\oe} uds toriques. Dans la deuxième partie, nous utilisons cela pour étudier des revêtements aléatoires de degré fini des compléments de n{\oe} uds toriques. Nous déterminons leurs limites au sens de Benjamini--Schramm et le taux de croissance linéaire de leur nombres de Betti. Tous ces résultats se généralisent à une classe plus large de réseaux de $\PSL(2,\bbR)\times \bbR$. Comme conséquence de nos preuves, nous obtenons également des théorèmes limites analogues pour des sous-groupes aléatoires de grand indice des réseaux Fuchsiens non-uniformes. \end{altabstract} \datereceived{2021-04-23} \daterevised{2023-04-14} \dateaccepted{2023-07-24} \editors{S. Gou\"ezel and I. Benjamini} \begin{DefTralics} \newcommand{\PSL}{\mathrm{PLS}} \newcommand{\bbR}{\mathbb{R}} \end{DefTralics} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \dateposted{2023-12-12} \begin{document} \maketitle \section{Introduction} A classical theorem due to Hempel~\cite{Hempel} states that the fundamental group of a tame $3$-manifold is residually finite. As such, it has many finite index subgroups, or equivalently, the manifold has lots of finite degree covers. In this paper we study the fundamental groups of torus knot complements and groups closely related to these. We ask two questions: How fast does the number of index $n$ subgroups grow as a function of $n$? And what are the properties of a random index $n$ subgroup and the corresponding degree $n$ cover? We will study groups of the form \[ \Gamma_{p_1,\,\ldots,\,p_m} = \left\langle x_1,\,\ldots\, x_m\,\middle|\, x_1^{p_1} = x_2^{p_2} = \cdots = x_m^{p_m} \right\rangle. \] When $\gcd(p,q)=1$ and $p,q\geq 2$ then $\Gamma_{p,q}$ is the fundamental group of a $(p,q)$-torus knot complement. More generally, $\Gamma_{p_1,\,\ldots,\,p_m}$ is a central extension of the form \begin{equation}\label{eq_central_ext} 1\longrightarrow \bbZ \longrightarrow \Gamma_{p_1,\,\ldots,\,p_m} \stackrel{\Phi_{p_1,\,\ldots,\,p_m}}{\longrightarrow} C_{p_1} * \cdots * C_{p_m} \longrightarrow 1, \end{equation} where $C_p$ denotes the finite cyclic group of order $p$ and $\Phi_{p_1,\,\ldots,\,p_m}$ is the map that sends the generator $x_j$ to a generator of $C_{p_j}$. We will consider the case $\sum_{j=1}^m \frac{1}{p_j} < m-1$, which includes all torus knot groups. In this setting $\Gamma_{p_1,\,\ldots,\,p_m}$ appears as a non-uniform lattice in $\PSL(2,\bbR)\times \bbR$ (see for instance~\cite[Proposition~7.2]{Eckmann}). $\Phi_{p_1,\,\ldots,\,p_m}(\Gamma_{p_1,\,\ldots,\,p_m})$ is then the projection onto $\PSL(2,\bbR)$ of $\Gamma_{p_1,\,\ldots,\,p_m}$ and is a Fuchsian group that acts on the hyperbolic plane $\bbH^2$. The orbifold Euler characteristic of $\Phi_{p_1,\,\ldots,\,p_m}(\Gamma_{p_1,\,\ldots,\,p_m}) \backslash \bbH^2$ is \[ -m+1+\sum_{i=1}^m\frac{1}{p_i}, \] a number that will appear repeatedly throughout this paper. \subsection{Subgroup growth} The first of our questions above asks for the \emph{subgroup growth} of these groups. That is, the study of the large $n$ behaviour of the quantity $a_n(\Gamma_{p_1,\,\ldots,\,p_m})$ -- the number of index $n$ subgroups of $\Gamma_{p_1,\,\ldots,\,p_m}$. Because $\Gamma_{p_1,\,\ldots,\,p_m}$ is a central extension of a free product of finite groups by $\bbZ$, a standard argument which we provide in Section~\ref{sec_subgroupgrowth}, combined with results due to M\"uller~\cite{Muller_FreeProducts}, Volynets~\cite{Volynets} and Wilf~\cite{Wilf} on the subgroup growth on free products of finite groups proves the following: \begin{theo}\label{thm_main1} Let $p_1,\,\dots,\,p_m \in \bbN_{\,>\,1}$ such that $\sum_{j=1}^m \frac{1}{p_j} < m-1$. Then it holds that\footnote{Here and throughout the paper, the notation $f(n)\sim g(n)$ as $n\to \infty$ will indicate that $\lim_{n\,\to\,\infty} f(n)/g(n) = 1$.} \[ a_n\left(\Gamma_{p_1,\,\ldots,\,p_m}\right) \sim A_{p_1,\,\ldots,\,p_m} \cdot n^{-1/2}\cdot \exp\left(\sum_{i=1}^m\sum_{\substack{0\,<\,j\,<\,p_i \\ \text{s.t. } j|p_i}} \frac{n^{j/p_i}}{j} \right) \cdot \left(\frac{n}{e}\right)^{n\cdot\left(m-1-\sum\limits_{i=1}^m \frac{1}{p_i}\right)} \] as $n\to\infty$, where \[ A_{p_1.\ldots p_m} = \sqrt{2\pi} \exp\left(- \sum_{i:\;p_i \text{ even}} \frac{1}{2p_i}\right) \prod_{i=1}^m p_i^{-1/2}. \] \end{theo} The theorem above also generalises to free products of the form \[ \Gamma_{p_{1,1},\,\ldots,\,p_{1,m_1}} * \cdots * \Gamma_{p_{r,1}\ldots,\,p_{r,m_r}} \] where $\sum_j p_{i,m_i} < m_i -1$ for all $i=1,\,\ldots,\,r$. In topological terms, this corresponds to taking connected sums. Using the asymptotic behaviour of $a_n(\Gamma_{p_1,\,\ldots,\,p_m})$, one can also derive an asymptotic equivalent for the related sequence \[ h_n\left(\Gamma_{p_1,\,\ldots,\,p_m}\right) = \left| \Hom\left(\Gamma_{p_1,\,\ldots,\,p_m},S_n\right) \right|. \] First of all, note that~\eqref{eq_central_ext} implies that \begin{equation}\label{eq_hn_projection} h_n\left(\Gamma_{p_1,\,\ldots,\,p_m}\right) \quad \geq \quad h_n\left(C_{p_1}*\cdots * C_{p_m}\right) = \prod_{j=1}^m h_n\left(C_{p_j},S_n\right). \end{equation} It turns out that asymptotically the bound in~\eqref{eq_hn_projection} is tight. In other words, a typical homomorphism factors through $\Phi_{p_1,\,\ldots,\,p_m}$. We prove: \begin{theo}\label{thm_main2} $p_1,\,\dots,\,p_m \in \bbN_{\,>\,1}$ such that $\sum_{j=1}^m \frac{1}{p_j} < m-1$. Then \[ \frac{\left|\left\{\rho \in \Hom\left(\Gamma_{p_1,\,\ldots,\,p_m},S_n\right);\; \rho \text{ factors through }\Phi_{p_1,\,\ldots,\,p_m} \right\}\right|}{h_n\left(\Gamma_{p_1,\,\ldots,\,p_m}\right)} \longrightarrow 1 \] as $n\to\infty$. \end{theo} The analogous result is also known to hold for orientable circle bundles over surfaces~\cite{LisMed}. A similar observation was also made for certain sequences of amalgamated products in~\cite[p.~130]{Muller_FreeProducts}. As we noted above, we use results due to M\"uller, Volynets and Wilf in order to prove the two results above. The fact that $\Gamma_{p_1,\,\ldots,\,p_m}$ has a relatively simple presentation also allows one to derive the theorems above with elementary arguments. In particular, one can write down a closed formula for $h_n(\Gamma_{p_1,\,\ldots,\,p_m})$ and derive the theorems from there, using the same type of techniques that M\"uller employed in~\cite{Muller_FreeProducts}. We will sketch these arguments, which we employed in a previous version of this paper, in Appendix~\ref{app_elt_approach}. \subsection{Random subgroups and covers} In the second part of our paper, we use the results above to study random finite index subgroups of $\Gamma_{p_1,\,\ldots,\,p_m}$. That is, since the number of index $n$ subgroups of $\Gamma_{p_1,\,\ldots,\,p_m}$ is finite, we can pick one uniformly at random and ask for its properties. Let us denote our random index $n$ subgroup by $H_n$. This is an example of an Invariant Random Subgroup (IRS) -- i.e. a conjugation invariant Borel measure on the Chabauty space of subgroups of $\Gamma_{p_1,\,\ldots,\,p_m}$ (for more details see Section~\ref{sec_IRS}). We will also fix a classifying space $X_{p_1,\,\ldots,\,p_m}$ for $\Gamma_{p_1,\,\ldots,\,p_m}$. For instance, if $p,q\geq 2 $ and $\gcd(p,q)=1$ we can take the corresponding torus knot complement. More generally, since $\Gamma_{p_1,\,\ldots,\,p_m}$ appears as a torsion-free lattice in $\PSL(2,\bbR)\times \bbR$, we may take the manifold $\Gamma \backslash (\bbH^2\times \bbR)$. $H_n$ gives rise to a random degree $n$ cover of $X_{p_1,\,\ldots,\,p_m}$. We will study three (related) problems: \begin{itemize} \item First, we will ask, given a conjugacy class $K\subset \Gamma_{p_1,\,\ldots,\,p_m}$, how many fixed points does $g\in K$ have for the left action on $ \Gamma_{p_1,\,\ldots,\,p_m}/H_n$? We will denote this number of fixed points by $Z_K(H_n)$. In topological terms, $K$ corresponds to a free homotopy class of loops in $X_{p_1,\,\ldots,\,p_m}$. $Z_K(H_n)$ is the number of closed lifts of that loop to the cover of $X_{p_1,\,\ldots,\,p_m}$ corresponding to $H_n$. We note that we count these lifts as loops and not as sets. In particular, if the corresponding element in $\Gamma_{p_1,\,\ldots,\,p_m}$ is non-primitive\footnote{In this article, \emph{primitive} means ``not a non-trivial power''.}, some of these different lifts may overlap. Indeed, if $g_0\in \Gamma_{p_1,\,\ldots,\,p_m}$ is primitive and it for instance has an orbit of order three on $ \Gamma_{p_1,\,\ldots,\,p_m}/H_n$, then $g_0^3$ has three fixed points on $ \Gamma_{p_1,\,\ldots,\,p_m}/H_n$ and the corresponding lifts at the three corresponding lifts of a base point on $X_{p_1,\,\ldots,\,p_m}$ all overlap. \item After this, we will ask what IRS the random subgroup $H_n$ converges to as $n\to\infty$. In topological terms, this asks for the \emph{Benjamini--Schramm} limit of the corresponding random cover of $X_{p_1,\,\ldots,\,p_m}$ (see Section~\ref{sec_BS_convergence} for a definition of Benjamini--Schramm convergence). \item Finally, we will study the asymptotic behaviour of the real Betti numbers $b_k(H_n;\bbR)$ of $H_n$, or equivalently of the corresponding random cover of $X_{p_1,\ldots,p_m}$. \end{itemize} We will write \[ L_{p_1,\,\ldots,\,p_m} := \ker\left(\Phi_{p_1,\,\ldots,\,p_m}\right) \simeq \bbZ. \] For a torus knot, this is the subgroup generated by the longitude. Since $L_{p_1,\,\ldots,\,p_m}$ is normal in $\Gamma_{p_1,\,\ldots,\,p_m}$, it's also an IRS. In the theorem below, $\clN(0,1)$ will denote a standard normal distribution on $\bbR$ and more generally, $\clN^{\otimes r}$ a standard normal distribution on $\bbR^r$. If $K_1,K_2\subset \Gamma$ are conjugacy classes in a group $\Gamma$ and $g\in \Gamma$ and $k_1,k_2 \in \bbN$ are such that $g^{k_1} \in K_1$ and $g^{k_2} \in K_2$ we will say $K_1$ and $K_2$ have a common root. Note that two conjugacy classes that don't have a common root are in particular distinct. We will prove\footnote{Doron Puder and Tomer Zimhoni pointed out to us that in a previous version of this paper, we had missed the case in which $\Phi_{p_1,\,\ldots,\,p_m}(g_0)$ is a product of two elements of order two. Puder--Zimhoni~\cite{PuderZimhoni} have also proved a generalisation of Corollary~\ref{cor_poissononhom} below that also yields an interpretation of these results in terms of group Euler characteristics. In particular, the case of products of order two elements in the corollary was first worked out by Puder--Zimhoni.}: \begin{theo}\label{thm_main3} Let $p_1,\,\ldots,\,p_m \in\bbN_{>1}$ be such that $\sum_{j=1}^m \frac{1}{p_j}0$ if and only if \[ \bbP[X=k] = \frac{\lambda^k e^{-\lambda}}{k!} \quad \forall k \in \bbN. \] So~\eqref{theo1.3.a} above gives us an explicit limit for the probability that a fixed curve lifts to any given number of curves in the cover. For example, if $p$ and $q$ are both odd and we denote the random degree $n$ cover of our $(p,q)$-torus knot complement by $X_{p,q}(n)$ and $\gamma$ is any primitive free homotopy class of closed curves in $X_{p,q}(1)$ that is not freely homotopic to the longitude we obtain: \[ \lim_{n\,\to\,\infty}\bbP\left[\gamma \text{ lifts to exactly }3\text{ closed curves in }X_{p,q}(n)\right] = \frac{1}{6e} = 0.0613\ldots. \] Using our techniques, the limit of the joint distribution of the variables associated to distinct conjugacy classes that do have common roots can also be determined. The independence will then however be lost (see Theorem~\ref{thm_factorialmomentsY} below). Note also that we don't consider combinations of variables coming from finite and infinite order elements. \eqref{theo1.3.b} In particular implies that a random degree $n$ cover of a torus knot complement does \emph{not} converge to the universal cover of the given torus knot complement as $n\to\infty$. This is different from the behaviour of random finite covers of graphs~\cite{DJPP}, surfaces~\cite{MageePuder} and many large volume locally symmetric spaces of higher rank~\cite{7sam}, that all do converge to their universal covers. \eqref{theo1.3.c} Also has implications for the number of boundary tori in a random cover of a torus knot complement. Indeed, together with ``half lives, half dies''~\cite[Lemma~3.5]{Hatcher_3D}, it also implies that the number of boundary components of a degree $n$ cover is typically at most $(1 - \frac{1}{p}-\frac{1}{q})\cdot n + o(n)$. Because all the results in the theorem above are really about the group $\Gamma_{p_1,\,\ldots,\,p_m}$, we can also apply them to random covers of more general spaces $Y_{p_1,\,\ldots,\,p_m}$ that have $\Gamma_{p_1.\,\ldots,\,p_m}$ as their fundamental group (i.e. without assuming that $Y_{p_1,\,\ldots,\,p_m}$ is a classifying space for $\Gamma_{p_1,\,\ldots,\,p_m}$). In that case, the random cover Benjamini--Schramm converges to the cover of $Y_{p_1,\,\ldots,\,p_m}$ corresponding to $L_{p_1,\,\ldots,\,p_m}$ and the normalised Betti numbers converge to the $\ell^2$-Betti numbers of that cover. Finally, we note that we prove analogous results to Theorem~\ref{thm_main3} for random index $n$ subgroups of non-cocompact Fuchsian groups. \begin{theo}\label{thm_main4} Let $\Lambda$ be a non-cocompact Fuchsian group of finite covolume. Moreover, let $G_n<\Lambda$ denote an index $n$ subgroup, chosen uniformly at random. \begin{enumerate}\Alphenumi \item\label{theo1.4.a} \begin{enumerate} \item\label{theo1.4.1} If $K_1,\,\ldots,\,K_r \subset \Lambda$ are conjugacy classes of infinite order elements of which no pair have a common root. Then, as $n\to\infty$, the vector of random variables \[ \left(Z_{K_1}(G_n),\,\ldots,\,Z_{K_r}(G_n)\right) \] converges jointly in distribution to a vector \[ \left(Z_{K_1}^\infty,\,\ldots,\,Z_{K_r}^\infty\right):\Omega \to \bbN^r \] of independent random variables, such that if $K_i$ is the conjugacy class of a $k^{th}$ power of a primitive element then: \begin{itemize} \item If the corresponding primitive element is not a product of two elements of order two: \[ Z_{K_i}^\infty \sim \sum_{d|k}\; d \cdot X_{1/d}, \] where $X_{1/d} \sim \Poisson(1/d)$ and $X_1,\,\ldots,\,X_{1/k}$ are independent. \item If the corresponding primitive element is a product of two elements of order two: \[ Z_{K_i}^\infty \sim \sum_{d|k}\; 2d \cdot X^{d,1}_{1/2d} + \sum_{d|k,\; d\text{ even}} d\cdot X_{1/2}^{d,2}+d\cdot X_{1/2}^{d,3} + \sum_{d|k,\; d\text{ odd}} d \cdot X_1^{d,4} \] where $X^{d,1}_{1/2d} \sim \Poisson(1/2d)$, $X_{1/2}^{d,2},X_{1/2}^{d,3}\sim \Poisson(1/2)$, $X_1^{d,4}\sim \Poisson(1)$ and all these variables are independent. \end{itemize} \item~\cite[Lemma~4]{MullerPuchta3} If $K_1,\,\ldots,\,K_r\subset \Lambda$ are non-trivial conjugacy classes of which no pair have a common root, whose elements have orders $k_1,\,\ldots,\,k_r\in\bbN$ respectively, then the vector of random variables \[ \left(\frac{Z_{K_1}(G_n)-n^{1/k_1}-\varepsilon_1\cdot n^{1/2k_1}}{\sqrt{p_{j_1}/k_1}\cdot n^{1/2k_1}},\,\ldots,\,\frac{Z_{K_r}(G_n)-n^{1/k_r}-\varepsilon_r\cdot n^{1/2k_r}}{\sqrt{p_{j_r}/k_r}\cdot n^{1/2k_r}} \right) \] converges in distribution to a $\clN(0,1)^{\otimes r}$-distributed random variable as $n\to \infty$. Here $p_{j_i}\in\bbN$ is such that $K_i$ is the conjugacy class of $x_{j_i}^{l_i}$, for $i=1,\,\ldots,\,r$. Finally $\varepsilon_i$ equals $1$ if $p_{j_i}/k_i$ is even and $0$ otherwise. \end{enumerate} \item\label{theo1.4.b} As $n\to\infty$, $G_n$ converges to the trivial group as an IRS. \end{enumerate} \end{theo} Note that the analogue to Theorem~\ref{thm_main3}$\MK$\eqref{theo1.3.c} also holds here. However, a much stronger statement follows directly from results by M\"uller--Schlage-Puchta~\cite{MullerPuchta3}. The case of free groups in the theorem above is very similar to results on cycle counts in random regular graphs in the permutation model (see for instance~\cite{DJPP} and also~\cite{Bol} for a slightly different model). In the case where $\Lambda$ is a free product of finite cyclic groups and $r=1$, Benaych-Georges~\cite{BG1} proved Theorem~\ref{thm_main4}$\MK$\eqref{theo1.4.1} for certain conjugacy classes. For surface groups similar results have very recently been proved by Magee--Puder~\cite{MageePuder} and Puder--Zimhoni~\cite{PuderZimhoni}. The case of cocompact Fuchsian groups with torsion is currently open. \subsection{The structure of the proofs} Our proofs start with the subgroup growth. We combine results due to M\"uller \cite{Muller_FreeProducts,Muller}, Volynets~\cite{Volynets} and Wilf~\cite{Wilf} with a classical bound on the number of index $n$ subgroups of an extension (see Proposition~\ref{prop_subgp_quotient}) in order to prove Theorem~\ref{thm_main1}. Combining this with the recurrence relating the sequences $(a_n(\Gamma_{p_1,\,\ldots,\,p_m}))_n$ and $(h_n(\Gamma_{p_1,\,\ldots,\,p_m}))_n$ we then obtain Theorem~\ref{thm_main2} as well. The idea behind the proofs of our results on random subgroups is to first prove the analogous results for random index $n$ subgroups of $C_{p_1}*\cdots *C_{p_m}$ and then use the fact that most index $n$ subgroups of $\Gamma_{p_1,\,\ldots,\,p_m}$ come from index $n$ subgroups of $C_{p_1}*\cdots *C_{p_m}$ to upgrade these into results about $\Gamma_{p_1,\,\ldots,\,p_m}$. First, we consider the problem of counting the number of fixed points of an element $g\in C_{p_1}*\cdots * C_{p_m}$ under a random homomorphism $C_{p_1}*\cdots * C_{p_m} \to S_n$. There are two cases to consider: \begin{itemize} \item M\"uller--Schlage-Puchta~\cite{MullerPuchta2,MullerPuchta3} proved the central limit theorem we need for finite order elements. \item If $g$ is of infinite order, its number of fixed points can be approximated by a sum of multiples of Poisson-distributed random variables. For certain conjugacy classes, this was proved by Benaych-Georges in~\cite{BG1}. We extend this to all conjugacy classes and also show that the statistics of different conjugacy classes are asymptotically independent. \end{itemize} We prove our Poisson distribution result by estimating the factorial moments of the random variables that count the fixed points of $g$. We note that in all of our estimates, the error terms could be made explicit using the error terms in M\"uller's results~\cite{Muller_FreeProducts}. Moreover, the Chen--Stein method (see for instance~\cite{AGG,BHT,DJPP,CGS}) might give sharper bounds than the method of moments. The fact that a conjugacy class $K\subset \Gamma_{p_1,\,\ldots,\,p_m}$ typically has very few lifts to $H_n$ if it does not lie in $L_{p_1,\,\ldots,\,p_m}$ and typically has $n$ lifts if it does (this is essentially Theorem~\ref{thm_main3}$\MK$\eqref{theo1.3.a}), implies that the IRS $H_n$ converges to $L_{p_1,\,\ldots,\,p_m}$ (Theorem~\ref{thm_main3}$\MK$\eqref{theo1.3.b}). Using results by Elek~\cite{Elek} and L\"uck~\cite{Lueck}, we then also obtain that the normalised Betti numbers of $H_n$ converge to the $\ell^2$-Betti numbers of the cover of $\widetilde{X}_{p_1,\ldots,p_m}/L_{p_1,\,\ldots,\,p_m}$. In Section~\ref{sec_fuchsian}, we sketch how to complete the proof of Theorem~\ref{thm_main4}. Finally, in Appendix~\ref{app_elt_approach} we explain an alternative approach to Theorems~\ref{thm_main1} and~\ref{thm_main2} which goes through computing a closed formula for $h_n(\Gamma_{p_1,\,\ldots,\,p_m})$. \subsection{Notes and references} As opposed to the case of $2$-manifolds~\cite{Dixon,MullerPuchta,LiebeckShalev}, there are very few $3$-manifolds for which the subgroup growth is well understood. For instance, to the best of our knowledge, there isn't a single hyperbolic $3$-manifold group $\Gamma$ for which the asymptotic behaviour of $a_n(\Gamma)$ is known. It does follow from largeness of these groups~\cite{Agol} that the number \[ s_n(G) := \sum_{m\,\leq\,n} a_m(G) \] grows faster than $(n!)^\alpha$ for some $\alpha>0$, but even at the factorial scale, the growth (i.e. the optimal $\alpha$) is not known. In the more general setting of lattices in $\PSL(2,\bbC)$ it's known in one very particular case~\cite[Section~2.5.2]{BPR}. One of the difficulties in determining $\alpha$ in general is that for a general hyperbolic $3$-manifold, no proof for a factorial lower bound is known that does not rely on Agol's work. For Seifert fibred manifolds a little more is known: the subgroup growth of orientable circle bundles over surfaces was determined by Liskovets and Mednykh~\cite{LisMed} and the subgroup growth of Euclidean manifolds can be derived from general results on the subgroup growth of virtually abelian groups~\cite{dSMcDS,Sulca}. One can also ask for the number of distinct isomorphism types of subgroups, in which case even less is known~\cite{FPPRR}. Finally, results similar to our Theorems~\ref{thm_main1} and~\ref{thm_main2} are known to hold for Baumslag--Solitar groups~\cite{Kelley}. The geometry of a random cover of a graph is a classical subject in the study of random regular graphs (see for instance~\cite{AmitLinial,DJPP,Friedman,Puder}). Moreover, it is known that, as $n\to\infty$, a random $2d$-regular graph sampled uniformly from the set of such graphs on $n$ vertices as a model is contiguous to the model given by a random degree $n$ cover of a wedge of $d$ circles~\cite{GJKW,Wor}. In other words, random covers are also a tool that can be used to study other models of random graphs. Random covers of manifolds are much less well understood. Of course, random graph covers also give rise to random covers of punctured surfaces, so some of the graph theory results can be transported to this context. Very recently, Magee--Puder~\cite{MageePuder} and Magee--Naud--Puder~\cite{MageeNaudPuder} studied random covers of closed hyperbolic surfaces. They proved that these covers Benjamini--Schramm converge to the hyperbolic plane and that the spectral gap of their Laplacian is eventually larger than $\frac{3}{16}-\varepsilon$ for all $\varepsilon>0$ (given that his holds for the base surface). More general random surfaces (see for instance~\cite{BCP,BM,GLST,GPY,Mir,MP,MRR,Pet,PT, Shrestha}), random $3$-manifolds (see for instance \cite{BBGHHKPV,DT,HV,Maher}) and random knots (see for instance \cite{BKLMR,EZ}) have recently also received considerable attention. Invariant Random Subgroups were introduced by Abért--Glasner--Virág in~\cite{AbertGlasnerVirag}, by Bowen in~\cite{Bowen} and under a different name by Vershik in~\cite{Vershik}, but had been studied in various guises before (see the references in~\cite{AbertGlasnerVirag}). Benjamini--Schramm convergence was introduced for graphs in~\cite{BenjaminiSchramm} and for lattices in Lie groups in~\cite{7sam}. The fact that Benjamini--Schramm convergence implies convergence of normalised Betti numbers was proved for sequences of simplicial complexes in~\cite{Elek}, for sequences of lattices in~\cite{7sam} and for sequences of negatively curved Riemannian manifolds in~\cite{ABBG}. \subsection*{Acknowledgements} We thank Jean Raimbault for useful remarks. Moreover, we are very grateful to the anonymous referees for pointing out errors in previous versions of Theorem~\ref{thm_main3}$\MK$\eqref{theo1.3.a}, for suggesting a shorter proof of Theorem~\ref{thm_main1} and for useful comments on the presentation. We also thank Doron Puder and Tomer Zimhoni for pointing out an error in a previous version and for multiple useful exchanges afterwards. \section{Preliminaries} \subsection{Subgroup growth}\label{sec_prelim_subgroup_growth} As mentioned in the introduction, our results on subgroup growth are based on the connection between finite index subgroups of a group $G$ and transitive permutation representations of $G$. Indeed, an index $n$ subgroup $H\,1}$ such that $\sum_{i=1}^m \frac{1}{p_i} < m-1$. Then \[ t_n\left(C_{p_1}*\cdots * C_{p_m}\right) \sim h_n\left(C_{p_1}*\cdots*C_{p_m}\right) \quad \text{as }n\to\infty. \] \end{theo} In fact, M\"uller also provides error terms and proves the theorem for more general groups; we refer to his paper for details. \subsection{Probability theory} For our Poisson approximation results, we will use the method of moments. Given a random variable $Z:\Omega \to \bbN$ and $k\in\bbN$, we will write \[ (Z)_k = Z(Z-1)\cdots (Z-k+1). \] Moreover, recall that a sequence of random variables $Z_n:\Omega_n\to\bbN^d$ is said to converge \emph{jointly in distribution} to a random variable $Z:\Omega\to\bbN^d$ if and only if \[ \bbP[Z_n\in A] \stackrel{n\,\to\,\infty}{\longrightarrow} \bbP[Z\in A] \quad \forall A\subset \bbN^d. \] The following theorem is classical. For a proof see for instance~\cite[Theorem~1.23]{Bol_book}. \begin{theo}[The method of moments]\label{thm_moments} Let $Z_{n,1},Z_{n,2},\,\ldots,\,Z_{n,r}:\Omega_n\to\bbN$, $n\in\bbN$ be random variables. If there exist $\lambda_1,\,\ldots,\,\lambda_r>0$ such that for all $k_1,\,\ldots,\,k_r \in~\bbN$ \[ \lim_{n\,\to\,\infty}\bbE\left[(Z_{n,1})_{k_1}(Z_{n,2})_{k_2}\cdots (Z_{n,r})_{k_r}\right] = \lambda_1^{k_1}\lambda_2^{k_2}\cdots \lambda_r^{k_r}, \] then $(Z_{n,1},\,\ldots,\,Z_{n,r}):\Omega_n\to\bbN^r$ converges jointly in distribution to a vector of random variables $(Z_1,\,\ldots,\,Z_r):\Omega\to\bbN^r$ where \begin{itemize} \item $Z_i\sim\Poisson(\lambda_i)$, $i=1,\,\ldots,\,r$ \item The random variables $Z_1,\,\ldots,\,Z_r$ form an independent family. \end{itemize} \end{theo} \subsection{Invariant Random Subgroups}\label{sec_IRS} We will phrase our results on random subgroups in the language of Invariant Random Subgroups. For a finitely generated group $\Gamma$, $\Sub(\Gamma)$ will denote the \emph{Chabauty space} of subgroups of $\Gamma$ (see for instance~\cite{Gelander} for an introduction). We will be interested in random index $n$ subgroups of such a group $\Gamma$. Given $n\in\bbN$, we will write \[ \clA_n(\Gamma) = \{H<\Gamma;\; [\Gamma:H] = n\} \subset \Sub(\Gamma), \] so that $a_n(\Gamma) = |\clA_n(\Gamma)|$. Studying a random index $n$ subgroup of $\Gamma$ comes down to understanding the measure $\mu_n$ on $\Sub(\Gamma)$, defined by \[ \mu_n = \frac{1}{a_n(\Gamma)} \sum_{H\,\in \,\clA_n(\Gamma)} \delta_H \] where $\delta_H$ denotes the Dirac mass on $H\in \Sub(\Gamma)$. $\mu_n$ is an example of what is called an \emph{Invariant Random Subgroup} (IRS) of $\Gamma$ -- \linebreak i.e. a Borel probability measure on $\Sub(\Gamma)$ that is invariant under conjugation by $\Gamma$. We will write $\IRS(\Gamma)$ for the space of IRS's of $\Gamma$ endowed with the weak-* topology. This space has been first studied under this name in~\cite{AbertGlasnerVirag} and~\cite{Bowen} and under a different name in~\cite{Vershik}. We will also use a characterisation for convergence in $\IRS(\Gamma)$ terms of fixed points. This characterisation is probably well known, but we couldn't find the exact statement in the literature (for instance~\cite[Lemma~16]{AbertGlasnerVirag} is very similar). We will provide a proof for the sake of completeness. Given a function $f:\Sub(\Gamma) \to \bbC$, we will write $\mu_n(f)$ for the integral of $f$ with respect to $\mu_n$ (all measures considered in our paper are finite sums of Dirac masses, so this is always well defined). Moreover, if $K\subset \Gamma$ is a conjugacy class then we will write \[ Z_K: \clA_n(\Gamma)\to\bbN \] for the random variable that counts the number of fixed points of any $g\in K$ on $\Gamma / H$. If we fix any $g\in K$ and $\varphi:\Gamma \to S_n$ is a transitive homomorphism corresponding to $H$ (cf. Proposition~\ref{subgp_trans}), then \[ Z_K(H) = \left|\big\{ j\in \{1,\,\ldots,\,n\};\;\varphi(g)\cdot j = j\big\}\right|. \] As noted by one of the referees of this paper, $Z_K$ can also be interpreted as the character on $\Gamma$ corresponding to the representation induced from the trivial representation of $H$. \begin{lemm}\label{lem_IRSfixedpoints} Let $\Gamma$ be a countable discrete group. Set \[ \mu_n = \frac{1}{a_n(\Gamma)} \sum_{\substack{ H\;<\; \Gamma \\ [\Gamma:H] \; = \; n}} \delta_H. \] and let $N\vartriangleleft \Gamma$. Then \[ \mu_n \stackrel{n\,\to\,\infty}{\longrightarrow} \delta_{N} \; \text{in }\IRS(\Gamma) \quad \Leftrightarrow \quad \left\{ \begin{array}{ll} \mu_n(Z_K) \stackrel{n\,\to\,\infty}{=} o(n) & \forall \text{ conjugacy class } K \not\subset N \\ \mu_n(Z_K)\stackrel{n\,\to\,\infty}{\sim} n & \forall \text{ conjugacy class } K \subset N \end{array} \right. \] \end{lemm} \begin{proof} We start with the fact that for $g\in K$, $\mu_n(\{H; g\in H\}) = \frac{1}{n}\mu_n(Z_K)$. Indeed, for any $p\in\{1,\,\ldots,\,n\}$, the map $\varphi\mapsto \Stab_\varphi\{p\}$ gives an $(n-1)!$-to-$1$ correspondence between transitive homomorphisms $\Gamma\to S_n$ and index $n$ subgroups of $\Gamma$. $Z_K(\varphi)$ equals the number of fixed points of $\varphi(g)$ on $\{1,\,\ldots,\,n\}$. As such \begin{equation}\label{eq_mufixedpts} \mu_n(\{H; g\in H\}) = \frac{1}{n\cdot t_n(\Gamma)} \sum_{p=1}^n \sum_{\varphi\,\in\,\clT_n(\Gamma)} \ind_{g\,\in\,\Stab_\varphi\{p\}}(\varphi) = \frac{1}{n}\mu_n(Z_K), \end{equation} where \[ \clT_n(\Gamma) = \left\{ \varphi\in \Hom(\Gamma,S_n);\; \varphi(\Gamma) \curvearrowright \{1,\ldots,n\} \text{ transitively}\right\}. \] Now, the topology on $\Sub(\Gamma)$ is generated by sets of the form \begin{align*} O_1(U) &{:=} \{ H\in \Sub(\Gamma); \; H\cap U \neq \emptyset \},\quad U \subset\Gamma \\ \intertext{and} O_2(V) &{:=} \{ H\in \Sub(\Gamma); \; H\cap V = \emptyset \},\quad V \subset\Gamma \text{ finite}, \end{align*} (see for instance~\cite{Gelander}). By the Portmanteau theorem, convergence $\mu_n \stackrel{w^*}{\longrightarrow} \delta_N$ is equivalent to \[ \liminf_{n\,\to\,\infty} \mu_n(O) \geq \delta_N(O) \] for every open set $O\subset \Sub(\Gamma)$. This is equivalent to proving that $\mu_n(O) \to 1$ for every open set $O\subset \Sub(\Gamma)$ such that $N\in O$. Since every open set is a union of sets of the form $O_1(U)$ and $O_2(V)$, $\mu_n \stackrel{w^*}{\longrightarrow} \delta_N$ if and only if \begin{equation}\label{eq_portmanteau} \mu_n(O_1(U)) \to 1 \text{ when }U\cap N \neq \emptyset \quad \text{and} \quad \mu_n(O_2(V)) \to 1 \text{ when }V\cap N = \emptyset \end{equation} for all $U\subset \Gamma$ and all finite $V\subset \Gamma$. Let us first prove that our conditions on the behaviour of $\mu_n(Z_K)$ imply convergence in $\IRS(\Gamma)$. We start by checking~\eqref{eq_portmanteau} for sets of the form $O_1(U)$. Suppose $g\in U\cap N$. Using~\eqref{eq_mufixedpts} and writing $K$ for the conjugacy class of $g$, \[ \mu_n(\{H; H\cap U \neq \emptyset\}) \geq \mu_n(\{H; g\in H\}) = \frac{1}{n}\mu_n(Z_K) \to 1, \] by our assumption on $\mu_n(Z_K)$. Now we deal with sets of the form $O_2(V)$. We will write $K(g)$ for the conjugacy class of an element $g\in\Gamma$. \eqref{eq_mufixedpts} gives us \[ \mu_n(\{H; H\cap V \neq \emptyset\}) \leq \frac{1}{n} \sum_{g\,\in\,V}\mu_n(Z_{K(g)}) \stackrel{n\,\to\,\infty}{\longrightarrow} 0, \] by our assumptions on $\mu_n(Z_{K(g)})$. This proves the first direction. For the other direction, suppose $g\in N$ then $\delta_{N}(O_1(\{g\})) = 1$ and hence by~\eqref{eq_portmanteau} and~\eqref{eq_mufixedpts}, we obtain \[ \liminf_{n\,\to\,\infty} \frac{1}{n}\mu_n(Z_K) = 1, \] which proves that $\mu_n(Z_K)\sim n$ as $n\to\infty$. Moreover, if $K$ is a conjugacy class such that $K\not\subset N$ and $g\in K$, then by~\eqref{eq_portmanteau} and~\eqref{eq_mufixedpts}, \[ \liminf_{n\,\to\,\infty} \mu_n(O_2(\{g\})) = \liminf_{n\,\to\,\infty} 1-\mu_n(O_1(\{g\})) = \liminf_{n\textbf{•}\to\,\infty} 1-\frac{1}{n}\mu_n(Z_K) \geq 1, \] which proves that $\mu_n(Z_K) = o(n)$ as $n\to\infty$. \end{proof} \subsection{Benjamini--Schramm convergence}\label{sec_BS_convergence} Now suppose that --- as many of the groups that we study do --- $\Gamma$ admits a finite simplicial complex $X$ as a classifying space. Picking a $0$-cell $x_0\in X$ gives an identification $\Gamma \simeq \pi_1(X,x_0)$. Moreover, an index $n$ subgroup $H<\Gamma$ gives rise to a pointed simplicial covering space \[ (Y_H,y_H) \to (X,x_0). \] This means that the measure $\mu_n$ above also gives rise to a probability measure $\nu_n$ on the set \[ \clK_D = \left\{ (Y,y_0); \begin{array}{c} Y \text{ a connected simplicial complex in} \\ \text{which the degree of }0\text{-cells is at} \\ \text{most }D,\; y_0 \in Y \text{ a }0\text{-cell} \end{array} \right\} \Bigg/ \sim \] for some $D>0$, where two pairs $(Y,y_0)\sim (Y',y_0')$ if there is a simplicial isomorphism $Y\to Y'$ that maps $y_0$ to $y_0'$. This set $\clK$ can be metrised by setting \[ d_\clK([Y,y_0],[Y',y_0']) = \frac{1}{1+\sup\left\{R\geq 0;\; \begin{array}{c} \text{The }R\text{-balls around }y_0\text{ and }y_0'\text{ are iso-}\\ \text{morphic as pointed simplicial complexes} \end{array}\right\}}. \] This allows us to speak of weak-* convergence of measures on $\clK_D$. If there is a pointed simplicial complex $[Z,z_0]\in\clK_D$ such that \[ \nu_n \stackrel{w^*}{\longrightarrow} \delta_{[Z,z_0]} \quad \text{as }n\to\infty, \] where $\delta_{[Z,z_0]}$ denotes the Dirac mass on $[Z,z_0]$, then we say that the random complex determined by $\nu_n$ \emph{Benjamini--Schramm converges} (or \emph{locally converges}) to $[Z,z_0]$. We will write $\clBS(\clK_D)$ for the space of probability measures on $\clK_D$ endowed with the weak-* topology. The procedure described above describes a continuous map \[ \IRS(\Gamma) \to \clBS(\clK_D), \] for some $D>0$, that depends on the choice of classifying space. \subsection{Betti numbers} One reason for determining Benjamini--Schramm limits is that they help determine limits of normalised Betti numbers. We will exclusively be dealing with homology with real coefficients in this paper. Given a simplicial complex $X$, we will write \[ b_k(X) = \dim(H_k(X;\bbR)). \] In order to state Elek's result, let $[\beta_1(R),o_1],\,\ldots,\,[\beta_M(R),o_M]$ denote all the complexes in $\clK_D$ that can appear as an $R$-ball of a complex in $\clK_D$. Note that this is a finite list, the length of which depends on $R$ and $D$. Moreover, given a finite simplicial complex $X$ of which all $0$-cells degree at most $D$, we will write \[ \rho_{\beta_i(R)}(X) = \frac{\left|\left\{x\in V(X);\; \text{The }R\text{-ball around }x\text{ is isomorphic to }\beta_i(R) \right\}\right|}{|V(X)|}, \] $i=1,\,\ldots,\,M$, where $V(X)$ denotes the set of $0$-cells of $X$. Elek's theorem now states: \begin{theo}[{Elek~\cite[Lemma~6.1]{Elek}}]\label{thm_Elek} Fix $D>0$ and let $(X_n)_n$ be a sequence of finite simplicial complexes in which the degree of every $0$-cell is bounded by $D$. If $|V(X_n)|\to\infty$ and for all $R>0$, for all $i$, $\rho_{\beta_i(R)}(X_n)$ converges as $n\to\infty$, then \[ \lim_{n\,\to\,\infty}\frac{b_k(X_n)}{|V(X_n)|} \] exists for all $k\in\bbN$. \end{theo} Often, an explicit limit for these normalised Betti numbers can be determined in terms of $\ell^2$-Betti numbers. We will not go into this theory very deeply in this paper and refer the interested reader to for instance~\cite{Lueck_Book} or~\cite{Kammeyer} for more information. If $\Gamma$ is a group and $X$ is a finite $\Gamma$-CW complex, then we will write $b^{(2)}_k(X;\Gamma)$ for the $k$\textsuperscript{th} $\ell^2$-Betti number of the pair $(X,\Gamma)$. We will rely on the L\"uck approximation theorem~\cite{Lueck} (see also~\cite[Theorem~5.26]{Kammeyer}). If $\Gamma$ is a group and $\Gamma_i\vartriangleleft \Gamma$, $i\in \bbN$ are such that \[ [\Gamma:\Gamma_i] < \infty \quad \text{and} \quad \Gamma_{i+1} < \Gamma_i, \; i\in\bbN, \] then we call $(\Gamma_i)_i$ a \emph{chain of finite index normal subgroups of }$\Gamma$. \begin{theo}[L\"uck approximation theorem] \label{thm_Lueck} Let $\Gamma$ be a group and $X$ be a finite free $\Gamma$-CW complex. Moreover, let $(\Gamma_i)_i$ be a chain of finite index normal subgroups of $\Gamma$ and set \[ \Theta = \bigcap_{i\,\in\,\bbN}\Gamma_i. \] Then \[ \lim_{i\,\to\,\infty} \frac{b_k(X/\Gamma_i)}{[\Gamma:\Gamma_i]} = b^{(2)}(\Theta\backslash X;\; \Gamma/\Theta). \] \end{theo} In order to prove convergence of Betti numbers we are after (Theorem~\ref{thm_main3}$\MK$\eqref{theo1.3.c}), we will use the approximation theorems of Elek and L\"uck to deduce the following lemma. Like Lemma~\ref{lem_IRSfixedpoints}, this lemma is probably well known (for instance~\cite[Theorem~3.1]{BergeronGaboriau} is similar) but, as far as we know, not available in the literature in this form, so we will provide a proof. \begin{lemm}\label{lem_betticonvergence} Let $\Gamma$ be a group that admits a finite simplicial complex $X$ as a classifying space. Set \[ \mu_n = \sum_{\substack{H\;< \; \Gamma \\ [\Gamma:H]\;=\;n}} \delta_H. \] If there exists a normal subgroup $N\vartriangleleft \Gamma $ such that $\Gamma/N$ is residually finite and \[ \mu_n \stackrel{n\,\to\,\infty}{\longrightarrow} \delta_N \] in $\IRS(\Gamma)$. Then for every $\varepsilon>0$ and every $k\in\bbN$, \[ \mu_n\left(\left|\frac{b_k(H)}{n} - b_k^{(2)}\left(N\backslash \widetilde{X}; \Gamma/N\right)\right| < \varepsilon \right) \stackrel{n\,\to\,\infty}{\longrightarrow} 1, \] where $\widetilde{X}$ denotes the universal cover of $X$. \end{lemm} \begin{proof} Recall that $V(X)$ denotes the set of $0$-cells of $X$ and write $D$ for the maximal degree among these $0$-cells. Fix a choice of $0$-cell $x_0\in V(X)$, to obtain an identification $\Gamma\simeq \pi_1(X,x_0)$ and denote the measure on $\clK_D$ induced by $\mu_n$ by $\nu_n \in \clBS(\clK_D)$. Finally, we will let $(Z,z_0)\to (X,x_0)$ denote the pointed cover corresponding to $N$. For $g\in K\subset \Gamma$, where $K$ is a conjugacy class, $Z_K(H)$ equals the number of lifts of $x_0$ at which the loop in $X$ corresponding to $g$ lifts to a closed loop. Now consider the set $W_R$ of all $g\in \Gamma$ that have translation distance at most $R$ on the universal cover $\widetilde{X}$. This set consists of a finite number of conjugacy classes. If $H<\Gamma$ is such that $[\Gamma:H] = n$ and, as $n\to\infty$, \begin{equation}\label{eq_fparelittle-o-n} \left\{ \begin{array}{ll} Z_K(H) = o(n) & \text{if } K\not\subset N \cap W_R \\ n-Z_K(H) = o(n) & \text{if } K\subset N \cap W_R \end{array} \right. \end{equation} then the number of lifts $y$ in the cover of $X$ corresponding to $H$, around which the $R$-ball $B_R(y)$ is not isometric to the $R$-ball $B_R(z_0)$ around $z_0\in Z$ is $o(n)$ (this uses that $W_R$ consists of finitely many conjugacy classes). Lemma~\ref{lem_IRSfixedpoints} tells us that for any finite set of conjugacy classes, \eqref{eq_fparelittle-o-n} is satisfied with asymptotic $\mu_n$-probability $1$. So we obtain that for every $R, \varepsilon > 0$ \[ \nu_n\left(\left\{[Y,y];\; \frac{|\{v\in V(Y)\text{ a lift of }x_0;\;B_R(v) \simeq B_R(z_0) \}|}{n} > 1- \varepsilon \right\} \right) \stackrel{n\,\to\,\infty}{\longrightarrow} 1. \] Now, since $V(X)$ is finite we can repeat the argument finitely many times and obtain that for each $R>0$ there is a finite list $B_1,\,\ldots,\,B_L$ of finite simplicial complexes and a finite list of densities $\rho_1,\,\ldots,\,\rho_L >0$ such that \[ \nu_n\left(\left\{[Y,y];\;\forall i: \; \left|\frac{|\{v\in V(Y);\;B_R(v) \simeq B_i \}|}{n} -\rho_i \right| < \varepsilon \right\} \right) \stackrel{n\to\infty}{\longrightarrow} 1. \] So, by Theorem~\ref{thm_Elek}, for every $\varepsilon>0$ there exists a $\delta>0$ such that if we fix any finite pointed complex $[Q,q]\in\clK_D$ that satisfies \[ \left|\frac{|\{v\in V(Q);\;B_R(v) \simeq B_i \}|}{n} -\rho_i \right| < \delta \quad \text{for }i=1,\,\ldots,\,L, \] then, \begin{equation}\label{eq_betticlose} \nu_n\left(\left\{[Y,y]; \; \left|\frac{b_k(Y)}{n} - \frac{b_k(Q)}{|V(Q)|} \right| < \varepsilon \right\} \right) \stackrel{n\,\to\,\infty}{\longrightarrow} 1 \quad \text{for all }k\in\bbN. \end{equation} Using the fact that $\Gamma/N$ is residually finite, we can find a chain of normal subgroups $H_i \vartriangleleft \Gamma/N$ of finite index such that $\cap_i H_i = \{e\}$. We lift this sequence of subgroups to a sequence $\widetilde{H}_i \vartriangleleft \Gamma$ and obtain a sequence of pointed covers $(Q_i,q_i) \to (X,x_0)$. Now, if we set \[ \eta_i = \frac{1}{\left[\Gamma:\widetilde{H}_i\right]} \sum_{u\,\in\,\left(\Gamma/\widetilde{H}_i\right)\cdot q_i} \delta_{[Q_i,u]} \in \clBS(\clK_D), \] then $\eta_i \stackrel{i\,\to\,\infty}{\longrightarrow} \delta_N$ by construction. So, for~\eqref{eq_betticlose}, we can take a $(Q_i,q_i)$ deep in the sequence we just constructed. Moreover, by Theorem~\ref{thm_Lueck} we have \[ \frac{b_k(Q_i)}{n} \approx b_k^{(2)}\left(N\backslash \widetilde{X}; \Gamma/N\right), \] which finishes the proof of Lemma~\ref{lem_betticonvergence}. \end{proof} \section{Subgroup growth}\label{sec_subgroupgrowth} Our first objective is to prove Theorem~\ref{thm_main1} -- the asymptotic subgroup growth of our groups $\Gamma_{p_1,\,\ldots,\,p_m}$. Note that this follows from the following theorem together with Theorems~\ref{hn_cyclic} and~\ref{thm_muller-transitive} and Proposition~\ref{subgp_trans}. \begin{theo}\label{thm_subgroup_growth} Let $p_1,\,\ldots,\,p_m \in \bbN_{>\,1}$ such that $\sum_{i=1}^m \frac{1}{p_i} < m-1$. Then, as $n\to\infty$, \[ a_n \left(\Gamma_{p_1,\,\cdots,\,p_m}\right) \sim a_n\left(C_{p_1}\ast \cdots \ast C_{p_m}\right). \] \end{theo} \begin{proof} We have already mentioned that the group $\Gamma_{p_1, \,\cdots,\,p_m}$ is a central extension \[ 1\longrightarrow \bbZ \longrightarrow \Gamma_{p_1,\,\ldots,\,p_m} \stackrel{\Phi_{p_1,\,\ldots,\,p_m}}{\longrightarrow} C_{p_1} * \cdots * C_{p_m} \longrightarrow 1 \] where $\Phi_{p_1,\,\ldots,\,p_m}$ sends $x_j$ to the generator of $C_{p_j}$. Using this alongside Proposition~\ref{prop_subgp_quotient}, implies that \begin{multline*} 1 \leq \frac{a_n \left(\Gamma_{p_1,\,\cdots,\,p_m}\right)}{a_n\left(C_{p_1}\ast \cdots \ast C_{p_m}\right)} \leq \frac{\sum_{r|n} a_{n/r}\left(C_{p_1}\ast \cdots \ast C_{p_m}\right)r^{m}}{a_n\left(C_{p_1}\ast \cdots \ast C_{p_m}\right)} \\ = 1 + \frac{\sum\limits_{\substack{r|n \\r\,>\,1}} a_{n/r}\left(C_{p_1}\ast \cdots \ast C_{p_m}\right)r^{m}}{a_n\left(C_{p_1}\ast \cdots \ast C_{p_m}\right)} \end{multline*} Take $r_n$ to be the divisor of $n$ with $1 < r_n \leq n$, that maximises $a_{n/r}(C_{p_1}\ast \cdots \ast C_{p_m})r^{m}$. Since the number of divisors of $n$ is certainly bounded above by $n$, we see \[ \frac{\sum\limits_{\substack{r|n \\ r\,>\,1}} a_{n/r}\left(C_{p_1}\ast \cdots \ast C_{p_m}\right)r^{m}}{a_n\left(C_{p_1}\ast \cdots \ast C_{p_m}\right)} \leq n \frac{a_{n/r_n}\left(C_{p_1}\ast \cdots \ast C_{p_m}\right)r_n^{m}}{a_n\left(C_{p_1}\ast \cdots \ast C_{p_m}\right)}. \] Using the growth rates of $a_n(C_{p_1}\ast \cdots \ast C_{p_m})$ which are obtained from Theorem~\ref{hn_cyclic} and Theorem~\ref{thm_muller-transitive}, we get \begin{multline*} \lim_{n\,\to\,\infty}\left(nr_n^{m}\frac{a_{n/r_n}\left(C_{p_1}\ast \cdots \ast C_{p_m}\right)}{a_n(C_{p_1}\ast \cdots \ast C_{p_m})}\right) \\ = \lim_{n\,\to\,\infty}\left( \exp \left(\sum_{i=1}^{m} \sum_{\substack{d|p_i\\ d\,<\, p_i}} \frac{1}{d} \left(\left(\frac{n}{r_n}\right)^{\frac{d}{p_i}} - n^{\frac{d}{p_i}} \right) \right) n\left(\frac{(n/r_n)!}{n!}\right)^{\sum\limits_{i=1}^{m}\alpha_{p_1,\,\cdots,\,p_m}} r_n^{\beta_{p_1,\,\cdots,\,p_m}} \right) \\ \begin{aligned} &\leq \lim_{n\,\to\,\infty} \left(n\left(\frac{(n/r_n)!}{n!}\right)^{\alpha_{p_1,\,\cdots,\,p_m}} r_n^{\beta_{p_1,\,\cdots,\,p_m}} \right)\\ &\leq \lim_{n\,\to\,\infty} \left( \left(\frac{(n/2)!}{n!}\right)^{\alpha_{p_1,\,\cdots,\,p_m}} n^{1+\beta_{p_1,\,\cdots,\,p_m}} \right)= 0, \end{aligned} \end{multline*} where we have used $2\leq r_n \leq n$, and denoted $\alpha_{p_1,\cdots, p_m} = \sum_{i=1}^{m}(1 - \frac{1}{p_i}) -1$ and $\beta_{p_1,\,\cdots,\,p_m} = m-1 + \frac{1}{2}(\sum_{i=1}^{m}(1 - \frac{1}{p_i}))$. Hence we have shown \[ {a_n \left(\Gamma_{p_1,\,\cdots,\,p_m}\right)} \sim {a_n\left(C_{p_1}\ast \cdots \ast C_{p_m}\right)}, \] as $n\to\infty$. \end{proof} As an immediate consequence of this alongside Proposition~\ref{subgp_trans}, we also find that \[ t_n\left(C_{p_1} \ast \cdots \ast C_{p_m}\right) \sim t_n\left(\Gamma_{p_1,\,\ldots,\,p_m}\right) \] as $n\to\infty$. Moreover, we obtain: \begin{coro}\label{cor_hn_tn} Let $p_1,\,\ldots,\,p_m \in \bbN_{>\,1}$ such that $\sum_{i=1}^m \frac{1}{p_i} < m-1$. Then \[ h_n\left(\Gamma_{p_1,\,\ldots,\,p_m}\right) \sim t_n\left(\Gamma_{p_1,\,\ldots,\,p_m}\right) \] as $n\to\infty$. \end{coro} Before we prove this corollary, we note that together with Proposition~\ref{subgp_trans} and Theorem~\ref{thm_main1}, it implies Theorem~\ref{thm_main2}. \begin{proof}[Proof of Corollary~\ref{cor_hn_tn}] Write $\Gamma=\Gamma_{p_1,\,\ldots,\,p_m}$ and $\chi = m-1-\sum_{i=1}^m \frac{1}{p_i}$. Fix any $\alpha<\chi$. Our goal will be to prove that there exists a constant $C>0$ such that \[ \frac{h_n(\Gamma)}{(n-1)!} \leq \left(1 + \frac{C}{n^\alpha}\right) \cdot a_n(\Gamma) \] for all $n\geq 1$. Observe that this, combined with the fact that $\frac{h_n(\Gamma)}{(n-1)!}\geq a_n(\Gamma)$ and Proposition~\ref{subgp_trans}, is sufficient to prove the corollary. We will prove our claim by induction. Let us first consider the induction step. We will use the fact (see~\cite{LubotzkySegal} Corollary~1.1.4) that \[ \frac{h_n(\Gamma)}{(n-1)!} = a_n(\Gamma) + \sum_{k=1}^{n-1} \frac{h_{n-k}(\Gamma)}{(n-k)!}\; a_k(\Gamma). \] Using the induction hypothesis, we get \begin{multline*} \frac{h_n(\Gamma)}{(n-1)!} \leq a_n(\Gamma) + \sum_{k=1}^{n-1} \left(1 + \frac{C}{(n-k)^\alpha}\right)\; a_{n-k}(\Gamma)\; a_k(\Gamma) \\ \leq a_n(\Gamma) + (1+C)\cdot \sum_{k=1}^{n-1} a_{n-k}(\Gamma)\; a_k(\Gamma). \end{multline*} Theorem~\ref{thm_subgroup_growth}, together with Lemma~\ref{lem_rapidgrowth}, \[ \frac{h_n(\Gamma)}{(n-1)!} \leq a_n(\Gamma) \cdot \left(1+\frac{C'\cdot (1+C)}{n^\chi}\right) = a_n(\Gamma) \cdot \left(1+\frac{C}{n^\alpha} \frac{C'\cdot (1+C)}{C\cdot n^{\chi-\alpha}}\right) \] for some uniform $C'>0$. Now, we observe that, for fixed $C>0$, the factor $\frac{C'\cdot (1+C)}{C\cdot n^{\chi-\alpha}}$ can be made smaller than $1$ by increasing $n$, meaning that the induction step works after a certain $n_0$. To get the base case to hold, we need to increase $C$, which only decreases the factor $\frac{C'\cdot (1+C)}{C\cdot n^{\chi-\alpha}}$, thus proving the corollary. \end{proof} \section{Random subgroups and covers}\label{sec_random} In this section we will study the properties of random index $n$ subgroups of $\Gamma_{p_1,\,\ldots,\,p_m}$ and random degree $n$ covers of torus knot complements. The basic idea is to prove that a random index $n$ subgroup of $C_{p_1}*\cdots * C_{p_m}$ (as an element of $\IRS(C_{p_1}*\cdots*C_{p_m})$) converges to the trivial subgroup. This, together with Theorem~\ref{thm_main2} will then imply that a random index $n$ subgroup of $\Gamma_{p_1,\,\ldots,\,p_m}$ converges to $L_{p_1,\,\ldots,\,p_m}$. Both of these results will be quantitative in the sense that we have control over the number of conjugacy classes a given conjugacy class of either $C_{p_1}*\cdots * C_{p_m}$ or $\Gamma_{p_1,\,\ldots,\,p_m}$ lifts to in a random index $n$ subgroup (Theorem~\ref{thm_main3}$\MK$(a)). This then immediately implies the fact that a random degree $n$ cover of $X_{p_1,\,\ldots,\,p_m}$ Benjamini--Schramm converges to $X_{p_1,\,\ldots,\,p_m}^\Phi$. Combined with Lemma~\ref{lem_betticonvergence}, this convergence implies our result on Betti numbers. \subsection{Set-up} Recall that, if $\Gamma$ is a group and $n\in\bbN$, then \[ \clA_n(\Gamma) = \{H<\Gamma;\; [\Gamma:H] = n\}, \] and that \[ Z_K: \clA_n(\Gamma)\to\bbN \] counts the number of fixed points of $g\in K$ acting on $\Gamma /H$. If we fix any $g\in K$ and $\varphi:\Gamma \to S_n$ is a transitive homomorphism corresponding to $H$ (cf. Proposition~\ref{subgp_trans}), then \[ Z_K(H) = \left|\big\{ j\in \{1,\,\ldots,\,n\};\;\varphi(g)\cdot j = j\big\}\right|. \] Our main goal now is to determine the asymptotic behaviour of the distribution of these random variables as $n\to\infty$. \subsection{Fixed point statistics of infinite order elements of {$C_{p_1}*\cdots*C_{p_m}$}} Our first step is to enlarge our probability space and prove our results there. Concretely, the expression for $Z_K$ in terms of fixed points is well-defined for any homomorphism, not just for transitive ones. As such, we can interpret $Z_K$ as a random variable \[ Z_K : \Hom\left(C_{p_1}*\cdots*C_{p_m},S_n\right) \to \bbN \] as well, where we equip $\Hom(C_{p_1}*\cdots*C_{p_m},S_n)$ with the uniform measure $\bbP^{\Hom}_n$. We will denote the expected value with respect to this measure by $\bbE^{\Hom}_n$. It will turn out that for conjugacy classes $K$ of elements of infinite order, $Z_K$ will limit to a sum of Poisson distributed random variables. In this section we will work this out, starting with some set-up. Suppose that $g\in C_{p_1}*\cdots*C_{p_m}$ is of infinite order and that $K$ is its conjugacy class. Write \[ g = x_{j_1}^{s_1} \cdots x_{j_l}^{s_l} \] as a reduced word in the generators $x_1,\,\ldots,\,x_m$ of $C_{p_1}*\cdots*C_{p_m}$. By potentially changing the conjugate, we may also assume that the word is cyclically reduced. Now, if we want $v\in \{1,\,\ldots,\,n\}$ to be a fixed point of $\varphi(g)$ for some $\varphi\in\Hom(C_{p_1}*\cdots*C_{p_m},S_n)$, then there need to be sequences $(w_{t,0}\; w_{t,1}\;\ldots w_{t,s_t})$, for $t=1,\ldots,l$, such that \begin{equation}\label{eq_phisatisfiesw} \left\{ \begin{array}{ll} \varphi(x_{j_t})(w_{t,q}) = w_{t,q-1}, & q=1,\,\ldots,\,s_t\\[2mm] w_{t,s_t} = w_{t+1,0} & t=1,\,\ldots,\,l-1 \\[2mm] w_{1,0}= w_{l,s_l} = v. & \end{array} \right. \end{equation} In other words, if we want $v$ to be a fixed point of $g$, then certain sequences (for which there are many choices) need to appear in the disjoint cycle decompositions of the images of the generators $x_1,\,\ldots,\,x_m$. Figure~\ref{pic_cycle} gives an example of the situation. Note that some of the labels in these sequences may coincide. \begin{figure} \begin{center} \begin{overpic}{pic_cycle} \put(12,69) {{\tiny $v=w_{1,0}=w_{3,2}$}} \put(1,96) {$\varphi(x_3)$} \put(40,84) {{\tiny $w_{3,1}$}} \put(74,97) {$\varphi(x_3)$} \put(90,74) {{\tiny $w_{3,0} = w_{2,1}$}} \put(99,53) {$\varphi(x_1)$} \put(51,40) {{\tiny $w_{2,0}=w_{1,4}$}} \put(86,13) {$\varphi(x_2)$} \put(62,18) {{\tiny $w_{1,3}$}} \put(32,12) {$\varphi(x_2)$} \put(18,21) {{\tiny $w_{1,2}$}} \put(-22,22) {$\varphi(x_2)$} \put(12,42) {{\tiny $w_{1,1}$}} \put(-25,62) {$\varphi(x_2)$} \end{overpic} \caption{$v$ is a fixed point of $\varphi(x_2^4x_1x_3^2)$.}\label{pic_cycle} \end{center} \end{figure} These sequences naturally correspond to labelled graphs. The vertices are labelled by the numbers $w_{t,i}$, which we connect with edges labelled by the generators $x_{j_i}$ according to the conditions in~\eqref{eq_phisatisfiesw}. We will say that $\varphi$ \emph{satisfies} this labelled graph -- another way of saying this is that the corresponding graph is a subgraph of the Schreier graph for the action of $\varphi(C_{p_1}*\cdots * C_{p_m})$ on $\{1,\,\ldots,\,n\}$. This allows us to decompose the variable $Z_K$ into a finite sum \begin{equation}\label{eq_decompZK} Z_K = \sum_{G} \mu(G)\cdot Y_G \end{equation} where \begin{itemize} \item the sum is over finite directed graphs $G$ such that \begin{itemize} \item the edges are labelled with generators $x_j$, \item for all $j=1,\,\ldots,\,m$: among the edges emanating from any vertex, at most one is labelled $x_j$ \item $G$ contains a directed circuit that runs through all of its edges a finite number of times in such a way that the word spelled out by the generators on these edges (in the order given by the circuit) is $g$ \item $\mu(G)$ is the number of fixed points of $g$ that the graph $G$ gives rise to. \end{itemize} Note that these graphs $G$ do \emph{not} carry vertex labels. We will call such graphs \emph{$K$-graphs}. \item $Y_G(\varphi)$ counts the number of labelled copies of $G$ that are satisfied by $\varphi$. \end{itemize} It will turn out that, asymptotically, the sum above is dominated by two types of graphs. That is cycles (connected $2$-regular graphs), and what we will call lines of circles. The latter are connected graphs that decompose into edge-disjoint cycles, in such a way that \begin{itemize} \item every vertex is incident to at most two of these cycles, \item every cycle is incident with at most two other cycles, \item all the labels on a given cycle are the same, \item the labels on adjacent cycles are distinct, and \item if a cycle is labelled with $x_i$, then its length is $p_i$ if it is incident to two other cycles, and $\frac{p_i}{2}$ if it is incident to one other cycle. \end{itemize} Figure~\ref{pic_lineofcircles} shows an example: \begin{figure}[!h] \begin{center} \begin{overpic}{pic_lineofcircles} \put(20,0){$x_1$} \put(-1,20){$x_1$} \put(-1,20){$x_1$} \put(21,20){$x_2$} \put(43,21){$x_2$} \put(53,22){$x_3$} \put(70,22.5){$x_3$} \put(83,23){$x_4$} \put(76,2){$x_3$} \put(64,-2.5){$x_3$} \put(49,1.5){$x_3$} \put(34,-2.5){$x_2$} \end{overpic} \caption{A line of circles corresponding to the element $g=x_3^3x_4x_3^2 x_2^2x_1^2x_2$. Here we have $p_1=4$, $p_2=3$, $p_3=5$, $p_4=2$, so that $g$ is a product of two elements of order two.}\label{pic_lineofcircles} \end{center} \end{figure} The conditions above guarantee that the group element that is formed by traversing such a graph once is a product of two elements of order two. Since we're assuming the group element we consider is written in cyclically reduced form, these elements of order two are distinct. Note that if $g=g_0^k$ is a non-trivial power of a primitive element $g_0$, the sum contains terms corresponding to graphs for $g_0^d$ for every divisor $d$ of $k$. These will all contribute to the asymptotic behaviour of $Z_K$. In the theorem below, given a graph $G$ as above, $\widehat{G}$ is the graph that is obtained from $G$ by ``completing the cycles''. That is, we can write $G$ as a union of disjoint loops and segments that are all labelled with a single generator. We do this in such a way that the segments all have maximal length, i.e. such that no two segments labelled with the same generator are incident to each other. $\widehat{G}$ is then the graph in which we complete all the segments labelled with $x_j$ to cycles of length $p_j$. Moreover, $\Aut(G)$ is the group of edge-label-preserving symmetries of the graph $G$. We have: \begin{theo}\label{thm_factorialmomentsY} Let $p_1,\,\ldots,\,p_m\in \bbN$ and let $K_1,\,\ldots, \,K_r \subset C_{p_1}*\cdots*C_{p_m}$ be conjugacy classes out of which no pair have a common root and none of which contains elements of finite order. Finally, let $\{G_{ij}\}_{j\in J_i}$ be a finite set of distinct $K_i$-graphs for all $i=1,\,\ldots,\,r$. Then \begin{itemize} \item If one of the graphs $G_{lm}$ is neither a cycle, nor a line of circles and $k_{ij} \in \bbN$, $j\in J_i$, $i=1,\,\ldots,\,r$ is a tuple so that $k_{lm}>0$, we have \[ \bbE_{n}^{\Hom}\left[\prod_{i,j}\left(Y_{G_{ij}}\right)_{k_{ij}}\right] = O\left(n^{-\alpha}\right),\quad \text{for some }\alpha>0 \] as $n\to\infty$. \item if not, then we have \[ \bbE_{n}^{\Hom}\left[\prod_{i,j}\left(Y_{G_{ij}}\right)_{k_{ij}}\right] = \prod_{i,j} \lambda(G_{ij})^{k_{ij}} + O\left(n^{-\alpha}\right),\quad \text{for some }\alpha>0 \] as $n\to\infty$. Here $\lambda(G_{ij}) = 1\; \Big/ \; |\Aut(\widehat{G}_{ij})|$. \end{itemize} \end{theo} The implied constants in the two bounds in the theorem depend both on the graphs $\{G_{ij}\}_{i,j}$ and the tuple $(k_{ij})_{i,j}$. As noted in the introduction, the case of lines of circles was first worked out by Puder--Zimhoni~\cite{PuderZimhoni} (in a somewhat different language). Before we prove the theorem, we observe that it immediately implies the following corollary, which in the case where $r=1$, was proved for certain conjugacy classes by Benaych-Georges~\cite{BG1}. In fact, for these conjugacy classes, Benaych-Georges proves similar results for all cycles, and not just the fixed points, but he does not prove the independence for different conjugacy classes. \begin{coro}\label{cor_poissononhom} Let $p_1,\,\ldots,\,p_m\in \bbN$ and let $K_1,\,\ldots,\, K_r \subset C_{p_1}*\cdots*C_{p_m}$ be conjugacy classes out of which no pair have a common root and none of which contain elements of finite order. Then, as $n\to\infty$, the vector of random variables \[ \left(Z_{K_1},\,\ldots,\,Z_{K_r}\right): \Hom\left(C_{p_1}*\cdots*C_{p_m},S_n\right) \to \bbN^r \] converges jointly in distribution to a vector \[ \left(Z_{K_1}^\infty,\, \ldots,\,Z_{K_r}^\infty\right):\Omega \to \bbN^r \] of independent random variables, such that \begin{itemize} \item if $K_i$ is the conjugacy class of a $k^{th}$ power of a primitive element that is not a product of two distinct elements of order two, then \[ Z_{K_i}^\infty \sim \sum_{d|k}\; d \cdot X_{1/d}, \] where $ X_{1/d} \sim \Poisson(1/d)$ and all these variables are independent. \item if $K_i$ is the conjugacy class of a $k^{th}$ power of a primitive element that is a product of two distinct elements of order two, then \[ Z_{K_i}^\infty \sim \sum_{d|k}\; 2d \cdot X^{d,1}_{1/2d} + \sum_{d|k,\; d\text{ even}} d\cdot X_{1/2}^{d,2}+d\cdot X_{1/2}^{d,3} + \sum_{d|k,\; d\text{ odd}} d \cdot X_1^{d,4} \] where $X^{d,1}_{1/2d} \sim \Poisson(1/2d)$, $X_{1/2}^{d,2}\sim \Poisson(1/2)$, $X_{1/2}^{d,3}\sim \Poisson(1/2)$, $X_1^{d,4}\sim \Poisson(1)$ and all these variables are independent. \end{itemize} \end{coro} \begin{proof}[Proof of Corollary~\ref{cor_poissononhom}] Theorem~\ref{thm_factorialmomentsY} together with Theorem~\ref{thm_moments} implies that, when $\{G_{ij}\}_{j\in J_i}$ is a finite set of distinct $K_i$-graphs for all $i=1,\,\ldots,\,r$, then, as $n\to\infty$, the vector of random variables \[ \left(Y_{G_{ij}}: \Hom\left(C_{p_1}*\cdots*C_{p_m},S_n\right) \longrightarrow \bbN\right)_{i,j} \] converges jointly in distribution to a vector \[ \left(Y_{G_{ij}}^\infty:\Omega \to \bbN\right)_{i,j} \] of independent random variables, such that: \[ Y_{G_{ij}}^\infty \sim \Poisson\left(\lambda(G_{ij})\right). \] So what remains is to use the decomposition in~\eqref{eq_decompZK} in order to write the limits of $Z_{K_{ij}}$ as a sum of Poisson-distributed variables. We again pick $g\in K_{ij}$ and write $g=g_0^k$ for some primitive element $g_0$. As the corollary suggests, there are two cases to consider. If $g_0$ is not a product of two distinct elements of order two, none of the graphs in the decomposition~\eqref{eq_decompZK} can be a line of circles. So the only graphs that contribute to the limit are cycles, and we obtain a cycle of length $d$ for every divisor of length $d$. The number of fixed points that such a cycle gives rise to ($\mu(G_{ij})$) is $d$, and the automorphism group of the cycle is the cyclic group of order $d$, which proves the first part of the corollary. Now suppose that $g_0 = ab$ where $a,b\in C_{p_1}*\cdots*C_{p_m}$ are distinct involutions. For each divisor $d$ of $k$, we now get two types of terms in~\eqref{eq_decompZK} that contribute to the limit: one cycle and one or two lines of circles. Pretending for a moment that $a$ and $b$ are standard generators, the graphs corresponding to $d|k$ correspond to a fixed point of $(ab)^d$ and are: \begin{itemize} \item Lines of $d+1$ circles, alternatingly labelled with $a$'s and $b$'s. If $d$ is even, then there are two distinct such lines of circles -- either both outer circles are labelled with $a$ or both are labelled with $b$ -- and if $d$ is odd, there is only one such line of circles -- in which one outer circle is labelled $a$ and the other is labelled $b$. \item A cycle of length $2d$, alternatingly labelled with $a$'s and $b$'s. \end{itemize} In the first case, all $d$ vertices in the graph $G_{ij}$ are fixed by $(ab)^d$ and hence by $(ab)^k$. This means that $\mu(G_{ij}) = d$. If $d$ is odd, the graph has no non-trivial automorphisms, if it's even the automorphism group has order $2$. The case of cycles is also different from before: because both $a$ and $b$ are involutions, \emph{all} vertices of the cycle are fixed and not just half of them, which means that if $G_{ij}$ is a cycle, then $\mu(G_{ij}) = 2d$ in this case. Moreover, the automorphism group is now the dihedral group of order $2d$. If the involutions $a$ and $b$ are not standard generators (even if we can assume that $ab$ is cyclically reduced, this does not imply that $a$ and $b$ are), then the result is the same. Indeed, in the case of cycles, the corresponding cycle can be obtained from the cycle labeled with $a$ and $b$ by replacing each edge with a segment labelled with a reduced word for $a$ or $b$ respectively. The number of fixed points that the resulting cycle gives rise to is still $2d$, also, because it's $\Aut(\widehat{G})$ that shows up as the mean (as opposed to $\Aut(G)$), the symmetries persist. In the case of lines of circles, we can obtain the correct graph by a similar replacement. $a$ and $b$ are conjugate to $x_{i_a}^{p_{i_a}/2}$ and $x_{i_b}^{p_{i_b}/2}$ for some (not necessarily distinct) $i_a$ and $i_b$. That is, we may for instance write \[ a= x_{j_1}^{s_1} \cdots x_{j_l}^{s_l} \; \cdot \; x_{i_a}^{p_{i_a}/2} \; \cdot \; x_{j_l}^{p_{j_l}-s_l}\cdots x_{j_1}^{p_{j_1}-s_1}. \] For some standard generators $x_{j_1},\,\ldots,\,x_{j_l}$ and some $0< s_1 < p_1, \,\ldots,\, 0< s_l < p_{j_l}$. The replacements we carry out are explained in Figures~\ref{pic_replacement1} and~\ref{pic_replacement2}. \begin{figure} \begin{center} \begin{overpic}[scale=0.5]{pic_replacement1} \put(4,10){\tiny{$a$}} \put(39,11.5){\tiny{$x_{j_1}$}} \put(42,5.5){\tiny{$x_{j_1}$}} \put(24,20){\tiny{length $p_{j_1}-s_1$}} \put(24,-2){\tiny{length $s_1$}} \put(51,10.5){\tiny{$x_{j_2}$}} \put(56.5,11){\tiny{$x_{j_2}$}} \put(53,4.5){\tiny{$x_{j_2}$}} \put(54,20){\tiny{length $p_{j_2}-s_2$}} \put(54,-3){\tiny{length $s_2$}} \put(86,16.5){\tiny{$x_{i_a}$}} \put(98,2.5){\tiny{$x_{i_a}$}} \put(87,7){\tiny{$p_{i_a}/2$}} \end{overpic} \caption{A circle labelled $a$ that is at one of the two ends of the original line of circles is replaced by a line of $l+1$ circles, of lengths $p_{j_1}$, $p_{j_2}$, $\ldots$, $p_{j_l}$ and $p_{i_a}/2$ and labelled with $x_{j_1},\,\ldots,\,x_{j_l}$ and $x_{i_a}$ respectively. The points of attachment of these circles are chosen in such a way that $a$ fixes the leftmost vertex of the graph. The necessary lengths are indicated in the figure.}\label{pic_replacement1} \end{center} \end{figure} \begin{figure} \begin{center} \begin{overpic}[scale=0.5]{pic_replacement2} \put(2.5,9){\tiny{$a$}} \put(6.5,5.5){\tiny{$a$}} \put(15,15.5){\tiny{length $p_{j_1}-s_1$}} \put(26,9.5){\tiny{$x_{j_1}$}} \put(28.5,6.5){\tiny{$x_{j_1}$}} \put(35,16.5){\tiny{length $p_{j_2}-s_2$}} \put(34.5,9.5){\tiny{$x_{j_2}$}} \put(37.5,6.5){\tiny{$x_{j_2}$}} \put(55,16.5){\tiny{length $p_{i_a}/2$}} \put(59,9.5){\tiny{$x_{i_a}$}} \put(61.5,6.5){\tiny{$x_{i_a}$}} \put(80,16.5){\tiny{length $s_2$}} \put(93,16.5){\tiny{length $s_1$}} \put(83.5,9.5){\tiny{$x_{j_2}$}} \put(86.5,6.5){\tiny{$x_{j_2}$}} \put(93,0){\tiny{length $p_{j_1}-s_1$}} \put(75,-1){\tiny{length $p_{j_2}-s_2$}} \put(55,-2){\tiny{length $p_{i_a}/2$}} \put(35,-1){\tiny{length $s_2$}} \put(92,9.5){\tiny{$x_{j_1}$}} \put(95,6.5){\tiny{$x_{j_1}$}} \put(20,-0.5){\tiny{length $s_1$}} \end{overpic} \caption{A circle labelled $a$ that is incident to two other circles in the original line of circles is replaced by a line of $2l+1$ circles, of lengths $p_{j_1}$, $p_{j_2}$, $\ldots$, $p_{j_l}$, $p_{i_a}$, $p_{j_l}$, $\ldots$, $p_{j_2}$, $p_{j_1}$ and labelled with $x_{j_1}$, $x_{j_2}$, $\ldots$, $x_{j_l}$, $x_{i_a}$, $x_{j_l}$, $\ldots$, $x_{j_2}$, $x_{j_1}$ respectively. The points of attachment of these circles are chosen in such a way that $a$ acts as an involution exchanging the two outermost vertices. The necessary lengths are indicated in the figure.}\label{pic_replacement2} \end{center} \end{figure} \end{proof} \begin{proof}[Proof of Theorem~\ref{thm_factorialmomentsY}] We will write $\Lambda=C_{p_1}*\cdots*C_{p_m}$ and $\clH_n(\Lambda) = \Hom(\Lambda,S_n)$. Observe that the random variable \[ \prod_{i,j}\left(Y_{G_{ij}}\right)_{k_{ij}}:\clH_n(\Lambda) \to \bbN \] counts tuples of vertex labelled copies of $G_{ij}$ (where each $G_{ij}$ appears $k_{ij}$ times) that are satisfied by $\varphi(g_i)$. As such, we may write \[ \bbE_n^{\Hom}\left[\prod_{i,j}\left(Y_{G_{ij}}\right)_{k_{ij}}\right] = \sum_{\alpha \in A(n)} \bbE^{\Hom}_n[\ind_\alpha], \] where \[ A(n) = \left\{ (\alpha_{ij})_{i,j};\; \begin{array}{c}\alpha_{ij} \text{ a }k_{ij}\text{-tuple of }K_i\text{-graphs, isomorphic to }G_{ij}\text{, with vertices} \\ \text{labelled with elements of }\{1,\ldots.n\} \text{, such that the labels}\\ \text{of the vertices of each graph in the collection are distinct} \end{array}\right\} \] and \[ \ind_\alpha :\clH_n(\Lambda) \to \{0,1\} \] satisfies $\ind_\alpha(\varphi) = 1$ if and only if $\varphi$ satisfies all the labelled graphs corresponding to $\alpha$. Note that many of these indicators are constant $0$ functions, because the combination of labels involved leads to a contradiction about the properties of $\varphi(x_j)$ for some $j\in\{1,\,\ldots,\,m\}$. We call $\alpha\in A(n)$ \emph{admissible} if $\ind_\alpha$ is not a constant $0$ function. We now start by computing $\bbE_n^{\Hom}[\ind_\alpha]$. Observe that \[ \bbE_n^{\Hom}[\ind_\alpha] = \frac{ \left|\left\{\varphi\in \clH_n(\Lambda);\; \varphi \text{ satisfies } \alpha \right\}\right|}{h_n(\Lambda)}. \] In order to count the numerator on the right-hand side, we need to count the number of ways to complete the information given in $\alpha$ to a homomorphism $\Lambda \to S_n$. We do this as follows. For admissible labellings $\alpha$, we decompose the labels appearing in $\alpha$ into \emph{words}. These are strings of labels in $\{1,2,\ldots,n\}$ that appear as the vertices of some path in $G_{ij}$, all of whose edges are marked with the same generator, and which is maximal with respect to this last property. So, a choice needs to be made for the lengths of these cycles that contain these words, which words appear together in a cycle, and which other labels appear in these cycles. Once these cycles have been completed, this determines $m$ homomorphisms $C_{p_j} \to S_{D_j}$, where $D_j$ is the union of cycles containing words marked by $x_j$. To complete this into a homomorphism $C_{p_j} \to S_n$, we have the choice out of $h_{n-D_j}(C_{p_j})$ homomorphisms. This, as $n\to\infty$, gives a total of \[ \sim \prod\limits_{j=1}^m \; \sum\limits_{\{S_1,\,\ldots,\,S_t\} \models W_j(\alpha)} \sum\limits_{\substack{d_1,\,\ldots,\,d_t|p_j \\ d_q\,\geq\sum\limits_{w\,\in\,S_q} \ell(w) }} C(S,d)\cdot n^{\sum\limits_q d_q -\sum\limits_{w\,\in\,W_j(\alpha)}\ell(w)} h_{n-\sum\limits_q d_q}\left(C_{p_j}\right) \] ways to complete the information in an admissible labelling $\alpha$ to a homomorphism, where \begin{itemize} \item $W_j(\alpha)$ is the set of words that appear in $\alpha$ and pose a condition on $\varphi(x_j)$, \item the notation $\{S_1,\,\ldots,\,S_t\}\models W_j(\alpha)$ means that $\{S_1,\,\ldots,\,S_t\}$ forms a set partition of $W_j(\alpha)$ (these are the groups of words that are going to appear together in cycles in $\varphi(x_j)$), \item the numbers $d_1,\,\ldots,\,d_t$ are going to be the lengths of the cycles containing the words in the sets $\{S_1,\,\ldots,\,S_t\}$, \item $\ell(w)$ is the number of vertex labels in a word $w$, \item $C(S,d)$ is a combinatorial constant that counts the number of ways to distribute the words over cycles in according to $\{S_1,\,\ldots,\,S_t\}$ and $d_1,\,\ldots,\,d_t$. Moreover, if the set partition $\{S_1,\,\ldots,\,S_t\}$ consists of singletons, then $C(S,d)=1$ \item and we have already made one simplification: the powers of $n$ should in reality take the form of a falling factorial. However, since we are only interested in asymptotics and all the products involved are of fixed bounded length, we replaced them by powers of $n$, whence the ``$\sim$''. \end{itemize} Now we notice that all the sums and products involved are finite, so we may apply Theorem~\ref{hn_cyclic}. This implies that, as $n\to\infty$, \begin{align*} \bbE_n^{\Hom}[\ind_\alpha] & \sim \prod\limits_{j=1}^m \; \sum\limits_{\substack{\{S_1,\,\ldots,\,S_t\}\\ \models W_j(\alpha)}} \sum\limits_{\substack{d_1,\,\ldots,\,d_t|p_j \\ d_q\, \geq \sum\limits_{w\,\in\,S_q} \ell(w) }} C(S,d)\cdot n^{\sum\limits_q d_q -\sum\limits_{w\,\in\,W_j(\alpha)}\ell(w)} \frac{h_{n-\sum\limits_q d_q}\left(C_{p_j}\right)}{h_n\left(C_{p_j}\right)} \\ & \sim \prod\limits_{j=1}^m n^{-\sum\limits_{w\,\in\,W_j(\alpha)}\ell(w)} \; \sum\limits_{\{S_1,\,\ldots,\,S_t\} \models W_j(\alpha)} \sum\limits_{\substack{d_1,\,\ldots,\,d_t|p_j \\ d_q\, \geq \sum\limits_{w\,\in\,S_q} \ell(w) }} C(S,d)\cdot n^{ \frac{1}{p_j}\sum\limits_q d_q}. \end{align*} The leading term in the double sum on the right is the term in which the sum $\sum_q d_q$ is the largest. This means that the terms in which the sets $\{S_1,\,\ldots,\,S_t\}$ are singletons and the divisors $d_1,\,\ldots,\,d_t$ of $p_j$ are as large as possible. Often, this means they are all equal to $p_j$, but not always. Indeed if $W_j(\alpha)$ contains a word $w$ that starts and ends with the same label, then the length of this word equals the length of the cycle it appears in, we will call such words \emph{closed}. Words that are not closed will be called open. Observe that \[ \ell(w) = \left\{ \begin{array}{ll} e(w) + 1 & \text{if }w\text{ is open} \\ e(w) & \text{if }w\text{ is closed}, \end{array} \right. \] where $e(w)$ denotes the number of edges of the corresponding graph involved in $w$. All in all, we obtain that, as $n\to\infty$, \begin{equation}\label{eq_asymptoteexind} \bbE_n^{\Hom}[\ind_\alpha] \sim \prod_{j=1}^m n^{\sum\limits_{w\,\in\,W_j(\alpha)} \frac{d_w}{p_j} -\ell(w)} = n^{- \left|W^o(\alpha)\right|-\sum\limits_{i,j} e(G_{ij})\cdot k_{ij} + \sum\limits_j \sum\limits_{w\,\in\,W_j(\alpha)} \frac{d_w}{p_j}}, \end{equation} where $d_w$ denotes the maximal possible divisor of $p_j$ associated to $w\in W_j(\alpha)$ -- i.e. $p_j$ if $w$ does not start and end with the same label, and the number of distinct labels in $w$ otherwise -- $e(G_{ij})$ the number of edges of $G_{ij}$ and $W^o(\alpha)$ the set of open words associated to $\alpha$. Now we need to estimate the sum of these quantities. First, we write \[ A_1(n) = \left\{\alpha \in A(n);\; \text{all the labels in }\alpha \text{ are distinct}\right\}, \quad \text{and} \quad A_2(n) = A(n) \setminus A_1(n) \] and observe that, as $n\to\infty$, \[ \left|A_2(n)\right| = O\left(n^{-1+\sum\limits_{i,j} v\left(G_{ij}\right)\cdot k_{ij}}\right), \] where $v(G_{ij})$ denotes the number of vertices of $G_{ij}$. On the other hand, \begin{multline*} |A_1(n)| = \left(\prod_{i,j} \frac{1}{\left|\Aut\left(\widehat{G}_{ij}\right)\right|^{k_{ij}}} \right)\cdot n\cdot\left(n-1\left)\cdots \left(n-\left(\sum_{i,j} v(G_{ij}) \cdot k_{ij}\right)+1\right)\right.\right. \\ \stackrel{n\,\to\,\infty}{\sim} \prod_{i,j}\frac{1}{\left|\Aut\left(\widehat{G}_{ij}\right)\right|^{k_{ij}}} n^{v\left(G_{ij}\right)\cdot k_{ij}}. \end{multline*} The reason that it's $|\Aut(\widehat{G}_{ij})|$ rather than $|\Aut(G_{ij})|$ that plays a role here, is the way we did the counting above. Indeed in our computation of $\bbE[\ind_\alpha]$ above, we're counting how many ways to complete the cycles of the generators. So we're really counting labellings of $\widehat{G}_{ij}$. The only case in which this distinction between $G$ and $\widehat{G}_{ij}$ will play a role is the case of elements $g$ that are products of two involutions. Combining this with~\eqref{eq_asymptoteexind} and using the fact that the function $\alpha\in A_1(n) \mapsto \bbE[\ind_\alpha]$ is constant, we obtain \begin{multline*} \bbE_n^{\Hom}\left[\prod_{i,j}\left(Y_{G_{ij}}\right)_{k_{ij}}\right] = \sum_{\alpha\, \in\,A_1(n)} \bbE_n^{\Hom}[\ind_\alpha]+ \sum_{\alpha\,\in\,A_2(n)} \bbE_n^{\Hom}[\ind_\alpha] \\ \sim \left(\prod_{i,j}\frac{1}{\left|\Aut\left(\widehat{G}_{ij}\right)\right|^{k_{ij}}}\right) n^{\sum\limits_{i,j} \left(v\left(G_{ij}\right)-e\left(G_{ij}\right)\right)\cdot k_{ij} + \sum\limits_j \sum\limits_{w\,\in\,W_j(\alpha)} \frac{d_w}{p_j}-\ind_{\text{open}}(w)} \end{multline*} as $n\to\infty$, where $\alpha$ is any labelling from $A_1(n)$, $e(G_{ij})$ denotes the number of edges of $G_{ij}$ and $\ind_{\text{open}}$ is the indicator of the event that a word is open. In order to conclude, we need to figure out for which graphs $G$, the expression \begin{align*} g(G){:=}&\,v(G)-e(G) + \sum_{\substack{w\text{ a word} \\ \text{coming from }G} } \frac{d_w}{p_w}-\ind_{\text{open}}(w) \\ =&\, v(G)-e(G) + \sum_{\substack{w\text{ a closed word} \\ \text{coming from }G} } \frac{d_w}{p_w}, \end{align*} where $p_w$ is the order of the group element corresponding to $w$, is non-negative. To this end, we will first prove the following claim: \begin{claim}\label{clm_adj_words} If $g(G)\geq 0$, then no word in $G$ can be adjacent to more than two words. \end{claim} \begin{proof}[Proof of Claim~\ref{clm_adj_words}] To prove this, we first observe that $v(G)-e(G)$ is the Euler characteristic of $G$, hence we can apply inclusion-exclusion. So, let $w$ be this word that is adjacent to more than two words. Using inclusion-exclusion for the Euler characteristic and the fact that if $w$ is open, then $d_w/p_w = 1$ (which equals the Euler characteristic of a segment), we obtain \begin{equation}\label{eq_inclexclword} \begin{split} g(G) &= \frac{d_w}{p_w} - \#\{\text{vertices that }w \text{ attaches to}\} + \sum_i g\left(G_w^{(i)}\right) \\ &= \frac{d_w}{p_w} + \sum_i g\left(G_w^{(i)}\right) - \#\left\{\text{vertices of }G_w^{(i)} \text{ that }w \text{ attaches to}\right\} \end{split} \end{equation} where the $G_w^{(i)}$ are the components of $G-w$. In order to understand the terms in the sum above, we first claim: \begin{enonce} {Subclaim}\label{subc_g_of_conn_comp} If $g(G_w^{(i)}) = 1$, then $G_w^{(i)}$ cannot contain a closed directed loop that \begin{itemize} \item starts and ends at the same vertex, \item runs through all of the edges of $G_w^{(i)}$ \item the generators on the edges of $G_w^{(i)}$ along this loop spell out a reduced word. \end{itemize} \end{enonce} \begin{proof}[Proof of Subclaim~\ref{subc_g_of_conn_comp}] Let $U$ be any connected graph whose edges are directed and labelled by the generators $x_1,\,\ldots,\,x_m$ and let us order the words appearing in $U$ by $w_1,\,\ldots,\,w_f$ in such a way that the graph $U_j$ containing only the words $w_1,w_2,\,\ldots,\,w_j$ is connected for $j=1,\,\ldots,\,f$. We then have $U=U_f$ and \[ g(U_1) = \frac{d_{w_1}}{p_{w_1}}\quad \text{and}\quad g(U_j) = g\left(U_{j-1}\right) + \frac{d_w}{p_w} - \#\left\{ \begin{array}{c}\text{vertices of }U_{j-1} \\ \text{that }w_j\text{ attaches to} \end{array}\right\}, \] for $j=2,\ldots, f$. Observe that \[ g(U)=g(U_f),\quad g(U_1)\leq 1 \quad \text{and}\quad g(U_j) \leq g\left(U_{j-1}\right), \] for $j=2,\,\ldots,\,f$. The third inequality follows from connectedness of all the graphs: $w_j$ attaches to at least one vertex of $U_{j-1}$. If we want that $g(U)=1$ then each word must be either closed and of length $p_{k_j}$ -- the order of the corresponding generator -- or open. Moreover, each new word needs to attach to exactly one vertex. So, \begin{itemize} \item either one of the words is open and $U$ cannot contain a closed directed path that runs through all edges (because this open word can only be traversed in one direction and disconnects $U$ when removed), \item or all the words are closed and of full length, in which case the word that is read out is not reduced. Indeed, there is at least one word that attaches to at most one vertex and any closed loop must traverse this loop all at once. \end{itemize} This proves our subclaim. \end{proof} This means that in~\eqref{eq_inclexclword}, if $g(G_w^{(i)})=1$ (the maximal possible value, given that $G_w^{(i)}$ is connected), then $w$ attaches to at least two vertices of $G_w^{(i)}$. If not, then $g(G_w^{(i)})\leq \frac{1}{2}$ (the next largest value possible). So \[ g\left(G_w^{(i)}\right) - \#\left\{\text{vertices of }G_w^{(i)} \text{ that }w \text{ attaches to}\right\} \leq -\frac{1}{2} \] in general. This means that if $G-w$ has more than two components, then $g(G) <0$. If $G-w$ has two components, then $w$ connects to at least two vertices on one of them and hence for that component we have \[ g\left(G_w^{(i)}\right) - \#\left\{\text{vertices of }G_w^{(i)} \text{ that }w \text{ attaches to}\right\} \leq -1 \] and we again obtain that $g(G)<0$. Finally, if $G-w$ is connected then $g(G-w) \leq 1$ and \[ g(G-w) - \#\left\{\text{vertices of }G-w \text{ that }w \text{ attaches to}\right\} \leq -2. \] So, we have proved our claim: if $g(G)\geq 0$, then $G$ contains no word that is adjacent more than to two other words, thus proving Claim~\ref{clm_adj_words}. \end{proof} Claim~\ref{clm_adj_words} now first implies that, if $g(G)\geq 0$, then either all words in $G$ are closed, or all words are open. Indeed, suppose $G$ contains both open and closed words. Since $G$ is connected, there is a vertex where an ``incoming'' open and a closed word meet. At least one other word must attach to the closed word. If it attaches at a different vertex, there must be a third word that attaches. If not, part of the closed word does not appear in the group element. So, the only option is that the incoming open word and a second word attach at the same vertex. But that means that the incoming open word must be incident to at least three other words. Now all that is left is to consider the two cases: ``all words are closed'' and ``all words are open''. If all words are open, then $g(G) = v(G)-e(G)$, the Euler characteristic of $G$. So $G$ must be either homotopic to a tree or a cycle. Because $G$ contains only open words, it cannot contain any leaf, and so $G$ must be a cycle. If all words in $G$ are closed and each word is incident to at most two other words, then $G$ is either a line of circles or a ``circle of circles''. The latter means that $G$ decomposes into closed words, each of which is incident to exactly two other closed words. Such a graph does not have a closed directed loop that traverses all its edges. So $G$ must be a line of circles. The conditions on the lengths of the loops that we mentioned before the theorem are implied by the positivity of $g(G)$. \end{proof} \subsection{Fixed point statistics of finite order elements of $C_{p_1}*\cdots*C_{p_m}$} Given a finite cyclic group $C_p=\langle x| x^p \rangle$ of order $p$ and a divisor $d|p$, we let \[ Y_d:\Hom\left(C_p,S_n\right)\to\bbN \] denote the random variable that associates the number of $d$-cycles of $\varphi(x)$ to $\varphi \in \Hom(C_p,S_n)$. M\"uller and Schlage-Puchta~\cite{MullerPuchta2,MullerPuchta3} proved that these variables satisfy a central limit theorem. Similar results we also proved by Benaych-Georges in~\cite{BG2}. \begin{theo}\label{thm_fin_ord_elts_sym_group} Let $\clD = \{ d \in \bbN;\; d|p\}$. \begin{enumerate} \item~\label{clt_cycles} (Central limit theorem) \cite[Lemma~4]{MullerPuchta3} The normalised vector \[ \left(\frac{Y_d-\frac{1}{d} n^{d/p}}{\frac{1}{\sqrt{d}} n^{d/2p}} \right)_{d\,\in\,\clD\setminus\{p\}}: \Hom\left(C_p,S_n \right)\to\bbN^{\clD\setminus\{p\}} \] converges in distribution to $\otimes_{d\,\in\,\clD\setminus\{p\}} \clN(0,1)$. \item~\label{clt_max_cycles} ~\cite[Lemma~3]{MullerPuchta2} (Central limit theorem for maximal cycles) Set $d_{\max}=\max\{ d\in \clD;\; d1}$ such that $\sum_{i=1}^m \frac{1}{p_i}\,1}$ be such that $\sum_{j=1}^m \frac{1}{p_j} < m-1$. Then the IRS \[ \mu_n = \frac{1}{a_n\left(\Gamma_{p_1,\,\ldots,\,p_m}\right)} \sum_{\substack{H \;<\; \Gamma_{p_1,\,\ldots,\,p_m} \\ \left[\Gamma_{p_1,\,\ldots,\,p_m}:H\right] \;=\; n}} \delta_H \quad \stackrel{w^*}{\longrightarrow} \quad \delta_{L_{p_1\,,\ldots,\,p_m}} \] as $n\to\infty$. \end{thmrep} \begin{proof} Write \[ \clA_n\left(\Gamma_{p_1,\,\ldots,\,p_m}\right) = \clA_{n,1}\sqcup\clA_{n,2}, \] where \[ \clA_{n,1} = \Phi_{p_1,\,\ldots,\,p_m}^{-1}\left(\clA_n\left(C_{p_1}*\cdots*C_{p_m}\right)\right) \quad \text{and}\quad \clA_{n,2}=\clA_n\left(\Gamma_{p_1,\,\ldots,\,p_m}\right) \setminus \clA_{n,1} \] If $f:\Sub(\Gamma_{p_1,\,\ldots,\,p_m})\to \bbR$ is a continuous function then \begin{multline*} \mu_n(f) = \frac{1}{a_n\left(\Gamma_{p_1,\,\ldots,\,p_m}\right)}\sum_{H\,\in\,\clA_n\left(C_{p_1}*\cdots*C_{p_m}\right)} f\left(\Phi_{p_1,\,\ldots,\,p_m}^{-1}(H)\right)\\ + \frac{1}{a_n\left(\Gamma_{p_1,\,\ldots,\,p_m}\right)} \sum_{H\,\in\,\clA_{n,2}} f(H). \end{multline*} Since $f$ is bounded and $\mu_n(\clA_{n,2}) \to 0$ (by Theorem~\ref{thm_main2}), the second term tends to $0$ as $n\to\infty$. The first term tends to $f(\ker(\Phi_{p_1,\,\ldots,\,p_m}))$ by Corollary~\ref{cor_BSconvC*...*C}, which proves the theorem. \end{proof} Finally, we will determine the limits of the normalised Betti numbers. We have: \begin{thmrep}{\ref*{thm_main3}$\MK$\eqref{theo1.3.c}} Let $p_1,\,\ldots,\,p_m\in\bbN_{>1}$ be such that $\sum_{i=1}^m \frac{1}{p_i} < m-1$. For every $\varepsilon>0$ it holds that \[ \lim_{n\,\to\,\infty} \mu_n\left(\left|\frac{b_k(H;\bbR)}{n}- b_k^{(2)}\left(X_{p_1,\,\ldots,\,p_m}^\Phi;\;C_{p_1}*\ldots*C_{p_m}\right)\right| < \varepsilon \right)= 1 \quad \text{for all }k \in \bbN. \] Moreover, \[ b_k^{(2)}\left(X_{p_1,\,\ldots,\,p_m}^\Phi;\;C_{p_1}*\ldots*C_{p_m}\right) = \left\{ \begin{array}{ll} m-1 - \sum\limits_{i=1}^m \frac{1}{p_i} & \text{if } k = 1,2 \\ 0 & \text{otherwise}. \end{array} \right. \] \end{thmrep} It follows from the fact that $\mu_n$ converges to $\delta_{L_{p_1,\,\ldots,\,p_m}}$ together with Lemma~\ref{lem_betticonvergence} that the normalised Betti numbers of a random index $n$ subgroup converge to those of the cover corresponding to $L_{p_1,\,\ldots,\,p_m}$. So the only thing that we still have to do is compute these Betti numbers, which is the content of the following lemma. Recall that $\Gamma/L_{p_1,\,\ldots,\,p_m} \simeq C_{p_1}*\cdots * C_{p_m}$. We have: \begin{lemm}\label{lem_l2_betti} Let $X_{p_1,\,\ldots,\,p_m}$ be a classifying space for $\Gamma_{p_1,\,\ldots,\,p_m}$ and let $X_{p_1,\,\ldots,\,p_m}^\Phi\linebreak \to X_{p_1,\,\ldots,\,p_m}$ denote the cover corresponding to $L_{p_1,\,\ldots,\,p_m} \vartriangleleft \Gamma_{p_1,\,\ldots,\,p_m}$. Then \[ b_k^{(2)}\left(X_{p_1,\,\ldots,\,p_m}^\Phi;\;C_{p_1}*\ldots*C_{p_m}\right) = \left\{ \begin{array}{ll} m-1 - \sum\limits_{i=1}^m \frac{1}{p_i} & \text{if } k = 1,2 \\ 0 & \text{otherwise}. \end{array} \right. \] \end{lemm} \begin{proof} Since the $\ell^2$-Betti numbers do not depend on the choice of classifying space, we identify $\Gamma_{p_1,\,\ldots,\,p_m}$ with a lattice in $\PSL(2,\bbR)\times \bbR$ and set $X_{p_1,\,\ldots,\,p_m} = \Gamma_{p_1.\,\ldots,\,p_m}\backslash(\bbH^2\times \bbR)$. This gives us an identification \[ X_{p_1,\,\ldots,\,p_m}^\Phi = \bbH^2\times \bbR/\bbZ. \] The action of $C_{p_1} *\cdots *C_{p_m}$ on $X_{p_1,\,\ldots,\,p_m}^\Phi$ preserves the factors. The action on $\bbR/\bbZ$ is through the quotient $C_{p_1} *\cdots *C_{p_m} \longrightarrow C_{p_1} \times \cdots \times C_{p_m}$. The kernel $\Lambda$ of this quotient is a free group that acts trivially on $\bbR/\bbZ$. Because $X_{p_1,\,\ldots,\,p_m}$ is three-dimensional and $\Lambda$ is infinite, \[ b_k^{(2)}\left(X_{p_1,\,\ldots,\,p_m}^\Phi;\;\Lambda\right)=0 \quad\text{for } k\in \{0,4,5,\,\ldots\} \] (see for instance~\cite[Theorem~1.35$\MK$(8)]{Lueck_Book} or~\cite[Theorem~3.18$\MK$(ii)]{Kammeyer}). Moreover, since \[ b_k^{(2)}\left(\bbH^2;\;\Lambda\right) = \left\{ \begin{array}{ll} -\chi\left(\Lambda\backslash\bbH^2\right) & \text{if }k=1 \\ 0 & \text{otherwise} \end{array} \right. \] (see for instance~\cite[Example~3.16]{Lueck_Book} or~\cite[Exercise~3.3.1]{Kammeyer}) where $\chi$ denotes Euler characteristic. So, the K\"unneth formula (see for instance~\cite[Theorem~1.35$\MK$(4)]{Lueck_Book} or~\cite[Theorem~3.18$\MK$(iii)]{Kammeyer}) gives us that \[ b_1^{(2)}\left(X_{p_1,\,\ldots,\,p_m}^\Phi;\;\Lambda\right) = b_2^{(2)}\left(X_{p_1,\,\ldots,\,p_m}^\Phi;\;\Lambda\right) = -\chi\left(\Lambda\backslash\bbH^2\right) \text{ and } b_3^{(2)}\left(X_{p_1,\,\ldots,\,p_m}^\Phi;\;\Lambda\right) =0. \] Since both orbifold Euler characteristic and $\ell^2$-Betti numbers are multiplicative with respect to finite index subgroups (see for instance~\cite[Theorem~1.35$\MK$(9)]{Lueck_Book} or~\cite[Theorem~3.18$\MK$(iv)]{Kammeyer} for the latter), the lemma follows. \end{proof} \begin{proof}[Proof of Theorem~\ref*{thm_main3}$\MK$\eqref{theo1.3.c}] This is now direct from Theorem~\ref*{thm_main3}$\MK$\eqref{theo1.3.b} and Lemmas~\ref{lem_l2_betti} and~\ref{lem_betticonvergence}. \end{proof} \subsection{Random index \texorpdfstring{$n$}{n} subgroups of Fuchsian groups}\label{sec_fuchsian} In this last section we discuss applications of our results to random subgroups of Fuchsian groups. We have: \begin{thmrep}{\ref*{thm_main4}} Let $\Lambda$ be a non-cocompact Fuchsian group of finite covolume. Moreover, let $G_n<\Lambda$ denote an index $n$ subgroup, chosen uniformly at random. \begin{enumerate}\Alphenumi \item\label{theo1.4.a'} \begin{enumerate} \item If $K_1,\,\ldots,\,K_r \subset \Lambda$ are conjugacy classes of infinite order elements of which no pair have a common root. Then, as $n\to\infty$, the vector of random variables \[ \left(Z_{K_1}(G_n),\,\ldots,\,Z_{K_r}(G_n)\right) \] converges jointly in distribution to a vector \[ \left(Z_{K_1}^\infty,\,\ldots,\,Z_{K_r}^\infty\right):\Omega \to \bbN^r \] of independent random variables, such that if $K_i$ is the conjugacy class of a $k^{th}$ power of a primitive element then \begin{itemize} \item if this primitive element is not a product of two elements of order two, \[ Z_{K_i}^\infty \sim \sum_{d|k}\; d \cdot X_{1/d}, \] where $X_{1/d} \sim \Poisson(1/d)$ and $X_1,\,\ldots,\,X_{1/k}$ are independent. \item if this primitive element is a product of two elements of order two \[ Z_{K_i}^\infty \sim \sum_{d|k}\; 2d \cdot X^{d,1}_{1/2d} + \sum_{d|k,\; d\text{ even}} d\cdot X_{1/2}^{d,2}+d\cdot X_{1/2}^{d,3} + \sum_{d|k,\; d\text{ odd}} d \cdot X_1^{d,4} \] where $X^{d,1}_{1/2d} \sim \Poisson(1/2d)$, $X_{1/2}^{d,2}\sim $Pois\-son$(1/2)$, $X_{1/2}^{d,3}\sim \Poisson\linebreak(1/2)$, $X_1^{d,4}\sim \Poisson(1)$ and all these variables are independent. \end{itemize} \item~\cite[Lemma~4]{MullerPuchta3} If $K_1,\,\ldots,\,K_r\subset \Lambda$ are non-trivial conjugacy classes of which no pair have a common root, whose elements have orders $k_1,\,\ldots,\,k_r\in\bbN$ respectively, then the vector of random variables \[ \left(\frac{Z_{K_1}(G_n)-n^{1/k_1}-\varepsilon_1\cdot n^{1/2k_1}}{\sqrt{p_{j_1}/k_1}\cdot n^{1/2k_1}},\,\ldots,\,\frac{Z_{K_r}(G_n)-n^{1/k_r}-\varepsilon_r\cdot n^{1/2k_r}}{\sqrt{p_{j_r}/k_r}\cdot n^{1/2k_r}} \right) \] converges in distribution to a $\clN(0,1)^{\otimes r}$-distributed random variable as $n\to \infty$. Here $p_{j_i}\in\bbN$ is such that $K_i$ is the conjugacy class of $x_{j_i}^{l_i}$, for $i=1,\,\ldots,\,r$. Finally $\varepsilon_i$ equals $1$ if $p_{j_i}/k_i$ is even and $0$ otherwise. \end{enumerate} \item\label{theo1.4.b'} As $n\to\infty$, $G_n$ converges to the trivial group as an IRS. \end{enumerate} \end{thmrep} \begin{proof}[Proof sketch] First of all note that non-cocompact Fuchsian group of finite covolume are exactly groups of the form $F_r*C_{p_1}*\cdots * C_{p_m}$, with $-r+m-1 - \sum_{i=1}^m 1/p_i < 0$, where $F_r$ denotes the free groups on $r$ generators. If $r=0$, \eqref{theo1.4.a'} and~\eqref{theo1.4.b'} are the content of Theorem~\ref{thm_statisticsforC*...*C} and Corollary~\ref{cor_BSconvC*...*C} respectively. If $r>0$, the proof of Theorem~\ref{thm_factorialmomentsY} needs to be adapted slightly: $r$ of the generators are now allowed to have any permutation of their image and not just permutations of a fixed order -- so we do not need to compute the number of ways to complete words to cycles of certain lengths, but can just complete them to permutations immediately. With exactly the same strategy (and slightly easier computations, which we leave to the reader) the analogue of Theorem~\ref{thm_factorialmomentsY} can now be proved (if $m=0$, much better bounds are in fact available~\cite{DJPP,Nica}). In order to prove the analogue of Corollary~\ref{cor_BSconvC*...*C}, the only new ingredient that is needed is that $t_n(\Gamma)/h_n(\Gamma) \to 1$. When $m=0$, this is a direct consequence of Dixon's theorem~\cite{Dixon}. For the remaining cases, the proof has not been written down, but a similar strategy does the trick. Indeed, the results by Volynets--Wilf (Theorem~\ref{hn_cyclic}) together with Stirling's approximation that for $p>1$, \[ h_n\left(F_r*C_{p_1}*\cdots*C_{p_m}\right) \sim B \cdot n^{r/2} \cdot \exp\left(\sum_{i=1}^m \sum_{d|p_i,\,d\,<\,p_i} \frac{1}{d}n^{d/p_i}\right) \cdot \left(\frac{n}{e}\right)^{n\left(r + \sum\limits_{i=1}^m 1-\frac{1}{p_i}\right)}, \] as $n\to\infty$, where $B$ is a constant depending on $(r,p_1,\,\ldots,\,p_m)$. We have \[ 1 - \frac{t_n(\Lambda)}{h_n(\Lambda)} = \sum_{k=1}^{n-1} \binom{n-1}{k-1}\frac{t_k(\Lambda) h_{n-k}(\Lambda)}{h_n(\Lambda)} \] (see for instance~\cite[Lemma~1.1.3]{LubotzkySegal}). Combining the two, we get that there exists a constant $A>0$ such that \[ 1 - \frac{t_n(\Lambda)}{h_n(\Lambda)} \leq A \sum_{k=1}^{n-1} \binom{n}{k}^{1 -r - m - \sum\limits_{i=1}^m \frac{1}{p_i}} \exp\left(\sum_{i=1}^m\sum_{\substack{d|p_i, \\ d\,<\,p_i}}\frac{(n-k)^{d/p_i}+k^{d/p_i} -n^{d/p_i}}{d} \right) \longrightarrow 0, \] as $n\to\infty$, which settles the remaining cases. \end{proof} \appendix \section{An elementary approach to the subgroup growth of \texorpdfstring{$\Gamma_{p_1,\ldots,p_m}$}{Gammap1,\dots,pm}} \label{app_elt_approach} In this appendix we sketch an alternative route to Theorems~\ref{thm_main1} and~\ref{thm_main2}. The proof sketched below, when worked out in full, is longer than the proof we give above. But, it's more self-contained and it also leads to a closed formula for $h_n(\Gamma_{p_1,\,\ldots,\,p_m})$ and hence for $a_n(\Gamma_{p_1,\,\ldots,\,p_m})$, which cannot be obtained from the proof above. On the other hand, while the large $n$ asymptotics can be derived directly from these sequences without relying on the results by M\"uller~\cite{Muller_FreeProducts} on the subgroup growth of free products, this computation uses very similar methods to his (in particular the asymptotic behaviour of the coefficients of certain analytic functions due to M\"uller~\cite{Muller}, Volynets~\cite{Volynets} and Wilf~\cite{Wilf}). \subsection{A Closed Formula} Our first objective is now to derive a closed formula for $h_n(\Gamma_{p_1,\,\ldots,\,p_m})$. We have: \begin{prop}\label{hn_closed_formula} Let $n,p_1,\,\ldots,\,p_m \in \bbN$. Then \[ h_n\left(\Gamma_{p_1,\,\ldots,\,p_m}\right) = n! \sum\limits_{\substack{r_1,\,\ldots,\,r_n\,\geq\,0 \\ \text{s.t. }\sum_l r_l\cdot l = n}} \; \prod_{\substack{1\,\leq\,l\,\leq\,n \\ \text{s.t. } r_l\,>\,0 }} \left(r_l!\cdot l^{r_l}\right)^{m-1} \prod_{i=1}^m\; \sum_{k\,\in\,\clK\left(p_i,l,r_l\right)} \prod_{j=1}^{p_i} \frac{1}{\left(l\cdot j\right)^{k_j} k_j!} \] where \[ \clK(p,l,r) = \left\{k \in \bbN^p \;\middle|\; \sum_{i=1}^p k_i\cdot i = r \text{ and } k_i = 0 \text{ whenever } \gcd(i\cdot l, p) \neq i \right\}. \] \end{prop} The main ingredient for the formula above is the count of the number of $m$\textsuperscript{th} roots of a given permutation $\pi\in S_n$ -- i.e. the number \[ N_m(\pi) = \left|\left\{ \sigma\in S_n;\; \sigma^m = \pi \right\}\right|. \] Note that this number only depends on the conjugacy class of $\pi$. The computation of $N_m(\pi)$ is a classical problem, that to the best of our knowledge, has been first worked out by Pavlov~\cite{Pavlov}. Let us first introduce some notation. Recall that the conjugacy class of a permutation $\pi\in S_n$ is determined by its \emph{cycle type} -- the unordered partition of $n$ given by the lengths of the cycles in a disjoint cycle decomposition of $\pi$. In what follows the notation $1^{r_1}2^{r_2}\cdots n^{r_n}$ will denote the partition of $n$ that has $r_1$ parts of size $1$, $r_2$ parts of size $2$, et cetera. $K(1^{r_1}2^{r_2}\cdots n^{r_n}) \subset S_n$ will denote the corresponding conjugacy class. In this notation, we will often omit the sizes of which there are $0$ parts and write $i$ for $i^1$. \begin{prop}[Pavlov~\cite{Pavlov}]\label{mth_roots} Let $m,n\in\bbN$ and $\pi \in K(1^{r_1}2^{r_2}\cdots n^{r_n}) \subset S_n$. Then \[ N_m(\pi) = \prod_{\substack{1\,\leq\,l\,\leq\,n \\ \text{s.t. }r_l\,>\,0}} r_l!\; l^{r_l} \sum_{k\,\in \,\clK\left(m,l,r_l\right)} \prod_{i=1}^m \frac{1}{(l \cdot i)^{k_i}k_i!} \] where $\clK(m,l,r)$ is as in Proposition~\ref{hn_closed_formula}. \end{prop} Note that there may be an $l$ such that $r_l>0$ and $\clK(m,l,r_l)=\emptyset$. In this case, $N_m(\pi)=0$. \begin{proof}[Proof of Proposition~\ref{hn_closed_formula}] Given a conjugacy class $K\subset S_n$, we write $N_m(K)$ for the number of roots of an element $\pi\in K$. We have \[ h_n\left(\Gamma_{p_1.\ldots,\,p_m}\right) = \sum_{\substack{K\,\subset\,S_n \\ \text{a conjugacy class}}} |K| \cdot N_{p_1}(K) \cdots N_{p_m}(K). \] Using Proposition~\ref{mth_roots} and the fact that $|K(1^{r_1}\cdots n^{r_n})| = n!/\prod_{i=1}^n i^{r_i} r_i!$ gives the formula. \end{proof} \subsection{Asymptotics} Theorems~\ref{thm_main1} and~\ref{thm_main2} can now be derived as follows. First of all, it turns out that the sum in Proposition~\ref{hn_closed_formula} is dominated by a single term, namely the term corresponding to \[ \left(r_1,r_2,\,\ldots,\,r_n\right) = (n,0,\,\ldots,\,0). \] In order to prove this, we write \[ \tau_{p,l,r} = \sum_{k\,\in\,\clK\left(p,l,r\right)} \prod_{j=1}^p \frac{1}{\left(l\cdot j\right)^{k_j}k_j!} \] so that \begin{equation}\label{eq_hn_tau} h_n\left(\Gamma_{p_1,\,\ldots,\,p_m}\right) = n! \sum_{\substack{r_1,\,\ldots,\,r_n\, \geq\,0 \\ \text{s.t. } \sum_l r_l\cdot l = n}} \; \prod_{\substack{1\,\leq\,l\,\leq\,n \\ \text{s.t. } r_l\,>\,0}} \left(r_l! l^{r_l}\right)^{m-1} \prod_{i=1}^m \tau_{p_i,l,r_l} \end{equation} by Proposition~\ref{hn_closed_formula}. The crucial bound is now: \begin{lemm}\label{tau_bounds} Let $p, l,r \in \bbN$. Then \[ \tau_{p,l,r} \leq \left(\frac{1}{r \cdot l}\right)^{\frac{r}{p}} \cdot \exp \left(\sum_{i|p} \frac{(r \cdot l)^{i/p}}{i\cdot l} \right). \] \end{lemm} \begin{proof}[Proof sketch] We define a generating function: \[ F_{p,l}(x) = \sum_{r=0}^{\infty} \tau_{p,l,r} x^r. \] A direct computation gives us that \[ F_{p,l}(x)= \prod_{i\,\in\,I_{p,l}} \exp\left(\frac{x^i}{i\cdot l}\right), \] where $I_{p,l} = \{i \leq p \mid \gcd(i\cdot l, p)= i\}.$ The fact that $F_{p,l}$ has non-negative coefficients implies that \[ \tau_{p,l,r} \leq \frac{F(x_0)}{x_0^r} \] for all $x_0\in (0,\infty)$. Filling this in for $x_0 = (r\cdot l)^{1/p}$ leads to the bound. \end{proof} Using this lemma, and the asymptotic behaviour of $\tau_{p,1,n}$ which follows from results due to M\"uller~\cite{Muller}, Volynets~\cite{Volynets} and Wilf~\cite{Wilf}, one obtains that, the term in Proposition~\ref{hn_closed_formula} we claim is dominant as $n\to\infty$ is indeed dominant. This now first of all proves Theorem~\ref{thm_main2}, because, the term that determines the asymptotic corresponds to maps \[ \varphi: \Gamma_{p_1,\,\ldots,\,p_m} = \left\langle x_1,\,\ldots x_m\,\middle|\;x_1^{p_1} = \ldots = x_m^{p_m}\right\rangle \longrightarrow S_n \] such that $\varphi(x_i^{p_i})$ is the identity element in $S_n$. These are exactly the maps that factor through $\Phi_{p_1,\,\ldots,\,p_m}$. We also obtain an asymptotic equivalent for $h_n(\Gamma_{p_1,\,\ldots,\,p_m})$ (which can also be derived from Corollary~\ref{cor_hn_tn}). This, together with Proposition~\ref{subgp_trans} and Lemma~\ref{lem_rapidgrowth}, then implies Theorem~\ref{thm_main1}. \section{Rapidly divergent sequences} In two of our proofs above, we need a bound on a quadratic combination of the terms of a rapidly divergent sequence. Many variations on the bound we need are known to hold. These bounds are, for instance, responsible for the fact that as $n\to\infty$, a random homomorphism $F_2\to S_n$ becomes transitive and the fact that, as $n\to\infty$, a random cubic graph on $n$ vertices becomes connected. Even if the bound we present certainly isn't new, we are not aware of a statement of it in the literature. For instance, \cite[Theorem~A.1$\MK$(ii)]{CMZ} comes close but does not apply to our case. The bound in~\cite[Proposition~1]{Muller}, or rather its proof, contains what we need but is phrased in a somewhat different language. Given this, we will provide a proof. \begin{lemm}\label{lem_rapidgrowth} Let $a_n \in \bbR$ for all $n\in\bbN$ be such that there exist $C>0 $, $\alpha>0$ and $\beta_1,\,\ldots,\,\beta_m \in \bbR$ and $\gamma_1,\,\ldots,\,\gamma_m \in (0,1]$ such that \begin{align*} a_n \sim C\cdot \exp\left(\alpha n \log(n) + \sum_{i=1}^m \beta_i n^{\gamma_i}\right) \quad &\text{as } n\to \infty, \\ \intertext{then} \sum_{k=1}^{n-1} \frac{a_k\; a_{n-k}}{a_n} = O\left(n^{-\alpha}\right)\quad &\text{as } n\to \infty. \end{align*} \end{lemm} \begin{proof} Our goal is to show that the sum is dominated by its outer terms, that is, when either $k$ or $n-k$ is small. For simplicity of exposition, we will assume the coefficients $\beta_i$ are positive (as they are in our application), the general case follows from a similar argument. We will assume that $k\leq n/2$ in what follows and deal with the other half of the sum by symmetry. Write $c_{n,k} = a_k a_{n-k}/a_n$. We have \begin{multline*} \frac{c_{n,k+1}}{c_{n,k}} = (1+o_{n,k}(1)) \cdot \exp\Bigg[\alpha \Big((k+1) \log(k+1) - k \log(k) \\ + (n-k-1) \log(n-k-1) - (n-k) \log(n-k) \Big) \\ + \sum_{i=1}^m \beta_i \cdot \Big((k+1)^{\gamma_i} - k^{\gamma_i} + (n-k-1)^{\gamma_i} - (n-k)^{\gamma_i} \Big) \Bigg]. \end{multline*} Using the fact that for $x>0$ and $\gamma \in (0,1]$ \[ \gamma \cdot (x+1)^{\gamma-1} \leq (x+1)^\gamma - x^\gamma = \int_x^{x+1} \gamma \cdot y^{\gamma-1} dy \leq \gamma\cdot x^{\gamma-1}, \] and that for $x\geq 1$ \[ \log(x) + 1 \leq (x+1)\log(x+1) - x \log(x) = \int_x^{x+1}(\log(y) + 1)dy \leq \log(x+1) + 1, \] we obtain that \begin{multline*} \frac{c_{n,k+1}}{c_{n,k}} \leq (1+o_{n,k}(1)) \cdot \exp\Bigg[\alpha \Big(\log(k+1) - \log(n-k-1) \Big) \\ + \sum_{i=1}^m \beta_i \cdot \gamma_i \cdot \Big(k^{\gamma_i-1} - (n-k)^{\gamma_i-1} \Big) \Bigg]. \end{multline*} We observe that the second term in the exponential is uniformly bounded, from which we conclude that there exists a uniform $L \in \bbN$ such that \[ \frac{c_{n,k+1}}{c_{n,k}} \leq 1 \] for all $L \leq k \leq n/2-L$, whenever $n$ is large enough. From a similar computation, we obtain that \[ c_{n,k} \leq c_{n,\lfloor n/2-L \rfloor} \] for all $n/2-L < k \leq n/2$. In other words, the sum above is dominated by its first and last $L$ terms. One now computes that for $k \in \bbN$ fixed, \[ c_{n,k} = O\left(n^{-\alpha k} \right) \quad \text{as } n\to\infty. \] This means that if we set $M = \max\{L,\lceil 2/\alpha \rceil\}$, then \[ \sum_{k=1}^{n-1} \frac{a_k\; a_{n-k}}{a_n} \leq c_{n,M}\cdot n + 2\cdot \sum_{k=1}^{M- 1} c_{n,k} = O\left(n^{-\alpha}\right) \quad \text{as } n\to\infty, \] thus proving the Lemma~\ref{lem_rapidgrowth}. \end{proof} \bibliography{baker} \end{document}