Ideals and subalgebras of finite dimensional Lie algebras

[gh-ehaka]

An implementation of ideals and subalgebras generated by a subset of a finite dimensional Lie algebra with basis. In the finite dimensional case a naive (and probably inefficient) method of repeatedly computing brackets to find a basis of the ideal or subalgebra is available, as opposed to the Gröbner-basis style methods that would need to be used in the general case. 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.

[tscrim]

That was basically how my previous code (on #14901) was doing things. Although it probably should be done lazily (i.e., when the user asks for basis). Will you also be including code for subalgebras?

[gh-ehaka]

The lazy implementation is a good idea, I will tweak it in when I get to the import. Currently I have no code related to generic subalgebras, only a coercion from an ideal back to the ambient algebra. I'll have to see if during cleanup of the ideal-code there is something that sticks out as belonging in a subalgebra construction.

[gh-ehaka]

A first iteration of ideals and subalgebras of finite dimensional Lie algebras with basis is in the commits. I added subalgebras to the scope of this ticket since it turned out that a lot of the code fit naturally within the subalgebra setting, and the only extra piece was the differing computation of a basis.

The implementation of ideals+subalgebras is through a LieSubset base class, whose elements are wrappers (subclassing LieAlgebraElementWrapper) around elements of the ambient Lie algebra. Any computations are done by the lift-retract model suggested by Sets().Subobjects().

Much of the code would fit inside also within a generic LieIdeal or LieSubalgebra class, however the essential part of containment testing of elements would not be implemented, so I decided to leave all the code in a finite dimensional class for now.

Although technically independent from nilpotent Lie algebras, I added the dependency #26076 in order to implement the fact that a subalgebra or ideal of a nilpotent Lie algebra is also nilpotent.

---

Last 10 new commits:

​b70bebd	doctest fix for changed category printing
​7699db4	Merge branch 'u/gh-ehaka/free_nilpotent_lie_algebras-26076' of git://trac.sagemath.org/sage into public/lie_algebras/free_nilpotent-26076
​d1fe093	Some reviewer changes and tweaks.
​a60ef68	Speedup constructor for free Nilpotent Lie algebras.
​664fbec	Changing r=10 as cutoff to requiring a linear ordering.
​1c3f341	Merge remote-tracking branch 'trac/public/lie_algebras/free_nilpotent-26076' into lieideals-26078
​a5a6600	Initial implementation of finite dim subalgebras and ideals
​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

[git]

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

​e2cdaed

Added doctest for nilpotency step computation of ideals and subalgebras

[git]

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

​ff672fc	retract to subalgebra now checks that the element is contained in the subalgebra
​2d7c007	Added repr_short method to ideals mimicking ring ideals

[git]

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

​209c755

Fixed error in testing if a subalgebra or ideal is an ideal of a Lie algebra

[tscrim]

Some comments:

Why do you have these ABCs? I don't see the point of having them and instead just having LieSubalgebra_finite_dimensional_with_basis as the starting class. It is easy enough to separate things once we find a use-case for them, but doing so prematurely can make it harder in terms of maintenance. Of course, if you do have a use-case for them in the future, just let me know.

Rather than manually setting the category as default, you should just use

ambient.category().Subobjects()

as that means you do not need the essentially duplication of subalgebra and ideal in the fin-dim nilpotent with basis category. It also is a much more robust default.

In basis(), EXAMPLES: -> EXAMPLES::.

monomoial_coefficients should not have keys that are not in the support (e.g., the 0: 0 in your example).

Subsequently your __getitem__ should just call self.to_vector()[i] (and return 0 if i is not in the basis index set).

I would consider caching the result of to_vector() since it is computationally expensive.

I would change ambient_submodule to

    def module(self, sparse=False):
        m = self.ambient().module(sparse=sparse)
        ambientbasis = [self.lift(X).to_vector() for X in self.basis()]
        return m.submodule_with_basis(ambientbasis)

I found the name somewhat confusing and nothing in the API for module forces the result to be an ambient module (nor should it have specifically contain "free" in its doc). The result of module is meant to reflect the space where we want to do the linear algebra computations.

if len(gens) == 0: -> if not gens: Although I think in this case, it is better to not have any generators, even if it makes the code more complicated. I would also strip all copies of 0 from the generating set for better input normalization.

I would avoid the use of the (more) ambiguous gens in the subalgebra code and instead use lie_algebra_generators.

Instead of P.ambient().bracket(self_lift, x_lift), use the more direct (and faster) self_lift._bracket_(x_lift). Similarly, instead of calling the lift, I would just use self_lift = self.value. Internal methods can use internal parts. :)

Do you want to implement methods like __add__, direct_sum, is_subalgebra, intersection (for ideals), etc. on this ticket? Similarly, do we want to add shorthands such as L[x, L] and x.bracket(L) for creating ideals? (I am happy to do these implementations.)

[gh-ehaka]

Replying to tscrim:

Some comments:

Of course, if you do have a use-case for them in the future, just let me know.

No use case, just my own misunderstanding of which way of doing things was more maintainable. I will fix this now.

Rather than manually setting the category as default, you should just use

ambient.category().Subobjects()

as that means you do not need the essentially duplication of subalgebra and ideal in the fin-dim nilpotent with basis category. It also is a much more robust default.

The thing I was worried about here is the Graded and Stratified categories. The result in such cases would be

sage: LieAlgebras(QQ).Graded().Subobjects()
Join of Category of graded Lie algebras over Rational Field and Category of subobjects of sets

but not every subalgebra is graded, so this would still need separate handling. Because of this it wasn't clear to me if categories should be handled in an 'opt-out' or 'opt-in' manner. The main worry was that if the default is 'opt-out', then any future implementation of a subcategory of Lie algebras would have to also consider whether ideals and subalgebras are automatically in this category, which sounded error-prone.

I would change ambient_submodule to

    def module(self, sparse=False):
        m = self.ambient().module(sparse=sparse)
        ambientbasis = [self.lift(X).to_vector() for X in self.basis()]
        return m.submodule_with_basis(ambientbasis)

I found the name somewhat confusing and nothing in the API for module forces the result to be an ambient module (nor should it have specifically contain "free" in its doc). The result of module is meant to reflect the space where we want to do the linear algebra computations.

Will fix. However I am not sure how to get rid of "free" coming from

sage: L.<X,Y,Z> = LieAlgebra(ZZ, {('X','Y'): {'Z': 3}})
sage: L.module(sparse=False)
Ambient free module of rank 3 over the principal ideal domain Integer Ring

if len(gens) == 0: -> if not gens: Although I think in this case, it is better to not have any generators, even if it makes the code more complicated. I would also strip all copies of 0 from the generating set for better input normalization.

How much processing should be done here? The upper limit I suppose would be to extract a maximal linearly independent subset, but this might be too expensive for high dimensions. I will add the 'cheap' zero-stripping now.

I would avoid the use of the (more) ambiguous gens in the subalgebra code and instead use lie_algebra_generators.

I will add lie_algebra_generators to subalgebras, but also keep gens, since it is used also by ideals, and I think it would be confusing to have the generating set of an ideal referred to as lie_algebra_generators.

Do you want to implement methods like __add__, direct_sum, is_subalgebra, intersection (for ideals), etc. on this ticket? Similarly, do we want to add shorthands such as L[x, L] and x.bracket(L) for creating ideals? (I am happy to do these implementations.)

These sound like very good convenience additions. You can do the implementation as you most likely have a clearer vision on how it should be done.

I will do the other corrections now, except for the default category thing, as I would still like to hear your comments on how to handle the Graded issue.

[tscrim]

Replying to gh-ehaka:

Replying to tscrim:

Rather than manually setting the category as default, you should just use

ambient.category().Subobjects()

as that means you do not need the essentially duplication of subalgebra and ideal in the fin-dim nilpotent with basis category. It also is a much more robust default.

The thing I was worried about here is the Graded and Stratified categories. The result in such cases would be

sage: LieAlgebras(QQ).Graded().Subobjects()
Join of Category of graded Lie algebras over Rational Field and Category of subobjects of sets

but not every subalgebra is graded, so this would still need separate handling. Because of this it wasn't clear to me if categories should be handled in an 'opt-out' or 'opt-in' manner. The main worry was that if the default is 'opt-out', then any future implementation of a subcategory of Lie algebras would have to also consider whether ideals and subalgebras are automatically in this category, which sounded error-prone.

Ah, I see your point. However, I think this might be more of an issue of Subobjects interacting with Grading improperly. The category should be subobjects of the ambient category, but you are correct, it does not imply they are graded. I will ask Nicolas about this.

I would change ambient_submodule to

    def module(self, sparse=False):
        m = self.ambient().module(sparse=sparse)
        ambientbasis = [self.lift(X).to_vector() for X in self.basis()]
        return m.submodule_with_basis(ambientbasis)

I found the name somewhat confusing and nothing in the API for module forces the result to be an ambient module (nor should it have specifically contain "free" in its doc). The result of module is meant to reflect the space where we want to do the linear algebra computations.

Will fix. However I am not sure how to get rid of "free" coming from

sage: L.<X,Y,Z> = LieAlgebra(ZZ, {('X','Y'): {'Z': 3}})
sage: L.module(sparse=False)
Ambient free module of rank 3 over the principal ideal domain Integer Ring

As for the free modules, the result of module are (generally) free modules since we usually work on Lie algebras over fields or PIDs. The result in this case is a free module, so it is somewhat expected in the output.

if len(gens) == 0: -> if not gens: Although I think in this case, it is better to not have any generators, even if it makes the code more complicated. I would also strip all copies of 0 from the generating set for better input normalization.

How much processing should be done here? The upper limit I suppose would be to extract a maximal linearly independent subset, but this might be too expensive for high dimensions. I will add the 'cheap' zero-stripping now.

I think removing the "cheap" zeros (i.e., identically zero) gens is sufficient.

I would avoid the use of the (more) ambiguous gens in the subalgebra code and instead use lie_algebra_generators.

I will add lie_algebra_generators to subalgebras, but also keep gens, since it is used also by ideals, and I think it would be confusing to have the generating set of an ideal referred to as lie_algebra_generators.

+1 for keeping gens, especially for ideals, but for an ideal, lie_algebra_generators should redirect to basis (as otherwise gens is not guaranteed to generate the ideal as a Lie subalgebra).

Do you want to implement methods like __add__, direct_sum, is_subalgebra, intersection (for ideals), etc. on this ticket? Similarly, do we want to add shorthands such as L[x, L] and x.bracket(L) for creating ideals? (I am happy to do these implementations.)

These sound like very good convenience additions. You can do the implementation as you most likely have a clearer vision on how it should be done.

I will do that soon.

[git]

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

​a25fe51

trac #26078: combining unused base classes and changing module behavior for subalgebras

[gh-ehaka]

I made the changes, however I am still having some confusion with the desired behavior for the subalgebra element methods __getitem__, to_vector and monomial_coefficients.

Having changed module to refer to a submodule of the ambient Lie algebra as opposed to the intrinsic module, to_vector should naturally give elements in the same ambient format, i.e. not in the intrinsic basis. The doc of monomial_coefficients refers to the basis of self though, so that is now still given in terms of the intrinsic basis. It wasn't clear to me which of these __getitem__ should refer to. Currently I left it pointing to monomial_coefficients.

[git]

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

​64ec990

trac #26078: to_vector() now gives an element whose parent is the correct module

[tscrim]

I think __getitem__ should mimic monomial_coefficients and give things in terms of the intrinsic basis (more generally, if we have some way to give a Lie algebra a custom support set, it should return the coefficient of the basis element corresponding to the input i, cf. the Lie algebras defined via structure coefficients).

So I had a brief email exchange with Nicolas, and the conclusion I arrived to is we probably should (for now) just do the parsing in the explicit subalgebra class (this is what is done in the SubmoduleWithBasis class). This will probably be the case until a generic mechanism is added to the category framework.

[git]

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

​4981fd4

trac #26078: moved ideal nilpotency construction out of category code

[tscrim]

I think it would be better to have

        category = cat.Subobjects().or_subcategory(category)
        if ambient in LieAlgebras(ambient.base_ring()).Nilpotent():
            category = category.Nilpotent()

since that way we don't have to force the user to pass a nilpotent category. Likewise, we should allow the user to pass a category via subalgebra and ideal.

Thinking a little bit more, we probably want to combine the ideal and subalgebra classes and simply use an attribute _is_ideal (for the basis() method) and the self.is_ideal(self.ambient()) as a check for when we need the code to diverge. This would keep things easier to work with as perhaps we construct something as a subalgebra that happens to be an ideal, but we don't want to compute things twice or have messy code to share data. Does that make sense?

[gh-ehaka]

Replying to tscrim:

I think it would be better to have

        category = cat.Subobjects().or_subcategory(category)
        if ambient in LieAlgebras(ambient.base_ring()).Nilpotent():
            category = category.Nilpotent()

since that way we don't have to force the user to pass a nilpotent category. Likewise, we should allow the user to pass a category via subalgebra and ideal.

Thinking a little bit more, we probably want to combine the ideal and subalgebra classes and simply use an attribute _is_ideal (for the basis() method) and the self.is_ideal(self.ambient()) as a check for when we need the code to diverge. This would keep things easier to work with as perhaps we construct something as a subalgebra that happens to be an ideal, but we don't want to compute things twice or have messy code to share data. Does that make sense?

That does sound like it could work. Should the class name stay as subalgebra or be something else? I could try to refactor this in later today.

[tscrim]

I would just keep it called subalgebra, but in the docs you will have to discuss the new input parameter is_ideal, where you can (indirectly) mention that the class will also be used to construct ideals.

[git]

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

​0a3784d	trac #26078: combined ideals and subalgebras into one class
​6d71aef	trac #26078: added category parameter to ideal and subalgebra interface

[git]

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

​3d1e21f

trac #26078: removed initializing of incomplete _indices attribute for subalgebras

[gh-ehaka]

I combined everything into one class, which seemed to work quite nicely as it even cut down on some of the duplicate code e.g. in the basis computation.

I also added the category parameter to the ideal and subalgebra methods. However testing creation of a stratified subalgebra I realized that the FilteredModulesWithBasis category requires the _indices attribute. The issue is that the proper _indices parameter can only be computed after the basis is computed. So currently trying to use methods of FilteredModulesWithBasis before basis computation gives errors

sage: L.<x,y> = LieAlgebra(QQ, abelian=True)
sage: C = LieAlgebras(QQ).FiniteDimensional().WithBasis().Subobjects().Graded().Stratified()
sage: S = L.subalgebra(x,category=C)
sage: S.homogeneous_component_basis(1).list()
Traceback (most recent call last):
...
AttributeError: 'LieSubalgebra_finite_dimensional_with_basis_with_category' object has no attribute '_indices'
sage: B = S.basis()
sage: S.homogeneous_component_basis(1).list()
[x]

I'm not sure how to handle the issue of not knowing the proper indices a priori. Having _indices initially correspond to the generators did not seem like a good solution, since the degree_on_basis method of FiniteDimensionalGradedLieAlgebrasWithBasis.Stratified will immediately compute the basis, and then the the old _indices will be irrelevant, leading to strange results for e.g. homogeneous_component_basis.

Is the correct way to fix this behavior to create a subclass for graded subalgebras or is there something else that could be done? Alternatively, the proper implementation of graded subalgebras could also be left to a later ticket.

[git]

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

​fe91f3b

trac #26078: removed unused imports and fixed a missing variable

[tscrim]

Make _indices a @lazy_attribute:

from sage.misc.lazy_attribute import lazy_attribute
from sage.sets.finite_enumerated_set import FiniteEnumeratedSet

@lazy_attribute
def _indices(self):
    return FiniteEnumeratedSet(self.basis().keys())

With this, the first part of your example passes. (The reason for FiniteEnumeratedSet is so that S._indices.cardinality() will work and is consistent with other parts of Sage.)

[tscrim]

Although code generally should not be using _indices as this just serves to index the keys of the generators, not necessarily the basis. I might consider also changing the code in filtered_modules_with_basis to use self.basis().keys() instead of self._indices, but that should be done on a separate ticket. (The reason it is doing this is because it was more or less assuming that things in this category are subclasses of CombinatorialFreeModule.)

[git]

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

​5c40f2b

trac #26078: added lazy attribute _indices to subalgebras

[tscrim]

My last round of comments (I am pretty sure); just two more things. I can do these fixes too (since I also have the other ideal creation to take care of too) if you prefer.

• We probably should do some form of caching on monomial_coefficients for each element. I would do a _monomial_coefficients, defaulting to None that stores the computation, then have

  def monomial_coefficients(self, copy=False):
      if self._monomial_coefficients is None:
          sm = self.parent().module()
          v = sm.coordinate_vector(self.to_vector())
          self._monomial_coefficients = {k: v[k] for k in range(len(v)) if not v[k].is_zero()}
      if copy:
          return dict(self._monomial_coefficients)
      return self._monomial_coefficients
  

  Using this, we can also override

  from sage.data_structures.blas_dict import add
  def _add_(self, other):
    sup = super(self, LieSubalgebra_finite_dimensional_with_basis.Element)
    ret = sup._add_(other)
    if self._monomial_coefficients is not None and other._monomial_coefficients is not None:
        ret._monomial_coefficients = add(self._monomial_coefficients, other._monomial_coefficients)
  

  and similarly for all of the other basic operations. I would also move this all into lie_algebra_element.pyx. What do you think?
• if not v[k].is_zero() -> if v[k].

[gh-ehaka]

I take it moving things to lie_algebra_element.pyx is a speed optimization? Sounds good to me. If it is not too much trouble for you, you can handle these.

[tscrim]

Yes, it would be an optimization (because it will be in Cython and closer to C code). I will get to work on them now.

[tscrim]

Okay, here are those changes. I did not do x.bracket(L) because that was going to be too much work to make sure it was consistent across the board, and it is really syntactic sugar at the end of the day.

If my changes are good, then I believe we are at a positive review.

---

New commits:

​650a325	Merge branch 'u/gh-ehaka/lie_ideals-26078' of git://trac.sagemath.org/sage into public/lie_algebras/fin_dim_ideals_subalgebras-26078
​5b84e1f	Adding code paths to compute ideals using the L[X, Y] and L.bracket(X, Y).
​42dd071	Cythonizing subalgebra elements and caching their monomial coefficients.

[git]

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

​fcb4888

trac #26078: added missing doctest to subalgebra element initialization

[gh-ehaka]

All the improvements above look good to me. I also added a doctest to the initialization of a subalgebra element (at least I assume that was what patchbot was complaining about).

[tscrim]

Whoops, yes, I forgot to add that. Thank you.