11
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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$. $\endgroup$ Mar 17, 2013 at 17:56
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 17, 2013 at 17:59
  • $\begingroup$ @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. $\endgroup$ Mar 18, 2013 at 2:06
  • 3
    $\begingroup$ How about PyCox? (arxiv.org/pdf/1201.5566v2.pdf) For type A, see also arxiv.org/pdf/1010.3961v1.pdf (and the author's C code available at cems.uvm.edu/~gswarrin/research/klpol/klpol.html). $\endgroup$ Mar 18, 2013 at 2:51
  • $\begingroup$ Thanks @Shunsuke, that's something novel to me. But what I'm looking for is like a list of prime numbers... $\endgroup$ Mar 18, 2013 at 12:18

3 Answers 3

11
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

The "Atlas of Lie Groups" project at http://www.liegroups.org/ has many computations of this sort.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Mar 18, 2013 at 3:28
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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