79 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). Most of the code deals with the equal parameters case.

From a computational point of view, Kazhdan-Lusztig polynomials are quite a challenge, even in the equal parameters case, and are even more difficult to compute when the algebra has unequal parameters. For the equal parameters case 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 w1, w2 ∈ W such that w1 ≤ w2 is critical if L(w2) ⊆ L(w1) and R(w2) ⊆ R(w1), where L and R denote the left and right descent set, respectively.

Now if y,w ∈ W are arbitrary elements with y ≤ w then there always exists a critical pair (z,w) with y ≤ z ≤ w such that the Kazhdan-Lusztig polynomials Py,w and Pz,w 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:

   gap> W:=CoxeterGroup("F",4);;
    gap> LeftCells(W);;

which takes 30 seconds cpu time on 2Ghz computer. The computation of all Kazhdan-Lusztig polynomials for type F4 takes a bit more than 1 minute. Computing the Bruhat order is a bottleneck for these computations; they can be speeded up by a factor of two if one does:

   gap> ReadChv("contr/brbase");
    gap> BaseBruhat(W);;

after which the computation of the Bruhat order will be speeded up by a large factor.

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 H4 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, who also contributed to the initial implementation and to the design of the programs dealing with Kazhdan-Lusztig bases. He also implemented some other bases, such as the Murphy basis which can be found in the contributions directory (see also his Specht package). The extension to the unequal parameters case has been written by F.Digne and J.Michel.

We recall now some theory to explain the computation done. The most general case when Kazhdan-Lusztig bases and polynomials can be defined is when the parameters of the Hecke algebra belong to a totally ordered abelian group Γ (a group for the multiplication of parameters). Thus we see the Hecke algebra as being defined over the ring Z[Γ], the group algebra of Γ over Z. We assume there is for each Ts an element qs∈ Γ+ such that (Ts-qs)(Ts+1)=0 and which has a square root qs1/2 in Γ. We extend this notation to define an element qw∈Γ+ by setting qw=qs1... qsn if w=s1... sn is a reduced expression for some element of the Coxeter group. We have two operations on Z[Γ]: the bar involution γ∈Γaγγ= ∑γ∈Γaγγ-1 and truncation:\ τ ≤νγ∈Γaγγ= ∑γ ≤νaγγ. We then define elements Rx,y of Z[Γ] by Ty-1=∑x Rx,y-1qx-1Tx. We then define inductively the Kazhdan-Lusztig polynomials (in this general context we should say the Kazhdan-Lusztig elements of Z[Γ]) by

Px,w ≤(qw/qx)1/2 (∑x<y ≤ wRx,yPy,w)
(the induction is thus on decreasing x for the Bruhat order and starts at Pw,w=1).

The C' basis is then defined by C'w=∑y qw-1/2 Py,wTy. If we extend the bar involution to the whole Hecke algebra by Ts=Ts-1 the basis C'w is characterized as the only basis stable by the bar involution and congruent to qw-1/2Tw modulo Γ- in the basis qw-1/2Tw.

The other Kazhdan-Lusztig bases are computed in CHEVIE in terms of the C' basis.

CHEVIE is able to define automatically the two operations above on Z(Γ) when all parameters are powers of the same indeterminate q, with total order on Γ by the power of q, or when the parameters are powers of some Mvps, with the lexicographic order on the variables. The bar involution is evaluating a Laurent polynomial at the inverse of the variables, and truncation is keeping terms of smaller degree than that of ν. It is possible to use arbitrary groups Γ by doing the following steps: first, define the Hecke algebra, say H. Then, before defining any of the Kazhdan-Lusztig bases, write functions H.Bar(p), H.PositivePart(p) and H.NegativePart(p) which perform the operations respectively γ∈Γ aγγ→ ∑γ∈Γ aγγ-1, γ∈Γ aγγ→ ∑γ ≥ 1 aγγ and γ∈Γ aγγ→ ∑γ ≤ 1 aγγ on elements p of Z[Γ]. It is then possible to define some Kahzdan-Lusztig bases and the operations above will be used internally by CHEVIE to compute them.

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

79.1 KazhdanLusztigPolynomial

KazhdanLusztigPolynomial( W, y, w)

returns the coefficients of the Kazhdan-Lusztig polynomial corresponding to the elements y and w of the Coxeter group W when all the parameters of the Hecke algebra are equal. If one prefers to give as input just two Coxeter words, one can define a new function as follows (for example):

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

We use this function in the following example where we compute the polynomials P1,w for all elements w in the Coxeter group of type A3.

    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 -> Polynomial(Rationals,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 for critical pairs is stored record component klpol of W. Thus the function is much faster the second time.

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

79.2 CriticalPair

CriticalPair( W, y, w )

Given elements y and w in the Coxeter group W the function CriticalPair returns the longest element in the double coset W L(w)y W R(w); it is such that the Kazhdan--Lusztig polynomials Pz,w and Py,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 := EltWord( W, [ 1, 2, 3, 4 ] );;
    gap> cr := CriticalPair( W, y, w );;
    gap> CoxeterWord( W, cr);
    [ 2, 3, 2, 1, 3, 4, 3, 2, 1, 3, 2, 3, 4, 3, 2, 3 ]
    gap> KazhdanLusztigPolynomial( W, y, w);
    [ 1, 0, 0, 1 ]
    gap> KazhdanLusztigPolynomial( W, cr, w);
    [ 1, 0, 0, 1 ]

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

79.3 KazhdanLusztigCoefficient

KazhdanLusztigCoefficient( W, y, w, k )

returns the coefficient of qk in the Kazhdan-Lusztig polynomial corresponding to the elements y and w of the Coxeter group W when all the parameters of the Hecke algebra are equal to the indeterminate q.

    gap> W := CoxeterGroup( "B", 4 );;
    gap> y := [ 1, 2, 3, 4, 3, 2, 1 ];;
    gap> py := EltWord( 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 := EltWord( 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, i ) );
    [ 1, 2, 1, 0 ] 

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

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

79.4 KazhdanLusztigMue

KazhdanLusztigMue( W, y, w )

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.

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

KazhdanLusztigCoefficient(W,y,w,(CoxeterLength(W,w)-CoxeterLength(W,y)-1)/2)

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

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

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

79.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> H := Hecke(CoxeterGroup( "H", 3), v^2, v );
    Hecke(CoxeterGroup("H",3),v^2,v)
    gap> c := LeftCells( Group( H ) );;
    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(H,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).

79.7 Hecke elements of the C basis

Basis( H, "C" )

returns a function which gives the C-basis of the Iwahori-Hecke algebra H. The parameters of H should be powers of a single indeterminate or Mvps (see the introduction). This is defined as follows (see e.g. Lus85, (5.1)). Let W be the underlying Coxeter group. For x,y ∈ W let Px,y be the corresponding Kazhdan--Lusztig polynomial. If {Tw | w∈ W} denotes the usual T-basis, then

Cx:=∑y ≤ x (-1)l(x)-l(y)Px,y(q-1)qx1/2qy-1 Ty

for every x ∈ W.

For example, we have Cs=qs-1/2Ts-qs1/2T1 for s ∈ S. Thus, the transformation matrix between the T-basis and the C-basis is lower unitriangular, with powers of v along the diagonal. In the one-parameter case (all qs are equal to v2 for some indeterminate v) the multiplication rules for this new basis are given as follows.
Cs . Cx ={
-(v+v-1)Cx , if sx<x
Csx+∑y μ(y,x)Cy , if sx>x
.
where the sum is over all y such that y<x, l(y) ≢ l(x) mod 2 and sy<y. The coefficient μ(y,x) is the coefficient of degree (l(x)-l(y)-1)/2 in the Kazhdan--Lusztig polynomial Px,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)
    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, WordsClassRepresentatives( 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).

79.8 Hecke elements of the primed C basis

Basis( H, "C'" )

returns a function which gives the C'-basis of the Iwahori-Hecke algebra H (see Lus85, (5.1)) The parameters of H should be powers of a single indeterminate (see the introduction). This is defined by

Cx' := ∑y ≤ x Px,yqx-1/2 Ty for every x ∈ W.
We have Cx'=(-1)l(x)Alt(Cx) for all x ∈ 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 ^4, v^2] );;
    gap>  h := Basis( H, "C'" )( 1 );
    #warning: C' basis: v\^2 chosen as 2nd root of v\^4
    C'(1)
    gap>  h2 := h * h;
    (v^2+v^-2)C'(1)
    gap>  Basis( H, "T" )( h2 );
    (1+v^-4)T()+(1+v^-4)T(1)
    gap> Basis(H,"C'")(last);
    (v^2+v^-2)C'(1)

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

79.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 Lus85, (5.1)) of the finite Coxeter group W. This can be defined by

Dx := v-NCxw0' Tw0 for every x ∈ W,
where N denotes the number of positive roots in the root system of W and w0 is the longest element of W. The D-basis is dual to the C-basis with respect to the non-degenerate form H x H → Z[v,v-1], (h1,h2) → τ(h1 . h2) where τ : H → Z[v,v-1] is the linear form such that τ(T1)=1 and τ(Tx)=0 for x ≠ 1. We have Dx=β(Cw0x') for all x ∈ 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)
    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).

79.10 Hecke elements of the primed D basis

Basis( H, "D'" )

returns a function which gives the D'-basis of the (one parameter generic) Iwahori-Hecke algebra H of the finite Coxeter group W (see Lus85, (5.1)). This can be defined by

Dx' := v-NCxw0 Tw0 for every x ∈ W,
where N denotes the number of positive roots in the root system of W and w0 is the longest element of W. The D'-basis is basis dual to the C'-basis with respect to the non-degenerate form H x H → Z[v,v-1], (h1,h2) → τ(h1 . h2) where τ : H → Z[v,v-1] is the linear form such that τ(T1)=1 and τ(Tx)=0 for x ≠ 1. We have Dx'=Alt(Dx) for all x ∈ 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)
    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