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?

  • $\begingroup$ There is the fact that $x\leq y$ in the Bruhat ordering if and only if for every maximal parabolic $P$, one has $Px\leq Py$ (see Bjorner/Brenti for Bruhat order on quotients). If there are $r$ Coxeter generators, then there are $r$ maximal parabolics and the size of the parabolic quotient by a maximal parabolic is much smaller than the size of the group. Can this be exploited? $\endgroup$ Nov 3, 2011 at 22:18
  • 2
    $\begingroup$ I will think a bit harder about this in a while, but I know that du Cloux did some interesting work that you may be interested in: emis.de/journals/EM/expmath/volumes/11/11.3/Cloux371_381.pdf $\endgroup$
    – Tom
    Nov 5, 2011 at 23:48

1 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:"


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).


Your Answer

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

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