> < ^ Date: Wed, 15 Jul 1998 20:31:29 -0700
> < ^ From: Javaid Aslam <jaslamx@yahoo.com >
< ^ Subject: Re: Permutation group enumeration by disjoint permutations

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]