Implement convolution_product for HopfAlgebras

[alauve]

In the study of Hopf algebras (both graded and finite dimensional), one is led to look at convolution powers of the identity, and convolution products more generally. These should be implemented in bialgebras.py.

Of possible future utility is the iterated coproduct, so I define that as well.

Depends on #17096

CC: @zabrocki @saliola @sagetrac-sage-combinat @amypang @nthiery @avirmaux @jhpalmieri @sagetrac-nborie @sagetrac-mshimo @tscrim @sagetrac-elixyre

Component: categories

Keywords: days65, convolution product

Author: Aaron Lauve, Jean-Baptiste Priez, Amy Pang, Travis Scrimshaw

Branch/Commit: 47d3a1b

Reviewer: Franco Saliola, Travis Scrimshaw

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

[alauve]

Branch: u/alauve/implement_convolution_product_for_hopfalgebras

[saliola]

Commit: 58f409b

[saliola]

comment:2

I have some ideas for you...

---

New commits:

58f409b

Added convolution_product and hopf_power method

[saliola]

comment:5

Here are some comments summarizing the live review we did at Sage Days 65:

• The first argument arg0 in def method_name(arg0, ...): should be self; this is a Python coding convention (and not strictly necessary for the code to work, but Sage coding conventions requires this).

• Your documentation strings need to be formatted according to Sage coding conventions. Here is a link to the relevant page in the Sage developer's guide:The docstring of a function.

• You also need to add doctests (see the above link for details). Make sure that all parts of your function are tested (i.e., if your code handles various cases, then your doctests should test the various possible cases).

• The function n_fold_coproduct defined within convolution_power is interesting and should be a method on its own.

[jhpalmieri]

comment:6

Is there overlap between this ticket and #18350?

[saliola]

comment:7

Replying to @jhpalmieri:

Is there overlap between this ticket and #18350?

Thanks for pointing this out! Yes, there is overlap (but not a duplicate). It will make the work on this ticket even easier.

[sagetrac-git]

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

66c6c0d

merging ticket 18350

[sagetrac-git]

Changed commit from 58f409b to 66c6c0d

[sagetrac-git]

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

aeefa26	new operator
a685ad1	new operator: iterate coproduct and product k times
fc8726a	ticket 18350: revision following comments
6913b18	merging ticket 18350
a80d67f	added convolution product based on code from Amy Pang

[sagetrac-git]

Changed commit from 66c6c0d to a80d67f

[alauve]

Changed author from alauve to Aaron Lauve

[alauve]

comment:11

All,

I have merged #18350 with this ticket. Some comments/questions for people in-the-know to weigh-in on...

• I have moved .adams_operator() to bialgebras.py, and overwrote it using code from Amy Pang (amypang). Then in hopf_algebras.py I overwrote the bialgebras version, allowing for negative integer powers. (E.g., the (-2)nd convolution power of the identity is none other than the 2nd power of the antipode.)

• In fact, while adams operators naturally belong in bialgebras.py, the present code actually belongs in bialgebras_with_basis.py---as it uses .module_morphism() and .apply_multilinear_morphism()---but this would require more rewriting than I feel qualified to handle.

• Easy fix? When poking around for an algebra without basis---on which to test a preliminary version of my code---I noticed that Sage doesn't know that QQ[x] is a module over QQ (and hence, one cannot build ``QQ[x].tensor(QQ[x])`. Crazy.

• Easy fix? Similarly, even though B = FreeAlgebra(QQ,a,b) is robust enough that B.tensor(B) doesn't throw errors, quotients are out-of-bounds again. Putting C = B.quotient_ring((a*b-b^2,)), I get an AttributeError when asking for C.tensor(C).

• I would like to add some morphism functionality at the parent level before setting ticket to "needs_review": given linear morphisms R,S,T for a bialgebra B, create their convolution product, a new morphism, via RST = B.convolution_product(R,S,T). However, it seems ticket tensor products of maps #15832 will have a lot of overlap with such code, so I'll hold off on implementing it unless somebody suggests otherwise.

• If anybody can explain why iterated coproduct followed by iterated product is slower than Amy Pang's code, I'd love to hear it.

A 'thanks' in advance for any comments.

-- Aaron

[sagetrac-git]

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

e07d789

fixed doctests for added methods in hopf_algebras_with_basis.py and bialgebras.py

[sagetrac-git]

Changed commit from a80d67f to e07d789

[tscrim]

comment:13

Replying to @alauve:

I have merged #18350 with this ticket.

I set this as a dependency.

• I have moved .adams_operator() to bialgebras.py, and overwrote it using code from Amy Pang (amypang). Then in hopf_algebras.py I overwrote the bialgebras version, allowing for negative integer powers. (E.g., the (-2)nd convolution power of the identity is none other than the 2nd power of the antipode.)

I would make these changes on #18350 directly (I'd recommend git cherry-pick the commit with that change in #18350 if it's in an isolated commit, otherwise you'll have to deal with the merge conflict).

• In fact, while adams operators naturally belong in bialgebras.py, the present code actually belongs in bialgebras_with_basis.py---as it uses .module_morphism() and .apply_multilinear_morphism()---but this would require more rewriting than I feel qualified to handle.

Then I would move the method into BialgebrasWithBasis and put an @abstract_method(optional=True) on an empty adams_operators in Bialgebras (on #18350).

• Easy fix? When poking around for an algebra without basis---on which to test a preliminary version of my code---I noticed that Sage doesn't know that QQ[x] is a module over QQ (and hence, one cannot build ``QQ[x].tensor(QQ[x])`. Crazy.

Sage is full of fun oddities like that. Personally I'm not opposed to changing the category to Algebras(QQ).WithBasis(), but even with that, I'd think there's still more work to do to get QQ[x].tensor(QQ[x]) to work...

• Easy fix? Similarly, even though B = FreeAlgebra(QQ,a,b) is robust enough that B.tensor(B) doesn't throw errors, quotients are out-of-bounds again. Putting C = B.quotient_ring((a*b-b^2,)), I get an AttributeError when asking for C.tensor(C).

What is a and b? I think there is an abuse going on, but as of right now I cannot even construct B.

• I would like to add some morphism functionality at the parent level before setting ticket to "needs_review": given linear morphisms R,S,T for a bialgebra B, create their convolution product, a new morphism, via RST = B.convolution_product(R,S,T). However, it seems ticket tensor products of maps #15832 will have a lot of overlap with such code, so I'll hold off on implementing it unless somebody suggests otherwise.

I would work on #15832 and either create a follow-up with the additional code or just add that code directly to #15832.

• If anybody can explain why iterated coproduct followed by iterated product is slower than Amy Pang's code, I'd love to hear it.

I would add an AUTHORS: block and give Amy the credit for her code. I have no idea at this point why this is. Try running %prun the_command to get timing information and look through that data for hints. Also what exactly are you testing this with? What is your timings (in particular, the approximate slowdown factor)?

[tscrim]

Dependencies: #18350

[sagetrac-git]

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

67c0e22

added convolution_product() at parent level, added a few more tests and examples.

[sagetrac-git]

Changed commit from e07d789 to 67c0e22

[sagetrac-git]

Changed commit from 67c0e22 to de4fa87

[sagetrac-git]

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

de4fa87

In ParentMethods of bialgebras.py, added ._convolution_product_from_element() for testing purposes.

[alauve]

comment:16

Hi Travis, Comments below...

Replying to @tscrim:

Replying to @alauve:

I have merged #18350 with this ticket.

I set this as a dependency.

I'm sure that's the wrong thing to do, but perhaps it's also the best thing to do, given the steps I already took (merging). In fact, there is no dependency, and the first thing I did was undo all the changes JBP made to hopf_algebras.py. I think not both tickets should be completed. I'm happy to move all my edits to #18350 and delete the present ticket if that makes more sense... though I don't know how to do that either.

Alternative?: set #18350 as positive review, as is, then start looking at this one? .... I'm really not sure what is the best; see next comment for more.

• I have moved .adams_operator() to bialgebras.py, and overwrote it using code from Amy Pang (amypang). Then in hopf_algebras.py I overwrote the bialgebras version, allowing for negative integer powers. (E.g., the (-2)nd convolution power of the identity is none other than the 2nd power of the antipode.)

I would make these changes on #18350 directly (I'd recommend git cherry-pick the commit with that change in #18350 if it's in an isolated commit, otherwise you'll have to deal with the merge conflict).

It was not an isolated commit (I've learned my lesson, thanks!). Alternative idea, implemented in present ticket: I have deleted .adams_operator() from hopf_algebras.py and from hopf_algebras_with_basis.py and instead added an attribute check, hasattr(self,'antipode') within bialgebras.py to allow for negative convolution powers of the identity.

• In fact, while adams operators naturally belong in bialgebras.py, the present code actually belongs in bialgebras_with_basis.py---as it uses .module_morphism() and .apply_multilinear_morphism()---but this would require more rewriting than I feel qualified to handle.

Then I would move the method into BialgebrasWithBasis and put an @abstract_method(optional=True) on an empty adams_operators in Bialgebras (on #18350).

I don't know how to do the former (the move), as bialgebras_with_basis.py just contains a def not a class. Maybe there is a monkey-patching solution, overwriting whatever ParentMethods and ElementMethods classes that get created by the def, but I'm comfortable trying neither this solution nor overhauling the whole file (i.e., to make it look more like hopf_algebras_with_basis.py).

Is there a better solution than the latter (abstract_method)? It's not really optional... more like not presently code-able. Perhaps a better solution is to keep things in bialgebras.py, perform an attribute check, self in ModulesWithBasis and add "..TODO:: remove dependency on bases" to the docstring? Anyhow, this is what I'm doing in latest commit.

• Easy fix? When poking around for an algebra without basis---on which to test a preliminary version of my code---I noticed that Sage doesn't know that QQ[x] is a module over QQ (and hence, one cannot build ``QQ[x].tensor(QQ[x])`. Crazy.

Sage is full of fun oddities like that. Personally I'm not opposed to changing the category to Algebras(QQ).WithBasis(), but even with that, I'd think there's still more work to do to get QQ[x].tensor(QQ[x]) to work...

I'm going to fiddle with this. If that's all it takes, I'll start a new ticket and it should be completed easily enough.

• Easy fix? Similarly, even though B = FreeAlgebra(QQ,a,b) is robust enough that B.tensor(B) doesn't throw errors, quotients are out-of-bounds again. Putting C = B.quotient_ring((a*b-b^2,)), I get an AttributeError when asking for C.tensor(C).

What is a and b? I think there is an abuse going on, but as of right now I cannot even construct B.

Sorry. the code I ran was:

sage: B = FreeAlgebra(QQ,['a','b'])
sage: a,b = B.gens()
sage: B.tensor(B)
sage: C = B.quotient_ring((a*b-b^2,))
sage: C.tensor(C)

• I would like to add some morphism functionality at the parent level before setting ticket to "needs_review": given linear morphisms R,S,T for a bialgebra B, create their convolution product, a new morphism, via RST = B.convolution_product(R,S,T). However, it seems ticket tensor products of maps #15832 will have a lot of overlap with such code, so I'll hold off on implementing it unless somebody suggests otherwise.

I would work on #15832 and either create a follow-up with the additional code or just add that code directly to #15832.

Found an alternative solution in present commit. If ever #15832 gets adopted, the code here can be shortened by a few lines at most.
Note 1: But see comments in sage.categories.bialgebras.ParentMethods.convolution_product regarding speed.
Note 2: Also, I do not know how to keep .convolution_product() from showing up in the list of methods available to, e.g., sym=SymmetricFunctions(QQ). Any ideas on how to remove this?
(At present, the code assumes self is something more like SymmetricFunctions(QQ).m() If the check wasn't there, Sage would throw an error, because sym.tensor(sym) doesn't work.)...

sage: sym = SymmetricFunctions(QQ); m = sym.m()
sage: Id3 = m.convolution_product((lambda x: x,)*3)
sage: Id3(m[1]) == 3*m[1]
True
sage: sym.con <TAB>
sym.construction         sym.convert_map_from     sym.convolution_product
sage: sym.convolution_product((lambda x: x,)*3)
AttributeError: `self` (Symmetric Functions over Rational Field) must belong to ModulesWithBasis. Try defining convolution product on a basis of `self` instead.

• If anybody can explain why iterated coproduct followed by iterated product is slower than Amy Pang's code, I'd love to hear it.

I would add an AUTHORS: block and give Amy the credit for her code. I have no idea at this point why this is. Try running %prun the_command to get timing information and look through that data for hints. Also what exactly are you testing this with? What is your timings (in particular, the approximate slowdown factor)?

I have included a second ParentMethods command, _convolution_product_from_elements() for others to investigate. I have looked at %prun using SymmetricFunctions(QQ).m() and SymmetricGroupAlgebra(QQ,6), which have radically different Hopf structure (and number of terms in product/coproduct). In both cases, _convolution_product_from_elements() (based on Amy's code) destroys convolution_product() (based on my code and Jean-Baptiste's code). I can't glean much, other than that total number of operations are vastly different.

sage: Id = lambda x: x
sage: m = SymmetricFunctions(QQ).m(); 
sage: mx = m[5,4,3,2,1]
sage: T1 = m.convolution_product((Id,)*4)
sage: timeit('T1(mx)',number=2,repeat=1)
2 loops, best of 1: 32 s per loop
sage: T2 = m._convolution_product_from_elements((Id,)*4)
sage: timeit('T2(mx)',number=2,repeat=1)
2 loops, best of 1: 32.3 s per loop

sage: mx = m[5,4,3,2,1]
sage: T1 = m.convolution_product((Id,)*7)
sage: timeit('T1(mx)',number=2,repeat=1)
2 loops, best of 1: 169 s per loop
sage: T2 = m._convolution_product_from_elements((Id,)*7)
sage: timeit('T2(mx)',number=2,repeat=1)
2 loops, best of 1: 80.3 s per loop

sage: qs = SymmetricGroupAlgebra(QQ,7); qsx = qs.an_element()^2; qsx
14*[1, 2, 3, 4, 5, 6, 7] + 4*[1, 2, 3, 4, 5, 7, 6] + 6*[1, 2, 3, 4, 6, 5, 7] + 6*[1, 2, 3, 4, 6, 7, 5] + 6*[1, 2, 3, 4, 7, 5, 6] + 2*[6, 1, 2, 3, 4, 5, 7] + [6, 7, 1, 2, 3, 4, 5] + 2*[7, 1, 2, 3, 4, 5, 6] + 5*[7, 1, 2, 3, 4, 6, 5] + 3*[7, 1, 2, 3, 5, 4, 6]
sage: T1 = qs.convolution_product(Id,Id,Id)
sage: timeit('T1(qsx)')
125 loops, best of 3: 3.98 ms per loop
sage: T2 = qs._convolution_product_from_elements(Id,Id,Id)
sage: timeit('T2(qsx)')
125 loops, best of 3: 3.4 ms per loop

sage: T1 = qs.convolution_product((Id,)*7)
sage: timeit('T1(qsx)')
25 loops, best of 3: 10.6 ms per loop
sage: T2 = qs._convolution_product_from_elements((Id,)*7)
sage: timeit('T2(qsx)')
25 loops, best of 3: 8.25 ms per loop

---

New commits:

de4fa87

In ParentMethods of bialgebras.py, added ._convolution_product_from_element() for testing purposes.

[vbraun]

comment:44

Doctests fail

[tscrim]

comment:45

I don't get any doctest failures with the current branch on beta7. Could you post more information or tell us some potential conflicts from things you've already merged into your working branch if you're still getting failures?

[vbraun]

comment:46

Still fails, duh. Try again with beta8.

[tscrim]

comment:47

Thank you for your very useful information.

[sagetrac-git]

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

84566cc	Merge branch 'public/algebras/convolution_product_hopf_algebras-18678' of trac.sagemath.org:sage into public/algebras/convolution_product_hopf_algebras-18678
ca0f846	Fixing doctest failures.

[sagetrac-git]

Changed commit from 50ecfe4 to ca0f846

[tscrim]

comment:49

Trivial failures due to the category hierarchy changing.

[vbraun]

comment:50

merge conflict, wait for the next beta

[sagetrac-git]

Changed commit from ca0f846 to 47d3a1b

[sagetrac-git]

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

570bc49	Merge branch 'public/categories/super_categories-18044' into 6.9.b1
b91cd82	trac #18044 correct one typo in the doc
7fd1df2	Merge branch 'public/categories/super_categories-18044' of trac.sagemath.org:sage into public/categories/super_categories-18044
0579337	Some reviewer tweaks and doc additions.
aec22cc	Added one more test.
4b2046f	Merge branch 'public/categories/super_categories-18044' into public/categories/filtered_algebras-17096
3f67b6b	Fixing trivial doctest due to changes in category heirarchy.
fa476dd	Fixing double-colon in INPUT block.
6cc8b84	Reviewer changes with Darij.
47d3a1b	Merge branch 'public/categories/filtered_algebras-17096' of trac.sagemath.org:sage into public/algebras/convolution_product_hopf_algebras-18678

[tscrim]

comment:52

Fixed what should be the merge conflict.

[tscrim]

Dependencies: #17096

[vbraun]

Changed branch from public/algebras/convolution_product_hopf_algebras-18678 to 47d3a1b