Coxeter

Bruhat ordering

The treatment of the Bruhat ordering on the group is the determining factor for the performance of all Kazhdan-Lusztig computations. The one-time comparison of two given elements is no problem (see here). But to carry out the massive amounts of Bruhat order comparisons required by Kazhdan-Lusztig computations, other means are required.

In my implementation, a Coxeter group always possesses an enumerated part; this is a finite subset P of the group, which is an order ideal (also called a decreasing subset) for the Bruhat ordering (this means that whenever y is in P, and x <= y, then x is in P), and which has been numbered increasingly w.r.t. the Bruhat ordering (in other words, if x <= y then the number of x is smaller than the number of y.) In addition, we maintain the following tables for the enumerated part P:

• the Hasse diagram of the Bruhat ordering (this means that for every y in P, we keep the list of all z in P which are immediately smaller than y);
• the left and right action of the generators of the group on P (insofar as the result lies within P);
• for each y in P, the left and right descent sets of y (the main reason for limiting the group rank to one half of the number of bits in an unsigned long, is that this allows us to store both descent sets together on a single machine word, as a small bitmap);
• the lengths of the elements in P.

When the program starts, the enumerated part is reduced to the identity element e. An algorithm is given in [1] by which from a given enumerated part P and an element y not in P, one may construct the smallest order ideal containing P and y (which is just the union of P and the interval [e,y]), as an enumerated set, and to extend to this new enumerated set the tables referred to above. This algorithm also affords a reasonably effective way of extracting the bitmap representing the interval [e,y], for any y in the enumerated part P. This interval-extraction is one of the main parts of the Kazhdan-Lusztig computations.

In fact, the Bruhat order functions are mostly used internally in the program, and are not too easily accessible for the outside user. The combinatorial study of the Bruhat ordering is a fascinating subject, which would probably deserve a (much simpler) program on its own. Coxeter unfortunately does not currently contain the functions, such as the extraction of the interval between to given elements x and y, which would have been desirable. Maybe in the future ?