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 g_i^e_i with i∈ I and e_i not in the range 0... r_i-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 g_i 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 [Sim94] and combinatorial collection from the left by [VL90]. In addition, the package provides access to Hall polynomials computed by Deep Thought for the multiplication in a nilpotent group, see [Mer97] 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 g_i_1^e_1g_i_2^e_2... g_i_k^e_k is represented by the generator exponent list [i_1,e_1,i_2,e_2,...,i_k,e_k].
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 ) | ( operation ) |
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 (3.1-2)), 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 ) | ( operation ) |
‣ SetRelativeOrderNC( coll, i, ro ) | ( operation ) |
set the relative order in collector coll for generator i to ro. The parameter coll is a collector as returned by the function FromTheLeftCollector (3.1-1), 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 ) | ( operation ) |
‣ SetPowerNC( coll, i, rhs ) | ( operation ) |
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 ) | ( operation ) |
‣ SetConjugateNC( coll, j, i, rhs ) | ( operation ) |
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 ) | ( operation ) |
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 ) | ( operation ) |
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 (4.3-1)).
‣ IsConfluent( coll ) | ( property ) |
tests if the collector coll is confluent. The function returns true or false accordingly.
Compare Chapter 2 for a definition of confluence.
Note that confluence is automatically checked by the function PcpGroupByCollector (see PcpGroupByCollector (4.3-1)).
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 \cr -1 & -1}.
This leads to the following polycyclic presentation:
\langle g_1,g_2,g_3 | g_1^3, g_2^{g_1}=g_3, g_3^{g_1}=g_2^{-1}g_3^{-1}, g_3^{g_2}=g_3\rangle.
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 g_1 on ⟨ g_2,g_2⟩ is given by the matrix
\pmatrix{ -1 & -1 \cr 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 ) | ( attribute ) |
returns (a copy of) the list of relative order stored in the collector coll.
‣ GetPower( coll, i ) | ( operation ) |
‣ GetPowerNC( coll, i ) | ( operation ) |
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 ) | ( operation ) |
‣ GetConjugateNC( coll, j, i ) | ( operation ) |
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 ) | ( operation ) |
returns the number of generators of the collector coll.
‣ ObjByExponents( coll, expvec ) | ( operation ) |
returns a generator exponent list for the exponent vector expvec. This is the inverse operation to ExponentsByObj. See ExponentsByObj (3.2-6) for an example.
‣ ExponentsByObj( coll, genexp ) | ( operation ) |
returns an exponent vector for the generator exponent list genexp. This is the inverse operation to ObjByExponents. The function assumes that the generators in genexp are given in the right order and that the exponents are in the right range.
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 ) | ( property ) |
checks if there is a function w from the generators of the collector coll into the positive integers such that w(g) ≥ w(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 ) | ( function ) |
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 ) | ( attribute ) |
converts a collector coll into a string.
‣ FTLCollectorPrintTo( file, name, coll ) | ( function ) |
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 ) | ( function ) |
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 | ( global variable ) |
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 | ( global variable ) |
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 | ( global variable ) |
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 | ( global variable ) |
this global variable can be set to false in order to prevent the combinatorial collector to be used.
generated by GAPDoc2HTML