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 *Q _{33}* 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 *Q _{37}* similar techniques again yield a quotient of order 124488 in which

`[(x*y*x*Y)^`*n*,IdWord]

for various values of For one of the 6 groups listed as having unknown structure, *Q _{27}*,