/usr/share/gap/pkg/Polycyclic/doc/chap3.txt

  
  3 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∈ 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].
  
  
  3.1 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.
  
  3.1-1 FromTheLeftCollector
  
  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.
  
    Example  
    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.
  
  3.1-2 SetRelativeOrder
  
  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.
  
    Example  
    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
  
  
  3.1-3 SetPower
  
  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.
  
  3.1-4 SetConjugate
  
  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.
  
  3.1-5 SetCommutator
  
  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.
  
  3.1-6 UpdatePolycyclicCollector
  
  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)).
  
  3.1-7 IsConfluent
  
  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.
  
  
  
    Example  
    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[122⟩X 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.
  
    Example  
    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
  
  
  
  3.2 Accessing Parts of a Collector
  
  3.2-1 RelativeOrders
  
  RelativeOrders( coll )  attribute
  
  returns (a copy of) the list of relative order stored in the collector coll.
  
  3.2-2 GetPower
  
  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.
  
  3.2-3 GetConjugate
  
  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.
  
  3.2-4 NumberOfGenerators
  
  NumberOfGenerators( coll )  operation
  
  returns the number of generators of the collector coll.
  
  3.2-5 ObjByExponents
  
  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.
  
  3.2-6 ExponentsByObj
  
  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.
  
    Example  
    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 ]
  
  
  
  3.3 Special Features
  
  In this section we descibe collectors for nilpotent groups which make use of
  the special structure of the given pc-presentation.
  
  3.3-1 IsWeightedCollector
  
  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.
  
  3.3-2 AddHallPolynomials
  
  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.
  
  3.3-3 String
  
  String( coll )  attribute
  
  converts a collector coll into a string.
  
  3.3-4 FTLCollectorPrintTo
  
  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.
  
  3.3-5 FTLCollectorAppendTo
  
  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.
  
  3.3-6 UseLibraryCollector
  
  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.
  
  3.3-7 USE_LIBRARY_COLLECTOR
  
  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.
  
  3.3-8 DEBUG_COMBINATORIAL_COLLECTOR
  
  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.
  
  3.3-9 USE_COMBINATORIAL_COLLECTOR
  
  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 dwww version 1.15 on Sun Jun 16 10:10:46 CEST 2024.