Bug in order_ideal_complement_generators: 'down' #12848

nthiery · 2012-04-17T03:41:33Z

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:

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

CC: @sagetrac-sage-combinat

Component: combinatorics

Keywords: posets, days49

Author: Nicolas M. Thiéry, Frédéric Chapoton

Reviewer: Darij Grinberg, Anne Schilling

Merged: sage-5.11.beta3

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

The text was updated successfully, but these errors were encountered:

anneschilling · 2012-05-08T15:58:26Z

comment:1

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 · 2012-05-08T18:57:52Z

comment:2

Replying to @anneschilling:

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

fchapoton · 2013-04-29T16:02:26Z

comment:3

could you please upload the patch here ?

fchapoton · 2013-04-30T08:35:19Z

comment:4

Attachment: trac_12848-posets-order_ideal_complement_generators_fix-nt.patch.gz

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"

anneschilling · 2013-04-30T09:29:23Z

comment:5

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

fchapoton · 2013-04-30T11:02:59Z

comment:6

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.

fchapoton · 2013-04-30T11:58:50Z

comment:7

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

In principle, it should not break anything anywhere.

fchapoton · 2013-05-03T08:37:37Z

comment:9

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

fchapoton · 2013-05-10T20:31:55Z

comment:10

anybody out there ? maybe it is ready to go ?

fchapoton · 2013-05-10T20:33:46Z

Changed author from Nicolas M. Thiéry to Nicolas M. Thiéry, Frédéric Chapoton

anneschilling · 2013-05-10T20:37:45Z

comment:12

Replying to @fchapoton:

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

fchapoton · 2013-05-13T19:32:14Z

comment:13

done, the patch is in the queue..

anneschilling · 2013-05-14T02:11:56Z

comment:14

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

fchapoton · 2013-06-07T12:34:12Z

comment:15

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 · 2013-06-07T12:50:16Z

comment:16

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

fchapoton · 2013-06-07T14:20:56Z

comment:17

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 · 2013-06-07T14:45:31Z

comment:18

Replying to @fchapoton:

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.

anneschilling · 2013-06-07T18:06:44Z

comment:19

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

Anne

fchapoton · 2013-06-07T20:16:58Z

Attachment: trac_12848-posets-order_ideal_complement_generators_fix-nt-v2.patch.gz

fchapoton · 2013-06-07T20:22:53Z

comment:20

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 ?

darijgr · 2013-06-19T14:16:42Z

comment:21

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

"generaly" generally

darijgr · 2013-06-19T15:09:08Z

comment:22

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

fchapoton · 2013-06-19T15:21:57Z

comment:23

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.

fchapoton · 2013-06-19T19:12:44Z

comment:24

please correct the failing doctests

darijgr · 2013-06-19T19:31:22Z

fixed. sorry!!

anneschilling · 2013-06-19T20:17:18Z

comment:25

Attachment: trac_12848-posets-modifications.patch.gz

anneschilling · 2013-06-19T20:19:01Z

Reviewer: Darij Grinberg, Anne Schilling

anneschilling · 2013-06-19T20:19:01Z

Changed keywords from posets to posets, days49

anneschilling · 2013-06-19T20:34:37Z

comment:28

Ok, looks good now and the tests pass!

Anne

jdemeyer · 2013-06-20T21:35:45Z

Merged: sage-5.11.beta3

nthiery added this to the sage-5.11 milestone Apr 17, 2012

nthiery added c: combinatorics labels Apr 17, 2012

nthiery assigned sagetrac-sage-combinat Apr 17, 2012

fchapoton added s: needs review labels Apr 30, 2013

This comment has been minimized.

Sign in to view

fchapoton added s: needs work and removed s: needs review labels Jun 19, 2013

This comment has been minimized.

Sign in to view

anneschilling added s: needs review and removed s: needs work labels Jun 19, 2013

anneschilling added s: positive review and removed s: needs review labels Jun 19, 2013

jdemeyer removed the s: positive review label Jun 20, 2013

jdemeyer closed this as completed Jun 20, 2013

jessicapalencia mannequin mentioned this issue Aug 20, 2013

Implement toggle group actions on posets #14783

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Bug in order_ideal_complement_generators: 'down' #12848

Bug in order_ideal_complement_generators: 'down' #12848

nthiery commented Apr 17, 2012

anneschilling commented May 8, 2012

nthiery commented May 8, 2012

fchapoton commented Apr 29, 2013

fchapoton commented Apr 30, 2013

anneschilling commented Apr 30, 2013

fchapoton commented Apr 30, 2013

fchapoton commented Apr 30, 2013

fchapoton commented May 3, 2013

fchapoton commented May 10, 2013

This comment has been minimized.

fchapoton commented May 10, 2013

anneschilling commented May 10, 2013

fchapoton commented May 13, 2013

anneschilling commented May 14, 2013

fchapoton commented Jun 7, 2013

nthiery commented Jun 7, 2013

fchapoton commented Jun 7, 2013

nthiery commented Jun 7, 2013

anneschilling commented Jun 7, 2013

fchapoton commented Jun 7, 2013

fchapoton commented Jun 7, 2013

darijgr commented Jun 19, 2013

darijgr commented Jun 19, 2013

fchapoton commented Jun 19, 2013

fchapoton commented Jun 19, 2013

darijgr commented Jun 19, 2013

anneschilling commented Jun 19, 2013

This comment has been minimized.

anneschilling commented Jun 19, 2013

anneschilling commented Jun 19, 2013

anneschilling commented Jun 19, 2013

jdemeyer commented Jun 20, 2013

Bug in order_ideal_complement_generators: 'down' #12848

Bug in order_ideal_complement_generators: 'down' #12848

Comments

nthiery commented Apr 17, 2012

anneschilling commented May 8, 2012

nthiery commented May 8, 2012

fchapoton commented Apr 29, 2013

fchapoton commented Apr 30, 2013

anneschilling commented Apr 30, 2013

fchapoton commented Apr 30, 2013

fchapoton commented Apr 30, 2013

fchapoton commented May 3, 2013

fchapoton commented May 10, 2013

This comment has been minimized.

fchapoton commented May 10, 2013

anneschilling commented May 10, 2013

fchapoton commented May 13, 2013

anneschilling commented May 14, 2013

fchapoton commented Jun 7, 2013

nthiery commented Jun 7, 2013

fchapoton commented Jun 7, 2013

nthiery commented Jun 7, 2013

anneschilling commented Jun 7, 2013

fchapoton commented Jun 7, 2013

fchapoton commented Jun 7, 2013

darijgr commented Jun 19, 2013

darijgr commented Jun 19, 2013

fchapoton commented Jun 19, 2013

fchapoton commented Jun 19, 2013

darijgr commented Jun 19, 2013

anneschilling commented Jun 19, 2013

This comment has been minimized.

anneschilling commented Jun 19, 2013

anneschilling commented Jun 19, 2013

anneschilling commented Jun 19, 2013

jdemeyer commented Jun 20, 2013