Opened 3 years ago

Closed 3 years ago

# Lie algebra quotients are incorrect for some basis orders

Reported by: Owned by: gh-ehaka major sage-8.4 algebra Lie algebras, ideals, subalgebras, quotients Eero Hakavuori Travis Scrimshaw N/A 25026d4 25026d48726e77d0f676351afcc3a6646ab90a8d

### Description

The current implementation of Lie subalgebras confuses two things: the ordering of the basis of the ambient algebra and the ordering of the indices of the ambient algebra. If both orderings agree, then everything works fine:

```sage: L.<a,b,c> = LieAlgebra(QQ, abelian=True)
sage: I = L.ideal([a+b,a+c])
sage: I.basis()
Family (a + b, a + c)
sage: Q = L.quotient(I)
sage: Q.basis()
Finite family {'a': a}
```

But if there is a mismatch in the ordering, then the output is wrong:

```sage: L.<c,b,a> = LieAlgebra(QQ, abelian=True)
sage: I2 = L.ideal([a+b,a+c])
sage: I2.basis()
Family (-c + b, c + a)
sage: Q = L.quotient(I2)
sage: Q.basis()
Finite family {'b': b, 'a': a}
```

The difference is

```sage: [I.lift(X).leading_support() for X in I.basis()]
['b', 'c']
sage: [I2.lift(X).leading_support() for X in I2.basis()]
['c', 'c']
```

That is, the behavior in the latter case is different to what is described in the doc. The indices which are not leading supports of `I2` do not span a complementary subspace, but instead something bigger.

The issue is that currently the computation in `basis` takes its pivot elements based on the ordering of the ambient basis, whereas quotients and reduction assume they can work with `leading_support`, i.e. the ordering of the indices.

### comment:1 Changed 3 years ago by gh-ehaka

• Authors set to Eero Hakavuori
• Branch set to u/gh-ehaka/subalgebra_basis_ordering-26352
• Commit set to eec759470e1f089eb05b130790ce8e9864fd4304
• Status changed from new to needs_review

I changed the helper methods `_to_m` and `_from_m` to use the ordering of indices instead of the ordering of the basis. At the same time I added support for a custom ordering of indices with an additional `order` keyword to the subalgebra. The previously failing example now works as expected:

```sage: L.<c,b,a> = LieAlgebra(QQ, abelian=True)
sage: I2 = L.ideal([a+b, a+c])
sage: I2.basis()
Family (b + a, c + a)
sage: Q = L.quotient(I2)
sage: Q.basis()
Finite family {'a': a}
```

The disadvantage is that the submodule computation is now more complicated as things needs to be sorted based on indices. Before the fix:

```sage: L=LieAlgebra(QQ,3,step=5)
sage: L.dimension()
80
sage: I = L.ideal(L.basis().list()[0])
sage: time I.dimension()
CPU times: user 7.83 s, sys: 4.01 ms, total: 7.83 s
Wall time: 7.82 s
66
```

After the fix:

```sage: time I.dimension()
CPU times: user 8.82 s, sys: 182 µs, total: 8.82 s
Wall time: 8.82 s
66
```

Having the extra functionality of custom orderings is nice, but it would be also good to have also a speed optimized one, where the submodule computation is done without worrying which elements are the pivot elements in the echelon form. In that case the reduction and complementary submodule computation would need special case handling though.

New commits:

 ​eec7594 `trac #26352: Lie subalgebra leading term ordering handling fix`

### comment:2 follow-up: ↓ 4 Changed 3 years ago by tscrim

Hmm...I see the problem:

```sage: L.<a,b,c> = LieAlgebra(QQ, abelian=True)
'c'
sage: L.<c,b,a> = LieAlgebra(QQ, abelian=True)
'c'
```

When I designed this, I was thinking of doing linear algebra directly using the `to_vector`/`from_vector` methods because in those cases, it would be simply (un)wrapping. However, this could be seen as a bug as it does not respect the ordering of `L.indices()`. It might also be better overall to work with actual `vector` objects in general, but I am not sure off-hand.

I am not sure I like having the ideal handle an `order` argument, but it does mean we could have less ambient objects to worry about or create. It probably is the right thing to do overall.

I don't think this is efficient either:

```return self.ambient().module().from_vector(vector(R, X_sorted))
```

I would avoid the call `from_vector` (which creates a `dict` and does the dumb, direct computation) and `vector`. I would just do

```M = self.ambient().module()
B = M.basis()
return M.sum(R(mc[i]) * b[i] for i in self._reversed_indices if i in mc)
```

You don't even need to create the `X_sorted`. Similar in `_from_m`.

I would `@cached_method` `leading_monomials`.

Little thing: `trac #26352` -> `:trac:`26352``

### comment:3 Changed 3 years ago by git

• Commit changed from eec759470e1f089eb05b130790ce8e9864fd4304 to 1f58a6475f42f098cf33d9ed4ff939d5d54b4b88

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

 ​1f58a64 `trac #26352: more efficient vector reordering`

### comment:4 in reply to: ↑ 2 ; follow-up: ↓ 5 Changed 3 years ago by gh-ehaka

It might also be better overall to work with actual `vector` objects in general, but I am not sure off-hand.

I did not understand what you mean by this.

I am not sure I like having the ideal handle an `order` argument, but it does mean we could have less ambient objects to worry about or create. It probably is the right thing to do overall.

It is true that `order` is more of a property of the ambient Lie algebra than the ideals. At least that is how it is in the polynomial ring setting. I don't really have a use case where I would want to create ideals in several different orderings on the same Lie algebra, so it would be perfectly fine to move `order` to an optional parameter in `LieAlgebra`. Although if nothing else in the Lie algebra code uses the ordering then it might be a bit unclear what `order` actually effects. But maybe this would be an issue solved by its doc description?

I don't think this is efficient either:

```return self.ambient().module().from_vector(vector(R, X_sorted))
```

I would avoid the call `from_vector` (which creates a `dict` and does the dumb, direct computation) and `vector`. I would just do

```M = self.ambient().module()
B = M.basis()
return M.sum(R(mc[i]) * b[i] for i in self._reversed_indices if i in mc)
```

You don't even need to create the `X_sorted`. Similar in `_from_m`.

Good call. It cut down the overhead in the previous testcase by a decent amount:

```sage: L=LieAlgebra(QQ,3,step=5)
sage: I = L.ideal(L.basis().list()[0])
sage: time d=I.dimension()
CPU times: user 8.22 s, sys: 16.1 ms, total: 8.23 s
Wall time: 8.23 s
```

This is still a ~5% increase from prepatch, but not nearly as bad as the earlier 12-17% one.

I would `@cached_method` `leading_monomials`.

Little thing: `trac #26352` -> `:trac:`26352``

### comment:5 in reply to: ↑ 4 ; follow-up: ↓ 8 Changed 3 years ago by tscrim

• Reviewers set to Travis Scrimshaw

It might also be better overall to work with actual `vector` objects in general, but I am not sure off-hand.

I did not understand what you mean by this.

I had gotten an impression you were doing some work with the Lie algebra elements instead of their corresponding (typically underlying) `vector`. I guess you are not. Sorry for the noise.

I am not sure I like having the ideal handle an `order` argument, but it does mean we could have less ambient objects to worry about or create. It probably is the right thing to do overall.

It is true that `order` is more of a property of the ambient Lie algebra than the ideals. At least that is how it is in the polynomial ring setting. I don't really have a use case where I would want to create ideals in several different orderings on the same Lie algebra, so it would be perfectly fine to move `order` to an optional parameter in `LieAlgebra`. Although if nothing else in the Lie algebra code uses the ordering then it might be a bit unclear what `order` actually effects. But maybe this would be an issue solved by its doc description?

There is some reasons to have this. It might be faster in one order than other or you want different representatives. The catch with storing this with the ambient Lie algebra is that you have to create a new object for each order. Which is somewhat annoying at the very least. Unfortunately I don't think this is something simply solved by adding/changing stuff in the doc.

Anyways, this fixes a bug and I don't see any other obvious ways to speed this up right now. Positive review.

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

• Status changed from needs_review to positive_review

### comment:7 Changed 3 years ago by git

• Commit changed from 1f58a6475f42f098cf33d9ed4ff939d5d54b4b88 to 25026d48726e77d0f676351afcc3a6646ab90a8d
• Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

 ​25026d4 `trac #26352: removed orphaned import`

### comment:8 in reply to: ↑ 5 Changed 3 years ago by gh-ehaka

• Status changed from needs_review to positive_review

I removed the orphaned import of `vector` that patchbot found. Setting back to positive review as the code itself was not changed and tests still passed.