This chapter describes functions to construct rewriting systems for finitely presented groups which store rewriting information. The main example used is a presentation of the quaternion group q8
with generators a,b and relators [a^4, b^4, abab^-1, a^2b^2].
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 listing 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]; [ fl^3 , f2^2, fl*f2*fl*f2] gap> s3 := F/rels3; <fp group on the generators [ fl, f2 ]> gap> SetName( s3, "s3" ); gap> idy3 := IdentityYSequences( s3 );; gap> Length( idy3 ); 18 gap> Y4 := idy3[4]; [ [ s3_R1^-1, f1^-1 ], [ s3_R1, <identity ...> ] ] gap> Y6 := idy3[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 ] ] gap> Y7 := idy3[7]; [ [ s3_R3^-1, f1*f2^-1 ], [ s3_R2, <identity ...> ], [ s3_R3, <identity ...> ], [ s3_R2^-1, <identity ...> ] ] gap> Y8 := idy3[8]; [ [ s3_R2^-1, f2^-1 ], [ s3_R2, <identity ...> ] ] |
Of the 18 Y-sequences formed, 6 are empty, and Y4
is the root identity ((a^3)^-1)^(a^-1).(a^3)
. If we write r=a^3, s=b^2, t=(ab)^2 then Y4
is (r^-1)^(a^-1).r
. Similarly, Y8
is the second root identity (s^-1)^(b^-1).s
, while Y7
is the third root identity (t^-1)^(ab^-1).t
. The identity Y6
, which is not a root identity, is obtained by walking around the Schreier diagram of the presentation, which is a somewhat truncated triangular prism, taking the appropriate conjugate of each face in turn: Y6=(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
.
gap> idrels3 := IdentitiesAmongRelators( s3 );; gap> Display( idrels3[1] ); [ ( 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) ), ( s3_Y6*( -s3_M2*s3_M1), s3_R1*( -s3_M2*s3_M1 - s3_M1) + s3_R2*( -s3_M1*s3_M\ 2 - s3_M1 - <identity ...>) + s3_R3*( s3_M3 + s3_M2 + <identity ...>) ) ] |
> FreeRelatorGroup ( grp ) | ( attribute ) |
> FreeRelatorHomomorphism ( grp ) | ( attribute ) |
The function FreeRelatorGroup
returns a free group on the set of relators of the given fp-group G
. If HasName(G)
is true
then a name is automatically assigned to the free group.
The function FreeRelatorHomomorphism
returns the group homomorphism from the free group on the relators to the free group on the generators of G
, mapping each generator to the corresponding word.
gap> F := FreeGroup( 2 );; gap> a := F.1;; b:= F.2;; gap> rels := [ a^4, b^4, a*b*a*b^-1, a^2*b^2];; gap> q8 := F/rels;; gap> SetName( q8, "q8" ); gap> frq8 := FreeRelatorGroup( q8 ); q8_R gap> GeneratorsOfGroup( frq8 ); [ q8_R1, q8_R2, q8_R3, q8_R4] gap> frhomq8 := FreeRelatorHomomorphism( q8 ); [ q8_R1, q8_R2, q8_R3, q8_R4] -> [ f1^4, f2^4, f1*f2*f1*f2^-1, f1^2*f2^2] |
> MonoidPresentationFpGroup ( grp ) | ( attribute ) |
> FreeGroupOfPresentation ( mon ) | ( attribute ) |
> GroupRelatorsOfPresentation ( mon ) | ( attribute ) |
> InverseRelatorsOfPresentation ( mon ) | ( attribute ) |
> HomomorphismOfPresentation ( mon ) | ( attribute ) |
A monoid presentation for a finitely presented group G
has two monoid generators g^+,g^- for each group generator g. The relators of the monoid presentation comprise the group relators, and relators g^+g^- specifying the inverses. The function MonoidPresentationFpGroup
returns the monoid presentation derived in this way from an fp-presentation. (Note: this function should always be followed by a double semicolon -- MonoidPresentationFpGroup(G);;
-- because an error occurs in attempting to display the results on the screen: the ElementsFamily
needs to be fixed.)
The function FreeGroupOfPresentation
returns the free group on the monoid generators.
The function GroupRelatorsOfPresentation
returns those relators of the monoid which correspond to the relators of the group. All negative powers in the group relators are converted to positive powers of the g^-.
The function InverseRelatorsOfPresentation
returns relators which specify the inverse pairs of the monoid generators.
The function HomomorphismOfPresentation
returns the homomorphism from the free group of the monoid presentation to the free group of the group presentation.
In the example below, the four monoid generators a^+, b^+, a^-, b^- are named q8\_M1, q8\_M2, q8\_M3, q8\_M4
.
gap> mon := MonoidPresentationFpgroup( q8 );; gap> fgmon := FreeGroupOfPresentation( mon); <free group on the generators [ q8_Ml, q8_M2, q8_M3, q8_M4]> gap> genfgmon := GeneratorsOfGroup( fgmon); [ q8_Ml, q8_M2, q8_M3, q8_M4] gap> gprels := GroupRelatorsOfPresentation( mon ); [ q8_Ml^4, q8_M2^4, q8_Ml*q8_M2*q8_Ml*q8_M4, q8_Ml^2*q8_M2^2] gap> invrels := InverseRelatorsOfPresentation( mon); [ q8_Ml*q8_M3, q8_M2*q8_M4, q8_M3*q8_Ml, q8_M4*q8_M2] gap> hompres := HomomorphismOfPresentation( mon ); [ q8_Ml, q8_M2, q8_M3, q8_M4] -> [ fl, f2, fl^-l, f2^-1 ] |
These functions duplicate the standard Knuth Bendix functions which are available in the GAP library. There are two reasons for this: (1) these functions were first written before the standard functions were available; (2) we require logged versions of the functions, and these are most conveniently extended versions of the non-logged code.
> RewritingSystemFpGroup ( grp ) | ( attribute ) |
This function attempts to return a complete rewrite system for the group G
obtained from the monoid presentation mon
, with a length-lexicographical ordering on the words in fgmon
, by applying Knuth-Bendix completion. Such a rewrite system can be obtained for all finite groups. The rewrite rules are (partially) ordered, starting with the inverse relators, followed by the rules which reduce the word length the most.
In our q8
example there are 16 rewrite rules.
gap> rws := RewritingSystemFpGroup( q8 ); [ [q8_Ml*q8_M3, <identity ...>], [ q8_M2*q8_M4, <identity ...> ], [q8_M3*q8_Ml, <identity ...>], [ q8_M4*q8_M2, <identity ...> ], [q8_M1^2*q8_M4, q8_M2], [q8_Ml^2*q8_M2, q8_M4], [ q8_Ml^3, q8_M3 ], [ q8_M4^2, q8_Ml^2], [ q8_M4*q8_M3, q8_Ml*q8_M4], [ q8_M4*q8_Ml, q8_Ml*q8_M2], [q8_M3*q8_M4, q8_Ml*q8_M2], [ q8_M3^2, q8_Ml^2], [q8_M3*q8_M2, q8_Ml*q8_M4], [ q8_M2*q8_M3, q8_Ml*q8_M2], [q8_M2^2, q8_Ml^2], [ q8_M2*q8_Ml, q8_Ml*q8_M4] ] |
The functions called by RewritingSystemFpGroup
are as follows.
> OnePassReduceWord ( word, rules ) | ( operation ) |
> ReduceWordKB ( word, rules ) | ( operation ) |
Assuming that word
is an element of a free monoid and rules
is a list of ordered pairs of such words, the function OnePassReduceWord
searches the list of rules until it finds that the left-hand side of a rule
is a subword
of word
, whereupon it replaces that subword
with the right-hand side of the matching rule. The search is continued from the next rule
in rules
, but using the new word
. When the end of rules
is reached, one pass is considered to have been made and the reduced word
is returned. If no matches are found then the original word
is returned.
The function ReduceWordKB
repeatedly applies the function OnePassReduceWord
until the word
remaining contains no left-hand side of a rule
as a subword
. If rules
is a complete rewrite system, then the irreducible word
that is returned is unique, otherwise the order of the rules in rules
will determine which irreducible word is returned. In the example we see that b^9a^9 reduces to ba, and we shall see later that this is not a normal form.
gap> monrels := Concatenation( gprels, invrels ); [ q8_Ml^4, q8_M2^4, q8_Ml*q8_M2*q8_Ml*q8_M4, q8_Ml^2*q8_M2^2, q8_Ml*q8_M3, q8_M2*q8_M4, q8_M3*q8_Ml, q8_M4*q8_M2] gap> id := One( monrels[l] );; gap> r0 := List( monrels, r -> [ r, id ] ); [ [ q8_Ml^4, <identity ...> ], [ q8_M2^4, <identity. ..> ], [ q8_Ml*q8_M2*q8_Ml*q8_M4, <identity ...> ], [ q8_Ml^2*q8_M2^2, <identity. ..>], [ q8_Ml*q8_M3, <identity ...> ], [ q8_M2*q8_M4, <identity ...> ], [ q8_M3*q8_Ml, <identity. ..>], [ q8_M4*q8_M2, <identity ...> ] ] gap> ap := genfgmon[l];; bp := genfgmon[2];; ## p for plus gap> am := genfgmon[3];; bm := genfgmon[4];; ## m for minus gap> w0 := bp^9 * ap^9; q8_M2^9*q8_M1^9 gap> w1 := OnePassReduceWord( w0, r0 ); q8_M2^5*q8_M1^5 gap> w2 := ReduceWordKB( w0, r0 ); q8_M2*q8_M1 |
> OnePassKB ( rules ) | ( operation ) |
> RewriteReduce ( rules ) | ( operation ) |
> KnuthBendix ( rules ) | ( operation ) |
> ShorterRule ( rule1, rule2 ) | ( operation ) |
The function OnePassKB
implements the main loop of the Knuth-Bendix completion algorithm. Rules are compared with each other; all critical pairs are calculated; and the irreducible critical pairs are orientated with respect to the length-lexicographical ordering and added to the rewrite system.
The function RewriteReduce
will remove unnecessary rules from a rewrite system. A rule is deemed to be unnecessary if it is implied by the other rules, i.e. if both sides can be reduced to the same thing by the remaining rules.
The function KnuthBendix
implements the Knuth-Bendix algorithm, attempting to complete a rewrite system with respect to a length-lexicographic ordering. It calls first OnePassKB
, which adds rules, and then (for efficiency) RewriteReduce
which removes any unnecessary ones. This procedure is repeated until OnePassKB
adds no more rules. It will not always terminate, but for many examples (all finite groups) it will be successful. The rewrite system returned is complete, that is: it will rewrite any given word in the free monoid to a unique irreducible; there is one irreducible for each element of the quotient monoid; and any two elements of the free monoid which are in the same class will rewrite to the same irreducible.
The function ShorterRule
gives an ordering on rules. Rules (g_lg_2,id) that identify two generators (or one generator with the inverse of another) come first in the ordering. Otherwise one precedes another if it reduces the length of a word by a greater amount.
One pass of this procedure for our q8
example adds 13 relators to the original 8, and these 21 are then reduced to 9. A second pass and reduction gives a list of 16 rules which forms a complete rewrite system for the group.
gap> r1 := OnePassKB( r0 ); [ [ q8_Ml^4, <identity ...> ], [ q8_M2^4, <identity ...> ], [ q8_Ml*q8_M2*q8_Ml*q8_M4, <identity ...> ], [ q8_Ml^2*q8_M2^2, <identity. ..> ], [ q8_Ml*q8_M3, <identity ...> ], [ q8_M2*q8_M4, <identity ...> ], [ q8_M3*q8_Ml, <identity ...> ], [ q8_M4*q8_M2, <identity ...> ], [ q8_M2*q8_Ml*q8_M4, q8_Ml^3], [ q8_Ml*q8_M2^2, q8_Ml^3 ], [ q8_M2^2, q8_Ml^2 ], [q8_Ml^3, q8_M3 ], [ q8_M2^3, q8_M4 ], [ q8_Ml*q8_M2*q8_Ml, q8_M2], [ q8_M2^3, q8_Ml^2*q8_M2], [ q8_M2^2, q8_Ml^2 ], [q8_Ml^2*q8_M2, q8_M4 ], [ q8_Ml^3, q8_M3 ], [ q8_M2*q8_Ml*q8_M4, q8_M3 ], [q8_Ml*q8_M2^2, q8_M3 ], [ q8_M2^3, q8_M4 ] ] gap> r1 := RewriteReduce( r1 ); [ [ q8_Ml*q8_M3, <identity ...> ], [ q8_M2^2, q8_Ml^2 ], [ q8_M2*q8_M4, <identity ...> ], [ q8_M3*q8_Ml, <identity ...> ], [ q8_M4*q8_M2, <identity ...> ], [ q8_Ml^3, q8_M3 ], [ q8_Ml^2*q8_M2, q8_M4 ], [ q8_Ml*q8_M2*q8_Ml, q8_M2 ], [ q8_M2*q8_Ml*q8_M4, q8_M3 ] ] gap> r2 := KnuthBendix( r1 ); [ [ q8_Ml*q8_M3, <identity ...> ], [ q8_M2*q8_Ml, q8_Ml*q8_M4 ], [ q8_M2^2, q8_Ml^2], [ q8_M2*q8_M3, q8_Ml*q8_M2 ], [ q8_M2*q8_M4, <identity ...> ], [ q8_M3*q8_Ml, <identity ...> ], [ q8_M3*q8_M2, q8_Ml*q8_M4 ], [ q8_M3^2, q8_Ml^2 ], [ q8_M3*q8_M4, q8_Ml*q8_M2 ], [ q8_M4*q8_Ml, q8_Ml*q8_M2 ], [ q8_M4*q8_M2, <identity ...> ], [ q8_M4*q8_M3, q8_Ml*q8_M4 ], [ q8_M4^2, q8_Ml^2], [ q8_Ml^3, q8_M3 ], [q8_Ml^2*q8_M2, q8_M4 ], [ q8_Ml^2*q8_M4, q8_M2 ] ] gap> w2 := ReduceWordKB( w0, r2 ); q8_M1*q8_M4 |
> ElementsOfMonoidPresentation ( mon ) | ( attribute ) |
The function ElementsOfMonoidPresentation
returns a list of normal forms for the elements of the group given by the monoid presentation mon
. The normal forms are the least elements in each equivalence class (with respect to length-lex order). When rules
is a complete rewrite system for G
the list returned is a set of normal forms for the group elements.
gap> elq8 := Elements( q8 ); [ <identity .. .>, fl, f2, fl^2, fl*f2, fl^3*f2, fl^3, fl^2*f2 ] gap> elmonq8 := ElementsOfMonoidPresentation( monq8 ); [ <identity. ..>, q8_Ml, q8_M2, q8_M3, q8_M4, q8_Ml^2, q8_Ml*q8_M2, q8_Ml*q8_M4 ] |
generated by GAPDoc2HTML