# 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 '10 at 21:55
research.att.com/~njas/sequences/A110143 no formula is given. –  Steve D Oct 7 '10 at 1:57
What's wrong with the generating function given there? –  Martin Rubey Oct 7 '10 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 '10 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 '10 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 '10 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 '10 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 '10 at 12:10