Combinatorial Techniques for Counting Conjugacy Classes - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T00:41:28Z http://mathoverflow.net/feeds/question/8415 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/8415/combinatorial-techniques-for-counting-conjugacy-classes Combinatorial Techniques for Counting Conjugacy Classes Nick Salter 2009-12-10T02:36:21Z 2012-02-12T03:22:59Z <p>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$?</p> http://mathoverflow.net/questions/8415/combinatorial-techniques-for-counting-conjugacy-classes/8418#8418 Answer by Greg Kuperberg for Combinatorial Techniques for Counting Conjugacy Classes Greg Kuperberg 2009-12-10T03:00:19Z 2009-12-10T03:31:47Z <p>Since <code>$A_n$</code> has index two in <code>$S_n$</code>, every conjugacy class in <code>$S_n$</code> either is a conjugacy class in <code>$A_n$</code>, or it splits into two conjugacy classes, or it misses <code>$A_n$</code> if it is an odd permutation. Which happens when is a nice undergraduate exercise in group theory. (And you are a nice undergraduate. :-) )</p> <p>The pair <code>$A_n \subset S_n$</code> 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.</p> <p>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.</p> <p>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.</p> <p>I suppose that finite Coxeter groups give you some exceptions where you do get a tidier answer, just because they all resemble <code>$S_n$</code> 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 <code>$S_n$</code>, except that cycles can also have odd or even total sign. There is also the type <code>$D_n$</code> 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 <code>$B_n$</code>. The crisp answer that I don't have would be a uniform description that includes the exceptional finite Coxeter groups, such as <code>$E_8$</code>.</p> http://mathoverflow.net/questions/8415/combinatorial-techniques-for-counting-conjugacy-classes/8691#8691 Answer by David Jordan for Combinatorial Techniques for Counting Conjugacy Classes David Jordan 2009-12-12T17:06:46Z 2009-12-12T17:06:46Z <p>You will no doubt find this paper interesting:</p> <p><a href="http://archive.numdam.org/ARCHIVE/CM/CM_1972__25_1/CM_1972__25_1_1_0/CM_1972__25_1_1_0.pdf" rel="nofollow">http://archive.numdam.org/ARCHIVE/CM/CM_1972__25_1/CM_1972__25_1_1_0/CM_1972__25_1_1_0.pdf</a></p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/8415/combinatorial-techniques-for-counting-conjugacy-classes/16300#16300 Answer by Richard Stanley for Combinatorial Techniques for Counting Conjugacy Classes Richard Stanley 2010-02-24T20:36:13Z 2012-02-12T03:22:59Z <p>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 <a href="http://math.mit.edu/~rstan/ec/ec1.pdf" rel="nofollow">http://math.mit.edu/~rstan/ec/ec1.pdf</a>. (There are formulas for the quantities appearing in (1.107) earlier in the text and in (1.108).)</p> <p>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$.</p>