Opened 9 years ago

Closed 9 years ago

# Poincaré-Birkhoff-Witt and dual bases

Reported by: Owned by: deneufchatel sage-combinat minor sage-5.13 combinatorics darij sage-5.13.beta0 Matthieu Deneufchâtel Travis Scrimshaw N/A

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.

### comment:2 Changed 9 years ago by deneufchatel

• Description modified (diff)
• Summary changed from Poincaré-Birkhoff-Witt basis of the free algebra to Poincaré-Birkhoff-Witt and dual bases

### comment:3 Changed 9 years ago by jhpalmieri

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.

### comment:4 Changed 9 years ago by deneufchatel

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 jhpalmieri

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 deneufchatel

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

### comment:7 Changed 9 years ago by tscrim

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 deneufchatel

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 tscrim

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 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). 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 tscrim

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

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 deneufchatel

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 tscrim

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 deneufchatel

sage -hg qtop returns "no patches applied"! I was in the folder /devel/sage-test/sage/algebras...

### comment:15 Changed 9 years ago by tscrim

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 deneufchatel

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 deneufchatel

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 tscrim

Run sage -hg qpop in that directory until you're at the base patch you want.

### comment:19 Changed 9 years ago by deneufchatel

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 tscrim 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 deneufchatel

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

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. Last edited 9 years ago by tscrim (previous) (diff) ### comment:23 Changed 9 years ago by deneufchatel [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 tscrim

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 deneufchatel

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 deneufchatel

[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 deneufchatel [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 tscrim

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.

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

### comment:29 Changed 9 years ago by deneufchatel

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 tscrim

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 deneufchatel

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 tscrim

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

trac_14898.patch

Done!

### comment:34 Changed 9 years ago by tscrim

Hmmm...could you tell me the content of each of the series file in your branches? Thanks.

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

### comment:35 Changed 9 years ago by tscrim

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.

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

### comment:36 Changed 9 years ago by tscrim

• 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 of AlgebrasWithBases.
• 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 deneufchatel

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

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

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 tscrim

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.

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

### comment:40 Changed 9 years ago by deneufchatel

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 deneufchatel

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 deneufchatel 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 tscrim • 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 deneufchatel

It works. Thanks.
Matthieu

### comment:45 Changed 9 years ago by tscrim

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 deneufchatel

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 deneufchatel

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 tscrim

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 tscrim

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 deneufchatel

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 tscrim

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 deneufchatel

• Status changed from needs_review to positive_review

### comment:53 Changed 9 years ago by jdemeyer

• 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
**********************************************************************
`

### comment:54 Changed 9 years ago by tscrim

• 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 jdemeyer

• Milestone changed from sage-5.12 to sage-5.13

### comment:56 Changed 9 years ago by jdemeyer

• Merged in set to sage-5.13.beta0
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.