Free nilpotent Lie algebras

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

Depends on #26074

CC: @tscrim

Component: algebra

Keywords: Lie algebras, nilpotent

Author: Eero Hakavuori

Branch/Commit: 664fbec

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/26076

[ehaka]

comment:1

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

[ehaka]

Commit: cb8a103

[ehaka]

Author: Eero Hakavuori

[ehaka]

comment:2

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

[ehaka]

Branch: u/gh-ehaka/free_nilpotent_lie_algebras-26076

[sagetrac-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

[sagetrac-git]

Changed commit from cb8a103 to 31fa53a

[sagetrac-git]

Changed commit from 31fa53a to b7c8a2a

[sagetrac-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

[sagetrac-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

[sagetrac-git]

Changed commit from b7c8a2a to 09b54f5

[sagetrac-git]

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

b70bebd

doctest fix for changed category printing

[sagetrac-git]

Changed commit from 09b54f5 to b70bebd

[tscrim]

Changed commit from b70bebd to a60ef68

[tscrim]

Changed branch from u/gh-ehaka/free_nilpotent_lie_algebras-26076 to public/lie_algebras/free_nilpotent-26076

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:7

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.

[sagetrac-git]

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

664fbec

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

[sagetrac-git]

Changed commit from a60ef68 to 664fbec

[tscrim]

comment:10

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

[ehaka]

comment:11

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!

[vbraun]

Changed branch from public/lie_algebras/free_nilpotent-26076 to 664fbec