#21054 closed defect (fixed)
Transition between bases is incorrect for Moebius algebras
Reported by:  jmantysalo  Owned by:  

Priority:  critical  Milestone:  sage7.3 
Component:  combinatorics  Keywords:  
Cc:  tscrim, nthiery, darij  Merged in:  
Authors:  Travis Scrimshaw  Reviewers:  Darij Grinberg 
Report Upstream:  N/A  Work issues:  
Branch:  6515b25 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
The multiplication in the Möbius algebra is defined using the join, whereas the transition matrices between the natural and idempotent bases are given using the meet.
sage: M = posets.BooleanLattice(4).moebius_algebra(QQ) sage: I = M.I() sage: E = M.E() sage: I.one() * E.an_element() == E.an_element() True sage: E.an_element() * I.one() == E.an_element() False sage: E.one() E[0] sage: I.one() I[0] + I[1] + I[2] + I[3] + I[4] + I[5] + I[6] + I[7] + I[8] + I[9] + I[10] + I[11] + I[12] + I[13] + I[14] + I[15] sage: E(I.one()) E[15] sage: I(E.one()) I[0] sage: E.an_element() * E(I.one()) 7*E[15]
We fix the transition matrix to use the join (the dual version of what is given in the references).
Change History (33)
comment:1 Changed 6 years ago by
 Cc nthiery darij added
comment:2 Changed 6 years ago by
 Branch set to public/combinat/fix_moebius_algebra_multiplication21054
 Commit set to 19db2a232e6471c536d0035b06d7a1beffaf63d1
 Description modified (diff)
 Status changed from new to needs_review
 Summary changed from Random test failure in moebius_algebra.py to Transition between bases is incorrect for Moebius algebras
comment:3 Changed 6 years ago by
The changes look good, except for one thing: Why do you use triangular='upper'
in the normal Möbius algebra, and triangular='lower'
in the quantum one? Maybe this needs to be changed too? Also, does Sage understand what order relation this triangularity refers to? (My knowledge of the modules framework is a bit rusted, so I don't remember the exact semantics of the triangular
keyword.)
comment:4 Changed 6 years ago by
 Commit changed from 19db2a232e6471c536d0035b06d7a1beffaf63d1 to e5e590392fcd641b3aa7946c63bc27a6ed5fbfd9
Branch pushed to git repo; I updated commit sha1. New commits:
e5e5903  Changing upper to lower due to transition matrix change.

comment:5 Changed 6 years ago by
 Description modified (diff)
 Reviewers set to Darij Grinberg
Good catch. The triangularity changed because of the change in transition maps.
comment:6 Changed 6 years ago by
Also, the order relations come from the basis index set.
comment:7 followup: ↓ 8 Changed 6 years ago by
So module_morphism
is smart enough to compare basis indices using something like index_set.le
instead of _cmp_
?
In this case, and if the tests pass, that's a positive review. Thanks for the fix, and sorry for my inactivity! (This fall I'll hopefully have both more time and a better laptop to work on Sage, plus your live support...)
comment:8 in reply to: ↑ 7 Changed 6 years ago by
Replying to darij:
So
module_morphism
is smart enough to compare basis indices using something likeindex_set.le
instead of_cmp_
?
Not exactly, but we are moving away from _cmp_
altogether (#21043 to Python3). So there might be a problem with a facade poset whose elements have a partial ordering which is not compatible with the poset's ordering. Although the triangularity part is somewhat moot because we have an explicit description of both transition maps.
In this case, and if the tests pass, that's a positive review.
All tests pass for me, so if you agree with the above, then please set a positive review.
Thanks for the fix, and sorry for my inactivity! (This fall I'll hopefully have both more time and a better laptop to work on Sage, plus your live support...)
Thanks for looking at this. I know you've got a lot on your plate moving out to UMN, and it will be great to have you here.
comment:9 Changed 6 years ago by
Oh; can we remove the "explicit" triangularity then? What is it used for, beyond computing inverses?
comment:10 Changed 6 years ago by
However, it is (uni)triangular, and AFAIK, it currently is only used in the inverses. It is an issue (and separate from this ticket) only if someone does something more perverse, but someone might want to take the inverse of the coerce map independently.
comment:11 Changed 6 years ago by
Can I consider this as a positive review?
comment:12 Changed 6 years ago by
I don't know, sorry. nthiery, can you weigh in? This abuts to infrastructure again, and that's out of my comfort zone...
comment:13 Changed 6 years ago by
(I guess the main question here is: When we define several bases of a modulewithrealizations, then can we regard the transition maps as internal attributes, or should we consider them as being exposed to the user? In the latter case, we cannot afford breaking things like preimage
; in the former it doesn't matter.)
(For quick reference: https://github.com/sagemath/sage/blob/develop/src/sage/modules/with_basis/morphism.py )
comment:14 Changed 6 years ago by
 Priority changed from major to critical
They are indirectly exposed to the user through coerce_map_from
. However, it is (mathematically) correct that they are triangular wrt the poset order. It just might happen that someone gives a very horrible poset that is a facade. However, that is an independent issue than what is fixed here, which really should get into 7.3 because it gives wrong answers, so it belongs on a separate ticket.
comment:15 Changed 6 years ago by
Well, one of the examples is a horrible poset that is a facade:
sage: L = posets.BooleanLattice(4) sage: L[3] < L[5] True sage: L.le(L[3],L[5]) False
IMHO, we should just remove the triangular
and unitriangular
keywords. It's not like the code is losing anything, is it?
comment:16 Changed 6 years ago by
No, that is not a horrible poset (which I realize my comment is far to curt) because the natural order is compatible with the partial order. It does lose some mathematical significance, plus any additional code we might add in the future that uses the triangularity.
comment:17 Changed 6 years ago by
Perhaps one simple way out is to make the poset indexing the basis a nonfacade all the time. This would avoid any incompatibility of the orders, but it might introduce other subtle issues that could take time to debug.
comment:18 Changed 6 years ago by
If any additional code we might add uses triangularity, then this subtle point about facades suddenly becomes a bug. Yes, I know that the above poset has a naturally ordered linear extension, but there's nothing that guarantees the same for user input. If I had my virtual machine at arm's reach, I would fire it up, remove those two lines and check that the speed does not regress; unfortunately, right now I don't. Could you?
This is not to blame any of your work on this ticket! It's just another problem caused by delayed decisions and a lack of standards. Long ago we (the Sage developers) should have figured out what "the usual comparison function on J
" is supposed to mean in TriangularModuleMorphism
. But we didn't, and now we've got an implementation of triangularity that is easier to avoid than to use properly.
comment:19 Changed 6 years ago by
I'm just going to do what I said in comment:17. It fixes the issues with facade elements and makes the triangular stuff work. Will post code shortly.
comment:20 Changed 6 years ago by
 Commit changed from e5e590392fcd641b3aa7946c63bc27a6ed5fbfd9 to 6515b25a563903e32045b717f36bbed6e1aba176
comment:21 Changed 6 years ago by
This should take care of the issues, and it doesn't have any overt problems.
comment:22 Changed 6 years ago by
LGTM now, thanks!
comment:23 Changed 6 years ago by
 Status changed from needs_review to positive_review
comment:24 Changed 6 years ago by
Thank you! (See you in about a month.)
comment:25 Changed 6 years ago by
Hi Travis and Darij!
Sorry for jumping in that late.
I also tend to see the coercion morphisms as being exposed, since, as
mentioned, the user can recover them through coerce_map_from
. So it
would be indeed better to keep the triangularity feature.
I am uncomfortable with converting the poset to a non facade: this forces users to do conversions whenever accessing the basis indices. This can be painful and may lead to subtle bugs if the user does not notice that the lattice was changed to non facades.
Instead we would want the term ordering to be computed through P
(e.g. through P.le
). I did not follow the details, but in case this
is easier to implement once some other ticket will be merged, I guess
the current workaround can be ok.
I let you decide how to proceed!
Cheers,
Nicolas
comment:26 Changed 6 years ago by
Thanks, Nicolas  but I think this is precisely the one combination of decisions that does *not* work. We cannot have all three:
 exposed coerce maps,
 triangularity being explicitly guaranteed in the coerce maps,
 the poset being left as is as opposed to being converted to nonfacade.
Because triangularity relies on cmp
rather than on P.le
. (Actually, I suspect that triangularity wrt a poset is not even implemented in Sage.)
comment:27 Changed 6 years ago by
Thank you for your comments Nicolas. Yes, I strongly agree that forcing the nonfacade of the poset could lead to subtle bugs, but I much more strongly believe we should not remove the triangularity just because a user could be evil and we needed to fix the actual mathematical error of this ticket.
The problem with facade parents is we cannot explicitly create elements of them. If we could, then we could then use them as a key with #21043, which would be a better fix. Although it would be somewhat of a hack solution, I could wrap the elements in a very small class which just implements comparison that calls up to the poset.
comment:28 Changed 6 years ago by
There is no evil involved here! A user could just follow the examples, while not realizing the implicit convention that the standard comparison cmp
on a poset should be a linear extension of P.le
(I wasn't aware of it until this very thread), and get something wrong out of it.
comment:29 Changed 6 years ago by
You do have to work somewhat hard to have a poset whose elements have a natural order that is not a linear extension of the poset. I don't think any of the examples have this.
comment:30 Changed 6 years ago by
I remember working hard to *not* have such a poset, back when I was writing my own code for birational rowmotion :) Sure, the examples are smarter than that, but the doc never tells the user the reasoning.
comment:31 Changed 6 years ago by
 Branch changed from public/combinat/fix_moebius_algebra_multiplication21054 to 6515b25a563903e32045b717f36bbed6e1aba176
 Resolution set to fixed
 Status changed from positive_review to closed
comment:32 Changed 6 years ago by
 Commit 6515b25a563903e32045b717f36bbed6e1aba176 deleted
Hi!
I am answering here for locality in the discussion, but of course this belongs to the new ticket.
Is there anything that prevents us from defining a custom cmp function
that is consistent with the default linear extension of the poset and
passing it to TriangularMorphism
?
Here is a facade poset for which cmp is wrong:
sage: P = posets.SetPartitions(3) sage: P.category() Join of Category of finite lattice posets and Category of finite enumerated sets and Category of facade sets sage: P.top() {{1, 2, 3}} sage: sorted(P, cmp=cmp) [{{1}, {2}, {3}}, {{1}, {2, 3}}, {{1, 2}, {3}}, {{1, 2, 3}}, {{1, 3}, {2}}]
A proper cmp function:
sage: key = dict((p,i) for i,p in enumerate(P.linear_extension())) sage: def mycmp(p,q): return cmp(key[p], key[q]) sage: sorted(P, cmp=mycmp) [{{1}, {2}, {3}}, {{1}, {2, 3}}, {{1, 2}, {3}}, {{1, 3}, {2}}, {{1, 2, 3}}]
sage: TriangularMorphism(..., cmp=mycmp)
This suggests that it would be nice for TriangularMorphism? to accept a
key
argument, but that's a different discussion.
Cheers,
Nicolas
comment:33 Changed 6 years ago by
Oh, sorry, I had not seen the further discussion in the other ticket. Let's follow up there.
So the reason why this gets exposed is not with the Möbius algebra code, but instead with the
WithRealizations
framework or the_test_one
method (and coercion) depending on how you look at it. The problem is that running the doctests in that order first produced theI
basis, which becomes the first basis in the_realizations
list, and this differs from thea_realization()
basis (theE
basis). So the_an_element_
constructs an element fromrealizations()[0]
, butone()
usesa_realization().one()
. So this coerces into theI
basis, and then compares it to theE
basis (or vice versa). It is this comparison which fails:So IMO, the simplest fix is to use
a_realization
for_an_element_
(which will probably fix some otherTestSuite
issues I've noticed in the past, which fails if a realization was never given).However, with all of that being said, there still is a problem with the
one
for the idempotent basis:So the first issue is now #21059. For the main issue on this ticket, I guess I will have to read the references again to make sure there isn't something like a sign flipped.