Default of Coxeter group methods is right but reflection group can be left

[tscrim]

The problem manifests itself when computing bruhat_lower_covers, where has_descent is localized to use whichever side is better, but first_descent is generic and defaults to the right.

sage: W = CoxeterGroup('A3', implementation='permutation')
sage: w = W.from_reduced_word([1,2,3,1])
sage: desc = w.first_descent()
sage: ww = w.apply_simple_reflection(desc)
sage: ww.reduced_word()
[1, 2, 3]
sage: [x.reduced_word() for x in ww.bruhat_lower_covers()]
[[2, 3], [1, 3], [1, 2]]
sage: [x.has_descent(desc) for x in ww.bruhat_lower_covers()]
[False, True, True]

This was first noticed on #23297.

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

Component: combinatorics

Keywords: coxeter groups

Author: Travis Scrimshaw

Branch/Commit: public/combinat/left_right_default-23299 @ f25b4e1

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

[tscrim]

comment:1

IMO, this is very subtle bug and could require some extra care to make sure we don't have it crop up again. I'm not sure what the best way forward is. Here are some thoughts:

1. Quick with technical debt: Just force bruhat_lower_covers to decide on a side.
2. Reflection groups should conform: Make them use right as the default.
3. Much better long term: Use a class based hook, such as an attribute _default_side.

We do not really want to do (2) because that would slow down the multiplication code for the reflection groups, which the whole point is basically to be fast on those operations. I'm somewhat in favor of (1) because it solves the problem at hand and basically everything else makes you choose a side.

We might also want to consider implementing a more efficient has_right_inverse which just goes and finds the specific inverse of W._index_set_inverse[i] in self.perm and checks that is not too far out.

[nthiery]

comment:2

Thanks Travis for your comments. My perspective is roughly the same:

To guarantee correct code, the behavior of all methods shall be consistent across all implementations. This implies:

• Methods about descents shall all assume that left descents are about products s_i.w and right descents about products w.s_i
• The default values shall be consistent.

That being said, it could indeed make sense to (eventually) introduce some attribute _preferred_side allowing a specific implementation to specify whether descents are more efficiently computed on the left or on the right.

[tscrim]

Author: Travis Scrimshaw

[tscrim]

Commit: 3fc53c3

[tscrim]

comment:3

Here is a version that uses a default attribute _default_side set at the class-level in the appropriate category. There were a number of other little things that needed some fixing, such as has_descent for Weyl groups had a non-standard argument order. I also did a bunch of PEP8 and documentation cleanup since they needed it.

---

New commits:

3fc53c3

Implementing a default left/right attribute for descents plus cleanup.

[tscrim]

Branch: public/combinat/left_right_default-23299

[nthiery]

comment:4

Hi Travis!

I haven't yet been through your patch. Just in case, see my comment above: I believe the default side should really be the same for all implementations.

Cheers,

[tscrim]

comment:5

I am -1 because some implementations are designed to work on the left and some on the right. It would require much deeper changes in order to get that, and even still, I am not sure we should favor one side over the other.

[stumpc5]

comment:6

I haven't yet been through your patch. Just in case, see my comment above: I believe the default side should really be the same for all implementations.

I don't want this to happen for reflection groups. I indeed believe it is a big misinterpretation that sage structures should behave similarly! Let me elaborate this a little too much:

As soon as you write a math paper that uses concepts from different areas (especially in combinatorics) you realize that it is super hard to get the different needed notions into a common framework and to choose notions and options in a consistent way. What I usually see is that for some aspects, one choice is better and for different aspects a different choice is better and that there is no "best global choice" for notions and options.

And this is only a single math paper! Sage (or a big portion of the developers) now wants to streamline notions over much bigger parts of math -- I consider this an impossible task and indeed a false believe.

For example, the reflection groups are implemented as permutations groups and now inherit everything from permutation groups. But most methods are just garbage in this context, completely useless or even provide wrong output (such as stuff that relates group elements to the permutation representation as a permutation group rather than the reflection representation of the reflection group).

I think a reflection group is a reflection group and nothing else! Of course, as such it is closely linked to other objects, and one can even think of this one group as other structures. But intrinsically, it is nothing else and all the implicit connections that a human brain can simultaneously handle are doomed to fail if one makes them all explicit for a computer use.

[stumpc5]

comment:7

Concretely in the present case, I prefer reflection groups to behave the way Jean Michel and others thought about it in chevie as this is the speed-wise best implementation we currently have.

[nthiery]

comment:8

Replying to @tscrim:

I am -1 because some implementations are designed to work on the left and some on the right. It would require much deeper changes in order to get that, and even still, I am not sure we should favor one side over the other.

Enabling different defaults in the different implementations is adding one more burden to the writter of generic code: namely being careful to specify the side whenever this is relevant.
A wrong choice will trigger incorrect code. Whereas with the "prefereed size" approach, the writter only needs to worry about it if speed is critical.

If we decide to go this way, then we need to proeminently document that, plus prepare for backward compatibility issues (and take responsibility for them), plus check all the existing code for locations where the side is not specified.

Unrelated issue: 3fc53c3 is a pain to review, because it mixes a few highly sensitive changes (that requires scrutinizing) to a lot of trivialities (that one can check by just glossing over them).

[nthiery]

comment:9

Replying to @stumpc5:

I don't want this to happen for reflection groups. I indeed believe it is a big misinterpretation that sage structures should behave similarly! Let me elaborate this a little too much:

As soon as you write a math paper that uses concepts from different areas (especially in combinatorics) you realize that it is super hard to get the different needed notions into a common framework and to choose notions and options in a consistent way. What I usually see is that for some aspects, one choice is better and for different aspects a different choice is better and that there is no "best global choice" for notions and options.
And this is only a single math paper! Sage (or a big portion of the developers) now wants to streamline notions over much bigger parts of math -- I consider this an impossible task and indeed a false believe.

I can't agree more. Ever since I am touching Sage, I have been
promoting code that can adapt to different conventions (indexed
objects, side of actions, Dynkin diagrams with any node labeling,
Hecke algebras with generic parameters, ...).

And yes, we want to have reflection groups implemented by left actions
and right actions (or no action at all). In fact, going further, when
a user requests a reflection group as, e.g., a permutation group, we
would want him to be able to specify whether he wants left or right
actions (in general, PermutationGroup should take a side option like
FiniteSetMaps does).

But here I believe the discussion is orthogonal.

The motivation for the change is efficiency: sometimes left descents
are faster to compute; sometimes right descents are. This choice is
not dictated by the conventions. There are implementations of
reflection groups acting on the left where descents are faster on the
left and other where descents are faster on the right.

Having the default value (and therefore the API) depend on the
conventions would add some mental burden to the user and developer,
but could be arguable. Having it depend on an implementation detail,
subject to change, is dangerous. In particular since we want to
support, if not encourage, users to switch from one implementation to
the other, to explore which one fits best her/his use case.

For example, the reflection groups are implemented as permutations groups and now inherit everything from permutation groups. But most methods are just garbage in this context, completely useless or even provide wrong output (such as stuff that relates group elements to the permutation representation as a permutation group rather than the reflection representation of the reflection group).
I think a reflection group is a reflection group and nothing else! Of course, as such it is closely linked to other objects, and one can even think of this one group as other structures. But intrinsically, it is nothing else and all the implicit connections that a human brain can simultaneously handle are doomed to fail if one makes them all explicit for a computer use.

That is an independent question. The developers of reflections groups
are free to switch from "is a" to a "contains a" relation with
permutation group if they feel this is more appropriate.

I can hear your frustration, but let's not mix all debates.

Cheers,
Nicolas

[tscrim]

comment:10

Replying to @nthiery:

Replying to @tscrim:

I am -1 because some implementations are designed to work on the left and some on the right. It would require much deeper changes in order to get that, and even still, I am not sure we should favor one side over the other.

Enabling different defaults in the different implementations is adding one more burden to the writter of generic code: namely being careful to specify the side whenever this is relevant.
A wrong choice will trigger incorrect code. Whereas with the "prefereed size" approach, the writter only needs to worry about it if speed is critical.

Huh? "Preferred" should be the same as "default" (for that implementation). The code is so diffuse that is makes it seem like a lot, but fundamentally only based on two methods: has_descent and apply_simple_reflection. It pretty much passes the side option it is given down to more lower level functions. So there is no way a wrong choice could be introduced by a user.

However, I do agree that there is a little more of a burden for someone writing generic code that needs to pass side down. However, there is nothing in the current API that says someone needs to have the default being right, which led to the current bug. Nor do I think there should be such a requirement. So I guess what I am saying is someone writing generic code should be dealing with this anyways, not making strict requirements for concrete implementations.

If we decide to go this way, then we need to proeminently document that, plus prepare for backward compatibility issues (and take responsibility for them), plus check all the existing code for locations where the side is not specified.

There should be no backwards incompatibility issues. The default is still right and all methods go to that first. Besides, I really see this more as a bugfix. As I said above, this really only comes down to a few small places.

Unrelated issue: 3fc53c3 is a pain to review, because it mixes a few highly sensitive changes (that requires scrutinizing) to a lot of trivialities (that one can check by just glossing over them).

For some of them, yes. However, many of those changes were useful to me when doing this to simplify my greping and workflow.

[tscrim]

comment:11

Replying to @nthiery:

The motivation for the change is efficiency: sometimes left descents
are faster to compute; sometimes right descents are. This choice is
not dictated by the conventions. There are implementations of
reflection groups acting on the left where descents are faster on the
left and other where descents are faster on the right.

Having the default value (and therefore the API) depend on the
conventions would add some mental burden to the user and developer,
but could be arguable. Having it depend on an implementation detail,
subject to change, is dangerous. In particular since we want to
support, if not encourage, users to switch from one implementation to
the other, to explore which one fits best her/his use case.

It is unfair to call this an implementation detail. Really, we are trying to pass (necessary IMO) information up to the generic code for it to use because it is not really generic code because of the default values (or extra assumptions that you would enforce on your concrete classes). While it may be subject to change, having the requirements with a clear idiom means that the person doing the implementation will not care (provided they follow the requirements).

Also, as soon as you start talking about speed, you are not really talking about conventions in mathematics (well, for permutations/actions/etc.). So in order to have the code make any sense, we have to take into account the choice of convention. Moreover, it is usually something that cannot be easily changed without doing a large refactoring of the code.

[stumpc5]

comment:12

Replying to @nthiery:

I can hear your frustration, but let's not mix all debates.

Well, it's not too bad :-) And yes, it is technically two debates. But both are under the common roof of how encapsulated/intertwined different but related structures in sage should be. I personally think we spend too much time on the intertwining part that we could instead spend on the quality and speed of individual modules. Let us build individual cutting edge modules (here: on reflection groups) and if this needs other modules, one can either type cast or use APIs.

For this reason, I prefer not to streamline default behaviors, though I see that this might be hard to understand for new users. But either way, the behavior should be properly documented.

[nthiery]

comment:13

Argl, I wanted to give a proper answer before taking of for 3-4 days of vacations, but did not get to it. So in very short ...

As far as I remember, for all the descent-related methods (has_descent, ...), that the default side was "right" was documented in the uppest implementation/abstract_method (and therefore applying to all implementations in subclasses). It was even tested (e.g. in _test_has_descent). So changing the default is really a backward incompatible change.

I see Christian's concern, and that's indeed something to keep in mind. Yet I also believe that having a preferred_side attribute (or method; plausibly better named fast_side), solves this concern as well as the current approach, by enabling the computational intensive methods to do the additional yoga to use the proper side, but without forcing an additional mental burden on all users and developpers.

@tscrim: I can see that writing the change all at once was the most practical. But this does not preclude splitting the commit in two, to not impose a burden on the reviewers, and anyone later that will want to investigate exactly what was done at the occasion of a sensitive change.

I don't want to hold progress, so think it over, and do what you believe the right thing is. Alternatively, I could have a shot at the "fast_side" approach, but not before FPSAC. Being able to reuse a commit holding just the "trivial changes" would help.

Cheers,
Nicolas

[nthiery]

comment:14

Stated otherwise: I prefer an idiom stating explicitly "yes, the side is irrelevant in my context; please use whichever is faster":

   W.compute_something(side=W.fast_side())

Rather than an idiom that implicitly changes semantic depending on W:

   W.compute_something()

Off to canoeing!

Cheers,

[sagetrac-git]

Changed commit from 3fc53c3 to 8ba1333

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

1fbee1b	Changing Coxeter groups to use _default_side.
ee5ee6f	Putting WeylGroup.Element.has_descent signature (self, i, side, positive).
8ba1333	Doing lots of cleanup because it needs to be done and is useful.

[tscrim]

comment:16

I hope you had a good time canoeing. Sounds like more fun than dealing with typhoons (well, that was last week for me.)

Okay, here is the branch rebased with separate commits that should be correct individually but I didn't bother checking.

Nicolas, I think you're being far too precious here. I really don't see any (reasonable) way how you could have something like a "fast"/"preferred" side without fundamentally having to change the default value. This part could be backwards incompatible for anyone who is using subclasses and overwriting some of these methods assuming the input is strictly 'left' or 'right'. However, for users, nothing has changed except for two specific implementations.

As far as I remember, for all the descent-related methods (has_descent, ...), that the default side was "right" was documented in the uppest implementation/abstract_method (and therefore applying to all implementations in subclasses).

This is not true. The only place that explicitly mentioned the default was 'right' was in apply_simple_reflection. Yet, that is essentially the base method in this method hierarchy, and so it does not enforce it upon any other method.

It was even tested (e.g. in _test_has_descent). So changing the default is really a backward incompatible change.

This is also not true. The only time the default argument is used for has_descent in _test_has_descent is for 1 and simple reflections.

[fchapoton]

comment:17

does not apply

[sagetrac-git]

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

400079f

Merge branch 'public/combinat/left_right_default-23299' of git://trac.sagemath.org/sage into public/combinat/left_right_default-23299

[sagetrac-git]

Changed commit from 8ba1333 to 400079f

[fchapoton]

comment:20

many failing doctests (but not hopelessly many), see patchbot reports

[sagetrac-git]

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

39b789f	Merge branch 'public/combinat/left_right_default-23299' of git://trac.sagemath.org/sage into public/combinat/left_right_default-23299
f25b4e1	Getting closer, but there are some hidden sides being explicitly chosen (i.e., more work to do).

[sagetrac-git]

Changed commit from 400079f to f25b4e1