Abstract
This note presents an elementary version of Sims's algorithm for computing strong generators of a given perm group, together with a proof of correctness and some notes about appropriate lowlevel data structures. Upper and lower bounds on the running time are also obtained. (Following a suggestion of Vaughan Pratt, we adopt the convention that perm=permutation, perhaps thereby saving millions of syllables in future research.)
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
László Babai: “On the length of subgroup chains in the symmetric group,”Communications in Algebra 14 (1986), 1729–1736.
László Babai, Eugene M. Luks, and Ákos Seress: “Fast management of permutation groups,”29th Annual Symposium on Foundations of Computer Science (IEEE Computer Society, 1988), 272–282.
J. H. Conway: “Three lectures on exceptional groups,” in M. B. Powell and G. Higman, ed.,Finite Simple Groups, Proceedings of the Oxford Instructional Conference on Finite Simple Groups, 1969 (London: Academic Press, 1971), 215–247.
Persi Diaconis, R. L. Graham, andWilliam M. Kantor: “The mathematics of perfect shuffles,”Advances in Applied Mathematics 4 (1983), 175–196.
Merrick Furst, John Hopcroft, and Eugene Luks: “Polynomial-time algorithms for permutation groups,”21st Annual Symposium on Foundations of Computer Science (IEEE Computer Society, 1980), 36–41.
Marshall Hall, Jr. andDavid Wales: “The simple group of order 604,800,”Journal of Algebra 9 (1968), 417–450.
Mark Jerrum: “A compact representation for permutation groups,”Journal of Algorithms 7 (1986), 60–78.
Charles C. Sims: “Computational methods in the study of permutation groups,” in John Leech, ed.,Computational Problems in Abstract Algebra, Proceedings of a conference held at Oxford University in 1967 (Oxford: Pergamon, 1970), 169–183.
Charles C. Sims: “Computation with permutation groups,” in S. R. Petrick, ed.,Proc. Second Symposium on Symbolic and Algebraic Manipulation, Los Angeles, California (New York: ACM, 1971), 23–28.
D. E. Taylor: “Pairs of generators for matrix groups,”The Cayley Bulletin 3 (Department of Pure Mathematics, University of Sydney, 1987).
Author information
Authors and Affiliations
Additional information
Dedicated to the memory of Marshall Hall
This research was supported in part by the National Science Foundation under grant CCR-86-10181, and by Office of Naval Research contract N00014-87-K-0502.