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