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.