Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-31T20:26:28.119Z Has data issue: false hasContentIssue false

2 - Algorithms for polycyclic groups

Published online by Cambridge University Press:  21 November 2024

By
Bettina Eick
Edited by
C. M. Campbell ,
M. R. Quick ,
E. F. Robertson ,
C. M. Roney-Dougal  and
D. I. Stewart
C. M. Campbell
Affiliation:
University of St Andrews, Scotland
M. R. Quick
Affiliation:
University of St Andrews, Scotland
E. F. Robertson
Affiliation:
University of St Andrews, Scotland
C. M. Roney-Dougal
Affiliation:
University of St Andrews, Scotland
D. I. Stewart
Affiliation:
University of Manchester
Get access

Summary

This paper gives a survey about the currently used methods for computing with polycyclic groups. It discusses the different representations for polycyclic groups, gives a brief outline of many existing methods and considers two algorithms in a little more detail: the Frattini subgroup algorithm and the methods for solving the conjugacy problem. The final section of the paper exhibits some open problems.

Keywords

polycyclic groupcomputational group theorysoluble group
Type
Chapter
Information
Groups St Andrews 2022 in Newcastle , pp. 53 - 73
Publisher: Cambridge University Press
Print publication year: 2024

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Assmann, B.. Polenta - computing presentations for polycyclic matrix groups, 2003. A refereed GAP 4 package, see [56].Google Scholar
[2] Assmann, B. and Eick, B.. Computing polycyclic presentations of polycyclic matrix groups. J. Symb. Comput., 40:1269 – 1284, 2005.CrossRefGoogle Scholar
[3] Assmann, B. and Eick, B.. Testing polycyclicity of finitely generated rational matrix groups. Math. Comp., 76(259):1669–1682 (electronic), 2007.CrossRefGoogle Scholar
[4] Assmann, B. and Linton, S.. Using the Malcev correspondence for collection in polycyclic groups. J. Algebra, 316(2):828–848, 2007.CrossRefGoogle Scholar
[5] Auslander, L.. The automorphism group of a polycyclic group. Ann. of Math. (2), 89:314–322, 1969.CrossRefGoogle Scholar
[6] Baumslag, G., Cannonito, F. B., Robinson, D. J. S., and Segal, D.. The algorithmic theory of polycyclic-by-finite groups. J. Algebra, 142:118–149, 1991.CrossRefGoogle Scholar
[7] Besche, H. U. and Eick, B.. Construction of finite groups. J. Symb. Comput., 27:387–404, 1999.CrossRefGoogle Scholar
[8] Cannon, J., Eick, B., and Leedham-Green, C. R.. Special polycyclic generating sequences for finite soluble groups. J. Symb. Comput., 38:1445–1460, 2004.CrossRefGoogle Scholar
[9] Cant, A. and Eick, B.. Polynomials describing the multiplication in finitely generated torsion-free nilpotent groups. J. Symb. Comput., 92:203–210, 2019.CrossRefGoogle Scholar
[10] Dixon, J. D.. The structure of linear groups. Van Nostrand Reinhold Company, London, 1971.Google Scholar
[11] Dixon, J. D.. The orbit-stabilizer problem for linear groups. Canad. J. Math., 37(2):238–259, 1985.CrossRefGoogle Scholar
[12] Eick, B.. Spezielle PAG Systeme im Computeralgebra System GAP. Diplomarbeit, RWTH Aachen, 1993.Google Scholar
[13] Eick, B.. Algorithms for polycyclic groups. Habilitationsschrift, Universit¨at Kassel, 2001.Google Scholar
[14] Eick, B.. Computing with infinite polycyclic groups. In A. Seress and Kantor, W. M., editors, Groups and Computation III, pages 139–153. (DIMACS, 1999), 2001.CrossRefGoogle Scholar
[15] Eick, B.. On the Fitting subgroup of a polycyclic-by-finite group and its applications. J. Algebra, 242:176–187, 2001.CrossRefGoogle Scholar
[16] Eick, B.. Orbit-stabilizer problems and computing normalizers for polycyclic groups. J. Symb. Comput., 34:1–19, 2002.CrossRefGoogle Scholar
[17] Eick, B. and Engel, A.-K.. The isomorphism problem for torsion free nilpotent groups of Hirsch length at most 5. Groups Complex. Cryptol., 9(1):55–75, 2017.Google Scholar
[18] Eick, B., Leedham-Green, C. R., and O’Brien, E. A.. Constructing automorphism groups of p-groups. Comm. Algebra, 30:2271–2295, 2002.CrossRefGoogle Scholar
[19] Eick, B. and Neumann-Brosig, M.. On the Frattini subgroup of a polycyclic group. J. Algebra, 591:523–537, 2022.CrossRefGoogle Scholar
[20] Eick, B. and Nickel, W.. Polycyclic - computing with polycyclic groups, 2005. A refereed GAP 4 package, see [56].Google Scholar
[21] Eick, B. and Ostheimer, G.. On the orbit stabilizer problem for integral matrix actions of polycyclic groups. Math. Comp, 72:1511–1529, 2003.CrossRefGoogle Scholar
[22] Gaschütz, W.. Über die ϕ-Untergruppe endlicher Gruppen. Math. Z., 58:160–170, 1953.CrossRefGoogle Scholar
[23] Gebhardt, V.. Efficient collection in infinite polycyclic groups. J. Symb. Comput., 34:213–228, 2002.CrossRefGoogle Scholar
[24] Glasby, S. P. and Slattery, M. C.. Computing intersections and normalizers in soluble groups. J. Symb. Comput., 9:637–651, 1990.CrossRefGoogle Scholar
[25] Grunewald, F. and Segal, D.. Some general algorithms, I: Arithmetic groups. Ann. Math., 112:531–583, 1980.CrossRefGoogle Scholar
[26] Grunewald, F. and Segal, D.. Some general algorithms, II: Nilpotent groups. Ann. Math., 112:585–617, 1980.CrossRefGoogle Scholar
[27] Hall, P.. The Edmonton notes on nilpotent groups. Queen Mary College Mathematics Notes. Queen Mary College, Mathematics Department, London, 1969.Google Scholar
[28] Higman, G.. Enumerating p-groups. I: Inequalities. Proc. London Math. Soc., 10:24–30, 1960.Google Scholar
[29] Higman, G.. Enumerating p-groups. II: Problems whose solution is PORC. Proc. London Math. Soc., 10:566–582, 1960.CrossRefGoogle Scholar
[30] Hirsch, K. A.. On infinite soluble groups (I). Proc. London Math. Soc., 44(2):53–60, 1938.CrossRefGoogle Scholar
[31] Hirsch, K. A.. On infinite soluble groups (II). Proc. London Math. Soc., 44(5):336–344, 1938.CrossRefGoogle Scholar
[32] Hirsch, K. A.. On infinite soluble groups (III). J. London Math. Soc., 49(2):184–94, 1946.Google Scholar
[33] Hirsch, K. A.. On infinite soluble groups (IV). J. London Math. Soc., 27:81–85, 1952.CrossRefGoogle Scholar
[34] Hirsch, K. A.. On infinite soluble groups. V. J. London Math. Soc., 29:250–251, 1954.CrossRefGoogle Scholar
[35] Holt, D. F., Eick, B., and O’Brien, E. A.. Handbook of computational group theory. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2005.CrossRefGoogle Scholar
[36] Kassabov, M. and Nikolov, N.. Generation of polycyclic groups. J. Group Theory, 12(4):567–577, 2009.CrossRefGoogle Scholar
[37] Laue, R., J. Neubüser, and U. Schoenwaelder. Algorithms for finite soluble groups and the SOGOS system. In Computational Group Theory, pages 105–135, London, New York, 1984. (Durham, 1982), Academic Press.Google Scholar
[38] Leedham-Green, C. R. and Soicher, L. H.. Collection from the left and other strategies. J. Symb. Comput., 9:665–675, 1990.CrossRefGoogle Scholar
[39] Leedham-Green, C. R. and Soicher, L. H.. Symbolic collection using Deep Thought. LMS J. Comput. Math., 1:9–24, 1998.CrossRefGoogle Scholar
[40] Linnell, P. A. and Warhurst, D.. Bounding the number of generators of a polycyclic group. Arch. Math. (Basel), 37(1):7–17, 1981.CrossRefGoogle Scholar
[41] Lo, E. H.. Finding intersection and normalizer in finitely generated nilpotent groups. J. Symb. Comput., 25:45–59, 1998.CrossRefGoogle Scholar
[42] Lo, E. H.. A polycyclic quotient algorithm. J. Symb. Comput., 25:61–97, 1998.CrossRefGoogle Scholar
[43] Lucchini, A. and Menegazzo, F.. Computing a set of generators of minimal cardinality in a solvable group. J. Symb. Comput., 17:409–420, 1994.CrossRefGoogle Scholar
[44] Malcev, A. L.. On certain classes of infinite solvable groups. Amer. Math. Soc. Transl. (2), 2:1–21, 1956.CrossRefGoogle Scholar
[45] Newman, M. F. and O’Brien, E. A.. Application of computers to questions like those of Burnside, II. Internat. J. Algebra Comput., 6:593–605, 1996.CrossRefGoogle Scholar
[46] Nickel, W.. Computing nilpotent quotients of finitely presented groups. In Geometric and computational perspectives on infinite groups, Amer. Math. Soc. DIMACS Series, pages 175–191, 1996.Google Scholar
[47] Nickel, W.. NQ, 1998. A refereed GAP 4 package, see [56].Google Scholar
[48] Robinson, D. J. S.. A Course in the Theory of Groups, volume 80 of Graduate Texts in Math. Springer-Verlag, New York, Heidelberg, Berlin, 1982.Google Scholar
[49] Schwingel, R.. Two matrix group algorithms with applications to computing the automorphism group of a finite p-group. PhD Thesis, QMW, University of London, 2000.Google Scholar
[50] Segal, D.. Polycyclic Groups. Cambridge University Press, Cambridge, 1983.CrossRefGoogle Scholar
[51] Segal, D.. Decidable properties of polycyclic groups. Proc. London Math. Soc., 61:497–528, 1990.CrossRefGoogle Scholar
[52] Sims, C. C.. Enumerating p-groups. Proc. London Math. Soc., 15:151–166, 1965.CrossRefGoogle Scholar
[53] Sims, C. C.. Computing the order of a solvable permutation group. J. Symb. Comput., 9:699–705, 1990.CrossRefGoogle Scholar
[54] Sims, C. C.. Computation with finitely presented groups. Cambridge University Press, Cambridge, 1994.CrossRefGoogle Scholar
[55] Smith, M. J.. Computing automorphisms of finite soluble groups. Ph.D. Thesis, Australian National University, 1995.Google Scholar
[56] The GAP Group. GAP – Groups, Algorithms and Programming, Version 4.10. Available from http://www.gap-system.org, 2019.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×