> < ^ From:

< ^ Subject:

Dear Gap Forum,

Thank you for your references.

It seems I failed to state the problem clearly; the main problem

is :

HOW TO REPRESENT EACH GROUP ELEMENT pi AS PRODUCT OF mutually

DISJOINT PERMUTATIONS TAKEN FROM A PRE-DEFINED SET OF

permutations of POLYNOMIAL SIZE.

Here I need *not* enumerate all or some of the elements, but I may need

any arbitrary pi in G. Also, no conversion from non-disjoint to

disjoint permutation product should be necessary.

Let me refresh the whole scenario/background:

The most common technique, I assume, for representing a permutation

group

is by a set of strong generators which produce a "representaion matrix",

where ecah row contains a right/left traversal of a subgroup

in a sub-group tower

(also called stablizer chain). In such a situation the complete group G

can be represented by a set theoretic expresiion of the form:

G = R1 X R2 X ... Rn, where Ri is a set containing right(left) traversal in a sub-group tower: G= G0 > G1 > G2 > ... > Gn = I, Gi being a subgroup of G(i-1), and the n-tuple (r1, r2, r3 ... rn) from R1 X R2 X ... Rn would imply the product r1*r2*r3 ... rn, where ri is in Ri.

In this case any element pi in G can be represented as

pi = r1*r2*r3 ... *rn.

The **problem** here is that permutations, r1 ... rn, are not

necessarily disjoint.

Now the question is whether any set-theoretic expression of polynomial

size can be found (in polynomial time) such that all permutations ri

are mutually disjoint.

One possible form of this set-theo expression could be:

SUM( Ri1 X Ri2 X ... Rin), i = 1.. n^k, for some constant k.

David Joyner wrote: > > Dear Gap Forum: > > > Mr. Aslam wrote: > > > > ------------------------- > > Dear Gap Forum, > > > > I am looking for an algorithm(s) that would enumerate > > a permutation group (from a set of genrators) such > > that each element of the > > group is represented as a product of the disjoint permutations > > (which would be from the set of the generators). > > > > That is if each element pi of the group G is represented as > > pi = g1*g2* ... gr , > > (where r is clearly a polynomial in the degree of the group), > > > > then g1,g2, .. gr are mutually disjoint. > > > > Here the size of set of generators could be a polynomial in r. > > Clearly, it is not important whether the generators are strong are not. > > > > Hope to receive some references in this direction. > > See > Gray Codes for Reflection Groups, J. H. Conway, N. J. A. Sloane and A. R. Wilks, > > Graphs and Combinatorics, > 5 (1989), pp. 315-325. > available at > http://www.research.att.com/~njas/doc/gp.html > > > > > > > Thanking you all. > > ------------------------------ > > > > -- > David Joyner, Assoc Prof of Math > US Naval Academy, Annapolis, MD 21402 > (410)293-6738 > wdj@nadn.navy.mil > http://web.usna.navy.mil/~wdj/homepage.html > ++++++++++++++++++++++++++++++++++++++++++++ > "A Mathematician is a machine for turning > coffee into theorems." Alfred Renyi -- ================================================= Javaid Aslam jaslamx@ichips.intel.com Architecture Validation Tools, Intel Corp. MS AL4-51 Location : AL4 2nd. Floor (near N5). Office Phone : 503-591-4735 Fax: 503-591-4862

> < [top]