Dear Gap Forum,

I would like thank Dr. Derek Holt for identifying the ambiguities in
my pervious queries.

I am explaining the terms "disjoint" and "size" of the set/expression.

Mutually Disjoint Permutation cycles: Two or more premutation cycles
=======================================
will be called Mutually Disjoint if the corresponding set of points
moved by those cycles are disjoint. Thus (1,2), (3,4) and (5,6,7)
are mutually disjoint.
Where as the cycles (1,2,3), (3,4) and (5,1) are not mutually disjoint.

"Of Polynomial Size": (cf. problem definition)
It refers to the "size of the (generating) set" of the
permutations. This restriction was used to follow "group generator" kind
of behaviour, where the size of the generating set is O(n^2),
n being the size of the set of points [1,2, ... , n].

Size of the Set Theoretic Expression: It is simply the total
occurrences of each of the permutation cycles. Thus
 the expression:
   [(1,2), (1,3)] X [(4,5), (6,7)]+ [(1,2), (1,4)]
                                            has a size 6.
  (Here X is the cross product and + is the disjoint union)

Clearly, if the size of the "generating set" (from which each product
will be formed to represent any group element) is of polynomial
size, the product is also of polynomial size (assuming no repetition
of the permutation cycles in the product).

Now I am investigating the representation of a symmetric (permutation)
group as a set-theoreic expression of polynomial size, where the
representation of group elements will be by the disjoint permutation
cycles, in the form p1*p2*p3...*pr.

To sum up, I am seeking some references on "generating set" kind
of group enumeration where the cycles in the product (computed during
an enumeration) are mutually disjoint.
-- 
================= Attaching Previous Query =====================>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
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.

=================================================
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