# Coset Spaces and Tables Let $G = < X | R >$ be a finitely presented group. Suppose that $H$ is a subgroup of $G$ having finite index $m$. Let $V = \lbrace c_1 (=H), c_2, \ldots, c_m \rbrace$ denote the set of distinct right cosets of $H$ in $G$. This set admits a natural $G$-action $f : V \times G \rightarrow V$ where $$ f : < c_i, x > = c_k \quad\iff\quad c_i*x = c_k, $$ for $c_i \in V$ and $x \in G$. The set $V$ together with this action is a $G$-set called a *right coset space* for $H$ in $G$. The action may also be represented using a coset table $T$. If certain of the products $c_i*x$ are unknown, the corresponding images under $f$ are undefined. In this case, $T$ is not closed, and $V$ is called an *incomplete coset space* for $H$ in $G$. ## Coset Tables A coset table is represented in Magma as a mapping. Given a finitely-presented group $G$ and a subgroup $H$, the corresponding (right) coset table is a mapping $f:\{1,\ldots,r\}\times G\rightarrow \{0,\ldots,r\}$, where $r$ is the index of $H$ in $G$. $f(i,x)$ is the coset to which coset $i$ is mapped under the action of $x\in G$. The value 0 is only included in the codomain if the coset table is not closed, and it denotes that the coset is not known. ### `CosetTable(G, H: parameters): GrpFP, GrpFP -> Map` The (right) coset table for $G$ over subgroup $H$, constructed by means of the Todd-Coxeter procedure. If the coset table does not close then the codomain will include the value 0. Experienced users can control the Todd-Coxeter procedure invoked by this function with a wide range of parameters. This function accepts the same parameters as the function [`CosetEnumerationProcess`](subgroup-general.md#function-grpfp-cosetenumerationprocess) described in Subsec. [Interactive Coset Enumeration](subgroup-general.md#coset-enumeration). ### `CosetTableToRepresentation(G, T): GrpFP, Map -> Map, GrpPerm, Grp` Given a coset table $T$ for a subgroup $H$ of $G$, construct the permutation representation of $G$ given by its action on the cosets of $H$, using the columns of $T$. The function returns: **(a)** The homomorphism $f: G \rightarrow P$; **(b)** The permutation group image $P$; **(c)** The kernel $K$ of the action (a subgroup of $G$). ### `CosetTableToPermutationGroup(G, T): GrpFP, Map -> GrpPerm` Given a coset table $T$ for a subgroup $H$ of $G$, construct the permutation group image of $G$ given by its action on the cosets of $H$, using the columns of $T$. This is the second return value of [`CosetTableToRepresentation`](#function-grpfp-1-cosettabletorepresentation)`(G, T)`. ### `Example: Coset Table1 (ex-ae13a4)` Consider the infinite dihedral group. ```magma > G := DihedralFPGroup(0); > G; Finitely presented group G on 2 generators Relations b^2 = Id(G) (a * b)^2 = Id(G) ``` We define a subgroup $S$ of $G$ and compute the coset table map for $S$ in $G$. ```magma > S := sub; > ct := CosetTable(G, S); > ct; Mapping from: Cartesian Product<{ 1 .. 10 }, GrpFP: G> to { 1 .. 10 } $1 $2 -$1 1. 2 2 3 2. 4 1 1 3. 1 4 5 4. 6 3 2 5. 3 6 7 6. 8 5 4 7. 5 8 9 8. 10 7 6 9. 7 10 10 10. 9 9 8 ``` When printing the coset table, the action of the generators and of the non-trivial inverses of generators on the enumerated transversal is shown in table form. Using the coset table, we now construct the permutation representation of $G$ on the cosets of $S$ in $G$. We assign the representation (a homomorphism), the image (a permutation group of degree $[G:S] = 10$) and the kernel of the permutation representation (a subgroup of $G$). ```magma > fP, P, K := CosetTableToRepresentation(G, ct); > fP; Homomorphism of GrpFP: G into GrpPerm: P, Degree 10, Order 2^2 * 5 induced by a |--> (1, 2, 4, 6, 8, 10, 9, 7, 5, 3) b |--> (1, 2)(3, 4)(5, 6)(7, 8)(9, 10) ``` Note that the images of $a$ and $b$ correspond to the first two columns of the printed coset table above. ```magma > P; Permutation group P acting on a set of cardinality 10 Order = 20 = 2^2 * 5 (1, 2, 4, 6, 8, 10, 9, 7, 5, 3) (1, 2)(3, 4)(5, 6)(7, 8)(9, 10) > K; Finitely presented group K Index in group G is 20 = 2^2 * 5 Subgroup of group G defined by coset table ``` Now, we define a subgroup of infinite index in $G$ and compute a coset table for it. ```magma > H := sub; > ct := CosetTable(G, H); ``` Of course, the coset table cannot be complete; note that 0 is in its codomain, indicating unknown images of cosets. ```magma > ct; Mapping from: Cartesian Product<{ 1 .. 1333331 }, GrpFP: G> to { 0 .. 1333331 } ``` ## Coset Spaces: Induced Homomorphism ### `CosetAction(G, H): Grp, Grp -> Hom(Grp), GrpPerm, Grp` Given a subgroup $H$ of the group $G$, this function constructs the permutation representation $\phi$ of $G$ given by the action of $G$ on the cosets of $H$. It returns: **(a)** The homomorphism $\phi$; **(b)** The image group $\phi(G)$. **(c)** (if possible) the kernel of $\phi$. The permutation representation is obtained by using the Todd-Coxeter procedure to construct the coset table for $H$ in $G$. Note that $G$ may be an infinite group: it is only necessary that the index of $H$ in $G$ be finite. ### `CosetAction(V): GrpFPCos -> Hom(Grp), GrpPerm` Construct the permutation representation $L$ of $G$ given by the action of $G$ on the coset space $V$. It returns the permutation representation $\phi$ (as a map) and its image. ### `CosetImage(G, H): Grp, Grp -> GrpPerm` Construct the image of $G$ given by its action on the (right) coset space of $H$ in $G$. ### `CosetImage(V): GrpFPCos -> GrpPerm` Construct the image of $G$ as defined by its action on the coset space $V$. ### `CosetKernel(G, H): GrpFP, GrpFP -> GrpFP` The kernel of $G$ in its action on the (right) coset space of $H$ in $G$. (Only available when the index of $H$ in $G$ is very small). 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). For a detailed description of the available parameters and their meanings, we refer to Subsec. [Interactive Coset Enumeration](subgroup-general.md#coset-enumeration). ### `CosetKernel(V): GrpFPCos -> GrpFP` The kernel of $G$ in its action on the (right) coset space $V$. (Only available when the index of the subgroup $H$ of $G$ defining the coset space is very small). ### `Example: Co1 (ex-a27ede)` The first Conway group has a representation as the image of the group $$ \begin{aligned}G =\ \end{aligned} $$ under the homomorphism defined by the action of $G$ on the cosets of the subgroup $H =\ .$ The permutation group can be constructed as follows: ```magma > F := FreeGroup(8); > G := quo (s*t)^3, (s*u)^2, (s*v)^2, (s*w)^4, (s*x)^2, (s*y)^2, (s*z)^3, > (t*u)^5, (t*v)^2, (t*w)^2, (t*x)^2, (t*y)^4, (t*z)^4, > (u*v)^3, (u*w)^3, (u*x)^4, (u*y)^2, (u*z)^2, > (v*w)^2, (v*x)^3, (v*y)^2, (v*z)^2, > (w*x)^6, (w*y)^2, (w*z)^2, > (x*y)^4, (x*z)^6, > (y*z)^2, > s*(u*x)^2 = (s*v*x*z)^3 = t*(w*x)^3 = (t*s*w*x*y)^3 = 1, > (u*w*x)^7 = v*(t*z)^2 = v*(s*w*z)^3 = w*(t*y)^2 = 1>; > H := sub< G | a, b, c, d, e, f, g, (a*d*e*f*c*e*f*g*h)^39 >; > V := CosetSpace(G, H: FillFactor := 100000); > Co1 := CosetImage(V); > Degree(Co1); 98280 ``` ### `Example: G23 (ex-6d4ee4)` The group $G_2(3)$ is a homomorph of the fp-group $G$ defined below. We construct a permutation representation $G1$ for $G_2(3)$ on $351$ points, and then compute the subgroup generated by the images of the first four generators of $G$ in $G1$. (The functions applied to permutation groups are described in Chapter [Permutation Groups](../../FiniteGroups/PermutationGroups/index-permutation-groups.md#chapgrpperm).) ```magma > F := FreeGroup(7); > z := y*c*a^2*b; > u := x*d; > t := w*c*a*d*b^2*c; > G, g := > quo< F | a^4, b^4, c^2, d^2, (a,b), (a*c)^2, (b*c)^2, > (c*d)^2, d*a*d*b^-1, y^3, (a^-1*b)^y*d*a^-1*b^-1, > (c*d*a^-1*b)^y*b^-1*a*d*c, a*d*y*d*a^-1*y, x^3, > a^x*b^-1, b^x*a*b, c^x*c, (x*d)^2, (u*z)^6, w^3, > (w,y), (a*b)^w*b^-1*a*d*c, (c*d*a^-1*b)^w*d*c*b^2, > (b^2*c*d)^w*a^-1*b^-1, (c*a^2*b*w)^2, > (a^-1*b)^w*d*a^-1*b^-1, (t*u)^3 >; > z1 := g(z); > u1 := g(u); > t1 := g(t); > H := sub< G | z1*a^2*b^2, u1*c, t1*a^2*b^2 >; > f, G1, K := CosetAction(G, H); > Degree(G1); 351 > print Order(G1), FactoredOrder(G1); 4245696 [ <2, 6>, <3, 6>, <7, 1>, <13, 1> ] > CompositionFactors(G1); G | G(2, 3) 1 > S := sub< G1 | f(a), f(b), f(c), f(d) >; > BSGS(S); > S; Permutation group S of degree 351 Order = 64 = 2^6 ``` Thus, the images of a, b, c and d in G1 generate the Sylow $2$-subgroup. ## Coset Spaces: Construction The indexed (right) coset space $V$ of the subgroup $H$ of the group $G$ is a $G$-set consisting of the set of integers $\{ 1, ..., m\}$, where $i$ represents the right coset $c_i$ of $H$ in $G$. The action of $G$ on this $G$-set is that induced by the natural $G$-action $$ f : V \times G \rightarrow V $$ where $$ f : < c_i, x > = c_k \quad\iff\quad c_i*x = c_k, $$ for $c_i \in V$ and $x \in G$. If certain of the products $c_i*x$ are unknown, the corresponding images under $f$ are undefined, and $V$ is called an *incomplete coset space* for $H$ in $G$. ### `CosetSpace(G, H: parameters): GrpFP, GrpFP -> GrpFPCos` This function attempts to construct a coset space for the subgroup $H$ in the group $G$ by means of the Todd-Coxeter procedure. If the enumeration fails to complete, the function returns an incomplete coset space. The coset space is returned as an indexed right coset space. For a sample application of this function see Example [Example: Coset Space](#example-ex-886b74). Experienced users can control the Todd-Coxeter procedure invoked by this function with a wide range of parameters. This function accepts the same parameters as the function [`CosetEnumerationProcess`](subgroup-general.md#function-grpfp-cosetenumerationprocess) described in Subsec. [Interactive Coset Enumeration](subgroup-general.md#coset-enumeration). ### `RightCosetSpace(G, H: parameters): GrpFP, GrpFP -> GrpFPCos` ### `LeftCosetSpace(G, H: parameters): GrpFP, GrpFP -> GrpFPCos` The explicit right coset space of the subgroup $H$ of the group $G$ is a $G$-set containing the set of right cosets of $H$ in $G$. The elements of this $G$-set are the pairs $< H, x >$, where $x$ runs through a transversal for $H$ in $G$. Similarly, the explicit left coset space of $H$ is a $G$-set containing the set of left cosets of $H$ in $G$, represented as the pairs $< x, H >$. These functions use the Todd-Coxeter procedure to construct the explicit right (left) coset space of the subgroup $H$ of the group $G$. For a sample application see Example [Example: Coset Space](#example-ex-886b74). Experienced users can control the Todd-Coxeter procedure invoked by these functions with a wide range of parameters. Both functions accept the same parameters as the function [`CosetEnumerationProcess`](subgroup-general.md#function-grpfp-cosetenumerationprocess) described in Subsec. [Interactive Coset Enumeration](subgroup-general.md#coset-enumeration). ## Coset Spaces: Elementary Operations ### `H * g: GrpFP, GrpFPElt -> GrpFPCosElt` Right coset of the subgroup $H$ of the group $G$, where $g$ is an element of $G$ (as an element of the right coset of $H$). ### `C * g: GrpFPCosElt, GrpFPElt -> GrpFPCosElt` Coset to which the right coset $C$ of the group $G$ is mapped by the (right) action of $g$, where $g$ is an element of $G$. ### `C * D: GrpFPCosElt, GrpFPCosElt -> GrpFPCosElt` Given two right cosets of the same normal subgroup $H$ of the group $G$, return the right coset that is the product of $C$ and $D$. ### `g in C: GrpFPElt, GrpFPCosElt -> BoolElt` Return `true` if element $g$ of group $G$ lies in the coset $C$. ### `g notin C: GrpFPElt, GrpFPCosElt -> BoolElt` Return `true` if element $g$ of group $G$ does not lie in the coset $C$. ### `C1 eq C2: GrpFPCosElt, GrpFPCosElt -> BoolElt` Returns `true` if the coset $C1$ is equal to the coset $C2$. ### `C1 ne C2: GrpFPCosElt, GrpFPCosElt -> BoolElt` Returns `true` if the coset $C1$ is not equal to the coset $C2$. ## Accessing Information ### `# V: GrpFPCos -> RngIntElt` The cardinality of the coset space $V$. ### `Action(V): GrpFPCos -> Map` The mapping $V \times G \rightarrow V$ giving the action of $G$ on the coset space $V$. This mapping is a coset table. ### ` @ T: GrpFPCosElt, GrpFPElt, Map -> GrpFPElt` ### `T(i, w): Map, GrpFPCosElt, GrpFPElt -> GrpFPElt` The image of coset $i$ as defined in the coset table $T$, under the action of word $w$. ### `ExplicitCoset(V, i): GrpFPCos, RngIntElt -> GrpFPCosElt` The element of the explicit coset space that corresponds to indexed coset $i$. ### `IndexedCoset(V, w): GrpFPCos, GrpFPElt -> GrpFPCosElt` The element of the indexed coset space $V$ to which the element $w$ of $G$ corresponds. ### `IndexedCoset(V, C): GrpFPCos, GrpFPCosElt -> GrpFPCosElt` The element of the indexed coset space $V$ to which the explicit coset $C$ of $G$ corresponds. ### `Group(V): GrpFPCos -> GrpFP` The group $G$ for which $V$ is a coset space. ### `Subgroup(V): GrpFPCos -> GrpFP` The subgroup $H$ of $G$ such that $V$ is a coset space for $G$ over $H$. ### `IsComplete(V): GrpFPCos -> BoolElt` Returns `true` if the coset space $V$ is complete. ### `ExcludedConjugates(V): GrpFPCos -> { GrpFPElt }` ### `ExcludedConjugates(T): Map -> { GrpFPElt }` Given a partial or complete coset space $V$ for the group $G$ over the subgroup $H$, or a coset table $T$ corresponding to this coset space, this function returns the set of words $E =\{g_i^{-1}h_jg_i\ |\ g_i$ a generator of $G$, $h_j$ a generator of $H$, and, modulo $V$, $g_i^{-1}h_jg_i$ does not lie in $H\}$. If $E$ is empty, then $H$ is a normal subgroup of $G$, while if $E$ is non-empty, the addition of the elements of $E$ to the generators of $H$ will usually be a larger subgroup of the normal closure of $H$. This function may be used with incomplete coset spaces for $G$ over $H$; it may then happen that some of the elements of $E$ actually lie in $H$ but there is insufficient information for this to be detected. This function is normally used in conjunction with the Todd-Coxeter algorithm when seeking some subgroup having index sufficiently small so that the Todd-Coxeter procedure completes. The conjugates are returned as a set of words. ### `Transversal(G, H): GrpFP, GrpFP -> { @ GrpFPElt @}, Map` ### `RightTransversal(G, H): GrpFP, GrpFP -> { @ GrpFPElt @}, Map` Given a finitely presented group $G$ and a subgroup $H$ of $G$, this function returns **(a)** A set of elements $T$ of $G$ forming a right transversal for $G$ over $H$; and **(b)** The corresponding transversal mapping $\phi: G \rightarrow T$. If $T = [t_1, \ldots, t_r]$ and $g \in G$, $\phi$ is defined by $\phi(g) = t_i$, where $g\in H*t_i$. These functions 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). For a detailed description of the available parameters and their meanings, we refer to Subsec. [Interactive Coset Enumeration](subgroup-general.md#coset-enumeration). ### `Example: Coset Table2 (ex-e36cb8)` Consider the infinite dihedral group. ```magma > G := DihedralFPGroup(0); ``` We define a subgroup $H$ of index 10 in $G$… ```magma > H := sub< G | a*b, a^10 >; > Index(G, H); 10 ``` …and construct a right transversal for $H$ in $G$ and the associate transversal map. ```magma > RT, transmap := Transversal(G, H); > RT; {@ Id(G), a, a^-1, a^2, a^-2, a^3, a^-3, a^4, a^-4, a^5 @} > transmap; Mapping from: GrpFP: G to SetIndx: RT ``` From this a left transversal is easily obtained: ```magma > LT := {@ x^-1 : x in RT @}; > LT; {@ Id(G), a^-1, a, a^-2, a^2, a^-3, a^3, a^-4, a^4, a^-5 @} ``` We construct the coset table and check whether the enumeration of the cosets is compatible to the enumeration of the right transversal $RT$. ```magma > ct := CosetTable(G, H); > forall(culprit){ i : i in [1..Index(G, H)] > | ct(1, RT[i]) eq i}; true ``` It is. Thus, we can very easily define a function $RT\times G \rightarrow RT$, describing the action of $G$ on the set of right cosets of $H$ in $G$. ```magma > action := func< r, g | RT[ct(Index(RT, r), g)] >; ``` Note that the definition of the function `action` relies on the fact that the computed right transversal and its enumeration match the ones internally used for the coset table $ct$. ```magma > action(Id(G), b); a ``` i.e. $H*b = H*a$. ```magma > action(a^-4, a*b); a^4 ``` i.e. $Ha^{-4}*(ab) = Ha^4$. ### `Example: Coset Space (ex-886b74)` Consider the group $G =< a, b\ |\ a^8, b^7, (ab)^2, (a^{-1}b)^3 >$ and the subgroup $H$ of $G$, generated by $a^2$ and $a^{-1}b$. ```magma > F := FreeGroup(2); > G := quo< F | x^8, y^7, (x*y)^2, (x^-1*y)^3 >; > H := sub< G | a^2,a^-1*b >; ``` We construct an indexed right coset space $V$ and an explicit right coset space $V\!\!r$ for $H$ in $G$. ```magma > V := CosetSpace(G, H); > Vr := RightCosetSpace(G, H); ``` The coset $H$ always has index 1. ```magma > trivial_coset := ExplicitCoset(Vr, 1); > trivial_coset; > IndexedCoset(V, trivial_coset); 1 ``` We now pick a coset… ```magma > coset := ExplicitCoset(Vr, 42); > coset; ``` …multiply from the right with $b$… ```magma > coset * b; ``` …and check where this gets us in the indexed coset space $V$. ```magma > IndexedCoset(V, coset * b); 23 ``` ### `Example: Der Sub (ex-13317b)` We present a function which computes the derived subgroup $G'$ for the finitely presented group $G$. It assumes that the Todd-Coxeter procedure can enumerate the coset space of $G'$ in $G$. ```magma > function DerSub(G) > > /* Initially define S to contain the commutator of each pair of distinct > generators of G */ > > S := { (x,y) : x, y in Generators(G) | (x,y) ne Id(G) }; > > /* successively extend S until it is closed under conjugation by the > generators of G */ > > repeat > V := CosetSpace(G, sub); > E := ExcludedConjugates(V); > S := S join E; > until # E eq 0; > return sub; > end function; ``` ### `Example: Excluded Conjugates (ex-8d212e)` Given a subgroup $H$ of the finitely presented group $G$, for which the Todd-Coxeter procedure does not complete, add excluded conjugates one at a time to the generators of $G$ until a subgroup $K$ is reached such that either $K$ is normal in $G$, or $K$ has sufficiently small index for the Todd-Coxeter method to complete. The set $hgens$ contains a set of generating words for $H$. ```magma > function NormClosure(G, hgens) > xgens := hgens; > kgens := hgens; > indx := 0; > while # xgens ne 0 do > Include(~kgens, Representative(xgens)); > V := CosetSpace(G, sub); > if IsComplete(V) then break; end if; > xgens := ExcludedConjugates(V); > end while; > if IsComplete(V) then > print "The subgroup generated by", kgens, "has index", #V; > return kgens; > else > print "The construction was unsuccessful"; > return {}; > end if; > end function; ``` ## Double Coset Spaces: Construction ### `DoubleCoset(G, H, g, K): GrpFP, GrpFP, GrpFPElt, GrpFP -> GrpFPDcosElt` The double coset $H*g*K$ of the subgroups $H$ and $K$ of the group $G$, where $g$ is an element of $G$. ### `DoubleCosets(G, H, K): GrpFP, GrpFP, GrpFP -> { GrpFPDcosElt }` Set of double cosets $H*g*K$ of the group $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). For a detailed description of the available parameters and their meanings, we refer to Subsec. [Interactive Coset Enumeration](subgroup-general.md#coset-enumeration). ### `Example: Double Cosets (ex-b7c1be)` Consider again the infinite dihedral group $G$… ```magma > G := DihedralFPGroup(0); ``` …and the subgroup $H$ of index 10 in $G$. ```magma > H := sub< G | a*b, a^10 >; ``` The set of $H$-$H$ double cosets in $G$ can be obtained with the statement ```magma > DoubleCosets(G, H, H); { , , , , , } ``` ## Coset Spaces: Selection of Cosets ### `CosetsSatisfying(T, S: parameters): Map, { GrpFPElt } -> { GrpFPCosElt }` ### `CosetSatisfying(T, S: parameters): Map, { GrpFPElt } -> { GrpFPCosElt }` ### `CosetsSatisfying(V, S: parameters): GrpFPCos, { GrpFPElt } -> { GrpFPCosElt }` ### `CosetSatisfying(V, S: parameters): GrpFPCos, { GrpFPElt } -> { GrpFPCosElt }` ```magma First : RngIntElt Default: 1 Last : RngIntElt Default: ＃V Limit : RngIntElt Default: Infinity() Normalizing: BoolElt Default: false Order : RngIntElt Default: 0 Print : RngIntElt Default: 0 ``` Given a fp-group $G$, and a partial or complete coset space $V$ or coset table $T$ for $G$ over the subgroup $H$ generated by the set of words $S$, these functions return representatives for the cosets of $V$ which satisfy the conditions defined in the parameters. In the description of the parameters below, the symbol $l$ will denote a Boolean value, while the symbol $n$ will denote a positive integer in the range [1, #$V$]. The functions are not identical. `CosetsSatisfying` returns a set of coset representatives for $V$ as defined in the parameters. `CosetSatisfying` is the same as `CosetsSatisfying` with the `Limit` parameter equal to 1; thus it returns a set containing a single coset representative, or an empty set if no cosets satisfy the conditions. Start looking for coset representatives satisfying the designated conditions beginning with coset $i$ of $V$. Stop looking for coset representatives after examining coset $j$ of $V$. Terminate the search for coset representatives as soon as $l$ have been found which satisfy the designated conditions. This parameter is not available for `CosetSatisfying`, since `Limit` is set to 1 for this function. If `true`, select coset representatives $x$ such that, modulo $V$, the word $x^{-1}h_1x$, $\ldots$, $x_1h_sx$ is contained in $H$. Select coset representatives $x$ such that, modulo $V$, the word $x^n$ is contained in $H$. If $t > 0$, print the coset representatives found to satisfy the designated conditions. ### `Example: Coset Satisfying (ex-c086e8)` Consider the braid group $G$ on 4 strings with Artin generators $a$, $b$ and $c$ and the subgroup $H$ of $G$ generated by $a$ and $b$. ```magma > G := BraidFPGroup(4); > H := sub< G | a,b >; ``` We construct an – obviously incomplete – explicit right coset space for $H$ in $G$. ```magma > V := RightCosetSpace(G, H); ``` Using the function [`CosetSatisfying`](#function-grpfp-1-cosetsatisfying), we compute an element of $G$, not contained in $H$, which normalises $H$. ```magma > cs := CosetSatisfying(V, Generators(Subgroup(V)) > : Normalizing := true, First := 2); > cs; { } > rep := c * b * a^2 * b * c; ``` The conjugates of $a$ and $b$ by this element had better be in $H$… ```magma > rep^-1 * a * rep in H; true > rep^-1 * b * rep in H; true ``` …OK. ## Constructing a Presentation for a Subgroup Let $H$ be a subgroup of finite index in the finitely presented group $G$. It frequently happens that it is desirable to construct a set of defining relations for $H$ from those of $G$. Such a presentation can be obtained either on a set of Schreier generators for $H$ or on the given generators of $H$ using the Reidemeister-Schreier rewriting technique [[Magnus *et al.*, 1976](../../references.md#cite-magnus-cgt)], if necessary together with extended coset enumeration [[Arrell and Robertson, 1984](../../references.md#cite-extended-tc), [Havas *et al.*, 1984](../../references.md#cite-havas-tietze)]. We emphasise that if the user wishes only to determine the structure of the maximal abelian quotient of $H$, then the function [`AbelianQuotientInvariants`](quotient.md#function-grpfp-1-abelianquotientinvariants) should be used. In this case there is no need to first construct a presentation for $H$ using the [`Rewrite`](#function-grpfp-1-rewrite) function described below, since [`AbelianQuotientInvariants`](quotient.md#function-grpfp-1-abelianquotientinvariants) employs a special form of the Reidemeister-Schreier rewriting process which abelianises each relator as soon as it is constructed. Thus, compared to the function `Rewrite`, the function `AbelianQuotientInvariants` can be applied to subgroups of much larger index. ### `Rewrite(G, H : parameters): GrpFP, GrpFP -> GrpFP, Map` ```magma Simplify : BoolElt Default: true EliminationLimit : RngIntElt Default: 100 ExpandLimit : RngIntElt Default: 150 GeneratorsLimit : RngIntElt Default: 0 LengthLimit : RngIntElt Default: Infinity() SaveLimit : RngIntElt Default: 10 SearchSimultaneous: RngIntElt Default: 20 Iterations : RngIntElt Default: 10000 Print : RngIntElt Default: 0 ``` Given a finitely presented group $G$ and a subgroup $H$ having finite index in $G$, return a group $R$ isomorphic to $H$ with a presentation on (some of) the Schreier generators of $H$ in $G$. The group $R$ will be created as a subgroup of $G$ and defining relations of $R$ on its generators will be available. Note that the generators of $R$ will, in general, not correspond to the generators of $H$. The isomorphism from $H$ onto $R$ is returned as second return value. 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). For a detailed description of the available parameters and their meanings, we refer to Subsec. [Interactive Coset Enumeration](subgroup-general.md#coset-enumeration). If this Boolean-valued parameter is given the value `true`, then the resulting presentation for $H$ will be simplified (default). The function `Rewrite` returns a finitely presented group that is isomorphic to $H$. If simplification is requested (by setting `Simplify := true`) then the simplification procedures are invoked (see next section). These procedures perform a sequence of Tietze transformations which typically result in a considerable simplification of the presentation produced by the rewriting process. Alternatively, the user can set `Simplify := false` and then perform the simplification directly if desired. (See next section). If simplification is not requested as part of `Rewrite`, a small amount of simplification is performed on the presentation before it is returned. These parameters control the simplification. See the description of [`Simplify`](simplification.md#function-grpfp-1-simplify) for an explanation of these parameters. ### `Rewrite(G, ~H : parameters): GrpFP, GrpFP` ```magma Simplify: BoolElt Default: true ``` Given a finitely presented group $G$ and a subgroup $H$ having finite index in $G$, compute a defining set of relations for $H$ on the existing generators, using extended coset enumeration and Reidemeister-Schreier rewriting, and change the presentation of $H$ accordingly. If the computation is successful, defining relations for $H$ on its generators will be available at the end; any previously computed relations of $H$ will be discarded. If the computation is unsuccessful, $H$ is not changed. In any case, both the isomorphism type of $H$ and its embedding into $G$ as a subgroup is preserved by this function. If this parameter is given the value `true` (default), then an attempt will be made to simplify the constructed set of relations by substring searches, that is, Tietze transformations not changing any generators. The generating set of $H$ is not modified by this process. Moreover, the extended coset enumeration can be controlled by a wide range of parameters. The function `Rewrite` – in addition to the parameter `Simplify` – accepts the same parameters as the function [`CosetEnumerationProcess`](subgroup-general.md#function-grpfp-cosetenumerationprocess) described in Subsec. [Interactive Coset Enumeration](subgroup-general.md#coset-enumeration). ### `Example: Rewrite (ex-e234d8)` Starting with the group $G$ defined by $$ < x, y\ |\ x^2, y^3, (xy)^{12}, (xy)^6(xy^{-1})^6 >, $$ we construct a subgroup $K$ of index $3$ generated by the words $x$, $yxy^{-1}$ and $yxy^{-1}xy^{-1}xy$. We present the subgroup $K$, compute its abelian quotient structure and then show that the class $30$ 2-quotient of $K$ has order $2^{62}$. ```magma > G := FPGroup< x, y | x^2, y^3, (x*y)^12, (x*y)^6*(x*y^-1)^6 >; > G; Finitely presented group G on 2 generators Relations x^2 = Id(G) y^3 = Id(G) (x * y)^12 = Id(G) x * y * x * y * x * y * x * y * x * y * x * y * x * y^-1 * x * y^-1 * x * y^-1 * x * y^-1 * x * y^-1 * x * y^-1 = Id(G) > K := sub< G | x, y*x*y^-1, y*x*y^-1*x*y^-1*x*y >; > K; Finitely presented group K on 3 generators Generators as words in group G K.1 = x K.2 = y * x * y^-1 K.3 = y * x * y^-1 * x * y^-1 * x * y > Index(G, K); 3 > T := Rewrite(G, K); > T; Finitely presented group T on 3 generators Generators as words in group G T.1 = x T.2 = y * x * y^-1 T.3 = x^y Relations T.1^2 = Id(T) T.2^2 = Id(T) T.3^2 = Id(T) (T.3 * T.2 * T.1 * T.3 * T.2)^2 = Id(T) (T.1 * T.3 * T.2 * T.1 * T.3)^2 = Id(T) (T.1 * T.2 * T.1 * T.3 * T.2)^2 = Id(T) > AbelianQuotientInvariants(T); [ 2, 2, 2 ] > Q2 := pQuotient(T, 2, 30); > FactoredOrder(Q2); [ <2, 62> ] ``` ### `Example: Rewrite2 (ex-490fe5)` In this example we illustrate how the function [`Rewrite`](#function-grpfp-1-rewrite-var) can be used to obtain a presentation of a finitely presented group on a different set of generators. We start with a presentation of $L_2(7)$ on two generators $x$ and $y$. ```magma > F := FPGroup< x, y | x^3 = 1, y^3 = 1, (x*y)^4 = 1, > (y*y^x)^2 = y^x*y >; ``` The group is also generated by the elements $a = (xy)^2$ and $b = y$. ```magma > H := sub; > Index(F,H); 1 ``` At the moment, no defining relations of $H\cong F$ on the generators $a$ and $b$ are known. ```magma > H; Finitely presented group H on 2 generators Index in group F is 1 Generators as words in group F a = (x * y)^2 b = y ``` We apply the function [`Rewrite`](#function-grpfp-1-rewrite-var) to $H$ as a subgroup of $F$ in order to compute defining relations on the generators $a$ and $b$. ```magma > Rewrite(F, ~H); > H; Finitely presented group H on 2 generators Index in group F is 1 Generators as words in group F a = (x * y)^2 b = y Relations a^2 = Id(H) b^3 = Id(H) (a * b)^7 = Id(H) (a * b^-1 * a * b)^4 = Id(H) (b * a * b^-1 * a * b * a)^4 = Id(H) ``` The last relation turns out to be redundant; $a$ and $b$ are standard generators for $L_2(7)$. ```magma > Order(DeleteRelation(H,5)) eq Order(H); true ```