44.5 Coset Tables and Coset Enumeration

returns the coset table of the finitely presented group G on the cosets of the subgroup H.

Basically a coset table is the permutation representation of the finitely presented group on the cosets of a subgroup (which need not be faithful if the subgroup has a nontrivial core). Most of the set theoretic and group functions use the regular representation of G, i.e., the coset table of G over the trivial subgroup.

The coset table is returned as a list of lists. For each generator of G and its inverse the table contains a generator list. A generator list is simply a list of integers. If l is the generator list for the generator g and if l[i] = j then generator g takes the coset i to the coset j by multiplication from the right. Thus the permutation representation of G on the cosets of H is obtained by applying PermList to each generator list (see PermList). The coset table is standardized, i.e., the cosets are sorted with respect to the smallest word that lies in each coset.

For finitely presented groups, a coset table is computed by a Todd-Coxeter coset enumeration. Note that you may influence the performance of that enumeration by changing the values of the global variables CosetTableFpGroupDefaultLimit and CosetTableFpGroupDefaultMaxLimit described below and that the options described under CosetTableFromGensAndRels are recognized.

gap> CosetTable( g, Subgroup( g, [ g.1, g.2*g.1*g.2*g.1*g.2^-1 ] ) );
[ [ 1, 3, 2, 5, 4 ], [ 1, 3, 2, 5, 4 ], [ 2, 4, 3, 1, 5 ], [ 4, 1, 3, 2, 5 ] ]
gap> List( last, PermList );
[ (2,3)(4,5), (2,3)(4,5), (1,2,4), (1,4,2) ]

is equivalent to CosetTable(G,H) where G is the (unique) finitely presented group such that H is a subgroup of G. It overrides a silent option (see CosetTableFromGensAndRels) with false.

The variant TryCosetTableInWholeGroup does not override the silent option with false in case a coset table is only wanted if not too expensive. It will store a result that is not fail in the attribute CosetTableInWholeGroup.

returns the action of G on the cosets of the subgroup H of G.

gap> u := Subgroup( g, [ g.1, g.1^g.2 ] );
Group([ a, b^-1*a*b ])
gap> FactorCosetAction( g, u );
[ a, b ] -> [ (2,3)(5,6), (1,2,4)(3,5,6) ]

returns a coset table for the action of G on the cosets of H. The columns of the table correspond to the GeneratorsOfGroup(G).

is an internal function which is called by the functions CosetTable, CosetTableInWholeGroup and others. It is, in fact, the proper working horse that performs a Todd-Coxeter coset enumeration. fgens must be a set of free generators and grels a set of relators in these generators. fsgens are subgroup generators expressed as words in these generators. The function returns a coset table with respect to fgens.

CosetTableFromGensAndRels will call TCENUM.CosetTableFromGensAndRels. This makes it possible to replace the built-in coset enumerator with another one by assigning TCENUM to another record.

The library version which is used by default performs a standard Felsch strategy coset enumeration. You can call this function explicitly as GAPTCENUM.CosetTableFromGensAndRels even if other coset enumerators are installed.

The expected parameters are

fgens

generators of the free group F

grels

relators as words in F

fsgens

subgroup generators as words in F.

CosetTableFromGensAndRels processes two options (see chapter Options Stack):

max

The limit of the number of cosets to be defined. If the enumeration does not finish with this number of cosets, an error is raised and the user is asked whether she wants to continue. The default value is the value given in the variable CosetTableDefaultMaxLimit. (Due to the algorithm the actual limit used can be a bit higher than the number given.)

silent

if set to true the algorithm will not raise the error mentioned under option max but silently return fail. This can be useful if an enumeration is only wanted unless it becomes too big.

is the default limit for the number of cosets allowed in a coset enumeration.

A coset enumeration will not finish if the subgroup does not have finite index, and even if it has it may take many more intermediate cosets than the actual index of the subgroup is. To avoid a coset enumeration ``running away'' therefore GAP has a ``safety stop'' built in. This is controlled by the global variable CosetTableDefaultMaxLimit.

If this number of cosets is reached, GAP will issue an error message and prompt the user to either continue the calculation or to stop it. The default value is 256000.

See also the description of the options to CosetTableFromGensAndRels.

gap> f := FreeGroup( "a", "b" );;
gap> u := Subgroup( f, [ f.2 ] );
Group([ b ])
gap> Index( f, u );
Error the coset enumeration has defined more than 256000 cosets:
type 'return;' if you want to continue with a new limit of 512000 cosets,
type 'quit;' if you want to quit the coset enumeration,
type 'maxlimit := 0; return;' in order to continue without a limit,

At this point you can either continue the calculation with a larger number of permitted cosets or stop the calculation if you don't expect the enumeration to finish (like in the example above).

Setting CosetTableDefaultMaxLimit (or the max option value) to infinity (or to 0) will enforce all coset enumerations to continue until they either get a result or exhaust the whole available space.

is the default number of cosets with which any coset table is initialized before doing a coset enumeration.

The function performing this coset enumeration will automatically extend the table whenever necessary (as long as the number of cosets does not exceed the value of CosetTableDefaultMaxLimit), but this is an expensive operation. Thus, if you change the value of CosetTableDefaultLimit, you should set it to a number of cosets that you expect to be sufficient for your subsequent coset enumerations. On the other hand, if you make it too large, your job will unnecessarily waste a lot of space.

The default value of CosetTableDefaultLimit is 1000.

is an internal function used by the subgroup presentation functions described in Subgroup Presentations. It applies a Modified Todd-Coxeter coset representative enumeration to construct an augmented coset table (see Subgroup presentations) for the given subgroup H of G. The subgroup generators will be named string1, string2, ... .

The function accepts the options max and silent as described for the function CosetTableFromGensAndRels (see CosetTableFromGensAndRels).

is an internal function used by the subgroup presentation functions described in Subgroup Presentations. It applies the Reduced Reidemeister-Schreier method to construct an augmented coset table for the subgroup of G which is defined by the given coset table table. The new subgroup generators will be named string1, string2, ... .

is an internal function which is used in some applications of coset table methods. It returns the first of those generators of the given finitely presented group G which occur most frequently in the relators.

returns the indices of those generators of the finitely presented group G which are known to be involutions. This knowledge is used by internal functions to improve the performance of coset enumerations.

[Top] [Previous] [Up] [Next] [Index]