In this tutorial we shall find out how using a wreath product wordordering can make the automata for a group much smaller than the corresponding "shortlex"
automata, but that, once again, the choice of generating set has a substantial impact. When a group is large and finite using a wreath product wordordering may be the only way to study the group as whole using MAF.
The examples/lesson3 directory contains various input files for various groups as listed in the following table:
File name(s)  Group 

antislice antislice_recursive 
The "antislice" subgroup of the Rubik cube group. This is the group generated by the moves which turn opposite faces in the same sense relative to the surface of the cube, for example the to execute the move corresponding to the "rl" generator one would turn the top edge of the right face away from one's body and the top edge of the left fact towards it. 
6561#8 6561#8_recursive 
A presentation of a group of order 6561 first mentioned in the paper "Groups of Deficiency Zero". This is a very difficult presentation for coset enumerators. KBMAG also finds this presentation tricky. 
m22 m22_recursive 
A presentation of Mathieu group M_{22} from ATLAS. The generators have been named a and c instead of a and b for a reason that will be revealed later. 
In each case the first presentation uses the usual wordordering "shortlex"
, and the second presentation uses the "recursive"
wordordering. "recursive"
and "rt_recursive"
orderings are the easiest wreath product orderings to use because
the level
field does not need to be set. For any input file, they also usually give the smallest minimal confluent rewriting system (by number of equations) of any of the supported wordorderings. MAF often finds a minimal confluent rewriting system more quickly with "recursive"
than "rt_recursive"
ordering, but this is highly dependent on the presentation, and even the ordering of the generators.
It is suggested that you process all six, and at least the first four, of these presentations, using the command automata nowd in each case. If you have KBMAG available you may also care to try running KBMAG's kbprog against these files.
In the table below are listed the number of equations in the minimal confluent rewriting system for each of the input files, followed by the state count for the index automaton, together with the run time required on the author's very old Windows PC. It is likely the times required will be much shorter for you.
File  Group order  Run time (seconds) 
Primary equations 
Index automaton states 

antislice  12288  4  8225  5938 
antislice_recursive  12288  < 1  94  226 
6561#8  6561  40  9662  5295 
6561#8_recursive  6561  27  26  65 
m22  443520  73  99286  294132 
m22_recursive  443520  82  35765  209622 
If we were to make a judgement based only on the first four rows of the table we would conclude that "recursive"
wordordering is a much better choice than "shortlex"
. The last two rows of the table are therefore a disappointment, although the automata are somewhat smaller, the difference is much less marked than for the first two groups, and the run time is longer.
Why should the behaviour of "recursive"
wordordering be so good with the first two groups, and so comparatively poor with m22? It is almost certainly something to do with the fact that the first two groups are solvable (and all the cyclic factors are very small) , while the last group is a simple group. Similar behaviour will be observed with many other finite groups.
It is possible to do better with m22 however. In the first place, in the m22 input file, the recommendation given in the previous tutorial, to order generators so that if one of them is an involution it comes second, has not been followed. If we do that the number of equations and states is reduced to 28436 and 178826, and the run time drops slightly as well, to 80 seconds.
Another thing we can try, is to follow the other recommendation of the previous tutorial, and try to make our first generator a torsion element with high order. Looking at the presentation of m22 we see that a*c
has order 11, so this is an obvious candidate. The easiest way to alter the presentation in this case is as follows, (and it is suggested you actually do this).
b
and B
. The new generators should come first. Remember to add B
and b
to the inverses
field as well.[b,a*c]
to the equations
field.c
will have been eliminated in that file; if run with no special command line options simplify will eliminate generators if possible, and will try to eliminate later generators before earlier ones.
If you do all this you will find that the new presentation has a confluent rewriting system with 18292 equations and 104667 states. This is considerably smaller than our first attempt for this group, but the difference from the "shortlex"
case is still much less than for the other groups. Worse, the run time with the new presentation is considerably longer, 146 seconds on the author's PC.
We can do much better if we can find a 2generator subgroup of low index in M_{22}, that is generated by one of the original generators and a word in the original generators. Then if we use "recursive"
ordering and put the new generator and the original generator needed for the subgroup first, and the other generator for the group last we can hope to find a much smaller rewriting system, because all the group elements will have a normal form of the type w*h where w is a coset representative and h is an element of the subgroup generated by the first two generators. This is similar to what we get with a coset system.
Somehow or other the author knows that a suitable candidate for the new generator, which this time we call d
is w^1*c*w
where w = a*c*a*c*a*c*a*c*a*c*c*a*c*a*c*c
. The subgroup <d,a
> is a largest maximal subgroup of M_{22}.
Unfortunately, if we simply add d
and D
as new generators, proceeding in a similar way to when we added b
and B
(but not running simplify), we run into a difficulty: for reasons that are unclear, automata finds the new presentation extremely difficult to process, whether we use "shortlex"
or "recursive"
ordering. The only way to make automata able to deal with the new presentation quickly is to use a wreath product ordering that causes d
to be reducible. If we do that then the file is processed more or less as before, but of course then we are no further forward.
We can solve the difficulty by using a coset system. The substructure file m22.sub defines the required subgroup of M_{22} in a form suitable for a coset system with named subgroup generators. d
and D
are defined as above, but we also have to add a new generator, called a_
, as a synonym for a
.
We can create and process the required coset system with the command automata m22 cos confluent nowd . This is a reasonably substantial computation, and takes about 6 minutes on the author's PC.
The output contains two files of interest: m22.sub.rws and m22.cos.kbprog. One would hope that if we took the equations of the former, which forms a confluent rewriting system for the subgroup <a,d> and added them to our new input file with the extra generator d
and D
, that this would be enough help for MAF to be able to process the input file quickly. Unfortunately this is not the case, perhaps because there are no short relations relating c
to d
. So we try a messier, but effective approach.
The file m22.cos.kbprog contains a large number of equations relating all the generators we are now
interested in. Unfortunately some of them are in the form of coset equations, and we have two equal generators a
and a_
that we would like to merge.
The following trick can be used to convert an output file for a coset system with named generators into an input file for the group, where the subgroup generators are now additional group generators. (In future an option will probably be added to simplify to do this automatically.)
Open the file with a text editor. Remove the ordering
and level
information by deleting the relevant lines. Also, make the coset symbol _H
invertible, by making it its own inverse. Change the order of the generators to match our requirements: in this case we want to move d
and D
from the end to the beginning of generatorOrder
and inverses
. We also add a new equation in the equations
section: [_H,IdWord]
, so that
the coset symbol becomes a trivial generator. Below you can see the relevant parts of the file before and after
we make these changes:
Before  After 

generatorOrder := [a,c,C,_H,a_,d,D],
ordering := "wreathprod",
level := [2,2,2,1,1,1,1],
inverses := [a,C,c,,a_,D,d],
equations :=
[
[_H*a,a_*_H],

generatorOrder := [d,D,a,c,C,_H,a_],
inverses := [D,d,a,C,c,_H,a_],
equations :=
[
[_H,IdWord],
[_H*a,a_*_H],

The file can now be saved, and is ready for processing by simplify. Eliminating the equations we just computed may seem perverse, but there is a good reason for doing so: when you use an output file as an input file but the wordordering has changed MAF can struggle to get started, especially when, as it would be here, the change is to a different wreath product ordering. Because the file is very large, we run simplify several times with varying options, and after each run we replace the original with the simplified file, as follows:
simplify raw no_simplify m22_new overwrite
On this first run the unwanted generators a_
and _H
are eliminated, but the only other processing is to remove cyclic conjugates of relators. The raw option is needed to prevent MAF from creating an object to filter the axioms, which would take too long on this initial run. The output file is about 50% of the initial size, about 5MB.
On this second run it is a good idea to press Ctrl+C when status messages about conjugation start appearing. simplify takes this as a hint to stop conjugating relators, which will speed up processing substantially on this run. A substantial number of relators are removed on this run, because they are "almost" conjugates, of another relator, and the small amount of conjugation done at the beginning allows most of these to be recognised and eliminated. The file size is now about 1MB.
simplify keep_generators no_simplify m22_new overwrite
This time allow simplify to run normally, and don't press Ctrl+C. Almost all the remaining relators that are easy consequences of others are removed. This reduces the size of the file to about 20K
simplify keep_generators m22_new overwrite
Finally we do one run of simplify proper. It will reduce the size of the input file by about 1/3 to 13Kb, though it would be possible to do better than this by specifying the kb command line option to simplify.
The final version of m22_new is now ready for use. It is only necessary to set the wordordering to our desired wordordering "recursive". Once again we process the file with automata nowd. After all our hard work it is a relief to find that the final file is processed in about 30 seconds. This time there are only 1147 equations, and the index automaton has 7941 states.
Finally, we shall perform the same trick on the next Mathieu group M_{23}. That group has more than 10 million members. It will be difficult to create a confluent rewriting system for it using "shortlex"
wordordering on all but the largest computers, and even when "recursive"
ordering is used the file is difficult to process. We could use the same method that we used to create our new presentation of M_{22}, but it turns out that this time MAF finds it easier to process an ordinary input file for M_{23} with extra generators, than a presentation created from a coset system. The files m23 and m23_4gen contain respectively a twogenerator and a four generator presentation of M_{23}. The latter defines two extra generators [c,b*a*b*a*B*a*b]
, and d
, which is defined in exactly the same way as in m22.sub. automata nowd takes about twenty minutes to process this file on the author's PC. The confluent rewriting system has only 1202 equations.