MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

When studying the combinatorics and representation of Coxeter groups, I often find it irksome to compute KL- and R- polynomials from scratch on Maple or Sage. The time it consumes to generate a complete list for all pairs of elements of a Coxeter group soon becomes unbearable as the magnitude of the group increases.

Surprisingly, the only one I could find is a small one by Mark Goresky(link text) obtained in 1996. Is there a more comprehensive list of such polynomials?

It seems meaningful work to generate such lists, compared with calculating the next biggest known prime number.

share|cite|improve this question
It's important to be specific about which Coxeter groups you are looking at, since the computations can get arbitrarily long and may not be instantly informative. Goresky's tables for Weyl groups and affine Weyl groups of low ranks are certainly useful (and as far as I know accurate). But the need to select a single reduced expression for each group element inevitably causes some trouble. While the newer computer methods of du Cloux, Adams, and others are improved, the main focus is just on finite Weyl groups including the notorious $E_8$. – Jim Humphreys Mar 17 '13 at 17:56
P.S. Maybe a tag co.combinatorics is more directly relevant here than rt? Of course, applications tend to involve representation theory, but combinatorists (and sometimes algebraic geometers) have also been active in studying the polynomials. – Jim Humphreys Mar 17 '13 at 17:59
@Jim: Currently I'm focused on symmetric groups since that is the easiest to work on. Indeed, Goresky specified elements of S_n by their reduced expressions and made the table very un-readable. – Harry Huang Mar 18 '13 at 2:06
How about PyCox? ( For type A, see also (and the author's C code available at – Shunsuke Tsuchioka Mar 18 '13 at 2:51
Thanks @Shunsuke, that's something novel to me. But what I'm looking for is like a list of prime numbers... – Harry Huang Mar 18 '13 at 12:18

I have placed data files containing the polynomials for $S_n$ with $n\in \{4,5,6,7,8,9\}$ here. The corresponding file for $S_{10}$ is a few gigabytes as a plain text file; I could certainly send that if you're interested.

This belongs as a response to Jim Humphrey's post, but I don't think I have the reputation for that, so: Patrick Polo's result (for which you can also find a combinatorial proof by Caselli ) is a wonderful, important result: Given a polynomial $f(q)$ of degree $d$ with constant term $1$ and nonnegative integer coefficients, Polo constructs a pair of permutations $x$ and $w$ living in some $S_N$ for which $P_{x,w}(q) = f(q)$. But $N = 1 + d + f(1)$. So even though $1+14q + 60q^2 + 96q^3 + 43q^4 + 4q^5$ appears as a Kazhdan-Lusztig polynomial for a pair of permutations in $S_{10}$, Polo's construction returns permutations in $S_{224}$. There's still a lot to be learned about what can happen for small $S_n$. Theory is going to be a crucial guide in studying these polynomials. But studying the data as one would do in the physical sciences is also, I think, going to play an important role.

share|cite|improve this answer

The "Atlas of Lie Groups" project at has many computations of this sort.

share|cite|improve this answer
Thanks @Paul, I'm still trying to make sense of it. I approached KL polynomials combinatorially (as in Brojner and Brenti's book) so I'm not really familiar with all the representation theory. – Harry Huang Mar 18 '13 at 3:28

Here are some cautionary remarks, plus references. You ask: Is there a more comprehensive list of such polynomials? The answer seems to be no. Lists get long very quickly, and as I commented earlier there is a built-in labeling problem: how to label each group element uniquely while working systematically with pairs of elements related by the Bruhat ordering?

If you focus especially on symmetric groups (or other finite Coxeter groups), the computational problem for each fixed group is a finite one. But already for $E_8$ the Lie group project cited by Paul Garrett has involved a huge effort to compute even the more limited list of Kazhdan-Lusztig-Vogan polynomials relevant to the study of unitary representations of a real Lie group. Here as elsewhere, computations are best done in a motivated framework where supporting theory exists to point toward likely uses for the information encoded in the polynomials.

For symmetric groups, there is the cautinary result of Patrick Polo, showing that every polynomial with non-negative integral coefficients and constant term 1 arises as a Kazhdan-Lusztig poluynomial for some pair of permutations related by the Bruhat ordering. This was announced in a bilingual Comptes Rendus note (1999) and explained in more detail in English in the online AMS journal Representation Theory here.

It's also worthwhile to look at Soergel's alternative development of the polynomials, avoiding mention of the $R$-polynomials (which haven't so far had a useful homological interpretation of their own): see his article in the same journal here. But his work, as in earlier cases involving algebraic geometry, combinatorics, representation theory, hasn't relied on first compiling lists of the polynomials.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.