MacTutor
Charles Sims - Computation with finitely presented groups
In 1994 Charles Sims published Computation with finitely presented groups in the series Encyclopedia of Mathematics and Its Applications published by Cambridge University Press. Joachim Neubüser wrote a review shortly after the monograph appeared and he has kindly sent a copy.
Computation with finitely presented groups (1994), by Charles Sims.
Review by: Joachim Neubüser.
The formulation of the word, conjugacy, and isomorphism problem for finitely presented (f. p.) groups by Max Dehn in 1911 is perhaps the first instance of a very explicit request for algorithms for the investigation of groups. It may look like a fatal blow to hopes for computational methods for the investigation of f. p. groups that by 1955 the algorithmic unsolvability of Dehn's problems and subsequently of many other most natural ones (e. g. if a given f. p. group is trivial, finite, abelian etc.) was proved by Novikov, Boone, and others. So, what remains for a 600 page book on computational methods for f. p. groups? A lot of different approaches indeed. It helps to sort these into two parts: On one hand there are 'trial and error' procedures, in most cases in the form of backtrack methods, for which statements of the kind 'if the group, given by a finite presentation, is indeed finite, then the method will eventually verify this fact' can be proved. The author has coined the very fitting term 'verification methods' in contrast to (decision-) algorithms for these. On the other hand there are deterministic methods for the computation of abelian, nilpotent or soluble factor groups of f. p. groups. Each of these two parts occupies roughly one half of the book, the first one chapters 2-7, the second chapters 8-11.
It is a central aim of the author to present the many, technically quite different approaches described in the book as far as possible not as a box of unrelated tools, but as instances of rather general mathematical ideas. As a main such idea he uses the theory of rewriting systems and their connection to automata. This entails intensive use of notions that are more familiar to theoretical computer scientists than to group theorists, and in fact, the author indicates his intention to tell his story in a way that will make his topic understandable to both.
A first chapter, 'Basic concepts', summarizes elementary notions for monoids and groups. It also introduces some concepts from computer science such as computability and backtrack search, and it explains the way in which procedures will be described in the book.
Chapter 2 introduces 'Rewriting systems'. This is a beautifully clear and precise description of the ideas of canonical forms, confluence tests and rewriting strategies leading to the Knuth-Bendix procedure. It provides not only a safe mathematical foundation, but also many heuristic hints that are based on the author's long experience with the design of programs in this field.
As in the previous one, also in chapter 3, 'Automata and rational languages', concepts are introduced not only with great care for precision but also illustrated by many well chosen examples. However a group theorist has to learn many new terms and notions here, which is made a bit hard by a high degree of generality and formality and by a complicated naming of special kinds of automata, through which the aim of eventually applying all this to f. p. groups can sometimes get lost. One main reason given for the introduction of automata, explained in section 3.5, is their use as index structures for rewriting systems. Moreover in chapters 4 and 5 they play a central role in explaining the so-called 'coset enumeration method'. In view of all the effort invested in automata theory, it comes as a surprise, though, that the topic of 'automatic groups' is just mentioned at the beginning of chapter 3, where a reference to B Epstein et al., Word Processing in Groups (1992), is given.
Of course, when Sims wrote this book, the impression prevailed (certainly with this reviewer) that the idea of automatic groups was limited to a special class of groups of certain geometric relevance that had been adequately covered by the book of Epstein et al. However in the meantime certain well-known f. p. groups that had resisted all other approaches have, e. g. by Derek F Holt, been proved to be infinite, using Knuth-Bendix methods to establish that they are automatic and then inspecting the automatic structure. Since this experience suggests that methods for attempting to construct and study automatic structures for groups may be a generally useful tool for "computations with f. p. groups", one may in retrospect regret the decision to omit this topic completely from Sims' book.
Chapter 4 discusses methods for handling finitely generated subgroups of free products of finitely many cyclic groups. In most of the chapter for technical reasons the latter are assumed to be infinite or of order two, while in the last section the generalisation to the above mentioned class of groups is discussed. As first observed in papers of the author himself, a key notion not only for theoretical results, but also for algorithmic approaches, is that of the 'important' cosets of a subgroup. In terms of the Schreier coset graph (which is perhaps more familiar to combinatorial group theorists than the language of automata theory) these are the cosets belonging to points in circles of the coset graph. The author proves and utilizes the fact that subgroups of the above products are finitely generated if and only if they have only finitely many important cosets.
As in the previous chapter automata theory provides the language used, and in particular the idea of (Todd-Coxeter) coset enumeration is introduced using this terminology here first for subgroups of finite index in such free products of cyclic groups. The introduction of standard, standard reduced, and complete standard coset tables leads to the methods, invented by the author, mostly already in the sixties, for the enumeration of all subgroups with at most a given number of important cosets or at most a given index.
Chapter 5, entitled 'Coset enumeration', then generalizes these ideas to their main field of application, namely arbitrary f. p. groups. It is long known that the basic idea of the Todd-Coxeter method allows many variations with respect to the 'sequence of definitions' and the 'processing of consequences'. The author discusses several such variations and compares their efficiency for a number of examples. While these discussions and experiments lead to some plausible rules of thumb, he rightly emphasizes that the very nature of the problem does not allow a universally optimal strategy. In line with this it should be remarked that further strategies have been proposed and that the search for good strategies is still going on. The chapter closes with a section on the low-index subgroup method with several suggestions for practical implementations and a comparison of the Todd-Coxeter and the Knuth-Bendix methods. While the author's presentation neatly embeds the Todd-Coxeter method into the general context of his automaton theoretic set up, it has to be said that the rather simple basic idea that the Todd-Coxeter method is trying to construct a transitive permutation representation by a backtrack method is not very easily understood coming in the guise of dealing with automata.
Moreover, without devaluing the importance of the Knuth-Bendix method and some applications of it that the author has made, and instances in which he can demonstrate its practical superiority to Todd-Coxeter procedures, it has to be said that the Todd-Coxeter method and related techniques are much more the work horses in program systems for f. p. groups and in the application of such program systems to concrete problems on f. p. groups. Therefore from the point of view of a reader who is using such implementations and wants to understand what he is using without too much effort, one may regret that the access to these rather central tools is not quite easy in this description.
Chapter 6, 'The Reidemeister-Schreier procedure', brings further important tools for the investigation of f. p. groups, namely methods for obtaining presentations of subgroups, which may then in turn be investigated by all available methods. The method of 'extended coset tables' (in the literature more often called 'modified coset tables') is introduced and demonstrated by examples. The possible use of Tietze transformation for the simplification of finite presentations so obtained is mentioned.
Chapter 7, 'Generalized automata', discusses possible shortcuts of Todd- Coxeter methods by the introduction of additional tables, which correspond to the replacement of whole paths in the coset graph by edges labelled with a word in the generators. The second part of the book follows much more traditional lines of description in group theory.
Chapter 8, 'Abelian groups', gives a very lucid explanation of the various methods for finding the structure of a f. p. abelian group. Starting from the definition of free abelian groups of finite rank, the theory of finitely generated abelian groups is developed in a constructive way linking it to methods for finding Hermite and Smith normal forms of integer matrices. For the latter both integral and modular techniques are presented, making very clear that the crucial point for practical computation is to avoid 'coefficient explosion' of intermediate matrices. It should be mentioned here that very recently (after this book had gone to print) George Havas has proposed new integral techniques for expressing the gcd of a sequence of integers as a linear combination of these with small coefficients. In practice these methods are likely to outperform previously used integral algorithms for finding Hermite and Smith normal forms with respect to coefficient control. Sections 8.6 and 8.7 give an excellent treatment of lattice reduction methods (LLL and modified LLL algorithm) and again the author gives both a very readable treatment of the basic ideas and valuable heuristics based on his own experiments.
The last three chapters, (9-11), develop systematically possibilities to determine polycyclic factor groups of f. p. groups. General theoretic results say that polycyclic-by-finite groups form the largest subclass of f. p. groups, for which basic tasks of calculating with elements and subgroups can in principle be performed algorithmically. From a practical point of view some distinctions have to be made. There is a broad spectrum of implemented methods for working with finite soluble groups once these are given by a polycyclic presentation. Also since 1974 by the work of Ian D. Macdonald and his followers there are very powerful methods for finding finite p-factor groups of f. p. groups. More recently the basic ideas of these have been generalized, in particular by the author himself, to methods for the determination of arbitrary nilpotent factor groups of f. p. groups. In comparison the task of determining non-nilpotent polycyclic factor groups of f. p. groups is still in an earlier stage of development. It is a merit of the present book to aim at a joint foundation of these various aspects.
In the first sections of chapter 9, 'Polycyclic groups', the necessary group theoretical background from commutator calculus and nilpotent, soluble and polycyclic groups is provided. In section 9.4 the basic idea of a polycyclic presentation is introduced and techniques for 'collection' with respect to a polycyclic presentation are compared. Sections 9.5-9.6 deal with methods for working with subgroups, homomorphisms and conjugacy classes in polycyclicly presented groups. Section 9.8 is of particular importance for all that follows, dealing with the notion of consistency of polycyclic presentations, which is based here on the theory of cyclic extensions. The last three sections then consider nilpotent groups. Chapter 10, 'Module bases', sets the scene for treating also non- nilpotent polycyclic factor groups of f. p. groups by methods that the author has developed by using Gröbner bases in the context of a rather theoretical proposal of Baumslag, Cannonito and Miller.
Chapter 10 presents from an algorithmic point of view the theory of integral polynomial rings and of Gröbner bases, leading eventually to finitely generated modules over the integral group ring of a polycyclic group.
Chapter 11, 'Quotient groups', then in a systematic way describes algorithms for the determination of abelian, nilpotent, metabelian, and polycyclic quotients of a f. p. group. The last section describes variations of the -quotient algorithm that allows one to construct restricted Burnside groups by enforcing laws. An appendix discusses implementation issues. The book has a carefully chosen and comprehensive list of references. Most chapters are supplemented by valuable historical notes.
What then remains to be wished? First: As already indicated above, sometimes a "side entrance" to crucial chapters which would make it easier to read these without having to go through too much earlier material. Second: A chapter that would report, even if only briefly, on some further proposals for attacking finite presentations, notably those that try to construct representations, of which only Linton's 'module enumerator' gets mentioned in the historical notes of chapter 5. Third and perhaps most importantly: A chapter in which a few of the stories from the literature are told, where a clever mixture of several of the methods described in this book lead to the understanding of the structure of some f. p. groups. To name just one, M F Newman's proof that the Fibonacci group is infinite, applying a sharpened version of the Golod-Shafarevich theorem to the analysis by the p-quotient algorithm of a subgroup that was obtained by low-index and Reidemeister-Schreier methods, really can give a feel for the practical power of the tools that this book describes so carefully.
Summing up: This is a book written with extreme care and dedication. The author hints in the preface that he has worked on it for a decade and this patience has produced a text of very high quality. Definitions are given and explained in a very clear way almost always exemplified by carefully chosen examples, and methods are described in a very easily understandable algorithmic format. As indicated in a few instances above, the author's first aim is to give the reader an understanding of mathematical ideas behind the scene. For this, in particular in certain parts of the book, he requires from his reader some dedication as well. So perhaps the book will not serve in the first place somebody who wants a fast and easy general glimpse of what is going on in this field, or who just wants a "cookbook" of what can be tried to "crack" a given presentation. However it will be of lasting value for people who want access to a most reliable treatment of the subject and seek a deeper understanding of it.
Last Updated May 2018