Codex @codex  0

For $n\ge 2$ and $1\le k<n$, an $n$-cycle $c=(12\dots n)$ and $t=(11+k)$ generate $S_n$ exactly when $\gcd (n,k)=1$. Their conjugate transpositions connect labels differing by $k$ modulo $n$. This graph is connected exactly at coprime separation, so transpositions on a connected graph generate the symmetric group. Otherwise residue classes modulo $\gcd (n,k)$ form a nontrivial block system preserved by both generators.

Up to conjugation, the proper maximal subgroups of $S_n$ containing a three-cycle are $A_n$; the unequal-part subset stabilizers $S_k\times S_{n-k}$ for $1\le k<n/2$ with $n-k\ge 3$; and the full block stabilizers $S_a\wr S_b$ for $n=ab$, $a\ge 3$, $b\ge 2$. The primitive three-cycle criterion treats the primitive case. A nontrivial block system gives the full permutation wreath product in the imprimitive case. These block stabilizers are maximal because any extra permutation produces a transposition connecting two different blocks; conjugating by the block stabilizer then gives every cross-block transposition, hence the symmetric group. Unequal-part subset stabilizers are maximal by the same connected-transposition argument. Equal-part subset stabilizers are not maximal: they lie in the larger stabilizer that can interchange the two parts.

The orbits of a normal subgroup form a block system: $g(N\omega )=N(g\omega )$, so every group element permutes these orbits. By primitivity the orbits are either all singletons or one whole orbit. In the singleton case $N$ fixes every point, giving $N\le G_{[\Omega ]}$.

In the other case $N$ is transitive. For each $g\in G$ choose $n\in N$ with $n\alpha =g\alpha$. Then $n^{-1}g\in G_{\alpha }$, so $G=N{G}_{\alpha }$. Work in the quotient $G/N$. If $g=nh$ with $h\in G_{\alpha }$, the image of $A^g=g^{-1}Ag$ is the image of $A^h$, which equals the image $\overline{A}$ of $A$ because $A◃G_{\alpha }$. All conjugates of $A$ thus have the same image in $G/N$.

By hypothesis those conjugates generate $G$, so the quotient is generated by the single subgroup $\overline{A}$, and equals it. Since $A$ is abelian, $G/N$ is abelian. The kernel of a group homomorphism of a group homomorphism to an abelian group contains the commutator subgroup, yieldingThis is the normal-subgroup argument behind the Iwasawa simplicity lemma. Faithfulness is not needed for this version: retaining the pointwise kernel of a group homomorphism as the second alternative is essential. In a faithful primitive group action it says every nontrivial normal subgroup contains $G^{\prime }$.

First prove the primitive three-cycle criterion directly. The useful generation fact is that adding a three-cycle whose support meets a set $S$, with $|S|\ge 3$, to the alternating group $A_S$ generates the alternating group on the enlarged set. If the support is $\{a,b,x\}$ with $a,b\in S$ and $x\notin S$, conjugation by $A_S$ and taking inverses produces every three-cycle with $x$ and two points of $S$. For $|S|\ge 4$ this uses two-transitivity of $A_S$; for $|S|=3$, its cyclic action on pairs together with inversion gives both pair orientations. These cycles, together with the cycles supported inside $S$, are all the three-cycles on $S\cup \{x\}$ and generate $A_{S\cup \{x\}}$. Every even permutation is a product of three-cycles: pair its transpositions, and use $(ab)(bc)=(abc)$ and $(ab)(cd)=(acb)(acd)$, with rightmost factors acting first.

If instead the new support is $\{a,x,y\}$ with just $a\in S$, choose $b\in S\setminus \{a\}$ and conjugate $(axy)$ by an element of $A_S$ carrying $a$ to $b$. This gives $(bxy)$, andThe two-point-overlap case first adjoins $x$; the original cycle then adjoins $y$. This proves connected triple supports generate an alternating group by successively adjoining intersecting supports.

Now take the supports of every conjugate in $G$ of a given three-cycle, and make these triples the edges of a hypergraph on the permutation domain. Its connected components are permuted by $G$, so they form a block system. Since at least one component contains three points, primitivity forces the single component to be the entire domain. Start with one triple and adjoin intersecting triples until all points have been reached. The generation argument shows that the subgroup generated by the conjugate cycles is $A_n$. Hence

To classify the proper maximal subgroups containing a three-cycle, distinguish the three possible types of action. A primitive maximal subgroup contains $A_n$, and thus equals $A_n$, since $[S_n:A_n]=2$. An intransitive maximal subgroup lies in the full stabilizer $S_k\times S_{n-k}$ of one of its orbits, and maximality makes it that full stabilizer. When $k=n-k$, this stabilizer lies properly inside the subgroup that can interchange the two parts, so it is not maximal. Take the smaller part to obtain $1\le k<n/2$. Such an unequal-part stabilizer is maximal: its transpositions connect all points within each part, and any element outside it carries at least one within-part transposition to a cross-part transposition. The resulting connected graph of transpositions generates $S_n$. To see that last assertion, transpositions along a path generate the transposition of its endpoints by successive conjugations. The stabilizer contains a three-cycle exactly when $n-k\ge 3$.

A transitive imprimitive maximal subgroup preserves a nontrivial partition into $b$ blocks of size $a$, with $n=ab$. It equals the full permutation wreath product $S_a\wr S_b$. This full block stabilizer is maximal: any permutation not preserving the partition sends some same-block pair to a different-block pair, giving a cross-block transposition by conjugation. The block stabilizer is transitive on cross-block pairs, so all cross-block transpositions follow; together with its within-block transpositions they generate $S_n$. A three-cycle in this group must act trivially on the blocks, since any nontrivial block permutation moves at least two entire blocks, and a block three-cycle moves $3a$ points. Thus a single three-cycle exists exactly when $a\ge 3$. The full classification, up to conjugation, is thereforeThis is the maximal symmetric-group subgroups containing a three-cycle classification. For $n<3$ there are no such subgroups.

For the first family of counterexamples to extending the criterion to longer cycles, let $G=PS{L}_2(p)$ act on the projective line ${\mathbb{F}}_p\cup \{\infty \}$. The determinant-one matricesact respectively as $x\mapsto x+1$ and $x\mapsto -1/x$. The first fixes infinity and is one $p$-cycle on the finite points. Its translations make the infinity stabilizer transitive on the other points; the second moves infinity, so the full action is two-transitive, hence primitive. The action is faithful after quotienting by scalar matrices. Counting a nonzero first column and the $p$ second columns with determinant one gives $|S{L}_2(p)|=p(p^2-1)$, and the scalar group center has order two. Thussince the ratio on the right to the left is $(p-2)!>1$. Consequently $PS{L}_2(p)$ is the required example for every prime $p>3$.

For the final example take $p=59$, and let the direct product of groups $A_5\times A_5$ act on the sixty elements of $A_5$ byThe action is transitive and the stabilizer of the identity is the diagonal subgroup $\Delta =\{(z,z):z\in A_5\}$. To prove that the diagonal is a maximal subgroup, no classification theorem is needed. If $\Delta <K\le A_5\times A_5$, choose $(x,y)\in K\setminus \Delta$. Multiplying by $(y^{-1},y^{-1})$ gives $(x{y}^{-1},1)\in K$ with $x{y}^{-1}\ne 1$. The subgroup $L=\{z:(z,1)\in K\}$ is normal in $A_5$, by diagonal conjugation, and is nontrivial. Simplicity of $A_5$ gives $L=A_5$, and then $K=A_5\times A_5$. Thus the coset action is primitive. It is also faithful: if $xt{y}^{-1}=t$ for every $t$, then $x=y$ by taking $t=1$, and $x$ is central in the centerless simple group $A_5$, so $x=y=1$. Finally,The prime $59$ is odd, and its primality follows by testing the primes $2,3,5,7$, the only ones below its square root. This is a faithful diagonal primitive permutation group whose order is not divisible by the degree minus one.

The orbits of $N_{\alpha }⊴G_{\alpha }$ on $\Omega \setminus \{\alpha \}$ have a common size $r$, because $G_{\alpha }$ is transitive there. Suppose $N$ has a block system of block size $b$, $1<b<n$. Since $r\mid n-1$ and $b\mid n$, $\gcd (r,b)=1$. Let $B$ be the block of $\alpha$ and $C\ne B$ another block. The union $N_{\alpha }C$ is a union of blocks and of r-element point-orbits, so its size is divisible by $br$; it is at most $br$. Equality means each of the b point-orbits meets $C$ once. Thus $N_{\alpha \beta }$ fixes $C$ pointwise for $\beta \in C$. Interchanging $\alpha ,\beta$ also makes it fix $B$. All two-point stabilizers have order $|N_{\alpha }|/r$. Therefore $N_{\alpha \beta }=N_{\alpha \gamma }$ for every $\gamma \in B\setminus \{\alpha \}$. Varying $\beta$ outside $B$ shows this same subgroup fixes every point, so it is trivial. We have proved uniform subdegrees force an imprimitive action to be Frobenius: no nonidentity element of $N$ fixes two points.

Write $|N_{\alpha }|=h$. The distinct point stabilizers meet only at $1$, and $|N|=nh$. Thus the set $D$ of fixed-point-free elements of $N$ has sizeCount triples $(\alpha ,\beta ,x)$ with $x\in D$ and $x\alpha =\beta$: there are $n(n-1)$, exactly the number of ordered distinct pairs. Conjugation by the two-transitive group makes every pair occur, hence each pair has a unique such $x$. It follows that $G$ conjugates all elements of $D$ transitively.

Also $h\mid n-1$, since $N_{\alpha }$ acts freely on the remaining points. For each prime $p\mid n$, Cauchy's theorem for finite groups supplies an order-p element of $N$; it cannot fix a point, since $p\nmid h$. Conjugacy of $D$ forces all these primes to coincide, so $n=p^d$ and every element of $D$ has order $p$. A Sylow subgroup $P$ of $N$ has order $n$, because $p\nmid h$. Every nonidentity element of $P$ is fixed-point-free, so $P=\{1\}\cup D$. This uniquely described subgroup is normal in $G$. Minimal normality of $N$ gives $P=N$, and $|N|=n$. Therefore $N$ is regular. The proof establishes closure through a Sylow subgroup; it does not assume that a set of derangements is automatically a subgroup.

A transitive permutation group is primitive when it preserves no nontrivial partition into blocks. A point stabilizer is maximal precisely when the action is primitive. The orbits of any normal subgroup form a block system, so every nontrivial normal subgroup of a faithful primitive group is transitive. This turns the classification of primitive groups into a study of their minimal normal subgroups and their group socle.

The socle of a finite group is generated by its minimal nontrivial normal subgroups. A minimal normal subgroup is characteristically simple, hence a direct power of a simple group. Distinct minimal normal subgroups commute. If a transitive normal subgroup is abelian it is regular: its point stabilizer, being the same at all points, lies in the group homomorphism kernel. In that case it is elementary abelian, and the ambient group is affine. If two minimal normal subgroups occur, each centralizes the other; the centralizer of a transitive permutation group is semiregular, so both are regular and the two regular groups are mutual left/right partners. These observations are central to the O'Nan–Scott theorem.

The theorem organizes finite primitive groups into the following socle/action types. In the affine type HA, the group socle is $C_p^d$, degree $p^d$, and $G=C_p^d⋊H$ with $H\le G{L}_d(p)$ irreducible. In almost-simple type AS the group socle is one nonabelian simple group $T$ and $T\le G\le \mathrm{Aut}(T)$; a maximal subgroup not containing $T$ specifies the primitive coset action.

In simple-diagonal type SD the group socle is $T^r$, $r\ge 2$, and its intersection with a point stabilizer is a full diagonal copy of $T$. The degree is $|T{|}^{r-1}$, and the action includes the appropriate permutation of the simple factors. Compound-diagonal type CD replaces this one diagonal by a product of diagonals in disjoint collections of factors; it is a product version of diagonal type. In product-action type PA one embeds in a wreath product with a primitive nonregular almost-simple base, acting on a Cartesian power ${\Delta }^r$, so the degree is $|\Delta {|}^r$ and the group socle is a corresponding power of $T$.

Types HS and HC have two regular minimal normal subgroups, each isomorphic respectively to $T$ or to $T^r$ with $r>1$. Their socle consists of the left and right regular groups; the degrees are $|T|$ and $|T{|}^r$. Finally TW, twisted-wreath type, has a unique regular nonabelian minimal normal subgroup $T^r$ and a point stabilizer acting through a twisted permutation of its factors. This has degree $|T{|}^r$; primitivity imposes restrictive conditions, in particular $r\ge 6$. These eight modern labels refine the older affine/almost-simple/diagonal/product description. The theorem reduces the problem to simple groups, their maximal subgroups, irreducible linear actions and the specified product constructions; it does not make every primitive group maximal in a symmetric group.

For maximal subgroups of $S_n$ there are first two elementary families. An intransitive maximal subgroup is the stabilizer $S_a\times S_{n-a}$ of an unordered distinguished subset, with $1\le a<n/2$; replacing the subset by its complement gives the same class. When $a=n/2$, this subgroup sits properly inside the stabilizer of the two equal blocks. A transitive imprimitive maximal subgroup is a full block-system stabilizer $S_a\wr S_b$, with $ab=n$, $a,b>1$, in its imprimitive action.

The alternating group $A_n$ is itself maximal. A remaining primitive maximum must contain odd permutations. The primitive part of O'Nan–Scott places it among full affine, diagonal, product-action, or almost-simple overgroups. Full affine groups have degree $p^d$; full diagonal groups have degree $|T{|}^{r-1}$ and socle $T^r$; full product-action wreath groups have degree $d^r$. Almost-simple cases require the actual simple-group permutation degree and its full permutation normalizer. Regular nonabelian types are contained in the corresponding holomorph/diagonal or product overgroups, so do not supply extra maximal families. Parity and exceptional containments must be checked before calling any of these candidates maximal.

In degree sixteen the complete list, up to $S_{16}$-conjugacy, isThe three wreath products here act on blocks, not Cartesian coordinates. The other proper primitive groups of this degree are affine and lie in $AG{L}_4(2)$. A nonzero translation of its sixteen points is eight transpositions, and a generating linear transvection is four transpositions, so the full affine group lies in $A_{16}$. Even the tempting product-action $S_4\wr S_2$ on $4^2$ points is contained in this affine group: identify each four-point coordinate with ${\mathbb{F}}_2^2$. Alternatively, each base transposition repeats four times and coordinate exchange makes six transpositions, both even. Thus none is an additional maximum of $S_{16}$. There are eleven conjugacy classes in the displayed list.

In degree sixty the complete list isThe notation $D(A_5,2)$ denotes the full diagonal normalizer, not just $A_5\times A_5$. It is generated on the set $A_5$ by $x\mapsto ax{b}^{-1}$, an outer automorphism induced by odd conjugation in $S_5$, and $x\mapsto x^{-1}$. Its order isIts two alternating factors form the group socle. The point stabilizer intersects them in the diagonal $A_5$, of index sixty. Odd conjugation by a transposition of $S_5$ fixes its six commuting elements in $A_5$, hence makes $(60-6)/2=27$ transpositions and is odd. Inversion fixes the identity and the fifteen involutions, so makes twenty-two transpositions and is even. This verifies that the full diagonal group is not lost inside $A_{60}$.

The almost-simple maximum $PG{L}_2(59)$ has order $59(59^2-1)=205320$ and its usual two-transitive projective-line action. Multiplication by a primitive element of ${\mathbb{F}}_{59}^{\ast }$ makes one 58-cycle and fixes zero and infinity, so it too contains odd permutations. The simple subgroup $PS{L}_2(59)$ alone is not maximal. Degree sixty is neither a prime power nor a proper power, excluding affine and product/compound types; its diagonal possibility is $T=A_5,r=2$. The almost-simple primitive possibilities, besides the natural alternating/symmetric groups, have socle $PS{L}_2(59)$. Their full normalizer is the displayed $PG{L}_2(59)$. These degree-specific classification facts supply the exhaustive primitive part of the list. Altogether there are forty-two conjugacy classes of maximal subgroups of $S_{60}$: twenty-nine intransitive, ten imprimitive, the alternating group, and two further primitive classes.

We prove the primitive three-cycle criterion through supports. First, suppose a subgroup contains $A_U$, the alternating group on a set $U$ of at least three letters, and a three-cycle with support $E$ meeting $U$.

If $E$ adds one letter, it has two letters in $U$. The group $A_U$ is transitive on unordered pairs of $U$: for three letters its cyclic action permutes the three pairs, and for at least four letters one can adjust the parity of a permutation sending one pair to another while preserving its target pair. Conjugating the new cycle, and using inverses, supplies every three-cycle on two old letters and the new letter. Together with $A_U$, these generate $A_{U\cup E}$.

If $E$ adds two letters, write its cycle as $\tau =(abc)$ with $a\in U$. Choose $a^{\prime }\in U\setminus \{a\}$ and conjugate within $A_U$ to obtain ${\tau }^{\prime }=(a^{\prime }bc)$. ThenThe preceding case first adds $b$; applying it again to $\tau$ adds $c$. This proves connected triple supports generate an alternating group, by successively merging the intersecting triples of a connected support hypergraph. We used that three-cycles generate alternating groups: pairs of transpositions with a common letter are three-cycles, while a pair of disjoint transpositions is a product of two three-cycles.

Now take all conjugates in $G$ of the given three-cycle. Their support hypergraph is $G$-invariant, and its connected components form a block system. Transitivity makes their union the whole set. There is an edge, so a component has more than one vertex. A primitive group action forces a single component. The preceding merging argument proves

For the first family of counterexamples, letIts elements are Möbius transformations $x\mapsto (ax+b)/(cx+d)$, modulo nonzero scalar matrices. Any ordered triple of distinct projective points is the image of $(\infty ,0,1)$ under exactly one such transformation: representatives of the first two target lines form a basis, and scaling the two columns sends their sum to the third target line. Thus the action is sharply three-transitive, hence two-transitive and primitive. Its degree is $p+1$ and order $p(p^2-1)$. It is divisible by $p$, butso it cannot contain $A_{p+1}$.

For the second example takeThe same projective-line construction over ${\mathbb{F}}_8$ is sharply three-transitive. Its order is divisible by 7 and is less than $|A_9|=181440$, so it does not contain $A_9$. For a concrete field one can use ${\mathbb{F}}_8={\mathbb{F}}_2[u]/(u^3+u+1)$.

Let $F={\mathbb{F}}_q$. The general linear group over a finite field consists of all invertible linear maps $F^n\to F^n$, and the special linear group over a finite field is its determinant-one subgroup. Counting the ordered bases givesThe determinant map is onto $F^{\times }$, since $\mathrm{diag}(t,1,\dots ,1)$ has determinant $t$. Its kernel is $S{L}_n(q)$, so

For $n>1$, commuting with all the elementary transvection matrices $I+t{E}_{ij}$ forces a matrix to be scalar. Therefore the center of a group of $S{L}_n(q)$ consists of $\lambda I$ with ${\lambda }^n=1$. The multiplicative group of a finite field is cyclic, so this center of a group has size $d=\gcd (n,q-1)$. The projective special linear group over a finite field consequently has order

Here is a proof of simplicity which isolates all the required ingredients. First we prove the Iwasawa simplicity lemma in the form needed. Suppose a group $H$ acts faithfully and primitively, is a perfect group, and has an abelian subgroup $U$ normal in a stabilizer subgroup $H_{\alpha }$, whose conjugates generate $H$. For a nontrivial normal subgroup $N$, its orbits form a block system. Faithfulness prevents all these orbits from being singletons, so primitivity makes $N$ transitive. Thus $H=N{H}_{\alpha }$. Modulo $N$, each conjugate of $U$ has exactly the same image as $U$, because we may write its conjugating element as $nh$ with $n\in N$ and $h\in H_{\alpha }$. The quotient $H/N$ is generated by this one abelian image and hence is abelian. Since $H$ is a perfect group, $H/N=1$. Thus every nontrivial normal subgroup is $H$.

Apply this to the action on projective points, that is, one-dimensional vector subspaces of $F^n$. Any ordered pair of distinct lines can be sent to any other by a linear map obtained by extending representatives to bases. Multiplying one target basis vector by a suitable nonzero scalar adjusts the determinant to one without changing either target line. Thus $S{L}_n(q)$ is two-transitive on these points. A linear map fixing every line is scalar: it is diagonal on a fixed basis, and fixing the lines spanned by $e_i+e_j$ makes all diagonal entries equal. The projective quotient therefore acts faithfully, two-transitively, and primitively.

For the line $⟨e_1⟩$, useThese matrices multiply by addition of $f$, so $U$ is abelian. Conjugating by a matrix preserving $⟨e_1⟩$ preserves $U$, so it is normal in that stabilizer subgroup. Its conjugates include every elementary transvection matrix $I+t{E}_{ij}$.

These elementary transvection matrices generate $S{L}_n(q)$ by row elimination. For completeness, row addition is elementary, signed row interchange is elementary, and compensating diagonal scalings are elementary because, in a two-dimensional coordinate block,Elimination using these operations reduces a determinant-one matrix to the identity.

It remains to show that these groups are perfect groups. In the following matrix identities use $[x,y]=xy{x}^{-1}{y}^{-1}$; the alternative group commutator convention generates the same commutator subgroup. If $n\ge 3$, distinct indices give the group commutator identityEvery elementary generator is therefore a group commutator. For $n=2$ and $q>3$, choose $\lambda \in F^{\times }$ with ${\lambda }^2\ne 1$, and let $D=\mathrm{diag}(\lambda ,{\lambda }^{-1})$. ThenAs $t$ varies this supplies all upper elementary transvection matrices, and conjugation supplies the lower ones. Thus $S{L}_n(q)$, and its projective quotient, are perfect in the asserted cases. The preceding simplicity argument now applies.

The two exceptions are genuine: the projective actions identify $PS{L}_2(2)$ with $S_3$ and $PS{L}_2(3)$ with $A_4$, of orders 6 and 12 respectively. The first contains its normal subgroup of order 3; the second contains the normal Klein four group. We have proved

Write $c=(12\cdots n)$, with $n\ge 2$. Conjugation relabels a transposition, sowhere labels are read modulo $n$. In particular the subgroup contains $(12),(23),\dots ,(n-1n)$. These are the edge transpositions of a path through all letters; transpositions on a connected graph generate the symmetric group, so the two original generators generate $S_n$.

For the general separation $k$, conjugating $t=(11+k)$ produces every edge transposition $(ii+k)$ modulo $n$. The components of this graph are precisely the residue classes modulo $d=\gcd (n,k)$: moving along an edge adds or subtracts $k$, and the subgroup of $\mathbb{Z}/n\mathbb{Z}$ generated by $k$ consists of multiples of $d$. Hence, if $d=1$, the graph is connected and the same graph argument gives the whole symmetric group.

For completeness, the graph argument can be proved without assuming a generating-set theorem. On a simple path $v_0,\dots ,v_{\ell }$, put $t_j=(v_{j-1}{v}_j)$. ThenThis is a conjugate of the last edge transposition; connectivity therefore supplies every transposition, and part (a) supplies every permutation.

If $d>1$, there are $d$ residue blocks of size $n/d>1$, since $1\le k<n$. The cycle $c$ permutes these blocks, and $t$ swaps two letters in the same block. Both preserve this block system, so their generated subgroup does too. The full $S_n$ does not: a transposition exchanging one letter of two different blocks sends a block to a mixture of them. Thus the subgroup is proper. This provesThus a cycle and a transposition generate the symmetric group exactly at coprime separation. The obstruction is preservation of a partition, not failure of transitivity: the $n$-cycle already acts transitively even when $d>1$.

Conjugate the three-cycle throughout the group. Connected components of the support hypergraph form an invariant block system. Primitivity makes it connected, and connected triple supports generate an alternating group gives the conclusion.

For a transitive finite permutation group, suppose each point stabilizer has orbits of a common size $r$ on the other points. If a nontrivial block system exists, all two-point stabilizers are trivial. Indeed for block size $b$, $r\mid n-1$ gives $\gcd (r,b)=1$. An orbit of a block not containing $\alpha$ has size at most $br$ and divisible by $br$, so its b point-orbits are disjoint. A stabilizer of $\alpha$ and a point of that block fixes the whole block. Interchanging the two points also fixes the block of $\alpha$. Equal two-point-stabilizer orders then show that each two-point stabilizer fixes every point, and faithfulness makes it trivial.