Implement categories for Lie algebras

[tscrim]

Part of #14901. This implements a basic version of the categories:

• Lie algebras
  • With basis
  • Finite dimensional

and examples for each.

[tscrim]

Yay, the first part of Lie algebras that is ready for review!!! Next up will be #16820.

---

New commits:

​9cbd3bd	Initial import from #14901 and started another example.
​16aaa72	Better implementation of Lie algebra examples.
​aae396b	Finished 2 of the 3 examples for Lie algebras.
​1544ff7	Moved lie_algebra_element.py into the example directly.
​a5d05e4	Started on finite dim lie alg with basis.
​663e1ae	Some more work to FD Lie Alg with basis.
​8d6084e	Fixes, improvements, and changes to FD Lie algebras with basis.
​100e8c4	Merge branch 'develop' into public/categories/lie_algebras-16819
​78579bd	Some more fixes and changes to FD Lie algebras with basis.
​1e1a6a7	Now we are at full coverage and working examples.

[git]

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

​cbfbb87	Merge branch 'public/categories/lie_algebras-16819' of trac.sagemath.org:sage into public/categories/lie_algebras-16819
​ed93f29	Created category for subalgebras of FD Lie algebras with basis.
​b302cc1	Added free_module abstract method.

[tscrim]

#16820 is also ready for review (so a "real" implementation that can be reviewed simultaneously).

[git]

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

​330497b	Merge branch 'public/categories/lie_algebras-16819' of trac.sagemath.org:sage into public/categories/lie_algebras-16819
​65c1f54	Removed the LiftMorphism.section map.

[darij]

+ The Killing form is defined as the matrix corresponding to the
+ action of `\mathrm{ad}_x \circ \mathrm{ad}_y` in the basis
+ of ``self``.

You mean "Killing matrix".

(Mainly posting this to get cc.)

[git]

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

​becabaa	Merge branch 'public/categories/lie_algebras-16819' of trac.sagemath.org:sage into public/categories/lie_algebras-16819
​980545e	Fixed the doc.

[git]

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

​8a6950a	Merge branch 'public/categories/lie_algebras-16819' of git://trac.sagemath.org/sage into lie1
​9b08311	a few questions to boot

[git]

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

​5a0bc7d

Answering some questions.

[git]

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

​144a5a5

Small fix for the doc.

[tscrim]

Something to note is that each of the examples are meant to be minimal.

Specifically I made the general LieAlgebras example be the algebra generated by a set of elements in order to avoid not having to worry about if the associative algebra does not have a good basis method. However this is easy enough to change if you feel strongly about it. Same for the WithBasis example.

[git]

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

​198f8a8

Added new categories to documentation.

[darij]

The lie_algebra_generators is currently a lie, so yes, it should be changed. About the names, thanks for accepting a number -- that's a good step -- but I'm still unsure why I am supposed to provide names if I provide a module, and what these names are used for. But we can talk about it in Davis, which I guess will be easier.

[darij]

Actually, I was stupid. The Lie algebra generators are fine, since LieAlgebraFromAssociative is defined to be the Lie superalgebra generated by gens, not the whole associative algebra. I should have actually read your post, if not the doc :/

On the other hand, I would expect to see the whole associative algebra implemented in a visible place. Is this in one of the followup tickets?

[tscrim]

Replying to darij:

Actually, I was stupid. The Lie algebra generators are fine, since LieAlgebraFromAssociative is defined to be the Lie superalgebra generated by gens, not the whole associative algebra. I should have actually read your post, if not the doc :/

On the other hand, I would expect to see the whole associative algebra implemented in a visible place. Is this in one of the followup tickets?

It's in #16820, but feel free to change it here if you want.

[git]

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

​f716d74	Merge branch 'public/categories/lie_algebras-16819' of git://trac.sagemath.org/sage into lie1
​6b3a623	review of src/sage/categories/examples/lie_algebras.py
​f7ba301	rest

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​3f07d05

fixing another doctest

[darij]

Please ignore ​f7ba301 "rest". That's an unfinished set of changes on the abelian Lie algebra example that causes 2 mysterious bugs.

[git]

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

​898b24a

anonymizing AbelianLieAlgebra example

[darij]

I've removed the names now, but I'm anything but sure of the resulting code's correctness; I still need to actually review it.

There is a weird doctest failure now in the lift method, but I find the fact that it used to work before even weirder. Moreover it wasn't working correctly to begin with, since the lift would end up living in a noncommutative(!) multivariate polynomial ring. The universal enveloping algebra of an abelian Lie algebra is the commutative multivariate polynomial ring. But I have no idea where in the code the construction of the universal envelope is...

[git]

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

​b0abe90

a few more fixes(?)

[darij]

Actually, my fixes probably break more stuff than they fix. Need to discuss where we are going with this after the talk.

[tscrim]

The universal_enveloping_algebra code is in the category and it calls the lift, which calls the _construct_UEA method (where the actual construction occurs). In the case of this Abelian Lie algebra, is it calls the generic code, which it returns something which thinks it's noncommutative, but the relations should make it commutative polynomial ring. Again, I was thinking minimial implementation, but it might be useful to implement this explicitly for the example...

[git]

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

​0341c9a	Merge branch 'public/categories/lie_algebras-16819' of git://trac.sagemath.org/sage into lie1
​ee7b9cd	cleaning fallout from removing the names in abelian Lie algebra example

[darij]

Question on categories/lie_algebras.py: if the (underscored) _bracket_ method is optional, shouldn't the other methods rely on bracket rather than _bracket_?

Also, should I keep removing unused imports found by pyflakes, or do they become necessary in further patches? e.g.: from sage.structure.sage_object import have_same_parent

[git]

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

​7ad90c0

trivial doc correction

[tscrim]

Strictly speaking we don't want the user to override bracket, but instead call _bracket_. So it would probably be best to make _bracket_ on the elements be a non-optional @abstract_method.

You can do the pyflakes cleanup as they can be added back in if they are needed elsewhere (they probably aren't).

[git]

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

​3084981

making _bracket_ required and bracket optional (was the other way round, which could lead to attributeerrors)

[git]

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

​b4a5b84	Merge branch 'develop' into public/categories/lie_algebras-16819
​a65bfc5	Merge branch 'develop' into public/categories/lie_algebras-16819
​64ca61d	Merge branch 'public/categories/lie_algebras-16819' of trac.sagemath.org:sage into public/categories/lie_algebras-16819
​896028a	A y for an x.
​6ca7aca	Fixing some parts of _construct_UEA.
​d35b756	Adding a default _basis_ordering and _dense_free_module
​e95d67c	More fixes to fin-dim w/ basis category.
​aabf540	Fixing coefficient division.

[git]

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

​2128184

yet another stupid question

[tscrim]

universal_enveloping_algebra automatically constructs the lift morphism and the coercion by calling the (lazy_attribute) lift, whereas _construct_UEA simply constructs the object. I did things this way so that the user doesn't have to worry about constructing the coercion, but if the user wants to not have a coercion, then one can just implement universal_enveloping_algebra.

[git]

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

​8eda104

some more changes

[darij]

Thanks for the explanation!

[tscrim]

AFAIK, we don't really have any support for non-free modules. Also I use the free module for finite dimensional with basis to do the linear algebra for the algorithms. However I don't think I need it except in that category. So I'm okay with changing the name or removing the method since in fin-dim w/ basis since I added _dense_free_module for compatibility with CombinatorialFreeModule(Element) methods.

[git]

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

​6c18d07	rename free_module as module
​c893945	review sage/categories/lie_algebras.py

[tscrim]

The is_field can be removed; that was a holdover from when I first made this a subcategory of MagmaticAlgebras. Also we should separate the test for antisymmetry from the Jacobi as this gives more information when TestSuite fails.

[git]

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

​37a1ece

a few more changes

[git]

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

​464c131

another appearance of free_module

[git]

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

​6608a18

.module and .to_vector: I still don't get them

[tscrim]

We have module and to_vector because the (fin-dim) Lie algebra (with basis) doesn't know how to do linear algebra (which requires the specialized implementations of FreeModule).

[darij]

So, these methods become important when self does not belong to FreeModules(self.base_ring()) ?

But shouldn't WithBasis automatically force it to be a FreeModules parent?

[tscrim]

We don't have a category of FreeModules (in fact, I don't really believe this should be a category), but the methods are important when doing things like finding (a basis for) the derived subalgebra.

[darij]

Uhm... don't we?

sage: FreeModules(QQ)
Category of vector spaces with basis over Rational Field
sage: FreeModules(ZZ)
Category of modules with basis over Integer Ring

Can it be that what you want are *un-indexed* free modules, i.e., ones which consist of row vectors?

[tscrim]

Duh, a module with a basis is a free module by definition...(Although that specific category is just an alias.) However in this case it is somewhat stronger of a category in that there is a distinguished basis (i.e., like sets with a marked point). Perhaps we need to lower the to_vector into the fin-dim w/ basis category (if it's not already there)?

[darij]

OK, let me be lazy/stupid and just ask concretely what methods require to_vector and module to work and would break if these were removed. What do you mean by a "free module" that a FiniteDimensionalLieAlgebraWithBasis does not satisfy?

[tscrim]

Basically anything in FiniteDimensionalLieAlgebraWithBasis since they are required to do things like echelonize a matrix constructed from a set of elements in the Lie algebra, and then pull back the rows of this matrix. Although to_vector doesn't strictly need to be a vector, but there needs to be a way to construct a list consistently to pass to a matrix. However having the to_vector gives better support for a forgetful functor if such a thing gets implemented. Although perhaps it should be _vector_ so it could be passed to to the vector() function...

[darij]

OK... Do I then understand you correctly that to_vector should return a list or tuple (of coordinates) as opposed to a family or (say) an element of NSym? And module should return a free module in which these to_vectors live?

[tscrim]

Yes and most likely yes. At least, my use cases are what I mentioned above which will come up more with #16820 and other follow-ups, and there, to_vector will return an element of module.

[git]

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

​106d75d	Merge branch 'public/categories/lie_algebras-16819' of git://trac.sagemath.org/sage into lie1
​6201720	does this make sense?

[tscrim]

I don't like stating that it is unindexed; in fact, it is typically indexed by [n]. Currently we don't have good support for other indexed instances of FreeModule, but this is something we want to change in the future. In that vein, I don't quite care for saying it is a column vector. Also I'd rather say that we pick an ordering of some basis if it exists, rather than saying if there exists one.

The reason I had an abstract method module in LieAlgebras was to say it was natural, but it was made optional for what I hope are obvious reasons.

I don't really like this paradigm of from_vector, but instead just wanted to use the basis and/or implementing a general _element_constructor_ in the ABC which handles the conversion (if such a conversion exists).

[darij]

Can I require that (for L a Lie algebra and x an element of L)

• the image x.to_vector() is an element of L.module(), and

• elements of L.module(), or -- rather -- lists of them can be put into the matrix constructor, and

• L(x.to_vector()) == x (I assume this is what you meant in the last paragraph)?

[tscrim]

Yes, no, and yes. However for fin-dim, the second one should be a yes.

The reason why I don't want the second in general is perhaps someone wants a free module version of the Lie algebra because there are extra features there, such as taking tensor products (which I guess is currently the only really distinct feature).

[git]

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

​ddc77b1	Merge branch 'public/categories/lie_algebras-16819' of git://trac.sagemath.org/sage into lie1a
​b0e36fe	changes I forgot to commit a few weeks ago

[git]

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

​42e505e	do not use pip to install mistune
​b412977	manual merge with 6.7.beta0
​de60849	I have no idea what I'm doing

[git]

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

​0c28f5f

reverting parts of previous commit with fire

[git]

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

​d952a7b	Merge branch 'public/categories/lie_algebras-16819' into 6.7.b1
​dfad36c	trac #16819 wrong inclusion into doc is corrected

[chapoton]

Doc does not build, now because of a double ref

[git]

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

​eb3b058

hopefully fix doc bug

[tscrim]

Frederic, do you remember which reference is duplicated?

[chapoton]

I was meaning nothing else than this 'gens' problem.

[tscrim]

Okay, Darij also noticed this and corrected it.

Also after some discussion, we decided to just fold this into #16820 and do it all in one block.