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`

.

- KazhdanLusztigPolynomial
- CriticalPair
- KazhdanLusztigCoefficient
- KazhdanLusztigMue
- LeftCells
- LeftCellRepresentation
- Hecke elements of the $C$ basis
- Hecke elements of the primed $C$ basis
- Hecke elements of the $D$ basis
- Hecke elements of the primed $D$ basis

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

`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[1];; gap> CoxeterLength( W, w ); 23 gap> y := PermCoxeterWord( W, [ 1, 2, 3, 4 ] );; gap> cr := CriticalPair( W, y, w, 4 );; gap> CoxeterWord( W, cr[1] ); [ 2, 3, 2, 1, 3, 4, 3, 2, 1, 3, 2, 3, 4, 3, 2, 3 ] gap> cr[3]; 16 gap> KazhdanLusztigPolynomial( W, y, w, 4, 23 ); q^3 + 1 gap> KazhdanLusztigPolynomial( W, cr[1], cr[2], 16, 23 ); q^3 + 1

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

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

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

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

`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[3]); [ [ [ -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).

`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

*
*

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).

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

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

`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