Opened 7 years ago
Closed 6 years ago
#20027 closed defect (fixed)
Different behavior for reflections for matrix Coxeter group and Weyl groups
Reported by:  tscrim  Owned by:  sagecombinat 

Priority:  major  Milestone:  sage7.1 
Component:  combinatorics  Keywords:  coxeter groups, reflections 
Cc:  sagecombinat, nthiery, chapoton, stumpc5, aschilling, mshimo, darij, jipilab, bump  Merged in:  
Authors:  Travis Scrimshaw  Reviewers:  Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  46565ec (Commits, GitHub, GitLab)  Commit:  46565ec3253dc5ef1b3c2e1e6e288e2806602b44 
Dependencies:  Stopgaps: 
Description
Currently, we have the following behavior:
sage: W = CoxeterGroup(['A',1]) sage: W.reflections() [[1]] sage: W = WeylGroup(['A',1]) sage: W.reflections() Finite family {[0 1] [1 0]: (1, 1)}
In particular, the former returns a list of elements in the group, whereas the latter returns a family whose keys are elements in the group and whose values are roots. This leads to different iterator behaviors between the two. Since Weyl groups are a subcategory of Coxeter groups, we should make this behavior consistent.
Note, this was introduced by #11010 and is specific for the matrix implementation of CoxeterGroup
. We can also lift this up to the category of (finite) Coxeter groups.
Change History (24)
comment:1 Changed 7 years ago by
comment:2 Changed 7 years ago by
Oops, really, reflections
does not return a collection of reflections? It makes sense to index the reflections by roots; and it can be ok to have the index set depend on the implementation, and or to return the collection as a plain list/tuple. But returning a family of roots indexed by reflections feels really weird. I am surprised I did not catch this earlier.
@stumpc5: by default I would indeed wait for a strong use case before adding a layer of complexity.
comment:3 followup: ↓ 5 Changed 7 years ago by
It makes sense to index the reflections by roots
for the complex reflection groups to come, this would not make sense, so if we want to have these to have similar behaviour, such an indexing would be bad.
comment:4 followup: ↓ 6 Changed 7 years ago by
I think it is best to have them be consistent, which we can easily do by making CoxeterGroup.reflections
return a family indexed by the reflections whose values are the roots.
With that being said, in many ways I feel that it is more natural for the family to be indexed by the roots and the values be reflections. It means we can just do for x in W.reflections()
as I don't think of roots as being reflection (instead of corresponding to).
I would return a family with the keys being roots and values being reflections. Since iteration over a family is iteration over the values, this will be consistent with complex reflection groups returning a tuple (taking advantage of ducktyping). At least, I don't think of reflections having a natural total ordering, so you should only be iterating over all them.
comment:5 in reply to: ↑ 3 Changed 7 years ago by
Replying to stumpc5:
It makes sense to index the reflections by roots
for the complex reflection groups to come, this would not make sense, so if we want to have these to have similar behaviour, such an indexing would be bad.
Agreed. I meant: it's a reasonable indexing in the above example. I guess at this point we want to leave freedom of the indexing set, and only impose that reflections return a collection of elements of the group.
comment:6 in reply to: ↑ 4 Changed 7 years ago by
Replying to tscrim:
With that being said, in many ways I feel that it is more natural for the family to be indexed by the roots and the values be reflections. It means we can just do
for x in W.reflections()
as I don't think of roots as being reflection (instead of corresponding to).I would return a family with the keys being roots and values being reflections. Since iteration over a family is iteration over the values, this will be consistent with complex reflection groups returning a tuple (taking advantage of ducktyping). At least, I don't think of reflections having a natural total ordering, so you should only be iterating over all them.
+1
comment:7 Changed 7 years ago by
At least, I don't think of reflections having a natural total ordering
See Dyer "Hecke algebras and shellings of Bruhat intervals" for the importance of reflection orderings ;). I usually want them to come at least in some "convex order" as in that paper...
Anyway, I am fine with giving freedom to the keys, and only force that iteration does iters through the actual reflections.
comment:8 Changed 7 years ago by
 Branch set to public/combinat/fix_reflections_coxeter_groups20027
 Commit set to 25958261175f453493c4da055cccfe5a1880ecb2
Okay, here is where I am at. I flipped the key/value order on WeylGroup.reflections()
. I made CoxeterGroup.reflections()
return a family. Additionally, I did some cleanup on the @cached_method
returning mutable objects. This included removing the caching of positive_roots
as it did not appear to be called anywhere except in roots()
, which is cached, so I don't see a reason to cache it (moreover, getting the keys from a Family
should be fast).
So now my questions are these:
 Do we want to issue a warning for the change in behavior for
WeylGroup.reflections()
? If so, how should we?  Do we want to lift one or both of these implementations to the category (and on this ticket)?
 Do we want to implement an iterator over all reflections for infinite groups? This could be done by a
RecursivelyEnumeratedSet
which goes by conjugating by simple reflections corresponding to the nondescents of a given reflection.
@stumpc5 I agree that convex orders are natural and important, but we would still need a natural/canonical reduced expression for the long element. Although I guess we could use the reduced expression that gives the BZL strings (I only know this for type A_{n} though...), but this still feels somewhat artificial to me.
New commits:
90b278a  Reversing the family for reflections.

8c9b809  Making CoxeterGroup.reflections return a Family and some touchups.

2595826  Removing caching of CoxeterGroup.positive_roots().

comment:9 Changed 6 years ago by
Travis, would you please set this to needs_review
? so that bots can work on it ?
There will be some tutorials to correct, probably.
Concerning your questions:
 I would give no warning (maybe this is bad, but I do not see a nice way to do that)
 no lifting to category on this ticket
 no care for infinite groups on this ticket
comment:10 Changed 6 years ago by
 Status changed from new to needs_review
Done. With those answers, this ticket is an honest needs review.
comment:11 Changed 6 years ago by
Ok, some doctests failing in tutorial, as expected.
Please also add a sentence like
The behaviour of this function has been changed in :trac:`20027`.
in the function where the dict is turned around.
comment:12 Changed 6 years ago by
 Status changed from needs_review to needs_work
comment:13 Changed 6 years ago by
 Commit changed from 25958261175f453493c4da055cccfe5a1880ecb2 to 3c32075db48c66b679bc142ce7ffd894d9d4b911
comment:14 Changed 6 years ago by
 Cc aschilling mshimo darij jipilab added
 Status changed from needs_work to needs_review
Done.
Those I've added in cc, you are known to me to potentially call this method. This and the sagedevel announcement will be your only warning that this behavior will have changed.
comment:15 Changed 6 years ago by
 Cc bump added
comment:16 Changed 6 years ago by
This sentence is now wrong (in the tutorial):
The keys are the positive roots, so given a reflection, you can look up the corresponding root.
And please add the ref to the ticket 20027 also directly in the modified function in
sage/combinat/root_system/weyl_group.py
comment:17 Changed 6 years ago by
 Commit changed from 3c32075db48c66b679bc142ce7ffd894d9d4b911 to 35eb71c31040c78280579c8f92496aa94d884705
Branch pushed to git repo; I updated commit sha1. New commits:
35eb71c  Fixing some documentation and adding note to WeylGroup.reflections.

comment:18 Changed 6 years ago by
I've corrected that sentence and added the note.
comment:19 Changed 6 years ago by
I also created a followup #20170 which implements WeylGroup.reflections
for the affine Weyl groups.
comment:20 Changed 6 years ago by
Now the sentence above is false (in tutorial):
The reflections are the keys in a finite family, which is a wrapper
comment:21 Changed 6 years ago by
 Commit changed from 35eb71c31040c78280579c8f92496aa94d884705 to 46565ec3253dc5ef1b3c2e1e6e288e2806602b44
Branch pushed to git repo; I updated commit sha1. New commits:
46565ec  Missed (hopefully the last) one instance of the flipped keys/values.

comment:22 Changed 6 years ago by
Yes indeed. I think that is the last falsewithpatch sentence.
comment:23 Changed 6 years ago by
 Reviewers set to Frédéric Chapoton
 Status changed from needs_review to positive_review
ok, looks good to me.
comment:24 Changed 6 years ago by
 Branch changed from public/combinat/fix_reflections_coxeter_groups20027 to 46565ec3253dc5ef1b3c2e1e6e288e2806602b44
 Resolution set to fixed
 Status changed from positive_review to closed
Hi Travis,
also in the light of hopefully having soon the
chevie
version of reflection groups:There, is is currently