Skip to main content
1 of 4
Geoff Robinson
  • 44.4k
  • 5
  • 123
  • 169

Here is a different viewpoint: the question is equivalent to asking for a permutation $\sigma$ whose disjoint cycle structure contains exactly $m$ cycles, and with $|C_{S_{n}}(\sigma)|$ as small as possible subject to that.

Note that if $\sigma$ has $a_{j}$ cycles of length $j$ for each $j$ in that decomposition, then $|C_{S_{n}}(\sigma)| = \prod_{j} j^{a_{j}} a_{j}!,$ (which is just the denominator in the expression given in the question for the size of the conjugacy class). Note that this is clearly at least as large as $ \prod_{ \{j : a_{j} >0\}} j$, and note on the other hand that equality holds if all cycle sizes are distinct.

From now on I consider the case where there is a partition of $n$ into $m$ parts of distinct sizes (which is equivalent to requiring that $n \geq \frac{m(m+1)}{2}).$ I want to show first that there is a unique (up to conjugacy) choice of $\sigma$ which minimizes $|C_{S_{n}}(\sigma)|$ subject to the condition that $\sigma$ has $m$ cycles of pairwise distinct sizes.

Given such a permutation $\sigma,$ choose $j = j(\sigma)$ maximal subject to the fact that the $r$-th shortest cycle of $\sigma$ has size $r$ whenever $r \leq j$ - the possibility that $j =0$ is allowed, and occurs precisely when the shortest cycle of $\sigma$ has size greater than one. Note that the $j+1$-st shortest cycle of $\sigma$ (if there is one) has size at least $j+2$ by the maximality of $j$.

If $\sigma$ has more than $j+1$ disjoint cycles, then we may produce a permutation $\tau$ with $m$ disjoint cycles of pairwise distinct lengths and with $|C_{S_{n}}(\tau)| < |C_{S_{n}}(\sigma)|.$ We simply shorten the $j+1$-st shortest cycle of $\sigma$ by one, and lengthen the longest cycle of $\sigma$ by one. The resulting permutation $\tau$ still has all its $m$ disjoint cycles of pairwise distinct lengths, but we see easily that if $a$ is the length of the $j+1$-st shortest cycle of $\sigma$ and $b > a $ is the length of the longest cycle of $\sigma,$ then $ab|C_{S_{n}}(\tau)|= (b+1)(a-1)|C_{S_{n}}(\sigma)|$, so the claim follows as $(b+1)(a-1) < ab.$

Hence we can "improve" our choice of $\sigma$ if $\sigma$ has more than one cycle of length greater than $j+1,$ so the unique minimizing choice of $\sigma$ has its $r$-th cycle of length $r$ for $r \leq j$ and only one cycle of length greater than $j+1$. This forces $j = m-1$ or $j =m.$

Hence if $n \geq \frac{m(m+1)}{2},$ the unique choice of $\sigma$ with $m$ disjoint cycles of pairwise distinct lengths which minimizes $|C_{S_{n}}(\sigma)|$ has its $r$-th cycle of length $r$ for $1 \leq r \leq m-1$ and one cycle of length $n - \frac{m(m-1)}{2}.$ Note that the size of the corresponding conjugacy class is greater than $\frac{(n-1)!}{(m-1!)}$.

While this does not directly answer the question, it does perhaps give some insight.

Geoff Robinson
  • 44.4k
  • 5
  • 123
  • 169