# Presentations

In this section we describe how to compute a presentation in terms of generators and relations for a permutation group and also how to obtain a representation of a permutation as word in the defining generators.

## Generators and Relations

### `FPGroup(G): GrpPerm -> GrpFP, Hom(Grp)`

Construct a presentation for the permutation group $G$ on the set of defining generators and return the presentation in the form of a finitely presented group $F$ that is isomorphic to $G$. The presentation is obtained by first computing the regular representation of $G$ and then using the Todd-Coxeter Schreier algorithm to construct a presentation on the strong generators. In this situation the strong generators are identical to the defining generators.

A group homomorphism $\phi: F \rightarrow G$, defining $G$ as a permutation representation of $F$, is also returned.

### `FPGroup(G, N): GrpPerm, GrpPerm -> GrpFP, Hom(Grp)`

### `FPQuotient(G, N): GrpPerm, GrpPerm -> GrpFP, Hom(Grp)`

Given a normal subgroup $N$ of $G$, compute an fp-group representation $F$ of the quotient $G/N$ and the homomorphism $\phi: G\rightarrow F$.

### `FPGroupStrong(G: parameters): GrpPerm -> GrpFP, Hom(Grp)`

```magma
Random: BoolElt                      Default: true
Run   : RngIntElt                    Default: 20
```

Construct a presentation for the permutation group $G$ on a set of strong generators and return the presentation in the form of a finitely presented group $F$ that is isomorphic to $G$. In Magma, a combination of the Schreier Todd-Coxeter Sims algorithm and the Brownie-Cannon-Sims verification procedure is used to construct the presentation. See Leon [[Leon, 1980](../../references.md#cite-leon3)] and Gebhardt [[Gebhardt, 2000](../../references.md#cite-gebhardt-presentations)] for more details of the individual algorithms.

If strong generators are not already known for $G$, they will be constructed. If strong generators have to be constructed, the parameters `Random` and `Run` may be used to control the application of the random schreier algorithm to construct a probable BSGS before commencing the construction of the presentation. If `Random` is set to false then no randomising is performed, and the algorithm becomes the straight STCS algorithm. In the case in which strong generators are already known for $G$, the presentation will be on these strong generators.

The presentation will have the property that it includes a presentation for each group in the stabilizer chain of the BSGS.

The group isomorphism $\phi: F \rightarrow G$, defining $G$ as a permutation representation of $F$, is also returned.

## Permutations as Words

Consider a permutation group $G$ defined on $d$ generators. The *word group* of $G$ is a free group $W$ of rank $d$. Then we regard $G$ as a homomorphic image of $F$ with associated homomorphism $\phi: W \rightarrow G$. All operations involving words in the generators of $G$ will be performed in $W$.

### `WordGroup(G): GrpPerm -> GrpBB, Map`

Given a permutation group $G$ defined on $d$ generators, return (a) a free group $W$ on $d$ generators represented as a group whose elements are defined by straight-line programs (SLP group), and (b) the homomorphism $\phi$ from $W$ to $G$ such that $W.i \rightarrow G.i$, for $i = 1, \ldots, d$. The group $W$ associated with $G$ by this function will be referred to as the *word group* for $G$.

### `InverseWordMap(G): GrpPerm -> Map`

Given a permutation group $G$ and its associated word group $W$ with canonical homomorphism $\phi:W \rightarrow G$, construct the inverse mapping $\rho$. Thus, given a permutation $g$ of $G$, $g@\rho$ returns an element in the preimage of $g$ under $\phi$. If the word group $W$ does not already exist, it will be created.

### `ActingWord(G, x, y): GrpPerm, Elt, Elt -> GrpFPElt`

Given points $x$ and $y$ belonging to the same $G$-orbit of the natural $G$-set $X$, return a word $w$ in the word group $W$ of $G$ such that $x^{\phi(w)} = y$. Here $\phi$ is the canonical homomorphism from $W$ to $G$.

### `WordInGenerators(G, g : parameters): GrpPerm, GrpPermElt -> GrpFPElt`

```magma
RegLimit: RngIntElt                    Default: 1000000
Print   : RngIntElt                    Default: 0
```

Compute a word in a free group with generators corresponding to those of the group $G$ that evaluates to the element $g \in G$.

If $G$ has order at most `RegLimit` then the word will be computed using the regular permutation representation of $G$, and will be guaranteed to be a shortest word representing $g$. Otherwise an algorithm of Minkwitz [] is used, which will find a reasonably short word for $g$ but not necessarily a shortest word. The optional parameter `Print` controls the printing of diagnostics.

The first call of this function for an element $g$ of the group $G$ will take longer than subsequent calls for elements of the same group, because some necessary data is calculated with the first call.