Breakthroughs in the theory of Macdonald polynomials

In 1998, I. G. Macdonald (1) introduced a remarkable new basis for the space of symmetric functions. The elements of this basis are denoted , where λ is a partition and p, q are two free parameters. The 's, which are now called “Macdonald polynomials,” specialize to many of the well known bases for the symmetric functions, by suitable choices of the parameters q and t. In fact, we can obtain in this manner the Schur functions, the Hall–Littlewood symmetric functions, the Jack symmetric functions, the zonal symmetric functions, the zonal spherical functions, and the elementary and monomial symmetric functions.

This Review is motivated by two recent PNAS articles (2, 3) that give an explicit combinatorial formula for a certain modified version of for each partition λ. This surprising development promises to revolutionize the whole field and open up a variety of new avenues of investigation. To appreciate its significance, we give a brief overview of the history of the subject.

Symmetric functions have played a key role in many areas of mathematics including the theory of polynomial equations, representation theory of finite groups, Lie algebras, algebraic geometry, and the theory of special functions. If denotes the space of homogeneous symmetric functions of degree n where N ≥ n, then the dimension of is the number of partitions of n and has many well known bases including the monomial symmetric functions , the power symmetric functions , the elementary symmetric functions , the homogeneous symmetric functions, and , where in each case λ ranges over the partitions of n. Here, , and . Then, for a partition λ = (λ₁,..., λ_k), is the sum over all monomials so that the nonzero terms in a ₁,...a_N can be rearranged to , and

The theory of symmetric functions has a long history. Indeed, the first known article on symmetric functions was published by Girard (4) in 1629 where an explicit formula for expressing the power symmetric function in terms of the elementary symmetric functions is given. The Schur function basis is the most important basis since it plays a fundamental role in many practical as well as theoretical applications of the theory. The first definition of , for λ = (λ₁ ≥ λ₂ ≥ ··· ≥ λ_n ≥ 0), was given by Cauchy (5) in 1815 as the following quotient of two determinants:

In 1841, Jacobi (6) gave a formula, now called the Jacobi–Trudi identity, that expressed the Schur function as a certain determinant of homogeneous symmetric functions. Jacobi did not give a proof of his formula, but his student, Nicoló Trudi, gave a proof in 1864 (7).

The expansion of the Schur functions in terms of the monomial symmetric functions, first appeared in a paper by Kostka (8), and the numbers K _λ,μ came to be called the “Kostka” numbers. In ref. 9 Young gave a combinatorial interpretation for the K _λ,μ in terms of his “Raising operators” in the proof of the so-called “Young's Rule,” which expresses the decomposition into irreducible representations of the action of the symmetric group, S_n, on the left ideal of a Young subgroup. As a symmetric function identity, Young's rule can be expressed in the form

Young arrived at this identity in the process of showing that the formula for the irreducible characters of S_n produced by Frobenius (10) was in fact identical to his. Frobenius's work anticipated Young's work by over 20 years. In ref. 10, Frobenius introduced a map F, which is now called the Frobenius map, that sends the center of the group algebra of S_n, C(S_n), onto . This map allowed him to identify the irreducible characters of S_n as the inverse images of the Schur functions. That is, by setting , Frobenius essentially introduced what appeared to him as the natural partition indexing of the characters of S_n, and it is truly remarkable that Young, who worked entirely within the group algebra of S_n, was led to exactly the same partition indexing.

These historical developments constitute the precursors of much of today's work in algebraic combinatorics, which ties symmetric function theory to representation theory. The introduction of standard tableaux and raising operators by Young and the Frobenius map yielded a powerful tool for the reduction of certain algebraic problems to purely combinatorial problems. In this connection, we should mention the early work of Robinson (11), a student of Young, who most likely inspired by some unpublished work of his master introduced a tableau correspondence yielding a combinatorial proof of 2 as well as a precursor of the Robinson–Schensted–Knuth (RSK) correspondence we shall soon encounter.

The symmetric function approach to the representation theory of finite groups was extensively expanded in a treatise of Littlewood (12) where we find the combinatorial interpretation of the Kostka numbers in terms of semistandard tableaux and an incomplete proof of the so called Littlewood–Richardson algorithm for the computation of the multiplicities of the irreducible representations of S_n that occur in the outer tensor product of two irreducible representations of S_n. A column strict tableaux T is a filling of the Ferrers diagram of λ, F _λ, with integers from {1,..., N} that are weakly increasing in row from left to right and strictly increasing in columns from bottom to top. If the number i occur n_T(i) in T, then the weight of the tableaux T is given by . For example, Fig. 1 shows the Ferrers diagram of ¹λ = (4, 4, 2, 1) on the left and a column strict tableaux of shape (4, 4, 2, 1) of weight on the right. Then a combinatorial definition of is given by , where CS(λ) is the set of all column strict tableaux of shape λ. It follows that the Kostka number K _λ,μ is the number of column strict tableaux of shape λ and weight .

Dimensions of algebraic varieties, multiplicities of irreducible constituents, and a variety of other algebraic constructs that require the computation of certain integers are nowadays reduced, via a growing number of generalizations of the Frobenius map, to the computation of the coefficients in expansions of certain symmetric function bases in terms of appropriate generalizations of the Schur basis. Invariably, it turns out that the sought-for coefficients can be identified as enumerators of a growing variety of tableau-like structures.

In the 1970s, we saw the further development of a variety of correspondences bijectively linking various combinatorial constructs of tableau-like structures. The interpretation of the Kostka coefficients in terms of column strict tableaux brought the expansions in 1 and 2 to a completely new light. The fundamental RSK correspondence between integer valued matrices and pairs (P, Q) of column strict tableaux of the same shape appearing in the work of Robinson (11), Schensted (13), and Knuth (14), the “jeu-de-taquin” and the “plactic monoid” of Lascoux and Schützenberger (15, 16) may now be used to give completely combinatorial proofs of 1 and 2 as well as a variety of other symmetric function identities. Perhaps the most significant development in this period is a purely combinatorial interpretation of the coefficients in the identity giving the Schur function expansion of a suitably modified Hall–Littlewood polynomial. Representation theoretically, 3 is none other than a refinement of 2. More precisely, the left hand side represents the Frobenius image of the character of a graded version of the action of S_n on the left ideal of a Young subgroup (17). It ensues from this that is a refinement of the Kotska number K _λ,μ in that the coefficient of q^k in represents the multiplicity of the character χ^λ in the kth homogeneous component of this graded module. This circumstance prompted Foulkes (18) to ask for an identification of the combinatorial objects counted by the coefficients K _λ,μ(q)'s. The solution of this problem by Lascoux and Schützenberger (15, 16), who showed that K _λ,μ(q) may be obtained as a sum over semistandard tableaux of shape λ and type μ of q raised to a certain statistic called “charge,” has widely been considered one of the deepest results of algebraic combinatorics of the last three decades.

In the subsequent years, we have seen the rise of a vast literature on the applications of symmetric functions and the combinatorics of tableaux to representation theory. For example, see the books by Fulton (19), Macdonald (20), Sagan (21), and Stanley (22).

Parallel to these developments there is yet another characterization of Schur functions that is important for our purposes. That is, one can define a scalar product 〈,〉 on by declaring that power symmetric functions form an orthogonal basis. More precisely, we set where if λ has n_i parts of size i for i = 1,..., n, then and δ_λ,μ equals 1 if λ = μ and equals 0, otherwise. It turns out that the Schur functions are characterized by the requirement that there are numbers K _λ,μ such that for all λ and μ,

Here, we say that a partition λ = (λ₁ ≥ ··· ≥ λ_n ≥ 0) of n dominates the partition μ = (μ₁ ≥ ··· ≥ μ_n ≥ 0) of n, written λ ≥_D μ, if for all i = 1,..., n, .

In 1954, Phillip Hall (23) defined the so-called Hall algebra for abelian groups (more generally, for finite modules over discrete valuation rings) and found that there are close connections between the Hall algebra and the algebra of symmetric functions. A central role in that theory is played by a set of symmetric functions over the ring of rational functions in t, , called the Hall–Littlewood symmetric functions. The Hall–Littlewood symmetric functions were first defined by Hall indirectly in terms of the Hall algebra and then a more direct definition was given by Littlewood in ref. 24. These functions have a characterization similar to that of the Schur functions. That is, one defines a scalar product 〈,〉_t on Λ_n by declaring that where . Then, the Hall–Littlewood functions are characterized by the requirement that there are rational functions K _λ,μ(t) such that for all λ and μ,

Needless to say, the “rational functions” K _λ,μ(t) are none other than minor modifications of the polynomials occurring in 3. In particular, the work of Lascoux and Schützenberger (16) gives a combinatorial proof of the polynomiality of these coefficients.

At a memorable meeting in Durham in 1985, Macdonald brought to the attention of the algebraic combinatorialist community a certain symmetric function basis containing an additional parameter that naturally arises in statistical analysis, now commonly referred to as the Jack basis (25). Richard Stanley took on the challenge to understand this basis (26), and he showed that this basis shared all of the properties of the Schur and Hall–Littlewood bases and formulated a number of challenging combinatorial conjectures including the integrality of their expansions in terms of the monomial basis.

The peak of the pyramid was reached in 1988 when Kadell (27), by a close study of q-extensions of the Selberg integral, was led to conjecture the existence of a basis of symmetric polynomials which could be viewed as a q-extension of the Jack basis. In that same year, Macdonald (1) solved Kadell's conjecture by introducing the Macdonald polynomials , which he defined by the process described above for defining the Schur and Hall–Littlewood symmetric functions. That is, he introduced a new scalar product 〈,〉_{q , t} on by declaring that

Macdonald then proved the existence of a unique family of polynomials such that for all λ and μ, there exists rational functions ξ_λ,μ(q, t) so that

In the same seminal paper (1), Macdonald proved that his basis satisfied all the basic properties of the Schur basis, including the so-called Pieri rules expressing the multiplication action of the elementary and homogeneous symmetric function on his basis. He also introduced a certain modified version of his new basis, which he called “integral forms,” and conjectured that the rational functions K _λ,μ(q, t) occurring in the expansion should be polynomials in q, t with positive integer coefficients. Here, the are a certain modified version of the Schur functions that in plethystic notation may simply be written as s _λ(x, t) = s _λ[X(1 – t)], where X = x ₁ + ··· + x_n. He supported his conjecture by computing several truly remarkable tables exhibiting some amazing properties of these conjectured polynomials. This conjecture came to be known as the Macdonald “q, t-Kostka conjecture.” Macdonald also proved that K _λ,μ(1, 1) is well defined and reduces to the number of standard tableaux of shape λ regardless of μ and that K _λ,μ(q, 0) reduces to the Kostka–Foulkes polynomial K _λ,μ(q).

Since their introduction, Macdonald polynomials have been intensely studied and have found applications in special function theory, representation theory, algebraic geometry, group theory, statistics, and quantum mechanics. Unfortunately, the rather indirect definition of the via 6, 7, and 8 meant that all results about Macdonald polynomial had to be proved by laborious technical algebraic manipulations. Intensive efforts were carried out over the nearly two decades since their discovery to find more explicit formulas. But even the problem of proving that the K _λ,μ(q, t) are polynomials resisted all attempts for nearly 8 years. Then, three almost simultaneous but completely different approaches yielded a proof (28–32). The first breakthrough was due to the young physicist Luc Lapointe, who, in a brilliant thesis (33) studying the dynamics of particle systems, introduced certain “creation operators” that yielded Rodriguez-type formulas for the Jack polynomials. This allowed Lapointe to prove some of the Stanley conjectures mentioned above. It was clear then that the ice was broken, and Lapointe and Vinet (34) were able to extend their results on Jack polynomials to Macdonald polynomials. In particular, they obtained, for the first time, explicit Rodriguez-type formulas for the and derived from them the polynomiality of the K _λμ(q, t).

Another notable approach to proving the positive integrality of the K _λ,μ(q, t) was initiated by Garsia and Haiman who noted that the modified Macdonald polynomial could be viewed as the ultimate extension of the identities in 2 and 3. Since with n(λ) = Σ_i(i – 1)λ_i, and gives the number of standard tableaux of shape λ, the analogy with 3 suggested the existence, for each partition μ, of a bi-graded module affording the regular representation of S_n whose bi-graded character had a Frobenius image given precisely by . Remarkably, such a module was identified (35) as the linear span of all partial derivatives of a bi-homogeneous polynomial Δ_μ(x ₁, x ₂,..., x_n, y ₁, y ₂,..., y_n), which can be constructed very simply from the Ferrers diagram of the partition μ. The module resulting from the diagonal S_n action on the two sets of variables was in fact a very natural extension of the one that yielded Eq. 3 (see ref. 17). This resulted in a variety of conjectures whose proof would not only establish that the K _λ,μ(q, t)'s are in fact polynomials with positive integer coefficients but would also reveal truly surprising connections between the theory of Macdonald polynomials and the representation theory of S_n. The success of this approach hung for almost a dozen years on a single conjecture (formulated in 1990), to the effect that the polynomial Δ_μ(x; y) had n! independent derivatives. This came to be known as the n!-conjecture. The efforts at proving it yielded a variety of conjectures directly impinging on the theory of Macdonald polynomials and revealing a truly amazing kaleidoscope of representation theoretical gems (see ref. 36). Most of these conjectures remain open to this date. The n! conjecture was finally proved by Haiman in 2002 (37) by an algebraic geometrical approach outlined by Procesi as early as 1994. To do this, Haiman had to extensively develop the algebraic geometric properties of the Hilbert Scheme on n-points in the plane well beyond what was previously known, and this work earned him the 2004 Moore prize of the American Mathematical Society.

A further quite notable approach to the study of Macdonald polynomials was initiated by Lapointe, Lascoux, and Morse (38) by the introduction of a new basis straddling between the Schur functions and the polynomials . This new basis , which they called “k-Schur functions,” was conjectured to have a Schur function expansion of the form where a _λ,μ(t) are polynomials with nonnegative integer coefficients. Moreover, when all the parts of μ are bounded by k, the expansion was conjectured to hold true with the polynomials with positive integer coefficients as well. There is now overwhelming computational evidence in support of this conjecture. Moreover, quite recently Lapointe and Morse (39) conjectured a truly surprising connection between the k-Schur functions specialized at t = 1 and the Schubert classes in the cohomology of the affine Grassmanian. These are truly outstanding developments that further enhance the connections between the theory of Macdonald polynomials and some of the deepest contemporary work in algebraic geometry.

At this time, most of the work on the Garsia–Haiman modules, as well as the work of Lascoux, Lapointe, and Morse, remains conjectural. Such a circumstance has arisen due to the fact that we now have powerful computer hardware and software available that has rendered many disciplines within mathematics into experimental sciences. As a result, our power of conjecture far exceeds the available tools of proof. In the midst of such circumstances, the recent conjecture of Haglund (2) that appeared in PNAS in 2004 and the solution of that conjecture announced in the paper by Haglund, Haiman, and Loehr (3) in this issue appear as a bombshell. Indeed, Haglund's purely combinatorial recipe for the polynomial is of such simplicity as to make accessible many problems that, up until recently, appeared insurmountable. For example, in ref. 3 we find a very accessible proof of the polynomiality result referred to above, which originally took 8 years of effort.

We also find there a one-and-a-half page proof of the Lascoux– Schützenberger “charge” result whose original proof, when written out in full detail, would need the best part of 40 pages. Several other deep results not mentioned here are also derived in ref. 3 with the greatest of ease. It is clear that we have here a new powerful tool of proof which many of us researchers in Macdonald polynomial theory are anxious to apply to the resolution of the wide variety of conjectures that are still unproven, the top of the list being the 20-year-old search for a combinatorial interpretation for the Macdonald q, t-Kostska polynomials K _λ,μ(q, t).