Opened 6 years ago

Closed 2 years ago

#16823 closed enhancement (fixed)

Implement the free Lie algebra

Reported by: tscrim Owned by: tscrim
Priority: major Milestone: sage-8.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) Commit: e27b98b282a0c86945fc155519169b77fa0b2d41
Dependencies: Stopgaps:

Description

Part of #14901. Implements the free Lie algebra in two different bases.

Change History (53)

comment:1 Changed 5 years ago by tscrim

  • Branch set to public/lie_algebras/free-16823
  • Cc sd67 added
  • Commit set to ef1741e5cc8d72692fcafcaf947be08ff6adce67
  • Dependencies changed from #16819 to #16820
  • Status changed from new to needs_review

Last 10 new commits:

e95d67cMore fixes to fin-dim w/ basis category.
c800d6cMerge branch 'public/categories/lie_algebras-16819' into public/lie_algebras/fd_structure_coeff-16820
a491bb0Some more cleanup and fixes.
aabf540Fixing coefficient division.
12074e8Merge branch 'public/categories/lie_algebras-16819' into public/lie_algebras/fd_structure_coeff-16820
7b50b7cMerge branch 'public/lie_algebras/fd_structure_coeff-16820' of trac.sagemath.org:sage into public/lie_algebras/fd_structure_coeff-16820
a9c57e2Merge branch 'public/lie_algebras/fd_structure_coeff-16820' into public/lie_algebras/free-16823
b35064dPutting out fires from refactoring of ABC's.
1c21f1bAdding doctests to most methods.
ef1741eFinishing adding doctests and getting bugs out.

comment:2 Changed 4 years ago by git

  • Commit changed from ef1741e5cc8d72692fcafcaf947be08ff6adce67 to 9d0e2114af5cd39c93387d7671e4f537d7342e6b

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

9d0e211fixed merge conflicts

comment:3 Changed 4 years ago by kdilks

  • Milestone changed from sage-6.4 to sage-6.10

New commits:

9d0e211fixed merge conflicts

comment:4 Changed 4 years ago by git

  • Commit changed from 9d0e2114af5cd39c93387d7671e4f537d7342e6b to 29b3b23c4c8ff89c145abea50f2d4329bbc6a12b

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

6815f1creview heisenberg.py again; coercion still relies on unstaged changes to module morphisms
573e074Merge branch 'public/lie_algebras/fd_structure_coeff-16820' of trac.sagemath.org:sage into public/lie_algebras/fd_structure_coeff-16820
3f9a4a1Fixing the failing doctests and making the doc build.
b9930e6some changes to standardization of names
60f743aParsing the input so that it uses the indexing set.
a02380fMerge branch 'public/lie_algebras/fd_structure_coeff-16820' in 7.0.rc1
50f4441trac #16820 correct the spelling of Cartesian
f1514bdMerge branch 'public/lie_algebras/fd_structure_coeff-16820' into 7.3.b2
7d155ecFixing trivial doctest failures.
29b3b23Merge branch 'public/lie_algebras/free-16823' of trac.sagemath.org:sage into public/lie_algebras/free-16823

comment:5 Changed 3 years ago by git

  • Commit changed from 29b3b23c4c8ff89c145abea50f2d4329bbc6a12b to 772391b350972e63c34257e20ccb406526d2b0ba

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

3e2c547Merge branch 'public/lie_algebras/fd_structure_coeff-16820' of git://trac.sagemath.org/sage into public/lie_algebras/fd_structure_coeff-16820
cf88feeChanges for the reviewer and using standard copyright.
42666d4Adding centralizer_basis method, improving to/from_vector for finite-dim Lie algebras, other fixes.
59df7ceFixing pdf docbuild in finite-dim Lie algebras w/ basis category.
ed587afImplementing ideal checks and fixing product_space.
3baf33fMerge branch 'develop' into public/lie_algebras/fd_structure_coeff-16820
c0f01dfCache is_ideal and explaining doc what is clear from the code.
fc395c8Fixing typo.
91f4688Merge branch 'public/lie_algebras/free-16823' of git://trac.sagemath.org/sage into public/lie_algebras/free-16823
772391bImprovements, fixes, and rebasing.

comment:6 Changed 3 years ago by tscrim

  • Milestone changed from sage-6.10 to sage-8.0

comment:7 Changed 3 years ago by git

  • Commit changed from 772391b350972e63c34257e20ccb406526d2b0ba to 1297bd5f5006ca9c5edf0413e030a6d857d98b22

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

2307180Merge branch 'public/lie_algebras/free-16823' of git://trac.sagemath.org/sage into lie
1297bd5doc fixes (deadlink for Munthe-Kaas in particular)

comment:8 Changed 3 years ago by darij

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 3 years ago by git

  • Commit changed from 1297bd5f5006ca9c5edf0413e030a6d857d98b22 to 9ec41ba84a72103188d6c7ff02dd26883f6401d9

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

9ec41bamore trivial fixes

comment:10 Changed 3 years ago by tscrim

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 3 years ago by darij

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 3 years ago by tscrim

Old code, back before I knew as much as I do now.

comment:13 Changed 3 years ago by git

  • Commit changed from 9ec41ba84a72103188d6c7ff02dd26883f6401d9 to 8efccc018244b2f0b01a5f12af0c07f24ae3775c

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

8efccc0Adding missing doctest and Python3 compatibility.

comment:14 Changed 3 years ago by git

  • Commit changed from 8efccc018244b2f0b01a5f12af0c07f24ae3775c to ca5b6371bee902a2747953d15483a61cbcebf2db

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

ca5b637Some minor code improvements as in comment:10.

comment:15 Changed 3 years ago by tscrim

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 3 years ago by git

  • Commit changed from ca5b6371bee902a2747953d15483a61cbcebf2db to 9de28bf9b286ee502cd847f943e4e92c38a0d426

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

9de28bfMerge branch 'public/lie_algebras/free-16823' in 8.0.b9

comment:17 Changed 3 years ago by git

  • Commit changed from 9de28bf9b286ee502cd847f943e4e92c38a0d426 to c7b203d9e9558b3869604962d04878c02d37a2d0

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

c7b203dtrac 16823 py3 iteritems

comment:18 Changed 3 years ago by chapoton

  • Dependencies #16820 deleted

comment:19 Changed 3 years ago by chapoton

  • Status changed from needs_review to needs_work

does not apply

comment:20 Changed 3 years ago by git

  • Commit changed from c7b203d9e9558b3869604962d04878c02d37a2d0 to 394d58f54c67a3737f31d4cb6095d251f8652899

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

394d58fMerge branch 'public/lie_algebras/free-16823' of git://trac.sagemath.org/sage into public/lie_algebras/free-16823

comment:21 Changed 3 years ago by tscrim

  • Status changed from needs_work to needs_review

comment:22 Changed 3 years ago by bsalisbury1

  • Cc bsalisbury1 added

comment:23 Changed 3 years ago by chapoton

doc does not build

+[dochtml] OSError: [groups   ] /home/chapoton/sage/local/lib/python2.7/site-packages/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 3 years ago by chapoton

  • Status changed from needs_review to needs_work

comment:25 follow-up: Changed 3 years ago by darij

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 higher-up 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 degree-first 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.

Last edited 3 years ago by darij (previous) (diff)

comment:26 Changed 3 years ago by git

  • Commit changed from 394d58f54c67a3737f31d4cb6095d251f8652899 to 1c32cd9b2ea89f79685517e0ed2dfaf36b0a404c

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

1c32cd9Adding back reference lost in a merge.

comment:27 Changed 3 years ago by git

  • Commit changed from 1c32cd9b2ea89f79685517e0ed2dfaf36b0a404c to a8ca231ac65bbf9ccf8b4cc316da23390d94f940

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

a8ca231Some doc improvements.

comment:28 in reply to: ↑ 25 Changed 3 years ago by tscrim

Replying to darij:

Yeah, not sure why the Stu1993 reference was removed. Merge gone wrong?

Yep, bad merge.

Doc of graded_dimension method: replace n^(k/d) by n^{k/d} (unless our parser somehow handles parentheses here).

Done.

I'm a bit surprised that _rewrite_bracket is an abstract method on class FreeLieBasis_abstract and not on some higher-up 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 if self is a Hall basis. Is this really what the rest of the code expects? Same for gens.

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 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 degree-first ordering, since otherwise it's probably illegal to restrict yourself to i 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 2 years ago by tscrim

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 2 years ago by tscrim

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 2 years ago by darij

Please do so!

comment:32 Changed 2 years ago by git

  • Commit changed from a8ca231ac65bbf9ccf8b4cc316da23390d94f940 to 63ea416948074f61516d8c93f3df1cf0ab82898c

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

48916e0Merge branch 'public/lie_algebras/free-16823' of git://trac.sagemath.org/sage into public/lie_algebras/free-16823
63ea416Added experimental warning to Hall basis.

comment:33 Changed 2 years ago by tscrim

  • Status changed from needs_work to needs_review

Done.

Note that this will trivially conflict with #24134. So if this is positively reviewed before #24134 is merged, then we will merge it in here. However, we will not do it beforehand.

Edit - Need the right ticket number.

Last edited 2 years ago by tscrim (previous) (diff)

comment:34 Changed 2 years ago by git

  • Commit changed from 63ea416948074f61516d8c93f3df1cf0ab82898c to b703250b8fbf324594a8b7f462a564cc429fc8a5

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

493d37cMerge branch 'public/lie_algebras/free-16823' in 8.1.rc2
b703250trac 16823 fix doctests

comment:35 Changed 2 years ago by chapoton

  • Status changed from needs_review to needs_work

This needs a non-fully-trivial rebase, that I did not know how to do myself.

comment:36 Changed 2 years ago by git

  • Commit changed from b703250b8fbf324594a8b7f462a564cc429fc8a5 to b18c900ade34cff2e0ef7b358f8ba294a7bc24ab

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

b18c900Merge branch 'public/lie_algebras/free-16823' of git://trac.sagemath.org/sage into public/lie_algebras/free-16823

comment:37 Changed 2 years ago by tscrim

  • Milestone changed from sage-8.0 to sage-8.2
  • Status changed from needs_work to needs_review

Wasn't too bad.

comment:38 Changed 2 years ago by git

  • Commit changed from b18c900ade34cff2e0ef7b358f8ba294a7bc24ab to bd22ffa849c1105859eb563f94a89a798949028b

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

bd22ffadoc changes; why do doctests fail?

comment:39 Changed 2 years ago by git

  • Commit changed from bd22ffa849c1105859eb563f94a89a798949028b to 0596991a54d5530bf48870c0ec824c9a721c49a1

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

0596991revert a wrong edit and document the pitfall

comment:40 Changed 2 years ago by git

  • Commit changed from 0596991a54d5530bf48870c0ec824c9a721c49a1 to 3fe36e75f4de330d81d09755f22b903984471fd9

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

0411726Merge branch 'public/lie_algebras/free-16823' of git://trac.sagemath.org/sage into freelie
3fe36e7maybe improvements

comment:41 Changed 2 years ago by git

  • Commit changed from 3fe36e75f4de330d81d09755f22b903984471fd9 to 01c9dca23deeb2a4206914ec6f64d5e74ba3c2fd

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

01c9dcareview, minus Hall basis and some technical stuff

comment:42 Changed 2 years ago by darij

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).
Last edited 2 years ago by darij (previous) (diff)

comment:43 Changed 2 years ago by git

  • Commit changed from 01c9dca23deeb2a4206914ec6f64d5e74ba3c2fd to d9e54f1472164256841acad5b54d86221b51f998

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

d9e54f1document basis key classes in free Lie algebra

comment:44 Changed 2 years ago by git

  • Commit changed from d9e54f1472164256841acad5b54d86221b51f998 to 882c861232abf0f6c50aa09effe8f4f32876dea3

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

d1ed81dMerge branch 'public/lie_algebras/free-16823' of trac.sagemath.org:sage into freelie
882c861improve the doc

comment:45 Changed 2 years ago by darij

  • Reviewers set to Darij Grinberg
  • Status changed from needs_review to positive_review

comment:46 Changed 2 years ago by tscrim

  • Milestone changed from sage-8.2 to sage-8.3

Thank you. See #25166 for a follow-up.

comment:47 Changed 2 years ago by vbraun

  • Status changed from positive_review to needs_work

PDF docs don't build

comment:48 Changed 2 years ago by git

  • Commit changed from 882c861232abf0f6c50aa09effe8f4f32876dea3 to 70cb2b75347945d9f75ac63189937bb85eda0b9b

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

b452a38Merge branch 'public/lie_algebras/free-16823' of trac.sagemath.org:sage into lie
70cb2b7fixes to doc

comment:49 Changed 2 years ago by darij

  • 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 2 years ago by tscrim

  • Status changed from positive_review to needs_review

I am testing it right now.

comment:51 Changed 2 years ago by git

  • Commit changed from 70cb2b75347945d9f75ac63189937bb85eda0b9b to e27b98b282a0c86945fc155519169b77fa0b2d41

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

4465d03Merge branch 'public/lie_algebras/free-16823' of git://trac.sagemath.org/sage into public/lie_algebras/free-16823
e27b98bFixing docbuild.

comment:52 Changed 2 years ago by tscrim

  • Status changed from needs_review to positive_review

I was able to build the pdf with these changes.

comment:53 Changed 2 years ago by vbraun

  • Branch changed from public/lie_algebras/free-16823 to e27b98b282a0c86945fc155519169b77fa0b2d41
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.