Opened 6 years ago
Closed 6 years ago
#21122 closed defect (fixed)
Do not force nonfacade posets as the indexing set for the Möbuis algebra basis
Reported by:  tscrim  Owned by:  

Priority:  major  Milestone:  sage7.3 
Component:  combinatorics  Keywords:  poset 
Cc:  sagecombinat, 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: 
Change History (20)
comment:1 Changed 6 years ago by
 Branch set to public/combinat/moebius_algebra_basis_keys21122
 Commit set to c09d3b086d3ba180743d7bc02ba150783ca76d4d
 Status changed from new to needs_review
comment:2 Changed 6 years ago by
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 lattice. The changeofbasis 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.)
 Do we know that whatever the
module_morphism
infrastructure does tokey
allowskey
to live in a poset? I seeleading_item
being called in https://github.com/sagemath/sage/blob/develop/src/sage/modules/with_basis/morphism.py ; what does this return when there are several maximal items?
comment:3 Changed 6 years ago by
 Commit changed from c09d3b086d3ba180743d7bc02ba150783ca76d4d to 499bbe65ec6fd20546c15f815f2a40faf29eb972
Branch pushed to git repo; I updated commit sha1. New commits:
499bbe6  Addressing Darij's comments.

comment:4 Changed 6 years ago by
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
?
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
We don't care, it just does reduction and the triangularity guarantees the invertibility.
comment:7 Changed 6 years ago by
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 endlessloop 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
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
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
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.
comment:11 Changed 6 years ago by
 Commit changed from 499bbe65ec6fd20546c15f815f2a40faf29eb972 to 872f3c0e21ab0d8608257f980c7ce6867dbcca8b
Branch pushed to git repo; I updated commit sha1. New commits:
872f3c0  Fixing pickleability for Moebius algebra morphisms.

comment:12 Changed 6 years ago by
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
Patchbot passes all tests as well. Positive review?
comment:14 Changed 6 years ago by
As far as I'm concerned, yes, positive_review. Nicolas, any objections?
comment:16 Changed 6 years ago by
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') 1 sage: loads(dumps(key)) {'a': 0, 'c': 2, 'b': 1} sage: key == loads(dumps(key)) True
comment:17 Changed 6 years ago by
 Commit changed from 872f3c0e21ab0d8608257f980c7ce6867dbcca8b to 56e4fb38f47ee24a88a2752393cf2a0b16eead0b
Branch pushed to git repo; I updated commit sha1. New commits:
56e4fb3  Using the Hasse diagram's promise that 0..n is a linear extension.

comment:18 Changed 6 years ago by
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
 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
 Branch changed from public/combinat/moebius_algebra_basis_keys21122 to 56e4fb38f47ee24a88a2752393cf2a0b16eead0b
 Resolution set to fixed
 Status changed from positive_review to closed
This is at least a much better solution than the hack I had to do on #21054.
New commits:
Merge branch 'public/21043' of trac.sagemath.org:sage into public/combinat/moebius_algebra_triangularityTBA
Using a dedicated key class instead of nonfacade posets.