A general formula for the number of conjugacy classes of $\mathbb{S}_n \times \mathbb{S}_n$ acted on by $ \mathbb{S}_n$

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

Let me follow up on, and try to clarify some of what has been said. Given a group $G$, we want to count the number of $G$-orbits on $G \times G$, where the action is conjugation in each coordinate. The number of fixed points of $x \in G$ is thus $|C_G(x)|^2$, so by the "Burnside" lemma (due to Cauchy and Frobenius) the number $N$ of orbits is given by $$ N = \frac{1}{|G|}\sum_{x \in G} |C_G(x)|^2 . $$ Grouping together the elements of each class, summing over classes $K$ and using the fact that $|G| = |C_G(x)|K|$, where $K$ is the class of $x$, we get

$$ N = \frac1{|G|}\sum_K |K|\big(\frac{|G|}{|K|}\big)^2 = |G| \sum_K \frac{1}{|K|}. $$

We can easily compute this in Magma for $G = S_n$ for small $n$, and we get: $1,4,11,43,161,901,5579,43206,\ldots$. This appears to match sequence A110143 in the OEIS.

Answer 2

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 3

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,\dots,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$.

Answer 4

The answer by Marty Isaacs is, of course, correct. For a general group $G,$ the number of orbits of $G$ acting by conjugation on $G \times G$ by conjugation (when diagonally embedded) is equivalently expressible as $\sum_{x}|C_{G}(x)|,$ where $x$ runs over a full set of representatives for the conjugacy classes of $G.$

For the symmetric group $S_{n}$ , the conjugacy classes are labelled by the partitions of $n.$ The centralizer of an element with cycle structure labelled by $\lambda = 1^{m_{1}}2^{m_{2}} \ldots r^{m_{r}}$ is $\prod_{i} C_{i} \wr S_{m_{i}}$ (direct), where $C_{i}$ denotes the cyclic group of order $i.$ The order of the centralizer of such an element is therefore $\prod_{i=1}^{r} i^{m_{i}} m_{i}!,$ which we denote by $w(\lambda).$

Hence the required number of orbits is $\sum_{\lambda} w(\lambda),$ where $\lambda$ runs over the partitions of $n.$

Answer 5

I discovered this old question in connection with someone else's similar (and current) question: The Simultaneous Conjugacy Problem in the symmetric group $S_N$

If anyone still cares, here is a slightly different answer for your question using the character table instead of centralizer sizes. The characters might be more accessible in certain cases (and of interest in their own right). $$N=\frac{1}{n!} \sum_{\alpha \in G} \left( \sum_{\text{irreps}\ \chi} \chi(\alpha)^2 \right)^2$$ The inner sum is just the centralizer term in Marty Isaacs answer, but expressed in a different way. It might be of some use in this form. For example, if you want to enrich the group action to allow coordinate swap or inversion, similar class functions can be used.

The OP and others may be interested in the above linked question, which discusses the related decision problem and the generalization to more coordinates.