Permutation group

2020 Mathematics Subject Classification: Primary: 20-XX [MSN][ZBL]

A permutation group is a set of permutations (cf. Permutation of a set) of a set $X$ that form a group under the operation of multiplication (composition) of permutations. In other words, a permutation group is a pair $(G,X)$, where $G$ is a group and $X$ is a set, and each $\def\g{\gamma}\g\in G$ corresponds to a transformation $x\mapsto x^\g$ of $X$ such that 1) $\def\a{\alpha}\def\b{\beta} x^{\a\b} = (x^\a)^\b$, $x\in X$, $\a,\b\in G$; and 2) $x^\a = x$ for all $x\in X$ if and only if $\def\e{\epsilon}\a = \e$ is the identity element of $G$. If only condition 1) is fulfilled, one speaks of an action (or a representation) of $G$ on $X$. In that case the subset $H$ of elements of $G$ that leave invariant all $x\in X$ will be a normal subgroup of $G$ (called the kernel of the action), and the quotient group $G/H$ acts on $X$ as a permutation group. If $X$ is a finite set, then a permutation group $(G,X)$ is called finite, otherwise infinite. The set of all permutations on $X$ is called the symmetric group on $X$, and is denoted by $S(X)$, or $S_n$ if $X=\{1,\dots,n\}$.

A similarity (or isomorphism) from a permutation group $(G,X)$ onto a permutation group $(G',X')$ is a pair $\def\phi{\varphi}(\phi,\psi)$ of mappings, where $\phi$ is an isomorphism from $G$ onto $G'$ and $\psi$ is a bijection from $X$ onto $X'$, where the two mappings fit in the sense that for all $x\in X$ and $\a\in G$ one has $(x^\a)^\psi = (x^\psi)^{\a\phi}$. Permutation groups between which there is a similarity are called similar. If $(G,X)$ is a permutation group, there is a naturally defined equivalence on the set $X$: $y\sim x$, $y,x\in X$, if and only if $y=x^\a$ for some $\a\in G$; the equivalence classes of a permutation group are called orbits or sets of transitivity of the group $(G,X)$. A permutation group is transitive if it has only one orbit, while otherwise it is called intransitive. (See Transitive group.)

Any abstract group $G$ can be represented as a permutation group on a suitable set $X$ (Cayley's theorem). Here as $X$ one may take the set of all elements of $G$ and put each $\g\in G$ into correspondence with the mapping obtained by multiplication on the right by that element $\g:\xi^\g = \xi\g$: $G$. The resulting regular representation of $G$ as a permutation group is not the only one possible. In research on permutation groups one is interested in properties different from those of interest in research on abstract groups. One is concerned not only with the group structure but primarily with how the group acts on the set $X$; for example, the property of transitivity is a property of permutation groups, not of abstract groups.

Let $(G,X)$ be a permutation group and $M$ a subset of $X$. The set of all permutations $\g\in G$ that map $M$ into itself (i.e. $x\in M \leftrightarrow x^\g \in M$) forms a subgroup $G_M$, called the stabilizer of the set $M$. The set of those permutations that leave invariant all individual $y\in M$ is called the pointwise stabilizer (or fixator) of the set $M$ and is denoted by $G_{\{M\}}$. The pointwise stabilizer is a normal subgroup of the stabilizer. If $M=\{\a\}$ is a one-element set, the concepts of stabilizer and pointwise stabilizer coincide (the result is denoted by $G_\a$). A permutation group is called semi-regular (or freely acting) if the stabilizer of each point is the identity group and regular (or simply transitive) if the group is also transitive. The centralizer $Z(G)$ of a permutation group $G$ is defined as the centralizer of $G$ in the symmetric group $S(X)$, i.e. the set of permutations on $X$ that commute with the elements of $G$. The centralizer of a transitive group is semi-regular, and, conversely, the centralizer of a semi-regular group is transitive. A regular permutation group $(G,X)$ is similar to the above-described regular representation of the group $G$. The centralizer $Z(G)$ of the regular representation is the so-called left regular representation of $G$, which associates with the element $\g\in G$ the permutation $\xi^\g = \g^{-1}\xi$, $\xi\in G$.

There are operations, [KaKlSu], that enable one to construct new permutation groups from given ones.

a) The sum of permutation groups. Let $(G,X)$ and $(H,Y)$ be two permutation groups with empty intersection $X\cap Y$. The sum $(G,X)+(H,Y)$ is defined as the permutation group consisting of the direct product $G\times H$ acting on the union $X\cup Y$, where for $\a\in G$, $\b\in H$, $z \in X\cup Y$,

$$z^{(\a,\b)} = \begin{cases}z^\a \quad & \textrm{ if } z\in X,\\ z^\b \quad & \textrm{ if } z\in Y.\end{cases}$$ b) The product $(G,X)\times (H,H)$ of two permutation groups $(G,X)$ and $(H,Y)$ is the group $(G\times H,X\times Y)$ acting on $X\times Y$ according to the formula $(x,y)^{(\a,\b)} = (x^\a,y^\b)$.

The two operations are associative and may be defined for any number of groups.

c) The wreath product. Let $(G,X)$ and $(H,Y)$ be two permutation groups and let $\b\in H^X$ denote a mapping from $X$ into $H$. On the set of pairs $[\a,\b]$, which are called tables, a multiplication is defined by:

$$[\a,\b][\a',\b'] = [\a\a',x\mapsto \b(x)\b'(x^\a)],$$ with respect to which they form a group $G\wr H$. The wreath product of the permutation groups $(G,X)$ and $(H,Y)$ is the permutation group $(G\wr H,X\times Y)$, where the action is defined by the formula

$$(x,y)^{[\a,\b]} = (x^\a,y^{\b(x)}).$$ The wreath product is associative and may even be defined for any totally ordered family of permutation groups. The wreath product of non-identity permutation groups is an imprimitive group. If $G$ and $H$ are taken in the guise of their regular representations, this concept coincides apart from the order of the factors with the usual group-theoretic wreath product.

d) Exponentiation. The group of tables acting on the set $Y^X$ leads to the permutation groups

$$(H,Y)^{(G,X)} = (G\wr H,Y^X),$$ where the action is defined as follows:

$$f^{[\a,\b]} = (x\mapsto f(x^\a)^{\b(x)}),$$ with $f\in Y^X$. Exponentiation is not associative and usually yields primitive groups, since $(H,Y)^{(G,X)}$ is primitive if $(H,Y)$ is a primitive non-cyclic group.

Permutation groups arise usually as groups of permutations preserving certain relations or operations on a set $X$ (see also Transformation group). For example, one source of the theory of permutation groups was the concept of the Galois group of a polynomial. If

$$f(x) = a_nx^n+\cdots + a_0$$ is a polynomial with coefficients $a_i$ in some field $K$ and $\xi_1,\dots,\xi_n$ are the roots in some extension field, then the Galois group is the group of permutations of the set $\{\xi_1,\dots,\xi_n\}$ that preserve rational relations between the roots, i.e. equations of the form

$$\sum c_{i_1\dots i_n}\xi_1^{i_1}\dots\xi_n^{i_n} = 0,$$ where $c_{i_1\dots i_n}\in K$. E. Galois showed that the properties of this group govern the solvability of the equation $f(x) = 0$ in radicals. This result led to developments in the theory of permutation groups by Galois, J. Serret, C. Jordan, and others. Further developments at the end of the nineteenth and the beginning of the 20th century were due to W. Burnside, W. Manning, G. Frobenius, O.Yu. Schmidt, and I. Schur. Permutation groups have many applications in discrete mathematics, for example in the classification of Boolean functions and finite automata, as well as in the theory of error-correcting codes and in counting the isomers of complicated organic compounds.

References

[Bu]	W. Burnside, "Theory of groups of finite order", Dover, reprint (1955) (Translated from German) MR0069818 Zbl 0064.25105
[Ha]	M. Hall, "The theory of groups", Macmillan (1959) MR0103215 Zbl 0084.02202
[KaKlSu]	L.A. Kaluzhnin, M.Kh. Klin, V.I. Sushchanskii, "Exponentiation of permutation groups I" Izv. Vyssch. Uchebn. Zaved. Mat. : 8 (1979) pp. 26–33 (In Russian) MR0554500 Zbl 0476.20004
[KaSu]	L.A. Kaluzhnin, V.I. Sushchanskii, "Transformations and permutations", Moscow (1979) (In Ukrainian) MR0569056 Zbl 0486.20001
[Pa]	D. Passman, "Permutation groups", Benjamin (1968) MR0237627 MR0236252 Zbl 0179.04405 Zbl 0164.33805
[Wi]	H. Wielandt, "Finite permutation groups", Acad. Press (1964) (Translated from German) MR0183775 Zbl 0138.02501