Last update: 25 September 2012

Generalized Hall–Littlewood polynomials (Macdonald spherical functions) and generalized Kostka–Foulkes polynomials ($q$-weight multiplicities) arise in many places in combinatorics, representation theory, geometry, and mathematical physics. This paper attempts to organize the different definitions of these objects and prove the fundamental combinatorial results from “scratch”, in a presentation which, hopefully, will be accessible and useful for both the nonexpert and researchers currently working in this very active field. The combinatorics of the affine Hecke algebra plays a central role. The final section of this paper can be read independently of the rest of the paper. It presents, with proof, Lascoux and Schützenberger’s positive formula for the Kostka–Foulkes polynomials in the type $A$ case.

The classical theory of Hall–Littlewood polynomials and the Kostka–Foulkes polynomials appears in the monograph of I.G. Macdonald [Mac1995]. The Hall–Littlewood polynomials form a basis of the ring of symmetric functions and the Kostka–Foulkes polynomials are the entries of the transition matrix between the Hall–Littlewood polynomials and the Schur functions.

This theory enters in many different places in algebra, geometry and combinatorics. Many of these connections appear in [Mac1995].

- [Mac1995, Ch. II] explains how this theory describes the structure of the Hall algebra of finite $\U0001d52c$-modules, where $\U0001d52c$ is a discrete valuation ring.
- [Mac1995, Ch. IV] explains how the Hall–Littlewood polynomials enter into the representation theory of ${GL}_{n}\left({\mathbb{F}}_{q}\right)$ where ${\mathbb{F}}_{q}$ is a finite field with $q$ elements.
- [Mac1995, Ch, V] shows that the Hall–Littlewood polynomials arise as spherical functions for ${GL}_{n}\left({\mathbb{Q}}_{p}\right)$ where ${\mathbb{Q}}_{p}$ is the field of $p$-adic numbers.
- [Mac1995, Ch. III §6 Ex. 6] explains how the Kostka–Foulkes polynomials relate to the intersection cohomology of unipotent orbit closures for ${GL}_{n}\left(\u2102\right)$ and [Mac1995, Ch. III §8 Ex. 8] explains how the Kostka–Foulkes polynomials describe the graded decomposition of the representations of the symmetric groups Sn on the cohomology of Springer fibers.
- [Mac1995, Ch. I App. A §8 and Ch. III §6] shows that the Kostka–Foulkes polynomials are $q$-analogues of the weight multiplicities for representations of ${GL}_{n}\left(\u2102\right)\text{.}$
- [Mac1995, Ch. III (6.5)] explains how the Kostka–Foulkes polynomials encode a subtle statistic on column strict Young tableaux.

Macdonald [Mac1971, (4.1.2)] showed that there is a formula for the spherical functions for the Chevalley group $G\left({\mathbb{Q}}_{p}\right)$ which generalizes the formula for Hall–Littlewood symmetric functions. This combinatorial formula is in terms of the root system data of the Chevalley group $G\text{.}$ In [Lus1983] Lusztig showed that Macdonald’s spherical function formula can be seen in terms of the affine Hecke algebra and that the “$q$-weight multiplicities” or generalized Kostka–Foulkes polynomials coming from these spherical functions are Kazhdan–Lusztig polynomials for the affine Weyl group. Kato [Kat1982] proved the “partition function formula” for the $q$-weight multiplicities which was conjectured by Lusztig. The partition function formula has led to continuing analysis of the connection between the $q$-weight multiplicities, functions on nilpotent orbits, filtrations of weight spaces by the kernels of powers of a regular nilpotent element, and degrees in harmonic polynomials (see [JLZ2000] and the references there).

The connection between Hall–Littlewood polynomials and o-modules has seen generalizations in the theory of representations of quivers, the classical case being the case where the quiver is a loop consisting of one vertex and one edge. This theory has been generalized extensively by Ringel, Lusztig, Nakajima and many others and is developing quickly; fairly recent references are [Nak1999] and [Nak2001].

The connection to Springer representations of Weyl groups and the representations of Chevalley groups over finite fields has been developed extensively by Lusztig, Shoji and others; a good survey of the current theory is in [Sho1987] and the recent papers [Sho2001] show how this theory is beginning to extend its reach outside Lie theory into the realm of complex reflection groups.

Since the theory of Macdonald spherical functions (the generalization of Hall–Littlewood polynomials) and $q$-weight multiplicities (the generalization of Kostka–Foulkes polynomials) appears in so many important parts of mathematics it seems appropriate to give a survey of the basics of this theory. This paper is an attempt to collect together the fundamental combinatorial results analogous to those which are found for the type A case in [Mac1995]. The presentation here centers on the role played by the affine Hecke algebra. Hopefully this will help to illustrate how and why these objects arise naturally from a combinatorial point of view and, at the same time, provide enough underpinning to the algebra of the underlying algebraic groups to be useful to researchers in representation theory.

Using the terms *Hall–Littlewood polynomial* and *Macdonald spherical function* interchangeably, and using the words *Kostka–Foulkes polynomial*
and *q-weight multiplicity* interchangeably, the results that we prove in this paper are as follows.

- The interpretation of the Hall–Littlewood polynomials as elements of the affine Hecke algebra (via the Satake isomorphism).
- Macdonald’s spherical function formula.
- The expansion of the Hall Littlewood polynomial in terms of the standard basis of the affine Hecke algebra.
- The triangularity of transition matrices between Macdonald spherical func- tions and other bases of symmetric functions.
- The straightening rules for Hall–Littlewood polynomials.
- The orthogonality of Macdonald spherical functions.
- The raising operator formula for Kostka–Foulkes polynomials.
- The partition function formula for $q$-weight multiplicities.
- The identification of the Kostka–Foulkes polynomial as a Kazhdan–Lusztig polynomial.

All of these results are proved here in general Lie type. They are all previously known, spread throughout various parts of the literature. The presentation here is a unified one; some of the proofs may (or may not) be new.

Section 4 is designed so that it can be read independently of the rest of the paper. In Section 4 we give the proof of Lascoux-Schützenberger’s positive combinatorial formula [LaS1978] (see also [Mac1995, Ch. III (6.5)]) for Kostka–Foulkes polynomials in type $A\text{.}$ Versions of this proof have appeared previously in [Sch1978] and in [But1994]. This proof has a reputation for being difficult and obscure. After finally getting the courage to attack the literature, we have found, in the end, that the proof is not so difficult after all. Hopefully we have been able to explain it so that others will also find it so.

A portion of this paper was written during a stay of A. Ram at the Newton Institute for the Mathematical Sciences at Cambridge University. A. Ram thanks them for their hospitality and support during Spring 2001. The preparation of this paper has been greatly aided by handwritten lecture notes of I.G. Macdonald from lectures he gave at the University of California, San Diego, in Spring 1991. In several places we have copied rather unabashedly from them. Over many years Professor Macdonald has generously given us lots of handwritten notes. We cannot thank him enough, these notes have opened our eyes to many beautiful things and shown us the “right way” many times when we were going astray.

The research of A. Ram was partially supported by the National Science Foundation (DMS-0097977), the National Security Agency (MDA904-01-1-0032) and by EPSRC Grant GR K99015 at the Newton Institute for Mathematical Sciences. The research of K. Nelsen was partially supported by the National Science Foundation (DMS-0097977 and a VIGRE grant) and the National Security Agency (MDA904-01-1-0032).