zbMATH — the first resource for mathematics

On the orbit-stabilizer problem for integral matrix actions of polycyclic groups. (English) Zbl 1051.20016
The foundations of the algorithmic theory of polycyclic groups were laid in two articles by G. Baumslag, F. B. Cannonito, D. J. S. Robinson and D. Segal [J. Algebra 142, No. 1, 118-149 (1991; Zbl 0774.20019)] and D. Segal [Proc. Lond. Math. Soc., III. Ser. 61, No. 3, 497-528 (1990; Zbl 0674.20020)]. The object of these works was to discover problems about polycyclic groups that could in principle be solved by an algorithm or for which it could be shown that no such algorithm exists. A very large number of standard group theoretic constructions were shown to be effective, while Segal in his paper gave examples of problems about polycyclic groups that are not effectively soluble (for example, the problem of deciding whether two elements are automorphically conjugate). At the time no attempt was made to produce algorithms which were “practical” and could actually be run on some machine: of course one can argue that it is the existence of an algorithm that is more significant, since what is practical is highly time dependent. At any rate the problem of finding implementable algorithms was left open.
Recently there has been considerable interest in constructing algorithms for polycyclic groups which can be run on machines currently available. For example, C. Sims, in his well-known book, describes implementable algorithms to find a polycyclic presentation of a polycyclic group, solve the membership problem and compute the kernel of a given homomorphism between polycyclic groups.
A well-known theorem of Auslander and Swan asserts that every polycyclic group is \(\mathbb{Z}\)-linear. E. H. Lo and G. Ostheimer [J. Symb. Comput. 28, No. 3, 339-360 (1999; Zbl 0977.20026)] constructed and implemented an algorithm to produce a faithful \(\mathbb{Z}\)-representation of a polycyclic group given by a finite presentation. Also E. H. Lo [J. Symb. Comput. 25, No. 1, 45-59 (1998; Zbl 0930.20038)] has implemented algorithms to construct normalizers of subgroups and intersections of subgroups of finitely generated nilpotent groups.
In the article under review the authors describe practical versions of two important algorithms for polycyclic groups. Let \(G\) be a polycyclic group acting faithfully on \(A=\mathbb{Z}^n\). The ‘stabilizer problem’ calls for the construction of the stabilizer \(St_G(a)\) of a given \(a\in A\). The ‘orbit problem’ is to decide of given \(a,b\in A\) whether there exists a \(g\in G\) such that \(ag=b\), i.e., if \(a,b\) belong to the same \(G\)-orbit. Evidently the stabilizer problem and the orbit problem are closely connected with the problem of constructing centralizers and the conjugacy problem, respectively, for polycyclic groups.
The method behind the algorithms is first to reduce the problem to the \(p\)-congruence subgroup \(G_p=\{g\in G\mid g\equiv 1\bmod p\}\) for a suitable odd prime \(p\). By a theorem of J. D. Dixon, \(G_p\) is torsion-free and unipotent-by-Abelian. The method then proceeds with the construction of a \(G\)-series in \(A\) with rationally irreducible factors, and an examination of the action of \(G\) on the factors (when \(G\) is represented by Abelian groups). Just as in the original theoretical papers, kernels of derivations play a role here.
Several specific examples are given for which the algorithms give the answer in a few seconds. The dimension \(n\) in these examples is at most 16.
This is obviously an area of computational group theory where much remains to be done. There are many standard constructions which it would be very useful to be able to implement, for example, to construct the Fitting subgroup. One might suspect that some constructions which are known to be effective will never be implementable – the Frattini subgroup comes to mind. On the other hand, with the ever-increasing speed of computers, it may be that some theoretical algorithms which are currently considered impracticable will be implemented in the future.

20F16 Solvable groups, supersolvable groups
20-04 Software, source code, etc. for problems pertaining to group theory
68W30 Symbolic computation and algebraic computation
20F05 Generators, relations, and presentations of groups
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20E07 Subgroup theorems; subgroup growth
20F19 Generalizations of solvable and nilpotent groups
20H20 Other matrix groups over fields
Full Text: DOI
[1] Gilbert Baumslag, Frank B. Cannonito, Derek J. Robinson, and Dan Segal, The algorithmic theory of polycyclic-by-finite groups, J. Algebra 142 (1991), no. 1, 118 – 149. · Zbl 0774.20019
[2] G. Butler, Fundamental algorithms for permutation groups, Lecture Notes in Computer Science, vol. 559, Springer-Verlag, Berlin, 1991. · Zbl 0785.20001
[3] Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. · Zbl 0786.11071
[4] M. Daberkow, C. Fieker, J. Klüners, M. Pohst, K. Roegner, M. Schörnig, and K. Wildanger, KANT V4, J. Symbolic Comput. 24 (1997), no. 3-4, 267 – 283. Computational algebra and number theory (London, 1993). · Zbl 0886.11070
[5] Karel Dekimpe, Almost-Bieberbach groups: affine and polynomial structures, Lecture Notes in Mathematics, vol. 1639, Springer-Verlag, Berlin, 1996. · Zbl 0865.20001
[6] Karel Dekimpe and Bettina Eick, Aclib, 2000, A GAP share package, see [15].
[7] John D. Dixon, The orbit-stabilizer problem for linear groups, Canad. J. Math. 37 (1985), no. 2, 238 – 259. · Zbl 0552.20019
[8] Bettina Eick, Algorithms for polycyclic groups, Habilitationsschrift, Universität Kassel, 2001. · Zbl 0991.20028
[9] Bettina Eick and Werner Nickel, Polycyclic, 2000, A GAP share package, see [15]. · Zbl 1163.20022
[10] R. Laue, J. Neubüser, and U. Schoenwaelder, Algorithms for finite soluble groups and the SOGOS system, Computational group theory (Durham, 1982) Academic Press, London, 1984, pp. 105 – 135. · Zbl 0547.20012
[11] Eddie H. Lo, A polycyclic quotient algorithm, J. Symbolic Comput. 25 (1998), no. 1, 61 – 97. · Zbl 0930.20037
[12] Gretchen Ostheimer, Practical algorithms for polycyclic matrix groups, J. Symbolic Comput. 28 (1999), no. 3, 361 – 379. · Zbl 0977.20024
[13] Michael E. Pohst, Computational algebraic number theory, DMV Seminar, vol. 21, Birkhäuser Verlag, Basel, 1993. · Zbl 0817.11063
[14] Charles C. Sims, Computation with finitely presented groups, Encyclopedia of Mathematics and its Applications, vol. 48, Cambridge University Press, Cambridge, 1994. · Zbl 0828.20001
[15] The GAP Group, GAP–Groups, Algorithms and Programming, www.gap-system.org, 2000.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.