Primitive permutation group

In mathematics, a permutation group G acting on a set X is called primitive if G acts transitively on X and G preserves no nontrivial partition of X. Otherwise, if G does preserve a nontrivial partition, G is called imprimitive.

This terminology has been introduced in his last letter by Évariste Galois who called (in French) equation primitive an equation whose Galois group is primitive.

In the same letter he stated also the following theorem.

If G is a primitive solvable group acting on a finite set X, then the order of X is a power of a prime number p, X may be identified with an affine space over the finite field with p elements and G acts on X as a subgroup of the affine group.

An imprimitive permutation group is an example of an induced representation; examples include coset representations G/H in cases where H is not a maximal subgroup. When H is maximal, the coset representation is primitive.

If the set X is finite, its cardinality is called the "degree" of G. The numbers of primitive groups of small degree were stated by Robert Carmichael in 1937:

Degree	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	OEIS
Number	1	2	2	5	4	7	7	11	9	8	6	9	4	6	22	10	4	8	4	A000019

Note the large number of primitive groups of degree 16. As Carmichael notes, all of these groups, except for the symmetric and alternating group, are subgroups of the affine group on the 4-dimensional space over the 2-element finite field.

While primitive permutation groups are transitive by definition, not all transitive permutation groups are primitive. The requirement that a primitive group be transitive is necessary only when X is a 2-element set; otherwise, the condition that G preserves no nontrivial partition implies that G is transitive.

Examples

• Consider the symmetric group S₃ acting on the set X = {1,2,3} and the permutation

$\eta=\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}$ .

The group generated by η and S₃ are both primitive.

• Now consider the symmetric group S₄ acting on the set {1,2,3,4} and the permutation

$\sigma=\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{pmatrix}$ .

The group generated by σ is not primitive, since the partition (X₁,X₂) where X₁ = {1,3} and X₂ = {2,4} is preserved under σ, i.e. σ(X₁) = X₂ and σ(X₂) = X₁.

• Every transitive group of prime degree is primitive
• Every simple group is primitive. In particular the symmetric group S_n is primitive for every n>1 and the alternating group A_n is primitive for every n>2.

See also

• Block (permutation group theory)
• Jordan's theorem (symmetric group)

References

• Roney-Dougal, Colva M. The primitive permutation groups of degree less than 2500, Journal of Algebra 292 (2005), no. 1, 154–183.
• The GAP Data Library "Primitive Permutation Groups".
• Carmichael, Robert D., Introduction to the Theory of Groups of Finite Order. Ginn, Boston, 1937. Reprinted by Dover Publications, New York, 1956.
• Rowland, Todd; Primitive Group Action. MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. [1]