In this tutorial we shall use MAF to investigate three more quotients of the 2,3,7, Von Dyck group: the quotients in which the commutator has order 6, 7, and 9. Input files for the three groups can be found in lesson5/7236, lesson5/7237, and lesson5/7239 and lesson5/2379.
automata will process both 7236 and 7237 very quickly. The output from automata tells us that both groups have order 1092. (If you miss the line of output that tells you the size of a group you can use the command fsacount groupname.wa or fsacount groupname.reduce to find the size). So it is natural to wonder if these groups might actually be isomorphic. Since the groups are finite we can use gpcclass to compute the conjugacy classes of the elements, using the command gpcclass 7236 or gpcclass 7237. This program computes an automaton groupname.cclasses which can be used to find the conjugacy class representative for any group element, and a second file groupname.cc_statistics which lists the number of elements in each conjugacy class and the order of the elements in each class. This tells us that these two groups also have matching conjugacy classes, which suggests that the groups indeed might be isomorphic. The utility gpmorphism can be used to find a homomorphism from a group to a group with a known structure. The command
../bin/gpmorphism -check_index lesson5/7236 lesson5/7237
will find such a homomorphism. It also reports the image of the index. Clearly, if it can find one of index 1, then we have an isomorphism, and indeed it can do so. Incidentally, even though one could run gpmorphism without first running gpcclass this is not a particularly good idea: gpmorphism will use the output from gpcclass to eliminate as many equivalent homomorphisms as possible, and will run faster as a result. gpmorphism can take a very long time to run if the group that is the source of the desired homomorphism has many generators, or if the target group is large. In principle, gpmorphism can find homomorphisms where the target is infinite. However, in practice such computations will only succeed if the images of all the generators are short words in the generators of the target group.
If one runs the command ../bin/automata lesson5/7239 -force_differences then it quickly becomes apparent that there is very little hope of finding an automatic structure. On the other hand, if one runs ../bin/automata lesson5/7239 -confluent for a while there is no sign that this will ever succeed. So let us see what, if anything, we can find out about the group using the trick described in the previous tutorial. First of all we move to working with a 2-generator presentation using the generators of order 2 and 3.
_RWS := rec
(
isRWS := true,
ordering := "shortlex",
generatorOrder := [a,b,B],
inverses := [a,B,b],
equations :=
[
[b^3,IdWord],
[(a*b)^7,IdWord],
[(a*b*a*B)^9,IdWord]
]
);
This input file can be found in lesson5/2379. The main reason for abandoning our previous policy for choosing generators, as followed in lesson5/7239 is that in the new input file our group is a quotient of the modular group. In this group, making a the generator of order 2, and b the generator of order 3, any quotienting word is a product of terms a*b and a*B, which makes it fairly simple to explore possible quotients systematically. In general, the first quotient to try to find is the abelian quotient, which you can create using simplify -abelian. There is no point doing that here, because 2,3,7 is a perfect group. However, we can try our trick from the previous tutorial. This suggests the following input file.
_RWS := rec
(
isRWS := true,
ordering := "shortlex",
generatorOrder := [a,b,B,x],
inverses := [a,B,b,x],
equations :=
[
[x*a*x,a],
[x*b*x,B],
[(a*b*x)^9,IdWord],
[b^3,IdWord],
[(a*b)^7,IdWord],
[(a*b*a*B)^9,IdWord]
]
);
We expect that it will turn out that x can be expressed as a word in a and b. Therefore we modify the input file slightly to use a wreath product ordering in which a and b are at the same level (so that words in a and b alone are decided on "shortlex" ordering, and x is at a higher level, and so will be eliminated if possible. So we finish up with the following input file, which can be found in lesson5/2379q:
_RWS := rec
(
isRWS := true,
ordering := "wreathprod",
generatorOrder := [a,b,B,x],
level := [1,1,1,2],
inverses := [a,B,b,x],
equations :=
[
[x*a*x,a],
[x*b*x,B],
[(a*b*x)^9,IdWord],
[b^3,IdWord],
[(a*b)^7,IdWord],
[(a*b*a*B)^9,IdWord]
]
);
We process this with automata using the following command line:
../bin/automata -nowd lesson5/2379q
automata will immediately tell us that x can indeed be eliminated; it is (a*b*a*B)^4*a*b, and also that 2379q is a a finite group of order 504. If we remember the orders of the first few non-abelian simple groups we shall probably suspect that either this quotient is an extension of the simple group of order 168, or it is the simple group of order 504. In fact, if one consults the ATLAS web site, one can find a standard presentation of L2(8) and a little experimentation with reduce will make it clear we have the latter group: our input file has all but one of the axioms of the latter group; the missing axiom is [((a*b*a*b*a*B)^2*a*B)^2,IdWord], and the following command shows that this axiom is true in our quotient:
..bin/reduce lesson5/2379q "((a*b*a*b*a*B)^2*a*B)^2)"
reduce produces as output:
Word reduces to: IdWord
The quotes around the second argument to reduce are need because shells often attach a special meaning to non-alpha characters such as ^. This is enough to show that 2379q is a quotient of L2(8), and since it has the same finite order it is surely isomorphic to it.
The next step is to discover more about the subgroup which gives us this quotient. We can do this by creating the following substructure file, which you can find in lesson5/2379.sub.
_RWS_Sub := rec ( normalSubGenerators := [(a*b*a*B*a*b*a*B*a*b*a*B*a*b*a*B*a*b)^2] );
Here, the word whose normal closure we are going to look for is x^2, where we have eliminated x and replaced it with the right hand side of the equation that eliminates x in lesson5/2379q.kbprog.
We now process this substructure file as a coset system using the following command line:
../bin/automata lesson5/2379 -cos -detect_finite_index
Generally the author would also use the -confluent command line option here as well, but in this particular case, although that makes automata run slightly more quickly, the presentation that is output is then a little more redundant. In cases where automata can process a coset system quickly it is often worth experimenting with the options used, to try to get the best presentation of the subgroup.
MAF has now created an input file, lesson5/2379.sub.rws, for the normal subgroup which gives 2379q as its quotient. If you examine this file you will see that it has around 60 monoid generators, which is on the high side. It is appropriate to try to simplify this presentation first. We shall also look for the abelian quotient of our new group.
Let us do the latter first:
../bin/simplify -abelian lesson5/2379.sub.rws
This runs very quickly, and produces lots of output like this:
Eliminating generators _g64 _g63 Presentation size is now 58,39,125 Eliminating generators _g61 _g62 Presentation size is now 56,38,124 ... Eliminating generators _g17 _g18 Presentation size is now 14,0,0 Creating new rewriting system
The line Presentation size is now 14,0,0 tells us that the abelian quotient of our subgroup is a free abelian group of rank 7, which you can confirm by examining lesson5/2379.sub.rws.simplify. So now we know that 2379 is an infinite group.
Now we run simplify again, this time without the -abelian option.
../bin/simplify lesson5/2379.sub.rws
This time the output looks like this:
Eliminating generators _g64 _g63 Presentation size is now 58,48,159 ... Eliminating generators _g17 _g18 Presentation size is now 14,23,226 Creating new rewriting system
Examining lesson5/2379.sub.rws.simplify again, we see that the monoid generators are now 14 of the first 16 generators from the original input file. This means we can easily create a new coset system for the same subgroup, this time using named subgroup generators. This is likely to be a little easier to make sense of. In order to do this you need to understand that the G-words for the subgroup generators are the initial states of the MIDFA coset system general multiplier, as found in lesson5/2379.cos.migm. In a coset system without named subgroup generators, the names MAF invents for the generators all take the form _gn. The first number used is always 1 more than the number of main group generators, and the subgroup generators are then taken in the order they appear in the coset general multiplier. (MAF goes to quite a lot of trouble to arrange these in a sensible order, whereas in KBMAG they will not be in a useful order).
The gpsubmake utility is able to create the required substructure file. The required command line is
../bin/gpsubmake -named ../lesson5/2379
This generates the file lesson5/2379.sub_named, which you might like to compare and contrast with lesson5/2379.cos.migm.
This file can also be processed in the same way as before using the following two commands:
../bin/automata lesson5/2379 -cos sub_named -detect_finite_index -no_h
../bin/simplify lesson5/2379.sub_named.rws
Examining the presentation of the subgroup lesson5/2379.sub_named.rws makes it clear that several of the generators do commute with each other. In such cases it is often worth experimenting with "recursive" word-ordering. So we copy lesson5/2379.sub_named.rws.simplify to lesson5/2379_i504 and change the word-ordering to "recursive". Perhaps surprisingly, automata can process the new input file almost instantly. Examining the output file lesson5/2379_i504.kbprog should lead you to suspect that the group only fails to be abelian because c and e do not commute, and adding [e*c,c*e] as an axiom will quickly confirm this. So we create a new input file for this group lesson5/2379_i504y, adding a new pair of generators y,Y and an axiom [y,c*e*C*E]. Once again MAF can process this file very quickly, and it tells us that y is in fact an involution.
It is now not too difficult to create a new input file lesson5/2379_recursive, which uses the subgroup generators as additional generators. In principle this only needs to include the definitions of the new generators. However, for the file to be processed quickly it is necessary to add all the axioms from lesson5/2379_i504y. In fact this input file is finely poised between being very difficult and very easy for MAF: if run with no special options against it automata will use up vast quantities of memory with no sign that it will ever succeed. However, the following command line finds a confluent rewriting system in a few seconds at most:
../bin/automata lesson5/2379_recursive -strategy long -nowd
Examining lesson5/2379_recursive.kbprog it is easy to see that y is central in the whole group, and also that there are numerous free abelian subgroups of rank 2 and rank 3. This shows that the group cannot possibly be word-hyperbolic. It is also easy to see that y generates the derived subgroup of lesson5/2379_i504y, so we have in effect found the derived series of 2379.