  
  [1m[4m[31m5. Module Polynomials[0m
  
  In this chapter we consider finitely generated modules over the monoid rings
  considered   previously.  We  call  an  element  of  this  module  a  [22m[36mmodule
  polynomial[0m,  and  we  describe functions to construct module polynomials and
  the standard algebraic operations for such polynomials.
  
  A  module  polynomial [22m[32mmodpoly[0m is recorded as a list of pairs, [22m[32m[ gen, monpoly
  ][0m,  where [22m[32mgen[0m is a module generator (basis element), and [22m[32mmonpoly[0m 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 [1m[46m5.4[0m).
  
  
  [1m[4m[31m5.1 Construction of module polynomials[0m
  
  [1m[4m[31m5.1-1 ModulePoly[0m
  
  [1m[34m> ModulePoly( [0m[22m[34mgens, monpolys[0m[1m[34m ) ____________________________________[0moperation
  [1m[34m> ModulePoly( [0m[22m[34margs[0m[1m[34m ) ______________________________________________[0moperation
  
  This function 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 [22m[32m[generator, monoid polynomial][0m pairs.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> frq8 := FreeRelatorGroup( q8 );[0m
    [22m[35mq8_R [0m
    [22m[35mgap> genfrq8 := GeneratorsOfGroup( frq8 );[0m
    [22m[35m[ q8_R1, q8_R2, q8_R3, q8_R4 ] [0m
    [22m[35mgap> mp1 := MonoidPolyFromCoeffsWords( [3,2,-5], [M[1]*M[3], M[2]^4, M[1] ] );[0m
    [22m[35m<monpoly> [0m
    [22m[35mgap> Print( mp1 );[0m
    [22m[35m2*q8_M2^4 + 3*q8_M1*q8_M3 _ 5*q8_M1 [0m
    [22m[35mgap> mp2 := MonoidPolyFromCoeffsWords( [1,-4,-1,2], [0m
    [22m[35m       [ M[2]*M[3]*M[1], M[3]^3, M[1]*M[2], M[4] ] [0m
    [22m[35m<monpoly> [0m
    [22m[35mgap> Print( mp2 );[0m
    [22m[35m- 4*q8_M3^3 + q8_M2*q8_M3*q8_M1 - q8_M1*q8_M2 + 2*q8_M4 [0m
    [22m[35mgap> s1 := ModulePoly( [ genfrq8[4] , genfrq8[1] ], [mp1, mp2 ] );[0m
    [22m[35m<modpoly> [0m
    [22m[35mgap> Print( s1 );[0m
    [22m[35mq8_R1*( - 4*q8_M3^3 + q8_M2*q8_M3*q8_M1 - q8_M1*q8_M2 + 2*q8_M4) [0m
    [22m[35m  + q8_R4*( 2*q8_M2^4 + 3*q8_M1*q8_M3 - 5*q8_M1) [0m
    [22m[35mgap> s2 := ModulePoly( [ genfrq8[3], genfrq8[2], genfrq8[1] ], [3*mp1, -1*mp2,\[0m
    [22m[35m (mp1+mp2) ] );[0m
    [22m[35m<modpoly> [0m
    [22m[35mgap> Print( s2 );[0m
    [22m[35mq8_R1*(2*q8_M2^4 - 4*q8_M3^3 + q8_M2*q8_M3*q8_M1  + 3*q8_M1*q8_M3 [0m
    [22m[35m  - q8_M1*q8_M2 + 2*q8_M4 - 5*q8_M1) + q8_R2*(4*q8_M3^3 - q8_M2*q8_M3*q8_M1 [0m
    [22m[35m  + q8_M1*q8_M2 - 2*q8_M4) + q8_R3*(6*q8_M2^4 + 9*q8_M1*q8_M3 - 15*q8_M1) [0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  
  [1m[4m[31m5.2 Components of a module polynomial[0m
  
  [1m[4m[31m5.2-1 Terms[0m
  
  [1m[34m> Terms( [0m[22m[34mmodpoly[0m[1m[34m ) ________________________________________________[0mattribute
  [1m[34m> LeadTerm( [0m[22m[34mmodpoly[0m[1m[34m ) _____________________________________________[0mattribute
  [1m[34m> LeadMonoidPoly( [0m[22m[34mmodpoly[0m[1m[34m ) _______________________________________[0mattribute
  [1m[34m> One( [0m[22m[34mmodpoly[0m[1m[34m ) __________________________________________________[0mattribute
  [1m[34m> Length( [0m[22m[34mmodpoly[0m[1m[34m ) _______________________________________________[0mattribute
  
  The  first  function  counts  the number of module generators which occur in
  [22m[32mmodpoly[0m  (a generator occurs in a polynomial if it has nonzero coefficient).
  The function [22m[32mOne[0m returns the identity in the free group on the generators.
  
  The  function  [22m[32mTerms[0m  returns  the terms of a module polynomial as a list of
  pairs. In [22m[32mLeadTerm[0m, the generators are ordered, and the term of [22m[32mmodpoly[0m 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 [22m[32mLeadMonoidPoly[0m.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> Length(s1);[0m
    [22m[35m2 [0m
    [22m[35mgap> Length(s2);[0m
    [22m[35m3[0m
    [22m[35mgap> One( s1 ); [0m
    [22m[35m<identity ...>[0m
    [22m[35mgap> Terms( s1 );[0m
    [22m[35m[ [ q8_R1,  - 4*q8_M3^3 + q8_M2*q8_M3*q8_M1 - q8_M1*q8_M2 + 2*q8_M4 ],[0m
    [22m[35m  [ q8_R4, 2*q8_M2^4 + 3*q8_M1*q8_M3 - 5*q8_M1 ] ][0m
    [22m[35mgap> Terms( s2 );[0m
    [22m[35m[ [ q8_R1, 2*q8_M2^4 - 4*q8_M3^3 + q8_M2*q8_M3*q8_M1 + 3*q8_M1*q8_M3 - q8_M1*q8_M\[0m
    [22m[35m2 + 2*q8_M4 - 5*q8_M1 ],[0m
    [22m[35m  [ q8_R2, 4*q8_M3^3 - q8_M2*q8_M3*q8_M1 + q8_M1*q8_M2 - 2*q8_M4 ],[0m
    [22m[35m  [ q8_R3, 6*q8_M2^4 + 9*q8_M1*q8_M3 - 15*q8_M1 ] ][0m
    [22m[35mgap> LeadTerm( s1 ); [0m
    [22m[35m[ q8_R4, <monpoly> ] [0m
    [22m[35mgap> LeadTerm( s2 ); [0m
    [22m[35m[ q8_R3, <monpoly> ] [0m
    [22m[35mgap> Print( LeadMonoidPoly( s1 ) );[0m
    [22m[35m2*q8_M2^4 + 3*q8_M1*q8_M3 - 5*q8_M1 [0m
    [22m[35mgap> Print( LeadMonoidPoly( s2 ) ); [0m
    [22m[35m6*q8_M2^4 + 9*q8_M1*q8_M3 - 15*q8_M1 [0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m5.2-2 ZeroModulePoly[0m
  
  [1m[34m> ZeroModulePoly( [0m[22m[34mFgens, Fmon[0m[1m[34m ) ___________________________________[0moperation
  
  Assuming  that  [22m[32mFgens[0m is the free group on the module generators and [22m[32mFmon[0m is
  the free group on the monoid generators, then this function returns the zero
  module polynomial, which has no terms, and is an element of the module.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> zeromp := ZeroModulePoly( frel, freeq8 );[0m
    [22m[35m<modpoly> [0m
    [22m[35mgap> Print( zeromp );[0m
    [22m[35mzero modpoly[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m5.2-3 AddTermModulePoly[0m
  
  [1m[34m> AddTermModulePoly( [0m[22m[34mmodpoly, gen, monpoly[0m[1m[34m ) ______________________[0moperation
  
  This function adds a term [22m[32m[gen, monpoly][0m to a module polynomial [22m[32mmodpoly[0m.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> s3 := AddTermModulePoly( s1, frelgen[3], mp1 );[0m
    [22m[35m<modpoly> [0m
    [22m[35mgap> Print( s3 );[0m
    [22m[35mq8_Rl*( - 4*q8_M3^3 + q8_M2*q8_M3*q8_Ml - q8_Ml*q8_M2 + 2*q8_M4) [0m
    [22m[35m  + q8_R3*( 2*q8_M2^4 + 3*q8_Ml*q8_M3 - 5*q8_Ml) [0m
    [22m[35m  + q8_R4*(2*q8_M2^4 + 3*q8_Ml*q8_M35*q8_Ml)[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  
  [1m[4m[31m5.3 Module Polynomial Operations[0m
  
  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.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> Print( s1 );[0m
    [22m[35mq8_Rl*( - 4*q8_M3^3 + q8_M2*q8_M3*q8_Ml - q8_Ml*q8_M2 + 2*q8_M4) [0m
    [22m[35m  + q8_R4*( 2*q8_M2^4 + 3*q8_Ml*q8_M3 _ 5*q8_Ml) [0m
    [22m[35mgap> Print( s2 );[0m
    [22m[35mq8_Rl*(2*q8_M2^4 - 4*q8_M3^3 + q8_M2*q8_M3*q8_Ml + 3*q8_Ml*q8_M3 [0m
    [22m[35m    - q8_Ml*q8_M2 + 2*q8_M4 - 5*q8_Ml) [0m
    [22m[35m  + q8_R2*(4*q8_M3^ 3 - q8_M2*q8_M3*q8_Ml + q8_Ml*q8_M2 - 2*q8_M4) [0m
    [22m[35m  + q8_R3*(6*q8_M2^4 + 9*q8_Ml*q8_M3 - 15*q8_Ml) [0m
    [22m[35mgap> Print( s1+s2 );[0m
    [22m[35mq8_Rl*(2*q8_M2^4 - 8*q8_M3^3 + 2*q8_M2*q8_M3*q8_Ml [0m
    [22m[35m    + 3*q8_Ml*q8_M32*q8_Ml*q8_M2 + 4*q8_M4 - 5*q8_Ml) [0m
    [22m[35m  + q8_R2*(4*q8_M3^ 3 - q8_M2*q8_M3*q8_Ml + q8_Ml*q8_M2 - 2*q8_M4) [0m
    [22m[35m  + q8_R3*(6*q8_M2^4 + 9*q8_Ml*q8_M3 - 15*q8_Ml) [0m
    [22m[35m  + q8_R4*(2*q8_M2^4 + 3*q8_Ml*q8_M3 - 5*q8_Ml) [0m
    [22m[35mgap> Print( s1 - s2 );[0m
    [22m[35mq8_Rl*( - 2*q8_M2^4 - 3*q8_Ml*q8_M3 + 5*q8_Ml) [0m
    [22m[35m  + q8_R2*( - 4*q8_M3^3 + q8_M2*q8_M3*q8_Ml - q8_Ml*q8_M2 + 2*q8_M4) [0m
    [22m[35m  + q8_R3*( - 6*q8_M2^49*q8_Ml*q8_M3 + 15*q8_Ml) + q8_R4*(2*q8_M2^4 [0m
    [22m[35m  + 3*q8_Ml*q8_M3 - 5*q8_Ml) [0m
    [22m[35mgap> Print( s1*1/2 ); [0m
    [22m[35mq8_R1*( - 2*q8_M3^3 + 1/2*q8_M2*q8_M3*q8_M1 - 1/2*q8_M1*q8_M2 + q8_M4)[0m
    [22m[35m  + q8_R4*( q8_M2^4 + 3/2*q8_M1*q8_M3 - 5/2*q8_M1)[0m
    [22m[35mgap> M[1];[0m
    [22m[35mq8_M1[0m
    [22m[35mgap> Print( s1*M[1] );[0m
    [22m[35mq8_R1*( - 4*q8_M3^3_q8_M1 + q8_M2*q8_M3*q8_M1^2 - q8_M1*q8_M2*q8_M1 [0m
    [22m[35m  + 2*q8_M4*q8_M1) + q8_R4*( 2*q8_M2^4*q8_M1 + 3*q8_M1*q8_M3*q8_M1 - 5*q8_M1^2)[0m
    [22m[35mgap> Length( s3 );[0m
    [22m[35m3[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  
  [1m[4m[31m5.4 Identities among relators[0m
  
  [1m[4m[31m5.4-1 IdentitiesAmongRelators[0m
  
  [1m[34m> IdentitiesAmongRelators( [0m[22m[34mgrp[0m[1m[34m ) __________________________________[0mattribute
  
  The  identities among the relators for a finitely presented group are logged
  module polynomials.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> idsq8 := IdentitiesAmongRelators( q8 );[0m
    [22m[35m[ [ ( q8_Y3*( q8_M1*q8_M4), q8_R1*( q8_M1 - <identity ...>) ),[0m
    [22m[35m      ( q8_Y10*( -q8_M1*q8_M4), q8_R2*( q8_M2 - <identity ...>) ),[0m
    [22m[35m      ( q8_Y17*( <identity ...>), q8_R1*( -q8_M3 - q8_M2) + q8_R3*( q8_M1^[0m
    [22m[35m        2 + q8_M3 + q8_M1 + <identity ...>) ),[0m
    [22m[35m      ( q8_Y31*( q8_M1*q8_M4), q8_R3*( q8_M3 - q8_M2) + q8_R4*( q8_M1 - <identity\[0m
    [22m[35m ...>) ), ( q8_Y32*( -q8_M1*q8_M4), q8_R2*( -q8_M1^[0m
    [22m[35m        2) + q8_R3*( -q8_M3 - <identity ...>) + q8_R4*( q8_M2 + <identity ...>) )[0m
    [22m[35m        ,[0m
    [22m[35m      ( q8_Y12*( q8_M1*q8_M4), q8_R1*( -q8_M2) + q8_R3*( q8_M1*q8_M2 + q8_M4) + q\[0m
    [22m[35m8_R4*( q8_M2 - <identity ...>) ),[0m
    [22m[35m      ( q8_Y16*( -<identity ...>), q8_R1*( -<identity ...>) + q8_R2*( -q8_M1) + q\[0m
    [22m[35m8_R4*( q8_M3 + q8_M1) ) ],[0m
    [22m[35m  [ ( q8_Y3*( q8_M1*q8_M4), q8_R1*( q8_M1 - <identity ...>) ),[0m
    [22m[35m      ( q8_Y10*( -q8_M1*q8_M4), q8_R2*( q8_M2 - <identity ...>) ),[0m
    [22m[35m      ( q8_Y3*( -q8_M1*q8_M4*q8_M3) + q8_Y17*( <identity ...>), q8_R1*( -q8_M2 - \[0m
    [22m[35m<identity ...>) + q8_R3*( q8_M1^2 + q8_M3 + q8_M1 + <identity ...>) ),[0m
    [22m[35m      ( q8_Y31*( q8_M1*q8_M4), q8_R3*( q8_M3 - q8_M2) + q8_R4*( q8_M1 - <identity\[0m
    [22m[35m ...>) ),[0m
    [22m[35m      ( q8_Y10*( -q8_M1*q8_M4*q8_M2 - q8_M1*q8_M4) + q8_Y32*( -q8_M1*q8_M4), q8_R\[0m
    [22m[35m2*( -<identity ...>) + q8_R3*( -q8_M3 - <identity ...>) + q8_R4*( q8_M2 + <identi\[0m
    [22m[35mty ...>) ),[0m
    [22m[35m      ( q8_Y12*( q8_M1*q8_M4), q8_R1*( -q8_M2) + q8_R3*( q8_M1*q8_M2 + q8_M4) + q\[0m
    [22m[35m8_R4*( q8_M2 - <identity ...>) ),[0m
    [22m[35m      ( q8_Y16*( -<identity ...>), q8_R1*( -<identity ...>) + q8_R2*( -q8_M1) + q\[0m
    [22m[35m8_R4*( q8_M3 + q8_M1) ) ] ][0m
    [22m[35mgap> RootIdentities( q8 );[0m
    [22m[35m[ ( q8_Y3*( q8_M1*q8_M4), q8_R1*( q8_M1 - <identity ...>) ),[0m
    [22m[35m  ( q8_Y3*( q8_M1*q8_M4), q8_R1*( q8_M1 - <identity ...>) ) ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m5.4-2 RootIdentities[0m
  
  [1m[34m> RootIdentities( [0m[22m[34mgrp[0m[1m[34m ) ___________________________________________[0mattribute
  
  The  [22m[36mroot  identities[0m  are identities of the form r^wr^-1 where r = w^n is a
  relator and n>1.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> RootIdentities( q8 );[0m
    [22m[35m[ ( q8_Y3*( q8_M1*q8_M4), q8_R1*( q8_M1 - <identity ...>) ),[0m
    [22m[35m  ( q8_Y3*( q8_M1*q8_M4), q8_R1*( q8_M1 - <identity ...>) ) ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
