Find the smallest nontrivial conjugacy class in $S_n$.

For small $n$, the answer can be found by counting the permutations of each possible cycle type. The result is: $$\begin{array}{ccc} n & \text{smallest nontrivial class(es)} & \text{size} \\ \hline 1 & \text{none} & \\ 2 & \text{transpositions} & 1 \\ 3 & 3\text{-cycles} & 2 \\ 4 & \text{double transpositions} & 3 \\ 5 & \text{transpositions} & 10 \\ 6 & \text{transpositions, triple transpositions} & 15 \end{array}$$

For $n\geq 7$, I think the unique smallest nontrivial conjugacy class in $S_n$ is given by the transpositions.

The conjugacy classes in $S_n$ are given by the sets of permutations of the same cycle type. For the cycle type $\alpha = 1^{a_1} 2^{a_2} \ldots$, the size of the respective conjugacy class is known to be $$N_\alpha = \frac{n!}{\prod_i (i^{a_i} a_i!)}.$$ In particular, the number of transpositions in $S_n$ is $\binom{n}{2}$.

In this way, it remains to show the following:

Let $n \geq 7$ and $\alpha$ be a partition of $n$ distinct from $1^n$ and $2^1 1^{n-2}$. Show that $N_\alpha > \binom{n}{2}$.

So far I can only come up with a lengthy and technical case-by-case study. I'm looking for a more elegant proof of the statement.

  • $\begingroup$ Could you tell us what kind of case by case study you did? Was it based on the formula you give for the number of elements inside a conjugacy class? $\endgroup$ – Olivier Bégassat May 18 '13 at 20:12
  • $\begingroup$ Would the following argument work? If $i$ is even, we split all the $i$-cycles into $i/2$ $2$-cycles. This increases the denominator in azimut's formula, so the conjugacy class becomes smaller. Similarly, if $i>3$ is odd, then splitting all the $i$-cycles to a product of a single 3-cycle and several 2-cycles makes the class smaller. Thus we are left with the classes of types $1^{a_1}2^{a_2}3^{a_3}$. Again $3^{a_3}a_3!<(3a_3)!$, so we might as well throw away the 3-cycles. The rest should be doable, but is a bit delicate as the tie in $S_6$ shows. $\endgroup$ – Jyrki Lahtonen May 18 '13 at 21:17
  • $\begingroup$ @OlivierBégassat: Indeed, my approach was based on the formula and similar to the one suggested by Jyrki Lahtonen: I took a cycle type different from identity and transposition, and tried to show that it is not the smallest one by splitting cycles (by different rules) such that the resulting conjugacy class is smaller. However, to really decrease the size, for all the rules I tried I got restrictions on the $a_i$. In the end it was a mess of different rules in different situations, to get every cycle type (hopefully) covered. $\endgroup$ – azimut May 18 '13 at 21:21

I don't think there is a very conceptual approach giving a meaning to the comparison of conjugacy class sizes, but I think there is a way to make the argument quite short. The first thing to do is to cancel the term $a_1!$ for $i=1$ (for the points remaining fixed) in the denominator against a part of the numerator $n!$, which leaves the numerator equal to $n(n-1)\ldots(a_1+1)$ (the number of factors is the sum of the sizes of the cycles for the conjugacy class, in the group-theoretic sense where cycles cannot have length$~1$).

A first easy simplification rids us the case of mixed cycle structures, classes with is more than one different cycle length${}\geq2$. For such cycle types we can map permutations in the class to another non-trivial cycle type by simply omitting the cycle(s) of the longest length$~l$ from the decomposition. This map commutes with any conjugation by a permutations (which simple relabels elements in the cycles) and is therefore surjective to a single new conjugacy class; moreover it is not injective since there is always more than one way to reconstruct the length$~l$ cycle(s). Therefore such classes are never the smallest non-trivial ones.

The next step is to show that we need only deal with the case of transpositions, possibly flying in formation. More precisely (and with three exceptions that do not occur for $n\geq7$), the class with $m$ disjoint $k$-cycles with $k>2$ is larger than the one with $m$ disjoint $2$-cycles. We have $a_k=m$ and factor our formula as $$ \frac{n(n-1)\ldots(n-mk+1)}{k^m}\times\frac1{m!}, $$ where the second factor is identical to the one for $k=2$. In the first factor replacing $k$ by $2$ means dropping the last $m(k-2)$ factors from the numerator and dividing the denominator by $(k/2)^m$. Using that a product of $k-2$ distinct positive integers can only be${}\leq k/2$ if $k\leq4$, we see that this decreases the first factor except when $a_1=0$, and $(m,k)\in\{(1,3),(1,4),(2,3)\}$, which happens only for $n=3,4,6$ (it explains that $3$-cycles are least numerous for $n=3$, that for $n=4$ there are as many $4$-cycles as $2$-cycles, namely $6$, and that for $n=6$ there are fewer ($40$) pairs of $3$-cycles then pairs of transpositions $(45)$).

We have reduced to the case of $m$ disjoint transpositions, which we shall compare with isolated transpositions ($m=1$). For fixed $m$, increasing $n$ leaves the denominator unchanged and increases all factors in the numerator by$~1$. This gives more relative increase for $m>1$ than for $m=1$, so if the class with $m$ disjoint transpositions is to be less numerous than that with one transposition, it must already be the case for the minimal possible value of $n$, which is $n=2m$. The formula for the number of products of $m$ disjoint transpositions when $n=2m$ is the product $1\times 3\times\cdots\times(2m-1)$ (which some people, defying the ambiguity, write as $(2m-1)!!$) which is${}\leq\binom{2m}2$ only for $m=2,3$; this explains these cases for $n=4,6$. For $n\geq7$ this does not happen any more.

  • $\begingroup$ Thank you for this great answer! I agree that a "more conceptual approach" is not likely to exist. The idea of splitting each $k$-cycle into a transposition and $k-2$ fixed points is great. Maybe the solution could be made even more compact including the argument of @OlivierBégassat that there is at most one fixed point, which immediately settles the special cases of a single $3$-cycle or a single $4$-cycle, and shows that in the "only transpositions case" $n = 2m$ or $n = 2m + 1$. $\endgroup$ – azimut May 19 '13 at 9:16
  • $\begingroup$ @azimut Right, answer updated (before I read you comments) and corrected (after) now. $\endgroup$ – Marc van Leeuwen May 19 '13 at 10:00
  • $\begingroup$ I think in the step replacing all $k$-cycles by a transposition and $k-2$ fixed points, there is another special case: $n = 3$ and $m = 2$ (here, the first factor doesn't decrease). $\endgroup$ – azimut May 20 '13 at 12:00
  • $\begingroup$ @azimut Worse, it increases. I've corrected. $\endgroup$ – Marc van Leeuwen May 20 '13 at 15:55

This is only a partial argument that solves some cases. The idea is simple: instead of focussing on a particular conjugacy class, we consider that of an appropriate power which has simpler cycle structure.

It follows from the fact that $\binom{n}{2}<\binom nl$ for all $2<l<n-2$ that for any permutation with total length $l$ (i.e. having $n-l$ fixed points), its conjugacy class is stricly bigger than that of the transpositions. Indeed, for every choice of $n-l$ points there are several permutations in that conjugacy class having these as fixed pionts. Also, for $l=n-2$ and $n\geq 5$, for every choice of two points there are several permutations in that conjugacy class having these points as fixed points. So there are only $2$ cases of interest: $l=n-1$ and $l=n$, i.e. $\sigma$ has one fixed point and none respectively.

In any case, if there are two distinct cycle lengths $2\leq k<K$, then we may consider the permutation $\sigma^k$ instead. This permutation is different from the identity, and has at least $2\leq k$ fixed points, so by the previous argument its conjugacy class contains at least $\binom n2$ elements. The map $$\mathrm{Conj}(\sigma)\to\mathrm{Conj}(\sigma^k),~\theta\mapsto \theta^k$$ is onto and non injective whenever $k\geq 3$ or $k=2$ and there are at least two $2$-cycles in $\sigma$. Furthermore if $\sigma$ contains only one $2$ cycle, then there are obviously more than $\binom n2$ elements in the conjugacy class. So your claim is true whenever there $\sigma$ contains cycles of different length.

So there remains one case: $\sigma$ has length $n$ or $n-1$, and only one cycle length $k$.

If $\sigma$ has one fixed point, then the choice of fixed point accounts for $n$ choices already. However it might be easiest to resort back to the formula you mentioned at the beginning: we have $n=qk+1$ and the cardinality equals $\frac{n!}{k^q q!}$.

  • $\begingroup$ Thanks for your answer. I like the idea of replacing $\sigma$ by $\sigma^k$, which increases the size of the stabilizer and therefore decreases the size of the conjugacy class. However, I don't understand your argument why a conjugacy class smaller than the transpositions has at most 1 fixed point in the respective cycle type. Could you add more details on this? $\endgroup$ – azimut May 18 '13 at 22:38
  • $\begingroup$ I don't quite see which part of my argument you want me to add details to. Which paragraph is it? $\endgroup$ – Olivier Bégassat May 18 '13 at 22:47
  • $\begingroup$ Thinking again about it, I got it. That's a very nice observation, thank you! $\endgroup$ – azimut May 18 '13 at 23:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.