Opened 6 years ago

Closed 4 years ago

#15456 closed defect (duplicate)

fix bug in has_right/left_descents in Weyl group code

Reported by: zabrocki Owned by:
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: combinatorics Keywords: coxeter, sd65
Cc: sdenton, aschilling, nthiery, sage-combinat Merged in:
Authors: Frédéric Chapoton Reviewers: Anne Schilling, Mike Zabrocki
Report Upstream: N/A Work issues:
Branch: public/15456 Commit: 45ff0e370aea78c35197688d8983e9bfd1c00b51
Dependencies: Stopgaps:

Description

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.

Change History (42)

comment:1 Changed 6 years ago by nthiery

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,

comment:2 Changed 6 years ago by zabrocki

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.

comment:3 Changed 6 years ago by zabrocki

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.

comment:4 Changed 6 years ago by nthiery

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.

comment:5 Changed 6 years ago by zabrocki

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?

Last edited 6 years ago by zabrocki (previous) (diff)

comment:6 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:7 Changed 6 years ago by chapoton

  • Authors set to Frédéric Chapoton
  • Branch set to u/chapoton/15456
  • Commit set to 549f238c87e446116457d645c2b0171b423c02df
  • Status changed from new to needs_review

Here is a possible solution. Please review.


New commits:

549f238trac #15456 tentative solution

comment:8 Changed 6 years ago by tscrim

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

comment:9 Changed 6 years ago by chapoton

8)

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

comment:10 Changed 6 years ago by sdenton

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.

comment:11 Changed 6 years ago by sdenton

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.

comment:12 follow-up: Changed 6 years ago by chapoton

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.

comment:13 Changed 6 years ago by tscrim

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.

comment:14 in reply to: ↑ 12 Changed 6 years ago by tscrim

Replying to chapoton:

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

comment:15 Changed 6 years ago by zabrocki

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.

comment:16 Changed 6 years ago by git

  • Commit changed from 549f238c87e446116457d645c2b0171b423c02df to d0bdccadb38c68a0019d2056daebfd601b8910cb

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

d0bdccatrac #15456 another try

comment:17 Changed 6 years ago by chapoton

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 ?

comment:18 Changed 6 years ago by git

  • Commit changed from d0bdccadb38c68a0019d2056daebfd601b8910cb to bef966f7e6f1ce42da5578c8da4df8d5ebdf9f9b

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

bef966ftrac #15456 remove two unused lines

comment:19 Changed 6 years ago by zabrocki

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

comment:20 Changed 6 years ago by tscrim

I don't like having the warning saying "don't override this", especially since I don't see a good reason for doing this (and there's no "final" semantic in python). I am in favor of saying we must implement either has_left_descent() or has_right_descent(). Also possibly implementing has_left/right_descent() for weyl_group.py to call has_descent()`.

Anyways, I've put my working version on trac at u/tscrim/15456. I also gave default implementations of has_left/right_descent() to weyl_group.py for speed. Although now that I've done the implementation, I'm less convinced of my suggestion. Perhaps what would be best is some category magic. We test upon creation of a Coxeter group to see if any of the methods have been implemented. Thus we do the following:

  • If has_descent() has been implemented, give default has_*_descent() call has_descent() with the appropriate args for those not implemented.
  • If none were implemented, error out on construction.
  • Otherwise set it up as we have it now.

Maybe this is heavy-handed?

Nevertheless, here are some timings. I'm using the example from the ticket description. Baseline:

sage: %timeit w.has_descent(3, side="left")
1000 loops, best of 3: 860 us per loop
sage: %timeit w.has_descent(3, side="left")
1000 loops, best of 3: 820 us per loop
sage: %timeit w.has_descent(3, side="right")
1000 loops, best of 3: 200 us per loop
sage: %timeit w.has_descent(3, side="right")
1000 loops, best of 3: 209 us per loop

With Frederic's branch:

sage: %timeit w.has_descent(3, side="left")
1000 loops, best of 3: 987 us per loop
sage: %timeit w.has_left_descent(3)
1000 loops, best of 3: 929 us per loop
sage: %timeit w.has_descent(3, side="right")
1000 loops, best of 3: 204 us per loop
sage: %timeit w.has_right_descent(3)
1000 loops, best of 3: 215 us per loop

With my branch:

sage: %timeit w.has_descent(3, side="left")
1000 loops, best of 3: 867 us per loop
sage: %timeit w.has_left_descent(3)
1000 loops, best of 3: 902 us per loop
sage: %timeit w.has_descent(3, side="right")
1000 loops, best of 3: 200 us per loop
sage: %timeit w.has_right_descent(3)
1000 loops, best of 3: 191 us per loop
Last edited 6 years ago by tscrim (previous) (diff)

comment:21 Changed 6 years ago by chapoton

So, what shall we do here ?

If I understand your proposal, when no has_something is implemented in an instance of Coxeter group, one has two different possibilities of infinite loop instead of one.

Supose now that I only implement has_left and that I call has_right. This will result in an infinite loop in your proposal, no ?

comment:22 Changed 6 years ago by tscrim

Ah, I made a correction in my implementation has_right(i) called (~self).has_descent(i, side='left').

I'm not so sure now what the best course of action is. From the above, having to create the inverse is slow (at least generically). I'm partially inclined to just implement has_left and has_right for Weyl groups which calls has_descent(i, side=*) to fix the problem at present. In any of the solutions except my initial one, I would think the speed should roughly be the same...

comment:23 Changed 6 years ago by chapoton

  • Keywords coxeter added

comment:24 Changed 5 years ago by git

  • Commit changed from bef966f7e6f1ce42da5578c8da4df8d5ebdf9f9b to c1deaa5708d0f9e08e02d24c8cb5a0a39328453b

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

c1deaa5Merge branch 'u/chapoton/15456' of ssh://trac.sagemath.org:22/sage into 15456

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

comment:26 Changed 5 years ago by git

  • Commit changed from c1deaa5708d0f9e08e02d24c8cb5a0a39328453b to 5922bda3f092d44b86b3a32b34b1d0a64834713c

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

5922bdaMerge branch 'u/chapoton/15456' of ssh://trac.sagemath.org:22/sage into 15456

comment:27 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:28 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:29 Changed 5 years ago by chapoton

  • Milestone changed from sage-6.4 to sage-6.5

comment:30 Changed 4 years ago by chapoton

  • Milestone changed from sage-6.5 to sage-6.7

comment:31 Changed 4 years ago by chapoton

  • Milestone changed from sage-6.7 to sage-6.8

comment:32 Changed 4 years ago by aschilling

  • Branch changed from u/chapoton/15456 to public/15456
  • Commit changed from 5922bda3f092d44b86b3a32b34b1d0a64834713c to 45ff0e370aea78c35197688d8983e9bfd1c00b51

New commits:

45ff0e3Merge branch 'develop' into u/chapoton/15456

comment:33 in reply to: ↑ 25 Changed 4 years ago by aschilling

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.

comment:34 Changed 4 years ago by zabrocki

  • Reviewers set to Anne Schilling, Mike Zabrocki
  • Status changed from needs_review to positive_review

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

comment:35 Changed 4 years ago by chapoton

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

This need to be checked, nevertheless.

comment:36 Changed 4 years ago by aschilling

  • Status changed from positive_review to needs_info

comment:37 Changed 4 years ago by aschilling

  • Milestone changed from sage-6.8 to sage-duplicate/invalid/wontfix

comment:38 Changed 4 years ago by zabrocki

  • Keywords sd65 added

comment:39 follow-up: Changed 4 years ago by chapoton

  • Status changed from needs_info to positive_review

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

comment:40 in reply to: ↑ 39 Changed 4 years ago by aschilling

Replying to chapoton:

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?

comment:41 Changed 4 years ago by chapoton

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

comment:42 Changed 4 years ago by vbraun

  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.