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:

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 ?

[1] Computing Kazhdan-Lusztig Polynomials for Arbitrary Coxeter Groups, Experiment. Math. 11:3 (2002), pp. 387-397

Back to the Coxeter home page.