|
An fp-group is normally constructed either by giving a presentation
in terms of generators and relations or it is defined to be a subgroup
or quotient group of an existing fp-group. However, fp-groups may be
also created from finite permutation and matrix groups. Finally, Magma
has separate types for a number of families of fp-groups that satisfy
a condition such as being polycyclic. Again functions are provided
to convert a member of one of these families into a general fp-group.
The construction of fp-groups utilises the fact that every group is a
quotient of some free group. Thus, two general fp-group constructors
are provided: FreeGroup(n) which constructs a
free group of rank n,
and quo< F | R > which constructs the quotient of
group F by the normal subgroup defined by the relations R.
The naming of generators presents special difficulties since they are
not always used in a consistent manner in the mathematical literature.
A generator name is used in two distinct ways. Firstly, it plays the
role of a variable having as its value a designated generator of
G. Secondly, it appears as the symbol designating the specified
generator whenever elements of the group are output. These two uses
are separated in the Magma semantics.
In Magma, a standard indexing notation is provided for referencing the
generators of any fp-group G. Thus, G.i denotes the i-th generator
of G. However, users may give individual names to the generators
by means of the generator-assignment. Suppose that the group G
is defined on r generators. Then if the right hand side of the following
statement creates a group, the special assignment
> G< v_1, ..., v_r> := construction;
is equivalent to the statements
> G := construction;
> v_1 := G.1;
> ...
> v_r := G.r;
It should be noted that when the fp-group G is created as the quotient
of the group F, any names that the user may have associated with the
generators of F will not be associated with the corresponding
generators of G. If this were allowed, then it would violate the
fundamental principle that every object is viewed as belonging to a
unique structure.
A group with non-trivial relations is constructed as a quotient of an
existing group, usually a free group. For convenience, the necessary
free group may be constructed in-line.
quo< F | R > : GrpFP, List -> GrpFP, Hom(Grp)
Given an fp-group F, and a set of relations R in the generators of F,
construct the quotient G of F by the normal subgroup of F defined by
R. The group G is defined by means of a presentation which consists
of the relations for F (if any), together with the additional relations
defined by the list R.
The expression defining F may be either simply the name of a previously
constructed group, or an expression defining an fp-group.
If R is a list then each term of the list is either a word, a
relation, a relation list or a subgroup of F.
A word is interpreted as a relator.
A relation consists of a pair of words, separated by `='.
(See above.)
A relation list consists of a list of words, where each pair
of adjacent words is separated by `=':
w1 = w2 = ... = wr.
This is interpreted as the set of relations
w1 = wr, ..., wr - 1 = wr.
Note that the relation list construct is only meaningful in the
context of the quo-constructor.
A subgroup H appearing in the list R contributes its generators
to the relation set for G, i.e. each generator of H is interpreted
as a relator for G.
The group F may be referred to by the special symbol $ in any word
appearing to the right of the `|' symbol in the quo-constructor.
Also, in the context of the quo-constructor, the identity element
may be represented by the digit 1.
The function returns:
- (a)
- The quotient group G;
- (b)
- The natural homomorphism φ : F -> G.
This function may require the computation of a coset table. Experienced users
can control the behaviour of a possibly invoked coset enumeration with a set of
global parameters. These global parameters can be changed using the function
SetGlobalTCParameters.
Given a subgroup H of the group G, construct the quotient of G
by the normal closure N of H. The quotient is formed by taking
the presentation for G and including the generating words of H as
additional relators.
The symmetric group of degree 4 may be represented as a
two generator group with presentation
< a, b | a 2, b 3, (ab) 4 >.
Giving the relations as a list of relators, the presentation would be
specified as:
> F<a, b> := FreeGroup(2);
> G<x, y>, phi := quo< F | a^2, b^3, (a*b)^4 >;
Alternatively, giving the relations as a relations list, the
presentation would be specified as:
> F<a, b> := FreeGroup(2);
> G<x, y>, phi := quo< F | a^2 = b^3 = (a*b)^4 = 1>;
Finally, giving the relations in the form of a set of relations, this
presentation would be specified as:
> F<a, b> := FreeGroup(2);
> rels := { a^2, b^3, (a*b)^4 };
> G<x, y>, phi := quo< F | rels >;
A group may be defined using the quo-constructor without
first assigning a free group. The $ symbol is used to reference the group
whose quotient is being formed.
> S4<x, y> := quo< FreeGroup(2) | $.1^2, $.2^3, ($.1*$.2)^4 >;
> S4;
Finitely presented group S4 on 2 generators
Relations
x^2 = Id(S4)
y^3 = Id(S4)
(x * y)^4 = Id(S4)
We illustrate the use of the quo-constructor in defining
the quotient of a group other than a free group.
> F<x, y> := FPGroup< x, y | x^2 = y^3 = (x*y)^7 = 1 >;
> F;
Finitely presented group F on 2 generators
Relations
x^2 = Id(F)
y^3 = Id(F)
(x * y)^7 = Id(F)
> G<a, b> := quo< F | (x, y)^8 >;
> G;
Finitely presented group G on 2 generators
Relations
a^2 = Id(G)
b^3 = Id(G)
(a * b)^7 = Id(G)
(a, b)^8 = Id(G)
> Order(G);
10752
For convenience, a constructor is provided which allows the user to
define an fp-group in a single step.
FPGroup< X | R > : List(Var), List(GrpFPRel) -> GrpFP, Hom(Grp)
Given a list X of variables x1, ..., xr, and a list of relations
R over these generators, first construct the free group F on the
generators x1, ..., xr and then construct the quotient of F
corresponding to the normal subgroup of F defined by the relations R.
The syntax for the relations R is the same as for the
quo-constructor.
The function returns:
- (a)
- The quotient group G;
- (b)
- The natural homomorphism φ : F -> G.
We illustrate the FPGroup-constructor by defining the binary
tetrahedral group in terms of the presentation
< r, s | r 3 = s 3 = (rs) 2 >:
> G<r, s> := FPGroup< r, s | r^3 = s^3 = (r*s)^2 >;
Again, using the FPGroup-constructor, the group
< r, s, t | r 2, s 2, t 2, rst = str = trs > would be specified as:
> G<r, s, t> := FPGroup<r, s, t | r^2, s^2, t^2, r*s*t = s*t*r = t*r*s>;
In our final example we illustrate the use of functions to
represent parametrised families of groups. In the notation of Coxeter,
the symbol (l, m | n, k) denotes the family of groups having presentation
< a, b | a l, b m, (a * b) n, (a * b - 1) k >.
> Glmnk := func< l, m, n, k | FPGroup< a, b | a^l, b^m, (a*b)^n, (a*b^-1)^k > >;
> G<a, b> := Glmnk(3, 3, 4, 4);
> G;
Finitely presented group G on 2 generators
Relations
a^3 = Id(G)
b^3 = Id(G)
(a * b)^4 = Id(G)
(a * b^-1)^4 = Id(G)
> Order(G);
168
> G<a, b> := Glmnk(2, 3, 4, 5);
> G;
Finitely presented group G on 2 generators
Relations
a^2 = Id(G)
b^3 = Id(G)
(a * b)^4 = Id(G)
(a * b^-1)^5 = Id(G)
> Order(G);
1
Thus (2, 3 | 4, 5 ) is the trivial group.
The functions in this group provide access to basic information stored for a
finitely-presented group G.
The i-th defining generator for G. A negative subscript indicates that the
inverse of the generator is to be created. The generator G.0 is Identity(G), the
empty word in G.
A set containing the generators for the group G.
Ngens(G) : GrpFP -> RngIntElt
The number of generators for the group G.
The total length of the relators for G.
A sequence containing the defining relations for G.
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 }
The functions described in this section construct a new fp-group from an
existing one by adding or deleting a generator or by adding, deleting or
changing a relation. The new group is created without any relationship to
the existing group.
Given an fp-group G with presentation < X | R >, create a new fp-group
with presentation < X ∪{ z } | R >,
where z is a symbol not in X.
Given an fp-group G with presentation < X | R >,
and given also a word w in the generators X, create a new fp-group
having the presentation
< X ∪{ z } | R ∪{ z = w } >,
where z is a symbol not in X.
Given an fp-group G, and a relation r on the generators of G, create a
new fp-group whose presentation consists of the relations of G together
with the relation r.
Given an fp-group G, and an element g of G, create a
new fp-group whose presentation consists of the relations of G together
with the relation g=(Id)(G).
Given an fp-group G, and a relation r on the generators of G, create
a new fp-group which has as its presentation the relations of G
together with the relation r inserted after the i-th existing relation
of G.
Given an fp-group G, and an element g of G, create
a new fp-group which has as its presentation the relations of G
together with the relation g=(Id)(G) inserted after the i-th existing relation
of G.
Given an fp-group G with presentation < X | R >, and given also
an element z in X, create a new fp-group with presentation
< X - {z} | R' >, where the relations R' are obtained from R by
deleting all relations containing an occurrence of z.
Given an fp-group G, which includes the relation r amongst its
relations, create a new fp-group which has as its presentation
the relations of G with relation r omitted.
Given an fp-group G, which includes the relation g=(Id)(G) amongst its
relations, create a new fp-group which has as its presentation
the relations of G with this relation omitted.
Given an fp-group G, create a new fp-group which
has as its presentation the relations for G with the i-th relation deleted.
ReplaceRelation(G, h, r) : GrpFP, GrpFPElt, RelElt -> GrpFP
ReplaceRelation(G, s, g) : GrpFP, RelElt, GrpFPElt -> GrpFP
ReplaceRelation(G, h, g) : GrpFP, GrpFPElt, GrpFPElt -> GrpFP
Given an fp-group G, which includes the relation s or h=(Id)(G)
amongst its relations, create a new fp-group which has as its presentation the
relations for G with the relation s replaced by the relation r or g=(Id)(G).
ReplaceRelation(G, i, r) : GrpFP, RngIntElt, RelElt -> GrpFP
Given an fp-group G and a relation r in the generators of G,
create a new fp-group which
has as its presentation the relations for G with relation number i
replaced by the relation r.
Given an fp-group G and an element g of G, create a new fp-group which
has as its presentation the relations for G with relation number i
replaced by the relation g=(Id)(G).
We use the function ReplaceRelation to vary a particular
relation in a presentation. The order of the resulting group together with
the index of a particular subgroup is determined.
> G<x,y,z,h,k,a> := FPGroup< x, y, z, h, k, a |
> x^2, y^2, z^2, (x,y), (y,z), (x,z), h^3, k^3, (h,k),
> (x,k), (y,k), (z,k), x^h*y, y^h*z, z^h*x, a^2, a*x*a*y,
> a*y*a*x, (a,z), (a,k), (a*h)^2 >;
> for i := 0 to 1 do
> for j := 0 to 1 do
> for k := 0 to 1 do
> for l := 0 to 2 do
> rel := G.1^i*G.2^j*G.3^k*G.5^l*(G.6*G.4)^2 = Id(G);
> K := ReplaceRelation(G, 21, rel);
> print Order(K), Index(K, sub< K | K.6, K.4>);
> end for;
> end for;
> end for;
> end for;
<0, 0, 0, 0> 144 24
<0, 0, 0, 1> 144 8
<0, 0, 0, 2> 144 8
<0, 0, 1, 0> 18 3
<0, 0, 1, 1> 18 1
<0, 0, 1, 2> 18 1
<0, 1, 0, 0> 72 3
<0, 1, 0, 1> 72 1
<0, 1, 0, 2> 72 1
<0, 1, 1, 0> 36 6
<0, 1, 1, 1> 36 2
<0, 1, 1, 2> 36 2
<1, 0, 0, 0> 18 3
<1, 0, 0, 1> 18 1
<1, 0, 0, 2> 18 1
<1, 0, 1, 0> 144 6
<1, 0, 1, 1> 144 2
<1, 0, 1, 2> 144 2
<1, 1, 0, 0> 36 6
<1, 1, 0, 1> 36 2
<1, 1, 0, 2> 36 2
<1, 1, 1, 0> 72 12
<1, 1, 1, 1> 72 4
<1, 1, 1, 2> 72 4
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|