%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Chapter{Collectors}

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\in I$ and $e_i$ not in the range $0\ldots 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 \cite{LGS90} and
\cite{Sims94} and *combinatorial collection from the left* by
\cite{MVL90}.  In addition, the package provides access to Hall
polynomials computed by Deep Thought for the multiplication in a
nilpotent group, see \cite{WWM97} and \cite{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_1}g_{i_2}^{e_2}\ldots g_{i_k}^{e_k}$ is represented by the
generator exponent list $[i_1,e_1,i_2,e_2,\ldots,i_k,e_k]$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Constructing a Collector}

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>.

\beginexample
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
\endexample

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,\ldots,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>.

\beginexample
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
\endexample


\>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 \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.$$

\beginexample
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
\endexample

The action of the inverse of $g_1$ on $\langle g_2,g_2\rangle$ 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. 

\beginexample
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
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Accessing Parts of a Collector}

\>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'.

\beginexample
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 ]
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Special Features}

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) \geq 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> )

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.