MAF Tutorial 3 : Using wreath product word-orderings

In this tutorial we shall find out how using a wreath product word-ordering 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 word-ordering 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:

In each case the first presentation uses the usual word-ordering "shortlex", and the second presentation uses the "recursive" word-ordering. "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 word-orderings. 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.

If we were to make a judgement based only on the first four rows of the table we would conclude that "recursive" word-ordering 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.

Reducing the state count for m22

Why should the behaviour of "recursive" word-ordering 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).

1. Edit the file m22_recursive and add a pair of generators, called b and B. The new generators should come first. Remember to add B and b to the inverses field as well.
2. Add a new axiom [b,a*c] to the equations field.
3. Now run the simplify utility against m22_recursive like this: simplify m22_recursive. A new input file called m22_recursive.simplify will be created and the generator 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.
4. Now run automata -nowd against m22_recursive.simplify. (Although input files usually do not have a suffix MAF does not mind at all if they do).

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.

Another approach

We can do much better if we can find a 2-generator subgroup of low index in M₂₂, 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₂₂.

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.

A trick with coset systems

We can solve the difficulty by using a coset system. The substructure file m22.sub defines the required subgroup of M₂₂ 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.)

1. Copy the output file for the coset system, in this case m22.cos.kbprog, to a new filename, say m22_new.

2. 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],

3. 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 word-ordering 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.

   simplify -keep_generators -no_simplify m22_new -overwrite
   

   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 word-ordering to our desired word-ordering "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.

Onwards and upwards

Finally, we shall perform the same trick on the next Mathieu group M₂₃. That group has more than 10 million members. It will be difficult to create a confluent rewriting system for it using "shortlex" word-ordering 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₂₂, but it turns out that this time MAF finds it easier to process an ordinary input file for M₂₃ with extra generators, than a presentation created from a coset system. The files m23 and m23_4gen contain respectively a two-generator and a four generator presentation of M₂₃. 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.