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.
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:
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.
- (a)
- The quotient group G;
- (b)
- The natural homomorphism φ : F -> G.
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.
> 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 >;
> 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)
> 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.
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.
> G<r, s> := FPGroup< r, s | r^3 = s^3 = (r*s)^2 >;
> G<r, s, t> := FPGroup<r, s, t | r^2, s^2, t^2, r*s*t = s*t*r = t*r*s>;
> 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.
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: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 }
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.
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).
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).
> 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