# Creation of a Permutation Group

## Construction of the Symmetric Group

### `Sym(n): RngIntElt -> GrpPerm`

### `SymmetricGroup(n): RngIntElt -> GrpPerm`

Given an integer $n \geq 1$, create the generic permutation group acting on the natural $G$-set $\Omega = \{ 1, 2, \ldots, n \}$, i.e. the symmetric group ${\operatorname{Sym}}(\Omega)$. Initially, only a structure table is created for ${\operatorname{Sym}}(n)$, so that, in particular, generators are not defined. This function is normally used to provide a context for the creation of elements and subgroups of ${\operatorname{Sym}}(n)$. If structural computation is attempted with the group created by `Sym(n)`, then generators will be created dynamically.

### `Sym(X): Set -> GrpPerm`

### `SymmetricGroup(X): Set -> GrpPerm`

Given a finite set $X$ of cardinality $n \geq 1$, create the generic group $G$ of permutations of $X$ – the symmetric group ${\operatorname{Sym}}(X)$. Initially, only a structure table is created for ${\operatorname{Sym}}(X)$, so that, in particular, generators are not defined. This function is normally used to provide a context for the creation of elements and subgroups of ${\operatorname{Sym}}(X)$. If structural computation is attempted with the group created by `Sym(X)`, then generators will be created dynamically. Although the group $G$ is defined on the set $X$, $G$ is represented internally as a group of permutations of the set $\Omega = \{ 1, 2, \ldots, n \}$. Translation between $X$ and $\Omega$ is done at input/output time. The precise representation can be found by using the `Labelling` function. If $X$ is an indexed set then the indexing of elements of $X$ determines the correspondence.

### `StandardGroup(G): GrpPerm -> GrpPerm, Map`

Return a group $H$ isomorphic to $G$, but acting on the standard set $\lbrace 1, \ldots, n \rbrace$. This function is useful when the natural $G$-set for $G$ is not the standard set. If the natural $G$-set for $G$ is the standard set, $G$ is returned. The isomorphism from $G$ to $H$ is also returned.

### `Example: Sym (ex-667d16)`

We define the symmetric group on the set of strings `{ "a" "b" "c" "d" }`:

```magma
> S4 := Sym({ "a", "b", "c", "d" });
> S4;
Symmetric group S4 acting on a set of cardinality 4
Order = 24 = 2^3 * 3
> GSet(S4);
GSet{@ c, b, a, d @}

```

We define the symmetric group of degree $10$ acting on the set $\{ 0, 1, \ldots,9\}$.

```magma
> G := Sym({ 0..9 });
> G;
Symmetric group G acting on a set of cardinality 10
Order = 3628800 = 2^8 * 3^4 * 5^2 * 7
> GSet(G);
GSet{@ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 @}

```

## Construction of a Permutation

Throughout this subsection we shall assume that the permutation group $G$ has natural $G$-set $X$.

### `elt< G | L >: GrpPerm, List(Elt) -> GrpPermElt`

Given a permutation group $G$ defined as acting on the set $X = \{ x_1,\ldots, x_n\}$ of cardinality $n \geq 1$, and a list $L$ of distinct elements $a_1, a_2, \ldots, a_n$ of $X$, construct the element $g$ of $G$ defined by $x_i \rightarrow a_i$, for $i = 1,\ldots, n$. Unless $G$ is known to be the generic permutation group of degree $n$, the permutation will be tested for membership of $G$, and if $g$ is not an element of $G$, the function will fail. If $g$ does lie in $G$, $g$ will have $G$ as its parent. Since the membership test may involve constructing a base and strong generating set for $G$, this constructor may occasionally be very costly. Hence, a permutation $g$ should be defined as an element of a subgroup of the generic group only when membership of $G$ is required by subsequent operations involving $g$.

### `G ! Q: GrpPerm, [ Elt ] -> GrpPermElt`

Given a permutation group $G$ defined as acting on the set $X = \{ x_1,\ldots, x_n\}$ of cardinality $n \geq 1$, and a sequence $Q = [a_1, a_2, \ldots, a_n]$ of distinct elements of $X$, construct the permutation $g$ of $X$ defined by $x_i \rightarrow a_i$, for $i = 1,\ldots, n$. This permutation will have $G$ as its parent structure. As in the case of the `elt`-constructor, the operation will fail if $g$ is not an element of $G$ and the same observations concerning the cost of membership testing apply.

### `G ! (...)(...)...(...): GrpPerm, Cycles -> GrpPermElt`

Given a permutation group $G$ defined as acting on the set $X=\{x_1$, $x_2, \dots, x_n\}$, construct the permutation $g$ corresponding to the given product of cycles. Adjacent letters must be separated by commas. Further, *cycles of length one must be omitted*. The coercion operator ! may be omitted only within the context of the standard constructors `sub<>`, `ncl<>` and `quo<>`. Once the permutation $g$ has been constructed, it will be tested for membership in $G$. If it is not a member, the construction fails.

### `G ! \(...)(...)...(...): GrpPerm, LiteralCycles -> GrpPermElt`

Given a permutation group $G$ defined as acting on the set $X=\{1 .. n\}$, construct the permutation $g$ corresponding to the given product of literal cycles of integers. Adjacent integers must be separated by commas. Once the permutation $g$ has been constructed, it will be tested for membership in $G$. If it is not a member, the construction fails. This construction is strongly recommended when creating large permutations to avoid overhead in constructing unnecessarily large parse trees by Magma.

### `G ! Q: GrpPerm, SeqEnum[SetIndx] -> GrpPermElt`

Given a permutation group $G$ defined as acting on the set $X=\{1 .. n\}$, construct the permutation $g$ corresponding to the given product of cycles. The indexed sets in $Q$ must be disjoint subsets of $X$, which are interpreted as the disjoint cycles of the permutation being constructed. Cycles of length 1 may be omitted, but do not have to be omitted. Once the permutation $g$ has been constructed, it will be tested for membership in $G$. If it is not a member, the construction fails. Note that the `Cycle` function produces results suitable for use as members of $Q$.

### `ElementToSequence(g): GrpPermElt -> [ Elt ]`

### `Eltseq(g): GrpPermElt -> [ Elt ]`

The sequence $Q$ of images of the $G$-set of g. In particular, it has the property that `Parent(g)!Eltseq(g) eq g`.

### `Identity(G): Grp -> GrpPermElt`

### `Id(G): Grp -> GrpPermElt`

### `G ! 1: Grp, RngIntElt -> GrpPermElt`

Construct the identity permutation in the permutation group $G$.

### `Example: Permutations (ex-ffdb2d)`

The three different constructions are illustrated by the following code, which assigns to each of the variables $x$, $y$ and $z$ the permutation (1)(2,3)(4,5,6).

```magma
> S6 := Sym(6);
> x := elt<S6 | 1,3,2,5,6,4>;
> x;
(2, 3)(4, 5, 6)
> y := S6![1,3,2,5,6,4];
> y;
(2, 3)(4, 5, 6)
> z := S6!(2,3)(4,5,6);
> z;
(2, 3)(4, 5, 6)
> S6!1;
Id(S6)

```

## Construction of a General Permutation Group

### `PermutationGroup< X | L >: Set, List -> GrpPerm`

Suppose that the cardinality of the set $X$ is $n$. Construct the permutation group $G$ acting on the set $X$ generated by the permutations defined by the list $L$. A term of the list $L$ must be an object of one of the following types:

**(a)**
A sequence of $n$ elements of $X$ defining a permutation of $X$ (note that this is only well-defined when $X$ is an indexed set);

**(b)**
A set or sequence of sequences of type (a);

**(c)**
An element of ${\operatorname{Sym}}(X)$;

**(d)**
A set or sequence of elements of ${\operatorname{Sym}}(X)$;

**(e)**
A subgroup of ${\operatorname{Sym}}(X)$;

**(f)**
A set or sequence of subgroups of ${\operatorname{Sym}}(X)$.

Each element or group specified by the list must belong to the *same* generic permutation group. The group $G$ will be constructed as a subgroup of some group which contains each of the elements and groups specified in the list. The generators of $G$ consist of the elements specified by the terms of the list $L$ together with the stored generators for groups specified by terms of the list. The `PermutationGroup` constructor is shorthand for the two statements:

```
   SX := Sym(X);
   G := sub< SX | L >;

```

where `sub< ... >` is the subgroup constructor described in the next subsection.

### `PermutationGroup< n | L >: RngIntElt, List -> GrpPerm`

Construct the permutation group $G$ acting on the set $X = \{ 1, 2, \ldots, n \rbrace$ generated by the permutations defined by the list $L$. The possibilities for the terms of the list $L$ are the same as for the constructor `PermutationGroup< X | L >`.

### `Example: Hessian (ex-1e0f19)`

The Hessian group generated by the permutations $(1,2,4)(5,6,8)(3,9,7)$ and $(4,5,6)(7,9,8)$ may be created by the statement:

```magma
> H := PermutationGroup< 9 | (1,2,4)(5,6,8)(3,9,7), (4,5,6)(7,9,8) >;
> H;
Permutation group H acting on a set of cardinality 9
       (1, 2, 4)(3, 9, 7)(5, 6, 8)
       (4, 5, 6)(7, 9, 8)

```