\documentclass[12pt]{article}
\topmargin=-0.2in
\textheight=8.6in
\oddsidemargin=0in
\evensidemargin=0in
\setlength{\textwidth}{6.1in}
\usepackage{amssymb,amsmath,amsthm,amsfonts,latexsym}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem*{example}{Example}
\def\reg{{\rm reg}}
\newcommand\beq{\begin{equation}}
\newcommand\bth{\begin{theorem}}
\newcommand\ethm{\end{theorem}}
\newcommand\bpf{\begin{proof}}
\newcommand\epf{\end{proof}}
\newcommand\poly{polynomial}
\newcommand\sri{sign-reversing involution}
\newcommand\corr{correspond}
\newcommand\chr{character}
\newcommand\arb{arbitrary}
\newcommand\st{such that\ }
\newcommand\wlg{without loss of generality}
\newcommand\resp{respectively}
\newcommand\sgn{{\rm sgn}}
\newcommand\wrt{with respect to\ }
\newcommand\ito{in terms of\ }
\newcommand\ifff{if and only if\ }
\newcommand\FLA{Free Lie Algebra}
\newcommand\pn{partition}
\newcommand\hpl{hyperplane}
\newcommand\arr{arrangement}
\newcommand\hgy{homology}
\newcommand\maxel{maximal element}
\newcommand\maxint{maximal interval}
\newcommand\fcn{function}
\newcommand\qhb{\quad\hbox}
\newcommand\Sn{\mathfrak{S}_n}
\newcommand\RR{\mathbb{R}}
\begin{document}
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 7 (2000), \#R23\hfill}
\thispagestyle{empty}
\title{The Action of the Symmetric Group\\
on a Generalized Partition Semilattice}
\author{Robert Gill\\
Department of Mathematics and Statistics\\
University of Minnesota Duluth\\
10 University Drive\\
Duluth, MN 55812\\
\texttt{rgill@d.umn.edu}\\[0.2in]
}
\date{Submitted: February 7, 1998; Accepted: April 21, 2000\\[0.5in]
\begin{flushleft}
{Key Words}: hyperplane arrangement, M\"obius function,
homology, induced character, cyclic group\\[1em]
{AMS Subject Classi{f}ication (1991)}: Primary 06A07;
Secondary 05E25, 52B30, 20C30, 11A05
\end{flushleft}
}
\maketitle
\begin{abstract}
Given an integer $n\geq 2$, and a non-negative integer $k$, consider all af{f}ine hyperplanes in $\mathbb{R}^n$ of the form $x_i=x_j+r$ for $i,j\in[n]$ and a non-negative integer $r\leq k$. Let $\Pi_{n,k}$ be the poset whose elements are all nonempty intersections of these af{f}ine hyperplanes, ordered by reverse inclusion. It is noted that $\Pi_{n,0}$ is isomorphic to the well-known partition lattice $\Pi_n$, and in this paper, we extend some of the results of $\Pi_n$ by Hanlon and Stanley to $\Pi_{n,k}$.
Just as there is an action of the symmetric group $\mathfrak{S}_n$ on $\Pi_n$, there is also an action on $\Pi_{n,k}$ which permutes the coordinates of each element. We consider the subposet $\Pi_{n,k}^\sigma$ of elements that are {f}ixed by some $\sigma\in\mathfrak{S}_n$, and find its M\"obius function $\mu_\sigma$, using the characteristic polynomial. This generalizes what Hanlon did in the case $k=0$. It then follows that $(-1)^{n-1}\mu_\sigma(\Pi_{n,k}^\sigma)$, as a function of $\sigma$, is the character of the action of $\mathfrak{S}_n$ on the homology of $\Pi_{n,k}$.
Let $\Psi_{n,k}$ be this character times the sign character. For $\mathfrak{C}_n$, the cyclic group generated by an $n$-cycle $\sigma$ of $\mathfrak{S}_n$, we take its irreducible characters and induce them up to $\mathfrak{S}_n$. Stanley showed that $\Psi_{n,0}$ is just the induced character $\chi\uparrow_{\mathfrak{C}_n}^{\mathfrak{S}_n}$ where $\chi(\sigma)=e^{2\pi 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 $\Psi_{n,k}$, and we {f}ind explicit formulas. In addition, we show another way to prove that $\Psi_{n,k}$ is a character, without using homology, by proving that the derived coefficients of certain induced characters of $\mathfrak{S}_n$ are non-negative integers.
\end{abstract}
\section{Introduction}\label{S:intro}
Given a finite partially ordered set $P$, let $\leq$ denote the partial order, and assume that $P$ has a unique minimal element $\hat 0$. An {\it automorphism} $\sigma$ on $P$ is a permutation of the elements of $P$ such that if $x\leq y$, then $\sigma(x)\leq\sigma(y)$. Let $P^\sigma$ be the subposet of $P$ that consists of the elements that are fixed by $\sigma$. If $P$ is a lattice, then so is $P^\sigma$ (For a proof, see page~319 of~\cite{H81}).
Now we look at one particular lattice. For some positive integer $n$, if we let $\Pi_n$ denote the set of all partitions of the set $[n]=\{1,2,...,n\}$, ordered by refinement, then $\Pi_n$ is a lattice. There has been a lot of work on $\Pi_n$, and the action of the symmetric group $\mathfrak{S}_n$ on it. An element of $\mathfrak{S}_n$ permutes the elements of ${[n]=\{1,2,...,n\}}$, and therefore acts as an automorphism on $\Pi_n$. Given $\sigma\in\mathfrak{S}_n$, let $\Pi_n^\sigma$ denote the subposet of $\Pi_n$ of elements that are fixed by $\sigma$.
The {\it M\"obius function} $\mu$ is de{f}ined on intervals ${[x,y]=\{z\colon\ x\leq z\leq y\}}$ of a poset $P$ such that $\mu(x,x)=1$ for all $x\in P$ and for $x0$. For an af{f}ine subspace $X\in\Pi_{n,k}$, its dimension $\dim(X)$ is equal to the dimension of the linear translation of $X$, the set $\{v-x\colon\ v\in X\}$ for a particular $x\in X$. So $X$ is maximal if and only if ${\dim(X)=1}$.
First, the {\it characteristic polynomial} of a poset $P$ of affine subspaces of $\mathbb{R}^n$ is given by
\[
\lambda_P(t)=\sum_{X\in P}{\mu (\ensuremath{\hat{0}},X)t^{\dim(X)}}.
\]
In section~\ref{S:mu}, we let $P=\Pi_{n,k}$ and consider $P^\sigma$, the subposet of $P$ {f}ixed by some $\sigma\in\mathfrak{S}_n$. We use the characteristic polynomial of~$P$ and the paper by Hanlon~\cite{H81} to show that the M\"obius function of this subposet, $\mu_\sigma(P^\sigma)$, is as stated in~\eqref{E:mobfn}. Then in section~\ref{S:hgy}, we use a result from Stanley's paper~\cite{St82} to show that the character of the representation of $\mathfrak{S}_n$ acting on the top homology of $P$ is $(-1)^{n-1}\mu_\sigma(P^\sigma)$.
Let $\Psi_{n,k}$ be this character times the sign character, so $\Psi_{n,k}=(-1)^{d-1}\mu_\sigma(P)^\sigma)$. In sections~\ref{S:ind} and~\ref{S:asnk}, we show that $\Psi_{n,k}$ can be expressed as a non-negative integer combination of the characters of $\mathfrak{S}_n$ that are induced from irreducible characters of $\mathfrak{C}_n$, as in~\eqref{E:expr}. First, we show that the induced characters in this sum are a basis for all induced characters from $\mathfrak{C}_n$. Then the main result in section~\ref{S:ind} is that $\Psi_{n,k}$ is a sum of induced characters from $\mathfrak{C}_d$ for each $d|n$. In section~\ref{S:asnk}, we {f}ind an explicit expression for $\Psi_{n,k}$ \ito these induced \chr s, also proving some concepts from number theory which we use along the way.
In the last section, we prove separately that the coef{f}icients are non-negative integers, using the formula derived in Lemma~\ref{L:iprod}, which gives us a way to prove that $\Psi_{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~$\Pi_{n,k}$. For example, Christos Athanasiadis in his Ph.D. thesis \cite{A96} used the M\"obius Inversion Formula to {f}ind the characteristic polynomial of numerous af{f}ine hyperplane arrangements, including this one \cite[Th.~5.1]{A96}. Also, Julie Kerr in her Ph.D. thesis \cite{K96} discusses the poset obtained by adding a unique maximal element to $\Pi_{n,k}$. Although it becomes a lattice, its characteristic polynomial does not in general factor linearly as it does for $\Pi_{n,k}$. But its top-dimensional homology is isomorphic to a direct sum of copies of the algebra $\mathbb{C}\mathfrak{S}_n$, known as the {\it regular representation} of $\mathfrak{S}_n$. There is also additional work on the poset $\Pi_{n,k}$ in~\cite{RG96}.
\section{The M\"obius Function of $\Pi_{n,k}^\sigma$}\label{S:mu}
We first state \cite[Th.~5.1]{A96}. This generalizes the \chr istic \poly\ of the well-known \pn\ lattice, which is the case ${k=0}$.
\bigskip
\begin{theorem}\label{T:cpoly}
The \chr istic \poly\ of $\Pi_{n,k}$ is given by
\beq\label{E:cpoly}
\lambda_{\Pi_{n,k}}(t)=t(t-nk-1)(t-nk-2)...(t-n(k+1)+1).
\end{equation}
\end{theorem}
\bigskip
We now extend some more results of the partition lattice $\Pi_n$ to $\Pi_{n,k}$, {f}irst from Hanlon's paper \cite{H81}. Given any poset $P$ with a unique minimal element \ensuremath{\hat{0}}, let ${\rm Max}(P)$ denote the set of maximal elements of $P$ and let \beq\label{E:muP}
\mu(P)=\sum_{x\in {\rm Max}(P)}\mu(\ensuremath{\hat{0}},x).
\end{equation}
Now let $P=\Pi_{n,k}$ and consider the action of the symmetric group $\mathfrak{S}_n$ on $P$, permuting the coordinates of the elements. We consider the subposet $P^{\sigma}$, which consists of the {elements} of $P$ that are {f}ixed by a permutation $\sigma\in\mathfrak{S}_n$, meaning whenever $X\in P^{\sigma}$ and $X\subseteq H_{i,j,r}$, then $X\subseteq H_{\sigma(i),\sigma(j),r}$. Note that if $\varepsilon$ is the identity {permutation}, then $P^{\varepsilon}=P$.
Let $\mu_{\sigma}$ denote the M\"obius function in $P^{\sigma}=\Pi_{n,k}^\sigma$. The goal in this section is to prove that
\begin{equation}\label{E:mobfn}
\mu_{\sigma}(P^{\sigma})=
\begin{cases}
\mu(n/d)(-\frac{n}{d})^{d-1}\binom{(k+1)d-1}{d-1}(d-1)!
&\text{if $\sigma$ is a product of $d$ cycles}\\
&\text{of length $n/d$ for some $d|n$;}\\
0&\text{otherwise}.
\end{cases}
\end{equation}
This is the M\"obius function of~$P^\sigma$, defined as in~\eqref{E:muP}. It generalizes Hanlon's result for $k=0$, stated in~\eqref{E:mupn}. If $\sigma,\tau\in \mathfrak{S}_n$, then one can verify the isomorphism $P^\sigma\cong P^{\tau\sigma\tau^{-1}}$. Hence, viewed as a function of $\sigma$, $\mu_\sigma(P^\sigma)$ is a class function on $\mathfrak{S}_n$. It is in fact, up to a sign, a character of $\mathfrak{S}_n$, as we will soon see.
In order to find $\mu_\sigma(P^\sigma)$, we find the sum of the M\"obius functions of each maximal interval of $P^\sigma$. 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=[\ensuremath{\hat{0}},\ensuremath{\hat{1}}]$. For some $x\in L$, de{f}ine ${\rm Comp}(x)$ to be the set of {\it complements} of $x$ in $L$, i.e., ${\rm Comp}(x)=\{y\in L\colon x\wedge y=\ensuremath{\hat{0}}{\rm\ and\ }x\vee y=\ensuremath{\hat{1}}\}$. Then Crapo's Complementation Theorem \cite[Th. 4]{Cr66} says that for any $x\in L$,
\begin{equation}\label{E:Crapo}
\mu(L)=\sum_{\substack{y,z\in {\rm Comp}(x) \\ y\leq z}}\mu(\ensuremath{\hat{0}},y)\mu(z,\ensuremath{\hat{1}}),
\end{equation}
and if some element of $L$ has no complements, then $\mu (L)=0$.
So we need to show that $[\hat 0,X]^\sigma$ is a lattice for each $X\in{\rm Max}(P^{\sigma})$. By \cite[Prop.~3.1]{Z92}, since every element of~$P$ is an intersection of affine hyperplanes from a given set, it is a geometric semilattice. Thus each maximal interval $[\ensuremath{\hat{0}},X]$ in $P$ is a lattice, and by the first paragraph of section~\ref{S:intro}, $[\ensuremath{\hat{0}},X]^\sigma$ is a lattice too. So Crapo's Theorem applies here. Now we determine which element we use in Equation~\eqref{E:Crapo}.
For each $\sigma\in\mathfrak{S}_n$, it can be verified that
\beq\label{E:Max}
{\rm Max}(P^\sigma)={\rm Max}(P)\cap P^\sigma,
\end{equation}
which is mentioned in the proof of \cite[Th.~2.1]{K96}. For $\sigma$, let
\begin{equation}\label{E:decomp}
\sigma=\sigma_1\sigma_2...\sigma_d
\end{equation}
be the decomposition of $\sigma$ into disjoint cycles. For $i=1,...,d$, let $C_i$ be the {\it support} of the cycle $\sigma_i$, that is, the set of all numbers from the cycle $\sigma_i$. It will be convenient to extend Hanlon's definition of the {\it hinge} of $\Pi_n$~\cite[p. 324]{H81}, the partition which puts each cycle of $\sigma$ into its own block. Here, we want to extend it to any $k\geq 0$, so that it is an intersection of affine hyperplanes. In $\Pi_{n,0}$ the element that corresponds to the hinge of $\Pi_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 $\Pi_{n,0}$. The following lemma shows that for any $k$, only certain hyperplanes in $\Pi_{n,k}$ can contain the hinge.
\bigskip
\begin{lemma}\label{L:eq}
Suppose two numbers $i$ and $j$ are in the same cycle of $\sigma$, and for some $Z\in P^\sigma$, $Z$ is contained in $H_{i,j,r}$ for some $r$. Then $r=0$.
\end{lemma}
\begin{proof}[{\bf Proof}]
Suppose $Z\in P^\sigma$ and $\sigma_1$ is one of the disjoint cycles of $\sigma$ as in \eqref{E:decomp}, with length $m\geq 2$. Suppose without loss of generality that ${i,j\in C_1}$ and ${Z\subseteq H_{i,j,r}}$. Then there exists an $s$ such that ${\sigma^s(i)=j}$, so let $\tau=\sigma^s$. Then ${Z\subseteq H_{i,\tau(i),r}}$ and then ${Z\subseteq H_{\tau^\omega(i),\tau^{\omega+1}(i),r}}$, since for each integer $\omega$, $P^\sigma\subseteq P^{\sigma^\omega}$. This means for any $z\in Z$, ${z_i=z_{\tau^l(i)}+lr}$, so ${z_i=z_{\tau^m(i)}+mr=z_i+mr}$, since $\tau^m$ fixes all elements of $C_1$. Therefore $r=0$ and $Z\subseteq H_{i,j}$.
\end{proof}
\bigskip
This proves that no nontrivial extension of the hinge is possible for $\Pi_{n,k}$. So define the {\it hinge} $h^\sigma$ of $P^\sigma$ to be the intersection of all $H_{j,l}$ for which $j$ and $l$ are in the same cycle of $\sigma$. For an element $Y\in\Pi_{n,k}$, define $\pi(Y)$ to be the \pn\ that \corr s to~$Y$. In other words, if $Y\subseteq H_{i,j,r}$ for some~$r$, then $i$ and $j$ are in the same block of $\pi(Y)$. Therefore, each $C_i$ is a block of $\pi(h^\sigma)$. Then $\dim(h^\sigma)$ is the number of blocks of $\pi(h^\sigma)$ and the number of cycles of $\sigma$. For example, if ${\sigma=(1,2,3)(4,5)(6)\in\mathfrak{S}_6}$, then ${h^\sigma=H_{1,2}\cap H_{1,3}\cap H_{2,3}\cap H_{4,5}}$ in $\mathbb{R}^6$, and $\dim(h^\sigma)=3$. Notice that by Lemma~\ref{L:eq}, $h^\sigma\leq X$ for all ${X\in {\rm Max}(P^{\sigma})}$, and that $h^\sigma$ is the greatest lower bound of all the maximal elements of $P^\sigma$. 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~\eqref{E:mobfn}.
\bigskip
\begin{theorem}\label{T:a}
$\mu_{\sigma}(P^{\sigma})=0$ unless all disjoint cycles of $\sigma$ have the same length.
\end{theorem}
\begin{proof}[{\bf Proof}]
We prove this by showing that for a given $X\in{\rm Max}(P^\sigma)$, $h^\sigma$ has no complements in $[\hat 0,X]^\sigma$. If $\sigma$ is an $n$-cycle, then all cycles of $\sigma$ have the same length, and we do not consider that here. Otherwise, given any two blocks $B_1$ and $B_2$ of $\pi(h^\sigma)$, a given element ${Z\in P^\sigma}$ is a complement of $h^\sigma$ in $[\ensuremath{\hat{0}},X]^\sigma$ only if there exists one element from each of the two blocks, say $i\in B_1$ and $j\in B_2$, such that $Z\subseteq H_{i,j,r}$ for some $r$. We need to show that if any two blocks of $\pi(h^\sigma)$ 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 \ensuremath{\hat{0}} and is also less than $h^{\sigma}$.
Suppose we pick out two cycles from $\sigma$ that have di{f}ferent lengths. We can assume that ${\sigma_1=(1,...,m)}$ and $\sigma_2=(m+1,...,m+b)$, as defined in \eqref{E:decomp}, and $m**\ensuremath{\hat{0}}}$, so $Z$ is not a complement of $h^\sigma$ in $[\ensuremath{\hat{0}},X]^\sigma$. Since we chose an arbitrary $X\in{\rm Max}(P^\sigma)$, we have proved that $h^{\sigma}$ has no complements in any $[\ensuremath{\hat{0}},X]^\sigma$. Thus $\mu_{\sigma}(\ensuremath{\hat{0}},X)=0$ for all $X\in {\rm Max}(P^{\sigma})$ and therefore, $\mu_{\sigma}(P^{\sigma})=0$ unless all cycles of $\sigma$ have the same length.
\end{proof}
\bigskip
Now we will {f}ind $\mu_{\sigma}(P^{\sigma})$ for the other case of~\eqref{E:mobfn}, if $\sigma$ is a product of $d$ cycles of length $n/d$. To do this, we may assume that
\[
\sigma=(1,2,...,j)(j+1,...,2j)\cdots (n-j+1,...,n),
\]
where $j=n/d$. Again, for each $X\in{\rm Max}(P^\sigma)$, we use complements of the hinge $h^\sigma$ in $[\ensuremath{\hat{0}},X]^\sigma$ and equation~\eqref{E:Crapo}. If $C\in {\rm Comp}(h^{\sigma})$ in $[\ensuremath{\hat{0}},x]^{\sigma}$, then $C\not\subseteq H_{\omega_1,\omega_2,r}$ for any $\omega_1,\omega_2\in[j]$ and any $r$, and
\begin{equation}\label{E:subset}
C\subseteq H_{1,sj+i_s,r_s}
\end{equation}
for $s=1,2,...,d-1$, and $r_s$ and $i_s\in [j]$ that depend on $s$. Note that ${\rm dim}(C)=j$ for all such $C$, so no two complements are comparable to each other. This will be used later to simplify \eqref{E:Crapo}. 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 \cite[Lemma 6]{H81}.
\bigskip
\begin{theorem}\label{T:b}
$\mu_{\sigma}(P^{\sigma})=\mu (n/d)(-\frac{n}{d})^{d-1}\binom{(k+1)d-1}{d-1}(d-1)!$ if $\sigma$ is a product of $d$ disjoint cycles of length $n/d$.
\end{theorem}
\bigskip
\begin{lemma}\label{L:div}
Given $X\in {\rm Max}(P^{\sigma})$, if $C\in {\rm Comp}(h^{\sigma})$ in $[\ensuremath{\hat{0}},X]^\sigma$, then $[C,X]^\sigma\cong \mathfrak{D}_{j}$, the lattice of divisors of $j$. Thus, $\mu_\sigma(C,X)=\mu(n/d)$.
\end{lemma}
\begin{proof}[{\bf Proof}]
For any point in an affine subspace from $[C,X]^\sigma$, whatever equality is in the coordinates $1,2,...,j$, the same equality holds for corresponding coordinates from the other blocks of $\pi(h^\sigma)$, depending on $i_s$ in \eqref{E:subset}. At the bottom element $C$ of the interval $[C,X]^\sigma$, for any $i_1,i_2\in[j]$, $C\not\subseteq H_{i_1,i_2,r}$ for any $r$. At the maximal element, ${X\subseteq H_{i_1,i_2}}$ by Lemma \ref{L:eq}. So $[C,X]^\sigma$ here is isomorphic to $[C,\ensuremath{\hat{1}}]^\sigma$ in the case $k=0$. Since~\cite[Lemma~6c]{H81} says that $[C,\ensuremath{\hat{1}}]^\sigma\cong \mathfrak{D}_{n/d}$, we are done.
\end{proof}
\bigskip
\begin{lemma}\label{L:maxbij}
There exists a one-to-one correspondence between the maximal elements of $P^\sigma$ and the maximal elements of $\Pi_{d,k}$.
\end{lemma}
\begin{proof}[{\bf Proof}]
If $d=1$, then $P^\sigma$ has only one maximal element, and $|\Pi_{1,k}|=1$. If $d\geq 2$, then by Lemma \ref{L:eq}, if $X\in{\rm Max}(P^\sigma)$, then ${X\subseteq H_{j(i-1)+\omega,j(i-1)+\omega+1}}$ for all ${i=1,...,d}$ and all ${\omega\in[j-1]}$. Then the ${X\in{\rm Max}(P^\sigma)}$ such that ${X\subseteq H_{j(\omega_1-1)+1,j(\omega_2-1)+1,r}\subseteq\mathbb{R}^n}$ corresponds to the ${Y\in{\rm Max}(\Pi_{d,k})}$ such that ${Y\subseteq H_{\omega_1,\omega_2,r}\subseteq\mathbb{R}^d}$, and vice-versa. So this correspondence is a bijection.
\end{proof}
\bigskip
\begin{lemma}\label{L:isom}
Given a maximal element $X\in P^\sigma$, let $Y$ be its corresponding maximal element in $\Pi_{d,k}$, as described in Lemma \ref{L:maxbij}. If $d\geq 2$, then for all $C\in {\rm Comp}(h^\sigma)$ in $[\ensuremath{\hat{0}},X]^\sigma$, ${[\ensuremath{\hat{0}},C]^\sigma\cong[\ensuremath{\hat{0}},Y]_{\Pi_{d,k}}}$. If $d=1$, then $C=\ensuremath{\hat{0}}$ is the only complement. Thus $\mu_\sigma(\ensuremath{\hat{0}},C)$ is constant for all $C\leq X$.
\end{lemma}
\begin{proof}[{\bf Proof}]
If $d=1$, then since $h^\sigma$ is the maximal element, $\hat 0$ is its only complement. If $d\geq 2$, then we must {f}ind a bijection between the elements of $[\ensuremath{\hat{0}},C]^\sigma\subseteq P^\sigma$ for a given $C\in {\rm Comp}(h^\sigma)$ in $[\ensuremath{\hat{0}},X]^\sigma$ and $[\ensuremath{\hat{0}},Y]\subseteq\Pi_{d,k}$. Suppose $C$ is as in \eqref{E:subset}, and assume without loss of generality that $i_s=1$ for all $s$. Then for all $l=1,...,j$, $C\subseteq H_{l,sj+l,r_s}$. Given $Z\in[\ensuremath{\hat{0}},C]^\sigma$, if $Z\not\subseteq H_{(\omega_1-1)i+1,(\omega_2-1)i+1,r}$ for any $r$, then this corresponds to the element $Z'\in[\ensuremath{\hat{0}},y]$ such that $Z'\not\subseteq H_{\omega_1,\omega_2,r}$ for any $r$. If ${Z\subseteq H_{(\omega_1-1)i+1,(\omega_2-1)i+1,r}}$, then the corresponding $Z'\subseteq H_{\omega_1,\omega_2,r}$. This correspondence can be defined similarly the other way, $Z'\mapsto Z$, so $[\ensuremath{\hat{0}},C]^\sigma\cong[\ensuremath{\hat{0}},Y]$. Thus $\mu_\sigma(\ensuremath{\hat{0}},C)=\mu_{\Pi_{d,k}}(\ensuremath{\hat{0}},Y)$ for all complements $C$ of $h^\sigma$ in $[\ensuremath{\hat{0}},X]$.
\end{proof}
\bigskip
\begin{lemma}\label{L:comps}
Given $X\in{\rm Max}(P^\sigma)$, $h^{\sigma}$ has $(\frac{n}{d})^{d-1}$ complements in $[\ensuremath{\hat{0}},X]^\sigma$.
\end{lemma}
\begin{proof}[{\bf Proof}]
If $d=1$, then $h^\sigma$ is the maximal element of $P^\sigma$, so \ensuremath{\hat{0}} is its only complement. If $d>1$, then for each $s=1,2,...,d-1$, $i_s$, as described in \eqref{E:subset}, has $n/d$ possible values, all independent of each other. So the number of complements of $h^{\sigma}$ is $(\frac{n}{d})^{d-1}$ for $d\geq 1$.
\end{proof}
\bigskip
\begin{proof}[{\bf Proof of Theorem~\ref{T:b}}]
Let $C_X$ be some complement of $h^\sigma$ in $[\ensuremath{\hat{0}},X]^\sigma$ for each $X\in{\rm Max}(P^\sigma)$. Thus:
\begin{align}
\sum_{X\in{\rm Max}(P^{\sigma})}\mu_{\sigma}(\ensuremath{\hat{0}},X)&=\sum_X\sum_{\substack{C\in {\rm Comp}(h^{\sigma}) \\ {\rm in\ }[\ensuremath{\hat{0}},X]^\sigma}}\mu_{\sigma}(\ensuremath{\hat{0}},C)\mu_{\sigma}(C,X)\label{E:crline}\\
&=\mu(n/d)\sum_X\sum_C\mu_{\sigma}(\ensuremath{\hat{0}},C)\label{E:revsum}\\
&=\mu (n/d)\left(\frac{n}{d}\right)^{d-1}\sum_X{\mu_{\sigma}(\ensuremath{\hat{0}},C_X)}\tag{Lemmas ~\ref{L:isom} and~\ref{L:comps}}\\
&=\mu (n/d)\left(\frac{n}{d}\right)^{d-1}\sum_{Y\in{\rm Max}(\Pi_{d,k})}\mu_{\Pi_{d,k}}(\ensuremath{\hat{0}},Y)\tag{Lemma~\ref{L:isom}}\\
&=\mu (n/d)\left(\frac{n}{d}\right)^{d-1}(-1)^{d-1}(d-1)!\binom{(k+1)d-1}{d-1}\label{E:extract}\\
&=\mu (n/d)\left(-\frac{n}{d}\right)^{d-1}\binom{(k+1)d-1}{d-1}(d-1)!\notag \\
\notag
\end{align}
Equation \eqref{E:crline} holds by Crapo's Complementation Theorem. Ordinarily, the sum would be over all ${C,C'\in {\rm Comp}(h^{\sigma})}$ such that ${C\leq C'}$. But no two complements of $h^{\sigma}$ are comparable, as mentioned right before the statement of this theorem. So the sum is just over all ${C\in {\rm Comp}(h^{\sigma})}$.
Equation \eqref{E:revsum} is true by Lemma \ref{L:div}. Also, $\bigcup_X{\{C\in {\rm Comp}(h^{\sigma})\ {\rm in\ }[C,X]^\sigma\}}$ has to be a disjoint union. Suppose $C\in {\rm Comp}(h^{\sigma})$ in both $[\ensuremath{\hat{0}},X]^\sigma$ and $[\ensuremath{\hat{0}},Y]^\sigma$ for $X\ne Y$. Then there exist $i$ and $j$ such that $X\subseteq H_{i,j,r_1}$ and $Y\subseteq H_{i,j,r_2}$, where $r_1\neq r_2$. If we let $Z=X\wedge Y$, then $i$ and $j$ are in different blocks of $\pi(Z)$, and $Z\not\subseteq H_{i',j',r}$ for any $r$ and for any $i'$ in the same block as $i$ of $\pi(Z)$ and any $j'$ in the same block as $j$, since $X\subseteq H_{i',j',r_1}$ and $Y\subseteq H_{i',j',r_2}$. So $Z$ cannot be greater than any complement of $h^\sigma$ in $[\ensuremath{\hat{0}},X]^\sigma$ or in $[\ensuremath{\hat{0}},Y]^\sigma$. But $C\leq X,Y$, which means ${C\leq X\wedge Y=Z}$, a contradiction. So it is a disjoint union.
To get the result \eqref{E:extract}, find $\mu(\Pi_{d,k})$ by extracting the coef{f}icient of $t$ in the characteristic polynomial \eqref{E:cpoly}.
\end{proof}
\section{A Homology Character from $\mu_\sigma(P^\sigma)$}\label{S:hgy}
Again, let $P=\Pi_{n,k}$. Now we define an integer-valued function $\Psi_{n,k}$ on $\mathfrak{S}_n$ given by
\begin{equation}\label{E:psi}
\Psi_{n,k}(\sigma)=(-1)^{d-1}\mu_\sigma(P^\sigma),
\end{equation}
where $d$ is the number of cycles of $\sigma$. Note that the cycles do not all have to be the same length; if they are not, then ${\mu_\sigma(P^\sigma)=0}$, so ${\Psi_{n,k}(\sigma)=0}$.
We now prove that $\Psi_{n,k}(\sigma)$ is, up to a sign, the character af{f}orded by a linear action of $\mathfrak{S}_n$ on a suitable homology. In fact, the character is $(-1)^{n-1}\mu_\sigma(P^\sigma)$, and $\Psi_{n,k}$ is this character times the sign character of~$\mathfrak{S}_n$. We use the methods of Stanley in \cite{St82}.
Let $Q$ be a poset with \ensuremath{\hat{0}} and \ensuremath{\hat{1}}, and let ${\bar Q=Q\setminus\{\ensuremath{\hat{0}},\ensuremath{\hat{1}}\}}$. We follow the notation of~\cite{W98}. The {\it order complex} $\Delta(\bar Q)$ is the abstract simplicial complex whose vertex set is $\bar Q$ and whose $r$-dimensional faces are all chains of the form ${x_0$ be the character of $\alpha$ evaluated at~$\tau\in\Sn$. Then here we have
\[
\left<\beta^{Q^X},\sigma\right>=(-1)^{n-1}\mu_\sigma(\hat 0,X)
\]
for any $X\in{\rm Max}(P^\sigma)$. Therefore, if we let $\beta^P$ be the representation with $\Sn$-action on ${H^W(P)=H_{n-2}^W(P)}$, then using~\eqref{E:hgysum} and~\eqref{E:Max},
\begin{align*}
\left<\beta^P,\sigma\right>&=\sum_{X\in{\rm Max}(P^\sigma)}\left<\beta^{Q^X},\sigma\right>\\
&=\sum_{X\in{\rm Max}(P^\sigma)}(-1)^{n-1}\mu_\sigma(\hat 0,X)=(-1)^{n-1}\mu_\sigma(P^\sigma).
\end{align*}
This is the \chr\ of the action of $\Sn$ on $H^W(P)$. If we combine this with~\eqref{E:psi}, we get $\Psi_{n,k}(\sigma)=(-1)^{n-d}\left<\beta^P,\sigma\right>$ and hence the following result.
\bigskip
\begin{theorem}
$\Psi_{n,k}$ is the product of the sign character of $\mathfrak{S}_n$ and the character afforded by the action of $\mathfrak{S}_n$ on the Whitney \hgy\ of~$\Pi_{n,k}$.
\end{theorem}
\bigskip
Note that $(-1)^{n-d}=-1$ only if $n$ is even and $d$ is odd. If $4|n$, then ${\mu(n/d)=0}$. Therefore, $\Psi_{n,k}$ is the \hgy\ character, and is {\it self-conjugate} unless ${n\equiv 2\pmod{4}}$. (This is an extension of \cite[Lemma~7.3]{St82}.)
\section{$\Psi_{n,k}$ is an Induced Character}\label{S:ind}
Now we know that $\Psi_{n,k}$ is a character, and it is zero for elements of $\mathfrak{S}_n$ that are not conjugate to any elements of $\mathfrak C_n$. So a good direction to go now is to prove that $\Psi_{n,k}$ can be represented as a sum of induced characters $\chi\uparrow_{\mathfrak C_n}^{\mathfrak{S}_n}$, where $\chi$ is an irreducible character of $\mathfrak{C}_n$. By \cite[Lemma 7.2]{St82}, $\Psi_{n,0}$ is simply the value of the induced character $\psi\uparrow_{\mathfrak{C}_n}^{\mathfrak{S}_n}$, where $\psi$ evaluated at a given $n$-cycle that generates $\mathfrak{C}_n$ is $e^{{2\pi i}/n}$. We now extend this result to $\Psi_{n,k}$ for ${k>0}$.
Let $\sigma$ be an $n$-cycle of $\mathfrak{S}_n$ in $\mathfrak{C}_n$. Let $\zeta=e^{2\pi i/n}$ and for $s=1,...,n$, let $\chi_{s,n}$ be the character of $\mathfrak{C}_n$ such that $\chi_{s,n}(\sigma)=\zeta^s$. Then it is known that the $\chi_{s,n}$ are the irreducible characters of $\mathfrak{C}_n$. Let $\chi_{s,n}^\star$ be the induced character $\chi_{s,n}\uparrow_{\mathfrak{C}_n}^{\mathfrak{S}_n}$. If $\gcd(d,n)=\gcd(s,n)$, then it can be verified that $\chi_{s,n}^\star=\chi_{d,n}^\star$, so the goal in this section and the next is to prove that
\begin{equation}\label{E:expr}
\Psi_{n,k}=\sum_{s|n}{a_{n,k}^s\chi_{s,n}^\star}
\end{equation}
for non-negative integers $a_{n,k}^s$. In this section, the main theorem shows that $\Psi_{n,k}$ is an induced character. In the next section, we calculate all the coefficients. It is well-known that if $\zeta$ is a primitive $n$-th root of unity, then
\begin{equation}\label{E:nroot}
\sum_{i=1}^n\zeta^{ir}=
\begin{cases}
n&\text{if $n|r$;} \\
0&\text{otherwise.} \\
\end{cases}
\end{equation}
First, we prove the following lemma.
\bigskip
\begin{lemma}\label{L:linind}
The $\chi_{d,n}^\star$ for $d|n$ are linearly independent.
\end{lemma}
\begin{proof}[{\bf Proof}]
For $d|n$, let ${\lambda_{d,n}=\sum_{i=1}^{n/d}{\chi_{di,n}}}$. Then ${\lambda_{d,n}=1\uparrow_{\mathfrak{C}_d}^{\mathfrak{C}_n}}$, because if we evaluate it at some $\sigma^r$, then we get \eqref{E:nroot}, so ${\lambda_{d,n}(\sigma^r)=0}$ unless $\frac{n}{d}|r$, in which case it is $\frac{n}{d}$. Let
\[
\nu_{d,n}=\sum_{s|d}{\mu(d/s)s\lambda_{s,n}}.
\]
Given $r$, let ${g=\gcd(n,r)}$. Then $\lambda_{s,n}(\sigma^r)=0$ unless $\frac{n}{s}|r$, or equivalently, $\frac{n}{g}|s$, in which case it is $\frac{n}{s}$. So
\begin{align*}
\nu_{d,n}(\sigma^r)&=\sum_{s|d}\mu(d/s)s\lambda_{s,n}(\sigma^r)=\sum_{s|d,\frac{n}{g}|s}\mu(d/s)s\lambda_{s,n}(\sigma^r)\\
&=n\sum_{s|d,\frac{n}{g}|s}\mu(d/s)=n\sum_{s|\frac{dg}{n}}\mu(s)=
\begin{cases}
n&\text{if $g=\frac{n}{d}$;}\\
0&\text{otherwise,}\\
\end{cases}
\end{align*}
since for any positive integer $m$, $\sum_{d|m}\mu(d)=\delta_{1,m}$. Inducing this up to $\mathfrak{S}_n$,
\[
\nu_{d,n}^\star(\sigma^r)=\nu_{d,n}\uparrow_{\mathfrak{C}_n}^{\mathfrak{S}_n}(\sigma^r)=
\begin{cases}
\frac{n!\phi(d)}{\left|{\rm ccl}_{\mathfrak{S}_n}(\sigma^r)\right|}
&\text{if $\gcd(r,n)=\frac{n}{d}$ (or equivalently, $\sigma^r\sim\sigma^{n/d}$);}\\
0&\text{otherwise,}\\
\end{cases}
\]
which, if not zero, is the number of $\tau\in \mathfrak{S}_n$ such that $\tau\sigma^r\tau^{-1}\in \mathfrak{C}_n$. Here, ${\rm ccl}_{\mathfrak{S}_n}(\sigma)$ is the conjugacy class of $\sigma$ in $\mathfrak{S}_n$. From the $\nu_{d,n}^\star$, we can get the standard basis of class functions that are zero in all classes that do not contain an element of $\mathfrak{C}_n$. Since each $\nu_{d,n}^\star$ can be expressed as a linear combination of the $\chi_{d,n}^\star$, and vice-versa, and the $\nu_{d,n}^\star$ are linearly independent for $d|n$, we can conclude that the $\chi_{d,n}^\star$ are linearly independent too, since there are the same number of $\chi_{d,n}^\star$ as there are $\nu_{d,n}^\star$.
\end{proof}
\bigskip
Thus the $\chi^*_{d,n}$ for $d|n$ are a basis for the induced characters from $\mathfrak{C}_n$ up to $\mathfrak{S}_n$. By Theorem~\ref{T:a} and the last part of the proof of Lemma~\ref{L:linind}, $\Psi_{n,k}$ can be expressed as a linear combination, as in \eqref{E:expr}. We now need to show that the $a_{n,k}^s$ are non-negative integers by {f}inding formulas for them. We {f}irst determine $a_{n,k}^n$, which can be found by simply using inner products. Then we {f}ind the $a_{n,k}^s$ in the next section.
\bigskip
\begin{lemma}\label{L:iprod}
$a_{n,k}^n=\frac{1}{n}\sum_{d|n}{\mu\left(\frac{n}{d}\right)\binom{(k+1)d-1}{d-1}}$ for $n\geq 1$.
\end{lemma}
\begin{proof}[{\bf Proof}]
For $n>1$, we show that $a_{n,k}^n=\left<\Psi_{n,k},1_{\mathfrak{S}_n}\right>_{\mathfrak{S}_n}$. Using Frobenius Reciprocity \cite[Th.~1.12.6]{Sa91},
\[
\left<\Psi_{n,k},1_{\mathfrak{S}_n}\right>_{\mathfrak{S}_n}=\sum_{d|n}a^d_{n,k}\left<\chi_{d,n}^{\star},1_{\mathfrak{S}_n}\right>_{\mathfrak{S}_n}=\sum_{d|n}a^d_{n,k}\left<\chi_{d,n},1_{\mathfrak{C}_n}\right>_{\mathfrak{C}_n}=a_{n,k}^n.
\]
The last equality is by orthogonality of irreducible characters. Thus the only time $1_{\mathfrak{S}_n}$ appears in the sum \eqref{E:expr} is when $d=n$. So for an $n$-cycle $\sigma$,
\begin{align}
a_{n,k}^n&=\left<\Psi_{n,k},1_{\mathfrak{S}_n}\right>=\frac{1}{n!}\sum_{\tau\in \mathfrak{S}_n}{\Psi_{n,k}(\tau)}\notag \\
&=\frac{1}{n!}\sum_{d|n}\left|{\rm ccl}_{\mathfrak{S}_n}(\sigma^d)\right|\hbox{\thinspace}\Psi_{n,k}(\sigma^d)\tag{Theorem~\ref{T:a}} \\
&=\frac{1}{n!}\sum_{d|n}\left(\frac{n!}{(n/d)^dd!}\right)\hbox{\thinspace}\mu\left(\frac{n}{d}\right)\left(\frac{n}{d}\right)^{d-1}\binom{(k+1)d-1}{d-1}(d-1)!\tag{Theorem~\ref{T:b}} \\
&=\frac{1}{n}\sum_{d|n}\mu\left(\frac{n}{d}\right)\binom{(k+1)d-1}{d-1}.\notag \\
\notag
\end{align}
For $n=1$, it is clear that $\Psi_{1,k}\equiv 1$ and $a^1_{1,k}=1$.
\end{proof}
\bigskip
Since $\Psi_{n,k}$ is a character of $\mathfrak{S}_n$, it follows by the first assertion in the proof of Lemma~\ref{L:iprod} that $a_{n,k}^n$ is a non-negative integer. For $d|n$, let $\mathfrak{C}_{n/d}=\left<\sigma^d\right>$, and let $\chi_{s,\frac{n}{d}}$ for ${s\leq\frac{n}{d}}$ be an irreducible character for $\mathfrak{C}_{n/d}$ such that ${\chi_{s,\frac{n}{d}}(\sigma^d)=\zeta^{sd}}$ for $1\leq s\leq\frac{n}{d}$. Now let $\chi_{d,n}^\reg=\chi_{1,\frac{n}{d}}\uparrow_{\mathfrak{C}_{n/d}}^{\mathfrak{S}_n}$. Notice that $\chi_{n,n}^\reg$ is the regular character for $\mathfrak{S}_n$ and $\chi_{1,n}^\reg=\chi_{1,n}^{\star}$. Also, note that the $\chi_{d,n}^\reg$ need not be linearly independent. Now we use the next lemma to prove the main result of this section, that $\Psi_{n,k}$ is an induced character from $\mathfrak{C}_n$, because each
$\chi_{d,n}^\reg$ is.
\bigskip
\begin{lemma}\label{L:chireg}
Let $\sigma$ be an $n$-cycle in $\mathfrak{S}_n$. Then we have the following identity:
\[
\frac{1}{d}\chi_{d,n}^\reg(\sigma^r)=
\begin{cases}
\chi_{1,n}^{\star}(\sigma^r)
&\text{if $d|r$}\\
0&\text{otherwise.}\\
\end{cases}
\]
\end{lemma}
\begin{proof}[{\bf Proof}]
We know that $\frac{1}{d}\chi_{d,n}^\reg(\sigma^r)=\frac{1}{d}\chi_{1,\frac{n}{d}}\uparrow_{\mathfrak{C}_{n/d}}^{\mathfrak{S}_n}(\sigma^r)$ and $\chi_{1,n}^{\star}=\chi_{1,n}\uparrow_{\mathfrak{C}_n}^{\mathfrak{S}_n}$. Since induction of representations is transitive, it is enough to show that
\[
\frac{1}{d}\chi_{1,\frac{n}{d}}\uparrow_{\mathfrak{C}_{n/d}}^{\mathfrak{C}_n}(\sigma^r)=
\begin{cases}
\chi_{1,n}(\sigma^r)
&\text{if $d|r$}\\
0&\text{otherwise.}\\
\end{cases}
\]
$d|r$ if and only if $\sigma^r\in \mathfrak{C}_{n/d}$, and then both sides are $\zeta^r$. We induce both sides up to $\mathfrak{S}_n$, and we are done.
\end{proof}
\bigskip
\begin{theorem}\label{T:psireg}
$\Psi_{n,k}=\sum_{d|n}{a_{d,k}^d\chi_{d,n}^\reg}$
\end{theorem}
\bigskip
\begin{proof}[{\bf Proof}]
Let $\mathfrak H_{k,s}=\binom{(k+1)s-1}{s-1}$. We know that
\[
\Psi_{n,k}(\tau)=
\begin{cases}
\mu (d)(\frac{n}{d})^{d-1}(d-1)!\mathfrak H_{k,d}
&\text{if $\tau$ is a product of $d$ cycles}\\
&\text{of length $n/d$ for some $d|n;$}\\
0&otherwise.\\
\end{cases}
\]
Again assume that $d|n$ and $\sigma$ is an $n$-cycle such that $\mathfrak{C}_n=\left<\sigma^d\right>$.
\begin{align}
\sum_{r|n}a_{r,k}^r\chi_{r,n}^\reg\left(\sigma^d\right)
&=\sum_{r|n}\left(\frac{1}{r}\sum_{s|r}\mu\left(\frac{r}{s}\right)\mathfrak H_{k,s}\right)\chi_{r,n}^\reg\left(\sigma^d\right)\tag{Lemma~\ref{L:iprod}}\\
&=\sum_{r|n}\frac{1}{r}\chi_{r,n}^\reg\left(\sigma^d\right)\sum_{s|r}\mu\left(\frac{r}{s}\right)\mathfrak H_{k,s}=\chi_{1,n}^{\star}(\sigma^d)\sum_{r|d}\sum_{s|r}\mu\left(\frac{r}{s}\right)\mathfrak H_{k,s}\notag\\
\intertext{\flushright{(Lemma~\ref{L:chireg})}}
&=\chi^\star_{1,n}(\sigma^d)\sum_{s|d}\mathfrak H_{k,s}\sum_{r|d,s|r}\mu\left(\frac{r}{s}\right)=\chi_{1,n}^{\star}(\sigma^d)\sum_{s|d}\mathfrak H_{k,s}\delta_{d,s}\label{E:musum}\\
&=\mu(n/d)(n/d)^{d-1}(d-1)!\mathfrak H_{k,d}\label{E:st72}\\
\notag
\end{align}
The second equality of~\eqref{E:musum} holds because given $s$,
\[
\sum_{r|d,s|r}\mu\left(\frac{r}{s}\right)=\sum_{q|\frac{d}{s}}\mu(q)=\delta_{d,s}.
\]
For equation~\eqref{E:st72}, \cite[Lemma 7.2]{St82} proves that $\chi_{1,n}^\star(\sigma^d)=\Psi_{n,0}(\sigma^d)$. Thus we have proved that the right-hand side is equal to a value that we know is $\Psi_{n,k}$.
\end{proof}
\bigskip
Given a real number $x$, let $\left$ be the nearest integer to $x$. Recall that the irreducible characters of $\mathfrak{S}_n$ are the $\chi^\lambda$ for each partition $\lambda$ of $n$, and $f^\lambda$ is the degree of $\chi^\lambda$. We now have a way to decompose $\Psi_{p,k}$ into irreducible characters of $\mathfrak{S}_p$ for any odd prime $p$. The following corollary is an extension of a result by Stanley.
\bigskip
\begin{corollary}
Given an odd prime $p$, and a partition $\lambda$ of $p$,
\[
\left<\Psi_{p,k},\chi^\lambda\right>_{\mathfrak{S}_n}=a^p_{p,k}f^\lambda+\left.
\]
\end{corollary}
\begin{proof}[{\bf Proof}]
By Theorem \ref{T:psireg},
\[
\Psi_{p,k}=a^1_{1,k}\chi_{1,p}^*+a^p_{p,k}\chi_{p,p}^\reg.
\]
Therefore, since $a_{1,k}^1=1$ for all~$k$, we get
\[
\left<\Psi_{p,k},\chi^\lambda\right>_{\mathfrak{S}_n}=a^p_{p,k}\left<\chi_{p,p}^\reg,\chi^\lambda\right>+\left<\chi^*_{1,p},\chi^\lambda\right>=a^p_{p,k}f^\lambda+\left.
\]
The {f}irst summand is well-known about the regular character of $\mathfrak{S}_n$ (For example, see Theorem~1.10.1 of~\cite{Sa91}). The second summand is by Corollary~7.4 of~\cite{St82}.
\end{proof}
\section{The Coef{f}icients $a^s_{n,k}$}\label{S:asnk}
By Theorem~\ref{T:psireg}, $\Psi_{n,k}$ is an induced character from $\mathfrak{C}_n$ up to $\mathfrak{S}_n$. For the sake of completeness, we now determine the coefficients $a^s_{n,k}$. This also makes it more clear how to decompose $\Psi_{n,k}$ into irreducibles if $n$ is not prime, since there are references that have the decomposition of induced characters from~$\mathfrak{C}_n$. See for Example~\cite[\S 3]{Stm89}, where it is done \ito 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 $\chi^\star_{d,n}$ appears in the expression of $\chi_{s,n}^\reg$. All we need to do now is determine what $a_{n,k}^s$ is for $s$ properly dividing $n$.
\bigskip
\begin{lemma}\label{L:regdef}
For $d|n$, $\chi_{d,n}^\reg=\sum_{i=0}^{d-1}{\chi_{i\frac{n}{d}+1,n}^{\star}}$.
\end{lemma}
\begin{proof}[Sketch of Proof]
It is enough to show that $\chi_{1,\frac{n}{d}}\uparrow_{\mathfrak{C}_{n/d}}^{\mathfrak{C}_n}=\sum_{i=0}^{d-1}\chi_{i\frac{n}{d}+1,n}$. Just evaluate both sides at $\sigma^r$, and then induce up to $\mathfrak{S}_n$.
\end{proof}
\bigskip
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 in{f}inite sequence $\{a_{n,k}^s\}_{k=0}^\infty$. 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 {f}ind a formula for these sequences, now that we know the $A_d^d$ sequences for $d|n$. De{f}ine the sum of two sequences and scalar multiplication of a sequence the usual way. By theorem \ref{T:psireg}, $a_{d,k}^d$ is the coef{f}icient of $\chi_{d,n}^\reg$ in $\Psi_{n,k}$, so by Lemma~\ref{L:regdef}, it appears in the coef{f}icient of $\chi_{(i-1)\frac{n}{d}+1,n}^{\star}$ for $i=1,2,...,d$, given $k$. Also, if $s=\gcd(g,n)$ for some $g$, then $\chi_{s,n}^{\star}=\chi_{g,n}^{\star}$, 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_{d,k}$ appears in the coef{f}icient of $\chi^\star_{s,n}$, and that is for each $d$ such that there exists an $r\equiv 1\pmod{\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 {f}ind how many of these $r$ exist up to modulo~$n$, and that will be the coef{f}icient of $A_d^d$ in $A_n^s$. First we prove a lemma from number theory that we will use.
\bigskip
\begin{lemma}\label{L:gcd}
Given positive integers $a,b,t$ such that $\gcd(a,b)=1$, there exists an integer $u$ such that $0\leq u0$.
\end{lemma}
\begin{proof}[{\bf Proof}]
We know the case $k=0$. Using \cite[Lemma 7.2]{St82}, $a^1_{n,0}=1$ and $a^d_{n,0}=0$ for $d>1$. For $k\geq 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$, ${\sum_{p|n}\frac{1}{p^2}<1}$ (This inequality also holds when summed over all primes). So we will prove that
\begin{equation}\label{E:ineq}
\binom{nr-1}{n-1}>p^2\binom{q_pr-1}{q_p-1}.
\end{equation}
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_pr-1)_{q_p-1}.$$
Since $pq_p=n$, it follows that $p^2(q_pr-1)(q_pr-2)<(nr-1)(nr-2)$. Thus it is enough to show that
$$(nr-3)_{n-3}>(n-1)_{n-q_p}(q_pr-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_pr-3$ and $nr-q_p>n-1$ (since $r>1$). Thus \eqref{E:ineq} is true, so for each prime $p|n$, ${\frac{1}{p^2}\binom{nr-1}{n-1}>\binom{q_pr-1}{q_p-1}}$. Therefore,
\[
\binom{nr-1}{n-1}>\left(\sum_{\substack{p|n \\ p{\rm\ prime}}}\frac{1}{p^2}\right)\binom{nr-1}{n-1}>\sum_{\substack{p|n \\ p{\rm\ prime}}}\binom{q_pr-1}{q_p-1}
\]
This inequality holds for each integer $n$. In \eqref{E:annk}, if one term $\mathfrak H_{k,d}$ (cf. proof of Theorem~\ref{T:psireg}) is subtracted, then $\mathfrak H_{k,pd}$ is added for some prime $p$, which is a lot larger than $\mathfrak H_{k,d}$ by~\eqref{E:ineq}. Also, the coef{f}icient of $\mathfrak H_{k,n}$ is always $1$. Therefore, $a_{n,k}^n>0$.
\end{proof}
\bigskip
Thus we have proved the following, which by Theorem~\ref{T:psireg} proves that $\Psi_{n,k}$ is a character of $\mathfrak{S}_n$
\bigskip
\begin{theorem}\label{T:imm}
$a_{n,k}^n$ is a non-negative integer for all $n\geq 2$, and it is zero only if $k=0$.
\end{theorem}
\section*{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.
\begin{thebibliography}{9}
\bibitem{A96}
C. A. Athanasiadis, Characteristic polynomials of subspace arrangements and {f}inite {f}ields, \emph{Adv. in Math.} \textbf{122} (1996), 193--233.
\bibitem{B75}
K. Baclawski, Whitney numbers of geometric lattices, {\it Adv. in Math.} {\bf 16} (1975), 125--138.
\bibitem{BB79}
K. Baclawski and A. Bj\"orner, Fixed points in partially ordered sets, {\it Adv. in Math.} {\bf 31} (1979), 263--287.
\bibitem{Bj82}
A. Bj\"orner, On the \hgy\ of geometric lattices, {\it Algebra Universalis} {\bf 14} (1982), 107--128.
\bibitem{Cr66}
H. H. Crapo, The M\"obius function of a lattice, \emph{J. Combin. Theory} {\bf 1} (1966), 126--131.
\bibitem{F66}
J. Folkman, The homology groups of a lattice, \emph{J. Math. Mech.} {\bf 15} (1966), 631--636.
\bibitem{RG96}
R. Gill, A Generalization of the Partition Lattice: Combinatorial Properties and the Action of the Symmetric Group, Ph.D. thesis, University of Michigan, 1998.
\bibitem{RG98}
R. Gill, The number of elements in a generalized \pn\ semilattice, {\it Discrete Math.} {\bf 186} (1998), 125--134.
\bibitem{H81}
P. Hanlon, The {f}ixed point partition lattices, \emph{Paci{f}ic J. Math.} {\bf 96} (1981), 319--341.
\bibitem{K96}
J. Kerr, A basis for the top homology of a generalized partition lattice, {\it J. Algebraic Combin.} {\bf 9} (1999), 47--60.
\bibitem{R64}
G.-C. Rota, On the foundations of combinatorial theory I. Theory of M\"obius Functions, \emph{Z. Wahrscheinlichkeitstheorie} {\bf 2} (1964), 340--368.
\bibitem{Sa91}
B. Sagan, {\it The Symmetric Group}, Wadsworth and Brooks/Cole, Belmont, CA, 1991.
\bibitem{St82}
R. Stanley, Some aspects of groups acting on {f}inite posets, \emph{J. Combin. Theory Ser. A} {\bf 32} (1982), 132--161.
\bibitem{St96}
R. Stanley, Hyperplane \arr s, interval orders, and trees, {\it Proc. Nat. Acad. Sci. U.S.A.} {\bf 93} (1996), 2620--2625.
\bibitem{Stm89}
J. R. Stembridge, On the eigenvalues of representations of reflection groups and wreath products, \emph{Pacific J. Math.} {\bf 140} (1989), 353--396.
\bibitem{W98}
M. L. Wachs, On the (co)\hgy\ of the \pn\ lattice and the \FLA, {\it Discrete Math.} {\bf 193} (1998), 287--319.
\bibitem{WW86}
M. L. Wachs and J. W. Walker, On geometric semilattices, \emph{Order} {\bf 2} (1986), 367--385.
\bibitem{Z92}
G. M. Ziegler, Matroid shellability, $\beta$-systems, and af{f}ine hyperplane arrangements, \emph{J. Algebraic Combin.} {\bf 3} (1992), 283--300.
\end{thebibliography}
\end{document}
**