Computing ShortLex rewite rules with Mathematica.


One may generate the ShortLex rewrite rules for finite Coxeter groups a little more intelligently than described in our note Computing some KL-polynomials for the poset of B×B-orbits in group compactifications . See also
Fokko du Cloux, A transducer approach to Coxeter groups, J. of Symbolic Computation 27 (1999), no. 3, 311-324.
For type E8 fewer than two hundred rules suffice. We did not actually use transducers to find these rules. Neither did we construct the minimal automaton. One method stayed close to the normal form algorithm of du Cloux, see also Casselman in issue 9(1) of the EJC.
As our programs are quite slow, we have collected some more rules in this directory.
Here is one possibility for the main part that is called in the programs below that generate rules for
type An
type Bn
type Dn
type En
type F4
type H4
One may also try other Coxeter groups, but then the rewriting system need not be finite. When it is finite, the programs will find the finite set of rules if one has enough time (and memory) available. One seems to have finiteness for affine Weyl groups, provided one uses a suitable numbering of nodes of the extended Dynkin diagram. We prepared the following cases. We tried them up to n=8. (Affine E8 took about two months and needs about 650 rules.)
type affine An
type affine Bn
type affine Cn
type affine Dn
type affine En
type affine F4
type affine G2.
If one follows the numbering of Bourbaki, and then gives the added node number zero, the resulting rewriting system is infinite for affine G2 and most probably infinite for affine F4. (The rules contain ever longer repeats of the same string.) Therefore we chose a different numbering in those cases. So the ordering of the nodes is important. With one ordering the rewriting system is finite, with another ordering there is apparently no bound on the length of the subwords that need to be inspected to decide if a word is ShortLex or not. For affine G2 we confirmed that this unboundedness really happens by inspecting the finite automaton of ( Casselman ) that recognizes ShortLex normal forms.

One may prove completeness of the rules with a program for checking the Church Rosser conditions. This program tells if the Knuth Bendix algorithm does not change the rewriting system. In fact, it seems to be advantageous to replace the "main part" above with a main part that is based entirely on searching, by length, for failures of the Church Rosser condition. (Some kind of Knuth Bendix by length, relying on the theorem of Tits.) This is better than just Knuth Bendix, but of course it gets quite slow when the number of rules is large. One should at least turn to a compiled language. Then again, if the number of rules gets really large, why would you want them?


Wilberd van der Kallen