Basic Operations

Accessing Monoid Information

The functions in this section provide access to basic information stored for a rewrite monoid \(M\).

M . i: MonRWS, RngIntElt -> MonRWSElt: The \(i\)-th defining generator for \(M\).

Generators(M): MonRWS -> [ MonRWSElt]: A sequence containing the defining generators for \(M\).

NumberOfGenerators(M): MonRWS -> RngIntElt
Ngens(M): MonRWS -> RngIntElt: The number of defining generators for \(M\).

Relations(M): MonRWS -> [MonFPRel]: A sequence containing the defining relations for \(M\). The relations will be given between elements of the free monoid of which \(M\) is a quotient. In these relations the (image of the) left hand side (in \(M\)) will always be greater than the (image of the) right hand side (in \(M\)) in the ordering on words used to construct \(M\).

NumberOfRelations(M): MonRWS -> RngIntElt
Nrels(M): MonRWS -> RngIntElt: The number of relations in \(M\).

Ordering(M): MonRWS -> String: The ordering of \(M\).

Parent(w): MonRWSElt -> MonRWS: The parent monoid \(M\) for the word \(w\).

Example: Accessing Rewrite Monoid Information (ex-de40ce)

Run in calculator (opens in a new tab)

We illustrate the access operations using the following presentation of \(S_4\).

> FM<a,b> := FreeMonoid(2);
> Q := quo< FM | a^2=1, b^3=1, (a*b)^4=1 >;
> M<x,y> := RWSMonoid(Q);
> print M;
A confluent rewrite monoid.
Generator Ordering = [ a, b ]
Ordering = ShortLex.
The reduction machine has 12 states.
    a^2 = Id(FM)
    b^3 = Id(FM)
    b * a * b * a * b = a * b^2 * a
    b^2 * a * b^2 = a * b * a * b * a
    b * a * b^2 * a * b * a = a * b * a * b^2 * a * b

> print Order(M);
24
> print M.1;
x
> print M.1*M.2;
x * y
> print Generators(M);
[ x, y ]
> print Ngens(M);
2
> print Relations(M);
[ a^2 = Id(FM), b^3 = Id(FM), b * a * b * a * b = a * b^2 * a, b^2 * a * b^2 = a
* b * a * b * a, b * a * b^2 * a * b * a = a * b * a * b^2 * a * b ]
> print Nrels(M);
5
> print Ordering(M);
ShortLex

Run in calculator (opens in a new tab)

Properties of a Rewrite Monoid

IsConfluent(M): MonRWS -> BoolElt: Returns true if \(M\) is confluent, false otherwise.

IsFinite(M): MonRWS -> BoolElt, RngIntElt: Given a confluent monoid \(M\) return true if \(M\) has finite order and false otherwise. If \(M\) does have finite order also return the order of \(M\).

Order(M): MonRWS -> RngIntElt
# M: MonRWS -> RngIntElt: Given a monoid \(M\) defined by a confluent presentation, this function returns the cardinality of \(M\). If the order of \(M\) is known to be infinite \(\infty\) is returned.

Example: Order of a Threefold Cover of A6 (ex-7a9289)

We construct a threefold cover of \(A_6\).

> FM<a,b> := FreeMonoid(2);
> Q := quo< FM | a^3=1, b^3=1, (a*b)^4=1, (a*b^2)^5 = 1 >;
> M := RWSMonoid(Q);
> print Order(M);
1080
> IsConfluent(M);
true

Run in calculator (opens in a new tab)

Example: Order of a Free Abelian Group (ex-541f65)

We construct the 2-generator free abelian group and compute its order. The result Infinity indicates that the group has infinite order.

> FM<a,A,b,B> := FreeMonoid(4);
> Q := quo< FM | a*A=1, A*a=1, b*B=1, B*b=1, B*a*b=a>;
> M := RWSMonoid(Q);
> Order(M);
Infinity

Run in calculator (opens in a new tab)

Example: Finiteness of the Weyl Group E8 (ex-2a5004)

We construct the Weyl group \(E_8\) and test whether or not it has finite order.

> FM<a,b,c,d,e,f,g,h> := FreeMonoid(8);
> Q := quo< FM | a^2=1, b^2=1, c^2=1, d^2=1, e^2=1, f^2=1, g^2=1,
>         h^2=1, b*a*b=a*b*a, c*a=a*c, d*a=a*d, e*a=a*e, f*a=a*f,
>         g*a=a*g, h*a=a*h, c*b*c=b*c*b, d*b=b*d, e*b=b*e, f*b=b*f,
>         g*b=b*g, h*b=b*h, d*c*d=c*d*c, e*c*e=c*e*c, f*c=c*f,
>         g*c=c*g, h*c=c*h, e*d=d*e, f*d=d*f, g*d=d*g, h*d=d*h,
>         f*e*f=e*f*e, g*e=e*g, h*e=e*h, g*f*g=f*g*f, h*f=f*h,
>         h*g*h=g*h*g>;
> M := RWSMonoid(Q);
> print IsFinite(M);
true
> isf, ord := IsFinite(M);
> print isf, ord;
true 696729600

Run in calculator (opens in a new tab)

Construction of a Word

Identity(M): MonRWS -> MonRWSElt
Id(M): MonRWS -> MonRWSElt
M ! 1: MonRWS, RngIntElt -> MonRWSElt: Construct the identity word in \(M\).

M ! [ i₁, ..., iₛ ]: MonRWS, [ RngIntElt ] -> MonRWSElt: Given a rewrite monoid \(M\) defined on \(r\) generators and a sequence \([i_1, \cdots, i_s]\) of integers lying in the range \([1, r]\), construct the word \(M.i_1*M.i_2* \cdots *M.i_s\).

Example: Constructing Words in a Rewrite Monoid (ex-00230f)

We construct the Fibonacci group \(F(2,7)\), and it’s identity.

> FM<a,A,b,B,c,C,d,D,e,E,f,F,g,G> := FreeMonoid(14);
> Q := quo< FM | a*A=1, A*a=1, b*B=1, B*b=1, c*C=1, C*c=1,
>                d*D=1, D*d=1, e*E=1, E*e=1, f*F=1, F*f=1, g*G=1, G*g=1,
>                a*b=c, b*c=d, c*d=e, d*e=f, e*f=g, f*g=a, g*a=b>;
> M := RWSMonoid(Q : TidyInt := 1000);
> print Id(M);
Id(M)
> print M!1;
Id(M)
> Order(M);
29

Run in calculator (opens in a new tab)

Arithmetic with Words

Having constructed a rewrite monoid \(M\) one can perform arithmetic with words in \(M\). Assuming we have \(u, v \in M\) 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 monoid.
(ii): The word \(w\) is reduced using the reduction machine associated with \(M\).

If \(M\) is confluent, then \(w\) will be the unique minimal word that represents \(u*v\) under the ordering of \(M\). If \(M\) is not confluent, then there are some pairs of words which are equal in \(M\), 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: MonRWSElt, MonRWSElt -> MonRWSElt: Product of the words \(w\) and \(v\).

u ^ n: MonRWSElt, RngIntElt -> MonRWSElt: The \(n\)-th power of the word \(w\), where \(n\) is a positive or zero integer.

u eq v: MonRWSElt, MonRWSElt -> BoolElt: Given words \(w\) and \(v\) belonging to the same monoid, return true if \(w\) and \(v\) reduce to the same normal form, false otherwise. If \(M\) is confluent this tests for equality. If \(M\) is non-confluent then two words which are the same may not reduce to the same normal form.

u ne v: MonRWSElt, MonRWSElt -> BoolElt: Given words \(w\) and \(v\) belonging to the same monoid, return false if \(w\) and \(v\) reduce to the same normal form, true otherwise. If \(M\) is confluent this tests for non-equality. If \(M\) is non-confluent then two words which are the same may reduce to different normal forms.

IsId(w): MonRWSElt -> BoolElt
IsIdentity(w): MonRWSElt -> BoolElt: Returns true if the word \(w\) is the identity word.

# u: MonRWSElt -> RngIntElt: The length of the word \(w\).

ElementToSequence(u): MonRWSElt -> [ RngIntElt ]
Eltseq(u): MonRWSElt -> [ RngIntElt ]: The sequence \(Q\) obtained by decomposing the element \(u\) of a rewrite monoid into its constituent generators. Suppose \(u\) is a word in the rewrite monoid \(M\). If \(u = M.i_1 \cdots M.i_m\), then \(Q[j] = i_j\), for \(j = 1, \ldots, m\).

Example: Word Arithmetic in a Fibonacci Monoid (ex-3c8630)

We illustrate the word operations by applying them to elements of the Fibonacci monoid \(FM(2,5)\).

> FM<a,b,c,d,e> := FreeMonoid(5);
> Q:=quo< FM | a*b=c, b*c=d, c*d=e, d*e=a, e*a=b >;
> M<a,b,c,d,e> := RWSMonoid(Q);
> a*b*c*d;
b^2
> (c*d)^4 eq a;
true
> IsIdentity(a^0);
true
> IsIdentity(b^2*e);
false

Run in calculator (opens in a new tab)

Basic Operations#

Accessing Monoid Information#

Properties of a Rewrite Monoid#

Construction of a Word#

Arithmetic with Words#

Basic Operations

Accessing Monoid Information

Properties of a Rewrite Monoid

Construction of a Word

Arithmetic with Words