using the fact that the two terms on the left are polynomials in "q"1/2 and "q"−1/2 without constant terms.These formulas are tiresome to use by hand for rank greater than about 3, but are well adapted for computers, and the only limit on computing Kazhdan-Lusztig polynomials with them is that for large rank the number of such polynomials exceeds the storage capacity of computers.
Examples
*If "y" ≤ "w" then "P""y","w" has constant term 1.
*If "y" ≤ "w" and "l"("w") − "l"("y") is 0, 1, or 2 then "P""y","w" = 1.
*If "w" is the longest element of a finite Coxeter group then "P""y","w" = 1
*If "W" is the Coxeter group "A"1 or "A"2 (or more generally any Coxeter group of rank at most 2) then "P""y","w" is 1 if "y"≤"w" and 0 otherwise.
*If "W" is the Coxeter group "A"3 with generating set "S" = {"a", "b", "c"} with "a" and "c" commuting then "P""b","bacb" = 1 + "q" and "P""ac","acbca" = 1 + "q", giving examples of non-constant polynomials.
*The simple values of Kazhdan-Lusztig polynomials for low rank groups are not typical of higher rank groups. For example, for the split form of E8 the [http://www.liegroups.org/kle8.html most complicated Lusztig-Vogan polynomial] (a variation of Kazhdan-Lusztig polynomials: see below) is:: In fact any polynomial with constant term 1 and non-negative integer coefficients is the Kazhdan-Lusztig polynomial for some pair of elements of some symmetric group.
Kazhdan-Lusztig conjectures
The Kazhdan-Lusztig polynomials arise as transition coefficients between their canonical basis and the natural basis of the Hecke algebra. The "Inventiones" paper also put forth two equivalent conjectures, known now as Kazhdan-Lusztig conjectures, which related the values of their polynomials at 1 with representations of complex semisimple Lie groups and Lie algebras, addressing a long-standing problem in representation theory.
Let "W" be a finite Weyl group. For each w ∈ "W" denote by "M""w" be the Verma module of highest weight −"w"(ρ)−ρ where ρ is the half-sum of positive roots (or Weyl vector), and let "L""w" be its irreducible quotient, the simple highest weight module of highest weight −"w"(ρ) − ρ. Both "M""w" and "L""w" are locally-finite weight modules over the complex semisimple Lie algebra "g" with the Weyl group "W", and therefore admit an algebraic character. Let us write ch("X") for the character of a "g"-module "X".The Kazhdan-Lusztig conjectures state:
:
:
where w0 is the element of maximal length of the Weyl group.
These conjectures were proved independently by Alexander Beilinson and Joseph Bernstein (1981) and by Jean-Luc Brylinski and Masaki Kashiwara (1981). The methods introduced in the course of the proof have guided development of representation theory throughout the 1980s and 1990s, under the name "geometric representation theory".
Remarks
1. The two conjectures are known to be equivalent. Moreover, Borho-Jantzen's translation principle implies that ρ can be replaced by any dominant regular integral weight. Thus, Kazhdan-Lusztig conjectures describe the Jordan-Hölder multiplicities of Verma modules in any regular integral block of Bernstein-Gelfand-Gelfand category O.
2. A similar interpretation of "all" coefficients of Kazhdan-Lusztig polynomials follows from the "Jantzen conjecture", which roughly says that individual coefficients of "Py,w" are multiplicities of "L""y" in certain subquotient of the Verma module determined by a canonical filtration, the "Jantzen filtration". The Jantzen conjecture in regular integral case was proved in a later paper of Beilinson and Bernstein.
3. David Vogan showed as a consequence of the conjectures that
:
and that Ext"j"("M""y","L""w") vanishes if "j" + "ℓ"("w") + "ℓ"("y") is odd, so the dimensions of all such Ext groups in category "O" are determined in terms of coefficients of Kazhdan-Lusztig polynomials. This result demonstrates that all coefficients of the Kazhdan-Lusztig polynomials of a finite Weyl group are non-negative integers. However, positivity for the case of a finite Weyl group "W" was already known from the interpretation of coefficients of the Kazhdan-Lusztig polynomials as the dimensions of intersection cohomology groups, irrespective of the conjectures. Conversely, the relation between Kazhdan-Lusztig polynomials and the Ext groups theoretically can be used to prove the conjectures, although this approach to proving them turned out to be more difficult to carry out.
4. Some special cases of the Kazhdan-Lusztig conjectures are easy to verify. For example, "M"1 is the antidominant Verma module, which is known to be simple. This means that "M"1 = "L"1, establishing the second conjecture for "w" = 1, since the sum reduces to a single term. On the other hand, the first conjecture for "w" = "w"0 follows from the Weyl character formula and the formula for the character of a Verma module, together with the fact that all Kazhdan-Lusztig polynomials are equal to 1.
5. Kashiwara (1990) proved a generalization of the Kazhdan-Lusztig conjectures to symmetrizable Kac-Moody algebras.
Relation to intersection cohomology of Schubert varieties
By the Bruhat decomposition the space "G"/"B" of the algebraic group "G" with Weyl group "W" is a disjoint union of affine spaces "X""w" parameterized by elements "w" of "W". The closures of these spaces "X""w" are called Schubert varieties, and Kazhdan and Lusztig, following a suggestion of Deligne, showed how to express Kazhdan-Lusztig polynomials in terms of intersection cohomology groups of Schubert varieties.
More precisely, the Kazhdan-Lusztig polynomial "P""y","w"("q") is equal to :where each term on the right means: take the complex IC of sheaves whose hyperhomology is the intersection homology of the Schubert variety of "w" (the closure of the cell "X""w"), take its cohomology of degree 2"i", and then take the dimension of the stalk of this sheaf at any point of the cell "X""y" whose closure is the Schubert variety of "y". The odd dimensional cohomology groups do not appear in the sum because they are all zero.
This gave the first proof that all coefficients of Kazhdan-Lusztig polynomials for finite Weyl groups are non-negative integers.
Generalization to real groups
Lusztig-Vogan polynomials (also called Kazhdan-Lusztig polynomials or Kazhdan-Lusztig-Vogan polynomials) were introduced in Lusztig and Vogan (1983). They are analogous to Kazhdan-Lusztig polynomials, but are tailored to representations of "real" semisimple Lie groups, and play major role in the conjectural description of their unitary duals. Their definition is more complicated, reflecting relative complexity of representations of real groups compared to complex groups.
The distinction, in the cases directly connection to representation theory, is explained on the level of double cosets; or in other terms of actions on analogues of complex flag manifolds "G"/"B" where "G" is a complex Lie group and "B" a Borel subgroup. The original (K-L) case is then about the details of decomposing
:"B""G"/"B",
a classical theme of the Bruhat decomposition, and before that of Schubert cells in a Grassmannian. The L-V case takes a real form "G""R" of "G", a maximal compact subgroup "K""R" in that semisimple group "G""R", and makes the complexification "K" of "K""R". Then the relevant object of study is
:"K""G"/"B".
In March 2007, it was announced that the L-V polynomials had been calculated for the split form of "E"8.
Generalization to other objects in representation theory
The second paper of Kazhdan and Lusztig established a geometric setting for definition of Kazhdan-Lusztig polynomials, namely, the geometry of singularities of Schubert varieties in the flag variety. Much of the later work of Lusztig explored analogues of Kazhdan-Lusztig polynomials in the context of other natural singular algebraic varieties arising in representation theory, in particular, closures of nilpotent orbits and quiver varieties. It turned out that the representation theory of quantum groups, modular Lie algebras and affine Hecke algebras are all tightly controlled by appropriate analogues of Kazhdan-Lusztig polynomials. They admit an elementary description, but the deeper properties of these polynomials necessary for representation theory follow from sophisticated techniques of modern algebraic geometry and homological algebra, such as the use of intersection cohomology, perverse sheaves and "Beilinson-Bernstein-Deligne decomposition".
Combinatorial theory
Combinatorial properties of Kazhdan-Lusztig polynomials and their generalizations are a topic of active current research. Given their significance in representation theory and algebraic geometry, attempts have been undertaken to develop the theory of Kazhdan-Lusztig polynomials in purely combinatorial fashion, relying to some extent on geometry, but without reference to intersection cohomology and other advanced techniques. This has led to exciting developments in algebraic combinatorics, such as "pattern-avoidance phenomenon". Some references are given in the textbook of Bjorner and Brenti. A research monograph on the subject is Billey and Lakshmibai.
As of 2005, there is no known combinatorial interpretation of all the coefficients of the Kazhdan-Lusztig polynomials (as the cardinalities of some natural sets) even for the symmetric groups, though explicit formulas exist in many special cases.
References
*Beilinson, Alexandre; Bernstein, Joseph "Localisation de g-modules." C. R. Acad. Sci. Paris Sér. I Math. 292 (1981), no. 1, 15–18.
* Citation
last1=Billey
first1=Sara
author1-link=
last2=Lakshmibai
first2=V.
author2-link=
title=Singular loci of Schubert varieties
year=2000
series=Progress in Mathematics
volume=182 of "Progress in Mathematics"
publisher=Birkhäuser Boston, Inc., Boston, MA
isbn=0-8176-4092-4
* Citation
last1=Björner
first1=Anders
author1-link=
last2=Brenti
first2=Francesco
author2-link=
chapter=Ch. 5: Kazhdan–Lusztig and "R-"polynomials
title=Combinatorics of Coxeter Groups
year=2005
series=Graduate Texts in Mathematics
volume=231 of "Graduate Texts in Mathematics"
publisher=Springer
isbn=978-3-540-44238-7
* Citation
last=Brenti
first=Francesco
author-link=
title=Kazhdan-Lusztig Polynomials: History, Problems, and Combinatorial Invariance
year=2003
journal=Séminaire Lotharingien de Combinatoire, B49b
volume=49
publisher=Haus Schönenberg
place=Ellwangen
url=http://www.emis.de/journals/SLC/wpapers/s49brenti.html
* Citation
last1=Brylinski
first1=Jean-Luc
author1-link=Jean-Luc Brylinski
last2=Kashiwara
first2=Masaki
author2-link=Masaki Kashiwara
title=Kazhdan-Lusztig conjecture and holonomic systems
year=1981
month=October
volume=64
number=3
journal=Inventiones Mathematicae
publisher=Springer-Verlag
pages=387–410
issn=0020-9910
doi=10.1007/BF01389272
*M. Kashiwara, "The Kazhdan-Lusztig conjecture for symmetrizable KacMoody algebras", in: "The Grothendieck Festschrift, II", Birkhauser, Progress in Mathem. 87, Boston, 1990, pp. 407–433. MathSciNet|id=93a:17026
* Citation
last1=Kazhdan
first1=David
author1-link=David Kazhdan
last2=Lusztig
first2=George
author2-link=George Lusztig
title=Representations of Coxeter groups and Hecke algebras
year=1979
month=June
volume=53
number=2
journal=Inventiones Mathematicae
publisher=Springer-Verlag
pages=165–184
issn=0020-9910
doi=10.1007/BF01390031
* Citation
last1=Kazhdan
first1=David
author1-link=David Kazhdan
last2=Lusztig
first2=George
author2-link=George Lusztig
title=Schubert varieties and Poincaré duality
year=1980
journal=Proc. Sympos. Pure Math., XXXVI
publisher=American Mathematical Society
pages=185–203
* Citation
last1=Lusztig
first1=George
author1-link=George Lusztig
last2=Vogan
first2=David
author2-link=David Vogan
title=Singularities of closures of K-orbits on flag manifolds.
year=1983
month=
volume=71
number=2
journal=Inventiones Mathematicae
publisher=Springer-Verlag
pages=365–379
issn=0020-9910
doi=10.1007/BF01389103
External links
* [http://www.math.ucdavis.edu/~vazirani/S05/KL.details.html Readings] from Spring 2005 course on Kazhdan-Lusztig Theory at U.C. Davis by Monica Vazirani
*Goresky's [http://www.math.ias.edu/~goresky/tables.html tables] of Kazhdan-Lusztig polynomials.
*The GAP [http://schmidt.ucg.ie/gap/CHAP083.htm programs] for computing Kazhdan-Lusztig polynomials.
*Atlas [http://atlas.math.umd.edu/software/ software] for computing Kazhdan-Lusztig polynomials.