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:
is equivalent to the statements
G := E; v1 := G.1; v2 := G.2; ... ; vr := G.r;
> 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.
> 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.
> 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
> 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
> 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:
> 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.
> 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
> 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:
> 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.
> 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)