Hecke algebras and the Kazhdan-Lusztig polynomials

The Hecke algebra attached to a Coxeter system is a deformation of the group algebra of defined as follows. Take the free -module with basis , and impose the multiplicative relations

if , and

otherwise. (For now, ignore the square root of .) Humphreys proves that these relations describe a unique associative algebra structure on with as the identity, but the proof is somewhat unenlightening, so I will skip it. (Actually, the only purpose of this post is to motivate the definition of the Kazhdan-Lusztig polynomials, so I’ll be referencing the proofs in Humphreys rather than giving them.)

The motivation behind this definition is a somewhat long story. When is the Weyl group of an algebraic group with Borel subgroup , the above relations describe the algebra of functions on which are bi-invariant with respect to the left and right actions of under a convolution product. The representation theory of the Hecke algebra is an important tool in understanding the representation theory of the group , and more general Hecke algebras play a similar role; see, for example MO question #4547 and this Secret Blogging Seminar post. For example, replacing and with and gives the Hecke operators in the theory of modular forms.

It is a classical theorem that for generic choices of , the Hecke algebra is isomorphic to the group algebra of the Weyl group. In fact, when the defining relations are precisely those in the group algebra. This is one way of making precise the idea that Weyl groups are algebraic groups over .

The Hecke algebras attached to are important outside of representation theory because they are finite-dimensional quotients of the group algebras of the braid groups . This allows us to use Hecke algebras to construct invariants of knots and links via Markov’s theorem. Most famously, we can construct the HOMFLY polynomial this way. This is described in some detail in Chapter 4 of Kassel and Turaev’s Braid Groups, along with the connection to the Temperley-Lieb algebras, and a categorification is described, again at the Secret Blogging Seminar, here.

However, today we are interested in the Hecke algebras for a completely different reason. In 1979, Kazhdan and Lusztig introduced a special basis of the Hecke algebra in order to construct certain representations of it. The transition matrix between this basis and the basis is given by a family of polynomials, the Kazhdan-Lusztig polynomials, which encode a lot of geometric information in the Weyl group case and which have since been recognized as fundamental objects of study in geometric representation theory. On the other hand, the Kazhdan-Lusztig polynomials, like the Hecke algebra itself, admit a completely combinatorial definition in terms of the Weyl group, so they have also become an important object of study in algebraic combinatorics. Brenti has written a good survey paper about the combinatorial point of view.

One reason for using combinatorial methods is simply that they are easier. But another is that the geometric and representation-theoretic methods only work when is a finite or affine Weyl group, since one can study the corresponding algebraic group or Kac-Moody algebra. But many statements about Kazhdan-Lusztig polynomials are known or conjectured to hold for all Coxeter groups, hinting at the existence of a deeper underlying geometric theory.

R-polynomials

So what are the Kazhdan-Lusztig polynomials? It is customary to first introduce a simpler family of polynomials as follows. The defining relations imply that , hence that

.

The relations also imply that whenever is a reduced expression, so it follows by induction that is invertible, and we would like to know what this inverse looks like.

Theorem (7.4): Let . There is a family of polynomials such that

.

These are the R-polynomials of . One can show that the degree of is and that . By convention, if then . Note that the fact that Bruhat order is involved is a property intrinsic to the definition of the Hecke algebra. It is also good to recognize that is the Mobius function of Bruhat order. This is equivalent to Bruhat order being Eulerian.

R-polynomials can be computed inductively as follows.

Theorem (7.5): Let be such that . Then

if , and

otherwise.

The Kazhdan-Lusztig polynomials

The R-polynomials make explicit the following definition. Define a map by sending to , sending to , and extending -linearly. It turns out (7.7) that is an involutive ring homomorphism, and for reasons which I only partially understand, we are interested in finding a basis for invariant under this involution.

Theorem (7.9): There is a unique basis of such that and such that there exist polynomials of degree less than or equal to satisfying

.

The polynomials are the Kazhdan-Lusztig polynomials associated to . Via the Kazhdan-Lusztig conjectures, now theorems, they have become very important in representation theory. When is the Weyl group of an algebraic group, their coefficients are non-negative and describe the intersection cohomology of the corresponding Schubert varieties. Essentially the only thing I know about this subject is that intersection cohomology is a cohomology theory which “repairs” Poincare duality in the presence of singularities, and the property that the basis is invariant under is a condition which guarantees that this occurs, as follows.

If is a graded poset such that each rank has finitely many elements, one can define the rank generating function

where is the rank function. When is the interval in a Weyl group attached to an algebraic group , the rank generating function is the Poincare polynomial of the singular cohomology of the Schubert variety ; in particular, if is nonsingular, then is rank-symmetric by Poincare duality. If is not rank-symmetric, then Poincare duality must fail, so the Schubert variety must be singular, e.g. the polynomial

does not have symmetric coefficients. The Kazhdan-Lusztig polynomials can be thought of as a canonical way to repair this symmetry; the condition that

is symmetric follows from the invariance under that we wanted in the theorem (and in fact, the above is precisely the Poincare polynomial of the intersection cohomology of in the Weyl group case). To see this, observe that is a homomorphism compatible with . One might call it the -sign homomorphism.

Conjecture: The coefficients of are always non-negative.

Thanks to intersection cohomology, this is known when is a Weyl group or affine Weyl group, the latter because one can define flag varieties, Schubert varieties, and intersection cohomology for the relevant Kac-Moody algebras. The coefficients are also known to be non-negative for dihedral groups by direct computation (in fact, here) and for universal Coxeter systems (the ones where for all ) by a result of Dyer. The only finite Coxeter groups not covered by these cases are the ones of type and , and there the corresponding Kazhdan-Lusztig polynomials are known to have non-negative coefficients by explicit computer calculations; see e.g. du Cloux.

Other than that, I’m not too knowledgeable about the state-of-the-art results, although Brenti’s survey has some good information. Without any additional hypotheses, it’s known that the constant term is always equal to ; this is not hard. It’s also known that the coefficient of is always non-negative; this was proven independently by Dyer and by Tagawa, and is an exercise in Bjorner and Brenti’s Combinatorics of Coxeter Groups (so presumably it follows from more general results proven in the relevant chapters). It’s known that when , and when , relatively simple combinatorial formulas are known.

As far as I know, it is still open whether the coefficient of is always non-negative. This is the problem I am currently working on at SPUR. In the next post I will discuss the strategy I’m currently attempting to solve this problem with.