Coxeter

Cells and W-graphs

The program provides commands for the computation and printout of the Kazhdan-Lusztig cells and the corresponding W-graphs, for finite groups. The computation is possible for left-, right- and two-sided cells. One should distinguish between the determination of the cells simply as subsets of the groups, which in some cases can be effected without computing any Kazhdan-Lusztig polynomials, and the determination of the corresponding W-graph, which requires the determination of the mu-coefficients.

It is also possible to print out the set of cells as a poset; for finite Weyl groups, it is known that the poset of left cells, say, is isomorphic to the poset of primitive ideals with trivial infinitesimal character, in the enveloping algebra of the corresponding semisimple Lie algebra.

The algorithm for left cells starts out by computing two partitions, the first one, sometimes called "coplactic equivalence", being finer than the left cell partition, and the second one, Vogan's "generalized tau-invariant" partition, being coarser. Both can be computed by elementary means, in terms of descent sets. Clearly if a class in the coarser partition is also a single class in the finer one, then it has to be a left cell; in particular, when the two partitions coincide --- as happens, for instance, in type A --- we conclude immediately. If not, we have to refine the coarse cells which are not single fine cells, by computing the necessary mu-coefficients.

The algorithm for one-sided cells is fairly satisfactory. The algorithm for two-sided cells, on the other hand (which should be an easier problem), is not, due to lack of knowledge on my part. Currently the partition is computed by brute force, finding the full W-graph of the group. Clearly this needs more work.

The three kinds of cells are determined also for the unequal parameter situation; here, one has to determine directly the preorder relation analogous to the one which comes from the W-graph in the equal-parameter case, and find the corresponding equivalence classes. To this end, the program uses the well-known Tarjan algorithm as explained to me by Bill Casselman; this is also what is used in the equal-parameter case, when it is required to find the order relation on the set of all left cells.