|
|
|
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, ..., 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);
The statement
> 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.
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
H78E3.
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
H78E3.
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.
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.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.
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
H78E3.
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
H78E3.
The parent group G of the word w.
Consider the free group F on 6 generators
> 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), (xz 2) 4, v 2y 3, (vz) 3, y 4, (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:
- (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 uv of the word u by the word v, is a word
(uv expands into the word v - 1 * u * v);
- (v)
- The power of a word, un, 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.
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.
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
We print the length of w and the weight (the exponent sum) of generator
a in w.
> #w;
5
>
> Weight(w, a);
-2
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
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:
- (a)
- l≥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.
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.
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
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
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
We locate the start of the word u in the word w.
> b, p := Match(w, u, 1);
> b, p;
true 4
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
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 }
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|
|