Opened 3 years ago

Closed 3 years ago

Last modified 3 years ago

#21054 closed defect (fixed)

Transition between bases is incorrect for Moebius algebras

Reported by: jmantysalo Owned by:
Priority: critical Milestone: sage-7.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) Commit:
Dependencies: Stopgaps:

Description (last modified by tscrim)

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 3 years ago by tscrim

  • Cc nthiery darij added

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 the I basis, which becomes the first basis in the _realizations list, and this differs from the a_realization() basis (the E basis). So the _an_element_ constructs an element from realizations()[0], but one() uses a_realization().one(). So this coerces into the I basis, and then compares it to the E basis (or vice versa). It is this comparison which fails:

sage: L = posets.BooleanLattice(4)
sage: M = L.moebius_algebra(QQ)
sage: M.I()
Moebius algebra of Finite lattice containing 16 elements over Rational Field in the idempotent basis
sage: TestSuite(M).run()
Failure in _test_one:
...
------------------------------------------------------------
The following tests failed: _test_one
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

So IMO, the simplest fix is to use a_realization for _an_element_ (which will probably fix some other TestSuite 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:

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]

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.

comment:2 Changed 3 years ago by tscrim

  • Authors set to Travis Scrimshaw
  • Branch set to public/combinat/fix_moebius_algebra_multiplication-21054
  • 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

FYI - this is independent of #21059. Ready for review.


New commits:

19db2a2Fixing multiplication in Moebius algebras.

comment:3 Changed 3 years ago by darij

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 3 years ago by git

  • Commit changed from 19db2a232e6471c536d0035b06d7a1beffaf63d1 to e5e590392fcd641b3aa7946c63bc27a6ed5fbfd9

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

e5e5903Changing upper to lower due to transition matrix change.

comment:5 Changed 3 years ago by tscrim

  • Description modified (diff)
  • Reviewers set to Darij Grinberg

Good catch. The triangularity changed because of the change in transition maps.

comment:6 Changed 3 years ago by tscrim

Also, the order relations come from the basis index set.

comment:7 follow-up: Changed 3 years ago by darij

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 3 years ago by tscrim

Replying to darij:

So module_morphism is smart enough to compare basis indices using something like index_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 3 years ago by darij

Oh; can we remove the "explicit" triangularity then? What is it used for, beyond computing inverses?

comment:10 Changed 3 years ago by tscrim

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 3 years ago by tscrim

Can I consider this as a positive review?

comment:12 Changed 3 years ago by darij

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 3 years ago by darij

(I guess the main question here is: When we define several bases of a module-with-realizations, 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 )

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

comment:14 Changed 3 years ago by tscrim

  • 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 3 years ago by darij

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 3 years ago by tscrim

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 3 years ago by tscrim

Perhaps one simple way out is to make the poset indexing the basis a non-facade 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 3 years ago by darij

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 3 years ago by tscrim

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 3 years ago by git

  • Commit changed from e5e590392fcd641b3aa7946c63bc27a6ed5fbfd9 to 6515b25a563903e32045b717f36bbed6e1aba176

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

05c2f60Merge branch 'develop' into public/combinat/fix_moebius_algebra_multiplication-21054
6515b25Force the defining lattice to be a non-facade lattice.

comment:21 Changed 3 years ago by tscrim

This should take care of the issues, and it doesn't have any overt problems.

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

comment:22 Changed 3 years ago by darij

LGTM now, thanks!

comment:23 Changed 3 years ago by darij

  • Status changed from needs_review to positive_review

comment:24 Changed 3 years ago by tscrim

Thank you! (See you in about a month.)

comment:25 Changed 3 years ago by nthiery

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 3 years ago by darij

Thanks, Nicolas -- but I think this is precisely the one combination of decisions that does *not* work. We cannot have all three:

  1. exposed coerce maps,
  2. triangularity being explicitly guaranteed in the coerce maps,
  3. the poset being left as is as opposed to being converted to non-facade.

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 3 years ago by tscrim

Thank you for your comments Nicolas. Yes, I strongly agree that forcing the non-facade 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 3 years ago by darij

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 3 years ago by tscrim

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 3 years ago by darij

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 3 years ago by vbraun

  • Branch changed from public/combinat/fix_moebius_algebra_multiplication-21054 to 6515b25a563903e32045b717f36bbed6e1aba176
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:32 Changed 3 years ago by nthiery

  • 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 3 years ago by nthiery

Oh, sorry, I had not seen the further discussion in the other ticket. Let's follow up there.

Note: See TracTickets for help on using tickets.