Let G = < X | R > be a finitely presented group. Suppose that H is a subgroup of G having finite index m. Let V = { c1 (=H), c2, ..., cm } denote the set of distinct right cosets of H in G. This set admits a natural G-action f : V x G -> V where f : < ci, x > = ck iff ci * x = ck, for ci ∈V and x ∈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 ci * 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.
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, ..., r} x G -> {0, ..., 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∈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.
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.
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 -> P;
- (b)
- The permutation group image P;
- (c)
- The kernel K of the action (a subgroup of G).
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).
> 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 }
Given a subgroup H of the group G, this function constructs the permutation representation φ of G given by the action of G on the cosets of H. It returns: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.
- (a)
- The homomorphism φ;
- (b)
- The image group φ(G).
- (c)
- (if possible) the kernel of φ.
Construct the permutation representation L of G given by the action of G on the coset space V. It returns the permutation representation φ (as a map) and its image.
Construct the image of G given by its action on the (right) coset space of H in G.
Construct the image of G as defined by its action on the coset space V.
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.
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).
The first Conway group has a representation as the image of the group
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>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
> 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.
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 ci of H in G. The action of G on this G-set is that induced by the natural G-action f : V x G -> V where f : < ci, x > = ck iff ci * x = ck, for ci ∈V and x ∈G. If certain of the products ci * x are unknown, the corresponding images under f are undefined, and V is called an incomplete coset space for H in G.
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 H78E36.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.
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 H78E36.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.
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).
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.
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.
Return true if element g of group G lies in the coset C.
Return true if element g of group G does not lie in the coset C.
Returns true if the coset C1 is equal to the coset C2.
Returns true if the coset C1 is not equal to the coset C2.
The cardinality of the coset space V.
The mapping V x G -> V giving the action of G on the coset space V. This mapping is a coset table.
The image of coset i as defined in the coset table T, under the action of word w.
The element of the explicit coset space that corresponds to indexed coset i.
The element of the indexed coset space V to which the element w of G corresponds.
The element of the indexed coset space V to which the explicit coset C of G corresponds.
The group G for which V is a coset space.
The subgroup H of G such that V is a coset space for G over H.
Returns true if the coset space V is complete.
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 ={gi - 1hjgi | gi a generator of G, hj a generator of H, and, modulo V, gi - 1hjgi 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.
Given a finitely presented group G and a subgroup H of G, this function returnsThese 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.
- (a)
- A set of elements T of G forming a right transversal for G over H; and
- (b)
- The corresponding transversal mapping φ: G -> T. If T = [t1, ..., tr] and g ∈G, φ is defined by φ(g) = ti, where g∈H * ti.
> 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 x G -> 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); aI.e. H * b = H * a.
> action(a^-4, a*b); a^4I.e. Ha - 4 * (ab) = Ha4.
Consider the group G =< a, b | a8, b7, (ab)2, (a - 1b)3 > and the subgroup H of G, generated by a2 and a - 1b.
> 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 Vr 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); 1We 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
> 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;
> 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;
The double coset H * g * K of the subgroups H and K of the group G, where g is an element of G.
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.
> 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> }
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.
First: RngIntElt Default: 1Start looking for coset representatives satisfying the designated conditions beginning with coset i of V.Last: RngIntElt Default: #VStop looking for coset representatives after examining coset j of V.Limit: RngIntElt Default: ∞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.Normalizing: BoolElt Default: falseIf true, select coset representatives x such that, modulo V, the word x - 1h1x, ..., x1hsx is contained in H.Order: RngIntElt Default: 0Select coset representatives x such that, modulo V, the word xn is contained in H.Print: RngIntElt Default: 0If t > 0, print the coset representatives found to satisfy the designated conditions.
> 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.
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.
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.
Simplify: BoolElt Default: trueIf 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.EliminationLimit: RngIntElt Default: 100ExpandLimit: RngIntElt Default: 150GeneratorsLimit: RngIntElt Default: 0LengthLimit: RngIntElt Default: ∞SaveLimit: RngIntElt Default: 10SearchSimultaneous: RngIntElt Default: 20Iterations: RngIntElt Default: 10000Print: RngIntElt Default: 0These parameters control the simplification. See the description of Simplify for an explanation of these parameters.
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.
Simplify: BoolElt Default: trueIf 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.
> 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> ]
We start with a presentation of L2(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); 1At the moment, no defining relations of H isomorphic to 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 L2(7).
> Order(DeleteRelation(H,5)) eq Order(H); true