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 Table in the Infinite Dihedral Group (ex-ae13a4)

Run in calculator (opens in a new tab)

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)

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

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)

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

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

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 (opens in a new tab)

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: Induced Homomorphism for Co1 (ex-a27ede)

Run in calculator (opens in a new tab)

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 (opens in a new tab)

Example: Permutation Representation of G2(3) (ex-6d4ee4)

Run in calculator (opens in a new tab)

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

Thus, the images of a, b, c, and d in G1 generate the Sylow \(2\)-subgroup.

Run in calculator (opens in a new tab)

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 Working with a 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 Working with a 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: Accessing a Coset Table (ex-e36cb8)

Run in calculator (opens in a new tab)

Consider the infinite dihedral group.

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

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

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

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

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

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

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

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

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

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

i.e. \(Ha^{-4}*(ab) = Ha^4\).

Run in calculator (opens in a new tab)

Example: Working with a Coset Space (ex-886b74)

Run in calculator (opens in a new tab)

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

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

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

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

We now pick a coset…

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

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

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

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

> IndexedCoset(V, coset * b);
23

Run in calculator (opens in a new tab)

Example: Derived Subgroup via Coset Enumeration (ex-13317b)

Run in calculator (opens in a new tab)

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 (opens in a new tab)

Example: Adding Excluded Conjugates (ex-8d212e)

Run in calculator (opens in a new tab)

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 (opens in a new tab)

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 in the Infinite Dihedral Group (ex-b7c1be)

Run in calculator (opens in a new tab)

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

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

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

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

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 (opens in a new tab)

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: Selecting Cosets by a Condition (ex-c086e8)

Run in calculator (opens in a new tab)

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

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

> V := RightCosetSpace(G, H);

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;

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

…OK.

Run in calculator (opens in a new tab)

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 [MKS76], if necessary together with extended coset enumeration [AR84, HKRR84]. 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: Presentation for an Index 3 Subgroup (ex-e234d8)

Run in calculator (opens in a new tab)

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 (opens in a new tab)

Example: Presentation on New Generators (ex-490fe5)

Run in calculator (opens in a new tab)

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

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

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

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)

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 (opens in a new tab)

On this page