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

[sagetrac-git]

Changed commit from 94d3e59 to 1ce9214

[sagetrac-git]

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

[sagetrac-git]

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

33b2b4b

trac 23406 some changes after reviewer's comments

[sagetrac-git]

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

[sagetrac-git]

Changed commit from 33b2b4b to ac04ea4

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

[sagetrac-git]

Changed commit from b1afa9d to 29c72a3

[sagetrac-git]

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

a192c4a	Merge branch 'public/ticket/23406' in 8.0.rc2
29c72a3	trac 23406 ascii art instead of unicode art

[sagetrac-git]

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

49055e4

trac 23406 testing also the antipode, shorter TestSuites

[sagetrac-git]

Changed commit from 29c72a3 to 49055e4

[tscrim]

comment:42

Replying to @fchapoton:

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

It is possible to define an operation restricted to a particular subset (e.g., inverse). The question becomes do we want to have another operation defined on the primitive subspace? For Lie algebras, this is not a problem because x.bracket(y) goes to Ux.bracket(Uy) and coercion should take care of the other combinations. Also in that case, the method bracket() is taking the place of the second operation.

I guess in either case we would want * to be the UEA product, so adding such a feature could be pushed off to another ticket. I'm also becoming more okay with using gens without such a feature, but I am not 100% there yet. However, pre_lie_algebra_generators is a bad name. How about primitive_generators?

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.

For that, all you need to do is have _construct_UEA return the corresponding GL algebra and define lift for the corresponding element class. I guess you would also then need to add to _coerce_map_from_

if isinstance(L, FreePreLieAlgebra):
    return self.coerce_map_from(L.universal_enveloping_algebra())

as L.universal_enveloping_algebra() automatically registers the coercion to its UEA and the coercion framework would take care of the rest. That on top of #23431 should give you what you want. However, I'm okay with that being another ticket.

[sagetrac-git]

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

b0dadb4

trac 23406 better (stricter) conversion

[sagetrac-git]

Changed commit from 49055e4 to b0dadb4

[sagetrac-git]

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

963c5eb	Merge branch 'public/ticket/23406' in 8.1.b5
117ad0d	trac 23406 some details

[sagetrac-git]

Changed commit from b0dadb4 to 117ad0d

[fchapoton]

comment:45

There is still a controversy about the naming of the methods gen, gens and algebra_generators.

My choice by decreasing order of preference:

1. use "gen" and "gens" (because these are not algebra generators)

2. use "single_vertex"

3. use "prelie_generators" (but they do not generate as a pre-Lie algebra !)

Can we try to agree on something ?

[darijgr]

comment:46

I'm in favor of option 2.

[tscrim]

comment:47

Okay, I had to re-familiarize myself with the discussion. So, I agree with Darij and think option 2 is the best way forward so we do not further muddy the gens ambiguity.

PS - I just thought of the operator << for the pre-Lie product, but unfortunately, that is lower priority than +-.

[sagetrac-git]

Changed commit from 117ad0d to fbe95a9

[sagetrac-git]

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

fbe95a9

trac 23406 using "single_vertex" instead of "gen"

[fchapoton]

comment:49

Done. I used single_vertex and single_vertex_all. I also had to override _first_ngens.

[tscrim]

Changed reviewer from Darij Grinberg to Darij Grinberg, Travis Scrimshaw

[tscrim]

comment:50

Thank you. Since all comments have been addressed, I am setting this to a positive review.

[vbraun]

Changed branch from public/ticket/23406 to fbe95a9