# Arithmetic with Words

## Construction of a Word

### `Identity(G): GrpRWS -> GrpRWSElt`

### `Id(G): GrpRWS -> GrpRWSElt`

### `G ! 1: GrpRWS, RngIntElt -> GrpRWSElt`

Construct the identity word in $G$.

### `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$.

### `Parent(w): GrpRWSElt -> GrpRWS`

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

### `Example: Words (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.

### `u * v: GrpRWSElt, GrpRWSElt -> GrpRWSElt`

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

### `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}$.

### `u ^ n: GrpRWSElt, RngIntElt -> GrpRWSElt`

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

### `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$.

### `Inverse(w): GrpRWSElt -> GrpRWSElt`

The inverse of the word $w$.

### `(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$.

### `(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.

### `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.

### `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.

### `IsId(w): GrpRWSElt -> BoolElt`

### `IsIdentity(w): GrpRWSElt -> BoolElt`

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

### `# u: GrpRWSElt -> RngIntElt`

The length of the word $w$.

### `ElementToSequence(u): GrpRWSElt -> [ RngIntElt ]`

### `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$.

### `Example: Arithmetic (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

```