Editing Symmetric group (section)

== Subgroup structure ==
A [[subgroup]] of a symmetric group is called a [[permutation group]].

=== Normal subgroups ===
The [[normal subgroup]]s of the finite symmetric groups are well understood. If {{math|''n'' ≤ 2}}, S<sub>''n''</sub> has at most 2 elements, and so has no nontrivial proper subgroups. The [[alternating group]] of degree ''n'' is always a normal subgroup, a proper one for {{math|''n'' ≥ 2}} and nontrivial for {{math|''n'' ≥ 3}}; for {{math|''n'' ≥ 3}} it is in fact the only nontrivial proper normal subgroup of {{math|S<sub>''n''</sub>}}, except when {{math|1=''n'' = 4}} where there is one additional such normal subgroup, which is isomorphic to the [[Klein four group]].

The symmetric group on an infinite set does not have a subgroup of index 2, as [[Giuseppe_Vitali|Vitali]] (1915<ref>{{cite journal |first=G. |last=Vitali |title=Sostituzioni sopra una infinità numerabile di elementi |journal=Bollettino Mathesis |volume=7 |pages=29–31 |date=1915 |doi= |url=}}</ref>) proved that each permutation can be written as a product of three squares. (Any squared element must belong to the hypothesized subgroup of index 2, hence so must the product of any number of squares.) However it contains the normal subgroup ''S'' of permutations that fix all but finitely many elements, which is generated by transpositions. Those elements of ''S'' that are products of an even number of transpositions form a subgroup of index 2 in ''S'', called the alternating subgroup ''A''. Since ''A'' is even a [[characteristic subgroup]] of ''S'', it is also a normal subgroup of the full symmetric group of the infinite set. The groups ''A'' and ''S'' are the only nontrivial proper normal subgroups of the symmetric group on a countably infinite set. This was first proved by [[Luigi_Onofri|Onofri]] (1929<ref>§141, p.124 in {{cite journal |first=L. |last=Onofri |title=Teoria delle sostituzioni che operano su una infinità numerabile di elementi |journal=Annali di Matematica |volume=7 |issue=1 |pages=103–130 |date=1929 |doi=10.1007/BF02409971 |s2cid=186219904 |url=|doi-access=free }}</ref>) and independently [[J%C3%B3zef_Schreier|Schreier]]–[[Stanislaw_Ulam|Ulam]] (1934<ref>{{cite journal |last1=Schreier |first1=J. |last2=Ulam |first2=S. |title=Über die Permutationsgruppe der natürlichen Zahlenfolge |journal=Studia Math |volume=4 |issue=1 |pages=134–141 |date=1933 |doi= 10.4064/sm-4-1-134-141|url=http://matwbn.icm.edu.pl/ksiazki/sm/sm4/sm4120.pdf}}</ref>). For more details see {{harv|Scott|1987|loc=Ch. 11.3}}. That result, often called the Schreier-Ulam theorem, is superseded by a stronger one which says that the nontrivial normal subgroups of the symmetric group on a set <math>X</math> are 1) the even permutations with finite support and 2) for every cardinality <math>\aleph_0 \leq \kappa \leq |X|</math> the group of permutations with support less than <math>\kappa</math> {{harv|Dixon|Mortimer|1996|loc=Ch. 8.1}}.

=== Maximal subgroups ===
{{expand section|date=September 2009}}

The [[maximal subgroup]]s of {{math|S<sub>''n''</sub>}} fall into three classes: the intransitive, the imprimitive, and the primitive.  The intransitive maximal subgroups are exactly those of the form {{math|S<sub>''k''</sub> × S<sub>''n''–''k''</sub>}} for {{math|1 ≤ ''k'' < ''n''/2}}.  The imprimitive maximal subgroups are exactly those of the form {{math|S<sub>''k''</sub> wr S<sub>''n''/''k''</sub>}}, where {{math|2 ≤ ''k'' ≤ ''n''/2}} is a proper divisor of ''n'' and "wr" denotes the [[wreath product]].  The primitive maximal subgroups are more difficult to identify, but with the assistance of the [[O'Nan–Scott theorem]] and the [[classification of finite simple groups]], {{harv|Liebeck|Praeger|Saxl|1988}} gave a fairly satisfactory description of the maximal subgroups of this type<!-- though beware of typos in the low degrees-->, according to {{harv|Dixon|Mortimer|1996|p=268}}.

=== Sylow subgroups ===
The [[Sylow subgroup]]s of the symmetric groups are important examples of [[p-group|''p''-groups]].  They are more easily described in special cases first:

The Sylow ''p''-subgroups of the symmetric group of degree ''p'' are just the cyclic subgroups generated by ''p''-cycles.  There are {{math|1=(''p'' − 1)!/(''p'' − 1) = (''p'' − 2)!}} such subgroups simply by counting [[Presentation of a group|generators]].  The [[normalizer]] therefore has order {{math|''p''⋅(''p'' − 1)}} and is known as a [[Frobenius group]] {{math|''F''<sub>''p''(''p''−1)</sub>}} (especially for {{math|1=''p'' = 5}}), and is the [[affine general linear group]], {{math|AGL(1, ''p'')}}.

The Sylow ''p''-subgroups of the symmetric group of degree ''p''<sup>2</sup> are the [[wreath product]] of two cyclic groups of order ''p''.  For instance, when {{math|1=''p'' = 3}}, a Sylow 3-subgroup of Sym(9) is generated by {{math|1=''a'' = (1 4 7)(2 5 8)(3 6 9)}} and the elements {{math|1=''x'' = (1 2 3), ''y'' = (4 5 6), ''z'' = (7 8 9)}}<!-- or just use (1,2,3) -->, and every element of the Sylow 3-subgroup has the form {{math|1=''a''<sup>''i''</sup>''x''<sup>''j''</sup>''y''<sup>''k''</sup>''z''<sup>''l''</sup>}} for {{tmath|1=0 \le i,j,k,l  \le 2}}.

The Sylow ''p''-subgroups of the symmetric group of degree ''p''<sup>''n''</sup> are sometimes denoted W<sub>''p''</sub>(''n''), and using this notation one has that {{math|W<sub>''p''</sub>(''n'' + 1)}} is the wreath product of W<sub>''p''</sub>(''n'') and W<sub>''p''</sub>(1).

In general, the Sylow ''p''-subgroups of the symmetric group of degree ''n'' are a direct product of ''a''<sub>''i''</sub> copies of W<sub>''p''</sub>(''i''), where {{math|1= 0 ≤ ''a<sub>i</sub>'' ≤ ''p'' − 1}} and {{math|1=''n'' = ''a''<sub>0</sub>&nbsp;+&nbsp;''p''⋅''a''<sub>1</sub>&nbsp;+&nbsp;...&nbsp;+&nbsp;''p''<sup>''k''</sup>⋅''a''<sub>''k''</sub>}} (the base ''p'' expansion of ''n'').

For instance, {{math|1=W<sub>2</sub>(1) =&nbsp;C<sub>2</sub> and W<sub>2</sub>(2) =&nbsp;D<sub>8</sub>}}, the [[dihedral group of order 8]], and so a Sylow 2-subgroup of the [[symmetric group]] of degree 7 is generated by {{math|{ (1,3)(2,4), (1,2), (3,4), (5,6) } }} and is isomorphic to {{math|D<sub>8</sub> × C<sub>2</sub>}}.

These calculations are attributed to {{harv|Kaloujnine|1948}} and described in more detail in {{harv|Rotman|1995|p=176}}.  Note however that {{harv|Kerber|1971|p=26}} attributes the result to an 1844 work of [[Augustin-Louis Cauchy|Cauchy]], and mentions that it is even covered in textbook form in {{harv|Netto|1882|loc=§39–40}}.

===<span id="Transitive subgroup anchor"></span> Transitive subgroups ===<!-- Transitive subgroup redirects to this anchor-->
A '''transitive subgroup''' of S<sub>''n''</sub> is a subgroup whose action on {1,&nbsp;2,&nbsp;,...,&nbsp;''n''} is [[transitive action|transitive]]. For example, the Galois group of a ([[finite extension|finite]]) [[Galois extension]] is a transitive subgroup of S<sub>''n''</sub>, for some ''n''.

===Young subgroups===
{{main|Young subgroup}}
A subgroup of {{math|S<sub>''n''</sub>}} that is generated by transpositions is called a ''Young subgroup''.  They are all of the form <math>S_{a_1} \times \cdots \times S_{a_\ell}</math> where <math>(a_1, \ldots, a_\ell)</math> is an [[integer partition]] of {{mvar|n}}.  These groups may also be characterized as the [[parabolic subgroup of a reflection group|parabolic subgroup]]s of {{math|S<sub>''n''</sub>}} when it is viewed as a [[reflection group]].

===Cayley's theorem===
[[Cayley's theorem]] states that every group ''G'' is isomorphic to a subgroup of some symmetric group.  In particular, one may take a subgroup of the symmetric group on the elements of ''G'', since every group acts on itself faithfully by (left or right) multiplication.