Although it cannot (yet) search systematically for them, MAF can often disclose a great deal about about the quotients of an unknown group, if users are prepared to experiment a little. This tutorial shows how the use of various MAF utilities can discover generators for subgroups with very high indexes and correspondingly large quotients. This may guide us in deciding how to proceed. If, for example, one has already succeeded in computing the automata for a quotient of order several million, and then discovers another quotient that implies the group has several billion elements at least, then it may become necessary to transfer our attention to a subgroup, because it is unlikely that enough memory will be available to compute a solution to the word problem for the whole group.
The file examples/lesson6/q33_xy is a presentation of the group Q33 mentioned in the preprint "One relator quotients of the modular group". The input file is shown below.
_RWS := rec
(
isRWS := true,
isConfluent := false,
generatorOrder := [y,Y,x],
ordering := "shortlex",
inverses := [Y,y,x],
equations :=
[
[y^2,Y],
[(x*y)^4*(x*Y)^2*(x*y)^2*(x*Y)^4*(x*y)^2*(x*Y)*(x*y)*(x*Y)^2),IdWord]
]
);
The structure of this group is unknown. In this tutorial we will find the largest known finite quotient of this group. In fact the subgroup which gives this quotient can easily be found by intersecting the derived subgroup with the subgroup which is the normal closure of the word you get by interchanging y and Y in the long relator: in other words, using the same technique as we used in the previous tutorial. In this tutorial we will use another technique : we shall use gpsublowindex to find a number of subgroups, and intersect their coset tables. It turns out that it is only necessary to find the subgroups of index 42 or below in order to do this. Of course in practice one would not know this in advance, and one would simply look as far as possible - the running time for gpsublowindex increases rapidly with the index and the number of group generators.
The following command line can be used to do this, assuming your shell has the directory containing q33_xy as the current directory:
../../bin/gpsublowindex q33_xy -stop 42 -table -rws -simplify -named
This command tells gpsublowindex to generate presentations for the subgroups and to output the coset table for the subgroups using named subgroup generators. The -simplify option improves the quality of the presentations by removing some unnecessary subgroup generators. If this option is not used the subgroup will usually be given by a much larger generating set that includes several trivial subgroup generators.
This command will take a minute or two to run, and outputs four coset tables for subgroups of index 42, three for subgroups of index 28, and one each for subgroups of index 2,3,6,14,19 ans 38. We can intersect the subgroups by using the fsaand utility repeatedly as follows:
../../bin/fsaand q33_xy.coslow_i2_1.cosets q33_xy.coslow_i3_10.cosets xx
../../bin/fsaand q33_xy.coslow_i6_13.cosets xx xx
../../bin/fsaand q33_xy.coslow_i14_2.cosets xx xx
...
../../bin/fsaand q33_xy.coslow_i42_12.cosets xx xx
At each stage the file xx that is output is a coset table for all the subgroups we have intersected so far. The final coset table has 124488 states (ignoring the inaccessible failure state). In fact we could a much smaller set of subgroups to intersect to get this subgroup - the subgroups of index 6,19,28 and two of the subgroups of index 42. We next need to find some generators for this subgroup. The easiest way to do this is to "and" the word acceptor for a suitable automatic group with the coset table. One can use the free group on the same generating set for example. In this case the obvious group to use is the modular group. So we create the word acceptor for the modular group by running automata against an input file for the modular group, and then using fsaand again as follows:
../../bin/automata modular
../../bin/fsaand modular.wa xx xx.wa
Now we can use fsasenumerate to enumerate some words contained in this subgroup:
../../bin/fsaenumerate 1 36 xx.wa
This produces a file xx.wa.enumerate containing 24 words beginning with x and 12 each begining with y and Y. We create a new input file, q33_xyq, containing the 12 words beginning with y as extra relators (we expect the other words to be cyclic conjugates of these). In principle there is no reason why this subgroup should be normal, but since the paper says such a quotient exists it is reasonable to hope that we have found the right subgroup. We can use gptcenum to check if we have enough relators to give a new quotient:
../../bin/gptcenum q33_xyq -table -strategy long
This quickly confirms that we have a quotient of order 124488. We then double check that this has the same coset table as we found by intersecting subgroups using fsalequal
../../bin/fsalequal xx q33_xyq.cosets
fsalequal confirms that the coset tables accept the same language, and thus that the subgroup generated by the normal closure of these 12 words is a subgroup of index 124488. In fact, if we run simplify against q33_xyq we find that only one of these words, (y*x*y*x*Y*x)^6, is needed as an extra relator.
In principle we could now create a substructure file for a normal closure coset system containing this word as the generator whose normal closure is to be found. Unfortunately MAF is not able to compute the presentation of this subgroup currently, because the multiplier has more than 32766 initial states. To compute the presentation it is necessary first to find a presentation of a larger subgroup and then find the subgroup as a subgroup of this. We can do this as follows:
../../bin/gpsubmake -derived q33_xy
../../bin/automata -cos q33_xy sub_derived -detect_finite_index -confluent
../../bin/simplify q33_xy.sub_derived.rws
../../bin/gpsubmake -named q33_xy sub_derived
../../bin/automata -cos q33_xy sub_derived_named -detect_finite_index -confluent
../../bin/reduce -kbprog q33_xy -cos sub_derived_named "-H*(y*x*y*x*Y*x)^6"
reduce will tell us that this word reduces to b*A*b*A^2*B^2*a*B*a^2*B*_H.
We could now copy q33_xy.sub_derived_named.rws to q33comm and create q33comm.sub as a substructure file for the normal closure of b*A*b*A^2*B^2*a*B*a^2*B. gptcenum will quickly confirm that this subgroup has index 20748. We can try to create a subgroup presentation using gptcenum directly, but once again this requires too many generators for MAF to be able to handle. automata will probably evenutally be able to compute a subgroup presentation from the multiplier for the general multiplier, but unfortunately it turns out that it performs particularly poorly against this coset system: it is able to prove that the index is finite quickly, but then takes a very long time to check partial confluence. In future automata will probably be changed to use coset enumeration for this check.
We could repeat the process - by finding a presentation of the derived subgroup of q33comm and finding generators for our desired subgroup in this group. However the presentation of the derived subgroup q33comm already has a largish number of generators, and if we reduce this with simplify -keep_going to 10 or 12 monoid generators (the latter is probably better, and is found by all strategies apart from strategy 3, which eliminates one more pair of generators), the relators become unpleasantly long.
In fact even if we were to compute a subgroup presentation it would almost certainly be completely intractable, except that simplify -abelian would probably be able to show that the subgroup was a perfect group. Unfortunately this behaviour seems to be fairly typical with difficult presentations.
The directory examples/onerelq contains several more presentations of difficult one relator modular group quotient groups mentioned in this paper. For several of these the author has been able to find very large finite quotients, though not in all cases the largest finite quotient. For example for Q37 similar techniques again yield a quotient of order 124488 in which xyxY has order 7*19. Experimenting by adding an additional relator of the form [(x*y*x*Y)^n,IdWord] for various values of n
reveals another large finite quotient of order 10! in which xyxY has order 8. Most low values of n give trivial quotients, but for n ≥ 10 there are numerous values where neither automata nor gptcenum collapse quickly.
For one of the 6 groups listed as having unknown structure, Q27, automata is able to show that the group is in fact finite and isomorphic to the quotient that can be found with the same sort of techniques. However, this is a computation that requires several hours of CPU time and requires the 64-bit version of MAF.