Computing Kazhdan-Lusztig Polynomials for Arbitrary Coxeter Groups

Abstract

Let (W, S) be an arbitrary Coxeter system, y ∊ S*. We describe an algorithm which will compute, directly from y and the Coxeter matrix of W, the interval from the identity to y in the Bruhat ordering, together with the (partially defined) left and right actions of the generators. This provides us with exactly the data that are needed to compute the Kazhdan-Lusztig polynomials P _{x, z} , x ≤ z ≤ y. The correctness proof of the algorithm is based on a remarkable theorem due to Matthew Dyer

Keywords:

• Kazhdan-Lusztig polynomials
• computational group theory