Initial support for posets

[Franco Saliola]

Dear all,

I've posted on trac the current version of my posets code.
There is still much to be done, some algorithms need
to be improved and others need to be implemented. (There
are no NotImplementedErrors.)

http://trac.sagemath.org/sage_trac/ticket/2519

But before I continue working, I'd like some feedback. I've
made some decisions, and I don't know if they are the
best decisions. So please offer suggestions.

I've defined a HasseDiagram class that inherits from
DiGraph. A Hasse diagram are transitively-reduced, directed,
acyclic graph without loops or multiple edges. NOTE: We
assume that range(n) is a linear extension of the Hasse
diagram. This decision was taken in the hopes that it
increases the efficiency of algorithms.

There is a FinitePoset class that stores the list of
elements of the poset (_elements), the HasseDiagram
(_hasse_diagram, or hasse_diagram()), and maps
_element_to_vertex and _vertex_to_element. So FinitePoset is
just a vertex labelling of the HasseDiagram.

There is a constructor called Poset that takes various forms
of data describing a finite poset and returns a FinitePoset
object.

There are also Lattice, MeetSemilattice, JoinSemilattice...,
and PosetElement, LatticeElement, .... So one create poset
elements and compare them with <, >, etc. And lattice
elements can by multiplied and added (for meet and join).

There are a few toy posets included (eventually there
should be a poset database): BooleanLattice, Chain,
Antichain, Pentagon, Diamond, PosetOfIntegerCompositions,
RandomPoset, SymmetricGroupBruhatOrder,
SymmetricGroupWeakOrder.

So what do you think?

Franco

--

[mhampton]

I'm not really qualified to comment in detail, but I thought I would
mention that I am interested in computing face lattices of polytopes
as part of my polytope module. Perhaps you could comment on whether
there is (or could be) anything in your code that might help me out
with that.

I think its exciting that we are getting more sage-native
functionality like this.

Cheers,
M. Hampton

[Robert Miller]

We might want to think about the naming conventions for Lattice. As
with all words in mathematics, this one has multiple meanings. A
lattice can be a poset with a meet and a join, or it can be a free
abelian group with an inner product. Normally I wouldn't bring such a
thing up, but I'm working with a group thinking about implementing the
latter, and you have already (it seems) implemented the former.

[Franco Saliola]

On Wed, Apr 23, 2008 at 3:48 PM, mhampton <hamp...@gmail.com> wrote:

> I'm not really qualified to comment in detail, but I thought I would
> mention that I am interested in computing face lattices of polytopes
> as part of my polytope module. Perhaps you could comment on whether
> there is (or could be) anything in your code that might help me out
> with that.

At the very least you can inherit from the Lattice and LatticeElement
classes. And use the plotting functionality.

Tell me what kind of things you want to be able to do, and if it is
missing, then I can add it. (For example, what kind of data you want
to hand me.)

I posted my code so that I find out how people intend to use it, so it
can be improved.

Take care,
Franco

--

[Franco Saliola]

On Wed, Apr 23, 2008 at 4:05 PM, Robert Miller <rlmil...@gmail.com> wrote:

> We might want to think about the naming conventions for Lattice. As
> with all words in mathematics, this one has multiple meanings. A
> lattice can be a poset with a meet and a join, or it can be a free
> abelian group with an inner product.

This is a good point. The only thing I can think of is to append
something: for example, LatticeGroup. I'm not sure how natural that
is. LatticePoset is definitely not. Other suggestions?

--

[John Cremona]

As someone who is much more likely to use the non-poset lattices, I
could certainly live with ZLattice (that's Z as in ZZ). Would either
side get to keep plain Lattice?

John

2008/4/23 Franco Saliola <sal...@gmail.com>:

[William Stein]

On Wed, Apr 23, 2008 at 1:42 PM, Franco Saliola <sal...@gmail.com> wrote:
>
> On Wed, Apr 23, 2008 at 4:05 PM, Robert Miller <rlmil...@gmail.com> wrote:
>
> > We might want to think about the naming conventions for Lattice. As
> > with all words in mathematics, this one has multiple meanings. A
> > lattice can be a poset with a meet and a join, or it can be a free
> > abelian group with an inner product.

I call dibs on Lattice being "free abelian group with an inner product".

:-)

>
> This is a good point. The only thing I can think of is to append
> something: for example, LatticeGroup. I'm not sure how natural that
> is. LatticePoset is definitely not. Other suggestions?
>
>
>
> --
>
> >
>

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

[John Cremona]

2008/4/24 William Stein <wst...@gmail.com>:

>
> On Wed, Apr 23, 2008 at 1:42 PM, Franco Saliola <sal...@gmail.com> wrote:
> >
> > On Wed, Apr 23, 2008 at 4:05 PM, Robert Miller <rlmil...@gmail.com> wrote:
> >
> > > We might want to think about the naming conventions for Lattice. As
> > > with all words in mathematics, this one has multiple meanings. A
> > > lattice can be a poset with a meet and a join, or it can be a free
> > > abelian group with an inner product.
>
> I call dibs on Lattice being "free abelian group with an inner product".

+1 --assuming that we can find a suitable name for the other kind!

John

[Simon King]

Hi!

I never understood why some people say "lattice" when they have a
"poset with meet and join"...

But i don't see the point: Would it really be difficult to live with
that name conflict?
I mean, certainly the two species of "lattice" would live in two
different packages, say (just for simplicity), in "group" and in
"poset".

Now, of course saying
sage: from sage.poset import lattice
sage: from sage.group import lattice
wouldn't work.

But if a user really wants to use both types of lattice in the same
program, he/she is free to say
sage: from sage.poset import lattice as lattice_po
sage: from sage.group import lattice as lattice_gr
and go ahead.

Or is it intended to have both types of lattice in sage without to
explicitly import them from the corresponding package?

Yours
Simon

[William Stein]

On Thu, Apr 24, 2008 at 4:27 AM, Simon King <ki...@mathematik.uni-jena.de> wrote:
>
> Hi!
>
> I never understood why some people say "lattice" when they have a
> "poset with meet and join"...

Same here. But they do and math terms are pretty arbitrary.

> But i don't see the point: Would it really be difficult to live with
> that name conflict?
> I mean, certainly the two species of "lattice" would live in two
> different packages, say (just for simplicity), in "group" and in
> "poset".
>
> Now, of course saying
> sage: from sage.poset import lattice
> sage: from sage.group import lattice
> wouldn't work.
>
> But if a user really wants to use both types of lattice in the same
> program, he/she is free to say
> sage: from sage.poset import lattice as lattice_po
> sage: from sage.group import lattice as lattice_gr
> and go ahead.
>
> Or is it intended to have both types of lattice in sage without to
> explicitly import them from the corresponding package?
>

Yes. We're only talking about the top-level global namespace.

William

[Simon King]

Hi William

On Apr 24, 2:21 pm, "William Stein" <wst...@gmail.com> wrote:
> > Or is it intended to have both types of lattice in sage without to
> > explicitly import them from the corresponding package?
>
> Yes. We're only talking about the top-level global namespace.

I wouldn't mind to have to load a package before having access to a
particular function, if it concerns a thing that is not ubiquitous in
math.

There is LatticeDiagram and LatticePolytope in Sage.
What do you think about LatticeGroup and LatticePoset?

Yours
Simon

[Franco Saliola]

On Thu, Apr 24, 2008 at 4:00 AM, John Cremona <john.c...@gmail.com> wrote:
>
> 2008/4/24 William Stein <wst...@gmail.com>:
>
> >
> > On Wed, Apr 23, 2008 at 1:42 PM, Franco Saliola <sal...@gmail.com> wrote:
> > >
> > > On Wed, Apr 23, 2008 at 4:05 PM, Robert Miller <rlmil...@gmail.com> wrote:
> > >
> > > > We might want to think about the naming conventions for Lattice. As
> > > > with all words in mathematics, this one has multiple meanings. A
> > > > lattice can be a poset with a meet and a join, or it can be a free
> > > > abelian group with an inner product.
> >
> > I call dibs on Lattice being "free abelian group with an inner product".
>
> +1 --assuming that we can find a suitable name for the other kind!

-1 --- I feel like I should champion the case for posets with meets
and joins. :-)

Franco

--

[Gabriel Dos Reis]

+1: Lattice as poset with meet and join
-1: Lattice as abelian group with inner product.

(of course I'm biaised by my French education and by what I'm working
on right now :-)

>
> Franco
>
> --
>
> >
>

[kcrisman]

The following references would seem relevant for what a "typical"
mathematician might think coming to Sage who isn't directly involved
in either kind of lattice on a daily basis, though it's not clear that
it resolves this discussion, since the authors below are self-
selecting. The idea that a "point" lattice (and hence Euclidean
lattice) is a special case of a "poset" lattice is interesting, though
I don't see how would that work for the cocompact definition or for
unordered fields...

- kcrisman

http://mathworld.wolfram.com/PointLattice.html
http://mathworld.wolfram.com/Lattice.html
http://en.wikipedia.org/wiki/Lattice_%28group%29
http://en.wikipedia.org/wiki/Lattice_%28order%29

[Oliver Wienand (TU Kaiserslautern, Singular Team)]

I made an implementation of a self designed algorithm to compute the
distribute lattice representing all linear extensions of a given
poset. It should be really fast and also gives you the number pretty
quickly.

If there is interest I can make it SAGE compatible, whatever this
means. It is already Python code.

See http://bio.math.berkeley.edu/ranktests/lcell/

Used to compute http://www.research.att.com/~njas/sequences/A046873

... Oliver

[David Roe]

+1: Lattice as abelian group with inner product.

-1: Lattice as poset with meet and join

(of course I'm biased by number theory, though I admit that I have
heard of the second kind of lattice. ;-)

That being said, I'm glad people are working on the poset kind of
lattice: I'd wanted to do so for a while, but too many other projects
intervened. I'll try to chip in a bit.

David

[root]

Axiom's "solution" to the lattice problem is to use an interpreter
for user interaction. Instead of just talking to a top level lisp
command prompt, you interact with the interpreter.

The interpreter looks at the arguments and classifies them by type.
It looks for "modemaps" that define the functions (e.g. all lattice
functions) and finds a minimum type matching modemap. The process
is repeated "working outward" for the final expression type.

Thus Axiom has some 10000 functions with approximately 3000 names
in the name space. The user can explicitly override this process
in various ways.

You might say lattice(args)$Posets to explictly override the
interpreter (although it will fail if the argument types don't
match).

Given the limits of naming conventions by various fields of math,
the interpreter provides a way to overload names in useful and
naturals ways. Thus a single function (say, map) can have multiple
well defined meanings (there are 80 map functions in Axiom).

In compiled code (Spad), you must specify exactly which function
of which domain you intend to call. If you're ambiguous about it,
the compiler gives you a suitably ambiguous error message.

Perhaps someone might give some thought to a Sage-interpreter
that helps in name resolution rather than having 80 people
try to define which "map" is the "correct" map.

Tim Daly

[William Stein]

Sage just uses the mainstream language Python; we are
not in the language design business. It's an interesting
exercise to think through how each of the ideas you generously
explained above is expressed using Python.

-- William

[David Harvey]

I guess we would just use Python namespaces for this.

For example, there might be two modules,
sage.groups.abelian_group.lattice and sage.combinat.lattice. Then you
would do something like

sage: from sage.groups.abelian_group.lattice import Lattice

or

sage: from sage.cominat.lattice import Lattice

depending on which Lattice you wanted to work with.

I think the debate going on in this thread is more about which is the
default one in the global namespace. I hate the global namespace, so
I'm not going to get involved :-)

david

[David Joyner]

I'll add my 2 cents, since I just read a post by William where he suggested he
might remove the command kernel, leaving left_kernel and right_kernel (and
I hope, adding kernel_left and kernel_right for tab completion).

I'm not strongly in favor of Lattice (alone) for either the poset or the
finite rank free ZZ-module. Just as UAT was thinking he might have found
a bug in "kernel", someone is going to post an analogous message about Lattice.
So, my vote is for LatticePoset and LatticeModule. (There is also a
object called
a lattice of groups, so LatticeGroup or LatticeAbelianGroup might be confusing).
If a use wants to shorten it in his local namespace he/she can more easily than
using an import startement. Also, LatticeWhatever allows one to use
tab completion to figure out
what one wants.

[William Stein]

On Thu, Apr 24, 2008 at 10:55 AM, David Joyner <wdjo...@gmail.com> wrote:
>
> I'll add my 2 cents, since I just read a post by William where he suggested he
> might remove the command kernel, leaving left_kernel and right_kernel (and
> I hope, adding kernel_left and kernel_right for tab completion).
>
> I'm not strongly in favor of Lattice (alone) for either the poset or the
> finite rank free ZZ-module. Just as UAT was thinking he might have found
> a bug in "kernel", someone is going to post an analogous message about Lattice.
> So, my vote is for LatticePoset and LatticeModule. (There is also a
> object called
> a lattice of groups, so LatticeGroup or LatticeAbelianGroup might be confusing).
> If a use wants to shorten it in his local namespace he/she can more easily than
> using an import startement. Also, LatticeWhatever allows one to use
> tab completion to figure out
> what one wants.

Another issue is that we *already* have a name for "finite rank free
ZZ-module with
inner product", namely "FreeModule". This has been in Sage for years.

sage: L = FreeModule(ZZ,2,inner_product_matrix=[[1,2],[2,4]])
sage: L.0.inner_product(L.1)
2

Choosing the names for the global namespace is a very important
responsibility, and each choice should be taken with a lot of taste
and care. It really does matter a great deal.

-- William

[root]

>Sage just uses the mainstream language Python; we are
>not in the language design business. It's an interesting
>exercise to think through how each of the ideas you generously
>explained above is expressed using Python.

This is a general purpose python idea, actually. If there was
a python function that looked at the namespace available for
each .py file then it could decide that there are two lattice
functions. This could issue an "import lattice from poset"
to disambiguate the lattice question automatically. (I have no
idea how you might look at a .py file and get its namespace).

This is not a new issue because Sage already has several different
polynomials available to it at any given time. The user has to
specify which one to call by naming the spkg tool explicitly.
Thus the various spkgs split the namespace at the moment.

As more functionality migrates from the external packages into
"Sage-native python" this issue will grow worse. Which package
gets to own the name "differentiate"? Axiom shows 25 different
functions of that name, e.g. polynomials vs power series.

Suppose the user wants to use the "same name" in the "same sentence"
(e.g. differentiate(poly)*differentiate(powerseries)). How is
this resolved? Does the user have to do special imports? How
will the user know that there are 50 differentiates from 7
different spkgs (25 from Axiom alone) and 6 from python packages?

It is an explicit design decision of the user interface to decide
whether there is an automatic resolution or a user-specified
resolution. It would be worthwhile to have a discussion of this
design decision before it gets "encoded by default" as a result
of the lattice discussion.

I don't think that Axiom's solution can work for Sage because
Axiom is a strongly typed language. But it does highlight at
least one other point in the space of design decisions.

Names matter.

Tim

[David Roe]

One thing that Python has going for it here is that it's object
oriented. So f.differentiate() is disambiguated because f has a type.

The time when this doesn't help is object creation (thus the issue for
Lattices). It's worth having this discussion, and I agree that names
matter, but the problem isn't quite as extensive as might be feared.
:-)
David

[Mike Hansen]

> This is a general purpose python idea, actually. If there was
> a python function that looked at the namespace available for
> each .py file then it could decide that there are two lattice
> functions. This could issue an "import lattice from poset"
> to disambiguate the lattice question automatically. (I have no
> idea how you might look at a .py file and get its namespace).

This seems like it has way too much guess-work for my liking. As
David Roe mentioned, this is handled pretty nicely by using an
object-oriented language. The only place this doesn't work is for the
initial creation of some objects. The discussion at hand is closer to
choosing the name ARRAY1 for Axioms's OneDimensionalArray instead of
something like ONEARRAY.

> I don't think that Axiom's solution can work for Sage because
> Axiom is a strongly typed language. But it does highlight at
> least one other point in the space of design decisions.

Python _is_ a strongly typed language. It is just dynamically typed
rather than statically typed.

--Mike

[Gabriel Dos Reis]

On Thu, Apr 24, 2008 at 3:00 PM, root <da...@axiom-developer.org> wrote:

>
> I don't think that Axiom's solution can work for Sage because
> Axiom is a strongly typed language. But it does highlight at
> least one other point in the space of design decisions.

`argument dependent name lookup' (which is what Axiom systems have
as language feature) is not just a trait of a statically typed language.
Given sufficient motivation, Python could be extended to make it
work. However, the way it works in Axiom systems is just half part
of the story. It works only one of the arguments has domain (or category)
that exports the operation. Meaning if you stick the operations in
a package, then you are hosed. :-( Which brings us to the fundamental
problem I raised in an previous message: Axiom systems want to insist
that a value belongs to a single domain (so that ADL, for example, can work),
when in fact that view is too restrictive and too limited.

Axiom systems have the strength that they are strongly typed; but their
computation models need to be deeply revised when they are intended to
be `solved' as solutions.

-- Gaby

[Nick Alexander]

> Suppose the user wants to use the "same name" in the "same sentence"
> (e.g. differentiate(poly)*differentiate(powerseries)). How is
> this resolved?

The pattern is to have differentiate(x) call x._differentiate_().

Nick