Opened 6 years ago

Closed 4 years ago

#12848 closed defect (fixed)

Bug in order_ideal_complement_generators: 'down'

Reported by: nthiery Owned by: sage-combinat
Priority: major Milestone: sage-5.11
Component: combinatorics Keywords: posets, days49
Cc: sage-combinat Merged in: sage-5.11.beta3
Authors: Nicolas M. Thiéry, Frédéric Chapoton Reviewers: Darij Grinberg, Anne Schilling
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by aschilling)

The down option is broken in order_ideal_complement_generators due to a glitch:

    sage: P = Poset( ( [1,2,3], [ [1,3], [2,3] ] ) )
    sage: sage: P.order_ideal_complement_generators([1,2], direction='up')
    set([3])
    sage: P.order_ideal_complement_generators([1,2], direction='down')
    set([3])

The result should be [] in the later case.

Upcoming patch on the Sage-Combinat queue

Apply:

trac_12848-posets-order_ideal_complement_generators_fix-nt-v2.patch trac_12848-posets-modifications.patch

Attachments (3)

Change History (32)

comment:1 follow-up: Changed 5 years ago by aschilling

I am looking at the patch on the sage-combinat queue. The method

+ def upper_set(self, elements, direction='up'): + if direction=='up': + return self.order_filter(elements) + else: + return self.order_ideal(elements)

is missing a doctest.

comment:2 in reply to: ↑ 1 Changed 5 years ago by nthiery

Replying to aschilling:

I am looking at the patch on the sage-combinat queue. The method

+ def upper_set(self, elements, direction='up'): + if direction=='up': + return self.order_filter(elements) + else: + return self.order_ideal(elements)

is missing a doctest.

Ah right. And we need to discuss the name for this method, and use it in order_ideal_complement_generators

comment:3 Changed 4 years ago by chapoton

could you please upload the patch here ?

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

Here is a modified patch, that should pass all tests and is fully documented.

There is an annoying issue with the names of the methods "upper_ideal", "lower_ideal", "order_ideal", "order_filter"

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

There is an annoying issue with the names of the methods "upper_ideal", "lower_ideal", "order_ideal", "order_filter"

What is the precise issue with the names?

Anne

comment:6 Changed 4 years ago by chapoton

Well, the issue is that of "order_ideal" is a synonym for "lower ideal" and "order_filter" is a synonym for "upper_ideal". Before this patch, everywhere one uses "order_ideal" and "order_filter". In my opinion, these are bad names, and "lower ideal" and "upper ideal" are much better.

And, well, I think that "upper set" and "lower set" are very bad too.

In any case, there is still some cleanup to do.

comment:7 Changed 4 years ago by chapoton

  • Status changed from new to needs_review

ok, here is a new patch, 100% doctest, should pass all tests.

In principle, it should not break anything anywhere.

comment:8 Changed 4 years ago by chapoton

  • Type changed from PLEASE CHANGE to defect

comment:9 Changed 4 years ago by chapoton

The bot has turned green, and the patch is ready for review !

comment:10 Changed 4 years ago by chapoton

anybody out there ? maybe it is ready to go ?

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

  • Authors changed from Nicolas M. Thiéry to Nicolas M. Thiéry, Frédéric Chapoton
  • Description modified (diff)

comment:12 in reply to: ↑ 11 Changed 4 years ago by aschilling

Replying to chapoton:

If you put the patch on the sage-combinat queue, I will review it!

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

done, the patch is in the queue..

comment:14 in reply to: ↑ 13 Changed 4 years ago by aschilling

Hi Frédéric,

Thank you for getting this patch ready for submission!

One small technical issue is that the header of the patch needs to start with #14828: ... description of the patch ... Could you change this?

I am not so happy about the naming conventions that you used. Could you please give me references that use order filter and order ideal? Why don't you like upper set and lower set? That seems like a standard name, see

http://en.wikipedia.org/wiki/Upper_set

Best,

Anne

comment:15 Changed 4 years ago by chapoton

Oh, I have not seen your answer, for some reason.

I will take care of the header question soon.

Concerning terminology, it seems that confusion is everywhere, see for instance

http://en.wikipedia.org/wiki/Order_ideal

saying "The terms order ideal, order filter, semi-ideal, down-set and decreasing subset are sometimes used for arbitrary lower or upper sets"

So far, in sage, we have the following definition (in P.order_ideal?)

I is an order ideal if, for any x in I and y such that y <= x, then y is in I.

So I have tried to stick at this convention and not to introduce two competing notations in sage. I do not like upper set and lower set because of the word set, which does not has the idea of closure. I do not like order ideal and order filter because I never remember which one is which. I would like to use upper ideal and lower ideal, but nobody seems to use that. This is rather boring.

comment:16 Changed 4 years ago by nthiery

Hi Frederic.

I agree that this naming thing is a pain; which is actually what stopped me from cleaning this earlier. Thanks for pushing it forward ...

order_ideal and order_filter are definitely bad for the reason you mention (which one is up, which one is down). So at least this is settled: we want to move away from those.

upper_set and lower_set has the advantage of being unambiguous and relatively clear (though I see your point about "closures"). So I would vote for this. But ... we also would want to be able to pass upper/lower as argument, and I agree that set(dir="up") really does not make sense :-) And upper_set(dir='down') is not great either.

I am really not keen with "ideal" because it has two conflicting meanings. But it's been in Sage for a while and we already do ideal(side="left/right") in rings/monoids, so ideal(dir="up/down") is consistent.

Would we have a nice method name for the other definition of ideal (e.g. a upper set such that any meet of two elements is also in it)?

Cheers,

Nicolas

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

The other definition of "order filter" is not quite that: it says "an upper set such that any two elements have a common lowest bound in the upper set"

It seems to imply (for finite posets) that it has a unique minimal element, and that this other definition could be called a "principal upper ideal" or "principal upper set".

There are subtle issues for infinite posets, but should we be concerned about that ?

comment:18 in reply to: ↑ 17 ; follow-up: Changed 4 years ago by nthiery

Replying to chapoton:

The other definition of "order filter" is not quite that: it says "an upper set such that any two elements have a common lowest bound in the upper set"

Oops, you are right; I formulated this to fast.

It seems to imply (for finite posets) that it has a unique minimal element, and that this other definition could be called a "principal upper ideal" or "principal upper set".

Indeed.

There are subtle issues for infinite posets, but should we be concerned about that ?

Not right now. But that will come! So it would be good to know that there exist a plan, even if we don't know right away which plan it should be.

comment:19 in reply to: ↑ 18 Changed 4 years ago by aschilling

upper ideal and lower ideal is ok with me if really nobody is using this with another meaning!

Anne

comment:20 Changed 4 years ago by chapoton

Here is new patch, with correct header.

I have chosen to do the following:

  • keep the names "order_ideal" and "order_filter" for backward compatibility
  • introduce "upper_set" and "lower_set" as aliases
  • use the names "ideal_of_subset" and "ideals_of_subsets" for generic cases

This is clearly not at all coherent. Should we try to reach coherence in this ticket, or should we rather use this ticket to solve the issue that has been raised ?

comment:21 Changed 4 years ago by darij

"Returns the order ideal in self generated by gens." Shouldn't that gens be elements now?

"generaly" generally

Last edited 4 years ago by darij (previous) (diff)

comment:22 Changed 4 years ago by darij

We (Tom, Emma, me) have a couple of suggestions on this patch (which we are working from). What do you think of them? Mainly it changes ideal_of_subset and ideals_of_subsets into directed_subset and directed_subsets, which IMHO are much less confusing (it's as much ideals as it's filters).

comment:23 Changed 4 years ago by chapoton

Yes, it is indeed a better name. I have no time right now to take part in the action, so please do what you want.

comment:24 Changed 4 years ago by chapoton

  • Status changed from needs_review to needs_work

please correct the failing doctests

Changed 4 years ago by darij

fixed. sorry!!

comment:25 Changed 4 years ago by aschilling

  • Description modified (diff)
  • Status changed from needs_work to needs_review

comment:26 Changed 4 years ago by aschilling

  • Keywords days49 added
  • Reviewers set to Darij Grinberg, Anne Schilling

comment:27 follow-up: Changed 4 years ago by aschilling

  • Status changed from needs_review to positive_review

comment:28 in reply to: ↑ 27 Changed 4 years ago by aschilling

Ok, looks good now and the tests pass!

Anne

comment:29 Changed 4 years ago by jdemeyer

  • Merged in set to sage-5.11.beta3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.