fix bug in has_right/left_descents in Weyl group code

[zabrocki]

The has_right_descents method in WeylGroup element methods calls has_left_descents and vice versa. This causes an error in the following example.

sage: W = WeylGroup(['A',4])
sage: w = W.from_reduced_word([3,4,2])
sage: w.has_right_descent(3)
Traceback (click to the left of this block for traceback)
...
RuntimeError: maximum recursion depth exceeded

The doc tests for this method make calls to CoxeterGroup code to test it and so all tests pass.

CC: @sdenton4 @anneschilling @nthiery @sagetrac-sage-combinat

Component: combinatorics

Keywords: coxeter, sd65

Author: Frédéric Chapoton

Branch/Commit: public/15456 @ 45ff0e3

Reviewer: Anne Schilling, Mike Zabrocki

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

[nthiery]

comment:1

Hi Mike!

This is not a bug but a feature :-)

When implementing a Coxeter group one can choose to either implement has_right_descent or has_left_descent (or both), and the Coxeter group category provides a default implementation for the other, if needed.

Granted, it would be nice if there was a nicer error message mentionning that at least one of has_left_descent or has_right_descent should be implemented. However, at this point, we have not generic infrastructure for this kind of situation, and it would be a bit tedious to do it by hand (but ideas on how to handle this are welcome!).

Cheers,

[zabrocki]

comment:2

Hi Nicolas,

This can't be a feature. In WeylGroup this is a bug. In CoxeterGroup it is correct.

In WeylGroups the method has_right_descent and has_left_descent don't do anything except call each other.

[zabrocki]

comment:3

BTW, in WeylGroup the method has_descent doesn't call either has_right_descent or has_left_descent and decides if there is a right/left descent by another method.

[nthiery]

comment:4

Right. The proper specification is:

• at least one of has_descent / has_right_descent / has_left_descent should be implemented
• in generic code, always use has_descent, not has_*_descent.

This definitely should be put in the doc if not yet there.

[zabrocki]

comment:5

I take the part about it being correct in CoxeterGroup back. It seems to only be correct for the CoxeterGroups().example().

I assume that you are right in that "Coxeter group category provides a default implementation for the other" but no one has implemented has_right_descent or has_left_descent for any of the finite or affine WeylGroups or CoxeterGroups (to an end user of these groups, this is a bug because it should just raise a Not Implemented error).

Is the correct solution then that

(1) someone needs to implement them for each of the types

(2) that the default implementation should be has_left_descent should call has_descent(self, side="left")

(3) the default implementation of has_right_descent should raise a Not Implemented error

(4) something else?

[fchapoton]

comment:7

Here is a possible solution. Please review.

---

New commits:

549f238

trac #15456 tentative solution

[fchapoton]

Commit: 549f238

[fchapoton]

Branch: u/chapoton/15456

[fchapoton]

Author: Frédéric Chapoton

[tscrim]

comment:8

I think what we should do is have has_left_descent call has_descent(self, side="right") and has_right_descent call has_descent(self, side="left").

[fchapoton]

comment:9

Indeed ? well, please do that if you think this is the thing to do.

[sdenton4]

comment:10

tscrim: That's what WAS happening, but if you instantiate an abstract Weyl Group or Coxeter Group it leads to an infinite loop, which is a bug. What we need is a NotImplemented error if neither side is implemented, and the appropriate call to the implemented 'side' if one side or the other is concretely implemented but not the other.

I see two possible ways forward:

1. The default Coxeter/Weyl Group 'has_x_descent' methods just give a NotImplemented error, pushing it to the person creating a concrete realization to actually implement them correctly and not give an infinite loop, or
2. Introduce some kind of '_is_implemented' flags for checking left and right descent, which are false by default, and set to true if there's a concrete implementation on one side that the other can use. Then if it's true, we call the other side, and otherwise raise a NotImplemented error.

Option 2 seems doable but introduces an Obscure Thing for the implementers of Coxeter groups to keep track of. As such, I would advocate for Option 1.

[sdenton4]

comment:11

It's also worth noting that sometimes one 'side' or the other is simply faster for computing descents. This is clearly true for simple permutations: one can check in constant time if there's a right descent, but it takes O(n) to check for a left descent. So then it would be bad news bears to have a default implementation of the right descent that calls the left decent.

But in other cases, it's maybe the left descent that's faster to compute, so you wouldn't want the reverse situation, either...

So I think I would advocate against breaking symmetry at the Category level, and just raise NotImplemented errors for both sides.

[fchapoton]

comment:12

I do not understand why my solution is not good enough. From my point of view, the function has_descent in weyl_group.py should rather be named has_right_descent, because it is necessary to have at least one of the two (left or right) descent methods to avoid the infinite loop. I think that has_descent should only be defined for abstract Coxeter groups.

[tscrim]

comment:13

Hey Tom,

If we made both left/right @abstract_method's, then we would have to implement all methods. If we made them optional, I feel that we'd get bug reports about these not being implemented. The problem is that has_descent() wasn't being brought into the loop, so if that was the only thing implemented, then one couldn't use has_left_descent() as expects. Thus the spec:

• at least one of has_descent / has_right_descent / has_left_descent should be implemented

would be satisfied in my proposal.

Although I think we could do a modified version of your proposal 1) by implementing some kind of modification to @abstract_method. Something like

@abstract_method(circular=['foo', 'bar'])

where if foo and bar were also called, then error out.

[tscrim]

comment:14

Replying to @fchapoton:

I do not understand why my solution is not good enough. From my point of view, the function has_descent in weyl_group.py should rather be named has_right_descent, because it is necessary to have at least one of the two (left or right) descent methods to avoid the infinite loop. I think that has_descent should only be defined for abstract Coxeter groups.

The has_descent() in weyl_group.py works for both sides, and by simply doing an alias, you're exposing invalid (at least 'should not be used') arguments in has_right_descent(). In essence what you're doing is saying has_right_descent() should call has_descent() with the appropriate arguments. I'm saying let's do this in a generic fashion to follow the spec (I think comment:4 point 1 is in the doc already, but I haven't checked).

[zabrocki]

comment:15

I couldn't find an indication that the documentation specifies that at least one of has_descent / has_right_descent / has_left_descent should be implemented.

Instead it seems to be that the default implementation of has_descent calls has_leftorright_descent

Maybe we should throw checks in _test_has_descent to ensure that all of the functions work.

[sagetrac-git]

Changed commit from 549f238 to d0bdcca

[sagetrac-git]

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

d0bdcca

trac #15456 another try

[fchapoton]

comment:17

Here is new (better) proposal:

The main idea is "please never override has_descent" and "please implement either has_left_descent or has_right_descent" in every instance (if only as a place holder raising NotImplementedError).

In categories/coxeter_group, there is only the mechanism:

• has_descent calls either has_left_descent or has right_descent
• they call each other

In instances of Coxeter group, one implements either has_left_descent or has_right_descent or both. Even in a minimalistic way, raising a NotImplementedError.

What do you think ?

[sagetrac-git]

Changed commit from d0bdcca to bef966f

[sagetrac-git]

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

bef966f

trac #15456 remove two unused lines

[zabrocki]

comment:19

I think this is a good solution and probably what was intended to happen when the CoxeterGroup code was originally written. Do others agree?

[anneschilling]

Changed branch from u/chapoton/15456 to public/15456

[anneschilling]

Changed commit from 5922bda to 45ff0e3

[anneschilling]

New commits:

45ff0e3

Merge branch 'develop' into u/chapoton/15456

[anneschilling]

comment:33

Replying to @zabrocki:

I am comfortable with accepting Frédéric's changes. From Nicolas' comments I think that the original implementation meant to have has_descent should call either has_left or has_right and at least one of those needs to be implemented.

I checked that at least the _test_has_descent will fail when one of these is not implemented by going into a Coxeter group implementation, deleting the has_right_descent method, and then checking that G._test_has_descent() raises an error. The problem is that all tests will pass in the implementation of a Coxeter group unless the _test_has_descent method is called (which was probably always the case and the source of the original problem). Is there a way of ensuring that a test of the left and right functions will be made for future implementations? We can just leave it up to the warning which is already in the documentation.

I am ok with Federic's solution. All tests pass, so I think this should go in.

[zabrocki]

comment:34

Anne looked at the code as well. We both approve and I am setting to positive review.

[zabrocki]

Reviewer: Anne Schilling, Mike Zabrocki

[fchapoton]

comment:35

This will conflict will #18610 and is probably a duplicate. The review is coming too late.

This need to be checked, nevertheless.

[zabrocki]

Changed keywords from coxeter to coxeter, sd65

[fchapoton]

comment:39

ok, let us consider that this has been solved by #18610

[anneschilling]

comment:40

Replying to @fchapoton:

ok, let us consider that this has been solved by #18610

Why are you setting it to positive review then and not leave it at sage-duplicate?

[fchapoton]

comment:41

This is 'positive review as a duplicate', the usual standard procedure, so that it can be closed!