\documentstyle[12pt]{article}
\textheight 230mm
\textwidth 160mm
\hoffset -12mm
\voffset -17mm
\font\goth=eufb10 scaled 1200

%\textheight 220mm
%\textwidth 160mm
%\hoffset -16mm
%\voffset -30mm

%\font\goth=cmbx10 scaled 1200
\font\sevenbf=cmbx7

\newtheorem{example}{Example}[section]
\newtheorem{note}[example]{Note}
\newtheorem{theorem}[example]{Theorem}
\newtheorem{corollary}[example]{Corollary}
\newtheorem{definition}[example]{Definition}
\newtheorem{proposition}[example]{Proposition}
\newtheorem{algorithm}[example]{Algorithm}
\newtheorem{lemma}[example]{Lemma}

\def\boxit#1#2{\setbox1=\hbox{\kern#1{#2}\kern#1}%
\dimen1=\ht1 \advance\dimen1 by #1 \dimen2=\dp1 \advance\dimen2 by #1
\setbox1=\hbox{\vrule height\dimen1 depth\dimen2\box1\vrule}%
\setbox1=\vbox{\hrule\box1\hrule}%
\advance\dimen1 by .4pt \ht1=\dimen1
\advance\dimen2 by .4pt \dp1=\dimen2 \box1\relax}
\def\bo#1{\boxit{1pt}{$#1$}}

\def\Proof{\medskip\noindent {\it Proof --- \ }}
\def\cqfd{\hfill $\Box$ \bigskip}
\def\adots{\mathinner{\mkern2mu\raise1pt\hbox{.}
\mkern3mu\raise4pt\hbox{.}\mkern1mu\raise7pt\hbox{.}}}
\def\<{\langle}
\def\>{\rangle}
\def\fsf{k\!\not< \! \bb{A}\!\not>}
\def\cf{{\it cf.$\ $}}
\def\ie{{\it i.e. }}
\def\mat{{\rm Mat}}
\def\limproj{\mathop{\oalign{lim\cr
\hidewidth$\longleftarrow$\hidewidth\cr}}}

\def\S{{\bf S}}
\def\sym{{\sl Sym}}
%\newfont{\bb}{msbm10}
\newfont{\bb}{cmbx10}
\def\N{{\bf N}}
\def\Z{{\bf Z}}
\def\E{{\bf E}}
\def\Q{{\bf Q}}
\def\sgn{{\rm sgn\, }}
\def\D{{\rm Des \, }}
\def\Q{{\bf Q}}
\def\maj{{\rm maj\, }}
\def\mod{{\rm mod\ }}
\def\C{{\bf C}}
\def\P{{\cal P}}
\def\Sl{\hbox{\goth sl}\hskip 2.5pt}
\def\g{\hbox{\goth g}}
\def\gl{\hbox{\goth gl}\hskip 2.5pt}
\def\tab{{\rm Tab\, }}
\def\ch{{\rm ch\,}}
\def\I{{\cal I}}
\def\h{\hbox{\goth h}}
\def\H{{\cal H}}
\def\dim{{\rm dim\,}}
\def\Hom{{\rm Hom\,}}
\def\Ad{{\rm Ad\,}}
\def\diag{{\rm diag\,}}
\def\Chi{X}
\def\F{{\cal F}}
\def\tr{{\rm tr\,}}
\def\eg{{\it e.g. }}

\def\vt{\vrule height 0mm depth 2mm width 0mm}
\def\vtt{\vrule height 0mm depth 3mm width 0mm}
\def\vttt{\vrule height 0mm depth 13mm width 0mm}
\def\vtr#1{\vrule height 0mm depth #1mm width 0mm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{HALL-LITTLEWOOD FUNCTIONS 
\\ AND KOSTKA-FOULKES POLYNOMIALS
\\ IN REPRESENTATION THEORY}

\author{\sc J. D\'esarm\'enien, B. Leclerc and J.-Y. Thibon}
\date{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{document}

\maketitle

\begin{abstract}
This paper presents a survey of recent applications of
Hall-Littlewood functions and Kostka-Foulkes polynomials
to the representation theory of the general
linear group $GL(n,\C)$ and of the symmetric group $\S_n$.
The reviewed topics include the $q$-analogue of Kostant's
partition function, vertex operators, generalized exponents
of $GL(n,\C)$ and $\S_n$-harmonic polynomials. We also give
a detailed description of the various combinatorial
interpretations of Kostka-Foulkes polynomials. We conclude
with the study of Hall-Littlewood functions at roots of
unity, which provide a combinatorial description of certain
plethysms.

\bigskip
\centerline{\bf R\'esum\'e}
\smallskip
Cet article donne un aper\c{c}u de plusieurs applications
r\'ecentes des fonctions de Hall-Littlewood et des polyn\^omes
de Kostka-Foulkes aux repr\'esentations 
du groupe lin\'eaire $GL(n,\C)$ et du groupe sym\'etrique $\S_n$.
Parmi les sujets abord\'es figurent notamment le $q$-analogue de la fonction
de partition de Kostant, les op\'erateurs vertex, les exposants
g\'en\'eralis\'es de $GL(n,\C)$ et les polyn\^omes harmoniques
de $\S_n$. Nous donnons aussi une description d\'etaill\'ee
des diverses interpr\'etations combinatoires des polyn\^omes
de Kostka-Foulkes. Nous concluons par l'\'etude des fonctions
de Hall-Littlewood aux racines de l'unit\'e, qui fournit une
interpr\'etation combinatoire de certains pl\'ethysmes. 
\end{abstract}

% ***********************************************************************
%                   TABLE OF CONTENTS
% ***********************************************************************

%\footnotesize
%\tableofcontents
%\normalsize

% ************************************************************************
%                      INTRODUCTION
% ************************************************************************

\section{Introduction}


The original motivation for defining Hall polynomials, Hall algebra and Hall-Littlewood
symmetric functions comes from group theory. It is well known that any finite Abelian
$p$-group $G$ is a direct sum of cyclic subgroups, of orders $p^{\lambda_1}$, 
$p^{\lambda_2}, \ \ldots ,p^{\lambda_r}$, say, where we may suppose that 
$\lambda_1 \ge \lambda_2 \ge \ldots \ge \lambda_r > 0$. The partition 
$\lambda = (\lambda_1, \ldots , \lambda_r)$ determines $G$ to within isomorphism, and
is called the {\it type} of $G$. The investigation of the lattice structure of
finite Abelian $p$-groups leads to the problem of enumerating  
the chains of subgroups
$$ 1 = H_0 \le H_1 \le \ldots \le H_s = G $$
in $G$ of type $\lambda$, such that $H_i/H_{i+1}$ has type $\mu^i$ for 
$i=1,\,2,\,\ldots ,\,s$. Let $g_{\mu^1\ldots \mu^s}^{\lambda}(p)$ denote the number
of such chains. Hall showed \cite{Ha} that 

\smallskip
(i) $g_{\mu^1\ldots \mu^s}^{\lambda}(p)$ is a polynomial function of $p$;

\smallskip
(ii) the numbers $g_{\lambda \mu}^{\nu}(p)$ can be taken as the structure constants
of an associative and commutative algebra $H(p)$, isomorphic to the algebra of symmetric
functions;

\smallskip
(iii) the polynomial function $g_{\lambda ,\mu}^{\nu}(p)$ vanishes identically in $p$
if and only if the corresponding multiplication constant for the Schur functions
$c_{\lambda \mu}^{\nu}=\<s_{\lambda}\,s_{\mu}\,,\,s_{\nu}\>$ is zero;

\smallskip
(iv) the leading term of $g_{\lambda \mu}^{\nu}(p)$ is equal to
$c_{\lambda \mu}^{\nu}\,p^{n(\lambda)-n(\mu)-n(\nu)}$, where 
$n(\lambda)=\sum_i(i-1)\lambda_i$.

\medskip
In fact, it has been brought to light recently by Johnsen \cite{Jo} that as early as
1900, Steinitz had arrived at the very same results in a forgotten note on the theory
of Abelian groups \cite{St}.

\medskip
The Hall algebra $H(p)$ with generators $u_{\lambda}(p)$ may be identified with the
algebra of symmetric functions by sending the complete homogeneous symmetric function
$h_n$ onto the sum $\sum_{|\lambda|=n} u_{\lambda}(p)$, thus introducing a new
family of symmetric functions $u_{\lambda}(p)$. Hall was able to show that the functions 
$u_{1^n}(p)$ coincide up to a power of $p$ with the elementary symmetric functions:
$$u_{1^n}(p)=p^{-n(n-1)/2} e_n\ ,$$
but it remained to Littlewood to obtain an explicit expression for the symmetric functions 
$u_{\lambda}(p)$ for any partition $\lambda$. Defining $P_{\lambda}(q)$ by  
formulas (\ref{QSYM}) and (\ref{PSYM}) below, Littlewood \cite{Li1} found that 
\begin{equation}\label{HALL}
u_{\lambda}(p)= p^{-n(\lambda)}P_{\lambda}(p^{-1}) \ .
\end{equation}

\medskip
It turns out that the $P_{\lambda}(q)$, called now Hall-Littlewood functions,
interpolate between two fundamental bases of the algebra of symmetric functions,
namely, the basis of Schur functions $s_{\lambda}$ when $q=0$, and the basis
of monomial functions $m_{\lambda}$ when $q=1$. The entries $K_{\lambda \mu}$
of the transition matrix from $m_\mu$ to $s_\lambda$ are well known
in representation theory: $K_{\lambda \mu}$ is the multiplicity of the weight
$\mu$ in an irreducible $\gl(n,\C)$-module with highest weight $\lambda$. These
$K_{\lambda \mu}$, or Kostka numbers, have several combinatorial expressions,
the most popular being that $K_{\lambda \mu}$ is the number of Young tableaux
of shape $\lambda$ and weight $\mu$. They can also be evaluated in terms of
Kostant's partition function ${\cal P}(\alpha)$ (see Section~\ref{KOSTANT} below).
${\cal P}(\alpha)$ is defined as the number of ways of writing the vector
$\alpha = (\alpha_1,\ldots ,\alpha_n)$ as a sum 
$$\alpha = \sum_{1\le i<j \le n} \nu_{ij}\,\epsilon_{ij} \ , \ \ \ \ m_{ij}\ge 0 \ $$
of positive roots $\epsilon_{ij}=(0,\ldots ,1, \ldots ,-1,\ldots ,0)$. 
A natural $q$-analogue ${\cal P}_q(\alpha)$ is obtained by taking into account
the `length' $\sum \nu_{ij}$ of each partition, which gives back by means of
Kostant's formula a $q$-analogue $K_{\lambda \mu}(q)$ of the Kostka
numbers $K_{\lambda \mu}$. These polynomials $K_{\lambda \mu}(q)$
happen to be none other than the entries of the transition matrix from
the basis $P_{\mu}(q)$ to the basis $s_{\lambda}$. 

\bigskip
Apart from the Hall algebra, the best known applications of Hall-Littlewood functions include
the character theory of finite linear groups \cite{Gr},
projective and modular representations of symmetric groups \cite{S},
\cite{Mo2} and various topics in algebraic geometry \cite{HS} \cite{He} 
\cite{Lu1} \cite{Lu2}.
The aim of these notes is to present some applications to the ordinary representation
theory of $\S_n$ and of $GL(n,\C)$, with emphasis on the combinatorial
aspects. In particular, the interpretation of Kostka-Foulkes polynomials in terms
of the charge of Young tableaux \cite{LS2} \cite{Sc}, and in terms of the quantum numbers
of rigged configurations \cite{KKR} \cite{KR} are presented and illustrated by
many examples. The notations for symmetric functions are those of \cite{Mcd}.




\section{Raising operators and Kostant's partition function}\label{KOSTANT}

The Jacobi-Trudi determinant for Schur functions can be compactly expressed
by means of {\it raising operators}
\begin{equation}\label{SH}
s_\lambda = \prod_{i<j} (1-R_{ij})\, h_\lambda
\end{equation}
where $R_{ij}\, h_\lambda := h_{R_{ij}(\lambda)}$ and $R_{ij}(\lambda):=
(\ldots,\lambda_i+1,\ldots,\lambda_j-1,\ldots)$.

One would like to be able to invert formula (\ref{SH}), \ie
to write
\begin{equation}\label{HS}
h_\lambda = \prod_{i<j} (1-R_{ij})^{-1} s_\lambda \ .
\end{equation}

The simplest way to justify such a formal manipulation seems to adopt 
the following point of view about raising operators. Rather than acting
on elements of $\Z^n$, we prefer to use {\it linear maps}  from the group
algebra $\Z[\Z^n]$ to some commutative ring $R$.

It is customary to use as a basis of $\Z[\Z^n]$ the {\it formal exponentials}
$(e^\alpha)_{\alpha\in\Z^n}$, satisfying the relations $e^\alpha e^\beta=e^{\alpha+\beta}$.
We shall follow this practice, and furthermore introduce $n$ independent indeterminates
$x_1,\ldots,x_n$ in order to identify $\Z[\Z^n]$ with the ring of polynomials
$\Z[x_1,x_1^{-1},\ldots,x_n,x_n^{-1}]$, by setting $e^\alpha=x_1^{\alpha_1}\cdots x_n^{\alpha_n}$.
We set $X=\{x_1,\ldots x_n\}$ and $X^{\vee} = \{x_1^{-1},\ldots x_n^{-1}\}$.

Now, let $f$ be any $\Z$-module homomorphism from $\Z[\Z^n]$ to a commutative ring $R$.
We define $g=R_{ij}f$ by
\begin{equation}
g(e^\lambda) := f\left( {x_i\over x_j} e^\lambda \right) \ .
\end{equation}

In the applications we have in mind, $R$ will be the ring $\sym$ of symmetric
functions, or of symmetric polynomials in $n$ variables. Introducing in both cases the two
linear maps
$$
s:\ e^\lambda \longmapsto s(\lambda)=s_\lambda
\quad {\rm and}\quad 
h:\ e^\lambda \longmapsto h(\lambda)=h_\lambda
$$
(with $h_i=0$ for $i<0$) and the element
$$
\theta_n = \prod_{1\le i<j \le n}\left (
1-{x_i\over x_j} \right)
$$
we see that (\ref{SH}) can be written
$$
s(e^\lambda) = h(\theta_n e^\lambda) \ ,
$$
from which it follows immediately by linearity that
$$
h(e^\lambda) = s(\theta_n^{-1}e^\lambda)
$$
which is exactly formula (\ref{HS}). We thus see that
this formula has to be interpreted as an identity
between linear maps, $h=\prod_{i<j}(1-R_{ij})^{-1}s$, evaluated
at $e^\lambda$. 

Consider now the function $\P:\ \Z^n\longrightarrow \N$ defined by
\begin{equation}\label{FPAR}
\theta_n^{-1} = \prod_{i<j}\left(1-{x_i\over x_j}\right)^{-1}
= \sum_{\alpha\in\Z^n}\P (\alpha)e^\alpha \ .
\end{equation}
This is an example of a {\it vector partition function}. It counts the
number of ways a vector $\alpha$ can be expressed as a sum of the vectors
$$
\epsilon_{ij} := \epsilon_i - \epsilon_j \quad (i<j)
$$
where $\epsilon_i=(0,\ldots,1,\ldots,0)$ is the canonical basis
of $\Z^n$.

The vectors $\epsilon_{ij}$ $(i\not= j)$ are nothing but the root
system $A_{n-1}$, and those $\epsilon_{ij}$ with $i<j$ are generally
taken as the positive roots. The sublattice $P=\{\alpha|\sum_i\alpha_i=0\}$
of $\Z^n$ can be identified with the weight lattice of $\Sl(n,\C)$, and
for $\alpha\in P$, $\P (\alpha)$ is the number of ways in which the
weight $\alpha$ can be expressed as a sum of positive roots.
Thus, $\P$ is called {\it Kostant's partition function} for the
root system $A_{n-1}$. The partition function can of course be
defined for any root system, and much of the theory presented in this
paper can be extended to this general setting.

Let us return to (\ref{HS}). Using (\ref{FPAR}), we can rewrite it
as
\begin{equation}\label{PARTF}
h_\mu =  \sum_{\alpha\in\Z^n} \P (\alpha) s_{\mu+\alpha}
\end{equation}
where the Schur functions $s_{\mu+\alpha}$ have to be standardized, \ie
expressed in terms of Schur functions indexed by partitions. Defining
$\rho=(n-1,n-2,\ldots,1,0)$, we see that $s_{\mu+\alpha}$ is
equal to $\varepsilon (w)s_\lambda$ if there exist a permutation $w\in \S_n$
and a partition $\lambda$ such that $\mu+\alpha+\rho=w(\lambda+\rho)$, and
is $0$ otherwise. Thus,
\begin{equation}
h_\mu=\sum_\lambda  \left(
\sum_{w\in\S_n} \varepsilon(w) 
\P\left( w(\lambda+\rho) - (\mu+\rho) \right)  \right) s_\lambda  \ .
\end{equation}
On the other hand, the expansion of $h_\mu$ on the basis $s_\lambda$
is well known to be given by the {\it Kostka numbers}
$$
K_{\lambda\mu} = \< h_\mu\, ,\, s_\lambda\> = |\tab (\lambda,\mu)|
$$
where $\tab(\lambda,\mu)$ is the set of Young tableaux with shape
$\lambda$ and weight $\mu$. Thus,
\begin{equation}\label{KM}
K_{\lambda\mu} = \sum_{w\in \S_n}\varepsilon(w)
\P\left( w(\lambda+\rho)-(\mu+\rho) \right) \ .
\end{equation}
This formula is {\it Kostant's weight multiplicity formula} (for
$GL(n,\C)$). Since one has as well
\begin{equation}\label{SM}
s_\lambda = \sum_\mu K_{\lambda\mu} m_\mu
\end{equation}
it expresses the multiplicity $K_{\lambda\mu}$ of the weight
$\mu$ in the irreducible polynomial representation $V_\lambda$
of $GL(n,\C)$ with highest weight $\lambda$.

\begin{example} \label{KOS1}{\rm We put $n=4$, $\lambda=(3,3,2,0)$, $\mu=(2,2,2,2)$.
Then $\lambda + \rho = (6,5,3,0)$ and $\mu + \rho = (5,4,3,2)$.
There are only three nonzero summands in (\ref{KM}), as shown in
the following table.
$$\matrix{ 
w(\lambda + \rho) & w(\lambda + \rho) - (\mu + \rho) & \P(w(\lambda + \rho) - (\mu + \rho)) & \varepsilon(w) \cr
(6,5,3,0)         & (1,1,0,-2)                       &  7                                   &  +             \cr
(5,6,3,0)         & (0,2,0,-2)                       &  3                                   &  -             \cr
(6,3,5,0)         & (1,-1,2,-2)                      &  1                                   &  -             \cr
}
$$
Hence, $K_{\lambda \mu} = 7 - 3 - 1 = 3$. The corresponding three tableaux are

\setlength{\unitlength}{0.25pt}
\centerline{
\begin{picture}(750,200)(0,0)
\put(0,0){\begin{picture}(150,150)
        \put(0,0){\framebox(50,50){1}}
        \put(50,0){\framebox(50,50){1}}
        \put(100,0){\framebox(50,50){2}}
        \put(0,50){\framebox(50,50){2}}
        \put(50,50){\framebox(50,50){3}}
        \put(100,50){\framebox(50,50){4}}
        \put(0,100){\framebox(50,50){3}}
        \put(50,100){\framebox(50,50){4}}
                  \end{picture}}
\put(300,0){\begin{picture}(200,150)
        \put(0,0){\framebox(50,50){1}}
        \put(50,0){\framebox(50,50){1}}
        \put(100,0){\framebox(50,50){2}}
        \put(0,50){\framebox(50,50){2}}
        \put(50,50){\framebox(50,50){3}}
        \put(100,50){\framebox(50,50){3}}
        \put(0,100){\framebox(50,50){4}}
        \put(50,100){\framebox(50,50){4}}
                  \end{picture}}
\put(600,0){\begin{picture}(200,150)
        \put(0,0){\framebox(50,50){1}}
        \put(50,0){\framebox(50,50){1}}
        \put(100,0){\framebox(50,50){3}}
        \put(0,50){\framebox(50,50){2}}
        \put(50,50){\framebox(50,50){2}}
        \put(100,50){\framebox(50,50){4}}
        \put(0,100){\framebox(50,50){3}}
        \put(50,100){\framebox(50,50){4}}
                  \end{picture}}
\end{picture}}

}
\end{example}


\section{Hall-Littlewood functions and the $q$-analogue of the partition function}

A natural statistics on ordinary partitions $\lambda$ of a number $n$ is the {\it length}
(number of parts). That is, the generating function
$$
\sum_{n\ge 0}p(n)t^n = \prod_{k\ge 1}(1-t^k)^{-1}
$$
can be refined in
$$
\sum_{m,n} p(n;m)q^mt^n = \prod_{k\ge 1}(1-qt^k)^{-1}
$$
where $p(n;m)$ is the number of partitions of $n$ in $m$ parts. The same can
be done with vector partition functions, and the length $q$-analog
of Kostant's partition function has indeed been considered by several authors
\cite{Kato}\cite{Mcd}\cite{Lu1}\cite{Gupta1}. For the root system $A_{n-1}$,
it is given by
\begin{equation}
\theta_n(q)^{-1}:=
\prod_{1\le i<j \le n}\left(1-q\,{x_i\over x_j} \right)^{-1}
=\sum_{\alpha\in\Z^n} \P_q(\alpha) e^\alpha
\end{equation}
the coefficient of $q^k$ in $\P_q(\alpha)$ being the number of ways
the weight $\alpha$ can be expressed as a sum of $k$ positive roots.

With this at hand, it is then tempting to define a $q$-analog of
the symmetric function $h_\lambda$ by
\begin{equation}\label{QPRIM}
Q'_\lambda (X;q) := 
\prod_{i<j} (1-qR_{ij})^{-1} s_\lambda(X)
\end{equation}
(the choice of this notation is explained below). One has then
\begin{equation}
Q'_\mu = \sum_\lambda K_{\lambda\mu}(q) s_\lambda
\end{equation}
where
\begin{equation}
K_{\lambda\mu}(q) =\sum_{w\in \S_n}\varepsilon(w)
\P_q\left( w(\lambda+\rho)-(\mu+\rho) \right) \ .
\end{equation}

\begin{example}
{\rm Take $\lambda=(3,3,2,0)$, $\mu=(2,2,2,2)$, as in Example~\ref{KOS1}.
The computation of $K_{\lambda \mu}(q)$ takes the form
$$\matrix{
w(\lambda + \rho) & w(\lambda + \rho) - (\mu + \rho) & \P_q(w(\lambda + \rho) - (\mu + \rho)) & \varepsilon(w) \cr
(6,5,3,0)         & (1,1,0,-2)                       &  q^2 + 3 q^3 + 2 q^4 + q^5           &  +             \cr
(5,6,3,0)         & (0,2,0,-2)                       &  q^2 + q^3 + q^4                     &  -             \cr
(6,3,5,0)         & (1,-1,2,-2)                      &  q^3                                 &  -             \cr
}
$$
Hence, $K_{\lambda \mu}(q) = q^3 + q^4 + q^5$.}
\end{example}

It turns out, although this is by no means obvious, that the
polynomials $K_{\lambda\mu}(q)$ have nonnegative coefficients \cite{LS2}.
They are the {\it Kostka-Foulkes} polynomials, and the symmetric
functions $Q'_\lambda$ are, up to a simple transformation, the
Hall-Littlewood functions.

To be more precise, recall that in the $\lambda$-ring formalism, the
symmetric functions of the argument $(1-q)X$ are defined by
$$
p_k((1-q)X)= (1-q^k)p_k(X)
$$
and similarly
$$
p_k\left( {X\over 1-q} \right) = (1-q^k)^{-1} p_k(X) \ .
$$
Then, the usual Hall-Littlewood functions are
\begin{equation}\label{HLQ}
Q_\mu(X;q) = Q'_\mu ((1-q)X;q) \ .
\end{equation}

\noindent
Littlewood's original definition \cite{Li1} of the $Q$-functions was, for
$X=\{x_1,\ldots,x_n\}$
\begin{equation}\label{QSYM}
Q_\lambda(X;q) = {(1-q)^{\ell (\lambda)}\over [m_0]_q !} 
\sum_{w\in\S_n} w\left(
   e^\lambda\, {\theta_n(q)\over\theta_n(1)} \right)
\end{equation}
where $m_0=n-\ell(\lambda)$ and 
$$
[m_0]_q!=[m_0]_q\,[m_0-1]_q\,\cdots [1]_q = \prod_{1\le i\le m_0}{1-q^i\over 1-q} \ .
$$
The normalization factor $[m_0]_q!^{-1}$ is introduced in order
to have stability with respect to adjunction of variables, \ie
$$
Q_\lambda(x_1,\ldots,x_n\, ;\, q) =
Q_\lambda(x_1,\ldots,x_{m+n}\, ;\, q)|_{x_{m+1}=\ldots =x_{m+n}=0} \ .
$$
The coefficients of $Q_\lambda(X;q)$ on the basis of Schur functions are
polynomials in $q$ having common factors of the type $1-q^i$. Hence one
defines also the symmetric function
\begin{equation}\label{PSYM}
P_{\lambda}(X;q) = {1\over (1-q)^{\ell (\lambda)}
\,[m_1]_q! \cdots [m_n]_q!}
\,Q_{\lambda}(X;q) \ ,
\end{equation}
which still has polynomial coefficients on the basis $(s_\lambda)$.
Littlewood showed 
that the symmetric functions obtained by
Schur as generating functions for the projective characters of $\S_n$
were the $Q_{\lambda}(X;-1)$. He also derived the formula
\begin{equation}\label{RHL}
Q_\lambda(X;q) = \prod_{i<j} (1-qR_{ij})^{-1} s_\lambda((1-q)X) 
\end{equation}
which is easily seen, in view of definition (\ref{QPRIM}), to be equivalent to (\ref{HLQ}).
Finally, he pointed out that Hall's functions $u_\lambda$ were given by
({\ref{HALL}). This relation is established by Morris in \cite{Mo3}.
From our point of view, $(P_\lambda(X;q))$ is simply
the adjoint basis of $\left(Q'_\lambda(X;q)\right)$ for the usual
scalar product of \sym.

\section{Morris' recurrence formula, vertex operators and Green polynomials}

An important consequence of (\ref{RHL}) is the following formula of Morris \cite{Mo1},
which allows to express a Kostka-Foulkes polynomial $K_{\lambda\mu}(q)$ in terms
of the lower weight ones $K_{\alpha\nu}(q)$, where $\nu=(\mu_2,\mu_3,\ldots,\mu_s)$ is
obtained from $\mu$ by removing its largest part:
\begin{equation}\label{MORRIS}
Q_\mu(X;q) = \sum_{r\ge 0} q^r \sum_\alpha K_{\alpha\nu}(q)
\sum_\beta \<s_\beta h_r\, ,\, s_\alpha\> s_{(\mu_1+r,\beta)}((1-q)X) \ .
\end{equation}
This formula looks simpler when stated in terms of {\it vertex operators}.
Recall that for any $f\in\sym$, there is a differential operator $D_f$
on $\sym$ (the {\it Foulkes derivative}) defined as the adjoint of
the multiplication operator $g\mapsto fg$, that is
$$
\< fg\, ,\, h\> = \<g\, ,\,D_f h\> \ .
$$
Introducing the generating series 
\begin{equation}
\sigma_z(X):=\sum_{r\ge 0} z^r h_r(X) \quad {\rm and}\quad
\lambda_z(X):=\sum_{r\ge 0} z^r e_r(X) \ ,
\end{equation}
the generating series for the Schur functions indexed by vectors
of the form $(r,\lambda)$ (where $\lambda$ is a fixed partition) can
then be expressed as
\begin{equation}\label{SVERTEX}
\sum_{r\in\Z}z^r s_{(r,\lambda)} = \sigma_zD_{\lambda_{-1/z}} s_\lambda \ .
\end{equation}
This identity is established by expanding the Jacobi-Trudi determinant by
its first row, which causes the appearance of the skew Schur functions
$s_{\lambda/(1^k)}=D_{e_k}s_\lambda$. The operator 
\begin{equation}
\Gamma_z = \sigma_z\, D_{\lambda_{-1/z}}
\end{equation}
is a typical example of the so-called {\it vertex operators} of 
Mathematical Physics. It has been applied to the determination
of the rational solutions of various hierarchies of soliton equations and
to the construction of representations of certain infinite dimensional
Lie algebras (see {\it e.g.} Kac's book \cite{Kac} Chap. 14 for 
examples and references). Some applications to symmetric 
functions and group characters can be found in \cite{T}\cite{CT}\cite{ST}.
Remark that in $\lambda$-ring notation, 
$$
D_{\sigma_z}f\, (X)=f(X+z)\quad {\rm and}\quad
D_{\lambda_{-z}}f\, (X) =f(X-z)
$$
when $z$ is an element of rank one (which means that
$e_r(z)=0$ for $r>1$), so that
$$
\Gamma_zf\, (X) = \sigma_z(X)\, f\left( X-{1\over z}\right) \ .
$$
Morris' formula can now be rewritten as a generating function identity
similar to (\ref{SVERTEX}) for the $Q'$-functions:
\begin{equation}\label{QVERTEX}
\sum_{p\in\Z} Q'_{(p,\nu)}(X;q) = \Gamma_1\, Q'_\nu (X+q;q) \ .
\end{equation}
Indeed, replacing $Q$ by $Q'$ in (\ref{MORRIS}) and summing over $p=\mu_1$, one
gets
$$
\sum_{p\in\Z}Q'_{(p,\nu)} =
\sum_{r\ge 0} q^r \sum_\alpha K_{\alpha\nu}(q)\sum_\beta \<s_\beta h_r\, ,\, s_\alpha\>
  \sum_{m\in\Z}s_{(m,\beta)}
$$
$$
= \Gamma_1 \left\{ \sum_\alpha K_{\alpha\nu}(q) \sum_\beta 
\left\langle \sum_{r\ge 0} q^r s_{\alpha/r}\, ,\, s_\beta \right\rangle\, s_\beta\right\}
$$
$$
=\Gamma_1\left\{ \sum_\alpha K_{\alpha\nu}(q)s_\alpha (X+q)\right\}
=\Gamma_1 \, Q'_\nu(X+q) = \Gamma_1 D_{\sigma_q} Q'_\nu \ .
$$
By homogeneity, one has as well
\begin{equation}\label{VERTEX}
\sum_{p\in\Z} z^p Q'_{(p,\nu)} = \Gamma_z Q'_\nu(X+q) \ .
\end{equation}

\begin{example}{\rm Let us compute the stable Schur expansion of the functions $Q'_{(p,2,1,1)}$.
First, we have
$$
\sum_{p\in\Z}Q'_{p11}=\Gamma_1\, Q'_{11}(X+q)=
\Gamma_1\left[ q\,s_2(X+q)+s_{11}(X+q)\right]
$$
$$
=\Gamma_1\left[ q\,(s_2+q\,s_1+q^2) + s_{11} + q\,s_1\right]
=\Gamma_1\left[q\,s_2+(q+q^2)\,s_1 +s_{11} +q^3s_0\right]
$$
so that  $Q'_{211}=q\,s_{22}+(q+q^2)\,s_{31}+s_{211}+q^3s_4$.
Now,
$$
\sum_{p\in\Z}Q'_{p211}=
\Gamma_1\left[
q\,s_{22}(X+q)+(q+q^2)\, s_{31}(X+q) +s_{211}(X+q) +q^3s_4(X+q)\right]
$$
$$
= \Gamma_1\left[
q^7s_0 + (q^4+q^5+q^6)\,s_1 + (2q^3+q^4+q^5)\,s_2 +(q^2+q^3+q^4)\, s_{11}
+(q^2+q^3+q^4)\, s_3 \right.
$$
$$
\left.
+q\,s_{111} +(q+2q^2+q^3)\, s_{21} +q^3\,s_4 +(q+q^2)\,s_{31}
+q\,s_{22} +s_{211} \right] \ .
$$
}
\end{example}

Equation (\ref{QVERTEX}) provides a $q$-analogue of the {\it character polynomials}
of the symmetric groups (see {\it e.g.}  \cite{Ke}) for the {\it Green polynomials}.
The (renormalized) Green polynomials $\Chi_\lambda^\mu(q)$ are $q$-analogues (at $q=0$)
of the characters $\chi_\lambda^\mu$ of the symmetric group, defined by
\begin{equation}
\Chi_\lambda^\mu(q) = \<Q'_\mu\, ,\, p_\lambda\> \ .
\end{equation}
If $\mu=(p,\nu)$, it follows from (\ref{QVERTEX}) that
$$
\Chi_\lambda^{(p,\nu)}(q) =\<\sigma_1D_{\lambda_{-1}}Q'_\nu (X+q)\, ,\, p_\lambda\>
$$
$$
=\<Q'_\nu(X+q-1)\, ,\, p_\lambda(X+1)\>
$$
\begin{equation}
= \<Q'_\nu(X+q-1)\, , \, \prod_i (1+p_i)^{m_i(\lambda)} \> 
\end{equation}
which yields an expression of $\Chi_\lambda^{\mu}(q)$ as a polynomial 
$\Xi^\nu(q\, ;\, m_1,m_2,\ldots,m_n)$ in the multiplicities $m_i$
of the parts of $\lambda$, which is independent of the first part $\mu_1$
of $\mu$. The polynomials $\Xi^\nu(0\, ;\, m_1,m_2,\ldots,m_n)$ are the
usual character polynomials of the symmetric group.

\begin{example}{\rm Let $\lambda=(1^{m_1}2^{m_2}\cdots n^{m_n})$. Then,
$$
\Chi_\lambda^{(p,1)}(q) =
\<s_1(X+q-1)\, ,\, \prod_i(1+p_i)^{m_i}\>
$$
$$
= \<p_1 + (q-1)\, ,\, 1+m_1p_1+\cdots\> = (q-1) +m_1 
$$
and
$$
\Chi_\lambda^{(p,2)}=\<Q'_2(X+q-1)\, ,\, \prod_i(1+p_i)^{m_i} \>
$$
$$
=\<s_2(X+q-1)\, ,\, (1+m_1p_1+ {m_1\choose 2}p_1^2+\cdots)(1+m_2p_2+\cdots)\cdots\>
$$
$$
=q(q-1) + (q-1){m_1\choose 1}+{m_1\choose 2} +{m_2\choose 1} \ .
$$
}
\end{example}




\section{Generalized exponents for $GL(n,\C)$}


Consider the adjoint representation of $G:=GL(n,\C)$, \ie its action by conjugation
on its Lie algebra $\g =\gl (n,\C) = M_n(\C)$
$$
\Ad (g) A = gA g^{-1} \ .
$$
Since as a $G$-module $\g = V\otimes V^*$, where $V=\C^n$ is the defining representation
of $GL(n,\C)$, with character $\ch_V = \sum_i x_i$ (the formal character $\ch_U$ of a
polynomial representation can be viewed as the trace of the image of the diagonal matrix
$\diag(x_1,\ldots,x_n)$ in this representation), the character of the adjoint representation
is
$$
\ch_{\g} =\left( \sum_{i=1}^n x_i \right)\left(\sum_{j=1}^n x_j^{-1}\right)
=\sum_{i,j} {x_i\over x_j} \ .
$$
Consider now the symmetric algebra
$$
S^\bullet (\g) = \bigoplus_{k\ge 0} S^k(\g)
$$
as a graded $G$-module. The character of $S^k(\g)$ is then given by the generating
series
\begin{equation}\label{SYMALG}
\sum_{k\ge 0} q^k \ch_{S^k(\g)} =
\sigma_q(XX^{\vee}) =\prod_{i,j}\left (1-q\, {x_i\over x_j}\right)^{-1} \ .
\end{equation}

Let $\I=S^\bullet (\g)^G$ be the algebra of $G$-invariants in $S^\bullet(\g)$.
By a theorem of Kostant \cite{Ko}, $S^\bullet (\g)$ is a free module over
$\I$, generated by the $G$-harmonic polynomials, which are those elements
of $S^\bullet (\g)$ annihilated by all $G$-invariant differential operators
without constant term.
One has $S^\bullet (\g)=\I\otimes\H$, where $\H=\bigoplus_{k\ge0}\H^k$
is the graded module of harmonic polynomials. Kostant defined the
{\it generalized exponents} of a finite-dimensional $G$-module $E$ to be
the exponents $e_1,\ldots,e_s$ of the nonzero terms in the polynomial
\begin{equation}\label{DEFGE}
F_q(E):= \sum_{k\ge 0} \<E\, ,\, \H^k\>q^k =\sum_{i=1}^sc_iq^{e_i}
\end{equation}
where $\<E\, ,\, \H^k\>=\dim_\C \Hom_G (E\, ,\, \H^k)$ is the intertwining
number.

The problem is to compute $F_q(V_\lambda)$ for the irreducible representations
$V_\lambda$ of $G$. Here, we have to consider {\it rational} irreducible
representations of $GL(n,\C)$, whose characters are of the form
$$
e_n(X)^ms_\mu(X)
$$
where $e_n(X)=x_1\cdots x_n$, $m\in\Z$, and $\mu$ is a partition which can be
taken of length $\le n-1$ since with $n$ variables $e_n^m(X)s_\mu(X)=s_{\mu+(m^n)}(X)$.
For $GL(n,\C)$, the result is
\begin{theorem}
The generating series of the characters of harmonic polynomials is equal to
\begin{equation}
\sum_{k\ge 0} q^k \ch_{\H^k} =
(q)_n \prod_{i,j}\left( 1-q\,{x_i\over x_j}\right)^{-1}
=\sum_{k\ge 0} e_n(X)^{-k} Q'_{(k^n)}(X)
\end{equation}
so that for a decreasing vector $\alpha$ with $|\alpha|=0$,
such that $\lambda =\alpha+(k^n)$ is a partition, one has
\begin{equation}
F_q(V_\alpha) = K_{\lambda,(k^n)}(q) \ .
\end{equation}
\end{theorem}

Several sophisticated proofs of this result appear in the literature.
An elementary one, due to Gupta \cite{Gupta1}, can be presented as follows.

Let $\Omega_n$ be the operator which sends the monomial $e^\lambda$
onto the Schur function $s_\lambda(X)$, \ie
\begin{equation}
\Omega_n(f)=\sum_{w\in\S_n} w \left( f\, \prod_{i<j}\left(1-{x_j\over x_i}\right)^{-1}
\right) \ .
\end{equation}
It is clear that when $f$ is symmetric, $\Omega_n(fg)=f\Omega_n(g)$.
Now, equation (\ref{SYMALG}) can be written
$$
(1-q)^n\prod_{i<j}\left(1-q\, {x_j\over x_i}\right)\cdot \sigma_q(XX^\vee)
=\prod_{i<j}\left( 1- q\, {x_i\over x_j} \right)^{-1} \ ,
$$
and we can apply $\Omega_n$ to both sides. An easy induction shows that
$$
\Omega_n\prod_{i<j}\left( 1-q\, {x_j\over x_i}\right)^{-1} = [n]_q! \ ,
$$
and the r.h.s. becomes
$$
\Omega_n\left( \sum_{\alpha\in\Z^n}\P_q(\alpha)e^\alpha\right)
=\sum_{\alpha\in\Z^n} \P_q(\alpha)s_\alpha(X)
=\sum_{\gamma\downarrow}K_{\gamma,(0^n)}(q)s_\gamma(X) \ ,
$$
(sum over decreasing vectors of integers $\gamma$) so that
$$
\sum_{k\ge 0} q^k \ch_{\H^k} = (q)_n\sigma_q(XX^\vee)
=\sum_{k\ge 0} (x_1\cdots x_n)^{-k} Q'_{(k^n)}(X) \ ,
$$
as required.












\section{Harmonic polynomials for the symmetric group}

The modified Hall-Littlewood functions $Q'_\lambda$ also appear as graded
characteristics of the representations of the symmetric group in certain spaces
of polynomials. Recall that the {\it Frobenius characteristic} is the linear
map $\F$ from the representation ring $R(\S_n)$ to the ring of symmetric
functions which sends the irreducible representation indexed by a partition
$\lambda$ to the Schur function $s_\lambda$. If $\chi$ is the character
of a representation $V$, one has (\cf \cite{Mcd}) 
$$
\F (V) = \sum_{|\alpha|=n} \chi(\alpha){p_\alpha\over z_\alpha} \ .
$$
For a graded module $V=\bigoplus_k V_k$, one defines the {\it graded characteristic} by
$$
\F_q(V)=\sum_k q^k \F (V_k) \ .
$$
For example, if $V=\C[x_1,\ldots,x_n]$ is the ring of polynomials endowed
with its usual graduation, the representation of $\S_n$ in $V_1$ is the 
representation by permutation matrices $w \mapsto g_w$, and the representation
in $V_k$ is its $k$-th symmetric power $w\mapsto S^k(g_w)$. Let $w$ be a 
permutation of type $\alpha=(1^{m_1}2^{m_2}\cdots n^{m_n})$. Then, by
a classical identity
$$
\sum_{k\ge 0} q^k\, \tr S^k(g_w) = 
{1\over \det (I - q\, g_w) }
= \prod_{i\ge 1} {1 \over (1-q^i)^{m_i}} = p_\alpha \left( {1\over 1-q} \right)
$$
(in $\lambda$-ring notation), so that
\begin{equation}
\F_q(V)=\sum_{|\alpha|=n}p_\alpha \left( {1\over 1-q} \right) {p_\alpha(X)\over z_\alpha}
= h_n\left( {X\over 1-q}\right) \ .
\end{equation}

The harmonic polynomials for the symmetric group $\S_n$ are those polynomials which
are annihilated by all differential operators of the form
$$
{\cal D} = f\left({\partial\over\partial x_1},\ldots,{\partial\over\partial x_n}\right)
$$
where $f$ is a symmetric polynomial without constant term. For example 
the Vandermonde determinant
$$
\Delta(X) = \prod_{r<s} (x_r-x_s) 
$$
is harmonic, since for $w\in S_n$, 
$$
w{\cal D}\Delta = {\cal D}w\Delta = \varepsilon(w) {\cal D}w
$$
so that ${\cal D}\Delta$ is an alternating polynomial of degree $< {\rm deg}\Delta$.
This implies that ${\cal D}\Delta = 0$ since any alternating polynomial is 
divisible by $\Delta$. As a consequence, any partial derivative 
$$\partial^\alpha \Delta = {\partial^{\alpha_1}\over\partial x_1}\ldots{\partial^{\alpha_n}\over\partial x_n} \Delta $$
of $\Delta$ is harmonic since 
$${\cal D}\partial^\alpha \Delta = \partial^\alpha{\cal D}\Delta = 0\ .$$

A result of Chevalley (valid for any finite reflection group) shows that
as an $\S_n$-module,
\begin{equation}
\C[x_1,\ldots,x_n] = {\cal I}\otimes {\cal H}
\end{equation}
where ${\cal I}=\C[x_1,\ldots,x_n]^{\S_n}$ is the ring of invariants, and
${\cal H}$ the module of harmonic polynomials. Since one clearly has
$$
\F_q({\cal I}) = \sum_{k\ge 0} q^k \dim {\cal I}_k\  h_n(X)
={1\over (q\, ;\, q)_n} \, h_n(X) \ ,
$$
it follows that
\begin{equation}
\F_q({\cal H}) = (q\, ;\, q)_n h_n\left( {X\over 1-q}\right)
=\omega\left( Q'_{(1^n)}(X;q)\right)
\end{equation}
where $\omega$ is the involution $h_n\leftrightarrow e_n$.

It can be shown that the other $Q'$ functions also arise as graded characteristics
of natural submodules of ${\cal H}$ (up to a simple transformation) . However, this is
far more complicated. Let us set
$$
\tilde Q'_\mu(X;q) =\sum_\lambda \tilde K_{\lambda\mu}(q)s_\lambda(X)
=q^{n(\mu)}Q'_\mu(X;q^{-1})
$$
and
$$
F_\mu(X;q) = \omega(\tilde Q'_\mu(X;q)) \ .
$$
(In the special case when $\mu = (1^n)$ we have $\omega(Q_{(1^n)}')=\tilde Q_{(1^n)}'$,
so that $F_{(1^n)}=Q_{(1^n)}'$).
These symmetric functions first appeared as graded $S_n$-characteristics 
in algebraic geometry (\cite{HS}, see
also \cite{Mcd} ex. 9 p. 136). To be precise, if we denote by $X_\mu$ the 
submanifold of the flag manifold $F(\C^n)$ formed by the flags which are
fixed by a unipotent $u$ such that the nilpotent $u-I$ has its Jordan
canonical form described by the partition $\mu$, there is an action
of $\S_n$ on the cohomology ring $H^*(X_\mu,\Q)$ such that
$$
\F_{\sqrt q}(H^*(X_\mu))=\sum_{i\ge 0} q^i \F(H^{2i}(X_\mu)) = F_\mu(X;q) \ .
$$
It is well known that the cohomology ring of the full flag manifold
$F(\C^n)=X_{(1^n)}$ is isomorphic as an $\S_n$-module to the ring of {\it coinvariants}
(for the action $\sigma\, f = f(x_{\sigma(1)}, \ldots ,x_{\sigma(n)})$ which is
conjugate to the above one)
\begin{equation}
\Q[x_1,\ldots,x_n]/{\cal I}^+
\end{equation}
where ${\cal I}^+$ is the ideal generated by the symmetric polynomials
without constant term, and that this ring is itself isomorphic to the
module ${\cal H_\Q}$ of harmonic polynomials (over $\Q$ here).

A description of $H^*(X_\mu)$ as the quotient of the ring of polynomials
by a certain ideal is given in \cite{DCP}, and an isomorphic module
of harmonic polynomials is constructed in \cite{La}. Let $\lambda$ be
a partition of $n$ and $\mu=\lambda'=(\mu_1,\mu_2,\ldots,\mu_k)$ be
its conjugate. The {\it Specht polynomial} $\Delta_\lambda$ is by definition
the product of Vandermonde determinants
$$
\Delta_\lambda = \prod_{i=1}^k \Delta(X^{(i)})
$$
where $X^{(i)}=\{x_r|\mu_0+\cdots+\mu_{r-1}<r\le\mu_0+\cdots+\mu_r\}$ 
($\mu_0:=0$) and for $A\subseteq X$
$$
\Delta(A) = \prod_{x_r,x_s\in A,\ r<s} (x_r-x_s) \ .
$$
Specht's result states that the linear span of the orbit of $\Delta_\lambda$
under $\S_n$ is a model of the irreducible representation of $\S_n$ indexed
by the partition $\lambda$. Now, one can also consider the linear span $L_\lambda$ of
the orbit of $\Delta_\lambda$ under the {\it affine symmetric group}, which
is generated by the permutations and the translations $T_i: x_i \mapsto x_i+1$.
The elements of this orbit are harmonic, since the Specht polynomials are
easily seen to be (up to a scalar factor) partial derivatives of the full
Vandermonde $\Delta(X)$.
By Taylor's formula, the image of a Specht polynomial under an element
of the affine symmetric group is itself
a linear combination of partial derivatives of the  Vandermonde $\Delta(X)$
(which in fact span ${\cal H}$). 
One can then state \cite{La}:

\begin{theorem} The linear span $L_\lambda$ of the orbit of a Specht polynomial
$\Delta_\lambda$ under the affine symmetric group is a submodule
of ${\cal H}$ having as graded characteristic the modified Hall-Littlewood
function $\tilde Q'_\lambda(X;q)$.
\end{theorem}

\begin{example}
{\rm
We choose $\lambda = (2,1,1)$. The Specht polynomial $\Delta_{211}$ may be
expressed as a derivative of the full Vandermonde $\Delta = \Delta(x_1,\ldots ,\,x_4)$:
$$
\Delta_{211} = -{1\over 6}\,\partial^{(0,0,0,3)}\Delta \ .
$$
The homogeneous component of degree 3 of $L_{211}$ is the Specht module
$W_{211}$. A basis is for example 
$$
\{\partial^{(0,0,0,3)}\Delta ,\, \partial^{(0,0,3,0)}\Delta ,\, \partial^{(0,3,0,0)}\Delta\} \ .
$$
The degree 2 component has the basis 
$$
\{\partial^{(0,1,0,3)}\Delta ,\, \partial^{(0,1,3,0)}\Delta ,\, \partial^{(0,3,0,1)}\Delta ,\,
\partial^{(0,0,1,3)}\Delta ,\, \partial^{(0,0,3,1)}\Delta\} \ ,
$$
and is isomorphic to the direct sum $W_{22} \oplus W_{31}$.
The degree 1 component has the basis 
$$
\{\partial^{(0,1,1,3)}\Delta ,\,  \partial^{(1,0,1,3)}\Delta ,\,
\partial^{(1,1,3,0)}\Delta\} \ ,
$$
and is isomorphic to $W_{31}$. Finally, the degree 0 component is generated by
$\partial^{(0,1,2,3)}\Delta$. The graded characteristic is therefore
$$
q^3\,s_{211} + (q+q^2)\,s_{31} + q^2\,s_{22} + s_4 = q^3\, Q'_{211}(q^{-1}) =
\tilde Q'_{211} \ .
$$

}
\end{example}

\medskip
Note that the interpretation of the $F_{\mu}(X;q)$ as graded
characteristics yields the positivity of the Kostka-Foulkes
polynomials.


















\section{Kostka-Foulkes polynomials and the charge of Young tableaux}


In \cite{Fo1}, Foulkes asked for a combinatorial explanation of the positivity
of Kostka polynomials. He conjectured the existence of a natural statistics $c(t)$ on the
set of Young tableaux such that 
$$K_{\lambda \mu}(q)= \sum_{t\in\tab(\lambda ,\mu)} q^{c(t)} \ .$$ 
This conjecture was settled by Lascoux and Sch\"utzenberger \cite{LS2}, \cite{Sc},
who identified $c(t)$ to be the rank of a poset structure on $\tab(\cdot ,\mu)$.

\medskip
The definition of the {\it charge} $c(t)$ rests upon the interpretation of  
Young tableaux as elements of a monoid, whose definition and basic properties will be 
recalled now \cite{LS1}, \cite{La}.
Let $A=\{a_1<a_2< \ldots <a_n\}$ denote a totally ordered alphabet of noncommutative indeterminates,
and consider the free monoid $A^*$ generated by $A$. The Robinson-Schensted bijection
associates with a word $w \in A^*$ a couple $(P(w),Q(w))$ of Young tableaux of the same
shape. It was shown by Knuth \cite{Kn} that the equivalence on $A^*$ defined by 
$$ w \equiv w' \Longleftrightarrow P(w) = P(w') $$
is generated by the relations 
$$zxy \equiv xzy \ , \ \ \ yxz \equiv yzx  \ , \ \ \ 
yxx \equiv xyx \ , \ \ \ yxy \equiv yyx  \ , $$
for any $x{<}y{<}z$ in $A$. The quotient set $A^*/{\equiv}$, which by definition is in
one to one correspondence with the set of Young tableaux on $A$, is therefore endowed
with a multiplicative structure reflecting the Robinson-Schensted construction. 

This multiplication being noncommutative, Lascoux and Sch\"utzenberger introduced the operation
of {\it cyclage}, a monoid analogue of the conjugation $h \rightarrow g^{-1}hg$ in 
noncommutative groups \cite{LS1}, \cite{La}. To be precise, given $t,\,t'$ in the plactic 
monoid $A^*/{\equiv}$ and $i\ge 2$, write 

\centerline{
\begin{picture}(60,20)(0,0)
\put(0,0){$t$}
\put(10,2){\vector(1,0){25}}
\put(20,5){$i$}
\put(40,0){$t'$}
\end{picture}
}

\bigskip
\noindent
if and only if there exists $u$ in $A^*/{\equiv}$ such that 
$t=a_i\,u$ and $t'=u\,a_i$. In this way, $\tab(\cdot ,\mu)$ is given the structure 
of a connected oriented graph, whose transitive closure is a partial order with
minimal element the row tableau $t_{\mu} := a_1^{\mu_1}a_2^{\mu_2}\cdots a_n^{\mu_n}$.
For example, if $\mu = (2,2,1)$, one obtains the ranked poset shown in Figure~\ref{POSET},
in which for convenience the letters $a_i$ in the tableaux have been replaced by
their indices $i$. The cocharge $co(t)$ of a tableau $t$ is defined as its rank
in the poset $\tab(\cdot\, , \, \mu)$, that is, the number of cyclages needed
to transform $t$ into the row tableau $t_{\mu}$. Denote by $m(\mu)$ the maximal
value of the cocharge on $\tab(\cdot\, , \, \mu)$ (if $\mu$ is a partition,
$m(\mu) = n(\mu)=\sum_i (i-1)\mu_i$). The {\it charge} of $t$ is $c(t) = m(\mu) - co(t)$
and one has

\begin{figure}[t]
\setlength{\unitlength}{0.25pt}
\centerline{
\begin{picture}(1300,1400)(0,0)
\put(600,0){\begin{picture}(200,150)
	\put(0,0){\framebox(50,50){1}}
	\put(50,0){\framebox(50,50){1}}
	\put(100,0){\framebox(50,50){2}}
	\put(150,0){\framebox(50,50){2}}
	\put(200,0){\framebox(50,50){3}}
		  \end{picture}}
\put(600,300){\begin{picture}(200,150)
	\put(0,0){\framebox(50,50){1}}
	\put(50,0){\framebox(50,50){1}}
	\put(100,0){\framebox(50,50){2}}
	\put(150,0){\framebox(50,50){2}}
	\put(0,50){\framebox(50,50){3}}
		  \end{picture}}
\put(300,600){\begin{picture}(200,150)
	\put(0,0){\framebox(50,50){1}}
	\put(50,0){\framebox(50,50){1}}
	\put(100,0){\framebox(50,50){2}}
	\put(0,50){\framebox(50,50){2}}
	\put(50,50){\framebox(50,50){3}}
		  \end{picture}}
\put(900,600){\begin{picture}(200,150)
	\put(0,0){\framebox(50,50){1}}
	\put(50,0){\framebox(50,50){1}}
	\put(100,0){\framebox(50,50){2}}
	\put(150,0){\framebox(50,50){3}}
	\put(0,50){\framebox(50,50){2}}
		  \end{picture}}
\put(300,900){\begin{picture}(200,150)
	\put(0,0){\framebox(50,50){1}}
	\put(50,0){\framebox(50,50){1}}
	\put(100,0){\framebox(50,50){3}}
	\put(0,50){\framebox(50,50){2}}
	\put(50,50){\framebox(50,50){2}}
		  \end{picture}}
\put(900,900){\begin{picture}(200,150)
	\put(0,0){\framebox(50,50){1}}
	\put(50,0){\framebox(50,50){1}}
	\put(100,0){\framebox(50,50){2}}
	\put(0,100){\framebox(50,50){3}}
	\put(0,50){\framebox(50,50){2}}
		  \end{picture}}
\put(600,1200){\begin{picture}(200,150)
	\put(0,0){\framebox(50,50){1}}
	\put(50,0){\framebox(50,50){1}}
	\put(0,50){\framebox(50,50){2}}
	\put(50,50){\framebox(50,50){2}}
	\put(0,100){\framebox(50,50){3}}
          \end{picture}}
\put(700,250){\vector(0,-1){150}}
\put(655,170){3}
\put(400,550){\vector(1,-1){150}}
\put(495,495){2}
\put(1000,550){\vector(-1,-1){150}}
\put(900,495){2}
\put(400,850){\vector(0,-1){100}}
\put(355,800){2}
\put(1000,850){\vector(0,-1){100}}
\put(1030,800){3}
\put(600,1150){\vector(-1,-1){150}}
\put(490,1090){3}
\put(700,1150){\vector(1,-1){150}}
\put(795,1090){2}
\put(75,25){0}
\put(75,325){1}
\put(75,625){2}
\put(75,925){3}
\put(75,1225){4}
\put(1250,25){4}
\put(1250,325){3}
\put(1250,625){2}
\put(1250,925){1}
\put(1250,1225){0}
\put(25,1300){Cocharge}
\put(1200,1300){Charge}
\end{picture}}
\caption{\label{POSET}}
\end{figure}
\setlength{\unitlength}{0.25pt}

\begin{theorem}
The Kostka-Foulkes polynomial $K_{\lambda \mu}(q)$ is the generating function of
the charge on $\tab(\lambda ,\mu)$:
$$K_{\lambda \mu}(q)= \sum_{t\in\tab(\lambda ,\mu)} q^{c(t)} \ .$$
\end{theorem}

Given a tableau $t$ of shape $\lambda$, put $s_t := s_{\lambda}$. With this
notation, the theorem can be stated as follows.

\begin{corollary}
The modified Hall-Littlewood function $Q'_{\mu}$ is equal to
$$Q'_{\mu}=\sum_{t\in\tab(\cdot\, , \, \mu)} q^{c(t)}\, s_t \ .$$
\end{corollary}

\begin{example}{\rm
The description given in Figure~\ref{POSET} of the ranked poset $\tab(.\,,\,(2,2,1))$
yields the expansion
$$
Q'_{221} = s_{221} + (q+q^2) s_{32} + q s_{311} + (q^2 + q^3) s_{41} + q^4 s_5 \ .
$$
}\end{example}

\medskip
Alternatively, one can compute the charge of a Young tableau $t$
whose weight is a partition $\mu$ using the following algorithm.

Suppose first that $\mu = (1^n)$. Let $w$ denote the word
obtained by reading $t$ from left to right and top to bottom.
Attach an index to each letter of $w$ as follows; the 
letter $a_1$ has index $0$, and if $a_r$ has index $i$, then
$a_{r+1}$ has index $i$ or $i+1$ according as it lies to the
left or right of $a_r$. The charge of $t$ (or $w$) is then the sum of the
indices. 

Now if $\mu$ is any partition, the row-reading
$w$ of $t$ is decomposed into a sequence of standard words $w_i$. 
To obtain $w_1$, read $w$ from the right and choose the first letter $a_1$, then the first letter $a_2$
to the left of the $a_1$ chosen, and so on. If at any stage
there is no $a_{r+1}$ to the left of the $a_r$ chosen, go back
to the right end of $w$. This procedure extracts a standard subword
$w_1$ of $w$ of length $\mu'_1$. Now erase $w_1$ from $w$ and repeat the procedure to 
get a standard subword $w_2$ of length $\mu'_2$, and so on. The charge of $t$ is
the sum of the charges of the $w_i$.
 
\begin{example} {\rm Take 

\centerline{
\begin{picture}(350,250)
\put(100,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){1}}
\put(50,0){\framebox(50,50){1}}
\put(100,0){\framebox(50,50){2}}
\put(150,0){\framebox(50,50){3}}
\put(200,0){\framebox(50,50){3}}
\put(0,50){\framebox(50,50){2}}
\put(50,50){\framebox(50,50){4}}
\put(100,50){\framebox(50,50){5}}
\put(0,100){\framebox(50,50){4}}
\put(50,100){\framebox(50,50){5}}
\put(0,150){\framebox(50,50){6}}
\put(50,150){\framebox(50,50){6}}
\end{picture}}
\put(0,20){$t =$}
\end{picture}
}

\bigskip\noindent
where for short the letter $a_r$ is simply written $r$. One has 
$w = 6\,{\bf 6}\,4\,{\bf 5\,2\,4}\,5\,{\bf 1}\,1\,2\,3\,{\bf 3}$ and 
$w_1 = 6\,5\,2\,4\,1\,3$,
$w_2 = 6\,4\,5\,1\,2\,3$.
Hence, $c(t)=c(w_1)+c(w_2)=4+11=15$.}
\end{example} 



The combinatorial description of Hall-Littlewood functions and Kostka
polynomials provides some new methods of investigation. Thus, it
enabled Han to prove the following conjecture of Gupta
for the growth of Kostka polynomials \cite{Gu3}, \cite{Han}.

Given a partition $\lambda$ and a positive integer $a$, denote by
$\lambda \cup a$ the partition obtained by inserting in $\lambda$
a new part equal to $a$.

\begin{theorem}\label{CROIS}
For any partitions $\lambda$, $\mu$ and integer $a$, the difference
$$
K_{\lambda \cup a , \mu \cup a}(q) - K_{\lambda \mu}(q)
$$
is a polynomial with nonnegative coefficients.
\end{theorem}

Han's proof consists in the construction of an injective map from
$\tab(\lambda , \mu)$ to $\tab(\lambda\cup a,\mu \cup a)$ which
preserves the charge of Young tableaux.

Another proof of Theorem~\ref{CROIS} has been given by Kirillov \cite{Ki4}.
It is based on the theory of rigged configurations that we shall now
present.

\section{Kostka-Foulkes polynomials, Bethe Ansatz and configurations}

A different description of Kostka-Foulkes polynomials was obtained by
Kirillov and Reshe\-tikhin \cite{KR} as a consequence of their investigation
of combinatorial aspects of the quantum inverse scattering method.

The state space of certain integrable quantum systems, called $\gl(n,\C)$-invariant
models, is equal to the tensor product 
$$\h = S^{\mu_1}(V)\otimes \cdots \otimes S^{\mu_r}(V)$$
of symmetric powers of the defining representation $V$ of $\gl(n,\C)$.
The eigenvectors of the Hamiltonian of the model can be constructed
by means of a substitution known as the {\it Bethe Ansatz} \cite{Fa}. They are
parametrized by the solutions of a system of algebraic equations (Bethe
equations) which in turn are in one to one correspondence with
combinatorial objects named {\it rigged configurations} \cite{TF}. It can be
shown analytically that the Bethe vectors form a complete system of
highest weight vectors for the $\gl(n,\C)$-module $\h$ and
hence can also be parametrized by Young tableaux of weight 
$\mu=(\mu_1,\ldots ,\mu_r)$ \cite{Ki1}\cite{Ki2}. In \cite{KKR} \cite{KR} an 
explicit bijection 
is constructed between Young tableaux and rigged configurations,
which sends the charge of Young tableaux on a natural invariant of
rigged configurations, namely, the sum of their {\it quantum numbers}.
This yields a very efficient formula for evaluating Kostka-Foulkes
polynomials as sums of products of $q$-binomial coefficients.

Before explaining the Kirillov-Reshetikhin bijection, we introduce
the necessary definitions concerning configurations. Let $\lambda$,
$\mu$ be partitions such that $|\lambda | = |\mu |$. It is convenient
to regard $\lambda$, $\mu$ as infinite nonincreasing sequences by
putting $\lambda_k = 0$ for $k> \ell(\lambda)$, $\mu_k = 0$ for
$k> \ell(\mu)$. A {\it matrix of type} $(\lambda ,\, \mu )$ is a matrix
$M=(m_{ij})_{i,j\ge 1}$ with only a finite number of nonzero integer
entries, such that
$$
\sum_{j\ge 1} m_{ij} = \lambda_i\ , \ \ \ 
\sum_{i\ge 1} m_{ij} = \mu'_j \ .
$$
Here and in the sequel, we denote by $\mu'_j$ the $j$th part of the conjugate
partition $\mu'$ of $\mu$. 

With such a matrix $M$ are associated two matrices $P=(P_{ij})_{i,j\ge 1}$,
$Q=(Q_{ij})_{i,j\ge 1}$ defined by
$$
P_{ij} = \sum_{k\le j}(m_{ik}-m_{i+1,k})\ , \ \ \
Q_{ij} = \sum_{k\ge i+1}(m_{kj}-m_{k,j+1})\ .
$$
The matrix $M$ is an {\it admissible matrix of type $(\lambda ,\, \mu )$}
if and only if $P_{ij}$ and $Q_{ij}$ are nonnegative for all $i,j\ge 1$.
The numbers $P_{ij}$ such that $Q_{ij}>0$ are called the {\it vacancy numbers}
of $M$. 

An admissible matrix is conveniently pictured as a sequence $\nu = (\nu^0, \nu^1, \nu^2, \ldots \,)$
of partitions, or {\it configuration}, defined by
$$
(\nu^i)'_j = \sum_{k\ge i+1} m_{kj} \ .
$$
Obviously, one can recover the admissible matrix $M$ from the configuration $\nu$,
so that the two combinatorial datas $M$ or $\nu$ are equivalent. In particular,
the type $(\lambda ,\, \mu )$ is computed from $\nu$ by
$\lambda_i = |\nu^i| - |\nu^{i-1}|$, for $i\ge 1$, and
$\mu = \nu^0$.

The rows of the diagram of $\nu^i$ are called {\it strings of type $i$}.
By construction the nonzero integers $Q_{ij}$ in the $i$th row of $Q$
are equal to the multiplicities of the partition $\nu^i$, {\it i.e.} to
the successive widths of the {\it blocks} of strings of equal length in $\nu^i$,
so that a vacancy number $P_{ij}$ is in fact associated with each block of
strings of type $i\ge 1$. It is written to the right of the block.

\begin{example}\label{EXCONF}{\rm
Let us illustrate all these definitions. The matrix 
$$
M = \pmatrix{
3 & 5 & -2 & -1 \cr
2 & 0 & 1 & 1   \cr
1 & 1 & 1 & 0 \cr
1 & 1 & 0 & 0 \cr
}
$$
has type $(\lambda , \mu)$, where $\lambda = (5,4,3,2)$ and
$\mu = (2,2,2,2,2,2,2)$. The associated matrices $P$ and $Q$
are equal to
$$
P = \pmatrix{
{\bf 1}& 6 & {\bf 3} & {\bf 1} \cr
1      & {\bf 0} & {\bf 0} & 1 \cr
0  & \bf{0} & 1 & 1 \cr
}
\ , \ \ \ 
Q = \pmatrix{
{\bf 2}& 0 & {\bf 1} & {\bf 1} \cr
0      & {\bf 1} & {\bf 1} & 0 \cr
0  & \bf{1} & 0 & 0 \cr
}
\ .
$$
The nonzero entries of $Q$ and the corresponding vacancy numbers in $P$
have been printed in bold type.

The representation of $M$ as a configuration $\nu = (\nu^0, \nu^1,\nu^2,\nu^3)$ is

\centerline{
\begin{picture}(1000,400)
\put(0,0){\begin{picture}(100,350)
			 \put(0,0){\framebox(50,50){}}
			 \put(0,50){\framebox(50,50){}}
			 \put(0,100){\framebox(50,50){}}
			 \put(0,150){\framebox(50,50){}}
			 \put(0,200){\framebox(50,50){}}
			 \put(0,250){\framebox(50,50){}}
			 \put(0,300){\framebox(50,50){}}
			 \put(50,0){\framebox(50,50){}}
			 \put(50,50){\framebox(50,50){}}
			 \put(50,100){\framebox(50,50){}}
			 \put(50,150){\framebox(50,50){}}
			 \put(50,200){\framebox(50,50){}}
			 \put(50,250){\framebox(50,50){}}
			 \put(50,300){\framebox(50,50){}}
           \end{picture}}
\put(200,0){\begin{picture}(250,200)
			 \put(0,0){\framebox(50,50){}}
		     \put(0,50){\framebox(50,50){}}
		     \put(0,100){\framebox(50,50){}}
			 \put(0,150){\framebox(50,50){}}
			 \put(50,0){\framebox(50,50){}}
		     \put(50,50){\framebox(50,50){}}
		     \put(100,0){\framebox(50,50){}}
			 \put(100,50){\framebox(50,50){}}
			 \put(150,0){\framebox(50,50){}}
			 \put(220,10){1}
			 \put(170,60){3}
			 \put(70,135){1}
			 \end{picture}}
\put(500,0){\begin{picture}(200,100)
              \put(0,0){\framebox(50,50){}}
			  \put(0,50){\framebox(50,50){}}
			  \put(50,0){\framebox(50,50){}}
			  \put(50,50){\framebox(50,50){}}
			  \put(100,0){\framebox(50,50){}}
			  \put(170,10){0}
			  \put(120,60){0}
			   \end{picture}}
\put(750,0){\begin{picture}(150,50)
              \put(0,0){\framebox(50,50){}}
			  \put(50,0){\framebox(50,50){}}
			  \put(120,10){0}
			  \end{picture}}
\end{picture}
}

}
\end{example}

\medskip
The last definition is that of a {\it rigged configuration}, by which we
mean a configuration $\nu$ together with a family of {\it quantum numbers}.
These are nonnegative integers ${\cal I}^i_j$ attached to each string
$\nu^i_j$ of type $i\ge 1$, which must not exceed the vacancy number 
associated with their block. Quantum numbers are written in the
leftmost cell of the string to which they belong. The order of the
quantum numbers inside a given block is irrelevant. In other words,
permutations of the strings of a same block are allowed, so that we can always assume that
quantum numbers are weakly increasing (or decreasing) from bottom to top within each block. 

\begin{example}\label{EXRIG}{\rm
The following is a rigging of the configuration $\nu$ of Example~\ref{EXCONF}.

\centerline{
\begin{picture}(1000,400)
\put(0,0){\begin{picture}(100,350)
\put(0,0){\framebox(50,50){}}
\put(0,50){\framebox(50,50){}}
\put(0,100){\framebox(50,50){}}
\put(0,150){\framebox(50,50){}}
\put(0,200){\framebox(50,50){}}
\put(0,250){\framebox(50,50){}}
\put(0,300){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(50,50){\framebox(50,50){}}
\put(50,100){\framebox(50,50){}}
\put(50,150){\framebox(50,50){}}
\put(50,200){\framebox(50,50){}}
\put(50,250){\framebox(50,50){}}
\put(50,300){\framebox(50,50){}}
\end{picture}}
%
\put(200,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){0}}
\put(0,50){\framebox(50,50){3}}
\put(0,100){\framebox(50,50){0}}
\put(0,150){\framebox(50,50){1}}
\put(50,0){\framebox(50,50){}}
\put(50,50){\framebox(50,50){}}
\put(100,0){\framebox(50,50){}}
\put(100,50){\framebox(50,50){}}
\put(150,0){\framebox(50,50){}}
\put(220,10){1}
\put(170,60){3}
\put(70,135){1}
\end{picture}}
%
\put(500,0){\begin{picture}(200,100)
\put(0,0){\framebox(50,50){0}}
\put(0,50){\framebox(50,50){0}}
\put(50,0){\framebox(50,50){}}
\put(50,50){\framebox(50,50){}}
\put(100,0){\framebox(50,50){}}
\put(170,10){0}
\put(120,60){0}
\end{picture}}
%
\put(750,0){\begin{picture}(150,50)
\put(0,0){\framebox(50,50){0}}
\put(50,0){\framebox(50,50){}}
\put(120,10){0}
\end{picture}}
\end{picture}
}}
\end{example}

\bigskip
It is clear from the definition that the number of rigged configurations $(\nu,{\cal I})$
corresponding to a given configuration $\nu$ is equal to the product of binomial
coefficients
$$
N = \prod_{i,j\ge 1} { P_{ij} + Q_{ij} \choose Q_{ij}} 
$$
(with the usual convention ${m \choose 0} = 1$ for $m \in \Z$). As stated above, the
Bethe vectors of $\h$ are highest weight vectors parametrized by rigged configurations.
More precisely, the Bethe vectors of weight $\lambda$ in 
$S^{\mu_1}(V)\otimes \cdots \otimes S^{\mu_r}(V)$ are labelled by rigged configurations
of type $(\lambda ,\, \mu)$. It follows from the completeness of the Bethe system that

\begin{theorem}\label{KOSTZ}
The Kostka number $K_{\lambda \mu}$ is equal to
$$
K_{\lambda \mu}=\sum_\nu N(\nu) = \sum_\nu \prod_{i,j\ge 1} { P_{ij}(\nu) + Q_{ij}(\nu) \choose Q_{ij}(\nu)}
$$
the sum running over all configurations $\nu$ of type $(\lambda ,\, \mu)$.
\end{theorem}

\begin{example}\label{EXTH1}{\rm
Take $\lambda = (8,5,2)$, $\mu = (6,4,3,2)$. There are two configurations $\nu$
of type $(\lambda ,\, \mu)$, viz.

\centerline{
\begin{picture}(1050,250)
\put(0,0){\begin{picture}(300,250)
\put(0,0){\framebox(50,50){}}
\put(0,50){\framebox(50,50){}}
\put(0,100){\framebox(50,50){}}
\put(0,150){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(50,50){\framebox(50,50){}}
\put(50,100){\framebox(50,50){}}
\put(50,150){\framebox(50,50){}}
\put(100,0){\framebox(50,50){}}
\put(100,50){\framebox(50,50){}}
\put(100,100){\framebox(50,50){}}
\put(150,0){\framebox(50,50){}}
\put(150,50){\framebox(50,50){}}
\put(200,0){\framebox(50,50){}}
\put(250,0){\framebox(50,50){}}
\end{picture}}
%
\put(400,0){\begin{picture}(350,100)
\put(0,0){\framebox(50,50){}}
\put(0,50){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(50,50){\framebox(50,50){}}
\put(100,0){\framebox(50,50){}}
\put(200,0){\framebox(50,50){}}
\put(150,0){\framebox(50,50){}}
\put(270,10){2}
\put(120,60){2}
\end{picture}}
%
\put(800,0){\begin{picture}(250,100)
\put(0,0){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(120,10){0}
\end{picture}}
%
\end{picture}
}

\centerline{
\begin{picture}(1050,250)
\put(0,0){\begin{picture}(300,250)
\put(0,0){\framebox(50,50){}}
\put(0,50){\framebox(50,50){}}
\put(0,100){\framebox(50,50){}}
\put(0,150){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(50,50){\framebox(50,50){}}
\put(50,100){\framebox(50,50){}}
\put(50,150){\framebox(50,50){}}
\put(100,0){\framebox(50,50){}}
\put(100,50){\framebox(50,50){}}
\put(100,100){\framebox(50,50){}}
\put(150,0){\framebox(50,50){}}
\put(150,50){\framebox(50,50){}}
\put(200,0){\framebox(50,50){}}
\put(250,0){\framebox(50,50){}}
\end{picture}}
%
\put(400,0){\begin{picture}(350,100)
\put(0,0){\framebox(50,50){}}
\put(0,50){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(50,50){\framebox(50,50){}}
\put(100,0){\framebox(50,50){}}
\put(100,50){\framebox(50,50){}}
\put(150,0){\framebox(50,50){}}
\put(220,10){1}
\put(170,60){1}
\end{picture}}
%
\put(800,0){\begin{picture}(250,100)
\put(0,0){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(120,10){0}
\end{picture}}
%
\end{picture}
}

\bigskip\noindent
Thus $K_{\lambda \mu} = {2+1 \choose 1}{2+1 \choose 1}{0+1 \choose 1}
+{1+1 \choose 1}{1+1 \choose 1}{0+1 \choose 1}
=9+4=13$.
}
\end{example}

We shall now explain the bijection devised by Kirillov and Reshetikhin
for proving combinatorially Theorem~\ref{KOSTZ}.

A string $\nu^i_j$ of type $i\ge 1$ in a rigged configuration $(\nu, {\cal I})$
is called {\it singular} when its quantum number ${\cal I}^i_j$ is maximal,
{\it i.e.} is equal to the corresponding vacancy number. By convention, the
only singular string of type $0$ is the upper one. Consider now chains of
weakly increasing singular strings 
$$
\nu^0_{i_0} \le \nu^1_{i_1} \le \cdots \le \nu^s_{i_s}
$$
in $(\nu, {\cal I})$. Define the {\it rank} of $(\nu, {\cal I})$ as the maximal
length of such a chain. For example, the rank of the rigged configuration shown
in Example~\ref{EXRIG} is equal to 3, the longest chain being

\centerline{
\begin{picture}(800,100)
\put(0,0){\begin{picture}(100,350)
\put(0,0){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\end{picture}}
%
\put(200,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){3}}
\put(50,0){\framebox(50,50){}}
\put(100,0){\framebox(50,50){}}
\put(170,10){3}
\end{picture}}
%
\put(500,0){\begin{picture}(200,100)
\put(0,0){\framebox(50,50){0}}
\put(50,0){\framebox(50,50){}}
\put(100,0){\framebox(50,50){}}
\put(170,10){0}
\end{picture}}
\end{picture}
}

\bigskip
Let $t$ be a Young tableau of shape $\lambda$ and weight $\mu$. The cells of $t$
can be ordered by first reading the 1's from left to right, then the 2's from
left to right, and so on (this is the usual standardization of $t$). The rigged
configuration $(\nu, {\cal I})$ corresponding to $t$ is now constructed inductively
as follows.

The last cell of $t$ belongs to row number $r$, say. Let $\overline{t}$ be the tableau obtained
from $t$ by erasing this cell, and assume that the corresponding rigged 
configuration $(\overline{\nu},\, \overline{\cal I})$ is known.

{\it Construction of $\nu$}: Add one cell to one of the longest singular strings of 
type $r-1$ in $(\overline{\nu},\, \overline{\cal I})$ (if there is none, create
a new string of type $r-1$ and length 1). Let $m$ be the length of this new
string. Similarly, add one cell to one of the longest singular strings of
type $r-2$ and length $\le m-1$ (if there is none, create
a new string of type $r-2$ and length 1). And so on. 
If necessary, reorder the strings inside each diagram in order to get a sequence
of partitions. In this way a new
configuration $\nu$ of type $(\lambda , \mu)$ is obtained, which differs from 
$\overline{\nu}$ by a single chain $C$ composed of $r$ strings.

{\it Construction of {$\cal I$}}: Compute the vacancy numbers of $\nu$. The
$r$ strings composing $C$ are given their maximal quantum numbers, while
the quantum numbers of all the other strings remain unchanged.

\begin{example}\label{EXBIJ1}{\rm
We take

\centerline{
\begin{picture}(350,250)
\put(100,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){1}}
\put(50,0){\framebox(50,50){1}}
\put(100,0){\framebox(50,50){2}}
\put(150,0){\framebox(50,50){3}}
\put(200,0){\framebox(50,50){3}}
\put(0,50){\framebox(50,50){2}}
\put(50,50){\framebox(50,50){4}}
\put(100,50){\framebox(50,50){5}}
\put(0,100){\framebox(50,50){4}}
\put(50,100){\framebox(50,50){5}}
\put(0,150){\framebox(50,50){6}}
\put(50,150){\framebox(50,50){6}}
\end{picture}}
\put(0,20){$t =$}
\end{picture}
}

\bigskip\noindent
The configuration $(\overline{\nu},\, \overline{\cal I})$ associated to 

\centerline{
\begin{picture}(350,250)
\put(100,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){1}}
\put(50,0){\framebox(50,50){1}}
\put(100,0){\framebox(50,50){2}}
\put(150,0){\framebox(50,50){3}}
\put(200,0){\framebox(50,50){3}}
\put(0,50){\framebox(50,50){2}}
\put(50,50){\framebox(50,50){4}}
\put(100,50){\framebox(50,50){5}}
\put(0,100){\framebox(50,50){4}}
\put(50,100){\framebox(50,50){5}}
\put(0,150){\framebox(50,50){6}}
\end{picture}}
\put(0,20){$\overline{t} =$}
\end{picture}
}

\bigskip\noindent
is supposed to be known, and is equal to

\centerline{
\begin{picture}(1000,400)
\put(0,0){\begin{picture}(100,350)
\put(0,0){\framebox(50,50){}}
\put(0,50){\framebox(50,50){}}
\put(0,100){\framebox(50,50){}}
\put(0,150){\framebox(50,50){}}
\put(0,200){\framebox(50,50){}}
\put(0,250){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(50,50){\framebox(50,50){}}
\put(50,100){\framebox(50,50){}}
\put(50,150){\framebox(50,50){}}
\put(50,200){\framebox(50,50){}}
\end{picture}}
%
\put(200,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){2}}
\put(0,50){\framebox(50,50){0}}
\put(0,100){\framebox(50,50){0}}
\put(0,150){\framebox(50,50){0}}
\put(50,0){\framebox(50,50){}}
\put(100,0){\framebox(50,50){}}
\put(170,10){2}
\put(70,105){0}
\end{picture}}
%
\put(500,0){\begin{picture}(200,100)
\put(0,0){\framebox(50,50){0}}
\put(0,50){\framebox(50,50){1}}
\put(50,0){\framebox(50,50){}}
\put(120,10){0}
\put(70,60){1}
\end{picture}}
%
\put(750,0){\begin{picture}(150,50)
\put(0,0){\framebox(50,50){0}}
\put(70,10){0}
\end{picture}}
\end{picture}}

\bigskip\noindent
Here, $r=4$ and the rigged configuration $(\nu, {\cal I})$ computed
by application of the rules described above is

\centerline{
\begin{picture}(1000,400)
\put(0,0){\begin{picture}(100,350)
\put(0,0){\framebox(50,50){}}
\put(0,50){\framebox(50,50){}}
\put(0,100){\framebox(50,50){}}
\put(0,150){\framebox(50,50){}}
\put(0,200){\framebox(50,50){}}
\put(0,250){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(50,50){\framebox(50,50){}}
\put(50,100){\framebox(50,50){}}
\put(50,150){\framebox(50,50){}}
\put(50,200){\framebox(50,50){}}
\put(50,250){\framebox(50,50){}}
\end{picture}}
%
\put(200,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){2}}
\put(0,50){\framebox(50,50){4}}
\put(0,100){\framebox(50,50){0}}
\put(0,150){\framebox(50,50){0}}
\put(50,0){\framebox(50,50){}}
\put(50,50){\framebox(50,50){}}
\put(100,0){\framebox(50,50){}}
\put(170,10){2}
\put(120,60){4}
\put(70,130){0}
\end{picture}}
%
\put(500,0){\begin{picture}(200,100)
\put(0,0){\framebox(50,50){0}}
\put(0,50){\framebox(50,50){0}}
\put(50,0){\framebox(50,50){}}
\put(50,50){\framebox(50,50){}}
\put(120,35){0}
\end{picture}}
%
\put(750,0){\begin{picture}(150,50)
\put(0,0){\framebox(50,50){0}}
\put(50,0){\framebox(50,50){}}
\put(120,10){0}
\end{picture}}
\end{picture}}


\bigskip\noindent
the associated matrices being
$$
M=\pmatrix{
2 & 4 & -1 \cr
2 & 0 & 1 \cr
1 & 1 & 0 \cr
1 & 1 & 0 \cr
}
\ ,
\ \ \ 
P=\pmatrix{
{\bf 0} & {\bf 4} & {\bf 2} \cr
1       & {\bf 0} &   1 \cr
0 & {\bf 0} & 0 \cr
}
\ ,
\ \ \
Q=\pmatrix{
{\bf 2} & {\bf 1} & {\bf 1} \cr
0       & {\bf 2} &   0 \cr
0 & {\bf 1} & 0 \cr
}
\ .
$$}
\end{example}

\begin{example}{\rm
We give now the complete construction of the rigged configuration associated to
the tableau $t$ of Example~\ref{EXBIJ1}. One passes from one step to the 
following by application of the previous rules. For the sake of brevity, the matrices
$M$, $P$, $Q$ necessary at each step for the determination of the vacancy and
quantum numbers have not been reproduced.

\bigskip

\centerline{
\begin{picture}(1300,150)
\put(0,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){1}}
\end{picture}}
%
\put(400,0){\begin{picture}(100,350)
\put(0,0){\framebox(50,50){}}
\end{picture}}
\end{picture}}
%

\centerline{
\begin{picture}(1300,150)
\put(0,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){1}}
\put(50,0){\framebox(50,50){1}}
\end{picture}}
%
\put(400,0){\begin{picture}(100,350)
\put(0,0){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\end{picture}}
\end{picture}}
%

\centerline{
\begin{picture}(1300,200)
\put(0,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){1}}
\put(50,0){\framebox(50,50){1}}
\put(0,50){\framebox(50,50){2}}
\end{picture}}
%
\put(400,0){\begin{picture}(100,350)
\put(0,0){\framebox(50,50){}}
\put(0,50){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\end{picture}}
%
\put(600,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){0}}
\put(70,10){0}
\end{picture}}
\end{picture}}
%

\centerline{
\begin{picture}(1300,200)
\put(0,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){1}}
\put(50,0){\framebox(50,50){1}}
\put(100,0){\framebox(50,50){2}}
\put(0,50){\framebox(50,50){2}}
\end{picture}}
%
\put(400,0){\begin{picture}(100,350)
\put(0,0){\framebox(50,50){}}
\put(0,50){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(50,50){\framebox(50,50){}}
\end{picture}}
%
\put(600,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){0}}
\put(70,10){0}
\end{picture}}
\end{picture}}
%

\centerline{
\begin{picture}(1300,250)
\put(0,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){1}}
\put(50,0){\framebox(50,50){1}}
\put(100,0){\framebox(50,50){2}}
\put(150,0){\framebox(50,50){3}}
\put(0,50){\framebox(50,50){2}}
\end{picture}}
%
\put(400,0){\begin{picture}(100,350)
\put(0,0){\framebox(50,50){}}
\put(0,50){\framebox(50,50){}}
\put(0,100){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(50,50){\framebox(50,50){}}
\end{picture}}
%
\put(600,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){0}}
\put(70,10){1}
\end{picture}}
\end{picture}}
%

\centerline{
\begin{picture}(1300,250)
\put(0,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){1}}
\put(50,0){\framebox(50,50){1}}
\put(100,0){\framebox(50,50){2}}
\put(150,0){\framebox(50,50){3}}
\put(200,0){\framebox(50,50){3}}
\put(0,50){\framebox(50,50){2}}
\end{picture}}
%
\put(400,0){\begin{picture}(100,350)
\put(0,0){\framebox(50,50){}}
\put(0,50){\framebox(50,50){}}
\put(0,100){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(50,50){\framebox(50,50){}}
\put(50,100){\framebox(50,50){}}
\end{picture}}
%
\put(600,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){0}}
\put(70,10){1}
\end{picture}}
\end{picture}}
%

\centerline{
\begin{picture}(1300,300)
\put(0,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){1}}
\put(50,0){\framebox(50,50){1}}
\put(100,0){\framebox(50,50){2}}
\put(150,0){\framebox(50,50){3}}
\put(200,0){\framebox(50,50){3}}
\put(0,50){\framebox(50,50){2}}
\put(0,100){\framebox(50,50){4}}
\end{picture}}
%
\put(400,0){\begin{picture}(100,350)
\put(0,0){\framebox(50,50){}}
\put(0,50){\framebox(50,50){}}
\put(0,100){\framebox(50,50){}}
\put(0,150){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(50,50){\framebox(50,50){}}
\put(50,100){\framebox(50,50){}}
\end{picture}}
%
\put(600,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){0}}
\put(0,50){\framebox(50,50){1}}
\put(70,35){1}
\end{picture}}
%
\put(850,0){\begin{picture}(200,100)
\put(0,0){\framebox(50,50){0}}
\put(70,10){0}
\end{picture}}
\end{picture}}
%

\centerline{
\begin{picture}(1300,300)
\put(0,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){1}}
\put(50,0){\framebox(50,50){1}}
\put(100,0){\framebox(50,50){2}}
\put(150,0){\framebox(50,50){3}}
\put(200,0){\framebox(50,50){3}}
\put(0,50){\framebox(50,50){2}}
\put(50,50){\framebox(50,50){4}}
\put(0,100){\framebox(50,50){4}}
\end{picture}}
%
\put(400,0){\begin{picture}(100,350)
\put(0,0){\framebox(50,50){}}
\put(0,50){\framebox(50,50){}}
\put(0,100){\framebox(50,50){}}
\put(0,150){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(50,50){\framebox(50,50){}}
\put(50,100){\framebox(50,50){}}
\put(50,150){\framebox(50,50){}}
\end{picture}}
%
\put(600,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){3}}
\put(0,50){\framebox(50,50){0}}
\put(50,0){\framebox(50,50){}}
\put(120,10){3}
\put(70,60){1}
\end{picture}}
%
\put(850,0){\begin{picture}(200,100)
\put(0,0){\framebox(50,50){0}}
\put(70,10){0}
\end{picture}}
\end{picture}}
%

\centerline{
\begin{picture}(1300,350)
\put(0,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){1}}
\put(50,0){\framebox(50,50){1}}
\put(100,0){\framebox(50,50){2}}
\put(150,0){\framebox(50,50){3}}
\put(200,0){\framebox(50,50){3}}
\put(0,50){\framebox(50,50){2}}
\put(50,50){\framebox(50,50){4}}
\put(0,100){\framebox(50,50){4}}
\put(50,100){\framebox(50,50){5}}
\end{picture}}
%
\put(400,0){\begin{picture}(100,350)
\put(0,0){\framebox(50,50){}}
\put(0,50){\framebox(50,50){}}
\put(0,100){\framebox(50,50){}}
\put(0,150){\framebox(50,50){}}
\put(0,200){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(50,50){\framebox(50,50){}}
\put(50,100){\framebox(50,50){}}
\put(50,150){\framebox(50,50){}}
\end{picture}}
%
\put(600,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){3}}
\put(0,50){\framebox(50,50){0}}
\put(0,100){\framebox(50,50){0}}
\put(50,0){\framebox(50,50){}}
\put(120,10){3}
\put(70,80){0}
\end{picture}}
%
\put(850,0){\begin{picture}(200,100)
\put(0,0){\framebox(50,50){0}}
\put(50,0){\framebox(50,50){}}
\put(120,10){0}
\end{picture}}
\end{picture}}
%

\centerline{
\begin{picture}(1300,350)
\put(0,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){1}}
\put(50,0){\framebox(50,50){1}}
\put(100,0){\framebox(50,50){2}}
\put(150,0){\framebox(50,50){3}}
\put(200,0){\framebox(50,50){3}}
\put(0,50){\framebox(50,50){2}}
\put(50,50){\framebox(50,50){4}}
\put(100,50){\framebox(50,50){5}}
\put(0,100){\framebox(50,50){4}}
\put(50,100){\framebox(50,50){5}}
\end{picture}}
%
\put(400,0){\begin{picture}(100,350)
\put(0,0){\framebox(50,50){}}
\put(0,50){\framebox(50,50){}}
\put(0,100){\framebox(50,50){}}
\put(0,150){\framebox(50,50){}}
\put(0,200){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(50,50){\framebox(50,50){}}
\put(50,100){\framebox(50,50){}}
\put(50,150){\framebox(50,50){}}
\put(50,200){\framebox(50,50){}}
\end{picture}}
%
\put(600,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){2}}
\put(0,50){\framebox(50,50){0}}
\put(0,100){\framebox(50,50){0}}
\put(50,0){\framebox(50,50){}}
\put(100,0){\framebox(50,50){}}
\put(170,10){2}
\put(70,80){0}
\end{picture}}
%
\put(850,0){\begin{picture}(200,100)
\put(0,0){\framebox(50,50){0}}
\put(50,0){\framebox(50,50){}}
\put(120,10){0}
\end{picture}}
\end{picture}}
%

\centerline{
\begin{picture}(1300,400)
\put(0,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){1}}
\put(50,0){\framebox(50,50){1}}
\put(100,0){\framebox(50,50){2}}
\put(150,0){\framebox(50,50){3}}
\put(200,0){\framebox(50,50){3}}
\put(0,50){\framebox(50,50){2}}
\put(50,50){\framebox(50,50){4}}
\put(100,50){\framebox(50,50){5}}
\put(0,100){\framebox(50,50){4}}
\put(50,100){\framebox(50,50){5}}
\put(0,150){\framebox(50,50){6}}
\end{picture}}
%
\put(400,0){\begin{picture}(100,350)
\put(0,0){\framebox(50,50){}}
\put(0,50){\framebox(50,50){}}
\put(0,100){\framebox(50,50){}}
\put(0,150){\framebox(50,50){}}
\put(0,200){\framebox(50,50){}}
\put(0,250){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(50,50){\framebox(50,50){}}
\put(50,100){\framebox(50,50){}}
\put(50,150){\framebox(50,50){}}
\put(50,200){\framebox(50,50){}}
\end{picture}}
%
\put(600,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){2}}
\put(0,50){\framebox(50,50){0}}
\put(0,100){\framebox(50,50){0}}
\put(0,150){\framebox(50,50){0}}
\put(50,0){\framebox(50,50){}}
\put(100,0){\framebox(50,50){}}
\put(170,10){2}
\put(70,105){0}
\end{picture}}
%
\put(850,0){\begin{picture}(200,100)
\put(0,0){\framebox(50,50){0}}
\put(0,50){\framebox(50,50){1}}
\put(50,0){\framebox(50,50){}}
\put(120,10){0}
\put(70,60){1}
\end{picture}}
%
\put(1050,0){\begin{picture}(150,50)
\put(0,0){\framebox(50,50){0}}
\put(70,10){0}
\end{picture}}
\end{picture}}

\centerline{
\begin{picture}(1300,400)
\put(0,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){1}}
\put(50,0){\framebox(50,50){1}}
\put(100,0){\framebox(50,50){2}}
\put(150,0){\framebox(50,50){3}}
\put(200,0){\framebox(50,50){3}}
\put(0,50){\framebox(50,50){2}}
\put(50,50){\framebox(50,50){4}}
\put(100,50){\framebox(50,50){5}}
\put(0,100){\framebox(50,50){4}}
\put(50,100){\framebox(50,50){5}}
\put(0,150){\framebox(50,50){6}}
\put(50,150){\framebox(50,50){6}}
\end{picture}}
%
\put(400,0){\begin{picture}(100,350)
\put(0,0){\framebox(50,50){}}
\put(0,50){\framebox(50,50){}}
\put(0,100){\framebox(50,50){}}
\put(0,150){\framebox(50,50){}}
\put(0,200){\framebox(50,50){}}
\put(0,250){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(50,50){\framebox(50,50){}}
\put(50,100){\framebox(50,50){}}
\put(50,150){\framebox(50,50){}}
\put(50,200){\framebox(50,50){}}
\put(50,250){\framebox(50,50){}}
\end{picture}}
%
\put(600,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){2}}
\put(0,50){\framebox(50,50){4}}
\put(0,100){\framebox(50,50){0}}
\put(0,150){\framebox(50,50){0}}
\put(50,0){\framebox(50,50){}}
\put(50,50){\framebox(50,50){}}
\put(100,0){\framebox(50,50){}}
\put(170,10){2}
\put(120,60){4}
\put(70,130){0}
\end{picture}}
%
\put(850,0){\begin{picture}(200,100)
\put(0,0){\framebox(50,50){0}}
\put(0,50){\framebox(50,50){0}}
\put(50,0){\framebox(50,50){}}
\put(50,50){\framebox(50,50){}}
\put(120,35){0}
\end{picture}}
%
\put(1050,0){\begin{picture}(150,50)
\put(0,0){\framebox(50,50){0}}
\put(50,0){\framebox(50,50){}}
\put(120,10){0}
\end{picture}}
\end{picture}}
}

\bigskip
\end{example}

The most important property of the Kirillov-Reshetikhin bijection is that
the charge of a Young tableau $t$ can be computed very easily from the 
rigged configuration $(\nu , {\cal I})$ to which it corresponds. 

Given a configuration $\nu$ with admissible matrix $M = (m_{ij})$, define
the {\it charge of} $\nu$ (or $M$) by
$$
c(\nu) = c(M) = {1\over 2} \sum_{i,j} m_{ij}(m_{ij} - 1) \ .
$$
Then one can show that 
$$
c(t) = c(\nu) + \sum_{i,j} {\cal I}^i_j \ ,
$$
which yields the following $q$-analogue of \ref{KOSTZ}

\begin{theorem}\label{CHCONF}
The Kostka polynomial $K_{\lambda \mu}(q)$ is equal to
$$
K_{\lambda \mu}(q)= \sum_\nu \prod_{i,j\ge 1} q^{c(\nu)} 
\left[ \matrix{ P_{ij}(\nu) + Q_{ij}(\nu) \cr Q_{ij}(\nu) \cr} \right]_q \ ,
$$
the sum running over all configurations $\nu$ of type $(\lambda ,\, \mu)$.
\end{theorem}

\begin{example}{\rm
Take $\lambda = (8,5,2)$, $\mu = (6,4,3,2)$ as in Example~\ref{EXTH1}.
The admissible matrices corresponding to the two configurations given
in this example are respectively
$$
\pmatrix{2&2&2&1&0&1\cr
		 1&1&1&1&1&0\cr
		 1&1&0&0&0&0\cr
		 }
\ \ \ \ 
\pmatrix{2&2&1&1&1&1\cr
		 1&1&2&1&0&0\cr
	     1&1&0&0&0&0\cr
		  }
\ .
$$
Their charges are both equal to 3, hence
$$
K_{\lambda \mu}(q)= q^3 \left[ \matrix{ 3 \cr 1 \cr} \right]_q \left[ \matrix{ 3 \cr 1 \cr} \right]_q
                   +q^3 \left[ \matrix{ 2 \cr 1 \cr} \right]_q \left[ \matrix{ 2 \cr 1 \cr} \right]_q
= 2q^3 +4q^4 + 4q^5 +2q^6 +q^7 \ .
$$
}\end{example}

An example of application of Theorem~\ref{CHCONF} is the proof by Kirillov of the 
unimodality of generalized Gaussian coefficients \cite{Ki5}. In fact, when $\lambda$
consists of only two parts, \ref{CHCONF} gives a generalization of the KOH formula for
$q$-binomial coefficients.

\section{Specializations at roots of unity}


When $q=-1$, the Hall-Littlewood functions
coincide with those introduced by Schur in his theory of projective
representations of the symmetric group.

The investigation of Hall-Littlewood functions at  other roots of unity has been
initiated by  Morris \cite{Mo2}, in connection with problems in the modular
representation theory of the symmetric group. Let $p$ be a prime, $\zeta$ a primitive
$p$th root of $1$, and $\mu$ a partition with at least one multiplicity
$m_i(\mu) \ge p$. It follows from (\ref{PSYM}) that $Q_{\mu}(X;\zeta)=0$.
On the other hand,
$$
Q_{\mu}(X;q)=\sum_{\lambda}K_{\lambda , \mu}(q)\, s_{\lambda}((1-q)X)
=\sum_{\lambda , \rho}K_{\lambda , \mu}(q)\,{\chi_\rho^\lambda\over z_\rho} \, p_\rho((1-q)X)
$$
$$
=\sum_\rho \left(\sum_\lambda K_{\lambda , \mu}(q)\,\chi_\rho^\lambda\right)
{\prod_i(1-q^{\rho_i})\over z_\rho} \, p_\rho(X) \ .
$$
Hence, for all partitions $\rho$ such that $\rho_i \not \equiv 0 \ \mod p$, one
has
\begin{equation}\label{LINREL}
\sum_{\lambda}K_{\lambda , \mu}(\zeta) \,\chi_\rho^\lambda = 0 \ .
\end{equation}
Denote by $\pi^p(n)$ the set of partitions $\rho$ of $n$ whose parts are not
divisible by $p$, and by $\pi_p(n)$ the set of partitions $\mu$ whose
multiplicities are less than $p$. It is well known that $p^*(n):=|\pi^p(n)|=|\pi_p(n)|$.
The elements of  $\pi^p(n)$ correspond to $p$-regular conjugacy classes
in $\S_n$, that is, classes whose elements have an order prime to $p$,
while $\pi_p(n)$ parametrizes the $p$-modular irreducibles characters.
A basic problem in the $p$-modular representation theory of $\S_n$ is 
to find a complete set of linearly independent relations between the
characters $\chi^\lambda$ restricted to $p$-regular classes $\rho$. The number
of such independent relations being equal to $p(n)-p^*(n)$, the system of
identities (\ref{LINREL}) provides a solution to this question.
Thus, in the case $n=4$, $p=2$, one obtains the three relations
$$
\chi_\rho^{1^4} - \chi_\rho^{211} + 2 \chi_\rho^{22} - \chi_\rho^{31} + \chi_\rho^4 = 0 \ , \ \ \ 
\chi_\rho^{211} - \chi_\rho^{22} - \chi_\rho^4 = 0 \ , \ \ \ 
\chi_\rho^{22}- \chi_\rho^{31} + \chi_\rho^4 = 0 \ ,
$$
for $\rho = (1^4),\ (3,\,1)$.

The problem of specializing Hall-Littlewood functions at roots of
unity is also related to some combinatorial properties of the so-called
{\it cyclic characters} introduced by Foulkes \cite{Fo2}. 
These symmetric functions correspond to
characters of the symmetric group induced by irreducible representations
of cyclic subgroups generated by a full cycle. A combinatorial interpretation of their
coefficients in the basis of Schur functions has been given by Kraskiewicz
and Weyman \cite{KW} in terms of congruence
properties of the major index of permutations, or, which amounts
to the same, charge of standard tableaux. A generalization
of this result has been proposed in \cite{LLT2}, 
in which the coefficients of certain plethysms with the cyclic characters
are interpreted in terms of the charge of more general
tableaux. This result can also be viewed as an isomorphism theorem
for certain submodules of the cohomology of a generalized flag manifold,
or also in terms of harmonic polynomials relative to the symmetric group.

Finally, these theorems can be interpreted in terms of congruence properties of  Kostka-Foulkes polynomials
modulo cyclotomic polynomials. 

We shall review in this Section the main results of \cite{LLT1} and \cite{LLT2}.

The first one is a factorization property of the functions $Q'_\lambda(X,q)$
when $q$ is specialized to a primitive root of unity. This is to be seen as
a generalization of the fact that when $q$ is specialized to $1$ the function
$Q'_{\lambda}(X;q)$ reduces to $h_{\lambda}(X) = \prod_i h_{\lambda_i}(X)$. 


\begin{theorem}\label{THLLT1} 
Let $\lambda = (1^{m_1}2^{m_2} \ldots n^{m_n})$ be a
partition written multiplicatively. 
Set $m_i=kq_i+r_i$ with $0\le r_i<k$, and
$\mu=(1^{r_1}2^{r_2} \ldots n^{r_n})$. Then, $\zeta$ being a primitive
$k$-th root of unity,
\begin{equation}\label{FACT}
Q'_{\lambda}(X;\zeta)=Q'_\mu(X;\zeta)
     \prod_{i\ge 1}\bigl[ Q'_{(i^k)}(X;\zeta)\bigr]^{q_i} \ . 
\end{equation}
\end{theorem}

The functions $Q'_{(i^k)}(X;\zeta)$ appearing in the right-hand side of (\ref{FACT}) 
can be given a more convenient expression.

\begin{theorem}\label{THLLT2} 
Let $p_k\circ h_n$ denote the plethysm of the
complete function $h_n$ by the power-sum $p_k$, which is defined
by the generating series
$\displaystyle \sum_n  p_k\circ h_n(X)\,z^n=\prod_{x\in X}(1-zx^k)^{-1}$.
Then, if $\zeta$ is as above a primitive $k$-th root of unity, one has
$$Q'_{(n^k)}(X;\zeta)=(-1)^{(k-1)n}p_k\circ h_n(X). $$
\end{theorem}

\begin{example}
{\rm With $k=3$ $(\zeta = e^{2i\pi /3})$, we have
$$
Q'_{444433311}(X;\zeta)=Q'_{411}(X;\zeta)\,Q'_{333}(X;\zeta)\,Q'_{444}(X;\zeta)
=Q'_{411}(X;\zeta)\,p_4\circ h_{43} \ .
$$
}
\end{example}

One can derive from \ref{THLLT1}, \ref{THLLT2} the following
results for Green polynomials at roots of unity,
which had been conjectured by Morris and Sultana \cite{MS} \cite{Su}:

\begin{theorem} 
Let $\lambda = (1^{m_1}2^{m_2} \ldots n^{m_n})$ be
a partition, with at least one part $i$ with multiplicity
$m_i\ge k$, and let $\mu=(\mu_1,\ldots,\mu_r)$ be another partition,
with at least one part $\mu_h\equiv 0\  (\mod k)$. Then,
$$X^\lambda_\mu(\zeta) \equiv 0\  (\mod k) \ .$$
\end{theorem}

\begin{theorem}\label{SU2}
Let $\lambda = (1^{m_1}\ldots i^{m_i} \ldots n^{m_n})$, where
for some $i$,
$m_i\ge 1$, $|\lambda|=n$, $\lambda^* = (1^{m_1}\ldots i^{m_i-1} \ldots n^{m_n})$ 
and suppose $n=kr$. Then,
$$X^{(r^k)}_\lambda(\zeta) = (-1)^{(k-1)j}k\ X^{(r-j)^k}_{\lambda^*}(\zeta)   $$
if $i=jk$, and $X^{(r^k)}_\lambda(\zeta)=0$ otherwise.
\end{theorem}

\begin{example}{\rm With $k=4$ $(\zeta=i=\sqrt{-1})$, we have
$$X^{41111}_{422}(i) = \< Q'_{1111} Q'_4 \, , \, p_4 p_{22} \> 
=(-1)^3\< p_4 Q_4'\, ,\, p_4 p_{22} \> $$
$$= -\< Q'_4 \, , \,D_{p_4}(p_4p_{22}) \> =
-\< Q_4'\, ,\, 4 p_{22}\> = -4\<h_4\, , \, p_{22}\>=-4 \ . $$
}\end{example}

Theorem~\ref{SU2} may in fact be generalized as follows.

Given two partitions $\lambda$ and $\mu$, we denote by $\lambda \vee \mu$
the partition obtained by reordering the concatenation of $\lambda$
and $\nu$, {\it e.g.}  $(2,\,2,\,1)\vee (5,\,2,\,1,\,1) = (5,\,2^3,\,1^3)$.
We write $\mu^k=\mu\vee \mu\vee \cdots\vee \mu$
($k$ factors). If $\mu = (\mu_1,\,\ldots ,\,\mu_r)$, we set
$k\mu = (k\mu_1,\,\ldots ,\,k\mu_r)$.
Let $\lambda=\mu^k$, and let $\nu$ be another
partition. The Green polynomial
$X^\lambda_\nu(\zeta)$ can then be expressed by means of the value
of a permutation character of ${\goth{S}}_n$:
$$X^{\mu^k}_\nu(\zeta) = (-1)^{(k-1)|\mu|}\< p_\nu,\ p_k(h_\mu)\>
=(-1)^{(k-1)|\mu|}\< \phi_k(p_\nu),\ h_\mu\> \ , $$
where $\phi_k$ is the adjoint of the linear operator
$\psi^k:\ F\mapsto p_k\circ F$ (Adams operator),
so that:

\begin{theorem} 
$X^{\mu^k}_\nu(\zeta)=0$ when $\nu$ is not of the form
$k\pi$ for
some partition $\pi$, and
$$X^{\mu^k}_{k\pi}(\zeta)=(-1)^{(k-1)|\mu|}k^{\ell(\pi)}\< p_\pi\, ,\, h_\mu \>\ .$$
In particular, $X^{(r^k)}_{k\pi}(\zeta)=(-1)^{(k-1)r}k^{\ell(\pi)}$.
\end{theorem}

\begin{example}
{\it (i)} \rm With $k=4$ ($\zeta=i$), $X^{2222}_{422}(i)
=\< p_4(h_2),\ p_{422}\>=0$ and 
$$X^{42}_{44}(i)= \< h_2,\ \phi_4(p_{44})\>=\< h_2,\ 16p_{11}\> = 16\ .$$

{\it (ii)} With $k=3$ ($\zeta=e^{2\pi i/3}$),
$$X^{333222}_{933}(\zeta)= +3^3\< p_{311},\ h_{23}\>=
3^3\< p_{11}, \ h_2D_{p_3}h_3\> = 27\ .$$
\end{example}


To state our next result, we recall some definitions from number theory.
For $k,n\in {\bf N}$, the \it Ramanujan \rm (or \it Von Sterneck\rm)
\it sum \rm $c(k,n)$ (also denoted $\Phi(k,n)$) is the sum of the
$k$-th powers of the \it primitive \rm $n$-th roots of unity.  Its value
is given by \it H\"older's formula\rm: if $(k,n)=d$ and $n=md$, then
$c(k,n)=\mu(m)\phi(n)/\phi(m)$, where $\mu$ is the Moebius function and
$\phi$ is the Euler totient function (see {\it e.g.} \cite{HW} or \cite{NV}).

Let $P(q)= \sum_{k=0}^{n-1}a_k\,q^k \ \in \Z[q]$ be
a polynomial of degree $\le n-1$. $P$ is said to be \it even modulo $n$ \rm
if $(i,n)=(j,n)\ \Rightarrow a_i=a_j$. 
The following result, due to
E. Cohen (\cite{Co}, see also \cite{De} for a simpler proof), provides a
generalization of the Moebius inversion formula:
\begin{lemma}
The polynomial $P$ is even modulo $n$ iff for
every divisor $d$ of $n$, the residue of $P(q)$ modulo the cyclotomic
polynomial $\Phi_d(q)$ is a constant $r_d\in{\bb Z}$. In this case, one has
$$
a_k={{1}\over{n}}\sum_{d\mid n}
                  c(k,d)r_d \ , \ \ \ \ 
              r_d=\sum_{t\mid n}c(n/d,t)a_{n/t}\ .
$$
\end{lemma}

With the aid of Ramanujan sums, we define the symmetric functions
\begin{equation}
\ell^{(k)}_n={{1}\over{n}}\sum_{d\mid n}c(k,d)p_d^{n/d} \ . 
\end{equation}
These functions were first obtained by Foulkes as Frobenius characteristics
of the representations of the symmetric group induced by irreducible
representations of a  cyclic subgroup generated by an $n$-cycle \cite{Fo2}.
A combinatorial interpretation of the multiplicity $\<s_\lambda\, ,\, \ell^{(k)}_n\>$
has been given by Kraskiewicz and Weyman \cite{KW}. This result is equivalent
to the congruence
$$
Q'_{1^n}(X;q) \equiv \sum_{0\le k \le n-1} q^k \ell_n^{(k)} \ (\mod 1-q^n) \ .
$$
A proof using
Cohen's formula can be found in
\cite{De}. Adapting this argument to our case, we arrive at
the following generalization of the result of \cite{KW}:
\begin{theorem}
 Let $e_i$ be the $\ i$-th elementary symmetric
function, and for $\lambda=(\lambda_1,\ldots,\lambda_m)$, $e_\lambda=
e_{\lambda_1}\cdots e_{\lambda_r}$.
Then, the multiplicity $\<s_\mu\, ,\,\ell^{(r)}_k\circ e_\lambda\>$
of the Schur function $s_\mu$ in the plethysm $\ell^{(r)}_k\circ e_\lambda$
is equal to the number of Young tableaux of shape $\mu'$ (conjugate
partition) and weight $\lambda^k$ whose charge is congruent to $r$ modulo $k$.
\end{theorem}

\begin{example}{ \rm With $k=4$, $r=2$ and $\lambda=(2)$,
$$\ell^{(2)}_4\circ e_2 = s_{431} +s_{422} +s_{41111}+2s_{3311}+2s_{3221}$$
$$+2s_{32111} +s_{2222}+s_{22211}+2s_{221111}+s_{2111111} \ .$$
To compute the coefficient $\<s_{32111}\, ,\, \ell^{(2)}_4\circ e_2\>=2$, we have
to find the number of tableaux of shape $(3,\,2,\,1,\,1,\,1)'=(5,\,2,\,1)$, weight $(2,\,2,\,2,\,2)$
and charge $\equiv 2\ (\mod 4)$. The two tableaux satisfying
these constraints are:

\centerline{
\begin{picture}(650,250)
\put(0,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){1}}
\put(50,0){\framebox(50,50){1}}
\put(100,0){\framebox(50,50){2}}
\put(150,0){\framebox(50,50){3}}
\put(200,0){\framebox(50,50){4}}
\put(0,50){\framebox(50,50){2}}
\put(50,50){\framebox(50,50){4}}
\put(0,100){\framebox(50,50){3}}
\end{picture}}
\put(400,0){\begin{picture}(250,200)
\put(0,0){\framebox(50,50){1}}
\put(50,0){\framebox(50,50){1}}
\put(100,0){\framebox(50,50){2}}
\put(150,0){\framebox(50,50){3}}
\put(200,0){\framebox(50,50){4}}
\put(0,50){\framebox(50,50){2}}
\put(50,50){\framebox(50,50){3}}
\put(0,100){\framebox(50,50){4}}
\end{picture}}
\end{picture}
}

\bigskip\noindent
which both have charge equal to $6$. \par
Similarly, the reader can check that $\<s_{732}\, ,\, \ell^{(2)}_4\circ e_{21}\>=5$
is the number of tableaux with shape $(3,\,3,\,2,\,1,\,1,\,1,\,1)$, weight $(2,\,2,\,2,\,2,\,1,\,1,\,1,\,1)$ and
charge $\equiv 2\ (\mod 4)$.
}
\end{example}

A related result (see \eg \cite{MT}), gives an interpretation
of the cyclic characters $\ell^{(k)}_n$ in terms of 
$\S_n$-harmonic polynomials: let
$H^k$ be the Frobenius characteristic of the homogeneous component
${\cal H}^k$ of degree $k$ of the module ${\cal H}$ of
$\S_n$-harmonic polynomials. Then,
$$\ell^{(k)}_n=\sum_{i\equiv k\ (\mod n)}H^i \ . $$


More generally, the plethysm $\ell^{(j)}_k\circ e_\lambda$ can be expressed
as a positive sum of Frobenius characteristics of modules of harmonic polynomials.
Recall that to each partition $\mu$ of $n$, it is possible to associate a certain
submodule $L_\mu$ of ${\cal H}_n$ with graded characteristic
\begin{equation}\label{HMU}
\F_q(L_\mu) =\tilde Q'_\mu(X;q) = \sum_k q^k H_\mu^k(X) \ .
\end{equation}



\begin{theorem}
Let $\mu=\lambda^k$. Then,
$$\ell^{(j)}_k\circ e_\lambda= \sum_{i\equiv j\ (\mod k)}H^i_\mu \ .
$$
\end{theorem}

\begin{example} {\rm The character of the
preceding example decomposes into three parts
$$\ell^{(2)}_4\circ e_2=H^2_{2222}+
H^6_{2222}+H^{10}_{2222},$$
the three components being
$$H^2_{2222}=s_{221111} +s_{2111111} \ ,$$
$$H^6_{2222}=s_{3311}+2s_{3221}+s_{2222}+s_{41111}+2s_{32111}+s_{22211} +s_{221111}\ ,
$$
$$H^{10}_{2222}= s_{431}+s_{422}+s_{3311} \ .
$$
}
\end{example}

Theorems \ref{THLLT1}, \ref{THLLT2} may also be stated in terms of 
specialization of Kostka-Foulkes polynomials at roots of unity, or
equivalently, in terms of congruence properties of the 
$K_{\lambda , \mu}(q)$ modulo cyclotomic polynomials.


\begin{theorem}\label{CONG1}
For any partition $\lambda$ with $|\lambda|=kn$,
$$
K_{\lambda , n^k}(q) \equiv (-1)^{(k-1)n}\,s_\lambda (1,\, q,\, q^2 ,\, \ldots ,\,q^{k-1})\ (\mod \Phi_k(q))
$$
and more generally, for any partition $\mu$ with $|\mu|=n$,
$$
K_{\lambda , \mu^k}(q) \equiv (-1)^{(k-1)|\mu|}\,(h_{k\mu}*s_\lambda)(1,\, q,\, q^2 ,\, \ldots ,\,q^{k-1})\ (\mod \Phi_k(q))\ .
$$
\end{theorem}

We mention that a different type of congruence follows from results of
Stanley \cite{Sta84} and Gupta \cite{Gupta1}, that is, for $\beta_1=n$
and 
$$\lambda = [\alpha ,\, \beta ]_k := (\alpha_1 + n,\ldots , \alpha_s + n , 
n, \ldots , n, n-\beta_t , n-\beta_{t-1} , \ldots , n-\beta_2 , 0) $$
then (\cf \cite{Ki4})
$$K_{\lambda,(n^k)}(q) \equiv (s_\alpha * s_\beta)(q,\,\ldots ,\, q^{k-1})\ (\mod q^k) \ .
$$
 
Theorem~\ref{CONG1} gives some congruences modulo cyclotomic polynomials
for certain co\-lumns of the $q$-Kostka matrix. We can also derive from
\ref{THLLT1}, \ref{THLLT2}
other congruences for certain rows of the same matrix.

Let $\rho_n$ be the staircase partition $(n,\ldots ,2,\,1)$.
It is well-known that for $k=2$ ($\zeta=-1$), one has $s_{\rho_n}(X)=
P_{\rho_n}(X;-1)$, the staircase $P$-Schur function. More generally, 
it can be shown that if $\zeta$ is a
primitive $k$-th root of unity, $P_{\rho^{k-1}_n}(X;\zeta)=
s_{\rho^{k-1}_n}(X)$. This is a consequence of the following result:

\begin{theorem} 
Let $\zeta$ be a primitive $k$-th root of $1$, and
$\lambda$ be a partition such that $\ell(\lambda')\le n$. Then,
$$s_{\lambda^k\vee\rho^{k-1}_n}(X)
=\sum_\mu K_{\lambda \mu}\ P_{\mu^k\vee\rho^{k-1}_n}(X;\zeta) $$
where $K_{\lambda \mu}$ are the usual Kostka numbers. In other words, we have
the following congruence modulo the cyclotomic polynomial $\Phi_k(q)$:
$$K_{\lambda^k\vee\rho^{k-1}_n,\ \nu}(q) \equiv
\left\{\matrix{
               K_{\lambda \mu} & {\it if} & \nu=\mu^k\vee\rho^{k-1}_n \cr
               0      & {\it otherwise.} & \cr
               }\right. $$
\end{theorem}

\begin{example}{\rm Take $k=3$, $n=3$, $I=(3,2)$ and $J=(2,2,1)$.
Then,
$$K_{333332222211,332222222211111}(q) =
  q^3 ( 1+ 2q  +6q^2  + 13 q^3  + 24q^4 + 39 q^5 $$
$$ +59 q^6  +   81  q^7 +  105 q^8  + 128  q^9 
+148 q^{10} +163 q^{11}  +171q^{12} + 172 q^{13}  +165 q^{14}
+  153 q^{15}  +   134 q^{16}$$
$$   +114 q^{17}  + 92 q^{18}  + 72 q^{19}
+   53 q^{20} + 38 q^{21} + 25 q^{22}  +16  q^{23}  + 9  q^{24}  
+ 5  q^{25}  + 2 q^{26}    +q^{27}    )$$
$$\equiv K_{32,221} =2 \ (\mod 1+q+q^2) \ . $$}
\end{example}

An alternative and more combinatorial formulation of Theorems \ref{THLLT1} and 
\ref{THLLT2} may be presented by introducing the notion of {\it ribbon tableau}.

Recall that to a partition $\lambda$ is associated a $k$-core $\lambda_{(k)}$
and a $k$-quotient $\lambda^{(k)}$
\cite{JK}. The $k$-core is the unique partition obtained by successively removing 
$k$-ribbons (or skew hooks) from $\lambda$. The different possible ways of 
doing so can be distinguished from one another by labelling $1$ the
last ribbon removed, $2$ the penultimate, and so on. Thus Figure~\ref{TRIBB}
shows two different ways of reaching the $3$-core $\lambda_{(3)}=(2,\,1^2)$
of $\lambda = (8,\, 7^2,\,4,\,1^5)$. These pictures represent two $3$-ribbon 
tableaux $T_1,\,T_2$ of shape $\lambda/\lambda_{(3)}$ and weight $\mu = (1^9)$.

\begin{figure}[t]
\setlength{\unitlength}{0.25pt}
\centerline{
\begin{picture}(1400,500)(0,0)
%
\put(0,10){$T_1 =$}
\put(120,0){\begin{picture}(400,450)
\put(0,0){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(0,50){\framebox(50,50){}}
\put(0,100){\framebox(50,50){}}
\put(100,0){\framebox(150,50){}}
\put(0,150){\framebox(50,150){}}
\put(0,300){\framebox(50,150){}}
\put(50,150){\framebox(150,50){}}
\put(200,100){\framebox(150,50){}}
\put(150,50){\line(0,1){50}}
\put(150,100){\line(-1,0){50}}
\put(100,100){\line(0,1){50}}
\put(200,50){\line(0,1){50}}
\put(300,0){\line(0,1){100}}
\put(350,50){\line(0,1){50}}
\put(350,50){\line(1,0){50}}
\put(400,0){\line(0,1){50}}
\put(250,0){\line(1,0){150}}
\put(165,10){1}
\put(65,60){2}
\put(115,110){3}
\put(15,160){4}
\put(215,60){5}
\put(165,160){6}
\put(315,10){7}
\put(15,310){8}
\put(265,110){9}
\end{picture}}
%
\put(880,10){$T_2 = $}
\put(1000,0){\begin{picture}(400,450)
\put(0,0){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(0,50){\framebox(50,50){}}
\put(0,100){\framebox(50,50){}}
\put(250,0){\framebox(150,50){}}
\put(0,150){\framebox(50,150){}}
\put(0,300){\framebox(50,150){}}
\put(50,150){\framebox(150,50){}}
\put(200,100){\framebox(150,50){}}
\put(50,100){\framebox(150,50){}}
\put(200,50){\framebox(150,50){}}
\put(150,0){\line(0,1){100}}
\put(250,0){\line(0,1){50}}
\put(100,0){\line(1,0){150}}
\put(165,10){4}
\put(65,60){2}
\put(115,110){6}
\put(15,160){1}
\put(215,60){7}
\put(165,160){8}
\put(315,10){5}
\put(15,310){3}
\put(265,110){9}
\end{picture}}
%
\end{picture}}
\caption{\label{TRIBB}}
\end{figure}

To define  $k$-ribbon tableaux of general weight and shape, we need some terminology.
The {\it initial cell} of a $k$-ribbon $R$ is its rightmost and bottommost
cell. Let $\theta = \beta/\alpha$ be a skew shape, and set 
$\alpha_+ = (\beta_1)\vee \alpha$, so that $\alpha_+/\alpha$ is the horizontal
strip made of the bottom cells of the columns of $\theta$. We say that $\theta$
is a {\it horizontal $k$-ribbon strip} of weight $m$, if it can be tiled by
$m$ $k$-ribbons the initial cells of which lie in $\alpha_+/\alpha$. (One can
check that if such a tiling exists, it is unique).


  

Now, a {\it $k$-ribbon tableau} $T$ of shape $\lambda/\nu$ and weight
$\mu=(\mu_1,\,\ldots ,\,\mu_r)$ is defined as a chain of partitions
$$
\nu=\alpha^0\subset \alpha^1 \subset \cdots \subset \alpha^r=\lambda
$$
such that $\alpha^i/\alpha^{i-1}$ is a horizontal $k$-ribbon strip of weight
$\mu_i$. Graphically, $T$ may be described by numbering each $k$-ribbon of 
$\alpha^i/\alpha^{i-1}$ with the number $i$. We denote by 
$\tab_k(\lambda/\nu,\,\mu)$ the
set of $k$-ribbon tableaux of shape $\lambda/\nu$ and weight $\mu$, and we set
$$
K_{\lambda/\nu,\,\mu}^{(k)} = |\tab_k(\lambda/\nu,\,\mu)| \ .
$$
Finally we recall the definition of the $k$-sign $\epsilon_k(\lambda/\nu)$. Define
the sign of a ribbon $R$ as $(-1)^{h-1}$, where $h$ is the height of $R$. The
$k$-sign $\epsilon_k(\lambda/\nu)$ is the product of the signs of all the ribbons
of a $k$-ribbon tableau of shape $\lambda/\nu$ (this does not depend on the
particular tableau chosen, but only on the shape).

The origin of these combinatorial definitions is best understood by analyzing
carefully the operation of multiplying a Schur function $s_\nu$ by a plethysm
of the form $p_k \circ h_\mu$. Equivalently, thanks to the involution $\omega$,
one may rather consider a product of the type $s_\nu \, [p_k\circ e_\mu]$. To this end,
since
$$
p_k\circ e_\mu = (e_{\mu_1}\circ p_k)\, \cdots (e_{\mu_n}\circ p_k)
= m_{k^{\mu_1}}\cdots m_{k^{\mu_n}} 
$$
one needs only to apply repeatedly the following multiplication rule due
to Muir \cite{Mu} (see also \cite{Li3}):
$$
s_\nu \, m_\alpha = \sum_\beta s_{\nu + \beta} \ ,
$$
sum over all distinct permutations $\beta$ of 
$(\alpha_1,\,\alpha_2,\,\ldots ,\, \alpha_n,\,0,\,\ldots \, )$.
Here, as in the right-hand side of (\ref{PARTF}), the Schur functions 
$s_{\nu + \beta}$ are not necessary indexed by partitions and have therefore
to be standardized, this reduction yielding only a finite number of nonzero
summands. For example,
$$
s_{31}\,m_3 = s_{61} + s_{313} + s_{31003} = s_{61} - s_{322} + s_{314} \ .
$$
Other terms such as $s_{34}$ or $s_{3103}$
reduce to $0$. It is easy to deduce
from this rule that the multiplicity
$$
\< s_\nu \, m_{k^{\mu_i}} \, , \, s_\lambda \>
$$
is nonzero iff $\lambda '/\mu '$ is a horizontal $k$-ribbon strip of weight
$\mu_i$, in which case it is equal to $\epsilon_k(\lambda/\nu)$. Hence, applying
$\omega$ we arrive at the expansion
$$
s_\nu \, [p_k\circ h_\mu] = \sum_\lambda \epsilon_k(\lambda/\mu) \, 
K_{\lambda/\nu \,, \mu}^{(k)} \, s_\lambda
$$
from which we deduce by \ref{THLLT1}, \ref{THLLT2} that
$$
K_{\lambda \, \mu}^{(k)} = (-1)^{(k-1)|\mu|} \, \epsilon_k(\lambda) 
\, K_{\lambda \, \mu^k}(\zeta)
$$
and more generally, defining as in \cite{KR} the skew Kostka-Foulkes polynomial
$K_{\lambda/\nu \,, \alpha}(q)$ by
$$
K_{\lambda/\nu \,, \alpha}(q) = \< s_{\lambda/\nu} \, , \, Q'_\alpha(q) \>
$$
we can write
$$
K_{\lambda/\nu \,, \mu}^{(k)} = (-1)^{(k-1)|\mu|} \, \epsilon_k(\lambda/\nu) 
\, K_{\lambda/\nu \,, \mu^k}(\zeta) \ .
$$

It turns out that enumerating $k$-ribbon tableaux is equivalent to enumerating
$k$-uples of ordinary Young tableaux, as shown by the correspondence to be described
now. This bijection was first studied by Stanton and White \cite{SW} in the case
of ribbon tableaux of right shape $\lambda$ (without $k$-core) and standard
weight $\mu = (1^n)$ (see also \cite{FS}). We need some additional definitions.


Let $R$ be a $k$-ribbon of a $k$-ribbon tableau. $R$ contains a unique cell 
with coordinates $(x,\,y)$ 
such that $y-x\equiv 0 \ (\mod k)$. We decide to write in this cell the number attached to
$R$, and we define the {\it type} $i\in \{0,\,1,\,\ldots ,\,k-1\}$
of $R$ as the distance between this cell and the initial cell of $R$.
For example, the $3$-ribbons of 
$T_1$ are divided up into three classes:
\begin{itemize}
\item 4, 6, 8, of type 0;
\item 1, 2, 7, 9, of type 1;
\item 3, 5, of type 2.
\end{itemize}
Define the {\it diagonals} of a $k$-ribbon tableau as the sequences of integers
read along the straight lines $D_i \, : \, y-x = ki $.
Thus $T_1$ has the sequence of diagonals 
$$((8),\,(4),\, (2,\,3,\,6),\,
(1,\,5,\,9),\,(7))\ .$$
This definition applies in particular to $1$-ribbon tableaux, {\it i.e.} ordinary
Young tableaux. It is obvious that a Young tableau is uniquely determined
by its sequence of diagonals. Hence, we can associate to a given $k$-ribbon tableau $T$ of
shape $\lambda/\nu$ a $k$-uple $(t_0,\,t_1,\,\ldots ,\,t_{k-1})$ of 
Young tableaux defined as follows; the diagonals of $t_i$ are obtained by erasing
in the diagonals of $T$ the labels of all the ribbons of type $\not = i$.
For instance, if $T=T_1$ the first ribbon tableau of Figure~\ref{TRIBB}, the sequence of
diagonals of $t_1$ is $\left((2),\,(1,\,9),\,(7)\right)$, and 

\centerline{
\begin{picture}(300,150)
\put(100,0){\begin{picture}(100,100)
\put(0,0){\framebox(50,50){1}}
\put(50,0){\framebox(50,50){7}}
\put(0,50){\framebox(50,50){2}}
\put(50,50){\framebox(50,50){9}}
\end{picture}}
\put(0,20){$t_1 =$}
\end{picture}
}

\bigskip
\noindent
The complete triple $(t_0,\,t_1,\,t_2)$ of Young tableaux associated to $T_1$ is

\centerline{
\begin{picture}(700,150)
\put(150,0){\begin{picture}(100,100)
\put(0,0){\framebox(50,50){4}}
\put(50,0){\framebox(50,50){6}}
\put(0,50){\framebox(50,50){8}}
\end{picture}}
%
\put(320,0){\begin{picture}(100,100)
\put(0,0){\framebox(50,50){1}}
\put(50,0){\framebox(50,50){7}}
\put(0,50){\framebox(50,50){2}}
\put(50,50){\framebox(50,50){9}}
\end{picture}}
%
\put(490,0){\begin{picture}(100,100)
\put(0,0){\framebox(50,50){3}}
\put(50,0){\framebox(50,50){5}}
\end{picture}}
\put(0,40){$\tau^1 =$}
\put(110,40){$\Big( $}
\put(270,40){,}
\put(440,40){,}
\put(610,40){$\Big) $}
\end{picture}}

\bigskip
\noindent
whereas that corresponding to $T_2$ is

\centerline{
\begin{picture}(700,150)
\put(150,0){\begin{picture}(100,100)
\put(0,0){\framebox(50,50){1}}
\put(50,0){\framebox(50,50){8}}
\put(0,50){\framebox(50,50){3}}
\end{picture}}
%
\put(320,0){\begin{picture}(100,100)
\put(0,0){\framebox(50,50){4}}
\put(50,0){\framebox(50,50){5}}
\put(0,50){\framebox(50,50){6}}
\put(50,50){\framebox(50,50){9}}
\end{picture}}
%
\put(490,0){\begin{picture}(100,100)
\put(0,0){\framebox(50,50){2}}
\put(50,0){\framebox(50,50){7}}
\end{picture}}
\put(0,40){$\tau^2 =$}
\put(110,40){$\Big( $}
\put(270,40){,}
\put(440,40){,}
\put(610,40){$\Big) $}
\end{picture}}

\bigskip
\noindent
One can show that if $\nu =\lambda_{(k)}$, the $k$-core of $\lambda$,
the $k$-uple of shapes $(\lambda^0,\, \lambda^1,\, \ldots,\,\lambda^{k-1})$
of $(t_0,\,t_1,\,\ldots ,\,t_{k-1})$ depends only on the shape $\lambda$ of
$T$, and is equal to the $k$-quotient $\lambda^{(k)}$ of $\lambda$. 
Moreover the correspondence $T \longrightarrow (t_0,\,t_1,\,\ldots ,\,t_{k-1})$ establishes a
bijection between the set of $k$-ribbon tableaux of shape $\lambda/\lambda_{(k)}$
and weight $\mu$, and the set of $k$-uples of Young tableaux of
shapes $(\lambda^0,\,\ldots ,\,\lambda^{k-1})$ and weights $(\mu^0,\, \ldots ,\,\mu^{k-1})$
with $\mu_i = \sum_j \mu^j_i$. 
(See \cite{SW} or \cite{FS}
for a proof in the case when $\lambda_{(k)}= (0)$ and $\mu = (1^n)$).

For example, keeping $\lambda = (8,\, 7^2,\,4,\,1^5)$, the triple

\centerline{
\begin{picture}(700,150)
\put(150,0){\begin{picture}(100,100)
\put(0,0){\framebox(50,50){3}}
\put(50,0){\framebox(50,50){3}}
\put(0,50){\framebox(50,50){4}}
\end{picture}}
%
\put(320,0){\begin{picture}(100,100)
\put(0,0){\framebox(50,50){1}}
\put(50,0){\framebox(50,50){3}}
\put(0,50){\framebox(50,50){2}}
\put(50,50){\framebox(50,50){4}}
\end{picture}}
%
\put(490,0){\begin{picture}(100,100)
\put(0,0){\framebox(50,50){2}}
\put(50,0){\framebox(50,50){3}}
\end{picture}}
\put(0,40){$\tau =$}
\put(110,40){$\Big( $}
\put(270,40){,}
\put(440,40){,}
\put(610,40){$\Big) $}
\end{picture}}

\bigskip
\noindent
with weights $\left( (0,\,0,\,2,\,1),\,(1,\,1,\,1,\,1),\,(0,\,1,\,1,\,0)\right)$
corresponds to the 3-ribbon tableau 

\centerline{
\begin{picture}(550,500)(0,0)
%
\put(0,10){$T =$}
\put(120,0){\begin{picture}(400,450)
\put(0,0){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(0,50){\framebox(50,50){}}
\put(0,100){\framebox(50,50){}}
\put(100,0){\framebox(150,50){}}
\put(0,150){\framebox(50,150){}}
\put(0,300){\framebox(50,150){}}
\put(50,150){\framebox(150,50){}}
\put(200,100){\framebox(150,50){}}
\put(150,50){\line(0,1){50}}
\put(150,100){\line(-1,0){50}}
\put(100,100){\line(0,1){50}}
\put(200,50){\line(0,1){50}}
\put(300,0){\line(0,1){100}}
\put(350,50){\line(0,1){50}}
\put(350,50){\line(1,0){50}}
\put(400,0){\line(0,1){50}}
\put(250,0){\line(1,0){150}}
\put(165,10){1}
\put(65,60){2}
\put(115,110){2}
\put(15,160){3}
\put(215,60){3}
\put(165,160){3}
\put(315,10){3}
\put(15,310){4}
\put(265,110){4}
\end{picture}}
\end{picture}}

\bigskip
\noindent
of weight $\mu=(1,\,2,\,4,\,2)$.

As before, the significance of this combinatorial construction becomes clearer
once interpreted in terms of symmetric functions. Recall the definition of
$\phi_k$, the adjoint of the linear operator 
$\psi^k:\ F\mapsto p_k\circ F$ acting on the space of symmetric functions.
In other words, $\phi_k$ is characterized by
$$
\< \phi_k(F) \, , \, G \> = \< F \, , \, p_k \circ G \> \ , \ \ \  F,\,G \in \sym \ .
$$
Littlewood has shown \cite{Li3} that if $\lambda$ is a partition whose
$k$-core $\lambda_{(k)}$ is null, then
\begin{equation}\label{PHIQUOT}
\phi_k(s_\lambda) = \epsilon_k(\lambda) \, s_{\lambda^0} \, s_{\lambda^1} \, \cdots
\, s_{\lambda^{k-1}}
\end{equation}
where $\lambda^{(k)} = (\lambda^0 ,\, \ldots \, ,\, \lambda^{k-1} )$ is the
$k$-quotient. Therefore, 
$$
K_{\lambda \, \mu}^{(k)} = \epsilon_k(\lambda) \, \< p_k \circ h_\mu \, , \, s_\lambda \>
= \epsilon_k(\lambda) \, \< \phi_k(s_\lambda) \, , \, h_\mu \>
= \< s_{\lambda^0} \, s_{\lambda^1} \, \cdots
\, s_{\lambda^{k-1}} \, , \, h_\mu \>
$$
is the multiplicity of the weight $\mu$ in the product of Schur functions
$s_{\lambda^0} \, \cdots \, s_{\lambda^{k-1}}$, that is, is equal to the number of 
$k$-uples of Young tableaux of shapes $(\lambda^0,\,\ldots ,\,\lambda^{k-1})$ and 
weights $(\mu^0,\, \ldots ,\,\mu^{k-1})$ with $\mu_i = \sum_j \mu^j_i$. Thus, the
bijection described above gives a combinatorial proof of (\ref{PHIQUOT}).

More generally, if $\lambda$ is replaced by a skew partition $\lambda/\nu$,
(\ref{PHIQUOT}) becomes \cite{KSW}
$$
\phi_k(s_{\lambda/\nu}) = \epsilon_k(\lambda/\nu) \, s_{\lambda^0/\nu^0} \, 
s_{\lambda^1/\nu^1} \, \cdots \, s_{\lambda^{k-1}/\nu^{k-1}}
$$
if $\lambda_{(k)} = \nu_{(k)}$, and $0$ otherwise. This can also be deduced from the 
previous combinatorial correspondence, but we shall not go into further details.

Returning to Kostka polynomials, we may summarize this discussion by stating 
Theorems~\ref{THLLT1} and \ref{THLLT2} in the following way:

\begin{theorem}
Let $\lambda$ and $\nu$ be partitions and set $\nu = \mu^k \vee \alpha$ with
$m_i(\alpha) < k$. Denoting by $\zeta$ a primitive $k$th root of unity, one
has
\begin{equation}\label{KOSTROOT}
K_{\lambda,\,\nu}(\zeta) = (-1)^{(k-1)|\mu|} 
\sum_\beta \epsilon_k(\lambda/\beta)\, K_{\lambda/\beta,\,\mu}^{(k)}\,
K_{\beta,\,\alpha}(\zeta) \ .
\end{equation}
\end{theorem}

\begin{example}{\rm We take $\lambda = (4^2,\,3)$, $\nu = (2^2,\,1^7)$ and
$k=3$ $(\zeta = e^{2i\pi/3})$. In this case, 
$\nu= \mu^k \vee \alpha$ with $\mu = (1^2)$ and
$\alpha = (2^2,\,1)$. The summands of (\ref{KOSTROOT}) are parametrized
by the $3$-ribbon tableaux of external shape $\lambda$ and weight $\mu$.
Here we have three such tableaux:

\centerline{
\begin{picture}(800,250)
\put(0,0){\begin{picture}(200,150)
\put(0,0){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(100,0){\framebox(50,50){}}
\put(150,0){\framebox(50,50){}}
\put(0,50){\framebox(50,50){}}
\put(0,0){\line(1,0){200}}
\put(0,100){\line(1,0){200}}
\put(0,0){\line(0,1){100}}
\put(200,0){\line(0,1){100}}
\put(50,50){\framebox(150,50){}}
\put(0,100){\framebox(150,50){}}
\put(65,60){1}
\put(115,110){2}
\end{picture}}
%
\put(300,0){\begin{picture}(200,150)
\put(0,0){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(100,0){\framebox(50,50){}}
\put(150,0){\framebox(50,50){}}
\put(0,50){\framebox(50,50){}}
\put(0,0){\line(1,0){200}}
\put(0,150){\line(1,0){150}}
\put(0,100){\line(1,0){50}}
\put(50,50){\line(0,1){50}}
\put(50,50){\line(1,0){150}}
\put(100,50){\line(0,1){100}}
\put(0,0){\line(0,1){150}}
\put(200,0){\line(0,1){100}}
\put(150,150){\line(0,-1){50}}
\put(150,100){\line(1,0){50}}
\put(65,60){1}
\put(115,110){2}
\end{picture}}
%
\put(600,0){\begin{picture}(200,150)
\put(0,0){\framebox(50,50){}}
\put(50,0){\framebox(50,50){}}
\put(100,0){\framebox(50,50){}}
\put(50,50){\framebox(50,50){}}
\put(0,50){\framebox(50,50){}}
\put(0,0){\line(1,0){200}}
\put(0,100){\line(1,0){200}}
\put(0,0){\line(0,1){100}}
\put(200,0){\line(0,1){100}}
\put(150,0){\line(0,1){50}}
\put(150,50){\line(-1,0){50}}
\put(100,50){\line(0,1){50}}
\put(0,100){\framebox(150,50){}}
\put(165,10){1}
\put(115,110){2}
\end{picture}}
%
\end{picture}}

\bigskip\noindent
so that 
$$
K_{443,\,221111111}(\zeta) = 2 K_{41,\,221}(\zeta) - K_{32,\,221}(\zeta)
= 2(\zeta^2 + \zeta^3) - (\zeta + \zeta^2) = 2\zeta^2 + 3\ .
$$
}
\end{example}

When $|\alpha|\le |\lambda_{(k)}|$, (\ref{KOSTROOT}) becomes simpler. For  
if $|\alpha| < |\lambda_{(k)}|$ then $K_{\lambda,\,\nu}(\zeta) = 0$, and
otherwise the sum reduces to one single term
$$
K_{\lambda,\,\nu}(\zeta) = (-1)^{(k-1)|\mu|}
\epsilon_k(\lambda/\lambda_{(k)})\, K_{\lambda/\lambda_{(k)},\,\mu}^{(k)}\,
K_{\lambda_{(k)},\,\alpha}(\zeta) \ .
$$
In particular, if $\nu = (1^n)$, one recovers the following theorem of Morris and
Sultana \cite{MS}.
\begin{theorem}
Let $\lambda$ be a partition of $n$ and $\zeta$ a primitive $k$th root of unity. 
Denote by $H(\lambda^{(k)})$ the product of the hook-lengths of the $k$
partitions $\lambda^0,\,\ldots ,\,\lambda^{k-1}$, and by $|\lambda^{(k)}|$ the
sum of their weights.
Set $n=kq+r$, $0\le r <k$. If $r \not = |\lambda_{(k)}|$, 
then $K_{\lambda,\,(1^n)}(\zeta) =0$, otherwise,
$$
K_{\lambda,\,(1^n)}(\zeta) = (-1)^{(k-1)q}
\epsilon_k(\lambda/\lambda_{(k)})\, {|\lambda^{(k)}|!\over H(\lambda^{(k)})}\,
K_{\lambda_{(k)},\,1^r}(\zeta) \ .
$$
\end{theorem}
Indeed, the correspondence we have just described between $k$-ribbon tableaux
and $k$-uples of Young tableaux shows at once, in view of the classical
hook-formula \cite{JK}, that
$$
K_{\lambda/\lambda_{(k)},\,1^q}^{(k)} = {|\lambda^{(k)}|!\over H(\lambda^{(k)})} \ .
$$




\section{Schur $P$-functions}

As mentionned before, the specialization of Hall-Littlewood functions 
at $q=-1$ is of particular interest, since, for a strict partition $\lambda$
in $\pi_2(n)$, the symmetric functions $P_\lambda(X;-1)$ and $Q_\lambda(X;-1)$ 
coincide with those introduced by Schur in his study of the projective
representations of $\S_n$.

A strict partition $\lambda$ of length $m$ can be represented in the form 
$\lambda = \rho_m + \nu$, where $\rho_m = (m,\, m-1,\, \ldots ,\, 1)$. It is
then known that, if $X$ is a finite set of variables of cardinality $\le m+1$,
the following factorization holds:
\begin{equation}\label{PFACT}
P_{\rho_m + \nu}(X;-1) = P_{\rho_m}(X;-1)\,s_\nu(X) = s_{\rho_m}(X)\,s_\nu(X)\ .
\end{equation}
This formula due to Stanley has been used by Pragacz to show that
the $\Z$-linear combinations of Schur $P$-functions are characterized among
symmetric polynomials by a cancellation property \cite{Pr}. The reader
is referred to \cite{Pr} for some geometric applications. 

Another interesting property of $P$-functions is the staircase multiplication
formula \cite{W}
\begin{equation}\label{MST}
P_{\rho_r}\, P_{\rho_s} = P_{\rho_r+\rho_s} \ ,
\end{equation}
valid irrespective of the number (finite or infinite) of variables. The following 
identity, established in \cite{LLT3}, provides a common generalization of 
(\ref{PFACT}) and (\ref{MST}). It gives a quadratic expression of any $P$-function
in terms of the $S$-functions.
%
\begin{theorem}
Let $\lambda$ be a partition of length at most $n$. Then 
\begin{equation}\label{THLLT3}
P_{\rho_n + \lambda} = \sum_\mu \omega\left( s_{\rho_n+2\mu} \right)\,D_{p_2\circ s_\mu} s_\lambda
\end{equation}
the summation being over all partitions $\mu$.
\end{theorem}
%
\begin{example}{\rm With $\lambda = (4,3,1)$ we have
$$
P_{752} = P_{(321)+(431)} = s_{321}\,s_{431} + s_{32111}\,s_{411} + s_{3211111}\,(-s_4)
+s_{32221}\,s_{211} 
$$
$$
+ s_{3222111}\,(-s_2) + s_{3222221}\,(-s_0) \ . 
$$
}
\end{example}

When $\lambda = \rho_m$ it is well known that 
$$
{\partial\over \partial p_{2i}} s_\lambda = 0
$$
for all $i$, so that $D_{p_2\circ s_\mu} s_\lambda = 0$ for $\mu \not = 0$, and
since $s_\lambda = P_{\rho_m}$, (\ref{THLLT3}) reduces to (\ref{MST}). Also,
when dealing with a set of variables $X$ of cardinality $n+1$, one has
$$
\omega\left( s_{\rho_n+2\mu} \right)(X) = 0
$$
as soon as $\mu \not = 0$, and (\ref{THLLT3}) reduces to (\ref{PFACT}).

Other interesting special cases can be explicited. For example, when $\lambda = (i)$
is a row partition, 
\begin{equation}
P_{\rho_n+(i)} = \sum_{0\le j \le [i/2]} \omega (s_{\rho_n+(2j)}) \, h_{i-2j} \ .
\end{equation}
More generally, in the case where $\lambda = \rho_m+2\nu$ with $\ell(\nu)\le m$, the derivatives
can be expressed as
\begin{equation}
D_{p_2\circ s_\mu}\,s_{\rho_m+2\nu} = \sum_\alpha \< s_\nu \,,\, s_\mu \, s_\alpha \> \, s_{\rho_m + 2\alpha} 
\end{equation}
so that, for $\ell(\nu)\le m\le n$,
\begin{equation}
P_{\rho_n+\rho_m+2\nu} = \sum _{\mu,\,\alpha} c_{\mu ,\, \alpha}^{\,\nu}\, 
\omega( s_{\rho_n+2\mu})\, s_{\rho_m+2\alpha}
\end{equation}
where the $c_{\mu ,\, \alpha}^{\,\nu}$ are the Littlewood-Richardson multiplicities.

In the general case, the multiplicity
$$
\< D_{p_2\circ s_\mu}\,s_\lambda\, , \, s_\gamma\>
= \< s_\lambda \, ,\, s_\gamma \, [p_2\circ s_\mu] \>
$$
of the product $\omega(s_{\rho_n+2\mu})\, s_\gamma$ in (\ref{THLLT3})
can be combinatorially described by means of an analogue of the Littlewood-Richardson
rule, in which the usual Young tableaux are to be replaced by $2$-ribbons tableaux 
(or {\it domino tableaux}) \cite{CL}. 

\bigskip
Surprisingly, the Schur $P$-functions happen to be connected to a family of orthogonal 
polynomials known as {\it Bessel polynomials}. These polynomials can be defined as
follows. The continued fraction expansion of ${\rm tanh}\, z^{-1}$ has for successive 
convergents
$$
F_1 = {1\over z}\,,\ \ F_2={3z\over 3z^2+1}\,,\ \ F_3={15z^2+1\over 15z^3+6z}\,,\ \ 
F_4={105z^3+10z\over 105z^4+45z^2+1} \,, \ \ldots
$$
The sum of the numerator and denominator of $F_n$ is a polynomial $y_n(z)$ of degree $n$,
called the $n$th Bessel polynomial.

A symmetric function $F(X;T)$ (where $T$ is some set of variables) is said to be a symmetric
analogue of a formal power series $f(T)$ if there exists a specialization $X=A$ of $X$ such
that $F(A;T) = f(T)$. The set of variables $A$ can be {\it virtual} which means that the
specialization is defined by specifying (in an arbitrary way) the values of a sequence of 
algebraically independent generators of \sym. For example, $\sigma_t(X)$ is a symmetric 
analogue of the exponential function $e^t=\sigma_t(E)$, where the virtual set $E$ is defined
by $h_n(E)=1/n!$, or equivalently by $p_1(E)=1$ and $p_k(E)=0$ for $k>1$.

A more substantial example is given by the symmetric Eulerian polynomials ${\cal A}_n(X;t)$,
with generating series \cite{De2}
$$
{\cal A}_X(t)=\sum_{n\ge 0} {\cal A}_n(X;t) = {1-t\over 1-t\,\sigma_{1-t}(X)} \ .
$$
The usual Eulerian polynomials are then given by
$$
A_n(t) = n!\, {\cal A}_n(E;t) \ .
$$

The Schur $P$ or $Q$-functions provide symmetric analogues of the Bessel polynomials.
Set once for all $q=-1$, and
$$
Y_n(X;z)={Q_{\rho_n}(X+z)\over Q_{\rho_n}(X)}
$$
(in $\lambda$-ring notation). Then the vertex operator formula (\ref{VERTEX}) shows
that if $\mu$ is the linear functional defined by 
$$
\mu(z^n) = (-1)^{n+1} Q_{n+1}(X) \ ,
$$
then \cite{LT},
\begin{theorem}
\begin{enumerate}\item The $Y_n(X;z)$ are 
orthogonal for $\mu$, and more precisely,
$$
\mu(z^k Y_n(X;z)) = (-1)^{k+1} {Q_{\rho_n \vee (k+1)}(X) \over Q_{\rho_n}(X)} \ ,
$$
which is zero for $0\le k \le n-1$.
\item $Y_n(E;z) = y_n(z)$
\end{enumerate}
\end{theorem}

The staircase multiplication formula (\ref{MST}) written in the form
$$
Q_{\rho_m}\,Q_{\rho_n} = 2^m \, Q_{\rho_m + \rho_n}
$$
($m\le n$), gives in view of (\ref{VERTEX})
$$
\mu(z^k \,Y_m(X;z)\,Y_n(X;z)) = (-1)^{k+1} {Q_{\rho_m+\rho_n \vee (k+1)}(X) \over Q_{\rho_m+\rho_n}(X)} \ ,
$$
and specializing again to $X=E$, one obtains a formula conjectured by Favreau
in his thesis \cite{Fa} for computing the linearization coefficients of Bessel 
polynomials. (This was proved independently by J. Zeng).
































\small

\begin{thebibliography}{ABCD}

%\bibitem[\bf BV]{BV} {\sc D. Barbasch and D. Vogan}, {\it Primitive ideals and orbital integrals
%in complex classical groups}, Math. Ann. 259, (1982) 153-199
\bibitem[\bf CL]{CL} {\sc C. Carr\'e and B. Leclerc}, {\it Splitting the square of a
Schur function into its symmetric and antisymmetric parts}, Institut Gaspard Monge, preprint, 1993.

\bibitem[\bf CT]{CT}  {\sc C. Carr\'e and J.-Y. Thibon}, {\it Plethysm and vertex operators},
Adv. in Applied Math. {\bf 13} (1992), 390-403.

\bibitem[\bf Co]{Co} {\sc E. Cohen}, {\it A class of arithmetical functions}\rm,  Proc. Nat.
Acad. Sci. U.S.A. {\bf 41} (1955), 939-944.

\bibitem[\bf DCP]{DCP}{\sc C. De Concini \rm and \sc C. Procesi}, {\it Symmetric functions,
conjugacy classes and the flag variety}, Invent. Math. {\bf 64} (1981), 203-230.


\bibitem[\bf De1]{De} {\sc J. D\'esarm\'enien}, {\it Etude modulo $n$ des statistiques
mahonniennes}\rm,
Actes du $22^{\rm e}$ s\'eminaire Lotharingien de Combinatoire, IRMA,
Strasbourg
(1990), 27-35.

\bibitem[\bf De2]{De2}  {\sc J. D\'esarm\'enien}, {\it Fonctions sym\'etriques
associ\'ees \`a des suites classiques de nombres}, Ann. Sci. \'Ec. Norm.
Sup. {\bf 16} (1983), 271-304.

\bibitem[\bf Fa]{Fa} {\sc L.D. Faddeev} {\it Integrable models in $1 + 1$ dimensional quantum
field theory}, {\it in} Les Houches Lectures 1982, Elsevier, Amsterdam, 1984.

\bibitem[\bf Fav]{Fav} {\sc L. Favreau}, {\it Combinatoire des tableaux oscillants et des
polyn\^omes de Bessel}, Publ. L.A.C.I.M., U.Q.A.M. Montr\'eal, 1991.

\bibitem[\bf FS]{FS} {\sc S. Fomin and D. Stanton}, {\em Rim hook lattices}, Mittag-Leffler institute,
preprint No 23, 1991/92.

\bibitem[\bf Fo1]{Fo1} {\sc H.O. Foulkes}, {\it A survey of some combinatorial aspects
of symmetric functions}, {\it in} Permutations, Gauthier-Villars, Paris, 1974.

\bibitem[\bf Fo2]{Fo2} {\sc H.O. Foulkes}, \it Characters of symmetric groups induced by
characters of cyclic subgroups\rm, in \it Combinatorics \rm (Proc.
Conf. Comb. Math. Inst. Oxford 1972), Inst. Math. Appl.,
Southend-on-Sea, 1972, 141-154.

%\bibitem[\bf Ga]{Ga} {\sc  D. Garfinkle}, {\it On the classification of primitive ideals for
%complex classical Lie algebras, I}, Compositio Mathematica, 75 (1990)
%2, 135-169

\bibitem[\bf Gr]{Gr} {\sc J.A. Green}, {\it The characters of the finite general linear groups},
Trans. Amer. Math. Soc. {\bf 80} (1955), 402-447.

\bibitem[\bf Gu1]{Gupta1} {\sc R.K. Gupta}, {\it Generalized exponents via
Hall-Littlewood symmetric functions}, Bull. Amer. Math. Soc. {\bf 16} (1987), 287-291.

\bibitem[\bf Gu2]{Gupta2} {\sc R.K. Gupta}, {\it Characters and the $q$-analog of
weight multiplicity}, J. London Math. Soc. {\bf 36} (1987), 68-76.

\bibitem[\bf Gu3]{Gu3} {\sc R.K. Gupta}, {\it Problem 9}, {\it in} Combinatorics and Algebra,
C. Greene ed. 1984, Contemporary Mathematics vol. 34.

\bibitem[\bf Ha]{Ha} {\sc P. Hall}, {\it The algebra of partitions}, Proc.
4th Canadian Math. Congress, 1957. 

\bibitem[\bf Han]{Han} {\sc G.-N. Han}, {\it Croissance des polyn\^omes de Kostka}, C. R.
Acad. Sci. Paris, {\bf 311} (1990) 269-272.

\bibitem[\bf HW]{HW} {\sc G.M. Hardy and E.M. Wright}, \it An introduction to the theory of
numbers\rm, (5th ed.), Oxford, Clarendon Press, 1979.

\bibitem[\bf He]{He} {\sc W.H. Hesselink}, {\it Characters of the nullcone},
Math. Ann. {\bf 252} (1980), 179-182.

\bibitem[\bf HS]{HS} {\sc R. Hotta and T.A. Springer}, \it A specialization theorem for
certain Weyl groups\rm, Invent. Math {\bf 41} (1977), 113-127.

\bibitem[\bf JK]{JK} {\sc G. D. James and A. Kerber}, {\it The representation theory of the symmetric group},
Addison-Wesley, 1981.

\bibitem[\bf Jo]{Jo} {\sc K. Johnsen}, {\it On a forgotten note by Ernst
Steinitz in the theory of Abelian groups}, Bull. London Math. Soc. {\bf 14} (1982),
353-355.

\bibitem[\bf Ka]{Kato} {\sc S. Kato}, {\it Spherical functions and a $q$-analogue
of Kostant's weight multiplicity formula}, Invent. Math. {\bf 66} (1982), 461-468.

\bibitem[\bf Kac]{Kac} {\sc V. Kac}, {\it Infinite dimensional Lie algebras}, Cambridge Univ. Press,
3rd ed., 1990.

\bibitem[\bf Ke]{Ke} {\sc A. Kerber}, {\it Algebraic combinatorics via finite group actions}, Mannheim, 1991.

\bibitem[\bf KSW]{KSW} {\sc A. Kerber, F. S\"anger and B. Wagner}, {\it Quotienten und 
Kerne von Young-Diagrammen, Brettspiele und Plethysmen gew\"ohnlicher irreduzibler 
Darstellungen symmetrischer Gruppen}, Mitt. Math. Sem. Giessen, {\bf 149} (1981), 131-175.

%\bibitem[\bf KKL]{KKL} {\sc A. Kerber, A. Kohnert and A. Lascoux}, {\it SYMMETRICA, an object oriented
%computer-algebra system for the symmetric group}, J. Symbolic Computation 14 (1992), 195-203

\bibitem[\bf KKR]{KKR} {\sc S. Kerov, A.N. Kirillov and N. Yu. Reshetikhin}, {\it Combinatorics,
Bethe Ansatz, and representations of the symmetric group}, J. Sov. Math., {\bf 41} (1988),
916-924. 

\bibitem[\bf Ki1]{Ki1} {\sc A.N. Kirillov}, {\it Combinatorial identities and completeness of states 
of Heisenberg magnetics},
{\it in} Questions of quantum field theory and statistical physics 4, J. Sov. Math. {\bf 30} No. 4 (1985).

\bibitem[\bf Ki2]{Ki2} {\sc A.N. Kirillov}, {\it Completeness of states of generalized Heisenberg magnetics},
{\it in} Automorphic functions and number theory 11, J. Sov. Math. {\bf 36} No. 1 (1987).

\bibitem[\bf Ki3]{Ki3} {\sc A. N. Kirillov}, {\it On the Kostka-Green-Foulkes polynomials and Clebsch-Gordan
numbers}, J. of Geometry and Physics, {\bf 5}:3 (1988), 365-389.

\bibitem[\bf Ki4]{Ki4} {\sc A.N. Kirillov}, {\it Decomposition of symmetric and exterior
powers of the adjoint representation of $\gl_N$}, Advanced Series in Math. Phys., {\bf 16}
B (1992), 545-580.

\bibitem[\bf Ki5]{Ki5} {\sc A.N. Kirillov}, {\it Unimodality of generalized Gaussian 
coefficients}, C. R. Acad. Sci. Paris, {\bf 315} (1992), 497-501.

%\bibitem[\bf KLLT]{KLLT} {\sc A. N. Kirillov, A. Lascoux, B. Leclerc and J.Y. Thibon}, {\it S\'eries
%g\'en\'eratrices pour les tableaux de dominos}, Preprint.

\bibitem[\bf KR]{KR} {\sc A. N. Kirillov and N. Yu. Reshetikhin}, {\it Bethe ansatz and the combinatorics
of Young tableaux}, J. Sov. Math., {\bf 41} (1988), 925-955.

%\bibitem[\bf Kl]{KL} {\sc T. Klein}, {\it The Hall polynomial}, J. Algebra {\bf 12}
%(1969), 61-78.

\bibitem[\bf Kn]{Kn}{\sc D.E. Knuth}, {\it Permutations, matrices and generalized Young
tableaux}, Pacific. J. Math. {\bf 34} (1970), 709-727.

\bibitem[\bf Ko]{Ko} {\sc B. Kostant}, {\it Lie group representations on polynomial rings},
Amer. J. Math. {\bf 85} (1963), 327-404.

\bibitem[\bf KW]{KW} {\sc W. Kraskiewicz and J. Weyman}, \it Algebra of invariants and the
action of a Coxeter element\rm, Preprint Math. Inst. Univ. Copernic,
Toru\'n, Poland.

\bibitem[\bf La]{La} {\sc A. Lascoux}, {\it Cyclic permutations on words, tableaux and harmonic
polynomials}, Proc. of the Hyderabad conference on algebraic groups, 1989, Manoj Prakashan, Madras (1991),
323-347.

\bibitem[\bf LLT1]{LLT1} {\sc A. Lascoux, B. Leclerc and J.Y. Thibon}, {\it Fonctions de Hall-Littlewood
et polyn\^{o}mes de Kostka-Foulkes aux racines de l'unit\'e}, C.R. Acad. Sci. Paris, {\bf 316}
(1993), 1-6.

\bibitem[\bf LLT2]{LLT2} {\sc A. Lascoux, B. Leclerc and J.Y. Thibon}, {\it Green polynomials and Hall-Littlewood
functions at roots of unity}, Europ. J. Combinatorics {\bf 15} (1994), 173-180.

\bibitem[\bf LLT3]{LLT3} {\sc A. Lascoux, B. Leclerc and J.Y. Thibon}, {\it Une nouvelle expression
des fonctions $P$ de Schur}, C.R. Acad. Sci. Paris, {\bf 316} (1993), 221-224.

%\bibitem[\bf LS1]{LS1} {\sc A. Lascoux and M. P. Sch\"{u}tzenberger}, Formulaire raisonn\'e de
%fonctions sym\'etriques, Publ. Math. Univ. Paris 7, 1985

\bibitem[\bf LS1]{LS1} {\sc A. Lascoux and M. P. Sch\"{u}tzenberger}, {\it Le mono\"{\i}de plaxique},
in ``Noncommutative structures in algebra and geometric combinatorics" (A. de Luca Ed.), Quaderni
della Ricerca Scientifica del C. N. R., Roma, 1981.

\bibitem[\bf LS2]{LS2}{\sc A. Lascoux and M. P. Sch\"{u}tzenberger}, {\it Sur une conjecture de
H.O. Foulkes}, C.R. Acad. Sci. Paris {\bf 286A} (1978), 323-324.

\bibitem[\bf LT]{LT} {\sc B. Leclerc and J.- Y. Thibon}, {\it Analogues sym\'etriques
des polyn\^omes de Bessel}, C.R. Acad. Sci. Paris, {\bf 315} (1992), 527-530.

\bibitem[\bf Li1]{Li1} {\sc D. E. Littlewood}, {\it On certain symmetric functions}, 
Proc. London Math. Soc. {\bf 43} (1961), 485-498.

\bibitem[\bf Li2]{Li2} {\sc D. E. Littlewood}, {\it The theory of group characters and matrix representations
of groups}, Oxford, 1950 (second edition).

\bibitem[\bf Li3]{Li3} {\sc D. E. Littlewood}, {\it Modular representations of symmetric groups},
Proc. Roy. Soc. A. 209 (1951) 333-353

\bibitem[\bf Lu1]{Lu1} {\sc G. Lusztig}, {\it Singularities, character formulas, and a $q$-analog
of weight multiplicities}, Analyse et topologie sur les espaces singuliers (II-III), Ast\'erisque
{\bf 101-102} (1983), 208-227.

\bibitem[\bf Lu2]{Lu2} {\sc G. Lusztig}, {\it Green polynomials and singularities of 
unipotent classes}, Adv. in Math. {\bf 42} (1981), 169-178.

\bibitem[\bf Mcd]{Mcd} {\sc I. G. Macdonald}, {\it Symmetric functions and Hall polynomials}, Oxford, 1979.

\bibitem[\bf MT]{MT} {\sc A.I. Molev and L.M. Tsalenko}, \it Representations of symmetric
groups in a free Lie (super) algebra and in the space of harmonic
polynomials\rm, Funct. Anal. Appl. {\bf 20}:2 (1986),
150-152.

\bibitem[\bf Mo1]{Mo1}{\sc A.O. Morris}, {\it The characters of the group $GL(n,q)$}, Math.
Zeitschr. {\bf 81} (1963), 112-123.

\bibitem[\bf Mo2]{Mo2} {\sc A.O. Morris}, \it On an algebra of symmetric functions\rm, Quart.  J.
Math. Oxford Ser. (2) {\bf 16} (1965), 53-64.

\bibitem[\bf Mo3]{Mo3}{\sc A.O. Morris}, {\it The multiplication of Hall functions},
Proc. Lond. Math. Soc. {\bf 13} (1963), 733-742.

\bibitem[\bf MS]{MS} {\sc A. O. Morris and N. Sultana}, {\it Hall-Littlewood polynomials at roots of $1$
and modular representations of the symmetric group}, Math. Proc. Cambridge Phil. Soc., {\bf 110} (1991),
443-453.

\bibitem[\bf Mu]{Mu} {\sc T. Muir}, {\it A treatise on the theory of determinants},
Macmillan, London, 1882.

\bibitem[\bf NV]{NV} {\sc C.A. Nicol and H.S. Vandiver}, \it A Von Sterneck arithmetical
function
and restricted partitions with respect to a modulus\rm, Proc. Nat.
Acad.
Sci. U.S.A. {\bf 40} (1954), 825-835.

\bibitem[\bf Pr]{Pr} {\sc P. Pragacz}, {\it Algebro-geometric applications of Schur $S$- and $P$- polynomials}
{\it in} Topics in invariant theory (S\'eminaire Dubreil-Malliavin), Lecture Notes in Math. vol. 1478, 
Springer, 1991.

%\bibitem[\bf Ro2]{Ro2} {\sc G. de B. Robinson}, Representation theory of the symmetric group, Edimburgh 1961

\bibitem[\bf ST]{ST} {\sc T. Scharf and J.-Y. Thibon}, {\it A Hopf algebra approach to inner plethysm},
Adv. in Math. (to appear).

\bibitem[\bf S]{S} {\sc I. Schur}, {\it \"Uber die Darstellung der symmetrischen und der alternierenden
Gruppen durch gebrochene lineare Substitutionen}, J. reine angew. Math. {\bf 139} (1911), 155-250.

\bibitem[\bf Sc]{Sc}{\sc M.P. Sch\"utzenberger}, {\it Propri\'et\'es nouvelles des tableaux
de Young}, S\'eminaire Delange-Pisot-Poitou, 19{\`eme ann\'ee}, {\bf 26}, 1977/78.

\bibitem[\bf SW]{SW} {\sc D. Stanton and D. White}, {\em A Schensted algorithm for rim-hook tableaux},
J. Comb. Theory A {\bf 40}, (1985), 211-247.

\bibitem[\bf Sta]{Sta84} {\sc R.P. Stanley}, {\it The stable behaviour of some characters of 
$SL(n,{\bf C})$}, Linear and Multilinear Alg. {\bf 16} (1984), 3-27.

\bibitem[\bf St]{St} {\sc E. Steinitz}, {\it Zur theorie der Abel'schen gruppen}, 
Jahresberichta der DMV {\bf 9} (1901), 80-85.

\bibitem[\bf Su]{Su} {\sc N. Sultana}, \it Hall-Littlewood functions and their applications
to representation theory\rm, Thesis, University of Wales,
1990.

\bibitem[\bf TF]{TF} {\sc L.A. Takhtadzhyan and L.D. Faddeev}, {\it Spectrum and scattering
of stimuli of excitations in the one-dimensional isotropic Heisenberg model},
Zap. Nauch. Semin. LOMI, {\bf 109} (1981), 134-173.

\bibitem[\bf T]{T} {\sc J.-Y. Thibon}, {\it Hopf algebras of symmetric functions and tensor
products of symmetric group representations}, Internat. J. of Alg. Comp., {\bf 1} (1991), 207-221.

%\bibitem[\bf vL]{vL} {\sc M. van Leeuwen}, {\em A Robinson-Schensted algorithm in the geometry of flags
%for Classical Groups}, Thesis, 1989

\bibitem[\bf W]{W} {\sc D.R. Worley}, {\it A theory of shifted Young tableaux}, Thesis, M.I.T. 1984.

\end{thebibliography}

\end{document}








@
