---
title: "Presentations"
canonical: "https://docs.magma-maths.org/v2.30-1/FiniteGroups/PermutationGroups/presentations.html"
source: "https://docs.magma-maths.org/v2.30-1/FiniteGroups/PermutationGroups/presentations.md"
part: "Finite Groups"
chapter: "Permutation Groups"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Finite Groups", "source": "https://docs.magma-maths.org/v2.30-1/FiniteGroups/index-finite-groups.md"}
  - {"title": "Permutation Groups", "source": "https://docs.magma-maths.org/v2.30-1/FiniteGroups/PermutationGroups/index-permutation-groups.md"}
prev: {"title": "Cosets and Transversals", "source": "https://docs.magma-maths.org/v2.30-1/FiniteGroups/PermutationGroups/cosets-transversals.md"}
next: {"title": "Automorphism Groups", "source": "https://docs.magma-maths.org/v2.30-1/FiniteGroups/PermutationGroups/automorphisms.md"}
intrinsics:
  - {"name": "FPGroup", "signature": "FPGroup(G): GrpPerm -> GrpFP, Hom(Grp)"}
  - {"name": "FPGroup", "signature": "FPGroup(G, N): GrpPerm, GrpPerm -> GrpFP, Hom(Grp)"}
  - {"name": "FPQuotient", "signature": "FPQuotient(G, N): GrpPerm, GrpPerm -> GrpFP, Hom(Grp)"}
  - {"name": "FPGroupStrong", "signature": "FPGroupStrong(G: parameters): GrpPerm -> GrpFP, Hom(Grp)"}
  - {"name": "WordGroup", "signature": "WordGroup(G): GrpPerm -> GrpBB, Map"}
  - {"name": "InverseWordMap", "signature": "InverseWordMap(G): GrpPerm -> Map"}
  - {"name": "ActingWord", "signature": "ActingWord(G, x, y): GrpPerm, Elt, Elt -> GrpFPElt"}
  - {"name": "WordInGenerators", "signature": "WordInGenerators(G, g : parameters): GrpPerm, GrpPermElt -> GrpFPElt"}
---

# 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

<a id="function-fpgroup-grpperm"></a>
### `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.

<a id="function-fpgroup-grpperm-grpperm"></a>
### `FPGroup(G, N): GrpPerm, GrpPerm -> GrpFP, Hom(Grp)`

<a id="function-fpquotient-grpperm-grpperm"></a>
### `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$.

<a id="function-fpgroupstrong-grpperm"></a>
### `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 [[Leo80](https://docs.magma-maths.org/v2.30-1/references.md#cite-leon3)] and Gebhardt [[Geb00](https://docs.magma-maths.org/v2.30-1/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$.

<a id="function-wordgroup-grpperm"></a>
### `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$.

<a id="function-inversewordmap-grpperm"></a>
### `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.

<a id="function-actingword-grpperm-elt-elt"></a>
### `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$.

<a id="function-wordingenerators-grpperm-grppermelt"></a>
### `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 [[Min98](https://docs.magma-maths.org/v2.30-1/references.md#cite-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.
