Opened 6 years ago

Closed 6 years ago

#21122 closed defect (fixed)

Do not force non-facade posets as the indexing set for the Möbuis algebra basis

Reported by: tscrim Owned by:
Priority: major Milestone: sage-7.3
Component: combinatorics Keywords: poset
Cc: sage-combinat, nthiery, darij Merged in:
Authors: Travis Scrimshaw Reviewers: Darij Grinberg
Report Upstream: N/A Work issues:
Branch: 56e4fb3 (Commits, GitHub, GitLab) Commit: 56e4fb38f47ee24a88a2752393cf2a0b16eead0b
Dependencies: #21054, #21043 Stopgaps:

Status badges


This can cause subtle bugs with comparisons between wrapped elements of a poset, which might not be given by the poset. We fix this and the triangularity issue that was hacked around in #21054, which introduced this problem.

See the discussion on #21054.

Change History (20)

comment:1 Changed 6 years ago by tscrim

  • Branch set to public/combinat/moebius_algebra_basis_keys-21122
  • Commit set to c09d3b086d3ba180743d7bc02ba150783ca76d4d
  • Status changed from new to needs_review

This is at least a much better solution than the hack I had to do on #21054.

New commits:

322ea9cMerge branch 'public/21043' of into public/combinat/moebius_algebra_triangularity-TBA
c09d3b0Using a dedicated key class instead of non-facade posets.

comment:2 Changed 6 years ago by darij

Great job! Two things, though:

  • I suggest replacing the doc of _Key by something more readable:
        Helper class to serve as a key for comparing elements of the
        The change-of-basis morphisms between the bases of the
        :class:`MoebiusAlgebra` are triangular with respect to the partial
        order of the poset. Since this partial order might not agree with
        the standard comparison function ``cmp``, we need a wrapper around
        the elements of the lattice which ensures that calling ``cmp`` on
        them (when wrapped) actually compares them using the lattice's
        partial order. This helper class is precisely that.

(You probably can do better.)

comment:3 Changed 6 years ago by git

  • Commit changed from c09d3b086d3ba180743d7bc02ba150783ca76d4d to 499bbe65ec6fd20546c15f815f2a40faf29eb972

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

499bbe6Addressing Darij's comments.

comment:4 Changed 6 years ago by tscrim

Thank you for looking at this.

I made that a lot shorter because (IMO) this class does not deserve any real documentation because it is hidden from the doc and never exposed to the user. You are only going to see this if you are looking at the code, but it is clear from the code what this class does. I feel it is just an implementation detail because of how we handle posets.

There is only one maximal element because the Möbius algebra is only defined for lattices.

comment:5 Changed 6 years ago by darij


I'm talking about leading terms of elements in the lattice algebra. Those can easily have multiple "leading" terms.

comment:6 Changed 6 years ago by tscrim

We don't care, it just does reduction and the triangularity guarantees the invertibility.

comment:7 Changed 6 years ago by darij

OK, I am still unconvinced of any guarantees, but that's probably the best I can do without knowing the module_morphism code (I'm not sure I ever did, for all the doc edits I made on that file). But in the worst case, it will just throw errors or endless-loop on methods which would otherwise just be not implemented; so there's no harm done here (and if there was, it would have been done by #21054, not by this ticket).

Sorry for my lack of faith in anything Sage lately... your code is good, that's not the issue.

comment:8 Changed 6 years ago by tscrim

It's okay, and skepticism is good. As I understand it, the triangular module morphism code will not throw errors or result in endless loops here because it is only used for computing the inverse, which uses the triangularity, something the theory guarantees. Can I count this as a positive review, or do you think we need more discussion?

comment:9 Changed 6 years ago by nthiery

See my comment on the previous ticket: maybe it's not needed to have a class for this. Well, maybe it is if we want the morphism to be picklable.

comment:10 Changed 6 years ago by darij

Oops, yes, I forgot to say: it's a positive review, if the tests pass.

@Nicolas: out of curiosity, why does a key class make morphisms picklable, but a custom cmp doesn't?

@Travis: it's also used for computing preimages, for example. Though, as I said, I'm fine with all sorts of bad behavior short of wrong results here, because these would be NotImplementedErrors? without the triangularity parameters.

Last edited 6 years ago by darij (previous) (diff)

comment:11 Changed 6 years ago by git

  • Commit changed from 499bbe65ec6fd20546c15f815f2a40faf29eb972 to 872f3c0e21ab0d8608257f980c7ce6867dbcca8b

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

872f3c0Fixing pickleability for Moebius algebra morphisms.

comment:12 Changed 6 years ago by tscrim

The reason why it doesn't pickle is because lambda functions don't pickle. I've fixed this by adding a method to the category. However, I have uncovered a very subtle bug with pickling of the module morphisms with cached methods, see #21133. All tests pass for me.

comment:13 Changed 6 years ago by tscrim

Patchbot passes all tests as well. Positive review?

comment:14 Changed 6 years ago by darij

As far as I'm concerned, yes, positive_review. Nicolas, any objections?

comment:15 Changed 6 years ago by tscrim

  • Reviewers set to Darij Grinberg

Ping, Nicolas?

comment:16 Changed 6 years ago by nthiery

Sorry, I am about to take off for vacations and was busy with preparation. I just had a look at the code. I believe the key function, should really just be an ranker according to the default linear extension. Luckily, I just remembered that we already had rankers as a picklable object:

sage: key = sage.combinat.ranker.rank_from_list(['a', 'b', 'c'])
sage: key('b')
sage: loads(dumps(key))
{'a': 0, 'c': 2, 'b': 1}
sage: key == loads(dumps(key))

comment:17 Changed 6 years ago by git

  • Commit changed from 872f3c0e21ab0d8608257f980c7ce6867dbcca8b to 56e4fb38f47ee24a88a2752393cf2a0b16eead0b

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

56e4fb3Using the Hasse diagram's promise that 0..n is a linear extension.

comment:18 Changed 6 years ago by tscrim

That actually gave me a good idea, where we can use data from the poset. In particular, we have _element_to_vertex and the promise that [1..n] is a linear extension of the HasseDiagram. Unfortunately using (the [marginally] faster) _element_to_vertex_dict.__getitem__ didn't want to unpickle. Anyways, this is a much better solution than what I had before.

comment:19 Changed 6 years ago by darij

  • Status changed from needs_review to positive_review

OOps, I completely forgot about this one! Yeah, you found the best possible solution. Great job!

comment:20 Changed 6 years ago by vbraun

  • Branch changed from public/combinat/moebius_algebra_basis_keys-21122 to 56e4fb38f47ee24a88a2752393cf2a0b16eead0b
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.