Kazhdan-Lusztig polynomials and bases

Chevie.KL — Module

This module defines Kazhdan-Lusztig polynomials and bases, and computes W-graphs and asymptotic algebras.

Let ℋ be the Iwahori-Hecke algebra of a Coxeter system (W,S), with quadratic relations (Tₛ-uₛ₀)(Tₛ-uₛ₁)=0 for s∈ S. If -uₛ₀uₛ₁ has a square root wₛ, we can scale the basis Tₛ to get a new basis tₛ=-Tₛ/wₛ with quadratic relations (tₛ-vₛ)(tₛ+vₛ⁻¹)=0 where vₛ=wₛ/uₛ₁. The most general case when Kazhdan-Lusztig bases and polynomials can be defined is when the parameters vₛ belong to a totally ordered abelian group Γ for multiplication, see Lusztig1983. We set Γ⁺= {γ∈ Γ∣γ>0} and Γ⁻={γ⁻¹∣γ∈ Γ⁺}={γ∈ Γ∣γ<0}.

Thus we assume ℋ defined over the ring ℤ[Γ], the group algebra of Γ over ℤ, and the quadratic relations of ℋ associate to each s∈ S a vₛ∈ Γ⁺ such that (tₛ-vₛ)(tₛ+vₛ⁻¹)=0. We also set qₛ=vₛ² and define the basis Tₛ=vₛtₛ with quadratic relations (Tₛ-qₛ)(Tₛ+1)=0; for w∈ W with reduced expression w=s₁…sₙ we define $q_w∈ Γ⁺$ by $q_w^½=v_{s₁}…v_{sₙ}$ and let $q_w=(q_w^½)²$; we have $T_w=q_w^½t_w$.

We define the bar involution on ℋ by linearity: on ℤ[Γ] we define it by $\overline{∑_{γ∈ Γ}a_γγ}= ∑_{γ∈ Γ} a_γ γ⁻¹$ and we extend it to ℋ by $\overline T_s=T_s^{-1}$ (equivalently $\overline t_s=t_s^{-1}$). Then the Kazhdan-Lusztig basis $C^′_w$ is defined as the only basis of ℋ stable by the bar involution and congruent to $t_w$ modulo $∑_{w∈ W}Γ⁻.t_w$.

The basis $C^′_w$ can be computed as follows. We define elements $R_{x,y}$ of ℤ[Γ] by $T_y⁻¹=∑_x \overline{R_{x,y⁻¹}} q_x⁻¹T_x$. We then define inductively the Kazhdan-Lusztig polynomials (in this general context we should say the Kazhdan-Lusztig elements of ℤ[Γ], which belong to the subalgebra of ℤ[Γ] generated by the qₛ) by $P_{x,w}=τ_{≤(q_w/q_x)^½} (∑_{x<y≤w}R_{x,y}P_{y,w})$ where τ is the truncation: $τ_≤\nu ∑_{γ∈ Γ} a_γγ= ∑_{γ≤\nu}a_γγ$; the induction is thus on decreasing x for the Bruhat order and starts at $P_{w,w}=1$. We have then $C^′_w=∑_y q_w^{-1/2} P_{y,w}T_y$.

The Chevie code for the Kazhdan-Lusztig bases C, D, C', D', was originally written by Andrew Mathas around 1994, who also contributed to the design of bases of Iwahori-Hecke algebras and implemented some other bases, such as the Murphy basis. Our code evolved from that code. The code for the case of unequal parameters was written around 1999 by F.Digne and J.Michel. The Kazhdan-Lusztig bases are computed starting from the C′ basis.

When the ℤ[Γ] is a Laurent polynomial ring the bar operation is taking the inverse of the variables, and truncation is keeping terms of degree smaller or equal to that of ν. It is possible to use arbitrary groups Γ as long as methods bar:$∑_{γ∈ Γ} a_γγ↦ ∑_{γ∈ Γ} a_γγ⁻¹$, positive_part : $∑_{γ∈ Γ} a_γγ↦ ∑_{γ≥ 1} a_γγ$ and negative_part: $∑_{γ∈ Γ} a_γγ ↦ ∑_{γ≤ 1} a_γγ$ have been defined on ℤ[Γ]. These operations will be used internally by the programs to compute Kazhdan-Lusztig bases.

We provide also functionality to study the Kazhdan-Lusztig left cells (for the equal-parameter Hecke algebra).

julia> W=coxgroup(:H,3)
H₃

julia> c=left_cells(W)
22-element Vector{LeftCell{FiniteCoxeterGroup{Perm{Int16},Cyc{Int64}}}}:
 LeftCell<H₃: duflo= character=φ₁‚₀>
 LeftCell<H₃: duflo=123 character=φ₁‚₁₅>
 LeftCell<H₃: duflo=(15) character=φ₅‚₅>
 LeftCell<H₃: duflo=(10) character=φ₅‚₅>
 LeftCell<H₃: duflo=(14) character=φ₅‚₅>
 LeftCell<H₃: duflo=7 character=φ₅‚₅>
 LeftCell<H₃: duflo=(12) character=φ₅‚₅>
 LeftCell<H₃: duflo=(9,12) character=φ₅‚₂>
 LeftCell<H₃: duflo=(5,11) character=φ₅‚₂>
 LeftCell<H₃: duflo=13 character=φ₅‚₂>
 ⋮
 LeftCell<H₃: duflo=(8,13) character=φ₃‚₆+φ₃‚₈>
 LeftCell<H₃: duflo=(1,15) character=φ₃‚₆+φ₃‚₈>
 LeftCell<H₃: duflo=3 character=φ₃‚₁+φ₃‚₃>
 LeftCell<H₃: duflo=2 character=φ₃‚₁+φ₃‚₃>
 LeftCell<H₃: duflo=1 character=φ₃‚₁+φ₃‚₃>
 LeftCell<H₃: duflo=6 character=φ₄‚₃+φ₄‚₄>
 LeftCell<H₃: duflo=(13) character=φ₄‚₃+φ₄‚₄>
 LeftCell<H₃: duflo=(11) character=φ₄‚₃+φ₄‚₄>
 LeftCell<H₃: duflo=9 character=φ₄‚₃+φ₄‚₄>

see also the functions elements, character, representation and Wgraph for left cells. The operations length, in (which refer to elements) and == (which compares Duflo involutions) are also defined for left cells. When character(c) has been computed, then c.a also has been bound which holds the common value of Lusztig's a-function for the elements of c and the irreducible constituents of character(c).

finally, benchmarks

julia> function test_kl(W)
         q=Pol(); H=hecke(W,q^2,rootpara=q)
         C=Cpbasis(H); T=Tbasis(H)
         [T(C(w)) for w in elements(W)]
       end
test_kl (generic function with 1 method)

julia> @btime test_kl(coxgroup(:F,4));  #julia 1.8
1.332 s (13934392 allocations: 2.27 GiB)

in GAP3 the following function takes 11s for W=F4

test_kl:=function(W)local q,H,T,C;
  q:=X(Rationals);H:=Hecke(W,q^2,q);
  T:=Basis(H,"T");C:=Basis(H,"C'");
  List(Elements(W),e->T(C(e)));
end;

Another benchmark:

function test_kl2(W)
  el=elements(W)
  [KLPol(W,x,y) for x in el, y in el]
end

test_kl2 (generic function with 1 method)

julia>@btime test_kl2(coxgroup(:F,4)); # julia 1.9
4.307 s (42294917 allocations: 5.24 GiB)

in GAP3 the following function takes 42s for F4

test_kl2:=function(W)local el;
  el:=Elements(W);
  List(el,x->List(el,y->KazhdanLusztigPolynomial(W,x,y)));
end;