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. For a sample application of this function, see Example H22E17.
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 Chapter FP GROUPS - ADVANCED FEATURES.
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
Given the group G defined by the presentation < a, b | a^8, b^7, (ab)^2, (a, b)^9 >, there is a homomorphism into Sym(9) defined by
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 stabiliser 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); 9Using the function GeneratingWords, we obtain a set of generators for H.
> 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 }
This section describes the simplest use of coset enumeration techniques in Magma. Magma also provides interactive facilities for coset enumeration. For information on these more advanced uses, the user is referred to Chapter FP GROUPS - ADVANCED FEATURES.
The Todd-Coxeter implementation installed in Magma is based on the stand alone coset enumeration programme ACE3 developed by George Havas and Colin Ramsay at the University of Queensland. The reader should consult [CDHW73] and [Hav91] for an explanation of the terminology and a general description of the algorithm. A manual for ACE3 as well as the sources of ACE3 can be found online [Ram].
Experienced users can control the Todd-Coxeter procedures invoked by the functions described in this section with a wide range of parameters. For a complete description of these parameters and their meanings we refer to the manual entry for the function CosetEnumerationProcess in Chapter FP GROUPS - ADVANCED FEATURES. We just mention briefly the most important ones:
CosetLimit : RngIntElt Default : 0
If CosetLimit is set to n, where n is a positive integer, then the coset table may have at most n rows. In other words, a maximum of n cosets can be defined at any instant during the enumeration. It is ensured in this case, that enough memory is allocated to store the requested number of cosets, regardless of the value of the parameter Workspace.
If CosetLimit is set to 0 (default), the maximal number of active cosets is determined by the size of the coset table (cf. parameter Workspace) and the number of columns of the coset table (i.e. the number of group generators).
Workspace : RngIntElt Default : 4000000
The number of words allocated for the coset table. Note that if CosetLimit is set, at least as much memory is allocated as is necessary to store the requested number of cosets.
Strategy : MonStgElt
Using this parameter one of several predefined strategies can be selected. (See the manual entry for the function CosetEnumerationProcess in Chapter FP GROUPS - ADVANCED FEATURES for a complete list.) The most important values of this parameter are:
The strategy employed by the functions Order and FactoredOrder may involve trying to obtain information on certain subgroups of G. Whether or not an attempt is made to construct a presentation for a subgroup arising in the course of the computation by means of Reidemeister-Schreier rewriting, is controlled by three parameters:
var UseRewrite: BoolElt Default: true var MinIndex: RngIntElt Default: 10 var MaxIndex: RngIntElt Default: 1000 If UseRewrite is set to false, attempts to construct presentations for subgroups are not made. Otherwise, MinIndex and MaxIndex specify for subgroups of which index range Reidemeister-Schreier rewriting is done.
The following strategy is used for trying to determine the order of G.
Experienced users can control the behaviour of coset enumerations which may be invoked by the functions Order and FactoredOrder with a wide range of parameters. Both functions -- in addition to the parameters mentioned above -- accept the same parameters as the function CosetEnumerationProcess described in Chapter FP GROUPS - ADVANCED FEATURES.
Given a subgroup H of the fp-group G, this function attempts to build up a coset table of H in G using the Todd-Coxeter procedure.
The first return value is the index of H in G (or 0, if the enumeration fails to complete). The other values returned are the coset table map, the maximum number of simultaneously active cosets, and the total number of cosets defined during the enumeration.
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 Chapter FP GROUPS - ADVANCED FEATURES.
Given a subgroup H of the fp-group G, these functions attempt to determine the index of H in G by enumerating the cosets of H using the Todd-Coxeter procedure. The index is returned as a positive integer (Index) or as a sequence of factors (FactoredIndex), respectively. If the coset enumeration fails to complete with a closed coset table, Index returns a value of 0, whereas FactoredIndex reports an error. No conclusion can be drawn in this case.
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 Chapter FP GROUPS - ADVANCED FEATURES.
> 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
Given an fp-group G, this function attempts to determine the order of G or to prove that G is infinite. If a finite order can be computed, the function Order returns the order as a positive integer, whereas the function FactoredOrder returns a sequence of prime power factors. The function FactoredOrder reports an error in all other cases, whereas the function Order returns the object Infinity, if G can be shown to be infinite and returns a value of 0 if neither a finite value for the group order nor a proof for the infinity of G can be obtained. No conclusions can be drawn from a return value 0 of Order.
In addition to the parameters controlling possibly invoked coset enumerations, there exist some other parameters controlling the strategy used by the functions Order and FactoredOrder. These parameters are described below.
> G<x, y> := Group<x,y | x^8, y^7, (x*y)^2, (x^-1*y)^3>;
> G;
Finitely presented group G on 2 generators
Relations
x^8 = Id(G)
y^7 = Id(G)
(x * y)^2 = Id(G)
(x^-1 * y)^3 = Id(G)
> Order(G);
10752
< 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. We use
the parameter CosetLimit to request a sufficiently large
coset table.
For the enumeration we choose the predefined strategy Hard
with the modification of a complete C-style lookahead
(Lookahead := 2).
> 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 >; > idx := Index(HN, H: Print := true, CosetLimit := 1200000, > Strategy := "Hard", Lookahead := 2); INDEX = 1140000 (a=1140000 r=1471 h=1168483 n=1168483; l=2945 c=201.17; m=1142416 t=1470356) > idx; 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) : Strategy := "Easy") > > : i, j, k in [0..1], l in [0..2] ]; [ <<0, 0, 0, 0>, 144>, <<0, 0, 1, 0>, 18>, <<0, 1, 0, 0>, 72>, <<0, 1, 1, 0>, 36>, <<1, 0, 0, 0>, 18>, <<1, 0, 1, 0>, 144>, <<1, 1, 0, 0>, 36>, <<1, 1, 1, 0>, 72>, <<0, 0, 0, 1>, 144>, <<0, 0, 1, 1>, 18>, <<0, 1, 0, 1>, 72>, <<0, 1, 1, 1>, 36>, <<1, 0, 0, 1>, 18>, <<1, 0, 1, 1>, 144>, <<1, 1, 0, 1>, 36>, <<1, 1, 1, 1>, 72>, <<0, 0, 0, 2>, 144>, <<0, 0, 1, 2>, 18>, <<0, 1, 0, 2>, 72>, <<0, 1, 1, 2>, 36>, <<1, 0, 0, 2>, 18>, <<1, 0, 1, 2>, 144>, <<1,1, 0, 2>, 36>, <<1, 1, 1, 2>, 72> ]
Several functions working with finitely presented groups at some point require a coset table of a subgroup and may invoke a coset enumeration indirectly, e.g. the function meet or the function Normaliser. The default behaviour for such implicitly called coset enumerations is the same as the one for coset enumerations invoked explicitly, e.g. using the function ToddCoxeter.
If such an implicitly called coset enumeration fails to produce a closed coset table, the calling function may terminate with a runtime error.
Experienced users can control the behaviour of indirectly invoked coset enumerations with a set of global parameters. These global parameters are valid for all implicitly called coset enumerations. For a detailed description of the available parameters and their meanings, we refer to Chapter FP GROUPS - ADVANCED FEATURES. Note that coset enumerations which are explicitly invoked, e.g. by a call to the function Index, are not affected by this global set of parameters. Parameters for these functions have to be specified in the function call.
This function sets the parameter values used for indirect invocations of the Todd-Coxeter coset enumeration procedure. The parameters accepted and their default values are the same as for the function CosetEnumerationProcess described in Chapter FP GROUPS - ADVANCED FEATURES.
This function restores the default values for the parameters used for indirect invocations of the Todd-Coxeter coset enumeration procedure. For a description of the meanings of the parameters and their default values, see CosetEnumerationProcess in Chapter FP GROUPS - ADVANCED FEATURES.
We consider again the Harada-Norton simple group with the presentation
< 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) >
and the subgroup H generated by x, b, c, d, e, f, g.
> 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 >;H has index 1,140,000 in HN. Using the default settings, the normaliser of H in HN cannot be computed.
We change the global parameters for implicitly called coset enumerations and try again.
> N := Normaliser(HN, H); >> N := Normaliser(HN, H); ^ Runtime error in 'Normaliser': Coset table is not closed
> SetGlobalTCParameters( : Strategy := "Hard"); > N := Normaliser(HN, H);With these parameters, the computation works. We see that H is self-normalising in HN.
> Index(HN, N); 1140000 > IsSelfNormalising(HN, H); true
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. In principle, such a presentation can be obtained either on a set of Schreier generators for H using the Reidemeister-Schreier rewriting technique [MKS76] or on the given generators of H [AR84], [HKRR84].
If the user wishes only to determine the structure of the derived quotient group of H, then the function AbelianQuotientInvariants, described above, 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 AbelianQuotientInvariants may be applied to subgroups H of much larger index in G than may be the function Rewrite.
Given a finitely presented group G and a subgroup H having finite index in G, construct a presentation for H by rewriting the presentation given for G. The isomorphism from H onto the constructed fp-group 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 Chapter FP GROUPS - ADVANCED FEATURES.
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: 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: 0These parameters control the simplification. See the description under Simplify below.
> G<x, y> := Group< 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 = y^3
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> ]