×

Automorphism group computation and isomorphism testing in finite groups. (English) Zbl 1032.20016

The authors generalize the automorphism group algorithm of E. A. O’Brien [Computational algebra and number theory. Math. Appl., Dordr. 325, 83-90 (1995; Zbl 0836.20002)] and M. J. Smith [Thesis, Australian National University (1994)] to the case of nonsolvable groups: Automorphisms of the radical factor are obtained via the normalizer in a suitable permutation representation. Then automorphisms are lifted along a characteristic series, similar to the approach of J. J. Cannon, B. C. Cox and D. F. Holt [J. Symb. Comput. 31, No. 1-2, 149-161 (2001; Zbl 0984.20002)] for subgroups. By choosing a particular characteristic series the authors are able to simplify the calculation of compatible pairs. The test for automorphisms that lift is performed by a backtrack search in a suitable permutation representation. The paper closes with an investigation of the algorithm’s performance. The worst case is that of \(p\)-groups, for which an improved algorithm recently has been proposed by B. Eick, C. R. Leedham-Green and E. A. O’Brien [Commun. Algebra 30, No. 5, 2271-2295 (2002; Zbl 1006.20001)].

MSC:

20D45 Automorphisms of abstract finite groups
20B40 Computational methods (permutation groups) (MSC2010)
20-04 Software, source code, etc. for problems pertaining to group theory
68W30 Symbolic computation and algebraic computation

Software:

Cayley; Magma; GAP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bosma, W.; Cannon, J. J., Structural computation in finite permutation groups, CWI-Q., 5, 127-160 (1992) · Zbl 0770.20003
[2] Bosma, W., Cannon, J.J. (Eds.), 2002a. Groups, Databases of Groups, Database of Almost-Simple Groups, pp. 639-642 (Chapter 22). In Bosma and Cannon (2002b); Bosma, W., Cannon, J.J. (Eds.), 2002a. Groups, Databases of Groups, Database of Almost-Simple Groups, pp. 639-642 (Chapter 22). In Bosma and Cannon (2002b)
[3] Bosma, W., Cannon, J.J. (Eds.), 2002b. Handbook of Magma Functions 2.9 ed. School of Mathematics and Statistics, University of Sydney. Available from: http://magma.maths.usyd.edu.au/magma/htmlhelp/MAGMA.htm; Bosma, W., Cannon, J.J. (Eds.), 2002b. Handbook of Magma Functions 2.9 ed. School of Mathematics and Statistics, University of Sydney. Available from: http://magma.maths.usyd.edu.au/magma/htmlhelp/MAGMA.htm
[4] Bosma, W.; Cannon, J. J.; Playoust, C., The Magma algebra system I: the user language, J. Symb. Comput., 24, 235-265 (1997) · Zbl 0898.68039
[5] Butler, G., Fundamental Algorithms for Permutation Groups, (Lecture Notes in Computer Science, vol. 559 (1991), Springer-Verlag: Springer-Verlag New York) · Zbl 0785.20001
[6] Cannon, J. J., An introduction to the group theory language Cayley, (Atkinson, M. D., Computational Group Theory (1984), Academic Press: Academic Press London), 145-183 · Zbl 0544.20002
[7] Cannon, J. J.; Cox, B.; Holt, D. F., Computing the subgroup lattice of a permutation group, J. Symb. Comput., 31, 149-161 (2001) · Zbl 0984.20002
[8] Cannon, J. J.; Holt, D. F., Computing chief series, composition series and socles in large permutation groups, J. Symb. Comput., 24, 285-302 (1997) · Zbl 0890.20006
[9] Conway, J. H.; Curtis, R. T.; Norton, S. P.; Parker, R. A.; Wilson, R. A., Atlas of Finite Groups: Maximal Subgroups and Ordinary Characters for Simple Groups (1985), Clarendon Press: Clarendon Press Oxford · Zbl 0568.20001
[10] Easdown, D.; Praeger, C. E., On minimal faithful permutation representations of finite groups, Bull. Aust. Math. Soc., 38, 207-220 (1988) · Zbl 0661.20012
[11] Eick, B.; Leedham-Green, C. R.; O’Brien, E. A., Constructing automorphism groups of \(p\)-groups, Commun. Alg., 30, 5, 2271-2295 (2002) · Zbl 1006.20001
[12] Felsch, V.; Neubüser, J., Über ein Programm zur Berechnung der Automorphismengruppe einer endlichen Gruppe, Numer. Math., 11, 277-292 (1968) · Zbl 0157.05703
[13] Felsch, V.; Neubüser, J., On a programme for the determination of the automorphism group of a finite group, (Leech, J., Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967) (1970), Pergamon: Pergamon Oxford), 59-60 · Zbl 0191.02002
[14] Gross, F.; Kovács, L. G., On normal subgroups which are direct products, J. Algebra, 90, 133-168 (1984) · Zbl 0594.20018
[15] Holt, D. F., Representing quotients of permutation groups, Q. J. Math. (Oxford), 48, 347-350 (1997) · Zbl 0890.20002
[16] Holt, D. F.; Rees, S., Testing modules for irreducibility, J. Aust. Math. Soc. A, 57, 1-16 (1994) · Zbl 0833.20021
[17] Hulpke, A., 1996. Konstruktion transitiver Permutationsgruppen, Aachener Beiträge zur Mathematik, Band, vol. 18. Verlag der Augustinus Buchhandlung, Aachen. Ph.D. Thesis, RWTH Aachen; Hulpke, A., 1996. Konstruktion transitiver Permutationsgruppen, Aachener Beiträge zur Mathematik, Band, vol. 18. Verlag der Augustinus Buchhandlung, Aachen. Ph.D. Thesis, RWTH Aachen · Zbl 0955.20002
[18] Kantor, W.M., Luks, E.M., 1990. Computing in quotient groups. Proceedings of the 22nd ACM STOC. pp. 524-563; Kantor, W.M., Luks, E.M., 1990. Computing in quotient groups. Proceedings of the 22nd ACM STOC. pp. 524-563
[19] Luks, E.; Seress, Á., Computing the Fitting subgroup and solvable radical of small-base permutation groups in nearly linear time, (Finkelstein, L.; Kantor, W. M., Groups and Computation, II (New Brunswick, NJ, 1995), DIMACS Ser. Discrete Math. Theor. Comput. Sci., vol. 28 (1997), American Mathematical Society: American Mathematical Society Providence, RI), 169-181 · Zbl 0878.20004
[20] Neubüser, J., An elementary introduction to coset table methods in finitely presented group theory, (Campbell, C. M.; Robertson, E. F., Groups—St Andrews 1981 London Mathematical Society Lecture Note Series, vol. 71 (1982), Cambridge University Press: Cambridge University Press Cambdridge), 1-45
[21] O’Brien, E. A., Computing automorphisms of \(p\)-groups, (Bosma, W.; van Poorten, A. J., Computational Algebra and Number Theory, Proceedings of CANT ’92 (1995), Kluwer), 83-90 · Zbl 0836.20002
[22] Robertz, H., 1976. Eine Methode zur Berechnung der Automorphismengruppe einer endlichen Gruppe. Diplomarbeit, RWTH Aachen; Robertz, H., 1976. Eine Methode zur Berechnung der Automorphismengruppe einer endlichen Gruppe. Diplomarbeit, RWTH Aachen
[23] Rotman, J. J., An Introduction to the Theory of Groups. Graduate Texts in Mathematics, vol. 148 (1995), Springer-Verlag: Springer-Verlag New York · Zbl 0810.20001
[24] Schneider, G. J.A., Computing with modular representations, J. Symb. Comput., 9 (1990) · Zbl 0703.20009
[25] Schönert, M. et al., 1995. GAP; Schönert, M. et al., 1995. GAP
[26] Schwingel, R., 2000. Two Matrix Group Algorithms with Applications to Computing the Automorphism Group of a Finite \(p\); Schwingel, R., 2000. Two Matrix Group Algorithms with Applications to Computing the Automorphism Group of a Finite \(p\)
[27] Sims, C. C., Computing with subgroups of automorphism groups of finite groups, (Küchlin, W., Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, ISSAC ’97 (1997), ACM Press), 400-403 · Zbl 0922.20026
[28] Smith, M.J., 1995. Computing Automorphisms of Finite Soluble Groups. Ph.D. Thesis, Australian National University; Smith, M.J., 1995. Computing Automorphisms of Finite Soluble Groups. Ph.D. Thesis, Australian National University
[29] Unger, W.R., 2003. Computing the solvable radical of a permutation group (in preparation); Unger, W.R., 2003. Computing the solvable radical of a permutation group (in preparation)
[30] Wilson, R. A., Standard generators for sporadic simple groups, J. Algebra, 184, 505-515 (1996) · Zbl 0855.20034
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.