reduced words in complex reflection group

[stumpc5]

The method to compute reduced words in complex, non-real reflection groups is rather slow and done in GAP3.

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.

[stumpc5]

The typical ways of getting elements in the group are

1. iterating through the group
2. "from_reduced_word" and "from_reduced_word_in_reflections"
3. getting special elements such as "a_coxeter_element"

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.

concerning 1)

• 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).
• this way, you get the info you want from the iterator for free without actually computing a reduced word from scratch.

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.

concerning 3) in this case, it is likely that you have to compute words explicitly.

Overall, I think the most common case will be (1) and we can treat that without actually computing reduced words.

[tscrim]

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 dict (which sent a 30s computation to 30ms!), but it would be good for doing testing on random elements for, e.g., G₃₂.

[nthiery]

Just wondering: is that still the case for a complex reflection group W that, if you take a parabolic subgroup W_I and its coset representatives W^I the factorization of an element w=w_I w^I is reduced? (that is len(w)=len(w_I)+len(w^I))?

If yes, would there be a way to compute this decomposition? Then one could use induction to compute the reduced word for w_I and only do the depth first search on W^I?

I would assume that, if one chooses carefully the base for the permutation group (e.g. by starting with the simple roots s_i for i not in I, and then the others), then W_I would be one of the groups in the stabilizer chain. So expressing w in terms of the strong generators would give the desired decomposition.

It's probably best to take a maximal parabolic subgroup W_I for I={1,...,n-1}. Then, W_I should be the first subgroup in the stabilizer chain (fixing the first element of the base alpha_n), 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).

All of this to be taken with a big grain of salt ...

[stumpc5]

Replying to nthiery:

Just wondering: is that still the case for a complex reflection group W that, if you take a parabolic subgroup W_I and its coset representatives W^I the factorization of an element w=w_I w^I is reduced? (that is len(w)=len(w_I)+len(w^I))?

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.

[stumpc5]

​https://groups.google.com/d/topic/sage-support/Bl9hRMRauFo/discussion

[stumpc5]

Travis, could you send me some example of what you do and where you get the 30s vs. 30ms timings?

[tscrim]

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 {element: length} (essentially I cached the results which are known from the iteration).