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( 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).
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).
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).
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).
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
We can also compute character values on elements in the C-basis as
follows:
This function requires the package "chevie" (see RequirePackage).
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
This function requires the package "chevie" (see RequirePackage).
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
This function requires the package "chevie" (see RequirePackage).
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
This function requires the package "chevie" (see RequirePackage).
C_sx+sum_y mu(y,x)C_y & mbox, if sx>xendarrayright.]
where the sum is over all y such that 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)
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 ]
83.8 Hecke elements of the primed $C$ basis
Basis( H, "C'" )
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)
83.9 Hecke elements of the $D$ basis
Basis( H, "D" )
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)
83.10 Hecke elements of the primed $D$ basis
Basis( H, "D'" )
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)
April 1997