Opened 4 years ago

Closed 4 years ago

#26079 closed enhancement (fixed)

Quotients of finite dimensional Lie algebras

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

Status badges

Description

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

Change History (13)

comment:1 Changed 4 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 4 years ago by gh-ehaka

  • Authors set to Eero Hakavuori
  • Branch set to u/gh-ehaka/quotients-26079
  • Commit set to ead5abdd0a6ee15a81c3092811d28aea61d528dc
  • Status changed from new to needs_review

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


Last 10 new commits:

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
e2cdaedAdded doctest for nilpotency step computation of ideals and subalgebras
ff672fcretract to subalgebra now checks that the element is contained in the subalgebra
2d7c007Added repr_short method to ideals mimicking ring ideals
209c755Fixed error in testing if a subalgebra or ideal is an ideal of a Lie algebra
0be7e09Merge remote-tracking branch 'trac/u/gh-ehaka/lie_ideals-26078' into quotients-26079
5a23c5etrac #26079: initial implementation of quotients of finite dimensional Lie algebras
ead5abdtrac #26079: removed unnecessary conversion from elements of the quotient to the ambient Lie algebra

comment:3 Changed 4 years ago by tscrim

  • Cc tscrim added
  • Status changed from needs_review to needs_info

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

comment:4 follow-up: Changed 4 years ago by gh-ehaka

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

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

Last edited 4 years ago by gh-ehaka (previous) (diff)

comment:5 in reply to: ↑ 4 ; follow-up: Changed 4 years ago by tscrim

Replying to gh-ehaka:

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

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

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

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

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

comment:6 Changed 4 years ago by git

  • Commit changed from ead5abdd0a6ee15a81c3092811d28aea61d528dc to 08fc4dc3c841ee49c85aa4ca3025fcf68d610028

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

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

comment:7 in reply to: ↑ 5 Changed 4 years ago by gh-ehaka

Replying to tscrim:

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

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

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

comment:8 Changed 4 years ago by gh-ehaka

  • Status changed from needs_info to needs_review

comment:9 Changed 4 years ago by tscrim

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

You should have a method

def defining_ideal(self):
    return self._I

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

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

-        sorted_indices = [ambient.basis().inverse_family()[X]
-                          for X in ambient.basis()]
+        inv = ambient.basis().inverse_family()
+        sorted_indices = [iv[X] for X in ambient.basis()]
-        sm = L.module().submodule_with_basis([I.reduce(L.basis()[i]).to_vector()
+        B = L.basis()
+        sm = L.module().submodule_with_basis([I.reduce(B[i]).to_vector()
                                               for i in index_set])
-        Xdict = X.monomial_coefficients().items()
-        return L.sum(ck * L.basis()[ik] for ik, ck in Xdict)
+        B = L.basis()
+        return L.sum(ck * B[ik] for ik, ck in X)

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

comment:10 Changed 4 years ago by git

  • Commit changed from 08fc4dc3c841ee49c85aa4ca3025fcf68d610028 to e775e2596a2fa39dae5b3ad304dd49d3a0329001

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

e775e25trac #26079: some effiency improvements

comment:11 Changed 4 years ago by git

  • Commit changed from e775e2596a2fa39dae5b3ad304dd49d3a0329001 to 01a3669e7472ca82c3fd56e755eca0e1b08cbbc7

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

01a3669trac #26079: moved import out of __classcall__

comment:12 Changed 4 years ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

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

comment:13 Changed 4 years ago by vbraun

  • Branch changed from u/gh-ehaka/quotients-26079 to 01a3669e7472ca82c3fd56e755eca0e1b08cbbc7
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.