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

[tscrim]

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.

Depends on #21054 Depends on #21043

CC: @sagetrac-sage-combinat @nthiery @darijgr

Component: combinatorics

Keywords: poset

Author: Travis Scrimshaw

Branch/Commit: 56e4fb3

Reviewer: Darij Grinberg

Issue created by migration from https://trac.sagemath.org/ticket/21122

[tscrim]

comment:1

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

---

New commits:

322ea9c	Merge branch 'public/21043' of trac.sagemath.org:sage into public/combinat/moebius_algebra_triangularity-TBA
c09d3b0	Using a dedicated key class instead of non-facade posets.

[tscrim]

Commit: c09d3b0

[tscrim]

Branch: public/combinat/moebius_algebra_basis_keys-21122

[darijgr]

comment:2

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 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.)

• Do we know that whatever the module_morphism infrastructure does to key allows key to live in a poset? I see leading_item being called in https://github.com/sagemath/sage-prod/blob/develop/src/sage/modules/with_basis/morphism.py ; what does this return when there are several maximal items?

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c09d3b0 to 499bbe6

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

499bbe6

Addressing Darij's comments.

[tscrim]

comment:4

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.

[darijgr]

comment:5

?

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

[tscrim]

comment:6

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

[darijgr]

comment:7

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.

[tscrim]

comment:8

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?

[nthiery]

comment:9

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.

[darijgr]

comment:10

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?

@tscrim: 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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

872f3c0

Fixing pickleability for Moebius algebra morphisms.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 499bbe6 to 872f3c0

[tscrim]

comment:12

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.

[tscrim]

comment:13

Patchbot passes all tests as well. Positive review?

[darijgr]

comment:14

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

[tscrim]

Reviewer: Darij Grinberg

[tscrim]

comment:15

Ping, Nicolas?

[nthiery]

comment:16

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 872f3c0 to 56e4fb3

[tscrim]

comment:18

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.

[darijgr]

comment:19

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

[vbraun]

Changed branch from public/combinat/moebius_algebra_basis_keys-21122 to 56e4fb3