\documentclass[12pt,reqno]{amsart}
\usepackage{latexsym}
%\usepackage{amsmath}
\usepackage{amssymb}
%\usepackage{amscd}
%\usepackage{amscd}
%\usepackage[ngerman]{babel}
%\usepackage[T1]{fontenc}
%\usepackage[ansinew]{inputenc}
%\usepackage{bbold}
%\usepackage{epsfig}
%\usepackage{titlepage}
\parskip2ex
\parindent0pt
\textheight23cm \textwidth15.6cm \hoffset-1.7cm
\voffset-.5cm
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{conjecture}{Conjecture}
\newtheorem{example}{Example}
\newtheorem{definition}{Definition}
\newtheorem{remark}{Remark}
\newtheorem*{propositionno}{Proposition}
\newtheorem*{remarkno}{Remark}
\def\Hom{\operatorname{Hom}}
\def\f{\mathfrak{f}}
\def\F{\mathfrak{F}}
\def\J{\mathfrak{J}}
\def\R{\mathfrak{R}}
\def\O{\underline{\Omega}}
\newcommand{\norm}{\triangleleft}
\newcommand{\C}{\mathfrak{C}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\T}{\underline{\underline{\tau}}}
\newcommand{\E}{\underline{\underline{e}}}
\newenvironment{proofof}[1]
{\par\noindent{\em {\it Proof of #1.}}}{\hfill
$\square$\par\medskip}
\newcommand{\dbin}[2]{\left(\kern-0.4em{#1\choose#2}
\kern-0.4em\right)}
%\newcommand{\qed}{\hfill
%\mbox{$\Box$}\vspace{\baselineskip}}
%\newenvironment{proof}{\noindent {\bf
%Proof.}}{{\qed}}
\begin{document}
\title[Character theory,
long relators, and random walks]
{Character theory of symmetric groups, analysis of
long relators, and random walks}
\author[T.\,W. M\"uller]{Thomas W. M\"uller}
\begin{abstract}
We survey a number of powerful recent results concerning diophantine and asymptotic properties of (ordinary) characters of symmetric groups. Apart from their intrinsic interest, these results are motivated by a connection with subgroup growth theory and the theory of random walks. As applications, we present an estimate for the subgroup growth of an arbitrary Fuchsian group, as well as a finiteness result for the number of Fuchsian presentations of such a group, the latter result solving a long-standing problem of Roger Lyndon's. We also sketch the proof of a well-known conjecture of Roichman's concerning the mixing time of random walks on finite symmetric groups, and of a result describing the parity of the subgroup numbers for a substantial class of one-relator groups.
\end{abstract}
\maketitle

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 56 \rms (2006), Article~B56a\hfill}
\def\thepage{}
%
%

\section*{Introduction}
As is well known, representation theory has a
number of applications in Probability Theory and in Statistics;
examples include, for instance, estimates for the
mixing time of random walks on finite groups and homogeneous
spaces, analysis of partially ranked data, and the
modelling of card shuffling. The monograph by Diaconis
\cite{Diaconis} covers these and other applications of
a similar flavour.   

What is needed for these applications is simply the
ordinary character theory (over $\mathbb{C}$) of
finite groups built up by Frobenius, Burnside, Schur
and others since the late 1890s; and the version of ordinary
representation theory of finite symmetric groups
developed by Young and others since the late 1920s.

It would seem that, by now, the ordinary representation
theory of finite symmetric groups is rather well
understood. Nevertheless, recent years have seen a number of
exciting developments and breakthroughs at the bottom of which
lie distinct advances in our understanding of the
characteristic zero representation theory of symmetric
groups. Here, we shall concentrate on a number of powerful results concerning diophantine and asymptotic properties of characters of symmetric groups, recently obtained in a series of papers by the author in collaboration with J.-C. Schlage--Puchta; cf. \cite{MP1}, \cite{MP2}, \cite{MP3}, and \cite{MP4}. Apart from their considerable intrinsic interest, these investigations are motivated by connections with the subgroup arithmetic of certain large groups (large in the sense of Pride \cite{Pride}) and with the theory of random walks; it is this interplay between an improved and refined character theory of $S_n$ (and, more generally, monomial groups) on the one hand, and the analysis of long relators and random walks on the other, which forms the main theme of the present paper. 

The main new results concerning the asymptotics of character values and multiplicities established in \cite{MP3} can be summarized as follows.  

{\bf Theorem A.}{\em\ Let $\varepsilon>0$ and a positive integer $q$ be given, suppose that $n$ is sufficiently large, and let $\chi$ be an irreducible character of $S_n$.\vspace{-3mm}
\begin{enumerate}
\item We have $|\chi(\mathbf{c})|\leq \big(\chi(1)\big)^{1-\delta}$ with
\[
\delta = \left(\big(1-1/(\log n)\big)^{-1}\frac{12\log n}{\log (n/f)} + 18\right)^{-1},
\]
where $\mathbf{c}$ is any conjugacy class of $S_n$ with $f$ fixed
points.\vskip5pt
\item We have
\[
\underset{\pi^q=1}{\sum_{\pi\in S_n}}|\chi(\pi)| \leq \big(\chi(1)\big)^{\frac{1}{q}+\varepsilon}\underset{\pi^q=1}{\sum_{\pi\in S_n}} 1.
\]
\item Let $m_\chi^{(q)}$ be the multiplicity of $\chi$ in the $q$-th root number
function of $S_n$. Then
\[
m_\chi^{(q)}\leq \big(\chi(1)\big)^{1-2/q+\varepsilon}.
\]
\end{enumerate}
}
All these bounds are essentially best possible. We remark that, in characteristic zero, estimates for character values and multiplicities are among the least understood topics in the representation theory of symmetric groups. In recent times,
additional interest in this circle of problems was sparked by the theory of random walks on finite groups.
In this context, the first part of Theorem~A enables us to prove the following.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL T. W. M\"ULLER}{\SMALL CHARACTER THEORY, LONG
RELATORS, AND RANDOM WALKS}
%
%

{\bf Theorem B.}{\em\ Let $\mathbf{c}$ be a non-trivial conjugacy class in $S_n$. Denote by $t_\mathrm{comb}(\mathbf{c})$ the least even integer such that $t_c(\mathbf{c})$ elements chosen at random from $\mathbf{c}$ have, with probability $\geq 1-\frac{1}{n},$
no common fixed point, and let $t_\mathrm{stat}(\mathbf{c})$ be the mixing time for the random walk generated by $\mathbf{c}$ {\em(}see the beginning of Section~$5$ for notions left undefined here{\em)}. Then, for $n\geq 4000,$ we have}
\[
t_\mathrm{comb}(\mathbf{c})\leq t_\mathrm{stat}(\mathbf{c})\leq 10 t_\mathrm{comb}(\mathbf{c}).
\]
Theorem~B establishes in full generality a conjecture of Roichman;
cf. \cite[Conj. 6.6]{Roichman}. For special choices of $\mathbf{c}$,
Roichman's conjecture had already been known to hold: Diaconis and Shahshahani \cite{DS} established it for transpositions, Roichman \cite{Roichman} generalized their result to conjugacy classes having at least $c n$ fixed points, where $c$ is some positive constant, and Fomin and Lulov \cite{FL} established a character bound implying Theorem~C for conjugacy classes having only cycles of the same length. On the other hand, parts (2) and (3) of Theorem~A allow us
to derive an asymptotic estimate for the subgroup growth of Fuchsian groups; that is, groups $\Gamma$ of the form
\begin{multline}\label{Eq:FuchsPres}
\Gamma = \Big\langle x_1, \ldots, x_r, y_1, \ldots, y_s, u_1, v_1, \ldots, u_t, v_t\,\big|\\
x_1^{a_1}=\cdots=x_r^{a_r} = x_1\cdots x_r y_1^{e_1}\cdots y_s^{e_s} [u_1, v_1]\cdots
[u_t, v_t] = 1\Big\rangle
\end{multline}
with integers $r,s,t\geq0$ and $e_1,\ldots, e_s\geq2$, and $a_1,\ldots,a_r\in\N\cup\{\infty\}$. ($\Gamma$ is a Fuchsian group in the most general sense met in the literature; cf., for instance, \cite[Prop.~5.3]{LS} or \cite[Sec:~II.7]{Magnus}).

{\bf Theorem C.} {\em Let $\Gamma$ be a Fuchsian group such that
\begin{equation*}
\alpha(\Gamma):= \sum_i\Big(1-\frac{1}{a_i}\Big)\hspace{.6mm}+\hspace{.6mm}\sum_j
\frac{2}{e_j}\hspace{.6mm}+\hspace{.6mm}2(t-1) > 0,
\end{equation*}
and let
\[
\mu(\Gamma) = \sum_i\Big(1-\frac{1}{a_i}\Big)\hspace{.6mm}+\hspace{.6mm}s\hspace{.6mm}+\hspace{.6mm}2(t-1)
\]
be the hyperbolic measure of $\Gamma$. Then the number $s_n(\Gamma)$ of index $n$ subgroups in $\Gamma$ satisfies an asymptotic expansion
\begin{equation*}
s_n(\Gamma) \approx \delta L_\Gamma (n!)^{\mu(\Gamma)}
\Phi_\Gamma(n)\bigg\{1\hspace{.6mm}+\hspace{.6mm}\sum_{\nu=1}^\infty
a_\nu(\Gamma)\hspace{.3mm}n^{-\nu/m_\Gamma}\bigg\},\quad(n\rightarrow\infty).
\end{equation*}
Here,
\begin{eqnarray*}
\delta  &=& \begin{cases} 2, &\forall i: a_i \text{ finite and odd}, \forall j: e_j\text{ even}\\[1mm]
1, & \text{otherwise,}
\end{cases}\\
L_\Gamma & = & (2\pi)^{-1/2-\sum_i(1-1/a_i)} (a_1\cdots a_r)^{-1/2} \exp
\left(-\sum_{\underset{2|a_i}{i}}\frac{1}{2a_i}\right),\\[1mm]
\Phi_\Gamma(n) & = & n^{3/2-\sum_i(1-1/a_i)} \exp\left(\sum_{i=1}^r\sum_{\underset{t<a_i}{t|a_i}}
\frac{n^{t/a_i}}{t}\right),\\[1mm]
m_\Gamma &=& [a_1,a_2,\ldots,a_r],
\end{eqnarray*}
and the $a_\nu(\Gamma)$ are explicitly computable constants depending only on $\Gamma$.}

Theorem~C has a number of noteworthy consequences for the classification of Fuchsian groups; in particular it leads to the solution of a long standing problem, apparently first raised in an important special case by Hurwitz, and later brought to the forefront in its general form by Roger Lyndon during a meeting at IAS Princeton in 1968:

{\leftskip1cm\rightskip1cm
\textit{Can a (non-degenerate) Fuchsian group have infinitely many Fuchsian presentations {\em(}i.e., presentations of the form $(\ref{Eq:FuchsPres})$ above{\em)}?}
\par}

While it is not hard to give examples of Fuchsian groups of positive hyperbolic measure allowing for more than one presentation of the form (\ref{Eq:FuchsPres}), we are able to show that such a group has at most \textit{finitely many} such presentations; cf. \cite[Theorem~7]{MP3} and Theorem~7 in Section~3 below.

A rather different note is struck by the earlier paper \cite{MP2};
here, we are concerned with certain diophantine properties of
character values and multiplicities, which appear to be both new and
of independent interest. To be more specific, denote by $\varphi$ the
bijection between the self-conjugate partitions of $n$ and the
partitions of $n$ into distinct odd parts, mapping a self-conjugate
partition $\lambda$ onto the partition given by the symmetric main
hooks of $\lambda$. Moreover, denote by ${\bf c}_\lambda$ the
conjugacy class of $S_n$ whose cycle structure is given by the
partition $\lambda\vdash n$, and by $\chi_\lambda$ the irreducible
character of $S_n$ corresponding to the Specht module $S^\lambda$. 
Finally, call an irreducible character $\chi$ of $S_n$
\textit{symmetric}, if $\chi=\epsilon_n\chi$, where
$\epsilon_n=\chi_{(1^n)}$ is the sign character. (This is equivalent to
demanding that the partition associated with $\chi$ be
self-conjugate). Then the first part of \cite{MP2} establishes the
following. 

\textbf{Theorem~D.} (a) \textit{Let $\lambda_1$ and $\lambda_2$ be partitions of $n$ with $\lambda_1$ self-conjugate. Then $\chi_{\lambda_1}({\bf c}_{\lambda_2})$ is odd if, and only if, $\lambda_2=\varphi(\lambda_1)$.}

(b) \textit{Let $\chi$ and $\chi'$ be irreducible characters of $S_n$. If both $\chi$ and $\chi'$ are symmetric, then the multiplicity $\langle \chi^2 \vert \chi'\rangle$ of $\chi'$ in $\chi^2$ is odd if, and only if, $\chi=\chi'$.}

After introducing a certain rather substantial class $\mathcal{W}$ of relators, including in particular all surface relators
\[
\prod_{1\leq j\leq g} [x_{2j-1},x_{2j}]\quad\mbox{and}\quad \prod_{1\leq j\leq h} x_j^2,
\]
the second part of \cite{MP2}, building on Theorem~D as well as detailed information concerning the representation numbers of binary quadratic forms, establishes the following surprising and beautiful result.

\textbf{Theorem~E.} \textit{If $w$ is in $\mathcal{W}$ and involves at least $3$ generators, then the number of index $n$ subgroups in the one-relator group defined by $w$ is odd if, and only if, $n=k^2$ or $n=2k^2$ for some $k\geq1$.}

Our treatment here will cover Theorems~A--E in some detail. This leaves out the asymptotic decomposition of the conjugacy representation and the estimate derived from it for the subgroup growth of a large class of groups, including in particular all one-relator groups with defining relation belonging to class $\mathcal{W}$, and all Fuchsian groups, as well as many other groups dominated by a long relation. These results, beginning with their actual statement, are rather technical, and seem altogether unsuitable for the purposes of a survey; for this topic, the reader is referred to the original paper \cite{MP4}.

Our article is organized as follows. In Section~\ref{Sec:LargeGroups}, we give a brief introduction to the subgroup growth theory of large groups. The purpose of this section is to provide the reader with some background for the analysis of long relators, which will form one of the main topics. In Section~\ref{Sec:Surface}, we explain our character-theoretic approach to the subgroup growth of surface groups, originally developed in \cite{MP1}. This is a first example to show how the solution of a problem in the ordinary representation theory of finite symmetric groups (here the asymptotic approximation of the sum $\sum_{\lambda\vdash n} \chi_\lambda(1)^{-s}$ for fixed real $s>0$) leads to a result concerning the subgroup growth associated with a certain type of long relator. Proposition~4, which provides an asymptotic expansion for the number of index $n$ subgroups in a large surface group, is essentially superseded by our corresponding result for Fuchsian groups (Theorem~C), which will be presented, together with related results (including its representation-theoretic background) in Section~\ref{Sec:FuchsianGroups}. However, the main new idea how to apply character theory in the context of long relations occurs here for the first time and in a particularly transparent form, so that I thought it worthwhile to discuss this special case first.

Section~4 introduces the class of relators $\mathcal{W}$, and sketches a proof of Theorem~E modulo Theorem~D, while Section~5 discusses and sketches the proof of Theorem~B.

The paper presents a somewhat extended version of a series of lectures given at the 56th S\'eminaire Lotharingien de Combinatoire, held 9--12 April 2006 in Ellwangen, Germany. It is my pleasure to thank Christian Krattenthaler and Volker Strehl for the invitation to give these lectures, and for inviting this report. 
\section{Counting subgroups of finite index in large groups}
\label{Sec:LargeGroups}
For a finitely generated group $\Gamma$, denote by $s_n(\Gamma)$
the number of index $n$ subgroups of $\Gamma$. Subgroup growth
theory, a thriving chapter in asymptotic group theory
developed over the last 20 years by Grunewald, Lubotzky, Mann, Segal, and others including the present author,
deals with number-theoretic properties of the sequence
$\big\{s_n(\Gamma)\big\}_{n\geq1}$ or related subgroup
counting functions and their connection with the algebraic
structure of the underlying group $\Gamma$. Here, we shall be concerned exclusively with \emph{large} groups: a group is termed large (in the sense of Pride~\cite{Pride}), if it contains a subgroup of finite index which projects homomorphically onto a non-abelian free group. Clearly, for such a group, $s_n(\Gamma)$ grows at least as fast as the subgroup numbers of a free group of rank $2$, but it is by no means true that $s_n(\Gamma)$ necessarily has \emph{smooth} growth; in particular there need not exist an asymptotic formula for this function.\footnote{Cf. \cite[Section~7]{MPExamples} for an example in this direction.}

As a first example, let us consider Marshall Hall's recurrence
relation
\begin{equation}
\label{Eq:HallRec}
s_n(F_r) = n(n!)^{r-1}\,-\,\sum_{\nu=1}^{n-1}
\big((n-\nu)!\big)^{r-1}\,s_\nu(F_r)
\end{equation}
for the subgroup numbers of a free group $G=F_r$ of
rank $r$; cf. \cite{MHall}. It is immediate from this
relation that, for $r\geq1$ and $n\geq2$,
\[
s_n(F_r) \equiv s_{n-1}(F_r)\bmod{2},
\]
hence \emph{the subgroup numbers of a non-trivial finitely generated free group are all odd.} With very little work (and almost no
thought) one also extracts from (\ref{Eq:HallRec}) an asymptotic formula for the subgroup numbers of a non-abelian free group. Indeed, observe from (\ref{Eq:HallRec}) that
\begin{equation}
\label{Eq:snest}
s_n(F_r) \leq n (n!)^{r-1},\quad n\geq1.
\end{equation}
Assuming $r\geq2$, and dividing (\ref{Eq:HallRec})
throughout by $n(n!)^{r-1}$, we then see that
\[
\frac{s_n(F_r)}{n (n!)^{r-1}} = 1 - \epsilon(n,r),
\]
where
\begin{align*}
\epsilon(n,r) &:= \sum_{\nu=1}^{n-1} \big((n-\nu)!\big)^{r-1}\,
s_\nu(F_r)\,/\,\big(n (n!)^{r-1}\big)\\
&\leq \sum_{\nu=1}^{n-1} \frac{\nu}{n}\,
\binom{n}{\nu}^{-(r-1)}\\
&\leq n^{-r}\,+\, \frac{n-1}{n^r}\,+\,
\sum_{\nu=2}^{n-2}
\binom{n}{\nu}^{-(r-1)}\\
&= n^{-r} \,+\, \frac{n-1}{n^r}\, +\,
\mathcal{O}_r\big(n^{-2r+3}\big)\\
&= \mathcal{O}_r\big(n^{-1}\big),
\end{align*}
so
\[
s_n(F_r) \sim n (n!)^{r-1}\quad(n\rightarrow\infty),
\quad r\geq2.
\]
This is \cite[Theorem~3]{Newman}. Note that $1-r=\chi(F_r)$ is the Euler characteristic of the free group of rank $r$, so that the exponent of $n!$
in the last formula can be re-expressed as $-\chi(F_r)$.    Non-abelian free groups and, more generally, finitely generated virtually free groups,
i.e., fundamental groups $\Gamma = \pi_1(G(-),Y)$ of finite graphs of finite groups (in the sense of Bass and Serre), with $\chi(\Gamma)<0$, are prototypes of large groups in the sense
of Pride, and are typical examples of groups with fast subgroup growth. A prominent example of a virtually free group is the classical modular group
\[
\Gamma=\mathrm{PSL}_2(\mathbb{Z})\cong C_2\ast C_3.
\]
Here the corresponding results concerning parity and
asymptotics are already quite non-trivial.

\textbf{Proposition~1} [Stothers \cite{Stothers},
1977].
\textit{Let $\Gamma=\mathrm{PSL}_2(\mathbb{Z})$ be
the modular group. Then}
\[
s_n(\Gamma) \equiv 1\bmod{2}\, \Longleftrightarrow\,
n=2^\alpha-3 \mbox{ or }
n=2(2^\alpha-3) \mbox{ for some } \alpha\geq1.
\]

\textbf{Proposition~2} [Newman \cite{Newman}, 1976].
\textit{For $\Gamma=\mathrm{PSL}_2(\mathbb{Z}),$}
\[
s_n(\Gamma) \sim (12 \pi e^{1/2})^{-1/2}\,
n^{n/6}\,\exp\Big(-\frac{n}{6} + n^{1/2} + n^{1/3} +
\frac{1}{2}
\log n\Big).
\]
Note that, apart from correction terms coming from the torsion in the group, the right-hand side of the last formula looks like
$(n!)^{-\chi(\Gamma)}$, where $\chi(\Gamma)=-\frac{1}{6}$ is the Euler characteristic (in the sense of Wall) of the modular group; cf. \cite[Chapter~IX]{Brown}. This behaviour appears to be typical of large virtually free groups of smooth growth; cf. also Theorem~2 below, which provides further evidence in this direction.

We mention in passing that the kernel of the Cartesian
map
\[
\Gamma = \mathrm{PSL}_2(\mathbb{Z}) \rightarrow
C_2\times C_3
\cong C_6
\]
is free of rank $2$ (Nielsen~\cite{Nielsen}, see also
Lyndon \cite{Lyndon}); hence, descending an index $6$ along a cyclic group, we have managed to completely destroy the rather complex
pattern exhibited by Stothers' result above. This indicates
that, unlike growth, divisibility properties of subgroup counting functions tend to be severely distorted when deforming the
underlying group over a commensurability class.

Here are two more recent results concerning free
products.

{\bf Theorem 1} [M\"uller \cite{MSAFP}, 2003].
\textit{Let $q\geq3$ be an integer. Then $q$ is a Fermat prime if, and only if,}
\begin{multline*}
s_n(C_2\ast C_q) \equiv 1\bmod{2} \Longleftrightarrow
n=\frac{2(q-1)^\alpha-q}{q-2}\\[2mm] \mbox{or }
n=2\bigg(\frac{2(q-1)^\alpha-q}{q-2}\bigg) \mbox{ for
some
$\alpha\geq1$.}
\end{multline*}
{\bf Theorem 2} [M\"uller \cite{MuInvent}, 1996].
\textit{Let} $\Gamma = G_1\ast\cdots\ast G_s\ast F_r$ 
\textit{be a free product with finite groups $G_i,$ $m_i=|G_i|,$ and
suppose that $\chi(\Gamma)<0$. Then}
\[
s_n(\Gamma) \sim L_\Gamma\,\Phi_\Gamma(n)
\quad(n\rightarrow\infty),
\]
\textit{where}
\[
L_\Gamma:= (2\pi)^{\frac{r-1}{2}}\,(m_1\cdots
m_s)^{-1/2}
\,\exp\Bigg(-\underset{2\mid m_i}{\sum_i}
\,\frac{\big(s_{G_i}(m_i/2)\big)^2}{2m_i}\Bigg)
\]
\textit{and}
\[
\Phi_\Gamma(n):= n^{-\chi(\Gamma) n}
\,\exp\Bigg(\chi(\Gamma) n
+ \sum_{i=1}^s
\,\underset{d_i< m_i}{\sum_{d_i\mid m_i}}
\frac{s_{G_i}(d_i)}{d_i}\, n^{d_i/m_i}\, +\,
\frac{r+1}{2}\, \log n\Bigg).
\]
As is well known, Fermat primes, that is, prime numbers of the form $2^{2^\lambda}+1$ with $\lambda\geq0$, satisfy (or can even be characterized by) a number of curious regularity conditions; for instance, according to Gau{\ss},\footnote{Disquisitiones arithmeticae \cite{Gauss}, \S 366.} a regular $p$-gon ($p>2$ a prime) can be constructed by compass and ruler if, and only if, $p$ is a Fermat prime. Theorem~1 provides a new such characterization, within the set of integers $\geq3$, through the arithmetic of the associated (standard) Hecke group $\mathfrak{H}(q)\cong C_2\ast C_q$, while at the same time representing the maximal generalization of Stothers' result (Proposition~1) for Hecke groups. Much more is known concerning 
divisibility properties of subgroup counting functions, but results tend to get quite technical; cf. \cite{CaMue}, \cite{MuBLMS}, \cite{MSAFP}, \cite{MuParheck}, and \cite{ModpFree}.

The second result gives an estimate for the subgroup
growth of free products $\Gamma$ of the form
\begin{equation}
\label{Eq:FreeProd}
\Gamma = G_1 \ast \cdots \ast G_s \ast
F_r\quad(m_i=|G_i|<\infty,\,\chi(\Gamma)<0)
\end{equation}
in terms of the local data $m_i$ and $s_{G_i}(d_i)$ for $d_i\mid m_i$. In fact, a full asymptotic expansion is
known for $s_\Gamma(n)$ in this case, of which $L_\Gamma
\Phi_\Gamma(n)$ is the main term; cf. \cite[Theorem~1]{MuInvent}. 

It appears that for virtually free groups $\Gamma$ of more complicated structure (for instance, amalgamated products or HNN extensions) global invariants like $\chi(\Gamma)$ do not suffice to
control the asymptotics of $s_n(\Gamma)$ (although they might still  suffice to determine the growth type), and it is 
unclear, whether this function still exhibits smooth
growth in such cases. In some mysterious way, the
character theory of the finite stabilizers seems to come
into the picture, but the situation is essentially not
understood. However, there are other large groups, for instance one-relator groups, or Fuchsian groups.\footnote{By a result of Baumslag and Pride, a one-relator group having 3 or more generators is large; cf. \cite{BP}. The situation for Fuchsian groups is more involved, compare Theorem~4 in Section~3.} What can we say about their subgroup growth? We shall come back to this question (which leads into our first main theme) shortly; but first let me explain how finite symmetric groups and, more generally, full monomial groups (i.e. groups of the form $H\wr S_n$ with a finite group $H$) enter our picture in an essential way.

For groups of super-exponential subgroup growth, no direct approach is known to the problem of counting finite index subgroups. Instead, one uses the transformation
formula
\begin{equation}
\label{Eq:Transform1}
\sum_{n\geq0} \frac{|\Hom(\Gamma, S_n)|}{n!}\, z^n =
\exp\Bigg(\sum_{n\geq1}\frac{s_n(\Gamma)}{n}\,
z^n\Bigg)
\end{equation}
or, more generally, the equation
\begin{equation}
\label{Eq:Transform2}
\sum_{n\geq0} \frac{|\Hom(\Gamma, H\wr S_n)|}{n!}\,z^n
= \exp\Bigg(\sum_{n\geq1} \frac{|H|^{n-1}
s_n(\Gamma,H)}{n}
\,z^n\Bigg),
\end{equation}
where
\[
s_n(\Gamma,H):= \sum_{(\Gamma:\Delta)=n}
|\Hom(\Delta,H)|\quad
(H\mbox{ a finite group}).
\]
We briefly sketch the proof of (\ref{Eq:Transform1}):\footnote{Cf. \cite{MuRepres} for the proof of 
(\ref{Eq:Transform2}), which is considerably more demanding.} classify the $\Gamma$-actions on the standard $n$-set
\[
[n]:= \{1,2,\ldots,n\}
\] 
by the orbit $\omega_0$ of the point $1$. This orbit $\omega_0$ may have any size $k$ between $1$ and $n$, and the $\Gamma$-action on $\omega_0$ is transitive, while the action of $\Gamma$ on $[n]\setminus\omega_0$ is arbitrary. Moreover, the transitive actions of $\Gamma$ on $[n]$, modulo the (free) action of the stabilizer $\mathrm{stab}_\Gamma(1)$, are in one-to-one correspondence with the subgroups of index $n$ in $\Gamma$. There are $\binom{n-1}{k-1}$ ways of choosing the elements of $\omega_0$; and, on each such 
$k$-set, $\Gamma$ has $(k-1)! s_k(\Gamma)$ transitive actions, hence
\begin{equation}\label{Eq:Transform1Equiv}
\vert\Hom(\Gamma, S_n)\vert = \sum_{1\leq k\leq n} \binom{n-1}{k-1} (k-1)! s_k(\Gamma) \vert\Hom(\Gamma, S_{n-k})\vert,
\end{equation}
from which (\ref{Eq:Transform1}) follows. Note also that Marshall Hall's relation (\ref{Eq:HallRec}) is a special case of (\ref{Eq:Transform1Equiv}).

For a large group $\Gamma$, a function like $|\Hom(\Gamma, S_n)|$ tends to be more approachable than $s_n(\Gamma)$ itself, and there is machinery in place (see, for instance, Bender \cite{Be} and Wright \cite{Wright}, \cite{Wright2}) to transfer, say, asymptotic information from one side of the
relations (\ref{Eq:Transform1}), (\ref{Eq:Transform2}) to the
other. Henceforth, for the purposes of this survey, the
problem of analyzing $s_n(\Gamma)$, the number of index $n$
subgroups in $\Gamma$, will be identified with that of
investigating the function $|\Hom(\Gamma, S_n)|$. No further mention will be made here of the more complicated case of monomial representations, apart from remarking that Formula (\ref{Eq:Transform2}), or rather the techniques underlying its proof, play a key role in the solution of the Poincar\'e-Klein Problem, one of the most important long-standing problems in pure mathematics; cf. \cite{IsoDis} and \cite{IsoDis2}.

Let us quickly come back to Theorem~2. For $\Gamma$ as in
(\ref{Eq:FreeProd}), the function $|\Hom(\Gamma,S_n)|$ decomposes as
\[
|\Hom(\Gamma, S_n)| = (n!)^r
\prod_{i=1}^s |\Hom(G_i, S_n)|.
\]
Thus, if we want to understand the asymptotics of
$s_n(\Gamma)$ in this case, we have to investigate the
function $|\Hom(G, S_n)|$, the number of $G$-actions
on an $n$-set for large $n$, where $G$ is an arbitrary
\emph{finite} group. In this situation, the transformation formula
(\ref{Eq:Transform1}) yields
\[
\sum_{n=0}^\infty \frac{|\Hom(G, S_n)|}{n!}\, z^n =
\exp\Bigg(\sum_{d\mid m}
\frac{s_d(G)}{d}\,z^d\Bigg),\quad
m=|G|.
\]
Hence, what we need is an asymptotic estimate for the
Laurent coefficients of an entire function of the form
$\exp(P(z))$, where $P(z)$ is a polynomial with real
coefficients. What makes this problem hard is the (necessary) requirement that our estimates be completely explicit in
the input data (the degree and coefficients of $P(z)$).
Indeed, interpreted in this way, this problem is not
well-posed, since the  family of functions
\[
\Big\{e^{P(z)}:\, P(z)\in\mathbb{R}[z]\Big\}
\]
turns out to be too large to admit of a uniform
asymptotics for its coefficients. Consequently, we have to study
this question under suitable restrictions on the polynomial $P(z)$. In \cite{MuComb}, among other things, the following is proved.

{\bf Theorem 3} [M\"uller \cite{MuComb}, 1997].
\textit{Let $P(z)=\sum_{\mu=1}^m c_\mu z^\mu$ be a polynomial of
degree $m\geq1$ with real coefficients $c_\mu$. Set
$\exp(P(z)) = \sum_{n=0}^\infty \alpha_n z^n,$ and assume that
{\em (i)} $\alpha_n>0$ for sufficiently large $n,$ and that
{\em (ii)} $c_\mu=0$ for $m/2<\mu<m$. Then we have the asymptotic
formula}
\begin{equation}
\label{Eq:EntireFuncAsymp}
\alpha_n \sim \frac{K}{\sqrt{2\pi n}}\,\Big(\frac{n}{m
c_m}\Big)^{-n/m}
\,\exp\bigg(P\Big(\Big(\frac{n}{m
c_m}\Big)^{1/m}\Big)\bigg),
\end{equation}
\textit{where}
\[
K = K(P) = \begin{cases}
       m^{-1/2},& m\mbox{ odd}\\
      
m^{-1/2}\,\exp\Big(-\frac{c_{m/2}^2}{8c_m}\Big),&
       m\mbox{ even}
       \end{cases}.
\]
Theorem~3, in conjunction with \cite[Theorem~3]{Wright} or
Bender's method \cite{Be}, suffices in order to establish Theorem~2. Under more stringent conditions, we also obtain in \cite{MuComb} a full
asymptotic expansion for $\alpha_n$ refining (\ref{Eq:EntireFuncAsymp}). The latter (much harder)
result in turn leads to the improvement of Theorem~2
mentioned above. Thus, we see that Theorem~2 and its
refinement are in fact complex analytic results.
\section{Subgroup growth of surface groups}
\label{Sec:Surface}
For elements $x,y$ in a group $\Gamma$, we denote by
\[
[x,y] = x^{-1} y^{-1} x y
\]
the commutator of $x$ and $y$. 
Let $\Gamma$ be the fundamental group of a closed
$2$-manifold, that is, $\Gamma$ equals
\[
\Gamma_g^+ =
\Big\langle x_1,y_1,\ldots,x_g,y_g \mid
[x_1,y_1]\cdots [x_g,y_g] = 1\Big\rangle
\]
or
\[
\Gamma_h^- = \Big\langle x_1,\ldots,x_h \mid x_1^2\cdots
x_h^2=1\Big\rangle,
\]
depending on whether or not the underlying manifold is
orientable. These groups are large if, and only if, they have at
least three generators, i.e.,
\[\Gamma_g^+ \mbox{ large} \Longleftrightarrow g\geq2,\quad
\Gamma_h^- \mbox{ large} \Longleftrightarrow h\geq3.
\]
The exceptional cases
\[
\Gamma_1^+ \cong \mathbb{Z}^2, \,\, \Gamma_1^- \cong
C_2,
\,\,\Gamma_2^- \cong \mathbb{Z}
\underset{2\mathbb{Z}}{\ast} \mathbb{Z}
\]
are well understood; it is known that\footnote{Cf., for instance, \cite[Section~4.2]{MP1}.}
\[
s_n(\Gamma_2^-) = s_n(\Gamma_1^+) = \sigma_1(n):=
\sum_{d\mid n}d,
\]
and, by a result of Gronwall,\footnote{Trans. Amer. Math. Soc. 14 (1913), see also \cite[Theorem~323]{HW}.} $\sigma_1(n)$ has
maximal
order $e^\gamma n \log\log n$, where $\gamma$ is
Euler's
(or Mascheroni's) constant, so the growth is indeed
slow in these cases.

If we want to estimate the asymptotics of, say
$s_n(\Gamma_g^+)$ for $g\geq2$, we have to control the
function
\[
|\Hom(\Gamma_g^+, S_n)| = \Big\vert\Big\{(x_1,y_1,
\ldots,x_g,y_g)\in
S_n^{2g}:\,[x_1,y_1]\cdots[x_g,y_g]=1\Big\}\Big\vert,
\]
or, on a slightly more general level, the function
\[
N_g^+(G,z):= \Big\vert\Big\{(x_1,y_1,\ldots,x_g,y_g)
\in G^{2g}:\,
[x_1,y_1]\cdots[x_g,y_g]=z\Big\}\Big\vert,
\]
where $G$ is a finite group, and $z\in G$. As a first
step,
consider the function
\[
N_1^+(G,z) =: N^G(z) = \big\vert\big\{(x,y)\in G\times
G:\,
[x,y]=z\big\}\big\vert.
\]
As is well known, the number of solutions of the
equation $x\cdot y=z$ with $x$ and $y$ restricted to given (not
necessarily distinct) conjugacy classes of $G$ can be
expressed in character-theoretic terms as follows:
\begin{equation}
\label{Eq:CharForm1}
\big\vert\big\{(x,y)\in G\times G:\,x\cdot y=z,\,
x\in {\bf c}_1,\, y\in
{\bf c}_2\big\}\big\vert
= \frac{|{\bf c}_1|\cdot|{\bf c}_2|}{|G|} \sum_\chi
\frac{\chi({\bf c}_1)
\chi({\bf c}_2) \chi(z^{-1})}{\chi(1)},
\end{equation}
where $\chi$ runs through the ordinary irreducible
characters of $G$; cf., for instance,
\cite[Proposition~9.33]{CR1} or \cite[Theorem~6.3.1]
{Kerber}. Since $[x,y] = x^{-1}\cdot x^y$, where $x^y=y^{-1}xy$, we can
obtain the solutions of the equation $[x,y]=z$ with $x$ in a
given conjugacy class ${\bf c}$ by first solving the
equation $\bar{x}\cdot\bar{x}'=z$ with $\bar{x}\in {\bf c}^{-1}$ and
$\bar{x}'\in {\bf c}$, and then choosing
$y\in G$ in
\[
|C_G(x)| = |G|/|{\bf c}|
\]
ways to write a given $\bar{x}'$ as $\bar{x}'=x^y$ with
$x=\bar{x}^{-1}$. Applying (\ref{Eq:CharForm1}) and noting
that $|{\bf c}|=|{\bf c}^{-1}|$, we see that
\begin{align*}
\big\vert\big\{(x,y)\in G\times G:\,[x,y]=z,\, x\in
{\bf c}\big\}\big\vert &= 
\big\vert\big\{(\bar{x},\bar{x}')\in G\times
G:\,\bar{x}\cdot\bar{x}'=z, \bar{x}\in {\bf c}^{-1},
\bar{x}'\in {\bf c}\big\}\big\vert\\[1mm]
&{}\hspace{7.05cm}\times |C_G(x)|\\[3mm]
&= \frac{|G|}{|{\bf c}|}\, \frac{|{\bf c}|^2}{|G|} \sum_\chi
\chi({\bf c}^{-1}) \chi({\bf c})
\chi(z^{-1})/\chi(1)\\[3mm]
&= |{\bf c}| \sum_\chi \chi({\bf c}^{-1}) \chi({\bf c})
\chi(z^{-1})/\chi(1).
\end{align*}
Summing over the conjugacy classes gives
\[
N^G(z) = \sum_{\bf c} |{\bf c}| \sum_\chi \chi({\bf c}^{-1})
\chi({\bf c}) \chi(z^{-1})/\chi(1).
\]
Interchanging summations, and using the fact that
characters are class functions plus their orthogonality,
we find that
\begin{align*}
N^G(z) &= \sum_\chi\, \frac{\chi(z^{-1})}{\chi(1)}\,
\sum_{\bf c}\, |{\bf c}| \,\chi({\bf c}^{-1})\, \chi({\bf c})\\[2mm]
&= \sum_\chi\,
\frac{\chi(z^{-1})}{\chi(1)}\,\sum_{x\in G}
\,\chi(x^{-1}) \chi(x)\\[2mm]
&= \sum_\chi\, \frac{\chi(z^{-1})}{\chi(1)}\, |G|\,
\langle\chi\mid\chi\rangle\\[2mm]
&= |G| \sum_\chi\, \chi(z^{-1})/\chi(1).
\end{align*}
Conjugating the resulting equation 
\[
N^G(z) = |G| \sum_\chi \chi(z^{-1})/\chi(1)
\]
yields the formula
\begin{equation}
\label{Eq:CharForm2}
N^G(z) = |G| \sum_\chi \chi(z)/\chi(1).
\end{equation}
We can now establish the character formula
\begin{equation}
\label{Eq:CharForm3}
N_g^+(G,z) = |G|^{2g-1} \sum_\chi
\chi(z)/(\chi(1))^{2g-1}
\end{equation}
by induction on $g$. If $g=1$, then
(\ref{Eq:CharForm3})
holds in virtue of (\ref{Eq:CharForm2}). Suppose that
(\ref{Eq:CharForm3}) holds for some $g\geq1$. Then
\begin{align*}
N_{g+1}^+(G,z) &= \sum_{x\in
G}\,N^+_g(G,x)\,N^G(x^{-1}z)
\\[2mm]
&=|G|^{2g} \sum_{x\in G}\bigg[\sum_\chi
\chi(x)/(\chi(1))^{2g-1}\bigg]
\bigg[\sum_\chi \chi(x^{-1}z)/
\chi(1)\bigg]\\[2mm]
&= |G|^{2g} \sum_{\chi_1,\chi_2} (\chi_1(1))^{-(2g-1)}
(\chi_2(1))^{-1}\sum_{x\in G} \chi_1(x)
\chi_2(x^{-1} z)\\[2mm]
&= |G|^{2g+1} \sum_\chi \chi(z)/(\chi(1))^{2g+1}.
\end{align*}
In the last step, we have used the generalized orthogonality relation
\[
\sum_{x\in G} \chi_1(x) \chi_2((ax)^{-1})
= |G|\,\chi_1(a^{-1})\,
\langle\chi_1\mid\chi_2\rangle/
\chi_1(1)
\]
with $a=z^{-1}$ (cf. \cite[Formula~31.16]{CR}) together with orthogonality of characters.
 In a similar way, one shows that
\begin{align}
N_h^-(G,z)&:=\Big\vert\Big\{(x_1,\ldots,x_h)\in G^h:\,
x_1^2\cdots x_h^2=z\Big\}\Big\vert\nonumber\\[2mm]
&= |G|^{h-1} \sum_\chi c_\chi^h(G)
\chi(z)/(\chi(1))^{h-1},
\label{Eq:CharForm4}
\end{align}
where the $c_\chi(G)$ are given by the expansion
\begin{equation}
\label{Eq:CharForm5}
R^G(z):= \Big\vert\Big\{x\in G:\, x^2=z\Big\}\Big\vert
= \sum_\chi c_\chi(G) \chi(z),\quad z\in G.
\end{equation}
In general, $R^G$ need not be a proper character; it
is a virtual character of $G$, and the (integral)
coefficients $c_\chi(G)$ in the Fourier decomposition
(\ref{Eq:CharForm5}) satisfy $|c_\chi(G)|\leq 1$ and
are non-zero if, and only if, the corresponding character
$\chi$ is real-valued. It is known that $R^{S_n}$ is
in fact the \textit{model character} of $S_n$, that is,
\begin{equation}
\label{Eq:CharForm6}
R^{S_n}(z) = \sum_{\lambda\vdash n} \chi_\lambda(z),
\quad z\in S_n.
\end{equation}
The higher root number functions of $S_n$ have more
recently also been shown to be proper characters; cf.\ Scharf \cite{Scharf}. 
An alternative proof of Scharf's
result using symmetric function theory is outlined in
the solution to \cite[Exercise~7.69 c]{Stanley2}. A good
account of all the facts on root number functions
mentioned is found in \cite[Chapter~6.2]{Kerber}.

Setting $G=S_n$ and $z=1$ in (\ref{Eq:CharForm3}) and
(\ref{Eq:CharForm4}), and using (\ref{Eq:CharForm6}),
we obtain the equation
\begin{equation}
\label{Eq:SurfaceCharForm}
|\Hom(\Gamma_d, S_n)| = (n!)^{d-1} \Phi_{d-2}(n),
\quad d\geq1,
\end{equation}
which summarizes the essence of our discussion so far.
Here, $\Gamma_d$ is a surface group (orientable or not)
of rank $d$,\footnote{The \emph{rank} of a finitely generated group is, by definition, the minimal number of generators for this group.} and, for fixed real $s$,
\[
\Phi_s(n):= \sum_{\lambda\vdash n}
\big(\chi_\lambda(1)
\big)^{-s}.
\]
It is clear from Equation~(\ref{Eq:SurfaceCharForm}), that information on the asymptotics of $s_n(\Gamma_d)$ with $d\geq3$ will flow from a sufficiently precise estimate of the character sum $\Phi_s(n)$ for $s>0$ as $n\rightarrow\infty$. Such an estimate is given by our next result.

{\bf Proposition 3} [M\"uller/Puchta~\cite{MP1}, Theorem~1].
\textit{For fixed $s>0,$ we have the asymptotic expansion}
\[
\Phi_s(n) \approx
2\,\sum_{\rho\geq0}\,\mathcal{A}_\rho(s)
\,n^{-\rho}\quad(n\rightarrow\infty).
\]
\textit{Here, the coefficients $\mathcal{A}_\rho(s)$ are given by}
\[
\mathcal{A}_\rho(s)= \sum_{r\geq0}\,
\sum_{\mu\vdash r}\,H[\mu]^s
\,\sum_{(\kappa_\nu)}\,\prod_{\nu\in
N(\mu,r)}\bigg[\binom{s+\kappa_\nu-1}{\kappa_\nu}
(2 r - \nu)^{\kappa_\nu}\bigg],\quad \rho\geq0,
\]
\textit{where $H[\mu]$ is the hook product of $\mu,$}
\begin{equation*}
N(\mu,r):= [2r]\,-\,\Bigg\{j +
\sum_{i=0}^{j-1} m_{r-i}(\mu): \,\,1\leq j\leq
r\Bigg\},
\end{equation*}
\textit{with $m_j(\mu)$ the multiplicity of $j$ in the partition $\mu$ of $r,$ and $\sum_{(\kappa_\nu)}$ denoting the sum over the
family of discrete variables
\[
\Big\{\kappa_\nu: \nu\in N(\mu,r)\Big\}
\]
satisfying $\kappa_\nu\geq0$ for $\nu\in N(\mu,r)$ and
$\sum_\nu \kappa_\nu = \rho - r s$.}

Observing that, for $1\leq\rho<s$ and every $r\geq0$, the summation over the $\kappa_\nu$ in the definition of the $\mathcal{A}_\rho(s)$ is empty, while $\mathcal{A}_0(s)=1$, we obtain the following estimate, which will be used in Section 5.

{\bf Corollary 1.} \textit{For fixed $s>0,$ we have}
\[
\Phi_s(n) = 2\,+\,\mathcal{O}(n^{-s}),\quad n\rightarrow\infty.
\]

Combining Proposition~3 with Bender's method \cite{Be} finally yields the following.

{\bf Proposition~4} [M\"uller/Puchta~\cite{MP1}, Theorem~2].
\textit{For $d\geq3,$ the function $s_n(\Gamma_d)$ satisfies the asymptotic expansion}
\[
s_n(\Gamma_d) \approx 2 n (n!)^{d-2}
\Bigg\{1 + \sum_{\nu\geq1} \mathcal{C}_\nu(d)
 n^{-\nu}\Bigg\}\quad(n\rightarrow\infty),
\]
\textit{where, for $\nu\geq1,$}
\begin{multline*}
\mathcal{C}_\nu(d) =
\sum_{k=1}^{\lfloor\frac{\nu}{d-2}
\rfloor}\,\sum_{\eta_1+\cdots+\eta_{k-1}+\eta+\rho+k(d-2)
=\nu}\, \mathfrak{c}_k(d)\, k^\eta\,
 \binom{\eta+\rho-1}{\eta}\,
\mathcal{A}_\rho(d-2)\\[2mm]
\times\,\prod_{i=1}^{k-1}\bigg[i^{\eta_i}\,
\binom{d+\eta_i-3}{\eta_i}\bigg],
\end{multline*}
\textit{and}
\[
\mathfrak{c}_k(d) = \Bigg\langle\Bigg(\sum_{n\geq0}\,
(n!)^{d-2}\, \Phi_{d-2}(n)\, z^n\Bigg)^{-1}\,\,
\Bigg\vert\,\, z^k\Bigg\rangle.
\]
\section{Subgroup growth of Fuchsian groups}
\label{Sec:FuchsianGroups}
By a Fuchsian group we shall mean a group $\Gamma$ having a presentation of the form\footnote{$\Gamma$ is a Fuchsian group in the most general sense met in the literature; cf., for instance, \cite[Prop.~5.3]{LS} or \cite[Sec.~II.7]{Magnus}.}
\begin{multline}
\label{Eq:FuchsPres1}
\Gamma = \Big\langle x_1,\ldots, x_r, y_1,\ldots, y_s,
u_1,
v_1,\ldots, u_t, v_t\,\Big\vert\\[3mm]
x_1\cdots x_r\, y_1^{e_1}\cdots
y_s^{e_s}\, [u_1,v_1]\cdots[u_t,v_t] = 
x_1^{a_1} = x_2^{a_2} = \cdots = x_r^{a_r} =
1\Big\rangle,
\end{multline}
where $r,s,t$ are non-negative integers, $e_1,\ldots,e_s$ are integers $\geq2$, and $a_1,\ldots,a_r\in\N\cup\{\infty\}$. 
If, for instance, $r=s=0$, then $\Gamma=\Gamma_t^+$, while for $r=t=0$ and $e_1=\cdots=e_s=2$ we have $\Gamma=\Gamma_s^-$. Another prominent class of examples are the (orientation preserving) hyperbolic triangle groups
\[
\Delta(p,q,r) = \Big\langle x,y,z\,\Big\vert\, x^p = y^q = z^r = xyz = 1\Big\rangle 
\]
with
\[
\frac{1}{p} + \frac{1}{q} + \frac{1}{r}\,<\, 1.
\] 
Here, $r=3$, $s=t=0$, $a_1=p$, $a_2=q$, and $a_3=r$. For a Fuchsian group as in (\ref{Eq:FuchsPres1}), we define the \emph{hyperbolic measure} $\mu(\Gamma)$ of $\Gamma$ via
\[
\mu(\Gamma):= \sum_i \Big(1-\frac{1}{a_i}\Big)\,+\, s\,+\,2(t-1).
\]
It can be shown that the hyperbolic measure is in fact an invariant of $\Gamma$, that is, independent of the Fuchsian presentation chosen for $\Gamma$, and one would expect $\mu(\Gamma)$ to play a role  similiar to that played by the rational Euler characteristic $\chi(\Gamma)$ in the case of virtually free groups. We shall also need another invariant, first introduced in \cite{MP3}, which yields a rough measure for the size of the Fuchsian group $\Gamma$:
\begin{align*}
\alpha(\Gamma)&:= \sum_i\Big(1-\frac{1}{a_i}\Big)\,+\,\sum_j \frac{2}{e_j}\,+\, 2(t-1)\\[2mm]
&= \mu(\Gamma)\,-\,\sum_j\Big(1-\frac{2}{e_j}\Big).
\end{align*}
Finally, we set $m_\Gamma:= [a_1,a_2,\ldots,a_r]$. The main result of this section provides an asymptotic estimate for the subgroup growth of large Fuchsian groups. 

{\bf Theorem~4} [M\"uller/Schlage--Puchta \cite[Theorem~3]{MP3}, 2002]. 
L\textit{et $\Gamma$ be as in $(\ref{Eq:FuchsPres1}),$ and suppose that $\alpha(\Gamma)>0$. Then the number of index $n$ subgroups in $\Gamma$ satisfies an asymptotic expansion}
\begin{equation}
\label{Eq:FuchsAsymp}
s_n(\Gamma) \approx \delta \hat{L}_\Gamma (n!)^{\mu(\Gamma)} \hat{\Phi}_\Gamma(n) \bigg\{1 + \sum_{\nu\geq1} a_\nu(\Gamma) n^{-\nu/m_\Gamma}\bigg\},\quad n\rightarrow\infty.
\end{equation}
\textit{Here,}
\[
\delta = \begin{cases}
            2,& \forall i:  a_i\, \mbox{\em finite and odd, } \forall j: e_j\, \mbox{\em even}\\
            1,&\mbox\em {otherwise,}
\end{cases}
\]

\[
\hat{L}_\Gamma = (2\pi)^{-1/2-\sum_i(1-1/a_i)} \bigg(\prod_{a_i\neq\infty} a_i\bigg)^{-1/2} \exp\bigg(-\sum_{2\mid a_i} \frac{1}{2 a_i}\bigg),
\]

\[
\hat{\Phi}_\Gamma (n)= n^{3/2-\sum_i(1-1/a_i)} \exp\Bigg(\sum_i \underset{d< a_i}{\sum_{d\mid a_i}}\, \frac{n^{d/a_i}}{d}\Bigg),
\]
\textit{and the $a_\nu(\Gamma)$ are explicitly computable constants depending only on $\Gamma$.}\footnote{See \cite[Sec.~5.2]{MP3} for details concerning the computation of the coefficients $a_\nu(\Gamma)$.}

As in the case of Proposition~4, the proof of Theorem~4 begins by establishing a character formula for the function $\vert\Hom(\Gamma, S_n)\vert$ counting the permutation representations of $\Gamma$ of degree $n$. (We remark in passing that, from a more philosophical point of view, this approach by means of a character formula for $|\Hom(\Gamma, S_n)|$ may be seen as a non-abelian and discrete analogue of the circle method, with the linear characters corresponding to the major arcs.)

{\bf Proposition~5} \cite[Formula~(38)]{MP3}. \textit{For $\Gamma$ as in $(\ref{Eq:FuchsPres1}),$ we have}
\begin{equation}
\label{Eq:FuchsCharForm1}
\vert\Hom(\Gamma, S_n)\vert = (n!)^{s+2t-1}\, \prod_{i=1}^r \vert\Hom(C_{a_i}, S_n)\vert\, \sum_{\lambda\vdash n} \frac{\prod_{i=1}^r \alpha_{\chi_\lambda}^{(a_i)} \prod_{j=1}^s m_{\chi_\lambda}^{(e_j)}}{(\chi_\lambda(1))^{r+s+2t-2}},
\end{equation}
\textit{where, for $q\in\N\cup\{\infty\}$ and an irreducible character $\chi,$}
\[
\alpha_\chi^{(q)} = \frac{1}{\vert\Hom(C_q, S_n)\vert}\,\sum_{\pi^q=1} \chi(\pi),
\]
\textit{and $m_\chi^{(q)} = \big\langle R_q^{S_n}\, \vert\, \chi\big\rangle$ is the Fourier coefficient of $\chi$ in the expansion of the $q$-th root number function}
\[
R_q^{S_n}(\pi) = \big\vert\big\{\sigma\in S_n:\, \sigma^q = \pi\big\}\big\vert
\]
\textit{of $S_n$.}
\begin{proof}
Let $w$ be a segment of 
\[
R = x_1 x_2\cdots x_r y_1^{e_1} y_2^{e_2}\cdots y_s^{e_s} [u_1,v_1] [u_2,v_2] \cdots [u_t,v_t],
\]
where powers $y_j^{e_j}$ and commutators $[u_k,v_k]$ are treated as single letters, and denote by $L(w)$ the formation length of $w$; that is, the number of letters (in the sense explained) comprising $w$. Given such a segment $w$ and $\pi\in S_n$, define $N_w(\pi)$ to be the number of solutions of the equation $w=\pi$, subject to the conditions $x_i^{a_i}=1$ for those $i$ for which $x_i$ occurs in $w$. Observing that $N_w(\pi)$ is a class function, define coefficients $\beta_\chi^{(w)}$ via the Fourier expansion
\[
N_w(\pi) = (n!)^{-1}\,\prod_{x_i\in w} \vert\Hom(C_{a_i}, S_n)\vert\,
\sum_{\chi\in \mathrm{Irr}(S_n)}\beta_\chi^{(w)} \chi(\pi).
\]
We claim that
\begin{equation}
\label{Eq:FuchsCharForm2}
\beta_\chi^{(w)} = (n!)^{\vert\{j:\, y_j\in w\}\vert + 2\vert\{k:\, u_k\in w\}\vert} \prod_{x_i\in w} \alpha_\chi^{(a_i)}\,\prod_{y_j\in w} m_\chi^{(e_j)} \big/\big(\chi(1)\big)^{\ell(w)-1},
\end{equation}
where $\ell(w)$ is the number of different generators $x_i, y_j, u_k, v_k$ occurring in $w$. The proof of (\ref{Eq:FuchsCharForm2}) is by induction on $L(w)$. If $L(w)=1$, then (i) $w=x_1$ (subject to the condition $x_1^{a_1}=1$), or (ii) $w=y_1^{e_1}$, or (iii) $w=[u_1,v_1]$, depending on whether $r>0$, $r=0$ and $s>0$, or $r=s=0$ and $t>0$. In cases (ii) and (iii), we have $N_w=R_{e_1}^{S_n}$ or $N_w=N^{S_n}$, respectively, hence $\beta_\chi^{(y_1^{e_1})} = n!\,m_\chi^{(e_1)}$ respectively $\beta_\chi^{([u_1,v_1])} = (n!)^2/\chi(1)$ by the definition of the multiplicity $m_\chi^{(e_1)}$ respectively Formula~(\ref{Eq:CharForm2}), as predicted by (\ref{Eq:FuchsCharForm2}). In case (i), 
\[
N_{x_1}(\pi) = \begin{cases}
                  1,& \pi^{a_1}=1\\
                  0,& \pi^{a_1}\neq 1,
                  \end{cases}
\]
and Equation (\ref{Eq:FuchsCharForm2}) requires us to verify the identity
\begin{equation}
\label{Eq:OrthRelConseq}
\frac{1}{n!}\,\sum_\chi\,\sum_{\sigma^{a_1}=1} \chi(\sigma)\,\chi(\pi) = \begin{cases}
                  1,& \pi^{a_1}=1\\
                  0,& \pi^{a_1}\neq 1,
                  \end{cases}
\end{equation}
which however follows directly from the orthogonality relation\footnote{Cf. \cite[Formula~(31.19)]{CR}.}
\begin{equation}
\label{Eq:OrthRel1}
\sum_\chi \chi({\bf c}_1)\,\overline{\chi({\bf c}_2)} = \frac{\vert G\vert}{\vert{\bf c}_1\vert}\,\delta_{{\bf c}_1,{\bf c}_2}.
\end{equation}
Similarly, the induction step breaks into three cases, according to which type of letter $x_i$, $y_j^{e_j}$, or $[u_k,v_k]$ is adjoined. We shall give the argument in the case where the new letter is $x_i$ for some $2\leq i\leq r$, the other two cases being similar but slightly easier. For $w'=wx_i$, we have
\begin{align*}
N_{w'}(\pi) &= \sum_{\sigma\in S_n} N_w(\sigma)\times\begin{cases}
                  1,& (\sigma^{-1}\pi)^{a_i}=1\\
                  0,& (\sigma^{-1}\pi)^{a_i}\neq 1,
                  \end{cases}\\[2mm]
&=\frac{1}{n!} \sum_\sigma N_w(\sigma) \sum_\chi\, \sum_{\tau^{a_i}=1} \chi(\tau)\, \chi(\sigma^{-1} \pi)\\[2mm]
&= \frac{1}{n!} \sum_\sigma \vert\Hom(C_{a_i}, S_n)\vert\,N_w(\sigma)\,\sum_\chi\alpha_\chi^{(a_i)}\,\chi(\sigma^{-1}\pi)\\[2mm]
&= \frac{\prod_{\nu=1}^i \vert\Hom(C_{a_\nu}, S_n)\vert}{(n!)^2}\,\sum_\sigma\,\sum_{\chi_1}\,\sum_{\chi_2}\,\alpha_{\chi_1}^{(a_i)}\,\beta_{\chi_2}^{(w)}\,\chi_1(\sigma^{-1}\pi)\,\chi_2(\sigma)\\[2mm]
&= \frac{\prod_{\nu=1}^i \vert\Hom(C_{a_\nu}, S_n)\vert}{n!}\,\sum_{\chi_1}\,\sum_{\chi_2}\,\alpha_{\chi_1}^{(a_i)}\,\beta_{\chi_2}^{(w)}\,\frac{\chi_1(\pi)}{\chi_1(1)}\,\delta_{\chi_1,\chi_2}\\[2mm]
&= \frac{\prod_{\nu=1}^i \vert\Hom(C_{a_\nu}, S_n)\vert}{n!}\,\sum_\chi\,\frac{\alpha_\chi^{(a_i)}\,\beta_\chi^{(w)}}{\chi(1)}\,\chi(\pi);
\end{align*}
that is,
\[
\beta_\chi^{(w')} = \frac{\alpha_\chi^{(a_i)}}{\chi(1)}\,\beta_\chi^{(w)} = \frac{\prod_{\nu=1}^i \alpha_\chi^{(a_\nu)}}{(\chi(1))^{i-1}},
\]
in accordance with (\ref{Eq:FuchsCharForm2}). Here, we have used (\ref{Eq:OrthRelConseq}) in step 2, the orthogonality relation\footnote{Cf. \cite[Formula~(31.16)]{CR}.}
\begin{equation}
\label{Eq:OrthRel2}
\sum_{x_1\in G}
\chi_1(x_2x_1)\,\overline{\chi_2(x_1)} = \frac{\vert G\vert\,\chi_1(x_2)}{\chi_1(1)}\,\delta_{x_1,x_2}
\end{equation}
in step 5, and the inductive hypothesis in the concluding computation of $\beta_\chi^{(w')}$.

With (\ref{Eq:FuchsCharForm2}) in hand, Equation~(\ref{Eq:FuchsCharForm1}) now follows by setting $w=R$ and $\pi=1$. 
\end{proof}
It is clear from Formula~(\ref{Eq:FuchsCharForm1}) that, in order to obtain asymptotic information concerning the function $\vert\Hom(\Gamma, S_n)\vert$ for a Fuchsian group $\Gamma$, we need an estimate for sums of the form
\[
\underset{\pi^q=1}{\sum_{\pi\in S_n}}\,\chi(\pi)
\]
as well as a good upper bound on the multiplicities $m_\chi^{(q)}$ of root number functions. Our main new results in this direction are as follows.

{\bf Theorem~5} [M\"uller/Schlage--Puchta \cite[Propositions~1 and 2(i)]{MP3}, 2002]. \textit{Let $\varepsilon>0$ and a positive integer $q$ be given, and let $\chi$ be an  irreducible character of $S_n$. Then, for sufficiently large $n,$}
\vspace{3mm}
\begin{itemize}
\item[(i)]
\[
\underset{\pi^q=1}{\sum_{\pi\in S_n}}
|\chi(\pi)|\,\leq\,\big(\chi(1)\big)^{\frac{1}{q}+
\varepsilon}\,\underset{\pi^q=1}{\sum_{\pi\in S_n}} 1,
\]
\vspace{3mm}
\item[(ii)]
\[
m_\chi^{(q)} \leq \big(\chi(1)\big)^{1-2/q+\varepsilon}.
\]
\end{itemize}
It can be shown that both bounds given in Theorem~5 are in fact best possible. Applying Theorem~5 together with a number of auxiliary results, we obtain an asymptotic expansion for $\vert\Hom(\Gamma, S_n)\vert$ in the case where $\alpha(\Gamma)>0$, that is, when $\Gamma$ is large, and Theorem~4 follows from this expansion via Bender's method \cite{Be}.

Theorem~4 has a number of noteworthy consequences for the classification of Fuchsian groups; in particular, it leads to the solution of a long standing problem, apparently first raised in an important special case by Hurwitz, and later brought to the forefront in its general form by Roger Lyndon during a meeting at IAS Princeton in 1968:

\begin{center}
\textit{Can a (non-degenerate) Fuchsian group have infinitely many Fuchsian presentations?} 
\end{center}

Indeed, it is not hard to give examples of Fuchsian groups of positive hyperbolic measure allowing for more than one presentation of the form (\ref{Eq:FuchsPres1}). 

Call two finitely generated groups $\Gamma$ and $\Delta$ \textit{equivalent}, denoted $\Gamma\sim\Delta$, if
\[
s_n(\Gamma) = \big(1 + o(1)\big)\,s_n(\Delta),\quad n\rightarrow\infty.
\] 
In \cite[Theorem~3]{MuInvent} a characterization in terms of structural invariants is given for the equivalence relation $\sim$ on the class of groups $\Gamma$ of the form (\ref{Eq:FreeProd}), and it is shown that each $\sim$-class decomposes into finitely many isomorphism classes. Our next result is concerned with the corresponding problem for Fuchsian groups. Denote by $\mathcal{F}$ the class of all groups $\Gamma$ having a presentation of the form (\ref{Eq:FuchsPres1}) with $\alpha(\Gamma)>0$, and by $\cong$ isomorphy of groups.

{\bf Theorem~6} [M\"uller/Schlage--Puchta \cite[Theorem~6(ii) and Corollary~2]{MP3}, 2002].
\begin{itemize}
\item[(i)] \textit{Let}
\begin{multline*}
\Gamma = \Big\langle x_1,\ldots, x_r, y_1,\ldots, y_s,
u_1,v_1,\ldots, u_t, v_t\,\Big\vert\\[3mm]
x_1\cdots x_r\, y_1^{e_1}\cdots
y_s^{e_s}\, [u_1,v_1]\cdots[u_t,v_t] = 
x_1^{a_1} = \cdots = x_r^{a_r} = 1\Big\rangle
\end{multline*}
\textit{and}
\begin{multline*}
\Delta = \Big\langle x_1,\ldots, x_{r'}, y_1,\ldots, y_{s'},
u_1,v_1,\ldots, u_{t'}, v_{t'}\,\Big\vert\\[3mm]
x_1\cdots x_{r'}\, y_1^{e_1'}\cdots
y_{s'}^{e_{s'}'}\, [u_1,v_1]\cdots[u_{t'},v_{t'}] = 
x_1^{a_1'} = \cdots = x_{r'}^{a_{r'}'} = 1\Big\rangle
\end{multline*}
\textit{be Fuchsian groups such that $\alpha(\Gamma), \alpha(\Delta)>0$. Then we have $\Gamma\sim\Delta$ if, and only if,}
\begin{itemize}
\item[(a)] \textit{the multisets $\{a_i:\, 1\leq i\leq r\}$ and $\{a_i':\, 1\leq i\leq r'\}$ coincide,}
\item[(b)] $\mu(\Gamma) = \mu(\Delta)$,
\item[(c)] $\delta = \delta'$.
\end{itemize}
\item[(ii)] \textit{Let $\Gamma$ be a Fuchsian group as in {\em (\ref{Eq:FuchsPres1})} with $\alpha(\Gamma)>0$. Then the set
\[ 
\{\Delta\in\mathcal{F}:\, \Delta\sim\Gamma\}/\cong 
\]
is finite if, and only if, one of the following holds:}
\begin{itemize}
\item[(a)] $s=t=0$,
\item[(b)] $s=1,\, t=0,\, \sum_i\big(1-\frac{1}{a_i}\big)<2$,
\item[(c)] $s=2t=2,\, r=1$.
\end{itemize}
\item[(iii)] \textit{Let $\Gamma$ be as in} (ii). \textit{Then the set}
\[
\big\{\Delta\in\mathcal{F}:\, \Delta\sim\Gamma\big\}\big/\cong
\]
\textit{is infinite, while the set}
\[
\big\{\Delta\in\mathcal{F}:\, s_n(\Delta) = \big(1 + \mathcal{O}(n^{-2\mu(\Gamma)})\big)\,s_n(\Gamma)\big\}\big/\cong
\]
\textit{is finite if, and only if, the following three conditions are satisfied:}
\begin{itemize}
\item[(a)] $s+2t+\sum_i\big(1-\frac{1}{a_i}\big) \geq3$,
\item[(b)] $a_i$ \textit{is odd for } $1\leq i\leq r$,
\item[(c)] $e_j=2$ \textit{for $1\leq j\leq s$ with at most one exception, and for the exceptional index $j_0$ (if it occurs), we have $e_{j_0}=2^{p-1}$ for some prime $p$.}
\end{itemize}
\end{itemize}
It follows in particular from Theorem~6 that, unlike the situation for free products (\ref{Eq:FreeProd}), the asymptotic class of the function $s_n(\Gamma)$ does not in general determine $\Gamma$ up to finitely many isomorphism types. On the other hand, part (iii) of that theorem indicates that a finiteness result may perhaps be obtained by increasing the precision with which we measure the asymptotic behaviour of $s_n(\Gamma)$. It is therefore natural to ask, what happens if we take into account the full precision of (\ref{Eq:FuchsAsymp}) in Theorem~4. More specifically, consider three refinements of the equivalence relation $\sim$: (i) the relation $\approx$ of \textit{strong equivalence} defined via
\[
\Gamma\approx\Delta :\Longleftrightarrow s_n(\Gamma) = s_n(\Delta)\big(1 + \mathcal{O}(n^{-A})\big)\mbox{ for every } A>0,
\]
(ii) isomorphy, and (iii) equality of the system of parameters
\[
(r,s,t;a_1,a_2,\ldots,a_r,e_1,e_2,\ldots,e_s)
\]
in the Fuchsian presentation~(\ref{Eq:FuchsPres1}), denoted $\Gamma=\Delta$.\footnote{Strictly speaking, all these equivalence relations are now defined on the set $\mathcal{FP}$ of Fuchsian presentations (in the sense of (\ref{Eq:FuchsPres1})) with $\alpha>0$.} Clearly,
\[
\Gamma = \Delta \,\Longrightarrow\, \Gamma\cong\Delta\, \Longrightarrow\, \Gamma\approx\Delta \,\Longrightarrow\, \Gamma\sim\Delta.
\]
It can be shown that all these implications are in fact strict. With this notation, we now have the following important result, which in particular settles Lyndon's problem mentioned above.

{\bf Theorem~7} [M\"uller/Schlage--Puchta \cite[Theorem~7]{MP3}, 2002]. \textit{Each $\approx$-equivalence class of $\mathcal{FP}$ decomposes into finitely many classes with respect to the relation $=;$ that is, each group $\Gamma\in\mathcal{F}$ has only finitely many presentations of the form {\em (\ref{Eq:FuchsPres1}),} and is $\approx$-equivalent to at most finitely many non-isomorphic $\mathcal{F}$-groups.}
\section{Parity patterns in one-relator groups}
\subsection{The result}
We shall work over the alphabet
\[
\mathcal{A} = \Big\{x_1, x_2,\ldots, x_1^{-1},
x_2^{-1},\ldots\Big\}.
\]
Define a class of words $\mathcal{W}$ over $\mathcal{A}$
by the following rules.
\begin{itemize}
\item[(i)] $x_j^2, [x_j,x_k]\in\mathcal{W}$ for $j,k\geq1$ and $j\neq k$.
\item[(ii)] If $w_1, w_2\in\mathcal{W}$ have no generator
in common, then $w_1w_2\in\mathcal{W}$.
\item[(iii)] If $v\in\mathcal{W}$, and $x_j$ is a generator not
occurring in $v$, then $[v,x_j]\in\mathcal{W}$.
\item[(iv)] $\mathcal{W}$ is the smallest set of words over
$\mathcal{A}$ satisfying (i), (ii), and (iii).
\end{itemize}
Clearly, all surface group relators
\[
\prod_{j=1}^g [x_{2j-1},x_{2j}]\,\, \mbox{ and }\,\,
\prod_{j=1}^h x_j^2,\quad g,h\geq1
\]
are contained in $\mathcal{W}$, as is for instance the
word $w = [x_1^2 x_2^2, x_3]$. For a word
$w=w(x_1,\ldots,x_d)$ over $\mathcal{A}$ involving the
generators $x_1,\ldots, x_d$, define the one-relator
group $\Gamma_w$ \textit{associated with} $w$ via
\[
\Gamma_w = \Big\langle x_1,\ldots,x_d\, \Big\vert\,
w(x_1,\ldots,x_d)=1\Big\rangle.
\]
Then we have the following surprising result.

{\bf Theorem~8} [M\"uller/Puchta \cite[Theorem~1]{MP2}, 2003]. \textit{If $w$ is
in $\mathcal{W}$ and involves at least three generators, then
$s_n(\Gamma_w)$ is odd if, and only if, $n=k^2$ or $n=2k^2$ for
some $k\geq1;$ in particular, all groups $\Gamma_w$ with
$w\in\mathcal{W}$ involving three or more generators share
the same parity pattern, and $s_n(\Gamma_w)$ is multiplicative modulo $2$.}

It appears likely that Theorem~8 is best possible in
the sense that if, for some word $w$ over $\mathcal{A}$
the function $s_n(\Gamma_w)$ displays the parity pattern
described in Theorem~8, then in fact $w\in\mathcal{W}$.
\subsection{Some background: A recurrence relation
modulo
$2$, Euler's pentagonal theorem, and the parity of the
partition function}
The key to Theorem~8 lies in a remarkable recurrence
relation for the mod $2$ behaviour of $s_n(\Gamma_w)$
with $w\in\mathcal{W}$.

{\bf Proposition~6} [M\"uller/Puchta \cite[Theorem~3]{MP2}, 2003]. \textit{Let $w\in\mathcal{W}$ be a word involving three or more
generators. Then, modulo $2,$}
\begin{equation}
\label{Eq:TriangDesc}
s_n(\Gamma_w) \equiv
\underset{k(k+1)<2n}{\sum_{k\geq1}}
s_{n-\frac{1}{2}k(k+1)}(\Gamma_w)\, +\, \delta(n),
\quad n\geq1,
\end{equation}
\textit{where}
\[
\delta(n) = \begin{cases}
               1,& \mbox{\em $n$ odd and triangular}\\
               0,&\mbox{\em otherwise.}
               \end{cases}
\]
The background of Proposition~6 is representation-theoretic, and will be discussed below. Here, let me digress for a moment, and explain why, with Proposition~6 in hand, Theorem~8 nevertheless almost would have remained undiscovered.

Looking at Equation~(\ref{Eq:TriangDesc}), which descends
in triangular numbers, one cannot help but feel reminded
of Euler's pentagonal theorem
\[
\prod_{n\geq1} (1 - q^n) = 1 + \sum_{k\geq1} (-1)^k
q^{\frac{1}{2}k(3k-1)} (1+q^k) =
\sum_{k=-\infty}^\infty
(-1)^k q^{\frac{1}{2}k(3k-1)},
\]
which yields the recurrence relation
\[
p(n) = \sum_{k\geq1}
(-1)^{k+1}\bigg\{p\Big(n-\frac{1}{2}k(3k-1)\Big) +
p\Big(n-\frac{1}{2}k(3k+1)\Big)\bigg\},\quad n\geq1
\]
for the partition function $p(n)$, with the convention
that $p(n)=0$ for $n<0$; cf. \cite[Chapter~1.3]{Andrews}.
However, while $p(n)$ is known to satisfy a number of
congruences (for instance modulo $5$, $7$, and $11$)
when $n$ is in certain arithmetic progressions\footnote{Cf.
\cite{Knopp} for a comprehensive account up to 1970
concerning divisibility properties of $p(n)$. Some
exciting recent developments in this area are described in
\cite{AO1} and \cite{AO2}.}, there do not seem to be any such congruences modulo $2$ and $3$. In fact, the parity of $p(n)$ appears to be quite random, and, on the basis of extensive numerical evidence, it is believed that the partition function is `about equally often' even and odd; that is, that
\[
\underset{p(n)\equiv0\hspace{.3mm}(2)}{\sum_{n\leq x}}
1\,\,\sim\,\, \frac{x}{2}\quad(x\rightarrow\infty);
\]
cf. \cite{ParkinShanks}. Subbarao \cite{Subbarao} has
conjectured that, for any arithmetic progression
$r\, (\textrm{mod}\,\,t)$, there are infinitely many
integers $m\equiv r\,(t)$ for which $p(m)$ is odd, and
also infinitely many integers $n\equiv r\,(t)$
for which $p(n)$ is even. Partial results in this
direction have been obtained by Ono \cite{Ono}.
Recently, Nicolas, Ruzsa, and S\'ark\"ozy \cite{NRS} have shown
that, for all $r$ and $t$,
\[
x^{-\frac{1}{2}} \underset{p(n)\equiv\hspace{.2mm} 0
\hspace{.3mm}(2)}
{\underset{n\equiv r\hspace{.3mm}(t)}{\sum_{n\leq x}}}
1\,\,\rightarrow\,\,\infty\quad\mbox{as $x\rightarrow
\infty$.}
\]
In an appendix to the latter paper, Serre shows that the
same type of result holds in fact for the coefficients of
arbitrary modular forms. Against this background,
Theorem~8 appears highly surprising. Once conjectured
however, it can be established by induction on $n$, using
the  recurrence relation (\ref{Eq:TriangDesc}) together
with classical results of Gau{\ss} and Legendre concerning
the representation numbers of binary quadratic forms; cf.
\cite[\S~205]{Gauss}, \cite{Legendre}, \cite[Chapter~VI.8]{Davenport}, and \cite[Satz~89]{Hecke}.
\subsection{Some representation theory}
The proof of Proposition~6 depends on certain parity
properties of character values and multiplicities for
symmetric groups, which appear to be both new and of
independent interest. Given a word $w=w(x_1,\ldots,x_d)$
over the alphabet $\mathcal{A}$ involving the generators
$x_1,\ldots, x_d$, and an irreducible character $\chi$ of
$S_n$, define complex numbers $\alpha_\chi(w)$ by means
of the Fourier expansion
\begin{align*}
N_w(\sigma) &=
\Big\vert\Big\{(\sigma_1,\ldots,\sigma_d)
\in S_n^d:\, w(\sigma_1,\ldots,\sigma_d) =
\sigma\Big\}
\Big\vert\\[2mm]
&= (n!)^{d-1} \sum_\chi \alpha_\chi(w) \chi(\sigma),
\quad \sigma\in S_n,
\end{align*}
where the sum is taken over the set $\mathrm{Irr}(S_n)$
of all irreducible characters $\chi$ of $S_n$. Note that $N_w(\sigma)$ is a class function, thus the coefficients
$\alpha_\chi(w)$ are well defined. Applying standard
results from the representation theory of symmetric
groups, it is not difficult to establish the following
information concerning the $\alpha_\chi(w)$, leading to
the explicit computation of these coefficients for each word
$w\in\mathcal{W}$ and all $\chi\in\mathrm{Irr}(S_n)$.

{\bf Lemma~1} \cite[Lemma~1]{MP2}. \textit{Let
$w_1, w_2, v$ be words over $\mathcal{A},$ and let
$\chi$ be an irreducible character of $S_n$.}
\begin{itemize}
\item[(i)] \textit{We have $\alpha_\chi(x_j^2) = 1$
and
$\alpha_\chi([x_j,x_k]) = \frac{1}{\chi(1)}$ for all
$j,k\geq1$ and $j\neq k$.}
\item[(ii)] \textit{If $w_1$ and $w_2$ have no
generator
in common, then}
\[
\alpha_\chi(w_1w_2) = \frac{\alpha_\chi(w_1)\,
\alpha_\chi(w_2)}{\chi(1)}.
\]
\item[(iii)] \textit{If $x_j$ does not occur among the
generators of $v,$ then}
\[
\alpha_\chi([v,x_j]) = \frac{1}{\chi(1)}
\sum_{\chi'\in\mathrm{Irr}(S_n)}
\alpha_{\chi'}(v)\,\langle\chi^2\mid\chi'\rangle.
\]
\end{itemize}
Indeed, (i) simply restates the fact that the square root
function is the model character of $S_n$, as well as
Equation~(\ref{Eq:CharForm2}), the character formula for
the function $N^G$; and parts (ii) and (iii) also follow
by arguments much in the spirit of Section~\ref{Sec:Surface}.

Denote by $\varphi$ the bijection between the
self-conjugate partitions of $n$ and the partitions of
$n$ into distinct odd parts, mapping a self-conjugate
partition $\lambda$ onto the partition given by the
symmetric main hooks of $\lambda$. For example, 
\[
\varphi(6,5,4,3,2,1) = (11,7,3).
\]
Furthermore, denote by ${\bf c}_\lambda$ the conjugacy
class of $S_n$ whose cycle structure is given by the
partition $\lambda\vdash n$, and by $\chi_\lambda$ the
irreducible character of $S_n$ corresponding to the
Specht module $S^\lambda$. Then an inductive argument
based on the Murnaghan-Nakayama rule enables one to prove
the following result.\footnote{Note that the Murnaghan-Nakayama rule implies in particular that characters of $S_n$ are integer-valued. A more elementary argument uses the fact that, for all $\sigma\in S_n$ and exponents $a$ coprime to the order of $\sigma$, the permutations $\sigma$ and $\sigma^a$ are conjugate.}

{\bf Lemma~2} \cite[Lemma~2]{MP2}. \textit{Let $\lambda_1$
and $\lambda_2$ be partitions of $n,$ with $\lambda_1$
self-conjugate. Then $\chi_{\lambda_1}({\bf c}_{\lambda_2})$ is
odd if, and only if, $\lambda_2 = \varphi(\lambda_1)$.}

Call an irreducible character $\chi$ of $S_n$
\textit{symmetric}, if $\chi=\epsilon_n \chi$, where
$\epsilon_n=\chi_{(1^n)}$ is the sign character; this is
equivalent to demanding that the partition associated with
$\chi$ be self-conjugate. Lemma~2 thus describes the
parity of any symmetric character of $S_n$. A rather subtle
argument in the $\mathrm{GF}(2)$-algebra
\[
\mathfrak{A} = \mathrm{GF}(2)[\mathrm{Irr}(S_n)]
\]
generated by the irreducible characters of $S_n$, building
heavily on Lemma~2, now establishes the following.

{\bf Lemma~3} \cite[Lemma~3]{MP2}. \textit{Let $\chi$
and $\chi'$ be irreducible characters of $S_n$.}
\begin{itemize}
\item[(i)] \textit{If $\chi$ is symmetric, then
$\big\langle\chi^{2^k}  \big\vert \chi'\big\rangle =
\big\langle\chi^{2^k}
\big\vert \epsilon_n \chi'\big\rangle$ for all $k$.}
\item[(ii)] \textit{If both $\chi$ and $\chi'$ are
symmetric, then $\langle\chi^2\vert\chi'\rangle$ is odd
if, and only if, $\chi=\chi'$.}
\end{itemize}
Call an irreducible character $\chi$ of $S_n$ a
\textit{$2$-core} character, if $n!/\chi(1)$ is odd.
Note that, since the dimension of an ordinary irreducible
representation of a finite group $G$ always divides the order of 
$G/\mathrm{centre}(G)$, this concept is well defined for
arbitrary finite groups; cf. \cite{Ito} or
\cite[Chapter~V, Satz~17.10]{Huppert}. For $G=S_n$, the
hook formula shows that an irreducible character
$\chi_\lambda$ is $2$-core if, and only if, all hook
lengths of the associated partition $\lambda$ are odd.
The last condition is easily seen to be equivalent to
requiring that $\lambda$ is of the form
$\triangle=(k,k-1,\ldots,1)$ for some $k\geq1$. It follows
that $S_n$ has a $2$-core character if, and only if,
$n=\frac{1}{2} k (k+1)$ is a triangular number, in which
case $\chi_\triangle$ is the unique $2$-core character;
in particular, the $2$-core character is symmetric. With
these preliminaries, we are now in a position to establish
the following result (a special case of
\cite[Lemma~4]{MP2}), which is the decisive tool in proving Proposition~6.

{\bf Lemma~4.} \textit{Let $w\in\mathcal{W}$ be a word
involving $d$ generators, and let $\chi$ be an
irreducible
character of $S_n$.}
\begin{itemize}
\item[(i)] \textit{If $d\geq2,$ then $(n!)^{d-2}
\chi(1)
\alpha_\chi(w)$ is an integer.}
\item[(ii)] \textit{If $d\geq3$ and $\chi$ is not
$2$-core, then $(n!)^{d-2} \chi(1) \alpha_\chi(w)$ is
even.}
\item[(iii)] \textit{If $d\geq2$ and $\chi$ is
$2$-core, then $(n!)^{d-2} \chi(1) \alpha_\chi(w)$ is
odd.}
\end{itemize}

\textit{Proof.} Using Lemma~1, we see by induction on $d$ that
$(\chi(1))^{d-1} \alpha_\chi(w)$ is integral for
$d\geq1$,
each irreducible character $\chi$, and every word
$w\in\mathcal{W}$, which implies (i). Moreover, if
$\chi$ is not
$2$-core, then $n!/\chi(1)$ is even, hence, for
$d\geq3$,
\[
(n!)^{d-2} \chi(1) \alpha_\chi(w) = \bigg(\frac{n!}
{\chi(1)}\bigg)^{d-2} \big(\chi(1)\big)^{d-1}
\alpha_\chi(w)
\]
is even, whence (ii). Now suppose that
$\chi=\chi_\triangle$ is $2$-core. We want to show that
in this case
$(\chi_\triangle(1))^{d-1} \alpha_{\chi_\triangle}(w)$
is odd. This is done by induction on the formation
length
of words in $\mathcal{W}$. By Lemma~1 (i), our claim
holds
for $w=x_j^2$ and $w=[x_j,x_k]$. Assume that our claim
is
true for words $w_1, w_2\in\mathcal{W}$ having no
generator in common, let $d_i$ be the number of
generators
involved in $w_i$, and consider the word $w=w_1w_2$.
Then
$w$ involves $d=d_1+d_2$ generators, and by part (ii)
of
Lemma~1,
\[
\big(\chi_\triangle(1)\big)^{d-1}
\alpha_{\chi_\triangle}(w) =
\big(\chi_\triangle(1)\big)^{d_1-1}
\alpha_{\chi_\triangle}(w_1)\cdot
\big(\chi_\triangle(1)\big)^{d_2-1}
\alpha_{\chi_\triangle}(w_2),
\]
which is odd, since by assumption both factors
$(\chi_\triangle(1))^{d_i-1}
\alpha_{\chi_\triangle}(w_i)$
are odd. Thus, it remains to show that our claim holds
for
$w=[v,x_j]$, provided it is true for
$v\in\mathcal{W}$,
 and $x_j$ does not occur in $v$. By Lemma~1~(iii),
\[
\big(\chi_\triangle(1)\big)^{d-1}
\alpha_{\chi_\triangle}(w) = \big(\chi_\triangle(1)
\big)^{d-2}\sum_{\chi'} \alpha_{\chi'}(v)
\big\langle\chi_\triangle^2\,\big\vert\,\chi'\big\rangle.
\]
Now we distinguish the cases $d\geq3$ and $d=2$. If
$d\geq3$ and $\chi'$ is not $2$-core, then
$(\chi'(1))^{d-2} \alpha_{\chi'}(v)$ is integral, and
$\chi_\triangle(1)$ is divisible by a higher power of $2$
than $\chi'(1)$. Hence, the terms in the last sum not
coming from the $2$-core character $\chi_\triangle$ sum
to an even integer, and we have
\[
\big(\chi_\triangle(1)\big)^{d-1}
\alpha_{\chi_\triangle}(w) \equiv
\big(\chi_\triangle(1)
\big)^{d-2} \alpha_{\chi_\triangle}(v)
\big\langle\chi_\triangle^2\,\big\vert\,\chi_\triangle\big\rangle
\bmod{2}.
\]
By assumption, $(\chi_\triangle(1))^{d-2}
\alpha_{\chi_\triangle}(v)$ is odd, as is the multiplicity
$\big\langle\chi_\triangle^2 \big\vert \chi_\triangle\big\rangle$ by
Lem\-ma~3~(ii). Hence, $(\chi_\triangle(1))^{d-1}
\alpha_{\chi_\triangle}(w)$ is odd, and the induction on
formation length is complete in this case. It remains to
deal with the case where $d=2$. Then $w=\big[x_j^2, x_k\big]$
for some $j\neq k$, and, by Lemma~1 parts (i) and (iii),
\[
\chi_\triangle(1) \alpha_{\chi_\triangle}(w) =
\sum_{\chi'}
\big\langle\chi_\triangle^2\,\big\vert\,\chi'\big\rangle.
\]
By Lemma~3 (i) for $k=1$, the right-hand side is congruent
modulo $2$ to
\[
\underset{\lambda=\lambda'}{\sum_{\lambda\vdash n}}
\big\langle\chi_\triangle^2\,\big\vert \chi_\lambda\big\rangle,
\]
which is odd by part (ii) of this lemma.\hfill$\Box$

With Lemma~4 in hand, we can now establish
Proposition~6.
Let $w\in\mathcal{W}$ be a word involving $d\geq3$
generators. By the transformation formula
(\ref{Eq:Transform1Equiv}), the subgroup numbers
$s_n(\Gamma_w)$ are related to the sequence
$h_n(\Gamma_w):= |\Hom(\Gamma_w, S_n)|/n!$ via the
equation
\[
n h_n(\Gamma_w) = \sum_{\nu=0}^{n-1}
s_{n-\nu}(\Gamma_w)
h_\nu(\Gamma_w),\quad n\geq1.
\]
Moreover, since homomorphisms of $\Gamma_w$ to $S_n$ can
be identified with solutions of the equation
$w(x_1,\ldots,x_d)=1$ in $S_n$, we have
\[
h_n(\Gamma_w) = (n!)^{-1} N_w(1) = (n!)^{d-2}
\sum_\chi
\alpha_\chi(w) \chi(1).
\]
From Lemma~4 we know that $h_n(\Gamma_w)$ is odd if, and
only if, $n$ is a triangular number. Hence, for $n\geq1$,
we find that, modulo $2$,
\begin{align*}
s_n(\Gamma_w) &= n h_n(\Gamma_w) - \sum_{\nu=1}^{n-1}
s_{n-\nu}(\Gamma_w) h_\nu(\Gamma_w)\\[2mm]
&\equiv \underset{k(k+1)<2n}{\sum_{k\geq1}}
s_{n-\frac{1}{2}k(k+1)}(\Gamma_w)\,+\,\delta(n),
\end{align*}
the correction term $\delta(n)$ coming from the term 
$n h_n(\Gamma_w)$.
\section{Random Walks on symmetric groups}
\subsection{Roichman's conjectures}
Let ${\bf E} = E_1, E_2, E_3,\ldots$ be a Markov chain on
a metric space $X$; i.e., the probability of a sample sequence
$\big(E_{j_0}, E_{j_1},\ldots, E_{j_n}\big)$ is given by
\[
p\big\{\big(E_{j_0}, E_{j_1},\ldots, E_{j_n}\big)\big\} = a_{j_0}
p_{j_0,j_1} p_{j_1,j_2}\cdots p_{j_{n-2},j_{n-1}}
p_{j_{n-1},j_n},
\]
where $p_{j,k}$ is the probability for the transition from
$E_j$ to $E_k$, $a_k$ is the probability of the state
$E_k$ at time $0$, and the initial probability
distribution $\{a_k\}$ as well as the conditional
probabilities $p_{j,k}$ are fixed throughout the whole
process. The random walk on $X$ determined by ${\bf
E}$ is by definition the collection of all infinite paths on
$X$ with probability distribution induced by ${\bf E}$.
If $X$ is finite, and the initial probability distribution
$\{a_k\}$ is given in advance, then ${\bf E}$ is
determined by its transition matrix $P=(p_{j,k})$.
In what follows, we will be interested in the case when
$X$ is a finite symmetric group given with the discrete
metric. In this case, paths are simply infinite sequences $\{x_k\}_{k\geq0}$ of states 
(that is, elements of $S_n$). Let $X=S_n$, and let $1\neq {\bf c}\subseteq S_n$ be a
non-trivial conjugacy class. The random walk $w_{\bf c}$
\textit{generated by ${\bf c}$} has initial state $x_0=\mbox{id}$ and the transition matrix 
$P_{\bf c} = \big(p^{\bf c}_{\sigma,\pi}\big)_{\sigma,\pi\in S_n}$, where
\[
p_{\sigma,\pi}^{\bf c}:= \begin{cases}
                           \frac{1}{|{\bf c}|},&
                           \pi\sigma^{-1}\in{\bf c}\\
                           0,& \mbox{otherwise.}
                           \end{cases}
\]
More explicitly, the statement concerning the initial state of $w_{\bf c}$ means that the initial probability distribution $p_\mathrm{initial}$ is concentrated in the identity; that is,
\[
p_\mathrm{initial}\{\pi\} = \begin{cases}
                               1,&\pi=\mbox{id}\\
                               0,&\mbox{otherwise}
\end{cases}.
\]
Given a norm $\|\cdot\|$ on the complex algebra $\mathbb{C}^{S_n}$
and a real number $\varepsilon>0$, we say that the random walk
$w_{\bf c}$ has reached \textit{$\varepsilon$-equidistribution
with respect to $\|\cdot\|$ in step $k$}, if
\begin{equation} \label{Eq:Equidis} 
\left\|p\{x_k=\cdot\} - \frac{2}{n!}{\bf
1}_{A_n}\right\|^2 \,\leq\, 
\varepsilon\cdot\left\|\frac{2}{n!} {\bf
1}_{A_n}\right\|^2.
\end{equation}
Here, ${\bf 1}_S$ denotes the characteristic function for
the subset $S$ of the sample space $X$. We define the
\textit{statistical mixing time}
$t_{\mathrm{stat}}({\bf c})$ of $w_{\bf c}$ as the least even 
integer $k$ for which $w_{\bf c}$ has reached $\frac{1}{n}$-equidistribution 
with respect to the $\ell^2$-norm; that is, the norm on 
$\mathbb{C}^{S_n}$ given by
\[
\|f\|_2^2 = \langle f\vert f\rangle = \frac{1}{n!} \sum_{\sigma\in S_n}
|f(\sigma)|^2,\quad f\in \mathbb{C}^{S_n}.
\]
The appearance of ${\bf 1}_{A_n}$ in \eqref{Eq:Equidis} instead of the expected ${\bf
1}_{S_n}$  
is just a technical detail allowing us to avoid certain parity
problems in the symmetric group $S_n$. For the same reason, step
numbers are here restricted to even numbers.   
Computing the $\ell^2$-norm of $\frac{2}{n!}{\bf 1}_{A_n}$,  $t_{\mathrm{stat}}({\bf c})$ 
is seen to be the least even integer $k$ such that
\[
\left\|p\{x_k=\cdot\} - \frac{2}{n!}{\bf 1}_{A_n}\right\|_2^2 \,\leq\,
\frac{2}{n(n!)^2}.
\]
A lower bound for $t_{\mathrm{stat}}({\bf c})$ is
given by the \textit{combinatorial mixing time}
$t_{\mathrm{comb}}({\bf c})$ of ${\bf c}$; that is, the
least even integer $k$, such that any $k$ elements of
${\bf c}$ have no common fixed point with probability at
least $1-\frac{1}{n}$. A heuristic reason for the name ``combinatorial
mixing time" is the fact that, after $t_\mathrm{comb}({\bf c})$ steps,
almost certainly every element of the set $\{1,2,\ldots,n\}$ has been
moved by the conjugacy class ${\bf c}$. In \cite{Roichman}, Roichman
conjectures that, for every non-trivial conjugacy class
${\bf c}\subseteq A_n$,
\begin{equation}
\label{Eq:RoichConj}
t_{\mathrm{stat}}({\bf c}) \ll t_{\mathrm{comb}}({\bf
c}).
\end{equation}
His main result \cite[Theorem~6.1]{Roichman} establishes
this  conjecture for classes ${\bf c}$ with $cn$ fixed
points, where $c$ is some positive constant; this in turn generalizes an earlier result of
Diaconis and Shahshahani \cite{DS} for transpositions.
Following Roichman's paper, Fomin and Lulov \cite{FL}
provide a character bound implying
Conjecture~(\ref{Eq:RoichConj}) for conjugacy
classes having only cycles of the same length. In
\cite{MP3}, among other things, Roichman's conjecture is
established in full generality.

{\bf Theorem~9} [M\"uller/Schlage--Puchta \cite[Theorem~2]{MP3}, 2002]. \textit{For
$n\geq4000$ and each non-trivial conjugacy class ${\bf c}\subseteq S_n,$ we have}
\[
t_{\mathrm{comb}}({\bf c}) \leq t_{\mathrm{stat}}({\bf c})
\leq 10\,t_{\mathrm{comb}}({\bf c}).
\]
In \cite{Roichman}, Roichman suggests an approach to the
general conjecture (\ref{Eq:RoichConj}) via a certain
estimate for character values of symmetric groups. More
specifically, he conjectures that, for every
$\varepsilon>0$, $n$ sufficiently large, each conjugacy
class ${\bf c}\subseteq S_n$, and every partition $\lambda\vdash n$,
\begin{equation}
\label{Eq:RoichCharConj}
|\chi_\lambda({\bf c})| \leq
\chi_\lambda(1)\bigg(\max\bigg\{\frac{\lambda_1}{n},
\frac{\|\lambda\|}{n}, \frac{1}{e}\bigg\}
\bigg)^{(1-\varepsilon)n \log\frac{n}{n-\mathrm{supp}
({\bf c}) + 1}},
\end{equation}
which would imply (\ref{Eq:RoichConj}).
\subsection{A remark concerning the estimate
(\ref{Eq:RoichCharConj})} As it stands,
estimate~(\ref{Eq:RoichCharConj}) is not correct. This can be
seen, for instance, as follows. For ${\bf c}$ fixed-point free, $\lambda$ such that
$\max\{\lambda_1, \|\lambda\|\} \leq \frac{n}{e}$, and $\varepsilon=\frac{1}{2}$,
Inequality~(\ref{Eq:RoichCharConj}) simplifies to
\begin{equation}
\label{Eq:RoichCharConjCons}
|\chi_\lambda({\bf c})| \leq \chi_\lambda(1)\,
e^{-(n \log n)/2}.
\end{equation}
The right-hand side of (\ref{Eq:RoichCharConjCons}) is
bounded above by $\sqrt{n!}\,n^{-n/2} < 1$; that is, for
${\bf c}$ and $\lambda$ as above, and $n$ sufficiently
large, it would follow that $\chi_\lambda({\bf c})=0$.
Since the irreducible characters
$\{\chi_\lambda\}_{\lambda\vdash n}$ form a basis for the
space of class functions on $S_n$, this would imply that,
for $n$ sufficiently large, the set of characters
\begin{equation}
\label{Eq:CharSet}
\Big\{\chi_\lambda: \lambda\vdash n,\,\max\{\lambda_1,
\|\lambda\|\}>n/e\Big\}
\end{equation}
would have to generate the space of class functions on
the union of fixed-point free conjugacy classes of $S_n$.
Comparing the size of the set (\ref{Eq:CharSet}) with the
dimension of the last space, we find that, for large $n$,
\begin{equation}
\label{Eq:RoichConjPartEst1}
2 \sum_{0\leq\nu\leq n-n/e}p(\nu)\,\geq\, p(n)-p(n-1),
\end{equation}
where $p(n)$ is the number of partitions of $n$. The
right-hand side of (\ref{Eq:RoichConjPartEst1}) can be
estimated via the first term in Rademacher's series
expansion for $p(n)$ (see, for example,
\cite[Theorem~5.1]{Andrews}) to give
\[
p(n) -p(n-1)\,\sim\, \frac{\pi
e^{\pi\sqrt{\frac{2n}{3}}}}
{12 \sqrt{2}\, n^{3/2}}\quad(n\rightarrow\infty).
\]
Bounding the left-hand side of
(\ref{Eq:RoichConjPartEst1})
by means of the estimate\footnote{Cf., for instance,
\cite[Satz~7.6]{Kraetzel}.}
\[
p(n) < \frac{\pi}{\sqrt{6n}}\,
e^{\pi\sqrt{\frac{2n}{3}}},
\]
we obtain
\[
2 \sum_{0\leq\nu\leq n-n/e}p(\nu)\,\leq\,
2 n p(n-\lfloor n/e
\rfloor)\,\leq \,A \sqrt{n}\,\,
e^{\pi\sqrt{2(1-1/e)n/3}},
\]
where $A$ is some positive constant. From these two
estimates it is clear that
inequality~(\ref{Eq:RoichConjPartEst1}) is violated
for large $n$.
\subsection{Proof of Theorem~9 (Sketch)}
Despite the failure of his conjecture concerning
character values, the basic idea
behind Roichman's suggested approach to
(\ref{Eq:RoichConj}) turns out to be correct. As a
substitute for (\ref{Eq:RoichCharConj}), we prove the following.

{\bf Theorem~10} [M\"uller/Schlage--Puchta \cite[Theorem~1]{MP3}, 2002].
\textit{For sufficiently large $n,$ every non-trivial
conjugacy class ${\bf c}\subseteq S_n,$ and each partition
$\lambda\vdash n,$ we have}
\[
|\chi_\lambda({\bf c})| \,\leq\,
\big(\chi_\lambda(1)\big)^{1-\frac{1-1/\log n}{6
t_{\mathrm{comb}}({\bf c})}},
\]
\textit{and, for $1\leq s_1({\bf c}) \leq n-2$ (here, $s_1({\bf c})$ is the number of $1$-cycles of ${\bf c}$),}
\[
\left|t_{\mathrm{comb}}({\bf c})\,-\,\frac{2 \log
n}{\log\big(n/s_1({\bf c})\big)}\right|\, \leq\, 3,
\]
\textit{whereas $t_{\mathrm{comb}}({\bf c}) = 2$ for
$s_1({\bf c}) = 0$.}

The proof of Theorem~10 is essentially probabilistic, making use of the following two auxiliary results.

{\bf Lemma~5.} \textit{Let ${\bf c}\subseteq S_n$ be a non-trivial conjugacy class, and let $\pi$ be the element visited by the random walk $w_{\bf c}$ after $3 t_\mathrm{comb}({\bf c})$ steps. Then, for each $k\geq1,$ the probability that $\pi$ has more than $k$ fixed points is bounded above by}
\[
\max\bigg\{\frac{2^k}{(k-1)!},\, \frac{2^{n/2}}{(\lfloor n/2\rfloor - 1)!}\bigg\}.
\]
{\bf Lemma~6.} \textit{Let ${\bf c}_1, {\bf c}_2\subseteq S_n$ be non-trivial conjugacy classes with $f_1$ respectively $f_2$ fixed points. For $i=1,2,$ let $x_i\in{\bf c}_i$ be chosen at random. Then the probability that $x_1$ and $x_2$ have $\ell$ common fixed points, is at most
\[
\binom{n}{\ell} \bigg(\frac{f_1 f_2}{n^2}\bigg)^\ell.
\] 
Moreover, the probability for $x_1x_2$ to have $k$ cycles on $\mathrm{supp}(x_1) \cup \mathrm{supp}(x_2)$ is bounded above by}
\[
(\log n)^{k-1}/(k-1)!.
\]

We give a rough indication how Theorem~9 can be derived from the first part of 
Theorem~10; the second part then allows us to obtain completely explicit lower and upper bounds for $t_{\mathrm{stat}}({\bf c})$  in terms of the number of fixed points of ${\bf c}$, while also transforming the first part of Theorem~10 into a more explicit form. 
 
First, we note that the probability distribution $p\{x_k=\cdot\}$ in step $k$ of the random walk $w_{\bf c}$ is
given by the $k$-fold convolution of the function
$\frac{1}{|{\bf c}|} {\bf 1}_{\bf c}$ with itself, 
where, for two functions $f,g: S_n\rightarrow \mathbb{C}$, the
convolution $f\ast g: S_n\rightarrow\mathbb{C}$ is
defined as\footnote{Note that the convolution of two class 
functions is again a class function.}
\[
(f\ast g)(\pi) = \sum_{\sigma\in S_n} f(\sigma)
g(\pi\sigma^{-1}).
\]
Indeed,
\begin{align*}
p\{x_k=\pi\} &= \sum_{\sigma\in S_n} p\big\{x_{k-1}=\pi\sigma^{-1}\big\}\,
p^{\bf c}_{\pi\sigma^{-1},\pi}\\
&=  \frac{1}{\vert{\bf c}\vert}\,\sum_{\sigma\in{\bf c}} 
p\big\{x_{k-1}=\pi\sigma^{-1}\big\}\\
&= \bigg[\bigg(\frac{1}{\vert{\bf c}\vert} {\bf 1}_{\bf c}\bigg) \ast 
p\big\{x_{k-1}=\cdot\big\}\bigg](\pi),
\end{align*}
and since
\[
p\{x_1=\pi\} = p^{\bf c}_{\mathrm{id},\pi} = \bigg(\frac{1}{\vert{\bf c}\vert}
{\bf 1}_{\bf c}\bigg)(\pi),
\]
our claim that
\[
p\{x_k=\cdot\} = \bigg(\frac{1}{\vert{\bf c}\vert}
{\bf 1}_{\bf c}\bigg)^{\ast k}
\]
follows by induction on $k$. Next, we need a result relating the statistical mixing time of
the random walk $w_{\bf c}$ to the character theory of the
underlying finite group $S_n$. This is the following.

{\bf Lemma~7.} \textit{Let ${\bf c}\subseteq S_n$ be a conjugacy class, $k$ a positive integer. Then}
\begin{equation}
\label{Eq:RWLemma}
(n!)^2 \left\|\bigg(\frac{1}{|{\bf c}|}\,{\bf 1}_{\bf c}
\bigg)^{\ast k}\,-\,\frac{2}{n!}\,{\bf 1}_{A_n}\right\|^2_2
= \underset{\chi(1)\neq 1}{\sum_\chi} \frac{|\chi({\bf
c})|^{2k}}{(\chi(1))^{2k-2}}.
\end{equation}
\begin{proof}
For a class function $f: S_n\rightarrow\mathbb{C}$ and an irreducible character $\chi$ of $S_n$, define the Fourier coefficient $\alpha_\chi(f)$ via
\begin{equation}
\label{Eq:CoeffDef}
f(\sigma) = \sum_\chi \alpha_\chi(f)\,\chi(\sigma),\quad \sigma\in S_n.
\end{equation}
Since the irreducible characters form a basis for the space of class functions, the Fourier coefficients $\alpha_\chi(f)$ exist and are uniquely determined by (\ref{Eq:CoeffDef}). We shall need the following facts concerning the coefficients $\alpha_\chi(f)$.
\begin{itemize}
\item[(i)] $\alpha_\chi(f) = \langle f\vert \chi\rangle$,\vskip5pt
\item[(ii)] $\alpha_\chi(f\ast g) = n! \alpha_\chi(f) \alpha_\chi(g)/\chi(1)$,\vskip5pt
\item[(iii)] $\sum_\chi\vert\alpha_\chi(f)\vert^2 = \vert\!\vert f\vert\!\vert_2^2$. 
\end{itemize}
The proof of (i) consists in evaluating the sum $\sum_\chi\langle f\vert\chi\rangle \chi(\sigma)$ via the orthogonality relation (\ref{Eq:OrthRel1}), while (iii) (Parseval's Equation) follows directly from properties of the scalar product $\langle\cdot\vert\cdot\rangle$. We focus on the proof of (ii). By (i),
\begin{align*}
\alpha_\chi(f\ast g) &= \langle f\ast g\,\vert\,\chi\rangle\\
&= \frac{1}{n!} \sum_\pi (f\ast g)(\pi) \chi(\pi^{-1})\\
&= \frac{1}{n!} \sum_\pi \sum_\sigma f(\sigma) g(\pi\sigma^{-1}) \chi(\pi^{-1})\\
&= \frac{1}{n!} \sum_\pi \sum_\sigma \sum_{\chi'} \sum_{\chi''} \alpha_{\chi'}(f) \alpha_{\chi''}(g) \chi'(\sigma) \chi''(\pi\sigma^{-1}) \chi(\pi^{-1})\\
&= \sum_\pi \sum_{\chi'} \sum_{\chi''}\alpha_{\chi'}(f) \alpha_{\chi''}(g) \chi(\pi^{-1}) \frac{1}{n!} \sum_\sigma \chi''(\pi\sigma^{-1}) \overline{\chi'(\sigma^{-1})}\\
&= \sum_\pi \sum_{\chi'} \sum_{\chi''}\alpha_{\chi'}(f) \alpha_{\chi''}(g) \chi(\pi^{-1}) \chi''(\pi) \delta_{\chi',\chi''}/\chi''(1)\\
&= \sum_\pi \sum_{\chi'} \alpha_{\chi'}(f) \alpha_{\chi'}(g) \chi(\pi^{-1}) \chi'(\pi)/\chi'(1)\\
&= \sum_{\chi'} \frac{n! \alpha_{\chi'}(f) \alpha_{\chi'}(g)}{\chi'(1)} \langle\chi'\vert\chi\rangle\\
&= n! \alpha_{\chi}(f) \alpha_{\chi}(g)/\chi(1),  
\end{align*}
where we have used the orthogonality relation (\ref{Eq:OrthRel2}) in step 6.

With (i)--(iii) in hand, the proof of Lemma~7 boils down to a straightforward calculation. More specifically, applying (i), the Fourier coefficient $\alpha_\chi(f)$ of the function $f=\frac{1}{\vert{\bf c}\vert} {\bf 1}_{\bf c}$ is found to be
\begin{align*}
\bigg\langle\frac{1}{\vert{\bf c}\vert} {\bf 1}_{\bf c}\,\bigg\vert\,\chi\bigg\rangle &=\frac{1}{n!} \sum_\sigma \bigg(\frac{1}{\vert{\bf c}\vert} {\bf 1}_{\bf c}\bigg)(\sigma)\, \chi(\sigma^{-1})\\
&= \frac{1}{n!} \sum_{\sigma\in{\bf c}} \chi(\sigma^{-1})/\vert{\bf c}\vert\\
&= \chi({\bf c}^{-1})/n!.
\end{align*}
Property (ii) together with induction on $k$ then yields
\[
\alpha_\chi\bigg(\bigg(\frac{1}{\vert{\bf c}\vert} {\bf 1}_{\bf c}\bigg)^{\ast k}\bigg) = \frac{(\chi({\bf c}^{-1}))^k}{n! (\chi(1))^{k-1}},
\]
thus
\[
\alpha_\chi\bigg(\bigg(\frac{1}{\vert{\bf c}\vert} {\bf 1}_{\bf c}\bigg)^{\ast k}\, -\, \frac{2}{n!} {\bf 1}_{A_n}\bigg) = 
\frac{(\chi({\bf c}^{-1}))^k}{n! (\chi(1))^{k-1}}\,-\,\frac{1}{n!} \delta_{\chi,\chi_0}\,-\,\frac{1}{n!} \delta_{\chi,\chi_1}, 
\]
where $\chi_1$ is the sign character, $\chi_0$ the trivial character of $S_n$. Equation~(\ref{Eq:RWLemma}) follows now from Parsival's Equation (iii).
\end{proof}
{\bf Remark.} By an argument very similar to the proof of Lemma~7, one can show for instance that, for any finite group $G$, each conjugacy class ${\bf c}$ in $G$, and every positive integer $k$,
\[
\vert G\vert^2 \left\vert\!\left\vert\bigg(\frac{1}{\vert{\bf c}\vert} {\bf 1}_{\bf c}\bigg)^{\ast k}\,-\,\frac{1}{\vert G\vert} {\bf 1}_G\right\vert\!\right\vert_2^2 = \sum_{\chi\neq\chi_0} \frac{\vert\chi({\bf c})\vert^{2k}}{(\chi(1))^{2k-2}},
\]
where $\chi_0$ is the trivial character of $G$.

Now let ${\bf c}\subseteq S_n$ be a non-trivial conjugacy class.
Then we infer from Lemma~7 that $w_{\bf c}$ has reached $\frac{1}{n}$-equidistribution with respect to the $\ell^2$-norm
after $k$ steps if, and only if,
\[
\underset{\chi(1)\neq1}{\sum_\chi} \frac{|\chi({\bf
c})|^{2k}}{(\chi(1))^{2k-2}}\,\leq\,\frac{2}{n}.
\]
By the first part of Theorem~10, the left-hand side can be bounded above by
\[
\underset{\chi(1)\neq1}{\sum_\chi}
\big(\chi(1)\big)^{2-\frac{2k(1-1/\log n)}{6
t_{\mathrm{comb}}({\bf c})}}.
\]
For $k\geq 10 t_{\mathrm{comb}}({\bf c})$ and sufficiently large $n$, the last expression is less than
\[
\underset{\chi(1)\neq1}{\sum_\chi} \big(\chi(1)
\big)^{-5/4},
\]
which in turn is $\mathcal{O}\big(n^{-5/4}\big)$ by Corollary~1. Hence, for $n$ sufficiently large, we obtain the bound
$t_{\mathrm{stat}}({\bf c}) \leq 10 t_{\mathrm{comb}}
({\bf c})$ as required.
\begin{thebibliography}{99}
\bibitem{Andrews} G. Andrews, \textit{The Theory of Partitions}, Cambridge University Press, New York, 1984.
\bibitem{AO1} S. Ahlgren and K. Ono, Congruence
properties for the partition function, \textit{Proc. Nat. Acad.
Sciences USA} \textbf{98} (2001), 12882--12884.
\bibitem{AO2} S. Ahlgren and K. Ono, Congruences and conjectures for the partition function. In: $q$-Series with Applications to Combinatorics, Number Theory, and Physics (Urbana (IL), 2000),
\textit{Contemp. Math.} \textbf{291} (2001), Amer. Math. Soc., Providence (RI), 1--10.
\bibitem{Be} E.\,A. Bender, An asymptotic expansion for the
coefficients of some formal power series, \textit{J. London Math.
Soc.} (2) \textbf{9} (1975), 451--458.
\bibitem{BP} B. Baumslag and S. Pride, Groups with two more generators than relators, \emph{J. London Math. Soc.} \textbf{17} (1978), 425--426.
\bibitem{Brown} K.\,S. Brown, \emph{Cohomology of Groups}, Springer, New York, 1982.
\bibitem{CaMue} P.\,J. Cameron and T.\,W. M\"uller, A descent principle in modular subgroup arithmetic, \textit{J. Pure Appl. Algebra} \textbf{203} (2005), 189--203.
\bibitem{CR} C.\,W. Curtis and I. Reiner, \emph{Representation Theory of Finite Groups and Associative Algebras}, John Wiley \& Sons, New York, 1962.
\bibitem{CR1} C.\,W. Curtis and I. Reiner, \textit{Methods of Representation Theory}, Vol.~I, John Wiley \& Sons, New York, 1981.
\bibitem{Davenport} H. Davenport, \textit{The Higher Arithmetic}, sixth edition, Cambridge University Press, 1992.
\bibitem{Diaconis} P. Diaconis, {\em Group Representations in Probability and Statistics}, IMS Lecture Notes Vol. 11, Hayward, California, 1988.
\bibitem{DS} P. Diaconis and M. Shahshahani, Generating a random permutation with random transpositions, \textit{Z.
Wahrscheinlichkeitstheorie u. Verw. Gebiete} \textbf{57} (1981), 159--179.
\bibitem{FL} S.\,V. Fomin and N. Lulov, On the number of
rim hook tableaux, \textit{J. Math. Sciences} \textbf{87}
(1997), 4118--4123.
\bibitem{Gauss} C.\,F. Gau{\ss},
\textit{Disquisitiones Arithmeticae} (Lipsia in commissis apud Gerh.
Fleischer Iun), 1801; English translation by A. Clarke (Springer, New
York), 1986.
\bibitem{MHall} M. Hall, Subgroups of finite index in
free groups, \textit{Canad. J. Math.} \textbf{1} (1949), 187--190.
\bibitem{HW} G.\,H. Hardy and E.\,M. Wright, \textit{An Introduction to the Theory of Numbers}, Oxford University Press, reprint of the fifth edition, 1989.
\bibitem{Hecke} E. Hecke, \textit{Vorlesungen \"uber die
Theorie der Algebraischen Zahlen}, Academische Verlagsgesellschaft, Leipzig, 1923; reprinted (Chelsea Publishing Company, New York), 1970. English translation by G. Bauer and J. Goldman with R. Kotzen as \textit{Lectures on the Theory of Algebraic Numbers}
(Springer, New York), 1981.
\bibitem{Huppert} B. Huppert, \textit{Endliche Gruppen},
vol.~1, Springer, Heidelberg, 1979.
\bibitem{Ito} N. Ito, On the degrees of irreducible
representations of a finite group,
\textit{Nagoya Math. J.} \textbf{3} (1951), 5--6.
\bibitem{Kerber} A. Kerber, \textit{Algebraic
Combinatorics via Finite Group Actions}, BI-Wissenschaften,
Mannheim, 1991.
\bibitem{Knopp} M. Knopp, \textit{Modular Functions in
Analytic Number Theory}, Markham, Chicago, 1970.
\bibitem{Kraetzel} E. Kr\"atzel, \textit{Zahlentheorie},
VEB Deutscher Verlag der Wissenschaften, Berlin, 1981.
\bibitem{Legendre} A.-M. Legendre, \textit{Essai sur la
Th\'eorie des Nombres}, Paris, 1798. Fourth edition as
\textit{Th\'eorie des Nombres}, 1830; reprinted
(Albert Blanchard, Paris), 1955.
\bibitem{Lyndon} R.\,C. Lyndon, Two notes on Rankin's book
on the modular group, \textit{J. Austral. Math. Soc.}
\textbf{16} (1973), 454--457.
\bibitem{LS} R.\,C. Lyndon and P.\,E. Schupp, \emph{Combinatorial Group Theory}, Springer, Berlin/Heidelberg, 1977.
\bibitem{Magnus} W. Magnus, \emph{Noneuclidean Tesselations and Their Groups}, Academic Press, New York, 1974,
\bibitem{MuInvent} T. M\"uller, Subgroup growth of free
products, \textit{Invent. math.} \textbf{126} (1996), 111--131.
\bibitem{MuComb} T. M\"uller, Finite group actions and asymptotic
expansion of $e^{P(z)}$, \textit{Combinatorica} \textbf{17}
(1997), 523--554.
\bibitem{MuRepres} T. M\"uller, Enumerating representations
in finite wreath products, \textit{Adv. in Math.} \textbf{153} (2000), 118--153.
\bibitem{MuBLMS} T.\,W. M\"uller, Modular subgroup arithmetic
and a theorem of Philip Hall, \textit{Bull. London Math. Soc.} \textbf{34} (2002), 587--598.
\bibitem{MSAFP} T.\,W. M\"uller, Modular subgroup arithmetic
in free products, \textit{Forum Math.} \textbf{15} (2003),
759--810.
\bibitem{MuParheck} T.\,W. M\"uller, Parity patterns in
Hecke groups and Fermat primes. In: Proceedings 1999 Bielefeld conference `Groups: Topological, Combinatorial and  Arithmetic Aspects' (T.\,W. M\"uller ed.). LMS Lecture Notes Series 311, Cambridge University Press, Cambridge, 2004, 327--374.
\bibitem{MP1} T.\,W. M\"uller and J.-C. Puchta,
Character Theory of symmetric groups and subgroup growth of surface
groups, \textit{J. London Math. Soc.} (2) \textbf{66} (2002),
1--18.
\bibitem{MP2} T.\,W. M\"uller and J.-C. Puchta, Parity
patterns in one-relator groups, \textit{J. Group Theory}
\textbf{6} (2003), 245--260.
\bibitem{IsoDis} T.\,W. M\"uller and J.-C. Schlage--Puchta, Classification and statistics of finite index subgroups in free products, \textit{Adv. Math.} \textbf{188} (2004), 1--50.
\bibitem{ModpFree} T.\,W. M\"uller and J.-C. Schlage--Puchta, Modular arithmetic of free subgroups, \textit{Forum Math.} \textbf{17} (2005), 375--405.
\bibitem{MPExamples} T.\,W. M\"uller and J.-C. Schlage--Puchta, Some examples in the theory of subgroup growth, \textit{Monatsh. Math.} \textbf{146} (2005), 49--76.
\bibitem{MP3} T.\,W. M\"uller and J.-C. Schlage--Puchta,
Character theory of symmetric groups, subgroup growth of
Fuchsian groups, and random walks, to appear.
\bibitem{IsoDis2} T.\,W. M\"uller and J.-C. Schlage--Puchta, Statistics of isomorphism types in free products, to appear.
\bibitem{MP4} T.\,W. M\"uller and J.-C. Schlage--Puchta,
Decomposition of the conjugacy representation for
symmetric groups and subgroup growth, to appear.
\bibitem{Newman} M. Newman, Asymptotic formulas
related to free products of cyclic groups, \textit{Math. Comp.}
\textbf{30} (1976), 838--846.
\bibitem{Nielsen} J. Nielsen, The commutator group of
the free product of cyclic groups, \textit{Mat. Tidsskr.}
B (1948), 49--56.
\bibitem{NRS} J.-L. Nicolas, I. Ruzsa, and A. S\'ark\"ozy,
On the parity of additive representation functions, \textit{J. Number Theory} \textbf{73} (1998), 292--317.
\bibitem{Ono} K. Ono, On the parity of the partition
function in arithmetic progressions, \textit{J. Reine u.
Angew. Math.} \textbf{472} (1996), 1--15.
\bibitem{Pride} S.\,J. Pride, The concept of largeness in group theory. In: Word Problems II, Amsterdam: North Holland, 1980, 299--335.
\bibitem{ParkinShanks} T. Parkin and D. Shanks, On the distribution of parity in the partition function, \textit{Math. Comp.} \textbf{21} (1967), 466--480.
\bibitem{Roichman} Y. Roichman, Upper bound on the characters of the symmetric groups, \textit{Invent. math.} \textbf{125} (1996), 451--485.
\bibitem{Roichman2} Y. Roichman, Decomposition of the conjugacy representation of the symmetric group, \textit{Israel J. Math.} \textbf{97} (1997), 305--316.
\bibitem{Scharf} T. Scharf, Die Wurzelanzahlfunktion in
symmetrischen Gruppen, \textit{J. Algebra} \textbf{139}
(1991), 446--457.
\bibitem{Stanley2} R. Stanley,
\textit{Enumerative Combinatorics}, Vol. 2, Cambridge
University Press, New York, 1999.
\bibitem{Stothers} W. Stothers, The number of subgroups
of given index in the modular group, \textit{Proc. Royal
Soc. Edinburgh} \textbf{78A} (1977), 105--112.
\bibitem{Subbarao} M. Subbarao, Some remarks on the
partition function, \textit{Amer. Math. Monthly}
\textbf{73} (1966), 851--854.
\bibitem{Wright} E.\,M. Wright, A relationship between
two sequences, \textit{Proc. London Math Soc.} (3)
\textbf{17} (1967), 296--304.
\bibitem{Wright2} E.\,M. Wright, Asymptotic relations between enumerative functions in graph theory, \textit{Proc. London Math. Soc.} \textbf{20} (1970), 558--572.
\end{thebibliography}

\vskip10pt
\small
\sc Thomas W. M\"uller\\
\sc School of Mathematical Sciences\\
\sc Queen Mary \& Westfield College\\
\sc University of London\\
\sc Mile End Road\\
\sc E1\,4NS London\\
\sc United Kingdom
\end{document}
