From: barring@fiji.cs.umass.edu (David Mix Barrington)
Newsgroups: sci.math.symbolic,sci.math,comp.theory,comp.programming
Subject: Re: _Strong_Generators_  of permutation groups.
Date: Nov. 21, 1995

student TS (TangSimon@cuhk.hk) wrote:
: Hi all,

: S_n = < (12...n), (12) >  (found in abstract algebra textbooks)

: Are the two elements above Strong_Generators for S_n?

No.  They are just generators.

: What do we mean by Strong_Generators of a permutation group?

I forget the exact definition, but they are a set of generators which
allow you to factor an arbitrary permutation into generators quickly.
They are the prime way to construct a poly-time membership test for a
permutation group -- to see whether sigma is in G you try to factor sigma
as a product of the strong generators, and you know that if you fail then
sigma is not in G.

: How to determine/find Strong_Generators of permutation groups?

You start off finding, for each j such that it's possible, some element of
the group that takes point 1 to point j.  Then for each k such that it's 
possible, you find an element of the group which fixes point 1 and takes 
point 2 to point k.  Then you find elements which fix 1 and 2 and take 3
to each possible k, and so forth.  There's a fairly simple (though n^6 time)
procedure called "sifting" where you take an arbitrary set of generators
and construct a table of one permutation in each of the n^2 or so categories
I list above (for any j<k, a permutation is in category C_jk if it fixes
points 1 through j and takes j+1 to k).  You take a new permution and multiply
it by members of the table until the result is in a previously unfilled 
category.  If every generator has passed through this table without creating
any new entries, you've got a strong generator table.

: What can be computed, (in polynomial time, what is it?) if the strong 
: generators are known?  

Lots of stuff, starting with membership testing.  You can calculate the order
of the group, for example, because you know a set of sequences of strong 
generators which are in one-to-one correspondence with the group.

: Would you mind quote some examples, exercises, and references?

Sims invented this stuff in the 1970's -- see J. Leech, ed., 
_Computational Problems in Abstract Algebra_ (Pergamon, Oxford, 1970), 169-183.
and Sims, _Some Group-theoretic Algorithms_, Springer Lecture Notes in
Mathematics 697 (Springer, Berlin, 1978) 108-124.  The survey I'm 
looking at in V. Strassen' article in the _Handbook of Theoretical
Computer Science_, J. van Leeuwen, ed. (MIT Press/Elsevier, 1990).

A lot (all?) of this stuff can also be done in NC, as shown by Babai, Luks,
and Seress, 19th ACM STOC (1987), 409-420.  Unlike the above, these results
involve difficult group theory.

Dave MB