In their seminal 1979 paper Representations of Coxeter groups and Hecke algebras (Invent. Math. 53, doi:10.1007/BF01390031), Kazhdan and Lusztig studied an arbitrary Coxeter group $(W,S)$ and the corresponding Iwahori-Hecke algebra. In particular they showed how to pass from a standard basis of this algebra to a more canonical basis, with the change of basis coefficients involving polynomials indexed by pairs of elements of $W$ (in the Bruhat ordering) over $\mathbb{Z}$. Even though the evidence at the time was quite limited, they conjectured following the statement of their Theorem 1.1 that the coefficients of these polynomials should always be non-negative. (In very special cases this is true because the coefficients give dimensions of certain cohomology groups.)

Several decades later, Wolfgang Soergel worked out a coherent strategy for proving the non-negativity conjecture, in his paper

Now that his program seems to have been completed, it is natural to renew the question in the header:

What if any implications would the non-negativity of coefficients of arbitrary Kazhdan-Lusztig polynomials have?

It has to be emphasized that in Soergel's formulation and the following work, the non-negativity is not itself the main objective. Instead the combinatorial framework proposed was meant to provide a more self-contained conceptual setting for proof of the original Kazhdan-Lusztig conjecture on Verma module multipliities for a semisimple Lie algebra (soon a theorem) and further theorems in representation theory of a similar flavor. But Coxeter groups form a vast general class of groups given by generators and relations, so it is surprising to encounter such strong constraints on the polynomials occurring in this generality.

ADDED: There is some overlap with older questions related to Soergel's approach, posted here and here.

UPDATE: It's been pointed out to me that older work by Jim Carrell and Dale Peterson involves the non-negativity condition, though their main goal is the study of singularities of Schubert varieties in classical cases. See the short account (with a long title)

  • J.B. Carrell, The Bruhat graph of a Coxeter group, a conjecture of Deodhar, and rational smoothness of Schubert varieties. Algebraic groups and their generalizations: classical methods (University Park, PA, 1991), 53–61, Proc. Sympos. Pure Math., 56, Part 1, Amer. Math. Soc., Providence, RI, 1994. https://doi.org/10.1090/pspum/056.1

The first section develops for an arbitrary Coxeter group some consequences of non-negativity of Kazhdan-Lusztig coefficients for the combinatorial study of Bruhat intervals. For further details about the geometry, see

I'm still not sure whether such consequences of the 1979 K-L conjecture are enough to make the conjecture in itself "important". But it's definitely been challenging to approach.

  • 4
    $\begingroup$ A further update: I wrote that Soergel's program "seems to have been completed" after hearing about recent work by Ben Elias and Geordie Williamson. Their preprint is now posted at arXiv:1212.0791. But my question doesn't logically depend on what they've done. $\endgroup$ Dec 10, 2012 at 14:25
  • 1
    $\begingroup$ P.S. The Elias-Williamson paper is to appear in Annals of Mathematics, but may of course differ somewhat from the arXiv preprint version. $\endgroup$ May 22, 2014 at 14:58
  • $\begingroup$ One thing that follows not from this positivity but rather the positivity of the structure constants of the Hecke algebra in the KL basis is that one can define special representations (in the sense of Lusztig) for arbitrary finite Coxeter groups, since these can be defined for any positively based algebra in a uniform way which coincides with Lusztig's original definition when specializing to Weyl groups (this is explored in a paper by Mazorchuk and myself). $\endgroup$ Sep 20, 2016 at 10:03
  • $\begingroup$ A slightly later paper by Lusztig also does this, but I have yet to actually read that in enough detail to see if the extended definitions agree (though I would be surprised if they did not). $\endgroup$ Sep 20, 2016 at 10:03

2 Answers 2


Non-negativity is important in the proof of Lusztig's 15 conjectures (in fact, it is easy to be proved with the non-negativity property, like in the "split case" and "quasi-split case"). Although even when in unequal parameter setting, where non-negativity is no longer true, we still can't find any counterexample of the 15 conjectures. When all the conjectures hold, a lot of work can be done on the representation of Coxeter groups and their Hecke algebras. Everything is contained here. (I don't have enough reputation to add a comment, so I have to put my comment as an answer. I'm sorry if it is bad.)

  • 2
    $\begingroup$ Better cite the abstract arxiv.org/abs/math/0208154 because I believe the paper is going to be updated. $\endgroup$ May 22, 2014 at 8:50
  • $\begingroup$ @darijgrinberg Why do you believe that? It is twelve years old and hasn't been updated. It has also been published in book form some years ago and the paper wasn't updated. $\endgroup$ May 22, 2014 at 12:50
  • 1
    $\begingroup$ @JohannesHahn: "I believe" was an overstatement, but "I have reasons suggesting that" would be more precise (from discussions at MIT). Either way, linking the abstract is the best choice (normally, it should be linked with version number, but here it doesn't matter due to the inconcreteness of the citation). $\endgroup$ May 22, 2014 at 12:55
  • $\begingroup$ @Sunkist: The unequal parameter case is interesting but not directly relevant to my question. Note that Lusztig's Montreal lecture write-up has been published: Hecke algebras with unequal parameters. CRM Monograph Series, 18. American Mathematical Society, Providence, RI, 2003. vi+136 pp. ISBN: 0-8218-3356-1. Aside from minor format changes this is probably the same as the arXiv version, but I haven't checked. A current update on analogues of positivity conjectures: ams.org/journals/ert/2014-18-04/S1088-4165-2014-00452-7 $\endgroup$ May 22, 2014 at 14:52
  • $\begingroup$ @JimHumphreys: Mr Humphreys, what I want to say is that the non-negativity property implies the truth of 15 conjectures. I mention the unequal parameter case in order to say the conjectures are no longer clear to hold when the non-negativity property fails. $\endgroup$
    – Sunkist
    May 23, 2014 at 1:32

Maybe I can provide a belated kind of answer to my own question, which I came across when looking for something else in the older literature. Vinay Deodhar published a paper in 1990 here (just before family medical problems and then his own health prevented him from continuing his research). This might have further combinatorial interest relative to Kazhdan-Lusztig polynomials for Coxeter groups outside the traditional framework of Lie theory. But his approach depends crucially on the assumption that a given element of the Coxeter group is "good", which is implied by non-negativity of all coefficients in certain of the KL polynomials. Deodhar seems to have expected, in line with the conjecture of Kazhdan and Lusztig, that this would always be satisfied.

The impressive work of Elias and Williamson published in 2014 here extends earlier work of Soergel on his bimodules and thereby proves the non-negativity conjecture in general. So Deodhar's algorithmic procedure might be worthwhile to revisit. In any case, those who have access to Math Reviews should find it useful to track the reviews and later citations of both of these papers.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.