# Standard Constructions In this section various intrinsics for constructing fp-groups are described. These are familiar groups constructed as fp-groups, extensions of existing fp-groups and the construction of fp-groups from some other type of group. ## Familiar Groups as FP-Groups A number of functions are provided which construct presentations for various standard groups. ### `AbelianFPGroup([n₁,...,nᵣ]): [ RngIntElt ] -> GrpFP` Construct the abelian group defined by the sequence $[n_1,\ldots,n_r]$ of non-negative integers as an fp-group. The function returns the direct product of cyclic groups $C_{n_1} \times C_{n_2} \times \cdots \times C_{n_r}$, where $C_0$ is interpreted as an infinite cyclic group. ### `AlternatingFPGroup(n): RngIntElt -> GrpFP` ### `Alt(GrpFP, n): Cat, RngIntElt -> GrpFP` Construct the alternating group of degree $n$ as an fp-group, where the generators correspond to the permutations $(3,4,\ldots ,n)$ and $(1,2,3)$, for $n$ odd, or $(1,2)(3,4$, $\ldots$, $n)$ and $(1,2,3)$, for $n$ even. ### `BraidFPGroup(n): RngIntElt -> GrpFP` Construct the braid group on $n$ strings ($n-1$ Artin generators) as an fp-group. ### `CoxeterFPGroup(t): MonStgElt -> GrpFP` Construct the Coxeter group of Cartan type $t$ as a finitely presented group, given by the standard Coxeter presentation. The Cartan type $t$ is passed to this function as a string; we refer to Chapter [Root Data](../../LieTheory/RootData/index-root-data.md#chaprootdtm) for details. ### `CyclicFPGroup(n): RngIntElt -> GrpFP` Construct the cyclic group of order $n$ as an fp-group. ### `DihedralFPGroup(n): RngIntElt -> GrpFP` For $n > 2$, return the dihedral group of order $2n$ as an fp-group. For $n=0$, return the infinite dihedral group as an fp-group. ### `ExtraSpecialFPGroup(p, n : parameters): RngIntElt, RngIntElt -> GrpFP` ```magma Type: MonStgElt Default: "+" ``` Given a small prime $p$ and a small positive integer $n$, construct an extra-special group $G$ of order $p^{2n+1}$ in the category `GrpFP`. The isomorphism type of $G$ can be selected using the parameter `Type`. Possible values for this parameter are “$+$” (default) and “$-$“. If `Type` is set to “$+$”, the function returns for $p = 2$ the central product of $n$ copies of the dihedral group of order 8, and for $p > 2$ it returns the unique extra-special group of order $p^{2n+1}$ and exponent $p$. If `Type` is set to “$-$”, the function returns for $p = 2$ the central product of a quaternion group of order 8 and $n-1$ copies of the dihedral group of order 8, and for $p > 2$ it returns the unique extra-special group of order $p^{2n+1}$ and exponent $p^2$. ### `SymmetricFPGroup(n): RngIntElt -> GrpFP` ### `Sym(GrpFP, n): Cat, RngIntElt -> GrpFP` Construct the symmetric group of degree $n$ as an fp-group, where the generators correspond to the permutations $(1,2,\ldots,n)$ and $(1,2)$. ### `Example: Standard Groups (ex-936a87)` We create the symmetric group ${\operatorname{Sym}}(8)$ as an fp-group: ```magma > S8 := SymmetricFPGroup(8); > S8; Finitely presented group S8 on 2 generators Relations S8.1^8 = Id(S8) S8.2^2 = Id(S8) (S8.1 * S8.2)^7 = Id(S8) (S8.1^-1 * S8.2 * S8.1 * S8.2)^3 = Id(S8) (S8.2 * S8.1^-2 * S8.2 * S8.1^2)^2 = Id(S8) (S8.2 * S8.1^-3 * S8.2 * S8.1^3)^2 = Id(S8) (S8.2 * S8.1^-4 * S8.2 * S8.1^4)^2 = Id(S8) % % ``` We create the Coxeter group of Cartan type $F4$ as an fp-group: ```magma > F := CoxeterFPGroup("F4"); > F; Finitely presented group F on 4 generators Relations (F.2 * F.3)^2 = (F.3 * F.2)^2 F.1^2 = Id(F) F.1 * F.3 = F.3 * F.1 F.2 * F.4 = F.4 * F.2 F.1 * F.2 * F.1 = F.2 * F.1 * F.2 F.2^2 = Id(F) F.3^2 = Id(F) F.3 * F.4 * F.3 = F.4 * F.3 * F.4 F.4^2 = Id(F) F.1 * F.4 = F.4 * F.1 %\endcode % %We create the imprimitive complex reflection group $G(4,2,3)$ as an fp-group: %\begincode %> G := ImprimitiveReflectionGroup(GrpFP, 4,2,3); %> G; %Finitely presented group G on 4 generators %Relations % G.4 * G.2 * G.3 = G.2 * G.3 * G.4 % G.3^4 = Id(G) % G.1 * G.2 * G.3 = G.2 * G.3 * G.1 % (G.1 * G.4)^3 = (G.4 * G.1)^3 % G.2^4 = Id(G) % G.2 * G.4 = G.4 * G.2 % G.1^4 = Id(G) % G.3 * G.1 = G.1 * G.2 % G.4^4 = Id(G) % G.3 * G.4 = G.4 * G.3 ``` ## Construction of Extensions ### `Darstellungsgruppe(G): GrpFP -> GrpFP` Given an fp-group $G$, construct a maximal central extension $\tilde G$ of $G$. The group $\tilde G$ is created as an fp-group. ### `DirectProduct(G, H): GrpFP, GrpFP -> GrpFP` Given two fp-groups $G$ and $H$, construct the direct product of $G$ and $H$. ### `DirectProduct(Q): [ GrpFP ] -> GrpFP` Given a sequence $Q$ of $r$ fp-groups, construct the direct product $Q[1] \times \dots \times Q[r]$. ### `FreeProduct(G, H): GrpFP, GrpFP -> GrpFP` Given two fp-groups $G$ and $H$, construct the free product of $G$ and $H$. ### `FreeProduct(Q): [ GrpFP ] -> GrpFP` Given a sequence $Q$ of $r$ fp-groups, construct the free product of the groups $Q[1], \dots, Q[r]$. ### `Example: Control Extn (ex-dc16bb)` We construct a maximal central extension of the following group of order $36$. ```magma > G := FPGroup; > G; Finitely presented group G on 2 generators Relations x1^4 = Id(G) (x1 * x2^-1)^2 = Id(G) x2^4 = Id(G) (x1 * x2)^3 = Id(G) > D := Darstellungsgruppe(G); > D; Finitely presented group D on 4 generators Relations D.1^4 * D.3^-1 * D.4^2 = Id(D) D.1 * D.2^-1 * D.1 * D.2^-1 * D.4 = Id(D) D.2^4 = Id(D) D.1 * D.2 * D.1 * D.2 * D.1 * D.2 * D.4 = Id(D) (D.1, D.3) = Id(D) (D.2, D.3) = Id(D) (D.1, D.4) = Id(D) (D.2, D.4) = Id(D) (D.3, D.4) = Id(D) > Index(D, sub< D | >); 108 ``` Thus, a maximal central extension of $G$ has order $108$ ### `Example: Direct Product (ex-bdaee4)` We create the direct product of the alternating group of degree $5$ and the cyclic group of order $2$. ```magma > A5 := FPGroup; > Z2 := quo< FreeGroup(1) | $.1^2 >; > G := DirectProduct(A5, Z2); > G; Finitely presented group G on 3 generators Relations G.1^2 = Id(G) G.2^3 = Id(G) (G.1 * G.2)^5 = Id(G) G.3^2 = Id(G) G.1 * G.3 = G.3 * G.1 G.2 * G.3 = G.3 * G.2 ``` ## Conversion to FP-Groups In this section we describe intrinsics which given a group in some category other than that of fp-group, return an isomorphic fp-group. ### `FPGroup(G): GrpPerm -> GrpFP, Hom(Grp)` ### `FPGroup(G): GrpMat -> GrpFP, Hom(Grp)` Given a finite group $G$ in category `GrpPerm` or `GrpMat`, this function returns a finitely presented group $F$, isomorphic to $G$, together with the isomorphism $\phi: F\rightarrow G$. The generators of $F$ correspond to the generators of $G$, so this function can be used to obtain a set of defining relations for the given generating set of $G$. It should be noted that this function is only practical for groups of order at most a few million. In the case of much larger permutation groups, an isomorphic fp-group can be constructed using the function [`FPGroupStrong`](#function-grpfp-1-fpgroupstrong). ### `Example: FP Group1 (ex-185d54)` We define the alternating group $G \simeq A_{10}$ as a permutation group. ```magma > G := Alt(10); > G; Permutation group G acting on a set of cardinality 5 Order = 1814400 = 2^7 * 3^4 * 5^2 * 7 (1, 2)(3, 4, 5, 6, 7, 8, 9, 10) (1, 2, 3) ``` Now we create an fp-group $F$ isomorphic to $G$, using the function [`FPGroup`](#function-grpfp-1-fpgroup). The presentation is constructed by computing a set of defining relations for the generators of $G$, i.e. the generators of the returned fp-group correspond to the generators of $G$. This defines a homomorphism from $F$ to $G$, which the function [`FPGroup`](#function-grpfp-1-fpgroup) returns as second return value. ```magma > F, f := FPGroup(G); > F; Finitely presented group F on 2 generators Relations x^8 = Id(F) y^3 = Id(F) (x^-1, y^-1)^2 = Id(F) (x * y^-1 * x^-2 * y^-1 * x)^2 = Id(F) (x * y * x^-3 * y^-1 * x^2)^2 = Id(F) x^-1 * y^-1 * x^-4 * y^-1 * x^4 * y^-1 * x^4 * y^-1 * x^-3 = Id(F) (y^-1 * x^-1)^9 = Id(F) > f; Mapping from: GrpFP: F to GrpPerm: G > f(x); (1, 2)(3, 4, 5, 6, 7, 8, 9, 10) > f(y); (1, 2, 3) ``` Constructing a nice presentation for a large finite permutation group or matrix group is a difficult problem. The next two intrinsics obtain a presentation as a side effect of the Todd-Coxeter-Schreier-Sims algorithm. ### `FPGroupStrong(G): GrpPerm -> GrpFP, Hom(Grp)` ### `FPGroupStrong(G): GrpMat -> GrpFP, Hom(Grp)` Given a finite group $G$ in category `GrpPerm` or `GrpMat`, this function returns a finitely presented group $F$, isomorphic to $G$, together with the isomorphism $\phi:F \rightarrow G$. The generators of $F$ correspond to a set of strong generators of $G$. If no strong generating set is known for $G$, one will be constructed. For a detailed description of this function, in particular for a list of available parameters, we refer to Chapter [Permutation Groups](../../FiniteGroups/PermutationGroups/index-permutation-groups.md#chapgrpperm) and Chapter [Matrix Groups over General Rings](../../FiniteGroups/MatrixGroupsOverGeneralRings/index-matrix-groups-over-general-rings.md#chapgrpmat), respectively. ### `FPGroupStrong(G, N): GrpPerm, GrpPerm -> GrpFP, Hom(Grp)` Given a permutation group $G$ and a normal subgroup $N$ of $G$, this function returns a finitely presented group $F$, isomorphic to $G/N$, together with a homomorphism $\phi:G \rightarrow F$. For a detailed description of this function, we refer to Chapter [Permutation Groups](../../FiniteGroups/PermutationGroups/index-permutation-groups.md#chapgrpperm). ### `Example: FP Group2 (ex-f1a62b)` We take the alternating group $G \simeq A_5$ as a permutation group. ```magma > G := Alt(5); > G; Permutation group G acting on a set of cardinality 5 Order = 60 = 2^2 * 3 * 5 (1, 2)(3, 4, 5, 6, 7, 8, 9, 10) (1, 2, 3) ``` Using the function [`FPGroupStrong`](#function-grpfp-1-fpgroupstrong), we now create an fp-group $Fs$, isomorphic to $G$, whose generators correspond to a set of strong generators of $G$. ```magma > Fs<[z]>, fs := FPGroupStrong(G); > Fs; Finitely presented group Fs on 3 generators Relations z[1]^-3 = Id(Fs) (z[1]^-1 * z[3]^-1)^2 = Id(Fs) z[3]^-3 = Id(Fs) z[1]^-1 * z[2]^-1 * z[1] * z[3]^-1 * z[2] = Id(Fs) z[2]^-3 = Id(Fs) (z[3]^-1 * z[2]^-1)^2 = Id(Fs) > fs; Mapping from: GrpFP: Fs to GrpPerm: G ``` Applying the isomorphism $fs$, we have a look at the strong generating set constructed for $G$. ```magma > [ fs(z[i]) : i in [1..#z] ]; [ (3, 4, 5), (1, 2, 3), (2, 3, 4) ] ``` It should be noted that `FPGroupStrong` constructs a presentation on what is often a much larger generating set and consequently the presentation can be much larger. However, this intrinsic will produce presentations for very large groups as compared to the intrinsic `FPGroup`. It is recommended that the user apply the simplification algorithm (intrinsic `Simplify`) to the presentation returned by `FPGroupStrong`). Groups that satisfy certain properties, such as being abelian or polycyclic, are known to possess presentations with respect to which the word problem is soluble. Specialised categories have been constructed in Magma for several of these, e.g. the categories `GrpGPC`, `GrpPC` and `GrpAb`. The functions described in this section allow a group created in one of the special presentation categories to be recast as an fp-group. ### `FPGroup(G): GrpPC -> GrpFP, Hom(Grp)` ### `FPGroup(G): GrpGPC -> GrpFP, Hom(Grp)` ### `FPGroup(G): GrpAb -> GrpFP, Hom(Grp)` Given a group $G$, defined either by a polycyclic group presentation (types `GrpPC` and `GrpGPC`) or an abelian group presentation (type `GrpAb`), return a group $H$ isomorphic to $G$, together with the isomorphism $\phi:G \rightarrow H$. The generators for $H$ will correspond to the generators of $G$. The effect of this function is to convert a presentation in a special form into a general fp-group presentation. ### `Example: FP Group2 (ex-a91a69)` We illustrate the cast from special forms of fp-groups to the category `GrpFP` by converting a polycyclic group. ```magma > G := DihedralGroup(GrpGPC, 0); > G; GrpGPC : G of infinite order on 2 PC-generators PC-Relations: G.1^2 = Id(G), G.2^G.1 = G.-2 > F := FPGroup(G); > F; Finitely presented group F on 2 generators Relations F.1^2 = Id(F) F.2^F.1 = F.2^-1 F.1^-1 * F.2^-1 * F.1 = F.2 ``` There is a special Magma category `GrpPermCox`, a subcategory of `GrpPerm`, for finite Coxeter groups. Here, we describe a function to create from a Coxeter group $W$ a finitely presented group $F$, isomorphic to $W$, which is given by the standard Coxeter group presentation. We refer to Chapter ChapGrpPermCox for the details. ### `CoxeterFPGroup(W): GrpFPCox -> GrpFP, Map` ### `CoxeterFPGroup(W): GrpPermCox -> GrpFP, Map` ```magma Local: BoolElt Default: false ``` Given a finite Coxeter group $W$ in the category `GrpFPCox` or `GrpPermCox`, construct a finitely presented group $F$ isomorphic to $W$, given by a standard Coxeter presentation. The isomorphism from $W$ to $F$ is returned as second return value. The first argument to this function must be the category `GrpFP`. If the parameter `Local` is set to `true`, $F$ is the appropriate subgroup of the FP version of the overgroup of $W$. ### `Example: FP Coxeter Groups (ex-1b08d9)` We construct a Coxeter group $W$ of Cartan type $C5$ and create an isomorphic fp-group $F$. We can use the isomorphism from $W$ to $F$ to map words in the generators of $F$ to permutation group elements and vice versa. ```magma > W := CoxeterGroup("C5"); > F<[s]>, h := CoxeterFPGroup(W); > F; Finitely presented group F on 5 generators Relations s[3]^2 = Id(F) s[2] * s[4] = s[4] * s[2] s[1]^2 = Id(F) s[1] * s[2] * s[1] = s[2] * s[1] * s[2] s[2] * s[5] = s[5] * s[2] s[4]^2 = Id(F) s[1] * s[3] = s[3] * s[1] s[3] * s[4] * s[3] = s[4] * s[3] * s[4] s[2]^2 = Id(F) s[1] * s[4] = s[4] * s[1] s[5]^2 = Id(F) (s[4] * s[5])^2 = (s[5] * s[4])^2 s[3] * s[5] = s[5] * s[3] s[1] * s[5] = s[5] * s[1] s[2] * s[3] * s[2] = s[3] * s[2] * s[3] > h; Mapping from: GrpCox: W to GrpFP: F given by a rule > h(W.1*W.2); s[1] * s[2] > (s[1]*s[2]*s[3]*s[4]) @@ h; (1, 39, 4, 3, 2)(5, 13, 19, 23, 25)(6, 36, 35, 8, 7)(9, 16, 21, 24, 17)(10, 33, 32, 31, 11)(12, 18, 22, 15, 20)(14, 29, 28, 27, 26)(30, 38, 44, 48, 50)(34, 41, 46, 49, 42)(37, 43, 47, 40, 45) ```