Poincaré-Birkhoff-Witt and dual bases

[sagetrac-deneufchatel]

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.

Apply: attachment: trac_14898-pbw_folded-ts.patch

CC: @darijgr

Component: combinatorics

Author: Matthieu Deneufchâtel

Reviewer: Travis Scrimshaw

Merged: sage-5.13.beta0

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

[sagetrac-deneufchatel]

Attachment: trac_18484_PBW_basis.patch.gz

[sagetrac-deneufchatel]

Attachment: pbw.patch.gz

[jhpalmieri]

comment:3

Attachment: 14898.patch.gz

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.

[sagetrac-deneufchatel]

comment:4

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?

[jhpalmieri]

comment:5

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.

[sagetrac-deneufchatel]

comment:6

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

[sagetrac-deneufchatel]

Attachment: Lyndon_dual_bases.patch.gz

[tscrim]

comment:7

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

[sagetrac-deneufchatel]

comment:8

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.

[tscrim]

comment:9

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

[sagetrac-deneufchatel]

comment:10

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

[tscrim]

comment:11

Replying to @sagetrac-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

[sagetrac-deneufchatel]

comment:12

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

[tscrim]

comment:13

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.

[sagetrac-deneufchatel]

comment:14

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

[tscrim]

comment:15

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?

[sagetrac-deneufchatel]

comment:16

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.

[sagetrac-deneufchatel]

comment:17

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

[tscrim]

comment:18

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

[sagetrac-deneufchatel]

comment:19

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.

[tscrim]

comment:20

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

[sagetrac-deneufchatel]

comment:21

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

[tscrim]

comment:22

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.

[tscrim]

comment:39

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.

[sagetrac-deneufchatel]

comment:40

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"?

[sagetrac-deneufchatel]

comment:41

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

[sagetrac-deneufchatel]

comment:42

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

    from sage.combinat.composition import Composition

ImportError: cannot import name Composition

[tscrim]

comment:43

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

[sagetrac-deneufchatel]

comment:44

It works. Thanks.
Matthieu

[tscrim]

comment:45

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

[sagetrac-deneufchatel]

comment:46

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?

[sagetrac-deneufchatel]

comment:47

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

[tscrim]

comment:48

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

[tscrim]

comment:49

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

[sagetrac-deneufchatel]

comment:50

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

[tscrim]

comment:51

Yep, no changes except the output format. Then I'll give you the honor of setting this to a positive review.

Best,

Travis

[jdemeyer]

comment:53

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

[tscrim]

Attachment: trac_14898-pbw_folded-ts.patch.gz

[tscrim]

comment:54

Fixed.

For patchbot:

Apply: trac_14898-pbw_folded-ts.patch

[jdemeyer]

Merged: sage-5.13.beta0