Opened 9 years ago
Closed 9 years ago
#14898 closed enhancement (fixed)
Poincaré-Birkhoff-Witt and dual bases
Reported by: | deneufchatel | Owned by: | sage-combinat |
---|---|---|---|
Priority: | minor | Milestone: | sage-5.13 |
Component: | combinatorics | Keywords: | |
Cc: | darij | Merged in: | sage-5.13.beta0 |
Authors: | Matthieu Deneufchâtel | Reviewers: | Travis Scrimshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Implements:
- the Poincaré-Birkhoff-Witt basis of the free algebra and several related functions
- the dual basis of the previous one in the shuffle algebra.
Also puts FreeAlgebra
in the category of AlgebrasWithBases
.
Attachments (9)
Change History (65)
Changed 9 years ago by
comment:1 Changed 9 years ago by
- Cc darij added
Changed 9 years ago by
comment:2 Changed 9 years ago by
- Description modified (diff)
- Summary changed from Poincaré-Birkhoff-Witt basis of the free algebra to Poincaré-Birkhoff-Witt and dual bases
Changed 9 years ago by
comment:3 Changed 9 years ago by
comment:4 Changed 9 years ago by
The reference which I would cite is Reutenauer, Free Lie algebra. The name I gave is probably confusing. Indeed, the basis is in fact the Poincaré-Birkhoff-Witt basis of the free Lie algebra whose enveloping algebra is the free algebra. Is it clearer?
comment:5 Changed 9 years ago by
Maybe instead of putting this into free_algebra.py
, you should create free_lie_algebra.py
and put it there? Anyway, if this is a basis for the Lie algebra, not for its enveloping algebra, then the documentation so far looks a little misleading. Feel free to add plenty of mathematical documentation to the code -- see the top of algebras/steenrod/steenrod_algebra.py
, for example -- so that people will understand what you've implemented.
comment:6 Changed 9 years ago by
Following Reutenauer, chapter 5, it might be a better idea to call the basis I implemented the Lyndon basis of the free algebra. It might be a good idea to start from the underlying Lie algebra but there is still much to do for Lie algebras and I don't think I am able to do it yet. Anyway, I added mathematical documentation. Hope it is enough...
Changed 9 years ago by
comment:7 Changed 9 years ago by
Right now I'm working on an initial version of Lie algebra's on #14901 (of which, I have a good amount of work done on the combinat queue and can post the [incomplete] patch on trac if desired), and it sounds like we should make sure to say in sync to not duplicate code and to have these play together.
Currently #14901 depends on #10963, so I think we're better of finishing the part on the free algebra first and making #14901 depend on this ticket.
A few things from glancing over the patches:
- Make sure all methods you add have docstrings and doctests.
- Could you fold all of the patches into a single patch? This makes it easier to review.
- Set it to "needs_review" when you're ready for someone to do the review. (which I volunteer)
- Did you work on this during Sage Days 49? If so, could you add "days49" to the keywords.
Hope everything is going well.
Thanks,
Travis
comment:8 Changed 9 years ago by
Make sure all methods you add have docstrings and doctests.
I will do it as soon as possible (currently, I am in a new flat without electricty!).
Could you fold all of the patches into a single patch? This makes it easier to review.
This is what I wanted to do, but when I followed the method described by Frédéric Chapoton here (https://groups.google.com/forum/#!topic/sage-devel/TmkXXg2UW_4) it produced a patch which only contains the modifications with respect to the previous one. What should I do ?
Set it to "needs_review" when you're ready for someone to do the review. (which I volunteer)
Ok, I didn't know who is supposed to do it!
Did you work on this during Sage Days 49? If so, could you add "days49" to the keywords.
Well, I got the informations I needed to start modifying Sage source code during these days, but I did not really work on this patch.
comment:9 Changed 9 years ago by
Hey Matthieu,
Sorry for falling behind on this.
So to fold a patch, start at "base.patch", then run
sage -hg qfold second.patch third.patch ...
(also for the record, if you want to rename your patch, you can run sage -hg qrename renamed.patch
).
Once that is done and the new version is uploaded, I'll continue the review. One other thing, if you keep the same name, please check the "replace previous file" box in the uploads.
Thanks,
Travis
comment:10 follow-up: ↓ 11 Changed 9 years ago by
Thank you for your answer. I got lost somewhere: the different patches I uploaded are on the trac server but I don't know where they actually are on my computer (and I deleted the file produced by the method of Frédéric cited above). Should I download the different patches attached to this ticket, fold them and upload the result? Since I did not change anything since the last time I uploaded something, when I try to produce a new patch, there is nothing in the diff... Sorry for these questions but I am a not-so-quick newbie! Matthieu
comment:11 in reply to: ↑ 10 Changed 9 years ago by
Replying to deneufchatel:
Thank you for your answer. I got lost somewhere: the different patches I uploaded are on the trac server but I don't know where they actually are on my computer (and I deleted the file produced by the method of Frédéric cited above).
They should be in $SAGE_ROOT/devel/sage/.hg/patches
, however you will want to run those commands in the source folders, i.e. in a subfolder of $SAGE_ROOT/devel/sage/sage/
.
Should I download the different patches attached to this ticket, fold them and upload the result?
You can if you've removed them from your queue (or installed a new version of Sage); just make sure to run sage -hg qimport first.patch ...
in the source folders.
Since I did not change anything since the last time I uploaded something, when I try to produce a new patch, there is nothing in the diff...
Because nothing has changed, there is no need for a new patch, which just records the differences.
Sorry for these questions but I am a not-so-quick newbie!
Not a problem. Hope this helps.
Best,
Travis
comment:12 Changed 9 years ago by
Ok, the different patches are in /devel/sage-test/.hg/patches, thus I should be able to fold them in one file. I tried sage -hg qnew 14898_r.patch then sage -hg qfold trac_14898.patch trac_14898_PBW.patch trac_14898_Lyndon.patch and got this answer: qfold cannot fold already applied patch trac_14898_PBW.patch What should I do? Matthieu
comment:13 Changed 9 years ago by
It seems like you are in the right folder, but just to make sure could you tell me what folder were you in?
Also the patch you want to fold everything into should be the top patch.
EXAMPLE: You have the patches first.patch
, second.patch
, third.patch
in that order in your queue and you want to fold second.patch
and third.patch
into first.patch
. You will run: sage -hg qfold second.patch third.patch
when sage -hg qtop
returns first.patch
. If it does not, you will have to run sage -hg qpop
to "pop off", i.e. unapply, those patches until you're at first.patch
.
Hope that makes sense and helps.
comment:14 Changed 9 years ago by
sage -hg qtop returns "no patches applied"! I was in the folder /devel/sage-test/sage/algebras...
comment:15 Changed 9 years ago by
Are you also doing sage -hg qtop
in the same folder? This is in conflict with your previous post where it seems like the patches are already applied. Perchance did you run sage -hg clone
with your patches applied?
comment:16 Changed 9 years ago by
You are right, I was not in the same folder since in /devel/sage-test/.hg/patches, when I run sage -hg qtop, it returns trac_14898_r.patch which is the last patch I created.
comment:17 Changed 9 years ago by
And what do I have to do about this? I tried sage -hg qnew 14898_r.patch then sage -hg qfold trac_14898.patch trac_14898_PBW.patch trac_14898_Lyndon.patch and got this answer: qfold cannot fold already applied patch trac_14898_PBW.patch
comment:18 Changed 9 years ago by
Run sage -hg qpop
in that directory until you're at the base patch you want.
comment:19 Changed 9 years ago by
The patch I want to use is called trac_14898_r.patch. [matthieu@localhost patches]$ ls series trac_14898_Lyndon.patch trac_14898_PBW.patch trac_14914_stuffle.patch status trac_14898.patch trac_14898_r.patch
I pushed it on top of the queue (but sage said that it was empty) if I am right: [matthieu@localhost patches]$ sage -hg qtop trac_14898_r.patch
But it does not want to fold the patch trac_14898_PBW.patch [matthieu@localhost patches]$ sage -hg qfold trac_14898_PBW.patch trac_14898_Lyndon.patch trac_14898.patch abort: qfold cannot fold already applied patch trac_14898_PBW.patch
Sorry for the delay, I do not have a reliable internet connection.
comment:20 Changed 9 years ago by
From your series file, trac_13898_r.patch
is the last patch that is applied, i.e. all the previous patches are also applied and why you are gettign the error message. Just to make sure we are on the same page, you should get the following
$ sage -hg qapplied trac_14898_Lyndon.patch trac_14898_PBW.patch trac_14914_stuffle.patch status trac_14898.patch trac_14898_r.patch
where $ blah
means you run command blah
from the terminal in the $SAGE_ROOT/devel/sage/sage
folder.
So what you should do is the following (the #
and anything after is a comment):
$ sage -hg qpop trac_14898_Lyndon.patch # This is the first patch applied $ sage -hg qfold trac_14898_PBW.patch trac_14898.patch trac_14898_r.patch # Fold all subsequent patches in (in order) $ sage -hg qrename trac_14898-folded-md.patch # Give the new patch a different name $ sage -hg qrefresh -e # Make sure there is a good commit message
Hope that helps,
Travis
comment:21 Changed 9 years ago by
Thank you for your help.
I followed the steps above (in the $SAGE_ROOT/devel/sage/sage folder), but when I ran
$ sage -hg qfold trac_14898_PBW.patch trac_14898.patch trac_14898_r.patch
I still got this
abort: qfold cannot fold already applied patch trac_14898_PBW.patch
comment:22 Changed 9 years ago by
What's the output when you run $ sage -hg qapplied
? Actually, just e-mail me: tscrim at ucdavis.edu, we'll do it off trac to stop some spam.
comment:23 Changed 9 years ago by
[matthieu@localhost sage]$ sage -hg qapplied
trac_14898_PBW.patch
trac_14914_stuffle.patch
trac_14898.patch
trac_14898-folded-md.patch
comment:24 Changed 9 years ago by
Run
$ sage -hg qpop trac_14898_PBW.patch $ sage -hg qfold trac_14898.patch trac_14898-folded-md.patch
That should have all of the patches folded into a single patch.
comment:25 Changed 9 years ago by
I just remembered that I have two versions of Sage on my computer and the last version (Sage 5.10), which is the version I worked with, is called sage10.
In fact,
[matthieu@localhost sage]$ sage10 -hg qapplied
answers
trac_14898_PBW.patch
I checked that I am in the right folder (sage-5.10/devel/sage/sage).
$ sage10 -hg qfold trac_14898_PBW.patch trac_14898.patch trac_14898_r.patch
answers
abort: no patches applied.
I am sorry for my mistake. What does this last information change?
comment:26 Changed 9 years ago by
[matthieu@localhost sage-5.10]$ sage10 -hg qapplied
[matthieu@localhost sage-5.10]$ sage10 -hg qunapplied
[matthieu@localhost sage-5.10]$ cat devel/sage/.hg/patches/series
trac_14898_PBW.patch
trac_14914_stuffle.patch
trac_14898.patch
trac_14898-folded-md.patch
trac_14898_r.patch
comment:27 Changed 9 years ago by
[matthieu@localhost sage-5.10]$ cd devel/sage/sage
[matthieu@localhost sage]$ sage10 -hg qapplied
trac_14914_stuffle.patch
[matthieu@localhost sage]$ sage10 -hg qunapplied
[matthieu@localhost sage]$ sage10 -hg qfold trac_14898.patch trac_14898-folded-md.patch
trac_14898_r.patch
abort: patch trac_14898.patch not in series
[matthieu@localhost sage]$ sage10 -hg qpop trac_14898_PBW.patch
abort: patch trac_14898_PBW.patch not in series
I don't know if this is important but I work with clones. I switched back to the main branch since you tell me that I have to work in the devel/sage/sage folder. But the files I modified are in the devel/sage-test/sage folder?
comment:28 Changed 9 years ago by
It is important because I think we've had a miscommunication. The devel/sage
is the current branch (which you call a clone) you are working in (it's a link), which we want it to be sage-test
; the main branch is devel/sage-main
.
comment:29 Changed 9 years ago by
Ok, so I switched back to the sage-test branch and went into the sage-test/sage folder.
I tried the commands you wanted me to try and I get something new[[BR]]
[matthieu@localhost sage]$ sage10 -b test
sage: Building and installing modified Sage library files.
Installing c_lib
scons: `install' is up to date.
Updating Cython code....
Finished compiling Cython code (time = 3.23941302299 seconds)
running install
running build
running build_py
warning: build_py: byte-compiling is disabled, skipping.
running build_ext
Executing 0 commands (using 1 thread)
Time to execute 0 commands: 0.00467801094055 seconds
Total time spent compiling C/C++ extensions: 0.139641046524 seconds.
running install_lib
warning: install_lib: byte-compiling is disabled, skipping.
running install_egg_info
Removing /home/matthieu/sage-5.10/local/lib/python2.7/site-packages/sage-0.0.0-py2.7.egg-info
Writing /home/matthieu/sage-5.10/local/lib/python2.7/site-packages/sage-0.0.0-py2.7.egg-info
real 0m5.383s
user 0m4.775s
sys 0m0.414s
[matthieu@localhost sage]$ cd ..
[matthieu@localhost sage]$ cd ..
[matthieu@localhost devel]$ ls
ext@ ext-main/ old/ sage@ sage-main/ sagenb@ sagenb-main/ sage-test/ sage-test_stuffle/
[matthieu@localhost devel]$ cd sage-test
[matthieu@localhost sage-test]$ cd sage
[matthieu@localhost sage]$ sage10 -hg qapplied
trac_14898_PBW.patch
[matthieu@localhost sage]$ sage10 -hg qunapplied
trac_14914_stuffle.patch
trac_14898.patch
trac_14898-folded-md.patch
trac_14898_r.patch
[matthieu@localhost sage]$ sage10 -hg qpop trac_14898_PBW.patch
qpop: trac_14898_PBW.patch is already at the top
[matthieu@localhost sage]$ sage10 -hg qfold trac_14898.patch trac_14898-folded-md.patch [BR]] trac_14898_r.patch
patching file sage/algebras/free_algebra.py
Hunk #1 FAILED at 954
1 out of 1 hunks FAILED -- saving rejects to file sage/algebras/free_algebra.py.rej
patching file sage/algebras/shuffle_algebra.py
Hunk #1 FAILED at 476
1 out of 1 hunks FAILED -- saving rejects to file sage/algebras/shuffle_algebra.py.rej
patch failed, unable to continue (try -v)
abort: error folding patch trac_14898.patch
comment:30 Changed 9 years ago by
It seems like the patches got out of order...post the trac_14898_r.patch
and I'll fold the results together along with some of my review changes.
After I post the folded patch, you'll want to run
$ sage -hg qpop -a # this pops off all patches $ sage -hg qunapplied $ sage -hg qremove [all patches outputted from above related to #14898] $ sage -hg qimport [my folded patch that you'll download]
Also, when you copy output text, it's best to put it in triple squiggly brackets: {{{
and }}}
. This gives it the nice formatting like what I have in this comment and you don't have to put in the [[BR]]
.
Best,
Travis
comment:31 Changed 9 years ago by
When I am in the /sage-test/.hg/patches folder,
cat trac_14898_r.patch
returns
# HG changeset patch
# Parent cfc68d83b7cc7ea7eec71175337f3712a45e0ced
and nothing more. It seems that it is empty...
comment:32 Changed 9 years ago by
Hey Matthieu,
Okay, since that patch is empty we can ignore (or remove) it. However I can't apply the patches, it seems like something is missing. Could you (re)post all of your current patches?
Thanks,
Travis
Changed 9 years ago by
Changed 9 years ago by
Changed 9 years ago by
comment:33 Changed 9 years ago by
Done!
comment:34 Changed 9 years ago by
Hmmm...could you tell me the content of each of the series file in your branches? Thanks.
comment:35 Changed 9 years ago by
Actually, better idea: send it to me in an e-mail along with the current versions of all the files you've modified for this patch, in particular free_algebra.py
. Thanks.
comment:36 Changed 9 years ago by
- Description modified (diff)
- Reviewers set to Travis Scrimshaw
- Status changed from new to needs_review
Hey Matthieu,
Here's the folded patch which:
- Makes your functions into methods of the correct classes.
- Implements coercion between the bases.
- Moves
FreeAlgebra
into the category ofAlgebrasWithBases
. - Makes every function have a doctest.
This is the patch which applies for me on sage 5.11 and 5.12.beta3. You'll probably want to delete using sage -hg qremove
all of the patches related to this ticket and then sage -hg qimport /path/to/this/file
and sage -hg qpush
.
Let me know if you're happy with my changes.
Best,
Travis
For patchbot:
Apply: trac_14898-pbw_folded-ts.patch
comment:37 Changed 9 years ago by
Thanks for your help. I have a problem that may be due to the fact that I use sage-5.10.
[matthieu@localhost patches]$ sage10 -hg /home/matthieu/Téléchargements/tr
trac_14898-pbw_folded-ts (1).patch trac_14898-pbw_folded-ts.patch
[matthieu@localhost patches]$ sage10 -hg qimport /home/matthieu/Téléchargements/trac_14898-pbw_folded-ts.patch
adding trac_14898-pbw_folded-ts.patch to series file
[matthieu@localhost patches]$ sage10 -hg qpush tr
trac_14898-pbw_folded-ts.patch trac_14914_stuffle.patch
[matthieu@localhost patches]$ sage10 -hg qpush trac_14898-pbw_folded-ts.patch
applying trac_14898-pbw_folded-ts.patch
patching file sage/combinat/words/word.py
Hunk #2 FAILED at 43
Hunk #4 FAILED at 182
2 out of 4 hunks FAILED -- saving rejects to file sage/combinat/words/word.py.rej
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir
errors during apply, please fix and refresh trac_14898-pbw_folded-ts.patch
Should I install sage-5.x?
comment:38 Changed 9 years ago by
I had a look at the patch you uploaded without applying it and it is fine with me.
comment:39 Changed 9 years ago by
Since you're getting those rejects in word.py
, it should be because you're using 5.10. Try it with 5.11, I believe it should apply there.
comment:40 Changed 9 years ago by
So I compiled sage-5.11 and tried to apply your patch but I still have a problem:
[matthieu@localhost sage-5.11]$ ./sage -hg qimport /home/matthieu/Téléchargements/trac_14898-pbw_folded-ts.patch
adding trac_14898-pbw_folded-ts.patch to series file
[matthieu@localhost sage-5.11]$ sage11 -hg qpush trac_14898-pbw_folded-ts.patch
applying trac_14898-pbw_folded-ts.patch
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir
errors during apply, please fix and refresh trac_14898-pbw_folded-ts.patch
Is there a "log file"?
comment:41 Changed 9 years ago by
Finally, I think it works but I get lost: the actual branch I work with is sage-test
[matthieu@localhost sage-main]$ sage11 -branch
test
but the files modified by the application of the patch are the file of the main branch
[matthieu@localhost sage-main]$ cat sage/algebras/free_algebra.py
##### Tests #####
# Check that expansion \circ to_pbw is the identity #
#PBW = PBWBasisOfFreeAlgebra(QQ,2)
#to_pbw(expansion(PBW.basis()[PBW._mon.1 * PBW._mon.0]))==PBW.basis()[PBW._mon.1 * PBW._mon.0]
#sage: M.<x0,x1>=FreeMonoid(2)
#sage: PBW=PBWBasisOfFreeAlgebra(QQ,2)
#sage: L=[]
#sage: for i in range(6):
#....: for j in Words(M.gens(),i).list():
#....: L.append(to_monoid_element(j))
#....:
#sage: for i in L:
#....: to_pbw(expansion(PBW.basis()[i]))==PBW.basis()[i]
#....:
[matthieu@localhost sage-main]$ less sage/algebras/free_algebra.py
whereas I would expect the files in sage-test to have been changed...
comment:42 Changed 9 years ago by
Does this patch require the patches of Sage Combinat to be installed?
When I (successfully) apply the patch, I get an error when I rebuild the library:
File "/home/matthieu/sage-5.11/local/lib/python2.7/site-packages/sage/combinat/permutation.py", line 211, in <module>
from sage.combinat.composition import Composition
ImportError: cannot import name Composition
comment:43 Changed 9 years ago by
- Description modified (diff)
As for why the files in sage-main
were modified, did you run the sage -hg qimport
in the sage-main
folder?
Hmmm....strange. I'm guessing my import statements are causing a circular dependency without #14772? (I did some reworking of the import statements and I recall they were very fickle.) Try moving the added import statements into the functions where we actually call the imported object(s).
If that doesn't work, perhaps it is worthwhile (IMO, it is even if the above does work) to install sage-combinat by doing the following:
$ sage -b main $ cd /to/sage-main $ sage -hg qpop -a # Because cloning will take the current changes to any patches that are applied $ sage -combinat install # This will take a few minutes $ cd /to/sage-combinat $ sage -hg qpop trac_14898-pbw_folded-ts.patch # It's in the combinat queue already
Best,
Travis
PS - Sorry for the delay
comment:44 Changed 9 years ago by
It works. Thanks.
Matthieu
comment:45 Changed 9 years ago by
Great!
However here's a new version of the patch which now has the multiplication agreeing between the monomials and the PBW basis. If you're happy with the patch after my changes, you can go ahead and set this to positive review.
Best,
Travis
comment:46 Changed 9 years ago by
I don't agree with your implementation of the multiplication. If u and v are two words, P_u P_v = P_{uv} iff the Lyndon factorization of uv is (u,v); if this is not the case, you have to look at the Lyndon factorization of uv and it is not so straightforward and this is why I did not add it so far.
Am I right?
comment:47 Changed 9 years ago by
The statement in my last comment is false. But in most cases, P_u P_v \neq P_{uv} (it is true if v is a Lyndon word such that \ell_n \geq v where \ell_n is the last factor of the Lyndon factorization of u).
comment:48 Changed 9 years ago by
Because it was driving me slightly nuts (because the basis is a free mult. basis indexed by Lyndon words), I've changed the output of PBW[y*x]
to PBW[y]*PBW[x]
. Is there anything else that you think should be changed Matthieu?
For patchbot:
Apply: trac_14898-pbw_folded-ts.patch
comment:49 Changed 9 years ago by
I also marked one of the tests in _repr_term()
as # indirect doctest
so sage -coverage
(and other people) knows it's been doctest.
For patchbot:
Apply: trac_14898-pbw_folded-ts.patch
comment:50 Changed 9 years ago by
I think that your last modification addresses the problem of the product that I was talking about; you did not make any other "theoretical" modification if I am right. In that case, I think I am ok.
Matthieu
comment:51 Changed 9 years ago by
Yep, no changes except the output format. Then I'll give you the honor of setting this to a positive review.
Best,
Travis
comment:52 Changed 9 years ago by
- Status changed from needs_review to positive_review
comment:53 Changed 9 years ago by
- Status changed from positive_review to needs_work
There is a doctest failure:
sage -t devel/sage/sage/rings/ring.pyx ********************************************************************** File "devel/sage/sage/rings/ring.pyx", line 403, in sage.rings.ring.Ring.category Failed example: FreeAlgebra(QQ, 3, 'x').category() # todo: use a ring which is not an algebra! Expected: Category of algebras over Rational Field Got: Category of algebras with basis over Rational Field **********************************************************************
Changed 9 years ago by
comment:54 Changed 9 years ago by
- Status changed from needs_work to positive_review
Fixed.
For patchbot:
Apply: trac_14898-pbw_folded-ts.patch
comment:55 Changed 9 years ago by
- Milestone changed from sage-5.12 to sage-5.13
comment:56 Changed 9 years ago by
- Merged in set to sage-5.13.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
What exactly is the Poincaré-Birkhoff-Witt basis of a free algebra? Free algebras have exponential growth, and PBW bases have polynomial growth, so I don't see how a free algebra can have a PBW basis.
I may very well be missing something, but I think you need to explain what this term means in this context, and probably provide a reference.