Finding blocks of imprimitivity in small-base groups in nearly linear time

ABSTRACT

The purpose of this note is to describe a new algorithm for finding blocks of imprimitivity for a permutation group G, operating on a domain &OHgr;.It runs in O(n log3|G| + ns log|G|) time, where n is the size of &OHgr; and s is the number of generators for G. In many situations it is therefore faster than Atkinson's method, which runs in O(n2s) time.A base of G is a subset B ⊆ &OHgr; such that only the identity of G fixes B pointwise. We call a family of groups small-base groups if they admit bases of size O(logc n) for some fixed constant c.If G belongs to a family of small-base groups, our algorithm runs in nearly linear time, namely in O(ns logc′ n). Beals recently gave an algorithm with the same worst case estimate. Our algorithm is simpler to implement and we expect faster practical performance.

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.
• 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]
• Be: R. Beals: Computing blocks of imprimitivity for smallbase groups in nearly linear time, DIMACS Series in Discrete Mathematics and Computer Science, 11 (1993), pp. 17-26.
• BeS: Robert Beals , Ákos Seress, Structure forest and composition factors for small base groups in nearly linear time, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.116-125, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129724]
• LS: E. Luks,/~. Seress: Nearly linear time computation of the Fitting subgroup and radical in small-base groups, in preparation.
• Schö: M. SchSnert et al: Groups, Algorithms, and Programming, Version 3, Release 2, RWTH Aachen, 1992.
• SW: A. Seress, I. Weisz: PERM' a program computing strong generating sets, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 11 (1993), pp. 269-276.
• 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:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Arrays

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations

General Terms:
Algorithms, Theory, Verification