From: Robin Chapman Newsgroups: sci.math Subject: Re: Generating the symmetric group... Date: Fri, 27 Feb 1998 03:42:24 -0600 To: dbass@utdallas.edu In article <6d4jjm$r99$1@news.utdallas.edu>, dbass@utdallas.edu () wrote: [headers deleted -- djr] > If I'm posting to the wrong newsgroup, please feel free to point me in > the appropriate direction. > > The symmetric group Sn is the group of permutations of length n, where > composition is the operator. A generating set of the symmetric group is > a set of permutations where every element of the symmetric group can be > generated as a product of the elements of the generating set. For > example, the set {{2 1 3}, {3 2 1}} is a generating set of S3, since > > {1 2 3} = {2 1 3} * {2 1 3} // * = composition > {1 3 2} = {2 1 3} * {3 2 1} * {2 1 3} > {2 1 3} = {2 1 3} > {2 3 1} = {3 2 1} * {2 1 3} > {3 1 2} = {2 1 3} * {3 2 1} > {3 2 1} = {3 2 1} > > Through brute force search, I can determine if some set of three > permutations is a generating set of Sn for n <= 10. I also have some > generalizations for restricted sets of permutations, namely prefix > reversals. What would really be nice is if there was a polynomial-time > algorithm that takes a value of n, a set of three permutations, and > returns "Yes" if the set is a generating set of Sn, and "No" otherwise. > > Another way of saying this is "Are the necessary and sufficient > conditions for a set of 3 permutations of length n to generate Sn known?" > In the 1960s Sims developed an algorithm for replacing a set of generators of a subgroup of S_n by a set of strong generators. Given a subset A of S_n, this subset generates a subgroup of S_n, namely is the set of all products of elements of A. I won't say what a set of strong generators is, except to say that if one has such a set, then one can read off the order of immediately. Your question amounts to deciding whether = n! and so Sims' algorithm suffices. One useful source is Donald Knuth's paper "Efficient representation of perm groups" available from his web site at http://www-cs-staff.Stanford.EDU/~knuth/preprints.html . This contains a full description of a modified version of Sims's algorithm together with a complexity analysis and some historical remarks. Knuth's algorithm has a worst case time bound of O(n^5 + |A|n^2) so your problem is polynomial-time soluble. A brief description od Sims's algorithm can all be found in Dixon & Mortimer's recent book on Permutation Groups, published in Springer's Graduate Texts in Mathematics series. Robin Chapman "256 256 256. Department of Mathematics O hel, ol rite; 256; whot's University of Exeter, EX4 4QE, UK 12 tyms 256? Bugird if I no. rjc@maths.exeter.ac.uk 2 dificult 2 work out." http://www.maths.ex.ac.uk/~rjc/rjc.html Iain M. Banks - Feersum Endjinn -----== Posted via Deja News, The Leader in Internet Discussion ==----- http://www.dejanews.com/ Now offering spam-free web-based newsreading ============================================================================== From: Carl Sturtivant Newsgroups: sci.math Subject: Re: Generating the symmetric group... Date: Fri, 06 Mar 1998 15:13:03 -0600 To: dbass@utdallas.edu Check the paper by Mark Jerrum in the 23rd IEEE Symposium on Foundations of Computer Science (1982) called something like "A Compact Representation of Permutation groups". The paper contains the following: a polynomial time algorithm that given some permutations (implicitly defining a subgroup of Sn) produces a special set of generators of that subgroup that can then be used to test for membership of the subgroup in polynomial time. So to see if the group generated is Sn, just use this machinery to test whether the two permutations (1 2) and (1 2 3 ... n) are in the generated group, as these generate Sn. Carl Sturtivant.