MAF Tutorial 4 : A useful trick with two generator groups

In this tutorial we shall use MAF to create a word-acceptor for some 2-generator Kleinian groups with an elliptic generator and an elliptic commutator. It was through doing this that the author discovered a trick which he has found a very useful method of discovering quite large quotients of unknown groups, and new presentations for intractable groups. All the filenames mentioned are relative to the examples subdirectory, which is assumed to be the current directory for your shell.

The first group we shall look at is generated by two matrices a and b with determinant 1 , chosen so that the trace of a is 1.91+0.05i (so a is highly loxodromic), the trace of b is 1, and the trace of a*b*a^-1*b^-1 is 2*cos(2*π/7). These three parameters determine the group modulo conjugation by an element of SL(2,C). As Moebius transformations b has order 3 and a*b*a^-1*b^-1 order 7.

One might expect that an input file for this group would look like this:

_RWS := rec
(
  isRWS := true,
  ordering := "shortlex",
  generatorOrder := [a,A,b,B],
  inverses := [A,a,B,b],
  equations :=
  [
    [b^3,IdWord],
    [(a*b*A*B)^7,IdWord]
  ]
);

This input file, which you can find in lesson4/kleinian is very easy and corresponds to an infinite shortlex automatic group as one would hope. Unfortunately, if you use the word-acceptor to attempt to enumerate group elements and draw the limit set with them, it quickly becomes obvious that it does not capture the structure of the group properly, and enumerates elements multiple times.

In order to find a correct presentation it is necessary to know that we can find a matrix x with trace 0 and determinant 1 such that x*x=-I and x*a*x=-a^-1 and x*b*x=-b^-1. (One can find a suitable matrix x by computing the Lie bracket (a*b-b*a) of a and b and normalising the resulting matrix to have determinant 1). This means that the matrix a*b*a^-1*b^-1 = a*b*x*a*x*x*b*x = -(a*b*x)^2.

The reason our original input file does not work is that it does not capture the fact that a*b*x should have order 7, rather than 14. It is perhaps not obvious that this should be the case, but the particular value chosen for the trace of a*b*a^-1*b^-1 guarantees that it is.

So instead we create the following input file, which you can find in lesson4/kleinian1:

_RWS := rec
(
  isRWS := true,
  ordering := "shortlex",
  generatorOrder := [x,a,A,b,B],
  inverses := [x,A,a,B,b],
  equations :=
  [
    [b^3,IdWord],
    [(a*b*x)^7,IdWord]
  ]
);

Although x has order 4 as a matrix, as a Moebius transformation it is an involution. The group we want is the subgroup of this group that is generated by a and b, so we can find a presentation for the group by processing this input file as a coset system, using the following substructure file, lesson4/kleinian1.sub:

_RWS_Sub := rec
(
  subGenerators := [a,A,b,B],
  subGeneratorNames := [a_,A_,b_,B_],
  subGeneratorInverseNames := [A_,a_,B_,b_]
);

It is clear that this subgroup has index at most 2, so that we can process the coset system using the following command line:

../bin/automata lesson4/kleinian1 -cos -detect_finite_index

This coset system takes only a few seconds to process and creates a presentation of the subgroup we require in kleinian1.sub.rws. Unfortunately, it turns out that the new presentation is too difficult for MAF easily to be able to find an automatic structure: the number of word differences quickly exceeds 7000. Nevertheless, it is possible to show indirectly that the group is shortlex automatic for this choice of generating set.

When the coset system is processed as above, it reveals the fact that the subgroup generated by a and b actually has index 1, so that the "subgroup" is the whole group. For this type of group this always happens when the order of a*b*x is odd - when it is even the subgroup has index 2. In fact the input file with the additional generator x is quickly shown to be shortlex automatic by the following command:

../bin/automata -nokb lesson4/kleinian1

Furthermore, the gpgeowa utility can quickly find a geodesic word-acceptor for this choice of generating set, which proves that the group is word-hyperbolic and is therefore shortlex automatic for any choice of generating set. The command line option -nokb is important with this input file, because otherwise MAF takes a long time to decide that it knows enough equations to proceed to building the automatic structure. It is possible to get MAF to succeed in building a shortlex automatic structure for the input file presentation using just a and b as generators, but it is a substantial computation: one has to interrupt MAF when the number of word differences appears to have stabilised, and then restart it with all these options:

../bin/automata -nokb -resume -force_multiplier -conjugation 0 -special_overlaps 0 -no_weak_acceptor lesson4/kleinian1.sub.rws

There are 9450 word differences altogether, of which 7908 are primary. Despite the large number of word-differences, the automatic structure is comparatively simple to build (the general multiplier has around 40000 states), but it is essential that almost all the word differences should be known first.

The most natural automatic structure for this group arises from the generating set x,b*x,a*x. All three of these elements are involutions. The substructure file examples/lesson4/kleinian1.sub1 contains this generating set with the generators named p,q,r. (The order of the generators here is not particularly important; but this particular order turns out to be natural geometrically). Once again we can process this as a coset system:

../bin/automata lesson4/kleinian1 -cos -detect_finite_index sub1

This completes in a few seconds and generates the input file kleinian1.sub1.rws. This time the command ../bin/automata lesson4/kleinian1.sub1.rws completes almost instantly, without the need for any command line options at all.

There are only 80 word differences, and the multiplier has only 343 states. MAF's C++ library contains two methods for translating the acceptor for the p,q,r alphabet into one for the alphabet a,A,b,B. The first method is implemented by the gpxlatwa utility. The second method is not the theoretically correct method for performing a translation of an automatic structure into a new alphabet, (in this particular case it translates all the even length words, but none of the odd length words), but it works well enough for the purpose of drawing the limit sets of such groups, as the picture on the right shows. (Of course, one could simply draw the limit set using p,q,r as the generators, but it is useful to be able to use do this, if one wants to draw the limit set with a coloring dependent on the generators in the word whose limit point is being plotted.) The picture shows that our group contains the 2,3,7 Von Dyck group as a subgroup (and the substructure file lesson4/kleinian1.sub2 is such a subgroup). Indeed it contains very many subgroups isomorphic to it - the hole in the centre of each roughly triangular piece of the limit set is an image of the outside of the hyperbolic disk (as can be seen in this zoom from the same limit set).

Another example

../bin/automata lesson4/kleinian2 -cos -nokb

../bin/automata lesson4/kleinian2 -nokb (to create the automatic structure for the group)

../bin/gpxlatwa kleinian2 (to create a translation of the word acceptor into the alphabet without x). This creates the file kleinian2.sub.xwa.

Applications

The technique of adding an extra involutory generator which conjugates the existing generators to their inverses can be applied to groups with more than 2 generators. It allows a group generated by n generators to be replaced by one generated by n+1 involutions, which will reduce the size of the monoid generating alphabet. Of course, in general there is no reason for the group to stay the same when one does this. The subgroup generated by the original generators has been quotiented by the equations that are the reverse of the original equations in the input file. However, the author has frequently found this a very useful technique for discovering quotients, which we shall see in action in the next tutorial. And, in the case where the group in the input file is supposed to correspond to a group generated by two matrices, it must be a valid technique for finding a new generating set.

More generally, one can look for other types of quotient that arise by adding a new generator which generates other symmetries between the original generators, or by simply applying appropriate transformations to some or all of the original axioms.

Unfortunately, in the author's experience, such extreme differences between the behaviour of "nearby" generating sets, as seen in this example, are the exception rather than the rule (though it works well for other similar Kleinian groups); at any rate, if there is a change of generating set that can convert an intractable group into a tractable one, it may be difficult to find.