Question

$\def\S{\mathbb{S}}$

Dear all,

So I have $\S_n$ acting on $\S_n \times \S_n$ via conjugacy. That is: for $g \in \S_n, (x,y) \in \S_n \times \S_n$: $g(x,y) = (gxg^{-1},gyg^{-1}).$

Is there a general formula (or a nice combinatorial description) for the number of conjugacy classes produced in this case?

Some thoughts on the problem: for a fixed $n$ one can compute this by hand as follows: Note that if we consider the action of $\S_n \times \S_n$ on $\S_n \times \S_n$ by conjugation, then we have classes of types $(\lambda, \mu)$ for each configuration $\lambda$ and $\mu$ of the Young diagram. Here we restrict ourselves to the diagonal action, so this would split the $(\lambda,\mu)$ pair further. To compute this splitting for a fixed pair $(x,y)$ where $x$ is of type $\lambda$, y is of type $\mu$, let $C(x)$ denotes the centralizer of $x$. For any $g \in \S_n$, write $g = g_1g_x$ for some $g_x \in C(x)$. Then $(x,y) \sim (g_1xg_1^{-1}, g_1(g_xyg_x^{-1})g_1^{-1})$ Then the number of equivalence classes we have for this pair is the number of orbits of the class $\mu$ acted upon by $C(x)$ via conjugation.

But is there a general formula?

Thanks,

Ngoc

Answer 1

The question is equivalent to asking for the number of homomorphisms of the free group on 2 generators to $\mathbb S_n$, up to conjugacy.

For large n, the majority of homomorphisms are epimorphisms, that is, most pairs of elements generate the full symmetric group: if they do not generate, they both lie in a proper subgroup, the biggest of which has index $n$ so has frequency $1/n^2$ ... and other terms trail off. The orbit of a pair of generators under the conjugacy action is free, so there are somewhat less than $n!*n!/n! = n!$ pairs of generators, up to conjugacy. In addition, there are pairs that do not generate, which have smaller orbits, but still, $n!$ is a good enough number for many purposes. You couldn't compute many of these by hand without further insight because of the combinatorial explosion.

Both GAP and Magma can compute this kind of thing for small n, and in particular they have highly-tuned functions to compute the related enumeration of epimorphisms from a finitely presented group to a finite group, up to automorphism of the target. Applying this to the free gropu, the first few numbers are (from GAP):

f = FreeGroup(2);;
epis := List( [2..6], i -> GQuotients(f, SymmetricGroup(i)) );;
List(epis, Length);
[ 3, 3, 9, 57, 159 ]

Neither this sequence nor $1,3,3,9,57,159$ (where the case for $\mathbb S_1$ is prepended) registers a hit in the OEIS. I have no expertise in combinatorics, but it seems to me probably difficult to get a good general exact formula for the number of homomorphisms, although it shouldn't be hard to get reasonable estimates.

Answer 2

I don't know that it is of the type you wish, but there is a formula of sorts.

Consider the more general case of a finite group G acting diagonally by conjugation on the set of k-tuples of elements of G. For a fixed g in G, the number of fixed points of g is |C_G(g)|^k. Let g_1,...,g_c be a set of representatives for the conjugacy classes of G. Applying Burnside's Lemma and grouping together elements in the same conjugacy class, we see that the number of orbits of G in the given action is the sum over all g_i of |C_G(g_i)|^{k-1}.

So, in your case, we have the sum of |C_G(g_i)| over a set of representatives for the conjugacy classes of S_n. As you noted, these classes are parameterized by partitions of n, and if such a partition p has a_j parts of size j for each j in [n], the order of the corresponding centralizer is the product over all such j of (a_j)!j^{a_j}. Thus we get the sum over all partitions of n of such products.

Maybe it is worth remarking that, for any G, when k=2 the number in question is the sum of the square norms of the entries of the character table of G.