Séminaire Lotharingien de Combinatoire 56 (2006), Article B56a

CHARACTER THEORY OF SYMMETRIC GROUPS, ANALYSIS OF LONG RELATORS, AND RANDOM WALKS

THOMAS W. MÜLLER

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.

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 [11] covers these and other applications of a similar flavour.

What is needed for these applications is simply the ordinary character theory (over ℂ) 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. [33], [34], [38], and [40]. 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 [45]) 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 [38] can be summarized as follows.

Theorem A. Let ε > 0 and a positive integer q be given, suppose that n is sufficiently large, and let χ be an irreducible character of S_{n}.

(1) We have |χ(c)| ≤ (χ(1))^{1−δ} with

δ = ((1 − 1/(log n))^{−1} \frac{12 log n}{log(n/f)} + 18)^{−1} ,

where c is any conjugacy class of S_{n} with f fixed points.

(2) We have

∑_{π∈S_{n}} ; π^{q}=1|χ(π)| ≤ (χ(1))^{\frac{1}{q} +ε}_{∑_{π∈S_{n}} ; π^{q}=1}1.

(3) Let m_{χ}^{(q)} be the multiplicity of χ in the q-th root number function of S_{n}. Then

m_{χ}^{(q)} ≤ (χ(1))^{1−2/q+ε}.

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.

Theorem B. Let c be a non-trivial conjugacy class in S_{n}. Denote by t_{comb}(c) the least even integer such that t_{c}(c) elements chosen at random from c have, with probability ≥ 1 − \frac{1}{n}, no common fixed point, and let t_{stat}(c) be the mixing time for the random walk generated by c (see the beginning of Section 5 for notions left undefined here). Then, for n ≥ 4000, we have

t_{comb}(c) ≤ t_{stat}(c) ≤ 10t_{comb}(c).

Theorem B establishes in full generality a conjecture of Roichman; cf. [47, Conj. 6.6]. For special choices of c, Roichman’s conjecture had already been known to hold: Diaconis and Shahshahani [12] established it for transpositions, Roichman [47] generalized their result to conjugacy classes having at least cn fixed points, where c is some positive constant, and Fomin and Lulov [13] 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 Γ of the form

Γ = ⟨x_{1}, …, x_{r}, y_{1}, …, y_{s}, u_{1}, v_{1}, …, u_{t}, v_{t} |

x_{1}^{a_{1}} = ⋯ = x_{r}^{a_{r}} = x_{1} ⋯ x_{r}y_{1}^{e_{1}} ⋯ y_{s}^{e_{s}}[u_{1}, v_{1}] ⋯ [u_{t}, v_{t}] = 1⟩ (1)

with integers r, s, t ≥ 0 and e_{1}, …, e_{s} ≥ 2, and a_{1}, …, a_{r} ∈ ℕ ∪ {∞}. (Γ is a Fuchsian group in the most general sense met in the literature; cf., for instance, [25, Prop. 5.3] or [26, Sec: II.7]).

Theorem C. Let Γ be a Fuchsian group such that

α(Γ) := ∑_{i} (1 − \frac{1}{a_{i}} ) + ∑_{j} \frac{2}{e_{j}} + 2(t − 1) > 0,

and let

μ(Γ) = ∑_{i} (1 − \frac{1}{a_{i}} ) + s + 2(t − 1)

be the hyperbolic measure of Γ. Then the number s_{n}(Γ) of index n subgroups in Γ satisfies an asymptotic expansion

s_{n}(Γ) ≈ δL_{Γ}(n!)^{μ(Γ)}Φ_{Γ}(n){1 + ∑_{ν=1}^{∞} a_{ν}(Γ)n^{−ν/m_{Γ}}}, (n → ∞).

Here,

δ = \begin{cases}2, & ∀i : a_{i} finite and odd, ∀j : e_{j} even \\ 1, & otherwise, \end{cases}

L_{Γ} = (2π)^{−1/2−∑_{i}(1−1/a_{i})}(a_{1} ⋯ a_{r})^{−1/2} exp (− ∑_{i_{2|a_{i}}} \frac{1}{2a_{i}} ) ,

Φ_{Γ}(n) = n^{3/2−∑_{i}(1−1/a_{i})} exp (∑_{i=1}^{r} ∑_{t|a_{i}_{t<a_{i}}} \frac{n^{t/a_{i}}}{t} ) ,

m_{Γ} = [a_{1}, a_{2}, …, a_{r}],

and the a_{ν}(Γ) are explicitly computable constants depending only on Γ.

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:

Can a (non-degenerate) Fuchsian group have infinitely many Fuchsian presentations (i.e., presentations of the form (1) above)?

While it is not hard to give examples of Fuchsian groups of positive hyperbolic measure allowing for more than one presentation of the form (1), we are able to show that such a group has at most finitely many such presentations; cf. [38, Theorem 7] and Theorem 7 in Section 3 below.

A rather different note is struck by the earlier paper [34]; 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 φ the bijection between the self-conjugate partitions of n and the partitions of n into distinct odd parts, mapping a self-conjugate partition λ onto the partition given by the symmetric main hooks of λ. Moreover, denote by c_{λ} the conjugacy class of S_{n} whose cycle structure is given by the partition λ ⊢ n, and by χ_{λ} the irreducible character of S_{n} corresponding to the Specht module S^{λ}. Finally, call an irreducible character χ of S_{n} symmetric, if χ = ϵ_{n}χ, where ϵ_{n} = χ_{(1^{n})} is the sign character. (This is equivalent to demanding that the partition associated with χ be self-conjugate). Then the first part of [34] establishes the following.

Theorem D. (a) Let λ_{1} and λ_{2} be partitions of n with λ_{1} self-conjugate. Then χ_{λ_{1}}(c_{λ_{2}}) is odd if, and only if, λ_{2} = φ(λ_{1}).

(b) Let χ and χ′ be irreducible characters of S_{n}. If both χ and χ′ are symmetric, then the multiplicity ⟨χ^{2}|χ′⟩ of χ′ in χ^{2} is odd if, and only if, χ = χ′.

After introducing a certain rather substantial class W of relators, including in particular all surface relators

∏_{1≤j≤g}[x_{2j−1}, x_{2j}] and ∏_{1≤j≤h} x_{j}^{2},

the second part of [34], building on Theorem D as well as detailed information concerning the representation numbers of binary quadratic forms, establishes the following surprising and beautiful result.

Theorem E. If w is in 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 ≥ 1.

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 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 [40].

Our article is organized as follows. In Section 1, 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 2, we explain our character-theoretic approach to the subgroup growth of surface groups, originally developed in [33]. 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 ∑_{λ⊢n} χ_{λ}(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 3. 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 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éminaire 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.

1. Counting subgroups of finite index in large groups

For a finitely generated group Γ, denote by s_{n}(Γ) the number of index n subgroups of Γ. 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 {s_{n}(Γ)}_{n≥1} or related subgroup counting functions and their connection with the algebraic structure of the underlying group Γ. Here, we shall be concerned exclusively with large groups: a group is termed large (in the sense of Pride [45]), if it contains a subgroup of finite index which projects homomorphically onto a non-abelian free group. Clearly, for such a group, s_{n}(Γ) 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}(Γ) necessarily has smooth growth; in particular there need not exist an asymptotic formula for this function.^{1}

As a first example, let us consider Marshall Hall’s recurrence relation

s_{n}(F_{r}) = n(n!)^{r−1} − ∑_{ν=1}^{n−1} ((n − ν)!)^{r−1} s_{ν}(F_{r})  (2)

for the subgroup numbers of a free group G = F_{r} of rank r; cf. [15]. It is immediate from this relation that, for r ≥ 1 and n ≥ 2,

s_{n}(F_{r}) ≡ s_{n−1}(F_{r}) mod 2,

hence 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 (2) an asymptotic formula for the subgroup numbers of a non-abelian free group. Indeed, observe from (2) that

s_{n}(F_{r}) ≤ n(n!)^{r−1}, n ≥ 1.  (3)

Assuming r ≥ 2, and dividing (2) throughout by n(n!)^{r−1}, we then see that

\frac{s_{n}(F_{r})}{n(n!)^{r−1}} = 1 − ϵ(n, r),

1Cf. [37, Section 7] for an example in this direction.

where

ϵ(n, r) := ∑_{ν=1}^{n−1} ((n − ν)!)^{r−1} s_{ν}(F_{r}) / (n(n!)^{r−1})

≤ ∑_{ν=1}^{n−1} \frac{ν}{n} \binom{n}{ν}^{−(r−1)}

≤ n^{−r} + \frac{n − 1}{n^{r}} + ∑_{ν=2}^{n−2} \binom{n}{ν}^{−(r−1)}

= n^{−r} + \frac{n − 1}{n^{r}} + O_{r}(n^{−2r+3})

= O_{r}(n^{−1}),

so

s_{n}(F_{r}) ∼ n(n!)^{r−1} (n → ∞), r ≥ 2.

This is [41, Theorem 3]. Note that 1 − r = χ(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 −χ(F_{r}). Non-abelian free groups and, more generally, finitely generated virtually free groups, i.e., fundamental groups Γ = π_{1}(G(−), Y) of finite graphs of finite groups (in the sense of Bass and Serre), with χ(Γ) < 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

Γ = PSL_{2}(ℤ) ≅ C_{2} ∗ C_{3}.

Here the corresponding results concerning parity and asymptotics are already quite non-trivial.

Proposition 1 [Stothers [51], 1977]. Let Γ = PSL_{2}(ℤ) be the modular group. Then

s_{n}(Γ) ≡ 1 mod 2 ⟺ n = 2^{α} − 3 or n = 2(2^{α} − 3) for some α ≥ 1.

Proposition 2 [Newman [41], 1976]. For Γ = PSL_{2}(ℤ),

s_{n}(Γ) ∼ (12πe^{1/2})^{−1/2} n^{n/6} exp ( − \frac{n}{6} + n^{1/2} + n^{1/3} + \frac{1}{2} log n).

Note that, apart from correction terms coming from the torsion in the group, the right-hand side of the last formula looks like (n!)^{−χ(Γ)}, where χ(Γ) = −\frac{1}{6} is the Euler characteristic (in the sense of Wall) of the modular group; cf. [6, Chapter IX]. 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

Γ = PSL_{2}(ℤ) → C_{2} × C_{3} ≅ C_{6}

is free of rank 2 (Nielsen [42], see also Lyndon [24]); 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.

Theorem 1 [Müller [31], 2003]. Let q ≥ 3 be an integer. Then q is a Fermat prime if, and only if,

s_{n}(C_{2} ∗ C_{q}) ≡ 1 mod 2 ⟺ n = \frac{2(q − 1)^{α} − q}{q − 2}

or n = 2(\frac{2(q − 1)^{α} − q}{q − 2} ) for some α ≥ 1.

Theorem 2 [Müller [27], 1996]. Let Γ = G_{1} ∗ ⋯ ∗ G_{s} ∗ F_{r} be a free product with finite groups G_{i}, m_{i} = |G_{i}|, and suppose that χ(Γ) < 0. Then

s_{n}(Γ) ∼ L_{Γ} Φ_{Γ}(n) (n → ∞),

where

L_{Γ} := (2π)^{\frac{r−1}{2}} (m_{1} ⋯ m_{s})^{−1/2} exp ( −_{∑_{i} ; 2|m_{i}} \frac{(s_{G_{i}}(m_{i}/2))^{2}}{2m_{i}} )

and

Φ_{Γ}(n) := n^{−χ(Γ)n} exp (χ(Γ)n + ∑_{i=1}^{s} _{∑_{d_{i}|m_{i}} ; d_{i}<m_{i}} \frac{s_{G_{i}}(d_{i})}{d_{i}} n^{d_{i}/m_{i}} + \frac{r + 1}{2} log n).

As is well known, Fermat primes, that is, prime numbers of the form 2^{2^{λ}} +1 with λ ≥ 0, satisfy (or can even be characterized by) a number of curious regularity conditions; for instance, according to Gauß,^{2} 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 ≥ 3, through the arithmetic of the associated (standard) Hecke group ℌ(q) ≅ C_{2} ∗ 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. [7], [30], [31], [32], and [36].

The second result gives an estimate for the subgroup growth of free products Γ of the form

Γ = G_{1} ∗ ⋯ ∗ G_{s} ∗ F_{r} (m_{i} = |G_{i}| < ∞, χ(Γ) < 0)  (4)

in terms of the local data m_{i} and s_{G_{i}}(d_{i}) for d_{i} | m_{i}. In fact, a full asymptotic expansion is known for s_{Γ}(n) in this case, of which L_{Γ}Φ_{Γ}(n) is the main term; cf. [27, Theorem 1].

It appears that for virtually free groups Γ of more complicated structure (for instance, amalgamated products or HNN extensions) global invariants like χ(Γ) do not suffice to control the asymptotics of s_{n}(Γ) (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.^{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 ≀ S_{n} with a finite group H) enter our picture in an essential way.

2Disquisitiones arithmeticae [14], §366.

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

∑_{n≥0} \frac{| Hom(Γ, S_{n})|}{n!} z^{n} = exp ( ∑_{n≥1} \frac{s_{n}(Γ)}{n} z^{n})  (5)

or, more generally, the equation

∑_{n≥0} \frac{| Hom(Γ, H ≀ S_{n})|}{n!} z^{n} = exp ( ∑_{n≥1} \frac{|H|^{n−1}s_{n}(Γ, H)}{n} z^{n}),  (6)

where

s_{n}(Γ, H) := ∑_{(Γ:Δ)=n} | Hom(Δ, H)| (H a finite group).

We briefly sketch the proof of (5):^{4} classify the Γ-actions on the standard n-set

[n] := {1, 2, …, n}

by the orbit ω_{0} of the point 1. This orbit ω_{0} may have any size k between 1 and n, and the Γ-action on ω_{0} is transitive, while the action of Γ on [n] \ ω_{0} is arbitrary. Moreover, the transitive actions of Γ on [n], modulo the (free) action of the stabilizer stab_{Γ}(1), are in one-to-one correspondence with the subgroups of index n in Γ. There are \binom{n−1}{k−1} ways of choosing the elements of ω_{0}; and, on each such k-set, Γ has (k − 1)!s_{k}(Γ) transitive actions, hence

| Hom(Γ, S_{n})| = ∑_{1≤k≤n} \binom{n − 1}{k − 1}(k − 1)!s_{k}(Γ)| Hom(Γ, S_{n−k})|,  (7)

from which (5) follows. Note also that Marshall Hall’s relation (2) is a special case of (7).

For a large group Γ, a function like | Hom(Γ, S_{n})| tends to be more approachable than s_{n}(Γ) itself, and there is machinery in place (see, for instance, Bender [4] and Wright [53], [54]) to transfer, say, asymptotic information from one side of the relations (5), (6) to the other. Henceforth, for the purposes of this survey, the problem of analyzing s_{n}(Γ), the number of index n subgroups in Γ, will be identified with that of investigating the function | Hom(Γ, S_{n})|. No further mention will be made here of the more complicated case of monomial representations, apart from remarking that Formula (6), or rather the techniques underlying its proof, play a key role in the solution of the Poincaré-Klein Problem, one of the most important long-standing problems in pure mathematics; cf.

3By a result of Baumslag and Pride, a one-relator group having 3 or more generators is large; cf.

[5]. The situation for Fuchsian groups is more involved, compare Theorem 4 in Section 3.

4Cf. [29] for the proof of (6), which is considerably more demanding.

[35] and [39].

Let us quickly come back to Theorem 2. For Γ as in (4), the function | Hom(Γ, S_{n})| decomposes as

| Hom(Γ, S_{n})| = (n!)^{r} ∏_{i=1}^{s} | Hom(G_{i}, S_{n})|.

Thus, if we want to understand the asymptotics of s_{n}(Γ) 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 finite group. In this situation, the transformation formula (5) yields

∑_{n=0}^{∞} \frac{| Hom(G, S_{n})|}{n!} z^{n} = exp ( ∑_{d|m} \frac{s_{d}(G)}{d} z^{d}), 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

{e^{P (z)} : P (z) ∈ ℝ[z]}

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 [28], among other things, the following is proved.

Theorem 3 [Müller [28], 1997]. Let P (z) = ∑_{μ=1}^{m} c_{μ}z^{μ} be a polynomial of degree m ≥ 1 with real coefficients c_{μ}. Set exp(P (z)) = ∑_{n=0}^{∞} α_{n}z^{n}, and assume that (i) α_{n} > 0 for sufficiently large n, and that (ii) c_{μ} = 0 for m/2 < μ < m. Then we have the asymptotic formula

α_{n} ∼ \frac{K}{\sqrt{2πn}} (\frac{n}{mc_{m}} )^{−n/m} exp (P ((\frac{n}{mc_{m}} )^{1/m})),  (8)

where

K = K(P) = \begin{cases}m^{−1/2}, & m odd \\ m^{−1/2} exp ( − \frac{c_{m/2}^{2}}{8c_{m}} ), & m even \end{cases} .

Theorem 3, in conjunction with [53, Theorem 3] or Bender’s method [4], suffices in order to establish Theorem 2. Under more stringent conditions, we also obtain in [28] a full asymptotic expansion for α_{n} refining (8). 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.

2. Subgroup growth of surface groups

For elements x, y in a group Γ, we denote by

[x, y] = x^{−1}y^{−1}xy

the commutator of x and y. Let Γ be the fundamental group of a closed 2-manifold, that is, Γ equals

Γ_{g}^{+} = ⟨x_{1}, y_{1}, …, x_{g}, y_{g} | [x_{1}, y_{1}] ⋯ [x_{g}, y_{g}] = 1⟩

or

Γ_{h}^{−} = ⟨x_{1}, …, x_{h} | x_{1}^{2} ⋯ x_{h}^{2} = 1⟩,

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.,

Γ_{g}^{+} large ⟺ g ≥ 2, Γ_{h}^{−} large ⟺ h ≥ 3.

The exceptional cases

Γ_{1}^{+} ≅ ℤ^{2}, Γ_{1}^{−} ≅ C_{2}, Γ_{2}^{−} ≅ ℤ ∗_{2ℤ} ℤ

are well understood; it is known that^{5}

s_{n}(Γ_{2}^{−}) = s_{n}(Γ_{1}^{+}) = σ_{1}(n) := ∑_{d|n} d,

and, by a result of Gronwall,^{6} σ_{1}(n) has maximal order e^{γ}n log log n, where γ 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}(Γ_{g}^{+}) for g ≥ 2, we have to control the function

| Hom(Γ_{g}^{+}, S_{n})| = |{(x_{1}, y_{1}, …, x_{g}, y_{g}) ∈ S_{n}^{2g} : [x_{1}, y_{1}] ⋯ [x_{g}, y_{g}] = 1}|,

or, on a slightly more general level, the function

N_{g}^{+}(G, z) := |{(x_{1}, y_{1}, …, x_{g}, y_{g}) ∈ G^{2g} : [x_{1}, y_{1}] ⋯ [x_{g}, y_{g}] = z}|,

where G is a finite group, and z ∈ G. As a first step, consider the function

N_{1}^{+}(G, z) =: N^{G}(z) = |{(x, y) ∈ G × G : [x, y] = z}|.

As is well known, the number of solutions of the equation x · 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:

|\{(x, y) ∈ G × G : x · y = z, x ∈ c_{1}, y ∈ c_{2}\}| = \frac{|c_{1}| · |c_{2}|}{|G|} ∑_{χ} \frac{χ(c_{1})χ(c_{2})χ(z^{−1})}{χ(1)}, (9)

where χ runs through the ordinary irreducible characters of G; cf., for instance, [9, Proposition 9.33] or [20, Theorem 6.3.1]. Since [x, y] = x^{−1} · 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 c by first solving the equation x̄ · x̄′ = z with x̄ ∈ c^{−1} and x̄′ ∈ c, and then choosing y ∈ G in

|C_{G}(x)| = |G|/|c|

5Cf., for instance, [33, Section 4.2].

6Trans. Amer. Math. Soc. 14 (1913), see also [16, Theorem 323].

ways to write a given x̄′ as x̄′ = x^{y} with x = x̄^{−1}. Applying (9) and noting that |c| = |c^{−1}|, we see that

|{(x, y) ∈ G × G : [x, y] = z, x ∈ c}| = |{(x̄, x̄′) ∈ G × G : x̄ · x̄′ = z, x̄ ∈ c^{−1}, x̄′ ∈ c}|
× |C_{G}(x)|

= \frac{|G|}{|c|} \frac{|c|^{2}}{|G|} ∑_{χ} χ(c^{−1})χ(c)χ(z^{−1})/χ(1)

= |c| ∑_{χ} χ(c^{−1})χ(c)χ(z^{−1})/χ(1).

Summing over the conjugacy classes gives

N^{G}(z) = ∑_{c} |c| ∑_{χ} χ(c^{−1})χ(c)χ(z^{−1})/χ(1).

Interchanging summations, and using the fact that characters are class functions plus their orthogonality, we find that

N^{G}(z) = ∑_{χ} \frac{χ(z^{−1})}{χ(1)} ∑_{c} |c| χ(c^{−1}) χ(c)

= ∑_{χ} \frac{χ(z^{−1})}{χ(1)} ∑_{x∈G} χ(x^{−1})χ(x)

= ∑_{χ} \frac{χ(z^{−1})}{χ(1)} |G| ⟨χ | χ⟩

= |G| ∑_{χ} χ(z^{−1})/χ(1).

Conjugating the resulting equation

N^{G}(z) = |G| ∑_{χ} χ(z^{−1})/χ(1)

yields the formula

N^{G}(z) = |G| ∑_{χ} χ(z)/χ(1).  (10)

We can now establish the character formula

N_{g}^{+}(G, z) = |G|^{2g−1} ∑_{χ} χ(z)/(χ(1))^{2g−1}  (11)

by induction on g. If g = 1, then (11) holds in virtue of (10). Suppose that (11) holds for some g ≥ 1. Then

N_{g+1}^{+}(G, z) = ∑_{x∈G} N_{g}^{+}(G, x) N^{G}(x^{−1}z)

= |G|^{2g} ∑_{x∈G} [ ∑_{χ} χ(x)/(χ(1))^{2g−1}][ ∑_{χ} χ(x^{−1}z)/χ(1)]

= |G|^{2g} ∑_{χ_{1},χ_{2}}(χ_{1}(1))^{−(2g−1)}(χ_{2}(1))^{−1} ∑_{x∈G} χ_{1}(x)χ_{2}(x^{−1}z)

= |G|^{2g+1} ∑_{χ} χ(z)/(χ(1))^{2g+1}.

In the last step, we have used the generalized orthogonality relation

∑_{x∈G} χ_{1}(x)χ_{2}((ax)^{−1}) = |G| χ_{1}(a^{−1}) ⟨χ_{1} | χ_{2}⟩/χ_{1}(1)

with a = z^{−1} (cf. [8, Formula 31.16]) together with orthogonality of characters. In a similar way, one shows that

N_{h}^{−}(G, z) := |{(x_{1}, …, x_{h}) ∈ G^{h} : x_{1}^{2} ⋯ x_{h}^{2} = z}|
= |G|^{h−1} ∑_{χ} c_{χ}^{h}(G)χ(z)/(χ(1))^{h−1},  (12)

where the c_{χ}(G) are given by the expansion

R^{G}(z) := |{x ∈ G : x^{2} = z}| = ∑_{χ} c_{χ}(G)χ(z), z ∈ G.  (13)

In general, R^{G} need not be a proper character; it is a virtual character of G, and the (integral) coefficients c_{χ}(G) in the Fourier decomposition (13) satisfy |c_{χ}(G)| ≤ 1 and are non-zero if, and only if, the corresponding character χ is real-valued. It is known that R^{S_{n}} is in fact the model character of S_{n}, that is,

R^{S_{n}}(z) = ∑_{λ⊢n} χ_{λ}(z), z ∈ S_{n}.  (14)

The higher root number functions of S_{n} have more recently also been shown to be proper characters; cf. Scharf [49]. An alternative proof of Scharf’s result using symmetric function theory is outlined in the solution to [50, Exercise 7.69 c]. A good account of all the facts on root number functions mentioned is found in [20, Chapter 6.2].

Setting G = S_{n} and z = 1 in (11) and (12), and using (14), we obtain the equation

| Hom(Γ_{d}, S_{n})| = (n!)^{d−1}Φ_{d−2}(n), d ≥ 1,  (15)

which summarizes the essence of our discussion so far. Here, Γ_{d} is a surface group (orientable or not) of rank d,^{7} and, for fixed real s,

Φ_{s}(n) := ∑_{λ⊢n} (χ_{λ}(1))^{−s}.

It is clear from Equation (15), that information on the asymptotics of s_{n}(Γ_{d}) with d ≥ 3 will flow from a sufficiently precise estimate of the character sum Φ_{s}(n) for s > 0 as n → ∞. Such an estimate is given by our next result.

Proposition 3 [Müller/Puchta [33], Theorem 1]. For fixed s > 0, we have the asymptotic expansion

Φ_{s}(n) ≈ 2 ∑_{ρ≥0} A_{ρ}(s) n^{−ρ} (n → ∞).

Here, the coefficients A_{ρ}(s) are given by

A_{ρ}(s) = ∑_{r≥0} ∑_{μ⊢r} H[μ]^{s} ∑_{(κ_{ν})} ∏_{ν∈N(μ,r)} [\binom{s + κ_{ν} − 1}{κ_{ν}}(2r − ν)^{κ_{ν}}], ρ ≥ 0,

where H[μ] is the hook product of μ,

N(μ, r) := [2r] − {j + ∑_{i=0}^{j−1} m_{r−i}(μ) : 1 ≤ j ≤ r},

with m_{j}(μ) the multiplicity of j in the partition μ of r, and ∑_{(κ_{ν})} denoting the sum over the family of discrete variables

{κ_{ν} : ν ∈ N(μ, r)}

satisfying κ_{ν} ≥ 0 for ν ∈ N(μ, r) and ∑_{ν} κ_{ν} = ρ − rs.

Observing that, for 1 ≤ ρ < s and every r ≥ 0, the summation over the κ_{ν} in the definition of the A_{ρ}(s) is empty, while A_{0}(s) = 1, we obtain the following estimate, which will be used in Section 5.

Corollary 1. For fixed s > 0, we have

Φ_{s}(n) = 2 + O(n^{−s}), n → ∞.

Combining Proposition 3 with Bender’s method [4] finally yields the following.

Proposition 4 [Müller/Puchta [33], Theorem 2]. For d ≥ 3, the function s_{n}(Γ_{d}) satisfies the asymptotic expansion

s_{n}(Γ_{d}) ≈ 2n(n!)^{d−2}{1 + ∑_{ν≥1} C_{ν}(d)n^{−ν}} (n → ∞),

7The rank of a finitely generated group is, by definition, the minimal number of generators for this group.

where, for ν ≥ 1,

C_{ν}(d) = ∑_{k=1}^{⌊ \frac{ν}{d−2} ⌋} ∑_{η_{1}+···+η_{k−1}+η+ρ+k(d−2)=ν} 𝔠_{k}(d) k^{η} \binom{η + ρ − 1}{η} A_{ρ}(d − 2)

× ∏_{i=1}^{k−1} [i^{η_{i}} \binom{d + η_{i} − 3}{η_{i}}],

and

𝔠_{k}(d) = ⟨( ∑_{n≥0} (n!)^{d−2} Φ_{d−2}(n) z^{n})^{−1} | z^{k}⟩.

3. Subgroup growth of Fuchsian groups

By a Fuchsian group we shall mean a group Γ having a presentation of the form^{8}

Γ = ⟨x_{1}, …, x_{r}, y_{1}, …, y_{s}, u_{1}, v_{1}, …, u_{t}, v_{t} |

x_{1} ⋯ x_{r} y_{1}^{e_{1}} ⋯ y_{s}^{e_{s}} [u_{1}, v_{1}] ⋯ [u_{t}, v_{t}] = x_{1}^{a_{1}} = x_{2}^{a_{2}} = ⋯ = x_{r}^{a_{r}} = 1⟩, (16)

where r, s, t are non-negative integers, e_{1}, …, e_{s} are integers ≥ 2, and a_{1}, …, a_{r} ∈ ℕ ∪ {∞}. If, for instance, r = s = 0, then Γ = Γ_{t}^{+}, while for r = t = 0 and e_{1} = ⋯ = e_{s} = 2 we have Γ = Γ_{s}^{−}. Another prominent class of examples are the (orientation preserving) hyperbolic triangle groups

Δ(p, q, r) = ⟨x, y, z | x^{p} = y^{q} = z^{r} = xyz = 1⟩

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 (16), we define the hyperbolic measure μ(Γ) of Γ via

μ(Γ) := ∑_{i} (1 − \frac{1}{a_{i}} ) + s + 2(t − 1).

It can be shown that the hyperbolic measure is in fact an invariant of Γ, that is, independent of the Fuchsian presentation chosen for Γ, and one would expect μ(Γ) to play a role similiar to that played by the rational Euler characteristic χ(Γ) in the case of virtually free groups. We shall also need another invariant, first introduced in [38], which yields a rough measure for the size of the Fuchsian group Γ:

8Γ is a Fuchsian group in the most general sense met in the literature; cf., for instance, [25, Prop. 5.3] or [26, Sec. II.7].

α(Γ) := ∑_{i} (1 − \frac{1}{a_{i}} ) + ∑_{j} \frac{2}{e_{j}} + 2(t − 1)

= μ(Γ) − ∑_{j} (1 − \frac{2}{e_{j}} ).

Finally, we set m_{Γ} := [a_{1}, a_{2}, …, a_{r}]. The main result of this section provides an asymptotic estimate for the subgroup growth of large Fuchsian groups.

Theorem 4 [Müller/Schlage–Puchta [38, Theorem 3], 2002]. Let Γ be as in (16), and suppose that α(Γ) > 0. Then the number of index n subgroups in Γ satisfies an asymptotic expansion

s_{n}(Γ) ≈ δL̂_{Γ}(n!)^{μ(Γ)}Φ̂_{Γ}(n){1 + ∑_{ν≥1} a_{ν}(Γ)n^{−ν/m_{Γ}}}, n → ∞.  (17)

Here,

δ = \begin{cases}2, & ∀i : a_{i} finite and odd, ∀j : e_{j} even \\ 1, & otherwise, \end{cases}

L̂_{Γ} = (2π)^{−1/2−∑_{i}(1−1/a_{i})}( ∏_{a_{i}≠∞} a_{i})^{−1/2} exp ( − ∑_{2|a_{i}} \frac{1}{2a_{i}} ),

Φ̂_{Γ}(n) = n^{3/2−∑_{i}(1−1/a_{i})} exp ( ∑_{i}_{∑_{d|a_{i}} ; d<a_{i}} \frac{n^{d/a_{i}}}{d} ),

and the a_{ν}(Γ) are explicitly computable constants depending only on Γ.^{9}

As in the case of Proposition 4, the proof of Theorem 4 begins by establishing a character formula for the function | Hom(Γ, S_{n})| counting the permutation representations of Γ 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(Γ, 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.)

Proposition 5 [38, Formula (38)]. For Γ as in (16), we have

| Hom(Γ, S_{n})| = (n!)^{s+2t−1} ∏_{i=1}^{r} | Hom(C_{a_{i}}, S_{n})| ∑_{λ⊢n} \frac{∏_{i=1}^{r} α_{χ_{λ}}^{(a_{i})} ∏_{j=1}^{s} m_{χ_{λ}}^{(e_{j})}}{(χ_{λ}(1))^{r+s+2t−2}} ,  (18)

where, for q ∈ ℕ ∪ {∞} and an irreducible character χ,

α_{χ}^{(q)} = \frac{1}{| Hom(C_{q}, S_{n})|} ∑_{π^{q}=1} χ(π),

9See [38, Sec. 5.2] for details concerning the computation of the coefficients a_{ν}(Γ).

and m_{χ}^{(q)} = ⟨R_{q}^{S_{n}} | χ⟩ is the Fourier coefficient of χ in the expansion of the q-th root number function

R_{q}^{S_{n}}(π) = |{σ ∈ S_{n} : σ^{q} = π}|

of S_{n}.

Proof. Let w be a segment of

R = x_{1}x_{2} ⋯ x_{r}y_{1}^{e_{1}}y_{2}^{e_{2}} ⋯ y_{s}^{e_{s}}[u_{1}, v_{1}][u_{2}, v_{2}] ⋯ [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 π ∈ S_{n}, define N_{w}(π) to be the number of solutions of the equation w = π, subject to the conditions x_{i}^{a_{i}} = 1 for those i for which x_{i} occurs in w. Observing that N_{w}(π) is a class function, define coefficients β_{χ}^{(w)} via the Fourier expansion

N_{w}(π) = (n!)^{−1} ∏_{x_{i}∈w} | Hom(C_{a_{i}}, S_{n})| ∑_{χ∈Irr(S_{n})} β_{χ}^{(w)}χ(π).

We claim that

β_{χ}^{(w)} = (n!)^{|{j: y_{j}∈w}|+2|{k: u_{k}∈w}|} ∏_{x_{i}∈w} α_{χ}^{(a_{i})} ∏_{y_{j}∈w} m_{χ}^{(e_{j})}/(χ(1))^{ℓ(w)−1},  (19)

where ℓ(w) is the number of different generators x_{i}, y_{j}, u_{k}, v_{k} occurring in w. The proof of (19) 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 β_{χ}^{(y_{1}^{e_{1}})} = n! m_{χ}^{(e_{1})} respectively β_{χ}^{([u_{1},v_{1}])} = (n!)^{2}/χ(1) by the definition of the multiplicity m_{χ}^{(e_{1})} respectively Formula (10), as predicted by (19). In case (i),

N_{x_{1}}(π) = \begin{cases}1, & π^{a_{1}} = 1 \\ 0, & π^{a_{1}} ≠ 1, \end{cases}

and Equation (19) requires us to verify the identity

\frac{1}{n!} ∑_{χ} ∑_{σ^{a_{1}}=1} χ(σ) χ(π) = \begin{cases}1, & π^{a_{1}} = 1 \\ 0, & π^{a_{1}} ≠ 1, \end{cases}  (20)

which however follows directly from the orthogonality relation^{10}

∑_{χ} χ(c_{1}) \overline{χ(c_{2})} = \frac{|G|}{|c_{1}|} δ_{c_{1},c_{2}}.  (21)

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 ≤ i ≤ r, the other two cases being similar but slightly easier. For w′ = wx_{i}, we have

10Cf. [8, Formula (31.19)].

N_{w′}(π) = ∑_{σ∈S_{n}} N_{w}(σ) × \begin{cases}1, & (σ^{−1}π)^{a_{i}} = 1 \\ 0, & (σ^{−1}π)^{a_{i}} ≠ 1, \end{cases}

= \frac{1}{n!} ∑_{σ} N_{w}(σ) ∑_{χ} ∑_{τ^{a_{i}}=1} χ(τ) χ(σ^{−1}π)

= \frac{1}{n!} ∑_{σ} | Hom(C_{a_{i}}, S_{n})| N_{w}(σ) ∑_{χ} α_{χ}^{(a_{i})} χ(σ^{−1}π)

= \frac{∏_{ν=1}^{i} | Hom(C_{a_{ν}}, S_{n})|}{(n!)^{2}} ∑_{σ} ∑_{χ_{1}} ∑_{χ_{2}} α_{χ_{1}}^{(a_{i})} β_{χ_{2}}^{(w)} χ_{1}(σ^{−1}π) χ_{2}(σ)

= \frac{∏_{ν=1}^{i} | Hom(C_{a_{ν}}, S_{n})|}{n!} ∑_{χ_{1}} ∑_{χ_{2}} α_{χ_{1}}^{(a_{i})} β_{χ_{2}}^{(w)} \frac{χ_{1}(π)}{χ_{1}(1)} δ_{χ_{1},χ_{2}}

= \frac{∏_{ν=1}^{i} | Hom(C_{a_{ν}}, S_{n})|}{n!} ∑_{χ} \frac{α_{χ}^{(a_{i})} β_{χ}^{(w)}}{χ(1)} χ(π);

that is,

β_{χ}^{(w′)} = \frac{α_{χ}^{(a_{i})}}{χ(1)} β_{χ}^{(w)} = \frac{∏_{ν=1}^{i} α_{χ}^{(a_{ν})}}{(χ(1))^{i−1}} ,

in accordance with (19). Here, we have used (20) in step 2, the orthogonality relation^{11}

∑_{x_{1}∈G} χ_{1}(x_{2}x_{1}) \overline{χ_{2}(x_{1})} = \frac{|G| χ_{1}(x_{2})}{χ_{1}(1)} δ_{x_{1},x_{2}}  (22)

in step 5, and the inductive hypothesis in the concluding computation of β_{χ}^{(w′)}.

With (19) in hand, Equation (18) now follows by setting w = R and π = 1. □

It is clear from Formula (18) that, in order to obtain asymptotic information concerning the function | Hom(Γ, S_{n})| for a Fuchsian group Γ, we need an estimate for sums of the form

∑_{π∈S_{n}} ; π^{q}=1 χ(π)

as well as a good upper bound on the multiplicities m_{χ}^{(q)} of root number functions. Our main new results in this direction are as follows.

Theorem 5 [Müller/Schlage–Puchta [38, Propositions 1 and 2(i)], 2002]. Let ε > 0 and a positive integer q be given, and let χ be an irreducible character of S_{n}. Then, for sufficiently large n, (i)

11Cf. [8, Formula (31.16)].

∑_{π∈S_{n}} ; π^{q}=1|χ(π)| ≤ (χ(1))^{\frac{1}{q} +ε} _{∑_{π∈S_{n}} ; π^{q}=1}1,

(ii)

m_{χ}^{(q)} ≤ (χ(1))^{1−2/q+ε}.

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 | Hom(Γ, S_{n})| in the case where α(Γ) > 0, that is, when Γ is large, and Theorem 4 follows from this expansion via Bender’s method [4].

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:

Can a (non-degenerate) Fuchsian group have infinitely many Fuchsian presentations?

Indeed, it is not hard to give examples of Fuchsian groups of positive hyperbolic measure allowing for more than one presentation of the form (16).

Call two finitely generated groups Γ and Δ equivalent, denoted Γ ∼ Δ, if

s_{n}(Γ) = (1 + o(1)) s_{n}(Δ), n → ∞.

In [27, Theorem 3] a characterization in terms of structural invariants is given for the equivalence relation ∼ on the class of groups Γ of the form (4), and it is shown that each ∼-class decomposes into finitely many isomorphism classes. Our next result is concerned with the corresponding problem for Fuchsian groups. Denote by F the class of all groups Γ having a presentation of the form (16) with α(Γ) > 0, and by ≅ isomorphy of groups.

Theorem 6 [Müller/Schlage–Puchta [38, Theorem 6(ii) and Corollary 2], 2002].

(i) Let

Γ = ⟨x_{1}, …, x_{r}, y_{1}, …, y_{s}, u_{1}, v_{1}, …, u_{t}, v_{t} |

x_{1} ⋯ x_{r} y_{1}^{e_{1}} ⋯ y_{s}^{e_{s}} [u_{1}, v_{1}] ⋯ [u_{t}, v_{t}] = x_{1}^{a_{1}} = ⋯ = x_{r}^{a_{r}} = 1⟩

and

Δ = ⟨x_{1}, …, x_{r′}, y_{1}, …, y_{s′}, u_{1}, v_{1}, …, u_{t′}, v_{t′} |

x_{1} ⋯ x_{r′} y_{1}^{e′_{1}} ⋯ y_{s′}^{e′_{s′}} [u_{1}, v_{1}] ⋯ [u_{t′}, v_{t′}] = x_{1}^{a′_{1}} = ⋯ = x_{r′}^{a′_{r′}} = 1⟩ be Fuchsian groups such that α(Γ), α(Δ) > 0. Then we have Γ ∼ Δ if, and only if,

(a) the multisets {a_{i} : 1 ≤ i ≤ r} and {a′_{i} : 1 ≤ i ≤ r′} coincide,

(b) μ(Γ) = μ(Δ),

(c) δ = δ′. (ii) Let Γ be a Fuchsian group as in (16) with α(Γ) > 0. Then the set

{Δ ∈ F : Δ ∼ Γ}/ ≅

is finite if, and only if, one of the following holds:

(a) s = t = 0,

(b) s = 1, t = 0, ∑_{i} (1 − \frac{1}{a_{i}} ) < 2,

(c) s = 2t = 2, r = 1. (iii) Let Γ be as in (ii). Then the set

{Δ ∈ F : Δ ∼ Γ}/ ≅

is infinite, while the set

{Δ ∈ F : s_{n}(Δ) = (1 + O(n^{−2μ(Γ)})) s_{n}(Γ)}/ ≅

is finite if, and only if, the following three conditions are satisfied:

(a) s + 2t + ∑_{i} (1 − \frac{1}{a_{i}} ) ≥ 3,

(b) a_{i} is odd for 1 ≤ i ≤ r,

(c) e_{j} = 2 for 1 ≤ j ≤ 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.

It follows in particular from Theorem 6 that, unlike the situation for free products (4), the asymptotic class of the function s_{n}(Γ) does not in general determine Γ 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}(Γ). It is therefore natural to ask, what happens if we take into account the full precision of (17) in Theorem 4. More specifically, consider three refinements of the equivalence relation ∼: (i) the relation ≈ of strong equivalence defined via

Γ ≈ Δ :⟺ s_{n}(Γ) = s_{n}(Δ)(1 + O(n^{−A})) for every A > 0,

(ii) isomorphy, and (iii) equality of the system of parameters

(r, s, t; a_{1}, a_{2}, …, a_{r}, e_{1}, e_{2}, …, e_{s})

in the Fuchsian presentation (16), denoted Γ = Δ.^{12} Clearly,

Γ = Δ ⟹ Γ ≅ Δ ⟹ Γ ≈ Δ ⟹ Γ ∼ Δ.

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.

Theorem 7 [Müller/Schlage–Puchta [38, Theorem 7], 2002]. Each ≈-equivalence class of FP decomposes into finitely many classes with respect to the relation =; that is, each group Γ ∈ F has only finitely many presentations of the form (16), and is ≈-equivalent to at most finitely many non-isomorphic F-groups.

12Strictly speaking, all these equivalence relations are now defined on the set FP of Fuchsian presentations (in the sense of (16)) with α > 0.

4. Parity patterns in one-relator groups

4.1. The result. We shall work over the alphabet

A = {x_{1}, x_{2}, …, x_{1}^{−1}, x_{2}^{−1}, … }.

Define a class of words W over A by the following rules.

(i) x_{j}^{2}, [x_{j}, x_{k}] ∈ W for j, k ≥ 1 and j ≠ k.

(ii) If w_{1}, w_{2} ∈ W have no generator in common, then w_{1}w_{2} ∈ W.

(iii) If v ∈ W, and x_{j} is a generator not occurring in v, then [v, x_{j}] ∈ W.

(iv) W is the smallest set of words over A satisfying (i), (ii), and (iii).

Clearly, all surface group relators

∏_{j=1}^{g}[x_{2j−1}, x_{2j}] and ∏_{j=1}^{h} x_{j}^{2}, g, h ≥ 1

are contained in W, as is for instance the word w = [x_{1}^{2}x_{2}^{2}, x_{3}]. For a word w = w(x_{1}, …, x_{d}) over A involving the generators x_{1}, …, x_{d}, define the one-relator group Γ_{w} associated with w via

Γ_{w} = ⟨x_{1}, …, x_{d} | w(x_{1}, …, x_{d}) = 1⟩.

Then we have the following surprising result.

Theorem 8 [Müller/Puchta [34, Theorem 1], 2003]. If w is in W and involves at least three generators, then s_{n}(Γ_{w}) is odd if, and only if, n = k^{2} or n = 2k^{2} for some k ≥ 1; in particular, all groups Γ_{w} with w ∈ W involving three or more generators share the same parity pattern, and s_{n}(Γ_{w}) is multiplicative modulo 2.

It appears likely that Theorem 8 is best possible in the sense that if, for some word w over A the function s_{n}(Γ_{w}) displays the parity pattern described in Theorem 8, then in fact w ∈ W.

4.2. 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}(Γ_{w}) with w ∈ W.

Proposition 6 [Müller/Puchta [34, Theorem 3], 2003]. Let w ∈ W be a word involving three or more generators. Then, modulo 2,

s_{n}(Γ_{w}) ≡ _{∑_{k≥1} ; k(k+1)<2n}s_{n− \frac{1}{2} k(k+1)}(Γ_{w}) + δ(n), n ≥ 1,  (23)

where

δ(n) = \begin{cases}1, & n odd and triangular \\ 0, & 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 (23), which descends in triangular numbers, one cannot help but feel reminded of Euler’s pentagonal theorem

∏_{n≥1}(1 − q^{n}) = 1 + ∑_{k≥1}(−1)^{k}q^{\frac{1}{2} k(3k−1)}(1 + q^{k}) = ∑_{k=−∞}^{∞}(−1)^{k}q^{\frac{1}{2} k(3k−1)},

which yields the recurrence relation

p(n) = ∑_{k≥1}(−1)^{k+1}\{p(n − \frac{1}{2}k(3k − 1)) + p(n − \frac{1}{2}k(3k + 1))\}, n ≥ 1

for the partition function p(n), with the convention that p(n) = 0 for n < 0; cf. [1, Chapter 1.3]. 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^{13}, 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

∑_{n≤x} ; p(n)≡0(2)1 ∼ \frac{x}{2} (x → ∞);

cf. [46]. Subbarao [52] has conjectured that, for any arithmetic progression r (mod t), there are infinitely many integers m ≡ r (t) for which p(m) is odd, and also infinitely many integers n ≡ r (t) for which p(n) is even. Partial results in this direction have been obtained by Ono [44]. Recently, Nicolas, Ruzsa, and Sárközy [43] have shown that, for all r and t,

x^{− \frac{1}{2}} _{∑_{n≤x} ; n≡r (t) ; p(n)≡0(2)}1 → ∞ as x → ∞.

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 (23) together with classical results of Gauß and Legendre concerning the representation numbers of binary quadratic forms; cf. [14, § 205], [23], [10, Chapter VI.8], and [17, Satz 89].

13Cf. [21] for a comprehensive account up to 1970 concerning divisibility properties of p(n). Some exciting recent developments in this area are described in [2] and [3].

4.3. 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}, …, x_{d}) over the alphabet A involving the generators x_{1}, …, x_{d}, and an irreducible character χ of S_{n}, define complex numbers α_{χ}(w) by means of the Fourier expansion

N_{w}(σ) = |{(σ_{1}, …, σ_{d}) ∈ S_{n}^{d} : w(σ_{1}, …, σ_{d}) = σ}|

= (n!)^{d−1} ∑_{χ} α_{χ}(w)χ(σ), σ ∈ S_{n},

where the sum is taken over the set Irr(S_{n}) of all irreducible characters χ of S_{n}. Note that N_{w}(σ) is a class function, thus the coefficients α_{χ}(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 α_{χ}(w), leading to the explicit computation of these coefficients for each word w ∈ W and all χ ∈ Irr(S_{n}).

Lemma 1 [34, Lemma 1]. Let w_{1}, w_{2}, v be words over A, and let χ be an irreducible character of S_{n}.

(i) We have α_{χ}(x_{j}^{2}) = 1 and α_{χ}([x_{j}, x_{k}]) = \frac{1}{χ(1)} for all j, k ≥ 1 and j ≠ k.

(ii) If w_{1} and w_{2} have no generator in common, then

α_{χ}(w_{1}w_{2}) = \frac{α_{χ}(w_{1}) α_{χ}(w_{2})}{χ(1)}.

(iii) If x_{j} does not occur among the generators of v, then

α_{χ}([v, x_{j}]) = \frac{1}{χ(1)} ∑_{χ′∈Irr(S_{n})} α_{χ′}(v) ⟨χ^{2} | χ′⟩.

Indeed, (i) simply restates the fact that the square root function is the model character of S_{n}, as well as Equation (10), the character formula for the function N^{G}; and parts (ii) and (iii) also follow by arguments much in the spirit of Section 2.

Denote by φ the bijection between the self-conjugate partitions of n and the partitions of n into distinct odd parts, mapping a self-conjugate partition λ onto the partition given by the symmetric main hooks of λ. For example,

φ(6, 5, 4, 3, 2, 1) = (11, 7, 3).

Furthermore, denote by c_{λ} the conjugacy class of S_{n} whose cycle structure is given by the partition λ ⊢ n, and by χ_{λ} the irreducible character of S_{n} corresponding to the Specht module S^{λ}. Then an inductive argument based on the Murnaghan-Nakayama rule enables one to prove the following result.^{14}

Lemma 2 [34, Lemma 2]. Let λ_{1} and λ_{2} be partitions of n, with λ_{1} self-conjugate. Then χ_{λ_{1}}(c_{λ_{2}}) is odd if, and only if, λ_{2} = φ(λ_{1}).

14Note that the Murnaghan-Nakayama rule implies in particular that characters of S_{n} are integervalued. A more elementary argument uses the fact that, for all σ ∈ S_{n} and exponents a coprime to the order of σ, the permutations σ and σ^{a} are conjugate.

Call an irreducible character χ of S_{n} symmetric, if χ = ϵ_{n}χ, where ϵ_{n} = χ_{(1^{n})} is the sign character; this is equivalent to demanding that the partition associated with χ be self-conjugate. Lemma 2 thus describes the parity of any symmetric character of S_{n}. A rather subtle argument in the GF(2)-algebra

𝔄 = GF(2)[Irr(S_{n})]

generated by the irreducible characters of S_{n}, building heavily on Lemma 2, now establishes the following.

Lemma 3 [34, Lemma 3]. Let χ and χ′ be irreducible characters of S_{n}.

(i) If χ is symmetric, then ⟨χ^{2^{k}} |χ′⟩ = ⟨χ^{2^{k}} |ϵ_{n}χ′⟩ for all k.

(ii) If both χ and χ′ are symmetric, then ⟨χ^{2}|χ′⟩ is odd if, and only if, χ = χ′.

Call an irreducible character χ of S_{n} a 2-core character, if n!/χ(1) is odd. Note that, since the dimension of an ordinary irreducible representation of a finite group G always divides the order of G/centre(G), this concept is well defined for arbitrary finite groups; cf. [19] or [18, Chapter V, Satz 17.10]. For G = S_{n}, the hook formula shows that an irreducible character χ_{λ} is 2-core if, and only if, all hook lengths of the associated partition λ are odd. The last condition is easily seen to be equivalent to requiring that λ is of the form △ = (k, k − 1, …, 1) for some k ≥ 1. 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 χ_{△} 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 [34, Lemma 4]), which is the decisive tool in proving Proposition 6.

Lemma 4. Let w ∈ W be a word involving d generators, and let χ be an irreducible character of S_{n}.

(i) If d ≥ 2, then (n!)^{d−2}χ(1)α_{χ}(w) is an integer.

(ii) If d ≥ 3 and χ is not 2-core, then (n!)^{d−2}χ(1)α_{χ}(w) is even.

(iii) If d ≥ 2 and χ is 2-core, then (n!)^{d−2}χ(1)α_{χ}(w) is odd.

Proof. Using Lemma 1, we see by induction on d that (χ(1))^{d−1}α_{χ}(w) is integral for d ≥ 1, each irreducible character χ, and every word w ∈ W, which implies (i). Moreover, if χ is not 2-core, then n!/χ(1) is even, hence, for d ≥ 3,

(n!)^{d−2}χ(1)α_{χ}(w) = (\frac{n!}{χ(1)})^{d−2}(χ(1))^{d−1}α_{χ}(w)

is even, whence (ii). Now suppose that χ = χ_{△} is 2-core. We want to show that in this case (χ_{△}(1))^{d−1}α_{χ_{△}}(w) is odd. This is done by induction on the formation length of words in 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} ∈ W having no generator in common, let d_{i} be the number of generators involved in w_{i}, and consider the word w = w_{1}w_{2}. Then w involves d = d_{1} + d_{2} generators, and by part (ii) of Lemma 1,

(χ_{△}(1))^{d−1}α_{χ_{△}}(w) = (χ_{△}(1))^{d_{1}−1}α_{χ_{△}}(w_{1}) · (χ_{△}(1))^{d_{2}−1}α_{χ_{△}}(w_{2}),

which is odd, since by assumption both factors (χ_{△}(1))^{d_{i}−1}α_{χ_{△}}(w_{i}) are odd. Thus, it remains to show that our claim holds for w = [v, x_{j}], provided it is true for v ∈ W, and x_{j} does not occur in v. By Lemma 1 (iii),

(χ_{△}(1))^{d−1}α_{χ_{△}}(w) = (χ_{△}(1))^{d−2} ∑_{χ′} α_{χ′}(v)⟨χ_{△}^{2} | χ′⟩.

Now we distinguish the cases d ≥ 3 and d = 2. If d ≥ 3 and χ′ is not 2-core, then (χ′(1))^{d−2}α_{χ′}(v) is integral, and χ_{△}(1) is divisible by a higher power of 2 than χ′(1). Hence, the terms in the last sum not coming from the 2-core character χ_{△} sum to an even integer, and we have

(χ_{△}(1))^{d−1}α_{χ_{△}}(w) ≡ (χ_{△}(1))^{d−2}α_{χ_{△}}(v)⟨χ_{△}^{2} | χ_{△}⟩ mod 2.

By assumption, (χ_{△}(1))^{d−2}α_{χ_{△}}(v) is odd, as is the multiplicity ⟨χ_{△}^{2}|χ_{△}⟩ by Lemma 3 (ii). Hence, (χ_{△}(1))^{d−1}α_{χ_{△}}(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 = [x_{j}^{2}, x_{k}] for some j ≠ k, and, by Lemma 1 parts (i) and (iii),

χ_{△}(1)α_{χ_{△}}(w) = ∑_{χ′} ⟨χ_{△}^{2} | χ′⟩.

By Lemma 3 (i) for k = 1, the right-hand side is congruent modulo 2 to

∑_{λ⊢n} ; λ=λ′⟨χ_{△}^{2} |χ_{λ}⟩,

which is odd by part (ii) of this lemma. □

With Lemma 4 in hand, we can now establish Proposition 6. Let w ∈ W be a word involving d ≥ 3 generators. By the transformation formula (7), the subgroup numbers s_{n}(Γ_{w}) are related to the sequence h_{n}(Γ_{w}) := | Hom(Γ_{w}, S_{n})|/n! via the equation

nh_{n}(Γ_{w}) = ∑_{ν=0}^{n−1} s_{n−ν}(Γ_{w})h_{ν}(Γ_{w}), n ≥ 1.

Moreover, since homomorphisms of Γ_{w} to S_{n} can be identified with solutions of the equation w(x_{1}, …, x_{d}) = 1 in S_{n}, we have

h_{n}(Γ_{w}) = (n!)^{−1}N_{w}(1) = (n!)^{d−2} ∑_{χ} α_{χ}(w)χ(1).

From Lemma 4 we know that h_{n}(Γ_{w}) is odd if, and only if, n is a triangular number. Hence, for n ≥ 1, we find that, modulo 2,

s_{n}(Γ_{w}) = nh_{n}(Γ_{w}) − ∑_{ν=1}^{n−1} s_{n−ν}(Γ_{w})h_{ν}(Γ_{w})

≡ _{∑_{k≥1} ; k(k+1)<2n}s_{n− \frac{1}{2} k(k+1)}(Γ_{w}) + δ(n),

the correction term δ(n) coming from the term nh_{n}(Γ_{w}).

5. Random Walks on symmetric groups

5.1. Roichman’s conjectures. Let E = E_{1}, E_{2}, E_{3}, … be a Markov chain on a metric space X; i.e., the probability of a sample sequence (E_{j_{0}}, E_{j_{1}}, …, E_{j_{n}}) is given by

p{(E_{j_{0}}, E_{j_{1}}, …, E_{j_{n}})} = a_{j_{0}}p_{j_{0},j_{1}}p_{j_{1},j_{2}} ⋯ 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 E is by definition the collection of all infinite paths on X with probability distribution induced by E. If X is finite, and the initial probability distribution {a_{k}} is given in advance, then 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≥0} of states (that is, elements of S_{n}). Let X = S_{n}, and let 1 ≠ c ⊆ S_{n} be a non-trivial conjugacy class. The random walk w_{c} generated by c has initial state x_{0} = id and the transition matrix P_{c} = (p_{σ,π}^{c})_{σ,π∈S_{n}}, where

p_{σ,π}^{c} := \begin{cases}\frac{1}{|c|}, & πσ^{−1} ∈ c \\ 0, & otherwise. \end{cases}

More explicitly, the statement concerning the initial state of w_{c} means that the initial probability distribution p_{initial} is concentrated in the identity; that is,

p_{initial}\{π\} = \begin{cases}1, & π = id \\ 0, & otherwise \end{cases} .

Given a norm ∥ · ∥ on the complex algebra ℂ^{S_{n}} and a real number ε > 0, we say that the random walk w_{c} has reached ε-equidistribution with respect to ∥ · ∥ in step k, if

∥p\{x_{k} = ·\} − \frac{2}{n!}1_{A_{n}} ∥^{2} ≤ ε · ∥\frac{2}{n!}1_{A_{n}} ∥^{2} .  (24)

Here, 1_{S} denotes the characteristic function for the subset S of the sample space X. We define the statistical mixing time t_{stat}(c) of w_{c} as the least even integer k for which w_{c} has reached \frac{1}{n}-equidistribution with respect to the ℓ^{2}-norm; that is, the norm on ℂ^{S_{n}} given by

∥f∥_{2}^{2} = ⟨f|f⟩ = \frac{1}{n!} ∑_{σ∈S_{n}} |f(σ)|^{2}, f ∈ ℂ^{S_{n}}.

The appearance of 1_{A_{n}} in (24) instead of the expected 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 ℓ^{2}-norm of \frac{2}{n!}1_{A_{n}}, t_{stat}(c) is seen to be the least even integer k such that

∥p\{x_{k} = ·\} − \frac{2}{n!}1_{A_{n}} ∥_{2}^{2} ≤ \frac{2}{n(n!)^{2}} .

A lower bound for t_{stat}(c) is given by the combinatorial mixing time t_{comb}(c) of c; that is, the least even integer k, such that any k elements of 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_{comb}(c) steps, almost certainly every element of the set {1, 2, …, n} has been moved by the conjugacy class c. In [47], Roichman conjectures that, for every non-trivial conjugacy class c ⊆ A_{n},

t_{stat}(c) ≪ t_{comb}(c).  (25)

His main result [47, Theorem 6.1] establishes this conjecture for classes c with cn fixed points, where c is some positive constant; this in turn generalizes an earlier result of Diaconis and Shahshahani [12] for transpositions. Following Roichman’s paper, Fomin and Lulov [13] provide a character bound implying Conjecture (25) for conjugacy classes having only cycles of the same length. In [38], among other things, Roichman’s conjecture is established in full generality.

Theorem 9 [Müller/Schlage–Puchta [38, Theorem 2], 2002]. For n ≥ 4000 and each non-trivial conjugacy class c ⊆ S_{n}, we have

t_{comb}(c) ≤ t_{stat}(c) ≤ 10 t_{comb}(c).

In [47], Roichman suggests an approach to the general conjecture (25) via a certain estimate for character values of symmetric groups. More specifically, he conjectures that, for every ε > 0, n sufficiently large, each conjugacy class c ⊆ S_{n}, and every partition λ ⊢ n,

|χ_{λ}(c)| ≤ χ_{λ}(1)( max \{\frac{λ_{1}}{n} , \frac{∥λ∥}{n}, \frac{1}{e}\})^{(1−ε)n log \frac{n}{n−supp(c)+1}} ,  (26)

which would imply (25).

5.2. A remark concerning the estimate (26). As it stands, estimate (26) is not correct. This can be seen, for instance, as follows. For c fixed-point free, λ such that max\{λ_{1}, ∥λ∥\} ≤ \frac{n}{e}, and ε = \frac{1}{2}, Inequality (26) simplifies to

|χ_{λ}(c)| ≤ χ_{λ}(1) e^{−(n log n)/2}.  (27)

The right-hand side of (27) is bounded above by \sqrt{n!} n^{−n/2} < 1; that is, for c and λ as above, and n sufficiently large, it would follow that χ_{λ}(c) = 0. Since the irreducible characters {χ_{λ}}_{λ⊢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

{χ_{λ} : λ ⊢ n, max{λ_{1}, ∥λ∥} > n/e}  (28)

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 (28) with the dimension of the last space, we find that, for large n,

2 ∑_{0≤ν≤n−n/e} p(ν) ≥ p(n) − p(n − 1),  (29)

where p(n) is the number of partitions of n. The right-hand side of (29) can be estimated via the first term in Rademacher’s series expansion for p(n) (see, for example, [1, Theorem 5.1]) to give

p(n) − p(n − 1) ∼ \frac{πe^{π\sqrt{\frac{2n}{3}}}}{12\sqrt{2} n^{3/2}} (n → ∞).

Bounding the left-hand side of (29) by means of the estimate^{15}

p(n) < \frac{π}{\sqrt{6n}} e^{π\sqrt{\frac{2n}{3}}} ,

we obtain

2 ∑_{0≤ν≤n−n/e} p(ν) ≤ 2np(n − ⌊n/e⌋) ≤ A\sqrt{n} e^{π\sqrt{2(1−1/e)n/3}},

where A is some positive constant. From these two estimates it is clear that inequality (29) is violated for large n.

5.3. Proof of Theorem 9 (Sketch). Despite the failure of his conjecture concerning character values, the basic idea behind Roichman’s suggested approach to (25) turns out to be correct. As a substitute for (26), we prove the following.

Theorem 10 [Müller/Schlage–Puchta [38, Theorem 1], 2002]. For sufficiently large n, every non-trivial conjugacy class c ⊆ S_{n}, and each partition λ ⊢ n, we have

|χ_{λ}(c)| ≤ (χ_{λ}(1))^{1− \frac{1−1/ log n}{6t_{comb}(c)}} ,

and, for 1 ≤ s_{1}(c) ≤ n − 2 (here, s_{1}(c) is the number of 1-cycles of c),

|t_{comb}(c) − \frac{2 log n}{log (n/s_{1}(c))}| ≤ 3,

whereas t_{comb}(c) = 2 for s_{1}(c) = 0.

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

Lemma 5. Let c ⊆ S_{n} be a non-trivial conjugacy class, and let π be the element visited by the random walk w_{c} after 3t_{comb}(c) steps. Then, for each k ≥ 1, the probability that π has more than k fixed points is bounded above by

max \{\frac{2^{k}}{(k − 1)!}, \frac{2^{n/2}}{(⌊n/2⌋ − 1)!}\}.

Lemma 6. Let c_{1}, c_{2} ⊆ S_{n} be non-trivial conjugacy classes with f_{1} respectively f_{2} fixed points. For i = 1, 2, let x_{i} ∈ c_{i} be chosen at random. Then the probability that x_{1} and x_{2} have ℓ common fixed points, is at most

\binom{n}{ℓ}(\frac{f_{1}f_{2}}{n^{2}} )^{ℓ}.

15Cf., for instance, [22, Satz 7.6].

Moreover, the probability for x_{1}x_{2} to have k cycles on supp(x_{1}) ∪ 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_{stat}(c) in terms of the number of fixed points of 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} = ·} in step k of the random walk w_{c} is given by the k-fold convolution of the function \frac{1}{|c|}1_{c} with itself, where, for two functions f, g : S_{n} → ℂ, the convolution f ∗ g : S_{n} → ℂ is defined as^{16}

(f ∗ g)(π) = ∑_{σ∈S_{n}} f(σ)g(πσ^{−1}).

Indeed,

p{x_{k} = π} = ∑_{σ∈S_{n}} p{x_{k−1} = πσ^{−1}} p_{πσ^{−1},π}^{c}

= \frac{1}{|c|} ∑_{σ∈c} p\{x_{k−1} = πσ^{−1}\}

= [(\frac{1}{|c|}1_{c}) ∗ p\{x_{k−1} = ·\}](π),

and since

p\{x_{1} = π\} = p_{id,π}^{c} = (\frac{1}{|c|}1_{c})(π),

our claim that

p\{x_{k} = ·\} = (\frac{1}{|c|}1_{c})^{∗k}

follows by induction on k. Next, we need a result relating the statistical mixing time of the random walk w_{c} to the character theory of the underlying finite group S_{n}. This is the following.

Lemma 7. Let c ⊆ S_{n} be a conjugacy class, k a positive integer. Then

(n!)^{2} ∥(\frac{1}{|c|} 1_{c})^{∗k} − \frac{2}{n!} 1_{A_{n}} ∥_{2}^{2} = _{∑_{χ} ; χ(1)≠1} \frac{|χ(c)|^{2k}}{(χ(1))^{2k−2}} .  (30)

Proof. For a class function f : S_{n} → ℂ and an irreducible character χ of S_{n}, define the Fourier coefficient α_{χ}(f) via

f(σ) = ∑_{χ} α_{χ}(f) χ(σ), σ ∈ S_{n}.  (31)

16Note that the convolution of two class functions is again a class function.

Since the irreducible characters form a basis for the space of class functions, the Fourier coefficients α_{χ}(f) exist and are uniquely determined by (31). We shall need the following facts concerning the coefficients α_{χ}(f).

(i) α_{χ}(f) = ⟨f|χ⟩,

(ii) α_{χ}(f ∗ g) = n!α_{χ}(f)α_{χ}(g)/χ(1),

(iii) ∑_{χ} |α_{χ}(f)|^{2} = ||f||_{2}^{2}.

The proof of (i) consists in evaluating the sum ∑_{χ}⟨f|χ⟩χ(σ) via the orthogonality relation (21), while (iii) (Parseval’s Equation) follows directly from properties of the scalar product ⟨·|·⟩. We focus on the proof of (ii). By (i),

α_{χ}(f ∗ g) = ⟨f ∗ g | χ⟩

= \frac{1}{n!} ∑_{π}(f ∗ g)(π)χ(π^{−1})

= \frac{1}{n!} ∑_{π} ∑_{σ} f(σ)g(πσ^{−1})χ(π^{−1})

= \frac{1}{n!} ∑_{π} ∑_{σ} ∑_{χ′} ∑_{χ′′} α_{χ′}(f)α_{χ′′}(g)χ′(σ)χ′′(πσ^{−1})χ(π^{−1})

= ∑_{π} ∑_{χ′} ∑_{χ′′} α_{χ′}(f)α_{χ′′}(g)χ(π^{−1})\frac{1}{n!} ∑_{σ} χ′′(πσ^{−1})\overline{χ′(σ^{−1})}

= ∑_{π} ∑_{χ′} ∑_{χ′′} α_{χ′}(f)α_{χ′′}(g)χ(π^{−1})χ′′(π)δ_{χ′,χ′′}/χ′′(1)

= ∑_{π} ∑_{χ′} α_{χ′}(f)α_{χ′}(g)χ(π^{−1})χ′(π)/χ′(1)

= ∑_{χ′} \frac{n!α_{χ′}(f)α_{χ′}(g)}{χ′(1)}⟨χ′|χ⟩

= n!α_{χ}(f)α_{χ}(g)/χ(1),

where we have used the orthogonality relation (22) 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 α_{χ}(f) of the function f = \frac{1}{|c|}1_{c} is found to be

⟨\frac{1}{|c|}1_{c} | χ⟩ = \frac{1}{n!} ∑_{σ} (\frac{1}{|c|}1_{c})(σ) χ(σ^{−1})

= \frac{1}{n!} ∑_{σ∈c} χ(σ^{−1})/|c|

= χ(c^{−1})/n!.

Property (ii) together with induction on k then yields

α_{χ}((\frac{1}{|c|}1_{c})^{∗k}) = \frac{(χ(c^{−1}))^{k}}{n!(χ(1))^{k−1}} ,

thus

α_{χ}((\frac{1}{|c|}1_{c})^{∗k} − \frac{2}{n!}1_{A_{n}}) = \frac{(χ(c^{−1}))^{k}}{n!(χ(1))^{k−1}} − \frac{1}{n!}δ_{χ,χ_{0}} − \frac{1}{n!}δ_{χ,χ_{1}},

where χ_{1} is the sign character, χ_{0} the trivial character of S_{n}. Equation (30) follows now from Parsival’s Equation (iii). □

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 c in G, and every positive integer k,

|G|^{2} | ; |(\frac{1}{|c|}1_{c})^{∗k} − \frac{1}{|G|}1_{G}| ; |_{2}^{2} = ∑_{χ≠χ_{0}} \frac{|χ(c)|^{2k}}{(χ(1))^{2k−2}} ,

where χ_{0} is the trivial character of G.

Now let c ⊆ S_{n} be a non-trivial conjugacy class. Then we infer from Lemma 7 that w_{c} has reached \frac{1}{n}-equidistribution with respect to the ℓ^{2}-norm after k steps if, and only if,

∑_{χ} ; χ(1)≠1 \frac{|χ(c)|^{2k}}{(χ(1))^{2k−2}} ≤ \frac{2}{n}.

By the first part of Theorem 10, the left-hand side can be bounded above by

∑_{χ} ; χ(1)≠1(χ(1))^{2− \frac{2k(1−1/ log n)}{6t_{comb}(c)}} .

For k ≥ 10t_{comb}(c) and sufficiently large n, the last expression is less than

∑_{χ} ; χ(1)≠1(χ(1))^{−5/4},

which in turn is O(n^{−5/4}) by Corollary 1. Hence, for n sufficiently large, we obtain the bound t_{stat}(c) ≤ 10t_{comb}(c) as required.

References

[1] G. Andrews, The Theory of Partitions, Cambridge University Press, New York, 1984.

[2] S. Ahlgren and K. Ono, Congruence properties for the partition function, Proc. Nat. Acad. Sciences USA 98 (2001), 12882–12884.

[3] 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), Contemp. Math. 291 (2001), Amer. Math. Soc., Providence (RI), 1–10.

[4] E. A. Bender, An asymptotic expansion for the coefficients of some formal power series, J. London Math. Soc. (2) 9 (1975), 451–458.

[5] B. Baumslag and S. Pride, Groups with two more generators than relators, J. London Math. Soc. 17 (1978), 425–426.

[6] K. S. Brown, Cohomology of Groups, Springer, New York, 1982.

[7] P. J. Cameron and T. W. Müller, A descent principle in modular subgroup arithmetic, J. Pure Appl. Algebra 203 (2005), 189–203.

[8] C. W. Curtis and I. Reiner, Representation Theory of Finite Groups and Associative Algebras, John Wiley & Sons, New York, 1962.

[9] C. W. Curtis and I. Reiner, Methods of Representation Theory, Vol. I, John Wiley & Sons, New York, 1981.

[10] H. Davenport, The Higher Arithmetic, sixth edition, Cambridge University Press, 1992.

[11] P. Diaconis, Group Representations in Probability and Statistics, IMS Lecture Notes Vol. 11, Hayward, California, 1988.

[12] P. Diaconis and M. Shahshahani, Generating a random permutation with random transpositions, Z. Wahrscheinlichkeitstheorie u. Verw. Gebiete 57 (1981), 159–179.

[13] S. V. Fomin and N. Lulov, On the number of rim hook tableaux, J. Math. Sciences 87 (1997), 4118–4123.

[14] C. F. Gauß, Disquisitiones Arithmeticae (Lipsia in commissis apud Gerh. Fleischer Iun), 1801; English translation by A. Clarke (Springer, New York), 1986.

[15] M. Hall, Subgroups of finite index in free groups, Canad. J. Math. 1 (1949), 187–190.

[16] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, reprint of the fifth edition, 1989.

[17] E. Hecke, Vorlesungen über 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 Lectures on the Theory of Algebraic Numbers (Springer, New York), 1981.

[18] B. Huppert, Endliche Gruppen, vol. 1, Springer, Heidelberg, 1979.

[19] N. Ito, On the degrees of irreducible representations of a finite group, Nagoya Math. J. 3 (1951), 5–6.

[20] A. Kerber, Algebraic Combinatorics via Finite Group Actions, BI-Wissenschaften, Mannheim, 1991.

[21] M. Knopp, Modular Functions in Analytic Number Theory, Markham, Chicago, 1970.

[22] E. Krätzel, Zahlentheorie, VEB Deutscher Verlag der Wissenschaften, Berlin, 1981.

[23] A.-M. Legendre, Essai sur la Théorie des Nombres, Paris, 1798. Fourth edition as Théorie des Nombres, 1830; reprinted (Albert Blanchard, Paris), 1955.

[24] R. C. Lyndon, Two notes on Rankin’s book on the modular group, J. Austral. Math. Soc. 16 (1973), 454–457.

[25] R. C. Lyndon and P. E. Schupp, Combinatorial Group Theory, Springer, Berlin/Heidelberg, 1977.

[26] W. Magnus, Noneuclidean Tesselations and Their Groups, Academic Press, New York, 1974,

[27] T. Müller, Subgroup growth of free products, Invent. math. 126 (1996), 111–131.

[28] T. Müller, Finite group actions and asymptotic expansion of e^{P (z)}, Combinatorica 17 (1997), 523–554.

[29] T. Müller, Enumerating representations in finite wreath products, Adv. in Math. 153 (2000), 118–153.

[30] T. W. Müller, Modular subgroup arithmetic and a theorem of Philip Hall, Bull. London Math. Soc. 34 (2002), 587–598.

[31] T. W. Müller, Modular subgroup arithmetic in free products, Forum Math. 15 (2003), 759–810.

[32] T. W. Müller, Parity patterns in Hecke groups and Fermat primes. In: Proceedings 1999 Bielefeld conference ‘Groups: Topological, Combinatorial and Arithmetic Aspects’ (T. W. Müller ed.). LMS Lecture Notes Series 311, Cambridge University Press, Cambridge, 2004, 327–374.

[33] T. W. Müller and J.-C. Puchta, Character Theory of symmetric groups and subgroup growth of surface groups, J. London Math. Soc. (2) 66 (2002), 1–18.

[34] T. W. Müller and J.-C. Puchta, Parity patterns in one-relator groups, J. Group Theory 6 (2003), 245–260.

[35] T. W. Müller and J.-C. Schlage–Puchta, Classification and statistics of finite index subgroups in free products, Adv. Math. 188 (2004), 1–50.

[36] T. W. Müller and J.-C. Schlage–Puchta, Modular arithmetic of free subgroups, Forum Math. 17 (2005), 375–405.

[37] T. W. Müller and J.-C. Schlage–Puchta, Some examples in the theory of subgroup growth, Monatsh. Math. 146 (2005), 49–76.

[38] T. W. Müller and J.-C. Schlage–Puchta, Character theory of symmetric groups, subgroup growth of Fuchsian groups, and random walks, to appear.

[39] T. W. Müller and J.-C. Schlage–Puchta, Statistics of isomorphism types in free products, to appear.

[40] T. W. Müller and J.-C. Schlage–Puchta, Decomposition of the conjugacy representation for symmetric groups and subgroup growth, to appear.

[41] M. Newman, Asymptotic formulas related to free products of cyclic groups, Math. Comp. 30 (1976), 838–846.

[42] J. Nielsen, The commutator group of the free product of cyclic groups, Mat. Tidsskr. B (1948), 49–56.

[43] J.-L. Nicolas, I. Ruzsa, and A. Sárközy, On the parity of additive representation functions, J. Number Theory 73 (1998), 292–317.

[44] K. Ono, On the parity of the partition function in arithmetic progressions, J. Reine u. Angew. Math. 472 (1996), 1–15.

[45] S. J. Pride, The concept of largeness in group theory. In: Word Problems II, Amsterdam: North Holland, 1980, 299–335.

[46] T. Parkin and D. Shanks, On the distribution of parity in the partition function, Math. Comp. 21 (1967), 466–480.

[47] Y. Roichman, Upper bound on the characters of the symmetric groups, Invent. math. 125 (1996), 451–485.

[48] Y. Roichman, Decomposition of the conjugacy representation of the symmetric group, Israel J. Math. 97 (1997), 305–316.

[49] T. Scharf, Die Wurzelanzahlfunktion in symmetrischen Gruppen, J. Algebra 139 (1991), 446–457.

[50] R. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, New York, 1999.

[51] W. Stothers, The number of subgroups of given index in the modular group, Proc. Royal Soc. Edinburgh 78A (1977), 105–112.

[52] M. Subbarao, Some remarks on the partition function, Amer. Math. Monthly 73 (1966), 851–854.

[53] E. M. Wright, A relationship between two sequences, Proc. London Math Soc. (3) 17 (1967), 296–304.

[54] E. M. Wright, Asymptotic relations between enumerative functions in graph theory, Proc. London Math. Soc. 20 (1970), 558–572.

Thomas W. Müller School of Mathematical Sciences Queen Mary & Westfield College University of London Mile End Road E1 4NS London United Kingdom