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.

Subsections

  1. KazhdanLusztigPolynomial
  2. CriticalPair
  3. KazhdanLusztigCoefficient
  4. KazhdanLusztigMue
  5. LeftCells
  6. LeftCellRepresentation
  7. Hecke elements of the $C$ basis
  8. Hecke elements of the primed $C$ basis
  9. Hecke elements of the $D$ basis
  10. Hecke elements of the primed $D$ basis

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

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

Previous Up Next
Index

GAP 3.4.4
April 1997