Ideals and subalgebras of finite dimensional Lie algebras

[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

Depends on #26076

CC: @tscrim

Component: algebra

Keywords: Lie algebras, ideals, subalgebras

Author: Eero Hakavuori

Branch/Commit: fcb4888

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/26078

[ehaka]

comment:1

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

[tscrim]

comment:2

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?

[ehaka]

comment:3

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.

[ehaka]

comment:4

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

[ehaka]

Branch: u/gh-ehaka/lie_ideals-26078

[ehaka]

Dependencies: #26076

[ehaka]

Commit: 5957697

[ehaka]

Changed keywords from Lie algebras, ideals to Lie algebras, ideals, subalgebras

[sagetrac-git]

Changed commit from 5957697 to e2cdaed

[sagetrac-git]

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

e2cdaed

Added doctest for nilpotency step computation of ideals and subalgebras

[sagetrac-git]

Changed commit from e2cdaed to 2d7c007

[sagetrac-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

[sagetrac-git]

Changed commit from 2d7c007 to 209c755

[sagetrac-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

[ehaka]

Author: Eero Hakavuori

[tscrim]

comment:9

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

[ehaka]

comment:10

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]

comment:11

Replying to @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.

[sagetrac-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

[sagetrac-git]

Changed commit from 209c755 to a25fe51

[ehaka]

comment:13

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.

[sagetrac-git]

Changed commit from a25fe51 to 64ec990

[sagetrac-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]

comment:19

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.

[sagetrac-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

[sagetrac-git]

Changed commit from 4981fd4 to 6d71aef

[sagetrac-git]

Changed commit from 6d71aef to 3d1e21f

[sagetrac-git]

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

3d1e21f

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

[ehaka]

comment:22

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.

[sagetrac-git]

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

fe91f3b

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

[sagetrac-git]

Changed commit from 3d1e21f to fe91f3b

[tscrim]

comment:24

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]

comment:25

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

[sagetrac-git]

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

5c40f2b

trac #26078: added lazy attribute _indices to subalgebras

[sagetrac-git]

Changed commit from fe91f3b to 5c40f2b

[tscrim]

comment:27

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

[ehaka]

comment:28

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]

comment:29

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]

Changed commit from 5c40f2b to 42dd071

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

Changed branch from u/gh-ehaka/lie_ideals-26078 to public/lie_algebras/fin_dim_ideals_subalgebras-26078

[tscrim]

comment:30

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.

[sagetrac-git]

Changed commit from 42dd071 to fcb4888

[sagetrac-git]

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

fcb4888

trac #26078: added missing doctest to subalgebra element initialization

[ehaka]

comment:32

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]

comment:33

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

[vbraun]

Changed branch from public/lie_algebras/fin_dim_ideals_subalgebras-26078 to fcb4888