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, ..., 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< v1, ... vn > := FreeGroup(n);
> F := FreeGroup(2);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);defines F to be the free group of rank 2 and assigns the names x and y to the two generators.
The operations in this section apply to both, free groups and arbitrary fp-groups.
Given a group G defined on r generators and a sequence [i1, ..., is] of integers lying in the range [ - r, r], excluding 0, construct the word G.|i1|ε1 * G.|i2|ε2 * ... * G.|is|εs where εj is +1 if ij is positive, and -1 if ij is negative.
Construct the identity element, represented as the empty word, for the fp-group G. For a sample application of this function, see Example H76E3.
A random word of length l in the generators of the group G, where m ≤l ≤n. For a sample application of this function, see Example H76E3.
This section describes some basic access functions for words. These operations apply to both, free groups and arbitrary fp-groups.
The length of the word w.
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.i1e1 ... G.imem, with each ei equalling plus or minus 1, then Q[j] = ij if ej = + 1 and Q[j] = - ij if ej = (-1), for j = 1, ..., m.
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 H76E3.
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.
Suppose w is a word belonging to a group G. If w = xε * w', w' a word in G, x a generator of G and ε∈{-1, + 1}, the functions returns xε. If w= Identity(G), it returns Identity(G). For a sample application of this function, see Example H76E3.
The parent group G of the word w.
> F<u,v,w,x,y,z> := FreeGroup(6);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 ];The abelianised relation matrix of the quotient < u, v, w, x, y, z | (uv)42, (v, x), (xz2)4, v2y3, (vz)3, y4, (xz)3 > 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](The function Matrix constructs a matrix from a sequence of row vectors.)
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:
Given words u and v belonging to the same fp-group G, return the product of u and v.
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.
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.
Given words u and v belonging to the same fp-group G, return the commutator u - 1v - 1uv of the words u and v.
Given the n words u1, ..., un belonging to the same fp-group G, return their commutator. Commutators are left-normed, so that they are evaluated from left to right.
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 < ... Here, u and v are words belonging to some common fp-group.
Return true if the free reductions of the words u and v are identical.
Return true if the free reductions of the words u and v are not identical.
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.
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.
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.
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.
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^-1We print the length of w and the weight (the exponent sum) of generator a in w.
> #w; 5 > > Weight(w, a); -2We 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
The functions described in this section perform low level string operations like substitution, elimination or substring matching on elements of fp-groups.
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.
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.
Suppose u and v are words belonging to the same group G, and that f is an integer such that 1 ≤f ≤# u. The function seeks the least integer l such that: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.
- (a)
- l≥f; and
- (b)
- v appears as a subword of u, starting at the l-th letter of u.
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.
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 = xi1e1 ... xifef ... x_(if + n - 1)ef + n - 1 ... ximem then the substring xifef ... x_(if + n - 1)ef + n - 1 is replaced by v. If the function is invoked with v = Id(G), then the substring xifef ... x_(if + n - 1)ef + n - 1 of u is deleted.
The subword of the word u comprising the n consecutive letters commencing at the f-th letter of u.
> 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 * yWe 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 * yWe count the number of occurrences of each generator in w.
> [ ExponentSum(w, F.i) : i in [1..Ngens(F)] ]; [ 0, 0, 0 ] > GeneratorNumber(w); -2We locate the start of the word u in the word w.
> b, p := Match(w, u, 1); > b, p; true 4We 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 * yWe 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 }