Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

An inductive schema for computing conjugacy classes in permutation groups


Author: Greg Butler
Journal: Math. Comp. 62 (1994), 363-383
MSC: Primary 20B40; Secondary 20-04
DOI: https://doi.org/10.1090/S0025-5718-1994-1208219-2
MathSciNet review: 1208219
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: An approach to computing the conjugacy classes of elements of large permutation groups is presented in detail, and a prototype implementation is described. The approach builds on recent efficient algorithms for computing conjugacy classes of p-groups, and for computing Sylow subgroups of large permutation groups. Classes of elements of composite order are determined by recursively analyzing quotients of centralizers of p-elements.


References [Enhancements On Off] (What's this?)

  • [1] G. Butler, Computing in permutation and matrix groups II: Backtrack algorithm, Math. Comp. 39 (1982), 671-680. MR 669659 (83k:20004b)
  • [2] -, Computing normalizers in permutation groups, J. Algorithms 4 (1983), 163-175. MR 699212 (84j:20003)
  • [3] -, Effective computation with group homomorphisms, J. Symbolic Comput. 1 (1985), 143-157. MR 818875 (87b:68057)
  • [4] -, A proof of Holt's algorithm, J. Symbolic Comput. 5 (1988), 275-283. MR 946583 (89k:20002)
  • [5] -, Computing a conditioned pc presentation of a soluble permutation group, TR 392, Basser Department of Computer Science, University of Sydney, 1990.
  • [6] G. Butler and J. J. Cannon, On Holt's algorithm, J. Symbolic Comput. 15 (1993), 229-233. MR 1218761 (94e:20001)
  • [7] -, Computing Sylow subgroups of permutation groups using homomorphic images of centralizers, J. Symbolic Comput. 12 (1991), 443-457. MR 1146510 (92m:20002)
  • [8] J. J. Cannon, An introduction to the group theory language, Cayley, Computational Group Theory (M. D. Atkinson, ed.), Academic Press, London, 1984, pp. 145-183. MR 760656
  • [9] V. Felsch and J. Neubüser, An algorithm for the computation of conjugacy classes and centralizers in p-groups, EUROSAM '79 (E. W. Ng, ed.), Lecture Notes in Comput. Sci., vol. 72, Springer-Verlag, Berlin, 1979, pp. 452-465. MR 575705 (82d:20003)
  • [10] S. P. Glasby, Constructing normalisers in finite soluble groups, J. Symbolic Comput. 5 (1988), 285-294. MR 946584 (90f:68092)
  • [11] S. P. Glasby and M. C. Slattery, Computing intersections and normalizers in soluble groups, J. Symbolic Comput. 9 (1990), 637-651. MR 1075428 (91j:20044)
  • [12] M. Hall, Jr., The theory of groups, Macmillan, New York, 1959. MR 0103215 (21:1996)
  • [13] C. M. Hoffman, Group theoretic algorithms and graph isomorphism, Lecture Notes in Comput. Sci., vol. 136, Springer-Verlag, Berlin, 1982. MR 785006 (87g:20004)
  • [14] D. F. Holt, The calculation of the Schur multiplier of a permutation group, Computational Group Theory (M. D. Atkinson, ed.), Academic Press, London, 1984, pp. 307-319. MR 760666 (85h:20004)
  • [15] -, Computing normalizers in permutation groups, J. Symbolic Comput. 12 (1991), 499-516. MR 1146513 (93b:20010)
  • [16] B. Huppert, Endliche Gruppen I, Springer-Verlag, Berlin, 1967. MR 0224703 (37:302)
  • [17] R. Laue, J. Neubüser, and U. Schoenwaelder, Algorithms for finite soluble groups and the SOGOS system, Computational Group Theory (M. D. Atkinson, ed.), Academic Press, New York, 1984, pp. 105-135. MR 760654 (86h:20023)
  • [18] J. S. Leon, On an algorithm for finding a base and strong generating set for a group given by generating permutations, Math. Comp. 35 (1980), 941-974. MR 572868 (82i:20004)
  • [19] M. Mecky and J. Neubüser, Some remarks on the computation of conjugacy classes of soluble groups, Bull. Austral. Math. Soc. 40 (1989), 281-292. MR 1012835 (91i:20001)
  • [20] C. C. Sims, Determining the conjugacy classes of a permutation group, Computers in Algebra and Number Theory (G. Birkhoff and M. Hall, Jr., eds.), SIAM-AMS Proc., vol. 4, Amer. Math. Soc., Providence, RI, 1971, pp. 191-195. MR 0338135 (49:2901)
  • [21] -, Computing the order of a solvable permutation group, J. Symbolic Comput. 9 (1990), 699-705. MR 1075432 (91m:20011)
  • [22] H. Wielandt, Finite permutation groups, Academic Press, New York, 1964. MR 0183775 (32:1252)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 20B40, 20-04

Retrieve articles in all journals with MSC: 20B40, 20-04


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1994-1208219-2
Keywords: Conjugacy class, permutation group, algorithm
Article copyright: © Copyright 1994 American Mathematical Society

American Mathematical Society