Construct the subgroup H of the fp-group G generated by the words specified by the terms of the generator list L = L_1, ..., L_r.A term L_i of the generator list may consist of any of the following objects:
The collection of words and groups specified by the list must all belong to the group G and H will be constructed as a subgroup of G.
- A word;
- A set or sequence of words;
- A sequence of integers representing a word;
- A set or sequence of sequences of integers representing words;
- A subgroup of an fp-group;
- A set or sequence of subgroups.
The generators of H consist of the words specified directly by terms L_i together with the stored generating words for any groups specified by terms of L_i. Repetitions of an element and occurrences of the identity element are removed (unless H is trivial).
If the sub-constructor is invoked with an empty list L, the trivial subgroup will be constructed.
Given a homomorphism f from G onto a transitive subgroup of Sym(n), construct the subgroup of G which affords this permutation representation.
Construct the subgroup N of the fp-group G as the normal closure of the subgroup H generated by the words specified by the terms of the generator list L.The possible forms of a term of the generator list are the same as for the sub-constructor.
This constructor may be applied even when H has infinite index in G, provided that its normal closure N has finite index. The subgroup N is obtained by computing the coset table of the trivial subgroup in the group defined by the relations of G together with relators corresponding to the words generating H.
Given a homomorphism f from G onto a transitive subgroup of Sym(n), construct the subgroup of G that is the normal closure of the subgroup K of G which affords this permutation representation.
> G<a, b> := Group<a, b| a^8, b^7, (a * b)^2, (a^-1 * b)^3>;
> G;
Finitely presented group G on 2 generators
Relations
a^8 = Id(G)
b^7 = Id(G)
(a * b)^2 = Id(G)
> H<x, y> := sub< G | a^2, a^-1 * b >;
> H;
Finitely presented group H on 2 generators
Generators as words in group G
x = a^2
y = a^-1 * b
a -> (2, 4)(3, 5)(6, 7)(8, 9), b -> (1, 2, 3)(4, 6, 7)(5, 8, 9)We construct the subgroup H of G that is the preimage of the stabilizer of the point 1 in G.
> G<a, b> := Group< a, b | a^2, b^3, (a*b)^7, (a, b)^9>; > T := PermutationGroup< 9 | (2, 4)(3, 5)(6, 7)(8, 9), > (1, 2, 3)(4, 6, 7)(5, 8, 9) >; > f := hom< G -> T | a -> T.1, b ->T.2 >; > H := sub< G | f >; > H;Finitely presented group H Subgroup of group G defined by coset table
> Index(G, H); 9 >print GeneratingWords(G, H);
{ a, b^-1 * a * b^3 * a * b, b * a * b * a * b * a * b^-1, b^3, b^-1 * a * b * a * b * a * b, b * a * b^3 * a * b^-1 }
Given a subgroup H of the fp-group G, this function attempts to determine the index of H in G by enumerating the cosets of H using the Todd-Coxeter procedure. In difficult situations the user may elect to exercise some control over the manner in which the enumeration is performed by setting appropriate values for the Todd-Coxeter parameters FillFactor, Hard, Strategy, SubgroupRelations. Note that this operation only requires that generating words for H in G be known: the coset table is calculated by this operation.
The principal value returned by these functions is the index of H in G (or 0, if the enumeration fails to complete). It is returned as a positive integer, except for FactoredIndex, which returns it in the form of a factorization sequence. The other values returned are the coset table, the maximum number of cosets, and the total number of cosets.
The version ToddCoxeter(G, H, n) is a short form of ToddCoxeter(G, H) with the parameter CosetLimit := n.
The Todd-Coxeter implementation installed in Magma was developed by George Havas and Jin Xian Lian at the University of Queensland in 1992. The reader should consult Cannon, Dimino, Havas and Watson (Math. Comp, 1973) and Havas (ISSAC'91) for an explanation of the terminology and a description of the algorithm.
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 permitted 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 200000 words.
The coset limit information may also be given as an argument to ToddCoxeter.
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 be 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 finite fp-group G, this function attempts to determine the order of G by enumerating the cosets of the trivial subgroup in G using the Todd-Coxeter procedure. If the enumeration completes, the order is returned either as a factored integer sequence or as a positive integer. Otherwise, zero is returned. The parameters described for the Index function may also be used with this function.
> 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>;
> Index(G, H);
448
< x, a, b, c, d, e, f, g |
x^2, a^2, b^2, c^2, d^2, e^2, f^2, g^2,
(x,a), (x,g),
(bc)^3, (bd)^2, (be)^2, (bf)^2, (bg)^2,
(cd)^3, (ce)^2, (cf)^2, (cg)^2,
(de)^3, (df)^2, (dg)^2,
(ef)^3, (eg)^2,
(fg)^3,
(b, xbx),
(a, edcb), (a,f)dcbdcd, (ag)^5,
(cdef, xbx), (b, xcdefx), (cdef, xcdefx) >.
The subgroup generated by x, b, c, d, e, f, g has index 1,140,000. In order
to enumerate the cosets of this subgroup, we need to set the parameter
CosetLimit to a value greater than 1,140,000. Setting the parameter
Hard to true results in a much faster enumeration.
> HN<x, a, b, c, d, e, f, g> := > Group< x, a, b, c, d, e, f, g | > x^2, a^2, b^2, c^2, d^2, e^2, f^2, g^2, > (x, a), (x, g), > (b*c)^3, (b*d)^2, (b*e)^2, (b*f)^2, (b*g)^2, > (c*d)^3, (c*e)^2, (c*f)^2, (c*g)^2, > (d*e)^3, (d*f)^2, (d*g)^2, > (e*f)^3, (e*g)^2, > (f*g)^3, > (b, x*b*x), > (a, e*d*c*b), (a, f)*d*c*b*d*c*d, (a*g)^5, > (c*d*e*f, x*b*x), (b, x*c*d*e*f*x), (c*d*e*f, x*c*d*e*f*x) > >; > H := sub<HN | x,b,c,d,e,f,g >; > ind := Index( HN, H: CosetLimit := 1200000, Hard := true, Print := 1 );
Index = 1140000 Max = 1141309 Total = 1470174 Time = 921.542145 seconds
> ind; 1140000
> Grp := func< p, q, r, s | > > Group< x, y, z, h, k, a | > x^2, y^2, z^2, (x,y), (y,z), (x,z), h^3, k^3, (h,k), > (x,k), (y,k), (z,k), x^h*y, y^h*z, z^h*x, a^2, a*x*a*y, > a*y*a*x, (a,z), (a,k), x^p*y^q*z^r*k^s*(a*h)^2 > > >; > > [ < <i,j,k,l>, Order(Grp(i,j,k,l)) > : i, j, k in [0..1], l in [0..2] ]; [ <<0, 0, 0, 0>, 144>, <<0, 0, 0, 1>, 144>, <<0, 0, 0, 2>, 144>, <<0, 0, 1, 0>, 18>, <<0, 0, 1, 1>, 18>, <<0, 0, 1, 2>, 18>, <<0, 1, 0, 0>, 72>, <<0, 1, 0, 1>, 72>, <<0, 1, 0, 2>, 72>, <<0, 1, 1, 0>, 36>, <<0, 1, 1, 1>, 36>, <<0, 1, 1, 2>, 36>, <<1, 0, 0, 0>, 18>, <<1, 0, 0, 1>, 18>, <<1, 0, 0, 2>, 18>, <<1, 0, 1, 0>, 144>, <<1, 0, 1, 1>, 144>, <<1, 0, 1, 2>, 144>, <<1, 1, 0, 0>, 36>, <<1, 1, 0, 1>, 36>, <<1, 1, 0, 2>, 36>, <<1, 1, 1, 0>, 72>, <<1, 1, 1, 1>, 72>, <<1, 1, 1, 2>, 72> ]