Feeds:
Posts

## Hecke algebras and the Kazhdan-Lusztig polynomials

The Hecke algebra attached to a Coxeter system $(W, S)$ is a deformation of the group algebra of $W$ defined as follows. Take the free $\mathbb{Z}[q^{ \frac{1}{2} }, q^{ - \frac{1}{2} }]$-module $\mathcal{H}_W$ with basis $T_w, w \in W$, and impose the multiplicative relations

$T_w T_s = T_{ws}$

if $\ell(sw) > \ell(w)$, and

$T_w T_s = q T_{ws} + (q - 1) T_w$

otherwise. (For now, ignore the square root of $q$.) Humphreys proves that these relations describe a unique associative algebra structure on $\mathcal{H}_W$ with $T_e$ 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 $W$ is the Weyl group of an algebraic group $G$ with Borel subgroup $B$, the above relations describe the algebra of functions on $G(\mathbb{F}_q)$ which are bi-invariant with respect to the left and right actions of $B(\mathbb{F}_q)$ under a convolution product. The representation theory of the Hecke algebra is an important tool in understanding the representation theory of the group $G$, and more general Hecke algebras play a similar role; see, for example MO question #4547 and this Secret Blogging Seminar post. For example, replacing $G$ and $B$ with $\text{SL}_2(\mathbb{Q})$ and $\text{SL}_2(\mathbb{Z})$ gives the Hecke operators in the theory of modular forms.

It is a classical theorem that for generic choices of $q$, the Hecke algebra is isomorphic to the group algebra of the Weyl group. In fact, when $q = 1$ 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 $\mathbb{F}_1$.

The Hecke algebras attached to $S_n$ are important outside of representation theory because they are finite-dimensional quotients of the group algebras of the braid groups $B_n$. 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 $\{ T_w \}$ 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 $W$ 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 $T_s^2 = (q - 1) T_s + q$, hence that

$T_s^{-1} = q^{-1} T_s - 1 + q^{-1}$.

The relations also imply that $T_{s_1} ... T_{s_r} = T_w$ whenever $s_1 ... s_r = w$ is a reduced expression, so it follows by induction that $T_w$ is invertible, and we would like to know what this inverse looks like.

Theorem (7.4): Let $u, v \in W$. There is a family $R_{u,v}(q)$ of polynomials such that

$\displaystyle (T_{v^{-1}})^{-1} = q^{-\ell(v)} \sum_{u \le v} (-1)^{\ell(v) - \ell(u)} R_{u,v}(q) T_u$.

These are the R-polynomials of $W$. One can show that the degree of $R_{u,v}(q)$ is $\ell(v) - \ell(u)$ and that $R_{u,u}(q) = 1$. By convention, if $u \not\leq v$ then $R_{u,v}(q) = 0$. 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 $(-1)^{\ell(v) - \ell(u)}$ 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 $s \in S$ be such that $vs < v$. Then

$R_{u,v}(q) = R_{us,vs}(q)$

if $us < u$, and

$R_{u,v}(q) = q R_{us,vs}(q) + (q - 1) R_{u,vs}(q)$

otherwise.

The Kazhdan-Lusztig polynomials

The R-polynomials make explicit the following definition. Define a map $\imath: \mathcal{H}_W \to \mathcal{H}_W$ by sending $q^{\frac{1}{2}}$ to $q^{-\frac{1}{2}}$, sending $T_w$ to $(T_{w^{-1}})^{-1}$, and extending $\mathbb{Z}$-linearly. It turns out (7.7) that $\imath$ is an involutive ring homomorphism, and for reasons which I only partially understand, we are interested in finding a basis for $\mathcal{H}_W$ invariant under this involution.

Theorem (7.9): There is a unique basis $C_v'$ of $\mathcal{H}_W$ such that $\imath(C_v') = C_v'$ and such that there exist polynomials $P_{u,v}(q)$ of degree less than or equal to $\frac{\ell(v) - \ell(u) - 1}{2}$ satisfying

$\displaystyle C_v' = q^{ - \frac{\ell(v)}{2} } \sum_{u \le v} P_{u,v}(q) T_u$.

The polynomials $P_{u,v}(q)$ are the Kazhdan-Lusztig polynomials associated to $W$. Via the Kazhdan-Lusztig conjectures, now theorems, they have become very important in representation theory. When $W$ 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 $C_w'$ is invariant under $\imath$ is a condition which guarantees that this occurs, as follows.

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

$\displaystyle \sum_{p \in P} q^{\rho(p)}$

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

$\displaystyle \sum_{u \le w} q^{\ell(u)}$

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

$\displaystyle \sum_{u \le w} P_{u, w}(q) q^{\ell(u)}$

is symmetric follows from the invariance under $\imath$ that we wanted in the theorem (and in fact, the above is precisely the Poincare polynomial of the intersection cohomology of $X_w$ in the Weyl group case). To see this, observe that $T_w \mapsto q^{\ell(w)}$ is a homomorphism compatible with $\imath$. One might call it the $q$-sign homomorphism.

Conjecture: The coefficients of $P_{u,v}(q)$ are always non-negative.

Thanks to intersection cohomology, this is known when $W$ 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, $P_{u,v}(q) = 1$ here) and for universal Coxeter systems (the ones where $m(i, j) = \infty$ for all $i \neq j$) by a result of Dyer. The only finite Coxeter groups not covered by these cases are the ones of type $H_3$ and $H_4$, 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 $1$; this is not hard. It’s also known that the coefficient of $q$ 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 $P_{u,v}(q) = 1$ when $\ell(v) - \ell(u) = 1, 2$, and when $\ell(v) - \ell(u) = 3, 4$, relatively simple combinatorial formulas are known.

As far as I know, it is still open whether the coefficient of $q^2$ 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.

### 2 Responses

1. Hi. Do you know of any cases where the maximum possible coefficient of P_{u,v}(q) is nonzero and also not equal to 1? It seems that in most small cases it always zero or 1.

Thanks.

• I believe it’s known that any polynomial with non-negative coefficients and constant term 1 is a Kazhdan-Lusztig polynomial of some Bruhat interval, but I’ve forgotten the reference.