Computing Kazhdan-Lusztig polynomials for arbitrary Coxeter groups. (English) Zbl 1101.20304

Summary: Let \((W,S)\) be an arbitrary Coxeter system, \(y\in 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\leq z\leq y\). The correctness proof of the algorithm is based on a remarkable theorem due to Matthew Dyer.


20F55 Reflection and Coxeter groups (group-theoretic aspects)
05E15 Combinatorial aspects of groups and algebras (MSC2010)
20C40 Computational methods (representations of groups) (MSC2010)
68W30 Symbolic computation and algebraic computation


Full Text: DOI Euclid EuDML


[1] Bourbaki N., Groupes et algèbres de Lie, Chap. 4–6. (1968) · Zbl 0186.33001
[2] DOI: 10.1007/BF01445101 · Zbl 0793.20036 · doi:10.1007/BF01445101
[3] Casselman W., Representation Theory 4 pp 32– (2000) · Zbl 1045.20038 · doi:10.1090/S1088-4165-00-00052-2
[4] Casselman, W. [Casselman 01],www.math.ubc.ca/people/faculty/cass/cass.html
[5] Casselman W., Electron. J. Combin. 9 (1) pp 22– (2002)
[6] DOI: 10.1007/BF01199813 · Zbl 0688.20028 · doi:10.1007/BF01199813
[7] du Cloux F., Coxeter
[8] du Cloux F., J. Symbolic Computation 27 pp 311– (1999) · Zbl 0973.20031 · doi:10.1006/jsco.1998.0254
[9] du Cloux F., Europ. J. Combinatorics 21 pp 197– (2000) · Zbl 0953.05083 · doi:10.1006/eujc.1999.0343
[10] Dyer M., PhD thesis, in: Hecke algebras and reflections in Coxeter groups. (1987)
[11] DOI: 10.1016/0021-8693(90)90149-I · Zbl 0712.20026 · doi:10.1016/0021-8693(90)90149-I
[12] Dyer M., Compositio Math. 78 pp 185– (1991)
[13] Goresky M., ”Tables of Kazhdan-Lusztig poly-omials.”
[14] Humphreys J. E., Reflection Groups and Coxeter Groups. (1990) · Zbl 0725.20028 · doi:10.1017/CBO9780511623646
[15] DOI: 10.1007/BF01390031 · Zbl 0499.20035 · doi:10.1007/BF01390031
[16] Stanley R. P., Enumerative Combinatorics. (1997) · Zbl 0889.05001 · doi:10.1017/CBO9780511805967
[17] Verma D.-N., Ann. Sci. Ec. Norm. Sup. 4 pp 393– (1971) · Zbl 0236.20035 · doi:10.24033/asens.1215
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.