Loading [MathJax]/jax/output/HTML-CSS/jax.js
Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

Path between representatives and normal forms in Coxeter groups

Hello everyone, I would like to find a way to compute a chain of rewriting move between two reduced representative of the same word in a Coxeter group.

As I work only with A,D,E groups, the only rewriting move I need are commutation (sisj=sjsi) and braid moves (sisjsi=sjsisj).

For example, in Coxeter Group of type A3 : s1,s2,s3|s2i=1 , s1s2s1=s2s1s2 , s2s3s2=s3s2s3 , s1s3=s3s1 given the representative i=[1,2,3,2,1] i can reach the representative i=[3,2,1,2,3] by a braid move on 2,3,2, then commutations between 1 and 3 and eventually a braid move on 1,2,1.

I thought than such an algorithm already existed but I was unable to find it so I decided to write it by myself, in a surely very unnefficient way : given a normal form algorithm, compute the moves from i to the normal form, then the moves from i to the normal form and then deducing a path from i to i (not the shortest I think, but at this moment efficiency questions are not very relevant to myself). In order to do so, I would like to know how coxeter words are implemented in Sage as it seems to me that when you ask w.reduced_word() it gives you the maximum representative for lexicographic ordering, does it have a table of all the representative ? Or does it use a normal form algorithm ?

click to hide/show revision 2
retagged

updated 5 years ago

FrédéricC gravatar image

Path between representatives and normal forms in Coxeter groups

Hello everyone, I would like to find a way to compute a chain of rewriting move between two reduced representative of the same word in a Coxeter group.

As I work only with A,D,E groups, the only rewriting move I need are commutation (sisj=sjsi) and braid moves (sisjsi=sjsisj).

For example, in Coxeter Group of type A3 : s1,s2,s3|s2i=1 , s1s2s1=s2s1s2 , s2s3s2=s3s2s3 , s1s3=s3s1 given the representative i=[1,2,3,2,1] i can reach the representative i=[3,2,1,2,3] by a braid move on 2,3,2, then commutations between 1 and 3 and eventually a braid move on 1,2,1.

I thought than such an algorithm already existed but I was unable to find it so I decided to write it by myself, in a surely very unnefficient way : given a normal form algorithm, compute the moves from i to the normal form, then the moves from i to the normal form and then deducing a path from i to i (not the shortest I think, but at this moment efficiency questions are not very relevant to myself). In order to do so, I would like to know how coxeter words are implemented in Sage as it seems to me that when you ask w.reduced_word() it gives you the maximum representative for lexicographic ordering, does it have a table of all the representative ? Or does it use a normal form algorithm ?