Opened 2 years ago

Closed 2 years ago

#26078 closed enhancement (fixed)

Ideals and subalgebras of finite dimensional Lie algebras

Reported by: gh-ehaka Owned by:
Priority: major Milestone: sage-8.4
Component: algebra Keywords: Lie algebras, ideals, subalgebras
Cc: tscrim Merged in:
Authors: Eero Hakavuori Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: fcb4888 (Commits) Commit: fcb488858260db781ccc93200d5e6976389d861d
Dependencies: #26076 Stopgaps:

Description (last modified by 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

Change History (34)

comment:1 Changed 2 years ago by gh-ehaka

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

comment:2 Changed 2 years ago by 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?

comment:3 Changed 2 years ago by 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.

comment:4 Changed 2 years ago by gh-ehaka

  • Branch set to u/gh-ehaka/lie_ideals-26078
  • Cc tscrim added
  • Commit set to 59576970729d4378562773cc04af617b183b2127
  • Dependencies set to #26076
  • Description modified (diff)
  • Keywords subalgebras added
  • Status changed from new to needs_review
  • Summary changed from Ideals of finite dimensional Lie algebras to Ideals and subalgebras of finite dimensional Lie algebras

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:

b70bebddoctest fix for changed category printing
7699db4Merge branch 'u/gh-ehaka/free_nilpotent_lie_algebras-26076' of git://trac.sagemath.org/sage into public/lie_algebras/free_nilpotent-26076
d1fe093Some reviewer changes and tweaks.
a60ef68Speedup constructor for free Nilpotent Lie algebras.
664fbecChanging r=10 as cutoff to requiring a linear ordering.
1c3f341Merge remote-tracking branch 'trac/public/lie_algebras/free_nilpotent-26076' into lieideals-26078
a5a6600Initial implementation of finite dim subalgebras and ideals
69dfbfePreserve nilpotent category for ideals and subalgebras of nilpotent Lie algebras
a0d60e1Refactored subobject computations to use lift and retract instead of value
5957697Fix for lower central series computation of subalgebras: 'from_vector' now checks if the vector is given in the ambient or intrinsic form

comment:5 Changed 2 years ago by git

  • Commit changed from 59576970729d4378562773cc04af617b183b2127 to e2cdaed522396d8154a9eed6246580a886b8f366

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

e2cdaedAdded doctest for nilpotency step computation of ideals and subalgebras

comment:6 Changed 2 years ago by git

  • Commit changed from e2cdaed522396d8154a9eed6246580a886b8f366 to 2d7c00706e3bc93cc85d81ef7d2f77c8632ea86a

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

ff672fcretract to subalgebra now checks that the element is contained in the subalgebra
2d7c007Added repr_short method to ideals mimicking ring ideals

comment:7 Changed 2 years ago by git

  • Commit changed from 2d7c00706e3bc93cc85d81ef7d2f77c8632ea86a to 209c75541d4f6a4bfe7ba1c469b14a9ffe66a6e8

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

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

comment:8 Changed 2 years ago by gh-ehaka

  • Authors set to Eero Hakavuori

comment:9 follow-up: Changed 2 years ago by 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.)

comment:10 in reply to: ↑ 9 ; follow-up: Changed 2 years ago by 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.

comment:11 in reply to: ↑ 10 Changed 2 years ago by 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.

comment:12 Changed 2 years ago by git

  • Commit changed from 209c75541d4f6a4bfe7ba1c469b14a9ffe66a6e8 to a25fe51f655acaac05ac7fcdd8c070f839feefe8

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

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

comment:13 Changed 2 years ago by 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.

comment:14 Changed 2 years ago by git

  • Commit changed from a25fe51f655acaac05ac7fcdd8c070f839feefe8 to 64ec99048e3635490dd8baa8d45763a73fd86592

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

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

comment:15 Changed 2 years ago by 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.

comment:16 Changed 2 years ago by git

  • Commit changed from 64ec99048e3635490dd8baa8d45763a73fd86592 to 4981fd4411d664ad87ae310baa0cefed5fb3a167

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

4981fd4trac #26078: moved ideal nilpotency construction out of category code

comment:17 follow-up: Changed 2 years ago by 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?

comment:18 in reply to: ↑ 17 Changed 2 years ago by 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.

comment:19 Changed 2 years ago by 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.

comment:20 Changed 2 years ago by git

  • Commit changed from 4981fd4411d664ad87ae310baa0cefed5fb3a167 to 6d71aefed41ae73745110b28e463977e5abe1bb2

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

0a3784dtrac #26078: combined ideals and subalgebras into one class
6d71aeftrac #26078: added category parameter to ideal and subalgebra interface

comment:21 Changed 2 years ago by git

  • Commit changed from 6d71aefed41ae73745110b28e463977e5abe1bb2 to 3d1e21fcf0de255b63fb1a7141aedfe0c01c97ab

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

3d1e21ftrac #26078: removed initializing of incomplete _indices attribute for subalgebras

comment:22 Changed 2 years ago by 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.

comment:23 Changed 2 years ago by git

  • Commit changed from 3d1e21fcf0de255b63fb1a7141aedfe0c01c97ab to fe91f3bc709974dee7365d761e08cf1267947474

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

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

comment:24 Changed 2 years ago by 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.)

comment:25 Changed 2 years ago by 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.)

comment:26 Changed 2 years ago by git

  • Commit changed from fe91f3bc709974dee7365d761e08cf1267947474 to 5c40f2b0ee248290ad97e451ea4446a8c3b3d9ec

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

5c40f2btrac #26078: added lazy attribute _indices to subalgebras

comment:27 Changed 2 years ago by 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].

comment:28 Changed 2 years ago by 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.

comment:29 Changed 2 years ago by 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.

comment:30 Changed 2 years ago by tscrim

  • Branch changed from u/gh-ehaka/lie_ideals-26078 to public/lie_algebras/fin_dim_ideals_subalgebras-26078
  • Commit changed from 5c40f2b0ee248290ad97e451ea4446a8c3b3d9ec to 42dd07107a85c823fa17eb0bb6e911b3e8944e17
  • Reviewers set to Travis Scrimshaw

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:

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

comment:31 Changed 2 years ago by git

  • Commit changed from 42dd07107a85c823fa17eb0bb6e911b3e8944e17 to fcb488858260db781ccc93200d5e6976389d861d

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

fcb4888trac #26078: added missing doctest to subalgebra element initialization

comment:32 Changed 2 years ago by gh-ehaka

  • Status changed from needs_review to positive_review

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

comment:33 Changed 2 years ago by tscrim

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

comment:34 Changed 2 years ago by vbraun

  • Branch changed from public/lie_algebras/fin_dim_ideals_subalgebras-26078 to fcb488858260db781ccc93200d5e6976389d861d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.