Free nilpotent Lie algebras

[gh-ehaka]

Implement the construction of free nilpotent Lie algebras, i.e. Lie algebras where the only additional relations among the brackets are that iterated brackets longer than the nilpotency step must vanish.

[gh-ehaka]

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

[gh-ehaka]

The adapted version of the free nilpotent Lie algebra construction is in the commits. I removed the parameter free from the method sage.algebras.lie_algebras.nilpotent_lie_algebra.NilpotentLieAlgebra of #26074, as the parameter seemed to be redundant.

---

New commits:

​19c27eb	New subcategories of Lie algebras (nilpotent, graded, stratified) and a base class for nilpotent Lie algebras
​f58cddd	Implementation of the construction of free nilpotent Lie algebras
​cb8a103	Changed doctests to use free nilpotent Lie algebras as more natural examples of graded or stratified Lie algebras

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​158bfdb	Fix to product_space() for when L is not a true subalgebra of A.
​293901e	Fixed a test for _test_generated_by_degree_one().
​8658e9d	Fixing print order for fin-dim nilpotent Lie algebras with basis.
​726639f	Some last little cleanup.
​8b3c585	A better failure example for _test_generated_by_degree_one and some more doc.
​a1e1ace	Refactored nilpotent Lie algebra constructor into Lie algebra constructor
​14fcd30	Deduction rule for the fact that finite dimensional stratified Lie algebras are nilpotent
​f1a0b1e	Docstring fix for indexing of grading of a stratification
​4d4bdf6	Merge remote-tracking branch 'trac/public/lie_algebras/base_class_nilponent-26074' into free_nilpotent_lie_algebras
​31fa53a	Added free nilpotent Lie algebras to LieAlgebra constructor

[git]

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

​a3dccfd	Merge branch 'public/lie_algebras/base_class_nilponent-26074' of git://trac.sagemath.org/sage into public/lie_algebras/base_class_nilponent-26074
​0fa41ad	Fixing doctests, making category an arugment, and other small tweaks.
​53a10be	Adding an extra doctest and fix for the category option.
​d7077cd	Merge remote-tracking branch 'trac/public/lie_algebras/base_class_nilponent-26074' into u/gh-ehaka/free_nilpotent_lie_algebras-26076
​b7c8a2a	Fixed category parameter of initialization of free nilpotent Lie algebra

[git]

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

​a5ec3ad	Moving the axioms around for better printing.
​09b54f5	Merge remote-tracking branch 'trac/public/lie_algebras/base_class_nilponent-26074' into u/gh-ehaka/free_nilpotent_lie_algebras-26076

[git]

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

​b70bebd

doctest fix for changed category printing

[tscrim]

I have made some documentation tweaks and a little better normalization and testing of the input. I have also obtained a speedup of the creation of the free nilpotent lie algebra (although it costs a big more in terms of memory usage by having to hold 2 copies of all of the Lyndon word tuples in memory):

%sage: %time L = LieAlgebra(QQ, 3, step=3)
CPU times: user 48 ms, sys: 4 ms, total: 52 ms
Wall time: 50.3 ms
sage: %time L = LieAlgebra(QQ, 5, step=3)
CPU times: user 16 ms, sys: 0 ns, total: 16 ms
Wall time: 12.7 ms
sage: %time L = LieAlgebra(QQ, 5, step=4)
CPU times: user 92 ms, sys: 0 ns, total: 92 ms
Wall time: 88.3 ms
sage: %time L = LieAlgebra(QQ, 5, step=5)
CPU times: user 1.45 s, sys: 28 ms, total: 1.48 s
Wall time: 1.47 s
sage: %time L = LieAlgebra(QQ, 6, step=3)
CPU times: user 16 ms, sys: 8 ms, total: 24 ms
Wall time: 21 ms
sage: %time L = LieAlgebra(QQ, 6, step=4)
CPU times: user 368 ms, sys: 36 ms, total: 404 ms
Wall time: 356 ms
sage: %time L = LieAlgebra(QQ, 6, step=5)
CPU times: user 8.83 s, sys: 148 ms, total: 8.98 s
Wall time: 8.97 s

vs prev

sage: %time L = LieAlgebra(QQ, 3, step=3)
CPU times: user 44 ms, sys: 8 ms, total: 52 ms
Wall time: 49.3 ms
sage: %time L = LieAlgebra(QQ, 5, step=3)
CPU times: user 12 ms, sys: 4 ms, total: 16 ms
Wall time: 15.5 ms
sage: %time L = LieAlgebra(QQ, 5, step=4)
CPU times: user 144 ms, sys: 12 ms, total: 156 ms
Wall time: 142 ms
sage: %time L = LieAlgebra(QQ, 5, step=5)
CPU times: user 2.29 s, sys: 24 ms, total: 2.32 s
Wall time: 2.31 s
sage: %time L = LieAlgebra(QQ, 6, step=3)
CPU times: user 24 ms, sys: 0 ns, total: 24 ms
Wall time: 25.2 ms
sage: %time L = LieAlgebra(QQ, 6, step=4)
CPU times: user 536 ms, sys: 28 ms, total: 564 ms
Wall time: 533 ms
sage: %time L = LieAlgebra(QQ, 6, step=5)
CPU times: user 13.7 s, sys: 204 ms, total: 13.9 s
Wall time: 13.9 s

If my changes are good, then positive review.

---

New commits:

​8f7aac5	Added missing files to documentation, removed non-existent one that was causing docbuild to fail
​120c02a	Some trivial fixes.
​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.

[git]

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

​664fbec

Changing r=10 as cutoff to requiring a linear ordering.

[tscrim]

I also changed the r = 10 case to not be accepted for the index naming because you are using 1-based indices.

[gh-ehaka]

Replying to tscrim:

I have made some documentation tweaks and a little better normalization and testing of the input.

All good changes.

I have also obtained a speedup of the creation of the free nilpotent lie algebra (although it costs a big more in terms of memory usage by having to hold 2 copies of all of the Lyndon word tuples in memory)

A ~30% speedup in the expensive cases, very impressive!

Replying to tscrim:

I also changed the r = 10 case to not be accepted for the index naming because you are using 1-based indices.

I left the cutoff at 11 because I figured technically a zero does not cause ambiguity since it must always be attached to a 10. For aesthetic and convenience the cutoff at 10 is much better though.

The changes all look very good to me, thanks for the improvements!