# 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`.

## 83.1 KazhdanLusztigPolynomial

`KazhdanLusztigPolynomial( W, y, w [, ly, lw ] )`

returns the Kazhdan-Lusztig polynomial in the indeterminate `X(Rationals)` corresponding to the elements y and w (given as permutations) of the Coxeter group W. The optional variables ly and lw contain the length of y and w, respectively. The above form for the input has been chosen for efficiency reasons. If one prefers to give as input just two reduced expressions, one can define a new function as follows (for example):

```    gap> klpol := function( W, x, y)
>      return KazhdanLusztigPolynomial( W, PermCoxeterWord( W, x ),
>                  PermCoxeterWord( W, y ), Length( x ), Length( y ) );
>    end;
function ( W, x, y ) ... end ```

We use this function in the following example where we compute the polynomials P_{1,w} for all elements w in the Coxeter group of type A_3.

```    gap> q := X( Rationals );; q.name := "q";;
gap> W := CoxeterGroup( "B", 3 );;
gap> el := CoxeterWords( W );
[ [  ], [ 3 ], [ 2 ], [ 1 ], [ 3, 2 ], [ 2, 1 ], [ 2, 3 ], [ 1, 3 ],
[ 1, 2 ], [ 2, 1, 2 ], [ 3, 2, 1 ], [ 2, 3, 2 ], [ 2, 1, 3 ],
[ 1, 2, 1 ], [ 1, 3, 2 ], [ 1, 2, 3 ], [ 3, 2, 1, 2 ],
[ 2, 1, 2, 3 ], [ 2, 3, 2, 1 ], [ 2, 1, 3, 2 ], [ 1, 2, 1, 2 ],
[ 1, 3, 2, 1 ], [ 1, 2, 1, 3 ], [ 1, 2, 3, 2 ], [ 3, 2, 1, 2, 3 ],
[ 2, 1, 2, 3, 2 ], [ 2, 3, 2, 1, 2 ], [ 2, 1, 3, 2, 1 ],
[ 1, 3, 2, 1, 2 ], [ 1, 2, 1, 2, 3 ], [ 1, 2, 1, 3, 2 ],
[ 1, 2, 3, 2, 1 ], [ 2, 3, 2, 1, 2, 3 ], [ 2, 1, 2, 3, 2, 1 ],
[ 2, 1, 3, 2, 1, 2 ], [ 1, 3, 2, 1, 2, 3 ], [ 1, 2, 1, 2, 3, 2 ],
[ 1, 2, 1, 3, 2, 1 ], [ 1, 2, 3, 2, 1, 2 ], [ 2, 1, 2, 3, 2, 1, 2 ],
[ 2, 1, 3, 2, 1, 2, 3 ], [ 1, 2, 3, 2, 1, 2, 3 ],
[ 1, 2, 1, 2, 3, 2, 1 ], [ 1, 2, 1, 3, 2, 1, 2 ],
[ 2, 1, 2, 3, 2, 1, 2, 3 ], [ 1, 2, 1, 2, 3, 2, 1, 2 ],
[ 1, 2, 1, 3, 2, 1, 2, 3 ], [ 1, 2, 1, 2, 3, 2, 1, 2, 3 ] ]
gap> List( el, w -> klpol( W, [], w ) );
[ q^0, q^0, q^0, q^0, q^0, q^0, q^0, q^0, q^0, q^0, q^0, q^0, q^0,
q^0, q^0, q^0, q^0, q^0, q^0, q + 1, q^0, q^0, q^0, q^0, q + 1,
q^0, q^0, q + 1, q^0, q^0, q + 1, q + 1, q^0, q + 1, q^0, q + 1,
q^0, q^2 + 1, q + 1, q^2 + q + 1, q + 1, q + 1, q^0, q^0, q^2 + 1,
q^0, q + 1, q^0 ] ```

The set of Kazhdan--Lusztig polynomials that were found during this computation is contained in the record component `klpol` (as lists of coefficients):

```    gap> W.klpol;
[ [ 1, 1 ], [ 1 ], [ 1, 0, 1 ], [ 1, 1, 1 ] ] ```

Thus, we have found four different Kazhdan-Lusztig polynomials, namely 1+q, 1, 1+q^2 and 1+q+q^2.

This function requires the package "chevie" (see RequirePackage).

## 83.2 CriticalPair

`CriticalPair( W, y, w, ly )`

Given an element y of length ly in the Coxeter group W and an element w the function `CriticalPair` returns a triple (z,w,lz) where (z,w) is a critical pair (i.e., we have mathcal{L}(w) subseteq mathcal{L}(z) and mathcal{R}(w) subseteq mathcal{R}(z) and lz is the length of z. This critical pair is chosen so that the corresponding Kazhdan--Lusztig polynomials P_{z,w} and P_{y,w} are equal.

```    gap> W := CoxeterGroup( "F", 4 );
CoxeterGroup("F", 4)
gap> w := LongestCoxeterElement( W ) * W.generators;;
gap> CoxeterLength( W, w );
23
gap> y := PermCoxeterWord( W, [ 1, 2, 3, 4 ] );;
gap> cr := CriticalPair( W, y, w, 4 );;
gap> CoxeterWord( W, cr );
[ 2, 3, 2, 1, 3, 4, 3, 2, 1, 3, 2, 3, 4, 3, 2, 3 ]
gap> cr;
16
gap> KazhdanLusztigPolynomial( W, y, w, 4, 23 );
q^3 + 1
gap> KazhdanLusztigPolynomial( W, cr, cr, 16, 23 );
q^3 + 1 ```

This function requires the package "chevie" (see RequirePackage).

## 83.3 KazhdanLusztigCoefficient

`KazhdanLusztigCoefficient( W, y, w, [ ly, lw,] k )`

returns the k-th coefficient of the Kazhdan-Lusztig polynomial corresponding to the elements y and w, which must be given as permutations on the root vectors, of the Coxeter group W. Again, the optional variables ly and lw contain the length of y and w, respectively.

```    gap> W := CoxeterGroup( "B", 4 );;
gap> y := [ 1, 2, 3, 4, 3, 2, 1 ];;
gap> py := PermCoxeterWord( W, y );
( 1,28)( 2,15)( 4,27)( 6,16)( 7,24)( 8,23)(11,20)(12,17)(14,30)(18,31)
(22,32)
gap> x := [ 1 ];;
gap> px := PermCoxeterWord( W, x );
( 1,17)( 2, 8)( 6,11)(10,14)(18,24)(22,27)(26,30)
gap> Bruhat( W, px, py );
true
gap> List([0..3],i->KazhdanLusztigCoefficient( W, px, py, 1, 7, i ) );
[ 1, 2, 1, 0 ] ```

So the Kazhdan-Lusztig polynomial corresponding to x and y is 1+2u+u^2.

This function requires the package "chevie" (see RequirePackage).

## 83.4 KazhdanLusztigMue

`KazhdanLusztigMue( W, y, w [, ly, lw ] )`

given elements y and w in the Coxeter group W, this function returns the coefficient of degree (l(w)-l(y)-1)/2 of the Kazhdan-Lusztig polynomial corresponding to y and w. The optional variables ly and lw contain the length of y and w, respectively.

Of course, the result of this function could also be obtained by

`KazhdanLusztigCoefficient( W, y, w, ly, lw, (lw - ly -1)/2)`

but there are some speed-ups compared to this general function.

This function requires the package "chevie" (see RequirePackage).

## 83.5 LeftCells

`LeftCells( W )`

returns a list of pairs. The first component of each pair consists of the reduced words in the Coxeter group W which lie in one left cell C, the second component consists of the corresponding matrix of highest coefficients mu_{y,w}, where y,w are in C.

```    gap> W := CoxeterGroup( "G", 2 );;
gap> LeftCells(W);
[ [ [ [  ] ], [ [ 0 ] ] ],
[ [ [ 1 ], [ 2, 1 ], [ 1, 2, 1 ], [ 2, 1, 2, 1 ], [ 1, 2, 1, 2, 1 ]
],
[ [ 0, 1, 0, 0, 0 ], [ 1, 0, 1, 0, 0 ], [ 0, 1, 0, 1, 0 ],
[ 0, 0, 1, 0, 1 ], [ 0, 0, 0, 1, 0 ] ] ],
[ [ [ 1, 2, 1, 2, 1, 2 ] ], [ [ 0 ] ] ],
[ [ [ 2 ], [ 1, 2 ], [ 2, 1, 2 ], [ 1, 2, 1, 2 ], [ 2, 1, 2, 1, 2 ]
],
[ [ 0, 1, 0, 0, 0 ], [ 1, 0, 1, 0, 0 ], [ 0, 1, 0, 1, 0 ],
[ 0, 0, 1, 0, 1 ], [ 0, 0, 0, 1, 0 ] ] ] ] ```

This function requires the package "chevie" (see RequirePackage).

## 83.6 LeftCellRepresentation

`LeftCellRepresentation( W , cell )`

returns a list of matrices giving the left cell representation of the Iwahori-Hecke algebra W. The argument cell is a pair with first component a list of reduced words which form a left cell, and second component the corresponding matrix of highest coefficients of the corresponding Kazhdan-Lusztig polynomials. Typically, cell is an entry from the result of the function `LeftCells`.

```    gap> v := X( Cyclotomics ) ;; v.name := "v";;
gap> W := Hecke(CoxeterGroup( "H", 3), v^2, v );
Hecke(CoxeterGroup("H", 3),[ v^2, v^2, v^2 ],[ v, v, v ])
gap> c := LeftCells( CoxeterGroup( W ) );;
gap> List( c, i -> Length( i[ 1 ] ) );
[ 1, 6, 5, 8, 5, 6, 1, 5, 8, 5, 5, 6, 6, 5, 8, 5, 5, 8, 5, 6, 6, 5 ]
gap> LeftCellRepresentation(W,c);
[ [ [ -v^0, v, 0*v^0, 0*v^0, 0*v^0 ],
[ 0*v^0, v^2, 0*v^0, 0*v^0, 0*v^0 ],
[ 0*v^0, v, -v^0, v, 0*v^0 ],
[ 0*v^0, 0*v^0, 0*v^0, v^2, 0*v^0 ],
[ 0*v^0, 0*v^0, 0*v^0, 0*v^0, v^2 ] ],
[ [ v^2, 0*v^0, 0*v^0, 0*v^0, 0*v^0 ], [ v, -v^0, v, 0*v^0, 0*v^0 ],
[ 0*v^0, 0*v^0, v^2, 0*v^0, 0*v^0 ],
[ 0*v^0, 0*v^0, v, -v^0, v ],
[ 0*v^0, 0*v^0, 0*v^0, 0*v^0, v^2 ] ],
[ [ -v^0, v, 0*v^0, 0*v^0, 0*v^0 ],
[ 0*v^0, v^2, 0*v^0, 0*v^0, 0*v^0 ],
[ 0*v^0, 0*v^0, v^2, 0*v^0, 0*v^0 ],
[ 0*v^0, 0*v^0, 0*v^0, v^2, 0*v^0 ],
[ 0*v^0, 0*v^0, 0*v^0, v, -v^0 ] ] ]```

This function requires the package "chevie" (see RequirePackage).

## 83.7 Hecke elements of the \$C\$ basis

`Basis( H, "C" )`

returns a function which gives the C-basis of the (one parameter generic) Iwahori-Hecke algebra H. This is defined as follows (see cite[(5.1)]Lus85, for example). Let W be the underlying finite Coxeter group. For x,y in W let P_{x,y} be the corresponding Kazhdan--Lusztig polynomial. If {T_w mid w in W} denotes the usual T-basis and u=v^2 the parameter for H, then [ C_x:=sum_y leq x (-1)^l(x)-l(y)P_x,y(v^-2)v^l(x)-2l(y) T_y quad mbox for every x in W.] For example, we have C_s=v^{-1}T_s-vT_1 for s in S. Thus, the transformation matrix between the T-basis and the C-basis is lower unitriangular, with powers of v along the diagonal. The multiplication rules for this new basis are given as follows. [ C_s cdot C_x =left{ beginarrayll -(v+v^-1)C_x & mbox, if sx
C_sx+sum_y mu(y,x)C_y & mbox, if sx>xendarrayright.] where the sum is over all y such that y, l(y) notequiv l(x)~mod~2 and sy. The coefficient mu(y,x) is the coefficient of degree (l(x)-l(y)-1)/2 in the Kazhdan--Lusztig polynomial P_{x,y}.

```    gap> W := CoxeterGroup( "B", 3 );;
gap> v := X( Rationals );; v.name := "v";;
gap> H := Hecke( W, v^2, v );
Hecke(CoxeterGroup("B", 3),[ v^2, v^2, v^2 ],[ v, v, v ])
gap> T := Basis( H, "T" );
function ( arg ) ... end
gap> C := Basis( H, "C" );
function ( arg ) ... end
gap> T( C( 1 ) );
-vT()+v^-1T(1)
gap> C( T( 1 ) );
v^2C()+vC(1) ```

We can also compute character values on elements in the C-basis as follows:

```    gap> ref := HeckeReflectionRepresentation( H );;
gap> c := CharRepresentationWords( ref, CoxeterConjugacyClasses( W ) );
[ 3, 2*v^2 - 1, v^8 - 2*v^4, -3*v^12, 2*v^2 - 1, v^4, v^4 - 2*v^2,
-v^6, v^4 - v^2, 0*v^0 ]
gap> List( ChevieClassInfo( W ).classtext, i ->
>                             HeckeCharValues( C( i ), c ) );
[ 3*v^0, -v - v^(-1), 0*v^0, 0*v^0, -v - v^(-1), 2*v^0, 0*v^0, 0*v^0,
v^0, 0*v^0 ]```

This function requires the package "chevie" (see RequirePackage).

## 83.8 Hecke elements of the primed \$C\$ basis

`Basis( H, "C'" )`

returns a function which gives the C^prime-basis of the (one parameter generic) Iwahori-Hecke algebra H (see cite[(5.1)]Lus85). This is defined by [ C_x^prime := sum_y leq x P_x,y(v^2)v^-l(x) T_y quad mbox for every x in W.] We have C_x^prime=Alt(C_x) for all x in W (see `AltInvolution` in section Operations for Hecke elements of the \$T\$ basis).

```    gap> v := X( Rationals );; v.name := "v";;
gap> H := Hecke( CoxeterGroup( "B", 2 ), v ^ 2, v );;
gap> h := Basis( H, "C'" )( 1 );
C'(1)
gap> h2 := h * h;
(v+v^-1)C'(1)
gap> Basis( H, "T" )( h2 );
(1+v^-2)T()+(1+v^-2)T(1) ```

This function requires the package "chevie" (see RequirePackage).

## 83.9 Hecke elements of the \$D\$ basis

`Basis( H, "D" )`

returns a function which gives the D-basis of the (one parameter generic) Iwahori-Hecke algebra H (see cite[(5.1)]Lus85). This can be defined by [ D_x := v^-NC_xw_0^prime T_w_0 mbox for every x in W, ] where N denotes the number of positive roots in the root system of W and w_0 is the longest element of W. The D-basis is dual to the C-basis with respect to the non-degenerate form H times H rightarrow {ZZ}[v,v^{-1}], (h_1,h_2) mapsto tau(h_1 cdot h_2) where tau colon H rightarrow {ZZ}[v,v^{-1}] is the linear form such that tau(T_1)=1 and tau(T_x)=0 for x neq 1. We have D_x=beta(C_{w_0x}^prime) for all x in W (see `BetaInvolution` in section Operations for Hecke elements of the \$T\$ basis).

```    gap> W := CoxeterGroup( "B", 2 );;
gap> v := X( Rationals );; v.name := "v";;
gap> H := Hecke( W, v^2, v );
Hecke(CoxeterGroup("B", 2),[ v^2, v^2 ],[ v, v ])
gap> T := Basis( H, "T" );
function ( arg ) ... end
gap> D := Basis( H, "D" );
function ( arg ) ... end
gap> D( T( 1 ) );
vD(1)-v^2D(1,2)-v^2D(2,1)+v^3D(1,2,1)+v^3D(2,1,2)-v^4D(1,2,1,2)
gap> BetaInvolution( D( 1 ) );
C'(2,1,2) ```

This function requires the package "chevie" (see RequirePackage).

## 83.10 Hecke elements of the primed \$D\$ basis

`Basis( H, "D'" )`

returns a function which gives the D^prime-basis of the (one parameter generic) Iwahori-Hecke algebra H (see cite[(5.1)]Lus85). This can be defined by [ D_x^prime := v^-NC_xw_0 T_w_0 mbox for every x in W, ] where N denotes the number of positive roots in the root system of W and w_0 is the longest element of W. The D^prime-basis is basis dual to the C^prime-basis with respect to the non-degenerate form H times H rightarrow {ZZ}[v,v^{-1}], (h_1,h_2) mapsto tau(h_1 cdot h_2) where tau colon H rightarrow {ZZ}[v,v^{-1}] is the linear form such that tau(T_1)=1 and tau(T_x)=0 for x neq 1. We have D_x^prime=Alt(D_x) for all x in W (see `AltInvolution` in section Operations for Hecke elements of the \$T\$ basis).

```    gap> W := CoxeterGroup( "B", 2 );;
gap> v := X( Rationals );; v.name := "v";;
gap> H := Hecke( W, v^2, v );
Hecke(CoxeterGroup("B", 2),[ v^2, v^2 ],[ v, v ])
gap> T := Basis( H, "T" );
function ( arg ) ... end
gap> Dp := Basis( H, "D'" );
function ( arg ) ... end
gap> AltInvolution( Dp( 1 ) );
D(1)
gap> Dp( 1 )^3;
(v+2v^-1-5v^-5-9v^-7-8v^-9-4v^-11-v^-13)D'()+(v^2+2+v^-2)D'(1) ```

This function requires the package "chevie" (see RequirePackage).

GAP 3.4.4
April 1997