In their seminal 1979 paper <a href="http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=GDZPPN002095319">here</a>, 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 *Kazhdan-Lusztig-Polynome und unzerlegbare Bimoduln uber Polynomringen.* J. Inst. Math. Jussieu 6 (2007), no. 3, 501–525. This is posted on the arXiv <a href="http://front.math.ucdavis.edu/0403.5496">here</a>. 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 <a href="https://mathoverflow.net/questions/29409/">here</a> and <a href="https://mathoverflow.net/questions/92221/">here</a>. 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) by 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. 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 the 2003 paper by Carrell and Kuttler in Invent. Math. 151.) 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.