ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 17 Jul 2018 11:26:43 +0200Path between representatives and normal forms in Coxeter groupshttps://ask.sagemath.org/question/43036/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 ($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 ?
Mon, 16 Jul 2018 15:58:37 +0200https://ask.sagemath.org/question/43036/path-between-representatives-and-normal-forms-in-coxeter-groups/Comment by rburing for <p>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. </p>
<p>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$).</p>
<p>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. </p>
<p>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 <code>w.reduced_word()</code> 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 ?</p>
https://ask.sagemath.org/question/43036/path-between-representatives-and-normal-forms-in-coxeter-groups/?comment=43046#post-id-43046The [source code](https://github.com/sagemath/sage/blob/master/src/sage/categories/coxeter_groups.py) 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.Tue, 17 Jul 2018 11:26:43 +0200https://ask.sagemath.org/question/43036/path-between-representatives-and-normal-forms-in-coxeter-groups/?comment=43046#post-id-43046