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