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