# 83 Kazhdan-Lusztig polynomials and bases

There is a number of programs in CHEVIE for computing Kazhdan-Lusztig polynomials, left cells, and the various Kazhdan-Lusztig bases of Iwahori-Hecke algebras (see KL79).

From a computational point of view, Kazhdan-Lusztig polynomials are quite a challenge. It seems that the best approach still is by using the recursion formula in the original article KL79. One can first run a number of standard checks on a given pair of elements to see if the computation of the corresponding polynomial can be reduced to a similar computation for elements of smaller length, for example. One such check involves the notion of critical pairs (cf. Alv87): We say that a pair of elements w_1,w_2 in W such that w_1 leq w_2 is critical if {mathcal{L}}(w_2) subseteq {mathcal{L}}(w_1) and {mathcal{R}}(w_2) subseteq {mathcal{R}}(w_1), where {mathcal{L}} and {mathcal{R}} denote the left and right descent set, respectively.

Now if y,w in W are arbitrary elements with y leq w then there always exists a critical pair (w_1,w_2) such that the Kazhdan-Lusztig polynomials P_{y,w} and P_{w_1,w_2} are equal. Given two elements y and w, such a critical pair is found by the function `CriticalPair`.

The CHEVIE programs for computing Kazhdan-Lusztig polynomials are organized in such a way that whenever the polynomial corresponding to a critical pair is computed then this pair and the polynomial are stored in the component `criticalPairs` of the record of the underlying Coxeter group. (This is different to earlier versions of CHEVIE.)

A good example to see how long the programs will take for computations in big Coxeter groups is the following:

` LeftCells( CoxeterGroup( "F", 4 ) );`

which takes 20 minutes cpu time on a SPARCstation 5 computer. The computation of all Kazhdan-Lusztig polynomials for type F_4 takes a bit more than~1 hour.

However, it still seems to be out of range to re-do Alvis' computation of the Kazhdan--Lusztig polynomials of the Coxeter group of type H_4 in a computer algebra system like GAP. For such applications, it is probably more efficient to use a special purpose program like the one provided by F. DuCloux DuC91.

The code for the Kazhdan-Lusztig bases `C`, `D` and their primed versions has been written by Andrew Mathas. Some other bases (e.g., the Murphy basis) can be found in his package `Specht`.

Previous Up Next
Index

GAP 3.4.4
April 1997