Deodhar’s Closed Formula for Kazhdan-Lusztig Polynomials

LetW be a Coxeter group. In [5], Kazhdan and Lusztig introduced the so-called Kazhdan-Lusztig polynomials Px,y indexed by a pair of elements x and y inW, and showed that these polynomials are related to a number of problems in representation theory. The original definition of the Kazhdan-Lusztig polynomials provides a recursive formula for these polynomials. Because the fundamental importance of Kazhdan-Lusztig polynomials, varies attempts have been made in computing these polynomials as well as in searching for no-recursive formulas. Usually the computational difficulty increases dramatically with the increase of the ranks. For example, if we use the code developed by Fokko du Cloux, which is based on the original recursive formula, to compute the complete set of polynomials Px,y for all x, y ∈ W, then for A8, we will get almost 20,000,000 polynomials. Passing from A8 to A9 increases the size of the problem by a factor of 100, while passing from E7 to E8 increases the size by factor of 40,000 [3,4]. Recently, the Atlas of Lie Groups and Representations Team used a modified version of the code by Fokko du Cloux to accomplish the task of computing all Kazhdan-Lusztig polynomials for the split real group G of type E8. The result consists sixty gigabytes of files [6]. It is then natural to ask what if one uses other formulas to compute the Kazhdan-Lusztig poly-nomials. To the best of my knowledge, the first no-recursive general formula was given by Deodhar [2]. Later, another closed formula was given by Brenti [1]. In these talks, I will give an introduction to Deodhar’s algorithm, which provides a closed formula for the Kazhdan-Lusztig polynomials under the assumption that the coefficients of these polynomials are nonnegative (which is known to be true for all Weyl groups)