Opened 3 years ago

Closed 3 years ago

#21419 closed enhancement (fixed)

LatticePoset: "kappa function" and relations A-D

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-7.5
Component: combinatorics Keywords:
Cc: tscrim, chapoton Merged in:
Authors: Jori Mäntysalo Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 7c192cd (Commits) Commit: 7c192cd06f1a5f88dcee9b6662863956d470bb8e
Dependencies: Stopgaps:

Description

I would like to implement relations A-D from http://www.math.hawaii.edu/~jb/unbound.ps

It seems natural to first start from the function that is marked as greek letter kappa at the paper. Here I gave it just a name kappa().

Change History (25)

comment:1 Changed 3 years ago by jmantysalo

  • Branch set to u/jmantysalo/kappa

comment:2 Changed 3 years ago by jmantysalo

  • Commit set to bc21b06d68c34dbad5c0039bd99883501485d157
  • Status changed from new to needs_review

New commits:

bc21b06Add kappa function.

comment:3 Changed 3 years ago by jmantysalo

  • Cc tscrim added

Travis: What you think about the name of the function? Is there (at least) educational value of having a kappa-function also "visible", i.e. at lattices.py and not only indirectly available at hasse_diagram.py?

comment:4 follow-up: Changed 3 years ago by tscrim

From your description, this seems like it is not a standard notation/function (I don't actually know). So I feel it doesn't make sense to call it kappa and instead give it a slightly more descriptive name. Perhaps maximal_incomparable_element?

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

Replying to tscrim:

From your description, this seems like it is not a standard notation/function (I don't actually know). So I feel it doesn't make sense to call it kappa and instead give it a slightly more descriptive name. Perhaps maximal_incomparable_element?

That's good name!

By googling I found that Lattices and Ordered Sets by Steven Roman p. 225 uses the name "kappa function", but I can not see the page itself. The symbol itself seems to be coherently used for this, see Algebras and Orders by Ivo G. Rosenberg and Gert Sabidussi, or http://journals.cambridge.org/download.php?file=%2FJAZ%2FJAZ1_63_01%2FS1446788700000355a.pdf&code=9cc17eeb007fe5d050aadfcbedad50cd, but I did not found other mentions of "kappa function" spelled out.

Should I ask from J. B. Nation himself?

Last edited 3 years ago by jmantysalo (previous) (diff)

comment:6 Changed 3 years ago by tscrim

It's okay; some textbooks is good enough reference for me. I leave it up to you if you want to change the name.

comment:7 Changed 3 years ago by jmantysalo

  • Status changed from needs_review to needs_info

Hmm.. Hard to say. I left this open and think.

Name maximal_incomparable_element would suggest that function works for all elements in every poset, and it really could be defined so. But I have seen it only used for join-irreducibles.

comment:8 Changed 3 years ago by jmantysalo

  • Status changed from needs_info to needs_review

Back to needs_review. This can not be "maximal incomparable element", as that is not the case in special case where an element covers a doubly irreducible element; then \kappa(a)=a. Hence I can see no easy name for the function at all, except "kappa".

Now the question is should we have this available at "interface level", i.e. in lattices.py at all, or just hidden in hasse_diagram.py. Also, is it more clear to explicitly say in the documentation that this is the greatest incomparable elemenet excluding the special case?

comment:9 follow-up: Changed 3 years ago by jmantysalo

  • Cc chapoton added

CC'd Frédéric. What you think about the name, and should this be available at lattices.py?

I found a book that uses a section title "The $\kappa$ function". But to make this more complicated: there are also dual functions, i.e. "kappa'" defined for meet-irreducibles.

comment:10 Changed 3 years ago by jmantysalo

  • Status changed from needs_review to needs_work

Arghs, a braindead bug in special case handling.

comment:11 Changed 3 years ago by git

  • Commit changed from bc21b06d68c34dbad5c0039bd99883501485d157 to 3359c29fdc997a58ee0054918218f8502c8d8877

Branch pushed to git repo; I updated commit sha1. New commits:

3359c29A correction, modify docstring.

comment:12 Changed 3 years ago by jmantysalo

  • Status changed from needs_work to needs_review

comment:13 in reply to: ↑ 9 Changed 3 years ago by tscrim

Replying to jmantysalo:

I found a book that uses a section title "The $\kappa$ function". But to make this more complicated: there are also dual functions, i.e. "kappa'" defined for meet-irreducibles.

That tells me we need to change either the function title or arguments, and I'd rather change the title. I go back to maximal_incomparable_element, and as long as we document that it is only for join-irreducible elements (which includes an appropriate error message), it is okay.

comment:14 Changed 3 years ago by jmantysalo

If you take L = Poset({0:[1,2,3], 1:[4, 5], 2:[5], 3:[6], 4:[7], 5:[7], 6:[7]}) then kappa(4) is 5, but both 5 and 6 are maximal incomparables. Hence maximal_incomparable_element does not work.

Hard question... To compare: both meet- and join-semidistributive are used, and semidistributive means that a lattice is both. (Then there are join-distributive and meet-distributive...) OTOH semimodular usually means upper semimodular. And pseudocomplement is almost never said to be meet-pseudocomplement, but of course there is a possible dual notion of join-pseudocomplement.

comment:15 Changed 3 years ago by jmantysalo

J.B. Nation answered: "It seems that the 'kappa' notation is fairly widely used, but perhaps not enough to be called standard. It is useful though."

It is useful at least to check if a lattice is semidistributive or to compute canonical joinands. But to publish it on lattices.py or not to publish - that is the question.

comment:16 Changed 3 years ago by git

  • Commit changed from 3359c29fdc997a58ee0054918218f8502c8d8877 to 4893b877b57cf93df457cbaeb8f5e553fe9435da

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

4893b87Add kappa() to Hasse diagram.

comment:17 Changed 3 years ago by jmantysalo

No common view about adding this to user-visible namespace at lattices.py. Hence I suggest a modified version where this is only added to hasse_diagram.py.

(This will make is_[meet|join]_semidistributive() much faster.

comment:18 follow-up: Changed 3 years ago by kdilks

You need to change the *.next() to next(*) for Python3 compliance.

comment:19 Changed 3 years ago by git

  • Commit changed from 4893b877b57cf93df457cbaeb8f5e553fe9435da to 46c64ccf32bd4fc7d421239ccf41d3bb63576dad

Branch pushed to git repo; I updated commit sha1. New commits:

46c64ccnext() to py3 style.

comment:20 in reply to: ↑ 18 Changed 3 years ago by jmantysalo

Replying to kdilks:

You need to change the *.next() to next(*) for Python3 compliance.

True. Done that.

comment:21 follow-up: Changed 3 years ago by jmantysalo

  • Milestone changed from sage-7.4 to sage-7.5

OK? If not, OK if name changed to _kappa?

comment:22 in reply to: ↑ 21 Changed 3 years ago by jmantysalo

Replying to jmantysalo:

OK? If not, OK if name changed to _kappa?

Just pinging this question.

comment:23 follow-up: Changed 3 years ago by tscrim

  • Branch changed from u/jmantysalo/kappa to u/tscrim/kappa-21419
  • Commit changed from 46c64ccf32bd4fc7d421239ccf41d3bb63576dad to 7c192cd06f1a5f88dcee9b6662863956d470bb8e
  • Reviewers set to Travis Scrimshaw

I think kappa is fine. I reworked things slightly and improved the documentation. If my changes look good, then you can set a positive review. (From Sage's definition of join-irreducible, the 1 element lattice does not have any join-irreducible elements, and subsequently this case is not handled by your code, which is okay.)


New commits:

3846724Merge branch 'u/jmantysalo/kappa' of git://trac.sagemath.org/sage into u/tscrim/kappa-21419
7c192cdSome reviewer changes.

comment:24 in reply to: ↑ 23 Changed 3 years ago by jmantysalo

  • Status changed from needs_review to positive_review

Replying to tscrim:

I think kappa is fine. I reworked things slightly and improved the documentation. If my changes look good, then you can set a positive review. (From Sage's definition of join-irreducible, the 1 element lattice does not have any join-irreducible elements, and subsequently this case is not handled by your code, which is okay.)

Thanks (once again). This is good.

I must remember that one-element case when making code for semidistributivity.

comment:25 Changed 3 years ago by vbraun

  • Branch changed from u/tscrim/kappa-21419 to 7c192cd06f1a5f88dcee9b6662863956d470bb8e
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.