Sage: Ticket #20477: reduced words in complex reflection group
https://trac.sagemath.org/ticket/20477
<p>
The method to compute reduced words in complex, non-real reflection groups is rather slow and done in GAP3.
</p>
<p>
This ticket is about improving reduced words in that case by implementing the algorithm either in Sage or in GAP4, and bypass it as often as possible.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/20477
Trac 1.2Christian StumpThu, 21 Apr 2016 08:42:03 GMT
https://trac.sagemath.org/ticket/20477#comment:1
https://trac.sagemath.org/ticket/20477#comment:1
<p>
The typical ways of getting elements in the group are
</p>
<ol><li>iterating through the group
</li><li>"from_reduced_word" and "from_reduced_word_in_reflections"
</li><li>getting special elements such as "a_coxeter_element"
</li></ol><p>
I believe whenever we know a reduced word Red(w) (in simples S or in all reflections R) *a priori*, we should store that information.
</p>
<p>
concerning 1)
</p>
<ul><li>if the user is interested in Red_S(w), then she should use an iterator that generates the group (as we already do) breadth first from S, and store all Red_S(w) along the way. Similarly for R: if you are interested in Red_R(w), you should use a breadth first iterator from R and store all Red_R(w).
</li><li>this way, you get the info you want from the iterator for free without actually computing a reduced word from scratch.
</li></ul><p>
concerning 2) same as for 1, store info you have, and only compute the other. This might be a problem (in case you give a word is S/R and want a word in R/S), but you usually do not create tons of elements from words.
</p>
<p>
concerning 3) in this case, it is likely that you have to compute words explicitly.
</p>
<p>
Overall, I think the most common case will be (1) and we can treat that without actually computing reduced words.
</p>
TicketTravis ScrimshawThu, 21 Apr 2016 13:21:20 GMT
https://trac.sagemath.org/ticket/20477#comment:2
https://trac.sagemath.org/ticket/20477#comment:2
<p>
What I am doing is iterating through the group and then doing multiplication. The groups are not so big that I couldn't store what I need in a <code>dict</code> (which sent a 30s computation to 30ms!), but it would be good for doing testing on random elements for, e.g., G<sub>32</sub>.
</p>
TicketNicolas M. ThiéryThu, 21 Apr 2016 13:54:51 GMT
https://trac.sagemath.org/ticket/20477#comment:3
https://trac.sagemath.org/ticket/20477#comment:3
<p>
Just wondering: is that still the case for a complex reflection group W that, if you take a parabolic subgroup <code>W_I</code> and its coset representatives <code>W^I</code> the factorization of an element <code>w=w_I w^I</code> is reduced?
(that is <code>len(w)=len(w_I)+len(w^I)</code>)?
</p>
<p>
If yes, would there be a way to compute this decomposition? Then one could use induction to compute the reduced word for <code>w_I</code> and only do the depth first search on <code>W^I</code>?
</p>
<p>
I would assume that, if one chooses carefully the base for the permutation group (e.g. by starting with the simple roots <code>s_i</code> for i not in I, and then the others), then <code>W_I</code> would be one of the groups in the stabilizer chain. So expressing w in terms of the strong generators would give the desired decomposition.
</p>
<p>
It's probably best to take a maximal parabolic subgroup <code>W_I</code> for <code>I={1,...,n-1}</code>. Then, <code>W_I</code> should be the first subgroup in the stabilizer chain (fixing the first element of the base <code>alpha_n</code>), and the strong generators for this last inclusion W_I \subset W should be exactly the coset representatives. Even better, the Shreier tree computed by GAP might actually just be the depth first search tree on then (I don't know if GAP uses a depth first search though).
</p>
<p>
All of this to be taken with a big grain of salt ...
</p>
TicketChristian StumpThu, 21 Apr 2016 18:24:42 GMTcc changed
https://trac.sagemath.org/ticket/20477#comment:4
https://trac.sagemath.org/ticket/20477#comment:4
<ul>
<li><strong>cc</strong>
<em>Jean Michel</em> added
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/20477#comment:3" title="Comment 3">nthiery</a>:
</p>
<blockquote class="citation">
<p>
Just wondering: is that still the case for a complex reflection group W that, if you take a parabolic subgroup <code>W_I</code> and its coset representatives <code>W^I</code> the factorization of an element <code>w=w_I w^I</code> is reduced?
(that is <code>len(w)=len(w_I)+len(w^I)</code>)?
</p>
</blockquote>
<p>
Complex reflection groups behave *very differently* with respect to a simple system (which basically doesn't exist, at least not in a Coxeter combinatorial sense). I believe this does not work, but Jean can certainly say what is possible and what is not.
</p>
TicketChristian StumpWed, 04 May 2016 12:30:50 GMT
https://trac.sagemath.org/ticket/20477#comment:5
https://trac.sagemath.org/ticket/20477#comment:5
<p>
<a class="ext-link" href="https://groups.google.com/d/topic/sage-support/Bl9hRMRauFo/discussion"><span class="icon"></span>https://groups.google.com/d/topic/sage-support/Bl9hRMRauFo/discussion</a>
</p>
TicketChristian StumpWed, 04 May 2016 12:32:16 GMT
https://trac.sagemath.org/ticket/20477#comment:6
https://trac.sagemath.org/ticket/20477#comment:6
<p>
Travis, could you send me some example of what you do and where you get the <code>30s vs. 30ms</code> timings?
</p>
TicketTravis ScrimshawSun, 15 May 2016 15:01:01 GMT
https://trac.sagemath.org/ticket/20477#comment:7
https://trac.sagemath.org/ticket/20477#comment:7
<p>
I am looking at lengths of coset representatives, so I am doing a multiplication and then looking at the length. What instead I did was loop over the group and created a dictionary <code>{element: length}</code> (essentially I cached the results which are known from the iteration).
</p>
Ticket