On the orbit-stabilizer problem for integral matrix actions of polycyclic groups

Eick, Bettina; Ostheimer, Gretchen

doi:10.1090/S0025-5718-03-01493-5

On the orbit-stabilizer problem for integral matrix actions of polycyclic groups
HTML articles powered by AMS MathViewer

by Bettina Eick and Gretchen Ostheimer PDF

Math. Comp. 72 (2003), 1511-1529 Request permission

Abstract:

We present an algorithm to solve the orbit-stabilizer problem for a polycyclic group $G$ acting as a subgroup of $GL(d, \mathbb Z)$ on the elements of $\mathbb Q^d$. We report on an implementation of our method and use this to observe that the algorithm is practical.

References

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. MR 1125209, DOI 10.1016/0021-8693(91)90221-S
G. Butler, Fundamental algorithms for permutation groups, Lecture Notes in Computer Science, vol. 559, Springer-Verlag, Berlin, 1991. MR 1225579, DOI 10.1007/3-540-54955-2
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
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). MR 1484479, DOI 10.1006/jsco.1996.0126
Karel Dekimpe, Almost-Bieberbach groups: affine and polynomial structures, Lecture Notes in Mathematics, vol. 1639, Springer-Verlag, Berlin, 1996. MR 1482520, DOI 10.1007/BFb0094472
Karel Dekimpe and Bettina Eick, Aclib, 2000, A GAP share package, see [The GAP Group, GAP—Groups, Algorithms and Programming, http://www.gap-system.org, 2000].
John D. Dixon, The orbit-stabilizer problem for linear groups, Canad. J. Math. 37 (1985), no. 2, 238–259. MR 780623, DOI 10.4153/CJM-1985-015-4
Bettina Eick, Algorithms for polycyclic groups, Habilitationsschrift, Universität Kassel, 2001.
Bettina Eick and Werner Nickel, Polycyclic, 2000, A GAP share package, see [The GAP Group, GAP—Groups, Algorithms and Programming, http://www.gap-system.org, 2000].
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. MR 760654
Eddie H. Lo, A polycyclic quotient algorithm, J. Symbolic Comput. 25 (1998), no. 1, 61–97. MR 1600618, DOI 10.1006/jsco.1997.0167
Gretchen Ostheimer, Practical algorithms for polycyclic matrix groups, J. Symbolic Comput. 28 (1999), no. 3, 361–379. MR 1716421, DOI 10.1006/jsco.1999.0287
Michael E. Pohst, Computational algebraic number theory, DMV Seminar, vol. 21, Birkhäuser Verlag, Basel, 1993. MR 1243639, DOI 10.1007/978-3-0348-8589-8
Charles C. Sims, Computation with finitely presented groups, Encyclopedia of Mathematics and its Applications, vol. 48, Cambridge University Press, Cambridge, 1994. MR 1267733, DOI 10.1017/CBO9780511574702
The GAP Group, GAP—Groups, Algorithms and Programming, http://www.gap-system.org, 2000.