ON THE DISTRIBUTION OF THE NUMBER OF

CYCLES OF ELEMENTS IN SYMMETRIC GROUPS

Don Zagier

Max-Planck-Institut für Mathematik, Bonn and Universiteit Utrecht

Abstract. We give a formula for the number of elements in a fixed conjugacy class of a symmetric group whose product with a cyclic permutation has a given number of cycles. A consequence is a very short proof of the formula for the number ε_{g}(n) of ways of obtaining a Riemann surface of given genus g by identifying in pairs the sides of a 2n-gon. This formula, originally proved by a considerably more difficult method in [1], was the key combinatorial fact needed there for the calculation of the Euler characteristic of the moduli space of curves of genus g. As a second application, we show that the number of ways of writing an even permutation π ∈ 𝔖_{N} as a product of two N-cycles always lies between 2(N − 1)!/(N − r + 2) and 2(N − 1)!/(N − r + 19/29), where r is the number of fixed points of π, and that both constants “2” and “19/29” are best possible.

Consider the following combinatorial problem. Let C be a conjugacy class in the symmetric group 𝔖_{N} on N letters, and let σ ∈ 𝔖_{N} denote a cyclic permutation. For 1 ≤ m ≤ N set

p_{m}(C) = \frac{1}{#C} · #\{π ∈ C | πσ has m cycles\} ,

so that ∑_{m=1}^{N} p_{m}(C) = 1. The problem is to give a closed formula for the numbers p_{m}(C).

Theorem 1. The numbers p_{m}(C) are determined by

∑_{m=1}^{N} p_{m}(C) Φ_{m}(X) = \frac{χ(C, X)}{(1 − X)^{N+2}} ,  (1)

where χ(C, X) = det(1 − πX, V) is the characteristic polynomial of an element π ∈ C acting on the permutation representation V = ℂ^{N} of 𝔖_{N} and

Φ_{1}(X) = \frac{1}{(1 − X)^{2}} , Φ_{2}(X) = \frac{1 + X}{(1 − X)^{3}} , Φ_{3}(X) = \frac{1 + 4X + X^{2}}{(1 − X)^{4}} , …

are the polynomials in \frac{1}{1 − X} defined by Φ_{m}(X) = ∑_{k=1}^{∞} k^{m}X^{k−1} ∈ ℤ[[X]].

Before giving the proof of this theorem, we mention a few of its consequences. Application 1. For π ∈ 𝔖_{N} denote by N_{i}(π) (1 ≤ i ≤ N) and N(π) the number of i-cycles and the total number of cycles, respectively, so that ∑ iN_{i}(π) = N, ∑ N_{i}(π) = N(π). Since these are conjugacy class invariants, we also denote them N_{i}(C) and N(C), where C = C(π) is the conjugacy class of π. Then

χ(C, X) = ∏_{i=1}^{N}(1 − X^{i})^{N_{i}(C)}  (2)

is divisible exactly by (1 − X)^{N(C)}, so the right-hand side of (1) has a pole of order N + 2 − N(C) at X = 1. Since Φ_{m}(X) is a polynomial of degree m + 1 in (1 − X)^{−1}, it follows from (1) that

Max{m | p_{m}(C) ≠ 0} = N + 1 − N(C) ,

and in particular, that N(π) + N(πσ) ≤ N + 1 for every π ∈ 𝔖_{N}. This is a special case of the easily proved inequality N(g_{1}) + N(g_{2}) ≤ N(g_{1}g_{2}) + N, valid for all g_{1}, g_{2} ∈ 𝔖_{N}. Application 2. Another easy consequence of (1) is that p_{m}(C) = 0 unless sgn(π) = (−1)^{m−1} (π ∈ C). This is of course trivial anyway since p_{m}(C) ≠ 0 implies that

(−1)^{N−m} = (−1)^{N−N(πσ)} = sgn(πσ) = sgn(σ) sgn(π) = (−1)^{N−1} sgn(π)

for some π ∈ C, but it also follows from (1) and (2) together with the observation that XΦ_{m}(X) is (−1)^{m−1}-symmetric under X ↦ 1/X. Application 3. In the special case when π ∈ C is cyclic, the number p_{m}(C) is the probability that a product of two cyclic permutations in 𝔖_{N} has exactly m cycles, and (1) says that this number

equals \frac{1 + (−1)^{N−m}}{(N + 1)!} times the coefficient of x^{m} in x(x + 1) ⋯ (x + N). For example, for N odd

the probability that the product of two random cyclic permutations in 𝔖_{N} is cyclic is 2/(N + 1), as opposed to the probability 2/N that a random even element of 𝔖_{N} is cyclic. Application 4. The most interesting special case of (1), however, and the main reason for this note, is the case when N = 2n and C is the conjugacy class of free involutions, i.e., any π ∈ C has n cycles of length 2. Here p_{m}(C) = 0 if m > n + 1 or n + 1 − m is odd, by the observations in “Application 1” and “Application 2.” The number p_{n+1−2g}(C) equals ε_{g}(n)/(2n − 1)!!, where (2n − 1)!! = |C| = 1 × 3 × ⋯ × (2n − 1) and ε_{g}(n) is the number of ways of identifying in pairs the sides of a 2n-gon to obtain an oriented surface of genus g. (This is because any orientation-reversing pairwise gluing π of the sides gives an oriented surface of some genus g, and the resulting surface is triangulated with N(πσ) vertices, n edges, and one 2-simplex, so that 2 − 2g = N(πσ) − n + 1 by Euler’s formula.) On the other hand, χ(C, X) = (1 − X^{2})^{n} by (2), so (1) becomes

\frac{1}{(2n − 1)!!} ∑_{0≤g≤n/2} ε_{g}(n) Φ_{n+1−2g}(X) = \frac{(1 + X)^{n}}{(1 − X)^{n+2}}  (3)

or, comparing the coefficients of X^{k−1} on both sides,

\frac{1}{(2n − 1)!!} ∑_{0≤g≤n/2} ε_{g}(n) k^{n+1−2g} = Coeff_{X^{k−1}}[\frac{(1 + X)^{n}}{(1 − X)^{n+2}} ] = Coeff_{T^{n+1}}[\frac{1}{2} (\frac{1 + T}{1 − T} )^{k}] , (4)

where the last equality follows from the residue theorem or by computing in two ways the coefficient of X^{k−1}T^{n+1} in (1 + T)/(1 − T − X − XT).

Formula (4) was proved by a considerably more complicated method in [1] and was the main combinatorial ingredient in the calculation given there of the Euler characteristic of the moduli space of curves of genus g. Actually, the formula was used there in the form

ε_{g}(n) = \frac{2^{n−2g} (2n − 1)!!}{(n + 1 − 2g)!} Coeff_{u^{2g}}[(\frac{u}{sinh u})^{2}(\frac{u}{tanh u})^{n} ] ,

which can be obtained from (4) either by susbstituting T = tanh u and applying the residue theorem or else directly from (3) by observing that

e^{−x} Φ_{m}(e^{−x}) = (−1)^{m} \frac{d^{m}}{dx^{m}} (\frac{1}{e^{x} − 1}) = \frac{m!}{x^{m+1}} + O(1) (x → 0)

and then comparing coefficients of u^{2g−2−n} in both sides of (3) with X = e^{−2u}. The same method applies to the general case and leads to the following equivalent form of the main theorem:

p_{m}(C) = \frac{1}{m!} Coeff_{x^{N+1−m}}[(\frac{x}{1 − e^{−x}} )^{N+2}e^{−x} χ(C, e^{−x})] .  (5)

Application 5. It is well-known that every even permutation π ∈ 𝔖_{N} is the product of two N-cycles. Let R(π) be the number of such representations. It is easy to see that

R(π) = (N − 1)! p_{1}(π) .  (6)

On the other hand, it is also easy to verify that the average of p_{m}(π) over all π ∈ 𝔖_{N} for any m ≥ 1 is just the coefficient of y^{m} in the polynomial \binom{y+N−1}{N}. For m = 1 this is 1/N, so (6) gives

Average\{R(π) | π ∈ 𝔖_{N}, π even\} = \frac{2 (N − 1)!}{N} .

We will show that

Min\{R(π) | π ∈ 𝔖_{N}, π even\} ≥ \frac{2 (N − 1)!}{N + 2} ,

so that the minimum value of R(π) is only slightly less than its average value. In fact, we will prove the following stronger and rather amusing result.

Theorem 2. Let π ∈ 𝔖_{N} be an even permutation with r fixed points, 0 ≤ r ≤ N. Then

\frac{2 (N − 1)!}{N − r + 2} ≤ R(π) ≤ \frac{2 (N − 1)!}{N − r + \frac{19}{29}}  (7)

and the constants 2 and \frac{19}{29} appearing in the denominators are both best possible.

We now give the proofs of the two theorems.

Proof of Theorem 1. A well-known formula, valid for any finite group G and conjugacy classes A, B, C ⊆ G, says that

#\{(a, b, c) ∈ A × B × C | abc = 1\} = \frac{|A| |B| |C|}{|G|} ∑_{χ∈Ĝ} \frac{χ(A)χ(B)χ(C)}{χ(1)}

(sum over the characters of the irreducible representations of G). An equivalent form of this is

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

for any b ∈ G and any class invariant F : G → ℂ. We apply it to G = 𝔖_{N}, b = σ, and F (π) = Φ_{N(π)}(X). Let V_{0} denote the irreducible (N −1)-dimensional subrepresentation of V = ℂ^{N} and χ_{r} (0 ≤ r ≤ N − 1) the character of the irreducible representation Λ^{r}(V_{0}). Clearly

∑_{r=0}^{N−1} χ_{r}(π) (−T)^{r} = det(1 − π T, V_{0}) = \frac{χ(π, T)}{1 − T}  (∀π ∈ G).  (9)

In particular, χ_{r}(σ) = (−1)^{r} since χ(σ, T) = 1 − T^{N} by (2). Hence

∑_{r=0}^{N−1} |χ_{r}(σ)|^{2} = N = \frac{|G|}{|C(σ)|} = ∑_{χ∈Ĝ} |χ(σ)|^{2}

(orthogonality relation for characters!), so χ(σ) = 0 for all χ ∉ {χ_{0}, …, χ_{N−1}} and (8) becomes

\frac{1}{|C|} ∑_{π∈C} Φ_{N(πσ)}(X) = ∑_{r=0}^{N−1} \frac{(−1)^{r} χ_{r}(C)}{\binom{N−1}{r}} (\frac{1}{N!} ∑_{A} |A| χ_{r}(A) Φ_{N(A)}(X)) .  (10)

But by formulas (9) and (2) we have

∑_{r=0}^{N−1}(\frac{1}{N!} ∑_{A} |A| χ_{r}(A) k^{N(A)}) (−T)^{r} = ∑_{N_{1}+2N_{2}+···=N} \frac{k^{N_{1}+N_{2}+···} (1 − T)^{N_{1}}(1 − T^{2})^{N_{2}} ⋯}{1^{N_{1}}2^{N_{2}} ⋯ N_{1}!N_{2}! ⋯ (1 − T)}

= \frac{1}{1 − T} Coeff_{u^{N}} [∏_{j=1}^{∞} ∑_{n=0}^{∞} \frac{k^{n}(1 − T^{j})^{n}u^{nj}}{j^{n} n!} ] = \frac{1}{1 − T} Coeff_{u^{N}} [(\frac{1 − uT}{1 − u} )^{k}] .

Multiplying by X^{k−1} and summing over all k ≥ 1, we find

∑_{r=0}^{N−1}(\frac{1}{N!} ∑_{A} |A| χ_{r}(A) Φ_{N(A)}(X)) (−T)^{r} = \frac{1}{1 − T} Coeff_{u^{N}} [\frac{1 − uT}{1 − u − X + uXT} ]= \frac{(1 − XT)^{N−1}}{(1 − X)^{N+1}}

or, comparing the coefficients of (−T)^{r} on both sides,

\frac{1}{N!} ∑_{A} |A| χ_{r}(A) Φ_{N(A)}(X) = \binom{N − 1}{r} \frac{X^{r}}{(1 − X)^{N+1}} .

Substituting this into (10) and using (9) again, we obtain the desired formula (1).

Proof of Theorem 2. Write N_{i} for N_{i}(π), so that r = N_{1}, and denote by f_{π}(k) the polynomial ∑_{m=1}^{N} p_{m}(π)k^{m}. Theorem 1 can be expressed in terms of f_{π} by the generating function

ϕ_{π}(y) = ∑_{k=1}^{∞} f_{π}(k) y^{k−1} = \frac{χ(π, y)}{(1 − y)^{N+2}} = \frac{1}{(1 − y)^{N+2}} ∏_{i=1}^{N} (1 − y^{i})^{N_{i}}  (11)

and we want to compute p_{1}(π) = f′_{π}(0). For this we use:

Lemma. Let f(k) be a polynomial with f(0) = 0 and ϕ(y) = ∑_{k=1}^{∞} f(k)y^{k−1} ∈ ℂ[\frac{1}{1−y} ]. Then

f′(0) = ∫_{0}^{∞} ϕ(−t) dt .

Proof. We may assume f(k) = \binom{k+r−1}{r} for some r ≥ 1, since any polynomial with zero constant term is a linear combination of these. Then ∫_{0}^{∞} ϕ(−t)dt = ∫_{0}^{∞}(1 + t)^{−r−1}dt = 1/r = f′(0).

Applying the lemma to the polynomial f = f_{π}, we find

p_{1}(π) = f′_{π}(0) = ∫_{0}^{∞} ϕ_{π}(−t) dt = 2 ∫_{0}^{1} ϕ_{π}(−t) dt ,

where the last identity follows from the fact that yϕ_{π}(y) is invariant under y ↦ 1/y since π is even (cf. “Application 3” above). Now substitute t = x/(1 − x) and use (11) to get

p_{1}(π) = 2 ∫_{0}^{1/2} ϕ_{π}(\frac{−x}{1 − x}) \frac{dx}{(1 − x)^{2}} = 2 ∫_{0}^{1/2} ∏_{i=2}^{N} [(1 − x)^{i} − (−x)^{i}]^{N_{i}} dx .  (12)

The lower bound in the theorem follows easily. Indeed, for i ≥ 2 we have

(1 − x)^{i} − (−x)^{i} ≥ [(1 − 2x) + x^{2}]^{i/2} − (x^{2})^{i/2} ≥ (1 − 2x)^{i/2} ,

so

p_{1}(π) ≥ 2 ∫_{0}^{1/2}(1 − 2x)^{(N−N_{1})/2} dx = \frac{2}{N − N_{1} + 2}

with equality if N = N_{1} + 2N_{2}, and in view of (6) this is equivalent to the lower bound in equation (7). (Recall that r = N_{1}.) For the other direction, we use the estimates

(1 − 3x + 3x^{2})^{2/3} = [(1 − 2x)^{3} + 2(2x^{2} − x)^{2} + (x^{2} − x)^{2}]^{1/3} ≥ 1 − 2x = (1 − x)^{2} − x^{2}
(1 − 3x + 3x^{2})^{i/3} = [(1 − x)^{3} + x^{3}]^{i/3} ≥ (1 − x)^{i} + x^{i} ≥ (1 − x)^{i} − (−x)^{i}  if i ≥ 3

to get

p_{1}(π) ≤ 2 ∫_{0}^{1/2}(1 − 3x + 3x^{2})^{(N−N_{1})/3} dx =: A(N − N_{1}) .

An easy analysis shows that A(k) = 2/(k + c_{k}) where c_{k} decreases monotonically from c_{2} = 1.24409 … to c_{8} = 0.64164 … and then increases monotonically to a limiting value of 1 as k → ∞, with c_{9} = \frac{19}{29} and c_{k} ≥ \frac{19}{29} for all k except 7 and 8. This proves the second inequality in (7) for all cases except N = N_{1} + 7 or N = N_{1} + 8 and shows also that it is best possible. (Take π with r = N − 9 fixed points and three 3-cycles; then (12) shows that p_{1}(π) = A(9) = 2/(N − r + \frac{19}{29}).) Finally, for the two cases where k = N − r has the value 7 or 8 we must look at the finite list of partitions of k as ∑_{i≥2} iN_{i} and for each one check that the value of the integral in (12) is ≤ 2/(k + \frac{19}{29}). (The integrand in (12) is a polynomial, so the ten integrals in question are easy to compute). This completes the proof of the theorem.

Remarks. The author would like to thank Professor T.A. Springer for helpful conversations and in particular for the observation that only the characters χ_{r} contribute to the calculation of p_{m}(C). The observation that the combinatorial result in [1] could in principle also be obtained by calculating the numbers p_{m}(C) for the conjugacy class of free involutions in 𝔖_{2n} was made to me shortly after [1] appeared by A. Odlyzko, and an explicit calculation along these lines is given in the paper [3] by D.M. Jackson, but with a longer derivation than the one here. Another proof of the combinatorial formula in question was given by Itzykson and Zuber [2], and a completely different proof of the Euler characteristic formula, not relying on a triangulation of the moduli space, by Kontsevich [4].

References

[1] J. Harer and D. Zagier, The Euler characteristic of the moduli space of curves, Invent. math. 85 (1986) 457–485

[2] C. Itzykson and J-B. Zuber, Matrix integration and combinatorics of modular groups, Comm. Math. Phys. 134 (1990) 197–207

[3] D.M. Jackson, Counting cycles in permutations by group characters, with an application to a topological problem, Trans. AMS 299 (1987) 785–801

[4] M. Kontsevich, Intersection theory on the moduli space of curves and the matrix Airy function, Comm. Math. Phys. 147 (1992) 1–23