Let G = < X | R > be a finitely presented group. Suppose that H is a subgroup of G having finite index m. Let V = { c_1 (=H), c_2, ..., c_m } 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 : < c_i, x > = c_k iff 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.
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 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. The parameters are:
Compact: RngIntElt Default: 20The percentage of space that must be available before a compaction will be done. (Default is 20 per cent.)
CosetLimit: RngIntElt Default: ?
Workspace: RngIntElt Default: 200000If CosetLimit is set, then the coset table may have at most n rows, where n is a positive integer. In other words, a maximum of n cosets can be defined at any instant during the enumeration. On the other hand, the total number of cosets defined during the enumeration may considerably exceed n.
If CosetLimit is not set, and Workspace is set, then m is the maximum number of words to use for the coset table and other data structures. The maximum number of rows is then the number that will fit into the workspace. Default is to use 200, 000 words.
FillFactor: RngIntElt Default: Floor((5*(c+2))/4)Coset table style only. The parameter FillFactor allows the user to specify the fill fraction (see Havas (1991)) which is the reciprocal of FillFactor. Default is Floor((5 * (c + 2))/4), where c is the number of columns in the coset table.
Grain: RngIntElt Default: 10000If the parameter Print is set higher than 1, Grain controls how often printing occurs. Default is to print every 10000 cosets.
Hard: BoolElt Default: falseThis parameter indicates whether the user considers the particular coset enumeration to be easy or difficult. Such terms are relative, but a rule of thumb is that overflow would not be expected for easy enumerations.
If this is set to be false (Default), then it is assumed that the enumeration will be straightforward, and will proceed using the relator table style of processing. It will switch to the coset table style if overflow occurs.
If the parameter is set to be true, then the enumeration is assumed to be more difficult, and the coset table style will be used from the outset.
Print: RngIntElt Default: 0If n > 0, a line is printed out whenever the number of active cosets is a multiple of n, and various other messages are printed. If n = 0 (Default), nothing is printed.
Strategy: <RngIntElt, RngIntElt> Default: <0, 0>This parameter is useful when neither of the default (easy and hard) strategies produce good results, and the mix of strategies needs to be tuned carefully. The two components of Strategy are called CTFactor and RTFactor.
The integer CTFactor is the number of relators to be processed in coset table style before switching to relator table style. This is similar to the Felsch algorithm.
The integer RTFactor is the number of relators to be processed in relator table style. This is similar to the HLT algorithm.
Setting CTFactor to a positive value and RTFactor to zero gives a coset table style enumeration. Setting CTFactor to zero and RTFactor to a positive value gives a relator table style enumeration. Setting both non-zero results in a mixed style enumeration.
As a guide, the default for "easy" enumerations is both CTFactor and RTFactor zero, which means that the enumeration begins with relator table style until the maximum allowed number of cosets have been defined. It then switches to a coset table style of enumeration. The default for "hard" enumerations is to set CTFactor to 1000 and RTFactor to 1.
SubgroupRelations: RngIntElt Default: 0The parameter SubgroupRelations allows the user to specify that some or all of the group defining relators are to completely traced at coset 1 before the enumeration proper begins. This is equivalent to treating these relations as additional subgroup generators. The value r assigned to SubgroupRelations is interpreted as follows:
r < 0: Do not trace the relators at coset 1;
r = 0: Trace all relators at coset 1 (Default);
r > 0: Trace the first r relators at coset 1.
Time: RngIntElt Default: InfinityThe enumeration is to terminate if it has not completed after executing for n seconds, where n is a positive integer. Default is infinite time.
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:
- The homomorphism f: G -> P;
- The permutation group image P;
- 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).
The (right) indexed 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 x G -> V where f : < c_i, x > = c_k iff 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.
Using the parameters described below, the user can select the strategy which appears best for the problem at hand.
Compact: RngIntElt Default: 20The percentage of space that must be available before a compaction will be done. (Default is 20 per cent.)
CosetLimit: RngIntElt Default: ?
Workspace: RngIntElt Default: 200000If CosetLimit is set, then the coset table may have at most n rows, where n is a positive integer. In other words, a maximum of n cosets can be defined at any instant during the enumeration. On the other hand, the total number of cosets defined during the enumeration may considerably exceed n.
If CosetLimit is not set, and Workspace is set, then m is the maximum number of words to use for the coset table and other data structures. The maximum number of rows is then the number that will fit into the workspace. Default is to use 200, 000 words.
FillFactor: RngIntElt Default: Floor((5*(c+2))/4)Coset table style only. The parameter FillFactor allows the user to specify the fill fraction (see Havas (1991)) which is the reciprocal of FillFactor. Default is Floor((5 * (c + 2))/4), where c is the number of columns in the coset table.
Grain: RngIntElt Default: 10000If the parameter Print is set higher than 1, Grain controls how often printing occurs. Default is to print every 10000 cosets.
Hard: BoolElt Default: falseThis parameter indicates whether the user considers the particular coset enumeration to be easy or difficult. Such terms are relative, but a rule of thumb is that overflow would not be expected for easy enumerations.
If this is set to be false (Default), then it is assumed that the enumeration will be straightforward, and will proceed using the relator table style of processing. It will switch to the coset table style if overflow occurs.
If the parameter is set to be true, then the enumeration is assumed to be more difficult, and the coset table style will be used from the outset.
Print: RngIntElt Default: 0If n > 0, a line is printed out whenever the number of active cosets is a multiple of n, and various other messages are printed. If n = 0 (Default), nothing is printed.
Strategy: <RngIntElt, RngIntElt> Default: <0, 0>This parameter is useful when neither of the default (easy and hard) strategies produce good results, and the mix of strategies needs to be tuned carefully. The two components of Strategy are called CTFactor and RTFactor.
The integer CTFactor is the number of relators to be processed in coset table style before switching to relator table style. This is similar to the Felsch algorithm.
The integer RTFactor is the number of relators to be processed in relator table style. This is similar to the HLT algorithm.
Setting CTFactor to a positive value and RTFactor to zero gives a coset table style enumeration. Setting CTFactor to zero and RTFactor to a positive value gives a relator table style enumeration. Setting both non-zero results in a mixed style enumeration.
As a guide, the default for "easy" enumerations is both CTFactor and RTFactor zero, which means that the enumeration begins with relator table style until the maximum allowed number of cosets have been defined. It then switches to a coset table style of enumeration. The default for "hard" enumerations is to set CTFactor to 1000 and RTFactor to 1.
SubgroupRelations: RngIntElt Default: 0The parameter SubgroupRelations allows the user to specify that some or all of the group defining relators are to completely traced at coset 1 before the enumeration proper begins. This is equivalent to treating these relations as additional subgroup generators. The value r assigned to SubgroupRelations is interpreted as follows:
r < 0: Do not trace the relators at coset 1;
r = 0: Trace all relators at coset 1 (Default);
r > 0: Trace the first r relators at coset 1.
Time: RngIntElt Default: InfinityThe enumeration is to terminate if it has not completed after executing for n seconds, where n is a positive integer. Default is infinite time.
The indexed coset space for G corresponding to the permutation representation f of G, where f is a homomorphism of G onto a transitive permutation group.
The indexed coset space obtained from the coset space V by forcing cosets i and j to be equal.
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. The parameters described for the CosetSpace function may also be used with these functions.
> 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>;
> V := CosetSpace(G, H: Print := 1);
Fill Factor = 7, CT Factor = 0, RT Factor = 0
Index = 448, Max = 2176, Total = 2626, Time = 0.180000 seconds
> #V;
448
> H := sub<G | a^2,a^-1*b>;
> V := CosetSpace(G, H: Hard := true, Print := 1);
Fill Factor = 7, CT Factor = 1000, RT Factor = 1
Index = 448, Max = 861, Total = 877, Time = 0.150000 seconds
> #V;
448
We see that by setting Hard true, the maximum number of cosets
defined at any one time has dropped from 2176 to 861.
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 space.
The image of coset i as defined in the coset table T, under the action of word w.
The carrier set for the coset space V.
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.
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 ={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.
Given a finitely presented group G and a subgroup H of G, this function returns
- A set of elements T of G forming a right transversal for G over H; and
- The corresponding transversal mapping phi: G -> T. If T = [t_1, ..., t_r] and g in G, phi is defined by phi(g) = t_i, where g in H * t_i.
> 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;
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.
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.
True if element g of group G lies in the coset C.
True if element g of group G does not lie in the coset C.
True if the coset C1 is equal to the coset C2.
True if the coset C1 is not equal to the coset C2.
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 = i: RngIntElt Default: 1Start looking for coset representatives satisfying the designated conditions beginning with coset i of V.
Last = j: RngIntElt Default: #VStop looking for coset representatives after examining coset j of V.
Limit = l: RngIntElt Default: InfinityTerminate 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 at 1 for this function.
Normalizing: BoolElt Default: falseIf true, select coset representatives x such that, modulo V, the word x^(-1)h_1x, ..., x_1h_sx is contained in H.
Order = n: RngIntElt Default: 0Select coset representatives x such that, modulo V, the word x^n is contained in H.
Print = t: RngIntElt Default: 0If t > 0, print the coset representatives found to satisfy the designated conditions.
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: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.
- The homomorphism phi;
- The image group phi(G).
- (if possible) the kernel of phi.
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.
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).
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).
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