Primitive permutation group

In mathematics, a permutation group G acting on a non-empty finite set X is called primitive if G acts transitively on X and the only partitions the G-action preserves are the trivial partitions into either a single set or into |X| singleton sets. Otherwise, if G is transitive and G does preserve a nontrivial partition, G is called imprimitive.

While primitive permutation groups are transitive, not all transitive permutation groups are primitive. The simplest example is the Klein four-group acting on the vertices of a square, which preserves the partition into diagonals. On the other hand, if a permutation group preserves only trivial partitions, it is transitive, except in the case of the trivial group acting on a 2-element set. This is because for a non-transitive action, either the orbits of G form a nontrivial partition preserved by G, or the group action is trivial, in which case all nontrivial partitions of X (which exists for |X| ≥ 3) are preserved by G.

This terminology was introduced by Évariste Galois in his last letter, in which he used the French term équation primitive for an equation whose Galois group is primitive.

Properties

In the same letter in which he introduced the term "primitive", Galois stated 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. Further, 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.

If the set X on which G acts is finite, its cardinality is called the degree of G.

A corollary of this result of Galois is that, if Template:Mvar is an odd prime number, then the order of a solvable transitive group of degree Template:Mvar is a divisor of $p(p-1).$ In fact, every transitive group of prime degree is primitive (since the number of elements of a partition fixed by Template:Mvar must be a divisor of Template:Mvar), and $p(p-1)$ is the cardinality of the affine group of an affine space with Template:Mvar elements.

It follows that, if Template:Mvar is a prime number greater than 3, the symmetric group and the alternating group of degree Template:Mvar are not solvable, since their order are greater than $p(p-1).$ Abel–Ruffini theorem results from this and the fact that there are polynomials with a symmetric Galois group.

An equivalent definition of primitivity relies on the fact that every transitive action of a group G is isomorphic to an action arising from the canonical action of G on the set G/H of cosets for H a subgroup of G. A group action is primitive if it is isomorphic to G/H for a maximal subgroup H of G, and imprimitive otherwise (that is, if there is a proper subgroup K of G of which H is a proper subgroup). These imprimitive actions are examples of induced representations.

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	21	22	23	24	OEIS
Number	1	2	2	5	4	7	7	11	9	8	6	9	4	6	22	10	4	8	4	9	4	7	5	Template:OEIS link

There are a large number of primitive groups of degree 16. As Carmichael notes,Template:Pages? 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.

Examples

• Consider the symmetric group $S_3$ acting on the set $X=\{1,2,3\}$ and the permutation

$\eta =\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right).$

Both $S_3$ and the group generated by $\eta$ are primitive.

• Now consider the symmetric group $S_4$ acting on the set $\{1,2,3,4\}$ and the permutation

$\sigma =\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 3& 4& 1\end{array}\right).$

The group generated by $\sigma$ is not primitive, since the partition $(X_1,X_2)$ where $X_1=\{1,3\}$ and $X_2=\{2,4\}$ is preserved under $\sigma$, i.e. $\sigma (X_1)=X_2$ and $\sigma (X_2)=X_1$.

• Every transitive group of prime degree is primitive
• The symmetric group $S_n$ acting on the set $\{1,\dots ,n\}$ is primitive for every n and the alternating group $A_n$ acting on the set $\{1,\dots ,n\}$ is primitive for every n > 2.

See also

• Block (permutation group theory)
• Jordan's theorem (symmetric group)
• O'Nan–Scott theorem, a classification of finite primitive groups into various types

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.
• Template:MathWorld