Fact-checked by Grok 2 weeks ago

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, which consists of all possible permutations of a set with n elements, serves as the foundational example and has order 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, the kernel of the sign homomorphism and a normal subgroup of S_n of index 2.^[4] For n \geq 5, A_n 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 on a set X is defined as a subgroup of the symmetric group \Sym(X), where the elements of G are bijections from X to itself, and the group operation is the composition of these bijections.^[8]^[1] The symmetric group \Sym(X) comprises all permutations of the set X, that is, all bijective functions from X to X, equipped with the operation of function composition, which forms a group under this operation.^[9] When X is finite with cardinality n, the order of \Sym(X) is 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 is infinite, leading to an uncountably many permutations in \Sym(X) for uncountable X.^[9] A basic example is the trivial group, which serves as the permutation group on a singleton set X = \{ a \}, where \Sym(X) consists solely of the identity bijection that maps a to itself.^[10]

Basic Properties

A permutation group G on a set X satisfies the closure property under the group operation of composition: the composition of any two elements \sigma, \tau \in G is another bijection from X to X, hence also in G.^[11]^[2] This ensures that G forms a subgroup of the symmetric group \mathrm{Sym}(X), the full group of all bijections on 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, (\sigma \circ \tau) \circ \rho = \sigma \circ (\tau \circ \rho).^[11]^[13] When X is finite with |X| = n, any permutation group G \leq \mathrm{Sym}(X) is finite, and by Lagrange's theorem applied to the finite group \mathrm{Sym}(X) of order n!, the order of G divides 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. The support of a permutation is the subset of 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) are conjugate if and only if they have the same cycle type; that is, \tau^{-1} \sigma \tau has the same cycle structure as \sigma for some \tau \in \mathrm{Sym}(X). In a subgroup G \leq \mathrm{Sym}(X), permutations with the same cycle type belong to the same conjugacy class in \mathrm{Sym}(X) but may form multiple conjugacy classes in G.^[2]^[15]

Notation and Operations

Notation Conventions

Permutations of a finite set, such as \{1, 2, \dots, n\}, are often represented in one-line notation as \sigma = (\sigma(1) \ \sigma(2) \ \dots \ \sigma(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},

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), 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 for 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).^[20] For imprimitive actions, blocks of imprimitivity are denoted as subsets B_1, B_2, \dots, B_k 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)) for all 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): applying (2\ 3) followed by (1\ 2) yields $1 \mapsto 2 \mapsto 3, $3 \mapsto 2 \mapsto 1, and $2 \mapsto 3 \mapsto 3 (fixed after the first step, but the cycle closes as (1\ 2\ 3)); thus, (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: the left side gives \sigma(\tau(\rho(x))), while the right side gives \sigma((\tau \rho)(x)) = \sigma(\tau(\rho(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 or id, and formally defined as id(x) = x for all 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 for any permutation \sigma.^[25] Every permutation \sigma has a unique inverse \sigma^{-1} such that \sigma \circ \sigma^{-1} = \sigma^{-1} \circ \sigma = 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) is (3\ 2\ 1), which is equivalent to (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 such that \sigma^k = id.^[25] For a permutation expressed as a product of disjoint cycles of lengths l_1, l_2, \dots, l_m, the order is the least common multiple of these lengths, |\sigma| = \operatorname{lcm}(l_1, l_2, \dots, l_m)./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 returns to the identity after l_i applications.^[25]

Examples

Symmetric and Alternating Groups

The symmetric group S_n consists of all permutations of a set with n elements, which can be viewed as the set of all bijections from \{1, 2, \dots, n\} to itself under composition.^[26]^[27] The order of S_n is n!, reflecting the number of distinct bijections on an n-element set.^[26]^[28] Furthermore, S_n is generated by the set of all transpositions, the permutations that swap exactly two elements and fix the rest, for n \geq 2.^[29]^[4] The alternating group A_n is the subgroup of S_n 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, A_n has index 2 in S_n, meaning |A_n| = n!/2, and it is a normal subgroup.^[31]^[32] Additionally, A_n is simple for n \geq 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 \}, which assigns +1 to even permutations and -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.^[30]^[32] A concrete example is S_3, the symmetric group on three elements, which has order 6 and includes all permutations such as the identity, transpositions like (1\ 2), and 3-cycles like (1\ 2\ 3).^[4]^[34] The alternating group A_3 consists of the even permutations: the identity and the two 3-cycles (1\ 2\ 3) and (1\ 3\ 2), forming a cyclic group of order 3 generated by (1\ 2\ 3).^[4]^[34]

Cyclic and Dihedral Groups

The cyclic group C_n of order n provides a fundamental example of a permutation group, realized as the subgroup generated by the n-cycle \sigma = (1\ 2\ \dots\ n) acting on the set \{1, 2, \dots, n\}. The elements of C_n are the powers \sigma^k for k = 0, 1, \dots, n-1, with \sigma^0 being the identity permutation, and the group operation is composition of permutations. Since powers of a single generator commute under composition, C_n is abelian.^[35] A key extension of the cyclic group in the context of permutation groups is the dihedral group D_n (also denoted D_{2n} in some conventions), which captures the full symmetry group of a regular n-gon and has order $2n. This group acts faithfully on the n vertices of the polygon as permutations and is generated by a rotation \rho = (1\ 2\ \dots\ n), which cycles the vertices, and a reflection s, which swaps pairs of vertices symmetrically while fixing one (for odd n) or passing through midpoints of edges (for even n). The defining relations are \rho^n = e, s^2 = e, and s \rho s = \rho^{-1}, reflecting how reflections conjugate rotations to their inverses.^[36]^[37] The abstract presentation of D_n is \langle \rho, s \mid \rho^n = s^2 = 1, s \rho s^{-1} = \rho^{-1} \rangle, which encodes its structure as a semidirect product of the cyclic group C_n by C_2. For n = 3, the dihedral group D_3 consists of the three rotations and three reflections of an equilateral triangle, permuting its vertices, and is isomorphic to the symmetric group S_3 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 as permutations of a set X. Formally, a left action of G on X is a group homomorphism \phi: G \to \Sym(X), where \Sym(X) denotes the symmetric group consisting of all bijections from X to itself under composition.^[38] Equivalently, it can be described by a map G \times X \to X, written (g, x) \mapsto g \cdot x, that satisfies two axioms: the identity element e \in G acts trivially, so e \cdot x = x for all x \in X, and the action is compatible with the group operation, so (gh) \cdot x = g \cdot (h \cdot x) for all g, h \in G and x \in X.^[20] This homomorphism perspective highlights that every group action induces a permutation representation of G, namely the image \phi(G), which is a subgroup of \Sym(X) acting naturally on X.^[39] The permutation representation arising from a group action captures how G permutes the elements of X; distinct elements of 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 \}, so that only the identity element fixes every point in X, and thus \phi embeds G as a subgroup of \Sym(X).^[40] Otherwise, the action is non-faithful, and the kernel is a normal subgroup of G consisting of all elements that act as the identity permutation.^[41] Illustrative examples clarify these concepts. The trivial action of any group G on a set X is defined by g \cdot x = x for all g \in G and x \in X; this always yields a valid action, but it is faithful only if G is the trivial group, and the corresponding permutation representation is the singleton subgroup of \Sym(X). A more substantive example is the left regular action, where G acts on itself as the set X = G by left multiplication: g \cdot h = gh for g, h \in G. This action is always faithful, producing a permutation representation that embeds G isomorphically into \Sym(G), the full symmetric group on |G| elements.^[20]

Orbits and Stabilizers

In group theory, when a permutation group G acts on a set X, the orbit of an element x \in X is defined as the set \operatorname{Orb}_G(x) = \{ g \cdot x \mid g \in G \}, where g \cdot x denotes the action of g on x. The orbits of all elements in X form a partition of X, meaning every element belongs to exactly one orbit, and distinct orbits are disjoint.^[42] The stabilizer of x \in X, denoted \operatorname{Stab}_G(x) = \{ g \in G \mid g \cdot x = x \}, is the subgroup of G consisting of all permutations that fix x. This subgroup captures the symmetries preserved at the point x under the action.^[42] A fundamental relation between orbits and stabilizers is given by the orbit-stabilizer theorem. For a finite group G acting on X, the size of the orbit of x equals the index of the stabilizer in G:

|\operatorname{Orb}_G(x)| = [G : \operatorname{Stab}_G(x)] = \frac{|G|}{|\operatorname{Stab}_G(x)|}.

This theorem arises from the bijection between the cosets of \operatorname{Stab}_G(x) in G and the elements of \operatorname{Orb}_G(x), where the coset g \operatorname{Stab}_G(x) maps to g \cdot x.^[43] The core of the stabilizer \operatorname{Stab}_G(x) is the largest normal subgroup of G contained in \operatorname{Stab}_G(x), defined as \operatorname{Core}_G(\operatorname{Stab}_G(x)) = \bigcap_{g \in G} g \operatorname{Stab}_G(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 acting naturally on the set \{1, 2, 3\} by permuting its elements. The orbit of 1 is \operatorname{Orb}_{S_3}(1) = \{1, 2, 3\}, with |\operatorname{Orb}_{S_3}(1)| = 3, while the stabilizer \operatorname{Stab}_{S_3}(1) = \{\operatorname{id}\}, the trivial subgroup of order 1. The orbit-stabilizer theorem confirms $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 acting on a finite set X is said to be transitive if there is only one orbit, meaning that for any two elements x, y \in X, there exists an element g \in G such that g \cdot x = y.^[45] This condition is equivalent to the action being such that G can map any point in X to any other point via some group element.^[46] The degree of a permutation group G acting on X is defined as the cardinality |X|. The minimal degree of G is the smallest possible degree of a transitive action of G on a finite set.^[45] For example, the symmetric group S_n acts transitively on the set \{1, 2, \dots, n\} by its natural action, which has degree n.^[45] Similarly, the alternating group A_n acts transitively on the same set for n \geq 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) and (x', y') in X \times X with x \neq y and x' \neq y', there exists g \in G such that g \cdot x = x' and g \cdot y = y'.^[46] The symmetric group S_n provides a classic example of a doubly transitive group on \{1, 2, \dots, n\} for n \geq 2, since any permutation can rearrange distinct points arbitrarily.^[45] In contrast, A_n is 2-transitive only for n \geq 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 is a block of imprimitivity for G if, for every g \in G, either g \cdot B = B or g \cdot B \cap B = \emptyset.^[45] Such blocks form partitions of 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 acting transitively on a finite set \Omega with |\Omega| > 1 is primitive if it preserves no nontrivial partition of \Omega.^[47] A subset \Delta \subseteq \Omega with $1 < |\Delta| < |\Omega| is a block of imprimitivity for G if, for every g \in G, either g\Delta = \Delta or g\Delta \cap \Delta = \emptyset; 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 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 of any point \alpha \in \Omega is a maximal subgroup of 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 and G that could correspond to block systems. For instance, the symmetric group S_n acts primitively on the set \{1, \dots, n\} for n \geq 2, as the point stabilizer S_{n-1} is maximal.^[49] Similarly, the alternating group A_n acts primitively on \{1, \dots, n\} for n \geq 3, with point stabilizer A_{n-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 acts on a set of size km by permuting m blocks of size 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 is isomorphic to a subgroup of the symmetric group \mathrm{Sym}(G) on the underlying set of G. This embedding arises from the left regular action of G on itself, defined by g \cdot h = gh for all g, h \in G.^[52] To prove this, consider the map \phi: G \to \mathrm{Sym}(G) given by \phi(g)(h) = gh for all h \in G. This defines a permutation of G for each g, as left multiplication by g is bijective: it has inverse left multiplication by 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)) for all g_1, g_2, h \in G. Moreover, \phi has trivial kernel: if \phi(g) is the identity permutation, then g e = e, so g = e. Thus, \phi is injective, establishing the isomorphism G \cong \phi(G) \leq \mathrm{Sym}(G).^[52] The corresponding action is the regular action of G on itself by left multiplication, which is faithful (as \phi is injective) and transitive: for any h_1, h_2 \in G, there exists g = h_1 h_2^{-1} such that g \cdot h_2 = h_1. The degree of this permutation representation is |G|, and the stabilizer of any point h \in G is trivial, since \mathrm{Stab}(h) = \{g \in G \mid 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. The regular action embeds C_3 into \mathrm{Sym}(C_3) \cong S_3 as the subgroup \{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' of a group G is generated by all commutators [g,h] = g^{-1}h^{-1}gh for g,h \in G, and the derived series is defined iteratively as G^{(0)} = G, 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) for a prime p, which acts on p points as the semidirect product \mathbb{Z}/p\mathbb{Z} \rtimes (\mathbb{Z}/p\mathbb{Z})^\times 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 for k \geq 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 with n \geq 5, a composition series is \{e\} \trianglelefteq A_n \trianglelefteq S_n, yielding composition factors A_n (simple non-abelian) and \mathbb{Z}/2\mathbb{Z} (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 acting semiregularly on a set means that only the identity element of N has fixed points, implying trivial point stabilizers.^[58] The theorem states that if G is a finite permutation group with a nontrivial proper semiregular normal subgroup N, then N admits a complement H \leq G such that G = N \rtimes H, H \cap N = \{e\}, and H acts faithfully and semiregularly on the non-identity elements of N; such groups are precisely the Frobenius groups.^[57] This semidirect product decomposition reveals the internal structure, with N as the Frobenius kernel (regular if the action is transitive) and 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, 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|.^[59] It proceeds by building stabilizers iteratively: starting with a base B = (b_1, \dots, b_k) such that the pointwise stabilizer chain G = G^{(0)} \geq G^{(1)} \geq \cdots \geq 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 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), where \Omega is typically a countably infinite set, is called oligomorphic if, for each natural number k \geq 1, the action of G on the set \Omega^k of ordered 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}, <) 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-tuples equal to the number of non-isomorphic labeled graphs on 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 and H, where G acts faithfully on a set X and H acts faithfully on a set Y, are isomorphic as permutation groups if there exists a bijective group homomorphism \phi: G \to H and a bijection \psi: X \to Y such that \phi(g) \cdot \psi(x) = \psi(g \cdot x) for all g \in G and x \in X. This condition ensures that the actions are preserved up to relabeling of the underlying sets, making the representations equivalent. If X = Y, the bijection \psi can be taken as the identity, reducing to the case where \phi is an automorphism of G that commutes with the action. Within the symmetric group \Sym(X), conjugacy provides a key notion of equivalence for elements and subgroups. Two permutations g, h \in \Sym(X) are conjugate if there exists \sigma \in \Sym(X) such that h = \sigma^{-1} g \sigma, denoted h = g^\sigma. This operation relabels the points of 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) are conjugate if K = \sigma^{-1} H \sigma for some \sigma \in \Sym(X), implying they are isomorphic as abstract groups and their actions on X are equivalent up to relabeling. Conjugacy classes in \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 on sets X and Y arise when there is a bijection \psi: X \to Y such that the image subgroups in \Sym(X) and \Sym(Y) are conjugate via \psi, meaning the actions are isomorphic. This equivalence captures how different embeddings of 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 acting on X, the number of orbits is given by

|X/G| = \frac{1}{|G|} \sum_{g \in G} \Fix(g),

where \Fix(g) is the number of fixed points of 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 of prime order p into \Sym(p) are conjugate. Here, each such embedding corresponds to the regular action of C_p on itself, and any two are related by conjugation in \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 for n \geq 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]

References

[1]
Permutation Groups - Department of Mathematics at UTSA
Nov 17, 2021 · A permutation group is a group G whose elements are permutations of a given set M and whose group operation is the composition of ...
[2]
[PDF] Math 403 Chapter 5 Permutation Groups: 1. Introduction
A permutation group of A is a set of permutations of A that forms a group under function composition. 3. Note: We'll focus specifically on the case when A = 11 ...
[3]
[PDF] 8 Groups of Permutations - UC Berkeley math
Theorem (Cayley's Theorem). Every group is isomorphic to a group of permutations. The proof of Cayley's theorem requires a definition and a lemma. Definition.
[4]
[PDF] Lecture 2.3: Symmetric and alternating groups
Loosely speaking, a symmetric group is the collection of all n! permutations of n objects. Alternating groups are similar. Thus, we will study permutations, and ...
[5]
[PDF] The Alternating Groups - DSpace@MIT
The alternating group An is the group of even permutations in Sn. Our object is to prove. Theorem. If n ≥ 5, the alternating group An is a simple group.
[6]
AATA Permutation Groups - Abstract Algebra: Theory and Applications
Permutation groups are central to the study of geometric symmetries and to Galois theory, the study of finding solutions of polynomial equations.
[7]
[PDF] Permutation Groups in NC - University of Oregon
Abstract. We show that the basic problems of permutation group manipulation admit e cient parallel solutions. Given a permutation group G by a list of ...
[8]
[PDF] §3.6 Permutation Groups - University of South Carolina
Any subgroup of the symmetric group Sym(S) is called a permutation group. Every group G is isomorphic to a permutation group. Proof: Given a ∈ G, define λa : G ...
[9]
https://sporadic.stanford.edu/bump/group/gr1_4.html
[10]
[PDF] The symmetric group
Definition 1.3. The symmetric group Sn is the group Perm({1,...,n}) of all permutations on the first n integers.
[11]
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_Through_Guided_Discovery_(Bogart)/06%3A_Groups_Acting_on_Sets/6.01%3A_Permutation_Groups
[12]
Basic definitions and facts
Syllabus: In this section we give the precise definition of an abstract group and recall some basic examples. We also recall basic properties of permutations ...Missing: finiteness | Show results with:finiteness
[13]
[PDF] Permutation - OU Math
Permutations. 1. Definition (Permutation). A permutation of a set A is a bijective function f : A → A. The set of all permutations of A is denoted by Perm(A).
[14]
[PDF] Finite sets, counting and group theory - Purdue Math
Theorem 5.9 (Lagrange). If H ✓ G is a subgroup of a finite group, then |G| = |H|·|G/H| In particular, the order of H divides the order of G. Proof. By the ...
[15]
one-line notation for permutations - PlanetMath.org
Mar 22, 2013 · So now we can translate the permutation into cycle notation: π=(1)(274)(56) π = ( 1 ) ⁢ ( 274 ) ⁢ ( 56 ) . If we are willing to allow words of ...
[16]
1.4 Permutations | MATH0007: Algebra for Joint Honours Students
One way to do this is two row notation in which we write the numbers 1 to n in a row and then write σ(i) σ ( i ) beneath i: (12⋯n−1nσ(1)σ(2)⋯σ(n−1)σ(n)) ( 1 2 ⋯ ...
[17]
15.3: Permutation Groups - Mathematics LibreTexts
Aug 16, 2021 · Cycle Notation. A second way of describing a permutation is by means of cycles, which we will introduce first ...
[18]
26.13 Permutations: Cycle Notation
In cycle notation, the elements in each cycle are put inside parentheses, ordered so that σ ⁡ ( j ) immediately follows j or, if j is the last listed element ...
[19]
[PDF] group actions - keith conrad
What we have been calling a group action could be called a left group action, while a right group action, denoted xg, has the properties xe = x and (xg1)g2 = x( ...
[20]
[PDF] Imprimitive Permutation Groups - UP FAMNIT
Any other block is nontrivial. If G has a nontrivial block then it is imprimitive. If G is not imprimitive, we say that G is primitive. Note that if B ...
[21]
Permutation -- from Wolfram MathWorld
### Summary of Permutation Composition from MathWorld
[22]
[PDF] Introduction to Abstract Algebra (Math 113)
3.4 Permutation Groups and Group Actions . ... We have an analogous concept in group theory. Definition. Let (G, ∗) be a group. A subgroup of G is a ...
[23]
Permutation Group -- from Wolfram MathWorld
A permutation group is a finite group G whose elements are permutations of a given set and whose group operation is composition of permutations in G.
[24]
[PDF] Group Theory - James Milne
There are over a hundred exercises, many with solutions. BibTeX information. @misc{milneGT, author={Milne, James S.}, title={Group Theory ...
[25]
SymmetricGroup
The symmetric group on n letters, written S n , has as its elements the n! distinct bijections from an n-element set (often taken to be {1...n}) to itself.
[26]
[PDF] 13. Symmetric groups
The symmetric group Sn is the group of bijections of {1,...,n} to itself, also called permutations of n. things. A standard notation for the permutation that ...Missing: S_n | Show results with:S_n
[27]
[PDF] Math 412. The Symmetric Group Sn.
The Symmetric Group Sn. DEFINITION: The symmetric group Sn is the group of bijections from any set of n objects, which we usu- ally call simply {1,2,...,n} ...
[28]
[PDF] Sign of permutations - Keith Conrad
Our starting point is that all permutations in Sn are products of transpositions. Theorem 1.1. For n ≥ 2, Sn is generated by its transpositions. Proof. Here are ...Missing: S_n | Show results with:S_n
[29]
[PDF] The Alternating Group
An is called the alternating group. An important feature of the alternating group is that, unless n = 4, it is a simple group. A group G is said to be simple ...
[30]
[PDF] Chapter 1: Abstract Group Theory - Rutgers Physics
Definition: The alternating group An ⊂ Sn is the subgroup of Sn of even permuta- ... describe below, An for n ≥ 5 are all simple groups. Moreover, |An| is ...
[31]
[PDF] Lecture 15 - Math 5111 (Algebra 1)
Nov 2, 2020 · Theorem (Alternating Group) The alternating group An is the kernel of the sign map and is therefore is a normal subgroup of Sn. Explicitly, An ...Missing: A_n S_n simple
[32]
[PDF] SIMPLICITY OF An - KEITH CONRAD
A finite group is simple if it's nontrivial and its only normal subgroups are the trivial subgroup and the whole group. For n ≥ 5, the group An is simple.
[33]
[PDF] Math 412. Symmetric Group: Answers.
The order of the four permutations that are products of disjoint transpositions is 2. (8) An example of a cyclic subgroup of order 2 is h(1 2)i = {e, (1 2)}.
[34]
Cyclic Group -- from Wolfram MathWorld
### Summary of Cyclic Group $ C_n $ Representation and Properties
[35]
3.3: Dihedral Groups (Group of Symmetries)
### Summary of Dihedral Groups as Permutation Groups
[36]
Dihedral Group -- from Wolfram MathWorld
The dihedral group D_n is the symmetry group of an n-sided regular polygon for n>1. The group order of D_n is 2n. Dihedral groups D_n are non-Abelian ...
[37]
group actions and homomorphisms - PlanetMath.org
Mar 22, 2013 · A group action of G on X is a mapping where g⋅x is defined. A group homomorphism F:G→SX maps g to fg. A group action can be induced by a ...
[38]
[PDF] Group Actions and Permutations Representations
permutation representation associated to the group action of. G on A ... 3 An action is said to be faithful if its kernel is the identity. Kevin James.
[39]
[PDF] Abstract Algebra I
Since the kernel of an action is the same as the kernel of the associated permutation representation, it is a normal subgroup of G. Two group elements induce ...
[40]
[PDF] GROUPS ACTING ON A SET 1. Left group actions Definition 1.1 ...
We now consider the same example in a slightly more explicit framework. Example 1.3. Suppose that G = S4, the group of permutations on the set S = {1,2,3,4}.
[41]
[PDF] More about Permutations and Symmetry Groups - Purdue Math
Theorem 10.7 (Orbit-Stabilizer theorem I). Given a transitive subgroup G ✓. Sn, let H be the stabilizer of some element i, then |G| = n|H|. Let us re ...
[42]
[PDF] The Orbit Stabilizer Theorem
Dec 9, 2002 · The Orbit Stabilizer Theorem: Let G be a finite group of permutations of a set S. Then for any i from S, |G| = |orbG(i)|·|stabG(i)|. Example:
[43]
[PDF] finding minimal permutation representations of finite groups
Apr 21, 2008 · Any permutation representation is a disjoint union of orbits. Definition 2.1. The core K(H) of a subgroup H of G is the maximal normal subgroup ...<|control11|><|separator|>
[44]
Permutation Groups | SpringerLink
Free delivery 14-day returnsThis text can serve as an introduction to permutation groups in a course at the graduate or advanced undergraduate level, or for self- study.
[45]
[PDF] Transitive group actions - Keith Conrad
Definition 4.1. An action of a group G on a set X, with |X| ≥ 2, is called doubly transitive when, for all ordered pairs of distinct elements (x, x0) and (y, y ...
[46]
A classification of primitive permutation groups with finite stabilizers
Jun 15, 2015 · A transitive group G is primitive if and only if for all α ∈ Ω the point stabilizer G α is a maximal subgroup of G. Note that if G is transitive ...
[47]
[PDF] Primitive permutation groups 1 The basics 2 Minimal normal ...
Aug 27, 2004 · The action of G on the set of right cosets of H by right multiplication is primitive if and only if H is a maximal proper subgroup of G. Thus, ...
[48]
[PDF] Extremely primitive sporadic and alternating groups - SEIS
Nov 4, 2011 · Abstract. A non-regular primitive permutation group is said to be extremely primitive if a point stabilizer acts primitively on each of its ...
[49]
[PDF] Imprimitive permutations in primitive groups
The permutation g is contained in an imprimitive permutation group with k blocks of size m if and only if the cycle partition of g on {1,...,km} (with k,m > ...
[50]
On the O'Nan-Scott theorem for finite primitive permutation groups
We give a self-contained proof of the O'Nan-Scott Theorem for finite primitive permutation groups.
[51]
[PDF] 21 Symmetric and alternating groups
1) Every finite abelian group is solvable. 2) For n ≥ 5 the symmetric group Sn has a composition series. {(1)} ⊆ An ⊆ Sn and so Sn is not solvable. 23.3 ...Missing: S_n | Show results with:S_n
[52]
[PDF] Basic Theory of Affine Group Schemes - James Milne
Mar 11, 2012 · A group G is said to be solvable if the derived series. G DG D. 2. G terminates with 1. For example, if n 5, then Sn (symmetric group on n ...
[53]
[PDF] Constructing Transitive Permutation Groups
This question is formulated in the language of invariants – at this time there was no formal definition of a permutation group – and what it asks for are ...
[54]
[PDF] arXiv:2305.08405v1 [math.GR] 15 May 2023
May 15, 2023 · The next class of groups we consider are permutation groups, all of whose non- ... has a composition series all of whose factors are cyclic groups ...
[55]
[PDF] Frobenius groups - Huskie Commons
A finite group G is called a Frobenius group if there is a non-trivial subgroup H of G, called the Frobenius complement, such that for all g ∈ G\H we have gHg−1 ...Missing: semiregular | Show results with:semiregular
[56]
[PDF] Chapter 7. Frobenius Groups - RPTU
(a) To use standard group theory terminology, the theorem says that the Frobenius kernel is a normal complement of H in G and that G is an internal semi-direct ...
[57]
(PDF) The Schreier-Sims algorithm - ResearchGate
This representation helps us to calculate the grouporder, list the group elements, generate random elements, test for group mem-bership and store group elements ...
[58]
[PDF] arXiv:1812.03346v2 [math.RA] 15 Dec 2018
Dec 15, 2018 · Our technique is an analogue to the Schreier-Sims algorithm for permutation groups and is a by-product of Frobenius reciprocity. 1. Introduction.Missing: recognition | Show results with:recognition
[59]
[PDF] A polynomial-time theory of black-box groups I 1 Introduction
Charles Sims pioneered the design of efficient algorithms for the rudimentary tasks of managing permutation groups (membership, order, normal closure) based on ...
[60]
[PDF] Oligomorphic permutation groups - Queen Mary University of London
Oligomorphic groups satisfy a rather different kind of finiteness condi- tion; paradoxically, one which makes them “large” rather than “small”. A permutation ...
[61]
https://people.cs.uchicago.edu/~laci/papers/bath1.pdf
[62]
[PDF] Valued Constraint Satisfaction in Structures with an Oligomorphic ...
Page 1. Valued Constraint Satisfaction in. Structures with an Oligomorphic. Automorphism Group ... theory ... The CSP of B (denoted. CSP(B)) is the problem of ...
[63]
Finite Permutation Groups - ScienceDirect.com
Finite Permutation Groups. Book • 1964. Author: HELMUT WIELANDT. Finite ... PDF version. Ways of reading. No information about appearance modifiability is ...
[64]
[PDF] The Evolution of Group Theory: A Brief Survey - Israel Kleiner
Mar 14, 2004 · In 1854 Cayley, in a paper entitled "On the theory of groups, as depending on the symbolic equation @" = 1," gave the first abstract ...
[65]
[PDF] Early group theory in the works of Lagrange, Cauchy, and Cayley
Aug 19, 2010 · ... Lagrange (1736–1813), the first to suggest a relation between permutations and the solution of equations by radicals. In Section 2, we ...
[66]
Paolo Ruffini (1765 - 1822) - Biography - MacTutor
Quick Info. Paolo Ruffini was an Italian mathematician who gave a proof that the quintic equation could not be solved earlier than Abel.
[67]
[PDF] Abel Answers the Question of the Quintic - IMA
Feb 20, 2025 · In his proof, Ruffini employed an important idea from La- grange's 1770 paper, namely that the algebraic solvability of equations was strongly ...
[68]
[PDF] The mathematical writings of Evariste Galois - Uberty
An article published in June 1830 created the theory of Galois imaginaries, a fore-runner of what are now known as finite fields; his so-called Premier Mémoire ...
[69]
[PDF] galois-testamentary.pdf
Letter to Auguste Chevalier. My dear friend,. Paris, 29 May 1832. I have done several new things in analysis. Some concern the theory of equations, others ...
[70]
[PDF] Early Group Theory in the Work of A.-L. Cauchy
Jul 1, 2025 · In Section 1, we examine excerpts from his 1845 work which explain the notion of permutation multiplication and its basic properties. With these ...
[71]
The mathematical life of Cauchy's group theorem - ScienceDirect.com
Cauchy included a variety of results about groups of permutations—conjugate systems of substitutions—in his great 1845 memoir, but he begins the section ...Missing: formalization | Show results with:formalization
[72]
[PDF] Theory of groups of finite order / W. Burnside.
Theory of groups of finite order / W. Burnside. Burnside, William, 1852-1927. Cambridge: The University press, 1911. http://hdl.
[73]
The O'Nan–Scott Theorem (Chapter 4) - Permutation Groups
The socle of a finite group G is the product of the minimal normal subgroups of G. (The original meaning of the word is 'the base on which a statue stands'.) ...
[74]
On an Algorithm for Finding a Base and a Strong Generating Set for ...
Abstract. This paper deals with the problem of finding a base and strong gener- ating set for the group generated by a given set of permutations.
[75]
GAP (ref) - Chapter 43: Permutation Groups
43.5-2 SocleTypePrimitiveGroup. ‣ SocleTypePrimitiveGroup ( G ), ( attribute ). returns the socle type of the primitive permutation ...
[76]
Permutation Group - Magma Computational Algebra System
A software package designed to solve computationally hard problems in algebra, number theory, geometry and combinatorics.Missing: solvable derived affine