The Action of the Symmetric Group on a Generalized Partition Semilattice

Robert Gill Department of Mathematics and Statistics University of Minnesota Duluth 10 University Drive Duluth, MN 55812

                  rgill@d.umn.edu

Submitted: February 7, 1998; Accepted: April 21, 2000

Key Words: hyperplane arrangement, Möbius function, homology, induced character, cyclic group

AMS Subject Classification (1991): Primary 06A07; Secondary 05E25, 52B30, 20C30, 11A05

Abstract

Given an integer n ≥ 2, and a non-negative integer k, consider all affine hyperplanes in ℝ^{n} of the form x_{i} = x_{j} +r for i, j ∈ [n] and a non-negative integer r ≤ k. Let Π_{n,k} be the poset whose elements are all nonempty intersections of these affine hyperplanes, ordered by reverse inclusion. It is noted that Π_{n,0} is isomorphic to the well-known partition lattice Π_{n}, and in this paper, we extend some of the results of Π_{n} by Hanlon and Stanley to Π_{n,k}.

Just as there is an action of the symmetric group 𝔖_{n} on Π_{n}, there is also an action on Π_{n,k} which permutes the coordinates of each element. We consider the subposet Π_{n,k}^{σ} of elements that are fixed by some σ ∈ 𝔖_{n}, and find its Möbius function μ_{σ}, using the characteristic polynomial. This generalizes what Hanlon did in the case k = 0. It then follows that (−1)^{n−1}μ_{σ}(Π_{n,k}^{σ}), as a function of σ, is the character of the action of 𝔖_{n} on the homology of Π_{n,k}.

Let Ψ_{n,k} be this character times the sign character. For ℭ_{n}, the cyclic group generated by an n-cycle σ of 𝔖_{n}, we take its irreducible characters and induce them up to 𝔖_{n}. Stanley showed that Ψ_{n,0} is just the induced character χ ↑_{ℭ_{n}}^{𝔖_{n}} where χ(σ) = e^{2πi/n}. We generalize this by showing that for k > 0, there exists a non-negative integer combination of the induced characters described here that equals Ψ_{n,k}, and we find explicit formulas. In addition, we show another way to prove that Ψ_{n,k} is a character, without using homology, by proving that the derived coefficients of certain induced characters of 𝔖_{n} are non-negative integers.

1 Introduction

Given a finite partially ordered set P, let ≤ denote the partial order, and assume that P has a unique minimal element ˆ0. An automorphism σ on P is a permutation of the elements of P such that if x ≤ y, then σ(x) ≤ σ(y). Let P^{σ} be the subposet of P that consists of the elements that are fixed by σ. If P is a lattice, then so is P^{σ} (For a proof, see page 319 of [9]).

Now we look at one particular lattice. For some positive integer n, if we let Π_{n} denote the set of all partitions of the set [n] = {1, 2, ..., n}, ordered by refinement, then Π_{n} is a lattice. There has been a lot of work on Π_{n}, and the action of the symmetric group 𝔖_{n} on it. An element of 𝔖_{n} permutes the elements of [n] = {1, 2, ..., n}, and therefore acts as an automorphism on Π_{n}. Given σ ∈ 𝔖_{n}, let Π_{n}^{σ} denote the subposet of Π_{n} of elements that are fixed by σ.

The Möbius function μ is defined on intervals [x, y] = {z: x ≤ z ≤ y} of a poset P such that μ(x, x) = 1 for all x ∈ P and for x < y,

∑_{z∈[x,y]} μ(x, z) = 0.

If P has ˆ1, then define μ(P) to be μ(ˆ0, ˆ1). Let μ_{σ} be the Möbius function of Π_{n}^{σ}. In 1981, Hanlon [9, Th. 4] showed that

μ_{σ}(Π_{n}^{σ}) = \begin{cases}μ(n/d)(−\frac{n}{d})^{d−1}(d − 1)! & if σ is a product of d cycles \\ & of length n/d for some d|n; \\ 0 & otherwise. \end{cases}  (1)

Here, μ(n/d) is the classical number-theoretic Möbius function. In 1982, Stanley [13] used this result and the Lefschetz Fixed Point Theorem (stated in section 3) to show that as a function of σ, (−1)^{n−1}μ_{σ}(Π_{n}^{σ}) is the character of a particular representation of 𝔖_{n} (Refer to [12, Ch.1] for definitions), its action on the top-dimensional homology of Π_{n}, which we define in section 3. Let σ be an n-cycle in 𝔖_{n} and let ℭ_{n} be the cyclic subgroup of 𝔖_{n} generated by σ. Let χ be the (irreducible) character of ℭ_{n} such that χ(σ) = e^{2πi/n}. Stanley showed that the induced character (defined in [12, §1.12]) χ ↑_{ℭ_{n}}^{𝔖_{n}} equals this homology character times the sign character, which we denote Ψ_{n}. It is appropriate to show that Ψ_{n} is an induced character from the cyclic group of order n since it is zero for all elements of 𝔖_{n} that are not conjugate to any element of ℭ_{n}.

In this paper, we extend these results of Π_{n} to a generalized partition semilattice, which we now define. We will call it Π_{n,k}. The partition lattice is isomorphic to a poset of subspaces of ℝ^{n} for n ≥ 2, ordered by reverse inclusion, whose elements are all intersections of the hyperplanes

H_{i,j} = {x ∈ ℝ^{n}: x_{i} = x_{j}} ,

for i, j ∈ [n], with minimal element ℝ^{n}. In other words, if i and j are in the same block of a partition of Π_{n}, then the corresponding subspace of ℝ^{n} is contained in H_{i,j}.

Now consider the affine hyperplanes

H_{i,j,r} = {x ∈ ℝ^{n}: x_{i} = x_{j} + r} .

For a non-negative integer k, let Π_{n,k} be the poset whose elements are all nonempty intersections of the H_{i,j,r} such that r ∈ ℤ and |r| ≤ k. These sets of hyperplanes are known as the extended Catalan arrangements (See after Theorem 2.3 in [14]). The unique minimal element is again the whole space ℝ^{n}, but there is more than one maximal element if k > 0. For an affine subspace X ∈ Π_{n,k}, its dimension dim(X) is equal to the dimension of the linear translation of X, the set {v − x: v ∈ X} for a particular x ∈ X. So X is maximal if and only if dim(X) = 1.

First, the characteristic polynomial of a poset P of affine subspaces of ℝ^{n} is given by

λ_{P} (t) = ∑_{X∈P} μ(ˆ0, X)t^{dim(X)}.

In section 2, we let P = Π_{n,k} and consider P^{σ}, the subposet of P fixed by some σ ∈ 𝔖_{n}. We use the characteristic polynomial of P and the paper by Hanlon [9] to show that the Möbius function of this subposet, μ_{σ}(P^{σ}), is as stated in (4). Then in section 3, we use a result from Stanley’s paper [13] to show that the character of the representation of 𝔖_{n} acting on the top homology of P is (−1)^{n−1}μ_{σ}(P^{σ}).

Let Ψ_{n,k} be this character times the sign character, so Ψ_{n,k} = (−1)^{d−1}μ_{σ}(P)^{σ}). In sections 4 and 5, we show that Ψ_{n,k} can be expressed as a non-negative integer combination of the characters of 𝔖_{n} that are induced from irreducible characters of ℭ_{n}, as in (15). First, we show that the induced characters in this sum are a basis for all induced characters from ℭ_{n}. Then the main result in section 4 is that Ψ_{n,k} is a sum of induced characters from ℭ_{d} for each d|n. In section 5, we find an explicit expression for Ψ_{n,k} in terms of these induced characters, also proving some concepts from number theory which we use along the way.

In the last section, we prove separately that the coefficients are non-negative integers, using the formula derived in Lemma 11, which gives us a way to prove that Ψ_{n,k} is a character without proving that it is a homology character.

There is a lot more one can do on the subject of Π_{n,k}. For example, Christos Athanasiadis in his Ph.D. thesis [1] used the Möbius Inversion Formula to find the characteristic polynomial of numerous affine hyperplane arrangements, including this one [1, Th. 5.1]. Also, Julie Kerr in her Ph.D. thesis [10] discusses the poset obtained by adding a unique maximal element to Π_{n,k}. Although it becomes a lattice, its characteristic polynomial does not in general factor linearly as it does for Π_{n,k}. But its top-dimensional homology is isomorphic to a direct sum of copies of the algebra ℂ𝔖_{n}, known as the regular representation of 𝔖_{n}. There is also additional work on the poset Π_{n,k} in [7].

2 The Möbius Function of Π_{n,k}^{σ}

We first state [1, Th. 5.1]. This generalizes the characteristic polynomial of the wellknown partition lattice, which is the case k = 0.

Theorem 1. The characteristic polynomial of Π_{n,k} is given by

λ_{Π_{n,k}}(t) = t(t − nk − 1)(t − nk − 2)...(t − n(k + 1) + 1).  (2)

We now extend some more results of the partition lattice Π_{n} to Π_{n,k}, first from Hanlon’s paper [9]. Given any poset P with a unique minimal element ˆ0, let Max(P) denote the set of maximal elements of P and let

μ(P) = ∑_{x∈Max(P)} μ(ˆ0, x).  (3)

Now let P = Π_{n,k} and consider the action of the symmetric group 𝔖_{n} on P, permuting the coordinates of the elements. We consider the subposet P^{σ}, which consists of the elements of P that are fixed by a permutation σ ∈ 𝔖_{n}, meaning whenever X ∈ P^{σ} and X ⊆ H_{i,j,r}, then X ⊆ H_{σ(i),σ(j),r}. Note that if ε is the identity permutation, then P^{ε} = P.

Let μ_{σ} denote the Möbius function in P^{σ} = Π_{n,k}^{σ}. The goal in this section is to prove that

μ_{σ}(P^{σ}) = \begin{cases}μ(n/d)(−\frac{n}{d})^{d−1}\binom{(k+1)d−1}{d−1}(d − 1)! & if σ is a product of d cycles \\ & of length n/d for some d|n; \\ 0 & otherwise. \end{cases}  (4)

This is the Möbius function of P^{σ}, defined as in (3). It generalizes Hanlon’s result for k = 0, stated in (1). If σ, τ ∈ 𝔖_{n}, then one can verify the isomorphism P^{σ} ≅ P^{τστ^{−1}}. Hence, viewed as a function of σ, μ_{σ}(P^{σ}) is a class function on 𝔖_{n}. It is in fact, up to a sign, a character of 𝔖_{n}, as we will soon see.

In order to find μ_{σ}(P^{σ}), we find the sum of the Möbius functions of each maximal interval of P^{σ}. The methods we use here are in many cases very similar to those used by Hanlon, with a slightly different poset. We state a well-known theorem that we will use here. Suppose we are given a finite lattice L = [ˆ0, ˆ1]. For some x ∈ L, define Comp(x) to be the set of complements of x in L, i.e., Comp(x) = {y ∈ L: x∧y = ˆ0 and x∨y = ˆ1}. Then Crapo’s Complementation Theorem [5, Th. 4] says that for any x ∈ L,

μ(L) = ∑_{\begin{matrix}y,z∈Comp(x) \\ y≤z \end{matrix}} μ(ˆ0, y)μ(z, ˆ1),  (5)

and if some element of L has no complements, then μ(L) = 0.

So we need to show that [ˆ0, X]^{σ} is a lattice for each X ∈ Max(P^{σ}). By [18, Prop. 3.1], since every element of P is an intersection of affine hyperplanes from a given set, it is a geometric semilattice. Thus each maximal interval [ˆ0, X] in P is a lattice, and by the first paragraph of section 1, [ˆ0, X]^{σ} is a lattice too. So Crapo’s Theorem applies here. Now we determine which element we use in Equation (5).

For each σ ∈ 𝔖_{n}, it can be verified that

Max(P^{σ}) = Max(P) ∩ P^{σ},  (6)

which is mentioned in the proof of [10, Th. 2.1]. For σ, let

σ = σ_{1}σ_{2}...σ_{d}  (7)

be the decomposition of σ into disjoint cycles. For i = 1, ..., d, let C_{i} be the support of the cycle σ_{i}, that is, the set of all numbers from the cycle σ_{i}. It will be convenient to extend Hanlon’s definition of the hinge of Π_{n} [9, p. 324], the partition which puts each cycle of σ into its own block. Here, we want to extend it to any k ≥ 0, so that it is an intersection of affine hyperplanes. In Π_{n,0} the element that corresponds to the hinge of Π_{n} is the intersection of all H_{j,l} such that j and l are in the same C_{i}. So this will be the hinge of Π_{n,0}. The following lemma shows that for any k, only certain hyperplanes in Π_{n,k} can contain the hinge.

Lemma 2. Suppose two numbers i and j are in the same cycle of σ, and for some Z ∈ P^{σ}, Z is contained in H_{i,j,r} for some r. Then r = 0.

Proof. Suppose Z ∈ P^{σ} and σ_{1} is one of the disjoint cycles of σ as in (7), with length m ≥ 2. Suppose without loss of generality that i, j ∈ C_{1} and Z ⊆ H_{i,j,r}. Then there exists an s such that σ^{s}(i) = j, so let τ = σ^{s}. Then Z ⊆ H_{i,τ(i),r} and then Z ⊆ H_{τ^{ω}(i),τ^{ω+1}(i),r}, since for each integer ω, P^{σ} ⊆ P^{σ^{ω}}. This means for any z ∈ Z, z_{i} = z_{τ^{l}(i)} + lr, so z_{i} = z_{τ^{m}(i)} + mr = z_{i} + mr, since τ^{m} fixes all elements of C_{1}. Therefore r = 0 and Z ⊆ H_{i,j}.

This proves that no nontrivial extension of the hinge is possible for Π_{n,k}. So define the hinge h^{σ} of P^{σ} to be the intersection of all H_{j,l} for which j and l are in the same cycle of σ. For an element Y ∈ Π_{n,k}, define π(Y) to be the partition that corresponds to Y. In other words, if Y ⊆ H_{i,j,r} for some r, then i and j are in the same block of π(Y). Therefore, each C_{i} is a block of π(h^{σ}). Then dim(h^{σ}) is the number of blocks of π(h^{σ}) and the number of cycles of σ. For example, if σ = (1, 2, 3)(4, 5)(6) ∈ 𝔖_{6}, then h^{σ} = H_{1,2} ∩ H_{1,3} ∩ H_{2,3} ∩ H_{4,5} in ℝ^{6}, and dim(h^{σ}) = 3. Notice that by Lemma 2, h^{σ} ≤ X for all X ∈ Max(P^{σ}), and that h^{σ} is the greatest lower bound of all the maximal elements of P^{σ}. This is the element that whose complements we will find in order to prove the main result of this section. Now we are ready to prove one case of (4).

Theorem 3. μ_{σ}(P^{σ}) = 0 unless all disjoint cycles of σ have the same length.

Proof. We prove this by showing that for a given X ∈ Max(P^{σ}), h^{σ} has no complements in [ˆ0, X]^{σ}. If σ is an n-cycle, then all cycles of σ have the same length, and we do not consider that here. Otherwise, given any two blocks B_{1} and B_{2} of π(h^{σ}), a given element Z ∈ P^{σ} is a complement of h^{σ} in [ˆ0, X]^{σ} only if there exists one element from each of the two blocks, say i ∈ B_{1} and j ∈ B_{2}, such that Z ⊆ H_{i,j,r} for some r. We need to show that if any two blocks of π(h^{σ}) are not the same size, or equivalently, if any two cycles are not the same length, then there is an element less than Z that is not ˆ0 and is also less than h^{σ}.

Suppose we pick out two cycles from σ that have different lengths. We can assume that σ_{1} = (1, ..., m) and σ_{2} = (m + 1, ..., m + b), as defined in (7), and m < b. In order for Z to be a complement of h^{σ} in [ˆ0, X]^{σ}, Z must be contained in some H_{1,j,r} for some r and for m + 1 ≤ j ≤ m + b. So assume without loss of generality that Z ⊆ H_{1,m+1,r}, so then Z ⊆ H_{s,m+s,r} for all s = 1, ..., m. Let g = gcd(m, b). Then g < b and Z ⊆ H_{m+1,m+g+1}. Let Y be the intersection of all hyperplanes H_{s−g,s} for m + g < s ≤ m + b. Then Z ≥ Y and π(Y) is a refinement of π(h^{σ}), so since by Lemma 2, only hyperplanes H_{i,j} can contain h^{σ}, h^{σ} ≥ Y too.

Therefore, h^{σ} ∧ Z ≥ Y > ˆ0, so Z is not a complement of h^{σ} in [ˆ0, X]^{σ}. Since we chose an arbitrary X ∈ Max(P^{σ}), we have proved that h^{σ} has no complements in any [ˆ0, X]^{σ}. Thus μ_{σ}(ˆ0, X) = 0 for all X ∈ Max(P^{σ}) and therefore, μ_{σ}(P^{σ}) = 0 unless all cycles of σ have the same length.

Now we will find μ_{σ}(P^{σ}) for the other case of (4), if σ is a product of d cycles of length n/d. To do this, we may assume that

σ = (1, 2, ..., j)(j + 1, ..., 2j) ⋯ (n − j + 1, ..., n),

where j = n/d. Again, for each X ∈ Max(P^{σ}), we use complements of the hinge h^{σ} in [ˆ0, X]^{σ} and equation (5). If C ∈ Comp(h^{σ}) in [ˆ0, x]^{σ}, then C ⊈ H_{ω_{1},ω_{2},r} for any ω_{1}, ω_{2} ∈ [j] and any r, and

C ⊆ H_{1,sj+i_{s},r_{s}}  (8)

for s = 1, 2, ..., d − 1, and r_{s} and i_{s} ∈ [j] that depend on s. Note that dim(C) = j for all such C, so no two complements are comparable to each other. This will be used later to simplify (5). We now state the other case that we will prove, but we need a few lemmas first. Many of the lemmas here are similar to parts of [9, Lemma 6].

Theorem 4. μ_{σ}(P^{σ}) = μ(n/d)(−\frac{n}{d})^{d−1}\binom{(k+1)d−1}{d−1}(d − 1)! if σ is a product of d disjoint cycles of length n/d.

Lemma 5. Given X ∈ Max(P^{σ}), if C ∈ Comp(h^{σ}) in [ˆ0, X]^{σ}, then [C, X]^{σ} ≅ 𝔇_{j}, the lattice of divisors of j. Thus, μ_{σ}(C, X) = μ(n/d).

Proof. For any point in an affine subspace from [C, X]^{σ}, whatever equality is in the coordinates 1, 2, ..., j, the same equality holds for corresponding coordinates from the other blocks of π(h^{σ}), depending on i_{s} in (8). At the bottom element C of the interval [C, X]^{σ}, for any i_{1}, i_{2} ∈ [j], C ⊈ H_{i_{1},i_{2},r} for any r. At the maximal element, X ⊆ H_{i_{1},i_{2}} by Lemma 2. So [C, X]^{σ} here is isomorphic to [C, ˆ1]^{σ} in the case k = 0. Since [9, Lemma 6c] says that [C, ˆ1]^{σ} ≅ 𝔇_{n/d}, we are done.

Lemma 6. There exists a one-to-one correspondence between the maximal elements of P^{σ} and the maximal elements of Π_{d,k}.

Proof. If d = 1, then P^{σ} has only one maximal element, and |Π_{1,k}| = 1. If d ≥ 2, then by Lemma 2, if X ∈ Max(P^{σ}), then X ⊆ H_{j(i−1)+ω,j(i−1)+ω+1} for all i = 1, ..., d and all ω ∈ [j − 1]. Then the X ∈ Max(P^{σ}) such that X ⊆ H_{j(ω_{1}−1)+1,j(ω_{2}−1)+1,r} ⊆ ℝ^{n} corresponds to the Y ∈ Max(Π_{d,k}) such that Y ⊆ H_{ω_{1},ω_{2},r} ⊆ ℝ^{d}, and vice-versa. So this correspondence is a bijection.

Lemma 7. Given a maximal element X ∈ P^{σ}, let Y be its corresponding maximal element in Π_{d,k}, as described in Lemma 6. If d ≥ 2, then for all C ∈ Comp(h^{σ}) in [ˆ0, X]^{σ}, [ˆ0, C]^{σ} ≅ [ˆ0, Y]_{Π_{d,k}}. If d = 1, then C = ˆ0 is the only complement. Thus μ_{σ}(ˆ0, C) is constant for all C ≤ X.

Proof. If d = 1, then since h^{σ} is the maximal element, ˆ0 is its only complement. If d ≥ 2, then we must find a bijection between the elements of [ˆ0, C]^{σ} ⊆ P^{σ} for a given C ∈ Comp(h^{σ}) in [ˆ0, X]^{σ} and [ˆ0, Y] ⊆ Π_{d,k}. Suppose C is as in (8), and assume without loss of generality that i_{s} = 1 for all s. Then for all l = 1, ..., j, C ⊆ H_{l,sj+l,r_{s}}. Given Z ∈ [ˆ0, C]^{σ}, if Z ⊈ H_{(ω_{1}−1)i+1,(ω_{2}−1)i+1,r} for any r, then this corresponds to the element Z′ ∈ [ˆ0, y] such that Z′ ⊈ H_{ω_{1},ω_{2},r} for any r. If Z ⊆ H_{(ω_{1}−1)i+1,(ω_{2}−1)i+1,r}, then the corresponding Z′ ⊆ H_{ω_{1},ω_{2},r}. This correspondence can be defined similarly the other way, Z′ ↦ Z, so [ˆ0, C]^{σ} ≅ [ˆ0, Y]. Thus μ_{σ}(ˆ0, C) = μ_{Π_{d,k}}(ˆ0, Y) for all complements C of h^{σ} in [ˆ0, X].

Lemma 8. Given X ∈ Max(P^{σ}), h^{σ} has (\frac{n}{d})^{d−1} complements in [ˆ0, X]^{σ}.

Proof. If d = 1, then h^{σ} is the maximal element of P^{σ}, so ˆ0 is its only complement. If d > 1, then for each s = 1, 2, ..., d − 1, i_{s}, as described in (8), has n/d possible values, all independent of each other. So the number of complements of h^{σ} is (\frac{n}{d})^{d−1} for d ≥ 1.

Proof of Theorem 4. Let C_{X} be some complement of h^{σ} in [ˆ0, X]^{σ} for each X ∈ Max(P^{σ}). Thus:

∑_{X∈Max(P^{σ})} μ_{σ}(ˆ0, X) = ∑_{X} ∑_{\begin{matrix}C∈Comp(h^{σ}) \\ in [ˆ0,X]^{σ} \end{matrix}} μ_{σ}(ˆ0, C)μ_{σ}(C, X)  (9)

= μ(n/d) ∑_{X} ∑_{C} μ_{σ}(ˆ0, C)  (10)
= μ(n/d) (\frac{n}{d})^{d−1} ∑_{X} μ_{σ}(ˆ0, C_{X})  (Lemmas 7 and 8)
= μ(n/d) (\frac{n}{d})^{d−1} ∑_{Y ∈Max(Π_{d,k})} μ_{Π_{d,k}}(ˆ0, Y)  (Lemma 7)

= μ(n/d) (\frac{n}{d})^{d−1} (−1)^{d−1}(d − 1)!\binom{(k + 1)d − 1}{d − 1}  (11)

= μ(n/d) (−\frac{n}{d})^{d−1} \binom{(k + 1)d − 1}{d − 1}(d − 1)!

Equation (9) holds by Crapo’s Complementation Theorem. Ordinarily, the sum would be over all C, C′ ∈ Comp(h^{σ}) such that C ≤ C′. But no two complements of h^{σ} are comparable, as mentioned right before the statement of this theorem. So the sum is just over all C ∈ Comp(h^{σ}).

Equation (10) is true by Lemma 5. Also, ⋃_{X} {C ∈ Comp(h^{σ}) in [C, X]^{σ}} has to be a disjoint union. Suppose C ∈ Comp(h^{σ}) in both [ˆ0, X]^{σ} and [ˆ0, Y]^{σ} for X ≠ Y. Then there exist i and j such that X ⊆ H_{i,j,r_{1}} and Y ⊆ H_{i,j,r_{2}}, where r_{1} ≠ r_{2}. If we let Z = X ∧ Y, then i and j are in different blocks of π(Z), and Z ⊈ H_{i′,j′,r} for any r and for any i′ in the same block as i of π(Z) and any j′ in the same block as j, since X ⊆ H_{i′,j′,r_{1}} and Y ⊆ H_{i′,j′,r_{2}}. So Z cannot be greater than any complement of h^{σ} in [ˆ0, X]^{σ} or in [ˆ0, Y]^{σ}. But C ≤ X, Y, which means C ≤ X ∧ Y = Z, a contradiction. So it is a disjoint union.

To get the result (11), find μ(Π_{d,k}) by extracting the coefficient of t in the characteristic polynomial (2).

3 A Homology Character from μ_{σ}(P^{σ})

Again, let P = Π_{n,k}. Now we define an integer-valued function Ψ_{n,k} on 𝔖_{n} given by

Ψ_{n,k}(σ) = (−1)^{d−1}μ_{σ}(P^{σ}),  (12)

where d is the number of cycles of σ. Note that the cycles do not all have to be the same length; if they are not, then μ_{σ}(P^{σ}) = 0, so Ψ_{n,k}(σ) = 0.

We now prove that Ψ_{n,k}(σ) is, up to a sign, the character afforded by a linear action of 𝔖_{n} on a suitable homology. In fact, the character is (−1)^{n−1}μ_{σ}(P^{σ}), and Ψ_{n,k} is this character times the sign character of 𝔖_{n}. We use the methods of Stanley in [13].

Let Q be a poset with ˆ0 and ˆ1, and let Q̄ = Q \ {ˆ0, ˆ1}. We follow the notation of [16]. The order complex Δ(Q̄) is the abstract simplicial complex whose vertex set is Q̄ and whose r-dimensional faces are all chains of the form x_{0} < x_{1} < ⋯ < x_{r} in Q̄. The dimension of Δ(Q) is the largest possible value of r for any chain in Q̄.

Now n is the number of elements in the largest chain in Q, which means r ≤ n − 3. So for r = 0, ..., n − 3, C_{r}(Q̄) is defined to be the vector space over ℂ whose basis is the r-dimensional faces of Δ(Q̄). Also, C_{−1}(Q̄) is the one-dimensional vector space generated by the null chain. For all other r, C_{r}(Q̄) = 0. For r = −1, 0, ..., n − 3, the map ∂_{r}: C_{r}(Q̄) ⟶ C_{r−1}(Q̄) is a linear map called the boundary map, defined as

∂_{r}(y_{0} < y_{1} < ⋯ < y_{r}) = ∑_{i=0}^{r}(−1)^{i}(y_{0} < y_{1} < ⋯ < ŷ_{i} < ⋯ < y_{r}),

where ŷ_{i} means that y_{i} is deleted. The homology of Q for each r is

H_{r}(Q̄) = ker ∂_{r}/im ∂_{r+1}.  (13)

Now suppose P is a poset with least element ˆ0 and maybe more than one maximal element. For any X ∈ P, let Q^{X} = [ˆ0, X]. We now define a boundary map the same way as above, except that we include the maximal element X in the chains, following the definition in [4, §5]. So ∂_{r} defined above corresponds to ∂_{r+1} here. We also define the homology the same way as in (13). The r-dimensional homology for the boundary map on the order complex is known as the Whitney homology, denoted H_{r}^{W} (P), which was first defined in [2].

A poset with ˆ0 and ˆ1 is Cohen-Macaulay if every interval I has H_{r}(I) = 0 whenever r ≠ dim(Δ(I)). As mentioned earlier, P = Π_{n,k} is a geometric semilattice. If we add a unique maximal element to the poset P = Π_{n,k}, then it is a geometric lattice and therefore Cohen-Macaulay by Theorem 4.1 in [6]. So the homology of each maximal interval in P is concentrated in dimension n − 3. Therefore, by Theorem 5.1 in [4], the Whitney homology of P is

H_{n−2}^{W}(P) = ⨁_{X∈Max(P)} H_{n−3}(Q̄^{X}).  (14)

We use the Lefschetz Fixed Point Theorem (See [13, §1], and it appears that it was first stated in [3]). A version of it states that if the homology of a poset Q is concentrated in a single dimension r, then the character of the action of a group G on the homology of Q is (−1)^{r} times the Möbius function of the poset. Note that in many papers, the dimension of the homology of the null chain is 0. In that case, the character is (−1)^{r+1} times the Möbius function. The sign depends on this.

The action of 𝔖_{n} on P induces a canonical action on both the homology and the Whitney homology of P. For a Cohen-Macaulay poset Q, let β^{Q}: 𝔖_{n} → End(H(Q)) be the representation with 𝔖_{n} action on H(Q), the non-trivial top-dimensional homology on Q, following the notation of [13]. For any linear representation α of 𝔖_{n}, let ⟨α, τ⟩ be the character of α evaluated at τ ∈ 𝔖_{n}. Then here we have

⟨β^{Q^{X}}, σ⟩ = (−1)^{n−1}μ_{σ}(ˆ0, X)

for any X ∈ Max(P^{σ}). Therefore, if we let β^{P} be the representation with 𝔖_{n}-action on H^{W} (P) = H_{n−2}^{W}(P), then using (14) and (6),

⟨β^{P} , σ⟩ = ∑_{X∈Max(P^{σ})} ⟨β^{Q^{X}}, σ⟩

= ∑_{X∈Max(P^{σ})}(−1)^{n−1}μ_{σ}(ˆ0, X) = (−1)^{n−1}μ_{σ}(P^{σ}).

This is the character of the action of 𝔖_{n} on H^{W} (P). If we combine this with (12), we get Ψ_{n,k}(σ) = (−1)^{n−d} ⟨β^{P} , σ⟩ and hence the following result.

Theorem 9. Ψ_{n,k} is the product of the sign character of 𝔖_{n} and the character afforded by the action of 𝔖_{n} on the Whitney homology of Π_{n,k}.

Note that (−1)^{n−d} = −1 only if n is even and d is odd. If 4|n, then μ(n/d) = 0. Therefore, Ψ_{n,k} is the homology character, and is self-conjugate unless n ≡ 2 (mod 4). (This is an extension of [13, Lemma 7.3].)

4 Ψ_{n,k} is an Induced Character

Now we know that Ψ_{n,k} is a character, and it is zero for elements of 𝔖_{n} that are not conjugate to any elements of ℭ_{n}. So a good direction to go now is to prove that Ψ_{n,k} can be represented as a sum of induced characters χ ↑_{ℭ_{n}}^{𝔖_{n}}, where χ is an irreducible character of ℭ_{n}. By [13, Lemma 7.2], Ψ_{n,0} is simply the value of the induced character ψ ↑_{ℭ_{n}}^{𝔖_{n}}, where ψ evaluated at a given n-cycle that generates ℭ_{n} is e^{2πi/n}. We now extend this result to Ψ_{n,k} for k > 0.

Let σ be an n-cycle of 𝔖_{n} in ℭ_{n}. Let ζ = e^{2πi/n} and for s = 1, ..., n, let χ_{s,n} be the character of ℭ_{n} such that χ_{s,n}(σ) = ζ^{s}. Then it is known that the χ_{s,n} are the irreducible characters of ℭ_{n}. Let χ_{s,n}^{⋆} be the induced character χ_{s,n} ↑_{ℭ_{n}}^{𝔖_{n}}. If gcd(d, n) = gcd(s, n), then it can be verified that χ_{s,n}^{⋆} = χ_{d,n}^{⋆}, so the goal in this section and the next is to prove that

Ψ_{n,k} = ∑_{s|n} a_{n,k}^{s}χ_{s,n}^{⋆}  (15)

for non-negative integers a_{n,k}^{s}. In this section, the main theorem shows that Ψ_{n,k} is an induced character. In the next section, we calculate all the coefficients. It is well-known that if ζ is a primitive n-th root of unity, then

∑_{i=1}^{n} ζ^{ir} = \begin{cases}n & if n|r; \\ 0 & otherwise. \end{cases}  (16)

First, we prove the following lemma.

Lemma 10. The χ_{d,n}^{⋆} for d|n are linearly independent.

Proof. For d|n, let λ_{d,n} = ∑_{i=1}^{n/d} χ_{di,n}. Then λ_{d,n} = 1 ↑_{ℭ_{d}}^{ℭ_{n}}, because if we evaluate it at some σ^{r}, then we get (16), so λ_{d,n}(σ^{r}) = 0 unless \frac{n}{d}|r, in which case it is \frac{n}{d}. Let

ν_{d,n} = ∑_{s|d} μ(d/s)sλ_{s,n}.

Given r, let g = gcd(n, r). Then λ_{s,n}(σ^{r}) = 0 unless \frac{n}{s}|r, or equivalently, \frac{n}{g}|s, in which case it is \frac{n}{s}. So

ν_{d,n}(σ^{r}) = ∑_{s|d} μ(d/s)sλ_{s,n}(σ^{r}) = ∑_{s|d, \frac{n}{g} |s} μ(d/s)sλ_{s,n}(σ^{r})

= n ∑_{s|d, \frac{n}{g} |s} μ(d/s) = n ∑_{s| \frac{dg}{n}} μ(s) = \begin{cases}n & if g = \frac{n}{d}; \\ 0 & otherwise, \end{cases}

since for any positive integer m, ∑_{d|m} μ(d) = δ_{1,m}. Inducing this up to 𝔖_{n},

ν_{d,n}^{⋆}(σ^{r}) = ν_{d,n} ↑_{ℭ_{n}}^{𝔖_{n}} (σ^{r}) = \begin{cases}\frac{n!ϕ(d)}{|ccl_{𝔖n}(σ^{r})|} & if gcd(r, n) = \frac{n}{d} (or equivalently, σ^{r} ∼ σ^{n/d}); \\ 0 & otherwise, \end{cases}

which, if not zero, is the number of τ ∈ 𝔖_{n} such that τσ^{r}τ^{−1} ∈ ℭ_{n}. Here, ccl_{𝔖_{n}}(σ) is the conjugacy class of σ in 𝔖_{n}. From the ν_{d,n}^{⋆}, we can get the standard basis of class functions that are zero in all classes that do not contain an element of ℭ_{n}. Since each ν_{d,n}^{⋆} can be expressed as a linear combination of the χ_{d,n}^{⋆}, and vice-versa, and the ν_{d,n}^{⋆} are linearly independent for d|n, we can conclude that the χ_{d,n}^{⋆} are linearly independent too, since there are the same number of χ_{d,n}^{⋆} as there are ν_{d,n}^{⋆}.

Thus the χ_{d,n}^{∗} for d|n are a basis for the induced characters from ℭ_{n} up to 𝔖_{n}. By Theorem 3 and the last part of the proof of Lemma 10, Ψ_{n,k} can be expressed as a linear combination, as in (15). We now need to show that the a_{n,k}^{s} are non-negative integers by finding formulas for them. We first determine a_{n,k}^{n}, which can be found by simply using inner products. Then we find the a_{n,k}^{s} in the next section.

Lemma 11. a_{n,k}^{n} = \frac{1}{n} ∑_{d|n} μ (\frac{n}{d}) \binom{(k+1)d−1}{d−1} for n ≥ 1.

Proof. For n > 1, we show that a_{n,k}^{n} = ⟨Ψ_{n,k}, 1_{𝔖_{n}}⟩_{𝔖_{n}}. Using Frobenius Reciprocity [12, Th. 1.12.6],

⟨Ψ_{n,k}, 1_{𝔖_{n}}⟩_{𝔖_{n}} = ∑_{d|n} a_{n,k}^{d} ⟨χ_{d,n}^{⋆}, 1_{𝔖_{n}}⟩_{𝔖_{n}} = ∑_{d|n} a_{n,k}^{d} ⟨χ_{d,n}, 1_{ℭ_{n}}⟩_{ℭ_{n}} = a_{n,k}^{n}.

The last equality is by orthogonality of irreducible characters. Thus the only time 1_{𝔖_{n}} appears in the sum (15) is when d = n. So for an n-cycle σ,

a_{n,k}^{n} = ⟨Ψ_{n,k}, 1_{𝔖_{n}}⟩ = \frac{1}{n!} ∑_{τ∈𝔖_{n}} Ψ_{n,k}(τ)
= \frac{1}{n!} ∑_{d|n} |ccl_{𝔖_{n}}(σ^{d})| Ψ_{n,k}(σ^{d})  (Theorem 3)

= \frac{1}{n!} ∑_{d|n} (\frac{n!}{(n/d)^{d}d!}) μ (\frac{n}{d}) (\frac{n}{d})^{d−1} \binom{(k + 1)d − 1}{d − 1}(d − 1)! (Theorem 4)

= \frac{1}{n} ∑_{d|n} μ (\frac{n}{d}) \binom{(k + 1)d − 1}{d − 1}.

For n = 1, it is clear that Ψ_{1,k} ≡ 1 and a_{1,k}^{1} = 1.

Since Ψ_{n,k} is a character of 𝔖_{n}, it follows by the first assertion in the proof of Lemma 11 that a_{n,k}^{n} is a non-negative integer. For d|n, let ℭ_{n/d} = ⟨σ^{d}⟩, and let χ_{s, \frac{n}{d}} for s ≤ \frac{n}{d} be an irreducible character for ℭ_{n/d} such that χ_{s, \frac{n}{d}} (σ^{d}) = ζ^{sd} for 1 ≤ s ≤ \frac{n}{d}. Now let χ_{d,n}^{reg} = χ_{1, \frac{n}{d}} ↑_{ℭ_{n/d}}^{𝔖_{n}}. Notice that χ_{n,n}^{reg} is the regular character for 𝔖_{n} and χ_{1,n}^{reg} = χ_{1,n}^{⋆}. Also, note that the χ_{d,n}^{reg} need not be linearly independent. Now we use the next lemma to prove the main result of this section, that Ψ_{n,k} is an induced character from ℭ_{n}, because each χ_{d,n}^{reg} is.

Lemma 12. Let σ be an n-cycle in 𝔖_{n}. Then we have the following identity:

\frac{1}{d}χ_{d,n}^{reg}(σ^{r}) = \begin{cases}χ_{1,n}^{⋆}(σ^{r}) & if d|r \\ 0 & otherwise. \end{cases}

Proof. We know that \frac{1}{d}χ_{d,n}^{reg}(σ^{r}) = \frac{1}{d}χ_{1, \frac{n}{d}} ↑_{ℭ_{n/d}}^{𝔖_{n}} (σ^{r}) and χ_{1,n}^{⋆} = χ_{1,n} ↑_{ℭ_{n}}^{𝔖_{n}}. Since induction of representations is transitive, it is enough to show that

\frac{1}{d}χ_{1, \frac{n}{d}} ↑_{ℭ_{n/d}}^{ℭ_{n}} (σ^{r}) = \begin{cases}χ_{1,n}(σ^{r}) & if d|r \\ 0 & otherwise. \end{cases}

d|r if and only if σ^{r} ∈ ℭ_{n/d}, and then both sides are ζ^{r}. We induce both sides up to 𝔖_{n}, and we are done.

Theorem 13. Ψ_{n,k} = ∑_{d|n} a_{d,k}^{d}χ_{d,n}^{reg}

Proof. Let ℌ_{k,s} = \binom{(k+1)s−1}{s−1}. We know that

Ψ_{n,k}(τ) = \begin{cases}μ(d)(\frac{n}{d})^{d−1}(d − 1)!ℌ_{k,d} & if τ is a product of d cycles \\ & of length n/d for some d|n; \\ 0 & otherwise. \end{cases}

Again assume that d|n and σ is an n-cycle such that ℭ_{n} = ⟨σ^{d}⟩.

∑_{r|n} a_{r,k}^{r}χ_{r,n}^{reg} (σ^{d}) = ∑_{r|n} (\frac{1}{r} ∑_{s|r} μ (\frac{r}{s}) ℌ_{k,s}) χ_{r,n}^{reg} (σ^{d})  (Lemma 11)

= ∑_{r|n} \frac{1}{r}χ_{r,n}^{reg} (σ^{d}) ∑_{s|r} μ (\frac{r}{s}) ℌ_{k,s} = χ_{1,n}^{⋆}(σ^{d}) ∑_{r|d} ∑_{s|r} μ (\frac{r}{s}) ℌ_{k,s}

(Lemma 12)

= χ_{1,n}^{⋆}(σ^{d}) ∑_{s|d} ℌ_{k,s} ∑_{r|d,s|r} μ (\frac{r}{s}) = χ_{1,n}^{⋆}(σ^{d}) ∑_{s|d} ℌ_{k,s}δ_{d,s}  (17)
= μ(n/d)(n/d)^{d−1}(d − 1)!ℌ_{k,d}  (18)

The second equality of (17) holds because given s,

∑_{r|d,s|r} μ (\frac{r}{s}) = ∑_{q| \frac{d}{s}} μ(q) = δ_{d,s}.

For equation (18), [13, Lemma 7.2] proves that χ_{1,n}^{⋆}(σ^{d}) = Ψ_{n,0}(σ^{d}). Thus we have proved that the right-hand side is equal to a value that we know is Ψ_{n,k}.

Given a real number x, let ⟨x⟩ be the nearest integer to x. Recall that the irreducible characters of 𝔖_{n} are the χ^{λ} for each partition λ of n, and f^{λ} is the degree of χ^{λ}. We now have a way to decompose Ψ_{p,k} into irreducible characters of 𝔖_{p} for any odd prime p. The following corollary is an extension of a result by Stanley.

Corollary 14. Given an odd prime p, and a partition λ of p,

⟨Ψ_{p,k}, χ^{λ}⟩_{𝔖_{n}} = a_{p,k}^{p}f^{λ} + ⟨f^{λ}/p⟩ .

Proof. By Theorem 13,

Ψ_{p,k} = a_{1,k}^{1}χ_{1,p}^{∗} + a_{p,k}^{p}χ_{p,p}^{reg}.

Therefore, since a_{1,k}^{1} = 1 for all k, we get

⟨Ψ_{p,k}, χ^{λ}⟩_{𝔖_{n}} = a_{p,k}^{p} ⟨χ_{p,p}^{reg}, χ^{λ}⟩ + ⟨χ_{1,p}^{∗}, χ^{λ}⟩ = a_{p,k}^{p}f^{λ} + ⟨f^{λ}/p⟩ .

The first summand is well-known about the regular character of 𝔖_{n} (For example, see Theorem 1.10.1 of [12]). The second summand is by Corollary 7.4 of [13].

5 The Coefficients a_{n,k}^{s}

By Theorem 13, Ψ_{n,k} is an induced character from ℭ_{n} up to 𝔖_{n}. For the sake of completeness, we now determine the coefficients a_{n,k}^{s}. This also makes it more clear how to decompose Ψ_{n,k} into irreducibles if n is not prime, since there are references that have the decomposition of induced characters from ℭ_{n}. See for Example [15, §3], where it is done in terms of standard Young tableaux. By the next lemma, each a_{n,k}^{s} is a sum of non-negative integers a_{d,k}^{d} for each d such that χ_{d,n}^{⋆} appears in the expression of χ_{s,n}^{reg}. All we need to do now is determine what a_{n,k}^{s} is for s properly dividing n.

Lemma 15. For d|n, χ_{d,n}^{reg} = ∑_{i=0}^{d−1} χ_{i \frac{n}{d} +1,n}^{⋆}.

Sketch of Proof. It is enough to show that χ_{1, \frac{n}{d}} ↑_{ℭ_{n/d}}^{ℭ_{n}}= ∑_{i=0}^{d−1} χ_{i \frac{n}{d} +1,n}. Just evaluate both sides at σ^{r}, and then induce up to 𝔖_{n}.

This shows that for a given k, a_{n,k}^{s} can be expressed in terms of the numbers a_{d,k}^{d}. So let A_{n}^{s} be the infinite sequence {a_{n,k}^{s}}_{k=0}^{∞}. Since the expression of a_{n,k}^{s} in terms of the numbers a_{d,k}^{d} is independent of k, this is a way to write these numbers so that we do not have to write k all the time. We need to find a formula for these sequences, now that we know the A_{d}^{d} sequences for d|n. Define the sum of two sequences and scalar multiplication of a sequence the usual way. By theorem 13, a_{d,k}^{d} is the coefficient of χ_{d,n}^{reg} in Ψ_{n,k}, so by Lemma 15, it appears in the coefficient of χ_{(i−1) \frac{n}{d} +1,n}^{⋆} for i = 1, 2, ..., d, given k. Also, if s = gcd(g, n) for some g, then χ_{s,n}^{⋆} = χ_{g,n}^{⋆}, so each A_{n}^{s} sequence can be written as a non-negative integer combination of the A_{d}^{d} sequences for which a_{d,k}^{d} appears in the coefficient of χ_{s,n}^{⋆}, and that is for each d such that there exists an r ≡ 1 (mod \frac{n}{d}) with gcd(r, n) = s. In this case, gcd(s, \frac{n}{d}) = gcd(r, n, \frac{n}{d}) = 1 and s|d. Our goal is to find how many of these r exist up to modulo n, and that will be the coefficient of A_{d}^{d} in A_{n}^{s}. First we prove a lemma from number theory that we will use.

Lemma 16. Given positive integers a, b, t such that gcd(a, b) = 1, there exists an integer u such that 0 ≤ u < t and gcd(ua + b, t) = 1.

Proof. We form an increasing sequence a_{0}, a_{1}, ..., a_{t} of integers that are pairwise relatively prime, or coprime. Let a_{0} = a and a_{1} = b. For m ≥ 1, let

a_{m+1} = a_{m} + a_{0}a_{1}...a_{m−1}.

We prove that these numbers are coprime by induction. First, it is given that a_{0} and a_{1} are relatively prime. Now assuming that a_{0}, ..., a_{m} are coprime, we use the Euclidean algorithm to prove that a_{m+1} is relatively prime to all a_{i} for i = 0, 1, ..., m. Now gcd(a_{m}, a_{m+1}) = gcd(a_{m}, a_{0}...a_{m−1}), and for i < m,

gcd(a_{i}, a_{m+1}) = gcd(a_{i}, a_{m}).

By hypothesis, both are 1, so the numbers in the sequence are all coprime. To prove that the a_{m} are of the form u′a+b for some integer u′ and m ≥ 1, we know that it holds for m = 1; it is 0a+b. Now assume that it holds for some m ≥ 1 and prove it for m+1. We need to show that a|(a_{m+1} − b). We know that a_{m+1} − b = a_{m} − b + a_{0}...a_{m−1}. We also know that a divides a_{m} − b by hypothesis, and a divides a_{0}...a_{m−1} because a = a_{0}. This proves that a_{1}, ..., a_{t} are t coprime numbers, all congruent to b modulo a, and therefore there must be at least one of these numbers that is relatively prime to t. Suppose a_{i} is one such number. Let u′ = \frac{a_{i}−b}{a}. In other words, a_{i} = u′a + b. Then there exists a unique expression u′ = u′′t + u such that 0 ≤ u < t. It follows that gcd(ua + b, t) = 1.

The number of r up to modulo n such that r ≡ 0 (mod s) is n/s, and the number of such r with gcd(r, n) = s is ϕ(n/s). Now we find how many of these r have r ≡ 1 (mod \frac{n}{d}). Let t_{1} and t_{2} be units in the ring ℤ/(\frac{n}{d}), t_{1} chosen so that there definitely exists an r among these numbers such that r ≡ t_{1} (mod \frac{n}{d}) (t_{1} can be s, for example). Suppose that r_{1}, ..., r_{w} are the numbers mod n such that

r_{i} ≡ t (mod \frac{n}{d}) and gcd(r_{i}, n) = s.  (19)

for t = t_{1}. In ℤ/(n), t_{2} is not necessarily a unit, but by Lemma 16, there exists a u such that gcd(t_{2} + u(\frac{n}{d}), n) = 1. Then (t_{2} + u(\frac{n}{d}))r_{1}, ..., (t_{2} + u(\frac{n}{d}))r_{w} are all congruent to t_{1}t_{2} mod n/d and distinct mod n, since the r_{i} were all multiplied by a unit of ℤ/(n). This proves that there are at least w of them. To prove there are exactly w, consider t_{2}^{−1} in ℤ/(\frac{n}{d}) and suppose there are w′ numbers, w′ ≥ w. By Lemma 16, there exists a u′ such that gcd(t_{2}^{−1} + u′(\frac{n}{d}), n) = 1. Then the numbers (t_{2}^{−1} + u′(\frac{n}{d}))(t_{2} + u(\frac{n}{d}))r_{i} are all congruent to t_{1} mod n/d, and there are at least w′ such numbers. Since there are w of them, w = w′. So we can let t_{2} = t_{1}^{−1}, and then we have w numbers that are congruent to 1 mod n/d. Thus for each unit t mod n/d, there are w numbers up to mod n that satisfy (19), so one out of every ϕ(n/d) of the numbers r is congruent to 1 mod n/d. Therefore,

A_{n}^{s} = ∑_{d} \frac{ϕ(n/s)}{ϕ(n/d)}A_{d}^{d},  (20)

summing over all d such that a_{d,k}^{d} appears in the coefficient of χ_{s,n}^{⋆}.

Example. Suppose n = 72 and s = 3. Then the values of d that would have nonzero coefficients in (20) are d = 9, 18, 36, 72. We do d = 9 in detail. Let t_{1} = 3 in ℤ/(8). The values of r such that gcd(r, 72) = 3 are 3, 15, 21, 33, 39, 51, 57, 69, and those r such that r ≡ 3 (mod 8) are 3 and 51, so w = 2. Then t_{1}^{−1} ≡ 3 (mod 8), but 3 is not a unit in ℤ/(72). However, by adding 8 (u = 1), we get 11, which is a unit. So multiply 3 and 51 by 11 to get 33 and 57, respectively, mod 72. These are the numbers r_{i} described in (19) for t = 1. Therefore, the coefficient of A_{9}^{9} in A_{72}^{3} is 2 and ϕ(n/s) = ϕ(24) = 8 and ϕ(n/d) = ϕ(8) = 4, which verifies (20) here. The expression for A_{72}^{3} in terms of the A_{d}^{d} is

A_{72}^{3} = 2A_{9}^{9} + 4A_{18}^{18} + 8A_{36}^{36} + 8A_{72}^{72}.

There is another equivalent condition on the d that can be used. With this, we will have a quicker way of obtaining which values of d have nonzero terms in the sum. We have the following lemma.

Lemma 17. Given integers s and d that divide n, there exists an r ≡ 1 (mod d) such that gcd(r, n) = s if and only if gcd(s, d) = 1.

Proof. To prove (⟹), if such an r exists, then since s|r, gcd(s, d) = 1.

To prove (⟸), if gcd(s, d) = 1, then it follows that s|\frac{n}{d}, so it’s enough to show there exists an r ≡ 1 (mod d) such that gcd(r, \frac{n}{d}) = s. There exists a t such that 0 < t < d and st ≡ 1 (mod d). This equation also holds if t is replaced by id + t for i = 0, 1, ..., \frac{n}{d} − 1. By Lemma 16, gcd(id + t, \frac{n}{d}) = 1 for at least one of these i, and then we let r = s(id + t).

Now in order to find which d have nonzero summands, we only need to find those divisors of n that are relatively prime to s, and then divide n by them. Thus we have the result.

Theorem 18. For s|n and some integer k ≥ 0,

a_{n,k}^{s} = ∑_{\begin{matrix}d|n \\ gcd(s, \frac{n}{d})=1 \end{matrix}} \frac{ϕ(n/s)}{ϕ(n/d)}a_{d,k}^{d} = ∑_{d} \frac{ϕ(n/s)}{dϕ(n/d)} ∑_{t|d} μ (\frac{d}{t}) \binom{(k + 1)t − 1}{t − 1}.

6 Another Proof that Ψ_{n,k} is a Character

It is also possible to prove that Ψ_{n,k} is a character of 𝔖_{n} without using homology of posets, as we did in section 3. In section 4, the only time the homology result was used was when it was found that Ψ_{n,k} is a character. From this, it was concluded that the a_{d,k}^{d} are all non-negative integers because of Lemma 11. By Theorem 13,

Ψ_{n,k} = ∑_{d|n} a_{d,k}^{d}χ_{d,n}^{reg}.

If we can show that a_{n,k}^{n} is a non-negative integer for each n, then we will have shown that Ψ_{n,k} is a sum of characters of 𝔖_{n}, and therefore, a character itself. By Lemma 11,

a_{n,k}^{n} = \frac{1}{n} ∑_{d|n} μ (\frac{n}{d}) \binom{(k + 1)d − 1}{d − 1}.  (21)

Lemma 19. For positive integers n and r, and k = r − 1, a_{n,k}^{n} is an integer.

Proof. Let p be a prime divisor of n, and let s be the positive integer such that p^{s} ∥ n. Then

na_{n,k}^{n} = ∑_{d| \frac{n}{p^{s}}} (μ (\frac{n}{p^{s−1}d}) \binom{p^{s−1}rd − 1}{p^{s−1}d − 1} + μ (\frac{n}{p^{s}d}) \binom{p^{s}rd − 1}{p^{s}d − 1})

= ∑_{d| \frac{n}{p^{s}}} μ (\frac{n}{p^{s}d}) (\binom{p^{s}rd − 1}{p^{s}d − 1} − \binom{p^{s−1}rd − 1}{p^{s−1}d − 1}) ,

since the other summands are definitely zero. We show that each summand is congruent to 0 mod p^{s}.

\binom{p^{s}rd − 1}{p^{s}d − 1} = \frac{(p^{s}rd − 1)(p^{s}rd − 2) ⋯ (p^{s}(r − 1)d + 1)}{(p^{s}d − 1)(p^{s}d − 2) ⋯ 3 · 2 · 1}

= A\frac{(p^{s}rd − p)(p^{s}rd − 2p) ⋯ (p^{s}(r − 1)d + p)}{(p^{s}d − p)(p^{s}d − 2p) ⋯ 3p · 2p · p}

= A\frac{(p^{s−1}rd − 1)(p^{s−1}rd − 2) ⋯ (p^{s−1}(r − 1)d + 1)}{(p^{s−1}d − 1)!} = A\binom{p^{s−1}rd − 1}{p^{s−1}d − 1}

Here, A is a product of fractions of the form \frac{p^{s}rd−a}{p^{s}d−a} for all a relatively prime to p. Since the numerator and denominator of each of these fractions are units in ℤ/(p^{s}), all the fractions are equivalent to 1 mod p^{s}. Thus A ≡ 1 (mod p^{s}). This proves that

\binom{p^{s}rd − 1}{p^{s}d − 1} − \binom{p^{s−1}rd − 1}{p^{s−1}d − 1} ≡ 0 (mod p^{s}),

and therefore na_{n,k}^{n} ≡ 0 (mod p^{s}) for each prime divisor p of n. Therefore, by the Chinese Remainder Theorem, na_{n,k}^{n} ≡ 0 (mod n), and this proves the lemma.

Lemma 20. For n ≥ 2, a_{n,0}^{n} = 0, and for k ≥ 1, a_{n,k}^{n} > 0.

Proof. We know the case k = 0. Using [13, Lemma 7.2], a_{n,0}^{1} = 1 and a_{n,0}^{d} = 0 for d > 1. For k ≥ 1, let r = k + 1. Given a prime divisor p of n, let q_{p} = n/p. It is well-known that summing over prime divisors of n, ∑_{p|n} \frac{1}{p^{2}} < 1 (This inequality also holds when summed over all primes). So we will prove that

\binom{nr − 1}{n − 1} > p^{2}\binom{q_{p}r − 1}{q_{p} − 1}.  (22)

If we let (a)_{b} = b!\binom{a}{b} for integers a and b, then this is equivalent to

(nr − 1)_{n−1} > p^{2}(n − 1)_{n−q_{p}}(q_{p}r − 1)_{q_{p}−1}.

Since pq_{p} = n, it follows that p^{2}(q_{p}r − 1)(q_{p}r − 2) < (nr − 1)(nr − 2). Thus it is enough to show that

(nr − 3)_{n−3} > (n − 1)_{n−q_{p}}(q_{p}r − 3)_{q_{p}−3}.

The left side is equal to (nr − 3)_{q_{p}−3}(nr − q_{p})_{n−q_{p}}. It is clear that nr − 3 > q_{p}r − 3 and nr−q_{p} > n−1 (since r > 1). Thus (22) is true, so for each prime p|n, \frac{1}{p^{2}} \binom{nr−1}{n−1} > \binom{q_{p}r−1}{q_{p}−1}. Therefore,

\binom{nr − 1}{n − 1} > ( ∑_{\begin{matrix}p|n \\ p prime \end{matrix}} \frac{1}{p^{2}} ) \binom{nr − 1}{n − 1} > ∑_{\begin{matrix}p|n \\ p prime \end{matrix}} \binom{q_{p}r − 1}{q_{p} − 1}

This inequality holds for each integer n. In (21), if one term ℌ_{k,d} (cf. proof of Theorem 13) is subtracted, then ℌ_{k,pd} is added for some prime p, which is a lot larger than ℌ_{k,d} by (22). Also, the coefficient of ℌ_{k,n} is always 1. Therefore, a_{n,k}^{n} > 0.

Thus we have proved the following, which by Theorem 13 proves that Ψ_{n,k} is a character of 𝔖_{n}

Theorem 21. a_{n,k}^{n} is a non-negative integer for all n ≥ 2, and it is zero only if k = 0.

Acknowledgments

I would like to thank my advisor Don Higman and Phil Hanlon for helpful discussions and for encouraging me to send this paper for publication. I would also like to thank the anonymous referee for his comments that helped me improve this paper and make it more understandable.

References

[1] C. A. Athanasiadis, Characteristic polynomials of subspace arrangements and finite fields, Adv. in Math. 122 (1996), 193–233.

[2] K. Baclawski, Whitney numbers of geometric lattices, Adv. in Math. 16 (1975), 125–138.

[3] K. Baclawski and A. Björner, Fixed points in partially ordered sets, Adv. in Math. 31 (1979), 263–287.

[4] A. Björner, On the homology of geometric lattices, Algebra Universalis 14 (1982), 107–128.

[5] H. H. Crapo, The Möbius function of a lattice, J. Combin. Theory 1 (1966), 126– 131.

[6] J. Folkman, The homology groups of a lattice, J. Math. Mech. 15 (1966), 631–636.

[7] R. Gill, A Generalization of the Partition Lattice: Combinatorial Properties and the Action of the Symmetric Group, Ph.D. thesis, University of Michigan, 1998.

[8] R. Gill, The number of elements in a generalized partition semilattice, Discrete Math. 186 (1998), 125–134.

[9] P. Hanlon, The fixed point partition lattices, Pacific J. Math. 96 (1981), 319–341.

[10] J. Kerr, A basis for the top homology of a generalized partition lattice, J. Algebraic Combin. 9 (1999), 47–60.

[11] G.-C. Rota, On the foundations of combinatorial theory I. Theory of Möbius Functions, Z. Wahrscheinlichkeitstheorie 2 (1964), 340–368.

[12] B. Sagan, The Symmetric Group, Wadsworth and Brooks/Cole, Belmont, CA, 1991.

[13] R. Stanley, Some aspects of groups acting on finite posets, J. Combin. Theory Ser. A 32 (1982), 132–161.

[14] R. Stanley, Hyperplane arrangements, interval orders, and trees, Proc. Nat. Acad. Sci. U.S.A. 93 (1996), 2620–2625.

[15] J. R. Stembridge, On the eigenvalues of representations of reflection groups and wreath products, Pacific J. Math. 140 (1989), 353–396.

[16] M. L. Wachs, On the (co)homology of the partition lattice and the Free Lie Algebra, Discrete Math. 193 (1998), 287–319.

[17] M. L. Wachs and J. W. Walker, On geometric semilattices, Order 2 (1986), 367– 385.

[18] G. M. Ziegler, Matroid shellability, β-systems, and affine hyperplane arrangements, J. Algebraic Combin. 3 (1992), 283–300.