## Kazhdan-Lusztig polynomials

Last update: 6 November 2012

## Bar invariant bases

Let $\left(W,\le \right)$ be a poset such that for $u,v\in W$ the interval $\left[u,v\right]$ is finite. Let $M$ be the free $ℤ\left[q,{q}^{-1}\right]$ modules with basis $\left\{{T}_{w}\phantom{\rule{0.2em}{0ex}}\mid \phantom{\rule{0.2em}{0ex}}w\in W\right\},$

$M=ℤ[qq-1] -span {Tw∣w∈W} ,$

and let $‾:\phantom{\rule{0.2em}{0ex}}M\to M$ be a $ℤ\text{-linear}$ involution such that

$q‾=q-1 and Tw‾=Tw+ ∑v

where ${a}_{vw}\in ℤ\left[q{q}^{-1}\right]\text{.}$ Then

1. There is a unique basis $\left\{{C}_{w}^{-}\phantom{\rule{0.2em}{0ex}}\mid \phantom{\rule{0.2em}{0ex}}w\in W\right\}$ such that $Cw‾=Cw andCw-= Tw+∑v
2. There is a unique basis $\left\{{C}_{w}^{-}\phantom{\rule{0.2em}{0ex}}\mid \phantom{\rule{0.2em}{0ex}}w\in W\right\}$ such that $Cw‾=Cw andCw+= Tw+∑v

 Proof. (a) The ${p}_{vw}^{-}$ are determined by induction: $Pww-=1and Puw-= ∑k∈ℤ<0 fkqk$ where $f=∑k∈ℤfk qk=∑u (b) The ${P}_{vw}^{+}$ are determined by induction: $Pww+=1and Puw+= ∑k∈ℤ>0 fkqk$ where $f=∑k∈ℤfkqk =∑u $\square$

The dual module

$M*=Homℤ[q,q-1] ( M,ℤ [q,q-1] )$

is given a bar involution

$‾:M*→ M*defined by ⟨φ‾,m⟩= ⟨φ,m‾⟩‾$

If $\left\{{T}^{w}\phantom{\rule{0.2em}{0ex}}\mid \phantom{\rule{0.2em}{0ex}}w\in W\right\}$ is the dual basis to $\left\{{T}_{w}\phantom{\rule{0.2em}{0ex}}\mid \phantom{\rule{0.2em}{0ex}}w\in W\right\}$ then

$Tw‾=∑v bvwTvwhere bvw= ⟨ Tw‾, Tv ⟩ = ⟨ Tw, Tv‾ ⟩ ‾ = ⟨ Tw,∑z≤v azvTz ⟩ ‾$

so that $B=\stackrel{‾}{{A}^{t}}\text{.}$ If $\left\{{C}^{w}\phantom{\rule{0.2em}{0ex}}\mid \phantom{\rule{0.2em}{0ex}}w\in W\right\}$ is the dual basis to $\left\{{C}_{w}\phantom{\rule{0.2em}{0ex}}\mid \phantom{\rule{0.2em}{0ex}}w\in W\right\}$ then

$Cw‾=Cwsince ⟨ Cw‾,Cv ⟩ = ⟨ Cw, Cv‾ ⟩ ‾ = ⟨ Cw, Cv ⟩ ‾ =δvw,$

and

$Cw=∑PvwTv whereδvw ⟨Cw,Cv⟩= ⟨ ∑uPuwTu, ∑zPzvTz ⟩ =∑uPuwPuv$

so that

$(Puw)= ((Puv)-1) t =(Pt)-1.$

## The affine Hecke algebra

The affine Hecke algebra $\stackrel{\sim }{H}$ has $ℤ\left[q,{q}^{-1}\right]$ basis $\left\{{T}_{w}\phantom{\rule{0.2em}{0ex}}\mid \phantom{\rule{0.2em}{0ex}}w\in \stackrel{\sim }{W}\right\},$

$H∼=ℤ [q,q-1]-span {Tw∣w∈W∼}$

with relations

$Tw1Tw2= Tw1w2, ifℓ(w1w2) =ℓ(w1)+ℓ (w2), TsiTw= (q-q-1)Tw+ Tsiw, ifℓ(siw)< ℓ(w) (0≤i≤n).$

The algebra $\stackrel{\sim }{H}$ also has bases

${ XλTw∣ w∈W,λ∈P } and { TvXμ∣ v∈W,μ∈P } ,$

where

$Xλ=Ttλ, ifλ∈P+, andXλ=Xμ (Xν)-1,$

if $\lambda =\mu -\nu$ with $\mu ,\nu \in {P}^{+}\text{.}$

The bar involution on $\stackrel{\sim }{H}$ is the $ℤ\text{-linear}$ map $‾:\phantom{\rule{0.2em}{0ex}}\stackrel{\sim }{H}\to \stackrel{\sim }{H}$ given by

$q‾=q-1and Tw‾= Tw-1-1 forw∈W∼.$

Define elements ${1}_{0},{\epsilon }_{0}\in H$ by

$102=10, and Tsi10=q 10,for 1≤i≤n, ε02=ε0, and Tsiε0= q-1ε0, for1≤i≤n,$

and let

$Aμ=ε0Xμ 10,forμ∈ P.$

1. $\stackrel{‾}{{X}^{\lambda }}={T}_{{w}_{0}}{X}^{{w}_{0}\lambda }{T}_{{w}_{0}}^{-1},$ for $\lambda \in P,$
2. $\stackrel{‾}{{1}_{0}}={1}_{0}$ and $\stackrel{‾}{{\epsilon }_{0}}={\epsilon }_{0}\text{.}$
3. If $z\in ℤ{\left[P\right]}^{W}$ then $\stackrel{‾}{z}=z\text{.}$
4. $\stackrel{‾}{{q}^{-\ell \left({w}_{0}\right)}{A}_{\lambda +\rho }}={q}^{-\ell \left({w}_{0}\right)}{A}_{\lambda +\rho }\text{.}$

The $\tau \text{-operators}$ are given by

$τi=Ti- q-q-1 1-X-αi .$

Then

1. ${X}^{\lambda }{\tau }_{i}={\tau }_{i}{X}^{{s}_{i}\lambda },$
2. ${\tau }_{i}^{2}=\frac{\left(q-{q}^{-1}{X}^{{\alpha }_{i}}\right)\left(q-{q}^{-1}{X}^{-{\alpha }_{i}}\right)}{\left(1-{X}^{{\alpha }_{i}}\right)\left(1-{X}^{-{\alpha }_{i}}\right)}$
3. $\underset{\underset{{m}_{ij}\phantom{\rule{0.2em}{0ex}}\text{factors}}{⏟}}{{\tau }_{i}{\tau }_{j}{\tau }_{i}\dots }=\underset{\underset{{m}_{ij}\phantom{\rule{0.2em}{0ex}}\text{factors}}{⏟}}{{\tau }_{j}{\tau }_{i}{\tau }_{j}\dots }$

The shift operator is

$Δ=∏α∈R+ ( qXα/2-q-1 X-α/2 ) .$

Then

$(Ti+q)Δ= (siΔ) (Ti-q)and Δℂ [P]W= { h∈H∼∣ (ti+q-1h =0for1≤i ≤n } ε0Eλ=Δ 10Eλ-ρ and ⟨ Δf, Δg ⟩ k =qNk ⟨f,g⟩ k+1 .$

The $??\text{-trace}$ on $\stackrel{\sim }{H}$ is the linear map $\tau :\phantom{\rule{0.2em}{0ex}}\stackrel{\sim }{H}\to ℂ$ given by

$tr(h)=h∣1, or, more precisely,tr(Tw)= δw1.$

Define an inner product $\stackrel{\sim }{H}$ by

$⟨h1,h2⟩= tr(h1h2),$

so that

$⟨Tu,Tv⟩ = [Tu-1Tv] 1 and ⟨Tu,Tv⟩ =qℓ(u)?? δuv-1.$

The generic degrees are ${d}_{\lambda }\left(q\right)$ given by

$tr∑λ∈H^ dλ(q)χHλ.$

The Kazhdan-Lusztig basis is defined by

${ h∈H∣ ⟨h,h#⟩ ∈1+q-1ℤ [q-1],h= h‾ }$

or by the usual bar invariance and triangularity conditions.

## Kazhdan-Lusztig polynomials

The Iwahori-Hecke algebra is the algebra over $ℤ\left[q\right]$ given by generators ${T}_{w},$ $w\in W$ and relations

$TsiTw = { Tsiw, ifsiw>w, qTsiw +(q-1)Tw, ifsiw

The bar involution on $H$ is the $ℤ\text{-algebra}$ involution given by

$q‾=q-1and Tw‾= Tw-1-1,$

for $w\in W\text{.}$ The Kazhdan-Lusztig basis of $H$ is the basis $\left\{{C}_{w}\phantom{\rule{0.2em}{0ex}}\mid \phantom{\rule{0.2em}{0ex}}w\in W\right\}$ given by

1. $\stackrel{‾}{{C}_{w}}={C}_{w},$ and
2. ${C}_{w}={T}_{w}+\sum _{v\le w}{p}_{vw}\left(q\right){T}_{v},\phantom{\rule{1em}{0ex}}\text{where}\phantom{\rule{0.2em}{0ex}}{p}_{vw}\left(q\right)\in qℤ\left[q\right]\text{.}$

Kazhdan-Lusztig polynomials

1. ${P}_{ww}\left(q\right)=1,$
2. ${P}_{xw}\left(q\right)=0,$ if $x\nless w,$
3. $\text{deg}\left({P}_{xw}\left(q\right)\right)\le \frac{1}{2}\left(\ell \left(w\right)-\ell \left(x\right)-1\right),$ if $x\ne w\text{.}$

Define

$μ(x,w)= coefficient of the highest degree term in Pxw(q),$

which is the term of degree $\frac{1}{2}\left(\ell \left(w\right)-\ell \left(x\right)-1\right)\text{.}$ Then, if $sw

$Pxw(q) = { Psx,w(q), ifsx>x, Psx,sw(q) +qPx,sw- ∑sz

The $W\text{-graph}$ has

1. Vertices: $W$
2. Edges: $x↔y$ if $\mu \left[x,y\right]=\left\{\begin{array}{cc}\mu \left(x,y\right),& \text{if}\phantom{\rule{0.2em}{0ex}}x

Then

$KL(s)xx = { -1, ifsxx, KL(s)xy = { μ[x,y], ifsxyandx ↔y, 0, otherwise,$

Define a relation ${\le }_{L}$ by taking the closure of the relation

$x≤Lyif Dℓ(x)⊈ Dℓ(y)and x↔yis an edge.$

and define

$x=Lyif x≤Lyand y≤Lx.$

### The case of dihedral groups

In type ${A}_{1},$

$H=span{1,T1} withT12= (q-1)T1+q.$

So

$T1‾=T1-1= (q-1-1)+ q-1T1,and C1=q-12 (1+T1),$

since

$q-12 (1+T1) ‾ =q12 (1+T1-1)= q12 ( 1+q-1T1+ (q-1-1) ) =q12q-1 (1+T1)= q-12 (1+T1).$

In type ${A}_{2},$ $H=\text{span}\left\{1,{T}_{1},{T}_{2},{T}_{1}{T}_{2},{T}_{2}{T}_{1},{T}_{1}{T}_{2}{T}_{2}\right\}$ and

$C1 = q-12 (1+T1), C2 = q-12 (1+T2), C1C2 = q-1 ( 1+T1+T2+ T1T2=C12, ) C2C1 = q-1 ( 1+T1+T2+ T2T1=C21, ) C1C21 = q-32 ( T1T2T1+ T1T2+ (q-1)T1+q +T1+ T2T1+T1 +T2+1 ) , = q-32 ( T1T2T1+ T1T2+ T2T1+T1 +T2+1 ) +C1 ,$

so that

$C121=C1 C12-C1= q-32 ( T1T2T1+T1 T2+T2T1+T1 +T2+1 ) .$

Note that ${C}_{1}^{2}=\left({q}^{\frac{1}{2}}+{q}^{-\frac{1}{2}}\right){C}_{1}\text{.}$ Then, using that ${T}_{i}={q}^{\frac{1}{2}}{C}_{i}-1,$ to produce the matrices for the regular representation in the KL-basis,

$ρ(T1)= ( -1 0 0 0 0 0 q12 q q12 0 0 0 0 0 -1 0 0 0 0 0 0 -1 0 0 0 0 0 q12 q 0 0 0 q12 0 0 q ) andρ(T2)= ( -1 0 0 0 0 0 0 -1 0 0 0 0 0 q12 q 0 0 0 q12 0 0 q q12 0 0 0 0 0 -1 0 0 0 0 0 q12 q )$

with rows and columns indexed by $1,{C}_{1},{C}_{21},{C}_{2},{C}_{12},{C}_{121}\text{.}$

In type ${B}_{2},$ $H=\text{span}\left\{1,{T}_{1},{T}_{2},{T}_{1}{T}_{2},{T}_{2}{T}_{1},{T}_{1}{T}_{2}{T}_{1},{T}_{2}{T}_{1}{T}_{2},{T}_{1}{T}_{2}{T}_{1}{T}_{2}\right\},$ and

$C1C2=C12, C2C1=C21, C1C21=C121 +C1,C2C12 =C212+C2, C2C121= C2121+C21.$

where

$C1 = q-12 (1+T1), C2 = q-12 (1+T2), C12 = q-1 ( 1+T1+T2+ T1T2, ) C21 = q-1 ( 1+T1+T2+ T2T1, ) C121 = q-32 ( 1+T1+T2+ T1T2+ T2T1+ T1T2T1 ) , C212 = q-32 ( 1+T1+T2+ T1T2+ T2T1+ T2T1T2 ) , C1212 = q-32 ( 1+T1+T2+ T1T2+ T2T1+ T1T2T1+ T2T1T2+ T2T1T2T1 ) .$

and the matrices of the regular representation in the KL-basis are

$ρ(T1) = ( -1 0 0 0 0 0 0 0 q12 q q12 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 q12 q 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 q12 q q12 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 q12 q ) ρ(T2) = ( -1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 q12 q q12 0 0 0 0 0 0 0 -1 0 0 0 0 q12 0 0 0 q q12 0 0 0 0 0 0 0 -1 0 0 0 0 0 q 0 q12 q 0 0 0 0 q12 0 0 0 q )$

with rows and columns indexed by $1,{C}_{1},{C}_{21},{C}_{121},{C}_{2},{C}_{12},{C}_{212},{C}_{1212}\text{.}$

Let $W$ be the dihedral group of order $2m\text{.}$ Then

$Cw=q-12ℓ(w) (∑v≤wTv), so thatpvw (q)=1,for all v≤w.$

 Proof. Let ${C}_{w}$ be defined by the formula in the statement of the Theorem. If ${s}_{1}w>w$ so that $w={s}_{2}{s}_{1}{s}_{2}{s}_{1}\dots$ then $Cs1Cw = q-ℓ(w)/2 q-12 ( ∑v≤wTv+ ∑ v≤s1w s1v and, if ${s}_{1}w so that $w={s}_{1}{s}_{2}{s}_{1}{s}_{2}\dots$ then let ${w}^{\prime }={s}_{1}w$ and ${w}^{\prime \prime }={s}_{2}{s}_{1}w$ so that $Cs1Cw = Cs1Cs1w′ =Cs1 ( Cs1Cw′ -Cs2w′ ) = Cs1 ( Cs1 Cw′- Cw′′ ) = ( q1/2+ q-1/2 ) Cs1Cw′ -Cs1 Cw′′ = ( q1/2+ q-1/2 ) Cs1 Cw′- ( q1/2+ q-1/2 ) Cw′′, by induction, = ( q1/2+ q-1/2 ) ( Cs1 Cw′- Cw′′ ) = ( q1/2+ q-1/2 ) Cw.$ So, $Cs1Cw= { Cs1w+ Cs2w, ifs1w In the first case, $\ell \left({s}_{2}w\right)<\ell \left(w\right)$ and so, by induction, ${C}_{{s}_{1}w}={C}_{{s}_{1}}{C}_{w}-{C}_{{s}_{2}w}$ is bar invariant. $\square$

From equation (???)

$T1Cw= { qCw, ifs1ww, i.e.w=s2s1 s2s1….$

For example, in the case ${I}_{2}\left(5\right),$

$C2C1=C21, C1C21= C121+C1, C2C121= C2121+C21, C1C2121= C12121+ C121, C1C2=C12, C2C12= C212+C2, C1C212= C1212+ C12, C2C1212= C21212+ C212,$

and the matrices of the regular representation in the KL-basis are

$ρ(T1) = ( -1 0 0 0 0 0 0 0 0 0 q12 q q12 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 q12 q q12 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 q12 q q12 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 q12 q 0 0 0 0 0 q12 0 0 0 0 q ) ρ(T2) = ( -1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 q12 q q12 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 q12 q 0 0 0 0 0 q12 0 0 0 0 q q12 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 q12 q q12 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 q12 q )$