   The Decomposition Theorem

## 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 of HG on nin, where H,G <= Sn , is equal to the cap-product
C(H,n)ÇC(G,n).
Proof: The set of bijections nin can be identified with the set Mc of classes of column equivalent 2´n-matrices containing injective n-tuples over n as rows, so that Redfield's theorem yields the statement.

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

Corollary: The cap product C(H,n)ÇC(G,n) is equal to the number of classes of elements sÎSn with respect to the following equivalence relation:
s1~s2 iff \$pÎH,rÎG: s1=ps2r-1.
In other words, this cap product is equal to the number of (H,G)-double cosets in Sn . More explicitly, in terms of intersections of conjugacy classes Ca of the symmetric group Sn with H and G, this cap product is equal to
(1)/( | H | | G | )åa|¾| n | CaÇH | | CaÇG | Õk ak!kak
=(n!)/( | H | | G | ) åa|¾| n( | CaÇH | | CaÇG | )/( | Ca | ).
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 [v choose 2], where the i-th pair of vertices is connected by an edge if and only if f(i) <= e. This together with the lemma above gives:
Corollary: The number of graphs with v vertices and e edges is equal to the cap product
C(Sv ,[v choose 2])ÇC(Se ÅS[v choose 2]\e).
More generally we obtain for the number of G-classes on nn, which consist of mappings with prescribed content the following result:
Corollary: The number of G-classes of content (b1, ...,bm) on mn is equal to the cap product
C(G,n)ÇC(Sb1Å...Å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 YX 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:

YcÈ...ÈYd:=(YcÇ...ÇYd)Yd.
It clearly has the following property:
Lemma: The cap product C(H,n)ÇC(G,n) is equal to the sum of the coefficients in the cup product 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 Lemma Let GX be a finite action, w1,...,wr its orbits, xiÎwi and c:G -> Q[Y] a class function. Then we have for the stabilizers Gi:=Gxi of these representatives that
(1)/( | G | )ågÎGc(g) | Xg | =åi=1r (1)/( | Gi | )ågÎGic(g).
Proof:
| G | åi(1)/( | Gi | )ågÎGic(g)= åi | wi | ågÎGic(g)
=åxÎXågÎGx c(g)=ågc(g) | Xg | .

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

Redfield's Decomposition Theorem Assume that we are given subgroups H1,...,Hm of Sn and an action of ´iHi on Mc. Let w1,...,wr denote the orbits, choose representatives AiÎwi, and denote by Gi their stabilizers. Then each Gi is conjugate in ´mSn to a subgroup of the diagonal D(´mSn ), and the cup product of the cycle indicator polynomials of the Hi can be decomposed with the aid of the Gi as follows:
C(H1,n)È...ÈC(Hm,n)=åi=1r(1)/( | Gi | ) å(p1,...,pm)ÎGiÕk=1nykak(p1).
Proof: Recall the action in question:
(´i Hi)´Mc -> Mc:((p1,...,pm),(aik)c) -> (piaik)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 Sn , and hence M can be identified with ´mSn . The equivalence relation ~c can therefore be expressed in group theoretical terms as follows. If AÎM is identified with (r1,...,rm), BÎM with (r1',...,rm'), then
A~c B iff \$sÎSn : (r1',...,rm')= (r1s,...,rms).
Thus the equivalence class Ac can be identified with the following left coset of the diagonal subgroup:
{(r1s,...,rms) | sÎSn }=(r1,..., rm)D(´mSn ).
Analogously we can rewrite Redfield's action of ´iHi on Mc as follows:
((p1,...,pm),(r1,..., rm)c) -> (p1r1,...,pmrm)c.
The stabilizer of Ac=(r1,...,rm)c is the subgroup
H1´...´HmÇ(r1,...,rm)D(´mSn ) (r1, ...,rm)-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=1mC(Hi,n)=(1)/(Õi | Hi | ) å(Õkak!kak)m-1 Õkykak,
where
(Õkak!kak)m-1=a1((p1,..., pm))

where the sum is taken over all the (p,...,pm)Î´iHi such that a(p1)=...=a(pm)=(a1,...,an). In order to show that this cup product can be decomposed as claimed, we apply Redfield's Lemma. We therefore introduce the class function c:´iHi -> Q[Y], defined by

c((p1,...,pm)):=Õkykak for each i Îm: a(pi)=(a1,...,an),
c((p1,...,pm)):=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: Consider H£Sn with orbits w1,..., wr on YX, representatives fiÎwi and stabilizers Gi of these representatives. Then the cycle indicator polynomial C(H,n) is equal to the following sum:
C(H,n)=åi=1r(1)/( | Gi | )åpÎGiÕk=1n ykak(p).
Examples: Let us also consider a few examples of the particular case m:=2. Redfield's Decomposition Theorem yields
C(H1,n)ÈC(H2,n)=åi=1(1)/( | Gi | ) å(p1,p2)ÎGiÕkykak(p1).
The mapping
j:Mc -> Sn :(r1,r2)c -> r1r2-1
is clearly a bijection, and it has the property
j((p1,p2)(r1,r2)c)=p1r1r2-1p2-1,
which means that the orbit of (r1,r2)c is mapped onto the (H1,H2)-double coset H1r1r2-1H2. The stabilizer of (r,1)c,rÎSn , is conjugate to the intersection (r-1H1r´H2)ÇD(Sn ´Sn ), and we have obtained:
Corollary: If {p1,...,pr} is a transversal of the (H1,H2)-double cosets of Sn , then, by Redfield's Decomposition Theorem, we have
C(H1,n)ÈC(H2,n)=åi=1rC(pi-1H1piÇH2,n).
Special cases are
C(An,n)ÈC(An,n)= | An\Sn /An | ·C(An,n),
and (exercise)
C(Sn-1,n)ÈC(Sn-1,n)= C(Sn-1,n)+C(Sn-2,n).

Redfield's Decomposition Theorem shows that a good knowledge of the conjugacy classes of subgroups of D(´mSn ) is important. We can obtain the desired information from a transversal of the left cosets of the normalizer of D(´mSn ) in ´mSn . In order to get such a transversal we derive the following theorem which describes, for an arbitrary finite G, the lattice of subgroups in between D(´m G) and ´mG. Then we shall evaluate, for particular cases, the normalizer of D(´mG) and consider applications.

Theorem: Let G be a finite group and lÎN*. The lattice of subgroups of ´lG, the normalizer of which contains D(´lG), is isomorphic to the lattice of subgroups in between D(´l+1G) and ´l+1G. A lattice isomorphism is provided by the mapping
U -> (U | G):={(u1g,...,ulg,g) | (u1,...,ul) Î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+1G) on ´(´lG), defined by
((g1,...,gl+1), (g1',...,gl')) -> (...,gigi'gl+1-1,...).
This action is clearly transitive, and the stabilizer of the identity element 1 is D(´l+1G). Consider a subgroup H, where
D(´l+1G) <= H <= ´l+1G,
and the orbit w of 1 under H, i.e. consider w:=H((1,...,1)). For any (g1',...,gl')Îw there exists an element (h1,..., hl+1)ÎH such that (g1',...,gl')=(h1hl+1-1,...,hl hl+1-1). And as H contains the diagonal subgroup D(´l+1G), we have that
(h1,...,hl,1)ÎH iff (h1,...,hl)Îw.
Using this remark it is easy to check that w is a subgroup of ´lG, the normalizer of which in ´lG contains the diagonal of ´lG, and that furthermore H=(w | G) holds. Hence the mapping U -> (U | G) is not only injective but also surjective and compatible with the lattice structure.

This theorem has the following consequence:

Corollary: The lattice of subgroups in between D(G´G) and G´G, where G is a finite group, is isomorphic to the lattice of normal subgroups of G.
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)=´mZ(G).
Theorem: The normalizer of D(´l+1G) in ´l+1G is the subgroup
(Z(´lG) | G)={(g1g,...,glg,g) | giÎZ(G),gÎG}.
Proof: It is obvious, that (Z(´lG) | G) is a subgroup of the normalizer. Consider (h1,...,hl) not ÎZ(´lG). There exist iÎl and gÎG such that highi-1 not = g. The last component of
h*:=(h1,...,hl,1)(g,...,g)(h1,...,hl,1)-1
shows that h* not ÎD(´l+1G). But each subgroup between D(´l+1G) and ´l+1G is of the form (U | G) described in the last theorem. In particular the normalizer of D(´l+1G) has this form, and therefore it is the normalizer of a subgroup of (Z(´lG) | G).

As the normalizer NG(U) of U <= G is the stabilizer of U under the conjugation operation of G on the subgroup lattice L(G), a knowledge of a transversal of the left cosets of NG(U) in G suffices to describe the conjugacy class of U. If {g1,...,gr} is such a transversal, then

[~U] ={g1Ug1-1,...,grUgr-1}.
Consider, for example, the symmetric group Sn . For n>2, the center of Sn consists of 1 only, so that the diagonal subgroup D(´l+1Sn ) is equal to its normalizer in ´l+1Sn . A transversal of the left cosets of the diagonal subgroup of ´l+1Sn is
{(p1,...,pl,1) | (p1,...,pl)Î´lSn }.
Exercises
E: Prove the formula for cup products of symmetric groups.
E: Prove that the cup product of m factors of C(Sn-1 is given by:
C(Sn-1,n)È...ÈC(Sn-1,n)=åk=1mS(m,k) C(Sn-k,n),
where S(m,k) denotes a Stirling number of the second kind.

Hint: Prove first the following result of Foulkes: For each subgroup H <= Sn

C(H,n)È...ÈC(H,n)=(1)/(n!)åa|¾| n ((n! | CaÇH | )/( | H | | Ca | ))m Õkxkak.
holds. Use the fact that xm=åk=0mS(m,k)(x)k.

harald.fripertinger@kfunigraz.ac.at,
last changed: August 28, 2001   The Decomposition Theorem