<html><head><title>[Polycyclic] 3 Collectors</title></head> <body text="#000000" bgcolor="#ffffff"> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP002.htm">Previous</a>] [<a href ="CHAP004.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <h1>3 Collectors</h1><p> <P> <H3>Sections</H3> <oL> <li> <A HREF="CHAP003.htm#SECT001">Constructing a Collector</a> <li> <A HREF="CHAP003.htm#SECT002">Accessing Parts of a Collector</a> <li> <A HREF="CHAP003.htm#SECT003">Special Features</a> </ol><p> <p> Let <var>G</var> be a group defined by a pc-presentation as described in the Chapter <a href="CHAP002.htm">Introduction to polycyclic presentations</a>. <p> The process for computing the collected form for an arbitrary word in the generators of <var>G</var> is called <strong>collection</strong>. 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 <var>g<sub>i</sub><sup>e_i</sup></var> with <var>iinI</var> and <var>e<sub>i</sub></var> not in the range <var>0...r<sub>i-1</sub></var>. 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 <var>g<sub>i</sub></var> into the required range. These steps are repeated until a collected word is obtained. <p> There exist a number of different strategies for collecting a given word to collected form. The strategies implemented in this package are <strong>collection from the left</strong> as described by <a href="biblio.htm#LGS90"><cite>LGS90</cite></a> and <a href="biblio.htm#Sims94"><cite>Sims94</cite></a> and <strong>combinatorial collection from the left</strong> by <a href="biblio.htm#MVL90"><cite>MVL90</cite></a>. In addition, the package provides access to Hall polynomials computed by Deep Thought for the multiplication in a nilpotent group, see <a href="biblio.htm#WWM97"><cite>WWM97</cite></a> and <a href="biblio.htm#LGS98"><cite>LGS98</cite></a>. <p> 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 <strong>a collector</strong>. <p> To describe the right hand sides of the relations in a pc-presentation we use <strong>generator exponent lists</strong>; the word <var>g<sub>i_1</sub><sup>e_1</sup>g<sub>i_2</sub><sup>e_2</sup>...g<sub>i_k</sub><sup>e_k</sup></var> is represented by the generator exponent list <var>[i<sub>1</sub>,e<sub>1</sub>,i<sub>2</sub>,e<sub>2</sub>,...,i<sub>k</sub>,e<sub>k</sub>]</var>. <p> <p> <h2><a name="SECT001">3.1 Constructing a Collector</a></h2> <p><p> 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. <p> <a name = "SSEC001.1"></a> <li><code>FromTheLeftCollector( </code><var>n</var><code> )</code> <p> returns an empty data structure for a collector with <var>n</var> 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 <var>n</var>. <p> <pre> 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 </pre> <p> If the relative order of a generators has been defined (see <a href="CHAP003.htm#SSEC001.2">SetRelativeOrder</a>), 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. <p> <a name = "SSEC001.2"></a> <li><code>SetRelativeOrder( </code><var>coll</var><code>, </code><var>i</var><code>, </code><var>ro</var><code> )</code> <a name = "SSEC001.2"></a> <li><code>SetRelativeOrderNC( </code><var>coll</var><code>, </code><var>i</var><code>, </code><var>ro</var><code> )</code> <p> set the relative order in collector <var>coll</var> for generator <var>i</var> to <var>ro</var>. The parameter <var>coll</var> is a collector as returned by the function <a href="CHAP003.htm#SSEC001.1">FromTheLeftCollector</a>, <var>i</var> is a generator number and <var>ro</var> is a non-negative integer. The generator number <var>i</var> is an integer in the range <var>1,...,n</var> where <var>n</var> is the number of generators of the collector. <p> If <var>ro</var> is <var>0,</var> then the generator with number <var>i</var> has infinite order and no power relation can be specified. As a side effect in this case, a previously defined power relation is deleted. <p> If <var>ro</var> is the relative order of a generator with number <var>i</var> and no power relation is set for that generator, then <var>ro</var> is the order of that generator. <p> The NC version of the function bypasses checks on the range of <var>i</var>. <p> <pre> 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 </pre> <p> <a name = "SSEC001.3"></a> <li><code>SetPower( </code><var>coll</var><code>, </code><var>i</var><code>, </code><var>rhs</var><code> )</code> <a name = "SSEC001.3"></a> <li><code>SetPowerNC( </code><var>coll</var><code>, </code><var>i</var><code>, </code><var>rhs</var><code> )</code> <p> set the right hand side of the power relation for generator <var>i</var> in collector <var>coll</var> to (a copy of) <var>rhs</var>. An attempt to set the right hand side for a generator without a relative order results in an error. <p> Right hand sides are by default assumed to be trivial. <p> The parameter <var>coll</var> is a collector, <var>i</var> is a generator number and <var>rhs</var> is a generators exponent list or an element from a free group. <p> The no-check (NC) version of the function bypasses checks on the range of <var>i</var> and stores <var>rhs</var> (instead of a copy) in the collector. <p> <a name = "SSEC001.4"></a> <li><code>SetConjugate( </code><var>coll</var><code>, </code><var>j</var><code>, </code><var>i</var><code>, </code><var>rhs</var><code> )</code> <a name = "SSEC001.4"></a> <li><code>SetConjugateNC( </code><var>coll</var><code>, </code><var>j</var><code>, </code><var>i</var><code>, </code><var>rhs</var><code> )</code> <p> set the right hand side of the conjugate relation for the generators <var>j</var> and <var>i</var> with <var>j</var> larger than <var>i</var>. The parameter <var>coll</var> is a collector, <var>j</var> and <var>i</var> are generator numbers and <var>rhs</var> is a generator exponent list or an element from a free group. Conjugate relations are by default assumed to be trivial. <p> The generator number <var>i</var> can be negative in order to define conjugation by the inverse of a generator. <p> The no-check (NC) version of the function bypasses checks on the range of <var>i</var> and <var>j</var> and stores <var>rhs</var> (instead of a copy) in the collector. <p> <a name = "SSEC001.5"></a> <li><code>SetCommutator( </code><var>coll</var><code>, </code><var>j</var><code>, </code><var>i</var><code>, </code><var>rhs</var><code> )</code> <p> set the right hand side of the conjugate relation for the generators <var>j</var> and <var>i</var> with <var>j</var> larger than <var>i</var> by specifying the commutator of <var>j</var> and <var>i</var>. The parameter <var>coll</var> is a collector, <var>j</var> and <var>i</var> are generator numbers and <var>rhs</var> is a generator exponent list or an element from a free group. <p> The generator number <var>i</var> 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. <p> <a name = "SSEC001.6"></a> <li><code>UpdatePolycyclicCollector( </code><var>coll</var><code> )</code> <p> 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. <p> Note that <code>UpdatePolycyclicCollector</code> is automatically called by the function <code>PcpGroupByCollector</code> (see <a href="CHAP004.htm#SSEC003.1">PcpGroupByCollector</a>). <p> <a name = "SSEC001.7"></a> <li><code>IsConfluent( </code><var>coll</var><code> )</code> <p> tests if the collector <var>coll</var> is confluent. The function returns true or false accordingly. <p> Compare Chapter <a href="CHAP002.htm">introduction to polycyclic presentations</a> for a definition of confluence. <p> Note that confluence is automatically checked by the function <code>PcpGroupByCollector</code> (see <a href="CHAP004.htm#SSEC003.1">PcpGroupByCollector</a>). <p> The following example defines a collector for a semidirect product of the cyclic group of order <var>3</var> with the free abelian group of rank <var>2</var>. The action of the cyclic group on the free abelian group is given by the matrix <p><var>pmatrix 0 1 <br>-1 -1.<p></var> This leads to the following polycyclic presentation: <p><var>langleg<sub>1</sub>,g<sub>2</sub>,g<sub>3</sub> | g<sub>1</sub><sup>3</sup>, g<sub>2</sub><sup>g_1</sup>=g<sub>3</sub>, g<sub>3</sub><sup>g_1</sup>=g<sub>2</sub><sup>-1</sup>g<sub>3</sub><sup>-1</sup>, g<sub>3</sub><sup>g_2</sup>=g<sub>3</sub>rangle.<p></var> <p> <pre> 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 </pre> <p> The action of the inverse of <var>g<sub>1</sub></var> on <var>langleg<sub>2</sub>,g<sub>2</sub>rangle</var> is given by the matrix <p><var>pmatrix -1 -1 <br>1 0.<p></var> The corresponding conjugate relations are automatically computed by <code>UpdatePolycyclicCollector</code>. It is also possible to specify the conjugation by inverse generators. Note that you need to run <code>UpdatePolycyclicCollector</code> after one of the set functions has been used. <p> <pre> 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 </pre> <p> <p> <h2><a name="SECT002">3.2 Accessing Parts of a Collector</a></h2> <p><p> <a name = "SSEC002.1"></a> <li><code>RelativeOrders( </code><var>coll</var><code> )</code> <p> returns (a copy of) the list of relative order stored in the collector <var>coll</var>. <p> <a name = "SSEC002.2"></a> <li><code>GetPower( </code><var>coll</var><code>, </code><var>i</var><code> )</code> <a name = "SSEC002.2"></a> <li><code>GetPowerNC( </code><var>coll</var><code>, </code><var>i</var><code> )</code> <p> returns a copy of the generator exponent list stored for the right hand side of the power relation of the generator <var>i</var> in the collector <var>coll</var>. <p> The no-check (NC) version of the function bypasses checks on the range of <var>i</var> and does not create a copy before returning the right hand side of the power relation. <p> <a name = "SSEC002.3"></a> <li><code>GetConjugate( </code><var>coll</var><code>, </code><var>j</var><code>, </code><var>i</var><code> )</code> <a name = "SSEC002.3"></a> <li><code>GetConjugateNC( </code><var>coll</var><code>, </code><var>j</var><code>, </code><var>i</var><code> )</code> <p> returns a copy of the right hand side of the conjugate relation stored for the generators <var>j</var> and <var>i</var> in the collector <var>coll</var> as generator exponent list. The generator <var>j</var> must be larger than <var>i</var>. <p> The no-check (NC) version of the function bypasses checks on the range of <var>i</var> and <var>j</var> and does not create a copy before returning the right hand side of the power relation. <p> <a name = "SSEC002.4"></a> <li><code>NumberOfGenerators( </code><var>coll</var><code> )</code> <p> returns the number of generators of the collector <var>coll</var>. <p> <a name = "SSEC002.5"></a> <li><code>ObjByExponents( </code><var>coll</var><code>, </code><var>expvec</var><code> )</code> <p> returns a generator exponent list for the exponent vector <var>expvec</var>. This is the inverse operation to <code>ExponentsByObj</code>. See <code>ExponentsByObj</code> (<a href="CHAP003.htm#SSEC002.6">ExponentsByObj</a>) for an example. <p> <a name = "SSEC002.6"></a> <li><code>ExponentsByObj( </code><var>coll</var><code>, </code><var>genexp</var><code> )</code> <p> returns an exponent vector for the generator exponent list <var>genexp</var>. This is the inverse operation to <code>ObjByExponents</code>. <p> <pre> 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 ] </pre> <p> <p> <h2><a name="SECT003">3.3 Special Features</a></h2> <p><p> In this section we descibe collectors for nilpotent groups which make use of the special structure of the given pc-presentation. <p> <a name = "SSEC003.1"></a> <li><code>IsWeightedCollector( </code><var>coll</var><code> )</code> <p> checks if there is a function <var>w</var> from the generators of the collector <var>coll</var> into the positive integers such that <var>w(g) geqw(x)+w(y)</var> for all generators <var>x</var>, <var>y</var> and all generators <var>g</var> in (the normal of) <var>[x,y]</var>. 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. <p> <a name = "SSEC003.2"></a> <li><code>AddHallPolynomials( </code><var>coll</var><code> )</code> <p> is applicable to a collector which passes <code>IsWeightedCollector</code> and computes the Hall multiplication polynomials for the presentation stored in <var>coll</var>. The default strategy for this collector is set to evaluating those polynomial when multiplying two elements. <p> <a name = "SSEC003.3"></a> <li><code>String( </code><var>coll</var><code> )</code> <p> converts a collector <var>coll</var> into a string. <p> <a name = "SSEC003.4"></a> <li><code>FTLCollectorPrintTo( </code><var>file</var><code>, </code><var>name</var><code>, </code><var>coll</var><code> )</code> <p> stores a collector <var>coll</var> in the file <var>file</var> such that the file can be read back using the function 'Read' into <font face="Gill Sans,Helvetica,Arial">GAP</font> and would then be stored in the variable <var>name</var>. <p> <a name = "SSEC003.5"></a> <li><code>FTLCollectorAppendTo( </code><var>file</var><code>, </code><var>name</var><code>, </code><var>coll</var><code> )</code> <p> appends a collector <var>coll</var> in the file <var>file</var> such that the file can be read back into <font face="Gill Sans,Helvetica,Arial">GAP</font> and would then be stored in the variable <var>name</var>. <p> <a name = "SSEC003.6"></a> <li><code>UseLibraryCollector</code> <p> this property can be set to <code>true</code> for a collector to force a simple from-the-left collection strategy implemented in the <font face="Gill Sans,Helvetica,Arial">GAP</font> language to be used. Its main purpose is to help debug the collection routines. <p> <a name = "SSEC003.7"></a> <li><code>USE_LIBRARY_COLLECTOR</code> <p> this global variable can be set to <code>true</code> to force all collectors to use a simple from-the-left collection strategy implemented in the <font face="Gill Sans,Helvetica,Arial">GAP</font> language to be used. Its main purpose is to help debug the collection routines. <p> <a name = "SSEC003.8"></a> <li><code>DEBUG_COMBINATORIAL_COLLECTOR</code> <p> this global variable can be set to <code>true</code> 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. <p> <a name = "SSEC003.9"></a> <li><code>USE_COMBINATORIAL_COLLECTOR</code> <p> this global variable can be set to <code>false</code> in order to prevent the combinatorial collector to be used. <p> <p> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP002.htm">Previous</a>] [<a href ="CHAP004.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <P> <address>Polycyclic manual<br>Februar 2009 </address></body></html>