Unspecified Journal Volume 00, Number 0, Pages 000–000 S ????-????(XX)0000-0

COUNTING SPECIAL MONOMIALS

CHRIS MONICO AND MARA D. NEUSEL

Abstract. Let ρ : G ↪ GL(n, 𝔽) be a permutation representation of a finite group G. In this paper we study the number of orbits of special monomials of G acting on the polynomials in n variables via ρ. We give formulae for several crucial families of groups, for direct sums of representations, as well as for vector invariants. In addition we give two algorithms for arbitrary permutation groups, one relying on the geometry of G acting on V = 𝔽^{n}, the other relying on the representation theory of the symmetric groups.

1. Introduction

Let ρ : G ⟶ GL(n, 𝔽) be a faithful permutation representation of a finite group G over a field 𝔽. The representation ρ induces a natural action of G on the vector space V = 𝔽^{n} of dimension n, thus on the dual space V^{∗}, and hence on the ring of polynomial functions 𝔽[V]. Our interest is focused on the subring of invariants

𝔽[V]^{G} = {f ∈ 𝔽[V]|gf = f ∀g ∈ G},

which is a finitely generated 𝔽-algebra by a classic result due to E. Noether, see Theorem 2.1.4 in [4].

Let x_{1}, …, x_{n} be the basis of V^{∗} being permuted by the G-action. Let x^{I} = x_{1}^{i_{1}} ⋯ x_{n}^{i_{n}} ∈ 𝔽[V] be a monomial. We order the exponent sequence I in nonincreasing order and summarize this in its associated ordered partition λ(I) = (λ_{1}(I) ≥ … ≥ λ_{n}(I)). Then x^{I} is called special if

(1) λ_{n}(I) = 0 and

(2) λ_{i}(I) − λ_{i+1}(I) ≤ 1, for i = 1, …, n − 1.

It is known that the ring of invariants 𝔽[V]^{G} of a permutation representation is generated by the orbit sums of special monomials and the top elementary symmetric function s_{n} = x_{1} ⋯ x_{n}, see Theorem 3.4.2 in [4]. The maximal degree of an algebra generator of 𝔽[V]^{G} in a minimal generating set is called the Noether number. It is denoted by β(𝔽[V]^{G}). By the above mentioned theorem we find that

β(𝔽[V]^{G}) ≤ max \{\binom{n}{2}, n\}

\begin{matrix}c \\ ◯ \end{matrix}0000 (copyright holder)

Received by the editors July 27, 2008.

2000 Mathematics Subject Classification. Primary 13A50, Secondary 05Axx.

Key words and phrases. Invariant Theory of Finite Permutation Groups, Special Monomials, Embedding Degree, Permutations, Stirling Numbers, Representation Theory of the Symmetric Groups.

The second author wants to thank Egon Schulte and Vic Reiner for interesting discussions.

for any permutation group G, see Corollary 3.4.3 in [4]. This degree bound is sharp as the defining representation of the alternating group A_{n} shows, see Example 1 in Section 3.4 in [4].

Degree bounds are an ongoing theme in the Invariant Theory of Finite Groups with many results for large families of group and representations, see [3] for a survey in these matters. In contrast, not much is known about the number of algebra generators of a ring of polynomial invariants, i.e., the embedding degree of the algebra 𝔽[V]^{G} denoted by emb − deg(𝔽[V]^{G}).

In this paper we want to study the embedding degree of 𝔽[V]^{G} for permutation representations by counting the number N_{G,V} of G-orbits of special monomials. This gives then an upper bound on the embedding degree. We note that the trivial monomial 1 = x_{1}^{0} ⋯ x_{n}^{0} is a special monomial.

Proposition 1.1. Let ρ : G ↪ GL(n, 𝔽) be a faithful permutation representation of a finite group G. Let H ≤ G be an arbitrary subgroup. Then the embedding degree is bounded above by the number of orbits of special monomials under the action of H:

emb − deg(𝔽[V]^{G}) ≤ N_{G,V} ≤ N_{H,V} ≤ N_{{e},V} .

Proof. Obvious. □

Even though it is not expected that N_{G,V} ever gives a sharp upper bound on the embedding degree, the number of special G-orbits has the advantage of being independent of the ground field. (This follows because the Poincaré series of 𝔽[V]^{G} is independent of the choice of the ground field 𝔽 whenever G acts by permutations, see Proposition 3.2.2 in [4].) In contrast, the embedding degree depends on the choice of 𝔽 as the 3-fold regular representation of ℤ/2 shows: The embedding degree of the associated ring of invariants is 9, unless the characteristic of 𝔽 is even. In that case the embedding degree is 10. Furthermore, the study of N_{G,V} is interesting in its own right as this number has intriguing combinatorial properties as we will see in the following.

2. Special Monomials in 𝔽[V]

We start by looking at the trivial group, i.e., we count the number N_{{e},V} of special monomials in the ambient polynomial ring 𝔽[V] itself thus obtaining a universal upper bound for N_{G,V} for an n-dimensional permutation representation of any group G.

For this denote by P (n, k) the number of distinct maps from a set with n elements onto a set with k elements. We note that

P (n, k) = kP (n − 1, k) + kP (n − 1, k − 1) = k!S(n, k) = ∑_{j=1}^{k}(−1)^{k−j}\binom{k}{j}j^{n},

where S(n, k) is the Stirling number of second kind.

Proposition 2.1. The number of special monomials in 𝔽[V] is given by

N_{{e},V} = ∑_{k=1}^{n} k!S(n, k) = ∑_{k=1}^{n} P (n, k).

Proof. Let S = {x_{1}, …, x_{n}} and let T = {0, …, k − 1}. Then P (n, k) counts the number of special monomials x^{I} with k different exponents. □

We will denote S(n) = ∑_{k=1}^{n} k!S(n, k). Note that S(n) counts the total number

of ordered partitions of a set with n elements which coincides with the number of surjective maps with a domain with n elements. One may compute S(n) recursively by

S(1) = 1
S(n) = 1 + ∑_{i=1}^{n−1} \binom{n}{i}S(n − i),

see Page 146 [6]. The first few values of S(n) beginning at n = 1 are

1, 3, 13, 75, 541, 4683, 545835, 7087261, ….

This is sequence A000670 in [5].

Remark 2.2. In Lemma 2 of [1] we find a different formula for the number of special monomials in 𝔽[V], namely

N_{\{e\},V} = \frac{d^{n}}{dx^{n}} \frac{1}{2 − e^{x}} |_{x=0} .

Recall (from, e.g., Page 34 of [6]) that a generating function for the Stirling numbers of second kind is given by

∑_{n≥k} S(n, k)\frac{x^{n}}{n!} = \frac{1}{k!}(e^{x} − 1)^{k}

for k ∈ ℕ_{0}. Thus

k!S(n, k) = \frac{d^{n}}{dx^{n}} (e^{x} − 1)^{k}|_{x=0} .

Hence we recover the generating function for S(n), see Page 146 [6],

S(n) = ∑_{k=1}^{n} k!S(n, k) = ∑_{k=1}^{n} \frac{d^{n}}{dx^{n}} (e^{x} − 1)^{k}|_{x=0} = \frac{d^{n}}{dx^{n}} \frac{1}{2 − e^{x}} |_{x=0} .

Remark 2.3. We note that by Proposition 1.1 we obtain a universal bound on the embedding degree valid for any permutation group:

emb − deg(𝔽[V]^{G}) ≤ N_{G,V} ≤ N_{{e},V} = ∑_{k=1}^{n} P (n, k) = S(n).

However, this bound is never sharp: Assume it were for some group G ≤ Σ_{n}. Then every special monomial would be an invariant. Thus the basis elements x_{1}, …, x_{n} are invariant. Therefore G = {e} is the trivial group. Its ring of invariants is 𝔽[V] which is generated by the n forms x_{1}, …, x_{n} and thus has embedding dimension n.

3. Special Orbits in 𝔽[V]^{G}

In this section we will derive a formula for the number of special G-orbits for an arbitrary permutation group G that makes use of the geometry of the G-action on the dual space V^{∗}. We illustrate the result with the calculation of the number of special Σ_{n}-orbits.

Let ρ : G ↪ GL(n, 𝔽) be a faithful permutation representation of a finite group G. Then ρ(G) ≤ Σ_{n} where we identified the symmetric group with its image in the general linear group under the defining representation.

Proposition 3.1. Denote by λ_{G,V} (k) the number of elements g ∈ G such that the dimension of the fixed field V^{g} is exactly k:

λ_{G,V} (k) = |{g ∈ G| dim_{𝔽} V^{g} = k}|.

Then

N_{G,V} = \frac{1}{|G|} ∑_{k=1}^{n} λ_{G,V} (k)S(k).

Proof. For any two integers a, b, a ≤ b, we set [a, b] = {a, a + 1, a + 2, …, b} ⊆ ℤ. For 1 ≤ k ≤ n we let

P_{n,k} = {ψ : [1, n] ⟶ [0, k − 1]|ψ is surjective}

be the set of surjective maps from [1, n] to [0, k − 1]. Thus |P_{n,k}| = P (n, k). Set P_{n} = ∪_{k=1}^{n}P_{n,k}. Our group G acts on V^{∗} by permuting the variables x_{1}, …, x_{n}

g(x_{1}^{i_{1}} ⋯ x_{n}^{i_{n}}) = x_{g(1)}^{i_{1}} ⋯ x_{g(n)}^{i_{n}} = x_{1}^{i_{g^{−1}(1)}} ⋯ x_{n}^{i_{g^{−1}(n)}}.

Thus we might as well consider G as a group permuting the set [1, n]. We define a G-action on the set P_{n} by

G × P_{n} ⟶ P_{n}, (g, ψ) ↦ ψ ∘ g^{−1}.

Furthermore, the set P_{n} is in one-to-one correspondence with the set of special monomials in 𝔽[x_{1}, …, x_{n}] by

P_{n} ⟶ {m = x_{1}^{i_{1}} ⋯ x_{n}^{i_{n}} ∈ 𝔽[V]|m special}, ψ ↦ x_{1}^{ψ(1)}x_{2}^{ψ(2)} ⋯ x_{n}^{ψ(n)}.

By construction this correspondence is G-equivariant, i.e., the diagram

ψ  ⟶  x_{1}^{ψ(1)}x_{2}^{ψ(2)} ⋯ x_{n}^{ψ(n)}
↓  ↓
ψ ∘ g^{−1} ⟶ x_{1}^{ψ(g^{−1}(1))}x_{2}^{ψ(g^{−1}(2))} ⋯ x_{n}^{ψ(g^{−1}(n))}

commutes. Thus the number of special G-orbits N_{G,V} is equal to the number of orbits in P_{n} under the G-action. For g ∈ G let Fix(g) denote the number of fixed points of g acting on P_{n}

Fix(g) = |{ψ ∈ P_{n}|ψ ∘ g^{−1} = ψ}|.

Then by Burnside’s Lemma

N_{G,V} = \frac{1}{|G|} ∑_{g∈G} Fix(g).

For a fixed g ∈ G, notice that ψ ∘ g^{−1} = ψ if and only if

(⋆)  ψ(g^{−1}m) = ψ(m)

for all m ∈ [1, n]. The number of independent equations in the System (⋆) is precisely the number of cycles in the disjoint cycle representation of g (considered as a permutation of [1, n] and counting 1-cycles). So if c(g) is the number of such cycles, it follows that

Fix(g) = ∑_{j=1}^{c(g)} P (c(g), j) = ∑_{j=1}^{c(g)} j!S(c(g), j) = S(c(g)).

Set λ_{G,V} (k) = |{g ∈ G|c(g) = k}| to be the number of elements g ∈ G which have exactly k disjoint cycles. Then

N_{G,V} = \frac{1}{|G|} ∑_{g∈G} Fix(g) = \frac{1}{|G|} ∑_{k=1}^{n} λ_{G,V} (k)S(k).

Note that λ_{G,V} (k) counts the number of elements g ∈ G such that the dimension of the fixed field V^{g} is exactly k. □

Example 3.2. We consider the defining representation of the symmetric group Σ_{n}. An element σ ∈ Σ_{n} has cycle type

t(σ) = (1^{m_{1}}, 2^{m_{2}}, …, n^{m_{n}})

if there are m_{i} cycles of length i in its decomposition into disjoint cycles. Thus such an element has a fixed field V^{σ} of dimension m_{1} + ⋯ + m_{n}. Furthermore, the conjugacy class of σ has

|C_{Σ_{n}}(σ)| = \frac{n!}{1^{m_{1}}m_{1}!2^{m_{2}}m_{2}! ⋯ n^{m_{n}}m_{n}!}

elements. Note that 1m_{1} + 2m_{2} + ⋯ + nm_{n} = n by definition. Combining these formulas gives

N_{Σ_{n},V} = \frac{1}{n!} ∑_{k=1}^{n} (∑_{σ_{t}} |C_{Σ_{n}}(σ_{t})|) S(k)

= \frac{1}{n!} ∑_{k=1}^{n} ( ∑_{1m_{1}+2m_{2}+···+nm_{n}=n} ; m_{1}+···+m_{n}=k \frac{n!}{1^{m_{1}}m_{1}!2^{m_{2}}m_{2}! ⋯ n^{m_{n}}m_{n}!}) S(k).

Indeed, the number of special Σ_{n}-orbit was already calculated by Göbel in Lemma 1 of [1]: The number of special Σ_{n}-invariant orbits is just 2^{n−1}. This coincides with the number of descending special monomials x_{1}^{i_{1}} ⋯ x_{n}^{i_{n}}, i_{1} ≥ i_{2} ≥ ⋯ ≥ i_{n}, since every Σ_{n}-orbit contains exactly one descending special monomial. Thus our formula above is just equal to 2^{n−1}.

Remark 3.3. We note that

N_{G,V} ≥ N_{Σ_{n},V} ,

i.e., N_{Σ_{n},V} is a universal lower bound for the number of special G-orbits.

4. Direct Products and Finite Abelian Groups

In this section we will illustrate Proposition 3.1 with a few examples of representations of (mainly abelian) groups. Moreover, we will develop a formula for the number of special orbits in direct sums of representations.

We start with an example.

Example 4.1 (Regular Representation of ℤ/4). Consider the cyclic group G = ℤ/4 of order 4 generated by the cycle (1234) ∈ Σ_{4}. Thus our group consists of the elements (1), (1234), (13)(24), and (1432). Remembering that we must be careful to count 1-cycles, we see that ℤ/4 has one element with four disjoint cycles, one element with two disjoint cycles, and two elements with only one cycle. Thus

N_{ℤ/4,V} = \frac{1}{4}(λ_{G,V} (1)S(1) + λ_{G,V} (2)S(2) + λ_{G,V} (4)S(4))

= \frac{1}{4}(2S(1) + 1S(1) + 1S(4))

= \frac{1}{4}(2 + 3 + 75) = 20.

More generally, we consider the regular representation for an arbitrary finite cyclic group.

Example 4.2 (Regular Representation of ℤ/n). Consider the cyclic group of order n, denoted by ℤ/n, generated by the cycle (123 ⋯ n) ∈ Σ_{n}. Since a permutation (123 ⋯ n)^{j} has precisely gcd(n, j) disjoint cycles, we find that

λ_{ℤ/n,V} (k) = ∑_{1≤j≤n} ; gcd(n,j)=k 1 = \begin{cases}ϕ(n/k), & if k|n \\ 0, & otherwise. \end{cases}

Thus N_{ℤ/n,V} = \frac{1}{n} ∑ ϕ(n/d)S(d). The first few values, beginning at n = 1 are

1, 2, 5, 20, 109, 784, 6757, 68240, 787477, 10224812, ….

This is sequence A019536 in [5], which counts the number of necklaces of n beads with up to n unlabeled colors.

We want to develop a formula for sums of representations. We start with two easy examples.

Example 4.3 (Elementary Abelian 2-Groups). Consider the Klein-Four Group K_{4} ⊆ Σ_{4} consisting of the elements (1), (12), (34), (12)(34). Then

N_{K_{4},V} = \frac{1}{4}(S(2) + 2S(3) + S(4)) = 26.

More generally, for an elementary abelian 2-group (ℤ/2)^{m} ⊆ Σ_{2m} generated by the transpositions (2i − 1, 2i), i = 1, …, m, we find

λ_{(ℤ/2)^{m},V} (k) = \begin{cases}\binom{m}{k−m}, & if m ≤ k ≤ 2m, \\ 0, & otherwise. \end{cases}

Hence

N_{(ℤ/2)^{m},V} = \frac{1}{2^{m}} ∑_{k=m}^{2m} \binom{m}{k − m}S(k).

The first few terms of this sequence from n = 1 are

2, 26, 818, 47834, 4488722, 617364026, 117029670578, ….

This is sequence A059516 in [5]. It counts the number of ways n intervals of length at least zero can overlap.

Example 4.4 (Elementary Abelian p-Groups). Let p be a prime number. Consider an elementary abelian p-group (ℤ/p)^{m} ⊆ Σ_{pm} generated by the cycles (p(i − 1) + 1, …, pi) for i = 1, …, m. If m = 1 we find by the calculations in Example 4.2:

N_{ℤ/p,V} = \frac{1}{p}(ϕ(p)S(1) + ϕ(1)S(p)).

For m = 2 we have

N_{ℤ/p×ℤ/p,V} = \frac{1}{p^{2}} (1 · S(2p) + (p − 1)2S(p + 1) + (p − 1)^{2}S(2)).

In general we find

N_{(ℤ/p)^{m},V} = \frac{1}{p^{m}} ∑_{k=0}^{m}(p − 1)^{k}\binom{m}{k}S(mp − k(p − 1)).

The first few terms of this sequence for p = 3 from m = 1 are

5, 555, 273245, 357071595, 969618315005, 4732462989457035, 37693215885154484765, . . ..

For p = 5 from m = 1 we have

109, 4091403, 1842421318717, 4284436559065961835, 34143676145867329865644189, . . ..

In general, we obtain the following result for direct sums of representations.

Proposition 4.5. Let ρ : G ↪ GL(n, 𝔽) and ρ′ : H ↪ GL(m, 𝔽) be permutation representations of finite groups G and H. Denote by V = 𝔽^{n} and W = 𝔽^{m}. Then

N_{G×H,V ×W} = \frac{1}{|G||H|} ∑_{k=1}^{n+m} (∑_{l=1}^{k−1} λ_{G,V} (l)λ_{H,W} (k − l)) S(k).

Proof. We note that

λ_{G×H,V ⊕W} (k) = ∑_{l=1}^{k−1} λ_{G,V} (l)λ_{H,W} (k − l)

and thus we are done by Proposition 3.1. □

We illustrate this with the computation for arbitrary finite abelian groups.

Example 4.6 (Finite Abelian Groups). Let G = ℤ/n_{1} × ⋯ × ℤ/n_{m} ≤ Σ_{n_{1}+···+n_{m}} be generated by the m disjoint cycles

(1, …, n_{1}), (n_{1} + 1, …, n_{1} + n_{2}), …, (n_{1} + ⋯ + n_{m−1} + 1, …, n_{1} + n_{2} + ⋯ + n_{m}).

Let g = (g_{1}, …, g_{m}) ∈ ℤ/n_{1} × ⋯ × ℤ/n_{m}. Let V_{i} be the corresponding subspace of dimension n_{i}. Then

dim_{𝔽} V^{g} = dim_{𝔽} V_{1}^{g_{1}} + ⋯ + dim_{𝔽} V_{m}^{g_{m}}.

We obtain by the preceding proposition

λ_{G,V} (k) = ∑_{l_{1}+···+l_{m}=k} λ_{ℤ/n_{1},V_{1}}(l_{1}) ⋯ λ_{ℤ/n_{m},V_{m}}(l_{m}).

N_{ℤ/n,V} = \frac{1}{n} ∑ ϕ(n/d)S(d). Thus

N_{G,V} = \frac{1}{n_{1} ⋯ n_{m}} ∑_{k} ∑_{l_{1}+···+l_{m}=k} ϕ(n_{1}/l_{1}) ⋯ ϕ(n_{m}/l_{m})S(k)

= \frac{1}{n_{1} ⋯ n_{m}} ∑_{l_{1}|n_{1}} ⋯ ∑_{l_{m}|n_{m}} ϕ(n_{1}/l_{1}) ⋯ ϕ(n_{m}/l_{m})S(l_{1} + ⋯ + l_{m}).

The following tables gives some values of N_{G,V} for G = ℤ/n_{1} × ℤ/n_{2}.

n = 1  n = 2  n = 3  n = 4  n = 5
ℤ/1 × ℤ/n  3  8  27  140  939
ℤ/2 × ℤ/n  8  26  108  668  5204
ℤ/3 × ℤ/n  27  108  555  4092  37035
ℤ/4 × ℤ/n  140  668  4092  34844  357308
ℤ/5 × ℤ/n  939  5204  37035  357308  4091403
ℤ/6 × ℤ/n  7900  49496  399332  4289444  54115732
ℤ/7 × ℤ/n 77979 545228 4920939 58243388  802679403
ℤ/8 × ℤ/n 885980 6833768 68202372 881517284 13172347508

We close this section with a nonabelian example.

Example 4.7 (The Dihedral Group D_{2n} of Order 2n). For n ≥ 3 let D_{2n} denote the dihedral group of order 2n. It has a natural permutation representation of dimension n as D_{2n} can be considered as the permutation group of the vertices of a regular n-gon. As such it is generated by a rotation (1, 2, …, n) and a reflection (1, n)(2, n − 1) ⋯ (\frac{n}{2}, \frac{n+2}{2}) for n even, resp. (1, n)(2, n − 1) ⋯ (\frac{n−1}{2}, \frac{n+1}{2}) for odd n. See Example 2 in Section 5.8 of [4] for the special case of n = 5. We can partition D_{2n} as D_{2n} = ℤ/n ⊔ R_{n} where R_{n} consists of elements of order 2. Having already deduced the necessary information about the disjoint cycle representations of elements of ℤ/n in Example 4.2, it remain only to do the same for elements in R_{n}. But since these are elements of order 2, the required information can be deduced by counting the number of fixed points of each elements of R_{n}, which will depend on the parity of n. The end result is

N_{D_{2n},V} = \begin{cases}\frac{1}{2}N_{ℤ/n,V} + \frac{1}{2}S(\frac{n+1}{2}), & for n odd, \\ \frac{1}{2}N_{ℤ/n,V} + \frac{1}{4}S(\frac{n}{2}) + \frac{1}{4}S(\frac{n+2}{2}), & for n even \end{cases}

with N_{ℤ/n,V} from the previous example. The first few terms, from n = 1 are

1, 2, 4, 14, 61, 414, 3416, 34274, 394009, 5113712, ….

This is Sequence A019537 in [5].

5. Regular Representations and Vector Invariants

If G acts diagonally on m copies of V then

λ_{G,V^{⊕m}}(k) = λ_{G,V} (\frac{k}{m})

We want to find the function λ_{G,V} for the regular representation of an arbitrary finite group G, 𝔽G. If g ∈ G, then ⟨g⟩ ≤ G is a cyclic subgroup. Thus 𝔽G restricted to ⟨g⟩ gives the |G : ⟨g⟩|-fold regular representation of ⟨g⟩. Hence

λ_{G,V} (k) = |\{g ∈ G | |g| = \frac{|G|}{k}\}| .

Thus

N_{G,V} = \frac{1}{|G|} ∑_{k||G|} λ_{G,V} (k)S(k) = \frac{1}{|G|} ∑_{k||G|} |\{g ∈ G||g| = \frac{|G|}{k}\}| S(k)

for the regular representation. Thus for the m-fold regular representation we get

N_{G,V} = \frac{1}{|G|} ∑_{k=1}^{|G|m} λ_{G,V^{⊕m}}(k)S(k)

= \frac{1}{|G|} ∑_{k=1}^{|G|m} λ_{G,V} (\frac{k}{m}) S(k)

= \frac{1}{|G|} ∑_{l=1}^{|G|} λ_{G,V} (l)S(ml).

More generally we find for arbitrary vector invariants:

Proposition 5.1. Let ρ : G ↪ GL(n, 𝔽) be a faithful representation of a finite group G. Let V = 𝔽^{n}, and set ρ_{1} = ρ. Then the m-fold vector invariants of ρ are given by the diagonal action of G on m copies of V. We find

N_{G,V^{⊕m}} = \frac{1}{|G|} ∑_{k=1}^{|G|} λ_{G,V} (k)S(mk).

Proof. This is a straightforward generalization of the case of vector invariants of the regular representation which we discussed above. □

6. Special Orbits in 𝔽[V]^{G}: an Algorithm

In this section we show how to use the results from the preceding sections to create another algorithm that counts the number of orbits of special monomials for an arbitrary permutation group which relies on the representation theory of the symmetric group.

Let ρ : Σ_{n} ↪ GL(n, 𝔽) be the defining representation of Σ_{n}. Let V = 𝔽^{n}. Then we define the function

μ : Σ_{n} ⟶ ℕ, g ↦ dim V^{g}.

Then for any subgroup G ≤ Σ_{n} we obtain

λ_{G,V} (k) = |μ^{−1}(k) ∩ G|.

Lemma 6.1. Note that this implies

|G|N_{G,V} ≤ N_{Σ_{n},V} |Σ_{n}|,

since λ is nonnegative. Thus we obtain a relative bound for the number of special orbits

N_{G,V} ≤ N_{Σ_{n},V} |Σ_{n} : G| = \frac{2^{n−1}n!}{|G|}.

Proof. We simply compute

|G|N_{G,V} = ∑_{k=1}^{n} λ_{G,V} (k)S(k) ≤ ∑_{k=1}^{n} λ_{Σ_{n},V} (k)S(k) = |Σ_{n}|N_{Σ_{n},V} .

□

We observe that μ is a class function. Even more, μ is constant on the sets of elements in Σ_{n} consisting of the same number of disjoint cycles. Thus we can write

N_{G,V} = \frac{1}{|G|} ∑_{g} |C_{g}(G)|S(c(g)) = \frac{1}{|G|} ∑_{g} |C_{g}(Σ_{n}) ∩ G|S(c(g))

where the sum runs over a set of representatives of the conjugacy classes, C_{g}(G) is the conjugacy class of g ∈ G, and c(g) is the number of disjoint cycles in g. The disadvantage of this formula is that it requires precise knowledge about the embedding G ↪ Σ_{n}, because one needs to find the values of |C_{g}(Σ_{n}) ∩ G|. Therefore, we propose the following:

Proposition 6.2.

N_{G,V} = \frac{1}{|G|} ∑_{g∈G} S(dim V^{g}) = \frac{1}{|G|} ∑_{g∈G} S(μ(g)).

Proof. Follows immediately from Proposition 3.1. □

Since our calculations are characteristic free, we might as well assume we are working over the complex numbers, thus we can write the class function μ as a linear combination of the characters of the full symmetric group. Let p_{i}(n) be the number of partitions of n into i nonnegative integers. Then the total number of conjugacy classes in Σ_{n} is equal

C = ∑_{l=1}^{n} p_{l}(n)

(i.e., the total number of partitions into nonnegative integers). Thus the character table of Σ_{n} is a C × C complex invertible matrix, call it M. Thus if we write the function μ as a linear combination of the irreducible characters χ_{i} of Σ_{n}

μ = a_{1}χ_{1} + ⋯ + a_{C}χ_{C}

we find

[a_{1} ; a_{2} ; ⋮ ; a_{C} ] = M^{−1} [ n ; n − 1 ; ⋮ ; 1]

where in the column vector on the right each i appears p_{i}(n) times. Thus once we have the character table of Σ_{n}, we can compute the function μ and hence N_{G,V} for any subgroup G ≤ Σ_{n}. We will study this in more detail in a succeeding paper, [2]. For now, we want to illustrate this process with the calculations for n = 2, …, 6.

Example 6.3 (Σ_{2}). The following table contains in character table of Σ_{2} and, in the last row, the values of the function μ on the conjugacy classes:

\begin{aligned}& (1) & (12) \\ χ_{1} & 1 & 1 \\ χ_{2} & 1 & -1 \\ μ & 2 & 1 \end{aligned}

We obtain the two linear equations

a_{1} + a_{2} = 2 and a_{1} − a_{2} = 1.

Thus a_{1} = 3/2 and a_{2} = 1/2.

Example 6.4 (Σ_{3}). The following table contains in character table of Σ_{3} and, in the last row, the values of the function μ on the conjugacy classes:

\begin{aligned}& (1) & (12) & (123) \\ χ_{1} & 1 & 1 & 1 \\ χ_{2} & 1 & 1 & -1 \\ χ_{3} & 2 & -1 & 0 \\ μ & 3 & 2 & 1 \end{aligned} Direct computation yields

a_{1} = 5/3, a_{2} = 2/3, and a_{3} = 1/3.

Example 6.5 (Σ_{4}). The following table contains in character table of Σ_{4} and, in the last row, the values of the function μ on the conjugacy classes:

(1) (12) (123) (12)(34) (1234)
χ_{1} 1  1  1  1  1
χ_{2} 1 -1  1  1  -1
χ_{3} 2  0  -1  2  0
χ_{4} 3  1  0  -1  -1
χ_{5} 3 -1  0  -1  1
μ 4  3  2  2  1

Direct computation yields

a_{1} = 25/12, a_{2} = 1/12, a_{3} = 1/6, a_{4} = 3/4, and a_{5} = −1/4.

Example 6.6 (Σ_{5}). The following table contains in character table of Σ_{5} and, in the last row, the values of the function μ on the conjugacy classes:

(1) (12) (123) (12)(34) (1234) (123)(45) (12345)
χ_{1} 1  1  1  1  1  1  1
χ_{2} 1 -1  1  1  -1  -1  1
χ_{3} 4  2  1  0  0  -1  -1
χ_{4} 4 -2  1  0  0  1  -1
χ_{5} 6  0  0  -2  0  0  1
χ_{6} 5  1  -1  1  -1  1  0
χ_{7} 5 -1  -1  1  1  -1  0
μ 5  4  3  3  2  2  1

Direct computation yields

a_{1} = 137/60, a_{2} = −1/20, a_{3} = 4/5, a_{4} = 2/15,
a_{5} = −3/10, a_{6} = 1/4, and a_{7} = −1/12.

Example 6.7 (Σ_{6}). The following table contains in character table of Σ_{6} and, in the last row, the values of the function μ on the conjugacy classes:

(1) (12) (123) (12)(34) (1234) (123)(45) (12345) (12)(34)(56) (123)(456) (1234)(56) (123456)
χ_{1} 1  1  1  1  1  1  1  1  1  1  1
χ_{2} 1  -1  1  1  -1  -1  1  -1  1  1  -1
χ_{3} 5  3  2  1  1  0  0  -1  -1  -1  -1
χ_{4} 5  -3  2  1  -1  0  0  1  -1  -1  1
χ_{5} 10 2  1  -2  0  -1  0  -2  1  0  1
χ_{6} 10 -2  1  -2  0  1  0  2  1  0  -1
χ_{7} 9  3  0  1  -1  0  -1  3  0  1  0
χ_{8} 9  -3  0  1  1  0  -1  -3  0  1  0
χ_{9} 5  1  -1  1  -1  1  0  3  2  -1  0
χ_{10} 5  -1  -1  1  1  -1  0  -3  2  -1  0
χ_{11} 16 0  -2  0  0  0  1  0  -2  0  0
μ  6  5  4  4  3  3  2  3  2  2  1

Direct computation yields

a_{1} = 289/120, a_{2} = 3/40, a_{3} = 7/8, a_{4} = −1/8, a_{5} = −1/4,
a_{6} = 1/12, a_{7} = 7/40, a_{8} = 7/40, a_{9} = 5/24, a_{10} = −1/8,
and a_{11} = −2/15.

References

1. M. Göbel, On the number of special permutation-invariant orbits and terms, Applicable Algebra in Engineering, Communication and Computing 8 (1997), 505-509.

2. C. Monico and M. D. Neusel, Counting Special Monomials II, in preparation.

3. M. D. Neusel, Degree Bounds. An Invitation to Postmodern Invariant Theory, Topology and its Applications 154 (2007), 792-814.

4. M. D. Neusel and L. Smith, Invariant Theory of Finite Groups, Mathematical Surveys and Monographs, Volume 94, AMS, Providence RI 2002.

5. N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://www.research.att.com/ njas/sequences/, 2008.

6. R. Stanley, Enumerative Combinatorics Volume I, Cambridge Studies in Advanced Mathematics 49, Cambridge University Press, Cambridge 1997.

Department of Mathematics and Statistics, MS 1042, Texas Tech University, Lubbock, Texas 79409

  E-mail address: C.Monico@ttu.edu and Mara.D.Neusel@ttu.edu