Opened 8 years ago
Closed 4 years ago
#16823 closed enhancement (fixed)
Implement the free Lie algebra
Reported by:  tscrim  Owned by:  tscrim 

Priority:  major  Milestone:  sage8.3 
Component:  algebra  Keywords:  lie algebras 
Cc:  sd67, bsalisbury1  Merged in:  
Authors:  Travis Scrimshaw  Reviewers:  Darij Grinberg 
Report Upstream:  N/A  Work issues:  
Branch:  e27b98b (Commits, GitHub, GitLab)  Commit:  e27b98b282a0c86945fc155519169b77fa0b2d41 
Dependencies:  Stopgaps: 
Description
Part of #14901. Implements the free Lie algebra in two different bases.
Change History (53)
comment:1 Changed 7 years ago by
 Branch set to public/lie_algebras/free16823
 Cc sd67 added
 Commit set to ef1741e5cc8d72692fcafcaf947be08ff6adce67
 Dependencies changed from #16819 to #16820
 Status changed from new to needs_review
comment:2 Changed 7 years ago by
 Commit changed from ef1741e5cc8d72692fcafcaf947be08ff6adce67 to 9d0e2114af5cd39c93387d7671e4f537d7342e6b
Branch pushed to git repo; I updated commit sha1. New commits:
9d0e211  fixed merge conflicts

comment:3 Changed 7 years ago by
 Milestone changed from sage6.4 to sage6.10
New commits:
9d0e211  fixed merge conflicts

comment:4 Changed 6 years ago by
 Commit changed from 9d0e2114af5cd39c93387d7671e4f537d7342e6b to 29b3b23c4c8ff89c145abea50f2d4329bbc6a12b
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
6815f1c  review heisenberg.py again; coercion still relies on unstaged changes to module morphisms

573e074  Merge branch 'public/lie_algebras/fd_structure_coeff16820' of trac.sagemath.org:sage into public/lie_algebras/fd_structure_coeff16820

3f9a4a1  Fixing the failing doctests and making the doc build.

b9930e6  some changes to standardization of names

60f743a  Parsing the input so that it uses the indexing set.

a02380f  Merge branch 'public/lie_algebras/fd_structure_coeff16820' in 7.0.rc1

50f4441  trac #16820 correct the spelling of Cartesian

f1514bd  Merge branch 'public/lie_algebras/fd_structure_coeff16820' into 7.3.b2

7d155ec  Fixing trivial doctest failures.

29b3b23  Merge branch 'public/lie_algebras/free16823' of trac.sagemath.org:sage into public/lie_algebras/free16823

comment:5 Changed 5 years ago by
 Commit changed from 29b3b23c4c8ff89c145abea50f2d4329bbc6a12b to 772391b350972e63c34257e20ccb406526d2b0ba
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
3e2c547  Merge branch 'public/lie_algebras/fd_structure_coeff16820' of git://trac.sagemath.org/sage into public/lie_algebras/fd_structure_coeff16820

cf88fee  Changes for the reviewer and using standard copyright.

42666d4  Adding centralizer_basis method, improving to/from_vector for finitedim Lie algebras, other fixes.

59df7ce  Fixing pdf docbuild in finitedim Lie algebras w/ basis category.

ed587af  Implementing ideal checks and fixing product_space.

3baf33f  Merge branch 'develop' into public/lie_algebras/fd_structure_coeff16820

c0f01df  Cache is_ideal and explaining doc what is clear from the code.

fc395c8  Fixing typo.

91f4688  Merge branch 'public/lie_algebras/free16823' of git://trac.sagemath.org/sage into public/lie_algebras/free16823

772391b  Improvements, fixes, and rebasing.

comment:6 Changed 5 years ago by
 Milestone changed from sage6.10 to sage8.0
comment:7 Changed 5 years ago by
 Commit changed from 772391b350972e63c34257e20ccb406526d2b0ba to 1297bd5f5006ca9c5edf0413e030a6d857d98b22
comment:8 Changed 5 years ago by
Travis: What Hall basis is this? Are you following a specific source? There are many different Hall bases, and the simplest one (I believe using the lexicographic order) is just the Lyndon basis IIRC; hence the question.
comment:9 Changed 5 years ago by
 Commit changed from 1297bd5f5006ca9c5edf0413e030a6d857d98b22 to 9ec41ba84a72103188d6c7ff02dd26883f6401d9
Branch pushed to git repo; I updated commit sha1. New commits:
9ec41ba  more trivial fixes

comment:10 Changed 5 years ago by
IIRC, I followed [MKO1998], which I thought was based on Hall's original construction, but I can't seem to find that reference. I am not tied to the name, and another name might be better if someone wants to implement the other 2 "natural" Hall set based bases. It's up to you.
Also, we should get rid of this filter:
cf = filter(lambda x: x != 0, c) +cf = [x for x in c if x != 0]
Just below that, we could also do:
 nonzero_indices = []  for i in range(len(c)):  if c[i] != 0:  nonzero_indices.append(i) + nonzero_indices = [i for i,val in enumerate(c) if val != 0]
I can make these changes if you want.
comment:11 Changed 5 years ago by
Would be great if you did them. I squinted with some unease at the filter as well, but I thought you had a rationale for using it :)
comment:12 Changed 5 years ago by
Old code, back before I knew as much as I do now.
comment:13 Changed 5 years ago by
 Commit changed from 9ec41ba84a72103188d6c7ff02dd26883f6401d9 to 8efccc018244b2f0b01a5f12af0c07f24ae3775c
Branch pushed to git repo; I updated commit sha1. New commits:
8efccc0  Adding missing doctest and Python3 compatibility.

comment:14 Changed 5 years ago by
 Commit changed from 8efccc018244b2f0b01a5f12af0c07f24ae3775c to ca5b6371bee902a2747953d15483a61cbcebf2db
Branch pushed to git repo; I updated commit sha1. New commits:
ca5b637  Some minor code improvements as in comment:10.

comment:15 Changed 5 years ago by
This makes the changes I noted in comment:10, as well as making it Python3 compatible and full doctest coverage (I missed one hidden method).
comment:16 Changed 5 years ago by
 Commit changed from ca5b6371bee902a2747953d15483a61cbcebf2db to 9de28bf9b286ee502cd847f943e4e92c38a0d426
Branch pushed to git repo; I updated commit sha1. New commits:
9de28bf  Merge branch 'public/lie_algebras/free16823' in 8.0.b9

comment:17 Changed 5 years ago by
 Commit changed from 9de28bf9b286ee502cd847f943e4e92c38a0d426 to c7b203d9e9558b3869604962d04878c02d37a2d0
Branch pushed to git repo; I updated commit sha1. New commits:
c7b203d  trac 16823 py3 iteritems

comment:18 Changed 5 years ago by
 Dependencies #16820 deleted
comment:20 Changed 5 years ago by
 Commit changed from c7b203d9e9558b3869604962d04878c02d37a2d0 to 394d58f54c67a3737f31d4cb6095d251f8652899
Branch pushed to git repo; I updated commit sha1. New commits:
394d58f  Merge branch 'public/lie_algebras/free16823' of git://trac.sagemath.org/sage into public/lie_algebras/free16823

comment:21 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:22 Changed 5 years ago by
 Cc bsalisbury1 added
comment:23 Changed 5 years ago by
doc does not build
+[dochtml] OSError: [groups ] /home/chapoton/sage/local/lib/python2.7/sitepackages/sage/groups/matrix_gps/finitely_generated.py:docstring of sage.groups.matrix_gps.finitely_generated.FinitelyGeneratedMatrixGroup_gap.invariant_generators:59: WARNING: citation not found: Stu1993
comment:24 Changed 5 years ago by
 Status changed from needs_review to needs_work
comment:25 followup: ↓ 28 Changed 5 years ago by
Yeah, not sure why the Stu1993 reference was removed. Merge gone wrong?
Doc of graded_dimension
method: replace n^(k/d)
by n^{k/d}
(unless our parser somehow handles parentheses here).
I'm a bit surprised that _rewrite_bracket
is an abstract method on class FreeLieBasis_abstract
and not on some higherup class for arbitrary Lie algebras with ordered family bases. But you know better how the class hierarchy should work.
Based on my arguably naive read of the lie_algebra_generators
method, it constructs the generators in the Lyndon bases, even if self
is a Hall basis. Is this really what the rest of the code expects? Same for gens
.
Where did you get the definition of a Hall set from? [MKO...]? I cannot really match it with Reutenauer's (Section 5 in http://www.lacim.uqam.ca/~christo/Publi%C3%A9s/2003/free%20Lie%20algebras.pdf ); for example, your b._left <= a
seems to contradict Reutenauer's rule, which is more like a._right >= b
. More importantly, what is the ordering on the free magma that you are using? Even [MKO...] leaves this undecided ("Elements of the same length are ordered internally as we please"). At the very least it seems to be a degreefirst ordering, since otherwise it's probably illegal to restrict yourself to i in range(1, (k+1) // 2)
.
Also, what is the mathematical significance of the GradedLieBracket
class? Are they something like the free magma? Things like this should probably be a lot more transparent, ideally with a way for the user to specify the ordering on the free magma.
comment:26 Changed 5 years ago by
 Commit changed from 394d58f54c67a3737f31d4cb6095d251f8652899 to 1c32cd9b2ea89f79685517e0ed2dfaf36b0a404c
Branch pushed to git repo; I updated commit sha1. New commits:
1c32cd9  Adding back reference lost in a merge.

comment:27 Changed 5 years ago by
 Commit changed from 1c32cd9b2ea89f79685517e0ed2dfaf36b0a404c to a8ca231ac65bbf9ccf8b4cc316da23390d94f940
Branch pushed to git repo; I updated commit sha1. New commits:
a8ca231  Some doc improvements.

comment:28 in reply to: ↑ 25 Changed 5 years ago by
Replying to darij:
Yeah, not sure why the Stu1993 reference was removed. Merge gone wrong?
Yep, bad merge.
Doc of
graded_dimension
method: replacen^(k/d)
byn^{k/d}
(unless our parser somehow handles parentheses here).
Done.
I'm a bit surprised that
_rewrite_bracket
is an abstract method on classFreeLieBasis_abstract
and not on some higherup class for arbitrary Lie algebras with ordered family bases. But you know better how the class hierarchy should work.
It makes no sense anywhere else as this is the only class that has elements stored as trees of Lie brackets.
Based on my arguably naive read of the
lie_algebra_generators
method, it constructs the generators in the Lyndon bases, even ifself
is a Hall basis. Is this really what the rest of the code expects? Same forgens
.
Not quite. This is a shortcut for creating elements of the free Lie algebra without explicitly specifying the basis (think SymmetricFunctions
). If you create the Hall basis, which is a separate object, then you have a different lie_algebra_generators
.
Where did you get the definition of a Hall set from? [MKO...]? I cannot really match it with Reutenauer's (Section 5 in http://www.lacim.uqam.ca/~christo/Publi%C3%A9s/2003/free%20Lie%20algebras.pdf ); for example, your
b._left <= a
seems to contradict Reutenauer's rule, which is more likea._right >= b
. More importantly, what is the ordering on the free magma that you are using? Even [MKO...] leaves this undecided ("Elements of the same length are ordered internally as we please"). At the very least it seems to be a degreefirst ordering, since otherwise it's probably illegal to restrict yourself toi in range(1, (k+1) // 2)
.
For the most part, it was far too long ago that I wrote this that I do not really remember. I am pretty sure I used [MKO...], but I can't say for certain. However, length := degree in this construction. Feel free to change what you want, but I know this works. IIRC, it agrees with the monomials in [MKO...]. As you point out, there are a number of different Hall sets (well, really I think there are 4 by fundamentally playing two types of left vs right games), and the code seems very sensitive when things are not correct (infinite recursions).
Also, what is the mathematical significance of the
GradedLieBracket
class? Are they something like the free magma? Things like this should probably be a lot more transparent, ideally with a way for the user to specify the ordering on the free magma.
It is precisely what it says it is: it is a Lie bracket with a grading. In particular, we use the natural grading of generators being degree 1. However, it is basically a helper class used to construct the basis elements and not really meant to be manipulated by the user.
comment:29 Changed 5 years ago by
Bringing over the side discussion from #24144: If you're worried about the Hall basis, then how about I mark it as experimental
(yes, there something for that similar to deprecation
). I recall doing a fair bit of testing with it, so I have some confidence it is solid. However, I am willing to give somewhat to get some implementation of the free Lie algebra into Sage. Moreover, if there are serious problems, we can always fix them on later tickets (Sage reviews do not have to be as thorough as math reviews :)
).
comment:30 Changed 5 years ago by
So if you're willing to review everything else now and simply mark the Hall as experimental (unless you find a bug if you do look at it), then I can rebase the ticket with that added in.
comment:31 Changed 5 years ago by
Please do so!
comment:32 Changed 5 years ago by
 Commit changed from a8ca231ac65bbf9ccf8b4cc316da23390d94f940 to 63ea416948074f61516d8c93f3df1cf0ab82898c
comment:33 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:34 Changed 4 years ago by
 Commit changed from 63ea416948074f61516d8c93f3df1cf0ab82898c to b703250b8fbf324594a8b7f462a564cc429fc8a5
comment:35 Changed 4 years ago by
 Status changed from needs_review to needs_work
This needs a nonfullytrivial rebase, that I did not know how to do myself.
comment:36 Changed 4 years ago by
 Commit changed from b703250b8fbf324594a8b7f462a564cc429fc8a5 to b18c900ade34cff2e0ef7b358f8ba294a7bc24ab
Branch pushed to git repo; I updated commit sha1. New commits:
b18c900  Merge branch 'public/lie_algebras/free16823' of git://trac.sagemath.org/sage into public/lie_algebras/free16823

comment:37 Changed 4 years ago by
 Milestone changed from sage8.0 to sage8.2
 Status changed from needs_work to needs_review
Wasn't too bad.
comment:38 Changed 4 years ago by
 Commit changed from b18c900ade34cff2e0ef7b358f8ba294a7bc24ab to bd22ffa849c1105859eb563f94a89a798949028b
Branch pushed to git repo; I updated commit sha1. New commits:
bd22ffa  doc changes; why do doctests fail?

comment:39 Changed 4 years ago by
 Commit changed from bd22ffa849c1105859eb563f94a89a798949028b to 0596991a54d5530bf48870c0ec824c9a721c49a1
Branch pushed to git repo; I updated commit sha1. New commits:
0596991  revert a wrong edit and document the pitfall

comment:40 Changed 4 years ago by
 Commit changed from 0596991a54d5530bf48870c0ec824c9a721c49a1 to 3fe36e75f4de330d81d09755f22b903984471fd9
comment:41 Changed 4 years ago by
 Commit changed from 3fe36e75f4de330d81d09755f22b903984471fd9 to 01c9dca23deeb2a4206914ec6f64d5e74ba3c2fd
Branch pushed to git repo; I updated commit sha1. New commits:
01c9dca  review, minus Hall basis and some technical stuff

comment:42 Changed 4 years ago by
TODO:
 Review Hall basis. (Which Hall set and which ordering does it use?)
 Extend Lyndon and Hall basis to arbitrary orderings perhaps. (Next ticket.)
 If you don't like my doc for the helper classes, please suggest better alternatives. Doc is highly necessary there. These classes *are* exposed: they are the parents for basis indices, and so will be relevant to anyone defining e.g. maps out of a free Lie algebra. And their use is sufficiently complex that a grep doesn't answer the questions (this is where I got stuck trying to review the ticket months ago).
comment:43 Changed 4 years ago by
 Commit changed from 01c9dca23deeb2a4206914ec6f64d5e74ba3c2fd to d9e54f1472164256841acad5b54d86221b51f998
Branch pushed to git repo; I updated commit sha1. New commits:
d9e54f1  document basis key classes in free Lie algebra

comment:44 Changed 4 years ago by
 Commit changed from d9e54f1472164256841acad5b54d86221b51f998 to 882c861232abf0f6c50aa09effe8f4f32876dea3
comment:45 Changed 4 years ago by
 Reviewers set to Darij Grinberg
 Status changed from needs_review to positive_review
comment:46 Changed 4 years ago by
 Milestone changed from sage8.2 to sage8.3
Thank you. See #25166 for a followup.
comment:47 Changed 4 years ago by
 Status changed from positive_review to needs_work
PDF docs don't build
comment:48 Changed 4 years ago by
 Commit changed from 882c861232abf0f6c50aa09effe8f4f32876dea3 to 70cb2b75347945d9f75ac63189937bb85eda0b9b
comment:49 Changed 4 years ago by
 Status changed from needs_work to positive_review
Better now? I regret I can't test PDF output on the university machine where I have sage installed (latexmk is missing).
comment:50 Changed 4 years ago by
 Status changed from positive_review to needs_review
I am testing it right now.
comment:51 Changed 4 years ago by
 Commit changed from 70cb2b75347945d9f75ac63189937bb85eda0b9b to e27b98b282a0c86945fc155519169b77fa0b2d41
comment:52 Changed 4 years ago by
 Status changed from needs_review to positive_review
I was able to build the pdf with these changes.
comment:53 Changed 4 years ago by
 Branch changed from public/lie_algebras/free16823 to e27b98b282a0c86945fc155519169b77fa0b2d41
 Resolution set to fixed
 Status changed from positive_review to closed
Last 10 new commits:
More fixes to findim w/ basis category.
Merge branch 'public/categories/lie_algebras16819' into public/lie_algebras/fd_structure_coeff16820
Some more cleanup and fixes.
Fixing coefficient division.
Merge branch 'public/categories/lie_algebras16819' into public/lie_algebras/fd_structure_coeff16820
Merge branch 'public/lie_algebras/fd_structure_coeff16820' of trac.sagemath.org:sage into public/lie_algebras/fd_structure_coeff16820
Merge branch 'public/lie_algebras/fd_structure_coeff16820' into public/lie_algebras/free16823
Putting out fires from refactoring of ABC's.
Adding doctests to most methods.
Finishing adding doctests and getting bugs out.