On the orbit-stabilizer problem for integral matrix actions of polycyclic groups
Authors:
Bettina Eick and Gretchen Ostheimer
Journal:
Math. Comp. 72 (2003), 1511-1529
MSC (2000):
Primary 20F16, 20-04; Secondary 68W30
DOI:
https://doi.org/10.1090/S0025-5718-03-01493-5
Published electronically:
February 3, 2003
MathSciNet review:
1972750
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
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.
- 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 https://doi.org/10.1016/0021-8693%2891%2990221-S
- G. Butler, Fundamental algorithms for permutation groups, Lecture Notes in Computer Science, vol. 559, Springer-Verlag, Berlin, 1991. MR 1225579
- Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206
- 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 https://doi.org/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
- 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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1006/jsco.1999.0287
- Michael E. Pohst, Computational algebraic number theory, DMV Seminar, vol. 21, Birkhäuser Verlag, Basel, 1993. MR 1243639
- Charles C. Sims, Computation with finitely presented groups, Encyclopedia of Mathematics and its Applications, vol. 48, Cambridge University Press, Cambridge, 1994. MR 1267733
- The GAP Group, GAP—Groups, Algorithms and Programming, http://www.gap-system.org, 2000.
Retrieve articles in Mathematics of Computation with MSC (2000): 20F16, 20-04, 68W30
Retrieve articles in all journals with MSC (2000): 20F16, 20-04, 68W30
Additional Information
Bettina Eick
Affiliation:
Institut für Geometrie, Universität Braunschweig, 38106 Braunschweig, Germany
MR Author ID:
614875
Email:
beick@tu-bs.de
Gretchen Ostheimer
Affiliation:
Department of Computer Science, 103 Hofstra University, Hempstead, New York 11549
Email:
cscgzo@husun3.Hofstra.edu
Received by editor(s):
July 9, 2001
Published electronically:
February 3, 2003
Additional Notes:
The authors thank Werner Nickel for useful discussions.
Article copyright:
© Copyright 2003
American Mathematical Society
