Applications of the representation theory of finite groups

Appendix by D. Zagier to “Graphs on Surfaces and Their Applications”, by S. Lando and A. Zvonkin

This appendix consists of two sections. In the first we give a self-contained and fairly complete introduction to the representation and character theory of finite groups, including Frobenius’s formula and a higher genus generalization. In the second we give several applications related to topics treated in this book.

1. Representation theory of finite groups

1.1. Irreducible representations and characters. Let G be a finite group. A (finitedimensional; we will always assume this) representation (V, π) of G is a finite-dimensional complex vector space V and a homomorphism π : G → GL(V). Thus each g ∈ G defines a linear map v ↦ π(g)v from V to V, with π(g_{1}g_{2}) = π(g_{1})π(g_{2}). One often drops the “π” and writes the action simply as v ↦ gv. Alternatively, one often drops the “V ” and simply denotes the representation itself by π. The definition given here corresponds to left representations; one also has right representations (where v ↦ vg with v(g_{1}g_{2}) = (vg_{1})g_{2}); this leads to an isomorphic theory, by replacing g by g^{−1}.

We call two representations V and V′ isomorphic, denoted V ≃ V′, if there is a G-equivariant isomorphism from V to V′, and write V ≅ V′ if such an isomorphism has been fixed. If V is a (left) representation of G and A a complex vector space, then both V ⊗_{ℂ} A and Hom_{ℂ}(A, V) are (left) representations in the obvious way (g(v ⊗ a) = (gv) ⊗ a, (gϕ)(a) = gϕ(a)). If dim_{ℂ} A = k, then both of these representations are isomorphic to V ⊕ ⋯ ⊕ V (k copies), the isomorphisms being canonical if one has chosen a basis of A. Similarly, the dual space V^{∗} = Hom_{ℂ}(V, ℂ) is in a natural way a right representation of G via (ϕg)(v) = ϕ(gv) and the space Hom_{ℂ}(V, A) is also a right representation, isomorphic to k copies of V^{∗}. Finally, if V and V′ are two representations of G, then we write V ⊗_{G} V′ for the quotient of V ⊗_{ℂ} V′ by the relation gv ⊗ v′ = v ⊗ gv′ and Hom_{G}(V, V′) for the set of G-equivariant linear maps from V to V′; these are simply vector spaces, without any natural G-action.

A representation V of G is called irreducible if it contains no proper subspace which is invariant under the action of G. As a simple example, let G = S_{n} and V = ℂ^{n} with the obvious action of G by permutation of the coordinates. Then V is not irreducible, since it contains the two subspaces W_{1} = {(x, …, x) | x ∈ ℂ} and W_{2} = {(x_{1}, …, x_{n}) ∈ ℂ^{n} | x_{1} + ⋯ + x_{n} = 0}, of dimensions 1 and n−1 respectively, which are obviously invariant under the action of G. On the other hand, these two representations are irreducible and V is their direct sum. More generally, one has:

Lemma 1. Any representation of G is a direct sum of irreducible ones.

Proof. Pick a G-invariant non-degenerate scalar product on V. (To obtain one, start with any positive-definite scalar product and replace it by the obvious average over G.) If V is not already irreducible, it contains a proper G-invariant subspace W. But then the orthogonal complement W^{⊥} of W is also G-invariant, and V = W ⊕ W^{⊥}. The result now follows by induction on the dimension. □

This will be used in conjunction with the following property of irreducible representations:

Lemma 2 (Schur’s Lemma). Let V and V′ be two irreducible representations of G. Then the complex vector space Hom_{G}(V, V′) is 0-dimensional if V ≄ V′ and 1-dimensional if V ≃ V′. The space Hom_{G}(V, V) is canonically isomorphic to ℂ.

Proof. Since neither V nor V′ has a non-trivial G-invariant subspace, any non-zero G-equivariant map ϕ : V → V′ has trivial kernel and cokernel. Hence Hom_{G}(V, V′) = {0} if V and V′ are not isomorphic. If they are, then we may assume that V′ = V. Then for any eigenvalue λ of ϕ, the map ϕ − λ has a kernel and therefore is zero. Hence Hom_{G}(V, V) ≅ ℂ canonically. □

These two lemmas already suffice to prove one of the first basic facts of the theory, the “first orthogonality relation for characters.” If (V, π) is an irreducible representation, we define its character as the function χ_{π}(g) = tr(π(g), V) from G to ℂ. Then we have:

Corollary (First orthogonality relation). Let (V, π) and (V′, π′) be two irreducible representations of G. Then

\frac{1}{|G|} ∑_{g∈G} χ_{π}(g) \overline{χ_{π′}(g)} = \{ \begin{matrix}1 & if π ≃ π′, \\ 0 & otherwise. \end{matrix}  (1)

Proof. The dimension of the space V^{G} of G-invariant vectors in any representation V of G is given by dim(V^{G}) = |G|^{−1} ∑_{g∈G} tr(g, V). (Proof. The linear map v ↦ |G|^{−1} ∑_{g∈G} gv is a projection from V to V^{G}, so its trace equals dim V^{G}.) Apply this to the G-representation Hom_{ℂ}(V, V′) ≅ V ⊗_{ℂ} V′^{∗}, with G acting by g(v, ϕ) = (gv, ϕ ∘ g^{−1}). (Recall that V′^{∗} is naturally a right representation of G, so that we have to replace g by g^{−1} when we act from the left.) Then the trace of g ∈ G equals χ_{π}(g)\overline{χ_{π′}(g)}, and the dimension of (Hom(V, V′))^{G} = Hom_{G}(V, V′) is 1 or 0 by Schur’s Lemma. □

Now let {(V_{i}, π_{i})}_{i∈I} be a full set of non-isomorphic irreducible representations of G. Lemma 1 tells us that any representation V of G is isomorphic to a direct sum ⨁_{i∈I} \underbrace{V_{i} ⊕ ⋯ ⊕ V_{i}}_{k_{i}} of the

representations V_{i} or equivalently, by what was said above, that

V ≅ ⨁_{i} V_{i} ⊗_{ℂ} A_{i} ≅ ⨁_{i} Hom_{ℂ}(B_{i}, V_{i})  (2)

for some k_{i}-dimensional vector spaces A_{i} and B_{i} over ℂ, but we do not yet know that these spaces, or even the multiplicities k_{i}, are independent of the decomposition chosen. The following lemma shows that this is true and gives a canonical description of the spaces A_{i} and B_{i}.

Lemma 3. Let V be an arbitrary representation of G. Then we have canonical G-equivariant isomorphisms

⨁_{i∈I} V_{i} ⊗_{ℂ} Hom_{G}(V_{i}, V) ⟶^{∼} V ,  V ⟶^{∼} ⨁_{i∈I} Hom_{ℂ}(Hom_{G}(V, V_{i}), V_{i})  (3)

given by sending x ⊗ ϕ ∈ V_{i} ⊗ Hom_{G}(V_{i}, V) to ϕ(x) and v ∈ V to the homomorphism ϕ ↦ ϕ(v) from Hom_{G}(V, V_{i}) to V_{i}. Conversely, given any decompositions of V of the form (2), there are canonical isomorphisms A_{i} ≅ Hom_{G}(V_{i}, V) and B_{i} ≅ Hom_{G}(V, V_{i}) as complex vector spaces.

Proof. Since both isomorphisms in (2) are additive under direct sums, we may assume by Lemma 1 that V is irreducible, say V = V_{j} for some j ∈ I. Then both statements in (3) follow immediately from Lemma 2, since V_{j} ⊗_{ℂ} ℂ ≅ Hom_{ℂ}(ℂ, V_{j}) ≅ V_{j} . The proof of the last statement, which will not be used in what follows, is similar and will be left to the reader. □

We next introduce the group algebra ℂ[G]. This is the set of linear combinations ∑_{g∈G} α_{g}[g] (α_{g} ∈ ℂ) of formal symbols [g] (g ∈ G), with the obvious addition and multiplication. It can be identified with Maps(G, ℂ) via α(g) = α_{g}. The group algebra is a left and right representation of G via g_{1}[g]g_{2} = [g_{1}gg_{2}], or equivalently (g_{1}αg_{2})(g) = α(g_{1}^{−1}gg_{2}^{−1}) if α is a map from G to ℂ. The central result of the representation theory of finite groups is the following assertion.

Theorem 1. Let G be a finite group. Then there is a canonical (G × G)-equivariant algebra isomorphism

ℂ[G] ≅ ⨁_{i∈I} End_{ℂ}(V_{i})  (4)

sending [g] to the collection of linear maps π_{i}(g) : V_{i} → V_{i}.

Proof. For any representation V of G, Hom_{G}(ℂ[G], V) ≅ V as G-representations, since an equivariant map ϕ : ℂ[G] → V is uniquely determined by ϕ([1]) ∈ V, which is arbitrary. Applying this to V = V_{i} (i ∈ I) and then applying the second isomorphism in (3) to V = ℂ[G], we obtain the assertion of the theorem. We can also obtain the isomorphism (4), in the reverse direction, by applying the first isomorphism in (3) to V = ℂ[G] and using the canonical isomorphisms Hom_{G}(V_{i}, ℂ[G]) ≅ V_{i}^{∗} and V_{i} ⊗_{ℂ} V_{i}^{∗} ≅ Hom_{ℂ}(V_{i}, V_{i}) ≅ End_{ℂ}(V_{i}). □

Essentially all important general facts about representations of finite groups are corollaries of this theorem. To state them, let us introduce the notation C for the set of conjugacy classes in G and R for the set of isomorphism classes of irreducible representations. (Of course R and the index set I used above are in canonical bijection, but we will no longer need to have picked representatives for the elements of R.) Since the value of the character χ_{π}(g) depends only on the isomorphism class of π and the conjugacy class of g, we can write, with some abuse of notation, χ_{π}(C) for any π ∈ R and C ∈ C. For instance, with these notations the first orthogonality relation (1) becomes

∑_{C∈C} |C| χ_{π}(C) \overline{χ_{π′}(C)} = |G| δ_{π,π′}  (π, π′ ∈ R) .  (5)

Then Theorem 1 has the following consequences.

Corollary 1. The cardinality of R is finite and

∑_{π∈R}(dim π)^{2} = |G| .  (6)

Proof. Compare the dimensions on both sides of (4). □

Corollary 2. The sets C and R have the same cardinality: there are as many irreducible representations of G as there are conjugacy classes in G.

Proof. A basis for the center Z(ℂ[G]) of ℂ[G] is clearly given by the elements e_{C} = ∑_{g∈C}[g] (C ∈ C). On the other hand, End_{ℂ}(V_{i}) is the matrix algebra M_{dim V_{i}}(ℂ), with 1-dimensional center. Hence the algebra isomorphism (4) tells us that |C| = dim_{ℂ} Z(ℂ[G]) = |R|. □

Corollary 3 (Second orthogonality relation). Let C_{1}, C_{2} ∈ C. Then

∑_{π∈R} χ_{π}(C_{1})\overline{χ_{π}(C_{2})} = \{ \begin{matrix}|G|/|C_{1}| & if C_{1} = C_{2}, \\ 0 & otherwise. \end{matrix}  (7)

Notice that this formula agrees with (6) when C_{1} = C_{2} = {1}, since χ_{π}(1) = dim π.

Proof. This follows from equation (5) and Corollary 2, since these imply that the matrix (|C|^{1/2}|G|^{−1/2}χ_{π}(C))_{π∈R, C∈C} is square and unitary, and the inverse of a unitary matrix is also unitary. But we can also obtain (7) directly (and then, if we wish, deduce (5) from it) by computing the trace of the action of (g_{1}, g_{2}) ∈ C_{1} × C_{2} on both sides of (4). The action of (g_{1}, g_{2}) on the basis {[g]}_{g∈G} of ℂ[G] is given by the permutation [g] ↦ [g_{1}gg_{2}^{−1}] (as before, we have to invert g_{2} to turn the right action into a left one), so its trace is the number of fixed points of this permutation, which is clearly |G|/|C_{1}| if g_{1} and g_{2} are conjugate and 0 otherwise. On the other hand, the trace of (g_{1}, g_{2}) on End_{ℂ}(π) = π ⊗_{ℂ} π^{∗} equals χ_{π}(g_{1})\overline{χ_{π}(g_{2})}. □

1.2. Examples. We illustrate the theory explained in §1.1 in a few important special cases.

Abelian groups. If G is a cyclic group of order n, with generator γ, then there are n obvious 1-dimensional (and hence irreducible!) representations of G given by V = ℂ and γv = ζv with ζ ∈ ℂ a (not necessarily primitive) nth root of unity. By the dimension formula (6), these are the only irreducible representations. More generally, for any finite abelian group one sees easily that all irreducible representations of G are 1-dimensional (because the commuting operators π(g) on any representation V have a common eigenvector, or alternatively by reducing to the cyclic case) and that the corresponding characters are simply the homomorphisms from G to ℂ^{∗}.

Symmetric groups of small order. The symmetric group S_{n} has two 1-dimensional representations 1 (the trivial representation, V = ℂ with all elements of G acting as +1) and εεε_{n} (the sign representation, V = ℂ with odd permutations acting as −1) and an (n − 1)-dimensional irreducible representation St_{n} which is the space W_{2} ⊂ ℂ^{n} mentioned at the beginning of this section. For n = 2 and n = 3, the dimension formula (6) shows that these are the only irreducible representations (and St_{n} ≃ εεε_{n} for n = 2), with character tables given by

1 εεε_{2}  |C|  1 εεε_{3} St_{3}  |C|
Id 1 1  1  Id 1 1 2  1
(12) 1 −1  1  (12) 1 −1 0  3
(123) 1 1 −1  2

(Here the numbers on the right show the size of the conjugacy classes, needed as weights to make the columns of the table orthogonal; the rows are orthogonal as they stand.) For n = 4, the orthogonality relations again have a unique solution and the character table must take the form

1 εεε_{4} A St_{4} St_{4} ⊗ εεε_{4}  |C|
Id 1 1 2 3  3  1
(12) 1 −1 0 1  −1  6
(123) 1 1 −1 0  0  8
(12)(34) 1 1 2 −1  −1  3
(1234) 1 −1 0 −1  1  6

for some 2-dimensional irreducible representation A of S_{4}. We can construct A explicitly as {(x_{s})_{s∈S} | ∑ x_{s} = 0}, where S is the 3-element set of decompositions of {1, 2, 3, 4} into two (unordered) subsets of cardinality 2. The reader may wish to attempt constructing “by hand” the 7×7 character table for the group S_{5}, where the dimensions of the irreducible representations are 1, 1, 4, 4, 5, 5 and 6.

Observe that in the above tables for S_{n} the character values χ_{π}(g) are all integers. This is a general fact. For arbitrary finite group representations, χ_{π}(g) is a sum of roots of unity and hence an algebraic integer, and its Galois conjugates are simply the values of χ_{π}(g^{ℓ}) with ℓ ∈ ℤ prime to the order of g. (This is because the action of Gal(\overline{ℚ}/ℚ) on roots of unity is given by ζ ↦ ζ^{ℓ} with ℓ prime to the order of ζ.) For G = S_{n}, however, g^{ℓ} and g are conjugate since they have the same cycle structure, so χ_{π}(g) is Galois invariant and hence belongs to ℤ.

Symmetric groups of arbitrary order. We will not give a complete account of the general representation theory of S_{n} here, since it is a little complicated and there are many good accounts, but will only mention some highlights, following the approach given in the beautiful paper [OV], which we highly recommend to the reader. The statements given here will be used only in §2.3. We denote by R_{n} the sets of isomorphism classes of irreducible representations of S_{n}. We will also consider S_{n−1} as a subgroup of S_{n} (namely, the set of elements fixing n), and similarly for all S_{i}, i < n.

A. The first basic fact is that each irreducible representation of S_{n}, when restricted to the subgroup S_{n−1}, splits into the direct sum of distinct irreducible representations of S_{n−1}. For π ∈ R_{n} and π′ ∈ R_{n−1} we write π′ ≺ π if π′ occurs in π|_{S_{n−1}}, so π|_{S_{n−1}} = ⊕_{π′≺π}π′. Similarly, each π′ ≺ π when restricted to S_{n−2} splits into a sum of irreducible rerpresentations π′′ of S_{n−2}, and continuing this process, we see that π splits canonically into a direct sum of 1-dimensional spaces V_{ξ} indexed by all possible chains ξ : π_{1} ≺ ⋯ ≺ π_{n} = π with π_{i} ∈ R_{i}. (Specifically, we have V_{ξ} = V_{1} ⊂ ⋯ ⊂ V_{n} = π where each V_{i} is S_{i}-invariant and isomorphic to π_{i}.) Notice how unusual this behavior is: for general finite groups G it is more modern, and of course better, to think of representations as actions of G on abstract vector spaces, without any choice of basis, rather than as collections of matrices satsifying the same relations as the elements of G, but for the symmetric groups the irreducible representations come equipped with their own nearly (i.e., up to scalar multiples) canonical bases, and we have matrices after all!

B. The next key idea is to introduce the so-called Jucys-Murphy element

X_{n} = (1 n) + (2 n) + ⋯ + (n − 1 n)

of the group algebra ℤ[S_{n}]. We can write this element as e_{[T]_{n}} − e_{[T]_{n−1}}, where e_{[T]_{n}} ∈ Z(ℤ[S_{n}]) as in the proof of Corollary 2 above is the sum of all elements in the conjugacy class [T]_{n} of T = (1 2) ∈ S_{n} and e_{[T]_{n−1}} is the corresponding element for n − 1. Since e_{[T]_{n}} is central, by Schur’s lemma it acts on each π ∈ R_{n}, and hence on each subrepresentation π′ ≺ π, as multiplication by a scalar ν_{π}(T) (which belongs to ℤ by the remark on integrality made above), and similarly e_{[T]_{n−1}} acts on π′ as a scalar ν_{π′}(T), so X_{n} acts on π′ as multiplication by the number a_{n} = ν_{π}(T) − ν_{π′}(T). By induction on i it follows that for each chain ξ = (π_{1}, …, π_{n}) each element X_{i} ∈ ℤ[S_{i}] ⊂ ℤ[S_{n}] acts on π_{i−1} as multiplication by some integer a_{i}(ξ), so we can associate to the chain ξ a weight vector a(ξ) = (a_{1}(ξ), …, a_{n}(ξ)) ∈ ℤ^{n}.

C. Conversely, the weight vector a(ξ) determines ξ (and hence also π) completely, and there is a complete description of which vectors a = (a_{1}, …, a_{n}) ∈ ℤ^{n} occur as weight vectors. (The conditions are (i) a_{1} = 0, (ii) for each j > 1, we have |a_{j} − a_{i}| = 1 for some i < j, and (iii) if a_{i} = a_{j} for some i < j then both a_{i} − 1 and a_{i} + 1 occur among the a_{k} with i < k < j.) Furthermore, two weight vectors a, a′ ∈ ℤ^{n} correpond to the same representation π if and only if they are permutations of one another, so that π is uniquely characterized by the function f : ℤ → ℤ_{≥0} defined by f(r) = #{i | a_{i} = r}, and this sets up a bijection between R_{n} and the set of finitely supported functions f : ℤ → ℤ_{≥0} satisfying f(r + 1) − f(r) ∈ {0, |r| − |r + 1|} for all r and ∑_{r∈ℤ} f(r) = n. These functions in turn correspond bijectively to the elements of the set Y_{n} of Young diagrams (= subsets Y ⊂ ℕ^{2} such that (x, y) ∈ Y ⇒ (x′, y′) ∈ Y whenever 1 ≤ x′ ≤ x, 1 ≤ y′ ≤ y) of cardinality n, the correspondence f ↔ Y being given by f(r) = #{(x, y) ∈ Y | x − y = r} and Y = {(x, y) ∈ ℕ^{2} | min(x, y) ≤ f(x − y)}. In the bijection between R_{n} and Y_{n} obtained in this way one has π′ ≺ π if and only if the corresponding Young diagrams Y′ ∈ Y_{n−1} and Y ∈ Y_{n} satisfy Y′ ⊂ Y.

D. Finally, there is an explicit inductive procedure, given by the so-called Murnaghan-Nakayama rule, to compute the value of the character χ_{π}(C) for any π ∈ R_{n} and conjugacy class C ⊂ S_{n} in terms of the Young diagram associated to π and the partition of n associated to C. However, we will not use this and do not give the details here, noting only that the case C = [T]_{n}, which will be needed in §2.3, follows from B. and C. above.

1.3. Frobenius’s formula. We end §1 by describing a formula which has applications to combinatorial problems in many parts of mathematics and in particular to several of the topics treated in this book; some of these applications will be discussed in §2. This formula computes the number

N (G; C_{1}, …, C_{k}) := # {(c_{1}, …, c_{k}) ∈ C_{1} × ⋯ × C_{k} | c_{1} ⋯ c_{k} = 1}

for arbitrary conjugacy classes C_{1}, …, C_{k} ∈ C in terms of the characters of the irreducible representations of G. Note that N (G; C_{1}, …, C_{k}) is independent of the order of the arguments, because the identity c_{i}c_{i+1} = c_{i+1}(c_{i+1}^{−1}c_{i}c_{i+1}) lets us interchange C_{i} and C_{i+1}.

Theorem 2 (Frobenius’s formula). Let G be a finite group and C_{1}, …, C_{k} conjugacy classes in G. Then

N (G; C_{1}, …, C_{k}) = \frac{|C_{1}| ⋯ |C_{k}|}{|G|} ∑_{χ} \frac{χ(C_{1}) ⋯ χ(C_{k})}{χ(1)^{k−2}} ,  (8)

where the sum is over all characters of irreducible representations of G.

Before giving the proof, we note three special cases. If k = 1 or k = 2, then (8) reduces to the orthogonality relation (7), applied to (C_{1}, 1) or (C_{1}, C_{2}^{−1}), respectively. For k = 3, we write (C_{1}, C_{2}, C_{3}) = (A, B, C^{−1}) with A, B, C ∈ C. Then N (G; C_{1}, C_{2}, C_{3}) = n_{AB}^{C}, where

n_{AB}^{C} = #{(a, b) ∈ A × B | ab ∈ C} .

The integers n_{AB}^{C} are nothing but the structure constants (i.e., the numbers defined by e_{A}e_{B} = ∑_{C} n_{AB}^{C}e_{C}) of the center of the group ring ℤ[G] with respect to the basis {e_{C}} defined in the proof of Corollary 2 above. Formula (8) therefore describes the ring structure of this commutative ring in terms of the character theory of G. This formula plays a role in mathematical physics in connection with the so-called “fusion algebras.”

Proof. If C is any conjugacy class of G, then the element e_{C} = ∑_{g∈C}[g] is central and hence, by Schur’s lemma, acts on any irreducible representation π of G as multiplication by a scalar ν_{π}(C). Since each element g ∈ C has the same trace χ_{π}(g) = χ_{π}(C), we find

|C| χ_{π}(C) = ∑_{g∈C} χ_{π}(g) = tr(π(e_{C}), V) = tr(ν_{π}(C) · Id, V) = ν_{π}(C) dim π

and hence

ν_{π}(C) = \frac{|C|}{dim π} χ_{π}(C) = \frac{χ_{π}(C)}{χ_{π}(1)} |C| .  (9)

Now we compute the trace of the action by left multiplication of the product of the elements e_{C_{1}}, …, e_{C_{k}} on both sides of (4). On the one hand, this product is the sum of the elements [c_{1} ⋯ c_{k}] with c_{i} ∈ C_{i} for all i, and since the trace of left multiplication by [g] on ℂ[G] is clearly |G| for g = 1 and 0 otherwise, the trace equals |G|N (G; C_{1}, …, C_{k}). On the other hand, the product of the e_{C_{i}} acts as scalar multiplication by ∏ ν_{π}(C_{i}) on π and hence also on the (dim π)^{2}-dimensional space End_{ℂ}(π). Formula (8) follows immediately. □

Theorem 2 has a clear topological interpretation. Let X be the 2-sphere with k (numbered) points P_{1}, …, P_{k} removed. Then π_{1}(X) is a (free) group on k generators x_{1}, …, x_{k} with x_{1} ⋯ x_{k} = 1, and N (G; C_{1}, …, C_{k}) simply counts the number of homomorphisms ρ from π_{1}(X) to G with ρ(x_{i}) ∈ C_{i} for each i. As explained in the text of the book, if G acts faithfully on some finite set F, then each such homomorphism corresponds to a (not necessarily connected) Galois covering of X with fibre F, Galois group G, and ramification points P_{i}, such that for each i the permutation of the elements of a fixed fibre induced by the local monodromy at P_{i} belongs to the conjugacy class C_{i}. Hence N (G; C_{1}, …, C_{k}) counts the coverings with these properties. Observe that the above-mentioned invariance of N (G; C_{1}, …, C_{k}) under permutation of its arguments is clear from this topological point of view.

A natural idea is now to generalize this to ramified coverings of Riemann surfaces of arbitrary genus g ≥ 0. In view of the structure of the fundamental group of a k-fold punctured surface of genus g, this boils down to computing the number

N_{g}(G; C_{1}, …, C_{k}) = #{(a_{1}, …, a_{g}, b_{1}, …, b_{g}, c_{1}, …, c_{k}) ∈ G^{2g} × C_{1} × ⋯ × C_{k} |
[a_{1}, b_{1}] ⋯ [a_{g}, b_{g}] c_{1} ⋯ c_{k} = 1} .

The result, given in the theorem below, turns out to be surprisingly simple, but was apparently not given in the classical group-theoretical literature and was discovered first in the context of mathematical physics ([DW], [FQ]). The proof is an almost immediate consequence of the special case g = 0.

Theorem 3. With the same notations as above, we have for all g ≥ 0

N_{g}(G; C_{1}, …, C_{k}) = |G|^{2g−1} |C_{1}| ⋯ |C_{k}| ∑_{χ} \frac{χ(C_{1}) ⋯ χ(C_{k})}{χ(1)^{k+2g−2}} .  (10)

Proof. Note that [a_{1}, b_{1}] ⋯ [a_{g}, b_{g}] = a_{1}(b_{1}a_{1}b_{1}^{−1})^{−1} ⋯ a_{g} (b_{g}a_{g}b_{g}^{−1})^{−1} and that, for a and a′ in the same conjugacy class A, there are |G|/|A| elements b ∈ G with bab^{−1} = a′. Hence

N_{g}(G; C_{1}, …, C_{k}) = ∑_{A_{1},...,A_{g}∈C} \frac{|G|}{|A_{1}|} ⋯ \frac{|G|}{|A_{g}|} N (G; A_{1}, A_{1}^{−1}, …, A_{g}, A_{g}^{−1}, C_{1}, …, C_{k}) .

Now applying Theorem 2 we find

N_{g}(G; C_{1}, …, C_{k}) = |G|^{g−1}|C_{1}| ⋯ |C_{k}|×

∑_{A_{1},...,A_{g}∈C} |A_{1}| ⋯ |A_{g}| ∑_{χ} \frac{χ(A_{1})\overline{χ(A_{1})} ⋯ χ(A_{g})\overline{χ(A_{g})}χ(C_{1}) ⋯ χ(C_{k})}{χ(1)^{k+2g−2}}

= |G|^{g−1}|C_{1}| ⋯ |C_{k}| ∑_{χ} \frac{χ(C_{1}) ⋯ χ(C_{k})}{χ(1)^{k+2g−2}} (∑_{A∈C} |A| χ(A) \overline{χ(A)})^{g} .

The theorem now follows from the case π = π′ of the orthogonality relation (5). □

We observe that, by formula (9), both Frobenius’s formula and its higher genus generalization can be written more naturally in terms of the eigenvalues ν_{π}(C) than the character values χ_{π}(C). In particular, equation (10) when expressed in terms of the ν_{π}(C) takes the simple form

N_{g}(G; C_{1}, …, C_{k}) = |G|^{2g−1} ∑_{π∈R} \frac{ν_{π}(C_{1}) ⋯ ν_{π}(C_{k})}{(dim π)^{2g−2}} .  (11)

2. Applications

In this section we give several applications of the character theory of finite groups in the case when G = S_{n}, the symmetric group on n letters. In this case the conjugacy classes are described simply by the partitions of n, the conjugacy class of an element g ∈ S_{n} with d_{1} one-cycles, d_{2} two-cycles, etc., corresponding to the partition λ = 1^{d_{1}}2^{d_{2}} ⋯ of n. It turns out that much of the part of the information which we are interested in can be captured by any of three polynomials Φ_{g}(X), P_{g}(r) or Q_{g}(k) which mutually determine each other but which encode the interesting combinatorial information about g in different ways.

2.1. Representations of S_{n} and canonical polynomials associated to partitions. In this subsection we define the three polynomials Φ_{g}(X), P_{g}(r) or Q_{g}(k) mentioned above and prove their main properties. Applications to several of the topics treated in the main text of the book will then be given in 2.2–2.4. Since each of these three polynomials depends only on the conjugacy class C of g ∈ S_{n} or equivalently only on the partition λ ⊢ n corresponding to C, we will also use the notations Φ_{C}(X), P_{C}(r) or Q_{C}(k) and Φ_{λ}(X), P_{λ}(r) or Q_{λ}(k).

We recall from §1.2 the standard irreducible representation St_{n} = ℂ^{n}/ℂ of S_{n} of dimension n − 1. We define Φ_{g}(X) as the characteristic polynomial of g on St_{n}:

Φ_{g}(X) = det(1 − g X, St_{n}) .  (12)

It is easy to see that, if g has the cycle structure 1^{d_{1}}2^{d_{2}} ⋯, then the characteristic polynomial of g on ℂ^{n} = St_{n} ⊕ 1 is simply ∏(1 − X^{i})^{d_{i}}, so in terms of λ we have

Φ_{λ}(X) = \frac{(1 − X)^{d_{1}}(1 − X^{2})^{d_{2}} ⋯}{1 − X}  (λ = 1^{d_{1}}2^{d_{2}} ⋯) .  (13)

This is the first of our three polynomials.

From linear algebra, we know that the coefficient of X^{r} in the characteristic polynomial of any endomorphism ϕ of a finite-dimensional vector space V equals (−1)^{r} times the trace of the endomorphism induced by ϕ on the rth exterior power ⋀^{r}(V). We therefore have

Φ_{g}(X) = ∑_{r=0}^{n−1}(−1)^{r} χ_{r}(g) X^{r} ,  (14)

where we have abbreviated

χ_{r}(g) := tr(g, π_{r}) ,  π_{r} := ⋀^{r}(St_{n})  (0 ≤ r ≤ n − 1) .

We shall show below that the representations π_{r} are irreducible and distinct, so the χ_{r} are distinct characters of S_{n}. We have χ_{r}(1) = dim π_{r} = \binom{n−1}{r}. Now, since there is a unique polynomial of degree n − 1 having specified values at any n specified points, we can define a polynomial P_{g}(r) by the requirements that deg P_{g} ≤ n − 1 and that

P_{g}(r) = \frac{χ_{r}(g)}{χ_{r}(1)} = \binom{n−1}{r}^{−1}χ_{r}(g)  (0 ≤ r ≤ n − 1) .  (15)

This is our second polynomial attached to (the conjugacy class of) g.

Finally, we recall the notations ℓ(g) = ∑ d_{i} and v(g) = ∑(i − 1)d_{i} for the number of cycles of an element g of S_{n} and for its complement v(g) = n − ℓ(g). (Again, since both depend only on the conjugacy class of g, we will use the alternative notations ℓ(C), v(C) or ℓ(λ), v(λ) as the situation requires.) Let σ denote the cyclic element (1 2 … n) of S_{n}. We then define

Q_{C}(k) = \frac{1}{|C|} ∑_{g∈C} k^{ℓ(gσ)}  (16)

for any conjugacy class C of S_{n}. This is our third polynomial.

Before stating the main result, which describes how each of the three polynomials just defined determines the other two, we need two simple (and well-known) lemmas concerning the representations π_{r}.

Lemma 4. The representations π_{r} = ⋀^{r}(St_{n}) (0 ≤ r ≤ n−1) of S_{n} are irreducible and distinct.

Proof. Set V = π_{0} ⊕ ⋯ ⊕ π_{n−1}, a representation of G = S_{n} of dimension 2^{n−1}. By the results of §1, we know that V can be decomposed uniquely as ⊕_{π∈R}m(π) π, where R is a set of representatives of the isomorphism classes of irreducible representations of G and the multiplicities m(π) are non-negative integers. Since V is by construction a sum of n nontrivial representations, we have ∑ m(π) ≥ n. Define χ_{V} : S_{n} → ℂ by χ_{V} (g) = tr(g, V). Then χ_{V} decomposes as χ_{V} = ∑ m(π)χ_{π}. We define a scalar product on the vector space of conjugacy-invariant functions f : S_{n} → ℂ by (f_{1}, f_{2}) = |G|^{−1} ∑_{g∈G} f_{1}(g)\overline{f_{2}(g)} . By equation (1) (first orthogonality relation) we know that the characters χ_{π} of the irreducible representations of G form an orthogonal basis for this vector space with respect to this scalar product, so (χ_{V} , χ_{V}) = ∑ m(π)^{2}. If we can show that (χ_{V} , χ_{V}) = n, it will follow that ∑(m(π)^{2}−m(π)) ≤ 0 and hence that each multiplicity m(π) equals 0 or 1, with m(π) = 1 for exactly n distinct irreducible representations of G, proving the lemma.

To calculate (χ_{V} , χ_{V}), we first use equations (14) and (13) to obtain that

χ_{V} (g) = ∑_{r=0}^{n−1} χ_{r}(g) = Φ_{g}(−1) = \{ \begin{matrix}2^{(d_{1}+d_{3}+···)−1} & if d_{2} = d_{4} = ⋯ = 0, \\ 0 & otherwise \end{matrix}

for g with the cycle structure ∏ i^{d_{i}}. Since the number of elements with this cycle structure is n!/ ∏(d_{i}! i^{d_{i}}), we obtain

(χ_{V} , χ_{V}) = \frac{1}{n!} ∑_{g∈S_{n}} |χ_{V} (g)|^{2} = \frac{1}{4} ∑_{\begin{matrix}d_{1}, d_{3}, d_{5},···≥0 \\ d_{1}+3d_{3}+5d_{5}+···=n \end{matrix}} \frac{4^{d_{1}+d_{3}+d_{5}+···}}{d_{1}! d_{3}! d_{5}! ⋯ 1^{d_{1}} 3^{d_{3}} 5^{d_{5}} ⋯}

= \frac{1}{4} · coefficient of x^{n} in ∏_{\begin{matrix}i≥1 \\ i odd \end{matrix}} e^{4x^{i}/i} = n ,

since 4 ∑_{i odd} \frac{x^{i}}{i} = 2 log \frac{1 + x}{1 − x} and (\frac{1 + x}{1 − x})^{2} = 1 + 4 ∑_{n≥1} nx^{n}. □

Lemma 5. The value of the character of an irreducible representation π of S_{n} on the conjugacy class of the cyclic element σ ∈ S_{n} is given by

χ_{π}(σ) = \{ \begin{matrix}(−1)^{r} & if π ≃ π_{r} for some r, 0 ≤ r ≤ n − 1, \\ 0 & otherwise. \end{matrix}

Proof. The first statement follows immediately from formulas (14) and (13), since

∑_{r=0}^{n−1}(−1)^{r} χ_{r}(σ) X^{r} = Φ_{σ}(X) = \frac{1 − X^{n}}{1 − X} = ∑_{r=0}^{n−1} X^{r} .

The second then follows immediately from the second orthogonality relation for characters, since ∑_{π∈R} |χ_{π}(σ)|^{2} = n!/(n − 1)! = n = ∑_{r=0}^{n−1} |χ_{r}(σ)|^{2} . □

Theorem 4. For any integer n ≥ 1 there are canonical linear isomorphisms between the three n-dimensional vector spaces

⟨1, X, …, X^{n−1}⟩ ,  ⟨1, r, …, r^{n−1}⟩ ,  ⟨k, k^{2}, …, k^{n}⟩ ,

such that the three polynomials Φ_{C}(X), P_{C}(r) and Q_{C}(k) correspond to one another for every conjugacy class C in S_{n}. These isomorphisms are given by Φ ↔ P ↔ Q, where Φ(X), P (r) and Q(k) are related by the generating function identities

Φ(X) = ∑_{r=0}^{n−1}(−1)^{r}\binom{n − 1}{r}P (r)X^{r} = (1 − X)^{n+1} ∑_{k=1}^{∞} Q(k) X^{k−1} ,  (17)

or alternatively in terms of bases of the three vector spaces by

(1 − X)^{n−1−s} ↔ \binom{n − 1 − r}{s}/\binom{n − 1}{s} ↔ \binom{s + k}{s + 1}  (0 ≤ s ≤ n − 1)  (18)

or

X^{s}(1 − X)^{n−1−s} ↔ (−1)^{s}\binom{r}{s}/\binom{n − 1}{s} ↔ \binom{k}{s + 1}  (0 ≤ s ≤ n − 1) . (19)

These isomorphisms are equivariant with respect to the three involutions ∗ defined by

Φ^{∗}(X) = (−X)^{n−1}Φ(1/X),  P^{∗}(r) = P (n − 1 − r),  Q^{∗}(k) = −Q(−k) , (20)

under which the polynomials Φ_{C}(X), P_{C}(r) and Q_{C}(k) are invariant or anti-invariant according to whether C is a conjugacy class of even or odd permutations.

Proof. The fact that the formulas (17) give isomorphisms between the spaces in question can be checked either directly or by using the binomial theorem to check that the collections of functions listed in (18) or in (19), each of which forms a basis for the relevant vector space, satisfy the identities in (17). The equivariance of the isomorphisms with respect to the involutions (20) follows most easily by noting that these involutions exchange the bases given in (18) and (19) up to a factor (−1)^{s}. The fact that Φ_{g}(X) and P_{g}(r) are related by the first formula in (17) follows immediately from equations (13) and (14) above. The statement about the invariance or anti-invariance of Φ_{g}, P_{g} and Q_{g} under the involutions ∗ is easy in each case (although of course it would suffice to verify only one of them and then use the rest of the theorem): for Φ_{g} it follows immediately from formula (13) and the fact that sgn(g) = (−1)^{v(g)} with v(g) = ∑(i − 1)d_{i}; for P_{g} it follows from (15) and the fact that ∧^{n−1−r}(St_{n}) is dual to the tensor product of ∧^{r}(St_{n}) with the sign representation εεε_{n} (because ∧^{d−r}V ⊗ ∧^{r}(V) →^{∧} ∧^{d}(V) is a perfect pairing for any d-dimensional vector space V and ∧^{n−1}(St_{n}) = εεε_{n}); and for Q_{g} it follows from the fact that ℓ(gσ) = n − v(gσ) ≡ v(g) + 1 (mod 2) for any g ∈ S_{n}. The only thing we have to show is therefore that the polynomials Φ_{C}(X) and Q_{C}(k) are related by the generating series identity

∑_{k=1}^{∞} Q_{C}(k) X^{k−1} = \frac{Φ_{C}(X)}{(1 − X)^{n+1}} ,  (21)

for any conjugacy class C in S_{n}. For this we use the following lemma.

Lemma 6. For any integers n, r and k with 0 ≤ r ≤ n − 1 we have

\frac{1}{n!} ∑_{g∈S_{n}} P_{g}(r) k^{ℓ(g)} = coefficient of X^{k−1} in \frac{X^{r}}{(1 − X)^{n+1}} .

Proof. By a calculation similar to the one in the proof of Lemma 4, we have

\frac{1}{n!} ∑_{g∈S_{n}} Φ_{g}(Y) k^{ℓ(g)} = ∑_{\begin{matrix}d_{1}, d_{2}, ... \\ d_{1}+2d_{2}+···=n \end{matrix}} \frac{k^{d_{1}+d_{2}+···}}{d_{1}! d_{2}! ⋯ 1^{d_{1}} 2^{d_{2}} ⋯} · \frac{(1 − Y)^{d_{1}}(1 − Y^{2})^{d_{2}} ⋯}{1 − Y}

= \frac{1}{1 − Y} · coefficient of u^{n} in ∏_{i=1}^{∞} exp(\frac{k(1 − Y^{i})u^{i}}{i} )

= \frac{1}{1 − Y} · coefficient of u^{n} in (\frac{1 − uY}{1 − u} )^{k}

= coefficient of X^{k−1} in \frac{(1 − XY)^{n−1}}{(1 − X)^{n+1}} ,  (22)

where the last equality follows either by using residue calculus to get

\frac{1}{1 − Y} Res_{u=0}((\frac{1 − uY}{1 − u} )^{k} \frac{du}{u^{n+1}} ) = − Res_{X=1}(\frac{(1 − XY)^{n−1}}{(1 − X)^{n+1}} \frac{dX}{X^{k}} )  (u = \frac{1 − X}{1 − XY} )

= + Res_{X=0}(\frac{(1 − XY)^{n−1}}{(1 − X)^{n+1}} \frac{dX}{X^{k}} )

or else from the geometric series identity

∑_{k=1}^{∞} X^{k−1} (\frac{1 − uY}{1 − u} )^{k} = \frac{1 − uY}{1 − u − X + uXY} = \frac{1}{1 − X} + (1 − Y) ∑_{n=1}^{∞} \frac{(1 − XY)^{n−1}}{(1 − X)^{n+1}} u^{n} .

The lemma follows by comparing the coefficients of (−1)^{r}\binom{n−1}{r}Y^{r} on both sides of (22). □

Remark. Lemma 6 implies that

\frac{1}{n!} ∑_{g∈S_{n}} P_{g}(r) k^{ℓ(g)} = \binom{k + n − r − 1}{n} − \binom{n − r − 1}{n}

as polynomials in r and n, since both sides of this identity are polynomials in k and r, both have degree ≤ n − 1 in r, and they agree for k ∈ ℕ and for r = 0, 1, …, n − 1.

We can now complete the proof of equation (21) and hence of Theorem 4. Frobenius’s formula (Theorem 2) in the case k = 3 can be rewritten in the form

\frac{1}{|C|} ∑_{c∈C} F (bc) = ∑_{π} χ_{π}(b)χ_{π}(C) (\frac{1}{|G|} ∑_{A∈C} |A| \frac{χ_{π}(A)}{χ_{π}(1)} F (A^{−1}))

for any finite group G, conjugacy classes A and C of G, and class function (= conjugacy-invariant function) F : G → ℂ, where the sum is over all irreducible representations of G. Specializing to G = S_{n} and b = σ and using Lemma 5, we find

\frac{1}{|C|} ∑_{c∈C} F (σc) = ∑_{r=0}^{n−1}(−1)^{r}χ_{r}(C) (\frac{1}{n!} ∑_{g∈G} P_{g}(r) F (g^{−1})) .

Now specializing further to F (g) = k^{ℓ(g)} and using Lemma 6 and equation (14) gives

Q_{C}(k) = coefficient of X^{k−1} in \frac{Φ_{C}(X)}{(1 − X)^{n+1}} . □

We mention two simple consequences of Theorem 4 which will be used later.

Corollary 1. Let λ = 1^{d_{1}}2^{d_{2}} ⋯ be a partition of n. Then the polynomial P_{λ}(r) has degree v(λ) = ∑(i − 1)d_{i} and leading coefficient (−1)^{v(λ)}K(λ), where

K(λ) = \frac{(n − 1 − v(λ))!}{(n − 1)!} 1^{d_{1}}2^{d_{2}} ⋯ n^{d_{n}} .  (23)

The polynomial Q_{λ}(k) has degree v(λ) + 1 and leading coefficient (∏ i^{d_{i}})/(v(λ) + 1)! .

Proof. From equation (13) we see that Φ_{λ}(X) ∼ \frac{(n−1)!}{(n−1−v(λ))!} K(λ) (1 − X)^{n−1−v(λ)} as X → 1. But this means that Φ_{λ}(X) is a linear combination of the basis elements (18) with s ≤ v(λ), with the coefficient for s = v(λ) being \frac{(n−1)!}{(n−1−v(λ))!} K(λ). The correspondence (18) then tells us that P_{λ} and Q_{λ} have the degrees and leading coefficients stated. □

Corollary 2. The polynomial Q_{λ}(k) takes integer values for k ∈ ℤ. Moreover, the value of Q_{λ}(k) for k ∈ ℕ depends only on the numbers n − d_{1}, d_{2}, …, d_{k−1}, the first few being

Q_{λ}(0) = 0, Q_{λ}(1) = 1, Q_{λ}(2) = n + 2 − d_{1}, Q_{λ}(3) = \binom{n + 3 − d_{1}}{2} − d_{2} .

Proof. Equations (21) and (13) give

Q_{C}(k) = coefficient of X^{k−1} in (1−X)^{d_{1}−n−2}(1−X^{2})^{d_{2}}(1−X^{3})^{d_{3}} ⋯ (1−X^{k−1})^{d_{k−1}} . □

Remark. The fact that deg Q_{λ} ≤ v(λ) says that ℓ(gσ) ≤ v(g) for all g ∈ S_{n}. Equivalently, v(g) + v(gσ) ≥ n − 1 = v(σ). This is a special case of the general fact that v(g_{1}) + v(g_{2}) ≥ v(g_{3}) for any three elements g_{1}, g_{2}, g_{3} ∈ S_{n} with product 1, which can be seen most easily by noticing that v(g_{i}) is the codimension of the fixed point set of g_{i} acting on ℂ^{n} (or on its irreducible subspace St_{n}) and that codimensions of subspaces behave subadditively. The statement that the polynomial Q_{λ}(k) depends only on n − d_{1} and the d_{i} with i ≥ 2 says that it is stable under the inclusions S_{n} ⊂ S_{n+1} and hence depends only on the class of g in S_{∞}. This is not difficult to see directly from the definition, but there does not seem to be any obvious reason why the value of Q_{λ}(k) for k ∈ ℕ depends only on the d_{i} with i < k or why it is an integer.

2.2. Examples. We give a number of examples of the polynomials introduced in §2.1 for special conjugacy classes and for small values of n.

Trivial element: g = 1. Here the cycle structure is simply 1^{n}, so equation (13) gives Φ_{1}(X) = (1 − X)^{n−1}, while from equations (4) and (5) we immediately get P_{1}(r) = 1 and Q_{1}(k) = k.

Transposition: T = (12). Now the cycle structure is 1^{n−2}2, so equation (13) gives

Φ_{T} (X) = (1 − X)^{n−3}(1 − X^{2}) = (1 − X)^{n−2}(1 + X) .  (24)

From equation (14) we therefore obtain

χ_{r}(T) = \binom{n − 2}{r} − \binom{n − 2}{r − 1} = \binom{n − 3}{r} − \binom{n − 3}{r − 2}

(with the obvious conventions when r < 2), so from (15) and the formula χ_{r}(1) = \binom{n−1}{r} we obtain

P_{T} (r) = 1 − \frac{2r}{n − 1}  (25)

while equation (17) or (18) or (19) gives

Q_{T} (k) = k^{2} .

Note that this last formula, unlike the formulas for Φ_{T} (X) and P_{T} (r), is independent of n. This is a special case of the above-mentioned fact that Q_{g}(k) is stable under S_{n} ⊂ S_{n+1} .

Cyclic permutation: σ = (12 ⋯ n). Here the cycle structure is simply n^{1}, so, as we have already seen, Φ_{σ}(X) = 1 + X + ⋯ + X^{n−1} and χ_{r}(σ) = (−1)^{r}. However, the explicit forms of the polynomials P_{σ} and Q_{σ} are quite complicated, as can be seen from the examples for n = 5 and 6 below.

Free involution: τ = (12)(34) ⋯ (n − 1 n). Here n must be even, say n = 2m. The cycle structure of the conjugacy class of τ is 2^{m}, so (13) gives

Φ_{τ} (X) = \frac{(1 − X^{2})^{m}}{1 − X} = (1 + X)(1 − X^{2})^{m−1}  (26)

and hence

χ_{r}(τ) = (−1)^{[(r+1)/2]} \binom{m − 1}{[r/2]} ,

but here again the polynomials P_{τ} and Q_{τ} have no simple closed form.

Small n. Finally, to give the reader a better feel for the Φ_{λ} ↔ P_{λ} ↔ Q_{λ} correspondence, we give a complete table of these three polynomials for partitions of n with 1 ≤ n ≤ 6. For convenience we tabulate the polynomial P̃_{λ}(t) := P (\frac{n−1}{2} − t) instead of P_{λ}(r), since by the last statement of Theorem 4 this is an even or an odd polynomial in t for all λ. The stability of Q_{λ} mentioned in the remark at the end of the last section is visible in this table: for example, the first seven entries in the column giving Q_{λ}(k) for n = 6 agree with the values for n = 5.

\begin{matrix}n & λ & _{P_{λ}}(t) & Q_{λ}(k) & Φ_{λ}(X) \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ 1 & 1^{1} & 1 & k & 1 \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ 2 & 1^{2} & 1 & k & 1 − X \\ 2^{1} & & 2t & & & k^{2} & & 1 + X \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ 3 & 1^{3} & 1 & k & 1 − 2X + X^{2} \\ 1^{1}2^{1} & & t & & & k^{2} & & 1  − X^{2} \\ 3^{1} & & \frac{1}{2} (3t^{2} − 1) & & & \frac{1}{2} (k^{3} + k) & & 1 + X + X^{2} \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ 4 & 1^{4} & 1 & k & 1 − 3X + 3X^{2} − X^{3} \\ 1^{2}2^{1} & & \frac{2}{3} t & & & k^{2} & & 1 − X − X^{2} + X^{3} \\ 1^{1}3^{1} & & \frac{1}{8} (4t^{2} − 1) & & & \frac{1}{2} (k^{3} + k) & & 1  − X^{3} \\ 2^{2} & & \frac{1}{6} (4t^{2} − 3) & & & \frac{1}{3} (2k^{3} + k) & & 1 + X − X^{2} − X^{3} \\ 4^{1} & & \frac{1}{6} (4t^{3} − 5t) & & & \frac{1}{6} (k^{4} + 5k^{2}) & & 1 + X + X^{2} + X^{3} \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ 5 & 1^{5} & 1 & k & 1 − 4X + 6X^{2} − 4X^{3} + X^{4} \\ 1^{3}2^{1} & & \frac{1}{2} t & & & k^{2} & & 1 − 2X  + 2X^{3} − X^{4} \\ 1^{2}3^{1} & & \frac{1}{4} t^{2} & & & \frac{1}{2} (k^{3} + k) & & 1 − X  − X^{3} + X^{4} \\ 1^{1}2^{2} & & \frac{1}{3} (t^{2} − 1) & & & \frac{1}{3} (2k^{3} + k) & & 1  − 2X^{2}  + X^{4} \\ 1^{1}4^{1} & & \frac{1}{6} (t^{3} − t) & & & \frac{1}{6} (k^{4} + 5k^{2}) & & 1  − X^{4} \\ 2^{1}3^{1} & & \frac{1}{4} (t^{3} − 2t) & & & \frac{1}{4} (k^{4} + 3k^{2}) & & 1 + X  − X^{3} − X^{4} \\ 5^{1} & & \frac{1}{24} (5t^{4} − 15t^{2} + 4) & & & \frac{1}{24} (k^{5} + 15k^{3} + 8k) & & 1 + X + X^{2} + X^{3} + X^{4} \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ 6 & 1^{6} & 1 & k & 1 − 5X + 10X^{2} − 10X^{3} + 5X^{4} − X^{5} \\ 1^{4}2^{1} & & \frac{2}{5} t & & & k^{2} & & 1 − 3X + 2X^{2} + 2X^{3} − 3X^{4} + X^{5} \\ 1^{3}3^{1} & & \frac{1}{80} (12t^{2} + 5) & & & \frac{1}{2} (k^{3} + k) & & 1 − 2X + X^{2} − X^{3} + 2X^{4} − X^{5} \\ 1^{2}2^{2} & & \frac{1}{20} (4t^{2} − 5) & & & \frac{1}{3} (2k^{3} + k) & & 1 − X − 2X^{2} + 2X^{3} + X^{4} − X^{5} \\ 1^{2}4^{1} & & \frac{1}{60} (4t^{3} − t) & & & \frac{1}{6} (k^{4} + 5k^{2}) & & 1 − X  − X^{4} + X^{5} \\ 1^{1}2^{1}3^{1} & & \frac{1}{90} (4t^{3} − 9t) & & & \frac{1}{4} (k^{4} + 3k^{2}) & & 1  − X^{2} − X^{3}  + X^{5} \\ 1^{1}5^{1} & & \frac{1}{384} (16t^{4} − 40t^{2} + 9) & & & \frac{1}{24} (k^{5} + 15k^{3} + 8k) & & 1  − X^{5} \\ 2^{3} & & \frac{1}{30} (4t^{3} − 13t) & & & \frac{1}{3} (k^{4} + 2k^{2}) & & 1 + X − 2X^{2} − 2X^{3} + X^{4} + X^{5} \\ 2^{1}4^{1} & & \frac{1}{240} (16t^{4} − 64t^{2} + 15) & & & \frac{1}{15} (k^{5} + 10k^{3} + 4k) & & 1 + X  − X^{4} − X^{5} \\ 3^{2} & & \frac{1}{640} (48t^{4} − 216t^{2} + 115) & & & \frac{1}{40} (3k^{5} + 25k^{3} + 12k) & & 1 + X + X^{2} − X^{3} − X^{4} − X^{5} \\ 6^{1} & & \frac{1}{960} (48t^{5} − 280t^{3} + 259t) & & & \frac{1}{120} (k^{6} + 35k^{4} + 84k^{2}) & & 1 + X + X^{2} + X^{3} + X^{4} + X^{5} \end{matrix}

2.3. First Application: Enumeration of polygon gluings. This is the combinatorial question which was discussed in Chapter 3 in connection with the evaluation of the (orbifold) Euler characteristic of the moduli space of curves of genus g. The problem was to count the number ε_{g}(m) of ways to identify in pairs (with reverse orientation) the sides of a (2m)-gon such that the closed oriented surface obtained has a given genus g. Clearly this is the same as the number of free involutions in S_{2m} whose product with the standard cyclic permutation σ has m + 1 − 2g cycles, so formula (16) gives

Q_{τ} (k) = \frac{1}{(2m − 1)!!} ∑_{0≤g≤m/2} ε_{g}(m) k^{m+1−2g} ,  (27)

where τ denotes any free involution (and where we have used that the conjugacy class of τ has cardinality (2m − 1)!!). On the other hand, from equations (21) and (26) we get

∑_{k=1}^{∞} Q_{τ} (k) X^{k−1} = \frac{Φ_{τ} (X)}{(1 − X)^{2m+1}} = \frac{(1 + X)^{m}}{(1 − X)^{m+2}} ,

which we can rewrite equivalently by using the same calculation as in the last line of (22) (with n replaced by m + 1 and Y by −1) as

Q_{τ} (k) = \frac{1}{2} · coefficient of u^{m+1} in (\frac{1 + u}{1 − u})^{k} .

Since the sum on the right-hand side of (27) is the polynomial denoted T_{m}(k) in §3.1, this reproduces the evaluation of ε_{g}(m) in terms of generating functions given in Theorem 3.1.5.

The proof just given follows the exposition in [Z], where the identity (21) was proved and a few other applications were given. We mention two briefly:

• the probability that the product of two random cyclic permutations in S_{n} has exactly ℓ cycles is (1+(−1)^{n−ℓ}) times the coefficient of x^{ℓ} in \binom{x+n}{n+1}. In particular, for n odd the probability that such a product is cyclic equals \frac{2}{n+1}, as opposed to the probability that a random even element of S_{n} is cyclic, which equals \frac{2}{n} .

• the number of representations of an arbitrary even element of S_{n} as a product of two cyclic permutations is ≥ \frac{2(n−1)!}{n+2}, as opposed to the average number of such representations for even permutations, which equals \frac{2(n−1)!}{n} .

2.4. Second Application: The Goulden-Jackson formula. Our second application, again reproducing a result proved by a different method within the main text of the book, is the formula of Goulden-Jackson given in various forms in Theorems 1.5.12, 1.5.15, 1.6.6 and 5.2.2. The problem, in our present language, is to count the “Frobenius number” N (S_{n}; C_{0}, C_{1}, ⋯, C_{k}) of (k + 1)-tuples (c_{0}, …, c_{k}) ∈ C_{0} × ⋯ × C_{k} when C_{0} is the class of the cyclic element σ ∈ S_{n} and C_{1}, …, C_{k} are arbitrary conjugacy classes in S_{n}. The Goulden-Jackson formula says that this number is 0 if v = v(C_{1}) + ⋯ + v(C_{k}) is less than n − 1 and gives an explicit formula for it when v(C_{1}) + ⋯ + v(C_{k}) = n − 1. We give a somewhat more general result.

Theorem 5. Let C_{1}, …, C_{k} be arbitrary conjugacy classes in S_{n} and C_{0} the class of the cyclic element σ. Then

N (S_{n}; C_{0}, C_{1}, …, C_{k}) = \frac{(−1)^{n−1}}{n} |C_{1}| ⋯ |C_{k}| · Δ^{n−1}(P_{C_{1}} ⋯ P_{C_{k}})(0) ,  (28)

where P_{C_{i}}(r) is the polynomial of degree v(C_{i}) associated to the conjugacy class C_{i} as in §2.1 and Δ denotes the forward differencing operator ΔP (r) = P (r + 1) − P (r).

For the conjugacy class C of S_{n} corresponding to a partition λ = 1^{d_{1}} ⋯ n^{d_{n}} of n, let us write N(C) for the number N(λ) = \frac{(d_{1}+···+d_{n}−1)!}{d_{1}! ··· d_{n}!} defined in 1.5.11. Then we have:

Corollary (Goulden-Jackson formula). Let the C_{i} be as in the theorem. Then the number N (S_{n}; C_{0}, C_{1}, …, C_{k}) vanishes if the number v := v(C_{1}) + ⋯ + v(C_{k}) is less than n − 1 and is given by

\frac{1}{(n − 1)!} N (S_{n}; C_{0}, C_{1}, …, C_{k}) = n^{k−1} N(C_{1}) ⋯ N(C_{k})  (29)

if v = n − 1.

Proof. The theorem is an immediate consequence of Frobenius’s formula (Theorem 2) and Lemma 5, which says that χ(C_{0}) equals (−1)^{r} if χ = χ_{r} and vanishes for all other irreducible characters, together with definition (15), which together give

N (S_{n}; C_{0}, C_{1}, …, C_{k}) = \frac{1}{n} |C_{1}| ⋯ |C_{k}| ∑_{r=0}^{n−1}(−1)^{r} \binom{n − 1}{r} P_{C_{1}}(r) ⋯ P_{C_{k}}(r) .

The corollary follows immediately from the theorem together with Corollary 1 above and the formula |C_{i}|K(λ_{i}) = nN(λ_{i}) (compare equation (23) and the definition of N(λ)), since the polynomial P_{C_{1}}(r) ⋯ P_{C_{k}}(r) has degree v and the mth difference of a polynomial of degree v is 0 for m > v and equal to m! times the leading coefficient of the polynomial if m = v. □

Remarks. 1. The fact that N (S_{n}; C_{0}, C_{1}, …, C_{k}) = 0 unless v ≥ n − 1 is also obvious from the remark at the end of §2.1, which says that the function v satisfies the triangle inequality and hence necessarily v(c_{1})+⋯+v(c_{k}) ≥ v(c_{0}) if c_{0}c_{1} ⋯ c_{k} = 1. It also follows from the topological interpretation of N (S_{n}; C_{0}, C_{1}, …, C_{k}) as the counting function for ramified coverings of S^{2} with ramification types C_{i}, since v − n − 1 equals the Euler characteristic of the total space of the covering, which has the form 2−2g ≤ 2 because a covering one of whose ramification types is cyclic is necessarily connected. This shows also that the number N (S_{n}; C_{0}, C_{1}, …, C_{k}) vanishes unless v ≡ n − 1 (mod 2). To see this from Theorem 5, it is convenient to rewrite formula (28) in the form

\frac{n N (S_{n}; C_{0}, C_{1}, …, C_{k})}{|C_{1}| ⋯ |C_{k}|} = Δ_{+}^{n−1}(P̃_{C_{1}} ⋯ P̃_{C_{k}})(0) ,  (30)

where P̃_{C}(t) = P_{C}(\frac{n−1}{2} − t) is the shifted version of P_{C}(r) mentioned in §2.2 and Δ_{+} is the symmetric difference operator Δ_{+}f(t) = f(t + \frac{1}{2}) − f(t − \frac{1}{2}). This expression obviously vanishes if v ≢ n − 1 (mod 2) because of the symmetry property P̃_{C}(−t) = (−1)^{v(C)}P̃_{C}(t) and the fact that Δ_{+} reverses the parity of an even or odd function.

2. As a special case, we can take C_{1} = ⋯ = C_{k} = [T], the class of transpositions in S_{n}. Then P̃_{C_{i}}(t) = \frac{2t}{n−1} by formula (25), so equation (30) gives

N (S_{n}; σ, \underbrace{T, …, T}_{k}) = n^{k−1} Δ_{+}^{n−1}(t^{k})|_{t=0} .

Using the identity

Δ_{+}^{n−1}(t^{k})|_{t=0} = ∑_{r=0}^{n−1}(−1)^{r}\binom{n − 1}{r} (\frac{n − 1}{2} − r)^{k} = \frac{d^{k}}{du^{k}} (e^{u/2} − e^{−u/2})^{n−1}]|_{u=0}

and the residue theorem, we can write this equivalently as

N (G; σ, \underbrace{T, …, T}_{k}) = k! · n^{k−1} · S_{g}(n)  for k = n − 1 + 2g  (g ≥ 0),  (31)

where S_{g}(n) is the polynomial of degree g in n given by

S_{g}(n) = coefficient of u^{2g} in (\frac{sinh u/2}{u/2})^{n−1}

= \frac{n − 1}{n − 1 + 2g} · coefficient of s^{2g} in (\frac{s/2}{asinh s/2})^{n+2g−1} ,  (32)

the first values of which are given by

S_{0}(n) = 1, S_{1}(n) = \frac{n − 1}{24} , S_{2}(n) = \frac{(n − 1)(5n − 7)}{5760} .  (33)

Formula (31) for N (S_{n}; σ, T, …, T) was given in [SSV].

3. Another observation is that, from formula (10) together with the fact that χ(σ) = χ(σ)^{3} for all irreducible characters χ of S_{n} (Lemma 5), we have the formula

N_{g}(S_{n}; σ, C_{1}, …, C_{k}) = n^{2g} N (S_{n}; \underbrace{σ, …, σ}_{2g+1}, C_{1}, …, C_{k})  (34)

for the “generalized Frobenius number” of Theorem 3, for any integer g ≥ 0 and any conjugacy classes C_{1}, …, C_{k} in S_{n}. This allows one to generalize Theorem 5 to the case of ramified coverings of a Riemann surface of arbitrary genus with cyclic ramification at at least one point.

In view of the very simple form of equation (34), it might be of interest to give a direct combinatorial or topological proof, without using character theory.

In the rest of this subsection, we show how one can use Theorem 5 to give explicit formulas for N (S_{n}; C_{0}, C_{1}, …, C_{k}) for arbitrary values of v. The calculation and the results are considerably simplified if we use the symmetric formula (30) instead of (28), but still rapidly become complicated as the number 2g = v − n + 1 grows.

The main step in the calculation is a refinement of Corollary 1 of Theorem 4 giving more leading terms of P_{λ}(r) (or equivalently, of P̃_{λ}(t)) for an arbitrary conjugacy class λ of S_{n}. Write λ = n_{1} + ⋯ + n_{s} = 1^{d_{1}}2^{d_{2}} ⋯ and define invariants ℓ_{h}(λ) (higher moments) of λ by

ℓ_{h}(λ) = n_{1}^{h} + ⋯ + n_{s}^{h} = ∑_{i≥1} i^{h} d_{i}  (h = 0, 1, …),  (35)

so that ℓ_{0}(λ) = ℓ(λ), ℓ_{1}(λ) = n. Assign to ℓ_{h}(λ) the weight h. Then we have:

Lemma 7. The polynomial P̃_{λ}(t) = P_{λ}(\frac{n−1}{2} − t) has the form

P̃_{λ}(t) = K(λ) (1 + a_{1}(λ) t^{v(λ)−2} + a_{2}(λ) t^{v(λ)−4} + ⋯) ,

where K(λ) is given by (23) and each a_{j}(λ) is a universal polynomial of weighted degree ≤ 2j in n and the invariants ℓ_{h} = ℓ_{h}(λ) with h even, the first two values being

a_{1}(λ) = (ℓ_{0} + 1)ℓ_{0} \frac{ℓ_{2} − 1}{24} − \frac{(n − 1)n(n + 1)}{24} ,
a_{2}(λ) = (ℓ_{0} + 3)(ℓ_{0} + 2)(ℓ_{0} + 1)ℓ_{0} \frac{5(ℓ_{2} − 1)^{2} − 2(ℓ_{4} − 1)}{5760}

− \frac{(n − 1)n(n + 1)}{24} (ℓ_{0} + 1)ℓ_{0} \frac{ℓ_{2} − 1}{24} + \frac{(n − 3)(n − 2)(n − 1)n(n + 1)(5n + 7)}{5760} .

Proof. We already know that P̃_{λ}(t) is a polynomial of degree and parity v(λ) and hence has the form K(λ) ∑_{j} a_{j}(λ)t^{v(λ)−2j} for some numbers a_{j}(λ). Define a power series Φ̃_{λ}(u) ∈ ℚ[[u]] by Φ̃_{λ}(u) = e^{(n−1)u/2} Φ_{λ}(e^{−u}). Then equations (14) and (15) give

Φ̃_{λ}(u) = ∑_{r=0}^{n−1}(−1)^{r} \binom{n − 1}{r} P̃_{λ}(\frac{n − 1}{2} − r) e^{( \frac{n−1}{2} −r)u}

= K(λ) ∑_{j≥0} a_{j}(λ) \frac{d^{v(λ)−2j}}{du^{v(λ)−2j}} [∑_{r=0}^{n−1}(−1)^{r} \binom{n − 1}{r} e^{( \frac{n−1}{2} −r)u}]

= K(λ) ∑_{j≥0} a_{j}(λ) \frac{d^{v(λ)−2j}}{du^{v(λ)−2j}} [(e^{u/2} − e^{−u/2})^{n−1}]

= K(λ) ∑_{j≥0} a_{j}(λ) \frac{d^{v(λ)−2j}}{du^{v(λ)−2j}} [∑_{g≥0} S_{g}(n) u^{n−1+2g}]

= (n − 1)! K(λ) ∑_{j, g≥0} a_{j}(λ) Ŝ_{g}(n) \frac{u^{n−v(λ)−1+2j+2g}}{(n − v(λ) − 1 + 2j + 2g)!} ,

where S_{g}(n) is as in (32) and

Ŝ_{g}(n) = \frac{(n − 1 + 2g)!}{(n − 1)!} S_{g}(n) = \frac{1}{(n − 1)!} Δ_{+}^{n−1}(t^{n−1+2g})|_{t=0} ,  (36)

a polynomial of degree 3g in n. On the other hand, from formula (13) and the expansion

e^{x/2} − e^{−x/2} = x exp(∑_{h=2}^{∞} \frac{B_{h}}{h} \frac{x^{h}}{h!} ) = x exp(\frac{x^{2}}{24} − \frac{x^{4}}{2880} + ⋯) ,

where B_{h} denotes the hth Bernoulli number, we have

Φ̃_{λ}(u) = ∏_{i≥1}(e^{iu/2} − e^{−iu/2})^{d_{i}^{∗}}

= (∏_{i} i^{d_{i}}) · u^{ℓ(λ)−1} · exp(∑_{h=2}^{∞} \frac{B_{h}}{h} ℓ_{h}^{∗}(λ) \frac{x^{h}}{h!} )

= \frac{(n − 1)! K(λ)}{(n − 1 − v(λ))!} u^{n−v(λ)−1} (1 + \frac{ℓ_{2}^{∗}(λ)}{24} u^{2} + \frac{5ℓ_{2}^{∗}(λ)^{2} − 2ℓ_{4}^{∗}(λ)}{5760} u^{4} + ⋯) ,

where d_{i}^{∗} = d_{i} − δ_{i,1} and ℓ_{h}^{∗}(λ) = ∑_{i≥1} i^{h}d_{i}^{∗} = ℓ_{h}(λ) − 1. Comparing with the previous formula for Φ̃_{λ}(u), we find

a_{0}(λ) = 1 ,
a_{1}(λ) + Ŝ_{1}(n) = \frac{(n + 1 − v(λ))!}{(n − 1 − v(λ))!} \frac{ℓ_{2}^{∗}(λ)}{24} ,
a_{2}(λ) + Ŝ_{1}(n) a_{2}(λ) + Ŝ_{2}(n) = \frac{(n + 3 − v(λ))!}{(n − 1 − v(λ))!} \frac{5ℓ_{2}^{∗}(λ)^{2} − 2ℓ_{4}^{∗}(λ)}{5760} ,

etc. The lemma now follows by induction on j. □

Returning to the situation of Theorem 5, we consider arbitrary conjugacy classes C_{i} ↔ λ_{i} (i = 1, …, k) of S_{n}. From Lemma 7 we get

∏_{i=1}^{k} P̃_{λ_{i}}(t) = (∏_{i=1}^{k} K(λ_{i})) (t^{v} + a_{1}(λ_{1}, …, λ_{k}) t^{v−2} + a_{2}(λ_{1}, …, λ_{k}) t^{v−4} + ⋯)

where v = ∑ v(λ_{i}) as before and

a_{1}(λ_{1}, …, λ_{k}) = ∑_{1≤i≤k} a_{1}(λ_{i}) , a_{2}(λ_{1}, …, λ_{k}) = ∑_{1≤i<j≤k} a_{1}(λ_{i})a_{2}(λ_{j}) + ∑_{1≤i≤k} a_{2}(λ_{i}) ,

etc. Substituting this into equation (30) and recalling that |C_{i}|K(C_{i}) = nN(C_{i}), we find

\frac{1}{(n − 1)!} \frac{N (S_{n}; C_{0}, C_{1}, …, C_{k})}{n^{k−1} N(λ_{1}) ⋯ N(λ_{k})} = \frac{1}{(n − 1)!} Δ_{+}^{n−1}(∑_{j≥0} a_{j}(λ_{1}, …, λ_{k}) t^{v−2j})|_{t=0}

= ∑_{j=0}^{g} Ŝ_{g−j}(n) a_{j}(λ_{1}, …, λ_{k}) (v = n − 1 + 2g),

where the polynomials Ŝ_{g−j}(n) are given by (36) and (32). This is the desired generalization of the Goulden-Jackson formula (29) to the case of ramified coverings of S^{2} by surfaces of arbitrary genus g with at least one cyclic ramification point. We note the case g = 1 separately since it is not too complicated:

Corollary. With the notations of Theorem 5 and its corollary, we have

\frac{1}{(n − 1)!} \frac{N (S_{n}; C_{0}, C_{1}, …, C_{k})}{n^{k−1} N(C_{1}) ⋯ N(C_{k})} = ∑_{i=1}^{k} ℓ(C_{i}) (ℓ(C_{i}) + 1) \frac{ℓ_{2}(C_{i}) − 1}{24} − (k − 1) \frac{n^{3} − n}{24}

if v(C_{1}) + ⋯ + v(C_{k}) = n + 1, where ℓ_{2}(C_{i}) denotes the sum of the squares of the lengths of the cycles in the conjugacy class C_{i}.

2.5. Third Application: “Mirror symmetry in dimension one”. “Mirror symmetry”, originally discovered in the context of mathematical physics (string theory) and intensively studied during recent years, is a predicted duality between certain families of Calabi-Yau manifolds. It manifests itself on several levels, one of which has to do with the counting functions (Gromov-Witten invariants) that enumerate the holomorphic mappings C → X of complex curves C into a Calabi-Yau manifold X representing a given class in the second homology group of X.

A Calabi-Yau manifold of dimension n is a complex (projective) n-manifold X such that the space of holomorphic i-forms on X is 0-dimensional for 0 < i < n and 1-dimensional for i = n. The original mirror symmetry phenomenon concerned the case n = 3, but it was observed by Dijkgraaf [D1] that it also occurs in the far simpler case n = 1. Here “Calabi-Yau” is just a synonym of “genus one”, and the coefficients of the counting functions merely enumerate the generic mappings Y → X, appropriately weighted, from curves of genus g to a given complex curve X of genus 1, where both g and the degree n of the mapping are fixed. Here “generic” means that exactly two sheets of the covering come together over every ramification point, so that each point of X has either n or n − 1 preimages, and “appropriately weighted” means, as usual, that each covering is counted with a weight equal to the reciprocal of the number of its automorphisms over X. Note that, by the Riemann-Hurwitz formula, a covering of the above type will be ramified over precisely 2g − 2 points of X.

The problem is therefore to compute h^{0}(2g − 2, n), where h^{0}(k, n) denotes the number of (weighted) isomorphism classes of connected n-sheeted coverings of a given Riemann surface X of genus 1 with generic ramification over k given points of X. If we denote by h(k, n) the corresponding number without the connectedness condition, then a standard argument gives the relation

∑_{n>0} ∑_{k≥0} h^{0}(k, n) \frac{X^{k}}{k!} q^{n} = log(1 + ∑_{n>0} ∑_{k≥0} h(k, n) \frac{X^{k}}{k!} q^{n}) ,  (37)

while another standard argument gives the formula

h(k, n) = \frac{1}{n!} N_{1}(S_{n}; \underbrace{T, …, T}_{k})  (38)

for h(k, n) in terms of the generalized Frobenius number N_{1}(S_{n}; T, …, T) of (k + 2)-tuples (a, b, c_{1}, …, c_{k}) ∈ (S_{n})^{2} × [T]^{k} with [a, b]c_{1} ⋯ c_{k} = 1 as introduced in §1.3. (The number h^{0}(n, k) counts the tuples which generate a subgroup of S_{n} acting transitively on {1, …, n}, but since we have no closed formula for this we must use (37) and (38) instead.)

From formulas (38) and (11) with g = 1 we find

h(k, n) = ∑_{π∈R_{n}} ν_{π}(T)^{k}

where R_{n} as in §1.2 denotes the set of irreducible representations of S_{n} and ν_{π}(T) (π ∈ R_{n}) as in §1.2 and §1.3 is the eigenvalue of ∑_{g∈[T]_{n}} g on the representation π. From this we obtain

∑_{k≥0} h(k, n) \frac{X^{k}}{k!} = ∑_{π∈R_{n}} e^{ν_{π}(T)X} = H_{n}(e^{X}) ,  (39)

where

H_{n}(u) = ∑_{π∈R_{n}} u^{ν_{π}(T)} ∈ ℤ[u, u^{−1}] ,

a symmetric Laurent polynomial in u which for small values of n can be computed directly from the information given in §1.2:

H_{2}(u) = u + u^{−1} ,
H_{3}(u) = u^{3} + 1 + u^{−3} ,
H_{4}(u) = u^{6} + u^{2} + 1 + u^{−2} + u^{−6} ,
H_{5}(u) = u^{10} + u^{5} + u^{2} + 1 + u^{−2} + u^{−5} + u^{−10} ,
H_{6}(u) = u^{15} + u^{9} + u^{5} + 2u^{3} + 1 + 2u^{−3} + u^{−5} + u^{−9} + u^{−15} .

In general, we see from B. and C. of §1.2 that, if π ∈ R_{n} corresponds to the function f : ℤ → ℤ_{≥0} and to the Young diagram Y ∈ Y_{n}, then

ν_{π}(T) = ∑_{r∈ℤ} rf(r) = ∑_{(x,y)∈Y} (x − y) .

Either of these descriptions leads to a formula for H_{n}(u), but a more convenient formula is obtained by using a third parametrization of the irreducible representations of S_{n}: if π corresponds to the function f and the Young diagram Y, denote by s = f(0) = max{i | (i, i) ∈ Y } the number of diagonal elements in Y and let

a_{i} = max{j | (i + j − 1, i) ∈ Y } , b_{i} = max{j | (i, i + j − 1) ∈ Y }

be the number of elements of Y to the right of or above the point (i, i) ∈ Y, respectively, so that Y is described as ⋃_{i=1}^{s}([i, i + a_{i} − 1]×{i} ∪ {i}×[i, i + b_{i} − 1]). Then we have

n = ∑_{i=1}^{s}(a_{i} + b_{i} − 1) ,  ν_{π}(T) = ∑_{i=1}^{s}(\binom{a_{i}}{2} − \binom{b_{i}}{2}) ,  (40)

and R_{n} is parametrized by the set of tuples (s, (a_{1}, …, a_{s}), (b_{1}, …, b_{s})) satisfying the inequalities a_{1} > ⋯ > a_{s} > 0, b_{1} > ⋯ > b_{s} > 0 and the first of equations (40). This gives the generating function identity

∑_{n≥0} H_{n}(u) q^{n} = coefficient of ζ^{0} in ∏_{a≥1}(1 + u^{\binom{a}{2}} q^{a−1} ζ) · ∏_{b≥1}(1 + u^{−\binom{b}{2}} q^{b} ζ^{−1}) .

This can be written more symmetrically by shifting a and b by \frac{1}{2} to get

∑_{n≥0} H_{n}(u) q^{n} = coefficient of ζ^{0} in ∏_{m∈\{ \frac{1}{2} , \frac{3}{2} , \frac{5}{2} ,... \}}(1 − u^{m^{2}/2} q^{m} ζ) (1 − u^{−m^{2}/2} q^{m} ζ^{−1}) .

(Here we have multiplied ζ by −q^{1/2}u^{1/8}, which does not affect the coefficient of ζ^{0}.) Combining this with the previous formulas, we obtain the following theorem, due to Douglas [Do] and Dijkgraaf [D1].

Theorem 6. For g ≥ 1, let F_{g}(q) = ∑_{n≥1} h^{0}(2g−2, n) q^{n} ∈ ℚ[[q]] denote the counting function of generically ramified coverings of a genus 1 Riemann surface by Riemann surfaces of genus g. Then

∑_{g=1}^{∞} F_{g}(q) \frac{X^{2g−2}}{(2g − 2)!} = log(∑_{n=0}^{∞} H_{n}(e^{X}) q^{n})

= log(coefficient of ζ^{0} in ∏_{m∈ℤ_{≥0}+ \frac{1}{2}}(1 − u^{m^{2}/2} q^{m} ζ)(1 − u^{−m^{2}/2} q^{m} ζ^{−1})) .

This theorem has an interesting corollary, which was discovered and proved in the language of mathematical physics by Dijkgraaf [D2] and Rudd [R] and proved from a purely mathematical point of view in [KZ]. Recall that a modular form of weight k on the full modular group Γ = SL(2, ℤ) is a function F (z), defined for complex numbers z with ℑ(z) > 0, which has a Fourier expansion of the form F (z) = ∑_{n=0}^{∞} a(n)e^{2πinz} with coefficients a(n) of polynomial growth and which satisfies the functional equation F (\frac{az+b}{cz+d}) = (cz + d)^{k}F (z) for all ( \begin{matrix}a & b \\ c & d \end{matrix} ) ∈ Γ. A quasimodular form of weight k on Γ is a function having a Fourier expansion with the same growth condition and such that for each value of z the function (cz+d)^{−k}F (\frac{az+b}{cz+d}) is a polynomial in (cz + d)^{−1} as ( \begin{matrix}a & b \\ c & d \end{matrix} ) ∈ Γ varies. The ring of modular forms is generated by the two functions

E_{4}(z) = 1 + 240 ∑_{n=1}^{∞} \frac{n^{3} q^{n}}{1 − q^{n}} = 1 + 240q + 2160q^{2} + 6720q^{3} + ⋯

and

E_{6}(z) = 1 − 504 ∑_{n=1}^{∞} \frac{n^{5} q^{n}}{1 − q^{n}} = 1 − 504q − 16632q^{2} − 122976q^{3} − ⋯

of weight 4 and 6, respectively, where q = e^{2πiz}, while the ring of quasimodular forms is generated by these two functions together with the quasimodular form

E_{2}(z) = 1 − 24 ∑_{n=1}^{∞} \frac{n q^{n}}{1 − q^{n}} = 1 − 24q − 72q^{2} − 96q^{3} − ⋯

of weight 2. Theorem 6 then implies:

Corollary. For all g ≥ 2, F_{g}(q) is the q-expansion of a quasimodular form of weight 6g − 6.

We omit the proof, referring the reader to the papers cited above. The first example is

F_{2}(q) = \frac{1}{2^{7}3^{4}5}(5E_{2}^{3} − 3E_{2}E_{4} − 2E_{6}) = q^{2} + 8q^{3} + 30q^{4} + 80q^{5} + 180q^{6} + ⋯,

which leads easily to the amusing closed formula h^{0}(2, n) = \frac{n}{6} ∑_{d|n}(d^{3} − nd) for the number of coverings (generically ramified, with fixed ramification points) of an elliptic curve by Riemann surfaces of genus 2. In general, however, the generating functions F_{g}(q) do not have integral coefficients, e.g. F_{3}(q) begins \frac{1}{12}q^{2} + \frac{20}{3}q^{3} + 102q^{4} + \frac{2288}{3}q^{5} + · · · .

References

[D1] R. Dijkgraaf, Mirror symmetry and elliptic curves, in: The Moduli Spaces of Curves, R. Dijkgraaf, C. Faber, G. van der Geer eds., Progress in Mathematics, vol. 129, Birkhäuser, Boston, 149–164 (1995)

[D2] R. Dijkgraaf, Chiral deformations of conformal field theories, Nuclear Phys. B, 493, 588– 612 (1997)

[Do] M. R. Douglas, Conformal string theory techniques in large N Yang–Mills theory, in: Quantum field theory and string theory (Cargese 1993), 119–135, NATO Adv. Sci. Inst. Ser. B Phys., 328, Plenum, New York (1995)

[DW] R. Dijkgraaf and E. Witten, Topological gauge theories and group cohomology, Commun. Math. Phys., 129, 393–429 (1990)

[FQ] D. Freed and F. Quinn, Chern–Simons gauge theory with a finite gauge group, Commun. Math. Phys., 156, 435–472 (1993)

[KZ] M. Kaneko and D. Zagier, A generalized Jacobi theta function and quasimodular forms, in: The Moduli Spaces of Curves, R. Dijkgraaf, C. Faber, G. van der Geer eds., Progress in Mathematics, vol. 129, Birkhäuser, Boston, 165–172 (1995)

[OV] A. Okounkov and A. Vershik, A new approach to representation theory of symmetric groups, Selecta Math. (N.S.), 2, 581–605 (1996)

[R] R. Rudd, The string partition function for QCD on the torus, hep-th/9407176

[SSV] B. Shapiro, M. Shapiro, A. Vainshtein, Ramified coverings of S^{2} with one degenerate branch point and enumeration of edge-ordered graphs, in: Topics in singularity theory, Amer. Math. Soc. Transl. Ser. 2, 180, AMS. Providence RI, 219–227 (1997)

[Z] D. Zagier, On the distribution of the number of cycles of elements in symmetric groups, Nieuw Arch. Wiskd., IV Ser., 13, 489–495 (1995)