Poset/lattice, join and join_matrix

[Jori Mantysalo]

1) Why is join() defined for join-semilattices, but join_matrix()
"defined" for posets? (I.e. it works by giving exception if the poset is
not join-semilattice.)

2) Would it be useful to have join() function taking more than two
arguments? And if so, should then also L.join(x) return x if x in L, and
maybe even L.join() return L.top()? Or could join take a list as argument,
so that both L.join(x,y) and L.join([x,y]) would work and latter one be
possible to extend to L.join([x,y,z,...])?

3) s/join/meet for questions 1 and 2.

--
Jori Mäntysalo

[Nathann Cohen]

Yo !

1) Why is join() defined for join-semilattices, but join_matrix()
"defined" for posets? (I.e. it works by giving exception if the poset is
not join-semilattice.)

Hmmmm...

1) I do not know why it is made like that, and I do not like the design

2) After several cycles of "a) answer question b) think c) erase the answer", I have a question: given a Poset, how can you detect if this poset is a meet semilattice ? For sure we need a function for that ! And it seems that this function is exactly what join_matrix does.

Then, how should it be implemented ?

My way of doing that (what would yours be?) to:

1) Have a FinitePoset.is_meet_semilattice() function that would try to build that matrix and answer yes/no accordingly. The matrix, when built, would be cached somewhere.

2) Move Poset.join_matrix() to FiniteMeetSemiLattice 

The good thing is that if you:

a) Build a Poset

b) Notice it is a MeetSemiLattice by calling .is_meet_semilattice (which builds the matrix)

c) Build the MeetSemiLattice from the poset

Then step c should not re-build the matrix as the matrix is currently a lazy attribute of the hasse diagram, which has no reason to be changed by those commands.

2) Would it be useful to have join() function taking more than two
arguments? And if so, should then also L.join(x) return x if x in L, and
maybe even L.join() return L.top()? Or could join take a list as argument,
so that both L.join(x,y) and L.join([x,y]) would work and latter one be
possible to extend to L.join([x,y,z,...])?

+1

3) s/join/meet for questions 1 and 2.

That does not make any sense. You might want to try s/join/meet/g.

Nathann

[Jori Mantysalo]

On Wed, 22 Oct 2014, Nathann Cohen wrote:

> given a Poset, how can you detect if this poset is a meet semilattice ?
> For sure we need a function for that ! And it seems that this function
> is exactly what join_matrix does.

Of course one can try to build a [semi]lattice and see if it works or not.
But is there some faster way? For a distributive lattice there is, see
http://www.lirmm.fr/~nourine/Papiers/dist-recognition.ps . It links to
http://download.springer.com/static/pdf/172/chp%253A10.1007%252F3-540-10854-8_14.pdf?auth66=1414046623_37fe0879bd09fb6dd923acdc2237f214&ext=.pdf
which says that detecting if a poset is lattice can be done on O(n^2.5).

> My way of doing that (what would yours be?) to:
> 1) Have a FinitePoset.is_meet_semilattice() function that would try to
> build that matrix and answer yes/no accordingly. The matrix, when built,
> would be cached somewhere.
> 2) Move Poset.join_matrix() to FiniteMeetSemiLattice 
>
> The good thing is that if you:
> a) Build a Poset
> b) Notice it is a MeetSemiLattice by calling .is_meet_semilattice (which
> builds the matrix)
> c) Build the MeetSemiLattice from the poset
>
> Then step c should not re-build the matrix as the matrix is currently a
> lazy attribute of the hasse diagram, which has no reason to be changed
> by those commands.

Yes. This way user can say somewhat more naturally

if P.is_lattice(): LatticePoset(P).do_something()

and not

try: L=LatticePoset(P)... except...

> 2) Would it be useful to have join() function taking more than two
> arguments? And if so, should then also L.join(x) return x if x in L, and
> maybe even L.join() return L.top()? Or could join take a list as argument,
> so that both L.join(x,y) and L.join([x,y]) would work and latter one be
> possible to extend to L.join([x,y,z,...])?
>
>
> +1

Ok. To have join(a,b,c,...) or join([a,b,c,...])?

--
Jori Mäntysalo

[Nathann Cohen]

Hello !

> which says that detecting if a poset is lattice can be done on O(n^2.5).

Oh. Cool.

> Ok. To have join(a,b,c,...) or join([a,b,c,...])?

Hmmm.. Well, we can have both at the same time. Something like that
should do the trick:

def join(elements, *args):
if args:
args.append(elements)
elements=args
elif elements in self:
elements=[elements]

Nathann

[Jori Mantysalo]

On Thu, 23 Oct 2014, Nathann Cohen wrote:

>> which says that detecting if a poset is lattice can be done on O(n^2.5).
>
> Oh. Cool.

Now somebody should just read, understand and implement it. :=)

>> Ok. To have join(a,b,c,...) or join([a,b,c,...])?
>
> Hmmm.. Well, we can have both at the same time.

True, but is it good for user perspective to have two ways to same end?

--
Jori Mäntysalo

[Nathann Cohen]

Hello !

> True, but is it good for user perspective to have two ways to same end?

When there is no risk of confusion I do not think that it is bad. Here
the only risk of confusion is the following:

P.join( ( (1,2), (3,4) ) )

In a poset that contains elements named (1,2), (3,4), as well as
((1,2),(3,4)). Not that there is no problem if the user types P.join(
[ (1,2), (3,4) ] ) instead.

It really is not a problem either to only have this P.join(a_list) available....

Nathann

[Jori Mantysalo]

On Thu, 23 Oct 2014, Nathann Cohen wrote:

> It really is not a problem either to only have this P.join(a_list) available....

And it can always be later expanded to accept also another kind of args.

Btw, I noticed that there kind of is a function for this already: sum().
But not that easy to use.

L=Posets.BooleanLattice(4)
L=LatticePoset(L, facade=False)
print sum([L(1), L(2), L(4)], L.bottom())

(Grr, facade-argument available for some but not all example posets.)

--
Jori Mäntysalo

[Erik Massop]

On Thu, 23 Oct 2014 10:38:53 +0200
Nathann Cohen <nathan...@gmail.com> wrote:

> > Ok. To have join(a,b,c,...) or join([a,b,c,...])?
>
> Hmmm.. Well, we can have both at the same time. Something like that
> should do the trick:
>
> def join(elements, *args):
> if args:
> args.append(elements)
> elements=args
> elif elements in self:
> elements=[elements]

I would personally prefer the following over the above:

def foo(*args):
if len(args) == 1:
elements = args[0]
else:
elements = args
... do stuff with elements ...

This way you can see which case will be used by just looking at the
number of arguments and without arguing about the contents of your
variables.

Also "join" above would throw an exception when a list or other
unhashable iterable is used as the only argument:

sage: P = Poset()
sage: [1,2] in P
TypeError: unhashable type: 'list'

Also, suppose that I build a poset with elements zero = (), one =
(zero,), and two = (zero,one). Then join([zero,one]) and
join((zero,one)) would be different, namely with elements=[zero,one] and
elements=[two], even though as iterables [one,two] and (one,two) are the
same.


Regards,

Erik Massop

[Nathann Cohen]

> I would personally prefer the following over the above:
>
> def foo(*args):
> if len(args) == 1:
> elements = args[0]
> else:
> elements = args
> ... do stuff with elements ...

You should test if "args in self" first. If your poset contains an
element named E=(x,y) and you want to compute join( E ) (which should
return E) then you raise an exception.

Nathann

[Martin R]

 this reminds me of the discussion about Permutation((1,2,3)) and Permutation([2,3,1]).  Of course, the situation is a bit different there, but my feeling is that it's usually better to have only one syntax.

Martin

[Nathann Cohen]

> this reminds me of the discussion about Permutation((1,2,3)) and
> Permutation([2,3,1]). Of course, the situation is a bit different there,
> but my feeling is that it's usually better to have only one syntax.

Precisely, though the risk of misunderstanding is slightly reduced.

Nathann

[Erik Massop]

I disagree.

If you want to obtain the join of a single element E, you can use
foo([E]), foo((E,)), or foo({E}), or any iterable that contains just E.
This works even if such an iterable is an element of the poset.

Anyway, the join of a single element is not very useful (since it is the
element itself). Hence using the one-argument version of the function
for iterables seems quite innocent an abuse to me.

Without "args in self" things are just simpler. If you give one
argument, you know that it will be interpreted as an iterable of
elements. If you give some other number of arguments, you know that
these arguments will be interpreted as elements. You don't need to
know anything about the actual elements of the poset to figure out what
what will happen.

Finally there is a bug when you add "args in self": Suppose that have
added "args in self" and called the new function foo'. Suppose
furthermore that you have a (facade) poset with elements x, y, and
E=(x,y). Now foo'(x,y) has args==(x,y)==E and therefore returns E
regardless of the order in the poset, which is not what is wanted from
foo'(x,y).


Regards,

Erik Massop

[Nathann Cohen]

Yo !

>> You should test if "args in self" first. If your poset contains an
>> element named E=(x,y) and you want to compute join( E ) (which should
>> return E) then you raise an exception.
>
> I disagree.
>
> If you want to obtain the join of a single element E, you can use
> foo([E]), foo((E,)), or foo({E}), or any iterable that contains just E.
> This works even if such an iterable is an element of the poset.

To be honest I do not care much about the join(a,b,c) syntax. Jori asked about that, and he also wanted the function to work with empty lists, one-element lists, and arbitrarily long lists.

I believe that supporting empty sets and sets of cardinality 1 has its value. If supporting both join([a,b,c]) and join(a,b,c) is going to start another war, no problem for me --> let's only support join([a,b,c])

I would be glad to see the same kind of fighting spirit when we talk of "Permutation":

sage: Permutation((1,2,3))(1)
2
sage: Permutation([1,2,3])(1)
1

That's way more dangerous than the slight inconsistency that could happen (only when using join(a,b,c) *and not join([a,b,c])*) on some poset with very specific elements.

> Without "args in self" things are just simpler. If you give one
> argument, you know that it will be interpreted as an iterable of
> elements. If you give some other number of arguments, you know that
> these arguments will be interpreted as elements.

Hmmm... There I really believe that the syntax with a set of size 1 should be allowed. This is exactly what "gcd" does, and its role is precisely to compute the join of elements in a specific poset:

sage: gcd([5])
5
sage: gcd([5,7])
1

It may be useful if some applications I guess. And join([]), too.

> Finally there is a bug when you add "args in self": Suppose that have
> added "args in self" and called the new function foo'. Suppose
> furthermore that you have a (facade) poset with elements x, y, and
> E=(x,y). Now foo'(x,y) has args==(x,y)==E and therefore returns E
> regardless of the order in the poset, which is not what is wanted from
> foo'(x,y).

Indeed, indeed, this is where the possible inconsistency is. If you think that is a problem let's only keep join([....]).

Nathann

[Jori Mantysalo]

On Thu, 23 Oct 2014, Nathann Cohen wrote:

> sage: gcd([5])
> 5
> sage: gcd([5,7])
> 1

This is good argument to support (only) []-style argument for several
elements. Be consistent within same program. Or in Sage terms, "Build a
car, don't let it look like bicycle combined to tractor." :=)

Btw, why gcd([]) returns zero? At least there is inconsistency with
lcm([]) returning one. I guess they should both return one or raise an
exception.

--
Jori Mäntysalo

[Nathann Cohen]

Yo !

> This is good argument to support (only) []-style argument for several
> elements. Be consistent within same program. Or in Sage terms, "Build a car,
> don't let it look like bicycle combined to tractor." :=)
>
> Btw, why gcd([]) returns zero? At least there is inconsistency with lcm([])
> returning one. I guess they should both return one or raise an exception.

I would say that it is because for guys doing number theory Z/2Z is
associated with 2 and Z is associated with 0. Think of 0 like the
infinity, or the product of all integers.

Nathann

[John Cremona]

On 27 October 2014 12:37, Nathann Cohen <nathan...@gmail.com> wrote:
> Yo !
>
>> This is good argument to support (only) []-style argument for several
>> elements. Be consistent within same program. Or in Sage terms, "Build a car,
>> don't let it look like bicycle combined to tractor." :=)
>>
>> Btw, why gcd([]) returns zero? At least there is inconsistency with lcm([])
>> returning one. I guess they should both return one or raise an exception.
>

It is not inconsistent, any more than this is:

sage: sum([])
0
sage: prod([])
1

and the reason is essentially the same.

> I would say that it is because for guys doing number theory Z/2Z is
> associated with 2 and Z is associated with 0. Think of 0 like the
> infinity, or the product of all integers.

I don't quite follow that but as a number theorist here is how I would
explain it. If you write a loop to read in integers and output their
sum, you just add each new one to the runing total, after initializing
this total to: 0

Same but for products: you have to initialize to 1.

Same but for gcd: each updated result is the gcd of the running
"total" and the new input. Must be initialised to: 0.

Same for lcm: each time you take the lcm with the new input. To get
the right answer you must initialize to: 1.

In every vase this tells you what f([]) should be!

John

>
> Nathann
>
> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

[Samuel Lelievre]

Here is how I would put it:

- sum([]) is zero because
  zero is the identity element for addition
  (for any x, the sum 0 + x equals x),
  therefore you can initialize a sum to 0,
  then add summands one by one,
  and this gets you the sum;
  so an empty sum is just the initial 0.

- prod([]) is one because
  one is the identity element for multiplication
  (for any x, the product 1*x equals x);
  therefore you can initialize a product to 1,
  then multiply by the multiplicands one by one,
  and this gets you the product;
  so an empty product is just the initial 1.

- gcd([]) is zero because
  zero is the identity element for gcd
  (for any x, gcd(0,x) equals x);
  therefore you can initialize a gcd to 0,
  then take gcd with the list elements one by one,
  and this gets you the gcd;
  so an empty gcd is just the initial 0.

- lcm([]) is one because
  one is the identity element for lcm
  (for any x, lcm(1,x) equals x);
  therefore you can initialize an lcm to 1,
  then take lcm with the list elements one by one,
  and this gets you the lcm;
  so an empty lcm is just the initial 1.

[Jori Mantysalo]

On Mon, 27 Oct 2014, Samuel Lelievre wrote:

> Here is how I would put it:

> - gcd([]) is zero because
>   zero is the identity element for gcd
>   (for any x, gcd(0,x) equals x);

Understood. Thanks.

--
Jori Mäntysalo

[William Stein]

On Mon, Oct 27, 2014 at 5:55 AM, John Cremona <john.c...@gmail.com> wrote:
> On 27 October 2014 12:37, Nathann Cohen <nathan...@gmail.com> wrote:
>> Yo !
>>
>>> This is good argument to support (only) []-style argument for several
>>> elements. Be consistent within same program. Or in Sage terms, "Build a car,
>>> don't let it look like bicycle combined to tractor." :=)
>>>
>>> Btw, why gcd([]) returns zero? At least there is inconsistency with lcm([])
>>> returning one. I guess they should both return one or raise an exception.
>>
>
> It is not inconsistent, any more than this is:
>
> sage: sum([])
> 0
> sage: prod([])
> 1
>
> and the reason is essentially the same.
>
>> I would say that it is because for guys doing number theory Z/2Z is
>> associated with 2 and Z is associated with 0. Think of 0 like the
>> infinity, or the product of all integers.
>
> I don't quite follow that but as a number theorist here is how I would
> explain it. If you write a loop to read in integers and output their
> sum, you just add each new one to the runing total, after initializing
> this total to: 0
>
> Same but for products: you have to initialize to 1.
>
> Same but for gcd: each updated result is the gcd of the running
> "total" and the new input. Must be initialised to: 0.

Here's another number theorist's perspective. I think of the gcd(X)
as a canonical generator for the ideal generated by X, when defined.
The ideal generated by a set X is the smallest ideal that contains it.
In case X is the empty set, that ideal is the 0 ideal (not the unit
ideal).

-- William

--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org

[Samuel Lelievre]

By coincidence I just found that the function GCD_list
in sage.rings.integer was coded to return one for an
empty list.

Fix (needs review!) at

    http://trac.sagemath.org/ticket/17257

Samuel