Polynomial-time normalizers for permutation groups with restricted composition factors

ABSTRACT

For an integer constant d > 0, let Γd denote the class of finite groups all of whose nonabelian composition factors lie in Sd; in particular, Γd includes all solvable groups. Motivated by applications to graph-isomorphism testing, there has been extensive study of the complexity of computation for permutation groups in this class. In particular, set-stabilizers, group intersections, and centralizers have all been shown to be polynomial-time computable. The most notable gap in the theory has been the question of whether normalizers of subgroups can be found in polynomial time. We resolve this question in the affirmative. Among other new procedures, the algorithm requires instances of subspace-stabilizers for certain linear representations and therefore some polynomial-time computation in matrix groups.

REFERENCES

• 1: M. ASCHBACHER, On the maximal subgroups of the finite classical groups, Invent. Math. 76 (1984), 469-514.
• 2: ____, Finite group theory, 2nd ed., Cambridge Stud. Adv. Math., vol. 10, Cambridge Univ. Press, Cambridge, 2000.
• 3: L. BABAI, P. J. CAMERON, and P. P. PÁLFY, On the orders of primitive groups with restricted nonabelian composition factors, J. Algebra 79 (1982), 161-168.
• 4: L. BABAI, W. M. KANTOR, and E. M. LUKS, Computational complexity and the classification of finite simple groups, 24th Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. Press, Washington, D.C., 1983, pp. 162-171.
• 5: László Babai , Shlomo Moran, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class, Journal of Computer and System Sciences, v.36 n.2, p.254-276, April 1988 [doi>10.1016/0022-0000(88)90028-1]
• 6: J. J. CANNON and C. PLAYOUST, An introduction to algebraic programming in MAGMA, School of Mathematics and Statistics, The University of Sydney, Sydney, 1996.
• 7: M. FURST, J. HOPCROFT, and E. LUKS, Polynomial-time algorithms for permutation groups, 21st Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. Press, Washington, D.C., 1980, pp. 36-41.
• 8: THE GAP GROUP, GAP-Groups, Algorithms, and Programming, version 4.2, Lehrstuhl D für Mathematik, Rheinisch-Westfälische Technische Hochschule, Aachen; Centre for Interdisciplinary Research in Computational Algebra, University of St Andrews, St Andrews, 2000.
• 9: S. P. Glasby , Michael C. Slattery, Computing intersections and normalizers in soluble groups, Journal of Symbolic Computation, v.9 n.5-6, p.637-651, May/June 1990 [doi>10.1016/S0747-7171(08)80079-X]
• 10: D. F. HOLT, C. R. LEEDHAM-GREEN, E. A. O'BRIEN, and S. REES, Testing matrix groups for primitivity, J. Algebra 184 (1996), 795-817.
• 11: W. M. KANTOR, Sylow's theorem in polynomial time, J. Comput. System Sci. 30 (1985), 359-394.
• 12: William M. Kantor, Finding Sylow normalizers in polynomial time, Journal of Algorithms, v.11 n.4, p.523-563, Dec. 1990 [doi>10.1016/0196-6774(90)90009-4]
• 13: W. M. Kantor , E. M. Luks, Computing in quotient groups, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.524-534, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100290]
• 14: C. R. LEEDHAM-GREEN, The computational matrix group project, Groups and Computation. III (W. M. Kantor and Á. Seress, eds.), Ohio State Univ. Math. Res. Inst. Publ., vol. 8, de Gruyter, Berlin, 2001, pp. 229-247.
• 15: J. S. LEON, Partitions, refinements, and permutation group computation, Groups and Computation. II (L. Finklelstein and W. M. Kantor, eds.), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 28, Amer. Math. Soc., Providence, R.I., 1997, pp. 123-158.
• 16: E. M. LUKS, Isomorphism of graphs of bounded valence can be tested in polynomial time, J. Comput. System Sci. 25 (1982), 42-65.
• 17: E. M. Luks, Computing the composition factors of a permutation group in polynomial time, Combinatorica, v.7 n.1, p.87-99, Jan. 1987 [doi>10.1007/BF02579204]
• 18: ____, Computing in solvable matrix groups, 33rd Annual Symposium on Foundations of Computer Science, IEEE Computer Soc. Press, Los Alamitos, Calif., 1992, pp. 111-120.
• 19: ____, Permutation groups and polynomial-time computation, Groups and Computation (L. Finkelstein and W. M. Kantor, eds.), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 11, Amer. Math. Soc., Providence, R.I., 1993, pp. 139-175.
• 20: E. M. LUKS and T. MIYAZAKI, In preparation.
• 21: Eugene M. Luks , Ferenc Rákóczi , Charles R. B. Wright, Computing normalizers in permutation p-groups, Proceedings of the international symposium on Symbolic and algebraic computation, p.139-146, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190390]
• 22: Eugene M. Luks , Ferenc Rákóczi , Charles R. B. Wright, Some algorithms for nilpotent permutation groups, Journal of Symbolic Computation, v.23 n.4, p.335-354, April 1997 [doi>10.1006/jsco.1996.0092]
• 23: G. L. MILLER, Isomorphism of k-contractible graphs, a generalization of bounded valence and bounded genus, Inform. and Control 56 (1983), 1-20.
• 24: Takunari Miyazaki , Eugene M. Luks, Polynomial-time computation in matrix groups, 1999
• 25: L. PYBER, Aymptotic results for permutation groups, Groups and Computation (L. Finkelstein and W. M. Kantor, eds.), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 11, Amer. Math. Soc., Providence, R.I., 1993, pp. 197-219.
• 26: Lajos Rónyai, Computing the structure of finite algebras, Journal of Symbolic Computation, v.9 n.3, p.355-373, March 1990 [doi>10.1016/S0747-7171(08)80017-X]
• 27: U. Schöning, Graph isomorphism is in the low hierarchy, 4th Annual Symposium on Theoretical Aspects of Computer Sciences on STACS 87, p.114-124, February 1987, Passau, Germany
• 28: L. L. SCOTT, Representations in characteristic p, The Santa Cruz Conference on Finite Groups (B. Cooperstein and G. Mason, eds.), Proc. Sympos. Pure Math., vol. 37, Amer. Math. Soc., Providence, R.I., pp. 319-331.
• 29: C. C. SIMS, Computational methods in the study of permutation groups, Computational Problems in Abstract Algebra (J. Leech, ed.), Pergamon Press, Oxford, 1970, pp. 169-183.
• 30: D. A. SUPRUNENKO, Matrix groups, "Nauka", Moscow, 1972 (Russian); English transl., Transl. Math. Monographs, vol. 45, Amer. Math. Soc., Providence, R.I., 1976.
• 31: H. THEISSEN, Eine Methode zur Normalisatorberechnung in Permutationsgruppen mit Anwendungen in der Konstruktion primitiver Gruppen, Dissertation, Lehrstuhl D für Mathematik, Rheinisch-Westfälische Technische Hochschule, Aachen, 1997.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Polymorphism

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Documentation