Opened 6 years ago

Closed 6 years ago

# Transition between bases is incorrect for Moebius algebras

Reported by: Owned by: jmantysalo critical sage-7.3 combinatorics tscrim, nthiery, darij Travis Scrimshaw Darij Grinberg N/A 6515b25

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

### comment:1 Changed 6 years ago by tscrim

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 6 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:

 ​19db2a2 `Fixing multiplication in Moebius algebras.`

### comment:3 Changed 6 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 6 years ago by git

• 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 tscrim

• 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 tscrim

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

### comment:7 follow-up: ↓ 8 Changed 6 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 6 years ago by tscrim

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

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

### comment:10 Changed 6 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 6 years ago by tscrim

Can I consider this as a positive review?

### comment:12 Changed 6 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 6 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 6 years ago by darij (previous) (diff)

### comment:14 Changed 6 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 6 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 6 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 6 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 6 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 6 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 6 years ago by git

• Commit changed from e5e590392fcd641b3aa7946c63bc27a6ed5fbfd9 to 6515b25a563903e32045b717f36bbed6e1aba176

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

 ​05c2f60 `Merge branch 'develop' into public/combinat/fix_moebius_algebra_multiplication-21054` ​6515b25 `Force the defining lattice to be a non-facade lattice.`

### comment:21 Changed 6 years ago by tscrim

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

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

### comment:22 Changed 6 years ago by darij

LGTM now, thanks!

### comment:23 Changed 6 years ago by darij

• Status changed from needs_review to positive_review

### comment:24 Changed 6 years ago by tscrim

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

### comment:25 Changed 6 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 6 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 6 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 6 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 6 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 6 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 6 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 6 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 6 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.