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 described in Subsec. Interactive 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(G, T).

Example: Coset Table1 (ex-ae13a4)#

Consider the infinite dihedral group.

> G<a,b> := DihedralFPGroup(0);
> G;
Finitely presented group G on 2 generators
Relations
    b^2 = Id(G)
    (a * b)^2 = Id(G)

Run in calculator

We define a subgroup \(S\) of \(G\) and compute the coset table map for \(S\) in \(G\).

> S := sub<G|a*b, a^10>;
> 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

Run in calculator

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\)).

> 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)

Run in calculator

Note that the images of \(a\) and \(b\) correspond to the first two columns of the printed coset table above.

> 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

Run in calculator

Now, we define a subgroup of infinite index in \(G\) and compute a coset table for it.

> H := sub<G|b>;
> ct := CosetTable(G, H);

Run in calculator

Of course, the coset table cannot be complete; note that 0 is in its codomain, indicating unknown images of cosets.

> ct;
Mapping from: Cartesian Product<{ 1 .. 1333331 }, GrpFP: G>
        to { 0 .. 1333331 }

Run in calculator

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. For a detailed description of the available parameters and their meanings, we refer to Subsec. Interactive 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{split}\begin{aligned}G =\ <a, b, c, d, e, f, g, h\ |&\ a^2, b^2, c^2, d^2, e^2, f^2, g^2, h^2,\\ &(ab)^3, (ac)^2, (ad)^2, (ae)^4, (af)^2, (ag)^2, (ah)^3,\\ &(bc)^5, (bd)^2, (be)^2, (bf)^2, (bg)^4, (bh)^4,\\ &(cd)^3, (ce)^3, (cf)^4, (cg)^2, (ch)^2,\\ &(de)^2, (df)^3, (dg)^2, (dh)^2,\\ &(ef)^6, (eg)^2, (eh)^2,\\ &(fg)^4, (fh)^6,\\ &(gh)^2,\\ &a(cf)^2 = (adfh)^3 = b(ef)^3 = (baefg)^3 = 1,\\ &(cef)^7 = d(bh)^2 = d(aeh)^3 = e(bg)^2 = 1>\end{aligned}\end{split}\]

under the homomorphism defined by the action of \(G\) on the cosets of the subgroup \(H =\ <a, b, c, d, e, f, g, (adefcefgh)^{39} >.\) The permutation group can be constructed as follows:

> F<s, t, u, v, w, x, y, z> := FreeGroup(8);
> G<a, b, c, d, e, f, g, h> := quo<F | s^2, t^2, u^2, v^2, w^2, x^2, y^2, z^2,
> (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

Run in calculator

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.)

> F<a,b,c,d,y,x,w> := FreeGroup(7);
> z := y*c*a^2*b;
> u := x*d;
> t := w*c*a*d*b^2*c;
> G<a,b,c,d,y,x,w>, 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

Run in calculator

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.

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 described in Subsec. Interactive 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.

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 described in Subsec. Interactive 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.

<i, w> @ 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. For a detailed description of the available parameters and their meanings, we refer to Subsec. Interactive Coset Enumeration.

Example: Coset Table2 (ex-e36cb8)#

Consider the infinite dihedral group.

> G<a,b> := DihedralFPGroup(0);

Run in calculator

We define a subgroup \(H\) of index 10 in \(G\)…

> H := sub< G | a*b, a^10 >;
> Index(G, H);
10

Run in calculator

…and construct a right transversal for \(H\) in \(G\) and the associate transversal map.

> 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

Run in calculator

From this a left transversal is easily obtained:

> 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 @}

Run in calculator

We construct the coset table and check whether the enumeration of the cosets is compatible to the enumeration of the right transversal \(RT\).

> ct := CosetTable(G, H);
> forall(culprit){ i : i in [1..Index(G, H)]
>                    | ct(1, RT[i]) eq i};
true

Run in calculator

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\).

> action := func< r, g | RT[ct(Index(RT, r), g)] >;

Run in calculator

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\).

> action(Id(G), b);
a

Run in calculator

i.e. \(H*b = H*a\).

> action(a^-4, a*b);
a^4

Run in calculator

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\).

> F<x, y> := FreeGroup(2);
> G<a, b> := quo< F | x^8, y^7, (x*y)^2, (x^-1*y)^3 >;
> H := sub< G | a^2,a^-1*b >;

Run in calculator

We construct an indexed right coset space \(V\) and an explicit right coset space \(V\!\!r\) for \(H\) in \(G\).

> V := CosetSpace(G, H);
> Vr := RightCosetSpace(G, H);

Run in calculator

The coset \(H\) always has index 1.

> trivial_coset := ExplicitCoset(Vr, 1);
> trivial_coset;
<GrpFP: H, Id(G)>
> IndexedCoset(V, trivial_coset);
1

Run in calculator

We now pick a coset…

> coset := ExplicitCoset(Vr, 42);
> coset;
<GrpFP: H, a^-1 * b^-1 * a^3 * b^-1>

Run in calculator

…multiply from the right with \(b\)…

> coset * b;
<GrpFP: H, a^-1 * b^-1 * a^3>

Run in calculator

…and check where this gets us in the indexed coset space \(V\).

> IndexedCoset(V, coset * b);
23

Run in calculator

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\).

> 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<G | S>);
>             E := ExcludedConjugates(V);
>             S := S join E;
>         until # E eq 0;
>     return sub<G | S>;
> end function;

Run in calculator

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\).

> function NormClosure(G, hgens)
> xgens := hgens;
> kgens := hgens;
> indx := 0;
> while # xgens ne 0 do
>       Include(~kgens, Representative(xgens));
>       V := CosetSpace(G, sub<G | kgens>);
>       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;

Run in calculator

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. For a detailed description of the available parameters and their meanings, we refer to Subsec. Interactive Coset Enumeration.

Example: Double Cosets (ex-b7c1be)#

Consider again the infinite dihedral group \(G\)…

> G<a,b> := DihedralFPGroup(0);

Run in calculator

…and the subgroup \(H\) of index 10 in \(G\).

> H := sub< G | a*b, a^10 >;

Run in calculator

The set of \(H\)-\(H\) double cosets in \(G\) can be obtained with the statement

> DoubleCosets(G, H, H);
{ <GrpFP: H, Id(G), GrpFP: H>, <GrpFP: H, a^5, GrpFP: H>,
  <GrpFP: H, a^4, GrpFP: H>, <GrpFP: H, a^2, GrpFP: H>,
  <GrpFP: H, a, GrpFP: H>, <GrpFP: H, a^3, GrpFP: H> }

Run in calculator

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 }#

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\).

> G<a,b,c> := BraidFPGroup(4);
> H := sub< G | a,b >;

Run in calculator

We construct an – obviously incomplete – explicit right coset space for \(H\) in \(G\).

> V := RightCosetSpace(G, H);

Run in calculator

Using the function CosetSatisfying, we compute an element of \(G\), not contained in \(H\), which normalises \(H\).

> cs := CosetSatisfying(V, Generators(Subgroup(V))
>                       : Normalizing := true, First := 2);
> cs;
{
    <GrpFP: H, c * b * a^2 * b * c>
}
> rep := c * b * a^2 * b * c;

Run in calculator

The conjugates of \(a\) and \(b\) by this element had better be in \(H\)…

> rep^-1 * a * rep in H;
true
> rep^-1 * b * rep in H;
true

Run in calculator

…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], if necessary together with extended coset enumeration [Arrell and Robertson, 1984, Havas et al., 1984]. We emphasise that if the user wishes only to determine the structure of the maximal abelian quotient of \(H\), then the function AbelianQuotientInvariants should be used. In this case there is no need to first construct a presentation for \(H\) using the Rewrite function described below, since 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#

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. For a detailed description of the available parameters and their meanings, we refer to Subsec. Interactive 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 for an explanation of these parameters.

Rewrite(G, ~H : parameters): GrpFP, GrpFP#

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 described in Subsec. Interactive 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}\).

> G<x, y> := 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> ]

Run in calculator

Example: Rewrite2 (ex-490fe5)#

In this example we illustrate how the function Rewrite 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\).

> F<x,y> := FPGroup< x, y | x^3 = 1, y^3 = 1, (x*y)^4 = 1,
>                         (y*y^x)^2 = y^x*y >;

Run in calculator

The group is also generated by the elements \(a = (xy)^2\) and \(b = y\).

> H<a,b> := sub<F | (x*y)^2, y >;
> Index(F,H);
1

Run in calculator

At the moment, no defining relations of \(H\cong F\) on the generators \(a\) and \(b\) are known.

> 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

Run in calculator

We apply the function Rewrite to \(H\) as a subgroup of \(F\) in order to compute defining relations on the generators \(a\) and \(b\).

> 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)

Run in calculator

The last relation turns out to be redundant; \(a\) and \(b\) are standard generators for \(L_2(7)\).

> Order(DeleteRelation(H,5)) eq Order(H);
true

Run in calculator