> < ^ From:

^ Subject:

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

> < [top]