# Introduction

## Terminology

A permutation group $G$ is a group of bijections $X \to X$, for some set $X$. The group $G$ is said to *act* on $X$ and the elements of $G$ are called permutations (of the set $X$). A given permutation group $G$ may have actions on sets other than the one on which it is defined. Thus, any set upon which $G$ has a legitimate action will be called a $G$-set. The set $X$ is called the *natural* $G$*-set* for the group $G$, and the action of $G$ on $X$ is called the *natural action* of $G$. Note that the group $G$ also has a natural induced action on the $G$-closure of any *derived set* of $X$ (see Section 14.8.1). Magma expects the $G$-set $X$ to be of finite cardinality $n$. Usually, $X$ will be $\{1,2,\dots,n\}$, but, as we shall see below, $X$ may be a set of strings, or any other legitimate Magma set.

The elements of a $G$-set are called *points*. Let $Y$ be a $G$-set for $G$. The (possibly empty) subset of $Y$ whose points are fixed by every permutation of $G$, is called the *fixed-point set* for $G$, while the subset of $Y$ consisting of points moved by some permutation of $G$ is called the *support* of $G$. Similarly, for an element $g$ of $G$ the *fixed-point set* and the *support* of $g$ are, respectively, the subsets of $Y$ consisting of the points fixed and moved by $g$. The *degree* of $G$ is defined to be the cardinality of the natural $G$-set of $G$; whereas the *degree* of an element $g$ of $G$ is defined to be the cardinality of the support of $g$, i.e. the number of points moved by $g$.

Permutation groups in Magma are limited to degree less than $2^{30}$.

## The Category of Permutation Groups

The family of all permutation groups of finite degree forms a category. The objects are the permutation groups and the morphisms are group homomorphisms. The Magma designation for this category of permutation groups is `GrpPerm`.

## The Construction of a Permutation Group

Every permutation group acting on a set $X$ is created as a subgroup of the symmetric group ${\operatorname{Sym}}(X)$. Thus, the construction of a general permutation group is a two-step process:

**(i)**
The appropriate symmetric group, ${\operatorname{Sym}}(X)$, is constructed;

**(ii)**
The required group $G$ is then defined as a subgroup of ${\operatorname{Sym}}(X)$.

For convenience, a constructor `PermutationGroup< ... >`, which combines these two steps, is provided.