Counting by stabilizer class

## Counting by stabilizer class

The preceding chapter was devoted to the enumeration of orbits by weight, a problem that can be solved by an easy refinement of the Cauchy-Frobenius Lemma. In the present chapter we shall introduce another variation of this lemma in order to count orbits by stabilizer class. Recall that the elements of an orbit have as their stabilizers a conjugacy class [~U] of subgroups of G. We say that [~U] is the type

of this orbit. The set of orbits of type [~U] , for a given subgroup U of G, is called the [~U] -stratum and indicated by

[~U] \\\X.

First we consider the lattice L(G) of subgroups of G. The group G is supposed to be finite and hence L(G) is a locally finite poset with respect to the inclusion order <= and we shall be able to apply in particular the Moebius Inversion. We assume that the subgroups Ui of G are numbered in such a way that

Ui <= Uk Þ i <= k.

In this case the zeta-matrix as well as the Moebius-matrix of G, defined by

z(G):=(z(Ui,Uk)), and m(G):=(m(Ui, Uk))=z(G)-1,

are upper triangular. Let us consider an easy example: G:=S3. This group has the lattice of subgroups shown in figure,

The subgroup lattice of S3

where U1=á1ñ, U2=á(12)ñ, U3=á(13)ñ, U4=á(23)ñ, U5=á(123)ñ, and U6= S3. Thus and so

m(S3)=(
 1 -1 -1 -1 -1 3 1 0 0 0 -1 1 0 0 -1 1 0 -1 1 -1 1
).

In order to calculate | [~U] \\\X | , we consider, for the finite action GX and U <= G, the sets

XU:={x | " gÎU: gx=x}.

Burnside called the order | XU | of this set the mark of U on X. We express it in terms of lengths of strata:

| XU | =åx:U <= Gx1=åV:U <= V <= Gåx:V=Gx1=åV:U <= V <= G(1)/( | [~V] | )åx:GxÎ[~V] 1
=åV:U <= V <= G( | G/V | )/( | [~V] | )åtÎT:GtÎ[~V] 1 =åV:U <= V <= G ( | G/V | )/( | [~V] | ) | [~V] \\\X | ,
=åVz(U,V) ( | G/V | )/( | [~V] | ) | [~V] \\\X | ,

where T denotes a transversal of the orbits of G on X. By Moebius Inversion this equation is equivalent to:

| [~U] \\\X | =( | [~U] | )/( | G/U | ) åVm(U,V) | XV | .

In order to simplify this expression we consider the set [~L] (G) consisting of the conjugacy classes of subgroups of G:

[~L] (G):={[~U] 1,...,[~U] d}, with representatives UiÎ[~U] i.

(Ui should not be mixed up with Ui!) Putting

bik:=( | [~U] i | )/( | G/Ui | )åVÎ[~U] km(Ui,V), and B(G):=(bik),

we can now reformulate the equation above in terms of this matrix B(G), which I call the Burnside matrix of G (in fact Burnside considered the inverse of B(G) and called it the table of marks; we shall return to this matrix later). It is in fact the following lemma (and not the lemma of Cauchy-Frobenius that is quite often named after Burnside, see the remarks on history in the chapter containing the comments and references) which is

Burnside's Lemma If GX is a finite action, then the vector of the lengths | [~U] i\\\X | of the strata of G on X satisfies the equation

We can apply this now in order to enumerate the G-classes on YX by type. Since fÎYX is fixed under each gÎUi if and only if f is constant on each orbit of Ui on X, we obtain:

Corollary: The number of symmetry classes of G on YX of type [~U] i is the i-th entry of the one column matrix

Thus, for example, the number of k-graphs on v vertices which are of type [~U] j, Uj a subgroup of Sv, is the element in the j-th row of the matrix For v:=4, an application of the Burnside matrix shown in the appendix yields the following table.

 type\k 0 1 2 3 4 [~U] _1 0 0 11 100 465 [~U] _2 0 2 21 84 230 [~U] _3 0 1 9 36 100 [~U] _4 0 0 0 0 0 [~U] _5 0 2 9 24 50 [~U] _6 0 0 0 0 0 [~U] _7 0 0 1 4 10 [~U] _8 0 2 6 12 20 [~U] _9 0 2 6 12 20 [~U] _10 0 0 0 0 0 [~U] _11 1 2 3 4 5 å 1 11 66 276 900
Multigraphs on 4 vertices, counted by type

The last column of this table shows among other things that there exist altogether 900 4-graphs on 4 vertices, and that exactly 465 of them are of type [~U] 1. Furthermore we note that the fourth, the sixth and the tenth row of this table consist of zeros only, which stimulates the question whether this also holds for bigger k. These rows belong to U4 simeq A3, U6 simeq C4 and U10 simeq A4. A shorter formulation of this question reads as follows: Do A3, C4 or A4 occur as automorphism groups of multigraphs? More generally: Which subgroups of G occur as stabilizers of mappings fÎYX? In order to answer this question we recall * which says that the stabilizer of f in the symmetric group SX is the subgroup

(SX)f=ÅyÎYSXy.

This implies

Corollary: The stabilizers of the fÎYX are the subgroups U <= G, the corresponding permutation group bar (U) of which satisfies
bar (U)=Sa Ç bar (G),
where bar (G) corresponds to G, and Sa is the direct sum of the symmetric groups on the orbits of U:
Sa:=ÅwÎU\\XSw.

We can now answer one of the questions posed above concerning automorphism groups of graphs.

Corollary: The alternating group Av does not occur as an automorphism group of a multigraph on v vertices, if v >= 3.

Proof: The assumption bar (A)v = SaÇbar (S)v yields, as Av acts transitively on [v choose 2], that Sa is the full symmetric group on [v choose 2], and hence bar (A)v = bar (S)v, which is a contradiction if v>2.

A similar result holds for the cyclic group Cv (see exercise *) and the alternating subgroup Av-1 (exercise *). Another immediate consequence of * is an expression for the number of orbits of prescribed length. Using the abbreviation, for U,V <= G:

m(U,[~V] ):=åWÎ[~V] m(U,W),

we derive from *

Corollary: If GX is a finite action, then the number of orbits of length k of G on X is equal to
(1)/(k)åi: | G/Ui | =k | [~U] i | åj m(Ui,[~U] j) | XUj | ,
and in particular the number of primitive orbits , i.e. of orbits of the (maximal) length | G | , is equal to
(1)/( | G | )åjm(1,[~U] j) | XUj | .

We consider a well known example from Galois theory.

Examples: Consider the finite field GF(q),q:=pm,p a prime number, and its extension field GF(qn) of degree n. By Galois theory its Galois group G is generated by the Frobenius isomorphism
s:GF(qn) -> GF(qn):x -> xq,
which is of order n:
G=ásñ={1,s,...,sn-1} simeq Cn.
Moreover GF(qn) possesses a normal basis, which means that there exist xÎ GF(qn) such that {x,sx,..., sn-1x} is a GF(q)-basis of GF(qn). Expressing the elements of GF(qn) in terms of this basis as GF(q)-linear combinations
åi=1nf(i)six, f(i)ÎGF(q),
we can identify them with vectors f=(f(1),...,f(n))Îqn on which the Galois group generator s acts as a cyclic shift. Hence the existence of a normal basis shows that the action of the Galois group G on GF(qn) is isomorphic to the canonical action of the cyclic group Cn on qn. Denoting by G\\ | G | X the set of orbits of (maximal) length | G | , we now evaluate the number
| G\\ | G | GF(qn) | = | Cn \\n qn |
of orbits of maximal length n of the Galois group. As the cyclic group Cn has a subgroup lattice isomorphic to the lattice of divisors d of n, the Moebius function m of L(Cn ) is the number theoretic Moebius function. Moreover the unique subgroup of order d, where d is a divisor of n, in the cyclic group Cn is generated by the power (1...n)n/d of the full cycle and, by *, this power consists of n/d disjoint cycles, each of which has the length d. Furthermore fÎqn is fixed under this subgroup á(1...n)n/dñ if and only if f is constant on the disjoint cyclic factors of (1...n)n/d. Hence, by *, we obtain
| G\\ | G | GF(qn) | = | Cn \\n qn | = (1)/(n)åd | nm(d)qn/d,
where m denotes the number theoretic Moebius function. Note that this number of primitive orbits is also equal to the number of irreducible monic polynomials with zeros in GF(qn) and coefficients in GF(q), since by Galois theory a root of a polynomial is mapped onto a root by each element of the Galois group. More generally, we can consider the orbits of maximal length of Cn on mn. The numbers
lmn:= | Cn \\n mn | =(1)/(n)åd | nm(d) mn/d
are called Dedekind numbers. Some of the smaller ones are shown in the following table:
 m\n 1 2 3 4 5 1 1 0 0 0 0 2 2 1 2 3 6 3 3 3 8 18 48 4 4 6 20 60 204 5 5 10 40 150 624
.
The fÎmn can be considered as words
f=f(1)...f(n)
of length  n over the alphabet  m. The lexicographically smallest elements in the orbits (for short: f£Cn (f)) of length n of Cn on mn form the canonic transversal
Ln(m):={fÎmn | | Cn (f) | =n,f£Cn (f)};
its elements are called the Lyndon words of length n over the alphabet m. The union of all these sets
L(m):=ÈnLn(m)
is called the Lyndon set over the alphabet m. Now we consider an arbitrary word fÎmn. As each letter iÎm forms a Lyndon word of length 1, there exists a uniquely determined longest left factor l1(f)=f(1)... of f which is a Lyndon word. The same holds for the remaining part w of f=l1(f)w, and hence there is a unique decomposition
f=l1(f)l2(f)...ll(f)(f)
of f into Lyndon words such that in the right part li(f)...ll(f)(f) the Lyndon word li(f) is the maximal left Lyndon factor. This decomposition is called the Lyndon decomposition of f, and the number l(f) of factors is called the Lyndon length of f. Even more, the Lyndon decomposition can also be described as follows (exercise *)
Lyndon's Theorem The factors li(f) of the decomposition * defined above are lexicographically nonincreasing:
l1(f)³l2(f)³...³ll(f)(f).
Conversely, each decomposition into nonincreasing Lyndon words is the decomposition * introduced above.
Using the Lyndon length we can define the following generating function:
ln(x,m):=åfÎmnxl(f),
which generates the numbers of words of length n over m with prescribed Lyndon length. V. Strehl has recently noticed and proved the remarkable fact that this function is symmetric in x and m. For example
l3(x,m)=(1)/(3!)(x3m3 +3(x3m2+x2m3-x2m2)+2(x3m+m3x)-2xm).
In order to prove this it is enough to show that, for all k,m,n in N*, the identity ln(k,m)=ln(m,k) is true. We consider a second alphabet k, say, and the corresponding set k* of all the words over k. Let F(m,k) denote the set of all the mappings f:L(m) -> k* such that all but a finite number of values f(f) are equal to the empty word epsÎk*. We map f onto [^f] :L(k) -> m*, defined as follows: Let [^f] ÎL(k) occur in the Lyndon decompositions of f(fi), say with the multiplicity m(f(fi),[^f] ). We can assume without restriction that fi³fi+1, for each i. Then put
[^f] ([^f] ):=f1·...·fi·...·fim(f(fi),[^f] )·...·fn.
Let us consider an example. Assume that f:L(3) -> 2* has the following nonempty images (we separate Lyndon factors by dots):
f(12)=2·12, f(113)=12·1·1, f(2)=2·12·1,
then [^f] has just the following nonempty images:
[^f] (1)=2·113·113, [^f] (12)=2·12·113, [^f] (2) =2·12.
It is clear that f can be reconstructed from [^f] , and Lyndon's Theorem assures that this is true also in general. Hence f -> [^f] is a bijection between F(m,k) and F(k,m). Now we introduce a norm by putting
| | f | | :=åfÎL(m) | f | | f(f) | ,
where | w | denotes the length (number of letters) of the word w. An important property of the norm is the identity
| | f | | =åfÎL(m) | f | å[^f] ÎL(k) | [^f] | ·m(f(f),[^f] )= | | [^f] | | ,
where the last equation holds since m(f(f),[^f] )=m([^f] ([^f] ),f), by construction of [^f] .
Lemma:  (Strehl) For all k,m,nÎN* we have the identity
ln(k,m)=ln(m,k).
Proof: Consider fÎmn and the corresponding subset LfÍF(m,k), consisting of the following f: f(f')=eps if and only if the Lyndon word f' is not a factor of f, while otherwise f(f')Îkm(f,f'). Easy checks show that | Lf | =kl(f) and
fÎÈfÎmnLf iff | | f | | =n,
which allows to complete the proof:
ln(k,m)=åfÎmnkl(f)= | {fÎF(m,k) | | | f | | =n } |
= | {[^f] ÎF(k,m) | | | [^f] | | =n} | = å[^f] Îknml([^f] )=ln(m,k).
Now we use a further indeterminate z in order to define the formal power series
L(x,m):=ånln(x,m)zn.
Lyndon's Theorem shows that the following is true:
L(x,m)=Õn((1)/(1-k·zn))lmn,
so that we obtain the following surprising result:
Õn((1)/(1-k·zn))lmn=Õn((1)/(1-m·zn))lkn,
which implies in particular (put k:=1 and note that l1n=1 if n=1, and l1n=0, otherwise):
The cyclotomic identity For all k,m,nÎN* and the Dedekind numbers lmn=(1)/(n)åd | nm(d) mn/d we have the identity
Õn((1)/(1-zn))lmn =(1)/(1-m·z).
Exercises
E: Prove the following identity for the elements of the Burnside matrix:
bik=m([~U] i,Uk)( | [~U] k | )/( | G/Ui | ), where m([~U] i,Uk):= åVÎ[~U] im(V,Uk).
E: Prove that the cyclic group Cv does not occur as an automorphism group of a multigraph on v vertices, if v³2.
E: Prove that the subgroup Av-1 of Av does not occur as an automorphism group of a multigraph on v vertices, if v³3.
E:   Prove *.

 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
last changed: January 19, 2005

 Counting by stabilizer class