Ï C Lo

F R Éd

Éric Patras
email: patras@unice.fr

LIE THEORY FOR QUASI-SHUFFLE BIALGEBRAS

Introduction

Enveloping algebras of Lie algebras are known to be a fundamental notion, for an impressive variety of reasons. Their bialgebra structure allows to make a natural bridge between Lie algebras and groups. As such they are a key tool in pure algebra, algebraic and differential geometry, and so on. Their combinatorial structure is interesting on its own and is the object of the theory of free Lie algebras. Applications thereof include the theory of differential equations, numerics, control theory... From the modern point of view, featured in Reutenauer's Free Lie algebras [START_REF] Ch | Free lie algebras[END_REF], the "right" point of view on enveloping algebras is provided by the descent algebra: most of their key properties can indeed be obtained and finely described using computations in symmetric group algebras relying on the statistics of descents of permutations. More recently, finer structures have emerged that refine this approach. Let us quote, among others, the Malvenuto-Reutenauer Hopf algebra [START_REF] Malvenuto | Duality between quasi-symmetrical functions and the solomon descent algebra[END_REF] and its bidendriform structure [START_REF] Foissy | Bidendriform bialgebras, trees, and free quasi-symmetric functions[END_REF].

Many features of classical Lie theory generalize to the broader context of algebras over Hopf operads [START_REF] Livernet | Lie theory for hopf operads[END_REF]. However, this idea remains largely to be developed systematically. Quasi-shuffle algebras provide for example an interesting illustration of these phenomena, but have not been investigated from this point of view.

The notion of quasi-shuffle algebras can be traced back to the beginings of the theory of Rota-Baxter algebras, but was developed systematically only recently, starting essentially with Hoffman's work, that was motivated by multizeta values (MZVs) and featured their bialgebra structure. Many partial results on the fine structure of quasi-shuffle bialgebras have been obtained since then [START_REF] Hoffman | Quasi-shuffle products[END_REF][START_REF]Trialgebras and families of polytopes, Homotopy theory: relations with algebraic geometry, group cohomology, and algebraic K-theory[END_REF][START_REF] Novelli | Polynomial realizations of some trialgebras, Proceedings of Formal Power Series and Algebraic Combinatorics[END_REF][START_REF] Novelli | Natural endomorphisms of quasi-shuffle hopf algebras[END_REF][START_REF] Foissy | Deformations of shuffles and quasi-shuffles[END_REF] but, besides the fact that each of these articles features a particular point of view, they fail to develop systematically a complete theory.

This article builds on these various results and develops the analog theory, for quasi-shuffle algebras, of the theory of descent algebras and their relations to free Lie algebras for classical enveloping algebras.

The plan is as follows. Sections 2 and 3 recall the fundamental definitions. These are fairly standard ideas and materials, excepted for the fact that bialgebraic structures are introduced from the point of view of Hopf operads that will guide later developments. The following section shows how the symmetrization process in the theory of twisted bialgebras (or Hopf species) can be adapted to define a noncommutative quasi-shuffle bialgebra structure on the operad of quasi-shuffle algebras. The properties of its primitive elements are studied from an operadic and enveloping algebra (left adjoint) point of view. Section 5 deals with the algebraic structure of linear endomorphisms of quasi-shuffle bialgebras and studies from this point of view the structure of surjections. Section 6 deals with the projection on the primitives of quasi-shuffle bialgebras -the analog in the present setting of the canonical projection from an enveloping algebra to the Lie algebra of primitives. As in classical Lie theory, a structure theorem for quasi-shuffle algebras follows from the properties of this canonical projection. Section 7 investigates the relations between the shuffle and quasi-shuffle operads when both are equipped with the Hopf algebra structure inherited from the Hopf operadic structure of their categories of algebras (as such they are isomorphic respectively to the Malvenuto-Reutenauer Hopf algebra, or Hopf algebra of free quasi-symmetric functions, and to the Hopf algebra of word quasi-symmetric functions). We recover in particular the exponential isomorphism relating shuffle and quasi-shuffle bialgebras. Section 8 studies coalgebra endomorphisms of quasi-shuffle bialgebras and classifies natural Hopf algebra endomorphisms and morphisms relating shuffle and quasi-shuffle bialgebras. Section 9 studies coderivations. Quasi-shuffle bialgebras are considered classically as filtered objects (the product does not respect the tensor graduation), however the existence of a natural graded Hopf algebra structure can be deduced from the general properties of their coderivations. Section 10 explains briefly how the formalism of operads can be adapted to take into account graduations by using decorated operads. We detail then the case of quasi-shuffle algebras and conclude by initiating the study of the analogue, in this context, of the classical descent algebra. Section 11 shows, using the bidendriform rigidity theorem, that the decorated quasi-shuffle operad is free as a noncommutative shuffle algebra. Section 12 shows that the quasi-shuffle analog of the descent algebra, QDesc, is, up to a canonical isomorphism, a free noncommutative quasi-shuffle algebra over the integers. The last section concludes by investigating the quasishuffle analog of the classical sequence of inclusions Desc ⊂ PBT ⊂ Sh of the descent algebra into the algebra of planar binary trees, resp. the operad of shuffle algebras. In the quasi-shuffle context, this sequence reads Desc ⊂ ST ⊂ QSh, where ST stands for the algebra of Schröder trees and QSh for the quasi-shuffle operad.

Notations and conventions All the structures in the article (vector spaces, algebras, tensor products...) are defined over a field k. Algebraic theories and their categories (Com, As, Sh, QSh . . . ) are denoted in italic, as well as the corresponding free algebras over sets or vector spaces (QSh(X), Com(V ) . . . ). Operads (of which we will study underlying algebra structures) and abbreviations of algebra names are written in bold (QSh, NSh, Com, FQSym . . . ).

Quasi-shuffle algebras

Quasi-shuffle algebras have mostly their origin in the theory of Rota-Baxter algebras and related objects such as MZVs (this because the summation operator of series is an example of a Rota-Baxter operator). As we just mentioned, this is in often traced back to Cartier's construction of free commutative Rota-Baxter algebras [START_REF] Cartier | On the structure of free baxter algebras[END_REF] but the recent developments really started with Hoffman's [START_REF] Hoffman | Quasi-shuffle products[END_REF]. Further historical details and references can be found in the survey article [START_REF] Ebrahimi-Fard | La structure combinatoire du calcul intégral[END_REF].

Another reason for the development of the theory lies in the theory of combinatorial Hopf algebras and, more specifically, into the developments originating in the theory of quasi-symmetric functions and the dual theory of noncommutative symmetric functions. This line of thought is illustrated in [START_REF] Novelli | Polynomial realizations of some trialgebras, Proceedings of Formal Power Series and Algebraic Combinatorics[END_REF][START_REF] Novelli | Natural endomorphisms of quasi-shuffle hopf algebras[END_REF][START_REF] Foissy | Deformations of shuffles and quasi-shuffles[END_REF].

Still another approach originates in the work of Chapoton on the combinatorial and operadic properties of permutohedra and other polytopes (see e.g. [START_REF] Chapoton | Algebres de hopf des permutoedres, associaedres et hypercubes[END_REF][START_REF]Opérades différentielles graduées sur les simplexes et les permutoèdres[END_REF] and the introduction of [START_REF] Novelli | Polynomial realizations of some trialgebras, Proceedings of Formal Power Series and Algebraic Combinatorics[END_REF]). These phenomena lead to the axiomatic definition of tridendriform algebras (or dendriform trialgebras) in [START_REF]Trialgebras and families of polytopes, Homotopy theory: relations with algebraic geometry, group cohomology, and algebraic K-theory[END_REF]. Commutative tridendriform algebras (CTAs) identify with quasishuffle algebras (in the sense that the structure axioms of CTAs are the analog, for quasi-shuffle algebras, of Schützenberger's axioms for shuffle algebras [START_REF] Schützenberger | Sur une propriété combinatoire des algèbres de lie libres pouvant être utilisée dans un problème de mathématiques appliquées, Séminaire Dubreil-Jacotin Pisot[END_REF]) -we prefer the terminology quasi-shuffle, better established and more intuitive.

We follow here the Rota-Baxter approach, which is the one underlying at the moment most of the applications of the theory and the motivations for its development (besides MZVs and the works initiated by Hoffman in this area, one can mention the field of stochastic integration [START_REF] Ebrahimi-Fard | Flows and stochastic taylor series in itô calculus[END_REF][START_REF] Ebrahimi-Fard | The exponential lie series for continuous semimartingales[END_REF]). Definition 1. A Rota-Baxter (RB) algebra of weight θ is an associative algebra A equipped with a linear endomorphism R such that ∀x, y ∈ A, R(x)R(y) = R(R(x)y + xR(y) + θxy).

It is a commutative Rota-Baxter algebra if it is commutative as an algebra.

Setting R ′ := R/θ when θ = 0, one gets that the pair (A, R ′ ) is a Rota-Baxter algebra of weight 1. This implies that, in practice, there are only two interesting cases to be studied abstractly: the weight 0 and weight 1 (or equivalently any other non zero weight). The others can be deduced easily from the weight 1 case. The same observation applies for one-parameter variants of the notion of quasi-shuffle algebras.

From now on in this article, RB algebra will stand for RB algebra of weight 1. When other RB algebras will be considered, their weight will be mentioned explicitely.

An important property of RB algebras, whose proof is left to the reader, is the existence of an associative product, the RB double product ⋆, defined by: [START_REF] Bourbaki | Groupes et algèbres de lie[END_REF] x ⋆ y := R(x)y + xR(y) + xy so that: R(x)R(y) = R(x ⋆ y). If one sets, in a RB algebra, x ≺ y := xR(y), x ≻ y := R(x)y, one gets immediately relations such as

(x • y) ≺ z = xyR(z) = x • (y ≺ z), (x ≺ y) ≺ z = xR(y)R(z) = x ≺ (y ⋆ z),
and so on. In the commutative case, x ≺ y = y ≻ x, and all relations between the products ≺, ≻, • and ⋆ :=≺ + ≻ +• follow from these two. In the noncommutative case, the relations duplicate and one has furthermore

(x ≻ y) ≺ z = R(x)yR(z) = x ≻ (y ≺ z).
These observations give rise to the axioms of quasi-shuffle algebras (or CTAs) and noncommutative quasishuffle algebras (NQSh or tridendriform algebras) [START_REF]Trialgebras and families of polytopes, Homotopy theory: relations with algebraic geometry, group cohomology, and algebraic K-theory[END_REF].

From now on, "commutative algebra" without other precision means commutative and associative algebra; "product" on a vector space A means a bilinear product, that is a linear map from A ⊗ A to A. Definition 2. A quasi-shuffle (QSh) algebra A is a nonunital commutative algebra (with product written •) equipped with another product ≺ such that

(x ≺ y) ≺ z = x ≺ (y ⋆ z) (2) (x • y) ≺ z = x • (y ≺ z). (3)
where x ⋆ y := x ≺ y + y ≺ x + x • y. We also set for further use x ≻ y := y ≺ x. As the RB double product in a commutative RB algebra, the product ⋆ is automatically associative and commutative and defines another commutative algebra structure on A.

Recall, for further use, that shuffle algebras correspond to weight 0 commutative RB algebras, that is quasi-shuffle algebras with a null product • = 0. Equivalently: Definition 3. A shuffle (Sh) algebra is a vector space equipped with a product ≺ satisfying (2) with x ⋆ y := x ≺ y + y ≺ x, see e.g. [START_REF] Schützenberger | Sur une propriété combinatoire des algèbres de lie libres pouvant être utilisée dans un problème de mathématiques appliquées, Séminaire Dubreil-Jacotin Pisot[END_REF][START_REF] Ebrahimi-Fard | La structure combinatoire du calcul intégral[END_REF][START_REF] Foissy | Natural endomorphisms of shuffle algebras[END_REF] for further details.

It is sometimes convenient to equip quasi-shuffle algebras with a unit. The phenomenon is exactly similar to the case of shuffle algebras [START_REF] Schützenberger | Sur une propriété combinatoire des algèbres de lie libres pouvant être utilisée dans un problème de mathématiques appliquées, Séminaire Dubreil-Jacotin Pisot[END_REF]: given a quasi-shuffle algebra, one sets B := k ⊕ A, and the products ≺, • have a partial extension to B defined by, for x ∈ A:

1 • x = x • 1 := 0, 1 ≺ x := 0, x ≺ 1 := x.
The products 1 ≺ 1 and 1 • 1 cannot be defined consistenly, but one sets 1 ⋆ 1 := 1, making B a unital commutative algebra for ⋆.

The categories of quasi-shuffle and of unital quasi-shuffle algebras are clearly equivalent (under the operation of adding or removing a copy of the ground field). Definition 4. A noncommutative quasi-shuffle algebra (NQSh or tridendriform algebra) is a nonunital associative algebra (with product written •) equipped with two other products ≺, ≻ such that, for all x, y, z ∈ A:

(x ≺ y) ≺ z = x ≺ (y ⋆ z) (4) (x ≻ y) ≺ z = x ≻ (y ≺ z) (5) (x ⋆ y) ≻ z = x ≻ (y ≻ z) (6) (x ≺ y) • z = x • (y ≻ z) (7) (x ≻ y) • z = x ≻ (y • z) (8) (x • y) ≺ z = x • (y ≺ z). ( 9
)
where x ⋆ y := x ≺ y + x ≻ y + x • y.

As the RB double product, the product ⋆ is automatically associative and equips A with another associative algebra structure. Indeed, the associativity relation [START_REF] Eilenberg | On the groups h(π, n)[END_REF] (x • y)

• z = x • (y • z)
and (4) + . . . + (9) imply the associativity of ⋆:

(11) (x ⋆ y) ⋆ z = x ⋆ (y ⋆ z).
If A is furthermore a quasi-shuffle algebra, then the product ⋆ is commutative. One can show that these properties are equivalent to the associativity of the double product ⋆ in a Rota-Baxter algebra (this is because the free NQSh algebras embed into the corresponding free Rota-Baxter algebras).

Noncommutative shuffle algebras correspond to weight 0 RB algebras, that is NQSh algebras with a null product • = 0. Equivalently: Definition 5. A noncommutative shuffle (NSh or dendriform) algebra is a vector space equipped with two products ≺, ≻ satisfying (4,5,6) with x ⋆ y := x ≺ y + y ≺ x.

The most classical example of such a structure is provided by the topologists' shuffle product and its splitting into two "half-shuffles" [START_REF] Eilenberg | On the groups h(π, n)[END_REF].

As in the commutative case, it is sometimes convenient to equip NQSh algebras with a unit. Given a NQSh algebra, one sets B := k ⊕ A, and the products ≺, ≻, • have a partial extension to B defined by, for x ∈ A:

1 • x = x • 1 := 0, 1 ≺ x := 0, x ≺ 1 := x, 1 ≻ x := x, x ≻ 1 := 0.
The products 1 ≺ 1, 1 ≻ 1 and 1 • 1 cannot be defined consistenly, but one sets 1 * 1 := 1, making B a unital commutative algebra for * .

The categories of NQSh and unital NQSh algebras are clearly equivalent.

The following Lemma encodes the previously described relations between RB algebras and quasi-shuffle algebras: Lemma 6. The identities x ≺ y := xR(y), x ≻ y := R(x)y, x • y := xy induce a forgetful functor from RB algebras to NQSh algebras, resp. from commutative RB algebras to QSh algebras.

Remarks. Let A be a NQSh algebra.

(1) If A is a commutative algebra (for the product •) and if for x, y ∈ A:

x ≺ y = y ≻ x, we say that A is commutative as a NQSh algebra. Then, (A, •, ≺) is a quasi-shuffle algebra.

(2) We put =≺ +•. Then (4) + ( 7) + ( 9) + ( 10), ( 5) + ( 9) and (6) give:

(x y) z = x (y z + y ≻ z), (12)
(x ≻ y) y = x ≻ (y z), (13)
(x y + x ≻ y) ≻ z = x ≻ (y ≻ z). ( 14
)
These are the axioms that define a noncommutative shuffle algebra structure (A, , ≻) on A. Similarly, if =≻ +•, then (A, ≺, ) is a noncommutative shuffle algebra.

Example 7 (Hoffman, [START_REF] Hoffman | Quasi-shuffle products[END_REF]). Let V be an associative, non unitary algebra. The product of v, w ∈ V is denoted by v.w. The augmentation ideal

T + (V ) = n∈N * V ⊗n of the tensor algebra T (V ) = n∈N * T n (V ) = n∈N * V ⊗n (resp. T (V ))
is given a unique (resp. unital) NQSh algebra structure by induction on the length of tensors such that for all a, b ∈ V , for all v, w ∈ T (V ):

av ≺ bw = a(v -bw), av ≻ bw = b(av -w), av • bw = (a.b)(v -w), (15)
where

-=≺ + ≻ +• is called the quasi-shuffle product on T (V ) (by defi- nition: ∀v ∈ T (V ), 1 -v = v = v -1).
Definition 8. The four-tuple (T + (V ), ≺, ≻, •) is the tensor quasi-shuffle algebra associated to V . It is a NQSh algebra and is a quasi-shuffle algebra if, and only if, (V, .) is commutative (and then is called simply the quasishuffle algebra associated to V ).

Here are examples of products in T + (V ). In particular, the restriction of • to V is the product of V . If the product of V is zero, we obtain the usual shuffle product .

A very useful observation, to which we will refer as "Schützenberger's trick" (see [START_REF] Schützenberger | Sur une propriété combinatoire des algèbres de lie libres pouvant être utilisée dans un problème de mathématiques appliquées, Séminaire Dubreil-Jacotin Pisot[END_REF]) is that, in

T + (V ), for v 1 , . . . , v n ∈ V , (16) v 1 . . . v n = v 1 ≺ (v 2 ≺ . . . (v n-1 ≺ v n ) . . . )).

Quasi-shuffle bialgebras

We recall that graded connected and more generally conilpotent bialgebras are automatically equipped with an antipode [START_REF]A primer of hopf algebras[END_REF], so that the two notions of bialgebras and Hopf algebras identify when these conditions are satisfied -this will be most often the case in the present article.

Quasi-shuffle bialgebras are particular deformations of shuffle bialgebras associated to the exponential and logarithm maps. They were first introduced by Hoffman in [START_REF] Hoffman | Quasi-shuffle products[END_REF] and studied further in [START_REF] Loday | On the algebra of quasi-shuffles[END_REF][START_REF] Foissy | Deformations of shuffles and quasi-shuffles[END_REF]. The existence of a natural isomorphism between the two categories of bialgebras is known as Hoffman's isomorphism [START_REF] Hoffman | Quasi-shuffle products[END_REF] and has been studied in depth in [START_REF] Foissy | Deformations of shuffles and quasi-shuffles[END_REF].

We introduce here a theoretical approach to their definition, namely through the categorical notion of Hopf operads, see [START_REF] Livernet | Lie theory for hopf operads[END_REF]. The underlying ideas are elementary and deserve probably to be better known. We avoid using the categorical or operadic langage and present them simply (abstract definitions and further references on the subject are given in [START_REF] Livernet | Lie theory for hopf operads[END_REF]).

Let us consider categories of binary algebras, that is algebras defined by one or several binary products satisfying homogeneous multilinear relations (i.e. algebras over binary operads). For example, commutative algebras are algebras equipped with a binary product • satisfying the relations x • (y • z) = (x • y) • z and x • y = y • x, and so on. Multilinear means that letters should not be repeated in the defining relations: for example, n-nilpotent algebras defined by a binary product with x n = 0, n > 1 are excluded.

The category of algebras will be said non-symmetric if in the defining relations the letters x, y, z... always appear in the same order. For example, the category Com of commutative algebras is not non-symmetric because of the relation x • y = y • x, whereas As, the one of associative algebras

(x • (y • z) = (x • y) • z) is.
Notice that the categories Sh, QSh of shuffle and quasi-shuffle algebras are not non-symmetric (respectively because of the relation x ⋆ y = x ≺ y + y ≺ x and because of the commutativity of the • product) and are equipped with a forgetful functor to Com. The categories NSh, NQSh of noncommutative shuffle and quasi-shuffle algebras are non-symmetric (in their defining relations the letters x, y, z are not permuted) and are equipped with a forgetful functor to As. Equivalently, it is a coalgebra in the tensor category of C -algebras. Further requirements can be made in the definition of bialgebras, for example when algebras have units. When C = Com or As, we recover the usual definition of bialgebras. Proposition 11. A category of binary algebras equipped with a forgetful functor to Com is Hopfian. In particular, Pois, Sh, QSh are Hopfian.

Here Pois stands for the category of Poisson algebras, studied in [START_REF] Livernet | Lie theory for hopf operads[END_REF] from this point of view.

Indeed, let C be a category of binary algebras equipped with a forgetful functor to Com. We write µ 1 , . . . , µ n the various binary products on A, B ∈ C and • the commutative product (which may be one of the µ i , or be induced by these products as the ⋆ product is induced by the ≺, ≻ and • products in the case of shuffle and quasi-shuffle algebras). Notice that a given category may be equipped with several distinct forgetful functors to Com: the quasishuffle algebras carry, for example, two commutative products (• and ⋆).

The Proposition follows by defining properly the C -algebra structure on the tensor products A ⊗ B:

µ i (a ⊗ b, a ′ ⊗ b ′ ) := µ i (a, a ′ ) ⊗ b • b ′ .
The new products µ i on A ⊗ B clearly satisfy the same relations as the corresponding products on A, which concludes the proof. Notice that one could also define a "right-sided" structure by

µ i (a ⊗ b, a ′ ⊗ b ′ ) := a • a ′ ⊗ µ i (b, b ′ ).
A bialgebra (without a unit) in the category of quasi-shuffle algebras is a bialgebra in the Hopfian category QSh, where the Hopfian structure is induced by the ⋆ product. Concretely, it is a quasi-shuffle algebra A equipped with a coassociative map ∆ in QSh to A ⊗ A, where the latter is equipped with a quasi-shuffle algebra structure by:

(17) (a ⊗ b) ≺ (a ′ ⊗ b ′ ) = (a ≺ a ′ ) ⊗ (b ⋆ b ′ ), ( 18
) (a ⊗ b) • (a ′ ⊗ b ′ ) = (a • a ′ ) ⊗ (b ⋆ b ′ ).
The same process defines the notion of shuffle bialgebra (without a unit), e.g. by taking a null • product in the definition. Using Sweedler's shortcut notation ∆(a) =: a (1) ⊗ a (2) , one has: (2) .

(19) ∆(a ≺ b) = a (1) ≺ b (1) ⊗ a (2) ⋆ b (2) , (20)
∆(a • b) = a (1) • b (1) ⊗ a (2) ⋆ b
In the unital case, B = k ⊕ A, one requires furthermore that ∆ be a counital coproduct (with ∆(1) = 1 ⊗ 1) and, since 1 ≺ 1 and 1 • 1 are not defined, sets:

(

1 ⊗ b) ≺ (1 ⊗ b ′ ) = 1 ⊗ (b ≺ b ′ ), (1 ⊗ b) • (1 ⊗ b ′ ) = 1 ⊗ (b • b ′ ).
Since unital quasi-shuffle and shuffle bialgebras are more important for applications, we call them simply quasi-shuffle bialgebras and shuffle bialgebras. In this situation it is convenient to introduce the reduced coproduct on A, ∆(a) := ∆(a) -a ⊗ 1 -1 ⊗ a.

Concretely, we get:

Definition 12. The unital QSh algebra k ⊕ A equipped with counital coassociative coproduct ∆ is a quasi-shuffle bialgebra if and only if for all x, y ∈ A (we introduce for the reduced coproduct the Sweedler-type notation

∆(x) = x ′ ⊗ x ′′ ): (21) ∆(x ≺ y) = x ′ ≺ y ′ ⊗x ′′ ⋆y ′′ +x ′ ⊗x ′′ ⋆y+x ≺ y ′ ⊗y ′′ +x ′ ≺ y⊗x ′′ +x⊗y, (22) ∆(x • y) = x ′ • y ′ ⊗ x ′′ ⋆ y ′′ + x ′ • y ⊗ x ′′ + x • y ′ ⊗ y ′′ .
The same constructions and arguments hold in the non-symmetric context. We do not repeat them and only state the conclusions. Proposition 13. A non-symmetric category of binary algebras equipped with a forgetful functor to As is Hopfian. In particular, NSh and NQSh are Hopfian.

A bialgebra (without a unit) in the category of noncommutative quasishuffle (NQSh) algebras is a bialgebra in the Hopfian category NQSh, where the Hopfian structure is induced by the ⋆ product. Concretely, it is a NQSh algebra A equipped with a coassociative map ∆ in NQSh to A ⊗ A, where the latter is equipped with a NQSh algebra structure by:

(23) (a ⊗ b) ≺ (a ′ ⊗ b ′ ) = (a ≺ a ′ ) ⊗ (b ⋆ b ′ ), ( 24
) (a ⊗ b) ≻ (a ′ ⊗ b ′ ) = (a ≻ a ′ ) ⊗ (b ⋆ b ′ ), ( 25
) (a ⊗ b) • (a ′ ⊗ b ′ ) = (a • a ′ ) ⊗ (b ⋆ b ′ ).
The same process defines the notion of NSh (or dendriform) bialgebra (without a unit), e.g. by taking a null • product in the definition.

Recall that setting :=≺ +• defines a forgetful functor from NQSh to NSh algebras. The same definition yields a forgetful functor from NQSh to NSh bialgebras.

In the unital case, one requires furthermore that ∆ be a counital coproduct (with ∆(1) = 1 ⊗ 1) and sets

(1 ⊗ b) ≺ (1 ⊗ b ′ ) = 1 ⊗ (b ≺ b ′ ),
and similarly for ≻ and •. Since this case is more important for applications, we call simply NQSh and NSh bialgebras the ones with a unit. Definition 14. The unital NQSh algebra k ⊕ A equipped with counital coassociative coproduct ∆ is a NQSh bialgebra if and only if for all x, y ∈ A:

(26) ∆(x ≺ y) = x ′ ≺ y ′ ⊗x ′′ ⋆y ′′ +x ′ ⊗x ′′ ⋆y+x ≺ y ′ ⊗y ′′ +x ′ ≺ y⊗x ′′ +x⊗y, (27) ∆(x ≻ y) = x ′ ≻ y ′ ⊗x ′′ ⋆y ′′ +y ′ ⊗x⋆y ′′ +x ≻ y ′ ⊗y ′′ +x ′ ≻ y⊗x ′′ +y⊗x, (28) ∆(x • y) = x ′ • y ′ ⊗ x ′′ ⋆ y ′′ + x ′ • y ⊗ x ′′ + x • y ′ ⊗ y ′′ .
Recall, for later use, that a NQSh bialgebra k ⊕ A is connected if the reduced coproduct is locally conilpotent:

A = n≥0 Ker( ∆(n) ),
where ∆(n) is the iterated coproduct of order n (and Ker( ∆(n) ) is also denoted P rim(A), the set of primitive elements) and similarly for the other unital bialgebras we will consider.

The reason for the importance of the unital case comes from Hoffman's:

Example 15. Let V be an associative, non unitary algebra. With the deconcatenation coproduct ∆, defined by:

∆(x 1 . . . x n ) = n i=0 x 1 . . . x i ⊗ x i+1 . . . x n ,
the tensor quasi-shuffle algebra T (V ) is a NQSh bialgebra. When V is commutative, it is a quasi-shuffle bialgebra.

Lie theory for quasi-shuffle bialgebras

The structural part of Lie theory, as developed for example in Bourbaki's Groupes et Algèbres de Lie [START_REF] Bourbaki | Groupes et algèbres de lie[END_REF] and Reutenauer's monograph on free Lie algebras [START_REF] Ch | Free lie algebras[END_REF], is largely concerned with the structure of enveloping algebras and cocommutative Hopf algebras. It was shown in [START_REF] Livernet | Lie theory for hopf operads[END_REF] that many phenomena that might seem characteristic of Lie theory do actually generalize to other families of bialgebras -precisely the ones studied in the previous section, that is the ones associated with Hopfian categories of algebras equiped with a forgetful functor to Com or As.

The most natural way to study these questions is by working with twisted algebras over operads -algebras in the category of S-modules (families of representations of all the symmetric groups S n , n ≥ 0) or, equivalently, of functors from finite sets to vector spaces. However, doing so systematically requires the introduction of many terms and preliminary definitions (see [START_REF] Livernet | Lie theory for hopf operads[END_REF]), and we prefer to follow here a more direct approach inspired by the theory of combinatorial Hopf algebras. The structures we are going to introduce are reminiscent of the Malvenuto-Reutenauer Hopf algebra [START_REF] Malvenuto | Duality between quasi-symmetrical functions and the solomon descent algebra[END_REF], whose construction can be deduced from the Hopfian structure of As, see [START_REF] Patras | On descent algebras and twisted bialgebras[END_REF][START_REF] Patras | Twisted descent algebras and the solomon-tits algebra[END_REF][START_REF] Patras | Trees, set compositions and the twisted descent algebra[END_REF] and [START_REF] Livernet | Lie theory for hopf operads[END_REF]Exple 2.3.4]. The same process will allow us to contruct a combinatorial Hopf algebra structure on the operad QSh of quasi-shuffle algebras.

Recall that an algebraic theory such as the ones we have been studying (associative, commutative, quasi-shuffle, NQSh... algebras) is entirely characterized by the behaviour of the corresponding free algebra functor F : an analytic functor described by a sequence of symmetric group representation F n (i.e. a S-module) so that, for a vector space V , F (V ) = n F n ⊗ Sn V ⊗n . Composition of operations for F -algebras are encoded by natural transformations from F • F to F . By a standard process, this defines a monad, and F -algebras are the algebras over this monad. The direct sum F = n F n equipped with the previous (multilinear) composition law is called an operad, and F -algebras are algebras over this operad. Conversely, the F n are most easily described as the multilinear part of the free F -algebras F (X n ) over the vector space spanned by a finite set with n elements, X n := {x 1 , . . . , x n }. Here, multilinear means that F n is the intersection of the n eigenspaces associated to the eigenvalue λ of the n operations induced on F (X n ) by the map that scales x i by λ (and acts as the identity on the x j , j = i).

Let X be a finite set, and let us anticipate on the next Lemma and write QSh(X) := T + (k[X] + ) for the quasi-shuffle algebra associated to k[X] + , the (non unital, commutative) algebra of polynomials without constant term over X. For I a multiset over X, we write x I the associated monomial (e.g. if

I = {x 1 , x 3 , x 3 }, x I = x 1 x 2 3 ). The tensors x I 1 . . . x In = x I 1 ⊗ • • • ⊗ x In form a basis of QSh(X).
There are several ways to show that QSh(X) is the free quasi-shuffle algebra over X: the property can be deduced from the classical constructions of commutative Rota-Baxter algebras by Cartier [START_REF] Cartier | On the structure of free baxter algebras[END_REF] or Rota [START_REF] Rota | Baxter algebras and combinatorial identities. i, ii[END_REF][START_REF]Fluctuation theory and baxter algebras[END_REF] (indeed the tensor product x I 1 . . . x In corresponds to the Rota-Baxter monomial

x I 1 R(x I 2 R(x I 3 . . . R(x In ) . . . ))
) in the free RB algebra over X). It can be deduced from the construction of the free shuffle algebra over X by standard filtration/graduation arguments. It can also be deduced from a Schur functor argument [START_REF] Loday | On the algebra of quasi-shuffles[END_REF]. The simplest proof is but the one due to Schützenberger for shuffle algebras that applies almost without change to quasi-shuffle algebras [36, p. 1-19].

Lemma 16. The quasi-shuffle algebra QSh(X) is the (unique up to isomorphism) free quasi-shuffle algebra over X.

Indeed, let A be an arbitrary quasi-shuffle algebra generated by X. Then, one checks easily by a recursion using the defining relations of quasi-shuffle algebras that every a ∈ A is a finite sum of "normed terms", that is terms of the form

x I 1 ≺ (x I 2 ≺ (x I 3 • • • ≺ x In ) . . . ). But, if A = QSh(X), by the Schützenberger's trick, x I 1 ≺ (x I 2 ≺ (x I 3 • • • ≺ x In ) . . . ) = x I 1 . . .

x

In ; the result follows from the fact that these terms form a basis of QSh(X).

Corollary 17. The component QSh n of the operad QSh identifies therefore with the linear span of tensors x I 1 . . . x I k , where

I 1 • • • I k = [n].
Let us introduce useful notations. We write x I := x I 1 . . . x I k , where I denotes an arbitrary ordered sequence of disjoint subsets of N * , I 1 , . . . , I k , and set

|I| := |I 1 |+• • •+|I k |. Recall that the standardization map associated to a subset I = {i 1 , . . . , i n } of N * , where i 1 < • • • < i n is the map st from I to [n]
defined by: st(i k ) := k. The standardization of I is then the ordered sequence st(I) := st(I 1 , . . . , I k ), where st is the standardization map associated to the subset I 1 • • • I k of the integers. We also set st(x I ) := x st(I) . For example, if I = {2, 6}, {5, 9}, st(I) = {1, 3}, {2, 4} and st(x I ) = x 1 x 3 ⊗ x 2 x 4 . The shift by k of a subset I = {i 1 , . . . , i n } (or a sequence of subsets, and so on...) of N * , written I + k, is defined by

I + k := {i 1 + k, . . . , i n + k}.
Theorem 18. The operad QSh of quasi-shuffle algebras inherits from the Hopfian structure of its category of algebras a NQSh bialgebra structure whose product operations are defined by:

x I ≺ x J := x I ≺ f x J +n , x I ≻ x J := x I ≻ f x J +n , x I • x J := x I • f x J +n ,
where I and J run over ordered partitions of [n] and [m]; the coproduct is defined by:

∆(x) := (st ⊗ st) • ∆ f (x)
, where, on the right-hand sides, ≺ f , ≻ f , • f , ∆ f stand for the corresponding operations on QSh(N * ) (where, as usual, x ≺ f y =: y ≻ f x).

The link with the Hopfian structure of the category of quasi-shuffle algebras refers to [START_REF] Livernet | Lie theory for hopf operads[END_REF]Thm 2.3.3]: any connected Hopf operad is a twisted Hopf algebra over this operad. The Theorem 18 can be thought of as a reformulation of this general result in terms of NQSh bialgebras.

The fact that QSh is a NQSh algebra follows immediately from the fact that QSh(N * ) is a NQSh algebra for ≺ f , ≻ f , • f , together with the fact that the category of NQSh algebras is non-symmetric. The coalgebraic properties and their compatibility with the NQSh algebra structure are less obvious and follow from the following Lemma (itself a direct consequence of the definitions): Lemma 19. Let I = I 1 , . . . , I k and J = J 1 , . . . , J l be two ordered sequence of disjoint subsets of N * that for any n ∈ I p , p ≤ k and any m ∈ J q , q ≤ l we have n < m. Then:

st(x I ≺ f x J ) = x st(I) ≺ f x st(J )+|I| = x st(I) ≺ x st(J ) , st(x I ≻ f x J ) = x st(I) ≻ f x st(J )+|I| = x st(I) ≻ x st(J ) , st(x I • f x J ) = x st(I) • f x st(J )+|I| = x st(I) • x st(J ) .
The Hopf algebra QSh is naturally isomorphic with WQSym, the Chapoton-Hivert Hopf algebra of word quasi-symmetric functions, that has been studied in [START_REF] Novelli | Natural endomorphisms of quasi-shuffle hopf algebras[END_REF][START_REF] Foissy | Deformations of shuffles and quasi-shuffles[END_REF], also in relation to quasi-shuffle algebras, but from a different point of view.

Let us conclude this section by some insights on the "Lie theoretic" structure underlying the previous constructions on QSh (where "Lie theoretic" refers concretely to the behaviour of the functor of primitive elements in a class of bialgebras associated to an Hopfian category with a forgetful functor to As or Com). Recall that there is a forgetful functor from quasi-shuffle algebras to commutative algebras defined by keeping only the • product. Dualy, the operad Com embeds into the operad QSh: Com n is the vector space of dimension 1 generated by the monomial x 1 . . . x n , and through the embedding into QSh this monomial is sent to the monomial (a tensor of length 1) Only the last sentence needs to be proved. It follows from the relations:

x •n 1 := x 1 • • • • • x 1 in
1 • x = x • 1 = 0 for x ∈ QSh n , n ≥ 1.
From the point of view of S-modules, the Theorem should be understood in the light of [21, Thm 2.4.2]: for P a connected Hopf operad, the space of primitive elements of the twisted Hopf P -algebra P is a sub-operad of P.

As usual in categories of algebras a forgetful functor such as the one from QSh to Com induced by • has a left adjoint, see e.g. [START_REF] Getzler | Operads, homotopy algebra and iterated integrals for double loop spaces[END_REF] for the general case and [START_REF] Loday | On the algebra of quasi-shuffles[END_REF] for quasi-shuffle algebras. This left adjoint, written U (by analogy with the case of classical enveloping algebras: U (A) ∈ QSh for A ∈ Com equipped with a product written •) is, up to a canonical isomorphism, the quotient of the free quasi-shuffle over the vector space A by the relations

a • b = a • b.
When the initial category is Hopfian, such a forgetful functor to a category of algebras over a naturally defined sub-operad arises from the properties of the tensor product of algebras in the initial category, see [21, Thm 2.4.2 and Sect. 3.1.2] -this is exactly what happens with the pair (As, Lie) in the classical situation where the left adjoint is the usual enveloping algebra functor, and here for the pair (QSh, Com).

Lemma 21 (Quasi-shuffle PBW theorem). The left adjoint U of the forgetful functor from QSh to Com, or "quasi-shuffle enveloping algebra" functor from Com to QSh, is (up to isomorphism) Hoffman's quasi-shuffle algebra functor T + .

An elementary proof follows once again from (a variant of) Schützenberger's construction of the free shuffle algebra. Notice first that T + (A) is generated by A as a quasi-shuffle algebra, and that, in it, the relations a

• b = a • b hold. Moreover, choosing a basis (a i ) i∈I of A, the tensors a i 1 . . . a in = a i 1 ≺ (a i 2 ≺ • • • ≺ a in ) . . . ) form a basis of T + (A).
On the other hand, by the definition of the left adjoint U (A) as a quotient of Sh(A) by the relations a • b = a • b, using the defining relations of quasi-shuffle algebras, any term in U (A) can be written recursively as a sum of terms in "normed form"

a i 1 ≺ (a i 2 ≺ . . . (a i n-1 ≺ a in ) . . . ). The Lemma follows.
Notice that the existence of a basis of

T + (A) of tensors a i 1 . . . a in = a i 1 ≺ (a i 2 ≺ • • • ≺ a in ) . . . )
is the analog, for quasi-shuffle enveloping algebras, of the Poincaré-Birkhoff-Witt (PBW) basis for usual enveloping algebras.

Endomorphism algebras

We follow once again the analogy with the familiar notion of usual enveloping algebras and connected cocommutative Hopf algebras and study, in this section the analogs of the convolution product of their linear endomorphisms. Surjections happen to play, for quasi-shuffle algebras T (A) associated to commutative algebras A, the role played by bijections in classical Lie theory, see [START_REF] Malvenuto | Duality between quasi-symmetrical functions and the solomon descent algebra[END_REF] and [START_REF] Novelli | Natural endomorphisms of quasi-shuffle hopf algebras[END_REF][START_REF] Foissy | Deformations of shuffles and quasi-shuffles[END_REF]. Proposition 22. Let A be a coassociative (non necessarily counitary) coalgebra with coproduct ∆ : A -→ A ⊗ A, and B be a NQSh algebra. The space of linear morphisms Lin(A, B) is given a NQSh algebra structure in the following way: for all f, g ∈ Lin(A, B),

f ≺ g =≺ •(f ⊗ g) • ∆, f ≻ g =≻ •(f ⊗ g) • ∆, f • g = • • (f ⊗ g) • ∆. ( 29
)
Proof. The construction follows easily from the fact that NQSh is nonsymmetric and from the coassociativity of the coproduct. As an example, let us prove (5) using Sweedler's notation for ∆. Let f, g, h ∈ Lin(A, B).

For all x ∈ A, (f ≻ g) ≺ h(x) = (f ≻ g)(x ′ ) ≺ h(x ′′ ) = (f ((x ′ ) ′ ) ≻ g((x ′ ) ′′ )) ≺ h(x ′′ ) = f (x ′ ) ≻ (g((x ′′ ) ′ ) ≺ h((x ′′ ) ′′ ) = f (x ′ ) ≻ (g ≺ h)(x ′′ ) = f ≻ (g ≺ h)(x). So (f ≻ g) ≺ h = f ≻ (g ≺ h).
Remark. The induced product ⋆ on Lin(A, B) is the usual convolution product.

Corollary 23. The set of linear endomorphisms of A, where k ⊕ A is a NQSh bialgebra is naturally equiped with the structure of a NQSh algebra.

Let us turn now to the quasi-shuffle analog of the Malvenuto-Reutenauer noncommutative shuffle algebra of permutations. The appearance of a noncommutative shuffle algebra of permutations in Lie theory in [START_REF] Malvenuto | Duality between quasi-symmetrical functions and the solomon descent algebra[END_REF] can be understood operadically by noticing that the linear span of the n-th symmetric group S n is As n , the n-th component of the operad of associative algebras (or also the n-th component of QSh, the quasi-shuffle operad). The same reason explain why surjections appear naturally in the study of quasishuffle algebras: ordered partitions of initial subsets of the integers (say {2, 4}, {5}, {1, 3}) parametrize a natural basis of QSh n , and such ordered partitions are canonically in bijection with surjections (here, the surjection s from [START_REF] Chapoton | Algebres de hopf des permutoedres, associaedres et hypercubes[END_REF] to [START_REF]Fonctions polylogarithmes, nombres polyzêtas et groupes pro-unipotents[END_REF] defined by s(2) = s(4) = 1, s(5) = 2, s(1) = s(3) = 3). Let us show how the NQSh algebra structure of QSh can be recovered from the point of view of the structure of NQSh algebras of linear endomorphisms. In the process, we also give explicit combinatorial formulas for the corresponding structure maps ≺, ≻, •. We also point out that composition of endomorphisms leads to a new product on QSh (such a product is usually called "internal product" in the theory of combinatorial Hopf algebras, we follow the use, see [START_REF] Gelfand | Noncommutative symmetric functions[END_REF][START_REF] Novelli | Natural endomorphisms of quasi-shuffle hopf algebras[END_REF]).

Let n ≥ 0. We denote by Surj n the set of maps σ : [n] := {1, . . . , n} -→ N * such that σ({1, . . . , n}) = {1, . . . , k} for a certain k. The corresponding elements in QSh n are the ordered partitions σ -1 ({1}), . . . , σ -1 ({k}) of [n]. The integer k is the maximum of σ and denoted by max(σ). The element σ ∈ Surj n will be represented by the packed word (σ(1) . . . σ(n)) (recall that a word n 1 . . . n k over the integers is called packed if the underlying set S = {n 1 , . . . , n k } is an initial subset of N * , that is, S = [m] for a certain m). We identify in this way elements of Surj n with packed words of length n. For later use, recall also that any word n 1 . . . n k over the integers can be packed: pack(n 1 . . . n k ) = m 1 . . . m k is the unique packed word preserving the natural order of letters (m i < m j ⇔ n i < n j , m i = m j ⇔ n i = n j , e.g. pack(6353) = 3121).

We assume that V is an associative, commutative algebra and work with the quasi-shuffle algebra T + (V ). Let σ ∈ Surj n , n ≥ 1. We define F σ ∈ End K (T (V )) in the following way: for all x 1 , . . . , x l ∈ V ,

F σ (x 1 . . . x l ) =              σ(i)=1 x i   . . .   σ(i)=max(σ) x i   if k = l, 0 otherwise.
Note that in each parenthesis, the product is the product of V . For example, if x, y, z ∈ V ,

F (123) (xyz) = xyz F (132) (xyz) = xzy F (213) (xyz) = yxz F (231) (xyz) = zxy F (312) (xyz) = yzx F (321) (xyz) = zyx F (122) (xyz) = x(y.z) F (212) (xyz) = y(x.z) F (221) (xyz) = z(x.y) F (112) (xyz) = (x.y)z F (121) (xyz) = (x.z)y F (211) (xyz) = (y.z)x F (111) (xyz) = x.y.z.
We also define F 1 , where 1 is the empty word, by

F 1 (x 1 . . . x n ) = ε(x 1 . . . x n )1 = δ x 1 ...xn,1 .
Notations. Let k, l ≥ 0.

(1) (a) We denote by QSh k,l the set of (k, l) quasi-shuffles, that is to say elements σ ∈ Surj k+l such that σ(1) < . . . < σ(k) and The subspace of End K (T (V )) generated by the maps F σ is stable under composition and the products:

σ(k + 1) < . . . < σ(k + l). (b) QSh ≺ k,l is the set of (k, l) quasi-shuffles σ such that σ -1 ({1}) = {1}. (c) QSh ≻ k,l is the set of (k, l) quasi-shuffles σ such that σ -1 ({1}) = {k + 1}. (d) QSh • k,l is the set of (k, l) quasi-shuffles σ such that σ -1 ({1}) = {1, k + 1}. Note that QSh k,l = QSh ≺ k,l ⊔ QSh ≻ k,l ⊔ QSh • k,l . (2) If σ ∈ Surj k and τ ∈ Surj l , σ ⊗ τ is the element of Surj
Proposition 24. Let σ ∈ Surj k and τ ∈ Surj l . (1) If max(τ ) = k, then F σ • F τ = F σ•τ . Otherwise, this composition is equal to 0. ( 2
)
F σ ≺ F τ = ζ∈QSh ≺ k,l F ζ•(σ⊗τ ) , F σ ≻ F τ = ζ∈QSh ≻ k,l F ζ•(σ⊗τ ) , F σ • F τ = ζ∈QSh • k,l F ζ•(σ⊗τ ) , F σ -F τ = ζ∈QSh k,l F ζ•(σ⊗τ ) .
The same formulas describe the structure of the operad QSh as a NQSh algebra (i.e., in QSh, using the identification between surjections and ordered partitions,

σ ≺ τ = ζ∈QSh ≺ k,l ζ • (σ ⊗ τ )
, and so on).

Proof. The proof of 1. and 2. follows by direct computations. The identification with the corresponding formulas for QSh follows from the identities, for all x 1 , . . . , x k+l ∈ V , in the quasi-shuffle algebra T + (A):

x 1 . . . x k ≺ x k+1 . . . x k+l = ζ∈QSh ≺ k,l F ζ (x 1 . . . x k+l ), x 1 . . . x k ≻ x k+1 . . . x k+l = ζ∈QSh ≻ k,l F ζ (x 1 . . . x k+l ), x 1 . . . x k • x k+1 . . . x k+l = ζ∈QSh • k,l F ζ (x 1 . . . x k+l ), x 1 . . . x k -x k+1 . . . x k+l = ζ∈QSh k,l F ζ (x 1 . . . x k+l ).
Moreover:

x 1 . . . x k x k+1 . . . x k+l = ζ∈Sh k,l F ζ (x 1 . . . x k+l ),
where Sh k,l is the set of (k, l)-shuffles, that is to say S k+l ∩ QSh k,l .

Remarks.

(1) F (1...n) is the projection on the space of words of length n. Consequently:

Id = ∞ n=0 F (1...n) .
(2) In general, this action of packed words is not faithful. For example, if A is a trivial algebra, then for any σ ∈ Surj k \ S k , F σ = 0. (3) Here is an example where the action is faithful.

Let A = K[X i | i ≥ 1] + .
Let us assume that a σ F σ = 0. Acting on the word X 1 . . . X k , we obtain:

σ∈Surj k a σ   σ(i)=1 X i   . . .   σ(i)=max(σ) X i   = 0.
As the X i are algebraically independent, the words appearing in this sum are linearly independent, so for all σ, a σ = 0.

Canonical projections on primitives

This section studies the analog, for quasi-shuffle bialgebras, of the canonical projection from a connected cocommutative Hopf algebra to its primitive part -the logarithm of the identity (see e.g. [START_REF] Ch | Free lie algebras[END_REF][START_REF] Patras | La décomposition en poids des algebres de hopf[END_REF][START_REF]L'algèbre des descentes d'une bigèbre graduée[END_REF]).

Recall that a coalgebra with a coassociative coproduct ∆ is connected if and only if the coproduct il locally conilpotent. Proposition 25. Let A be a coassociative, non counitary, coalgebra with a locally conilpotent coproduct

∆ : A -→ A ⊗ A, A = n≥0 Ker( ∆(n) ),
and let B be a NQSh algebra. Then, for any f ∈ Lin(A, B), there exists a unique map π f ∈ Lin(A, B), such that

f = π f + π f ≺ f.
Proof. For all n ≥ 1, we put F n = Ker( ∆(n) ): this defines the coradical filtration of A. In particular,

F 1 =: P rim(A). Moreover, if n ≥ 1: ∆(F n ) ⊆ F n-1 ⊗ F n-1 .
Let us choose for all n a subspace E n of A such that

F n = F n-1 ⊕ E n . In particular, E 1 = F 1 = P rim(A).
Then, A is the direct sum of the E n 's and for all n:

∆(E n ) ⊆ i,j<n E i ⊗ E j .
Existence. We inductively define a map π f : E n -→ B for all n ≥ 1 in the following way:

• For all

a ∈ E 1 , π f (a) = f (a). • If a ∈ E n , as ∆(a) ∈ i+j<n E i ⊗ E j , (π f ⊗ f )• ∆(a) is already defined.
We then put:

π f (a) = f (a)-≺ •(π f ⊗ f ) • ∆(a) = f (a) -(π f ≺ f )(a) Unicity. Let µ f such that f = µ f + (µ f ≺ f ). For all a ∈ E 1 , f (a) = µ f (a)+ 0, so µ f (a) = π f (a). Let us assume that for all k < n, µ f (a) = π f (a) if a ∈ E k . Let a ∈ E n . Then: a = µ f (a) + µ f (a ′ ) ≺ a ′′ = µ f (a) + π f (a ′ ) ≺ a ′′ = µ f (a) + a -π f (a), so µ f (a) = π f (a). Hence, µ f = π f .
Proposition 26. When A = B = T + (V ) and f = Id, the map π := π f defined in proposition 25 is equal to the projection F (1) .

Proof. First, observe that, as

QSh ≺ 1,k = {(1, . . . , k)}, for all packed words (a 1 . . . a k ), F (1) ≺ F (a 1 ...a k ) = F (1a 1 +1...a k +1) . Hence, in A: F (1) +F (1) ≺ Id A = F (1) + ∞ n=1 F (1) ≺ F (1...n) = F (1) + ∞ n=1 F (1...n+1) = ∞ n=1 F (1...n) = Id A .
By unicity in proposition 25, π f = F (1) .

More generally, we have: Proposition 27. Let A be a non unital, connected NQSh bialgebra, and π the unique solution to

Id A = π + π ≺ Id A ,
then π is a projection on P rim(A), and for all x ∈ P rim(A), y ∈ A, π(x ≺ y) = 0.

Proof. Let us prove that for all a ∈ E n , π(a) ∈ P rim(A) by induction on n. As E 1 = P rim(A), this is obvious if n = 1. Let us assume the result for all k < n. Let a ∈ E n . Then π(a) = a -π(a ′ ) ≺ a ′′ . By the induction hypothesis, we can assume that π(a ′ ) ∈ P rim(A), so:

∆(π(a)) = a ′ ⊗a ′′ -π(a ′ ) ≺ a ′′ ⊗a ′′′ -π(a ′ )⊗a ′′ = (a ′ -(π ≺ Id)(a ′ )-π(a ′ ))⊗a ′′ = 0.
Hence, for all a ∈ A, π(a) ∈ P rim(a). So π that, by its very definition, acts as the identity on P rim(A), is a projection on P rim(A).

Let x ∈ P rim(A) and y ∈ E n , let us prove that π(x ≺ y) = 0 by induction on n. If n = 1, then y ∈ P rim(A), so ∆(x ≺ y) = x ⊗ y, and π(x ≺ y) = x ≺ y -π(x) ≺ y = x ≺ y -x ≺ y = 0. Let us assume the result at all rank < n. We have:

∆(x ≺ y) = x ≺ y ′ ⊗ y ′′ + x ⊗ y.
By the induction hypothesis, we can assume that π(x

≺ y ′ ) = 0, so π(x ≺ y) = x ≺ y -0 -π(x) ≺ y = x ≺ y -x ≺ y = 0.
Remark. For all x, y ∈ P rim(A):

π(x ≺ y) = 0, π(x ≻ y) = x ≻ y -y ≺ x, π(x • y) = x • y.
Corollary 28. Let A be a nonunital, connected quasi-shuffle bialgebra. Then P rim(A) is stable under • and the following map is an isomorphism of quasi-shuffle bialgebras:

θ : T + (P rim(A)) -→ A a 1 . . . a k -→ a 1 ≺ (a 2 ≺ (. . . ≺ a k ) . . .).
Proof. Let a 1 , . . . , a k ∈ P rim(A). An easy induction on k proves that:

∆(θ(a 1 ⊗ . . . ⊗ a k )) = k-1 i=1 θ(a 1 ⊗ . . . ⊗ a i ) ⊗ θ(a i+1 ⊗ . . . ⊗ a k ).
So θ is a coalgebra morphism. From this coalgebra morphism property and the identity π(x ≺ y) = 0 for x ∈ P rim(A), we get for a 1 , . . . , a k ∈ P rim(A),

(Id A ⊗ π) • ∆(θ(a 1 ⊗ . . . ⊗ a k )) = θ(a 1 ⊗ . . . ⊗ a k-1 ) ⊗ θ(a k ).
Since θ is the identity on its restriction to P rim(A), its injectivity follows by induction.

θ(a ≺ b) = θ(a) ≺ θ(b), θ(a ≻ b) = θ(a) ≻ θ(b), θ(a • b) = θ(a) • θ(b). If k = 1, then a ≺ b 1 . . . b l = ab 1 . . . b l , so θ(a ≺ b) = a ≺ θ(b) = θ(a) ≺ θ(b). If l = 1, then a ≻ b = ba, so θ(a ≻ b) = b ≺ θ(a) = θ(b) ≺ θ(a) = θ(a) ≻ θ(b). If k = l = 1, , x•y = π(x•y) ∈ P rim(A), so θ(a•b) = a•b = θ(a)
θ(a ≺ b) = a 1 ≺ (θ(a 2 . . . a k )⋆θ(b)) = (a 1 ≺ θ(a 2 . . . a k )) ≺ θ(b) = θ(a) ≺ θ(b).
Using the commutativity of T + (P rim(A)) and A, we obtain θ(a

≻ b) = θ(a) ≻ θ(b). If l > 1, a • b = a • (b 1 ≺ b 2 . . . b l ) = (a • b 1 ) ≺ b 2 . . . b l .
Moreover, a • b 1 is a linear span of words of length ≤ k + 1, so, by the preceding computation and the induction hypothesis:

θ(a • b) = θ(a • b 1 ) ≺ θ(b 2 . . . b l ).
The induction hypothesis holds for a and b 1 , so:

θ(a • b) = (θ(a) • θ(b 1 )) ≺ •(b 2 . . . b l ) = θ(a) • (b 1 ≺ θ(b 2 . . . b l )) = θ(a) • θ(b).
If l = 1, then k > 1 and we conclude with the commutativity of •.

Let us now prove that P rim(A) generates A as a quasi-shuffle algebra. Let A ′ be the quasi-shuffle subalgebra of A generated by P rim(A). Let a ∈ E n , let us prove that x ∈ A ′ by induction on n. As E 1 = P rim(A), this is obvious if n = 1. Let us assume the result for all ranks < n. Then a = π(a) + π(a ′ ) ≺ a ′′ . By the induction hypothesis, a ′′ ∈ A ′ . Moreover, π(a) and π(a ′ ) ∈ P rim(A), so a ∈ A ′ .

As a conclusion, θ is a morphism of quasi-shuffle algebras, whose image contains P rim(A), which generates A, so θ is surjective.

Relating the shuffle and quasi-shuffle operads

A fundamental theorem of the theory of quasi-shuffle algebras relates quasi-shuffle bialgebras and shuffle bialgebras and, under some hypothesis (combinatorial and graduation hypothesis on the generators in Hoffman's original version of the theorem [START_REF] Hoffman | Quasi-shuffle products[END_REF]), shows that the two categories of bialgebras are isomorphic. This result allows to understand quasi-shuffle bialgebras as deformations of shuffle bialgebras and, as such, can be extended to other deformations of the shuffle product than the one induced by Hoffman's exponential map, see [START_REF] Foissy | Deformations of shuffles and quasi-shuffles[END_REF]. We will come back to this line of arguments in the next section.

Here, we stick to the relations between shuffle and quasi-shuffle algebras and show that Hoffman's theorem can be better understood and refined in the light of an Hopf algebra morphism relating the shuffle and quasi-shuffle operads.

Let us notice first that the same construction that allows to define a NQSh algebra structure on the operad QSh allows, mutatis mutandis, to define a noncommutative shuffle algebra structure on Sh, the operad of shuffle algebras. A natural basis of the latter operad is given by permutations (the result goes back to Schützenberger, who showed that the tensor algebra over a vector space V is a model of the free shuffle algebra over V [START_REF] Schützenberger | Sur une propriété combinatoire des algèbres de lie libres pouvant être utilisée dans un problème de mathématiques appliquées, Séminaire Dubreil-Jacotin Pisot[END_REF]). Let us stick here to the underlying Hopf algebra structures.

Recall first that the set of packed words (or surjections, or ordered partitions of initial subsets of the integers) Surj is a basis of QSh. As a Hopf algebra, QSh is isomorphic to WQSym, the Hopf algebra of word symmetric functions, see e.g. [START_REF] Foissy | Deformations of shuffles and quasi-shuffles[END_REF] for references on the subject. This Hopf algebra structure is obtained as follows. For all σ ∈ Surj k , τ ∈ Surj l : where for all I ⊆ {1, . . . , max(σ)}, σ |I is the packed word obtained by keeping only the letters of σ which belong to I.

σ ⋆ τ = ζ∈QSh k,l ζ • (σ ⊗ τ ).
On the other hand, the set of permutations is a basis of the operad Sh. As a Hopf algebra, the latter identifies with the Malvenuto-Reutenauer Hopf algebra [START_REF] Malvenuto | Duality between quasi-symmetrical functions and the solomon descent algebra[END_REF] and with the Hopf algebra of free quasi-symmetric functions FQSym. Its Hopf structure is obtained as follows. For all σ ∈ S k , τ ∈ S l :

σ ⋆ τ = ζ∈Sh k,l ζ • (σ ⊗ τ ).
For all σ ∈ S n :

∆(σ) = max(σ) k=0 σ |{1,...,k} ⊗ P ack(σ |{k+1,...,max(σ)} ).
There is an obvious surjective Hopf algebra epimorphism Ξ from QSh to Sh, sending a packed word σ to itself if σ is a permutation, and to 0 otherwise. From an operadic point of view, this maps amounts to put to zero the • product. There is however another, non operadic, transformation, relating the two structures.

Theorem 29. We use the following notations:

(1) Let σ ∈ S n and τ ∈ Surj n . We shall say that τ ∝ σ if:

∀1 ≤ i, j ≤ n, (σ(i) ≤ σ(j) =⇒ τ (i) ≤ τ (j)).
(

) Let τ ∈ Surj n . We put τ ! = max(τ ) i=1 |τ -1 ({i})|!. 2
We consider the following map:

Φ :    Sh -→ QSh σ ∈ S n -→ τ ∝σ τ τ ! .
Then Φ is an injective Hopf algebra morphism. Moreover it is equivariant:

for all σ, τ ∈ S n , Φ(σ • τ ) = Φ(σ) • τ.
Proof. Let σ, τ ∈ S n . Then τ ∝ σ if, and only if, σ = τ . So, for all σ ∈ S n : Φ(σ) = σ + linear span of packed words which are not permutations.

So Ξ • Φ = Id Sh , and Φ is injective.

Let τ ∈ Surj n and σ ∈ S n . Then τ ∝ σ if, and only if,

τ • σ -1 ∝ I n . Moreover, |τ • σ -1 |! = τ !, as σ is a bijection. Hence: Φ(σ) = τ ∝σ τ τ ! = ρ∝In ρ • σ ρ! = Φ(I n ) • σ. More generally, if σ, τ ∈ S n , Φ(σ • τ ) = Φ(I n ) • (σ • τ ) = (Φ(I n ) • σ) • τ = Φ(σ) • τ . Let σ 1 ∈ S n 1 and σ 2 ∈ S n 2 . Φ(σ 1 ) ⋆ Φ(σ 2 ) = τ 1 ∝σ 1 ,τ 2 ∝σ 2 ζ∈QSh(max(τ 1 ),max(τ 2 )) ζ • (τ 1 ⊗ τ 2 ) τ 1 !τ 2 ! .
Let S be the set of elements σ ∈ Surj n 1 +n 2 such that:

• For all 1 ≤ i, j ≤ n 1 , σ 1 (i) ≤ σ 1 (j) =⇒ σ(i) ≤ σ(j). • For all 1 ≤ i, j ≤ n 2 , σ 2 (i) ≤ σ 2 (j) =⇒ σ(i + n 1 ) ≤ σ(j + n 2 ). Let τ 1 ∝ σ 1 , τ 2 ∝ σ 2 and ζ ∈ QSh(max(τ 1 ), max(τ 2 )
). As ζ is increasing on {1, . . . , max(τ 1 )} and {max(τ 1 )+1, . . . , max(τ

1 )+max(τ 2 )}, ζ •(τ 1 ⊗τ 2 ) ∈ S. Conversely, if σ ∈ S, there exists a unique τ 1 ∈ Surj n 1 , τ 2 ∈ Surj n 2 and ζ ∈ QSh max(τ 1 ),max(τ 2 ) such that σ = ζ • (τ 1 ⊗ τ 2 )
: in particular, τ 1 = P ack(σ(1) . . . σ(n 1 )) and τ 2 = P ack(σ(n 1 + 1) . . . σ(n 1 + n 2 )). As σ ∈ S and ζ ∈ QSh max(τ 1 ),max(τ 2 ) , τ 1 ∝ σ 1 and τ 2 ∝ σ 2 . Hence:

Φ(σ 1 ) ⋆ Φ(σ 2 ) = σ∈S σ P ack(σ(1) . . . σ(n 1 ))!P ack(σ(n 1 + 1) . . . σ(n 1 + n 2 ))! .
On the other hand:

Φ(σ 1 ⋆ σ 2 ) = ζ∈Sh(n 1 ,n 2 ) τ ∝ζ•(σ 1 ⊗σ 2 ) τ τ ! . Let ζ ∈ Sh(n 1 , n 2 ) and τ ∝ ζ • (σ 1 ⊗ σ 2 ). If 1 ≤ i, j ≤ n 1 and σ 1 (i) ≤ σ 1 (j), then: ζ • (σ 1 ⊗ σ 2 )(i) = ζ(σ 1 (i)) ≤ ζ(σ 1 (j)) = ζ • (σ 1 ⊗ σ 2 )(i), so τ (i) ≤ τ (j). If 1 ≤ i, j ≤ n 2 and σ 2 (i) ≤ σ 2 (j), then: ζ•(σ 1 ⊗σ 2 )(i+n 1 ) = ζ(σ 2 (i)+max(σ 1 )) ≤ ζ(σ 2 (j)+max(σ 1 )) = ζ•(σ 1 ⊗σ 2 )(j+n 1 ), so τ (i + n 1 ) ≤ τ (j + n 2 )
. Hence, τ ∈ S and finally:

Φ(σ 1 ⋆ σ 2 ) = τ ∈S τ τ ! ♯{ζ ∈ Sh(n 1 , n 2 ) | τ ∝ ζ • (σ 1 ⊗ σ 2 )}.
Let τ ∈ S. We put τ 1 = (τ (1) . . . τ (n 1 )) and τ 2 = (τ (n 1 + 1) . . . τ

(n 1 + n 2 )). Let ζ ∈ Sh(n 1 , n 2 ), such that τ ∝ ζ • (σ 1 ⊗ σ 2 ). For all 1 ≤ i ≤ max(τ ), ζ(τ -1 ({i})) = I i is
max(τ ) i=1 |τ -1 (i)|! |τ -1 1 ({i})|!|τ -1 2 ({i})|! = max(τ ) i=1 |τ -1 ({i})|! max(τ 1 ) i=1 |τ -1 1 ({i})|! max(τ 2 ) i=1 |τ -1 2 ({i})|! = max(τ ) i=1 |τ -1 ({i})|! max(P ack(τ 1 )) i=1 |P ack(τ 1 ) -1 ({i})|! max(P ack(τ 2 )) i=1 |P ack(τ 2 ) -1 ({i})|! = τ ! P ack(τ 1 )!P ack(τ 2 )! .
Hence:

Φ(σ 1 ⋆ σ 2 ) = τ ∈S τ τ ! τ ! P ack(τ (1) . . . τ (n 1 ))!P ack(τ (n 1 + 1) . . . τ (n 1 + n 2 ))! = Φ(σ 1 ) ⋆ Φ(σ 2 ). So Φ is an algebra morphism. Let σ ∈ S n . ∆(Φ(σ)) = τ ∝σ max(τ ) k=0 1 τ ! τ |{1,...,
τ 1 τ 1 ! ⊗ τ 2 τ 2 ! = (Φ ⊗ Φ) • ∆(σ).
Hence, Φ is a coalgebra morphism.

Examples.

Φ((1)) = (1), Φ(( 12)) = ( 12 More generally:

Φ((1 . . . n)) = n k=1 i 1 +...+i k =n 1 i 1 ! . . . i k ! (1 i 1 . . . k i k ).
Remark. The map Φ is not a morphism of NSh algebras from (Sh, ≺, ≻) to (QSh, , ≻), nor to (QSh, ≺, ). Indeed:

Φ((1) ≺ (1)) = (12) + 1 2 (11), Φ((1)
) ≺ Φ((1)) = ( 12), Φ((1)) Φ((1)) = ( 12) + [START_REF] Fauvet | Ecalle's arborification-coarborification transforms and connes-kreimer hopf algebra[END_REF].

We extend the map σ -→ F σ into a linear map from QSh to End(T (V )). By proposition 24, F is an algebra morphism.

Corollary 30 (Exponential isomorphism). Le us consider the following linear map:

φ : T (V ) -→ T (V ) x 1 . . . x n -→ F Φ(In) (x 1 . . . x n ).
Then φ is a Hopf algebra isomorphism from (T (V ), , ∆) to (T (V ), -, ∆).

Proof. Let x 1 , . . . , x k+l ∈ V . φ(x 1 . . . x k x k+1 . . . x k+l ) = ζ∈Sh(k,l) F Φ(I k+l ) • F ζ (x 1 . . . x k+l ) = ζ∈Sh(k,l) F Φ(I k+l )•ζ (x 1 . . . x k+l ) = ζ∈Sh(k,l) F Φ(ζ) (x 1 . . . x k+l ) = F Φ(I k ⋆I l ) (x 1 . . . x k+l ) = F Φ(I k )⋆Φ(I l ) (x 1 . . . x k+l ) = F Φ(I k ) -F Φ(I l ) (x 1 . . . x k+l ) = k+l i=0 F Φ(I k ) (x 1 . . . x i ) -F Φ(I l ) (x i+1 . . . x k+l ) = F Φ(I k ) (x 1 . . . x k ) -F Φ(I l ) (x k+1 . . . x k+l ) = φ(x 1 . . . x k ) -φ(x k+1 . . . x l ).
So φ is an algebra morphism.

For any packed words σ ∈ Surj k , τ ∈ Surj l and all x 1 , . . . , x n ∈ V we define G σ⊗τ by:

G σ⊗τ (x 1 . . . x n ) = F σ (x 1 . . . x k ) ⊗ F τ (x k+1 . . . x n )
is k + l = n and = 0 else. Then, for all increasing packed word σ, for all x ∈ T (V ):

∆(F σ (x)) = G ∆(σ) (x). Hence, if x 1 , . . . , x n ∈ V : ∆ • φ(x 1 . . . x n ) = G ∆(Φ(In)) (x 1 . . . x n ) = G (Φ⊗Φ)•∆(In) (x 1 . . . x n ) = n k=0 G Φ(I k )⊗Φ(I n-k ) (x 1 . . . x n ) = n k=0 F Φ(I k ) (x 1 . . . x k ) ⊗ F Φ(I n-k ) (x k+1 . . . x n ) = n k=0 φ(x 1 . . . x k ) ⊗ φ(x k+1 . . . x n ) = (φ ⊗ φ) • ∆(x 1 . . . x n ).
So φ is a coalgebra morphism.

As the unique bijection appearing in Φ(I n ) is I n , for all word x 1 . . . x n :

φ(x 1 . . . x n ) = x 1 . . . x n + linear span of words of length < n.

So φ is a bijection.

Examples. Let x 1 , x 2 , x 3 , x 4 ∈ V . φ(x 1 ) = x 1 , φ(x 1 x 2 ) = x 1 x 2 + 1 2 x 1 .x 2 , φ(x 1 x 2 x 3 ) = x 1 x 2 x 3 + 1 2 (x 1 .x 2 )x 3 + 1 2 x 1 (x 2 .x 3 ) + 1 6 x 1 .x 2 .x 3 , φ(x 1 x 2 x 3 x 4 ) = x 1 x 2 x 3 x 4 + 1 2 (x 1 .x 2 )x 3 x 4 + 1 2 x 1 (x 2 .x 3 )x 4 + 1 2 x 1 x 2 (x 3 .x 4 ) + 1 4 (x 1 .x 2 )(x 3 .x 4 ) + 1 6 (x 1 .x 2 .x 3 )x 4 + 1 6 x 1 (x 2 .x 3 .x 4 ) + 1 24 x 1 .x 2 .x 3 .x 4 .
More generally, for all x 1 , . . . , x n ∈ V :

φ(x 1 . . . x n ) = n k=1 i 1 +...+i k =n 1 i 1 ! . . . i k ! F (1 i 1 ...k i k ) (x 1 . . . x n ).
Remarks.

(1) This isomorphism is the morphism denoted by exp and obtained in the graded case by Hoffman in [START_REF] Hoffman | Quasi-shuffle products[END_REF]. (2) If V is a trivial algebra, then φ = Id T (V ) .

(3) This morphism is not a NSh algebra morphism, except if V is a trivial algebra. In fact, except if the product of V is zero, the NSh algebras (T (V ), , ≻) and (T (V ), ≺, ) are not commutative, so cannot be isomorphic to a shuffle algebra.

Coalgebra and Hopf algebra endomorphisms

In the previous section, we studied the links between shuffle and quasishuffle operads and obtained as a corollary the exponential isomorphism of Cor. 30 between the shuffle and quasi-shuffle Hopf algebra structures on T (V ). This section aims at classifying all such possible (natural, i.e. functorial in commutative algebras V ) morphisms. We refer to our [START_REF] Foissy | Deformations of shuffles and quasi-shuffles[END_REF] for applications of natural coalgebra endomorphisms to the study of deformations of shuffle bialgebras.

Recall that we defined π as the unique linear endomorphism of the quasishuffle bialgebra

T + (V ) such that π + π ≺ Id T + (V ) = Id T + (V )
. By proposition 26, it is equal to F (1) , so is the canonical projection on V . This construction generalizes as follows.

Hereafter, we work in the unital setting and write ε for the canonical projection from T (V ) to the scalars (the augmentation map). It behaves as a unit w.r.t. the NQSh products on End(T + (V )): for g ∈ End(T + (V )), ε ≺ g = 0, g ≺ ε = g. Proposition 31. Let f : T (V ) -→ V be a linear map such that f (1) = 0. There exists a unique coalgebra endomorphism ψ of T (V ) such that π•ψ = f . This coalgebra endomorphism is the unique linear endomorphism of T (V ) such that ε + f ≺ ψ = ψ.

Proof. First step. Let us prove the unicity of the coalgebra morphism ψ such that π • ψ = f . Let ψ 1 , ψ 2 be two (non zero) coalgebra endomorphisms such that π • ψ 1 = π • ψ 2 . Let us prove that for all x 1 , . . . , x n ∈ V , ψ 1 (x 1 . . . x n ) = ψ 2 (x 1 . . . x n ) by induction on n. If n = 1, as ψ 1 (1) and ψ 2 (1) are both nonzero group-like elements, they are both equal to 1. Let us assume the result at all rank < n. Then:

∆ • ψ 1 (x 1 . . . x n ) = (ψ 1 ⊗ ψ 1 ) • ∆(x 1 . . . x n ) = ψ 1 (x 1 . . . x n ) ⊗ 1 + 1 ⊗ ψ 1 (x 1 . . . x n ) + n-1 i=1 ψ 1 (x 1 . . . x i ) ⊗ ψ 1 (x i+1 . . . x n ), ∆ • ψ 2 (x 1 . . . x n ) = ψ 2 (x 1 . . . x n ) ⊗ 1 + 1 ⊗ ψ 2 (x 1 . . . x n ) + n-1 i=1 ψ 2 (x 1 . . . x i ) ⊗ ψ 2 (x i+1 . . . x n ).

Applying the induction hypothesis, for all

i ≤ 1 ≤ n -1, ψ 1 (x 1 . . . x i ) = ψ 2 (x 1 . . . x i ) and ψ 1 (x i+1 . . . x n ) = ψ 2 (x i+1 . . . x n ). Consequently, ψ 1 (x 1 . . . x n )- ψ 2 (x 1 . . . x n ) is
primitive, so belongs to V and:

ψ 1 (x 1 . . . x n ) -ψ 2 (x 1 . . . x n ) = π • ψ 1 (x 1 . . . x n ) -π • ψ 2 (x 1 . . . x n ) = 0.
Second step. Let us prove the existence of a (necessarily unique) endomorphism ψ such that ψ = ε + f ≺ ψ. We construct ψ(x 1 . . . x n ) for all x 1 , . . . , x n ∈ V by induction on n in the following way: ψ(1) = 1 and, if n ≥ 1:

ψ(x 1 . . . x n ) := f (x 1 . . . f n ) + n-1 i=1 f (x 1 . . . x i ) ≺ ψ(x i+1 . . . x n ). Then (ε + f ≺ ψ)(1) = ε(1) = 1 = ψ(1). If n ≥ 1: (ε + f ≺ ψ)(x 1 . . . x n ) = ε(x 1 . . . x n ) + f (x 1 . . . x n ) + n-1 i=1 f (x 1 . . . x i ) ≺ ψ(x i+1 . . . x n ) = 0 + f (x 1 . . . x n ) + n-1 i=1 f (x 1 . . . x i ) ≺ ψ(x i+1 . . . x n ) = ψ(x 1 . . . x n ). Hence, ε + f ≺ ψ = ψ. Third step. Let ψ such that ε + f ≺ ψ = ψ. Let us prove that ∆ • ψ(x 1 . . . x n ) = (ψ ⊗ ψ) • ∆(x 1 . . . x n ) by induction on n. If n = 0, then ψ(1) = ε(1) + f (1) = 1 + 0 = 1, so ∆ • ψ(1) = (ψ ⊗ ψ) • ∆(1) = 1 ⊗ 1. If n ≥ 1, we put x = x 1 . . . x n , ∆(x) = x ⊗ 1 + 1 ⊗ x + x ′ ⊗ x ′′ .
The induction hypothesis holds for x ′′ . Moreover:

ψ(x) = ε(x) + f (x) + f (x ′ ) ≺ ψ(x ′′ ) = f (x) + f (x ′ ) ≺ ψ(x ′′ ). As f (x), f (x ′ ) ∈ V are primitive: ∆ • ψ(x) = f (x ′ ) ⊗ ψ(x ′′ ) + f (x ′ ) ≺ ψ(x ′′ ) ′ ⊗ ψ(x ′′ ) ′ = f (x ′ ) ⊗ ψ(x ′′ ) + f (x ′ ) ≺ ψ(x ′′ ) ⊗ ψ(x ′′′ ) = ψ(x ′ ) ⊗ ψ(x ′′ ) = (ψ ⊗ ψ) • ∆(x). As ψ(1) = 1, we deduce that ∆ • ψ(x) = (ψ ⊗ ψ) • ∆(x). So ψ is a coalgebra morphism. Moreover, π • ψ(1) = π(1) = 0 = f (1). If ε(x) = 0: π • ψ(x) = π • f (x) + π(f (x ′ ) ≺ f (x ′′ )) = f (x), as f (x), (x ′ ) ∈ V (so f (x ′ ) ≺ f (x ′′
) is a linear span of words of length ≥ 2, so vanishes under the action of π). Hence, π • ψ = f . Proposition 32. Let A = n≥1 a n X n be a formal series without constant term. Let f A be the linear map from T (V ) to V defined by f A (x 1 . . . x n ) = a n x 1 • . . . • x n and let φ A be the unique coalgebra endomorphism of T (V ) such that π • φ A = f A . For all x 1 , . . . , x n ∈ V :

(30) φ A (x 1 . . . x n ) = n k=1 i 1 +...+i k =n a i 1 . . . a i k F (1 i 1 ...k i k ) (x 1 . . . x n ). Proof. Note that f A (x 1 . . . x n ) = a n F (1 n ) (x 1 . . . x n ).
Let φ be the morphism defined by the second member of [START_REF] Patras | On descent algebras and twisted bialgebras[END_REF].

Then (ε + f A ≺ φ)(1) = 1 + f A (1) = 1 = φ(1). If n ≥ 1: (ε + f A ≺ φ)(x 1 . . . x n ) = f A (x 1 . . . x n ) + n-1 i=1 f A (x 1 . . . x i ) ≺ φ(x i+1 . . . x n ) = a n F (1 n ) (x 1 . . . x n ) + n-1 i=1 n k=2 i 2 +...+i k =n-i a i a i 2 . . . a i k F (1 i ) ≺ F (1 i 2 ...(k-1) i k ) (x 1 . . . x n ) = a n F (1 n ) (x 1 . . . x n ) + n-1 i=1 n k=2 i+i 2 +...+i k =n a i a i 2 . . . a i k ≺ F (1 i 2 i 2 ...k i k ) (x 1 . . . x n ) = φ(x 1 . . . x n ).
By unicity in proposition 31, φ = φ A .

Remark. The morphism φ defined in corollary 30 is φ exp(X)-1 .

Proposition 33. φ X = Id and for all formal series A, B without constant terms,

φ A • φ B = φ A•B . Proof. For all x 1 , . . . , x n ∈ V , π•Id(x 1 . . . x n ) = δ 1,n x 1 . . . x n = f X (x 1 . . . x n ).
By unicity in proposition 31, φ X = Id. Moreover:

π • φ A • φ B (x 1 . . . x n ) = f A   n k=1 i 1 +...+i k =n b i 1 . . . b i k (x 1 • . . . • x i 1 ) . . . (x i 1 +...+i k-1 +1 • . . . • x 1+...+i k )   = n k=1 i 1 +...+i k =n a k b i 1 . . . b i k x 1 • . . . • x n = f A•B (x 1 . . . x n ).

By unicity in proposition 31, φ

A • φ B = φ A•B .
So the set of all φ A , where A is a formal series such that A(0) = 0 and A ′ (0) = 1, is a subgroup of the group of coalgebra isomorphisms of T (V ), isomorphic to the group of formal diffeomorphisms of the line.

Corollary 34. The inverse of the isomorphism φ defined in corollary 30 is φ ln(1+X) :

φ -1 (x 1 . . . x n ) = n k=1 i 1 +...+i k =n (-1) n+k i 1 . . . i k F (1 i 1 ...k i k ) (x 1 . . . x n ). Proposition 35. Let A ∈ K[[X]] + .
(1) φ A : (T (V ), , ∆) -→ (T (V ), , ∆) is a Hopf algebra morphism for any commutative algebra V if, and only if, A = aX for a certain

a ∈ K. (2) φ A : (T (V ), , ∆) -→ (T (V ), -, ∆) is a Hopf algebra morphism
for any commutative algebra V if, and only if,

A = exp(aX) -1 for a certain a ∈ K. (3) φ A : (T (V ), -, ∆) -→ (T (V ), -, ∆) is a Hopf algebra morphism
for any commutative algebra V if, and only if

, A = (1 + X) a -1 for a certain a ∈ K. (4) φ A : (T (V ), -, ∆) -→ (T (V ), , ∆) is a Hopf algebra morphism
for any commutative algebra V if, and only if, A = a ln(1 + X) for a certain a ∈ K.

Proof. First, note that for any x 1 , . . . , x k ∈ V :

π • φ A (x 1 . . . x k ) = a k F (1...1) (x 1 . . . x k ).
Consequently, for any commutative algebra V , for any x, x 1 , . . . ,

x k ∈ V , k ≥ 1: π • φ A (x x 1 . . . x k ) = π(xx 1 . . . x k+1 + . . . + x 1 . . . x k+1 x) = (k + 1)a k+1 x.x 1 • . . . • x k , π(φ A (x) φ A (x 1 . . . x k )) = 0, π(φ A (x) -φ A (x 1 . . . x k )) = a 1 a k x.x 1 • . . . • x k .
1. We assume that φ A is an algebra morphism for any V for the shuffle product. Let us choose an algebra V and elements x, x 1 , . . . , x k ∈ V such that x.x 1 • . . . • x k = 0 in V . As φ(x x 1 . . . x k ) = φ(x) φ(x 1 . . . x k ), applying π, we deduce that for all k ≥ 1, (k + 1)a k+1 = 0, so a k+1 = 0. Hence, A = a 1 X. Conversely, for any x 1 , . . . , x k ∈ V , φ aX (x 1 . . . x k ) = a k 1 x 1 . . . x k , so φ aX is an endomorphism of the Hopf algebra (T (V ), , ∆).

2. We already proved that φ exp(X)-1 is a Hopf algebra morphism from (T (V ), , ∆) to (T (V ), -, ∆). By composition:

φ exp(aX)-1 = φ exp(X)-1 •φ aX : (T (V ), , ∆) -→ (T (V ), , ∆) -→ (T (V ), -, ∆)
is a Hopf algebra morphism.

We assume that φ A is an algebra morphism for any V from the shuffle product to the quasi-shuffle product. Let us choose an algebra V , and

x, x 1 , . . . , x k ∈ V , such that x.x 1 • . . . • x k = 0 in V . As φ(x x 1 . . . x k ) = φ(x) -φ(x 1 . . . x k ), applying π, we deduce that for all k ≥ 1, (k + 1)a k+1 = a 1 a k , so a k = a k 1 k! for all k ≥ 1. Hence, A = exp(a 1 X) -1.
3. The following conditions are equivalent:

• For any V , φ A : (T (V ), -, ∆) -→ (T (V ), -, ∆) is a Hopf algebra morphism. • For any V , φ ln(1+X) •φ A •φ exp(X)-1 : (T (V ), , ∆) -→ (T (V ), , ∆) is a Hopf algebra morphism. For any V , φ ln(1+X)•A•(exp(X)-1) : (T (V ), , ∆) -→ (T (V ), , ∆) is a Hopf algebra morphism. • There exists a ∈ K, ln(1 + X) • A • (exp(X) -1) = aX. • There exists a ∈ K, A = (1 + X) a -1. 4. Similar proof.
Remark. The Proposition 35 classifies actually all the Hopf algebra endomorphisms and morphisms relating shuffle and quasi-shuffle algebras T (V ), that are natural (i.e. functorial) in V . This naturality property follows formally from the study of nonlinear Schur-Weyl duality in [START_REF] Novelli | Natural endomorphisms of quasi-shuffle hopf algebras[END_REF][START_REF] Foissy | Deformations of shuffles and quasi-shuffles[END_REF].

Coderivations and graduations

The present section complements the previous one that studied coalgebra endomorphisms. We aim at investigating here coderivations of quasi-shuffle bialgebras. As an application we recover the existence of a natural graded structure on the Hopf algebras (T (V ), -, ∆) [START_REF] Foissy | Deformations of shuffles and quasi-shuffles[END_REF].

Notations. Let A be a NQSh algebra, f ∈ End K (A) and v ∈ A. We define:

f ≺ v : A -→ A x -→ f (x) ≺ v, v ≺ f : A -→ A x -→ v ≺ f (x).
Proposition 36. Let f : T (V ) -→ V be a linear map. There exists a unique coderivation D of T (V ) such that π • D = f . Moreover, D is the unique linear endomorphism of T (V ) such that D = f + π ≺ D + f ≺ Id.

Proof. First step. Let us prove that the unicity of the coderivation D such that π•D = f . Let D 1 and D 2 be two coderivations such that π [START_REF] Bourbaki | Groupes et algèbres de lie[END_REF]. Let us assume the result at all ranks < n.

•D 1 = π•D 2 . Let us prove that D 1 (x 1 . . . x n ) = D 2 (x 1 . . . x n ) by induction on n. ∆ • D 1 (1) = (D 1 ⊗ Id + Id ⊗ D 1 )(1 ⊗ 1) = D 1 (1) ⊗ 1 + 1 ⊗ D 1 (1), so D 1 (1) ∈ P rim(T (V )) = V . Similarly, D 2 (1) ∈ V . Hence, D 1 (1) = π • D 1 (1) = π • D 2 (1) = D 2
If p = 1 or 2: ∆•D p (x 1 . . . x n ) = n i=0 D p (x 1 . . . x i )⊗x i+1 . . . x n + n i=0 x 1 . . . x i ⊗D p (x i+1 . . . x n ).
Applying the induction hypothesis at all ranks < k, we obtain by substraction:

∆•(D 1 -D 2 )(x 1 . . . x n ) = (D 1 -D 2 )(x 1 . . . x n )⊗1+1⊗(D 1 -D 2 )(x 1 . . . x n ). So (D 1 -D 2 )(x 1 . . . x n ) ∈ V . Applying π: (D 1 -D 2 )(x 1 . . . x n ) = π • (D 1 -D 2 )(x 1 . . . x n ) = 0. So D 1 (x 1 . . . x n ) = D 2 (x 1 . . . x n ).
Second step. Let us prove the existence of a map D such that D = f +π ≺ D + f ≺ Id. We define D(x 1 . . . x n ) by induction on n by D(1) = f (1) and:

D(x 1 . . . x n ) = x 1 ≺ D(x 2 . . . x n )+ n-1 i=0 f (x 1 . . . x i ) ≺ x i+1 . . . x n +f (x 1 . . . x n ). Then (f + π ≺ D + f ≺ Id)(1) = f (1) = D(1). If n ≥ 1: (f + π ≺ D + f ≺ Id)(x 1 . . . x n ) = f (x 1 . . . x n ) + n i=1 π(x 1 . . . x i ) ≺ D(x i+1 . . . x n ) + n-1 i=0 f (x 1 . . . x i ) ≺ x i+1 . . . x n = f (x 1 . . . x n ) + x 1 ≺ D(x 2 . . . x n ) + n-1 i=0 f (x 1 . . . x i ) ≺ x i+1 . . . x n = D(x 1 . . . x n ). So D = f + π ≺ D + f ≺ Id. Last step. Let D such that D = f + π ≺ D + f ≺ Id. Let us prove that ∆ • D(x 1 . . . x n ) = (D ⊗ Id + Id ⊗ D) • ∆(x 1 . . . x n ) by induction on n. If n = 0: ∆ • D(1) = ∆(f (1)) = f (1) ⊗ 1 + 1 ⊗ f (1) = D(1) ⊗ 1 + 1 ⊗ D(1) = (D ⊗ Id + Id ⊗ D)(1 ⊗ 1).
Let us assume the result at all ranks < n.

D(x 1 . . . x n ) = (f + π ≺ D + f ≺ Id)(x 1 . . . x n ) = n i=1 π(x 1 . . . x i ) ≺ D(x i+1 . . . x n ) + n-1 i=0 f (x 1 . . . x i ) ≺ x i+1 . . . x n + f (x 1 . . . x n ) = x 1 D(x 2 . . . x n ) + n i=0 f (x 1 . . . x i )x i+1 . . . x n .
Hence:

∆ • D(x 1 . . . x n )) = n j=1 x 1 D(x 2 . . . x j ) ⊗ x j+1 . . . x n + n j=1 x 1 . . . x j ⊗ D(x j+1 . . . x n ) + 1 ⊗ x 1 D(x 2 . . . x n ) + n i=0 n j=i f (x 1 . . . x i )x i+1 . . . x j ⊗ x j+1 . . . x n + n i=0 1 ⊗ f (x 1 . . . x i )x i+1 . . . x n = n j=1 x 1 D(x 2 . . . x j ) ⊗ x j+1 . . . x n + n j=1 x 1 . . . x j ⊗ D(x j+1 . . . x n ) + 1 ⊗ x 1 D(x 2 . . . x n ) + n j=1 j i=1 f (x 1 . . . x i )x i+1 . . . x j ⊗ x j+1 . . . x n + f (1) ⊗ x 1 . . . x n + n i=0 1 ⊗ f (x 1 . . . x i )x i+1 . . . x n = n j=0 D(x 1 . . . x j ) ⊗ x j+1 . . . x n + n j=1 x 1 . . . x j ⊗ D(x j+1 . . . x n ) = (D ⊗ Id + Id ⊗ D) • ∆(x 1 . . . x n ). Moreover, π • D(1) = π • f (1) = f (1); if n ≥ 1: •D(x 1 . . . x n ) = π(x 1 D(x 2 . . . x n )) + n i=0 π(f (x 1 . . . x i )x i+1 . . . x n ) = 0 + f (x 1 . . . x n ). So π • D = f . Proposition 37. Let A = n≥1 a n X n be a formal series without constant term. Let D A be the unique coderivation of T (V ) such that π • φ A = f A . For all x 1 , . . . , x n ∈ V : (31) D A (x 1 . . . x n ) = n i=1 a i n-i+1 j=1 F (12...j-1j i j+1...n-i+1) (x 1 . . . x n ).
Proof. Let D be the linear endomorphism defined by the right side of (31). As f A (1) = 0, we get by induction on n:

(f + π ≺ D + f ≺ Id)(x 1 . . . x n ) = f (x 1 . . . x n ) + x 1 D(x 2 . . . x n ) + n-1 i=1 f (x 1 . . . x i )x i+1 . . . x n = x 1 D(x 2 . . . x n ) + n i=1 f (x 1 . . . x i )x i+1 . . . x n = n-1 i=1 a i n-i+1 j=2 F (12...j-1j i j+1...n-i+1) (x 1 . . . x n ) + n i=1 a i F (1 i 2...n-i+1) (x 1 . . . x n ) = n i=1 a i n-i+1 j=1 F (12...j-1j i j+1...n-i+1) (x 1 . . . x n ) = D(x 1 . . . x n ). Moreover, π • D(x 1 . . . x n ) = a n x 1 • . . . • x n = f A (x 1 . . . x n ).
The unicity in proposition 36 implies that D = D A .

Corollary 38. For all word x 1 . . .

x n , D X (x 1 . . . x n ) = nx 1 . . . x n . Proof. Indeed, D X (x 1 . . . x n ) = n j=1 F (12...j-1j 1 j+1...n) (x 1 . . . x n ) = nx 1 . . . x n .
Remark. Let A and B be two formal series and λ ∈ K. As D A + λD B is a coderivation and π • (D A + λD B ) = f A + λf B = f A+λB :

D A + λD B = D A+λB .
Moreover, the group of coalgebra automorphims of T (V ) acts on the space of coderivations of T (V ) by conjugacy. Let us precise this action if we work only with automorphisms and coderivations associated to formal series. Proposition 39. Let A, B be two formal series without constant terms, such that A ′ (0) = 0. Then:

φ -1 A • D B • φ A = D B•A A ′ .
Proof. By linearity and continuity of the action, it is enough to prove this formula if B = X p . We denote by C the inverse of A for the composition.

π • φ -1 A • D X p • φ A (x 1 . . . x n ) = f C • D Xp   n k=1 i 1 +...+i k =n a i 1 . . . a i k F (1 i 1 ...k i k ) (x 1 . . . x n )   = n k=p-1 i 1 +...+i k =n (k -p -1)c k-p+1 a i 1 . . . a i k x 1 • . . . • x n . So π • φ A -1 • D X p • φ A is the linear map associated to the formal series:   ∞ k=p-1 (k -p + 1)c k-p+1 X k   • A = ∞ i=0 ia i X i-1+p • A = (X p C ′ ) • A = A p C ′ • A = A p A ′ . Hence, φ A -1 • D X p • φ A = D A p A ′ .
Corollary 40. The eigenspaces of the coderivation D (1+X)ln(1+X) give a gradation of the Hopf algebra (T (V ), -, ∆).

Proof. Let D = φ • D X • φ -1 . As φ = φ exp(X)-1 : D = φ -1 ln(1+X) • D X • φ ln(1+X) = D (1+X)ln(1+X)
. As D X is a derivation of the algebra (T (V ), ) and φ is an algebra isomorphism from (T (V ), ) to (T (V ), -), D is is a derivation of the algebra (T (V ), -). As it is conjugated to D X , its eigenvalues are the elements of N.

Remark. As (1 + X)ln(1

+ X) = 1 + ∞ k=2 (-1) k k(k -1)
X k :

D (1+X)ln(1+X) (x 1 . . . x n ) = nx 1 . . . x n + n i=2 n-i+1 j=1 (-1) i i(i -1)
x 1 . . . x j-1 (x j • . . . • x j+i-1 )x j+i . . . x n .

The gradation of A = (T (V ), -) is given by:

A n = V ect     n k=1 i 1 +...+i k =n 1 i 1 ! . . . i k ! i 1 i=1 x i . . .   i 1 +...+i k i=i 1 +...+i k-1 +1 x i   , x 1 , . . . , x n ∈ V     .

Decorated operads and graded structures

In many applications, algebras over operads carry a natural graduation. This is because geometrical objects (polynomial vector fields, spaces, differential forms. . . ), but also combinatorial and algebraic ones carry often a graduation (or a dimension, a cardinal. . . ) that is better taken into account in the associated algebra structures. As far as quasi-shuffle algebras are concerned, they carry often naturally a graduation in their application domains : think to quasi-symmetric functions and multizeta values (MZVs) [START_REF]Fonctions polylogarithmes, nombres polyzêtas et groupes pro-unipotents[END_REF]; Ecalle's mould calculus and dynamical systems [START_REF] Fauvet | Ecalle's arborification-coarborification transforms and connes-kreimer hopf algebra[END_REF]; iterated integrals of Itô type in stochastic calculus [START_REF] Ebrahimi-Fard | Flows and stochastic taylor series in itô calculus[END_REF][START_REF] Ebrahimi-Fard | The exponential lie series for continuous semimartingales[END_REF].

Here, we explain briefly how the formalism of operads can be adapted to take into account graduations. We detail then the case of quasi-shuffle algebras and conclude by studying the analogue, in this context, of the classical descent algebra of a graded commutative or cocommutative Hopf algebra [START_REF]L'algèbre des descentes d'une bigèbre graduée[END_REF].

In this section, we denote by A = n∈N A n (where A 0 = k, the ground field), a graded, connected, quasi-shuffle bialgebra. By graded we mean that all the structure maps (≺, •, ∆) are graded maps. Then P rim(A) = V = n∈N *

V n is an associative, commutative graded algebra for the product

• and we can identify A and the quasi-shuffle algebra T + (V ) as graded tridendriform algebras. Be aware that the graduation of T + (V ) is not the tensor length: for example, for

v 1 ∈ V n 1 , . . . , v k ∈ V n k , the degree of the tensor v 1 . . . v k ∈ V ⊗k is now n 1 + • • • + n k .
It is an easy exercice to adapt the definition of operads to the graded case: whereas the component F n of an operad identifies with the set of multilinear elements in the n letters x 1 , . . . , x n in the free algebra F (X n ), X n := {x 1 , . . . , x n }, the corresponding graded operad F d n is obtained by considering the set of multilinear elements in the free algebra F (X d n ), where X d n := {x k i } i≤n,d∈N * and where multilinear means now that we consider the subspace i≤n Γ i , where Γ i is the eigenspace of F (X d n ) associated to the eigenvalue λ of the map induced by Notation. Let (σ, d) = σ(1) . . . σ(k) d(1) . . . d(k) be a decorated packed word. Let m be the maximum of σ. We define F (σ,d) ∈ End K (A) in the following way: for all x 1 , . . . , x l ∈ V , homogeneous,

x d i → λx d i , x d j → x d j else. We call F d = ∪ n
F (σ,d) (x 1 . . . x l ) =                σ(i)=1 x i   . . .   σ(i)=m x i   if k = l and deg(x 1 ) = d(1), . . . deg(x k ) = d(k), 0 otherwise.
Note that in each parenthesis, the product is the product • of V . For example, if x, y, z ∈ V are homogeneous,

F (σ,d) • F (τ,e) = F σ • τ (1) . . . σ • τ (l)
e(1) . . . e(l)

.

Otherwise, this composition is equal to 0. Moreover: .

F (σ,d) ≺ F (τ,
Proof. Direct computations.

Remarks.

(1) For all packed word (σ(1) . . . σ(n)): (2) In general, this action of decorated packed words is not faithful. For example, if V = K[X] + , where X is homogeneous of degree n, then F 1 2

F (σ(1)...σ(n)) = d (
1 1 = F 2 1 1 1
. Indeed, both sends the word XX on itself and all the other words on 0. (3) Here is an example where the action is faithful. Let

V = K[X i | i ≥ 1] +
, where X i is homogeneous of degree 1 for all i. Let us assume that a (σ,d) F (σ,d) = 0. Acting on the word (X a 1 1 ) . . . (X a k k ), we obtain:

length(σ)=k a σ(1) . . . σ(k) a 1 . . . a k   σ(i)=1 X a i i   . . .   σ(i)=max(σ) X a i i   = 0.
As the X i are algebraically independent, the words appearing in this sum are linearly independent, so for all (σ, d), a (σ,d) = 0.

Notations.

(1) For all n ≥ 1, we put:

p n = n k=1 d(1)+...+d(k)=n F 1 . . . k d(1) . . . d(k) .
The map p n is the projection on the space of words of degree n, so n≥1 p n = Id A .

(2) For all n ≥ 1, we put:

q n = F 1 n .
The map q n is the projection on the space of letters of degree n, so, by proposition 26, q = n≥1 q n = F (1) is the projection π of proposition 25. It is not difficult to deduce, in the same way as proposition 12 of [START_REF] Foissy | Natural endomorphisms of shuffle algebras[END_REF], the following result:

Theorem 43. The NQSh subalgebra QDesc(A) of End K (A) generated by the homogeneous components p n of Id A is also generated by the homogeneous components q n of the projection on P rim(A) of proposition 25. Moroever, for all n ≥ 1:

q n = n k=1 (-1) k+1 a 1 +...+a k =n p a 1 ≺ (p a 2 -. . . -p a k ).
Remark. This result is the quasi-shuffle analog of the statement that the descent algebra of a graded connected cocommutative Hopf algebra H (the convolution subalgebra of End(H) generated by the graded projections) is equivalently generated by the graded components of the convolution logarithm of the identity [START_REF]L'algèbre des descentes d'une bigèbre graduée[END_REF].

Freeness of the decorated quasi-shuffle operad

In this section, we show that the decorated quasi-shuffle operad QSh d is free as a NSh algebra using the bidendriform techniques developed in [START_REF] Foissy | Bidendriform bialgebras, trees, and free quasi-symmetric functions[END_REF].

We denote by QSh d + the subspace of the decorated quasi-shuffle operad generated by nonempty decorated packed words. As for a well-chosen graded quasi-shuffle bialgebra A the action of packed words is faithful, we deduce .

Notations. Let (σ, d) be a decorated packed word of length k and let I ⊆ {1, . . . , max(σ)}. We put σ -1 (I) = {i 1 , . . . , i l }, with i 1 < . . . < i l . The decorated packed word (σ, d) |I is (P ack(σ(i 1 ), . . . , σ(i l )), (d(i 1 ), . . . , d(i l ))).

Definition 44. We define two coproducts on QSh d + in the following way: for all nonempty packed word (σ, d),

∆ ≺ (σ, d) = max(σ)-1 i=σ(1) (σ, d) |{1,...,i} ⊗ (σ, d) |{{i+1,...,max(σ)} , ∆ ≻ (σ, d) = σ(1)-1 i=1 (σ, d) |{1,...,i} ⊗ (σ, d) |{{i+1,...,max(σ)} .
Then QSh d + is a NSh coalgebra, that is to say:

(∆ ≺ ⊗ Id) • ∆ ≺ = (Id ⊗ (∆ ≺ + ∆ ≻ )) • ∆ ≺ , (32)
(∆ ≻ ⊗ Id) • ∆ ≺ = (Id ⊗ ∆ ≺ ) • ∆ ≻ , (33)
((∆ ≺ + ∆ ≻ ) ⊗ Id) • ∆ ≻ = (Id ⊗ ∆ ≻ ) • ∆ ≻ . (34) For all a, b ∈ QSh d + : ∆ ≺ (a ≺ b) = a ′ ≺ ≺ b ′ ⊗ a ′′ ≺ ⋆ b ′′ + a ′ ≺ ≺ b ⊗ a ′′ ≺ + a ′ ≺ ⊗ a ′′ ≺ ⋆ b (35) + a ≺ b ′ ⊗ b ′′ + a ⊗ b, ∆ ≺ (a ≻ b) = a ′ ≺ ≻ b ′ ⊗ a ′′ ≺ ⋆ b ′′ + a ≻ b ′ ⊗ b ′′ + a ′ ≺ ≻ b ⊗ a ′′ ≺ , (36)
∆ ≺ (a • b) = a ′ ≺ • b ′ ⊗ a ′′ ≺ ⋆ b ′′ + a ′ ≺ • b ⊗ a ′′ ≺ + a • b ′ ⊗ b ′′ , (37) ∆ ≻ (a ≺ b) = a ′ ≻ ≺ b ′ ⊗ a ′′ ≻ ⋆ b ′′ + a ′ ≻ ≺ b ⊗ a ′′ ≻ + a ′ ≻ ⊗ a ′′ ≻ ⋆ b, (38) ∆ ≻ (a ≻ b) = a ′ ≻ ≻ b ′′ ⊗ a ′′ ≻ ⋆ b ′′ + a ′ ≻ ≻ b ⊗ a ′′ ≻ + b ′ ≻ ⊗ a ⋆ b ′′ + b ⊗ a, (39) ∆ ≻ (a • b) = a ′ ≻ • b ′ ⊗ a ′′ ≻ ⋆ b ′′ + a ′ ≻ • b ⊗ a ′′ ≻ . (40)
Remark. We also obtain, by addition:

∆ ≺ (a b) = a ′ ≺ b ′ ⊗ a ′′ ≺ ⋆ b ′′ + a ′ ≺ b ⊗ a ′′ ≺ + a ′ ≺ ⊗ a ′′ ≺ ⋆ b (41) + a b ′ ⊗ b ′′ + a ⊗ b, ∆ ≺ (a b) = a ′ ≺ b ′ ⊗ a ′′ ≺ ⋆ b ′′ + a b ′ ⊗ b ′′ + a ′ ≺ b ⊗ a ′′ ≺ , (42) ∆ ≻ (a b) = a ′ ≻ b ′ ⊗ a ′′ ≻ ⋆ b ′′ + a ′ ≻ b ⊗ a ′′ ≻ + a ′ ≻ ⊗ a ′′ ≻ ⋆ b, (43) ∆ ≻ (a b) = a ′ ≻ b ′′ ⊗ a ′′ ≻ ⋆ b ′′ + a ′ ≻ b ⊗ a ′′ ≻ + b ′ ≻ ⊗ a ⋆ b ′′ + b ⊗ a; (44) ∆(a ≺ b) = a ′ ≺ b ′ ⊗ a ′′ ⋆ b ′′ + a ′ ≺ b ⊗ a ′′ + a ′ ⊗ a ′′ ⋆ b (45) + a ≺ b ′ ⊗ b ′′ + a ⊗ b, ∆(a ≻ b) = a ′ ≻ b ′ ⊗ a ′′ ⋆ b ′′ + a ′ ≻ b ⊗ a ′′ + a ≻ b ′ ⊗ b ′′ (46) + b ′ ⊗ a ⋆ b ′′ + b ⊗ a, ∆(a • b) = a ′ • b ′ ⊗ a ′′ ⋆ b ′′ + a ′ • b ⊗ a ′′ + a • b ′ ⊗ b ′′ ; (47) ∆(a b) = a ′ b ′ ⊗ a ′′ ⋆ b ′′ + a ′ b ⊗ a ′′ + a ′ ⊗ a ′′ ⋆ b (48) + a b ′ ⊗ b ′′ + a ⊗ b, ∆(a b) = a ′ b ′ ⊗ a ′′ ⋆ b ′′ + a ′ b ⊗ a ′′ + a b ′ ⊗ b ′′ (49) + b ′ ⊗ a ⋆ b ′′ + b ⊗ a.
Consequently, (QSh d + , ≻ op , op , ∆ op ≻ , ∆ op ≺ ) and (QSh d + , op , ≺ op , ∆ op ≻ , ∆ op ≺ ) are bidendriform bialgebras [START_REF] Foissy | Bidendriform bialgebras, trees, and free quasi-symmetric functions[END_REF]. By the bidendriform rigidity theorem, (QSh d + , , ≻) and (QSh d + , ≺, ) are free NSh algebras. Forgetting the decoration, we get back theorem 2.5 of [START_REF] Novelli | Polynomial realizations of some trialgebras, Proceedings of Formal Power Series and Algebraic Combinatorics[END_REF], up to a permutation of maximum and minimum, and first and last letters.

Forgeting the decorations, we obtain a NQSh algebra structure on QSh + and a NSh coalgebra structure, with compatibilities (35)-(40). Let us describe, for completeness sake, the dual (half-)products and coproducts. The elements of the dual basis of packed words are denoted by N u .

Proposition 45.

(1) For all nonempty packed words σ, τ , of respective lengths k and l:

N σ ≺ N τ = α∈Sh ≺ k,l N (σ⊗τ )•α -1 , N σ ≻ N τ = α∈Sh ≻ k,l N (σ⊗τ )•α -1 .
(2) For any nonempty packed word σ of length n, denoting by f (σ) the index of the first appearance of 1 in σ and by l(σ) the index of the last appearance of 1 in σ:

∆≺ (N σ ) = n-1 k=l(σ) N pack(σ(1)...σ(k)) ⊗ N pack(σ(k+1)...σ(n)) , ∆≻ (N σ ) = f (σ)-1 k=1 N pack(σ(1)...σ(k)) ⊗ N pack(σ(k+1)...σ(n)) , ∆• (N σ ) = l(σ)-1 k=f (σ) N pack(σ(1)...σ(k)) ⊗ N pack(σ(k+1)...σ(n)) .
12. The quasi-shuffle analog of the descent algebra

Recall that, given a graded NQSh bialgebra A, we introduced QDesc(A), the quasi-shuffle analogue of the descent algebra defined as the NQSh subalgebra of End(A) generated by the graded projections or, equivalently, by the graded components of the projection on P rim(A). We write QDesc for the corresponding NQSh subalgebra of QSh d (the subalgebra generated by the 1 d ). Recall first some properties of NSh algebras. (

) Let t 1 , . . . , t k ∈ T N * Sch and let d 1 , . . . , d k-1 ∈ N * . The element t 1 ∨ d 1 . . . ∨ d k-1 t k 2
is obtained by grafting t 1 , . . . , t k on a common root; for all 1 ≤ i ≤ k, the space between the right leaf of t i and the left leaf of t i+1 is decorated by d i .

Following [START_REF]Trialgebras and families of polytopes, Homotopy theory: relations with algebraic geometry, group cohomology, and algebraic K-theory[END_REF], T D Sch is a basis of the free NQSh algebra generated by D, N QSh(D). The three products are inductively defined:

if t = t 1 ∨ d 1 . . .∨ d k-1 t k and t ′ = t ′ 1 ∨ d ′ 1 . . . ∨ d ′ l-1 t ′ l ∈ T Sch (D), then t ≻ t ′ = (t ⋆ t ′ 1 ) ∨ d ′ 1 t ′ 2 ∨ d ′ 2 . . . ∨ d ′ l-1 t ′ l , t ≺ t ′ = t 1 ∨ d 1 . . . ∨ t k-1 ∨ d k-2 . . . ∨ d k-1 (t k ⋆ t ′ ), t • t ′ = t 1 ∨ d 1 . . . ∨ d k-1 (t k ⋆ t ′ 1 ) ∨ d ′ 1 . . . ∨ d ′ l-1 t ′ l .
Sending any non binary tree to 0, we obtain the free NSh algebra N Sh(D) generated by D. A basis is given by the set of planar binary trees T bin (D) ⊆ T Sch (D) whose spaces between the leaves are decorated by elements of D. The products are given in the following way:

if t = t 1 ∨ d t 2 and t ′ = t ′ 1 ∨ d ′ t ′ 2 ,
(PBT can be constructed directly as a subspace of the direct sum of the symmetric group algebras is by using a construction going back to Viennot: a natural partition of the symmetric groups parametrized by planar binary trees), see [START_REF] Hivert | The algebra of binary search trees[END_REF][START_REF] Hivert | Trees, functional equations, and combinatorial hopf algebras[END_REF][START_REF] Loday | Hopf algebra of the planar binary trees[END_REF]. The second, Desc, is known as the descent algebra [START_REF] Ch | Free lie algebras[END_REF], is isomorphic to Sym, the Hopf algebra of noncommutative symmetric functions, and is the sub Hopf algebra of PBT and Sh freely generated as an associative algebra by (all) the identity permutations using the convolution product ⋆. We get:

Desc = Sym ⊂ PBT = N SH(1) ⊂ Sh = FQSym.
The situation is similar when moving to surjections, that is to QSh. As we already saw, the noncommutative quasi-shuffle sub-bialgebra freely generated by the identity permutation in S 1 (i.e. the packed word 1) is the free NQS algebra on one generator, identified with ST, the linear span of Schröder trees. The sub Hopf algebra of ST and QSh freely generated as an associative algebra by (all) the identity permutations using the convolution product ⋆ is isomorphic (using e.g. that it is a free associative algebra over a countable set of generators) to Desc. We get:

Desc = Sym ⊂ ST = N QSH(1) ⊂ QSh = WQSym.
The aim of the present and last section is to compare explicitely the two sequences of inclusions. The existence of a Hopf algebra map from Sh = FQSym to QSh = WQSym was obtained in [START_REF] Foissy | Deformations of shuffles and quasi-shuffles[END_REF]Cor. 18]. The existence of a map comparing the two copies of the descent algebra follows, a simple direct proof was given in [START_REF] Ebrahimi-Fard | Flows and stochastic taylor series in itô calculus[END_REF]Lemma 7.1]. We aim here at refining these results and extend the constructions to planar and Schröder trees.

We start by showing how planar trees (PBT) can be embedded into Schröder trees (ST).

Definition 47. Let t, t ′ ∈ T Sch .

(1) We denote by R(t) the set of internal edges of t which are right, that is to say edges e such that:

• both extremities of e are internal vertices.

• e is the edge which is at most on the right among all the egdes with the same origin as e. (2) Let I ⊆ R(T ). We denote by t/I the planar reduced tree obtained by contracting all the edges e ∈ I. (3) We shall say that t ′ ≤ t if there exists I ⊆ R(t), such that t ′ = t/I.

Remarks. If I ⊆ R(t), then R(t/I) = R(t) \ I. Moreover, if I, J ⊆ R(t) are disjoint, then (t/I)/J = t/(I ⊔ J). This implies that ≤ is a partial order on T Sch .

Examples. Here are the Hasse graphs of T Sch (2) and T Sch [START_REF]Fonctions polylogarithmes, nombres polyzêtas et groupes pro-unipotents[END_REF].

∨ ∨ ∨ ∨ ∨ ; ∨ ∨ ∨ ∨ ∨ ∨ r ∨ ∨ ∨ ∨ ∨ ∨ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ∨ ∨ ∨ ∨ ∨ ∨ ∨ ∨ a a a a a a a a a ∨ ∨ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ r ∨
It is possible to prove the following points:

• For any t ∈ T Sch , there exists a unique b(t) ∈ T bin , such that t ≤ b(t). We denote by I(t) the unique subset I ⊆ R(b(t)), such that t = b(t)/I. • For any t, t ′ ∈ T Sch , t ≤ t ′ if, and only if, b(t) = b(t ′ ) and I(t) ⊇ I(t ′ ).

Theorem 48. The following map is an injective morphism of bidendriform bialgebras:

ψ :    (PBT, ≺, ≻, ∆ ≺ , ∆ ≻ ) -→ (ST, , ≻, ∆ ≺ , ∆ ≻ ) t ∈ T bin -→ t ′ ≤t t ′ .
Proof. By universal properties of free objects, there exists a unique morphism of noncommutative shuffle algebras ψ ′ from (N Sh(1) = PBT, ≺, ≻)

to (N QSh(1) = ST, , ≻), sending ∨ to ∨ . As ∨ is a primitive element (in the bidendriform sense) for both sides, ψ ′ is a morphism of bidendriform bialgebras. We shall prove that ψ = ψ ′ . Let us show that for all t 1 , t 2 ∈ T bin , ψ ′ (t 1 ∨ t 2 ) = ψ ′ (t 1 ) ≻ ∨ ψ ′ (t 2 ). and ψ(t 1 ∨ t 2 ) = ψ(t 1 ) ≻ ∨ ψ(t 2 ).

The identity ψ = ψ ′ will follow by induction. The identity involving ψ ′ follows immediately from the identity, in T bin :

t 1 ∨ t 2 = t 1 ≻ ∨ ≺ t 2 .
Let us consider the action of ψ. We put t = t 1 ∨ t 2 . We first consider the case where t 2 = . In this case, R(t) = R(t 1 ) and for any I ⊆ R(t 1 ), t/I = (t 1 /I) ∨ . Hence:

ψ(t) = I⊆R(t 1 ) (t 1 /I) ∨ =   I⊆R(t 1 ) t 1 /I   ≻ ∨ = ψ(t 1 ) ≻ ∨ .
We now consider the case where t 2 = . Let r be the internal edge of t relating the root of t to the root of t 2 . Then R(t) = R(t So ψ = ψ ′ . As ≤ is an order, ψ is injective.

We investigate now how the injection of PBT into ST behaves with respect to the respective embeddings into Sh and QSh. We consider the morphism: Proposition 49. [START_REF] Foissy | The hopf algebra of finite topologies and t-partitions[END_REF] Let σ, τ be two packed words of the same length n. We shall say that σ ≤ τ if:

(1) If i, j ∈ [n] and σ(i) ≤ σ(j), then τ (i) ≤ τ (j).

(2) If i, j ∈ [n], i < j and σ(i) > σ(j), then τ (i) > τ (j). Then ≤ is a partial order. Moreover, the following map is a Hopf algebra morphism:

Ψ :    Sh -→ QSh σ -→ τ ≤σ τ.
Here are the Hasse graphs of Surj 2 and Surj 3 :

(12) (21) (11)
;

(123) q q q q q q q q q w w w w w w w w w (122) q q q q q q q q q (112) Proof. We put i = ι(τ ). For any j, τ (j) ≥ τ (i), so σ(j) ≥ σ(i) as σ ≤ τ . So σ(i) = 1, and by definition ι(σ) ≤ i. Let us assume that j < i. By definition of ι(τ ), τ (j) > τ (i). As σ ≤ τ , σ(j) > σ(i), so σ(j) = 1, and ι(σ) = j. So ι(σ) = i.

Proposition 51. The map ̺ : Surj -→ T Sch is a morphism of posets: for any packed words σ, τ , σ ≤ τ =⇒ ̺(σ) ≤ ̺(τ ).

We define a map ω : T Sch -→ Surj by:

• ω( ) = 1,

• ω(t 1 ∨ . . . ∨ t k ) = (ω(t 1 )[1])1 . . . 1(ω(t k ) [START_REF] Bourbaki | Groupes et algèbres de lie[END_REF]). Then ̺ • ω = Id T Sch , and ω is a morphism of posets: for any t, t ′ ∈ T Sch , t ≤ t ′ =⇒ ω(t) ≤ ω(t ′ ).

Proof. Let us prove that ̺ is a morphism. Let σ, τ be two packed words, such that σ ≤ τ ; let us prove that ̺(σ) ≤ ̺(τ ). We proceed by induction on the common length n of σ and τ . If n = 0 or 1, the result is obvious. Let us assume the result at all rank < n. As ι(σ) = ι(τ ), we can write σ = σ ′ 1σ ′′ and τ = τ ′ 1τ ′′ , where σ ′ and τ ′ have the same length and do not contain any 1. By restriction, P ack(σ ′ ) ≤ P ack(τ ′ ) and P ack(σ ′′ ) ≤ P ack(τ ′′ ). By the induction hypothesis, s 0 = ̺(σ ′ ) ≤ ̺(τ ′ ) = t 0 and s 1 ∨ . . . ∨ s k = ̺(σ ′′ ) ≤ ̺(τ ′′ ) = t 1 ∨ . . . ∨ t l . Then:

̺(σ) = s 0 ∨ s 1 ∨ . . . ∨ . . . s k ≤ t 0 ∨ t 1 ∨ . . . ∨ t l = ̺(τ ).

  Let a, b, c ∈ V . a ≺ b = ab, a ≻ b = ba, a • b = a.b, a ≺ bc = abc, a ≻ bc = bac + bca + b(a.c), a • bc = (a.b)c, ab ≺ c = abc + acb + a(b.c), ab ≻ c = cab, ab • c = (a.c)b.

Definition 9 .

 9 Let C be a category of binary algebras. The category is said Hopfian if tensor products of algebras in C are naturally equipped with the structure of an algebra in C (i.e. the tensor product can be defined internally to C ). Classical examples of Hopfian categories are Com and As. Definition 10. A bialgebra in a Hopfian category of algebras C (or Cbialgebra) is an algebra A in C equipped with a coassociative morphism to A ⊗ A in C .

  QSh viewed as a NQSh algebra. Let us write slightly abusively Com for the image of Com in QSh, we have, by definition of the coproduct on QSh: Theorem 20. The operad Com embeds into the primitive part of the operad QSh viewed as a NQSh bialgebra. Moreover, the primitive part of QSh is stable under the • product.

  k+l represented by the packed word στ [max(σ)]., where [k] denotes the translation by k (312[5] = 867).

Let a = a 1

 1 . . . a k and b = b 1 . . . b l ∈ T + (P rim(A)). Let us prove by induction on k + l that:

  •θ(b). All these remarks give the results for k + l ≤ 2. Let us assume the result at all ranks < k + l. If k = 1, we already proved that θ(a ≺ b) = θ(a) ≺ θ(b). If k ≥ 2, a ≺ b = a 1 (a 2 . . . a k -b). By the induction hypothesis applied to a 2 . . . a k and b:

For all σ ∈

 σ Surj n : ∆(σ) = max(σ) k=0 σ |{1,...,k} ⊗ P ack(σ |{k+1,...,max(σ)} ),

  F d n the (integer-)decorated operad associated to F-algebras. The decorated operad QSh d is then spanned by decorated packed words, where: Definition 41. A decorated packed word of length k is a pair (σ, d), where σ is a packed word of length k and d is a map from {1, . . . , k} into N * . We denote it by σ(1) . . . σ(k) d(1) . . . d(k) .

F 2 1 2

 2 a b c (xyz) = y(x • z) if deg(x) = a, deg(y) = b, and deg(z) = c, and 0 otherwise. The subspace of End K (A) generated by these maps is stable under composition and the noncommutative quasi-shuffle products: Proposition 42. Let (σ, d) = σ(1) . . . σ(k) d(1) . . . d(k) and (τ, e) = τ (1) . . . τ (l) e(1) . . . e(l) be two decorated packed words. max(τ ) = k and for all 1 ≤ j ≤ k, τ (i)=j e(i) = d(j), then:

F

  e) = P ack(u(1)...u(k))=σ, P ack(u(k+1)...u(k+l))=τ, min(u(1)...u(k))<min(u(k+1)...u(k+l))F u(1) . . . u(k) u(k + 1) . . . u(k + l) d(1) . . . d(k) e(1) . . . e(l),F (σ,d) ≻ F (τ,e)= P ack(u(1)...u(k))=σ, P ack(u(k+1)...u(k+l))=τ, min(u(1)...u(k))>min(u(k+1)...u(k+l))F u(1) . . . u(k) u(k + 1) . . . u(k + l) (σ,d) • F (τ,e)= P ack(u(1)...u(k))=σ, P ack(u(k+1)...u(k+l))=τ, min(u(1)...u(k))=min(u(k+1)...u(k+l))F u(1) . . . u(k) u(k + 1) . . . u(k + l)

  1),...,d(n)≥1 F σ(1) . . . σ(n) d(1) . . . d(n) .

Notations. Let n ≥ 1 .( 1 )

 11 (a) Let T Sch (n) be the set of Schröder trees of degree n, that is to say reduced planar rooted trees with n + 1 leaves. (b) For any set D, let T D Sch (n) be the set of reduced planar rooted trees t with n + 1 leaves, such that the n spaces between the leaves of t are decorated by elements of D. (c) T D Sch = n≥1 T D Sch (n).

  There exists a unique map from PBT = N Sh(1) to Sh, denoted by Ω ′ , making the following diagram commuting: Sh where the vertical arrows are the canonical projection. For any t ∈ T bin : 123), Ω ′ ( r ) = (312) + (213)

Lemma 50 .

 50 For any packed word σ, we put ι(σ) = min{i | σ(i) = 1}. If σ ≤ τ , then ι(σ) = ι(τ ).

  As Ψ is a coalgebra morphism,∆ • Ψ(σ) = τ ≤σ max(τ ) k=0 τ |[k] ⊗ P ack(τ |[max(τ )]\[k] ) = (k,τ )∈A τ |[k] ⊗ P ack(τ |[max(τ )]\[k] ) = (Ψ ⊗ Ψ) • ∆(σ) = max(σ) k=0 τ ′ ≤σ |[k] τ ′′ ≤P ack(σ |[max(σ)]\[k] ) τ ′ ⊗ τ ′′ = (l,τ ′ ,τ ′′ )∈B τ ′ ⊗ τ ′′ .Hence, there exists a bijectionF : A -→ B, such that, if F (k, τ ) = (l, τ ′ , τ ′′ ), then: • τ ′ = τ |[k] and τ ′′ = P ack(τ |[max(τ )]\[k] ); • l is the unique integer such that τ ′ ≤ σ |[l] . If k ≥ τ (1), then the first letter of τ appears in τ |[k] , so the first letter of σ appears also in σ |[l] . Consequently l ≥ σ(1). Similarly, if l ≥ σ(1), then k ≥ τ (1). We obtain:∆ ≺ • Ψ(σ) = = (k,τ )∈A,k≥τ (1) τ |[k] ⊗ P ack(τ |[max(τ )]\[k] ) = (l,τ ′ ,τ ′′ )∈B,l≥σ(1) τ ′ ⊗ τ ′′ = (Ψ ⊗ Ψ) • ∆ ≺ (σ)So Ψ is a morphism of dendriform coalgebras.Let σ, τ be two permutations. We put:C = {(α, ζ) | α ∈ Sh(max(σ), max(τ )), ζ ≤ α • (σ ⊗ τ )}, D = {(β, σ ′ , τ ′ ) | σ ′ ≤ σ, τ ′ ≤ τ, β ∈ QSh(max(σ ′ ), max(τ ′ ))}, Then: Ψ(σ τ ) = α∈Sh(max(σ),max(τ )) ζ≤α•(σ⊗τ ) ζ = (α,ζ)∈C ζ = Ψ(σ) -Ψ(τ ) = σ ′ ≤σ τ ′ ≤τ β∈QSh(max(σ ′ ),max(τ ′ )) β • (σ ′ ⊗ τ ′ ) = (β,σ ′ ,τ ′ )∈D β • (σ ′ ⊗ τ ′ ).

  k} ⊗ P ack(τ |{k+1,...,max(τ )}

	=	τ ∝σ	max(τ ) k=0	1 τ |{1,...,k} !P ack(τ |{k+1,...,max(τ )} !	τ |{1,...,k} ⊗ P ack(τ |{k+1,...,max(τ )}
		n
	=
		k=0	τ 1 ∝σ |{1,...,k}
			τ 2 ∝P ack(σ |{k+1,...,n} )

  LetI 1 ⊆ R(t 1 ), I 2 ⊆ R(t 2 ). Then:t/I 1 ⊔ I 2 = (t 1 /I 1 ) ∨ (t 2 /I 2 ) = (t 1 /I 1 ) ≻ ∨ ≺ (t 2 /I 2 ). We put t 2 /i 2 = t 3 ∨ . . . ∨ t k . Then: t/I 1 ⊔ I 2 ⊔ {r} = t 1 /I 1 ∨ t 3 ∨ . . . ∨ t k = (t 1 /I 1 ∨ ) • (t 3 ∨ . . . ∨ t k ) = ((t 1 /I 1 ) ≻ ∨ ) • (t 2 /I 2 ) = (t 1 /I 1 ) ≻ ∨ • (t 2 /I 2 ). 1 ⊆R(t 1 ),I 2 ⊆R(t 2 ) (t 1 /I 1 ) ≻ ∨ ≺ (t 2 /I 2 ) + (t 1 /I 1 ) ≻ ∨ • (t 2 /I 2 ) = I 1 ⊆R(t 1 ),I 2 ⊆R(t 2 )

	Hence:
	ψ(t) =

1 ) ⊔ R(t 2 ) ⊔ {r}. I (t 1 /I 1 ) ≻ ∨ (t 2 /I 2 ) = ψ(t 1 ) ≻ ∨ ψ(t 2 ).

Acknowledgements The authors were supported by the grant CARMA ANR-12-BS01-0017. We thank its participants and especially Jean-Christophe Novelli and Jean-Yves Thibon, for stimulating discussions on noncommutative symmetric functions and related structures. This article is, among others, a follow up of our joint works [26,15]. We also thank the ICMAT Madrid for its hospitality.

Proof. Let (σ, d) be a decorated packed word. Then:

(σ, d) |{1,...,i} ⊗ (σ, d) |{i+1,...,j} ⊗ (σ, d) |{j+1,...,max(σ)} ,

(σ, d) |{1,...,i} ⊗ (σ, d) |{i+1,...,j} ⊗ (σ, d) |{j+1,...,max(σ)} ,

(σ, d) |{1,...,i} ⊗ (σ, d) |{i+1,...,j} ⊗ (σ, d) |{j+1,...,max(σ)} .

Let us prove [START_REF]Fluctuation theory and baxter algebras[END_REF], for a = (σ, d) and b = (τ, e) two decorated packed words of respective length k and l. We put:

. . . σ(k) τ (1) + max(σ) . . . τ (l) + max(τ ) d(1) . . . d(k) e [START_REF] Bourbaki | Groupes et algèbres de lie[END_REF] . . . e(l) .

Then a ≺ b is the sum of all decorated packed words obtained by quasishuffling in all possible ways the values of the letters in the first row of a ⊗ b, in such a way that 1 occurs only in the first k columns; ∆ ≺ (a ⊗ b) is then given by separating the letters of the first row of these decorated packed words in such a way that the first letter appears in the left side. So at least one of the k first letters appears on the left side. This gives five possible cases:

( Summing all these terms, we obtain [START_REF]Fluctuation theory and baxter algebras[END_REF]. The other compatibilities can be proved similarly.

then:

We denote by N QSh(1) and by N Sh(1) the free NQSh and the free NSh algebra on one generator. The set T Sch is a basis of N QSh(1), and T bin is a basis of N Sh [START_REF] Bourbaki | Groupes et algèbres de lie[END_REF].

Examples.

.

We define now inductively a surjective map ̺ from the set of packed words decorated by D into T D Sch in the following way: (1) ̺(1) = .

(2) If w = (σ, d), let σ -1 (1) = {i 1 , . . . , i k }, i 1 < . . . < i k . We put:

. . .

d(n) .

Then:

such that the spaces between the leaves are decorated from left to right by d(1), . . . , d(n). In particular ̺ 1 d is the tree ∨ d-decorated.

For any t ∈ T N * Sch , we put:

We extend Ω : N QSh(N * ) -→ QSh d + by linearity map. It is clearly injective.

Examples

.

Theorem 46. The map Ω is an injective morphism of NQSh algebras. Consequently, QDesc, the NQSh subalgebra of QSh d + generated by the elements 1 d , d ≥ 1, is free and isomorphic to N QSh(N * ). Proof. Let w = (σ, d) be a packed word of length n and let i 1 , . . . , i k be integers such that i 1 + . . . + i k = n. For all d 1 , . . . , d k-1 ≥ 1, we put:

.

It is not difficult to show that:

).

An induction on m + n proves that for t ∈ T

So Ω is an injective morphism of NQSh algebras.

Lie theory, continued

In classical Lie theory, it has been realized progressively that many applications of the combinatorial part of the theory rely on the freeness of the Malvenuto-Reutenauer algebra of permutations (for us, the operad Sh or, equivalently, the algebra of free quasi-symmetric functions FQSym) as a noncommutative shuffle bialgebra (and more precisely, as a bidendriform bialgebra [START_REF] Foissy | Bidendriform bialgebras, trees, and free quasi-symmetric functions[END_REF]). As such, Sh has two remarquable subalgebras. The first is PBT, the noncommutative shuffle sub-bialgebra freely generated as a noncommutative shuffle algebra by the identity permutation in S 1 (in particular PBT is isomorphic to N SH(1), the free NQSh algebra on one generator).

Its elements can be understood as linear combinations of planar binary trees

Let us now prove that ω is a morphism. Let t, t ′ ∈ T Sch , such that t ≤ t ′ . By transitivity, we can assume that there exists e ∈ R(t ′ ), such that t = t ′ |e . Let us prove that ω(t) ≤ ω(t ′ ). We proceed by induction on the common degree n of t and t ′ . The result is obvious if n = 0 or 1. Let us assume the result at all ranks < n. We put

We put σ ′ j = ω(t ′ j ) and σ j = ω(t j ) for all j. If j = i, σ ′ j = σ j ; by the induction hypothesis, σ i ≤ σ ′ i . Then:

If e is the edge relation the root of t to the root of t ′ k , putting

Putting σ i = ω(t i ), we obtain:

It is not difficult to prove that ω(t) ≤ ω(t ′ ).

Remark. There are similar results for decorated packed words, replacing N Sh(1) and N QSh(1) by N Sh(N * n ) and N QSh(N * ).

Examples.

Proposition 52. The map Ψ is a bidendriform bialgebra morphism from (Sh, ≺, ≻, ∆ ≺ , ∆ ≻ ) to (QSh, , ≻, ∆ ≺ , ∆ ≻ ). Moreover, the following diagram commutes:

Proof. Let σ be a packed word. We put:

Hence, there exists a bijection G : D By composition, Ω • ψ and Ψ • Ω are both noncommutative shuffle algebra morphisms, sending ∨ to (1), so, since PBT is a free NSh algebra, they are equal.