Goto Chapter: Top 1 2 3 4 5 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

1 Introduction
 1.1 An illustrative example

1 Introduction

This manual describes the IdRel package for GAP 4.7 for computing the identities among relators of a group presentation using rewriting, logged rewriting, monoid polynomials, module polynomials and Y-sequences.

The theoretical background for these computations is contained in Brown and Huebschumann [BH82], Brown and Razak Salleh [BRS99] and is surveyed in the first author's thesis [Hey99].

IdRel is primarily designed for the computation of a minimal set of generators for the module of identities among relators. It also contains functions which compute logged rewrite systems for group presentations (and complete them where possible); functions for operations involving elements of monoid rings; and functions for operations with elements of right modules over monoid rings. The Y-sequences are used as a rewriting way of representing elements of a free crossed module (products of conjugates of group relators and inverse relators). The package is written entirely in GAP4, and requires no compilation.

The package is loaded into GAP with the LoadPackage command, and on-line help is available in the usual way.

gap> LoadPackage( "idrel" ); 
gap> ?idrel

A pdf version of the IdRel manual is available in the doc directory of the home directory of IdRel. The information parameter InfoIdRel has default value 0. When raised to a higher value, additional information is printed out. IdRel was originally developed in 1999 using GAP3, partially supported by a University of Wales Research Assistantship for the first author, Anne Heyworth.

If you use IdRel to solve a problem then please send a short email to the second author, to whom bug reports, suggestions and other comments should also be sent. You may reference the package by mentioning [HW03] and [Hey99].

The current version is 2.38 for GAP 4.8, released on 15th December 2017.

The package may be obtained as a compressed tar file idrel-2.38.tar.gz by ftp from one of the following sites:

1.1 An illustrative example

A typical input for IdRel is an fp-group presentation. This requires a free group F on a set of generators and a set of relators R (words in the free group). The module of identities among relators for this presentation has as its elements the Peiffer equivalence classes of all products of conjugates of relators which represent the identity in the free group.

In this package the identities among relators are represented by Y-sequences, which are lists [[r_1, u_1],...,[r_k,u_k]] where r_1,...,r_k are the group relators or their inverses, and u_1,...,u_k are words in the free group F. A Y-sequence is evaluated in F as the product (u_1^-1r_1u_1)...(u_k^-1r_ku_k) and is an identity Y-sequence if it evaluates to the identity in F. An identity Y-sequence represents an identity among the relators of the group presentation. The main function of the package is to produce a set of Y-sequences which generate the module of identites among relators, and further, that this set be minimal in the sense that every element in it is needed to generate the module.

Before starting on the main example, we consider a simpler example illustrating the use of IdRel. All the functions used are described in detail in this manual. We compute a reduced set of identities among relators for the presentation of the symmetric group s3 with generators a,b and relators [a^3 , b^2, (ab)^2]. In the listings below, s3_M1 is the first monoid generator for s3, s3_R2 is the second relator, while s3_Y4 is the fourth Y-sequence for s3.

gap> F := FreeGroup( 2 );;
gap> a := F.l;; b:= F.2;;
gap> rels3 := [ a^3 , b^2, a*b*a*b];
[ f1^3, f2^2, (f1*f2)^2 ]
gap> s3 := F/rels3;
<fp group on the generators [ fl, f2 ]> 
gap> SetName( s3, "s3" ); 
gap> idy3 := IdentityYSequences( s3 );; 
gap> Length( idy3 ); 
gap> Y1 := idy3[1];
[ 1, 4, [ [ s3_R1^-1, f1^-1 ], [ s3_R1, <identity ...> ] ] ]
gap> Y3 := idy3[3];
[ 3, 8, [ [ s3_R2^-1, f2^-1 ], [ s3_R2, <identity ...> ] ] ]
gap> Y5 := idy3[5];
[ 5, 9, [ [ s3_R3^-1, f2^-1 ], [ s3_R3, f1 ] ] ]
gap> Y11 := idy3[11];
[ 11, 6, [ [ s3_R3^-1, f1^-1 ], [ s3_R1, <identity ...> ], [ s3_R3^-1, f1 ], 
      [ s3_R2, f1^-1*f2^-1 ], [ s3_R1, f2^-1 ], [ s3_R3^-1, f1*f2^-1 ], 
      [ s3_R2, <identity ...> ], [ s3_R2, f1^-1 ] ] ]

Of the 18 Y-sequences formed, 6 are empty, and discarded, so that idy3 has 12 entries, and the list is then sorted. Y1 is the root identity ((a^3)^-1)^(a^-1).(a^3). If we write r=a^3, s=b^2, t=(ab)^2 then Y1 becomes (r^-1)^a^-1}r. Similarly, Y3 is the second root identity (s^-1)^b^-1}s. The third root identity is (t^-1)^(ab)^-1}t, which is equivalent to (t^-1)^b^-1}t^a, and is the sequence Y5. The identity Y11, which is not a root identity, is obtained by walking around the Schreier diagram of the presentation, a somewhat truncated triangular prism. Taking the appropriate conjugate of each face in turn, we get: Y11=(t^-1)^(a^-1).r.(t^-1)^a.s^(a^-1b^-1).r^(b^-1).(t^-1)^(ab^-1).s.s^(a^-1). These four identities generate the module of identities for s3.

In order to form the module of identities for s3 the identities are transformed into module polynomials. Thus Y1 = (r^-1)^a^-1}r becomes y_1 = (-r)(a^-1)+r = r(1-a^-1) and y_1a = r(a-1). Similarly Y3 = (s^-1)^b^-1}s yields y_3b = s(b-1) and Y5 = (t^-1)^b^-1}t^a yields y_5ba = t(b-a).

gap> idrels3 := IdentitiesAmongRelators( s3 );;
gap> Display( idrels3[1] );
[ ( s3_Y1*( s3_M1), s3_R1*( s3_M1 - <identity ...>) ), 
  ( s3_Y3*( s3_M2), s3_R2*( s3_M2 - <identity ...>) ), 
  ( s3_Y5*( s3_M2*s3_M1), s3_R3*( s3_M2 - s3_M1) ), 
  ( s3_Y11*( -s3_M1), s3_R1*( -s3_M2*s3_M1 - s3_M1) + s3_R2*( -s3_M1*s3_M2 - s\
3_M1 - <identity ...>) + s3_R3*( s3_M3 + s3_M2 + <identity ...>) ) ]

Further examples are given in section 5.4.

 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 Bib Ind

generated by GAPDoc2HTML