Kazhdan-Lusztig polynomials

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au
and

Department of Mathematics
University of Wisconsin, Madison
Madison, WI 53706 USA
ram@math.wisc.edu

Last updates: 10 June 2010

Bar invariant spaces

Let $\left(W,\le \right)$ be a poset such that for $u,v\in W$ the interval $\left[u,b\right]$ is finite. Let $M$ be the free $\mathbb{Z}\left[q,q^{-1}\right]$ modules with basis $\left[T_w|w\in W\right],$ $$M=\mathbb{Z}\left[q,q^{-1}\right]\mathrm{-span}\left\{T_w|w\in W\right\},$$ and let $-:M\to M$ be a $\mathbb{Z}$-linear involution such that $$$$ q = q -1 and Tw = Tw + ∑ v<w a wv Tv , where $a_{vw}\in \mathbb{Z}\left[q,q^{-1}\right].$ Then

1. There is a unique basis $\left\{C_w^{-}|w\in W\right\}$ such that $$$$ Cw = Cw and Cw- = Tw + ∑ v<w P vw - Tv with P vw - ∈ q -1 ℤ q -1
1. There is a unique basis $\left\{C_w^{-}|w\in W\right\}$ such that $$$$ Cw = Cw and Cw+ = Tw + ∑ v<w P vw + Tv with P vw + ∈qℤ q .

		Proof.
	The $p_{vw}^{-}$ are determined by induction: $$P_{ww}^{-}=1\text{ and }{P}_{uw}^{-}=\sum _{k\in {\mathbb{Z}}_{<0}}{f}_k{q}^k$$ where $$f=\sum _{k\in \mathbb{Z}}{f}_k{q}^k=\sum _{u<v\le w}{a}_{uz}$$ P zw - = P uw - - P uw - . The $p_{vw}^{+}$ are determined by induction: $$P_{ww}^{+}=1\text{ and }{P}_{uw}^{+}=\sum _{k\in {\mathbb{Z}}_{>0}}{f}_k{q}^k$$ where $$f=\sum _{k\in \mathbb{Z}}{f}_k{q}^k=\sum _{u<v\le w}{a}_{uz}$$ P zw + = P uw + - P uw + . $\square$

The dual module $$M^{*}={\mathrm{Hom}}_{\mathbb{Z}\left[q,q^{-1}\right]}\left(M,\mathbb{Z}\left[q,q^{-1}\right]\right)$$ is given a bar involution $$-:M^{*}\to M^{*}\text{ defined by }⟨⟩$$ φ m = < φ, m- >

If $\left\{T^w|w\in W\right\}$ is the dual basis to $\left\{T_w|w\in W\right\}$ then $$$$ Tw = ∑v b vw Tv where b vw = Tw Tv = < Tw , Tv _ > = < Tw , ∑ z≤v a zv Tz > so that $B=$ At . If $\left\{C^w|w\in W\right\}$ is the dual basis to $\left\{C_w|w\in W\right\}$ then $$$$ Cw = Cw since Cw Cv = < Cw , Cv _ = < Cw , Cv > = δ vw , and $$C^w=\sum P^{vw}{T}^v\text{where}{\delta }_{vw}=⟨C^w,C_v⟩=⟨\sum _u{P}^{uw}{T}_u,\sum _z{P}_{zv}{T}_z⟩=\sum _u{P}^{uw}{P}_{uv},$$ so that $$\left(P^{uw}\right)={\left({\left(P_{uv}\right)}^{-1}\right)}^t={\left(P^t\right)}^{-1}.$$

The affine Hecke algebras

The affine Hecke algebra $\tilde{H}$ has $\mathbb{Z}\left[q,q^{-1}\right]$ basis $\left\{T_w|w\in \tilde{W}\right\},$ with relations $$T_{w_1}{T}_{w_2}=T_{w_1{w}_2},\text{if }l\left(w_1{w}_2\right)=l\left(w_1\right)+l\left(w_2\right),$$$$T_{s_i}{T}_w=\left(q-q^{-1}\right)T_w+T_{s_{i}w},\text{if }l\left(s_{i}w\right)<l\left(w\right),\left(0\le i\le n\right).$$ The algebra $\tilde{H}$ also has bases $$\left\{X^{\lambda }{T}_w|w\in W,\lambda \in P\right\}\text{ and }\left\{T_v{X}^{\mu }|v\in W,\mu \in P\right\},$$ where $$X^{\lambda }=T_{t_{\lambda }},\text{ if }\lambda \in P^{+},\text{ and }{X}^{\lambda }=X^{\mu }{\left(X^{\nu }\right)}^{-1},$$ if $\lambda =\mu -\nu$ with $\mu ,\nu \in P^{+}.$

The bar involution on $\tilde{H}$ is the $\mathbb{Z}$-linear map $-:\tilde{H}\to \tilde{H}$ given by $$$$ q = q -1   and   Tw = T w -1 -1   for  w∈ W~ .

Define elements $1_0,{\epsilon }_0\in H$ by $$1_0^2=1_0,\text{ and }{T}_{s_i}{1}_0=q{1}_0,\text{ for }1\le i\le n,$$ $${\epsilon }_0^2={\epsilon }_0,\text{ and }{T}_{s_i}{\epsilon }_0=q^{-1}{1}_0,\text{ for }1\le i\le n,$$ and let $$A_{\mu }={\epsilon }_0{X}^{\mu }{1}_0,\text{for }\mu \in P.$$

1. $$ Xλ = T w0 X w0 λ T w0 -1 , for $\lambda \in P,$
2. $$ 10 = 10 and $$ ε0 = ε0 .
3. If $z\in \mathbb{Z}{\left[W\right]}^W$ then $$ z =z.
4. $$ q -l w0 A λ+ρ = q -l w0 A λ+ρ = q -l w0 A λ+ρ .

The $\tau$-operators are given by $${\tau }_i=T_i-\frac{q-q^{-1}}{1-X^{-{\alpha }_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. ${\tau }_i{\tau }_j{\tau }_i\dots \left(m_{ij}\text{ factors}\right)={\tau }_j{\tau }_i{\tau }_j\dots \left(m_{ij}\text{ factors}\right)$

The shift operator is $$\Delta =\prod _{\alpha \in R^{+}}\left(q{X}^{\frac{\alpha }{2}}-q^{-1}{X}^{-\frac{\alpha }{2}}\right).$$ Then $$\left(T_i+q\right)\Delta =\left(s_i\Delta \right)\left(T_i-q\right)\text{ and }\Delta ℂ{\left[P\right]}^W=\left\{h\in \tilde{H}|\left(t_i+q^{-1}h\right)=0\text{ for }1\le i\le n\right\}.$$ Also, $${\epsilon }_0{E}_{\lambda }=\Delta 1_0{E}_{\lambda -\rho }\text{ and }{⟨\Delta f,\Delta g⟩}_k=q^{Nk}{⟨f,g⟩}_{k+1}$$

The ????-trace on $\tilde{H}$ is the linear map $\tau :\tilde{H}\to ℂ$ given by $$\mathrm{tr}\left(h\right)=h{|}_1,\text{or, more precisely, }\mathrm{tr}\left(T_w\right)={\delta }_{w1}.$$

Define an inner product on $\tilde{H}$ by $$⟨h_1,h_2⟩=\mathrm{tr}\left(h_1{h}_2\right),$$ so that $$⟨T_u,T_v⟩={\left[T_{u^{-1}}{T}_v\right]}_1\text{ and },T_u{T}_v=q^{l\left(u\right)?}{\delta }_{u{v}^{-1}}.$$ The generic degrees are $d_{\lambda }\left(q\right)$ given by $$\mathrm{tr}=\sum _{\lambda \in \tilde{H}}{d}_{\lambda }\left(q\right){\chi }_H^{\lambda }.$$ The Kazhdan-Lusztig basis is defined by $$\left\{h\in H|⟨h,h^{\#}⟩\in 1+q^{-1}\mathbb{Z}\left[q^{-1}\right],h=\right\}$$ h or by the usual bar invariance and triangularity conditions.

Kazhdan-Lusztig polynomials

The Iwahori-Hecke algebra is the algebra over $\mathbb{Z}\left[q\right]$ given by generators $T_w,w\in W$ and relations $$T_{s_i}{T}_w=\left\{\begin{array}{rcl}{T}_{s_{i}w},& \text{if}& s_{i}w>w,\\ q{T}_{s_{i}w}+\left(q-1\right)T_w,& \text{if}& s_{i}w<w.\end{array}\right.$$ The bar involution on $H$ is the $\mathbb{Z}$-algebra involution given by $$$$ q = q -1 ,  and   Tw = T w -1 -1 , for $w\in W.$ The Kazhdan-Lusztig basis of $H$ is the basis $\left\{C_w|w\in W\right\}$ given by

1. $$ Cw = Cw , and
2. $C_w=T_w+\sum _{v\le w}{p}_{vw}\left(q\right)T_v,\text{where }{p}_{vw}\left(q\right)\in q\mathbb{Z}\left[q\right].$

The Kazhdan-Lusztig polynomials are

1. $P_{ww}\left(q\right)=1,$
2. $P_{xw}\left(q\right)=0,\text{ if }x\nleqq w,$
3. $\mathrm{deg}\left(P_{xw}\left(q\right)\right)\le \frac{1}{2}\left(l\left(w\right)-l\left(x\right)-1\right),\text{ if }x\ne w.$

Define $$\mu \left(x,w\right)=\text{coefficient of the highest degree term in }{P}_{xw}\left(q\right),$$ which is a term of degree $\frac{1}{2}\left(l\left(w\right)-l\left(x\right)-1\right).$ Then, if $sw<w$ $$P_{xw}\left(q\right)=\left\{\begin{array}{rcl}{P}_{sx,w}\left(q\right),& \text{if}& sx>x,\\ P_{sx,w}\left(q\right)+q{P}_{x,sw}-\sum _{sz<z}{q}^{\frac{1}{2}\left(l\left(w\right)-l\left(z\right)\right)}\mu \left(z,sw\right)P_{x,z},& \text{if}& sx<x.\end{array}\right.$$

The $W$-graph has

1. Vertices: $W$
2. Edges: $x\leftrightarrow y$ if $\mu \left[x,y\right]=\left\{\begin{array}{rcl}\mu \left(x,y\right),& \text{if}& x<y,\\ \mu \left(y,x\right),& \text{if}& y<x.\end{array}\right.$

Then $$KL{\left(s\right)}_{xx}=\left\{\begin{array}{rcl}1& \text{if}& sx<x,\\ -1& \text{if}& sx>x,\end{array}\right.$$ $$KL{\left(s\right)}_{xy}=\left\{\begin{array}{rcl}\mu \left[x,y\right]& \text{if}& sx>x,sy>y\text{ and }x\leftrightarrow y,\\ 0,& \text{otherwise.}& \end{array}\right.$$ Define a relation ${\le }_L$ by taking the closure of the relation $$x{\le }_{L}y\text{ if }{D}_l\left(x\right)⊊D_l\left(y\right)\text{ and }x\leftrightarrow y\text{ is an edge.}$$ Define $$x{=}_{L}y\text{ if }x{\le }_{L}y\text{ and }y{\le }_{L}x.$$

The case of dihedral groups

In type $A_1,$ $$H=\mathrm{span}\left\{1,T_1\right\}\text{with}{T}_1^2=\left(q-1\right)T_1+q.$$ So $$$$ T1 = T1 -1 = q -1 -1 + q -1 T1 ,  and   C1 = q - 1 2 1+ T1 , since $$$$ q -1/2 1+ T1 = q 1 2 1+ q -1 T1 + q -1 -1 = q 1 2 q -1 1+ T1 = q - 1 2 1+ T1 .

In type $A_2,$ $H=\mathrm{span}\left\{1,T_1,T_2,T_1{T}_2,T_2{T}_1,T_1{T}_2{T}_2\right\}$ and $$\begin{array}{rcl}{C}_1& =& q^{-\frac{1}{2}}\left(1+T_1\right),\\ C_2& =& q^{-\frac{1}{2}}\left(1+T_2\right),\\ C_1{C}_2& =& q^{-1}\left(1+T_1+T_2+T_1{T}_2\right)=C_{12},\\ C_2{C}_1& =& q^{-1}\left(1+T_1+T_2+T_2{T}_1\right)=C_{21},\\ C_1& =& q^{-\frac{3}{2}}\left(T_1{T}_2{T}_1+T_1{T}_2+\left(q-1\right)T_1+q+T_1+T_2{T}_1+T_1+T_2+1\right)\\ & =& q^{-\frac{3}{2}}\left(T_1{T}_2{T}_1+T_1{T}_2+T_2{T}_1+T_1+T_2+1\right)+C_1,\end{array}$$ so that $$C_{121}=C_1{C}_{12}-C_1=q^{-\frac{3}{2}}\left(T_1{T}_2{T}_1+T_1{T}_2+T_2{T}_1+T_1+T_2+1\right).$$ Note that $C_1^2=\left(q^{\frac{1}{2}}+q^{-\frac{1}{2}}\right)C_1.$ Then, using that $T_i=q^{\frac{1}{2}}{C}_i-1,$ to produce the matrices for the regular representation in the $\mathrm{KL}$-basis, $$\rho \left(T_1\right)=\left(\begin{array}{cccccc}-1& 0& 0& 0& 0& 0\\ q^{\frac{1}{2}}& q& q^{\frac{1}{2}}& 0& 0& 0\\ 0& 0& -1& 0& 0& 0\\ 0& 0& 0& -1& 0& 0\\ 0& 0& 0& q^{\frac{1}{2}}& q& 0\\ 0& 0& q^{\frac{1}{2}}& 0& 0& q\end{array}\right)$$ and $$\rho \left(T_2\right)=\left(\begin{array}{cccccc}-1& 0& 0& 0& 0& 0\\ 0& -1& 0& 0& 0& 0\\ 0& q^{\frac{1}{2}}& q& 0& 0& 0\\ q^{\frac{1}{2}}& 0& 0& q& q^{\frac{1}{2}}& 0\\ 0& 0& 0& 0& -1& 0\\ 0& 0& 0& 0& q^{\frac{1}{2}}& q\end{array}\right)$$ with rows and columns indexed by $1,C_1,C_{21},C_2,C_{12},C_{121}.$

In type $B_2,$ $H=\mathrm{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 $$C_1{C}_2=C_{12},C_2{C}_1=C_{21},C_1{C}_{21}=C_{121}+C_1,C_2{C}_{12}=C_{212}+C_2,C_2{C}_{121}=C_{2121}+C_{21},$$ where $$\begin{array}{rcl}{C}_1& =& q^{-\frac{1}{2}}\left(1+T_1\right)\\ C_2& =& q^{-\frac{1}{2}}\left(1+T_2\right)\\ C_{12}& =& q^{-1}\left(1+T_1+T_2+T_1{T}_2\right)\\ C_{21}& =& q^{-1}\left(1+T_1+T_2+T_2{T}_1\right)\\ C_{121}& =& q^{-\frac{3}{2}}\left(1+T_1+T_2+T_1{T}_2+T_2{T}_1+T_1{T}_2{T}_1\right)\\ C_{212}& =& q^{-\frac{3}{2}}\left(1+T_1+T_2+T_1{T}_2+T_2{T}_1+T_2{T}_1{T}_2\right)\\ C_{1212}& =& q^{-2}\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).\end{array}$$ and the matrices of the regular representation in the KL-basis are $$\rho \left(T_1\right)=\left(\begin{array}{cccccccc}-1& 0& 0& 0& 0& 0& 0& 0\\ q^{\frac{1}{2}}& q& q^{\frac{1}{2}}& 0& 0& 0& 0& 0\\ 0& 0& -1& 0& 0& 0& 0& 0\\ 0& 0& q^{\frac{1}{2}}& q& 0& 0& 0& 0\\ 0& 0& 0& 0& -1& 0& 0& 0\\ 0& 0& 0& 0& q^{\frac{1}{2}}& q& q^{\frac{1}{2}}& 0\\ 0& 0& 0& 0& 0& 0& -1& 0\\ 0& 0& 0& 0& 0& 0& q^{\frac{1}{2}}& q\end{array}\right)$$ $$\rho \left(T_1\right)=\left(\begin{array}{cccccccc}-1& 0& 0& 0& 0& 0& 0& 0\\ 0& -1& 0& 0& 0& 0& 0& 0\\ 0& q^{\frac{1}{2}}& q& q^{\frac{1}{2}}& 0& 0& 0& 0\\ 0& 0& 0& -1& 0& 0& 0& 0\\ q^{\frac{1}{2}}& 0& 0& 0& q& q^{\frac{1}{2}}& 0& 0\\ 0& 0& 0& 0& 0& -1& 0& 0\\ 0& 0& 0& 0& 0& q^{\frac{1}{2}}& q& 0\\ 0& 0& 0& q^{\frac{1}{2}}& 0& 0& 0& q\end{array}\right)$$ with rows and columns indexed by $1,C_1,C_{21},C_{121},C_2,C_{12},C_{212},C_{1212}.$

Let $W$ be the dihedral group of order $2m.$ Then $$C_w=q^{-\frac{1}{2}l\left(w\right)}\sum _{v\le w}{T}_v,\text{so that }{p}_{vw}\left(q\right)=1,\text{ for all }v\le 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 $$\begin{array}{rcl}{C}_{s_1}& =& q^{-l\left(w\right)/2}{q}^{-1/2}\left(\sum _{v\le w}{T}_v+\sum _{v\le s_{1}w,s_{1}v<v}{T}_v+\left(q-1\right)\sum _{v<w,s_{1}v<v}{T}_v+q\sum _{v<w,s_{2}v<v}{T}_v\right)\\ & =& q^{-l\left(w\right)/2}{q}^{-1/2}\left(\sum _{v\le s_{1}w,s_{2}v<v}{T}_v+\sum _{v<w,s_{1}v<v}{T}_v+\sum _{v\le s_{1}w,s_{1}v<v}{T}_v-\sum _{v<w,s_{1}v<v}{T}_v+q\sum _{v\le s_{2}w}{T}_v\right)\\ & =& C_{s_{1}v}+q^{-l\left(w\right)/2}{q}^{\frac{1}{2}}\left(\sum _{v\le s_{2}w}{T}_v\right)\\ & =& C_{s_{1}w}+C_{s_{2}w},\end{array}$$ and, if $s_{1}w<w$ so that $w=s_1{s}_2{s}_1{s}_2\dots$ then let $w^{\text{'}}=s_{1}w$ and $w^{"}=s_2{s}_{1}w$ so that $$\begin{array}{rcl}{C}_{s_1}& =& C_{s_1}{C}_{s_1{w}^{\text{'}}}=C_{s_1}\left(C_{s_1}{C}_{w^{\text{'}}}-C_{s_2{w}^{\text{'}}}\right)\\ & =& C_{s_1}\left(C_{s_1}{C}_{w^{\text{'}}}-C_{w^{"}}\right)=\left(q^{\frac{1}{2}}+q^{-\frac{1}{2}}\right)C_{s_1}{C}_{w^{\text{'}}}-C_{s_1}{C}_{w^{"}}\\ & =& \left(q^{\frac{1}{2}}+q^{-\frac{1}{2}}\right)C_{s_1}{C}_{w^{\text{'}}}-\left(q^{\frac{1}{2}}+q^{-\frac{1}{2}}\right)C_{w^{"}},\text{by induction,}\\ & =& \left(q^{\frac{1}{2}}+q^{-\frac{1}{2}}\right)\left(C_{s_1}{C}_{w^{\text{'}}}-C_{w^{"}}\right)=\left(q^{\frac{1}{2}}+q^{-\frac{1}{2}}\right)C_w.\end{array}$$ So, $$C_{s_1}{C}_w=\left\{\begin{array}{rcl}{C}_{s_{1}w}+C_{s_{2}w},& \text{if}& s_{1}w>w,\text{ ie }w=s_2{s}_1{s}_2{s}_1\dots \\ \left(q^{\frac{1}{2}}+q^{-\frac{1}{2}}\right)C_w,& \text{if}& s_{1}w<w,\text{ ie }w=s_1{s}_2{s}_1{s}_2\dots \end{array}\right.$$ In the first case, $l\left(s_{2}w\right)<l\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 (???) $$T_1{C}_w=\left\{\begin{array}{rcl}{q}^{\frac{1}{2}}{C}_{s_{1}w}-C_w+q^{\frac{1}{2}}{C}_{s_{2}w},& \text{if}& s_{1}w>w,\text{ ie }w=s_2{s}_1{s}_2{s}_1\dots \\ q{C}_w,& \text{if}& s_{1}w<w,\text{ ie }w=s_1{s}_2{s}_1{s}_2\dots \end{array}\right.$$

For example, in the case $I_2\left(5\right),$ $$C_2{C}_1=C_{21},C_1{C}_{21}=C_{121}+C_1,C_2{C}_{121}=C_{2121}+C_{21},C_1{C}_{2121}=C_{12121}+C_{121},$$ $$C_1{C}_2=C_{12},C_2{C}_{12}=C_{212}+C_2,C_1{C}_{212}=C_{1212}+C_{12},C_2{C}_{1212}=C_{21212}+C_{212},$$ and the matrices of the regular representation in the KL-basis are: $$\rho \left(T_1\right)=\left(\begin{array}{cccccccccc}-1& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ q^{\frac{1}{2}}& q& q^{\frac{1}{2}}& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& -1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& q^{\frac{1}{2}}& q& q^{\frac{1}{2}}& 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& q^{\frac{1}{2}}& q& q^{\frac{1}{2}}& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& -1& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& q^{\frac{1}{2}}& q& 0\\ 0& 0& 0& 0& q^{\frac{1}{2}}& 0& 0& 0& 0& q\end{array}\right)$$ $$\rho \left(T_2\right)=\left(\begin{array}{cccccccccc}-1& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& -1& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& q^{\frac{1}{2}}& q& q^{\frac{1}{2}}& 0& 0& 0& 0& 0\\ 0& 0& 0& -1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& q^{\frac{1}{2}}& q& 0& 0& 0& 0& 0\\ q& 0& 0& 0& 0& q& q^{\frac{1}{2}}& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& -1& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& q^{\frac{1}{2}}& q& q^{\frac{1}{2}}& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& -1& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& q^{\frac{1}{2}}& q\end{array}\right)$$

References [PLACEHOLDER]

[Cu1] C. Curtis, Representations of Hecke Algebras, Asterisque 9, (1988), 13-60; arXiv:math/9909077v2, MR1828302 (2002e:20083)

page history