SYMMETRICA-MANUAL -- Multi-dimensional cycle indices

Multi-dimensional cycle indices

Multi-dimensional cycle indices

Whenever a group G is acting on sets X₁,..., X_n then G acts in a natural way on the disjoint union

X := n
∪
i=1
X_i.

Replacing in such a situation the cycle index of G acting on X by a so-called n-dimensional cycle index we get more information about the permutation representation of G. The n-dimensional cycle index which uses for each set X_i a separate family of indeterminates x_i,1,x_i,2,... is given by

Z_n(G,X₁∪ ...∪ X_n) := 1

|G|

∑
g∈ G
n
∏
i=1
( |X_i|
∏
j=1
x_i,j^a_i,j(g)),

where (a_i,1(g),...,a_{i,|X_i|}(g)) is the cycle type of the permutation corresponding to g acting on X_i.

Let me give a short description how to handle polynomials with variables in several alphabets. In SYMMETRICA there is a routine which allows to multiply two polynomials in disjoint sets of indeterminates. The corresponding routine is called

INT mult_disjunkt_polynom_polynom(a,b,c) OP a,b,c;

where a and b are the two polynomials that should be multiplied. c is the result. A POLYNOM object in SYMMETRICA consists of three parts:

A coefficient,
the so called self-part, which is a VECTOR of INTEGER objects that represent the exponents of the monomial summands,
and a next-part, which is the lexicographically next monomial, or zero, if there is no further monomial summand of the polynomial in question.

The routine for multiplication of two polynomials in disjoint sets of indeterminates works in the following way: At first the number of variables of the first polynomial a is evaluated. (Let this number be n.) Then for each monomial summand of a it is tested, if its self-part is of length less than n, and if this is so, then this self-part is changed into a VECTOR object of length n and all the new entries are set to zero. Then the self part of each monomial summand of b is appended to the self-part of a (of length n), forming a new self-part of a monomial summand of c. The corresponding coefficients of the monomials of a and b are multiplied to get the new coefficient of this monomial.

In order to work with these polynomials in two or more alphabets it is therefore important to know how many variables are in the first alphabet, in the second alphabet and so on. Or in other words, we must keep in mind at which index of the self-part of the monomial summands the different alphabets start. (The index where the i-th family starts, is the number of variables which have already occurred in the previous i-1 families.) Using a vector of INTEGER objects, where for each polynomial the position in the self-parts of the monomial summands is indicated, where the new alphabet starts, gives the whole information. For example consider two polynomials a and b in two different alphabets (a is a polynomial in x_i and b is a polynomial in y_i) where a has n variables. Then applying

INT mult_disjunkt_polynom_polynom(a,b,c)

makes c to be a polynomial in two families of variables and the corresponding vector of starting points would be [0,n]. A monomial summand of c can be interpreted as

s_po_k(c) n-1
∏
i=0
x_i+1^s_po_ii(c,i) s_po_li(c)-1
∏
i=n
y_i-n+1^s_po_ii(c,i).

For that reason a multi dimensional cycle index in SYMMETRICA consists of a VECTOR-part and a POLYNOMial-part, which can be selected by

OP s_mz_v(a) OP a!;      OP s_mz_po(a) OP a;

s_mz_v stands for select_multi-zykelind_vector, which selects the vector part of the multi-dimensional cycle index a. The routine s_mz_po stands for select_multi-zykelind_polynom, which selects the polynomial part of the multi-dimensional cycle index a.

Furthermore there is

OP s_mz_vi(a,i) OP a; INT i;

which selects the i-th entry (0≤ i) of the vector part of the multi-dimensional cycle index a.

With

INT s_mz_vii(a,i) OP a; INT i;

you can select the i-th entry of the vector part of the multi-dimensional cycle index a as an integer.

From a VECTOR part and a POLYNOM part of a multi-dimensional cycle index you can form the corresponding cycle index with

INT m_v_po_mz(v,po,zyk) OP v,po,zyk;

It makes a multi-dimensional cycle index zyk from the POLYNOMial po with the different alphabets starting at the position given in the VECTOR v. v, po and zyk must be different.

From a multi-dimensional cycle index one can extract some of the families of indeterminates by

INT mz_extrahieren(a,b,c)   OP a,b,c;

where a is a multi dimensional cycle index and b is a VECTOR object. Its length tells how many families shall be combined into the new cycle index c. The entries of b are INTEGER objects. If for instance a is a 6-dimensional cycle index and you want to extract the first and fifth family of indeterminates then b would be the VECTOR [1,5] of length 2. In the case you choose only one family to be extracted the result will be a POLYNOM object, otherwise it is a multi dimensional cycle index as described above.

For identifying different alphabets there is the routine

INT mz_vereinfachen(a,b) OP a,b;

which computes from a multi dimensional cycle index a a cycle index b in only one alphabet.

harald.fripertinger "at" uni-graz.at, May 26, 2011

Multi-dimensional cycle indices