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?**