Free Groups and Words#

Construction of a Free Group#

FreeGroup(n): RngIntElt -> GrpFP#

Construct the free group \(F\) of rank \(n\), where \(n\) is a positive integer.

The \(i\)-th generator of \(F\) may be referenced by the expression F.i, \(i = 1, \ldots, n\). Note that a special form of the assignment statement is provided which enables the user to assign names to the generators of \(F\). In this form of assignment, the list of generator names is enclosed within angle brackets and appended to the variable name on the left hand side of the assignment statement:

F< v_1, ... v_n > := FreeGroup(n);

Example: Free (ex-f04611)#

The statement

> F := FreeGroup(2);

Run in calculator

creates the free group of rank 2. Here the generators may be referenced using the standard names, F.1 and F.2. The statement

> F<x, y> := FreeGroup(2);

Run in calculator

defines \(F\) to be the free group of rank 2 and assigns the names \(x\) and \(y\) to the two generators.

Construction of Words#

The operations in this section apply to both, free groups and arbitrary fp-groups.

G ! [ i₁, ..., iₛ ]: GrpFP, [ RngIntElt ] -> GrpFPElt#

Given a 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.

Identity(G): GrpFP -> GrpFPElt#
Id(G): GrpFP -> GrpFPElt#
G ! 1: GrpFP, RngIntElt -> GrpFPElt#: Construct the identity element, represented as the empty word, for the fp-group \(G\). For a sample application of this function, see Example Example: Words.

Random(G, m, n): GrpFP, RngIntElt, RngIntElt -> GrpFPElt#: A random word of length \(l\) in the generators of the group \(G\), where \(m \leq l \leq n\). For a sample application of this function, see Example Example: Words.

Access Functions for Words#

This section describes some basic access functions for words. These operations apply to both, free groups and arbitrary fp-groups.

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

ElementToSequence(w): GrpFPElt -> [ RngIntElt ]#
Eltseq(w): GrpFPElt -> [ RngIntElt ]#: The sequence \(Q\) obtained by decomposing the word \(w\) into its constituent generators and generator inverses. Suppose \(w\) is a word in the group \(G\). Then, if \(w = 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\).

ExponentSum(w, x): GrpFPElt, GrpFPElt -> RngIntElt#
Weight(w, x): GrpFPElt, GrpFPElt -> RngIntElt#: Given a word \(w\), and the name of a generator \(x\) of a group \(G\), compute the sum of the exponents of the generator \(x\) in the word \(w\). For a sample application of this function, see Example Example: Words.

GeneratorNumber(w): GrpFPElt -> RngIntElt#

Suppose \(w\) is a word belonging to a group \(G\). Assume \(x\) is the name of the \(i\)-th generator of \(G\). Then

(i): if \(w =\) Identity(G), GeneratorNumber(w) is 0;
(ii): if \(w = x*w'\), \(w'\) a word in \(G\), GeneratorNumber(w) is \(i\);
(iii): if \(w = x^{-1}*w'\), \(w'\) a word in \(G\), GeneratorNumber(w) is \(-i\).

LeadingGenerator(w): GrpFPElt -> GrpFPElt#: Suppose \(w\) is a word belonging to a group \(G\). If \(w = x^\epsilon*w'\), \(w'\) a word in \(G\), \(x\) a generator of \(G\) and \(\epsilon\in\{-1,+1\}\), the functions returns \(x^\epsilon\). If \(w=\) Identity(G), it returns Identity(G). For a sample application of this function, see Example Example: Words.

Parent(w): GrpFPElt -> GrpFP#: The parent group \(G\) of the word \(w\).

Example: Word Access (ex-117fb7)#

Consider the free group \(F\) on 6 generators

> F<u,v,w,x,y,z> := FreeGroup(6);

Run in calculator

and the sequence of words

> rels := [ (u*v)^42, (v,x), (x*z^2)^4,
>           v^2*y^3, (v*z)^3, y^4, (x*z)^3 ];

Run in calculator

The abelianised relation matrix of the quotient

\[\langle u,v,w,x,y,z \;\;|\;\; (uv)^{42}, (v,x), (xz^2)^4, v^2y^3, (vz)^3, y^4, (xz)^3 \rangle\]

can be obtained using the following construction

> R := Matrix(Integers(),
>        [ [ Weight(r, F.j) : j in [1..6] ] : r in rels ]);
> R;
[42 42  0  0  0  0]
[ 0  0  0  0  0  0]
[ 0  0  0  4  0  8]
[ 0  2  0  0  3  0]
[ 0  3  0  0  0  3]
[ 0  0  0  0  4  0]
[ 0  0  0  3  0  3]

Run in calculator

(The function Matrix constructs a matrix from a sequence of row vectors.)

Arithmetic Operators for Words#

Suppose \(G\) is an fp-group for which generators have already been defined. This subsection defines the elementary arithmetic operations on words that are derived from the multiplication and inversion operators. The availability of the operators defined here enables the user to construct an element (word) of \(G\) in terms of the generators as follows:

(i): A generator is a word;
(ii): The expression \((u)\) is a word, where \(u\) is a word;
(iii): The product \(u*v\) of the words \(u\) and \(v\) is a word;
(iv): The conjugate \(u^v\) of the word \(u\) by the word \(v\), is a word (\(u^v\) expands into the word \(v^{-1}*u*v\));
(v): The power of a word, \(u^n\), where \(u\) is a word and \(n\) is an integer, is a word;
(vi): The commutator \((u, v)\) of the words \(u\) and \(v\) is a word (\((u, v)\) expands into the word \(u^{-1}*v^{-1}*u*v\)). Note that \((u, v, w)\) is equivalent to \(((u, v), w)\), i.e. commutators are left-normed.

The word operations defined here may be applied either to the words of a free group or the words of a group with non-trivial relations. If such an operator is applied to a group possessing non-trivial relations, only free reduction will be applied to the resulting words.

u * v: GrpFPElt, GrpFPElt -> GrpFPElt#: Given words \(u\) and \(v\) belonging to the same fp-group \(G\), return the product of \(u\) and \(v\).

u ^ n: GrpFPElt, RngIntElt -> GrpFPElt#: The \(n\)-th power of the word \(u\), where \(n\) is an integer. When invoked with \(n = {-1}\), the function computes the inverse of \(u\). When invoked with \(n = 0\), the function returns the identity element.

u ^ v: GrpFPElt, GrpFPElt -> GrpFPElt#: Given words \(u\) and \(v\) belonging to the same fp-group \(G\), return the conjugate \(v^{-1}*u*v\) of the word \(u\) by the word \(v\).

(u, v): GrpFPElt, GrpFPElt -> GrpFPElt#: Given words \(u\) and \(v\) belonging to the same fp-group \(G\), return the commutator \(u^{-1}v^{-1}uv\) of the words \(u\) and \(v\).

(u₁, ..., uₙ): List(GrpFPElt) -> GrpFPElt#: Given the \(n\) words \(u_1, \ldots, u_n\) belonging to the same fp-group \(G\), return their commutator. Commutators are left-normed, so that they are evaluated from left to right.

Comparison of Words#

Words in an fp-group may be compared both for equality and for their relationship with respect to a natural lexicographic ordering. It should be noted that even when a pair of words belong to a group defined by non-trivial relations, only the free reductions of the words are compared. Thus, a pair of words belonging to a group \(G\) may be declared to be distinct even though they may represent the same element of \(G\). The words of an fp-group \(G\) are ordered first by length and then lexicographically. The lexicographic ordering is determined by the following ordering on the generators and their inverses:

\[G.1 < G.1^{-1} < G.2 < G.2^{-1} < \cdots\]

Here, \(u\) and \(v\) are words belonging to some common fp-group.

u eq v: GrpFPElt, GrpFPElt -> BoolElt#: Return true if the free reductions of the words \(u\) and \(v\) are identical.

u ne v: GrpFPElt, GrpFPElt -> BoolElt#: Return true if the free reductions of the words \(u\) and \(v\) are not identical.

u lt v: GrpFPElt, GrpFPElt -> BoolElt#: Return true if the word \(u\) precedes the word \(v\), with respect to the ordering defined above for elements of an fp-group. The words \(u\) and \(v\) are freely reduced before the comparison is made.

u le v: GrpFPElt, GrpFPElt -> BoolElt#: Return true if the word \(u\) either precedes, or is equal to, the word \(v\), with respect to the ordering defined above for elements of an fp-group. The words \(u\) and \(v\) are freely reduced before the comparison is made.

u ge v: GrpFPElt, GrpFPElt -> BoolElt#: Return true if the word \(u\) either follows, or is equal to, the word \(v\), with respect to the ordering defined above for elements of an fp-group. The words \(u\) and \(v\) are freely reduced before the comparison is made.

u gt v: GrpFPElt, GrpFPElt -> BoolElt#: Return true if the word \(u\) follows the word \(v\), with respect to the ordering defined above for elements of an fp-group. The words \(u\) and \(v\) are freely reduced before the comparison is made.

Example: Words (ex-65f8bd)#

We construct the free group on three generators and generate a random word \(w\) of length between 4 and 6.

> F<a,b,c> := FreeGroup(3);
>
> w := Random(F, 4, 6);
> w;
b^-1 * a^-1 * b^2 * a^-1

Run in calculator

We print the length of \(w\) and the weight (the exponent sum) of generator \(a\) in \(w\).

> #w;
5
>
> Weight(w, a);
-2

Run in calculator

We now strip the generators from \(w\) one by one, using arithmetic and comparison operators for words and the access function LeadingGenerator.

> while w ne Identity(F) do
>    g := LeadingGenerator(w);
>    print g;
>    w := g^-1 * w;
> end while;
b^-1
a^-1
b
b
a^-1

Run in calculator

String Operations on Words#

The functions described in this section perform low level string operations like substitution, elimination or substring matching on elements of fp-groups.

Eliminate(u, x, v): GrpFPElt, GrpFPElt, GrpFPElt -> GrpFPElt#: Given words \(u\) and \(v\), and a generator \(x\), all belonging to a group \(G\), return the word obtained from \(u\) by replacing each occurrence of \(x\) by \(v\) and each occurrence of \(x^{-1}\) by \(v^{-1}\).

Eliminate(U, x, v): { GrpFPElt }, GrpFPElt, GrpFPElt -> { GrpFPElt }#: Given a set of words \(U\), a word \(v\), and a generator \(x\), all belonging to a group \(G\), return the set of words obtained by taking each element \(u\) of \(U\) in turn, and replacing each occurrence of \(x\) in \(u\) by \(v\) and each occurrence of \(x^{-1}\) by \(v^{-1}\).

Match(u, v, f): GrpFPElt, GrpFPElt, RngIntElt -> BoolElt, RngIntElt#

Suppose \(u\) and \(v\) are words belonging to the same group \(G\), and that \(f\) is an integer such that \(1 \leq f \leq \# u\). The function seeks the least integer \(l\) such that:

(a): \(l\geq f\); and
(b): \(v\) appears as a subword of \(u\), starting at the \(l\)-th letter of \(u\).

If such an integer \(l\) is found Match returns the value true and \(l\). If no such \(l\) is found, Match returns the value false.

RotateWord(u, n): GrpFPElt, RngIntElt -> GrpFPElt#: The word obtained by cyclically permuting the word \(u\) by \(n\) places. If \(n\) is positive, the rotation is from left to right, while if \(n\) is negative the rotation is from right to left. In the case where \(n\) is zero, the function returns \(u\).

Substitute(u, f, n, v): GrpFPElt, RngIntElt, RngIntElt, GrpFPElt -> GrpFPElt#: Given words \(u\) and \(v\) belonging to a group \(G\), and non-negative integers \(f\) and \(n\), this function replaces the substring of \(u\) of length \(n\), starting at position \(f\), by the word \(v\). Thus, if \(u = x_{i_1}^{e_1}\cdots x_{i_f}^{e_f}\cdots x_{i_{f+n-1}}^{e_{f+n-1}}\cdots x_{i_m}^{e_m}\) then the substring \(x_{i_f}^{e_f}\cdots x_{i_{f+n-1}}^{e_{f+n-1}}\) is replaced by \(v\). If the function is invoked with \(v =\) Id(G), then the substring \(x_{i_f}^{e_f}\cdots x_{i_{f+n-1}}^{e_{f+n-1}}\) of \(u\) is deleted.

Subword(u, f, n): GrpFPElt, RngIntElt, RngIntElt -> GrpFPElt#: The subword of the word \(u\) comprising the \(n\) consecutive letters commencing at the \(f\)-th letter of \(u\).

Example: Word Ops (ex-b14d33)#

We demonstrate some of these operations in the context of the free group on generators \(x\), \(y\), and \(z\).

> F<x, y, z> := FreeGroup(3);
> u := (x, y*z);
> w := u^(x^2*y);
> #w;
12
> w;
y^-1 * x^-3 * z^-1 * y^-1 * x * y * z * x^2 * y

Run in calculator

We replace each occurrence of the generator \(x\) in \(w\) by the word \(y*z^-1\).

> Eliminate(w, x, y*z^-1);
y^-1 * z * y^-1 * z * y^-1 * z * y^-1 * z^-2 * y * z * y * z^-1 * y * z^-1 * y

Run in calculator

We count the number of occurrences of each generator in \(w\).

> [ ExponentSum(w, F.i) : i in [1..Ngens(F)] ];
[ 0, 0, 0 ]
> GeneratorNumber(w);
-2

Run in calculator

We locate the start of the word \(u\) in the word \(w\).

> b, p := Match(w, u, 1);
> b, p;
true 4

Run in calculator

We now replace the subword \(u\) in \(w\) by the word \(y*x\).

> t := Substitute(w, p, #u, y*x);
> t;
y^-1 * x^-2 * y * x^3 * y

Run in calculator

We create the set of all distinct cyclic permutations of the word \(u\).

> rots := { RotateWord(u, i) : i in [1 ..#u] };
> rots;
{ y^-1 * x * y * z * x^-1 * z^-1,  x * y * z * x^-1 * z^-1 * y^-1,
x^-1 * z^-1 * y^-1 * x * y * z,  z * x^-1 * z^-1 * y^-1 * x * y,
z^-1 * y^-1 * x * y * z * x^-1,  y * z * x^-1 * z^-1 * y^-1 * x }

Run in calculator