The Decomposition Theorem |

Redfield's theorem allows to express the solutions of many enumeration problems as cap products of cycle indicator polynomials. We consider a few examples.

Lemma:The number of orbits ofHon^{G}, wheren_{i}^{n}H,G <= S, is equal to the cap-product_{n}C(H,n)ÇC(G,n).

Proof: The set of bijections * n_{i}^{n}* can be identified with the set

Noticing that bijections are permutations, we can reformulate this lemma as follows:

Corollary:The cap productC(H,is equal to the number of classes of elementsn)ÇC(G,n)sÎSwith respect to the following equivalence relation:_{n}In other words, this cap product is equal to the number ofs_{1}~s_{2}iff $pÎH,rÎG: s_{1}=ps_{2}r^{-1}.(H,G)-double cosets inS. More explicitly, in terms of intersections of conjugacy classes_{n}Cof the symmetric group^{a}Swith_{n}HandG, this cap product is equal to(1)/(| H | | G |)å_{a|¾| n}| C^{a}ÇH | | C^{a}ÇG | Õ_{k}a_{k}!k^{ak}=(n!)/(| H | | G |)å_{a|¾| n}(| C^{a}ÇH | | C^{a}ÇG |)/(| C^{a}|).

An expression for the number of graphs can also be obtained from Redfield's
Counting Theorem as follows. A labelled
graph with *v* vertices and *e* edges can be considered
as an injective mapping *f* from
* [v choose 2]* to

Corollary:The number of graphs withvvertices andeedges is equal to the cap productC(S_{v},[v choose 2])ÇC(S_{e}ÅS_{[v choose 2]\e}).

More generally we obtain for the number of *G*-classes on * n^{n}*, which
consist of mappings with prescribed content the following result:

Corollary:The number ofG-classes of content(bon_{1}, ...,b_{m})is equal to the cap productm^{n}C(G,n)ÇC(S_{b1}Å...ÅS_{ bm},n).

We shall return to this later. Tools from linear representation theory will
allow a further elucidation of Redfield's methods and results. Furthermore we
can derive an algorithm for a redundancy free construction of representatives
of the *G*-classes on *Y ^{X}* from the last corollary.

Besides this useful cap operation Redfield introduced a *cup operation*
*È*, defined to be the linear extension of the following operation on
monomials:

Y^{c}È...ÈY^{d}:=(Y^{c}Ç...ÇY^{d})Y^{d}.

It clearly has the following property:

Lemma:The cap productC(H,is equal to the sum of the coefficients in the cup productn)ÇC(G,n)C(H,.n)ÈC(G,n)

This shows that it should be useful to examine cup products of cycle indicator polynomials. In fact it is possible to write each such cup product as a sum of cycle indicators of stabilizers. We shall prove this result of Redfield with the aid of the following lemma:

Redfield's LemmaLetbe a finite action,_{G}Xwits orbits,_{1},...,w_{r}xand_{i}Îw_{i}c:G ->a class function. Then we have for the stabilizersQ[Y]Gof these representatives that_{i}:=G_{xi}(1)/(| G |)å_{gÎG}c(g) | X_{g}| =å_{i=1}^{r}(1)/(| G_{i}|)å_{gÎGi}c(g).

Proof:

| G | å_{i}(1)/(| G_{i}|)å_{gÎGi}c(g)= å_{i}| w_{i}| å_{gÎGi}c(g)

=å_{xÎX}å_{gÎGx}c(g)=å_{g}c(g) | X_{g}| .

We are now in a position to prove the main theorem of Redfield's first paper:

Redfield's Decomposition TheoremAssume that we are given subgroupsHof_{1},...,H_{m}Sand an action of_{n}´on_{i}H_{i}M. Let_{c}wdenote the orbits, choose representatives_{1},...,w_{r}A, and denote by_{i}Îw_{i}Gtheir stabilizers. Then each_{i}Gis conjugate in_{i}´to a subgroup of the diagonal^{m}S_{n}D(´, and the cup product of the cycle indicator polynomials of the^{m}S_{n})Hcan be decomposed with the aid of the_{i}Gas follows:_{i}C(H_{1},n)È...ÈC(H_{m},n)=å_{i=1}^{r}(1)/(| G_{i}|)å_{(p1,...,pm)ÎGi}Õ_{k=1}^{n}y_{k}^{ak(p1)}.

Proof: Recall the action in question:

(´_{i}H_{i})´M_{c}-> M_{c}:((p_{1},...,p_{m}),(a_{ik})_{c}) -> (p_{i}a_{ik})_{c}.

Then *A* is a matrix, the rows of which are injective *n*-tuples over * n*,
i.e. they can be identified with elements of

A~_{c}B iff $sÎS_{n}: (r_{1}',...,r_{m}')= (r_{1}s,...,r_{m}s).

Thus the equivalence class *A _{c}* can be identified with the following left
coset of the diagonal subgroup:

{(r_{1}s,...,r_{m}s) | sÎS_{n}}=(r_{1},..., r_{m})D(´^{m}S_{n}).

Analogously we can rewrite Redfield's action of
*´ _{i}H_{i}* on

((p_{1},...,p_{m}),(r_{1},..., r_{m})_{c}) -> (p_{1}r_{1},...,p_{m}r_{m})_{c}.

The stabilizer of *A _{c}=(r_{1},...,r_{m})_{c}* is the subgroup

H_{1}´...´H_{m}Ç(r_{1},...,r_{m})D(´^{m}S_{n}) (r_{1}, ...,r_{m})^{-1},

and hence is conjugate to a subgroup of the diagonal, as is claimed.

In order to prove the second part of the assertion, we first of all note that by the definition of the cup operation we have that

È_{i=1}^{m}C(H_{i},n)=(1)/(Õ_{i}| H_{i}|)å(Õ_{k}a_{k}!k^{ak})^{m-1}Õ_{k}y_{k}^{ak},

where

(Õ_{k}a_{k}!k^{ak})^{m-1}=a_{1}((p_{1},..., p_{m}))

where the sum is taken over all the *(p,...,p _{m})Î´_{i}H_{i}* such
that

c((p_{1},...,p_{m})):=Õ_{k}y_{k}^{ak}for each i Îm: a(p_{i})=(a_{1},...,a_{n}),

c((p_{1},...,p_{m})):=0 otherwise.

Then the cup operation together with Redfield's Lemma yields the statement.

Putting *m:=1*, we obtain the following decomposition of the cycle indicator
polynomial according to the stabilizers of the orbits:

Corollary:ConsiderH£Swith orbits_{n}won_{1},..., w_{r}Y, representatives^{X}fand stabilizers_{i}Îw_{i}Gof these representatives. Then the cycle indicator polynomial_{i}C(H,is equal to the following sum:n)C(H,n)=å_{i=1}^{r}(1)/(| G_{i}|)å_{pÎGi}Õ_{k=1}^{n}y_{k}^{ak(p)}.

Examples:Let us also consider a few examples of the particular casem:=2. Redfield's Decomposition Theorem yieldsThe mappingC(H_{1},n)ÈC(H_{2},n)=å_{i=1}(1)/(| G_{i}|)å_{(p1,p2)ÎGi}Õ_{k}y_{k}^{ak(p1)}.is clearly a bijection, and it has the propertyj:M_{c}-> S_{n}:(r_{1},r_{2})_{c}-> r_{1}r_{2}^{-1}which means that the orbit ofj((p_{1},p_{2})(r_{1},r_{2})_{c})=p_{1}r_{1}r_{2}^{-1}p_{2}^{-1},(ris mapped onto the_{1},r_{2})_{c}(H-double coset_{1},H_{2})H. The stabilizer of_{1}r_{1}r_{2}^{-1}H_{2}(r,1), is conjugate to the intersection_{c},rÎS_{n}(r, and we have obtained:^{-1}H_{1}r´H_{2})ÇD(S_{n}´S_{n})Special cases areCorollary:If{pis a transversal of the_{1},...,p_{r}}(H-double cosets of_{1},H_{2})S, then, by Redfield's Decomposition Theorem, we have_{n}C(H_{1},n)ÈC(H_{2},n)=å_{i=1}^{r}C(p_{i}^{-1}H_{1}p_{i}ÇH_{2},n).and (exercise)C(A_{n},n)ÈC(A_{n},n)= | A_{n}\S_{n}/A_{n}| ·C(A_{n},n),C(S_{n-1},n)ÈC(S_{n-1},n)= C(S_{n-1},n)+C(S_{n-2},n).

Redfield's Decomposition Theorem shows that a good knowledge of the conjugacy
classes of subgroups of *D(´ ^{m}S_{n} )* is important. We can obtain
the desired information from a transversal of the left cosets of the
normalizer of

Theorem:LetGbe a finite group andlÎ. The lattice of subgroups ofN^{*}´, the normalizer of which contains^{l}GD(´, is isomorphic to the lattice of subgroups in between^{l}G)D(´and^{l+1}G)´. A lattice isomorphism is provided by the mapping^{l+1}GU -> (U | G):={(u_{1}g,...,u_{l}g,g) | (u_{1},...,u_{l}) ÎU,gÎG}.

Proof: It is easy to check that *U -> (U | G)* is of the desired form
and injective.
We have to show that it is surjective and that it respects the lattice
operations. In order to do this we consider the action
of *(´ ^{l+1}G)* on

((g_{1},...,g_{l+1}), (g_{1}',...,g_{l}')) -> (...,g_{i}g_{i}'g_{l+1}^{-1},...).

This action is clearly transitive, and the stabilizer of the identity element
*1* is *D(´ ^{l+1}G)*. Consider a subgroup

D(´^{l+1}G) <= H <= ´^{l+1}G,

and the orbit *w* of *1* under *H*, i.e. consider
*w:=H((1,...,1))*.
For any *(g _{1}',...,g_{l}')Îw* there exists an element

(h_{1},...,h_{l},1)ÎH iff (h_{1},...,h_{l})Îw.

Using this remark it is easy to check that *w* is a subgroup of
*´ ^{l}G*, the normalizer of which in

This theorem has the following consequence:

Corollary:The lattice of subgroups in betweenD(G´G)andG´G, whereGis a finite group, is isomorphic to the lattice of normal subgroups ofG.

Recall now the definition of *Z(G)*, the *center*
of *G*:

Z(G):={hÎG | hg=gh, for each gÎG}.

One easily checks that

Z(´^{m}G)=´^{m}Z(G).

Theorem:The normalizer ofD(´in^{l+1}G)´is the subgroup^{l+1}G(Z(´^{l}G) | G)={(g_{1}g,...,g_{l}g,g) | g_{i}ÎZ(G),gÎG}.

Proof: It is obvious, that *(Z(´ ^{l}G) | G)* is a subgroup of
the normalizer.
Consider

h^{*}:=(h_{1},...,h_{l},1)(g,...,g)(h_{1},...,h_{l},1)^{-1}

shows that *h ^{*} not ÎD(´^{l+1}G)*. But each subgroup between

As the normalizer *N _{G}(U)* of

[~U] ={g_{1}Ug_{1}^{-1},...,g_{r}Ug_{r}^{-1}}.

Consider, for example, the symmetric group *S _{n} *. For

{(p_{1},...,p_{l},1) | (p_{1},...,p_{l})Î´^{l}S_{n}}.

E:Prove the formula for cup products of symmetric groups.

E:Prove that the cup product ofmfactors ofC(Sis given by:_{n-1}whereC(S_{n-1},n)È...ÈC(S_{n-1},n)=å_{k=1}^{m}S(m,k) C(S_{n-k},n),S(m,k)denotes a Stirling number of the second kind. Hint: Prove first the following result of Foulkes: For each subgroupH <= S_{n}holds. Use the fact thatC(H,n)È...ÈC(H,n)=(1)/(n!)å_{a|¾| n}((n! | C^{a}ÇH |)/(| H | | C^{a}|))^{m}Õ_{k}x_{k}^{ak}.x^{m}=å_{k=0}^{m}S(m,k)(x)_{k}.

harald.fripertinger "at" uni-graz.at | http://www-ang.kfunigraz.ac.at/~fripert/ |

UNI-Graz | Institut für Mathematik |

UNI-Bayreuth | Lehrstuhl II für Mathematik |

The Decomposition Theorem |