Chapter 7. Hecke algebras and Kazhdan–Lusztig polynomials
FC15 — Humphreys, Reflection Groups and Coxeter Groups.
This chapter contains 9 definitions, 4 theorems, 9 propositions, 2 lemmas, 2 corollaries, 5 examples, 8 constructions, 1 convention, 1 notation and 3 other statements.
Nobody has checked this chapter against Lean yet, so the statements below say nothing about whether they are formalized.
Convention: chapter-wide Coxeter-system notation
Throughout Chapter 7, (W,S) is an arbitrary Coxeter system; s,t denote elements of S and u,v,w,x,y,z arbitrary elements of W.
Construction: generic-algebra parameter module
Let A be a commutative ring with 1. Choose parameters a_s,b_s∈A constant on W-conjugacy classes of simple reflections, and let E be the free A-module with basis {T_w | w∈W}.
Theorem: existence and uniqueness of the generic multiplication
There is a unique associative A-algebra structure on E with T_1=1 and T_sT_w=T_{sw} when ℓ(sw)>ℓ(w), while T_sT_w=a_sT_w+b_sT_{sw} when ℓ(sw)<ℓ(w).
Definition: generic algebra
The algebra supplied by the preceding theorem is the generic algebra E_A(a_s,b_s) attached to (W,S) and the chosen parameters.
Example: group algebra as a generic algebra
Taking a_s=0 and b_s=1 for every s identifies the generic algebra with the group algebra A[W].
Result: equivalent quadratic and right-handed multiplication relations
The defining rules are equivalent to the length-increasing rule together with T_s²=a_sT_s+b_sT_1; the corresponding right-handed rules follow as well. For a reduced expression w=s_1⋯s_r, T_w=T_{s_1}⋯T_{s_r}.
Construction: left and right generic multiplication operators
Define A-linear endomorphisms λ_s and ρ_t of the free module E by the left- and right-handed versions of the generic multiplication rules on each basis vector T_w.
Lemma: four-length configuration lemma
For w∈W and s,t∈S, if ℓ(swt)=ℓ(w) and ℓ(sw)=ℓ(wt), then sw=wt, equivalently swt=w.
Proposition: commutation of left and right generic operators
For all s,t∈S, the endomorphisms λ_s and ρ_t commute on E.
Construction/result: endomorphism realization of the generic algebra
Let C⊂End_A(E) be generated by the λ_s. Evaluation φ:C→E at T_1 is an A-module isomorphism; for reduced w=s_1⋯s_r the operator λ_w=λ_{s_1}⋯λ_{s_r} is independent of the reduced expression. Transporting multiplication along φ realizes the generic algebra of §7.1.
Definition: Hecke algebra of a Coxeter system
Over A=Z[q,q^{-1}], set a_s=q−1 and b_s=q for every s. The resulting generic algebra is the Hecke algebra H of W, with standard A-basis {T_w}.
Proposition/result: invertibility of the standard Hecke basis
In H, T_s{-1}=q{-1}T_s−(1−q^{-1})T_1. Hence every T_w is invertible, by multiplying inverses along any reduced expression.
Lemma: Bruhat comparison under a left descent
If sw<w and x<w, then sx<x implies sx<sw, while sx>x implies sx<w and x<sw. In either case sx<w.
Notation: sign and q-length notation
Write ε_w=(−1)^{ℓ(w)} and q_w=q^{ℓ(w)}; extend R_{x,w} by zero when x is not ≤w.
Proposition: R-polynomial expansion of inverses
For each w, the inverse of T_{w^{-1}} has a triangular expansion in {T_x | x≤w} with coefficients ε_xR_{x,w}(q) and the standard ε_w q_w normalization. The polynomial R_{x,w} lies in Z[q], has degree ℓ(w)−ℓ(x), satisfies R_{w,w}=1, and is nonzero exactly when x≤w.
Construction/result: recursive computation of R-polynomials
If sw<w, then R_{x,w}=R_{sx,sw} when sx<x, while R_{x,w}=(q−1)R_{x,sw}+qR_{sx,sw} when x<sx; symmetric right-handed recurrences also hold.
Examples: R-polynomials in Bruhat codimension one and two
If ℓ(w)−ℓ(x)=1 then R_{x,w}=q−1; if the difference is 2 then R_{x,w}=(q−1)².
Definition: distinguished subexpressions and their statistics
For a fixed reduced word w=s_1⋯s_r, encode a subexpression by σ=(σ_0,…,σ_r), where σ_0=1 and σ_j is σ_{j−1} or σ_{j−1}s_j. Define the selected-step and descent statistics n(σ),m(σ); a subexpression is distinguished when σ_j≤σ_{j−1}s_j at every step. D(x) denotes the distinguished subexpressions ending at x.
Theorem/recorded result: Deodhar formula for R-polynomials
The source records Deodhar’s closed formula expressing R_{x,w} as a finite sum over distinguished subexpressions in D(x), with each summand a monomial q{m}(q−1){n} determined by the two statistics.
Proposition: finite-longest-element symmetry of R-polynomials
If W is finite with longest element w_0, then R_{x,w}=R_{w_0w,w_0x} for all x≤w.
Definition: bar involution on the Hecke algebra
Let the involution of A send q to q^{-1}. Extend semilinearly to H by ar T_w=(T_{w{-1}}){-1}.
Proposition/result: the bar map is an algebra involution
The semilinear bar map is multiplicative and has order two, hence is a ring automorphism of H compatible with q↦q^{-1}.
Proposition: bar-symmetry and inversion identities for R-polynomials
The R-polynomials satisfy the bar-reciprocity relation obtained by q↦q^{-1}; the bar of each T_w has a triangular R-polynomial expansion; and the resulting upper-unitriangular R-matrix has the explicit signed R-polynomial inverse, giving the Kronecker-delta convolution identity of Proposition 7.8(c).
Construction: half-power coefficient ring and initial bar-invariant elements
Enlarge A to Z[q{1/2},q{-1/2}]. The source constructs bar-invariant elements C_s for s∈S and uses their products to motivate a canonical triangular bar-invariant basis.
Theorem: Kazhdan–Lusztig basis theorem
For every w∈W there is a unique bar-invariant C_w with triangular expansion in the T_x, x≤w, whose coefficient polynomials P_{x,w}(q) satisfy P_{w,w}=1 and deg P_{x,w}≤(ℓ(w)−ℓ(x)−1)/2 for x<w.
Definition: Kazhdan–Lusztig polynomials
The polynomials P_{x,w} in the canonical-basis theorem are the Kazhdan–Lusztig polynomials; by convention P_{x,w}=0 when x is not ≤w.
Recorded conjecture: nonnegativity of Kazhdan–Lusztig coefficients
The source records the Kazhdan–Lusztig conjecture, at the time of writing, that every coefficient of every P_{x,w} is nonnegative, together with special cases then known.
Construction/result: triangular uniqueness recurrence for P{x,w}
Equating coefficients in ar C_w=C_w yields equation (21), a triangular recurrence in the R-polynomials and the already determined P_{y,w} for x<y≤w; the degree bound separates positive and negative half-powers and proves uniqueness.
Definition: top-degree relation x≺w and coefficient μ(x,w)
For x<w, write x≺w when P_{x,w} attains the largest degree allowed by the Kazhdan–Lusztig bound; μ(x,w) is the coefficient of that top power of q.
Construction/theorem: recursive existence construction of the canonical basis
If sw<w and v=sw, define C_w=C_sC_v−Σ μ(z,v)C_z over z≺v with sz<z. Expanding gives recurrence (23) for P_{x,w}; cancellation of the only potentially excessive top-degree term proves the required degree bound and hence existence.
Example: Kazhdan–Lusztig polynomials for dihedral groups
For every finite or infinite dihedral Coxeter group, P_{x,w}=1 whenever x≤w.
Example: first nontrivial Kazhdan–Lusztig polynomials in type A3
For W=S_4 with adjacent simple transpositions, the source exhibits the first rank-three cases with P_{x,w}=1+q, for the two displayed pairs (x,w).
Recorded comparison: known positivity and geometric/combinatorial computations
The source records explicit computations for H_4, universal Coxeter groups, symmetric groups and several small finite types, and the cohomological interpretation for Weyl/affine Weyl cases that yields nonnegative coefficients in those settings.
Proposition: inverse Kazhdan–Lusztig matrix for finite W
If W is finite with longest element w_0, the triangular matrix (P_{x,w}) has inverse given by the signed matrix whose entries use P_{w_0w,w_0x}; equivalently the convolution in Proposition 7.13 is the Kronecker delta.
Corollary: Eulerian alternating sum for Bruhat intervals
For x≤w, the signed sum over the Bruhat interval [x,w] is the Kronecker delta. Thus every nontrivial closed Bruhat interval contains equally many even- and odd-length elements.
Proposition: multiplication of the canonical basis by a simple Hecke generator
For s∈S: if sw<w then T_sC_w=−C_w; if w<sw, T_sC_w is the stated linear combination of C_w,C_{sw}, and C_z with z≺w, sz<z, coefficients determined by q^{1/2} and μ(z,w).
Corollary: simple-reflection invariance of Kazhdan–Lusztig polynomials
If x<w, sw
Definition: left and right descent sets
For w∈W, L(w)={s∈S | sw<w} and R(w)={s∈S | ws<w}.
Definition: left and right cell preorders and cells
Let x—w mean x≺w or w≺x. Define x≤_Lw by a chain of —-adjacent elements whose left descent sets fail the indicated inclusion; mutual reachability defines left cells. Replacing L by R gives the right preorder and right cells.
Definition: two-sided cell preorder and two-sided cells
Define ≤_{LR} by chains whose steps are left- or right-preorder steps; mutual reachability gives two-sided cells. Every two-sided cell is a union of left cells and of right cells.
Example: cells of a dihedral Coxeter group
For a dihedral group, the source determines the left/right/two-sided cells explicitly: there are three left cells in the infinite case and four in the finite case, and apart from 1 (and w_0 when finite) all elements form one two-sided cell.
Proposition: left-cell preorder refines right descent sets
If x≤_Ly then R(x)⊇R(y); consequently elements in the same left cell have equal right descent sets.
Construction: left cell modules
For a left cell Z, the span of C_w for w∈Z together with all C_x below Z in ≤_L is a left ideal; the span of the strictly lower terms is a left ideal, and the quotient M_Z is a free A-module with basis indexed by Z, affording an H-representation. Right-cell and two-sided analogues give right modules and bimodules.
Theorem/recorded result: affine Weyl cells and unipotent classes
The source records Lusztig’s results that affine Weyl groups have only finitely many one-sided (hence two-sided) cells and that their two-sided cells correspond bijectively to unipotent classes in an associated simple algebraic group.