# Combinatorial Techniques for Counting Conjugacy Classes

The number of conjugacy classes in $S_n$ is given by the number of partitions of $n$. Do other families of finite groups have a highly combinatorial structure to their number of conjugacy classes? For example, how much is known about conjugacy classes in $A_n$?

-
I'm interested in this question for the case of Coxeter groups, which should behave somewhat similarly, right? –  j.c. Dec 10 '09 at 2:41
For group extension have also a look at the Kirillov Orbit method for studying the irreducible representations. –  Marc Palm Feb 12 '12 at 11:22

Since $A_n$ has index two in $S_n$, every conjugacy class in $S_n$ either is a conjugacy class in $A_n$, or it splits into two conjugacy classes, or it misses $A_n$ if it is an odd permutation. Which happens when is a nice undergraduate exercise in group theory. (And you are a nice undergraduate. :-) )

The pair $A_n \subset S_n$ is typical for this question in finite group theory. You want the conjugacy classes of a finite simple group $G$, but the answer is a little simpler for a slightly larger group $G'$ that involves $G$. Another example is $\text{GL}(n,q)$. It involves the finite simple group $L(n,q)$, but the conjugacy classes are easier to describe in $\text{GL}(n,q)$ . They are described by their Jordan canonical form, with the twist that you may have to pass to a field extension of $\mathbb{F}_q$ to obtain the eigenvalues.

The group $\text{GL}(n,q)$ is even more typical. It is a Chevallay group, which means a finite group analogue of a Lie group. All of the infinite sequences of finite simple groups other than $A_n$ and $C_p$ are Chevallay groups. You expect a canonical form that looks something like Jordan canonical form, although it can be rather more complicated.

If $G$ is far from simple, i.e., if it has some interesting composition series, then one approach to its conjugacy classes is to chase them down from the conjugacy classes of its composition factors, together with the structure of the extensions. The answer doesn't have to be very tidy.

I suppose that finite Coxeter groups give you some exceptions where you do get a tidier answer, just because they all resemble $S_n$ to varying degrees. But I don't know a crisp answer to all cases of this side question. The infinite sequences of finite Coxeter groups consist only of permutation groups, signed permutation groups, and dihedral groups. (And Cartesian products of these.) In the case of signed permutation groups, the answer looks just like $S_n$, except that cycles can also have odd or even total sign. There is also the type $D_n$ Coxeter group of signed permutation matrices with an even number of minus signs; the answer is just slightly different from all of the signed permutation matrices, which is type $B_n$. The crisp answer that I don't have would be a uniform description that includes the exceptional finite Coxeter groups, such as $E_8$.

-
A very obvious addition to what you said about B_n - in general, if you have a combinatorial description of conjugacy class in G, classes of the semidirect product of S_n and G^n have a closely related description as well, and that shows up in various situations. –  Vladimir Dotsenko Dec 10 '09 at 9:21
Right. We can say that the conjugacy classes in the wreath product of $S_n$ and $G$ are cycle types in $S_n$ with each cycle decorated by a conjugacy class of $G$. The decoration is the holonomy of the cycle. The corner group of the Rubik's cube is a fun example of this principle. –  Greg Kuperberg Dec 10 '09 at 15:18

For an explicit formula for the size of the conjugacy classes of GL$(n,q)$ (going back to Frobenius and Philip Hall), see equation (1.107) on page 92 of http://math.mit.edu/~rstan/ec/ec1.pdf. (There are formulas for the quantities appearing in (1.107) earlier in the text and in (1.108).)

As for the number $\omega^\ast(n,q)$ of conjugacy classes, see Exercise 1.190 on page 156 of the above reference. In particular, for fixed $n$, $\omega^\ast(n,q)$ is a polynomial in $q$ satisfying $$\sum_{n\geq 0}\omega^\ast(n,q)x^n = \prod_{j\geq 1} \frac{1-x^j}{1-qx^j}$$ $$\omega^\ast(n,q) = q^n-q^m- q^{m-1}-q^{m-2}-\cdots -q^{\lfloor n/3\rfloor}+O(q^{\lfloor n/3\rfloor-1}),$$ where $m=\lfloor (n-1)/2\rfloor$.

-
Dear Richard, the link does not work for me. –  Alex B. Feb 11 '12 at 23:58
The link has been fixed. –  Richard Stanley Feb 12 '12 at 0:18
You can also use Sage to do these calculations; see sagemath.org/doc/reference/combinat/sage/combinat/…. Note that the expressions for the numbers and cardinalities of conjugacy classes here are formal polynomials in $q$ (the cardinality of the finite field). –  Amritanshu Prasad Aug 19 '14 at 11:43

You will no doubt find this paper interesting:

http://archive.numdam.org/ARCHIVE/CM/CM_1972__25_1/CM_1972__25_1_1_0/CM_1972__25_1_1_0.pdf

As Greg suggested, for Weyl groups, both conjugacy classes and irreducible representations are known. Beyond this class of examples, and perhaps a few of the other Coxeter groups, my understanding is that there is not a combinatorial description of the conjugacy classes of a finite group.

A related difficulty: you know that there are the same number of conjugacy classes as there are irreducible representations in any finite group, as characters form a basis of class functions. In $S_n$, and also in the Coxeter group examples, one can give explicitly a bijection (so there is both a conjugacy class in $S_n$ and an irrep associated to a Young diagram $\lambda$, for instance). For a general group, there is not a general framework for corresponding conjugacy classes to irreps.

-
Can you give some details on " and also in the Coxeter group examples, one can give explicitly a bijection. I kind of quoted you in mathoverflow.net/questions/153731/… –  Alexander Chervov Jan 6 '14 at 13:14