Bug in order_ideal_complement_generators: 'down'

[nthiery]

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

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

[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

[chapoton]

could you please upload the patch here ?

[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"

[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

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

[chapoton]

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

In principle, it should not break anything anywhere.

[chapoton]

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

[chapoton]

anybody out there ? maybe it is ready to go ?

[aschilling]

Replying to chapoton:

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

[chapoton]

done, the patch is in the queue..

[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

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

[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

[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 ?

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

[aschilling]

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

Anne

[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 ?