Different behavior for reflections for matrix Coxeter group and Weyl groups

[tscrim]

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.

CC: @sagetrac-sage-combinat @nthiery @fchapoton @stumpc5 @anneschilling @sagetrac-mshimo @darijgr @jplab @dwbump

Component: combinatorics

Keywords: coxeter groups, reflections

Author: Travis Scrimshaw

Branch/Commit: 46565ec

Reviewer: Frédéric Chapoton

Issue created by migration from https://trac.sagemath.org/ticket/20027

[stumpc5]

comment:1

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)}

[nthiery]

comment:2

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.

[stumpc5]

comment:3

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.

[tscrim]

comment:4

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.

[nthiery]

comment:5

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.

[nthiery]

comment:6

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

[stumpc5]

comment:7

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.

[tscrim]

Branch: public/combinat/fix_reflections_coxeter_groups-20027

[tscrim]

Author: Travis Scrimshaw

[tscrim]

comment:8

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 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().

[tscrim]

Commit: 2595826

[fchapoton]

comment:9

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

[tscrim]

comment:10

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

[fchapoton]

comment:11

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.

[sagetrac-git]

Changed commit from 2595826 to 3c32075

[sagetrac-git]

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

7ed4c2a	Merge 7.1.beta6.
3c32075	Fixing doctest failures in the thematic tutorials.

[tscrim]

comment:14

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.

[fchapoton]

comment:16

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

[sagetrac-git]

Changed commit from 3c32075 to 35eb71c

[sagetrac-git]

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

35eb71c

Fixing some documentation and adding note to WeylGroup.reflections.

[tscrim]

comment:18

I've corrected that sentence and added the note.

[tscrim]

comment:19

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

[fchapoton]

comment:20

Now the sentence above is false (in tutorial):

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

[sagetrac-git]

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

46565ec

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

[sagetrac-git]

Changed commit from 35eb71c to 46565ec

[tscrim]

comment:22

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

[fchapoton]

comment:23

ok, looks good to me.

[fchapoton]

Reviewer: Frédéric Chapoton

[vbraun]

Changed branch from public/combinat/fix_reflections_coxeter_groups-20027 to 46565ec