implement Grossman-Larson Hopf algebras of rooted forests

[fchapoton]

as an interesting and useful combinatorial Hopf algebra

CC: @tscrim @darijgr

Component: combinatorics

Author: Frédéric Chapoton

Branch/Commit: fbe95a9

Reviewer: Darij Grinberg, Travis Scrimshaw

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

[fchapoton]

Commit: 94d3e59

[fchapoton]

New commits:

94d3e59

basic implementation of the Grossman-Larson Hopf algebra of rooted forests

[fchapoton]

Branch: u/chapoton/23406

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 94d3e59 to 1ce9214

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

1ce9214

doc detail on Grossman-Larson product

[darijgr]

comment:3

You have defined the single_graft method on class RootedTree, which is a class for unordered rooted trees. But the method clearly requires an ordering for the subtrees (which I hope mean children -- maybe this is the better word?) of x. Now, this may be a non-issue since you aren't saying that t should be of class RootedTree; but then I'm not sure which class it should be of. Could you clarify, or move this to a more concrete class? Thanks!

[fchapoton]

comment:4

Hello Darij, thanks for having a look.

The single_graft implementation uses an ordering of the subtrees (by which I mean the elements of list(t)), but the result (as a RootedTree) does not depend on it.

Indeed, if I remember correctly, there is a planar version of the Grossman-Larson Hopf algebra, for which a planar version of single_graft would be used. But this is not the aim of this ticket. But maybe one want to think a bit more and implement directly the correct planar version.

[darijgr]

comment:5

Hi Frédéric!

Oh, I see. The children have a fixed order, probably by sort_key (not sure how exactly this works).

I've got a question: Is the behavior below acceptable for basis indices of a combinatorial free module?

sage: RT4 = RootedTrees(4)
sage: t1 = RT4([[],[[]]])
sage: t1
[[], [[]]]
sage: t2 = RT4([[[]],[]])
sage: t2
[[], [[]]]
sage: t1 == t2
True
sage: t1 is t2
False
sage: LRT4 = LabelledRootedTrees(4)
sage: t1 = LRT4(t1)
sage: t2 = LRT4(t2)
sage: t1 == t2
True
sage: t1 is t2
False
sage:

[tscrim]

comment:6

@darijgr That behavior has always been supported in CFM (assuming hash(a) == hash(b), which should happen by Python's specs):

sage: C = CombinatorialFreeModule(ZZ, QQ)
sage: B = C.basis()
sage: 1/2 is 1/2
False
sage: B[1/2] == B[1/2]
True
sage: B[1/2] is B[1/2]
False

[fchapoton]

comment:7

By the way, there is an important morphism of Hopf algebras from NCSF to the one here (for one variable) that maps the generator Psi_n of NCSF to the linear tree on n vertices (n+1 if counting the root). Would it be easy to implement that, either in this ticket or after ?

[darijgr]

comment:8

Yes, this should be easy -- just define it by first converting to the Psi-basis.

That is, as long as the base ring has the rational numbers in it. I assume the morphism doesn't exist otherwise?

[darijgr]

comment:9

@tscrim: Wow; I never realized that Sage rationals aren't uniquerepresentation! Great to hear this works.

[tscrim]

comment:10

I would probably do it in this ticket by implementing a _coerce_map_from_ to return a self.module_morphism with the correct construction data.

[darijgr]

comment:11

I would prefer not to make it a coercion. The thicket is already too dense around NSym, and this would be a coercion defined in dependence on the base ring, which too complicates thing. Plus, are we sure this is the most natural map NCSF -> GrossLars?

[tscrim]

comment:12

That is what _coerce_map_from_ is for. You can not make it a coercion if the base ring isn't a field of char 0 and it is localized to the object here. I don't see what the other coercions into/out-of NSym has to do with anything. However, there is something to be asked about if this is a natural map. My impression from comment:7 was that it was, but I'm not the person to be asking about this.

[fchapoton]

comment:13

This maps NCSF -> GL fits in a nice diagram, that I will not describe here. Anyway, let us keep it for a later ticket. I would be happy enough to have this algebra in sage.

[darijgr]

comment:14

Hmm.

+        CombinatorialFreeModule.__init__(self, R, Trees,
+                                         latex_prefix="",
+                                         sorting_key=key,
+                                         category=cat)

But Trees is not actually a basis; it has too much chaff. Is this a problem?

[darijgr]

comment:15

As far as I understand, algebra_generators is a misnomer: the 1-vertex forests don't generate GrossLars as an algebra. (I don't know in what sense they actually generate it...)

Also, is this part

They are the
    universal enveloping algebras of free pre-Lie algebras, seen
    as Lie algebras.

true in all characteristics?

[darijgr]

comment:16

In the doc of degree_on_basis, I'd clarify whether the fake root is counted or not.

Generally, the docs should be uniform about whether to speak in terms of forests or in terms of trees with a fake root. Currently, some of them do one and some the other.

[darijgr]

comment:17

Don't you want the coercion to only require the weaker condition all(x in self.variable_names() for x in R.variable_names()) instead of R.variable_names() == self.variable_names() in the coercion method?

That said, I think the __init__ tries a bit too hard to be smart. If I provide it a 1-element alphabet, I think it shouldn't use RootedTrees(). Instead, it should use LabelledRootedTrees() with the one letter I gave it. Otherwise, algorithms written with a multi-letter alphabet in mind would break. I suggest having an extra parameter to ask for the use of RootedTrees().

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

33b2b4b

trac 23406 some changes after reviewer's comments

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 1ce9214 to 33b2b4b

[fchapoton]

comment:19

Preliminary remark: this implementation has been made by copy-modifying the existing implementation of free pre-Lie algebras, which has therefore almost exactly the same issues. And something very similar was done for free Dendriform algebras recently.

1) The fact that Trees is not a basis does not prevent anything from working. As stated as a comment in the code, it would be good to have classes for LabelledRootedTrees with restricted labellings. But this is not really required here.

2) algebra_generators is indeed some kind of misnomer. These elements are the generators of the primitives as a free pre-Lie algebra. They also span the space on which the underlying functorial construction (vector species of labelled forests) is based. I would be ok to remove algebra_generators but would like to keep gen and gens

3) I have tried to clarify the doc by using "forest" consistently

4) I have changed the coercion as suggested

5) Concerning the use of unlabelled trees for the case of one variable. It is important for me to have an optimised 1-variable case. And also this behaviour is the one already existing for free pre-Lie algebras. But I agree that one could propose an option for the user to choose.

6) another question that you did not ask but should have : the treatment of variable names is not exactly the same as for polynomials, for example, using 'x,y' will do something strange. I do not know how to enhance this. Free pre-Lie, Zinbiel and Dendriform algebras suffer from the same strangeness.

[darijgr]

comment:20

1) Okay. Worth a warning in the doc though -- I can easily imagine some tests failing because of this, and worse, someone could try checking an identity by bruting through the basis, unaware of the fact that some of the elements don't belong into the algebra and probably don't behave accordingly.

2) I am fine with gen and gens; it's just the algebra_generators part I don't like.

3, 4) Thank you!

5) I understand you want the optimized code there; all I'm saying is there should also be a way to get the non-optimized one. Ideally there should be a difference between algebras.GrossmanLarson(QQ, ['x']) (unoptimized) and algebras.GrossmanLarson(QQ) (default value None, optimized). If the Alphabet constructor confuses the difference between these two inputs, I'm in favor of setting an extra variable for this.

If I pass an explicit list of variable names to algebras.GrossmanLarson, then I want to be able to construct basis elements of this algebra in a sane way. Since gen/gens is insufficient (those aren't algebra generators), this means passing actual labelled forests. And in order to construct the forest, I need to know the labels -- ideally, the labels I provided myself. If the labels at n = 1 are different from the ones I provided, I need to write a fugly special-casing code. Now that I'm thinking this out aloud, I guess we also need to expose ROOT at the level of the GrossmanLarson class...

6) Are you just saying that shorthands, such as 'x,y' for ['x','y'], are not correctly understood? I don't mind this much, although a doc warning wouldn't be out of place.

I wasn't fully aware that we had free pre-Lie, Zinbiel and dendriform algebras in Sage already; time is passing fast! I'm wondering if we can make QSym into a dendriform algebra, as the relevant operations are in the code already...

[By the way, I'm at my parents' home in Karlsruhe until the end of August -- consider yourself invited! In order to do any serious Sage coding, I'll have to install it on my laptop though, as opposed to sshing into Minneapolis...]

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 33b2b4b to ac04ea4

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

ac04ea4

trac 23406 more improvements

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from ac04ea4 to e13fb56

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

e13fb56

trac 23406 details

[fchapoton]

comment:23

Thanks for the invitation, I will think about it.

I think I have now taken all your comments into account. I removed algebra generators. I have added some doc, and changed the behaviour of single-variate case, using None to get unlabelled trees.

I forgot to answer your question on the isomorphism with the enveloping algebra. I think it holds over ZZ.

I have made a follow-up ticket in #23431, to do the similar cleanup for free pre-Lie algebras.

By the way, we do not have yet categories for all these kinds of algebras. So it is not yet possible to turn Qsym into a dendriform algebra.

[tscrim]

comment:24

Strong -1 on removing algebra_generators, especially in favor of gens, which does not take into account what structure you are considering (Darij, I think you even created the ticket about that). It makes no sense to have gens that constructs a tuple of a Family (if anything, it should just construct the tuple directly). Have the Family be the return value of algebra_generators.

There is another way to set the variable names. CFM now should take names and handle them properly. You can also use _assign_names. You may also want run either one of these (likely the former):

from sage.structure.category_object import normalize_names
from sage.structure.indexed_generators import parse_indices_names

in the __classcall_private__ for better standardization of input. I think it will be more robust than Alphabet, but it is a little more restrictive. At least IMO, it is easier to work with by your gens method (which restricts it to a finite generating set). Plus, in a way what you're doing is an abuse of the current framework. However, if you prefer the current approach, then I will not hold this ticket up for this.

Technically this comment is wrong

# after this line : coercion

_element_constructor_ defines conversion.

While the unicode does look nice, if there is no unicode support in the terminal, then the output of the examples is basically unreadable (I recently had to work with such a terminal). So I would prefer if the examples used ascii_art.

[darijgr]

comment:25

I will come back to a proper review of this later today, but for now, a brief response about gens: I have gotten used to gens being a context-dependent portmanteau. Meanwhile, algebra_generators should return algebra generators.

What about single_vertex?

As usual, I have nothing to say about standardization of input :/

[darijgr]

comment:26

I have reviewed everything except for the technical functions (__classcall_private__, __init__, _element_constructor_). Travis, can you take a look at these?

I also have added the antipode. (No unicode in the doctests, because unicode seems to break over my ssh connection. Sorry!)

Warning: branch change incoming.

(And yes, itertools.product and itertools.combinations are significantly faster than cartesian_product and powerset, respectively. I would also suspect that my child_grafts change speeds up the except case, since it would be computed twice before; but I haven't checked this.)

[darijgr]

Reviewer: Darij Grinberg

[darijgr]

Changed commit from e13fb56 to none

[darijgr]

Changed branch from u/chapoton/23406 to public/ticket/23406

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

94d3e59	basic implementation of the Grossman-Larson Hopf algebra of rooted forests
1ce9214	doc detail on Grossman-Larson product
33b2b4b	trac 23406 some changes after reviewer's comments
ac04ea4	trac 23406 more improvements
e13fb56	trac 23406 details
e7a5d36	review changes

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Commit: e7a5d36

[jhpalmieri]

comment:29

Please move the references to the master bibliography file, doc/en/reference/references/index.rst.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e7a5d36 to b1afa9d

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

b1afa9d

move references to master index

[tscrim]

comment:31

There are some problems with _element_constructor_ being too permissive:

sage: R.<x,y> = algebras.GrossmanLarson(QQ)
sage: S.<z> = algebras.GrossmanLarson(GF(3))
sage: R(z)
B[#[z[]]]
sage: R(2*z)^2
B[#[z[z[]]]] + B[#[z[], z[]]]
sage: (2*x)^2
4*B[#[x[x[]]]] + 4*B[#[x[], x[]]]

This is a conversion, so it doesn't care about the output of _coerce_map_from_. A different (but somewhat entangled) problem:

sage: S(x)
...
RuntimeError: maximum recursion depth exceeded while getting the str of an object

which seems to stem from the containment check if x in self.basis().keys(). Note that this "works":

sage: S(x.leading_support())
B[#[x[]]]

So the fix is to check to make sure. Same issue for

sage: P.<a> = QQ[]
sage: S(2*a + 2)
...
RuntimeError: maximum recursion depth exceeded while getting the str of an object

So does x*y correspond to taking the Lie bracket or their universal enveloping algebra (UEA) product? At least it seems to me that it is the latter (the former would mean x*y = -y*x, which is not the case), in which case they are algebra generators as every element in the Lie algebra is the commutator bracket, which then allows you to get every element the UEA by PBW. Thus it would be okay to call them algebra_generators.

Otherwise I really do not like the fact that gens does not generate the Grossman-Larson algebra under any structure. In which case, you should instead override _first_ngens to return the corresponding variable names to allow the R.<x,y> syntax.

@darijgr, I don't understand what you are proposing for single_vertex. As an alternative to gens?

Everything else of comment:24 still applies.

[darijgr]

comment:32

Yes, I am suggesting single_vertex as an alternative name to gens.

x*y corresponds to the UEA product. But the Lie algebra is not generated by the gens as a Lie algebra! (It is generated by them as a pre-Lie algebra.)

[tscrim]

comment:33

This is a little outside of my knowledge zone, so please bear with me. What you are saying is the entire Lie algebra is generated by gens under *, correct? So, by extension, it generates the entire algebra.

[darijgr]

comment:34

No. The Lie algebra is not generated by the gens. The pre-Lie algebra is generated by them.

The notation is quite confusing: A pre-Lie algebra is not "a Lie algebra without the Jacobi identity". A pre-Lie algebra is a usual nonunital algebra whose multiplication satisfies something weaker than associativity. In order to obtain a Lie algebra from a pre-Lie algebra, you have to replace the "product" by its commutator (whereas obtaining a pre-Lie algebra from an associative algebra requires doing nothing). So a pre-Lie algebra should perhaps rather be called a pre-associative algebra.

[tscrim]

comment:35

However, is the Lie algebra of primitives the Lie given by the commutators of the pre-Lie algebra given by gens? At least I do not understand elements are not able to be generated by gens under *.

[fchapoton]

comment:36

There are 3 different products at play here (plus a coproduct) :

• the Lie bracket [,]
• the UEA associative product, call it *
• the non-associative product of free pre-Lie algebras, call it <

The Lie bracket (on the span Prim(GL) of rooted trees) is the commutator of both * and <

Then "gens" do generate Prim(GL) as a free pre-Lie algebra (under <), but not as a Lie algebra. Think of the one variable case, where the free Lie algebra is one dimensional, whereas the free pre-Lie algebra is the span of rooted trees. It is a theorem that the space Prim(GL) is free as a Lie algebra, but on an infinite set of generators.

Therefore the "gens" do no generate GL as an associative algebra, as the correct generators are the same infinite set.

[tscrim]

comment:37

Oh, I see, the * does not correspond to the pre-Lie product <, that was what I was missing. So the issue is more of the fact we only have one distributive binary operation *, which you want it to be the UEA product (if we were in Python3, we could use @/__matmul__ for the other). Do we want to support the pre-Lie product, and if so, how? One way would be to use ** between two elements to mean the pre-Lie product. It would be a bit of a hackaround, but I don't see a use for x ** y otherwise.

As for the name, how about explicitly saying pre_lie_generators? I would also say we should do a custom _first_ngens to support R.<x> = GL() syntax.

[darijgr]

comment:38

Is there a pre-Lie product on the UEA at all? That's an actual question, which I am curious about. It's not per se obvious to me that a pre-Lie product on a Lie algebra automatically gives rise to a pre-Lie product on its UEA; but it sounds like the kind of statement that could be a theorem.

(Baby example: Does the symmetric algebra of a commutative algebra have a canonical pre-Lie product that is different from just the usual multiplication in the symmetric algebra?)

[fchapoton]

comment:39

There is no pre-Lie product on the UEA. The pre-Lie product exists only on the primitive subspace of GL.

I think I would like (later) to have the inclusion morphism from the Lie algebra algebras.FreePreLie to its UEA, namely GL. But not for this ticket.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b1afa9d to 29c72a3