Constructing matrix representations of finitely presented groups
Most decision questions that can be asked about a finitely presented (f.p.) group, e.g. the question if it is finite or infinite, are algorithmically unsolvable. Therefore computational methods are of great interest that either compute certain factor groups of an f.p. group (e.g. its commutator factor group or its largest nilpotent group of preassigned class) or that can verify properties, e.g. finiteness, i.e. that eventually give the order of an f.p. group provided this group is finite. The Todd-Coxeter method for the enumeration of the cosets of a subgroup \(U\) of an f.p. group \(G\) (for which \(U\) is given by a finite set of generators of \(U\), qua words in the generators of \(G\)) can be used either way; if \(U\) is chosen to be the trivial subgroup it is a verification method for \(| G|\), if \(U\) is chosen nontrivial of finite index in \(G\) it provides the permutation representation of \(G\) on the cosets of \(U\) and hence a finite factor group of \(G\). In analogy the present paper provides a method for the determination of a matrix representation over a field \(F\) of an f.p. group \(G\). Such a matrix representation yields of course a representation of the group algebra \(FG\), and in fact the method described can be more generally applied to finitely presented algebras. The first chapter clarifies underlying ideas and the relation of this new method, the idea of which has been suggested by J. Conway and L. Soicher, to the Todd-Coxeter method. The second chapter gives details of the algorithm. Fortunately the author does not only give a good description of the method but has implemented it with consideration for practical efficiency. This implementation is described in Chapter 3, it is meanwhile e.g. available in the form of a share library of the GAP system. In chapter 4 some results obtained with this algorithm are given. The reviewer can add that meanwhile Linton's program has become a key part in the implementation of a new Soluble Quotient Algorithm by Alice Niemeyer, following suggestions of C. Leedham-Green. For both, theoretical insight in algorithmic possibilities and practical use, this paper and the implementation on which it reports, represent important progress in the field of Computational Group Theory.
scientific article; zbMATH DE number 60657
scientific article