Software for automatic groups, isomorphism testing and finitely presented groups.

D.F.Holt and Sarah Rees

The purpose of this note is to give a brief description of some software that has been developed by the authors (partly in collaboration with David Epstein), and which was demonstrated by them at the Workshop at the University of Sussex. It is all written in the C language and designed for use on UNIX systems. It is available for distribution (via ftp) free of charge, with documentation included, mainly in the form of UNIX-style manual entries. Input and output is all done using files in a specially designed format. Usually, the user only needs to create files containing group presentations prior to running the programs. There are three principal components of this package, which we shall describe individually.

1 Automata

This is a sequence of programs that is designed to compute the automatic structure of a short-lex automatic group. For general information on automatic groups see [ECHLPT 92], and for a detailed description of the algorithms employed in these programs see [EHR 91]. These programs were written together with David Epstein.

Let G = ⟨X|R⟩ be a finitely presented group, where X is ordered and closed under inversion. For each g ∈ G, let w(g) be the lexicographically least (using the given ordering of X) amongst the shortest words in X that represent g. Then G is said to be short-lex automatic (with respect to the ordered set X) if the following hold.

(i) There is a finite state automaton W called the word-acceptor with input alphabet X, which accepts precisely the words w(g) for g ∈ G.

(ii) For each x ∈ X, there is a finite state automata M(x) with input alphabet (X∪{$})×(X∪{$}), which accepts the pair of words (w_{1}, w_{2}) if and only if w_{1} and w_{2} are both accepted by W and w_{1}x and w_{2} represent the same element of G. (The extra symbol $ is used only to append on to the end of the shorter of the two words w_{1} and w_{2} to make them have the same lengths.) The automata M(x) are known as the multipliers.

It is important to note that, although the general property of a group being automatic is independent of the generating set, the property of being short-lex automatic may depend on both the choice of X and on its ordering.

The input to the programs as supplied by the user is simply a file containing a finite group presentation, where the ordering of the generators is defined by the order in which they appear. In principal, if the group is shortlex automatic with these generators, then, given enough time and space, the programs will compute the word-acceptor and multipliers, and verify that they are correct. These are all output to files in our standard format. For examples requiring more time or space than is available, it can happen that a word-acceptor is produced, or even a word-acceptor and multipliers, but without a complete verification. In this case, it is possible but not certain that they will be correct. In any case W will accept all of the words w(g), but in case of incorrectness it may accept some additional words.

Some other programs are available that operate on these automata. For example it is possible to enumerate systematically the accepted words, to decide whether this set is finite or infinite, and to determine its cardinality if it is finite. The finiteness and the order of G can therefore be determined, provided that the verification process has been completed. There is also a program that will draw a picture of a finite state automaton, as a labelled graph, in an X-window; the positions of the points and labels can be adjusted interactively, and a postscript version of the final result can be generated. Finally, there is a program (written by Uri Zwick in C++) that can compute the growth-rate polynomial of the group from the word-acceptor.

Currently, the automata package can complete within a reasonable period of time on various classes of examples. These include Euclidean groups, Coxeter groups with up to 4 generators, 2-dimensional surface groups, some 3-dimensional hyperbolic groups, and some knot groups. We are constantly attempting to extend its scope to include more examples.

2 IsomorphismTesting

This is a program that attempts to decide whether two given finitely presented groups are isomorphic or not. A more detailed description can be found in [HoR 92a]. This problem is of course known to be undecidable in general, and so any such program is bound to fail on some inputs, but we might nevertheless hope to achieve success in many cases. The basic idea is to try to prove isomorphism and nonisomorphism alternately, for increasing periods of time, hoping to succeed eventually in one of these two aims. It is also possible, of course, to instruct the program to look only for an isomorphism, or for a proof of nonisomorphism. The package is arranged as a master program which calls other programs to perform specific calculations on the groups. These other programs can also be used individually if required. This can be advantageous if the user has some idea in advance of which particular calculations are likely to be the most helpful or decisive. The user has only to create files containing the two group presentations before starting.

We attempt to prove isomorphism, by running the Knuth-Bendix procedure on the group presentations (see, for example, [Gil 79]), in order to generate a word reduction algorithm for words in the generators. In cases of success, this will enable us to verify that a particular map from one group to the other is an isomorphism. In order to find this map, we have to use an exhaustive search, which often becomes rapidly impractical as the word lengths of the images of the generators under the map increase. We can offset this a little by using various additional tests, such as checking that the induced map between the abelian quotients is an isomorphism, or capable of being extended to an isomorphism when only some of the generator images are known. In addition, if both groups can be mapped onto a suitable finite permutation group, then we can check that our map or partial map can induce an automorphism of the permutation group. In principle, if the two groups are isomorphic, then this algorithm would eventually find an explicit isomorphism, but in practice the required time would eventually be prohibitive in many cases.

We attempt to prove nonisomorphism by examining the finite (and abelianby-finite) quotients of the two groups, and checking to see if they correspond. This method was used successfully by Havas and Kovács to distinguish between various knot groups (see [HaK 84]). Unlike the isomorphism test, this approach cannot be guaranteed to work in general, even in principle, since there are certainly nonisomorphic groups whose finite quotients are the same; for example, finitely presented infinite simple groups. Furthermore, for reasons of space, it is only possible to look for finite quotients of reasonably small order, and in the case of finite nonabelian simple images, we have to look for epimorphisms onto each simple group individually. However, for various classes of groups that arise naturally from geometry and topology, such as knot groups and fundamental groups of manifolds, this approach seems to be quite successful. Indeed, this is one of the applications that we had in mind when planning this program. More details of the method for searching for finite quotients are given in the next section.

This program has been applied successfully to a number of genuine problems that have been passed on to us. For example, in [Kel 90], a collection of about 30 pairs of link groups is considered, each pair of which came from identical links with different orientations. All of these are groups with four generators and up to four relations. Some of these pairs were isomorphic and some not, and the program was able to decide this in all cases. Two of these cases took some hours of cpu-time, but all of the others were very quick.

3 Quotpic

This is a graphics package that the authors are currently developing for plotting the finite quotient groups of a given finitely presented group G. A more detailed description will appear in [HoR 92b]. For the graphics display, an X-windows server is required, which may be coloured or black and white. The user must first make a file containing the given presentation of G; thereafter, all computations are done interactively, by using a mouse to select menu options. A finite quotient Q = G/N of G is represented in the display by a vertex, which can be thought of as being labelled by the normal subgroup N. Given two such vertices M and N such that |G/M| has more prime factors (counted with repetition) than |G/N|, M will always appear lower than N. If N is joined to M either by an edge, or by a sequence of edges passing through intermediate vertices, then the inclusion M ⊂ N holds. Initially, there will be a single vertex G corresponding to the trivial quotient; further vertices are plotted as the corresponding quotients are calculated. The system can output a postscript file for producing a good hard copy of the lattice that has been plotted. It operates by calling up other programs to perform individual calculations; these are more or less the same programs that are used in the isomorphism testing package for computing finite quotients.

Since all groups G of moderately small order are extensions of a soluble group N by a group T, where T is either trivial or satisfies S ⊆ T ⊆ Aut(S) with S a direct product of isomorphic nonabelian simple groups, we have provided the system with two basic facilities. The first is to find the epimorphisms from G onto the relevant subgroups of Aut(S), for all appropriate groups S. This is done interactively by the user, by selecting the group S from a list on the menu. (The list of groups S can easily be extended if required.) The second facility can be described as follows. Given a finite quotient G/M of G of sufficiently small order (a few thousand), find those quotients G/N of G with N ⊂ M and M/N an elementary abelian p-group for some prime p. We achieve this as follows. First, we use an abelianized Reidemeister-Schreier process to compute the largest elementary abelian p-quotient M/M^{(p)} of M for a particular prime p (which the user can select from the menu). (This process was first implemented by Havas in [Hav 74].) Then M/M^{(p)} can be regarded as a K(G/M)-module, where K is the finite field of order p, and the normal subgroups N that we are seeking correspond precisely to the K(G/M)-submodules N/M^{(p)} of M/M^{(p)}. In fact there was already in existence an efficient collection of programs for computing the submodule lattice of a module over a prime field, based on the well-known ’Meataxe’ algorithm of Richard Parker (see [Par 84] and [LMR 92]). This had been written at Aachen, and we were kindly given permission to incorporate these programs into our system.

In addition to these basic facilities, we have provided a number of other options, which experience has suggested are useful in examples which arise in practice. For example, when G/M is not too large, we can compute the complete set of abelian invariants of M/[M, M], and thereby determine which prime numbers p are relevant. We have also provided a version of the Canberra p-quotient algorithm (often known as the NQA; see, for example, [HaN 80]) to compute the quotients of the lower p-central series of M. The basic lattice operations intersection and join on the vertices (thought of as normal subgroups of G) are also available; indeed, these operations are used to ascertain whether or not one vertex is contained in another when this is not already clear. Although we are not providing sufficient facilities to completely identify any given quotient up to isomorphism, this is possible in many cases. As an easy aid to this, it is possible to count the numbers of elements of each order in a quotient. This is particularly useful if we are trying to distinguish one group from another. The simplest example is the use of this technique to distinguish between the dihedral and quaternion groups of order 8.

4 References

[ECHLPT 92] D.B.A. Epstein, J.W. Cannon, D.F. Holt, S. Levy, M.S. Paterson, W.P. Thurston, “Word Processing and Group Theory”, Jones and Bartlett, 1992.

[EHR 91] D.B.A. Epstein, D.F. Holt and S.E. Rees, ‘The use of Knuth-Bendix methods to solve the word problem in automatic groups’, J. Symbolic Computation 12, 397-414, 1991.

[Gil 79] R.H. Gilman, ‘Presentations of groups and monoids’, J. Alg. 57, 544-554, 1979.

[HaK 84] G. Havas and L.G. Kovács, ‘Distinguishing eleven crossing knots’, in: M. Atkinson (ed.), Computational Group Theory, Academic Press, London, 367-373, 1984.

[HaN 80] G. Havas and M.F. Newman, ‘Applications of computers to questions like those of Burnside’, in: J.L. Mennicke (ed.) Burnside Groups, Lecture Notes in Mathematics 806, Springer, 211-30, 1980.

[Hav 74] G. Havas, ‘A Reidemeister-Schreier program’, in: M.F. Newman (ed.) Proceedings of the Second International Conference on the Theory of Groups, Canberra 1973, Lecture Notes in Mathematics, vol. 372, Springer, Berlin, 347-356, 1974.

[HoR 92a] D. F. Holt and Sarah Rees, ‘Testing for isomorphism between finitely presented groups’, to appear in Proceedings of Conference ‘Groups and Combinatorics’, Durham 1990.

[HoR 92b] D. F. Holt and Sarah Rees, ‘A graphics sytem for displaying finite quotients of finitely presented groups’, submitted to: Proceedings of DIMACS conference on Computational Group Theory, Rutgers, 1991.

[Kel 90] A.J. Kelly, ‘Groups from link diagrams’, Ph.D. Thesis, University of Warwick, 1990.

[LMR 92] K. Lux, J. Müller and M. Ringe, ‘Peakword condensation and submodule lattices, an application of the Meat-Axe’, to appear.

[Par 84] R. Parker, ‘The computer calculation of modular characters. (The Meat-Axe)’, in M. Atkinson (ed.), Computational Group Theory, Academic Press, London, 267-74, 1984.

Addresses:

Mathematics Institute University of Warwick Coventry CV4 7AL Great Britain e-mail: dfh@maths.warwick.ac.uk

Department of Mathematics and Statistics Merz Court The University Newcastle-upon-Tyne NE1 7RU Great Britain e-mail: sarah.rees@newcastle.ac.uk