# Injective proof about sizes of conjugacy classes in S_n

It's not hard to count the number of permutations in a given conjugacy class of Sn. In particular, the number of permutations in Sn whose cycle decomposition has ci i-cycles is n!/(Πi=1n ci!ici). It's also not too hard to see that this is maximized for the conjugacy class that leaves one element fixed and permutes the others in an (n-1)-cycle, and that this is strictly the maximum when n ≥ 3.

What I'm looking for is an "injective proof" of this fact. Namely, a set of injections from the other conjugacy classes into the set of (n-1)-cycles. Ideally you should be able to define a single nice function from Sn into these cycles, which is injective but not surjective (for n ≥ 3) when restricted to every other conjugacy class.

-
I'm still pretty interested in finding an answer to this, though I haven't really made any progress myself. Here's something you might think about, though. The second-largest conjugacy classes (there are a few of these for small n) are the ones of size (n-1)! (by contrast, there are n!/(n-1) (n-1)-cycles). So to make an obviously non-surjective mapping from these second-biggest sets, we might try thinking about which element gets fixed in the image. It would be nice if exactly one element never gets, so that the functions are clearly not surjective.... –  Jonah Ostroff Nov 2 '09 at 15:56
(Append the word "fixed" after "gets" in the last sentence above.) Something that seems to work here is fixing whichever element follows the 1 in Sonia's cycle ordering below. In the second-biggest conjugacy classes, everything but 1 meets this condition exactly (n-2)! times, which is what we'd hope if there are (n-1)! permutations total in that class. Where to go from there, though, eludes me. Perhaps someone else can figure it out. (Now with bounty!) –  Jonah Ostroff Nov 2 '09 at 15:59

For any cycle decomposition, we can uniquely order the cycles from smallest length to largest length, breaking ties between cycles of the same length in some fixed arbitrary way (say by maximal elements). Let us do this for concreteness.

Suppose there was an (injective) way to "join" and A-cycle and a B-cycle together to form an A+B cycle whenever |A| and |B| are > 1. Then, given any cycle decomposition as above, one can start bubbling the two largest cycles together to eventually form a single cycle of some length m.

If m = n - 1, we are done.

If m = n, write S = (1............) and then omit the last term.

If m = 1 the problem is very easy.

If n - 1 > m > 2, there is an injective map from m-cycles to elements whose cycle decomposition is a product of an m-cycle with a 2-cycle. For concreteness, one can add the 2-cycle with the two lowest missing entries. Now bubble again to form an m+2 cycle.

If m = 2, and n is at least 5, bubble with a 3-cycle.

If m = 2 and n = 4 (the last case), form whatever bijection you like between the two sets of 6 elements.

The key point is therefore to find a way to bubble an A-cycle and a B-cycle when |A|,|B| > 1. We do this as follows.

Amongst the entries of A and B, there is a unique smallest integer, call it X.

Case 1. If X lies in A, Let Z denote the largest element of B. Then one can (uniquely) write A = (X.....) and B = (.....Y,Z), where Y < Z. Then consider the A+B cycle obtained by concatenating A and B in this form, i.e. (X,......,Y, Z).

Case 2. If X lies in B, let Z denote the smallest element of A. Then one can (uniquely) write B = (X....) and A = (.....,Y,Z), where now Y > Z. Then consider the A+B cycle (X,.....,Y,Z).

Given an A+B cycle, one can uniquely write it in the form (X,....,Y,Z), where X is the smallest entry. Then one can break it up into an A-cycle and B-cycle depending on whether Y < Z or Y > Z.

Since this was apparently a little confusing, suppose that the cycle lengths of S are a_1 <= a_2 <= a_3 <= ..... <= a_r. Here I omit the 1-cycle lengths, so a_1 > 1, and sum a_r = m for some m possibly less than n. Then the cycle lengths of the steps in the algorithm will have lengths:

(a_1, ...., a_(r-1),a_r),

(a_1, ...., a_(r-2),a_(r-1) + a_r),

(a_1, ...., a_(r-3),a_(r-2) + a_(r-1) + a_r),

....

(a_1 + a__2 + ... + a_r) = (m)

(2,m)

(m+2)

(2,m+2)

(m+4)

...

(n-1 or n, depending on m mod 2),

then n-1.

(if m = 2 and n is at least 5, then instead it should go

(2) --> (2,3) --> (5) --> (2,5) --> (7) --> (2,7) --> (9) ...,etc.

-
That's a really nice argument! –  Sonia Balagopalan Nov 3 '09 at 16:58
The breakup isn't unique; (2, 4, 5, 3, 7), for instance, is the image of both (2 4 5) + (3 7) and (2 4) + (5 3 7). Maybe it's unique when |A| < |B|, but I don't think what you said is quite enough to prove this. –  Harrison Brown Nov 3 '09 at 17:14
Hmm, now that I think about it, it doesn't even work uniquely when |A| < |B|, although if you specify a conjugacy class the examples like I mentioned above do decompose uniquely. I'll have to think about it some more. –  Harrison Brown Nov 3 '09 at 17:22
I guess I'm uncomfortable saying that a case needs to be checked "by hand". I'd feel better if instead we could do the following: given an A-cycle for |A| > 1 and 1-cycles, bubble them together to make an A+2-cycle. A similar technique to the other bubbling should work: look at the smallest element x between A and the two 1-cycles. If it's in A, bubble things together with A first (starting at x) and the larger fixed point last. If it's a fixed point, bubble them together with the fixed points first (starting with x) and ending with the smallest element of A. Again, easy to undo. –  Jonah Ostroff Nov 3 '09 at 17:47
Between these two bubbling techniques, we can repeatedly bubble together the two or three largest cycles until we hit one of two walls: either we're stuck with two cycles (one of length 1 and another of length n-1, so we're done) or a big n-cycle (which we truncate to get an n-1-cycle). If people are satisfied with my second bubbling technique (which really just uses FC's ideas), I'm happy to give FC the check (and the bounty). –  Jonah Ostroff Nov 3 '09 at 17:49

This is rather vague, but I'll try and restate the question to something I think can be done without much difficulty. Here goes:
What you want is a fixed way of representing each permutation (written as its cycle decomposition, but with rules as to what order the cycles are written in and for picking first elements of each cycle, and an ordering of all permutations of a particular cycle type under this "representation"), such that the (n-1)-cycles you get from reading off the first n-1 symbols of each permutation are all different.

We can write down the permutation \sigma with bigger cycles first, and within cycles of same size (if size >1), we can choose the cyle containing the least of the symbols (from {1,2,...,N}), say x, let the first cycle be (x,\sigma(x),...,\sigma^(d-1)(x)) (where d is the order of x in \sigma), look for the smallest of the remaining symbols, etc. For cycles of size 1, we may have to reverse the ordering, or apply some sort of cyclic order.

-
Yeah, this seems like the general way to go. But then in S_4, both (12)(3)(4) and (23)(1)(4) get mapped to (123)=(231). Or, for an example without fixed points, in S_5 we've got (123)(45) and (234)(15) getting mapped to (1234)=(2341). –  Jonah Ostroff Oct 28 '09 at 12:25
Yeah, that's pretty much where I'm stuck. I can work around it in some cases, but there's still no general answer in sight. –  Sonia Balagopalan Oct 28 '09 at 13:13

The second largest conjugacy class in Sn is the n-cycles, which make up 1/n of all elements of S. Although I haven't thought about this too hard, it may be easier to find an injection from C to the set of n-cycles in Sn, where C is any conjugacy class in Sn other than the largest one. The "hard part" here in finding an injection from C to permutations with a fixed point and an (n-1)-cycle could be choosing the fixed point, and finding an injection from C to the set of n-cycles would avoid that problem.

-