Quotients of finite dimensional Lie algebras

[gh-ehaka]

An implementation of quotients of finite dimensional Lie algebras with basis. As with ideals, in the finite dimensional case a naive (and probably inefficient) to compute quotients is available by reducing a basis of the Lie algebra modulo the ideal and computing structural coefficients in terms of the reduced basis. Part of a part of #16824

[gh-ehaka]

Some implementation already exists in a codebase that I need to clean up and import into Sage.

[gh-ehaka]

An initial implementation in the commits. The Lie algebra that the quotient was created from is stored for internal use in the __ambient attribute instead of _ambient as the latter is being used in product_space in sage.categories.algebras.finite_dimensional_lie_algebras_with_basis, which caused issues with e.g. lower central series computations for quotient Lie algebras.

---

Last 10 new commits:

​69dfbfe	Preserve nilpotent category for ideals and subalgebras of nilpotent Lie algebras
​a0d60e1	Refactored subobject computations to use lift and retract instead of value
​5957697	Fix for lower central series computation of subalgebras: 'from_vector' now checks if the vector is given in the ambient or intrinsic form
​e2cdaed	Added doctest for nilpotency step computation of ideals and subalgebras
​ff672fc	retract to subalgebra now checks that the element is contained in the subalgebra
​2d7c007	Added repr_short method to ideals mimicking ring ideals
​209c755	Fixed error in testing if a subalgebra or ideal is an ideal of a Lie algebra
​0be7e09	Merge remote-tracking branch 'trac/u/gh-ehaka/lie_ideals-26078' into quotients-26079
​5a23c5e	trac #26079: initial implementation of quotients of finite dimensional Lie algebras
​ead5abd	trac #26079: removed unnecessary conversion from elements of the quotient to the ambient Lie algebra

[tscrim]

So having _ambient and __ambient being different objects will be horribly confusing and prone to causing errors. So what we probably need is a better test in product_space (or anything else that needs to check if something is constructed as a subalgebra. I haven't thought about this yet, but will try to do so today. Do you have any ideas?

[gh-ehaka]

One option could be to replicate the is_ideal approach and to add a is_subalgebra method, leaving the particular implementation to the classes themselves. In the current implementation the subalgebras are already overriding is_ideal since module currently refers to the intrinsic basis of the subalgebra. This is possibly something that I should refactor in #26078, since the mix between the intrinsic and ambient bases is a bit confusing as well. Perhaps for subalgebras anything referring to vectors is best done only in the ambient basis?

Another possibility would be to make use of the Subobjects category. Ideals and subalgebras are in the Subobjects category and quotients in the Subquotients category instead. So subalgebras are distinguished from quotients by containment in LieAlgebras(R).Subobjects(). Although I am not sure how this would fit together with other Lie algebra implementations that use _ambient (nor do I know what are all the places where this is used).

[tscrim]

Replying to gh-ehaka:

One option could be to replicate the is_ideal approach and to add a is_subalgebra method, leaving the particular implementation to the classes themselves. In the current implementation the subalgebras are already overriding is_ideal since module currently refers to the intrinsic basis of the subalgebra. This is possibly something that I should refactor in #26078, since the mix between the intrinsic and ambient bases is a bit confusing as well. Perhaps for subalgebras anything referring to vectors is best done only in the ambient basis?

I think in terms of computations, it would be better to do keep it in terms of the local basis. This will be much faster and structure coefficients can be computed lazily (i.e., on demand) because you keep track of the lift to the ambient (which should basically be stored in a list or some other fast data structure).

Another possibility would be to make use of the Subobjects category. Ideals and subalgebras are in the Subobjects category and quotients in the Subquotients category instead. So subalgebras are distinguished from quotients by containment in LieAlgebras(R).Subobjects(). Although I am not sure how this would fit together with other Lie algebra implementations that use _ambient (nor do I know what are all the places where this is used).

This should not be heavily (or maybe even at all other than some toy examples) used currently because I never got around to really implementing subalgebras. I think this would be a better strategy (I don't think categories were implemented in Sage when I first did this). The only other thing that seems reasonable to me is doing an is_subalgebra, but that seems kind of dumb and would be better suited to doing things like L.is_subalgebra(M).

I guess also nobody thought about having subobjects of quotients. Although this lift to the ambient is really just an optimization because the ambient will already have the structure coeffs, but the submodule may not. However, I think it is generally a useful optimization (as it allows you to work only with the submodules).

[git]

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

​3c0251b	Merge branch 'develop' into u/gh-ehaka/quotients-26079
​115b579	trac #26079: fix for changed ideal baseclass and fixed nonsense doctest
​3289fc4	trac #26079: modified Lie algebra product space computation to test for Subobject category instead of the _ambient attribute
​08fc4dc	trac #26079: removed orphaned line of code

[gh-ehaka]

Replying to tscrim:

This should not be heavily (or maybe even at all other than some toy examples) used currently because I never got around to really implementing subalgebras. I think this would be a better strategy (I don't think categories were implemented in Sage when I first did this).

Trying to find all uses of _ambient with search_src under the category and algebra modules only turned up a commented out piece of code in sage.algebras.lie_algebras.lie_algebra.py and the Lie algebra example in sage.categories.examples.finite_dimensional_lie_algebras_with_basis.py, which conveniently enough already uses the Subobjects category.

Based on the above search, I replaced the use of the _ambient attribute in the product_space method of FiniteDimensionalLieAlgebrasWithBasis to test for containment in the Subobjects subcategory instead. All the doctests still worked, so at least on the surface the change did not break anything.

[tscrim]

Thank you. There are a few more things, but it is almost ready.

You should have a method

def defining_ideal(self):
    return self._I

(This is what is done for, e.g., quotients of the FreeAlgebra.)

These changes limit a little bit the number of function calls. While they are not likely to give a significant/noticeable speedup, they do help limit the overhead a bit more:

-        sorted_indices = [ambient.basis().inverse_family()[X]
-                          for X in ambient.basis()]
+        inv = ambient.basis().inverse_family()
+        sorted_indices = [iv[X] for X in ambient.basis()]

-        sm = L.module().submodule_with_basis([I.reduce(L.basis()[i]).to_vector()
+        B = L.basis()
+        sm = L.module().submodule_with_basis([I.reduce(B[i]).to_vector()
                                               for i in index_set])

-        Xdict = X.monomial_coefficients().items()
-        return L.sum(ck * L.basis()[ik] for ik, ck in Xdict)
+        B = L.basis()
+        return L.sum(ck * B[ik] for ik, ck in X)

(This also reduced the memory overhead.) Lastly, pull the sm.basis() call outside of the for loop.

[git]

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

​e775e25

trac #26079: some effiency improvements

[git]

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

​01a3669

trac #26079: moved import out of __classcall__

[tscrim]

Thank you again for doing such a fine job implementing this. LGTM.