Reduction of group constructions to point stabilizers

ABSTRACT

The construction of point stabilizer subgroups is a problem which has been studied intensively. [1, 4, 5, 10, 11, 12, 14] This work describes a general reduction of certain group constructions to the point stabilizer problem. Examples are given for the centralizer, the normal closure, and a restricted group intersection problem. For the normal closure problem, this work provides an alternative to current algorithms, which are limited by the need for repeated closures under conjugation. For the centralizer and restricted group intersection problems, one can use an existing point stabilizer sequence along with a recent base change algorithm [2] to avoid generating a new point stabilizer sequence. This reduces the time complexity by at least an order of magnitude. Algorithms and theoretical time estimates for the special case of a small base are also summarized. An implementation is in progress.

REFERENCES

• 1: L. Ba.bM, E. Luks, and A. Seress, "On Managing Permutation Groups in O(r~41og~ n)", Proc. ~8th IEEE FOCS (1988), 272-282.
• 2: C. A. Brown , L. Finkelstein , P. W. Purdom, Jr., A new base change algorithm for permutation groups, SIAM Journal on Computing, v.18 n.5, p.1037-1047, Oct. 1989 [doi>10.1137/0218070]
• 3: G. Butler and J.J. C~nnon, "Computing in Permutation and Matrix Groups I: Normal Closure, Commutator Subgroups, Series" Math. Comp. 39 (1982), 663- 670.
• 4: Gene Cooperman , Larry Finkelstein, A strong generating test and short presentations for permutation groups, Journal of Symbolic Computation, v.12 n.4-5, p.475-497, Oct./Nov. 1991 [doi>10.1016/S0747-7171(08)80099-5]
• 5: G. Cooperman , L. Finkelstein , P. W. Purdom, Jr., Fast group membership using a strong generating test for permutation groups, Proceedings of the third conference on Computers and mathematics, p.27-36, May 1989, Boston, Massachusetts, United States
• 6: M. Fontet, "Calcul du CentrMisateur d'un Groupe de Permutations", Bull. Soe. Math. France. Mdmoires 49- a0, (1977), 53-63.
• 7: M. HM1, Jr., The Theory of Groups, Macmillan, New York, 1959.
• 8: C.M. Hoffm~n, Group-theoretic Algorithms and Graph Isomorphism, Lecture Notes in Computer Science, 136, Springer-Verlag, Berlin, 1982.
• 9: B. Huppert, "Endliche Gruppen I", Springer-Verlag, Berlin, 1967.
• 10: Mark Jerrum, A compact representation for permutation groups, Journal of Algorithms, v.7 n.1, p.60-78, March 1986 [doi>10.1016/0196-6774(86)90038-6]
• 11: D.E. Knuth, "Notes on Efficient Representation of Permutation Groups" (1981), unpublished manuscript.
• 12: J. Leon, "On an Algorithm for Finding a Base and Strong Generating Set for a Groap Given by a Set of Generating Permutations", Math. Comp. 35 (1980), 941-974.
• 13: 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]
• 14: 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]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Mechanical theorem proving

General Terms:
Algorithms, Theory