Structure forest and composition factors for small base groups in nearly linear time

ABSTRACT

A base of a permutation group G is a subset B of the permutation domain such that only the identity of G fixes B pointwise. The permutation representations of important classes of groups, including all finite simple groups other than the alternating groups, admit O(log n) size bases, where n is the size of the permutation domain. Groups with very small bases dominate the work on permutation groups within computational group theory. We use the “soft” version of the big-O notation introduced by [BLSI]: for two functions f(n), g(n), we write f(n)=O˜(g(n)) if for some constants c, C > 0, we have f(n) ≤ Cg(n) logcn. We address the problems of finding structure trees and composition factors for permutation groups with small (O˜(1) size) bases. For general permutation groups, a method of Atkinson will find a structure tree in O(n2) time. We give an O˜(n) algorithm for the small base case. The composition factor problem was first shown to have a polynomial time solution by Luks [Lu], and recently Babai, Luks, Seress [BLS2] gave an O˜(n3) algorithm. The [BLS2] algorithm takes &THgr;(n3) time even in the small base case. We overcome several quadratic and cubic bottlenecks in the [BLS2] algorithm to give an O˜(n) Monte Carlo algorithm for the small base case. In addition, we show that the center of a small base group can be found in time O˜(n).

REFERENCES

• AHU: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• Atk: M.D. Atkinson: An algorithm for finding the blocks of a permutation group, Math. Comp. 29 (1975), pp. 911-913.
• Ba: László Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.164-174, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103440]
• BCFS: László Babai , Gene Cooperman , Larry Finkelstein , Ákos Seress, Nearly linear time algorithms for permutation groups with a small base, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.200-209, July 15-17, 1991, Bonn, West Germany [doi>10.1145/120694.120724]
• BCFLS: László Babai , Gene Cooperman , Larry Finkelstein , Eugene Luks , Ákos Seress, Fast Monte Carlo algorithms for permutation groups, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.90-100, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103435]
• BLS1: L. Babai, E. Luks,/k. Seress" Fast management of permutation groups, Proc. 28#h IEEE FOCS (1988), pp. 272-282.
• BLS2: L. Babai, E. Luks,/k. Seress: Fast management of permutation groups II, in preparation.
• BSz: L. Babai, E. Szemer#di: On the complexity of matrix group problems I, Proc 25th IEEE FOCS (1984), pp. 229-240.
• Be: R. Beals: Structure forest for small base groups in nearly linear time, in preparation.
• BS: R. Beals,/#. Seress: Composition factors for small base groups in nearly linear time, in preparation.
• Cam: P. J. Cameron: Finite permutation groups and finite simple groups, Ball. London Math Soc. 13 (1981), pp. 1-#.
• CF: G. Cooperman, L. Finkelstein: personal communication.
• CFL: G. Cooperman , L. Finkelstein , E. Luks, Reduction of group constructions to point stabilizers, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.351-356, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74581]
• Ho: C. M. ttoffman, Group-theoretic Algorithms and Graph Isomorphism, Lecture Notes in Computer Science 136, Springer-Verlag, Berlin, 1982.
• GHLSW: Zvi Galil , Christoph M. Hoffmann , Eugene M. Luks , Claus P. Schnorr , Andreas Weber, An O(n3log n) deterministic and an O(n3) Las Vegs isomorphism test for trivalent graphs, Journal of the ACM (JACM), v.34 n.3, p.513-531, July 1987 [doi>10.1145/28869.28870]
• Kn: D. E. Knuth: Efficient representation of perm groups, Combinatorica 11 (1991), 33-44 (preliminary version circulated since 1981).
• Lu: 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]
• PS: C. E. Praeger, J. Saxl: On the orders of primitive permutation groups, Bull. London Math Soc. 12 (1980), pp. 303-307.
• Sc: L. L. Scott: Representations in characteristic p, Proc Santa Cruz Conf. on Finite Groups, AMS (1980), pp. 319-322.
• Sim: Charles C. Sims, Computation with permutation groups, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.23-28, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806264]
• Ta: R. E. Tarjan, Depth first search and linear graph algorithms, SIAM J. Comp. 1 (1972), pp. 146-160.
• Wi: H. Wielandt: Finite Permutation Groups, Acad. Press, New York 1964.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory