Opened 5 years ago

Closed 5 years ago

#20027 closed defect (fixed)

Different behavior for reflections for matrix Coxeter group and Weyl groups

Reported by: tscrim Owned by: sage-combinat
Priority: major Milestone: sage-7.1
Component: combinatorics Keywords: coxeter groups, reflections
Cc: sage-combinat, 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:

Status badges

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 5 years ago by stumpc5

Hi Travis,

also in the light of hopefully having soon the chevie version of reflection groups:

  • What do you think is the correct behaviour?
  • Does it make sense to allow user labels of the reflections in the case of finite reflection groups? -- this might be interesting in the situation that you want to look for words in all reflections. (But that also puts another layer of possible bugs!)

There, is is currently

sage: ReflectionGroup(['A',1]).reflections()
Finite family {0: (1,2)}
sage: ReflectionGroup(['A',1],reflection_index_set=["A"]).reflections()
Finite family {'A': (1,2)}

comment:2 Changed 5 years ago by nthiery

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 follow-up: Changed 5 years ago by 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.

comment:4 follow-up: Changed 5 years ago by tscrim

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 5 years ago by nthiery

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 5 years ago by nthiery

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 5 years ago by stumpc5

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 5 years ago by tscrim

  • Authors set to Travis Scrimshaw
  • Branch set to public/combinat/fix_reflections_coxeter_groups-20027
  • 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 non-descents 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 An though...), but this still feels somewhat artificial to me.


New commits:

90b278aReversing the family for reflections.
8c9b809Making CoxeterGroup.reflections return a Family and some touchups.
2595826Removing caching of CoxeterGroup.positive_roots().

comment:9 Changed 5 years ago by chapoton

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 5 years ago by tscrim

  • Status changed from new to needs_review

Done. With those answers, this ticket is an honest needs review.

comment:11 Changed 5 years ago by chapoton

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 5 years ago by chapoton

  • Status changed from needs_review to needs_work

comment:13 Changed 5 years ago by git

  • Commit changed from 25958261175f453493c4da055cccfe5a1880ecb2 to 3c32075db48c66b679bc142ce7ffd894d9d4b911

Branch pushed to git repo; I updated commit sha1. New commits:

7ed4c2aMerge 7.1.beta6.
3c32075Fixing doctest failures in the thematic tutorials.

comment:14 Changed 5 years ago by tscrim

  • 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 sage-devel announcement will be your only warning that this behavior will have changed.

comment:15 Changed 5 years ago by aschilling

  • Cc bump added

comment:16 Changed 5 years ago by chapoton

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 5 years ago by git

  • Commit changed from 3c32075db48c66b679bc142ce7ffd894d9d4b911 to 35eb71c31040c78280579c8f92496aa94d884705

Branch pushed to git repo; I updated commit sha1. New commits:

35eb71cFixing some documentation and adding note to WeylGroup.reflections.

comment:18 Changed 5 years ago by tscrim

I've corrected that sentence and added the note.

comment:19 Changed 5 years ago by tscrim

I also created a follow-up #20170 which implements WeylGroup.reflections for the affine Weyl groups.

comment:20 Changed 5 years ago by chapoton

Now the sentence above is false (in tutorial):

The reflections are the keys in a finite family, which is a wrapper

comment:21 Changed 5 years ago by git

  • Commit changed from 35eb71c31040c78280579c8f92496aa94d884705 to 46565ec3253dc5ef1b3c2e1e6e288e2806602b44

Branch pushed to git repo; I updated commit sha1. New commits:

46565ecMissed (hopefully the last) one instance of the flipped keys/values.

comment:22 Changed 5 years ago by tscrim

Yes indeed. I think that is the last false-with-patch sentence.

comment:23 Changed 5 years ago by chapoton

  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_review to positive_review

ok, looks good to me.

comment:24 Changed 5 years ago by vbraun

  • Branch changed from public/combinat/fix_reflections_coxeter_groups-20027 to 46565ec3253dc5ef1b3c2e1e6e288e2806602b44
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.