Opened 2 years ago
Closed 2 years ago
#26078 closed enhancement (fixed)
Ideals and subalgebras of finite dimensional Lie algebras
Reported by:  ghehaka  Owned by:  

Priority:  major  Milestone:  sage8.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 )
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öbnerbasis 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
comment:2 Changed 2 years ago by
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
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 idealcode there is something that sticks out as belonging in a subalgebra construction.
comment:4 Changed 2 years ago by
 Branch set to u/ghehaka/lie_ideals26078
 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 liftretract 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/ghehaka/free_nilpotent_lie_algebras26076' of git://trac.sagemath.org/sage into public/lie_algebras/free_nilpotent26076

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 remotetracking branch 'trac/public/lie_algebras/free_nilpotent26076' into lieideals26078

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

comment:5 Changed 2 years ago by
 Commit changed from 59576970729d4378562773cc04af617b183b2127 to e2cdaed522396d8154a9eed6246580a886b8f366
Branch pushed to git repo; I updated commit sha1. New commits:
e2cdaed  Added doctest for nilpotency step computation of ideals and subalgebras

comment:6 Changed 2 years ago by
 Commit changed from e2cdaed522396d8154a9eed6246580a886b8f366 to 2d7c00706e3bc93cc85d81ef7d2f77c8632ea86a
comment:7 Changed 2 years ago by
 Commit changed from 2d7c00706e3bc93cc85d81ef7d2f77c8632ea86a to 209c75541d4f6a4bfe7ba1c469b14a9ffe66a6e8
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

comment:8 Changed 2 years ago by
comment:9 followup: ↓ 10 Changed 2 years ago by
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 usecase for them, but doing so prematurely can make it harder in terms of maintenance. Of course, if you do have a usecase 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 findim 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 ; followup: ↓ 11 Changed 2 years ago by
Replying to tscrim:
Some comments:
Of course, if you do have a usecase 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
andideal
in the findim 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 'optout' or 'optin' manner. The main worry was that if the default is 'optout', 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 errorprone.
I would change
ambient_submodule
todef 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 ofmodule
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' zerostripping now.
I would avoid the use of the (more) ambiguous
gens
in the subalgebra code and instead uselie_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 asL[x, L]
andx.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
Replying to ghehaka:
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
andideal
in the findim nilpotent with basis category. It also is a much more robust default.The thing I was worried about here is the
Graded
andStratified
categories. The result in such cases would besage: LieAlgebras(QQ).Graded().Subobjects() Join of Category of graded Lie algebras over Rational Field and Category of subobjects of setsbut 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 'optout' or 'optin' manner. The main worry was that if the default is 'optout', 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 errorprone.
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
todef 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 ofmodule
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' zerostripping 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 uselie_algebra_generators
.I will add
lie_algebra_generators
to subalgebras, but also keepgens
, since it is used also by ideals, and I think it would be confusing to have the generating set of an ideal referred to aslie_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 asL[x, L]
andx.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
 Commit changed from 209c75541d4f6a4bfe7ba1c469b14a9ffe66a6e8 to a25fe51f655acaac05ac7fcdd8c070f839feefe8
Branch pushed to git repo; I updated commit sha1. New commits:
a25fe51  trac #26078: combining unused base classes and changing module behavior for subalgebras

comment:13 Changed 2 years ago by
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
 Commit changed from a25fe51f655acaac05ac7fcdd8c070f839feefe8 to 64ec99048e3635490dd8baa8d45763a73fd86592
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

comment:15 Changed 2 years ago by
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
 Commit changed from 64ec99048e3635490dd8baa8d45763a73fd86592 to 4981fd4411d664ad87ae310baa0cefed5fb3a167
Branch pushed to git repo; I updated commit sha1. New commits:
4981fd4  trac #26078: moved ideal nilpotency construction out of category code

comment:17 followup: ↓ 18 Changed 2 years ago by
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
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
viasubalgebra
andideal
.Thinking a little bit more, we probably want to combine the ideal and subalgebra classes and simply use an attribute
_is_ideal
(for thebasis()
method) and theself.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
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
 Commit changed from 4981fd4411d664ad87ae310baa0cefed5fb3a167 to 6d71aefed41ae73745110b28e463977e5abe1bb2
comment:21 Changed 2 years ago by
 Commit changed from 6d71aefed41ae73745110b28e463977e5abe1bb2 to 3d1e21fcf0de255b63fb1a7141aedfe0c01c97ab
Branch pushed to git repo; I updated commit sha1. New commits:
3d1e21f  trac #26078: removed initializing of incomplete _indices attribute for subalgebras

comment:22 Changed 2 years ago by
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
 Commit changed from 3d1e21fcf0de255b63fb1a7141aedfe0c01c97ab to fe91f3bc709974dee7365d761e08cf1267947474
Branch pushed to git repo; I updated commit sha1. New commits:
fe91f3b  trac #26078: removed unused imports and fixed a missing variable

comment:24 Changed 2 years ago by
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
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
 Commit changed from fe91f3bc709974dee7365d761e08cf1267947474 to 5c40f2b0ee248290ad97e451ea4446a8c3b3d9ec
Branch pushed to git repo; I updated commit sha1. New commits:
5c40f2b  trac #26078: added lazy attribute _indices to subalgebras

comment:27 Changed 2 years ago by
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 toNone
that stores the computation, then haveUsing this, we can also overridedef 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
and similarly for all of the other basic operations. I would also move this all intofrom 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)
lie_algebra_element.pyx
. What do you think? if not v[k].is_zero()
>if v[k]
.
comment:28 Changed 2 years ago by
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
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
 Branch changed from u/ghehaka/lie_ideals26078 to public/lie_algebras/fin_dim_ideals_subalgebras26078
 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:
650a325  Merge branch 'u/ghehaka/lie_ideals26078' of git://trac.sagemath.org/sage into public/lie_algebras/fin_dim_ideals_subalgebras26078

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.

comment:31 Changed 2 years ago by
 Commit changed from 42dd07107a85c823fa17eb0bb6e911b3e8944e17 to fcb488858260db781ccc93200d5e6976389d861d
Branch pushed to git repo; I updated commit sha1. New commits:
fcb4888  trac #26078: added missing doctest to subalgebra element initialization

comment:32 Changed 2 years ago by
 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
Whoops, yes, I forgot to add that. Thank you.
comment:34 Changed 2 years ago by
 Branch changed from public/lie_algebras/fin_dim_ideals_subalgebras26078 to fcb488858260db781ccc93200d5e6976389d861d
 Resolution set to fixed
 Status changed from positive_review to closed
Some implementation already exists in a codebase that I need to clean up and import into Sage.