Permutation group

In mathematics, particularly within abstract algebra, a permutation group is a group whose elements are permutations of a given finite set and whose binary operation is the composition of such permutations, forming a subgroup of the symmetric group on that set.^[1] The symmetric group $S_n$Sn​, which consists of all possible permutations of a set with $n$n elements, serves as the foundational example and has order $n!$n!, representing the total number of ways to rearrange the elements.^[2] A key result in group theory, known as Cayley's theorem, establishes that every finite group is isomorphic to a permutation group acting regularly on itself, thereby embedding abstract groups into the concrete framework of permutations.^[3] This theorem underscores the universality of permutation groups in modeling symmetries and structures across mathematics. Permutations within these groups can be classified by their sign—even or odd—based on the parity of the number of transpositions needed to express them, leading to the alternating group $A_n$An​, the kernel of the sign homomorphism and a normal subgroup of $S_n$Sn​ of index 2.^[4] For $n \geq 5$n≥5, $A_n$An​ is a simple group, meaning it has no nontrivial normal subgroups, which has profound implications for the classification of finite simple groups.^[5] Permutation groups play a central role in various applications, including the study of geometric symmetries, where they describe the automorphism groups of polytopes and graphs; in combinatorics, for enumerating objects under group actions via tools like Burnside's lemma; and in physics and chemistry, for analyzing molecular symmetries and identical particle systems.^[6] In computational contexts, algorithms for permutation group manipulation, such as membership testing and finding strong generators, enable efficient solutions to problems in computer science and cryptography.^[7] These structures also connect to Galois theory, where permutation groups of roots illuminate the solvability of polynomial equations.^[6]

Fundamentals

Definition

In group theory, a permutation group $G$G on a set $X$X is defined as a subgroup of the symmetric group $\Sym(X)$\Sym(X), where the elements of $G$G are bijections from $X$X to itself, and the group operation is the composition of these bijections.^[8][1] The symmetric group $\Sym(X)$\Sym(X) comprises all permutations of the set $X$X, that is, all bijective functions from $X$X to $X$X, equipped with the operation of function composition, which forms a group under this operation.^[9] When $X$X is finite with cardinality $n$n, the order of $\Sym(X)$\Sym(X) is $n!$n!, reflecting the number of distinct bijections possible.^[10] Permutation groups may be finite or infinite, with the infinite case arising when the underlying set $X$X is infinite, leading to an uncountably many permutations in $\Sym(X)$\Sym(X) for uncountable $X$X.^[9] A basic example is the trivial group, which serves as the permutation group on a singleton set $X = \{ a \}$X={a}, where $\Sym(X)$\Sym(X) consists solely of the identity bijection that maps $a$a to itself.^[10]

Basic Properties

A permutation group $G$G on a set $X$X satisfies the closure property under the group operation of composition: the composition of any two elements $\sigma, \tau \in G$σ,τ∈G is another bijection from $X$X to $X$X, hence also in $G$G.^[11][2] This ensures that $G$G forms a subgroup of the symmetric group $\mathrm{Sym}(X)$Sym(X), the full group of all bijections on $X$X.^[12] The operation of composition in a permutation group inherits associativity from the associativity of function composition: for any $\sigma, \tau, \rho \in G$σ,τ,ρ∈G, $(\sigma \circ \tau) \circ \rho = \sigma \circ (\tau \circ \rho)$(σ∘τ)∘ρ=σ∘(τ∘ρ).^[11][13] When $X$X is finite with $|X| = n$∣X∣=n, any permutation group $G \leq \mathrm{Sym}(X)$G≤Sym(X) is finite, and by Lagrange's theorem applied to the finite group $\mathrm{Sym}(X)$Sym(X) of order $n!$n!, the order of $G$G divides $n!$n!.^[11][14] Every permutation in a permutation group admits a unique decomposition into a product of disjoint cycles, up to ordering of the cycles and rotation within each cycle; this decomposition reveals the structure of the permutation by partitioning the moved points into orbits under repeated application.^[2][13] The cycle type of a permutation is the multiset of lengths of these disjoint cycles, providing a complete invariant for its action on $X$X. The support of a permutation is the subset of $X$X consisting of points not fixed by the permutation, i.e., those appearing in its cycle decomposition (excluding 1-cycles).^[2] Two permutations in $\mathrm{Sym}(X)$Sym(X) are conjugate if and only if they have the same cycle type; that is, $\tau^{-1} \sigma \tau$τ−1στ has the same cycle structure as $\sigma$σ for some $\tau \in \mathrm{Sym}(X)$τ∈Sym(X). In a subgroup $G \leq \mathrm{Sym}(X)$G≤Sym(X), permutations with the same cycle type belong to the same conjugacy class in $\mathrm{Sym}(X)$Sym(X) but may form multiple conjugacy classes in $G$G.^[2][15]

Notation and Operations

Notation Conventions

Permutations of a finite set, such as $\{1, 2, \dots, n\}${1,2,…,n}, are often represented in one-line notation as $\sigma = (\sigma(1) \ \sigma(2) \ \dots \ \sigma(n))$σ=(σ(1) σ(2) … σ(n)), where the sequence lists the images of the elements under the permutation $\sigma$σ.^[16] This compact form emphasizes the functional mapping directly.^[16] Another common representation is the two-row notation, written as $$\begin{pmatrix} 1 & 2 & \dots & n \\ \sigma(1) & \sigma(2) & \dots & \sigma(n) \end{pmatrix},$$(1σ(1)​2σ(2)​……​nσ(n)​), which explicitly pairs each domain element with its image.^[17] This format highlights the bijection between the top and bottom rows.^[17] Cycle notation decomposes a permutation into its disjoint cycles, such as $(1 \ 3 \ 2)(4 \ 5)$(1 3 2)(4 5), where each cycle indicates a cyclic shift and fixed points are typically omitted.^[18] Cycles are written with elements in sequence, starting from an arbitrary point, and the notation is unique up to rotation and ordering of cycles.^[19] In permutation group actions, the convention often distinguishes left and right actions; a right action applies the permutation post-fix, denoted $x^\sigma$xσ for $x$x in the set acted upon, which aligns with standard algebraic composition where permutations multiply on the right.^[20] This right-action preference avoids reversal in group multiplication orders, unlike the left-action form $\sigma(x)$σ(x).^[20] For imprimitive actions, blocks of imprimitivity are denoted as subsets $B_1, B_2, \dots, B_k$B1​,B2​,…,Bk​ forming a partition of the set, where the group permutes these blocks as units while preserving the partition.^[21] Such notation captures the non-trivial equivalence classes under the group action.^[21]

Composition as Group Product

In permutation groups, the group operation is defined as the composition of permutations, which are bijective functions on a finite set. For two permutations $\sigma$σ and $\tau$τ, their product $\sigma \tau$στ is the permutation that applies $\tau$τ first and then $\sigma$σ, formally given by $(\sigma \tau)(x) = \sigma(\tau(x))$(στ)(x)=σ(τ(x)) for all $x$x in the set. This convention aligns with the standard right-to-left order of function composition, where the rightmost permutation is applied initially in any sequence.^[22][23] When computing the product of permutations expressed in cycle notation, the mappings are evaluated sequentially from right to left for each element in the set. To determine the image of an element under the product, start by applying the rightmost cycle, then proceed leftward through the cycles, tracking the position until returning to the starting element or fixing it. For instance, consider the product $(1\ 2)(2\ 3)$(1 2)(2 3): applying $(2\ 3)$(2 3) followed by $(1\ 2)$(1 2) yields $1 \mapsto 2 \mapsto 3$1↦2↦3, $3 \mapsto 2 \mapsto 1$3↦2↦1, and $2 \mapsto 3 \mapsto 3$2↦3↦3 (fixed after the first step, but the cycle closes as $(1\ 2\ 3)$(1 2 3)); thus, $(1\ 2)(2\ 3) = (1\ 2\ 3)$(1 2)(2 3)=(1 2 3). This process ensures the resulting permutation is expressed in disjoint cycle form by identifying all cycles in the mapping.^[22][2] The composition operation is associative, as permutations are functions and function composition satisfies $(\sigma \tau) \rho = \sigma (\tau \rho)$(στ)ρ=σ(τρ) for any permutations $\sigma, \tau, \rho$σ,τ,ρ. To see this, evaluate both sides on an arbitrary $x$x: the left side gives $\sigma(\tau(\rho(x)))$σ(τ(ρ(x))), while the right side gives $\sigma((\tau \rho)(x)) = \sigma(\tau(\rho(x)))$σ((τρ)(x))=σ(τ(ρ(x))), confirming equality. This associativity underpins the group structure.^[24][23] The product of any two elements in a permutation group yields another element within the group, ensuring closure under composition. This property generates new permutations while preserving the group's finite order, as all elements are bijections on a set of fixed size, and repeated compositions remain within the set of all possible permutations.^[24][2]

Identity and Inverses

In permutation groups, the identity element is the permutation that maps every element of the domain to itself, denoted by $e$e or $id$id, and formally defined as $id(x) = x$id(x)=x for all $x$x in the set./15:_Group_Theory_and_Applications/15.03:_Permutation_Groups) This identity serves as the neutral element under composition, satisfying $\sigma \circ id = id \circ \sigma = \sigma$σ∘id=id∘σ=σ for any permutation $\sigma$σ.^[25] Every permutation $\sigma$σ has a unique inverse $\sigma^{-1}$σ−1 such that $\sigma \circ \sigma^{-1} = \sigma^{-1} \circ \sigma = id$σ∘σ−1=σ−1∘σ=id./15:_Group_Theory_and_Applications/15.03:_Permutation_Groups) Since permutations are bijections—both injective and surjective—they are invertible in the set of all functions from the domain to itself, with the inverse also being a bijection.^[25] To compute the inverse in cycle notation, reverse the order of elements in each cycle while preserving the disjoint cycle structure; for example, the inverse of $(1\ 2\ 3)$(1 2 3) is $(3\ 2\ 1)$(3 2 1), which is equivalent to $(1\ 3\ 2)$(1 3 2)./15:_Group_Theory_and_Applications/15.03:_Permutation_Groups) The order of a permutation $\sigma$σ, denoted $|\sigma|$∣σ∣, is the smallest positive integer $k$k such that $\sigma^k = id$σk=id.^[25] For a permutation expressed as a product of disjoint cycles of lengths $l_1, l_2, \dots, l_m$l1​,l2​,…,lm​, the order is the least common multiple of these lengths, $|\sigma| = \operatorname{lcm}(l_1, l_2, \dots, l_m)$∣σ∣=lcm(l1​,l2​,…,lm​)./15:_Group_Theory_and_Applications/15.03:_Permutation_Groups) This follows from the fact that powers of disjoint cycles act independently, and each cycle of length $l_i$li​ returns to the identity after $l_i$li​ applications.^[25]

Examples

Symmetric and Alternating Groups

The symmetric group $S_n$Sn​ consists of all permutations of a set with $n$n elements, which can be viewed as the set of all bijections from $\{1, 2, \dots, n\}${1,2,…,n} to itself under composition.^[26][27] The order of $S_n$Sn​ is $n!$n!, reflecting the number of distinct bijections on an $n$n-element set.^[26][28] Furthermore, $S_n$Sn​ is generated by the set of all transpositions, the permutations that swap exactly two elements and fix the rest, for $n \geq 2$n≥2.^[29][4] The alternating group $A_n$An​ is the subgroup of $S_n$Sn​ comprising all even permutations, defined as those that can be expressed as a product of an even number of transpositions.^[29][30] For $n \geq 2$n≥2, $A_n$An​ has index 2 in $S_n$Sn​, meaning $|A_n| = n!/2$∣An​∣=n!/2, and it is a normal subgroup.^[31][32] Additionally, $A_n$An​ is simple for $n \geq 5$n≥5, possessing no nontrivial normal subgroups.^[33][31] The distinction between even and odd permutations arises from the sign homomorphism $\operatorname{sgn}: S_n \to \{ \pm 1 \}$sgn:Sn​→{±1}, which assigns $+1$+1 to even permutations and $-1$−1 to odd ones, based on the parity of the number of transpositions in their decomposition.^[29][30] The kernel of this homomorphism is precisely $A_n$An​.^[30][32] A concrete example is $S_3$S3​, the symmetric group on three elements, which has order 6 and includes all permutations such as the identity, transpositions like $(1\ 2)$(1 2), and 3-cycles like $(1\ 2\ 3)$(1 2 3).^[4][34] The alternating group $A_3$A3​ consists of the even permutations: the identity and the two 3-cycles $(1\ 2\ 3)$(1 2 3) and $(1\ 3\ 2)$(1 3 2), forming a cyclic group of order 3 generated by $(1\ 2\ 3)$(1 2 3).^[4][34]

Cyclic and Dihedral Groups

The cyclic group $C_n$Cn​ of order $n$n provides a fundamental example of a permutation group, realized as the subgroup generated by the $n$n-cycle $\sigma = (1\ 2\ \dots\ n)$σ=(1 2 … n) acting on the set $\{1, 2, \dots, n\}${1,2,…,n}. The elements of $C_n$Cn​ are the powers $\sigma^k$σk for $k = 0, 1, \dots, n-1$k=0,1,…,n−1, with $\sigma^0$σ0 being the identity permutation, and the group operation is composition of permutations. Since powers of a single generator commute under composition, $C_n$Cn​ is abelian.^[35] A key extension of the cyclic group in the context of permutation groups is the dihedral group $D_n$Dn​ (also denoted $D_{2n}$D2n​ in some conventions), which captures the full symmetry group of a regular $n$n-gon and has order $2n$2n. This group acts faithfully on the $n$n vertices of the polygon as permutations and is generated by a rotation $\rho = (1\ 2\ \dots\ n)$ρ=(1 2 … n), which cycles the vertices, and a reflection $s$s, which swaps pairs of vertices symmetrically while fixing one (for odd $n$n) or passing through midpoints of edges (for even $n$n). The defining relations are $\rho^n = e$ρn=e, $s^2 = e$s2=e, and $s \rho s = \rho^{-1}$sρs=ρ−1, reflecting how reflections conjugate rotations to their inverses.^[36][37] The abstract presentation of $D_n$Dn​ is $\langle \rho, s \mid \rho^n = s^2 = 1, s \rho s^{-1} = \rho^{-1} \rangle$⟨ρ,s∣ρn=s2=1,sρs−1=ρ−1⟩, which encodes its structure as a semidirect product of the cyclic group $C_n$Cn​ by $C_2$C2​. For $n = 3$n=3, the dihedral group $D_3$D3​ consists of the three rotations and three reflections of an equilateral triangle, permuting its vertices, and is isomorphic to the symmetric group $S_3$S3​ of order 6.^[36]

Group Actions

Definition and Examples

In the context of permutation groups, a group action provides a way to realize the elements of a group $G$G as permutations of a set $X$X. Formally, a left action of $G$G on $X$X is a group homomorphism $\phi: G \to \Sym(X)$ϕ:G→\Sym(X), where $\Sym(X)$\Sym(X) denotes the symmetric group consisting of all bijections from $X$X to itself under composition.^[38] Equivalently, it can be described by a map $G \times X \to X$G×X→X, written $(g, x) \mapsto g \cdot x$(g,x)↦g⋅x, that satisfies two axioms: the identity element $e \in G$e∈G acts trivially, so $e \cdot x = x$e⋅x=x for all $x \in X$x∈X, and the action is compatible with the group operation, so $(gh) \cdot x = g \cdot (h \cdot x)$(gh)⋅x=g⋅(h⋅x) for all $g, h \in G$g,h∈G and $x \in X$x∈X.^[20] This homomorphism perspective highlights that every group action induces a permutation representation of $G$G, namely the image $\phi(G)$ϕ(G), which is a subgroup of $\Sym(X)$\Sym(X) acting naturally on $X$X.^[39] The permutation representation arising from a group action captures how $G$G permutes the elements of $X$X; distinct elements of $G$G may induce the same permutation if the action is not injective. A key distinction is between faithful and non-faithful actions: an action is faithful if the kernel of $\phi$ϕ is trivial, meaning $\ker \phi = \{ e \}$kerϕ={e}, so that only the identity element fixes every point in $X$X, and thus $\phi$ϕ embeds $G$G as a subgroup of $\Sym(X)$\Sym(X).^[40] Otherwise, the action is non-faithful, and the kernel is a normal subgroup of $G$G consisting of all elements that act as the identity permutation.^[41] Illustrative examples clarify these concepts. The trivial action of any group $G$G on a set $X$X is defined by $g \cdot x = x$g⋅x=x for all $g \in G$g∈G and $x \in X$x∈X; this always yields a valid action, but it is faithful only if $G$G is the trivial group, and the corresponding permutation representation is the singleton subgroup of $\Sym(X)$\Sym(X). A more substantive example is the left regular action, where $G$G acts on itself as the set $X = G$X=G by left multiplication: $g \cdot h = gh$g⋅h=gh for $g, h \in G$g,h∈G. This action is always faithful, producing a permutation representation that embeds $G$G isomorphically into $\Sym(G)$\Sym(G), the full symmetric group on $|G|$∣G∣ elements.^[20]

Orbits and Stabilizers

In group theory, when a permutation group $G$G acts on a set $X$X, the orbit of an element $x \in X$x∈X is defined as the set $\operatorname{Orb}_G(x) = \{ g \cdot x \mid g \in G \}$OrbG​(x)={g⋅x∣g∈G}, where $g \cdot x$g⋅x denotes the action of $g$g on $x$x. The orbits of all elements in $X$X form a partition of $X$X, meaning every element belongs to exactly one orbit, and distinct orbits are disjoint.^[42] The stabilizer of $x \in X$x∈X, denoted $\operatorname{Stab}_G(x) = \{ g \in G \mid g \cdot x = x \}$StabG​(x)={g∈G∣g⋅x=x}, is the subgroup of $G$G consisting of all permutations that fix $x$x. This subgroup captures the symmetries preserved at the point $x$x under the action.^[42] A fundamental relation between orbits and stabilizers is given by the orbit-stabilizer theorem. For a finite group $G$G acting on $X$X, the size of the orbit of $x$x equals the index of the stabilizer in $G$G: $$|\operatorname{Orb}_G(x)| = [G : \operatorname{Stab}_G(x)] = \frac{|G|}{|\operatorname{Stab}_G(x)|}.$$∣OrbG​(x)∣=[G:StabG​(x)]=∣StabG​(x)∣∣G∣​. This theorem arises from the bijection between the cosets of $\operatorname{Stab}_G(x)$StabG​(x) in $G$G and the elements of $\operatorname{Orb}_G(x)$OrbG​(x), where the coset $g \operatorname{Stab}_G(x)$gStabG​(x) maps to $g \cdot x$g⋅x.^[43] The core of the stabilizer $\operatorname{Stab}_G(x)$StabG​(x) is the largest normal subgroup of $G$G contained in $\operatorname{Stab}_G(x)$StabG​(x), defined as $\operatorname{Core}_G(\operatorname{Stab}_G(x)) = \bigcap_{g \in G} g \operatorname{Stab}_G(x) g^{-1}$CoreG​(StabG​(x))=⋂g∈G​gStabG​(x)g−1, the intersection of all conjugates of the stabilizer. This core measures the "essential" normality properties embedded in the pointwise symmetries.^[44] For example, consider the symmetric group $S_3$S3​ acting naturally on the set $\{1, 2, 3\}${1,2,3} by permuting its elements. The orbit of 1 is $\operatorname{Orb}_{S_3}(1) = \{1, 2, 3\}$OrbS3​​(1)={1,2,3}, with $|\operatorname{Orb}_{S_3}(1)| = 3$∣OrbS3​​(1)∣=3, while the stabilizer $\operatorname{Stab}_{S_3}(1) = \{\operatorname{id}\}$StabS3​​(1)={id}, the trivial subgroup of order 1. The orbit-stabilizer theorem confirms $3 = 6 / 1$3=6/1, and the core of the stabilizer is trivial since it is already normal (being trivial).^[43]

Transitive and Primitive Groups

Transitive Actions

A permutation group $G$G acting on a finite set $X$X is said to be transitive if there is only one orbit, meaning that for any two elements $x, y \in X$x,y∈X, there exists an element $g \in G$g∈G such that $g \cdot x = y$g⋅x=y.^[45] This condition is equivalent to the action being such that $G$G can map any point in $X$X to any other point via some group element.^[46] The degree of a permutation group $G$G acting on $X$X is defined as the cardinality $|X|$∣X∣. The minimal degree of $G$G is the smallest possible degree of a transitive action of $G$G on a finite set.^[45] For example, the symmetric group $S_n$Sn​ acts transitively on the set $\{1, 2, \dots, n\}${1,2,…,n} by its natural action, which has degree $n$n.^[45] Similarly, the alternating group $A_n$An​ acts transitively on the same set for $n \geq 3$n≥3, as any even permutation can map any element to any other while preserving the parity.^[45] A transitive action is doubly transitive if, for any two distinct ordered pairs $(x, y)$(x,y) and $(x', y')$(x′,y′) in $X \times X$X×X with $x \neq y$x=y and $x' \neq y'$x′=y′, there exists $g \in G$g∈G such that $g \cdot x = x'$g⋅x=x′ and $g \cdot y = y'$g⋅y=y′.^[46] The symmetric group $S_n$Sn​ provides a classic example of a doubly transitive group on $\{1, 2, \dots, n\}${1,2,…,n} for $n \geq 2$n≥2, since any permutation can rearrange distinct points arbitrarily.^[45] In contrast, $A_n$An​ is 2-transitive only for $n \geq 4$n≥4 in certain contexts, but its basic transitivity holds more broadly.^[45] Transitive permutation groups may exhibit imprimitivity, characterized by the existence of blocks of imprimitivity. A nonempty proper subset $B \subset X$B⊂X is a block of imprimitivity for $G$G if, for every $g \in G$g∈G, either $g \cdot B = B$g⋅B=B or $g \cdot B \cap B = \emptyset$g⋅B∩B=∅.^[45] Such blocks form partitions of $X$X that are preserved by the group action, indicating a coarser structure within the transitive action; for instance, the dihedral group acting on the vertices of a regular polygon may preserve subsets corresponding to opposite vertices as blocks.^[45]

Primitive Actions

In group theory, a permutation group $G$G acting transitively on a finite set $\Omega$Ω with $|\Omega| > 1$∣Ω∣>1 is primitive if it preserves no nontrivial partition of $\Omega$Ω.^[47] A subset $\Delta \subseteq \Omega$Δ⊆Ω with $1 < |\Delta| < |\Omega|$1<∣Δ∣<∣Ω∣ is a block of imprimitivity for $G$G if, for every $g \in G$g∈G, either $g\Delta = \Delta$gΔ=Δ or $g\Delta \cap \Delta = \emptyset$gΔ∩Δ=∅; thus, primitivity means no such blocks exist.^[48] This condition distinguishes primitive actions from imprimitive ones, where nontrivial blocks allow the action to factor into coarser structures, such as when $G$G acts on blocks and within blocks separately.^[47] An equivalent characterization is that the action is primitive if and only if the stabilizer $G_\alpha$Gα​ of any point $\alpha \in \Omega$α∈Ω is a maximal subgroup of $G$G.^[47] In this view, primitivity reflects the irreducibility of the action in terms of subgroup lattice: there are no intermediate subgroups between $G_\alpha$Gα​ and $G$G that could correspond to block systems. For instance, the symmetric group $S_n$Sn​ acts primitively on the set $\{1, \dots, n\}${1,…,n} for $n \geq 2$n≥2, as the point stabilizer $S_{n-1}$Sn−1​ is maximal.^[49] Similarly, the alternating group $A_n$An​ acts primitively on $\{1, \dots, n\}${1,…,n} for $n \geq 3$n≥3, with point stabilizer $A_{n-1}$An−1​ maximal.^[49] Imprimitive actions often arise from wreath products, which embed transitive but block-preserving groups. For example, the imprimitive wreath product $S_k \wr S_m$Sk​≀Sm​ acts on a set of size $km$km by permuting $m$m blocks of size $k$k, where the blocks form a nontrivial system of imprimitivity preserved by the group.^[50] This construction illustrates how imprimitivity permits decomposition into a product action on blocks and a base group action within blocks, contrasting with the "indecomposable" nature of primitive actions.^[50] The structure of finite primitive permutation groups is classified by the O'Nan-Scott theorem, which asymptotically divides them into five basic types based on the socle (minimal normal subgroup): affine (socle elementary abelian, acting regularly), almost simple (socle nonabelian simple), diagonal (socle direct product of simple groups, acting by diagonal embedding), product (socle product of simple groups in wreath product action), and twisted wreath (socle simple group in a twisted extension).^[51] This classification, refined over decades, underpins much of modern permutation group theory by linking primitivity to underlying simple group structures without exhaustive enumeration.^[51]

Key Theorems

Cayley's Theorem

Cayley's theorem asserts that every group $G$G is isomorphic to a subgroup of the symmetric group $\mathrm{Sym}(G)$Sym(G) on the underlying set of $G$G. This embedding arises from the left regular action of $G$G on itself, defined by $g \cdot h = gh$g⋅h=gh for all $g, h \in G$g,h∈G.^[52] To prove this, consider the map $\phi: G \to \mathrm{Sym}(G)$ϕ:G→Sym(G) given by $\phi(g)(h) = gh$ϕ(g)(h)=gh for all $h \in G$h∈G. This defines a permutation of $G$G for each $g$g, as left multiplication by $g$g is bijective: it has inverse left multiplication by $g^{-1}$g−1.^[52] The map $\phi$ϕ is a group homomorphism because $\phi(g_1 g_2)(h) = g_1 g_2 h = \phi(g_1)(\phi(g_2)(h))$ϕ(g1​g2​)(h)=g1​g2​h=ϕ(g1​)(ϕ(g2​)(h)) for all $g_1, g_2, h \in G$g1​,g2​,h∈G. Moreover, $\phi$ϕ has trivial kernel: if $\phi(g)$ϕ(g) is the identity permutation, then $g e = e$ge=e, so $g = e$g=e. Thus, $\phi$ϕ is injective, establishing the isomorphism $G \cong \phi(G) \leq \mathrm{Sym}(G)$G≅ϕ(G)≤Sym(G).^[52] The corresponding action is the regular action of $G$G on itself by left multiplication, which is faithful (as $\phi$ϕ is injective) and transitive: for any $h_1, h_2 \in G$h1​,h2​∈G, there exists $g = h_1 h_2^{-1}$g=h1​h2−1​ such that $g \cdot h_2 = h_1$g⋅h2​=h1​. The degree of this permutation representation is $|G|$∣G∣, and the stabilizer of any point $h \in G$h∈G is trivial, since $\mathrm{Stab}(h) = \{g \in G \mid gh = h\} = \{e\}$Stab(h)={g∈G∣gh=h}={e}.^[52] As consequences, every group admits a faithful permutation representation, allowing abstract groups to be realized concretely as subgroups of symmetric groups. This shows that the class of permutation groups is universal, encompassing all finite groups up to isomorphism. For example, consider the cyclic group $C_3 = \langle r \mid r^3 = e \rangle$C3​=⟨r∣r3=e⟩. The regular action embeds $C_3$C3​ into $\mathrm{Sym}(C_3) \cong S_3$Sym(C3​)≅S3​ as the subgroup $\{e, (1\ 2\ 3), (1\ 3\ 2)\}${e,(1 2 3),(1 3 2)}, corresponding to the rotations of an equilateral triangle.^[52]

Structure of Permutation Groups

A permutation group, as a finite group, is solvable if and only if its derived series terminates at the trivial subgroup after a finite number of steps, with the number of steps known as the derived length.^[53] The derived subgroup $G'$G′ of a group $G$G is generated by all commutators $[g,h] = g^{-1}h^{-1}gh$[g,h]=g−1h−1gh for $g,h \in G$g,h∈G, and the derived series is defined iteratively as $G^{(0)} = G$G(0)=G, $G^{(k+1)} = (G^{(k)})'$G(k+1)=(G(k))′.^[54] Examples of solvable permutation groups include affine groups, such as the affine general linear group $\mathrm{AGL}(1,p)$AGL(1,p) for a prime $p$p, which acts on $p$p points as the semidirect product $\mathbb{Z}/p\mathbb{Z} \rtimes (\mathbb{Z}/p\mathbb{Z})^\times$Z/pZ⋊(Z/pZ)× and has derived length 2 since both factors are abelian.^[55] Every finite permutation group admits a composition series, a maximal chain of normal subgroups where each factor is simple, and by the Jordan-Hölder theorem, the composition factors are unique up to isomorphism and permutation.^[53] The composition factors of permutation groups are thus non-abelian simple groups or cyclic groups of prime order, with alternating groups $A_k$Ak​ for $k \geq 5$k≥5 and cyclic groups frequently appearing due to the embedding of abstract groups into the symmetric group via Cayley's theorem.^[56] For the symmetric group $S_n$Sn​ with $n \geq 5$n≥5, a composition series is $\{e\} \trianglelefteq A_n \trianglelefteq S_n${e}⊴An​⊴Sn​, yielding composition factors $A_n$An​ (simple non-abelian) and $\mathbb{Z}/2\mathbb{Z}$Z/2Z (cyclic of prime order).^[53] The Frobenius theorem provides key insight into the structure of certain permutation groups possessing semiregular normal subgroups.^[57] A subgroup $N \trianglelefteq G$N⊴G acting semiregularly on a set means that only the identity element of $N$N has fixed points, implying trivial point stabilizers.^[58] The theorem states that if $G$G is a finite permutation group with a nontrivial proper semiregular normal subgroup $N$N, then $N$N admits a complement $H \leq G$H≤G such that $G = N \rtimes H$G=N⋊H, $H \cap N = \{e\}$H∩N={e}, and $H$H acts faithfully and semiregularly on the non-identity elements of $N$N; such groups are precisely the Frobenius groups.^[57] This semidirect product decomposition reveals the internal structure, with $N$N as the Frobenius kernel (regular if the action is transitive) and $H$H as the Frobenius complement.^[58] Computational methods elucidate the structure of permutation groups given by generating sets.^[59] The Schreier-Sims algorithm constructs a base and strong generating set (BSGS) for a permutation group $G \leq S_n$G≤Sn​, enabling efficient computation of the group order via the product of orbit lengths on the base points and testing membership of elements in polynomial time relative to $n \log |G|$nlog∣G∣.^[59] It proceeds by building stabilizers iteratively: starting with a base $B = (b_1, \dots, b_k)$B=(b1​,…,bk​) such that the pointwise stabilizer chain $G = G^{(0)} \geq G^{(1)} \geq \cdots \geq G^{(k)} = \{e\}$G=G(0)≥G(1)≥⋯≥G(k)={e} has known orbits, and using Schreier generators from coset transversals to ensure strong generation.^[60] Extensions of the Schreier-Sims algorithm apply to black-box permutation groups, where $G$G is accessed via an oracle for multiplication, inversion, and order queries, allowing recognition and structure determination without explicit permutation representation, as in nearly linear-time algorithms for order computation.^[61]

Advanced Topics

Oligomorphic Groups

A permutation group $G \leq \Sym(\Omega)$G≤\Sym(Ω), where $\Omega$Ω is typically a countably infinite set, is called oligomorphic if, for each natural number $k \geq 1$k≥1, the action of $G$G on the set $\Omega^k$Ωk of ordered $k$k-tuples has only finitely many orbits.^[62] This finiteness condition contrasts with finite permutation groups, emphasizing bounded complexity in infinite domains despite the group's potential largeness. The concept connects to model theory through the age of a structure, defined as the class of all finite substructures up to isomorphism, which forms a closed set under embeddings for relational structures with oligomorphic automorphism groups.^[62] A structure is homogeneous if every isomorphism between its finite substructures extends to an automorphism of the whole structure; such homogeneity often characterizes Fraïssé limits, where the automorphism group is oligomorphic.^[62] Prominent examples include the automorphism group $\Aut(\mathbb{Q}, <)$\Aut(Q,<) of the rational numbers under the strict order, which is oligomorphic and has exactly two orbits on the set of ordered pairs of distinct elements: one where the first is less than the second, and one where the order is reversed.^[62] Another is the automorphism group of the Rado graph (or random graph), the Fraïssé limit of the class of finite graphs, which is oligomorphic with the number of orbits on $n$n-tuples equal to the number of non-isomorphic labeled graphs on $n$n vertices up to adjacency relations.^[62] Countable oligomorphic permutation groups arise precisely as the automorphism groups of Fraïssé limits of their ages, as established in classifications of homogeneous structures; for instance, Lachlan and Woodrow's work on countable homogeneous graphs identifies the random graph and certain Henson graphs as such limits with oligomorphic groups.^[63] These groups correspond to ω-categorical theories in model theory, where the finiteness of orbits equates to the finiteness of n-types, enabling structural classifications.^[62] Oligomorphic groups find applications in model theory for analyzing countable structures via their automorphism groups and in constraint satisfaction problems (CSPs), where structures with oligomorphic automorphisms allow complexity dichotomies; for example, valued CSPs over such templates reduce tractability to the existence of fractional polymorphisms or pp-constructions.^[64]

Permutation Group Isomorphisms

In group theory, two permutation groups $G$G and $H$H, where $G$G acts faithfully on a set $X$X and $H$H acts faithfully on a set $Y$Y, are isomorphic as permutation groups if there exists a bijective group homomorphism $\phi: G \to H$ϕ:G→H and a bijection $\psi: X \to Y$ψ:X→Y such that $\phi(g) \cdot \psi(x) = \psi(g \cdot x)$ϕ(g)⋅ψ(x)=ψ(g⋅x) for all $g \in G$g∈G and $x \in X$x∈X. This condition ensures that the actions are preserved up to relabeling of the underlying sets, making the representations equivalent. If $X = Y$X=Y, the bijection $\psi$ψ can be taken as the identity, reducing to the case where $\phi$ϕ is an automorphism of $G$G that commutes with the action. Within the symmetric group $\Sym(X)$\Sym(X), conjugacy provides a key notion of equivalence for elements and subgroups. Two permutations $g, h \in \Sym(X)$g,h∈\Sym(X) are conjugate if there exists $\sigma \in \Sym(X)$σ∈\Sym(X) such that $h = \sigma^{-1} g \sigma$h=σ−1gσ, denoted $h = g^\sigma$h=gσ. This operation relabels the points of $X$X via $\sigma$σ, preserving the cycle type of the permutation, which determines the conjugacy class.^[65] For subgroups, two subgroups $H, K \leq \Sym(X)$H,K≤\Sym(X) are conjugate if $K = \sigma^{-1} H \sigma$K=σ−1Hσ for some $\sigma \in \Sym(X)$σ∈\Sym(X), implying they are isomorphic as abstract groups and their actions on $X$X are equivalent up to relabeling. Conjugacy classes in $\Sym(X)$\Sym(X) thus classify permutation representations up to such equivalences, with cycle types serving as invariants that distinguish non-conjugate elements. Equivalent representations of a group $G$G on sets $X$X and $Y$Y arise when there is a bijection $\psi: X \to Y$ψ:X→Y such that the image subgroups in $\Sym(X)$\Sym(X) and $\Sym(Y)$\Sym(Y) are conjugate via $\psi$ψ, meaning the actions are isomorphic. This equivalence captures how different embeddings of $G$G into symmetric groups can represent the same underlying structure after adjusting for point labels. Burnside's lemma relates to these concepts by providing a tool to count orbits under group actions, which helps analyze the structure of permutation groups up to isomorphism. Specifically, for a group $G$G acting on $X$X, the number of orbits is given by $$|X/G| = \frac{1}{|G|} \sum_{g \in G} \Fix(g),$$∣X/G∣=∣G∣1​g∈G∑​\Fix(g), where $\Fix(g)$\Fix(g) is the number of fixed points of $g$g. This formula, originally due to Frobenius and popularized by Burnside, quantifies the distinct "behaviors" of the action, aiding in distinguishing non-isomorphic representations. A concrete example illustrates conjugacy in transitive actions: all transitive embeddings of the cyclic group $C_p$Cp​ of prime order $p$p into $\Sym(p)$\Sym(p) are conjugate. Here, each such embedding corresponds to the regular action of $C_p$Cp​ on itself, and any two are related by conjugation in $\Sym(p)$\Sym(p), as the transitive cyclic subgroups of prime degree are uniquely determined up to relabeling.^[55] This uniformity underscores how conjugacy normalizes representations, ensuring that isomorphic permutation groups share equivalent transitive structures.

Historical Development

Early Contributions

The study of permutation groups originated in the late 18th century amid efforts to understand the solvability of polynomial equations. In his 1770 memoir Réflexions sur la résolution algébrique des équations, Joseph-Louis Lagrange examined permutations of equation roots as a means to analyze the structure of solutions for cubic and quartic equations, laying groundwork for linking algebraic resolvents to rearrangements of variables.^[66] Lagrange introduced rudimentary concepts of cycles by considering how repeated substitutions could generate solution functions, though he did not formalize them as group elements.^[67] Building on Lagrange's ideas, Paolo Ruffini advanced the connection between permutations and equation solvability in his 1799 memoir Teoria generale delle equazioni, where he attempted to prove the impossibility of solving the general quintic equation by radicals using properties of permutation arrangements of roots.^[68] Ruffini's argument, though incomplete, highlighted the role of the full symmetric group in obstructing radical solutions for degree five polynomials.^[69] In 1824, Niels Henrik Abel provided a rigorous proof of the quintic's unsolvability, employing permutation-based analysis to show that certain root rearrangements prevent expression via nested radicals, solidifying the permutation group's centrality to algebraic insolubility.^[69] Évariste Galois established the foundational framework for permutation groups in the 1830s through his work on equation solvability. In his 1831 Mémoire sur les conditions de résolubilité des équations par radicaux, Galois defined groups as closed sets of permutations under composition and linked solvability by radicals to the existence of a normal series with abelian factors in the symmetric group acting on roots.^[70] He demonstrated that the symmetric group $S_n$Sn​ for $n \geq 5$n≥5 lacks such a series, rendering general polynomials of degree five or higher unsolvable by radicals.^[70] A pivotal event occurred in Galois's 1832 letters to Auguste Chevalier, where he implicitly outlined group actions on roots as permutations preserving algebraic relations, encapsulating his theory just before his death.^[71] Augustin-Louis Cauchy formalized permutation groups in the 1840s, treating them as abstract systems of substitutions. In his 1845 memoir Mémoire sur le nombre des valeurs qu'une fonction peut acquérir, lorsqu'on y permute de toutes les manières possibles les quantités qu'elle renferme, Cauchy defined permutation multiplication and explored their algebraic structure, including decompositions into cycles and disjoint cycles.^[72] He introduced conjugacy classes as sets of permutations related by simultaneous relabeling, proving that such classes partition the group and share cycle types, which became essential for classifying permutation behaviors.^[73]

Modern Developments

In the second half of the 19th century, Camille Jordan made substantial advances in the theory of permutation groups. In works culminating in his 1879 treatise Traité des substitutions et des équations algébriques, Jordan developed a systematic treatment of substitution groups, introducing concepts such as primitive and imprimitive actions, composition series for groups, and the Jordan-Hölder theorem. His abstraction of permutation groups from concrete substitutions paved the way for modern abstract group theory.^[74] In the late 19th and early 20th centuries, William Burnside advanced the understanding of permutation groups through his work on normalizers and transfer theory, which provided tools for analyzing subgroup structures and early attempts at classification. Burnside's normal p-complement theorem, which states that if a Sylow p-subgroup P of a finite group G satisfies P ⊆ Z(N_G(P)), then G has a normal p-complement, relied on transfer homomorphisms to establish conditions for the existence of normal subgroups complementing Sylow subgroups.^[75] These ideas, developed in his foundational text, laid groundwork for later classifications by linking permutation representations to broader group-theoretic properties.^[75] A major milestone in the mid-20th century was the O'Nan-Scott theorem, formulated in the 1970s and 1980s, which provides a classification of finite primitive permutation groups into five broad types: affine, almost simple, simple diagonal, product action, and twisted wreath product types. This theorem, originally outlined in unpublished notes by Michael O'Nan and Leonard Scott, categorizes primitive groups based on the structure of their socles and stabilizers, reducing the study of such groups to cases involving simple groups or their products.^[76] The classification has been instrumental in applications to combinatorics and geometry, such as enumerating designs and graphs with specified symmetries.^[76] In the 1980s, Michael Aschbacher provided key refinements to the O'Nan-Scott theorem, resulting in what is now known as the Aschbacher-O'Nan-Scott theorem, which expands the classification to eight types by incorporating extensions like the holomorph of vector spaces and correcting earlier formulations, providing a more precise structural description reliant on the classification of finite simple groups. Aschbacher's contributions clarified the twisted wreath product case and integrated quasiprimitive groups, enhancing the theorem's completeness for primitive actions.^[51] Concurrently, computational methods emerged with Charles Sims' development of the Schreier-Sims algorithm in the 1970s, which computes a base and strong generating set (BSGS) for a permutation group given by generators, enabling efficient determination of the group's order and membership testing. The algorithm constructs a stabilizer chain using Schreier's lemma to generate coset representatives, with a time complexity polynomial in the degree for groups of bounded non-triviality, making it foundational for software implementations.^[77] This breakthrough shifted permutation group theory toward algorithmic approaches, facilitating the verification of theoretical classifications on large examples.^[77] Computational group theory has flourished through systems like GAP and Magma, which implement Schreier-Sims variants and O'Nan-Scott reductions to construct and analyze permutation groups up to high degrees, supporting research in random generation and subgroup lattices.^[78][79]