It is possible to use the Knuth-Bendix and Automatic Structure program on cosets of a specified subgroup \(H\) of \(G\). Most of the functions in the preceding chapter have analogues for cosets rather than for elements. It is also possible sometimes to compute a complete rewriting system or a subgroup presentation of \(H\).
The functions in this section are currently only applicable when the rewriting system is defined from a group \(G\).
‣ SubgroupOfKBMAGRewritingSystem( rws, H ) | ( function ) |
The subgroup \(H\) of the group \(G\) (= SemigroupOfRewritingSystem(rws) ) from which \({\sf rws}\) is defined can be specified either as a subgroup of \(G\); or as a list of elements of \(G\) that generate \(H\); or as a subgroup of \(F\) = FreeStructureOfRewritingSystem(rws) that maps onto \(H\); or as a list of elements of \(F\) that generate a subgroup mapping onto \(H\).
SubgroupOfKBMAGRewritingSystem returns a rewriting system subrws for \(H\), but subrws has no rules, and is only intended to be used as a parameter in the functions that follow.
‣ ResetRewritingSystemOnCosets( rws, subrws ) | ( function ) |
This function resets subrws back to its form as it was before the application of KnuthBendixOnCosets (3.2-1) or AutomaticStructureOnCosets (3.3-1). The normal form and reduction algorithms on cosets will be unavailable after this call.
Any optional control parameters set for \({\sf rws}\) will automatically be used when applying the Knuth-Bendix and Automatic Structure functions on cosets, that are now to be described.
‣ KnuthBendixOnCosets( rws, subrws ) | ( operation ) |
‣ KnuthBendixOnCosetsWithSubgroupRewritingSystem( rws, subrws ) | ( operation ) |
KnuthBendixOnCosets runs the external Knuth-Bendix program on the rewriting system \({\sf rws}\) with respect to the cosets of the subgroup corresponding to subrws. It returns true if it finds a confluent rewriting system on coset representatives, and otherwise false.
If KnuthBendixOnCosets halts without finding a confluent system, but still manages to output the current system and update \({\sf rws}\), then it is possible to use the resulting rewriting system to reduce coset representatives, and count and enumerate the irreducible coset representatives; it cannot be guaranteed that the irreducible coset representatives are all in normal form, however.
KnuthBendixOnCosetsWithSubgroupRewritingSystem does the same and, in addition, tries to compute a confluent rewriting system for the subgroup \(H\).
‣ RewritingSystemOfSubgroupOfKBMAGRewritingSystem( rws, subrws ) | ( function ) |
Use this after a successful call of KnuthBendixOnCosetsWithSubgroupRewritingSystem (3.2-1). It returns a confluent rewriting system for \(H\) on a generating set corresponding to the generators of \(H\) that were used to define subrws.
‣ IsConfluentOnCosets( rws ) | ( operation ) |
This operation returns true if \({\sf rws}\) is a rewriting system on cosets that is known to be confluent.
‣ AutomaticStructureOnCosets( rws, subrws[, large, filestore, diff1] ) | ( function ) |
‣ AutomaticStructureOnCosetsWithSubgroupPresentation( rws, subrws[, large, filestore, diff1] ) | ( function ) |
AutomaticStructureOnCosets runs the external automatic cosets program on the rewriting system \({\sf rws}\) with respect to the cosets of the subgroup \(H\) from which subrws was defined. It returns true if successful and false otherwise.
The optional parameters to AutomaticStructureOnCosets are the same as for AutomaticStructure (2.6-1).
The ordering of \({\sf rws}\) must be shortlex.
AutomaticStructureOnCosetsWithSubgroupPresentation does the same and, in addition, tries to compute a presentation of the subgroup \(H\).
‣ PresentationOfSubgroupOfKBMAGRewritingSystem( rws, subrws ) | ( function ) |
Use this after a successful call of AutomaticStructureOnCosetsWithSubgroupPresentation (3.3-1). It returns a presentation for \(H\), but this is not on the generators used to define \(H\).
‣ IsReducedCosetRepresentative( rws, subrws, w ) | ( operation ) |
This operation tests whether the word \(w\) in the generators of the freestructure FreeStructure(rws) of the rewriting system system \({\sf rws}\) is reduced or not as a coset representative of the subgroup \(H\) of \(G\). It returns true or false.
IsReducedCosetRepresentative can only be used after KnuthBendixOnCosets (3.2-1) or AutomaticStructureOnCosets (3.3-1) has been run successfully on \({\sf rws}\) and subrws. In the former case, if KnuthBendixOnCosets halted without a confluent set of rules, then irreducible words are not necessarily in normal form (but reducible words are definitely not in normal form). If KnuthBendixOnCosets completes with a confluent rewriting system or AutomaticStructureOnCosets completes successfully, then it is guaranteed that all irreducible words are in normal form.
‣ ReducedCosetRepresentative( rws, subrws, w ) | ( operation ) |
‣ ReducedFormOfCosetRepresentative( rws, subrws, w ) | ( operation ) |
ReducedCosetRepresentative reduces the word \(w\) in the generators of the free structure FreeStructure(rws) of the rewriting system \({\sf rws}\) as a coset representative of the subgroup \(H\) from which subrws was defined, and returns the result.
ReducedFormOfCosetRepresentative can only be used after KnuthBendixOnCosets (3.2-1) or AutomaticStructureOnCosets (3.3-1) has been run successfully on \({\sf rws}\) and subrws. In the former case, if KnuthBendixOnCosets halted without a confluent set of rules, then the irreducible word returned is not necessarily in normal form. If KnuthBendixOnCosets completes with a confluent rewriting system or AutomaticStructureOnCosets completes successfully, then it is guaranteed that all irreducible words are in normal form.
‣ Index( rws, subrws ) | ( method ) |
Returns the number of irreducible words for coset representatives of the subgroup \(H\) of \(G\) corresponding to subrws.
Index can only be used after KnuthBendixOnCosets (3.2-1) or AutomaticStructureOnCosets (3.3-1) has been run successfully on \({\sf rws}\) and subrws. In the former case, if KnuthBendixOnCosets halted without a confluent set of rules, then the number of irreducible words may be greater than the number of words in normal form (which is equal to the index of \(H\) in \(G\)). If KnuthBendixOnCosets completes with a confluent rewriting system or AutomaticStructureOnCosets completes successfully, then it is guaranteed that Index will return the correct index of \(H\) in \(G\).
‣ EnumerateReducedCosetRepresentatives( rws, subrws, min, max ) | ( operation ) |
Enumerate all irreducible words for coset representatives of \(H\) in \(G\), that have lengths between min and max (inclusive), which should be non-negative integers. The result is returned as a list of words. The enumeration is by depth-first search of a finite state automaton, and so the words in the list returned are ordered lexicographically (not by shortlex). EnumerateReducedCosetRepresentatives can only be used after KnuthBendixOnCosets (3.2-1) or AutomaticStructureOnCosets (3.3-1) has been run successfully on \({\sf rws}\) and subrws. In the former case, if KnuthBendixOnCosets halted without a confluent set of rules, then not all irreducible words in the list returned will necessarily be in normal form. If KnuthBendixOnCosets completes with a confluent rewriting system or AutomaticStructureOnCosets completes successfully, then it is guaranteed that all words in the list will be in normal form.
‣ GrowthFunctionOfCosetRepresentatives( rws, subrws ) | ( function ) |
Returns the growth function of the set of irreducible words for coset representatives of \(H\) in \(G\), where subrws and \({\sf rws}\) are the rewriting systems for \(H\) and \(G\). This is a rational function, of which the coefficient of \(x^n\) in its Taylor expansion is equal to the number of coset representatives words of length \(n\).
If the coefficients in this rational function are larger than about \(16000\) then strange error messages will appear and fail will be returned.
GrowthFunctionOfCosetRepresentatives can only be used after KnuthBendixOnCosets (3.2-1) or AutomaticStructureOnCosets (3.3-1) has been run successfully on \({\sf rws}\) and subrws. In the former case, if KnuthBendixOnCosets halted without a confluent set of rules, then not all irreducible words in the list returned will necessarily be in normal form. If KnuthBendixOnCosets completes with a confluent rewriting system or AutomaticStructureOnCosets completes successfully, then it is guaranteed that all words in the list will be in normal form.
Here are two examples to illustrate the operations described above.
gap> F := FreeGroup( "a", "b", "c" );; gap> a := F.1;; b := F.2;; c := F.3;; gap> G := F/[b^3,c^3,(b*c)^4,(b*c^-1)^5,a^-1*b^-1*c*b*c*b^-1*c*b*c^-1]; <fp group on the generators [ a, b, c ]> gap> R := KBMAGRewritingSystem( G ); rec( isRWS := true, silent := true, generatorOrder := [_g1,_g2,_g3,_g4,_g5,_g6], inverses := [_g2,_g1,_g4,_g3,_g6,_g5], ordering := "shortlex", equations := [ [_g3^2,_g4], [_g5^2,_g6], [_g3*_g5*_g3*_g5,_g6*_g4*_g6*_g4], [_g3*_g6*_g3*_g6*_g3,_g5*_g4*_g5*_g4*_g5], [_g2*_g4*_g5*_g3*_g5,_g5*_g4*_g6*_g3] ] ) gap> S := SubgroupOfKBMAGRewritingSystem( R, [ a^3, c*a^2 ] ); rec( isRWS := true, silent := true, generatorOrder := [_x1,_X1,_x2,_X2], inverses := [_X1,_x1,_X2,_x2], ordering := "shortlex", equations := [ ] ) gap> KnuthBendixOnCosetsWithSubgroupRewritingSystem( R, S ); true gap> Index( R, S ); 18 gap> IsReducedCosetRepresentative( R, S, b*a*b*a ); false gap> ReducedFormOfCosetRepresentative( R, S, b*a*b*a ); b^-1*a^-1 gap> EnumerateReducedCosetRepresentatives( R, S, 0, 4 ); [ <identity ...>, a, a*b, a*b*c, a*b^-1, a^-1, a^-1*b, a^-1*b*c, a^-1*b^-1, b, b*c, b*c*a, b*c*a^-1, b*c^-1, b^-1, b^-1*a, b^-1*a^-1, b^-1*a^-1*b ] gap> SS := RewritingSystemOfSubgroupOfKBMAGRewritingSystem( R, S );; gap> Size( SS ); 60
We find a free subgroup of the Fibonacci group \(F(2,8)\). This example may take about \(20\) minutes to run on a typical WorkStation.
gap> F := FreeGroup( 8 );; gap> a := F.1; b := F.2; c := F.3; d := F.4; gap> e := F.5; f := F.6; g := F.7; h := F.8; gap> G := F/[a*b*c^-1, b*c*d^-1, c*d*e^-1, d*e*f^-1, > e*f*g^-1, f*g*h^-1, g*h*a^-1, h*a*b^-1]; gap> R := KBMAGRewritingSystem( G );; gap> S := SubgroupOfKBMAGRewritingSystem( R, [a,e] );; gap> AutomaticStructureOnCosetsWithSubgroupPresentation( R, S ); gap> P := PresentationOfSubgroupOfKBMAGRewritingSystem( R, S ); <fp group on the generators [ f1, f3 ]> gap> RelatorsOfFpGroup( P ); [ ] gap> Index( R, S ); infinity
generated by GAPDoc2HTML