---
title: "Arithmetic with Words"
canonical: "https://docs.magma-maths.org/v2.30-1/FinitelyPresentedGroups/GroupsDefinedByRewriteSystems/arithmetic.html"
source: "https://docs.magma-maths.org/v2.30-1/FinitelyPresentedGroups/GroupsDefinedByRewriteSystems/arithmetic.md"
part: "Finitely Presented Groups"
chapter: "Groups Defined by Rewrite Systems"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Finitely Presented Groups", "source": "https://docs.magma-maths.org/v2.30-1/FinitelyPresentedGroups/index-finitely-presented-groups.md"}
  - {"title": "Groups Defined by Rewrite Systems", "source": "https://docs.magma-maths.org/v2.30-1/FinitelyPresentedGroups/GroupsDefinedByRewriteSystems/index-groups-defined-by-rewrite-systems.md"}
prev: {"title": "Properties of a Rewrite Group", "source": "https://docs.magma-maths.org/v2.30-1/FinitelyPresentedGroups/GroupsDefinedByRewriteSystems/properties.md"}
next: {"title": "Operations on the Set of Group Elements", "source": "https://docs.magma-maths.org/v2.30-1/FinitelyPresentedGroups/GroupsDefinedByRewriteSystems/Set.md"}
intrinsics:
  - {"name": "Identity", "signature": "Identity(G): GrpRWS -> GrpRWSElt"}
  - {"name": "Id", "signature": "Id(G): GrpRWS -> GrpRWSElt"}
  - {"name": "!", "signature": "G ! 1: GrpRWS, RngIntElt -> GrpRWSElt"}
  - {"name": "!", "signature": "G ! [ i₁, ..., iₛ ]: GrpRWS, [ RngIntElt ] -> GrpRWSElt"}
  - {"name": "Parent", "signature": "Parent(w): GrpRWSElt -> GrpRWS"}
  - {"name": "*", "signature": "u * v: GrpRWSElt, GrpRWSElt -> GrpRWSElt"}
  - {"name": "/", "signature": "u / v: GrpRWSElt, GrpRWSElt -> GrpRWSElt"}
  - {"name": "^", "signature": "u ^ n: GrpRWSElt, RngIntElt -> GrpRWSElt"}
  - {"name": "^", "signature": "u ^ v: GrpRWSElt, GrpRWSElt -> GrpRWSElt"}
  - {"name": "Inverse", "signature": "Inverse(w): GrpRWSElt -> GrpRWSElt"}
  - {"name": "(u, v)", "signature": "(u, v): GrpRWSElt, GrpRWSElt -> GrpRWSElt"}
  - {"name": "(u₁, ..., uᵣ)", "signature": "(u₁, ..., uᵣ): GrpRWSElt, ..., GrpRWSElt -> GrpRWSElt"}
  - {"name": "eq", "signature": "u eq v: GrpRWSElt, GrpRWSElt -> BoolElt"}
  - {"name": "ne", "signature": "u ne v: GrpRWSElt, GrpRWSElt -> BoolElt"}
  - {"name": "IsId", "signature": "IsId(w): GrpRWSElt -> BoolElt"}
  - {"name": "IsIdentity", "signature": "IsIdentity(w): GrpRWSElt -> BoolElt"}
  - {"name": "#", "signature": "# u: GrpRWSElt -> RngIntElt"}
  - {"name": "ElementToSequence", "signature": "ElementToSequence(u): GrpRWSElt -> [ RngIntElt ]"}
  - {"name": "Eltseq", "signature": "Eltseq(u): GrpRWSElt -> [ RngIntElt ]"}
examples:
  - "ex-6e6f68"
  - "ex-0eba9a"
---

# Arithmetic with Words

## Construction of a Word

<a id="function-identity-grprws"></a>
### `Identity(G): GrpRWS -> GrpRWSElt`

<a id="function-id-grprws"></a>
### `Id(G): GrpRWS -> GrpRWSElt`

<a id="operation-op-grprws-rngintelt"></a>
### `G ! 1: GrpRWS, RngIntElt -> GrpRWSElt`

Construct the identity word in $G$.

<a id="operation-op-grprws-rngintelt-2"></a>
### `G ! [ i₁, ..., iₛ ]: GrpRWS, [ RngIntElt ] -> GrpRWSElt`

Given a rewrite group $G$ defined on $r$ generators and a sequence $[i_1, \cdots, i_s]$ of integers lying in the range $[-r, r]$, excluding $0$, construct the word

$$
G.|i_1|^{\epsilon_1}*G.|i_2|^{\epsilon_2}* \cdots *G.|i_s|^{\epsilon_s}
$$

where $\epsilon_j$ is $+1$ if $i_j$ is positive, and $-1$ if $i_j$ is negative. The resulting word is reduced using the reduction machine associated with $G$.

<a id="function-parent-grprwselt"></a>
### `Parent(w): GrpRWSElt -> GrpRWS`

The parent group $G$ for the word $w$.

<a id="example-ex-6e6f68"></a>
### `Example: Constructing Words in a Rewrite Group (ex-6e6f68)`

We construct the Fibonacci group $F(2,7)$, and its identity.

```magma
> FG<a,b,c,d,e,f,g> := FreeGroup(7);
> F := quo< FG | a*b=c, b*c=d, c*d=e, d*e=f, e*f=g, f*g=a, g*a=b>;
> G := RWSGroup(F : TidyInt := 1000);
> Id(G);
Id(G)
> G!1;
Id(G)
> G![1,2];
G.3
```

## Element Operations

Having constructed a rewrite group $G$ one can perform arithmetic with words in $G$. Assuming we have $u, v \in G$ then the product $u*v$ will be computed as follows:

**(i)**
the product $w = u*v$ is formed as a product in the appropriate free group.

**(ii)**
$w$ is reduced using the reduction machine associated with $G$.

If $G$ is confluent, then $w$ will be the unique minimal word that represents $u*v$ under the ordering of $G$. If $G$ is not confluent, then there are some pairs of words which are equal in $G$, but which reduce to distinct words, and hence $w$ will not be a unique normal form. Note that:

**(i)**
reduction of $w$ can cause an increase in the length of $w$. At present there is an internal limit on the length of a word – if this limit is exceeded during reduction an error will be raised. Hence any word operation involving reduction can fail.

**(ii)**
the implementation is designed more with speed of execution in mind than with minimizing space requirements; thus, the reduction machine is always used to carry out word reduction, which can be space-consuming, particularly when the number of generators is large.

<a id="operation-op-times-grprwselt-grprwselt"></a>
### `u * v: GrpRWSElt, GrpRWSElt -> GrpRWSElt`

Given words $w$ and $v$ belonging to a common group, return their product.

<a id="operation-op-div-grprwselt-grprwselt"></a>
### `u / v: GrpRWSElt, GrpRWSElt -> GrpRWSElt`

Given words $w$ and $v$ belonging to a common group, return the product of the word $u$ by the inverse of the word $v$, i.e. the word $u*v^{-1}$.

<a id="operation-op-pow-grprwselt-rngintelt"></a>
### `u ^ n: GrpRWSElt, RngIntElt -> GrpRWSElt`

The $n$-th power of the word $w$.

<a id="operation-op-pow-grprwselt-grprwselt"></a>
### `u ^ v: GrpRWSElt, GrpRWSElt -> GrpRWSElt`

Given words $w$ and $v$ belonging to a common group, return the conjugate of the word $u$ by the word $v$, i.e. the word $v^{-1}*u*v$.

<a id="function-inverse-grprwselt"></a>
### `Inverse(w): GrpRWSElt -> GrpRWSElt`

The inverse of the word $w$.

<a id="literal-literal-u-v-grprwselt-grprwselt-grprwselt"></a>
### `(u, v): GrpRWSElt, GrpRWSElt -> GrpRWSElt`

Given words $w$ and $v$ belonging to a common group, return the commutator of the words $u$ and $v$, i.e., the word $u^{-1}v^{-1}uv$.

<a id="literal-literal-u1-ur-grprwselt-grprwselt-grprwselt"></a>
### `(u₁, ..., uᵣ): GrpRWSElt, ..., GrpRWSElt -> GrpRWSElt`

Given $r$ words $u_1, \ldots, u_r$ belonging to a common group, return their commutator. Commutators are *left-normed*, so they are evaluated from left to right.

<a id="operation-op-eq-grprwselt-grprwselt"></a>
### `u eq v: GrpRWSElt, GrpRWSElt -> BoolElt`

Given words $w$ and $v$ belonging to the same group, return `true` if $w$ and $v$ reduce to the same normal form, `false` otherwise. If $G$ is confluent this tests for equality. If $G$ is non-confluent then two words which are the same may not reduce to the same normal form.

<a id="operation-op-ne-grprwselt-grprwselt"></a>
### `u ne v: GrpRWSElt, GrpRWSElt -> BoolElt`

Given words $w$ and $v$ belonging to the same group, return `false` if $w$ and $v$ reduce to the same normal form, `true` otherwise. If $G$ is confluent this tests for non-equality. If $G$ is non-confluent then two words which are the same may reduce to different normal forms.

<a id="function-isid-grprwselt"></a>
### `IsId(w): GrpRWSElt -> BoolElt`

<a id="function-isidentity-grprwselt"></a>
### `IsIdentity(w): GrpRWSElt -> BoolElt`

Returns `true` if the word $w$ is the identity word.

<a id="operation-operation-grprwselt-rngintelt"></a>
### `# u: GrpRWSElt -> RngIntElt`

The length of the word $w$.

<a id="function-elementtosequence-grprwselt"></a>
### `ElementToSequence(u): GrpRWSElt -> [ RngIntElt ]`

<a id="function-eltseq-grprwselt"></a>
### `Eltseq(u): GrpRWSElt -> [ RngIntElt ]`

The sequence $Q$ obtained by decomposing the element $u$ of a rewrite group into its constituent generators and generator inverses. Suppose $u$ is a word in the rewrite group $G$. Then, if $u = G.i_1^{e_1} \cdots G.i_m^{e_m}$, with each $e_i = \pm 1$, then $Q[j] = i_j$ if $e_j = +1$ and $Q[j] = -i_j$ if $e_j = {-1}$, for $j = 1, \ldots, m$.

<a id="example-ex-0eba9a"></a>
### `Example: Word Arithmetic in a Fibonacci Group (ex-0eba9a)`

We illustrate the word operations by applying them to elements of the Fibonacci group $F(2,5)$.

```magma
> FG<a,b,c,d,e> := FreeGroup(5);
> F := quo< FG | a*b=c, b*c=d, c*d=e, d*e=a, e*a=b>;
> G<a,b,c,d,e> := RWSGroup(F);
> a*b^-1;
e^-1
> a/b;
e^-1
> (c*d)^4;
a
> a^b, b^-1*a*b;
a a
> a^-2,
> Inverse(a)^2;
d d
> c^-1*d^-1*c*d eq (c,d);
true
> IsIdentity(a*b*c^-1);
true
> #(c*d);
1
```
