Construct the subgroup H of the fp-group G generated by the words specified by the terms of the generator list L = L1, ..., Lr.A term Li 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)
- A word;
- (b)
- A set or sequence of words;
- (c)
- A sequence of integers representing a word;
- (d)
- A set or sequence of sequences of integers representing words;
- (e)
- A subgroup of an fp-group;
- (f)
- A set or sequence of subgroups.
The generators of H consist of the words specified directly by terms Li together with the stored generating words for any groups specified by terms of Li. 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 H78E53.
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, see Subsec. Interactive Coset Enumeration.
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.
Given an fp-group G, try to construct the derived subgroup Gprime of G as finite index subgroup of G. The construction fails if no presentation for G is known or can be constructed, or if the index of Gprime in G is too large or infinite.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, see Subsec. Interactive Coset Enumeration.
> G<a, b> := FPGroup<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, b | a8, b7, (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> := FPGroup< 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 Subsec. Interactive Coset Enumeration.
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. We just mention briefly the most important ones:
CosetLimit : RngIntElt Default : 0If 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 : 4000000The 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 : MonStgEltUsing this parameter one of several predefined strategies can be selected. (See the manual entry for the function CosetEnumerationProcess in Subsec. Interactive Coset Enumeration for a complete list.) The most important values of this parameter are:
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 in Subsec. Interactive Coset Enumeration.
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 in Subsec. Interactive Coset Enumeration.
> 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. 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> := > FPGroup< 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 | > > FPGroup< > 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> ]
This section presents the interactive coset enumeration facility of Magma. This concept makes it possible to restart an enumeration after changing enumeration parameters or adding relators or subgroup generators, while making use of information obtained up to that point as much as possible. It is thus particularly suitable for very hard enumerations, requiring a careful and interactive choice of enumeration parameters or for series of similar enumerations.
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].
In Magma an interactive coset enumeration is realised as an object of the category GrpFPCosetEnumProc which can be created and modified, allows starting and restarting of coset enumerations and provides access to internal data like the coset table and various status information.
This function creates a coset enumeration process for enumerating the cosets of the subgroup H of the finitely presented group G. Note that no actual coset enumeration is started for the created coset enumeration process. This can be done with the function StartEnumeration.The user can control in detail the way a subsequent enumeration will be performed with the help of the following parameters. For a more thorough explanation of the parameters and of how they affect the coset enumeration, we refer to the ACE3 manual.
Compact: RngIntElt Default: 10This parameter controls the compaction of the coset table during an enumeration. A compaction will be done if a new coset definition is required, there is no space for a new coset available in the coset table and the percentage of dead cosets exceeds the value of the parameter Compact.CosetLimit: RngIntElt Default: 0If 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: 4000000The 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.FillFactor: RngIntElt Default: 0In certain situations it is necessary to ensure that a certain proportion, the fill fraction (see Havas (1991)), of the coset table is always kept filled, even if preferred definitions are made. The parameter FillFactor allows the user to specify the fill fraction which is the reciprocal of FillFactor. The default value of 0 selects a fill factor of ⌊(5 * (c + 2))/4⌋, where c is the number of columns in the coset table.CTFactor: RngIntElt Default: 1000RTFactor: RngIntElt Default: 2000/lStyle: MonStgElt Default: "R_CR"These parameters control the enumeration style and the balance between coset table style definitions (C-style, Felsch style) and relator table style definitions (R-style, HLT style).The parameters CTFactor and RTFactor set the number of C-style coset definitions and R-style coset applications, respectively, which are performed in every step of the appropriate type. The default value for RTFactor is 2000/l, where l is the total length of the relators.
In style R all definitions are made via relator scans, i.e. this is HLT mode.
In style C all definitions are made by filling the next empty position in the coset table and testing the new coset in all essentially different positions in the relators, i.e. this is Felsch mode.
In style R_CR we run in style R until an overflow occurs, perform a lookahead on the entire table and then switch to style CR (see below).
The styles Rc and Cr are like the styles R and C, except that a single style C or style R pass is done after the initial R or style C pass, respectively.
In style Rt definitions are made as in style R, but the new cosets are tested in all essentially different positions in the relators as in style C.
In style CR alternate passes of style C and style R are performed, with all definitions tested in all essentially different positions in the relators as in style C.
Lookahead: RngIntElt Default: 0In HLT style enumerations, possible implications of new definitions or deductions made while tracing relators may not be detected until much later. One possible solution to this problem is to perform lookaheads occasionally, i.e. to process the coset table, looking for deductions or coincidences. A lookahead can be done using the entire table (complete) or only that part of the table above the current coset (partial) and it can be done in R-style (scanning cosets from the beginning of relators) or in C-style (testing all definitions in all essentially different relator positions). The following lookahead modes are supported.For Lookahead := 0 (default) no lookahead is done.
For Lookahead := 1 a partial R-style lookahead is done.
For Lookahead := 2 a complete C-style lookahead is done.
For Lookahead := 3 a complete R-style lookahead is done.
For Lookahead := 4 a partial C-style lookahead is done.
Mendelsohn: BoolElt Default: falseIf Mendelsohn is set, coset applications are done at all cyclic permutations of the relators. This is usually very expensive but may nevertheless be helpful in certain cases.RelationsInSubgroup: RngIntElt Default: -1This parameter controls, whether relators are treated as additional subgroup generators, i.e. whether they are applied to coset 1 at the start of an enumeration. An argument of -1 (default) includes all relators, an argument of 0 turns this feature off and a positive argument includes the appropriate number of relators, in order.RowFilling: BoolElt Default: trueIn R-style it is usual to scan each row of the table after its coset has been applied to all relators, and to make definitions to fill any holes encountered. Failure to do so can cause even simple enumerations to overflow. To switch row filling off, set the parameter RowFilling to false.PrefDefMode: RngIntElt Default: 3If the argument is 0, then Felsch style definitions are made using the next empty position in the coset table. Otherwise, gaps of length one found during relator scans are preferentially filled. If the argument is 1, they are filled immediately, and if it is 2, the consequent deduction is also made immediately. If the argument is 3, then the gaps are noted in the preferred definition queue and the next coset definition will be made to fill the oldest gap of length one.PrefDefSize: RngIntElt Default: 8This parameter controls the size of the preferred definition queue, which is implemented as a ring buffer, dropping earliest entries. Setting PrefDefSize to n allocates a buffer of size 2n.DeductionMode: RngIntElt Default: 4A completed table is only valid if every table entry has been tested in all essentially different relator positions. Untested deductions are stored on a stack. This parameter allows the user to specify how deductions should be handled. The possible actions are:For DeductionMode := 0 : discard deductions if there is no stack space left.
For DeductionMode := 1 : as 0, but redundant cosets are purged off the top of the stack whenever a coincidence is found.
For DeductionMode := 2 : as 0, but all redundant cosets are purged from the stack whenever a coincidence is found.
For DeductionMode := 3 : discard the entire stack if it overflows.
For DeductionMode := 4 : if the stack overflows, then double the stack size and purge all redundant cosets from the stack.
If deductions are discarded for any reason during an enumeration, then a final relator application pass will be done at the end of the enumeration automatically to check the result.
DeductionSize: RngIntElt Default: 1000Sets the (initial) size of the deduction stack in words, with one deduction taking two words. A value of 0 selects the default size of 1000 words.PathCompression: BoolElt Default: falseSwitching this option on reduces the amount of data movement during coincidence processing at the expense of tracing and compressing coincidence paths, which involves many coset table accesses. The value of this parameter has no effect on the result but may influence the running time.TimeLimit: RngIntElt Default: -1This parameter puts a time limit in seconds on the length of an enumeration. A value of -1 (default) means no limit. A value of 0 performs exactly one pass through the main enumeration loop.LoopLimit: RngIntElt Default: 0The core enumerator is organised as a state machine, with each step performing an action (e.g. lookahead, compaction) or a block of actions (e.g. CTFactor coset definitions or RTFactor coset applications). Using this parameter, a limit on the total number of steps can be imposed. A value of 0 (default) turns this feature off.LowerBound: RngIntElt Default: 1This may be set to any known lower bound for the index. Should it happen that the coset table has no holes, and the number of active cosets is equal to the given bound, the enumeration will terminate. When the given bound is equal to the index, this will save tracing relators at many cosets when there is no possibility of finding coincidences.Print: BoolElt Default: falseIf this parameter is set to true, the enumerator prints a single message at the end of an enumeration and possibly some progress messages during an enumeration (cf. parameter Messages).Messages: RngIntElt Default: 0If the argument n of this parameter is non-zero (and Print is set to true), then a progress message is printed after every |n| "actions" (i.e. coset definitions, deductions, coincidences, etc.) A negative value of n turns hole monitoring on.Strategy: MonStgElt Default:Using this parameter one of several predefined strategies can be selected. The effect is equivalent to selecting an appropriate combination of arguments for some of the parameters explained above. Any predefined strategy can be modified by explicitly overriding parameter values.The following predefined strategies exist: "Default", "Easy", "Hard", "Felsch", "HLT", "CT", "RT", "Sims1", "Sims3", "Sims5", "Sims7", "Sims9".
All predefined strategies set PrefDefSize := 8, DeductionSize := 1000, PathCompression := false and LoopLimit := 0. For the remaining parameter settings see Table 1, Table 2 and Table 3.
Default Easy Hard Felsch HLT CT Compact 10 100 10 10 10 100 Workspace 4 1 10 4 4 4 FillFactor 0 1 0 0 1 1 CTFactor 1000 0 1000 1000 0 1000 RTFactor 2000/l 1000 1 0 1000 0 Style R_CR R CR C R C Lookahead 0 0 0 0 1 0 Mendelsohn false false false false false false RelationsInSubgroup -1 0 -1 -1 0 0 RowFilling true true true false true false PrefDefMode 3 0 3 3 0 0 DeductionMode 4 0 4 4 0 4RT Sims1 Sims3 Sims5 Sims7 Sims9 Compact 100 10 10 10 10 10 Workspace 4 4 4 4 4 4 FillFactor 1 1 1 1 1 1 CTFactor 0 0 0 0 0 1000 RTFactor 1000 1000 1000 1000 1000 0 Style R R Rt R Rt C Lookahead 0 0 0 0 0 0 Mendelsohn false false false true true false RelationsInSubgroup 0 0 0 0 0 0 RowFilling false true true true true false PrefDefMode 0 0 0 0 0 0 DeductionMode 0 0 4 0 4 4
Add a word w in the generators of the group G underlying the coset enumeration process P to the defining relations of G. This means that a coset enumeration process P for the cosets of H in G is transformed into a coset enumeration process for the cosets of π(H) in π(G), where π: G -> π(G) is an epimorphism with kernel < w >G. (Here < w >G denotes the normal closure in G of the subgroup of G generated by w.)
Add an element w of the group G underlying the coset enumeration process P to the generators of the subgroup. This means that a coset enumeration process P for the cosets of H in G is transformed into a coset enumeration process for the cosets of < H, w > in G, where < H, w > denotes the subgroup of G generated by H and w.
Change enumeration parameters of the coset enumeration process P. The set of parameters accepted by this function is the same as for the function CosetEnumerationProcess; see there for a description.All parameters which are not explicitly changed or modified by selecting one of the predefined strategies retain their old values.
It should be noted that it is not possible to decrease the workspace allocated by a coset enumeration process, once an enumeration has been started. However the workspace can be extended without invalidating any information contained in the process.
There are several ways of starting and restarting an enumeration for a coset enumeration process, which retain information from previous enumerations to a varying extent.
Start a new enumeration for P. All information in P is discarded. This function can be called at any time for an existing coset enumeration process. The enumeration parameters for P can be modified by passing parameters to this function. (This is equivalent to calling the function SetProcessParameters before calling StartEnumeration.) The set of parameters accepted by this function is the same as for the function CosetEnumerationProcess; see there for a description.
Restart an enumeration for P. All information in P is retained and the enumeration is restarted at coset number 1. This function can be called for any coset enumeration process, which contains a valid coset table. (If P does not contain a valid coset table, a call to RedoEnumeration causes a runtime error. Use the function CanRedoEnumeration to check whether a call to RedoEnumeration is legal for a certain coset enumeration process.) Note that the coset table of P need not be complete to use this function.This function is intended for the case where additional relators and/or subgroup generators have been introduced. The coset table contained in P is still valid. However, the additional data may allow the enumeration to compete, or cause a collapse to a smaller index.
The enumeration parameters for P can be modified by passing parameters to this function. (This is equivalent to calling the function SetProcessParameters before calling RedoEnumeration.) The set of parameters accepted by this function is the same as for the function CosetEnumerationProcess; see there for a description.
Returns true, if a call to RedoEnumeration is legal for the coset enumeration process P.
Continue an enumeration for P, which has been interrupted because some limit was exceeded. All information in P is retained and the enumeration is restarted at the coset where the previous enumeration was stopped. This function can only be called for a coset enumeration process, if the previous enumeration produced a valid coset table and the subgroup underlying P has not been changed since then. (Otherwise, a call to ContinueEnumeration causes a runtime error. Use the function CanContinueEnumeration to check whether a call to ContinueEnumeration is legal for a certain coset enumeration process.) Note that the coset table of P need not be complete to use this function.This function is intended for the case where an enumeration stopped without producing a finite index. This function allows to continue the enumeration with modified enumeration parameters with the minimal possible overhead.
The enumeration parameters for P can be modified by passing parameters to this function. (This is equivalent to calling the function SetProcessParameters before calling ContinueEnumeration.) The set of parameters accepted by this function is the same as for the function CosetEnumerationProcess; see there for a description.
Returns true, if a call to ContinueEnumeration is legal for the coset enumeration process P.
Resume or start an enumeration for P in the "cheapest" way permitted by the state of the coset enumeration process P. The callResumeEnumeration(~P : parameters);is equivalent to
if CanContinueEnumeration(P) then ContinueEnumeration(~P : parameters); elif CanRedoEnumeration(P) then RedoEnumeration(~P : parameters); else StartEnumeration(~P : parameters); end if;The enumeration parameters for P can be modified by passing parameters to this function. (This is equivalent to calling the function SetProcessParameters before calling ResumeEnumeration.) The set of parameters accepted by this function is the same as for the function CosetEnumerationProcess; see there for a description.
Given a coset enumeration process P with underlying group G and subgroup H, which contains a valid coset table, these functions return a set of words representing cosets which satisfy the conditions defined in the parameters.A call to CosetSatisfying is equivalent to calling CosetsSatisfying with Limit set to 1 and First set to 2 (unless a higher value for First is specified explicitly), i.e. the function returns when the first coset, other than H, satisfying the specified conditions has been found.
First: RngIntElt Default: 1This parameter determines at which coset the search for coset representatives satisfying the designated conditions is started. The coset H always is coset number 1, i.e. setting First to 2 restricts the search to non-trivial cosets.For the function CosetSatisfying, the minimal possible value for this parameter is 2; setting it to 1 does not cause an error but will be ignored.
Last: RngIntElt Default: 0This parameter determines at which coset the search for coset representatives satisfying the designated conditions is stopped. If it is set to 0 (default), all active cosets (starting from First) are searched.Limit: RngIntElt Default: 0If this parameter is set to l > 0, the search for coset representatives is aborted as soon as l cosets satisfying the designated condition have been found. If it is set to 0 (default for CosetsSatisfying), no limit is in force.This parameter is not available for the function CosetSatisfying.
Normalizing: BoolElt Default: falseIf true, select coset representatives x such that x - 1hix is known to be contained in H from the information in the coset table of P for every generator hi of H. (I.e. x is recognised as an element of the normaliser of H in G.)Order: RngIntElt Default: 0Select coset representatives x such that xn is known to be contained in H from the information in the coset table of P.Print: RngIntElt Default: 0If the value of this parameter is positive, print the coset representatives found to satisfy the designated conditions.These functions can be called for any coset enumeration process, which contains a valid coset table. If P does not contain a valid coset table, a call to any of these functions causes a runtime error. You can use the function HasValidCosetTable to check whether a call to these functions is legal for a certain coset enumeration process.
The current coset table of P as a map f:{1, ..., r} x G -> {0, ..., r}, where G and H are the finitely presented group and the subgroup underlying P, respectively, and r is number of active cosets. 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 complete, and it denotes that the image of i under x is not known.This function can be called for any coset enumeration process, which contains a valid coset table. If P does not contain a valid coset table, a call to CosetTable causes a runtime error. Use the function HasValidCosetTable to check whether a call to CosetTable is legal for a certain coset enumeration process. Note that the coset table of P need not be complete to use this function.
Returns true, if P contains a valid (but not necessarily closed) coset table, i.e. if a call to CosetTable is legal for the coset enumeration process P.
Returns true, if P contains a closed, valid coset table.Note that if HasClosedCosetTable returns true for a coset enumeration process P, then in particular a call to CosetTable is legal for P.
Given a coset enumeration process P with underlying group G and subgroup H, which contains a valid coset table, these functions return a set E containing either at most one word (ExcludedConjugate) or all words (ExcludedConjugates) of the form gi - 1hjgi, where gi is a generator of G and hj is a generator of H, such that gi - 1hjgi is not known to lie in H from the information contained in the coset table of P.If E is empty, then H is a normal subgroup of G. Otherwise the addition of elements of E to the generators of H may yield a larger subgroup of the normal closure of H in G. In the case of a non-complete coset table it may happen, however, that excluded conjugates are found which actually lie in H.
These functions can be called for any coset enumeration process, which contains a valid coset table. If P does not contain a valid coset table, a call to ExcludedConjugate or ExcludedConjugates causes a runtime error. You can use the function HasValidCosetTable to check whether a call to these functions is legal for a certain coset enumeration process.
Given a coset enumeration process P with underlying group G and subgroup H, which contains a valid coset table, return whether or not there exists a coset other than H, which satisfies the conditions defined in the parameters. If such a coset exists, a representing word is returned as second return value. This function accepts the same set of parameters as the function CosetSatisfying; see there for a description.This function can be called for any coset enumeration process, which contains a valid coset table. If P does not contain a valid coset table, a call to ExistsCosetSatisfying causes a runtime error. You can use the function HasValidCosetTable to check whether a call to ExistsCosetSatisfying is legal for a certain coset enumeration process.
Given a coset enumeration process P with underlying group G and subgroup H, which contains a valid coset table, return whether or not there exists a word of the form gi - 1hjgi, where gi is a generator of G and hj is a generator of H, such that gi - 1hjgi is not known to lie in H from the information contained in the coset table of P. If the answer is positive, such a word is returned as second return value.This function can be called for any coset enumeration process, which contains a valid coset table. If P does not contain a valid coset table, a call to ExistsExcludedConjugate causes a runtime error. You can use the function HasValidCosetTable to check whether a call to ExistsExcludedConjugate is legal for a certain coset enumeration process.
Note that the coset table of P need not be complete to call this function. A negative result of ExistsExcludedConjugate always implies that H is a normal subgroup of G, even if the coset table of P is not complete. In the case of a non-complete coset table it may happen, however, that excluded conjugates are found which actually lie in H.
Returns true, if an element of G - H which normalises H can be found from the coset table contained in P. (Here, G and H are the finitely presented group and the subgroup underlying P, respectively.) If the answer is positive, such an element is returned as second return value.This function can be called for any coset enumeration process, which contains a valid coset table. If P does not contain a valid coset table, a call to ExistsNormalisingCoset causes a runtime error. You can use the function HasValidCosetTable to check whether a call to ExistsNormalisingCoset is legal for a certain coset enumeration process.
Note that the coset table of P need not be complete to call this function. However, no conclusion can be drawn from a negative result in the case of a non-complete coset table.
Returns the group underlying P as a finitely presented group.
Returns the index of H in G. (Here, G and H denote the finitely presented group and the subgroup underlying P, respectively.)This function can only be called, if the last enumeration done for P has completed successfully with a finite index. Otherwise, a call to Index will cause a runtime error. Use the function HasValidIndex to check whether a call to Index is legal for a certain coset enumeration process.
Returns true, if the last enumeration done for P has completed successfully with a finite index, i.e., if a call to Index is legal for the coset enumeration process P.
Returns the maximal number of cosets which were simultaneously active during the last enumeration done for P, or 1 if no enumeration has been done for P.This function may be useful for assessing the performance of a certain set of enumeration parameters.
Returns the subgroup H underlying the coset enumeration process P. H is returned as a subgroup of G, where G is the finitely presented group underlying P.
Returns the total number of cosets defined during the last enumeration done for P, or 1 if no enumeration has been done for P.This function may be useful for assessing the performance of a certain set of enumeration parameters.
< 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) >.
we want to construct the coset table for the subgroup generated by
x, b, c, d, e, f, g interactively. First, we create a coset enumeration
process. Since the index of the chosen subgroup is 1 140 000, we request a
coset limit of 1 200 000. Then we start the enumeration.
> HN<x, a, b, c, d, e, f, g> := > FPGroup< 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 >; > P := CosetEnumerationProcess(HN, H : CosetLimit := 1200000, Print := true); > StartEnumeration(~P); Overflow (a=1110331 r=58605 h=101193 n=1200001; l=5444 c=105.36; m=1110331 t=2001537)The enumeration could not be completed successfully. Though P does contain a valid coset table, but this coset table fails to be closed.
> HasValidCosetTable(P); true > HasClosedCosetTable(P); falseWe extract the coset table map, check its domain and its codomain, and determine the position of the first "hole" in the coset table.
> ct := CosetTable(P);
> Domain(ct) : Minimal;
Cartesian Product<{ 1 .. 1110331 }, GrpFP: HN>
> Codomain(ct);
{ 0 .. 1110331 }
> row := 1;
> while forall(col){ gen : gen in {x, a, b, c, d, e, f, g}
> | ct(<row, gen>) ne 0 } do
> row +:= 1;
> end while;
> row;
41881
> col;
x
We change the enumeration parameters for the process P, selecting the
predefined strategy Hard. Since this predefined strategy sets a
workspace of 10 000 000, we must expressly override this, if we want
the old value to be retained. Because the workspace size never is decreased
once an enumeration has been started, we can retain the old value simply by
setting Workspace to 0; this overrides the setting done by
selecting
the predefined strategy, but actually doesn't change the process' workspace.
We then continue the enumeration with the new set of parameters, after
checking that this is legal.
> SetProcessParameters(~P : Strategy := "Hard", > Workspace := 0); > CanContinueEnumeration(P); true > ContinueEnumeration(~P); INDEX = 1140000 (a=1140000 r=58512 h=1144534 n=1144534; l=70 c=6.50; m=1140000 t=2035739)We have obtained a closed coset table. Note that the codomain of the new coset table map does not contain 0.
> HasClosedCosetTable(P);
true
> ct := CosetTable(P);
> Domain(ct) : Minimal;
Cartesian Product<{ 1 .. 1140000 }, GrpFP: HN>
> Codomain(ct);
{ 1 .. 1140000 }
G := < a, b | a^8, b^7, (a*b)^2, (a^-1*b)^3 >and start the enumeration.
> F<x, y> := FreeGroup(2); > G<a, b> := quo<F | x^8, y^7, (x*y)^2, (x^-1*y)^3>; > H := sub<G | >; > P := CosetEnumerationProcess(G, H : Print := true); > StartEnumeration(~P); INDEX = 10752 (a=10752 r=57263 h=1 n=57263; l=292 c=0.11; m=47825t=57262)We want to enumerate the cosets of the two non-trivial subgroups of G generated by a - 1 * b and a2, respectively. To do this, we create two copies of the coset enumeration process P and use the function AddSubgroupGenerator for each of them. Since the copies inherit all information contained in P, we then can call the function RedoEnumeration to enumerate the cosets of the two non-trivial subgroups, making use of the existing coset table.
> P1 := P;
> AddSubgroupGenerator(~P1, a^-1*b);
> Subgroup(P1);
Finitely presented group on 2 generators
Generators as words in group G
$.1 = Id(G)
$.2 = a^-1 * b
> CanRedoEnumeration(P1);
true
> RedoEnumeration(~P1);
INDEX = 3584
(a=3584 r=57263 h=1 n=57263;
l=49 c=0.02;
m=47825 t=57262)
>
> P2 := P;
> AddSubgroupGenerator(~P2, a^2);
> Subgroup(P2);
Finitely presented group on 2 generators
Generators as words in group G
$.1 = Id(G)
$.2 = a^2
> CanRedoEnumeration(P2);
true
> RedoEnumeration(~P2);
INDEX = 2688
(a=2688 r=57263 h=1 n=57263;
l=37 c=0.02;
m=47825 t=57262)
Finally, we are interested in the quotient of G by the normal closure of the
subgroup generated by a4 and want to enumerate the cosets of the image of
the subgroup generated by a2 in this quotient. Since this is the subgroup
used in P2, we create a copy of P2 and add the relation a4.
Again, we are able to make use of information obtained earlier, by continuing
the inherited enumeration.
> P3 := P2; > AddRelator(~P3, a^4); > CanContinueEnumeration(P3); true > ContinueEnumeration(~P3); INDEX = 84 (a=84 r=57263 h=1 n=57263; l=2 c=0.00; m=47825 t=57262)We extract the quotient and its subgroup from the process P3, using the appropriate access functions.
> G3<a3,b3> := Group(P3);
> G3;
Finitely presented group G3 on 2 generators
Relations
a3^8 = Id(G3)
b3^7 = Id(G3)
(a3 * b3)^2 = Id(G3)
(a3^-1 * b3)^3 = Id(G3)
a3^4 = Id(G3)
> H3<u3, v3> := Subgroup(P3);
> H3;
Finitely presented group H3 on 2 generators
Generators as words in group G3
u3 = Id(G3)
v3 = a3^2
G := < a, b | b^7, (a*b)^2, (a^-1*b)^3 >generated by a. We create a coset enumeration process and start an enumeration with the default parameters.
> F<x, y> := FreeGroup(2); > G<a, b> := quo<F | y^7, (x*y)^2, (x^-1*y)^3>; > H := sub<G | a>; > P := CosetEnumerationProcess(G, H); > StartEnumeration(~P : Print := true); Overflow (a=957026 r=415230 h=415230 n=999999; l=3553 c=2.38; m=960050 t=999998)The enumeration produces a valid (albeit not complete) coset table.
> HasValidCosetTable(P); true > HasCompleteCosetTable(P); falseEven the partial coset table is sufficient to find an element in the normaliser of H in G.
> found, elt := ExistsNormalisingCoset(P); > found; true > elt; b^-4 * a * b^-2
G := < a, b | b^7, (a*b)^2, (a^-1*b)^3 >generated by a. We create a coset enumeration process and start an enumeration with the default parameters.
> F<x, y> := FreeGroup(2); > G<a, b> := quo<F | y^7, (x*y)^2, (x^-1*y)^3>; > H := sub<G | a>; > P := CosetEnumerationProcess(G, H); > StartEnumeration(~P : Print := true); Overflow (a=957026 r=415230 h=415230 n=999999; l=3553 c=2.38; m=960050 t=999998)We check, whether the coset table exhibits excluded conjugates.
> ExistsExcludedConjugate(P); true a^bIt does. This means in particular, that H is not normal in G. We create a copy P1 of the coset enumeration process P, extend the subgroup of P1 by the excluded conjugates found in the previous step and restart the enumeration for P1.
> P1 := P; > for c in ExcludedConjugates(P) do > AddSubgroupGenerator(~P1, c); > end for; > RedoEnumeration(~P1); INDEX = 1 (a=1 r=2 h=2 n=2; l=2 c=0.94; m=960050 t=999998)The new subgroup is equal to G. In particular, the normal closure of H in G is the whole of G.
We return to the coset enumeration process P and check whether we can find a non-trivial element x∈(N)G(H) such that x2 ∈H.
> ExistsCosetSatisfying(P : Order := 2, Normalizing := true); true b^-4 * a * b^-2We can. In fact, b - 4 a b - 2 is the only non-trivial coset which is known to satisfy this condition ...
> CosetsSatisfying(P : Order := 2, Normalizing := true);
{ Id(G), b^-4 * a * b^-2 }
... and we can't find in a similar way a non-trivial element
x∈(N)G(H) such that x3 ∈H.
> ExistsCosetSatisfying(P : Order := 3, Normalizing := true); falseNote the difference in the output of CosetSatisfying and CosetsSatisfying: The former takes into account only cosets other than H, whereas the latter (unless we set the parameter First) includes the coset H, which obviously satisfies the specified conditions.
> CosetSatisfying(P : Order := 3, Normalizing := true);
> CosetsSatisfying(P : Order := 3, Normalizing := true);
{ Id(G) }
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 Subsec. Interactive Coset Enumeration. 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 Subsec. Interactive Coset Enumeration.
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 Subsec. Interactive Coset Enumeration.
< 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> := > FPGroup< 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.
> N := Normaliser(HN, H);
>> N := Normaliser(HN, H);
^
Runtime error in 'Normaliser': Coset table is not closed
We change the global parameters for implicitly called coset enumerations and
try again.
> 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