5 Module Polynomials
  
  In this chapter we consider finitely generated modules over the monoid rings
  considered   previously.  We  call  an  element  of  this  module  a  module
  polynomial,  and  we  describe functions to construct module polynomials and
  the standard algebraic operations for such polynomials.
  
  A  module  polynomial modpoly is recorded as a list of pairs, [ gen, monpoly
  ],  where gen is a module generator (basis element), and monpoly is a monoid
  polynomial.  The  module  polynomial  is printed as the formal sum of monoid
  polynomial multiples of the generators. Note that the monoid polynomials are
  the  coefficients  of  the module polynomials and appear to the right of the
  generator, as we choose to work with right modules.
  
  The  examples  we  are aiming for are the identities among the relators of a
  finitely presented group (see section 5.4).
  
  
  5.1 Construction of module polynomials
  
  5.1-1 ModulePoly
  
  > ModulePoly( gens, monpolys ) ____________________________________operation
  > ModulePoly( args ) ______________________________________________operation
  > ZeroModulePoly( Fgens, Fmon ) ___________________________________operation
  
  The  function  ModulePoly  returns  a  module  polynomial.  The terms of the
  polynomial  maybe input as a list of generators followed by a list of monoid
  polynomials or as one list of [generator, monoid polynomial] pairs.
  
  Assuming  that  Fgens is the free group on the module generators and Fmon is
  the free group on the monoid generators, the function ZeroModulePoly returns
  the  zero  module  polynomial,  which has no terms, and is an element of the
  module.
  
  ---------------------------  Example  ----------------------------
    
    gap> frq8 := FreeRelatorGroup( q8 );; 
    gap> genfrq8 := GeneratorsOfGroup( frq8 ); 
    [ q8_R1, q8_R2, q8_R3, q8_R4 ]
    gap> Display( rmp1 ); 
     - 7*q8_M4 + 5*q8_M1 + 9*<identity ...>
    gap> mp2 := MonoidPolyFromCoeffsWords( [4,-5], [ M[4], M[1] ] );;
    gap> Display( mp2 ); 
    4*q8_M4 - 5*q8_M1
    gap> s1 := ModulePoly( [ genfrq8[4], genfrq8[1] ], [ rmp1, mp2 ] );
    q8_R1*(4*q8_M4 - 5*q8_M1) + q8_R4*( - 7*q8_M4 + 5*q8_M1 + 9*<identity ...>)
    gap> s2 := ModulePoly( [ genfrq8[3], genfrq8[2], genfrq8[1] ], 
    gap>    [ -1*rmp1, 3*mp2, (rmp1+mp2) ] );
    q8_R1*( - 3*q8_M4 + 9*<identity ...>) + q8_R2*(12*q8_M4 - 15*q8_M1) + q8_R3*(
    7*q8_M4 - 5*q8_M1 - 9*<identity ...>)
    gap> zeromp := ZeroModulePoly( frq8, freeq8 );
    zero modpoly
    
  ------------------------------------------------------------------
  
  
  5.2 Components of a module polynomial
  
  5.2-1 Terms
  
  > Terms( modpoly ) ________________________________________________attribute
  > LeadTerm( modpoly ) _____________________________________________attribute
  > LeadMonoidPoly( modpoly ) _______________________________________attribute
  > One( modpoly ) __________________________________________________attribute
  > Length( modpoly ) _______________________________________________attribute
  
  The  first  function  counts  the number of module generators which occur in
  modpoly  (a generator occurs in a polynomial if it has nonzero coefficient).
  The function One returns the identity in the free group on the generators.
  
  The  function  Terms  returns  the terms of a module polynomial as a list of
  pairs. In LeadTerm, the generators are ordered, and the term of modpoly with
  the  highest  value  generator is defined to be the leading term. The monoid
  polynomial  (coefficient)  part  of  the  leading  term  is  returned by the
  function LeadMonoidPoly.
  
  ---------------------------  Example  ----------------------------
    
    gap> [ Length(s1), Length(s2) ];
    [ 2, 3 ]
    gap> One( s1 );
    <identity ...> 
    gap> Terms( s1 );
    [ [ q8_R1, <monpoly> ], [ q8_R4, <monpoly> ] ]
    gap> Display( LeadTerm( s1 ) );
    [ q8_R4,
       - 7*q8_M4 + 5*q8_M1 + 9*<identity ...>
      ]
    gap> Display( LeadTerm( s2 ) );
    [ q8_R3,
      7*q8_M4 - 5*q8_M1 - 9*<identity ...>
      ]
    gap> Display( LeadMonoidPoly( s1 ) );
     - 7*q8_M4 + 5*q8_M1 + 9*<identity ...>
    gap> Display( LeadMonoidPoly( s2 ) );
    7*q8_M4 - 5*q8_M1 - 9*<identity ...>
    
  ------------------------------------------------------------------
  
  
  5.3 Module Polynomial Operations
  
  5.3-1 AddTermModulePoly
  
  > AddTermModulePoly( modpoly, gen, monpoly ) ______________________operation
  
  The  function  AddTermModulePoly  adds  a  term  [gen,  monpoly] to a module
  polynomial modpoly.
  
  Tests for equality and arithmetic operations are performed in the usual way.
  Module  polynomials may be added or subtracted. A module polynomial can also
  be  multiplied  on the right by a word or by a scalar. The effect of this is
  to  multiply the monoid polynomial parts of each term by the word or scalar.
  This is made clearer in the example.
  
  ---------------------------  Example  ----------------------------
    
    gap> mp0 := MonoidPolyFromCoeffsWords( [6], [ M[2] ] );;
    gap> Display(mp0);
    6*q8_M2
    gap> s0 := AddTermModulePoly( s1, genfrq8[3], mp0 ); 
    q8_R1*(4*q8_M4 - 5*q8_M1) + q8_R3*(6*q8_M2) + q8_R4*( - 7*q8_M4 + 5*q8_M1 +
    9*<identity ...>)
    gap> Display( s1 + s2 );
    q8_R1*( q8_M4 - 5*q8_M1 + 9*<identity ...>) + q8_R2*(12*q8_M4 -
    15*q8_M1) + q8_R3*(7*q8_M4 - 5*q8_M1 - 9*<identity ...>) + q8_R4*( -
    7*q8_M4 + 5*q8_M1 + 9*<identity ...>)
    gap> Display( s1 - s0 );
    q8_R3*( - 6*q8_M2)
    gap> Display( s1 * 1/2 );
    q8_R1*(2*q8_M4 - 5/2*q8_M1) + q8_R4*( - 7/2*q8_M4 + 5/2*q8_M1 + 9/
    2*<identity ...>)
    gap> Display( s1 * M[1] );
    q8_R1*(4*q8_M4*q8_M1 - 5*q8_M1^2) + q8_R4*( - 7*q8_M4*q8_M1 + 5*q8_M1^2 +
    9*q8_M1)
    
  ------------------------------------------------------------------
  
  
  5.4 Identities among relators
  
  5.4-1 IdentityYSequences
  
  > IdentityYSequences( grp ) _______________________________________attribute
  > IdentityModulePolynomials( grp ) ________________________________operation
  > IdentitiesAmongRelators( grp ) __________________________________attribute
  
  The  identities  among  the  relators  for  a  finitely  presented group are
  constructed as logged module polynomials. The procedure, described in [HW03]
  and  based  on work in [BS99], is to construct a full set of Y-sequences for
  the   group;  convert  these  into  module  polynomials  (eliminating  empty
  sequences);  and  then  apply  simplification  rules  (including the primary
  identity property) to eliminate obvious duplicates and conjugates.
  
  It  is not guaranteed that a minimal set of identities is obtained. For q8 a
  set  of  seven  identities  is obtained, whereas a minimal set contains only
  six. See Example 5.1 of [HW03] for further details.
  
  ---------------------------  Example  ----------------------------
    
    gap> yseqs := IdentityYSequences( q8 );;
    gap> Length( yseqs );
    32
    gap> polys := IdentityModulePolys( q8 );;
    gap> Length( polys );
    22
    gap> idsq8 := IdentitiesAmongRelators( q8 );;
    gap> Length( idsq8 );
    2
    gap> Length( idsq8[1] );
    7
    gap> Display( idsq8[1] );
    [ ( q8_Y3*( q8_M1*q8_M4), q8_R1*( q8_M1 - <identity ...>) ),
      ( q8_Y10*( -q8_M1*q8_M4), q8_R2*( q8_M2 - <identity ...>) ),
      ( q8_Y17*( <identity ...>), q8_R1*( -q8_M3 - q8_M2) + q8_R3*( q8_M1^
    2 + q8_M3 + q8_M1 + <identity ...>) ),
      ( q8_Y31*( q8_M1*q8_M4), q8_R3*( q8_M3 - q8_M2) + q8_R4*( q8_M1 - <identity \
    ...>) ),
      ( q8_Y32*( -q8_M1*q8_M4), q8_R2*( -q8_M1^
    2) + q8_R3*( -q8_M3 - <identity ...>) + q8_R4*( q8_M2 + <identity ...>) ),
      ( q8_Y12*( q8_M1*q8_M4), q8_R1*( -q8_M2) + q8_R3*( q8_M1*q8_M2 + q8_M4) + q8\
    _R4*( q8_M2 - <identity ...>) ),
      ( q8_Y16*( -<identity ...>), q8_R1*( -<identity ...>) + q8_R2*( -q8_M1) + q8\
    _R4*( q8_M3 + q8_M1) )
      ]
    
  ------------------------------------------------------------------
  
  5.4-2 RootIdentities
  
  > RootIdentities( grp ) ___________________________________________attribute
  
  The  root  identities  are identities of the form r^wr^-1 where r = w^n is a
  relator and n>1.
  
  For  q8 only two of the four relators are proper powers, q=a^4 and r=b^4, so
  the root identities are q^aq^-1 and r^br^-1.
  
  ---------------------------  Example  ----------------------------
    
    gap> RootIdentities( q8 );
    [ ( q8_Y3*( q8_M1*q8_M4), q8_R1*( q8_M1 - <identity ...>) ),
      ( q8_Y10*( -q8_M1*q8_M4), q8_R2*( q8_M2 - <identity ...>) ) ]
    gap> RootIdentities(s3);
    [ ( s3_Y4*( s3_M2*s3_M1), s3_R1*( s3_M1 - <identity ...>) ),
      ( s3_Y8*( s3_M2*s3_M1), s3_R2*( s3_M2 - <identity ...>) ),
      ( s3_Y7*( s3_M2*s3_M1), s3_R3*( s3_M2 - s3_M1) ) ]
    
  ------------------------------------------------------------------