Software

Other software

Other programs for computations related to the Atlas project.

Coxeter, by Fokko du Cloux

Coxeter is a computer program for the study of combinatorial aspects of Coxeter group theory, particularly those related to the Bruhat ordering and Kazhdan–Lusztig polynomials. It was written by Fokko du Cloux (1954–2006), the original author of the atlas software.

The current version is Coxeter 3, written in C++. It works for essentially any Coxeter group (with some mild restrictions on the rank and the coefficients of the Coxeter matrix), and computes:

• reduced expressions and normal forms;
• the Bruhat ordering;
• ordinary Kazhdan–Lusztig polynomials;
• Kazhdan–Lusztig polynomials with unequal parameters;
• inverse Kazhdan–Lusztig polynomials;
• cells and W-graphs.

Downloads:

• coxeter_3.0_beta3.tgz: Coxeter 3, the source code (unpack with tar xzf, then make);
• coxeter64.tar: an enhanced 64-bit version (updated 10/19/2010);
• positivity.tgz: Fokko du Cloux’s positivity program.

See the archived copy of Fokko du Cloux’s pages for Coxeter 3, with documentation of each of its features and installation notes. The original Coxeter 1 (version 1.01, in C, for finite Coxeter groups) is kept for its historical interest.

klpoly, by Erez Lapid

klpoly computes every Kazhdan–Lusztig polynomial P_x,w of the symmetric group S_n and stores them in a compact table; a second program, klread, looks a polynomial up, or the coefficient μ(x,w). It is written in C. To keep the tables small, only one representative of each class of pairs under four invariances of the Kazhdan–Lusztig polynomials is stored.

There is no limit in the program beyond memory. S₁₀ takes about two minutes, and its 981,173 distinct polynomials fit in 68 MB; S₁₁ takes a little over three hours and needs about 16 GB of memory; S₁₂ has been done on a machine with a terabyte of memory.

Download klpoly.zip (source code, 19 KB)

unzip klpoly.zip
cd klpoly
make
make tables                  # S_4 to S_10, about two minutes
./klread 5 02314 23401       # prints  02314 23401  1,2

Permutations are written in one-line notation on the letters 0,…,n−1, and klread prints the coefficients of P_x,w from the constant term up. The README.txt in the zip file describes the table format, the reductions used, the limits, and how the results were checked.

klpoly is distributed under the MIT licence, © 2017–2026 Erez Lapid. If you use it, please cite it, together with the paper in which the polynomials and the recursion were introduced: D. Kazhdan and G. Lusztig, Representations of Coxeter groups and Hecke algebras, Invent. Math. 53 (1979), 165–184.