A finite soluble quotient algorithm (Q1897565): Difference between revisions

[This review also covers the preceding item Zbl 0844.20001.] The two papers ``Computing Finite Soluble Quotients'' (CFSQ) and ``A Finite Soluble Quotient Algorithm'' (FSQA) really tell the same story. The first is a more easily readable, early summary following a talk given in the conference ``Computational Algebra and Number Theory'' in Sydney in 1992, published in the proceedings of that conference. The second details formal proofs of statements needed for the algorithm that is described in both. It is unfortunate that, due to an overlong delay of the publication of the proceedings, CFSQ came out after FSQA and it is poor performance of the editors that SCFQ has no ``received'' date, so that the relation of the two papers is puzzling without any fault of the author. The algorithm described constructs finite soluble factor groups of a group \(G\) given by a finite presentation. Like the \(p\)-quotient algorithm of \textit{I. D. Macdonald} [J. Aust. Math. Soc. 17, 102-112 (1974; Zbl 0277.20024)], that has been developed into the present most powerful tool in particular by \textit{M. F. Newman, G. Havas} and \textit{E. A. O'Brien} [cf. e.g. Lect. Notes Math. 806, 211-230 (1980; Zbl 0432.20033)]), this ``soluble quotient'' algorithm proceeds by an induction which can only be sketched here. Following a prescribed sequence of primes \(p\) in the steps of the induction, already known epimorphic images of \(G\) are extended by certain \(p\)-elementary abelian normal subgroups (which at some steps may turn out to be trivial). For the induction step it is assumed that an epimorphism \(\theta\) of \(G\) onto a soluble group \(K\) has been determined. \(K\) is given by a polycyclic (power-conjugate) presentation in terms of a polycyclic generating set \(A\). A ``labelling'' preserves information on what was considered as the definition of the elements of \(A\) during previous steps. Similarly to the \(p\)-quotient algorithm, in the form given to it by Newman and collaborators, as an intermediate step a ``\(p\)-cover'' \(\widehat K\) of \(K\) is constructed by introducing new generators \(y_i\) that are used to turn the ``unlabelled'' relations of \(K\) into congruences modulo a \(p\)-elementary normal subgroup of \(\widehat K\) generated as normal subgroup by these \(y_i\), and subjecting the presentation so obtained to the set of consistency conditions. The main difference (and difficulty) in comparison to the \(p\)-quotient algorithm stems from the fact that the \(y_i\) can no longer be assumed to be central in \(\widehat K\). So instead of just using linear algebra over \(\mathbb{F}_p\) as in the \(p\)-quotient algorithm, the ``vector enumerator'' of \textit{S. Linton} [J. Symb. Comput. 12, No. 4/5, 427-438 (1991; Zbl 0789.20002), Linear Algebra Appl. 192, 235-248 (1993; Zbl 0827.20021)] is invoked to find an \(\mathbb{F}_p\)-basis for the \(p\)-elementary abelian normal subgroup spanned by the \(y_i\). In the last step, which in a similar way is complicated by the fact that the extensions constructed are not central, by bringing in the relations of \(G\) a factor group \(H\) of \(\widehat K\) is found which is the new epimorphic image of \(G\), in otherwise much the same way as in the \(p\)-quotient algorithm. The algorithm has been implemented in \(C\) and is generally available as a share package of the GAP system. FSQA discusses three variants of the implementation and lists performance statistics for 14 presentations to which this soluble quotient algorithm has been applied with impressive success. With this implementation there are now three different approaches available to the problem of finding polycyclic factor groups of a finitely presented group \(G\), all working by induction ``top-down''. In \textit{W. Plesken}'s approach [J. Symb. Comput. 4, 111-122 (1987; Zbl 0635.20013)] irreducible \(\mathbb{F}_p\) representations of an already found epimorphic image \(K\) are determined, essentially using Clifford theory, then extensions of \(K\) by the corresponding \(\mathbb{F}_p\)-module (the second cohomology is found by solving consistency conditions) and finally possible lifts of the epimorphism. \textit{C. Sims}' approach [ibid. 9, No. 5/6, 707-723 (1990; Zbl 0703.20029)] even allows the construction of infinite polycyclic epimorphic images of \(G\), using Groebner base techniques. His idea has recently been carried further by his PhD student Eddie Lo; the publication of details of this work is awaited.