Path between representatives and normal forms in Coxeter groups

asked 2018-07-16 15:58:37 +0100

EtienneMénard gravatar image

updated 2019-09-01 18:53:48 +0100

FrédéricC gravatar image

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 ($s_i s_j=s_j s_i$) and braid moves ($s_i s_j s_i=s_j s_i s_j$).

For example, in Coxeter Group of type $A_3$ : $\langle s_1,s_2,s_3|s_i^2=1\ ,\ s_1s_2s_1=s_2s_1s_2\ ,\ s_2s_3s_2=s_3s_2s_3\ ,\ s_1s_3=s_3s_1 \rangle $ given the representative $\mathbf{i}=[1,2,3,2,1] $ i can reach the representative $\mathbf{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 $\mathbf{i}$ to the normal form, then the moves from $\mathbf{i}'$ to the normal form and then deducing a path from $\mathbf{i}$ to $\mathbf{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 ?

edit retag flag offensive close merge delete

Comments

The source code for reduced_word() is

result = list(self.reduced_word_reverse_iterator())
return list(reversed(result))

which calls reduced_word_reverse_iterator(); its implementation is

while True:
    i = self.first_descent()
    if i is None:
        return
    self = self.apply_simple_reflection(i, 'right')
    yield i

i.e. recursively remove the first right descent until the identity is reached.

You can use this to implement your algorithm.

rburing gravatar imagerburing ( 2018-07-17 11:26:43 +0100 )edit
add a comment