Example 1
We start with a easy example - the alternating group A_4.
gap> G:=FreeGroup("a","b");;
gap> a:=G.1;; b:=G.2;;
gap> G.relators:=[a^2, b^3, (a*b)^3];;
gap> R:=FpGroupToRWS(G);
rec(
isRWS := true,
generatorOrder := [a,b,b^-1],
inverses := [a,b^-1,b],
ordering := "shortlex",
equations := [
[b^2,b^-1],
[a*b*a,b^-1*a*b^-1]
]
)
gap> KB(R);
#System is confluent.
#Halting with 11 equations.
true
gap> R;
rec(
isRWS := true,
isConfluent := true,
generatorOrder := [a,b,b^-1],
inverses := [a,b^-1,b],
ordering := "shortlex",
equations := [
[a^2,IdWord],
[b*b^-1,IdWord],
[b^-1*b,IdWord],
[b^2,b^-1],
[b^-1*a*b^-1,a*b*a],
[b^-2,b],
[b*a*b,a*b^-1*a],
[b^-1*a*b*a,b*a*b^-1],
[a*b*a*b^-1,b^-1*a*b],
[b*a*b^-1*a,b^-1*a*b],
[a*b^-1*a*b,b*a*b^-1]
]
)
#The 'equations' field of <R> is now a complete system of rewriting rules
gap> SizeRWS(R);
12
gap> SortEnumerateRWS(R,0,12);
[ IdWord, a, b, b^-1, a*b, a*b^-1, b*a, b^-1*a, a*b*a, a*b^-1*a,
b*a*b^-1, b^-1*a*b ]
#We have enumerated all of the elements of the group
Example 2
The Heisenberg group - that is, the free 2-generator nilpotent group of class 2. For this to complete, we need to use the recursive ordering, and reverse our initial order of generators. (Alternatively, we could avoid this reversal, by using a wreathproduct ordering, and setting the levels of the generators to be 6,5,4,3,2,1.)
gap> G:=FreeGroup("x","y","z");;
gap> x:=G.1;; y:=G.2;; z:=G.3;;
gap> G.relators:=[Comm(y,x)*z^-1, Comm(z,x), Comm(z,y)];;
gap> R:=FpGroupToRWS(G);
rec(
isRWS := true,
generatorOrder := [x,x^-1,y,y^-1,z,z^-1],
inverses := [x^-1,x,y^-1,y,z^-1,z],
ordering := "shortlex",
equations := [
[y^-1*x^-1*y,z*x^-1],
[z^-1*x^-1,x^-1*z^-1],
[z^-1*y^-1,y^-1*z^-1]
]
)
gap> SetOrderingRWS(R,"recursive");
gap> ReorderGeneratorsRWS(R,(1,6)(2,5)(3,4));
gap> R;
rec(
isRWS := true,
generatorOrder := [z^-1,z,y^-1,y,x^-1,x],
inverses := [z,z^-1,y,y^-1,x,x^-1],
ordering := "recursive",
equations := [
[y^-1*x^-1*y,z*x^-1],
[z^-1*x^-1,x^-1*z^-1],
[z^-1*y^-1,y^-1*z^-1]
]
)
gap> KB(R);
#System is confluent.
#Halting with 18 equations.
true
gap> R;
rec(
isRWS := true,
isConfluent := true,
generatorOrder := [z^-1,z,y^-1,y,x^-1,x],
inverses := [z,z^-1,y,y^-1,x,x^-1],
ordering := "recursive",
equations := [
[z^-1*z,IdWord],
[z*z^-1,IdWord],
[y^-1*y,IdWord],
[y*y^-1,IdWord],
[x^-1*x,IdWord],
[x*x^-1,IdWord],
[z^-1*x^-1,x^-1*z^-1],
[z^-1*y^-1,y^-1*z^-1],
[y^-1*x^-1,x^-1*y^-1*z],
[z*x^-1,x^-1*z],
[z^-1*x,x*z^-1],
[z*y^-1,y^-1*z],
[z^-1*y,y*z^-1],
[y*x,x*y*z],
[y^-1*x,x*y^-1*z^-1],
[y*x^-1,x^-1*y*z^-1],
[z*x,x*z],
[z*y,y*z]
]
)
gap> SizeRWS(R);
"infinity"
gap> IsReducedWordRWS(R,z*y*x);
false
gap> ReduceWordRWS(R,z*y*x);
x*y*z^2
gap> IsReducedWordRWS(R,x*y*z^2);
true
Example 3
This is an example of the use of the Knuth-Bendix algorithm to prove
the nilpotence of a finitely presented group. (The method is due to
Sims, and is described in Chapter 11.8 of Sims94.) This example
is of intermediate difficulty, and demonstrates the necessity of using
the maxstoredlen control parameter.
The group is langle a,b hspace1mm| hspace1mm[b,a,b],
[b,a,a,a,a], [b,a,a,a,b,a,a] rangle with left-normed commutators.
The first step in the method is to check that there is a maximal
nilpotent quotient of the group, for which we could use, for example,
the GAP NilpotentQuotient command, from the shared-library
``nq". We find that there is a maximal such quotient, and it has
class 7, and the layers going down the lower central series have the
abelian structures [0,0], [0], [0], [0], [0], [2], [2].
By using the stand-alone C nilpotent quotient program, it is
possible to find a power-commutator presentation of this maximal
quotient. We now construct a new presentation of the same group, by
introducing the generators in this power-commutator presentation,
together with their definitions as powers or commutators of earlier
generators. It is this new presentation that we use as input for the
Knuth-Bendix program. Again we use the recursive ordering, but this
time we will be careful to introduce the generators in the correct
order in the first place!
gap> G:=FreeGroup("h","g","f","e","d","c","b","a");;
gap> h:=G.1;;g:=G.2;;f:=G.3;;e:=G.4;;d:=G.5;;c:=G.6;;b:=G.7;;a:=G.8;;
gap> G.relators:=[Comm(b,a)*c^-1, Comm(c,a)*d^-1, Comm(d,a)*e^-1,
> Comm(e,b)*f^-1, Comm(f,a)*g^-1, Comm(g,b)*h^-1,
> Comm(g,a), Comm(c,b), Comm(e,a)];;
gap> R:=FpGroupToRWS(G);
rec(
isRWS := true,
generatorOrder := [h,h^-1,g,g^-1,f,f^-1,e,e^-1,d,d^-1,c,c^-1,
b,b^-1,a,a^-1],
inverses := [h^-1,h,g^-1,g,f^-1,f,e^-1,e,d^-1,d,c^-1,c,
b^-1,b,a^-1,a],
ordering := "shortlex",
equations := [
[b^-1*a^-1*b,c*a^-1],
[c^-1*a^-1*c,d*a^-1],
[d^-1*a^-1*d,e*a^-1],
[e^-1*b^-1*e,f*b^-1],
[f^-1*a^-1*f,g*a^-1],
[g^-1*b^-1*g,h*b^-1],
[g^-1*a^-1,a^-1*g^-1],
[c^-1*b^-1,b^-1*c^-1],
[e^-1*a^-1,a^-1*e^-1]
]
)
gap> SetOrderingRWS(R,"recursive");
A little experimentation reveals that this example works best when
only those equations with left and right hand sides of lengths at most
10 are kept.
gap> R.maxstoredlen:=[10,10];;
gap> R.verbose:=true;;
gap> KB(R);
#60 eqns; total len\:\hspace{2mm}lhs, rhs = 129, 143; 25 states; 0 secs.
#68 eqns; total len\:\hspace{2mm}lhs, rhs = 364, 326; 28 states; 0 secs.
#77 eqns; total len\:\hspace{2mm}lhs, rhs = 918, 486; 45 states; 0 secs.
#91 eqns; total len\:\hspace{2mm}lhs, rhs = 728, 683; 58 states; 0 secs.
#102 eqns; total len\:\hspace{2mm}lhs, rhs = 1385, 1479; 89 states; 0 secs.
. . . .
#310 eqns; total len\:\hspace{2mm}lhs, rhs = 4095, 4313; 489 states; 1 secs.
#200 eqns; total len\:\hspace{2mm}lhs, rhs = 2214, 2433; 292 states; 1 secs.
#194 eqns; total len\:\hspace{2mm}lhs, rhs = 835, 922; 204 states; 1 secs.
#157 eqns; total len\:\hspace{2mm}lhs, rhs = 702, 723; 126 states; 1 secs.
#151 eqns; total len\:\hspace{2mm}lhs, rhs = 553, 444; 107 states; 1 secs.
#101 eqns; total len\:\hspace{2mm}lhs, rhs = 204, 236; 19 states; 1 secs.
#No new eqns for some time - testing for confluence
#System is not confluent.
#172 eqns; total len\:\hspace{2mm}lhs, rhs = 616, 473; 156 states; 1 secs.
#171 eqns; total len\:\hspace{2mm}lhs, rhs = 606, 472; 156 states; 1 secs.
#No new eqns for some time - testing for confluence
#System is not confluent.
#151 eqns; total len\:\hspace{2mm}lhs, rhs = 452, 453; 92 states; 1 secs.
#151 eqns; total len\:\hspace{2mm}lhs, rhs = 452, 453; 92 states; 1 secs.
#No new eqns for some time - testing for confluence
#System is not confluent.
#101 eqns; total len\:\hspace{2mm}lhs, rhs = 200, 239; 15 states; 1 secs.
#101 eqns; total len\:\hspace{2mm}lhs, rhs = 200, 239; 15 states; 1 secs.
#No new eqns for some time - testing for confluence
#System is confluent.
#Halting with 101 equations.
WARNING: The monoid defined by the presentation may have changed,
since equations have been discarded.
If you re-run, include the original equations.
true
#We re-run with the 'maxstoredlen' limit removed and the original
#equations added, to check that the system really is confluent.
gap> Unbind(R.maxstoredlen);
gap> AddOriginalEqnsRWS(R);
gap> KB(R);
#101 eqns; total len\:\hspace{2mm}lhs, rhs = 200, 239; 15 states; 0 secs.
#No new eqns for some time - testing for confluence
#System is confluent.
#Halting with 101 equations.
true
#In fact, in this case, we did have a confluent set already.
Inspection of the confluent set now reveals it to be precisely a
power-commutator presentation of a nilpotent group, and so we have
proved that the group we started with really is nilpotent. Of course,
this means also that it is equal to its largest nilpotent quotient, of
which we already know the structure.
Example 4
Our final example illustrates the use of the Automata command, which
runs the automatic groups programs. The group has a balanced
symmetrical presentation with 3 generators and 3 relators, and was
originally proposed by Heineken as a possible example of a finite
group with such a presentation. In fact, the Automata command proves
it to be infinite.
This example is of intermediate difficulty, but there is no need to use any special options. It takes about 20 minutes to run on a fast WorkStation.
We will not attempt to explain all of the output in detail here; the interested user should consult the documentation for the stand-alone KBMAG package. Roughly speaking, it first runs the Knuth-Bendix program, which does not halt with a confluent rewriting system, but is used instead to construct a word-difference finite state automaton. This in turn is used to construct the word-acceptor and multiplier automata for the group. Sometimes the initial constructions are incorrect, and part of the procedure consists in checking for this, and making corrections. In fact, in this example, the correct automata are considerably smaller than the ones first constructed. The final stage is to run an axiom-checking program, which essentially checks that the automata satisfy the group relations. If this completes successfully, then the correctness of the automata has been proved, and they can be used for correct word-reduction and enumeration in the group.
gap> G:=FreeGroup("a","b","c");;
gap> a:=G.1;;b:=G.2;;c:=G.3;;
gap> G.relators:=[Comm(a,Comm(a,b))*c^-1, Comm(b,Comm(b,c))*a^-1,
> Comm(c,Comm(c,a))*b^-1];
[ a^-1*b^-1*a^-1*b*a*b^-1*a*b*c^-1, b^-1*c^-1*b^-1*c*b*c^-1*b*c*a^-1,
c^-1*a^-1*c^-1*a*c*a^-1*c*a*b^-1 ]
gap> R:=FpGroupToRWS(G);
rec(
isRWS := true,
generatorOrder := [a,a^-1,b,b^-1,c,c^-1],
inverses := [a^-1,a,b^-1,b,c^-1,c],
ordering := "shortlex",
equations := [
[a^-1*b^-1*a^-1*b*a,c*b^-1*a^-1*b],
[b^-1*c^-1*b^-1*c*b,a*c^-1*b^-1*c],
[c^-1*a^-1*c^-1*a*c,b*a^-1*c^-1*a]
]
)
gap> Automata(R);
#Running Knuth-Bendix Program:
#Maximum number of equations exceeded.
#Halting with 200 equations.
#First word-difference machine with 161 states computed.
#Second word-difference machine with 175 states computed.
#Re-running Knuth-Bendix Program
#Halting with 7672 equations.
#First word-difference machine with 259 states computed.
#Second word-difference machine with 269 states computed.
#System is confluent, or halting factor condition holds.
#Running program to construct word-acceptor and multiplier automata
#Word-acceptor with 5488 states computed.
#General multiplier with 6806 states computed.
#Multiplier incorrect with generator number 2.
#Equation found between two words accepted by word-acceptor.
#Word-acceptor with 1106 states computed.
#General multiplier with 2428 states computed.
#Validity test on general multiplier succeeded.
#Running program to verify axioms on the automatic structure
#General length-2 multiplier with 2820 states computed.
#Checking inverse and short relations.
#Checking relation\:\hspace{2mm}'a\^-1\*b\^-1\*a\^-1\*b\*a = c\*b\^-1\*a\^-1\*b'
#Checking relation\:\hspace{2mm}'b\^-1\*c\^-1\*b\^-1\*c\*b = a\*c\^-1\*b\^-1\*c'
#Checking relation\:\hspace{2mm}'c\^-1\*a\^-1\*c\^-1\*a\*c = b\*a\^-1\*c\^-1\*a'
#Axiom checking succeeded.
#Minimal reducible word acceptor with 1058 states computed.
#Minimal Knuth-Bendix equation fsa with 1891 states computed.
#Minimal diff1 fsa with 271 states computed.
true
gap> SizeRWS(R);
"infinity"
We have proved that the group is infinite, but it would also be
interesting to know whether the group generators have infinite
order. This can often be shown by inspecting the word-acceptor
automaton directly.
The GAP interface to KBMAG includes a number of (currently
undocumented) functions for manipulating finite state automata. The
calculation below illustrates the use of one or two of these. In this
example, it turns out that all powers of the generators are accepted
by the word-acceptor automaton R.wa. The accepted language of this
automaton is precisely the set of words in normal form, and so this
proves that each of these powers is in normal form - so, in
particular, no such power is equal to the identity, and the generators
have infinite order.
The comments in the example below were added after the run.
gap> IsFSA(R.wa);
true #'R.wa' is a finite-state automaton.
gap> RecFields(R.wa);
[ "isFSA", "alphabet", "states", "flags", "initial",
"accepting", "table", "denseDTable", "operations",
"isInitializedFSA" ]
gap> R.wa.states.size;
1106 #The number of states of the automaton 'R.wa'
gap> R.wa.initial;
[ 1 ] #The initial state of 'R.wa' is state number 1.
gap> R.wa.flags;
[ "BFS", "DFA", "accessible", "minimized", "trim" ]
#The 'flags' fields list properties that are known to be true in the
#automaton. For example, {``DFA\"} means that it is deterministic.
#The alphabet of the automaton is the set of integers $\{1, \ldots, 6 \}$,
#the integer $i$ in this set corresponds to the $i$-th generator of
#'R', as listed in 'R.generatorOrder'.
#To inspect transitions, we use the function 'TargetDFA'.
gap> TargetDFA(R.wa,1,1);
2 # The first generator, $a$, maps the initial state 1 to state 2.
gap> TargetDFA(R.wa,1,2);
8 #It maps state 2 to state 8 -
gap> TargetDFA(R.wa,1,8);
8 #and state 8 to itself.
gap> 8 in R.wa.accepting;
true
We now know that all powers of the first generator, a, map the
initial state of the word-acceptor to an accepting state, which
establishes our claim that all powers of a are in normal form. In
fact, the same can be verified for all 6 generators.
GAP 3.4.4