Opened 5 years ago
Closed 5 years ago
#20402 closed enhancement (fixed)
Make subword complexes compatible with real reflection groups
Reported by: | stumpc5 | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-7.2 |
Component: | combinatorics | Keywords: | reflection group, coxeter group, subword complex, days80 |
Cc: | tscrim, chapoton, nthiery, vripoll | Merged in: | |
Authors: | Christian Stump | Reviewers: | Frédéric Chapoton, Travis Scrimshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | 71eba72 (Commits, GitHub, GitLab) | Commit: | 71eba72e896ba17314bcab6965f33005d02a26e4 |
Dependencies: | #20521 | Stopgaps: |
Description
The subword complex code was written and optimized for real reflection groups, but then made its way into Sage for Coxeter groups. This ticket is to make it handle both.
Change History (67)
comment:1 Changed 5 years ago by
- Dependencies set to #11187
comment:2 Changed 5 years ago by
- Branch set to u/stumpc5/20402
comment:3 Changed 5 years ago by
- Commit set to 5ae3b7f793ad96f9f39999b158398434009435da
comment:4 Changed 5 years ago by
- Commit changed from 5ae3b7f793ad96f9f39999b158398434009435da to df55cdd653d443594a0726b4e1e6e97c539fb0e9
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
72082b1 | fixed a bug in noncrossing partition lattice and reflection/absolute order
|
844f450 | Merge branch 'u/stumpc5/11187' of trac.sagemath.org:sage into u/tscrim/reflection_groups-11187
|
d425669 | Fixing failures and some other things.
|
87cd989 | fixed one doctest in category complex reflection group
|
05a8ab4 | 11187: fixed trivial doctest failures
|
32bf1ae | 11187: cleanup of the organization of the various axioms (WellGenerated, ...) for complex/generalized reflection groups + documentation improvements
|
73276ca | Merge branch 'u/tscrim/11187' of trac.sagemath.org:sage into t/11187/11187
|
e074050 | merged
|
b572c74 | fixed a missing doctest
|
df55cdd | merged the newest version of 11187
|
comment:5 Changed 5 years ago by
- Commit changed from df55cdd653d443594a0726b4e1e6e97c539fb0e9 to 19271510dd0f4b3ea6480fb9e6d15d70383440fc
Branch pushed to git repo; I updated commit sha1. New commits:
1927151 | fixed a bug in simple_root_index
|
comment:6 Changed 5 years ago by
This ticket seems to be ready once #11187 has positive review.
comment:7 Changed 5 years ago by
This is failing:
sage: a3r=ReflectionGroup(['A',3], base_ring=QQ) sage: sr=SubwordComplex([1,3,2,1,3,2,1,3,2],a3r.w0) sage: fr=sr.greedy_facet() sage: fr.extended_weight_configuration()
comment:8 Changed 5 years ago by
- Commit changed from 19271510dd0f4b3ea6480fb9e6d15d70383440fc to d6bc459825560776ea95c8d3e34d32b2fb78d059
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
0becba3 | Merge branch 'public/11187' of git://trac.sagemath.org/sage into u/stumpc5/20396
|
8927ab9 | matrix action is on the right!
|
eb2ea75 | cleaned the reduced word code
|
6fbba18 | undo the change to repr methods
|
8497f5d | first try to skip elements in the iteration, too slow
|
def7015 | reorganized the invariant form (still missing an improvement) + fixed two doctests
|
ab73bc3 | Merge branch 'u/stumpc5/11187' into u/stumpc5/20402
|
b5a2c8d | moved all examles back to ReflectionGroup
|
e36ddad | added fundamental_weight to coxetergroup implementation
|
d6bc459 | made all doctests work, but I used a dirty hack to solve the weight configuration
|
comment:9 Changed 5 years ago by
- Commit changed from d6bc459825560776ea95c8d3e34d32b2fb78d059 to a1b3d3ba5055e4217d8cecd5b09bd51b078802f2
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
dc01066 | started to add 'optional - gap3'
|
fd0c9cc | added optional gap3
|
1537a79 | added optional gap3
|
a60cf31 | added some missing optional gap3
|
feebf97 | finalized the invariant form
|
4955d68 | added the missing optional gap3 in the cython file
|
c5c43bc | the next round of optional gap3 insertions
|
244e6ff | Merge branch 'public/11187' of trac.sagemath.org:sage into public/reflection_groups-11187
|
f541349 | Some last little beautification.
|
a1b3d3b | Merge branch 'u/stumpc5/11187' into u/stumpc5/20402
|
comment:10 Changed 5 years ago by
- Commit changed from a1b3d3ba5055e4217d8cecd5b09bd51b078802f2 to e63d2ece579d1afd1df9c4afcf951407e6fbe36d
Branch pushed to git repo; I updated commit sha1. New commits:
0db28d6 | fixed doctests that have not been run last week!
|
7afc02c | Fixing doctests in combinat/root_system/coxeter_group.py.
|
0269425 | Blanket fix bare except block.
|
9b0ef92 | Making it an AttributeError.
|
87cdde0 | Merge branch 'public/11187' into u/stumpc5/20402
|
8d76520 | using a cached version self._number_of_reflections to avoid computing it again and again, expecially important in has_descent
|
0b6d895 | Merge branch 'develop' into public/11187
|
e63d2ec | Merge branch 'public/11187' into u/stumpc5/20402
|
comment:11 Changed 5 years ago by
- Summary changed from Make real reflection group compatible with subword complex to Make subword complexes compatible with real reflection groups
comment:12 Changed 5 years ago by
- Commit changed from e63d2ece579d1afd1df9c4afcf951407e6fbe36d to 0b81cd6ccf77c652672ca75aa693123ca77bd93c
Branch pushed to git repo; I updated commit sha1. New commits:
4bacaea | trivial typo
|
fc8a0aa | replaced the wrongly assumed right action by a left action
|
ef6dbac | fixed the action on root indices with left and right version
|
308f26b | added optional gap3 everywhere
|
0b81cd6 | added a few missing optional gap3
|
comment:13 Changed 5 years ago by
- Status changed from new to needs_review
comment:14 Changed 5 years ago by
I think this is ready to go once the patchbots are happy!
comment:15 Changed 5 years ago by
- Keywords reflection days80 added
comment:16 Changed 5 years ago by
- Commit changed from 0b81cd6ccf77c652672ca75aa693123ca77bd93c to 0ee1f3bf9c772352b9a7994afc7f4359e618b309
Branch pushed to git repo; I updated commit sha1. New commits:
0ee1f3b | added a few more missing optional gap3
|
comment:17 follow-up: ↓ 18 Changed 5 years ago by
- Status changed from needs_review to needs_work
-1 to changing all of the examples to only using GAP3/reflection groups. Until GAP3 becomes an optional spkg, it means they become completely untested. Moreover, it is good to make sure the functionality works between different implementations.
I think there are a few things in here which need to be abstracted up to the category, root system code, and/or Coxeter type code. For example, is_crystallographic
should be called on the Coxeter type, of which ReflectionGroup
does not have and should (or perhaps the Coxeter matrix).
I also do not see the reason why this change is needed:
- Lambda = {li: coeff[li] * Lambda[li] for li in Lambda} + Lambda = {li: coeff[li] * Lambda[li] for li in Lambda.keys()}
as the iteration for a dictionary is over its keys (and the former is faster and more memory efficient). With this change:
- V_weights.append(pi * fund_weight) + # TODO: little hack to distinguish the implementations + # for ReflectionGroups and CoxeterGroup + from sage.groups.perm_gps.permgroup_element import PermutationGroupElemen + if isinstance(pi,PermutationGroupElement): + V_weights.append( sum(fund_weight[j]*Phi[ (~pi)(j+1)-1 ] for j in ran + else: + V_weights.append(pi * fund_weight)
I think it would be better to have the fundamental weights handle the action of the reflection group element.
comment:18 in reply to: ↑ 17 ; follow-ups: ↓ 20 ↓ 22 Changed 5 years ago by
Replying to tscrim:
-1 to changing all of the examples to only using GAP3/reflection groups. Moreover, it is good to make sure the functionality works between different implementations.
The header contains tests that the core functionality works for Coxeter groups, maybe one could add a more elaborate example there, providing examples for more functionality.
But I clearly wrote the code the way I did in close relationshiop to the implementation of reflection groups, and I must confess that I prefer the speed (and indeed I need that speed for my research) over the code being usable by other implementations. I think, it is okay to have the code sort of working for CoxeterGroup
, but for example the necessity to introduce a method action_on_root_indices
for those tells that there is actually more work to be done to make the implementation work with both without giving up the speed on one, and not introducing unnecessary function overhead on the other.
Until GAP3 becomes an optional spkg, it means they become completely untested.
This should be done soon in my eyes, but I understand that so far I am the only one being desperate to have it.
I think there are a few things in here which need to be abstracted up to the category, root system code, and/or Coxeter type code. For example,
is_crystallographic
should be called on the Coxeter type, of whichReflectionGroup
does not have and should (or perhaps the Coxeter matrix).
A reflection group acting on a real vector space can have the property of being crystallographic or not (whether or not it stabilizes a lattice). I thus think the group itself should have this property.
What do you think of (me) adding this method also to Coxeter groups (in this ticket or another)?
I also do not see the reason why this change is needed:
- Lambda = {li: coeff[li] * Lambda[li] for li in Lambda} + Lambda = {li: coeff[li] * Lambda[li] for li in Lambda.keys()}as the iteration for a dictionary is over its keys (and the former is faster and more memory efficient).
As we have per default that simple reflections are families rather than dicts (so that iterating over them actually iterates over them), the reflection group implementation also have simple roots and fundamental weights as finite families, so iterating goes over the values. That's what the keys
is there for.
With this change:
- V_weights.append(pi * fund_weight) + # TODO: little hack to distinguish the implementations + # for ReflectionGroups and CoxeterGroupI think it would be better to have the fundamental weights handle the action of the reflection group element.
If you mean, one might have a method act on weight
, one could think about it, but the point here is that the action on fundamental weights can be quickly understood using the action on roots, while the general action on weights is not as simple.
I can implement a method act_on_fundamental_weight
to factor out the hack, but is that what we actually want?
comment:19 Changed 5 years ago by
- Commit changed from 0ee1f3bf9c772352b9a7994afc7f4359e618b309 to 2c95a41c537c6625ed6abdf03fd5bbedc9da21cb
Branch pushed to git repo; I updated commit sha1. New commits:
2c95a41 | added a few more test cases for CoxeterGroup to the header
|
comment:20 in reply to: ↑ 18 Changed 5 years ago by
A reflection group acting on a real vector space can have the property of being crystallographic or not (whether or not it stabilizes a lattice). I thus think the group itself should have this property.
What do you think of (me) adding this method also to Coxeter groups (in this ticket or another)?
I gonna for now also use
sage: W = ReflectionGroup(['A',3]) sage: W.coxeter_matrix().is_crystallographic() True sage: W = CoxeterGroup(['A',3]) sage: W.coxeter_matrix().is_crystallographic() True
(without giving up the idea that the property is attached to the group itself).
comment:21 Changed 5 years ago by
- Commit changed from 2c95a41c537c6625ed6abdf03fd5bbedc9da21cb to 803d8b9226e376cbd777f4bb1d1ef67342d289fd
Branch pushed to git repo; I updated commit sha1. New commits:
803d8b9 | replace a hack by using G.coxeter_matrix().is_crystallogrphic()
|
comment:22 in reply to: ↑ 18 Changed 5 years ago by
If you mean, one might have a method
act on weight
, one could think about it, but the point here is that the action on fundamental weights can be quickly understood using the action on roots, while the general action on weights is not as simple.
Let me take that back for now, I'll get back to it...
comment:23 Changed 5 years ago by
- Commit changed from 803d8b9226e376cbd777f4bb1d1ef67342d289fd to 52c39d9ef149ee6826cb3f8f06b7aa7582d49f14
Branch pushed to git repo; I updated commit sha1. New commits:
bc23f81 | fixed the action on root indices, roots, and general vectors
|
0ecefc2 | renamed action_on_root_indices to act_on_root_indices for name unifications
|
63639a6 | removed a fixed todo
|
f12a61e | added method 'act' to CoxeterGroup and used it in the action on weights, also marked a few more doctests as optional gap3
|
52c39d9 | fixed one broken doctest in coxeter_group.py
|
comment:24 Changed 5 years ago by
- Status changed from needs_work to needs_review
Hi Travis, I believe I fixed everything you mentioned except for the fact that I almost completely test using ReflectionGroup
's. In particular, I fixed a few hacks and todo
's.
The changes to reflection_group_real.py
and to coxeter_group.py
are not strictly there to get subword complexes to work (though the uniformization is done for that reason). Should I extect those changes into a different ticket, or is everyone okay with having it here?
Beside that, I set it back to needs review
.
comment:25 Changed 5 years ago by
- Status changed from needs_review to needs_work
It's looking a lot better Christian. Thank you.
However, let me be a bit more stern, I will not set this ticket to a positive review when you essentially remove doctest coverage because gap3
is not an optional package yet (although this argument weakens once it is). Moreover, you can test all of the functionality with standard Sage, which such tests should be localized to each method, not (only) in a class-level test which does the "core" functionality.
For the speed issues, how much of this is making a difference? If it does, you can separate out the important functionality into a separate method, and then subclass the general class which special cases the methods when you use ReflectionGroup
.
You are right about the issue with Lambda
.
By renaming action_on_root_indices
, you need to deprecate it.
I am okay with you adding an is_crystallographic
to the group here, but it might be a little strange if the crystallographic-ness of a Coxeter group is different than its Coxeter type/matrix.
Also, instead of act
, IIRC there is a method, which I believe is _act_on_
(not to be confused with _acted_upon_
), that automatically gets checked by the coercion framework. So it gives you w * la
essentially for free. Although
comment:26 Changed 5 years ago by
- Commit changed from 52c39d9ef149ee6826cb3f8f06b7aa7582d49f14 to 283ccf598079150e16406adc6a5a55b519f8ec26
comment:27 follow-ups: ↓ 30 ↓ 37 Changed 5 years ago by
Replying to tscrim:
For the speed issues, how much of this is making a difference?
sage: W = ReflectionGroup(['A',5]) sage: c = W.index_set(); Q = c + tuple(W.w0.coxeter_sorting_word(c)) sage: %time S = SubwordComplex(Q,W.w0) CPU times: user 42.7 ms, sys: 612 µs, total: 43.3 ms Wall time: 39.5 ms sage: len(S) 132 sage: W = CoxeterGroup(['A',5]) sage: c = W.index_set(); Q = c + tuple(W.w0.coxeter_sorting_word(c)) sage: %time S = SubwordComplex(Q,W.w0) CPU times: user 15.1 s, sys: 84.3 ms, total: 15.1 s Wall time: 15.1 s sage: len(S) 132
The complete implementation depends on has_descents
and multiplication of elements to be fast (and this will get another boost for ReflectionGroup
in #20484), when you %prun
the code for CoxeterGroup
you don't see a single bottleneck but that it is too slow in many parts (I am not complaining about this speed issue in general, this implementation is uniform for all Coxeter systems, finite or infinite, so that's great and the speed is what one gets there!)
If it does, you can separate out the important functionality into a separate method, and then subclass the general class which special cases the methods when you use
ReflectionGroup
.
This implementation of subword complexes is not a general implementation that could be moved up the hierarchy, and then a few methods could be replaced for concrete implementations. All the internal core methods are written so that internally it only plays with numbers and permutations of numbers, you only see roots popping out when using the API.
Is is indeed possible to write a toy (in terms of speed) implementation for the category of CoxeterGroups
, but I am not the one doing that at the moment -- what I provide is a research level implementation for ReflectionGroup
.
However, let me be a bit more stern, I will not set this ticket to a positive review when you essentially remove doctest coverage because
gap3
is not an optional package yet (although this argument weakens once it is). Moreover, you can test all of the functionality with standard Sage, which such tests should be localized to each method, not (only) in a class-level test which does the "core" functionality.
Hm -- you see my complaints about that above. On the other hand, I also see your point of getting rotten untested code after a while, and I don't really care if we pollute the documentation with more tests.
By renaming
action_on_root_indices
, you need to deprecate it.
It was only there for a few months, see #11010, and this method is almost surely not used by anyone so far. You still think it should be deprecated ?
I am okay with you adding an
is_crystallographic
to the group here, but it might be a little strange if the crystallographic-ness of a Coxeter group is different than its Coxeter type/matrix.
How could crystallographic-ness being different for the group and for its Coxeter type ? See Section 2.8 in Humphreys Coxeter group book for a "proof" that the two are the same. Or am I overseeing something?
comment:28 follow-up: ↓ 29 Changed 5 years ago by
Also, instead of
act
, IIRC there is a method, which I believe is_act_on_
(not to be confused with_acted_upon_
), that automatically gets checked by the coercion framework. So it gives youw * la
essentially for free.
Done, I must admit that I like that way of having an element w in W act on vectors, while I am nervous about this implicitness in the construction that will likely result in bugs.
Although
missing sentence?
comment:29 in reply to: ↑ 28 ; follow-up: ↓ 31 Changed 5 years ago by
Replying to stumpc5:
Also, instead of
act
, IIRC there is a method, which I believe is_act_on_
(not to be confused with_acted_upon_
), that automatically gets checked by the coercion framework. So it gives youw * la
essentially for free.Done, I must admit that I like that way of having an element w in W act on vectors, while I am nervous about this implicitness in the construction that will likely result in bugs.
Same here; it's nice to have a short hand for actions (and to benefit from coercion!), but I am also uncomfortable giving yet another meaning to the operator '*'.
In any cases, we should keep consistency with Weyl groups. It's currently w.action(l)
there (not w.act(l)
btw); if we switch to _act_on_
, then we should do it consistently everywhere.
Cheers,
comment:30 in reply to: ↑ 27 ; follow-up: ↓ 38 Changed 5 years ago by
Replying to stumpc5:
How could crystallographic-ness being different for the group and for its Coxeter type ? See Section 2.8 in Humphreys Coxeter group book for a "proof" that the two are the same.
I guess that's Travis's point: mathematically, they two should be the same. If there are two methods implementing this fact, then we need to make sure that they remain consistent.
comment:31 in reply to: ↑ 29 ; follow-up: ↓ 33 Changed 5 years ago by
Replying to nthiery:
In any cases, we should keep consistency with Weyl groups. It's currently
w.action(l)
there (notw.act(l)
btw); if we switch to_act_on_
, then we should do it consistently everywhere.
Term-wise, I think that w
acts on l
, while there is an action of W
on l
. But I am equally okay to use w.action(l)
for consistency.
I don't get your point of switching: what is wrong with having the method action
and then using this method in the body of _act_on_
?
comment:32 Changed 5 years ago by
- Commit changed from 283ccf598079150e16406adc6a5a55b519f8ec26 to 295d784db0ae24bed97ed7b4d3777df9dbd652c2
Branch pushed to git repo; I updated commit sha1. New commits:
295d784 | replace act* by action*
|
comment:33 in reply to: ↑ 31 ; follow-ups: ↓ 34 ↓ 39 Changed 5 years ago by
Replying to stumpc5:
I don't get your point of switching: what is wrong with having the method
action
and then using this method in the body of_act_on_
?
Just that I am not sure that we want to overload/polute '*' with this; and if we do, it should be done consistently for Weyl groups as well.
Cheers
comment:34 in reply to: ↑ 33 Changed 5 years ago by
Replying to nthiery:
Replying to stumpc5:
I don't get your point of switching: what is wrong with having the method
action
and then using this method in the body of_act_on_
?Just that I am not sure that we want to overload/polute '*' with this; and if we do, it should be done consistently for Weyl groups as well.
One reason in favour is that elements in CoxeterGroup
are matrices, so they use '*' anyways. Otherwise, I would have to re-enable the method action
there which is simply using '*'.
One reason against is that for complex reflection groups, the action on the space and on its dual are different. And since both are represented by vectors (in the dual bases {ei} and {xi}), the '*' does not see this for now. But one could have an optional argument in_dual
for action
.
comment:35 follow-ups: ↓ 36 ↓ 40 Changed 5 years ago by
Oh, I had not noticed that CoxeterMatrixGroup
were acting on plain vectors with '*'. As you mention this is very ambiguous. For a Weyl group this is even worst: is the vector interpreted as in the span of the (co)roots? of the (co)weights? in the ambient space?
For now, I'd rather keep the notations as explicit as possible (in particular, it's easier to document a method .action
than an overloaded operator). And leave us room in the future to overload '*', either by default, or upon explicit request from the user.
comment:36 in reply to: ↑ 35 Changed 5 years ago by
Replying to nthiery:
Oh, I had not noticed that
CoxeterMatrixGroup
were acting on plain vectors with '*'.
Yes, the elements are matrices which act on vectors :-)
As you mention this is very ambiguous. For a Weyl group this is even worst: is the vector interpreted as in the span of the (co)roots? of the (co)weights? in the ambient space?
I agree.
For now, I'd rather keep the notations as explicit as possible (in particular, it's easier to document a method
.action
than an overloaded operator). And leave us room in the future to overload '*', either by default, or upon explicit request from the user.
One could define _act_on_
in different ways for elements in the root/coroot/weight/coweight space, and not at all for plain vectors. But on the reflection group side there is no class for elements in V
and in V^*
yet. I am okay with both: considering the action on vectors for now on elements in V
, or removing the coercion for now.
comment:37 in reply to: ↑ 27 Changed 5 years ago by
Replying to stumpc5:
Replying to tscrim:
For the speed issues, how much of this is making a difference?
The complete implementation depends on
has_descents
and multiplication of elements to be fast (and this will get another boost forReflectionGroup
in #20484), when you%prun
the code forCoxeterGroup
you don't see a single bottleneck but that it is too slow in many parts (I am not complaining about this speed issue in general, this implementation is uniform for all Coxeter systems, finite or infinite, so that's great and the speed is what one gets there!)
That is not answering the question I asked. I asked about having one additional level of indirection to have a specialized function for when the input is an instance of RealReflectionGroup
.
If it does, you can separate out the important functionality into a separate method, and then subclass the general class which special cases the methods when you use
ReflectionGroup
.This implementation of subword complexes is not a general implementation that could be moved up the hierarchy, and then a few methods could be replaced for concrete implementations. All the internal core methods are written so that internally it only plays with numbers and permutations of numbers, you only see roots popping out when using the API.
I'm sure there are only some key parts of it which are written that strongly depend on the input format. These could be abstracted to work in general with a special subclass which has the specialized method or into the implementations of the Coxeter group. This is a standard design pattern for code that I've seen many times over (we even have the former in Sage's matrix code).
Is is indeed possible to write a toy (in terms of speed) implementation for the category of
CoxeterGroups
, but I am not the one doing that at the moment -- what I provide is a research level implementation forReflectionGroup
.
In many ways, we are beating a dead horse as you have basically done what I am asking for already (with the specializing being done in the different implementations of a Coxeter group).
However, let me be a bit more stern, I will not set this ticket to a positive review when you essentially remove doctest coverage because
gap3
is not an optional package yet (although this argument weakens once it is). Moreover, you can test all of the functionality with standard Sage, which such tests should be localized to each method, not (only) in a class-level test which does the "core" functionality.Hm -- you see my complaints about that above. On the other hand, I also see your point of getting rotten untested code after a while, and I don't really care if we pollute the documentation with more tests.
Then let's leave those tests in. That is the only thing I am asking for here.
By renaming
action_on_root_indices
, you need to deprecate it.It was only there for a few months, see #11010, and this method is almost surely not used by anyone so far. You still think it should be deprecated ?
I am pretty sure it appears in a stable release (i.e., 7.1), so yes.
comment:38 in reply to: ↑ 30 Changed 5 years ago by
Replying to nthiery:
Replying to stumpc5:
How could crystallographic-ness being different for the group and for its Coxeter type ? See Section 2.8 in Humphreys Coxeter group book for a "proof" that the two are the same.
I guess that's Travis's point: mathematically, they two should be the same. If there are two methods implementing this fact, then we need to make sure that they remain consistent.
Well, my interpretation of Christian's first comment was this was a property of the realization of the group, not of the group itself. So the group's is_crystallographic
should just call that of its Coxeter type/matrix.
comment:39 in reply to: ↑ 33 ; follow-up: ↓ 41 Changed 5 years ago by
Replying to nthiery:
Replying to stumpc5:
I don't get your point of switching: what is wrong with having the method
action
and then using this method in the body of_act_on_
?Just that I am not sure that we want to overload/polute '*' with this; and if we do, it should be done consistently for Weyl groups as well.
I have been told by a few people that they would want this feature (in the finite Coxeter group setting) as it is natural and corresponds to what we would write mathematically.
comment:40 in reply to: ↑ 35 Changed 5 years ago by
Replying to nthiery:
Oh, I had not noticed that
CoxeterMatrixGroup
were acting on plain vectors with '*'. As you mention this is very ambiguous. For a Weyl group this is even worst: is the vector interpreted as in the span of the (co)roots? of the (co)weights? in the ambient space?
For CoxeterMatrixGroup
, it is given as a (faithful) representation, so the basis of a vector space is (implicitly) given, which is the roots. For the Weyl group, it is also given as a representation, so again, we have a basis which we define the action on. So I see no ambiguity, and in fact, I think the Weyl groups are very explicit about this.
For now, I'd rather keep the notations as explicit as possible (in particular, it's easier to document a method
.action
than an overloaded operator). And leave us room in the future to overload '*', either by default, or upon explicit request from the user.
I agree, that it is easier to document action()
than an overloaded operator, but I think it is only marginally easier. The first thing I would (and do) look at is the class-level documentation for what I can do with a particular object. So if we have examples in there that describe the action of *
, I think that makes it easily accessible what we are doing, in addition to the naturality of the action. Or am I forgetting something (again, in the [finite] Coxeter group setting)?
comment:41 in reply to: ↑ 39 Changed 5 years ago by
Replying to tscrim:
I have been told by a few people that they would want this feature (in the finite Coxeter group setting) as it is natural and corresponds to what we would write mathematically.
Well, mathematicaly, I tend to write v.s_i
, not vs_i
, precisely to raise the potential ambiguity (this is an action, not a multiplication)
comment:42 follow-up: ↓ 43 Changed 5 years ago by
Replying to tscrim:
In many ways, we are beating a dead horse as you have basically done what I am asking for already (with the specializing being done in the different implementations of a Coxeter group).
Well, let's keep it as it is for now then.
Then let's leave those tests in. That is the only thing I am asking for here.
Fine.
I am pretty sure it appears in a stable release (i.e., 7.1), so yes.
After Nicolas' comment that WeylGroup
uses .action
, I moved it back to action*
...
my interpretation of Christian's first comment was this was a property of the realization of the group, not of the group itself. So the group's
is_crystallographic
should just call that of its Coxeter type/matrix.
Yes, for real groups I only wanted the is_crystallographic
of the group to call the one of the Coxeter type/matrix. But complex reflection groups can still be crystallographic (though they only are if they are real and crystallographic), so they deserve the method is_crystallographic
without having a Coxeter type/Coxeter matrix attached to them.
So I see no ambiguity, and in fact, I think the Weyl groups are very explicit about this.
But what if w
is an element of the group and v
is a *Sage vector*. Does it represent an element in the vector space spanned the simple roots, or by the simple coroots, or by the fundamental weights, or by the fundamental coweights? Or does that not matter since the actions are all the same?
comment:43 in reply to: ↑ 42 Changed 5 years ago by
Replying to stumpc5:
Replying to tscrim:
my interpretation of Christian's first comment was this was a property of the realization of the group, not of the group itself. So the group's
is_crystallographic
should just call that of its Coxeter type/matrix.Yes, for real groups I only wanted the
is_crystallographic
of the group to call the one of the Coxeter type/matrix. But complex reflection groups can still be crystallographic (though they only are if they are real and crystallographic), so they deserve the methodis_crystallographic
without having a Coxeter type/Coxeter matrix attached to them.
Ah, I see. This good.
So I see no ambiguity, and in fact, I think the Weyl groups are very explicit about this.
But what if
w
is an element of the group andv
is a *Sage vector*. Does it represent an element in the vector space spanned the simple roots, or by the simple coroots, or by the fundamental weights, or by the fundamental coweights? Or does that not matter since the actions are all the same?
Sage's vectors exists expressed in some canonical basis, and by doing matrix multiplication, there is an implicit assumption that these bases are the same. In a way, what you are advocating for is that we need to explicitly specify the matrix for any matrix m
and v
and check those are the same anytime we write m * v
. The various subclasses of CombinatorialFreeModule
does this by saying the (parent) class corresponds to a choice of basis, but this is not, and really can never be, the case for Sage's vectors, where there is an assumption of a canonical basis. In fact, because these matrices are representations of a vector space given in terms of a basis, that basis is canonical as far as Sage's vectors are concerned. (I hope that makes some sense...)
comment:44 follow-up: ↓ 45 Changed 5 years ago by
Sage's vectors exists expressed in some canonical basis, and by doing matrix multiplication, there is an implicit assumption that these bases are the same.
I'd say that multiplying a matrix M
with a vector v
(as a tuple in distinction to vector space elements) is well-defined and completely independent on bases. So that's totally fine to do as M*v
.
Only if the matrix is representing a linear map and the tuple represents a vector space element there is an assumption on both being represented in the same basis. When you now represent a Coxeter group element as a matrix you make a choice of basis (which might be the root basis, its dual, some linearly independent vectors of an "ambient space", or any other) This is now what you stick this matrix to, but when you do w*v
, one does not specify the matrix that represents w
in some basis, so this operation is ambiguous, as it didn't specify on which space w
acts here (i.e., it is not clear in which basis you represent w
as a matrix for that action.
For ReflectionGroup
I just thought that the best is to have the method .action
to take two parameters side
being "left"
or "right"
and on_space
being "primal"
or "dual"
.
Beside that, I am okay with providing the coercion to act on the primal, but am also okay with removing it again (I am slightly in favour of keeping it though).
comment:45 in reply to: ↑ 44 ; follow-up: ↓ 46 Changed 5 years ago by
Replying to stumpc5:
Sage's vectors exists expressed in some canonical basis, and by doing matrix multiplication, there is an implicit assumption that these bases are the same.
I'd say that multiplying a matrix
M
with a vectorv
(as a tuple in distinction to vector space elements) is well-defined and completely independent on bases. So that's totally fine to do asM*v
.
No, that is not true except in the most abstract sense of a linear morphism and an element of a vector space. A matrix comes with an implicit choice of a basis, and when we write vectors as tuples, there is an implicit choice of a basis as well. For example, if M
is a diagonalizable matrix acting on a vector space V
, we can find some basis such that M
can be expressed as acting on scalars on that basis. While the diagonal matrix and M
are different matrices, they define the same linear automorphism on V
, and hence, have the same action on a vector. Yet, to do the computation, we need to express the vector in terms of our basis.
Only if the matrix is representing a linear map and the tuple represents a vector space element there is an assumption on both being represented in the same basis. When you now represent a Coxeter group element as a matrix you make a choice of basis (which might be the root basis, its dual, some linearly independent vectors of an "ambient space", or any other) This is now what you stick this matrix to, but when you do
w*v
, one does not specify the matrix that representsw
in some basis, so this operation is ambiguous, as it didn't specify on which spacew
acts here (i.e., it is not clear in which basis you representw
as a matrix for that action.
That is not how a CoxeterMatrixGroup
or a WeylGroup
is defined. It is given precisely by that choice of representation/matrix, so in a way, it is a Coxeter system along with a specified representation.
Also, any v
(implicitly) carries with it a vector space (not up to isomorphism), and we are checking to see if the Coxeter group has a defined action on that vector space. An alternative viewpoint is if v
is a Sage vector, in a way, we are only considering that element up to isomorphism, so we have lost some information (but again, that is if we don't fix a representation which makes a canonical choice of basis for the vector space). In contrast, for v
being an element of the root/weight/ambient space, we have an explicit basis and we have defined where the roots are in these, so the action is well-defined and explicit.
For
ReflectionGroup
I just thought that the best is to have the method.action
to take two parametersside
being"left"
or"right"
andon_space
being"primal"
or"dual"
.Beside that, I am okay with providing the coercion to act on the primal, but am also okay with removing it again (I am slightly in favour of keeping it though).
In case there is any ambiguity, I'm also only really advocating for using *
in the real reflection group setting. Moreover, I think we should avoid using Sage vectors for the roots (at least in the generic parents) because there is some ambiguity about their basis.
comment:46 in reply to: ↑ 45 ; follow-up: ↓ 48 Changed 5 years ago by
Replying to tscrim:
No, that is not true except in the most abstract sense of a linear morphism and an element of a vector space. A matrix comes with an implicit choice of a basis, and when we write vectors as tuples, there is an implicit choice of a basis as well.
The point I wanted to make is that given a field k, you can define an nxn matrix M over k as a table of entries in k and you can define an n-tuple to be an n-tuple x of entries in k, and you can multiply them Mx by some explicit row-column definition. At this point, there is no basis involved. One can even enrich the set kn with a vector space structure and then see the multiplication by M at a linear map without ever talking about bases. And this multiplication is defined in Sage, even if k is not a field so there is no as simple concept of bases.
Only if one wants to consider a k-linear map phi : V -> V on a vector space V over k as a matrix, then the basis comes into play.
Of course one could say that kn has an implicit basis in which the above matrix represents a linear map, but that is not quite adequate since kn comes with a canonical standard basis, so there is no choice of an implicit basis.
For example, if
M
is a diagonalizable matrix acting on a vector spaceV
,
in your argument, you always assume a general vector space V, there I agree that you play with explicit or implicit bases.
That is not how a
CoxeterMatrixGroup
or aWeylGroup
is defined. It is given precisely by that choice of representation/matrix, so in a way, it is a Coxeter system along with a specified representation.
That's right, and I am fine with arguing that this action of the group should be used when doing w*v
. But there are still other spaces involved on which the group also acts, so if you do not specify which space v
lives in one has to implicitly assume it to be this representation.
In case there is any ambiguity, I'm also only really advocating for using
*
in the real reflection group setting.
My proposition for reflection groups at the moment is
- have a method
.action(vec, side="left", on_space="primal")
that does the appropriate action, and - have
._act_on_(vec, self_on_left)
defined as.action(vec, side=side, on_space="primal")
where the side is set depending on self_on_left beingTrue
orFalse
.
Moreover, I think we should avoid using Sage vectors for the roots (at least in the generic parents) because there is some ambiguity about their basis.
I agree, but I have not yet implemented root spaces and coroot spaces for crg's. So I don't have anything better to provide for now than vectors. But that's on the todo list...
comment:47 Changed 5 years ago by
One quick question outside of finite type Weyl and Coxeter groups W
: is it correct that the actions of W
on V
and on V^*
are the same. This is, the image of (x1,...,xn) under w
is the same for (x1,...,xn) being a vector in V
expressed in the basis {ei} and being a vector in V^*
expressed in the dual basis {xi}?
comment:48 in reply to: ↑ 46 ; follow-up: ↓ 49 Changed 5 years ago by
Replying to stumpc5:
Replying to tscrim: Of course one could say that kn has an implicit basis in which the above matrix represents a linear map, but that is not quite adequate since kn comes with a canonical standard basis, so there is no choice of an implicit basis.
There is a standard basis, but it is not canonical.
That is not how a
CoxeterMatrixGroup
or aWeylGroup
is defined. It is given precisely by that choice of representation/matrix, so in a way, it is a Coxeter system along with a specified representation.That's right, and I am fine with arguing that this action of the group should be used when doing
w*v
. But there are still other spaces involved on which the group also acts, so if you do not specify which spacev
lives in one has to implicitly assume it to be this representation.
This is no more implicit than the relationship with the chosen basis of a matrix and a vector. I still contend that by fixing a representation, we now have a canonical basis for V
(and we implicitly assume v
is an element of V
). For good reasons, we can't tell if v
is to be considered an element in the representation or some other (isomorphic) vector space.
In case there is any ambiguity, I'm also only really advocating for using
*
in the real reflection group setting.My proposition for reflection groups at the moment is
- have a method
.action(vec, side="left", on_space="primal")
that does the appropriate action, and- have
._act_on_(vec, self_on_left)
defined as.action(vec, side=side, on_space="primal")
where the side is set depending on self_on_left beingTrue
orFalse
.
That is good with me.
comment:49 in reply to: ↑ 48 ; follow-up: ↓ 50 Changed 5 years ago by
Replying to tscrim:
There is a standard basis, but it is not canonical.
Okay, let's agree that we both know the situation, but that we do not agree which structure to emphasize...
- have a method
.action(vec, side="left", on_space="primal")
that does the appropriate action, and- have
._act_on_(vec, self_on_left)
defined as.action(vec, side=side, on_space="primal")
where the side is set depending on self_on_left beingTrue
orFalse
.That is good with me.
Good!
@Nicolas, do you agree this to be reasonable or do even not like this usage of the coercion?
comment:50 in reply to: ↑ 49 Changed 5 years ago by
Replying to stumpc5:
@Nicolas, do you agree this to be reasonable or do even not like this usage of the coercion?
When in doubt, I tend to take the path that is easier to change in the future in case one change one's mind after gaining more experience. In this case, it's easier to add the coercion later on than to remove it, or replace it by something else.
But that's no strong opinion. Proceed as you believe is right.
Cheers,
comment:51 Changed 5 years ago by
- Commit changed from 295d784db0ae24bed97ed7b4d3777df9dbd652c2 to 619ba6e8422ce14b34cbfed3d9f982a72cf27183
comment:52 Changed 5 years ago by
I am still struggling with the left/right action -- here, we want left actions (i.e., matrix*vector), but the standard for reflection groups is right action. I know how to turn left to right action for real and for well-generated groups, but still don't get it right to have it for the badly generated groups.
Actually, this shouldn't hold this ticket of, but I haven't resorted things yet...
comment:53 Changed 5 years ago by
- Commit changed from 619ba6e8422ce14b34cbfed3d9f982a72cf27183 to f0353a5ff43a9c1c5b113379513350a194416dc8
Branch pushed to git repo; I updated commit sha1. New commits:
f0353a5 | working out the left/right action
|
comment:54 Changed 5 years ago by
- Commit changed from f0353a5ff43a9c1c5b113379513350a194416dc8 to 5076f0bfcaae0e7592262d1bddc0df9ff5452230
Branch pushed to git repo; I updated commit sha1. New commits:
5076f0b | Merge branch 'develop' into u/stumpc5/20402
|
comment:55 Changed 5 years ago by
- Dependencies changed from #11187 to #11187, #20521
comment:56 Changed 5 years ago by
- Commit changed from 5076f0bfcaae0e7592262d1bddc0df9ff5452230 to 8ffeaf9449529ed0f1d05007fc16a3ae4c5143f5
comment:57 Changed 5 years ago by
- Dependencies changed from #11187, #20521 to #20521
- Status changed from needs_work to needs_review
comment:58 Changed 5 years ago by
- Commit changed from 8ffeaf9449529ed0f1d05007fc16a3ae4c5143f5 to 03b1ae00fbf0857b4ee29e819008d01f751dbdae
comment:59 Changed 5 years ago by
I just rechecked -- beside the changes now moved to #20521 and the few changes in coxeter_groups.py
, there are almost entirely newly added doctests for ReflectionGroup
.
comment:60 Changed 5 years ago by
Instead of
print "Caution: the Minkowski summands are build with rational vertices."
(which it should be print("foo") to be Python3 compatible) you should use Sage's warning mechanism:
from warnings import warn warn("foo", RuntimeWarning)
Otherwise LGTM.
comment:61 Changed 5 years ago by
- Commit changed from 03b1ae00fbf0857b4ee29e819008d01f751dbdae to 71eba72e896ba17314bcab6965f33005d02a26e4
Branch pushed to git repo; I updated commit sha1. New commits:
71eba72 | using python warnings
|
comment:62 Changed 5 years ago by
- Reviewers set to Frederic Chapoton, Travis Scrimshaw
Done, thx also here! -- more improvements to come hopefully soon...
comment:63 Changed 5 years ago by
Frédéric, Nicolas, anything else before setting this to a positive review?
comment:64 Changed 5 years ago by
- Reviewers changed from Frederic Chapoton, Travis Scrimshaw to Frédéric Chapoton, Travis Scrimshaw
comment:65 Changed 5 years ago by
A quick *ping* here to check whether we can get this ticket merged...
comment:66 Changed 5 years ago by
- Status changed from needs_review to positive_review
If there is possibly anything else, then they can set this back from a positive review.
comment:67 Changed 5 years ago by
- Branch changed from u/stumpc5/20402 to 71eba72e896ba17314bcab6965f33005d02a26e4
- Resolution set to fixed
- Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
trac #11187 more doc tuning
Merge branch 'u/chapoton/11187' of trac.sagemath.org:sage into u/tscrim/reflection_groups-11187
added ST type casting for real groups + documentation of crg's
Merge branch 'u/stumpc5/11187' of trac.sagemath.org:sage into u/tscrim/reflection_groups-11187
working through the doctests for complex groups
fixing all doctests
Merge branch 'u/stumpc5/11187' into u/stumpc5/20402
fixed a typo in the doc
Merge branch 'u/stumpc5/11187' into u/stumpc5/20402
marked a missing doctest + fixed a bug to show type C2