|
An fp-group is normally either constructed 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. Additionally,
Magma has separate types for a number of families of fp-groups such
as soluble groups which can be defined by power-conjugate presentations
thus providing a solution to the word problem. Functions are provided
to convert a member of one of these families into a general fp-group.
A finitely presented group G is a quotient group of some free group having
finite rank. The free group of rank n is constructed by the intrinsic
FreeGroup(n). Having constructed an appropriate free group F,
an fp-group G is constructed by specifying relations on the generators of
F that must be satisfied by the corresponding generators
of G. The details of how this is achieved are discussed in the following
sections.
A relation is an equality between two words in an fp-group while
a relator consists of a word that equals the identity, that is,
it is a relation where the right hand side is understood to be the
identity. A presentation is a set of symbols called generators
together with a set of relations on those generators.
To facilitate working with relations, a relation type is provided so
that relations can be treated in a similar way to any other object in
Magma. Below are the three operations that are specific to relations.
Intrinsics:
w1 = w2 : Given words w1 and w2 belonging to fp-group G
create the relation w1 = w2.
LHS(r) : Given a relation r over the generators of G, return the
left hand side of the relation r as a word in G.
RHS(r) : Given a relation r over the generators of G, return the
right hand side of the relation r as a word in G.
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.
Constructors:
quo< F | R > :
Given an fp-group F, and a set R of relations and/or relators 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 constructor returns the quotient group G
and the natural homomorphism φ : F -> G.
G / H : Given a subgroup H of the fp-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.
Notes:
- (i)
- If explicit names are not available, a standard indexing notation
is provided for referencing the generators of any group G. Thus, G.i
denotes the i-th generator of G.
- (ii)
- Individual names may be given to the generators by means of the
generator-assignment syntax. Suppose that the group G is defined on
r generators. Then if E is an expression creating G the special
assignment
G < v1, v2, ..., vr > := E;
is equivalent to the statements
G := E; v1 := G.1; v2 := G.2; ... ; vr := G.r;
Three variations of the constructor are used to define the fp-group G
isomorphic to the symmetric group of degree 4 with presentation
< a, b | a 2, b 3, (ab) 4 >. Note
that as F (the free group) and G (the S 4-quotient) are two distinct
groups it is necessary to have different names for the generators of each.
The relations given in the quo expression are relations on the free
group generators.
> F<a, b> := FreeGroup(2);
> G<x, y>, phi := quo< F | a^2, b^3, (a*b)^4 >;
Finitely presented group G on 2 generators
Relations
x^2 = Id(G)
y^3 = Id(G)
(x * y)^4 = Id(G)
In the next example, the relations are given as a relations list.
> F<a, b> := FreeGroup(2);
> G<x, y>, phi := quo< F | a^2 = b^3 = (a*b)^4 = 1>;
> G;
Finitely presented group G on 2 generators
Relations
x^2 = Id(G)
y^3 = Id(G)
(x * y)^4 = Id(G)
Another alternative is to provide a set of relators:
> F<a, b> := FreeGroup(2);
> rels := { a^2, b^3, (a*b)^4 };
> G<x, y>, phi := quo< F | rels >;
> G;
Finitely presented group G on 2 generators
Relations
x^2 = Id(G)
(x * y)^4 = Id(G)
y^3 = Id(G)
The relations printed out are in a different order than in the set
rels because sets are not ordered. If it is desired to have
the relations appear in some particular order then a sequence should
be used.
A group may be defined using the quo-constructor without first assigning
a free group. The $ symbol is used to reference a group whose quotient is being
formed. Recalling the indexing notation for generators, the generic names
$.1, $.2, etc can be used in this situation.
> 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)
For convenience, a constructor is provided which allows the user to define an
fp-group without explicitly constructing a free group.
Intrinsics:
FPGroup < X | R > :
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 intrinsic returns the quotient group G and the natural homomorphism
φ : F -> G.
The FPGroup-constructor is used to create the binary tetrahedral group
using the presentation
< r, s | r 3 = s 3 = (rs) 2 >:
> G<r, s> := FPGroup< r, s | r^3 = s^3 = (r*s)^2 >;
> G;
Finitely presented group G on 2 generators
Relations
r^3 = (r * s)^2
s^3 = (r * s)^2
Again, using the FPGroup-constructor, the group
< r, s, t | r2, s2, t2, 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>;
> G;
Finitely presented group G on 3 generators
Relations
r^2 = Id(G)
s^2 = Id(G)
t^2 = Id(G)
r * s * t = t * r * s
s * t * r = t * r * s
As shown in this example, the quo-constructor is not
restricted to defining the quotient of 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)
> #G;
10752
In this example Magma functions are used 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.
Intrinsics:
AddGenerator (G) : Add a new generator to the presentation defining G.
AddGenerator (G, w) : Add a new generator z and the relation z = w
to the presentation defining G.
AddRelation (G, r) : Add the relation r to the presentation defining
G.
AddRelation (G, r, i) : Add the relation r after the i-th relation of
the presentation defining G.
DeleteGenerator (G, x) : Delete the generator x and all relations
involving x from the presentation defining G.
ReplaceRelation (G, s, r) : Here each of r and s may be a relation
or a word. The relation r must be part of the presentation for G. The
relation r is replaced by the relation s in the presentation defining G.
DeleteRelation (G, r) : Delete the relation r from the presentation
defining group G.
Generators (G) : The set of generators for G.
NumberOfGenerators (G) : The number of generators used to define G.
PresentationLength (G): The length of the presentation defining G.
The length is defined to be the sum of the lengths of the words defining
each relation or relator.
Simplify(G) : A simplified presentation for G is found
by using Tietze transformations and substring searching. A new group
K defined by the simplified presentation is returned together with
the isomorphism f:G -> K.
SimplifyLength(G) : This has the same effect as Simplify
except that the simplification process terminates when the presentation
length starts to increase. While it may be possible to eliminate further
generators it is likely that this will significantly lengthen the
simplified presentation.
Notes:
- (i)
- : The intrinsic Simplify works by repeatedly eliminating generators
and subsequently shortening relators by substitution of substrings that correspond
to the left or right hand side of a relation. The transformation process
terminates when no more eliminations of generators and no more length reducing
substring replacements are possible. The choice of simplification strategy
can either be left to Magma or selected by the user, The simplification
process can be controlled by a set of parameters described in chapter
FINITELY PRESENTED GROUPS.
Consider the Fibonacci group F(8).
> F<x1, x2, x3, x4, x5, x6, x7, x8> := FreeGroup(8);
> F8<x1, x2, x3, x4, x5, x6, x7, x8> :=
> quo< F | x1*x2=x3, x2*x3=x4, x3*x4=x5, x4*x5=x6,
> x5*x6=x7, x6*x7=x8, x7*x8=x1, x8*x1=x2>;
The intrinsic Simplify will be applied to obtain a presentation
of F(8) on fewer generators. It is returned as the presentation for
a new group H. As the number of generators used in the
simplified presentation for H is unknown it is necessary to use a
variation of the generator assignment expression: H<[y]>. This
will give the generators of H the names y[1], y[2], ....
Here y is any variable name.
> H<[y]>, f := Simplify(F8);
> H;
Finitely presented group H on 2 generators
Generators as words in group F8
y[1] = x3
y[2] = x4
Relations
y[2] * y[1]^-2 * y[2] * y[1]^-1 * y[2]^2 * y[1] * y[2]^2 *
y[1]^-1 = Id(H)
y[1] * y[2] * y[1] * y[2]^2 * y[1] * y[2] * y[1]^2 * y[2]^-1
* y[1] = Id(H)
The isomorphism f can be used to express the old generators in terms of
the new ones.
> f;
Mapping from: GrpFP: F8 to GrpFP: H
> f(x1);
y[1]^2 * y[2]^-1
The words u and v in the intrinsics below must belong to a
common fp-group G.
Intrinsics:
u * v : The product of words u and v.
u - 1 : The inverse of word u.
Identity (G) : The identity element for group G. Other
notations are Id (G) and G!1.
un : The n-th power of u.
uv : The conjugate v - 1 * u * v of words u and v.
(u, v) : The commutator u - 1 * v - 1 * u * v of words u and v.
u eq v : Returns true if the words u and v are identical
when freely reduced. NB When G is not a free group and false
is returned, this does not imply that u and v do not represent the
same element of G.
u ne v : Returns true if the words u and v are distinct
when freely reduced. NB When G is not a free group and true is returned,
this does not imply that u and v do not represent the same element of G.
Intrinsics are provided for constructing presentations for a number
of familiar groups.
Intrinsics:
AbelianFPGroup (Q) : The abelian group defined by the sequence of integers Q.
CyclicFPGroup (n) : The cyclic group of order n.
AlternatingFPGroup (n) : The alternating group of degree n on two generators.
BraidFPGroup (n) : The braid group on n strings on n - 1 Artin generators.
DihedralFPGroup (n) : For n > 2, the dihedral group of order 2n on two generators.
SymmetricFPGroup(n) : The symmetric group of degree n on two generators.
An abelian group is presented as a direct product of cyclic groups. This direct
product is defined by a sequence of integers giving the orders of the cyclic
factors, where 0 indicates Z. To illustrate this the code below constructs the
abelian group Z 4 x Z 9 x Z.
> A<a, b, c> := AbelianFPGroup([4, 9, 0]);
> A;
Finitely presented group A on 3 generators
Relations
a^4 = Id(A)
b^9 = Id(A)
a * b = b * a
a * c = c * a
b * c = c * b
In this example the symmetric group Sym(8) is constructed as an fp-group:-
> S8<x, y> := SymmetricFPGroup(8);
> S8;
Finitely presented group S8 on 2 generators
Relations
x^8 = Id(S8)
y^2 = Id(S8)
(x * y)^7 = Id(S8)
(x^-1 * y * x * y)^3 = Id(S8)
(y * x^-2 * y * x^2)^2 = Id(S8)
(y * x^-3 * y * x^3)^2 = Id(S8)
(y * x^-4 * y * x^4)^2 = Id(S8)
Intrinsics are provided to construct products of fp-groups and also to
to transform groups defined by various types of polycyclic presentations
into fp-groups. In addition there are intrinsics which construct a
presentation for a finite permutation or matrix group G and return a
fp-group isomorphic to G.
Intrinsics:
DirectProduct (G, H) : The direct product of the fp-groups G and H.
FreeProduct (G, H) : The free product of the fp-groups G and H.
FPGroup (T) : If T is a finite nilpotent or soluble group defined
by a polycyclic presentation return an fp-group G isomorphic to T together
with the isomorphism φ: T -> G.
FPGroup (T) : If T is a finite permutation or matrix group of
moderate size then return an fp-group G isomorphic to T together with
the isomorphism φ: G -> T.
FPGroupStrong (T) : If T is a finite permutation or matrix group
which may have order much greater than a million return an fp-group G
isomorphic to T. While FPGroup returns a presentation on the
permutation/matrix generators, FPGroupStrong constructs a presentation
on a larger set of generators (strong generators for T). An
isomorphism φ: G -> T is also returned.
Notes:
- (i)
- : Note that the intrinsic FPGroup applied to permutation or
matrix groups may need to construct the coset table of G over the identity
and hence is limited to groups of order less than a million. The exact limit
is determined by the amount of memory available.
The direct product and free product of the alternating group of degree 7 and
the cyclic group of order 2 are created as follows:-
> A7<a, b> := AlternatingFPGroup(7);
> A7;
Finitely presented group A7 on 2 generators
Relations
a^5 = Id(A7)
b^3 = Id(A7)
(a * b)^7 = Id(A7)
(b * a^-1 * b * a)^2 = Id(A7)
(b * a^-2 * b * a^2)^2 = Id(A7)
> Z2<c> := CyclicFPGroup(2);
Finitely presented group Z2 on 1 generator
Relations
c^2 = Id(Z2)
> G<x, y, z> := DirectProduct(A7, Z2);
> G;
Finitely presented group G on 3 generators
Relations
x^5 = Id(G)
y^3 = Id(G)
(x * y)^7 = Id(G)
(y * x^-1 * y * x)^2 = Id(G)
(y * x^-2 * y * x^2)^2 = Id(G)
z^2 = Id(G)
x * z = z * x
y * z = z * y
> H<x, y, z> := FreeProduct(A7, Z2);
> H;
Finitely presented group H on 3 generators
Relations
x^5 = Id(H)
y^3 = Id(H)
(x * y)^7 = Id(H)
(y * x^-1 * y * x)^2 = Id(H)
(y * x^-2 * y * x^2)^2 = Id(H)
z^2 = Id(H)
Note that the free product is always an infinite group.
In this example, an fp-group G that is isomorphic to GL(3, 4) of order
181440 is created.
> k<u> := GF(4);
> T := GL(3, k); #T;
181440
> T;
MatrixGroup(3, GF(2^2)) of order 2^6 * 3^4 * 5 * 7
Generators:
[ u 0 0]
[ 0 1 0]
[ 0 0 1]
[ 1 0 1]
[ 1 0 0]
[ 0 1 0]
> G<x, y> := FPGroup(T);
> G;
Finitely presented group G on 2 generators
Relations
x^3 = Id(G)
y^7 = Id(G)
(x, y)^3 = Id(G)
(x*y^-1*x^-1*y^2)^3 = Id(G)
x^-1*y*x^-1*y^-1*x^-1*y*x^-1*y^-1*x*y*x*y^-1*x*y*x*y^-1 = Id(G)
y^-1*x^-1*y*x^-1*y^-1*x*y^-1*x^-1*y^-1*x*y*x*y^-1*x*y^3*x^-1 = Id(G)
(y^-1*x^-1*y^-1*x*y^-2)^3 = Id(G)
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|