Question

Hi everyone.

I'm currently programming some stuff for Hecke algebras. My current implementations have several bottlenecks and I'd like to improve that as much as I can so that I can use stuff like $E_8$ as input one day (without waiting until the heat death of the universe for an answer).

Given a Coxeter group W (let's start with a finite one), one of the things that I would like to improve are some iterations over intervals in the Bruhat order in W. For example a recursion for the Kazhdan-Lusztig-polynomials $P_{y,w}$ and the $\mu$-polynomials $\mu_{y,w}^s$ involves formulas like
$P_{y,w}^\ast = v_t P_{y,w}^\ast + P_{ty,tw}^\ast - \sum_{z\in W: y\leq z < tw \wedge tz < z} P_{y,z}^\ast \mu_{z,tw}^t $
The crucial step of calculating $\mu_{y,w}^s$ involves a similar sum over the interval $(y,w)$. Some other calculations I'd like to perform in the future also have this structure.

One way (this is how I do it at the moment) of realizing this summation over intervals $[a,b]$ is to iterate through all elements of $W$ whose length is between $l(a)$ and $l(b)$ and check everytime if $a\leq z \leq b$ is satisfied. This works fine if both $a$ and $b$ are near the bottom or near the upper end of the Bruhat order, but if they are in the middle, the level sets $\lbrace z | l(z)=const\rbrace$ are much, much bigger than the interval $[y,z]$: Considering the characterization of the Bruhat order in terms of subwords something like $2^{l(w)-l(y)}$ should be an upper bound for the cardinality of this interval, but the level sets in the middle of the Bruhat order have more than $|W|/l(w_0)$ (which is more than $5,8*10^6$ in the $E_8$ case).

A solution could be to use the subword-characterization and iterate through all subwords of $w$. It is no difficult to write a program iterates that way through $[1,w]$. But this approach enumerates all $2^{l(w)}$ subwords and discards several of them to ensure that only reduced words appear and each appears only once. Now an additional check whether $y\leq z$ or not only slows thing down even further. So this also is not a very efficient way if $w$ is somewhere in the middle of the Bruhat order.

Hence my question is:
Is there an efficient way to enumerate all elements of Bruhat intervals?

Answer 1

There is a recursive way to do this that will probably do better for intervals in the middle than the two methods that you said you are unhappy with. Check out Section 5 of N. Reading, "The cd-index of Bruhat Interals:"

http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r74

Basically, here's how it goes: Suppose the interval is $[u,w]$. We choose a reduced word for $w$ and use it to guide a recursive construction. The recursion starts from the singleton interval $[u',w']=[e,e]$ at the identity and, for every letter $s$ in the reduced word, we have a way of constructing either $[u',w's]$ or $[u's,w's]$ from $[u',w']$ by performing a simple global operation (either "doubling" the interval or doing something slightly more complicated) and then killing off certain elements.

There is a lot of computation still, but here is why it is better, for example, than checking all $2^{l(w)}$ subwords of w to find the interval $[1,w]$: In effect, you start with one element, but multiply by $2$ a total of $l(w)$ times, but at each step you get rid of elements you don't want, rather than producing $2^{l(w)}$ elements and then deleting the ones you don't want. You get a similar savings for general intervals $[u,w]$ (which can be much "fatter" than $2^{l(w)-l(u)}$ elements).