liberiksson is a C++ library for performing basic operations on Coxeter elements. The client program verify.cpp classifies Deodhar elements of finite Coxeter groups by embedded factor containment and checks that all of the mu coefficients of Kazhdan--Lusztig polynomials for these elements are 0 or 1. The client program deodhar.cpp allows ad hoc calculuations of certain Kazhdan--Lusztig polynomials and basis elements for finite Weyl groups, as well as the combinatorial information related to Deodhar algorithm that underlies these computations.

The library source files are:


The Makefile compiles these into a shared library (liberiksson.so on unix, liberiksson.dll on cygwin).
One client file is verify.cpp. The other is deodhar.cpp.
See the README.txt for more information and sample output.

Usage of deodhar.cpp

1. First compile the program using "make deodhar".
2. Running without arguments gives help text. Input is sent to the program using command-line parameters.

brant@fuzzy$ ./deodhar
No arguments given.
Usage:  ./deodhar A3 -w 1021
Given a reduced expression for a Deodhar element,
returns the Kazhdan-Lusztig basis element.
Optional argument:  -x  only prints the polynomial P_{x,w}(q).
Optional argument:  -mu prints the mu-coefficients.
Optional argument:  -masks prints all masks.
3. Passing a Coxeter type prints the Coxeter matrix. The generators are 0, 1, ..., n-1 and the ijth entry of the matrix gives the order of the Coxeter element (ij).
brant@fuzzy$ ./deodhar A3
Coxeter type A3 with Coxeter matrix: 
0 3 2 
3 0 3 
2 3 0 
No w expression given.
4. Passing a reduced expression w prints the Kazhdan--Lusztig basis element {C'}_w.
brant@fuzzy$ ./deodhar A3 -w 1201
Coxeter type A3 with Coxeter matrix: 
0 3 2 
3 0 3 
2 3 0 
w is using reduced expression 
....:  ( 1 2 0 1 ).
In lex order on reduced expressions: 
P(( 1 2 0 1 ),( )) = 1 + q
P(( 1 2 0 1 ),( 0 )) = 1
P(( 1 2 0 1 ),( 0 1 )) = 1
P(( 1 2 0 1 ),( 0 1 0 )) = 1
P(( 1 2 0 1 ),( 1 )) = 1 + q
P(( 1 2 0 1 ),( 1 0 )) = 1
P(( 1 2 0 1 ),( 1 2 )) = 1
P(( 1 2 0 1 ),( 1 2 0 )) = 1
P(( 1 2 0 1 ),( 1 2 0 1 )) = 1
P(( 1 2 0 1 ),( 1 2 1 )) = 1
P(( 1 2 0 1 ),( 2 )) = 1
P(( 1 2 0 1 ),( 2 0 )) = 1
P(( 1 2 0 1 ),( 2 0 1 )) = 1
P(( 1 2 0 1 ),( 2 1 )) = 1
5. This can be filtered to just compute the Kazhdan--Lusztig polynomial P_{w,x}(q) for a particular x < w.
brant@fuzzy$ ./deodhar A3 -w 1201 -x 1
Coxeter type A3 with Coxeter matrix: 
0 3 2 
3 0 3 
2 3 0 
w is using reduced expression 
....:  ( 1 2 0 1 ).
x is using reduced expression ( 1 ).
In lex order on reduced expressions: 
P(( 1 2 0 1 ),( 1 )) = 1 + q
6. If the element w is not Deodhar then the basis won't be printed, although mask statistics can still be viewed.
brant@fuzzy$ ./deodhar A3 -w 121 -masks
Coxeter type A3 with Coxeter matrix: 
0 3 2 
3 0 3 
2 3 0 
w is using reduced expression 
....:  ( 1 2 1 ).
mask:  ( 0 0 0 ):  1
mask:  ( 1 0 0d):  q (not Deodhar) 
mask:  ( 0 1 0 ):  1
mask:  ( 1 1 0 ):  1 (mu mask) 
mask:  ( 0 0 1 ):  1
mask:  ( 1 0 1d):  q (mu mask) 
mask:  ( 0 1 1 ):  1 (mu mask) 
mask:  ( 1 1 1 ):  1