# Construction of an FP-Group 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. ## Introduction 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`](../FreeGroups/creation.md#function-grpfp-1-freegroup)`(n)` which constructs a free group of rank $n$, and [`quo< F | R >`](#constructor-grpfp-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. ## Quotient Group Constructor 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 ‘=’: $w_1 = w_2 = \cdots = w_r$. This is interpreted as the set of relations $w_1 = w_r, \ldots, w_{r - 1} = w_r$. 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 $\phi : F \rightarrow 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`](subgroup-general.md#function-grpfp-setglobaltcparameters). ### `G / H: GrpFP, GrpFP -> GrpFP` 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. ### `Example: Symmetric1 (ex-94ed98)` 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: ```magma > F := FreeGroup(2); > G, phi := quo< F | a^2, b^3, (a*b)^4 >; ``` Alternatively, giving the relations as a relations list, the presentation would be specified as: ```magma > F := FreeGroup(2); > G, 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: ```magma > F := FreeGroup(2); > rels := { a^2, b^3, (a*b)^4 }; > G, phi := quo< F | rels >; ``` ### `Example: Symmetric2 (ex-803aa2)` A group may be defined using the [`quo< F | R >`](#constructor-grpfp-quo)-constructor without first assigning a free group. The $ symbol is used to reference the group whose quotient is being formed. ```magma > S4 := 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) ``` ### `Example: Modular (ex-8457bf)` We illustrate the use of the [`quo< F | R >`](#constructor-grpfp-quo)-constructor in defining the quotient of a group other than a free group. ```magma > F := 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 := 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 ``` ## The FP-Group Constructor 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 $x_1, \ldots, x_r$, and a list of relations $R$ over these generators, first construct the free group $F$ on the generators $x_1, \cdots, x_r$ 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< F | R >`](#constructor-grpfp-quo)-constructor. The function returns: **(a)** The quotient group $G$; **(b)** The natural homomorphism $\phi : F \rightarrow G$. ### `Example: Tetrahedral (ex-388271)` We illustrate the [`FPGroup< X | R >`](#constructor-grpfp-1-confpgroup)-constructor by defining the binary tetrahedral group in terms of the presentation $< r, s \ | \ r^3 = s^3 = (rs)^2 >:$ ```magma > G := FPGroup< r, s | r^3 = s^3 = (r*s)^2 >; ``` ### `Example: Three Invols (ex-cb4daf)` Again, using the [`FPGroup< X | R >`](#constructor-grpfp-1-confpgroup)-constructor, the group $< r, s, t \ | \ r^2, s^2, t^2, rst = str = trs >$ would be specified as: ```magma > G := FPGroup; ``` ### `Example: Coxeter (ex-4c068c)` 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 >. $$ ```magma > Glmnk := func< l, m, n, k | FPGroup< a, b | a^l, b^m, (a*b)^n, (a*b^-1)^k > >; > G := 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 := 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. ## Accessing the Defining Generators and Relations The functions in this group provide access to basic information stored for a finitely-presented group $G$. ### `G . i: GrpFP, RngIntElt -> GrpFPElt` 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$. ### `Generators(G): GrpFP -> { GrpFPElt }` A set containing the generators for the group $G$. ### `NumberOfGenerators(G): GrpFP -> RngIntElt` ### `Ngens(G): GrpFP -> RngIntElt` The number of generators for the group $G$. ### `PresentationLength(G): GrpFP -> RngIntElt` The total length of the relators for $G$. ### `Relations(G): GrpFP -> [ GrpFPRel ]` A sequence containing the defining relations for $G$. ## Operations on Words The functions described in this section perform low level string operations like substitution, elimination or substring matching on elements of fp-groups. ### `Eliminate(u, x, v): GrpFPElt, GrpFPElt, GrpFPElt -> GrpFPElt` 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}$. ### `Eliminate(U, x, v): { GrpFPElt }, GrpFPElt, GrpFPElt -> { GrpFPElt }` 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}$. ### `Match(u, v, f): GrpFPElt, GrpFPElt, RngIntElt -> BoolElt, RngIntElt` Suppose $u$ and $v$ are words belonging to the same group $G$, and that $f$ is an integer such that $1 \leq f \leq \# u$. The function seeks the least integer $l$ such that: **(a)** $l\geq 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`. ### `RotateWord(u, n): GrpFPElt, RngIntElt -> GrpFPElt` 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$. ### `Substitute(u, f, n, v): GrpFPElt, RngIntElt, RngIntElt, GrpFPElt -> GrpFPElt` 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 = x_{i_1}^{e_1}\cdots x_{i_f}^{e_f}\cdots x_{i_{f+n-1}}^{e_{f+n-1}}\cdots x_{i_m}^{e_m}$ then the substring $x_{i_f}^{e_f}\cdots x_{i_{f+n-1}}^{e_{f+n-1}}$ is replaced by $v$. If the function is invoked with $v =$ Id(G), then the substring $x_{i_f}^{e_f}\cdots x_{i_{f+n-1}}^{e_{f+n-1}}$ of $u$ is deleted. ### `Subword(u, f, n): GrpFPElt, RngIntElt, RngIntElt -> GrpFPElt` The subword of the word $u$ comprising the $n$ consecutive letters commencing at the $f$-th letter of $u$. ### `Example: Word Ops (ex-1c9bc2)` We demonstrate some of these operations in the context of the free group on generators $x$, $y$, and $z$. ```magma > F := 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$. ```magma > 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$. ```magma > [ 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$. ```magma > b, p := Match(w, u, 1); > b, p; true 4 ``` We now replace the subword $u$ in $w$ by the word $y*x$. ```magma > 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$. ```magma > 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 } ``` ## Operations on Presentations 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. ### `AddGenerator(G): GrpFP -> GrpFP` Given an fp-group $G$ with presentation $\langle X\ |\ R \rangle$, create a new fp-group with presentation $\langle X \cup \{ z\rbrace\ |\ R \rangle$, where $z$ is a symbol not in $X$. ### `AddGenerator(G, w): GrpFP, GrpFPElt -> GrpFP` Given an fp-group $G$ with presentation $\langle X\ |\ R \rangle$, and given also a word $w$ in the generators $X$, create a new fp-group having the presentation $\langle X\ \cup \{ z\rbrace\ |\ R \cup \{ z = w \rbrace \rangle$, where $z$ is a symbol not in $X$. ### `AddRelation(G, r): GrpFP, RelElt -> GrpFP` 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$. ### `AddRelation(G, g): GrpFP, GrpFPElt -> GrpFP` 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={\rm Id}(G)$. ### `AddRelation(G, r, i): GrpFP, RelElt, RngIntElt -> GrpFP` 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$. ### `AddRelation(G, g, i): GrpFP, GrpFPElt, RngIntElt -> GrpFP` 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={\rm Id}(G)$ inserted after the $i$-th existing relation of $G$. ### `DeleteGenerator(G, x): GrpFP, GrpFPElt -> GrpFP` Given an fp-group $G$ with presentation $\langle X\ |\ R \rangle$, and given also an element $z$ in $X$, create a new fp-group with presentation $\langle X \setminus \{z\}\ |\ R' \rangle$, where the relations $R'$ are obtained from $R$ by deleting all relations containing an occurrence of $z$. ### `DeleteRelation(G, r): GrpFP, RelElt -> GrpFP` 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. ### `DeleteRelation(G, g): GrpFP, GrpFPElt -> GrpFP` Given an fp-group $G$, which includes the relation $g={\rm Id}(G)$ amongst its relations, create a new fp-group which has as its presentation the relations of $G$ with this relation omitted. ### `DeleteRelation(G, i): GrpFP, RngIntElt -> GrpFP` 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, s, r): GrpFP, RelElt, RelElt -> GrpFP` ### `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={\rm 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={\rm 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$. ### `ReplaceRelation(G, i, g): GrpFP, RngIntElt, GrpFPElt -> GrpFP` 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={\rm Id}(G)$. ### `Example: Replace (ex-c80efd)` We use the function [`ReplaceRelation`](#function-grpfp-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. ```magma > G := 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 ```