Implementation of the Kazhdan–Lusztig algorithm

October 29, 2007

Some notes to myself about the implementation of the K-L algorithm. The main reference are David’s notes [2] from a Park City conference.

We assume that we are given tables of the cross-actions and Cayley transforms. For s ∈ S, we denote C^{s} the Cayley transform going from more compact to less compact Cartans, C_{s} the inverse Cayley tranform. We also use γ^{s} (resp. γ_{±}^{s}) for C^{s}(γ) when C^{s} is one– (resp. two–) valued on γ; similarly γ_{s} (resp. γ_{s}^{±}) for C_{s}.

1 Hecke algebra action

We denote D the set of parameters (of course the existence of the Cayley transform and cross action tables imply that the set D has already been enumerated, and thus identified with a set [0, M[ of integers.) We let M be the free A-module generated by D, where A = Z[v, v^{−1}], and we write q = v^{2}. We replace the canonical basis (T_{δ})_{δ∈D} of M by t_{δ} = v^{−l(δ)}T_{δ}, where l : D → N is the length function (also assumed to be tabulated), and similarly denote t_{w} the corresponding basis of the Hecke algebra H of the complex Weyl group. We denote i the canonical involution on M: the unique A-antilinear involution such that

i(hm) = i(h)i(m) for all h ∈ H, m ∈ M

i(t_{δ}) = t_{δ} + ∑_{γ<δ} r(γ, δ) t_{γ} r(γ, δ) ∈ A

The Kazhdan–Lusztig basis of M is the unique basis (c_{δ})_{δ∈D} such that :

i(c_{δ}) = c_{δ} for all δ ∈ D

c_{δ} = t_{δ} + ∑_{γ<δ} p(γ, δ) t_{γ} p(γ, δ) ∈ v^{−1}Z[v^{−1}]

We denote μ(γ, δ) the coefficient of v^{−1} in p(γ, δ).

Denote M_{≤} = ⨁_{δ∈D} Z[v^{−1}]t_{δ}, M_{<} = ⨁_{δ∈D} v^{−1}Z[v^{−1}]t_{δ}. Then it is easy to show that if m ∈ M_{≤} is such that i(m) = m, there are uniquely defined integers a_{δ} such that

m = ∑_{δ∈D} a_{δ}c_{δ}

Indeed, there are certainly uniquely defined polynomials a_{δ} ∈ Z[v^{−1}] such that m = ∑_{δ∈D} a_{δ}c_{δ}, and then i(m) = m is equivalent to i(a_{δ}) = a_{δ} for all δ, which is equivalent to a_{δ} ∈ Z.

We denote τ(δ) the descent set for δ (this may also be assumed to be tabulated.) In other words, τ(δ) is the set of s that are either compact imaginary, complex such that s × δ < δ, or real type I or type II for δ. The formulas for the action of the Hecke algebra are as follows :

(a) s is compact imaginary for δ :

T_{s}.T_{δ} = q T_{δ}
t_{s}.t_{δ} = v t_{δ}
c_{s}.t_{δ} = (v + v^{−1}) t_{δ}

(b) s is noncompact imaginary type I for δ :

T_{s}.T_{δ} = T_{s×δ} + T_{δ^{s}}
t_{s}.t_{δ} = v^{−1}t_{s×δ} + t_{δ^{s}}
c_{s}.t_{δ} = v^{−1}t_{δ} + v^{−1}t_{s×δ} + t_{δ^{s}}

(c) s is noncompact imaginary type II for δ :

T_{s}.T_{δ} = T_{δ} + T_{δ_{+}^{s}} + T_{δ_{−}^{s}}
t_{s}.t_{δ} = v^{−1}t_{δ} + t_{δ_{+}^{s}} + t_{δ_{−}^{s}}
c_{s}.t_{δ} = 2v^{−1}t_{δ} + t_{δ_{+}^{s}} + t_{δ_{−}^{s}}

(d) s is complex for δ, s ∈ τ(δ) :

T_{s}.T_{δ} = (q − 1)T_{δ} + qT_{s×δ}
t_{s}.t_{δ} = (v − v^{−1})t_{δ} + t_{s×δ}
c_{s}.t_{δ} = vt_{δ} + t_{s×δ}

(e) s is complex for δ, s ∉ τ(δ) :

T_{s}.T_{δ} = T_{s×δ}
t_{s}.t_{δ} = t_{s×δ}
c_{s}.t_{δ} = v^{−1}t_{δ} + t_{s×δ}

(f) s is real type I for δ :

T_{s}.T_{δ} = (q − 2)T_{δ} + (q − 1)(T_{δ_{s}^{+}} + T_{δ_{s}^{−}})
t_{s}.t_{δ} = (v − 2v^{−1})t_{δ} + (1 − v^{−2})(t_{δ_{s}^{+}} + t_{δ_{s}^{−}})
c_{s}.t_{δ} = (v − v^{−1})t_{δ} + (1 − v^{−2})(t_{δ_{s}^{+}} + t_{δ_{s}^{−}})

(g) s is real type II for δ :

T_{s}.T_{δ} = (q − 1)T_{δ} − T_{s×δ} + (q − 1)T_{δ_{s}}
t_{s}.t_{δ} = (v − v^{−1})t_{δ} − v^{−1}t_{s×δ} + (1 − v^{−2})t_{δ_{s}}
c_{s}.t_{δ} = vt_{δ} − v^{−1}t_{s×δ} + (1 − v^{−2})t_{δ_{s}}

(h) s is real for δ, s ∉ τ(δ) :

T_{s}.T_{δ} = −T δ
t_{s}.t_{δ} = −v^{−1}t_{δ}
c_{s}.t_{δ} = 0

2 Bruhat ordering

It turns out that there are in fact a number of orderings that one could use for the computation of Kazhdan–Lusztig polynomials. And in fact, what I am probably going to do is take the radical step of not using Bruhat order at all! (or rather, use the ordering where γ ≤ δ iff γ = δ or l(γ) < l(δ).)

What we want from a “Bruhat ordering” is that (a) it is compatible with length (i.e., weaker than the ordering described above, which we shall call the length ordering), and that (b) p_{γ,δ} ≠ 0 implies γ ≤ δ. Obviously, there is a strongest such ordering (the length ordering) and a weakest one (the one generated by the relations p_{γ,δ} ≠ 0.) Surprisingly, those two extremes do not seem to be all that far apart; even more so if instead of the weakest one, which seems rather hard to get at (is it even clear that it is graded?) we use one of the natural candidates, such as the one described in [2]. In all the cases I computed, which included the large block for type E_{7}, more than half the comparable pairs for the length ordering were also comparable for the Bruhat ordering in [2].

Recall the definition. Write δ →^{s} δ′ if s is a strict descent for δ (i.e., a complex descent, or real type I or II), and δ′ = s × δ if s is a complex descent, δ′ ∈ C_{s}(δ) is s is real. Now let δ, γ ∈ D. Then we say that γ < δ iff there exists an s ∈ S with δ →^{s} δ′, and either γ ≤ δ′, or there is a γ′ < δ′ such that γ →^{s} γ′. It should be fairly easy to show, pretty much as for the ordinary Bruhat order, that this ordering is graded, with degree being given by the length function. Then, in order to describe it, it suffices to give the covering relations.

As David pointed out to me, this ordering suffers from a lack of symmetry when passing over to the dual; one should want that the duality is orderreversing for the Bruhat ordering. As he explained, one solution would be to make the ordering even stronger, essentially by imposing that in the situation where δ →^{s} δ′, γ →^{s} γ′, one has γ < δ iff γ′ < δ′. It is not clear to me whether this definition is susceptible of a recursive construction; perhaps something of doing it as previously, and then applying symmetrizing passes until symmetry is achieved ?

Another solution, that would make the order weaker, would be to take the “product ordering” for the two projections on orbit sets, where on the orbit sets one takes the closure ordering as described combinatorially in Richardson and Springer [1]. I think this is an acceptable ordering, but this needs to be re-checked.

3 Kazhdan–Lusztig polynomials

Denote c_{δ} the Kazhdan-Lusztig basis. In order to compute the c_{δ}, we use two kinds of formulas :

I. Let s ∈ τ(δ) (recall that this means that s is either imaginary compact, real in the domain of the inverse Cayley transform, or complex with s × δ < δ.) then we have :

c_{s}.c_{δ} = (v + v^{−1}) c_{δ}  (1)

This is Lemma 6.7 (b) in [2]. This yields the “easy case” induction formulas (second case type II in [2]) : p_{γ,δ} = v^{−1}p_{γ^{s},δ} for s imaginary type I w.r.t. γ p_{γ,δ} = v^{−1}(p_{γ_{+}^{s},δ} + p_{γ_{−}^{s},δ}) for s imaginary type II w.r.t. γ p_{γ,δ} = v^{−1}p_{s×γ,δ} for s complex ascent w.r.t. γ p_{γ,δ} = 0 for s real nonparity w.r.t. γ

Indeed, we have :

c_{s}.c_{δ} = ∑_{γ≤δ} p_{γ,δ} c_{s}.t_{γ} = ∑_{{γ<δ \atop s compact}}(v + v^{−1})p_{γ,δ}t_{γ}

+ ∑_{γ<δ s type I imaginary}[v^{−1}(p_{γ,δ} + p_{s×γ,δ}) + (1 − v^{−2})p_{γ^{s},δ}]t_{γ}

+ ∑_{γ<δ s type II imaginary}[2v^{−1}p_{γ,δ} + (1 − v^{−2})(p_{γ_{+}^{s},δ} + p_{γ_{−}^{s},δ})]t_{γ}

+ ∑_{γ<δ s complex descent}(vp_{γ,δ} + p_{s×γ,δ})t_{γ} + ∑_{γ<δ s complex ascent}(v^{−1}p_{γ,δ} + p_{s×γ,δ})t_{γ}

+ ∑_{γ<δ ; s type I real}[(v − v^{−1})p_{γ,δ} + p_{γ_{s}^{+},δ} + p_{γ_{s}^{−},δ}]t_{γ}

+ ∑_{γ<δ s type II real}[vp_{γ,δ} − v^{−1}p_{s×γ,δ} + p_{γ_{s},δ}]t_{γ} + ∑_{γ<δ s real nonparity} 0.t_{γ}

Consider now the four cases where s is an ascent for γ :

(a) s is noncompact type I imaginary with respect to γ. Then (1) yields :

v^{−1}(p_{γ,δ} + p_{s×γ,δ}) + (1 − v^{−2})p_{γ^{s},δ} − (v + v^{−1})p_{γ,δ} = 0  (2)

But the same equation for γ^{s} yields :

(v − v^{−1})p_{γ^{s},δ} + p_{γ,δ} + p_{s×γ,δ} − (v + v^{−1})p_{γ^{s},δ} = 0

Multiplying by v^{−1}, and using (2), we get

(v + v^{−1})(p_{γ,δ} − v^{−1}p_{γ^{s},δ}) = 0

whence p_{γ,δ} = v^{−1}p_{γ^{s},δ}.

(b) s is noncompact type II imaginary with respect to γ. Then (1) yields :

2v^{−1}p_{γ,δ} + (1 − v^{−2})(p_{γ_{+}^{s},δ} + p_{γ_{−}^{s},δ}) − (v + v^{−1})p_{γ,δ} = 0 (3)

But the same equation for γ_{+}^{s} and γ_{−}^{s} yields :

vp_{γ_{+}^{s},δ} − v^{−1}p_{γ_{−}^{s},δ} + p_{γ,δ} − (v + v^{−1})p_{γ_{+}^{s},δ} = 0

vp_{γ_{−}^{s},δ} − v^{−1}p_{γ_{+}^{s},δ} + p_{γ,δ} − (v + v^{−1})p_{γ_{−}^{s},δ} = 0

Multiplying by v^{−1}, adding up and combining with (3) yields : (v + v^{−1})(p_{γ,δ} − v^{−1}(p_{γ_{+}^{s},δ} + p_{γ_{−}^{s},δ})) = 0

whence p_{γ,δ} = v^{−1}(p_{γ_{+}^{s},δ} + p_{γ_{−}^{s},δ}).

(c) s is complex for γ, s ∉ τ(γ). Then (1) yields

v^{−1}p_{γ,δ} + p_{s×γ,δ} − (v + v^{−1})p_{γ,δ} = 0  (4)

The same equation for s × γ yields :

vp_{s×γ,δ} + p_{γ,δ} − (v + v^{−1})p_{s×γ,δ} = 0

Multiplying by v^{−1} and combining with (4) yields :

(v + v^{−1})(p_{γ,δ} − v^{−1}p_{s×γ,δ}) = o

whence p_{γ,δ} = v^{−1}p_{s×γ,δ}.

(d) s is real for γ, s ∉ τ(γ). Then (1) yields :

(v + v^{−1})p_{γ,δ} = 0

whence p_{γ,δ} = 0.

II. Let s ∉ τ(δ). Then there are four cases to consider :

(a) s is complex for δ, s × δ > δ. Then :

c_{s}.c_{δ} = c_{s×δ} + ∑_{{ζ<δ \atop s∈τ(ζ)}} μ(ζ, δ) c_{ζ}

(b) s is imaginary noncompact type I for δ. Then :

c_{s}.c_{δ} = c_{δ^{s}} + ∑_{{ζ<δ \atop s∈τ(ζ)}} μ(ζ, δ) c_{ζ}

(c) s is imaginary noncompact type II for δ. Then :

c_{s}.c_{δ} = c_{δ_{+}^{s}} + c_{δ_{−}^{s}} + ∑_{{ζ<δ \atop s∈τ(ζ)}} μ(ζ, δ) c_{ζ}

(d) s is real nonparity for δ. Then :

c_{s}.c_{δ} = ∑_{{ζ<δ \atop s∈τ(ζ)}} μ(ζ, δ) c_{ζ}

III. Of course, in practice one would like to use the formulas in II for expressing c_{δ} in terms of lower parameters. This works as follows :

(a) s is complex for δ, s × δ < δ. Then :

c_{δ} = c_{s}.c_{s×δ} − ∑_{{ζ<s×δ \atop s∈τ(ζ)}} μ(ζ, s × δ) c_{ζ}

(b) s is real type I for δ. Then :

c_{δ} = c_{s}.c_{δ_{s}^{+}} − ∑_{{ζ<δ_{s}^{+} \atop s∈τ(ζ)}} μ(ζ, δ_{s}^{+}) c_{ζ}

(here δ_{s}^{−} might have been used just as well instead of δ_{s}^{+}.)

(c) s is real type II for δ. Then :

c_{δ} + c_{s×δ} = c_{s}.c_{δ_{s}} − ∑_{{ζ<δ_{s} \atop s∈τ(ζ)}} μ(ζ, δ_{s}) c_{ζ}

The last of these formulas is the one that doesn’t directly give a recursion, and where the “structural fact” of Lemma 6.2 in [2] has to be used to show that the recursion can be gotten to go through. More specifically, if G(δ) is the connected component of δ in the graph where the edges are the (δ, s×δ) corresponding to generators in case (c) above, then for each fixed γ < δ there will be a δ′ ∈ G(δ) for which s is an ascent, allowing p_{γ,δ′} to be computed through one of the “easy” formulas obtained in I. Then the equations can be solved to get all the p_{γ,δ′′}, δ′′ ∈ G(δ).

In terms of polynomials, if we set δ′ to be s × δ in case (a), δ_{s}^{+} in case (b), and δ_{s} in case (c), we get the following formulas for γ < δ, where lhs denotes p_{γ}, δ in the first two cases, p_{γ,δ} + p_{γ,s×δ} in case (c)

(a) when s is a complex descent for γ :

lhs = v p_{γ,δ′} + p_{s×γ,δ′} − ∑_{γ≤ζ<δ′} μ(ζ, δ′)p_{γ,ζ}

(b) s is real type I for γ. Then :

lhs = (v − v^{−1})p_{γ,δ′} + p_{γ_{s}^{+},δ′} + p_{γ_{s}^{−},δ′} − ∑_{γ≤ζ<δ′} μ(ζ, δ′)p_{γ,ζ}

(c) s is real type II for γ. Then :

lhs = v p_{γ,δ′} − v^{−1}p_{s×γ,δ′} + p_{γ_{s},δ′} − ∑_{γ≤ζ<δ′} μ(ζ, δ′)p_{γ,ζ}

(d) s is imaginary noncompact for γ. Then :

lhs = (v + v^{−1})p_{γ,δ′} − ∑_{γ≤ζ<δ′} μ(ζ, δ′)p_{γ,ζ}

References

[1] Roger W. Richardson and Tonny A. Springer. The Bruhat Order on Symmetric Varieties. GeometriæDedicata, 35:389–436, 1990.

[2] David A. Vogan, Jr. The Kazhdan-Lusztig conjecture for real reductive groups. In Representation Theory of Reductive Groups (Park City, Utah, 1982), volume 40 of Progress in Mathematics, pages 223–264, Boston, Mass., 1983. Birkhäuser.