## A general formula for the number of conjugacy classes of \S_n \times \S_n acted on by \S_n

$\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

-
You say you can compute this for fixed $n$. Have you tried computing the first few terms and looking in the Encyclopedia of Integer Sequences? – Michael Lugo Oct 6 2010 at 21:55
research.att.com/~njas/sequences/A110143 no formula is given. – Steve D Oct 7 2010 at 1:57
What's wrong with the generating function given there? – Martin Rubey Oct 7 2010 at 18:31

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.

-
 In what way is the answer related to the question? – Guntram Oct 7 2010 at 9:50 The first paragraph directly addresses the question by giving a rough estimate of the number of equivalence classes. The GAP computation is of a commonly-studied set of numbers for a variation of the question, where it was easy to get the first few numbers. The lack of hits in the OEIS suggests it's not likely there's a known good pattern or formula. With more work one could compute similar numbers for the original question, but I answered what I had time for. – Bill Thurston Oct 7 2010 at 11:43 @Guntram: Rereading my answer, I saw that I made abrupt leaps, so I added some connective sentences to clarify the connection of what I was doing to the wording of the question. Someone with better fluency than me in GAP or Magma, or who is good at hand calculation, should calculate the first few terms of the sequence as requested, and more terms of the sequence I gave (I stopped where I did because it required changing memory parameters to go further, and I didn't want to mess with it). – Bill Thurston Oct 7 2010 at 11:52 I am confused. How could this be the right answer? For S_2 acting on S_2 x S_2, there should be 4 orbits, not 3. – Steve D Oct 7 2010 at 11:59 @Steve D: The numbers above are not for the original question (homomorphisms up to conjugacy), but for the related question of epimorphisms up to automorphism, just because the latter question has a built-in GAP function, GQuotients. Efficiency is a critical issue in computations like this because of the combinatorial explosion, so I didn't want to casually code the original question from scratch. – Bill Thurston Oct 7 2010 at 12:10

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.

-