Let G be a group defined by a pc-presentation as described in the Chapter Introduction to polycyclic presentations.
The process for computing the collected form for an arbitrary word in the generators of G is called collection. The basic idea in collection is the following. Given a word in the defining generators, one scans the word for occurrences of adjacent generators (or their inverses) in the wrong order or occurrences of subwords gie_i with iinI and ei not in the range 0...ri-1. In the first case, the appropriate conjugacy relation is used to move the generator with the smaller index to the left. In the second case, one uses the appropriate power relation to move the exponent of gi into the required range. These steps are repeated until a collected word is obtained.
There exist a number of different strategies for collecting a given word to collected form. The strategies implemented in this package are collection from the left as described by LGS90 and Sims94 and combinatorial collection from the left by MVL90. In addition, the package provides access to Hall polynomials computed by Deep Thought for the multiplication in a nilpotent group, see WWM97 and LGS98.
The first step in defining a pc-presented group is setting up a data structure that knows the pc-presentation and has routines that perform the collection algorithm with words in the generators of the presentation. Such a data structure is called a collector.
To describe the right hand sides of the relations in a pc-presentation we use generator exponent lists; the word gi_1e_1gi_2e_2...gi_ke_k is represented by the generator exponent list [i1,e1,i2,e2,...,ik,ek].
A collector for a group given by a pc-presentation starts by setting up an empty data structure for the collector. Then the relative orders, the power relations and the conjugate relations are added into the data structure. The construction is finalised by calling a routine that completes the data structure for the collector. The following functions provide the necessary tools for setting up a collector.
FromTheLeftCollector( n )
returns an empty data structure for a collector with n generators. No generator has a relative order, no right hand sides of power and conjugate relations are defined. Two generators for which no right hand side of a conjugate relation is defined commute. Therefore, the collector returned by this function can be used to define a free abelian group of rank n.
gap> ftl := FromTheLeftCollector( 4 ); <<from the left collector with 4 generators>> gap> PcpGroupByCollector( ftl ); Pcp-group with orders [ 0, 0, 0, 0 ] gap> IsAbelian(last); true
If the relative order of a generators has been defined (see SetRelativeOrder), but the right hand side of the corresponding power relation has not, then the order and the relative order of the generator are the same.
SetRelativeOrder( coll, i, ro )
SetRelativeOrderNC( coll, i, ro )
set the relative order in collector coll for generator i to ro. The parameter coll is a collector as returned by the function FromTheLeftCollector, i is a generator number and ro is a non-negative integer. The generator number i is an integer in the range 1,...,n where n is the number of generators of the collector.
If ro is 0, then the generator with number i has infinite order and no power relation can be specified. As a side effect in this case, a previously defined power relation is deleted.
If ro is the relative order of a generator with number i and no power relation is set for that generator, then ro is the order of that generator.
The NC version of the function bypasses checks on the range of i.
gap> ftl := FromTheLeftCollector( 4 ); <<from the left collector with 4 generators>> gap> for i in [1..4] do SetRelativeOrder( ftl, i, 3 ); od; gap> G := PcpGroupByCollector( ftl ); Pcp-group with orders [ 3, 3, 3, 3 ] gap> IsElementaryAbelian( G ); true
SetPower( coll, i, rhs )
SetPowerNC( coll, i, rhs )
set the right hand side of the power relation for generator i in collector coll to (a copy of) rhs. An attempt to set the right hand side for a generator without a relative order results in an error.
Right hand sides are by default assumed to be trivial.
The parameter coll is a collector, i is a generator number and rhs is a generators exponent list or an element from a free group.
The no-check (NC) version of the function bypasses checks on the range of i and stores rhs (instead of a copy) in the collector.
SetConjugate( coll, j, i, rhs )
SetConjugateNC( coll, j, i, rhs )
set the right hand side of the conjugate relation for the generators j and i with j larger than i. The parameter coll is a collector, j and i are generator numbers and rhs is a generator exponent list or an element from a free group. Conjugate relations are by default assumed to be trivial.
The generator number i can be negative in order to define conjugation by the inverse of a generator.
The no-check (NC) version of the function bypasses checks on the range of i and j and stores rhs (instead of a copy) in the collector.
SetCommutator( coll, j, i, rhs )
set the right hand side of the conjugate relation for the generators j and i with j larger than i by specifying the commutator of j and i. The parameter coll is a collector, j and i are generator numbers and rhs is a generator exponent list or an element from a free group.
The generator number i can be negative in order to define the right hand side of a commutator relation with the second generator being the inverse of a generator.
UpdatePolycyclicCollector( coll )
completes the data structures of a collector. This is usually the last step in setting up a collector. Among the steps performed is the completion of the conjugate relations. For each non-trivial conjugate relation of a generator, the corresponding conjugate relation of the inverse generator is calculated.
Note that UpdatePolycyclicCollector is automatically called by the
function PcpGroupByCollector (see PcpGroupByCollector).
IsConfluent( coll )
tests if the collector coll is confluent. The function returns true or false accordingly.
Compare Chapter introduction to polycyclic presentations for a definition of confluence.
Note that confluence is automatically checked by the function
PcpGroupByCollector (see PcpGroupByCollector).
The following example defines a collector for a semidirect product of the cyclic group of order 3 with the free abelian group of rank 2. The action of the cyclic group on the free abelian group is given by the matrix
pmatrix 0 1
-1 -1.
This leads to the following polycyclic presentation:
langleg1,g2,g3 | g13, g2g_1=g3, g3g_1=g2-1g3-1, g3g_2=g3rangle.
gap> ftl := FromTheLeftCollector( 3 ); <<from the left collector with 3 generators>> gap> SetRelativeOrder( ftl, 1, 3 ); gap> SetConjugate( ftl, 2, 1, [3,1] ); gap> SetConjugate( ftl, 3, 1, [2,-1,3,-1] ); gap> UpdatePolycyclicCollector( ftl ); gap> IsConfluent( ftl ); true
The action of the inverse of g1 on langleg2,g2rangle is given by the matrix
pmatrix -1 -1
1 0. The
corresponding conjugate relations are automatically computed by
UpdatePolycyclicCollector. It is also possible to specify the
conjugation by inverse generators. Note that you need to run
UpdatePolycyclicCollector after one of the set functions has been
used.
gap> SetConjugate( ftl, 2, -1, [2,-1,3,-1] ); gap> SetConjugate( ftl, 3, -1, [2,1] ); gap> IsConfluent( ftl ); Error, Collector is out of date called from CollectWordOrFail( coll, ev1, [ j, 1, i, 1 ] ); called from <function>( <arguments> ) called from read-eval-loop Entering break read-eval-print loop ... you can 'quit;' to quit to outer loop, or you can 'return;' to continue brk> gap> UpdatePolycyclicCollector( ftl ); gap> IsConfluent( ftl ); true
RelativeOrders( coll )
returns (a copy of) the list of relative order stored in the collector coll.
GetPower( coll, i )
GetPowerNC( coll, i )
returns a copy of the generator exponent list stored for the right hand side of the power relation of the generator i in the collector coll.
The no-check (NC) version of the function bypasses checks on the range of i and does not create a copy before returning the right hand side of the power relation.
GetConjugate( coll, j, i )
GetConjugateNC( coll, j, i )
returns a copy of the right hand side of the conjugate relation stored for the generators j and i in the collector coll as generator exponent list. The generator j must be larger than i.
The no-check (NC) version of the function bypasses checks on the range of i and j and does not create a copy before returning the right hand side of the power relation.
NumberOfGenerators( coll )
returns the number of generators of the collector coll.
ObjByExponents( coll, expvec )
returns a generator exponent list for the exponent vector expvec.
This is the inverse operation to ExponentsByObj. See
ExponentsByObj (ExponentsByObj) for an example.
ExponentsByObj( coll, genexp )
returns an exponent vector for the generator exponent list genexp.
This is the inverse operation to ObjByExponents.
gap> G := UnitriangularPcpGroup( 4, 0 ); Pcp-group with orders [ 0, 0, 0, 0, 0, 0 ] gap> coll := Collector ( G ); <<from the left collector with 6 generators>> gap> ObjByExponents( coll, [6,-5,4,3,-2,1] ); [ 1, 6, 2, -5, 3, 4, 4, 3, 5, -2, 6, 1 ] gap> ExponentsByObj( coll, last ); [ 6, -5, 4, 3, -2, 1 ]
In this section we descibe collectors for nilpotent groups which make use of the special structure of the given pc-presentation.
IsWeightedCollector( coll )
checks if there is a function w from the generators of the collector coll into the positive integers such that w(g) geqw(x)+w(y) for all generators x, y and all generators g in (the normal of) [x,y]. If such a function does not exist, false is returned. If such a function exists, it is computed and stored in the collector. In addition, the default collection strategy for this collector is set to combinatorial collection.
AddHallPolynomials( coll )
is applicable to a collector which passes IsWeightedCollector and
computes the Hall multiplication polynomials for the presentation
stored in coll. The default strategy for this collector is set to
evaluating those polynomial when multiplying two elements.
String( coll )
converts a collector coll into a string.
FTLCollectorPrintTo( file, name, coll )
stores a collector coll in the file file such that the file can be read back using the function 'Read' into GAP and would then be stored in the variable name.
FTLCollectorAppendTo( file, name, coll )
appends a collector coll in the file file such that the file can be read back into GAP and would then be stored in the variable name.
UseLibraryCollector
this property can be set to true for a collector to force a simple
from-the-left collection strategy implemented in the GAP language
to be used. Its main purpose is to help debug the collection
routines.
USE_LIBRARY_COLLECTOR
this global variable can be set to true to force all collectors to
use a simple from-the-left collection strategy implemented in the
GAP language to be used. Its main purpose is to help debug the
collection routines.
DEBUG_COMBINATORIAL_COLLECTOR
this global variable can be set to true to force the comparison of
results from the combinatorial collector with the result of an
identical collection performed by a simple from-the-left collector.
Its main purpose is to help debug the collection routines.
USE_COMBINATORIAL_COLLECTOR
this global variable can be set to false in order to prevent the
combinatorial collector to be used.
[Up] [Previous] [Next] [Index]
Polycyclic manual