Opened 6 years ago
Last modified 6 years ago
#20477 new enhancement
reduced words in complex reflection group
Reported by: | Christian Stump | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-7.2 |
Component: | combinatorics | Keywords: | complex reflection groups, reduced words |
Cc: | Travis Scrimshaw, Frédéric Chapoton, Nicolas M. Thiéry, Vivien Ripoll, Jean Michel | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
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.
Change History (7)
comment:1 Changed 6 years ago by
comment:2 Changed 6 years ago by
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_{32}.
comment:3 follow-up: 4 Changed 6 years ago by
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 decomposition.
It's probably best to take I a maximal parabolic subgroup. Then, W_I should be the first subgroup in the stabilizer chain, and the strong generators for this last inclusion W_I \subset W should be exactly the coset representatives. And 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 grain of salt ...
comment:4 Changed 6 years ago by
Cc: | Jean Michel added |
---|
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 representativesW^I
the factorization of an elementw=w_I w^I
is reduced? (that islen(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.
comment:5 Changed 6 years ago by
comment:6 Changed 6 years ago by
Travis, could you send me some example of what you do and where you get the 30s vs. 30ms
timings?
comment:7 Changed 6 years ago by
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).
The typical ways of getting elements in the group are
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)
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.