Finite Groups, p Cycles Generate an Alternating/Symmetric Group

Primitive Permutation Groups

Let G be a permutation group in Sn. Let T, a subset of the n elements, be a block if G maps T onto T or G maps T to a set of elements disjoint from T. The block stays where it is, or it moves entirely. Obviously any single element acts as a block. If a block has size 1 or n, it is trivial.

The group G is primitive if all blocks are trivial.

Assume G is transitive, and is generated by isolated p cycles. Let T be a nontrivial block, and let c be one of the generators. We know that c, invoked again and again, eventually produces the identity permutation. Let k be the smallest exponent such that ck maps T onto itself. Clearly k divides p, hence k = 1 or p. If k = p then c moves t elements onto another t elements, then another, then another, covering t×p elements. This is a set of p cycles running in parallel, not an isolated p cycle. Therefore k = 1, and c maps T onto T. Since G is generated by these cycles, G maps T onto T. Yet G is transitive, so T is all of S.

a transitive group generated by p cycles is primitive.

A Primitive Permutation Group is Symmetric or Alternating

If G is primitive inside Sn, and G contains a transposition, then G = Sn. Prove this by induction on k, as k runs from 2 to n.

Since there is a transposition, G includes the subgroup S2. This is our starting point, k = 2.

Let G include Sk, permuting the k elements in a subset U of S. Let V be the complement of U in S. If a transposition swaps something in U for something in V, G contains Sk+1. If there is no such transposition, we have more work to do.

Let H be the subgroup of G generated by all transpositions. Note that H maps U to U and V to V. Therefore H has at least two orbits in S. The conjugate of a transposition is another transposition, so H is normal in G. Let r, a permutation in G, move x to y, where x and y are in the same orbit of H. Where does r take z if z is in this same orbit? Let q be the permutation in H that takes z to x. Thus rq takes z to y. (Remember, the action of rq is q followed by r.) Let r take z to w. Now rq/r takes w to y, and since H is normal, rq/r is in H. Thus w and y are in the same orbit.

We applied r to x and z, where x and z are in the same orbit of H, and produced two more points in this same orbit. If one stays in our "neighborhood", so does the other. In other words, the orbits of H are blocks under G.

Since G is primitive, H must not define a block of size k between 1 and n. This is a contradiction, hence H swaps elements between U and V.

At each step a transposition mixes U and V, and k advances until G = Sn.

Now suppose G is primitive and contains a 3 cycle. This means G contains A3, i.e. k = 3. Proceed by induction as before.

A 3 cycle in both U and V allows us to extend U by either 1 or two elements. Otherwise H is the subgroup generated by all the 3 cycles of G. The conjugate of a 3 cycle is a 3 cycle, hence H is normal in G. Run the same orbit-block argument as above. You'll get the same contradiction, hence we can ratchet k all the way up to n.

p Cycles Generate Alternating/Symmetric Groups

The corollary is more important than the theorem. If a permutation group on p elements includes a p cycle and a 2 cycle, it is primitive, and transitive, and generated by p cycles, hence it is Sp. We are simply putting the previous theorems together.

Similarly, a p cycle and a 3 cycle generate Ap.