A collision between cycle index polynomials

Today’s post is a short, to describe an example of when the cycle index polynomial of a permutation group is not a total invariant of the group up to conjugacy.

Cycle index polynomials

Let \(G\) be a permutation group. In other words, \(G\) is a finte group, together with a specified embedding into some symmetric group \(\mathfrak{S}_n\).

For example, consider the following two embeddings of \(C_2 \times C_2 \leq \mathfrak{S}_6\):

\[G_1 = \langle (1,2)(3,4), (1,2)(5,6)\rangle \]

\[G_2 = \langle (1,2)(3,4), (1,3)(2,4) \rangle \]

These are two distinct permutation groups which are not conjugate inside of \(\mathfrak{S}_6\).

The cycle index polynomial of \(G \leq \mathfrak{S}_n\) is defined to be \[ \frac{1}{|G|} \sum_{g \in G} p_{\operatorname{type}(g)},\] where \(p_{\operatorname{type}(g)}\) is the power-sum symmetric function (of degree \(n\)) indexed by the cycle type of \(g\) regarded as an element of \(\mathfrak{S}_n\).

The collision

It is reasonable to ask if the cycle index polynomial is an invariant of a permutation group \(G\) up to conjugacy (i.e. up to relabeling the set that \(G\) acts on). It is not. The two examples of \(G_1\) and \(G_2\) above provide a counter example. Since \(G_1\) acts on \({1,2,3,4,5,6}\) and \(G_2\) acts on \({1,2,3,4} \subseteq {1,2,3,4,5,6}\), they are not conjugate subgroups of \(\mathfrak{S}_6\). However, both have cycle index polynomial \[\frac{1}{4} p_{1^6} + \frac{3}{4} p_{2^21^2}.\]

Code to generate more collisions

The examples of \(G_1\) and \(G_2\) above give the smallest example of a collision between two permutation groups. If you ever need to find more, you can find the collisions using the following SageMath code (and suitably modifying N). The dict called multiples has keys given by cycle index polynomials with multiple corresponding groups. the corresponding groups are the values.

sage: N = 6
....: SN = SymmetricGroup(N)
....: CIs = {G: G.cycle_index() for G in SN.conjugacy_classes_subgroups()}
....: Gs = dict()
....: for G, f in CIs.items():
....:     l = Gs.get(f,list())
....:     l.append(G)
....:     Gs[f] = l
....: 
....: multiples = {f:Glist for f, Glist in Gs.items() if len(Glist) > 1}

For example, with N=7, there are 3 distict cycle index polynomials with collisions.