Jean-Paul Bultel
email: jean-paul.bultel@univ-rouen.fr

Samuele Giraudo
email: samuele.giraudo@u-pem.fr.

COMBINATORIAL HOPF ALGEBRAS FROM PROS

Keywords: Mathematics Subject Classification. 05E99, 05E05, 05C05, 57T05, 18D50 Operad, PRO, Hopf algebra, Noncommutative symmetric function, Faà di Bruno algebra

come

Introduction 1. Algebraic structures and background 1.1. Combinatorial Hopf algebras 1.2. The natural Hopf algebra of an operad 1.3. PROs and free PROs 2. From PROs to combinatorial Hopf algebras 2.1. The Hopf algebra of a free PRO 2.2. Properties of the construction 2.3. The Hopf algebra of a stiff PRO 2.4. Related constructions 3. Examples of application of the construction 3.1. Hopf algebras of forests 3.2. The Faà di Bruno algebra and its deformations 3.3. Hopf algebra of forests of bitrees 3.4. Hopf algebra of heaps of pieces 3.5. Hopf algebra of heaps of friable pieces Concluding remarks and perspectives References

Introduction

Operads are algebraic structures introduced in the 70s by Boardman and Vogt [START_REF] Boardman | Homotopy invariant algebraic structures on topological spaces[END_REF] and by May [May72] in the context of algebraic topology to offer a formalization of the notion of operators and their composition (see [START_REF] Markl | Operads and PROPs[END_REF] and [START_REF] Loday | Algebraic Operads[END_REF] for a very complete presentation of the theory of operads). Operads provide therefore a unified framework to study some sorts of a priori very different algebras, such as associative algebras, Lie algebras, and commutative algebras. Besides, the theory of operads is also beneficial in combinatorics [START_REF] Chapoton | Operads and algebraic combinatorics of trees[END_REF] since it provides some ways to decompose combinatorial objects into elementary pieces. On the other hand, the theory of Hopf algebras holds a special place in algebraic combinatorics [START_REF] Joni | Coalgebras and bialgebras in combinatorics[END_REF]. In recent years, many Hopf algebras were defined and studied, and most of these involve very famous combinatorial objects such as permutations [START_REF] Malvenuto | Duality between quasi-symmetric functions and Solomon descent algebra[END_REF][START_REF] Duchamp | Noncommutative Symmetric Functions VI: Free Quasi-Symmetric Functions and Related Algebras[END_REF], standard Young tableaux [START_REF] Poirier | Algèbres de Hopf de tableaux[END_REF][START_REF] Duchamp | Noncommutative Symmetric Functions VI: Free Quasi-Symmetric Functions and Related Algebras[END_REF], or binary trees [START_REF] Loday | Hopf Algebra of the Planar Binary Trees[END_REF][START_REF] Hivert | The Algebra of Binary Search Trees[END_REF].

These two theories -operads and Hopf algebras-have several interactions. One of these is a construction [vdL04] taking an operad O as input and producing a bialgebra H (O) as output, which is called the natural bialgebra of O. This construction has been studied in some recent works: in [START_REF] Chapoton | Relating two Hopf algebras built from an operad[END_REF], it is shown that H can be rephrased in terms of an incidence Hopf algebra of a certain family of posets, and in [START_REF] Méndez | An antipode formula for the natural Hopf algebra of a set operad[END_REF], a general formula for its antipode is established. Let us also cite [START_REF] Frabetti | Groups of tree-expanded series[END_REF] in which this construction is considered to study series of trees.

The initial motivation of our work was to generalize this H construction with the aim of constructing some new and interesting Hopf algebras. The direction we have chosen is to start with PROs, algebraic structures which generalize operads in the sense that PROs deal with operators with possibly several outputs. Surprisingly, these structures appeared earlier than operads in the work of Mac Lane [START_REF] Lane | Categorical algebra[END_REF]. Intuitively, a PRO P is a set of operators together with two operations: an horizontal composition and a vertical composition. The first operation takes two operators x and y of P and builds a new one whose inputs (resp. outputs) are, from left to right, those of x and then those of y. The second operation takes two operators x and y of P and produces a new one obtained by plugging the outputs of y onto the inputs of x. Basic and modern references about PROs are [START_REF] Leinster | Higher operads, higher categories[END_REF] and [START_REF] Markl | Operads and PROPs[END_REF].

Our main contribution consists in the definition of a new construction H from PROs to bialgebras. Roughly speaking, the construction H can be described as follows. Given a PRO P satisfying some mild properties, the bialgebra HP has bases indexed by a particular subset of elements of P. The product of HP is the horizontal composition of P and the coproduct of HP is defined from the vertical composition of P, enabling to separate a basis element into two smaller parts. The properties satisfied by P imply, in a nontrivial way, that the product and the coproduct of HP satisfy the required axioms to be a bialgebra. This construction generalizes H and establishes a new connection between the theory of PROs and the theory of Hopf algebras.

Our results are organized as follows. In Section 1, we recall some general background about Hopf algebras, operads, and PROs. In particular, we give a description of free PROs in terms of prographs, similar to the one of Lafont [START_REF] Lafont | Diagram rewriting and operads[END_REF]. We also recall the natural bialgebra construction of an operad. We provide in Section 2 the description of our new construction H. A first version of this construction is presented, associating a bialgebra H(P) with a free PRO P. We then present an extended version of the construction, taking as input non-necessarily free PROs satisfying some properties, called stiff PROs. Next, we consider two well-known constructions of PROs [START_REF] Markl | Operads and PROPs[END_REF], one, R, taking as input operads and the other, B, taking as input monoids. We prove that under some mild conditions, these constructions produce stiff PROs. We establish that the natural bialgebra of an operad can be reformulated as a particular case of our construction H. We conclude by giving some examples of application of H in Section 3. The Hopf algebras that we obtain are very similar to the Connes-Kreimer Hopf algebra [START_REF] Connes | Hopf algebras, renormalization and noncommutative geometry[END_REF] in the sense that their coproduct can be computed by means of admissible cuts in various combinatorial objects. From very simple stiff PROs, we reconstruct the Hopf algebra of noncommutative symmetric functions Sym [GKL + 95,KLT97] and the noncommutative Fàa di Bruno algebra FdB 1 [START_REF] Brouder | Non-commutative Hopf algebra of formal diffeomorphisms[END_REF]. Besides, we present a way of using H to reconstruct some of the Hopf algebras FdB γ , a γdeformation of FdB 1 introduced by Foissy [START_REF] Foissy | Faà di Bruno subalgebras of the Hopf algebra of planar trees from combinatorial Dyson-Schwinger equations[END_REF]. We also obtain several other Hopf algebras, which, respectively, involve forests of planar rooted trees, some kind of graphs consisting of nodes with one parent and several children or several parents and one child that we call forests of bitrees, heaps of pieces (see [START_REF] Viennot | Heaps of pieces. I. Basic definitions and combinatorial lemmas[END_REF] for a general presentation of these combinatorial objects), and a particular class of heaps of pieces that we call heaps of friable pieces. All these Hopf algebras depend on a nonnegative integer as parameter.

Acknowledgments. The authors would like to thank Jean-Christophe Novelli for his suggestions during the preparation of this paper. Moreover, the authors would like to thank the anonymous referee for its useful suggestions, improving the paper. The computations of this work have been done with the open-source mathematical software Sage [S + 14] and one of its extensions, Sage-Combinat [START_REF]The Sage-Combinat community. Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics[END_REF].

Notations. For any integer n 0, [n] denotes the set {1, . . . , n}. If u is a word and i is a positive integer no greater than the length of u, u i denotes the i-th letter of u. The empty word is denoted by .

Algebraic structures and background

We recall in this preliminary section some basics about the algebraic structures in play in all this work, i.e., Hopf algebras, operads, and PROs. We also present some well-known Hopf algebras and recall the construction associating a combinatorial Hopf algebra with an operad.

1.1. Combinatorial Hopf algebras. In the sequel, all vector spaces have C as ground field. By algebra we mean a unitary associative algebra and by coalgebra a counitary coassociative coalgebra. We call combinatorial Hopf algebra any graded bialgebra H = n 0 H n such that for any n 1, the n-th homogeneous component H n of H has finite dimension and the dimension of H 0 is 1. The degree of any element x ∈ H n is n and is denoted by deg(x). Combinatorial Hopf algebras are Hopf algebras because the antipode can be defined recursively degree by degree. Let us now review some classical combinatorial Hopf algebras which play an important role in this work.

1.1.1. Faà di Bruno algebra and its deformations. Let FdB be the free commutative algebra generated by elements h n , n 1 with deg(h n ) = n. The bases of FdB are thus indexed by integer partitions, and the unit is denoted by h 0 . This is the algebra of symmetric functions [START_REF] Macdonald | Symmetric functions and Hall polynomials[END_REF]. There are several ways to endow FdB with a coproduct to turn it into a Hopf algebra. In [START_REF] Foissy | Faà di Bruno subalgebras of the Hopf algebra of planar trees from combinatorial Dyson-Schwinger equations[END_REF], Foissy obtains, as a byproduct of his investigation of combinatorial Dyson-Schwinger equations in the Connes-Kreimer algebra, a one-parameter family ∆ γ , γ ∈ R, of coproducts on FdB, defined by using alphabet transformations (see [START_REF] Macdonald | Symmetric functions and Hall polynomials[END_REF]), by

∆ γ (h n ) := n k=0 h k ⊗ h n-k ((kγ + 1)X), (1.1.1)
where, for any

α ∈ R and n ∈ N, h n (αX) is the coefficient of t n in k 0 h k t k α . In particular, ∆ 0 (h n ) = n k=0 h k ⊗ h n-k . (1.1.2)
The algebra FdB with the coproduct ∆ 0 is the classical Hopf algebra of symmetric functions Sym [START_REF] Macdonald | Symmetric functions and Hall polynomials[END_REF]. Moreover, for all γ = 0, all FdB γ are isomorphic to FdB 1 , which is known as the Faà di Bruno algebra [START_REF] Joni | Coalgebras and bialgebras in combinatorics[END_REF]. The coproduct ∆ 0 comes from the interpretation of FdB as the algebra of polynomial functions on the multiplicative group (G(t) := {1 + k 1 a k t k }, •) of formal power series of constant term 1, and ∆ 1 comes from its interpretation as the algebra of polynomial functions on the group (tG(t), •) of formal diffeomorphisms of the real line.

1.1.2. Noncommutative analogs. Formal power series in one variable with coefficients in a noncommutative algebra can be composed (by substitution of the variable). This operation is not associative, so that they do not form a group. For example, when a and b belong to a noncommutative algebra, one has

(t 2 • at) • bt = a 2 t 2 • bt = a 2 b 2 t 2 (1.1.3) but t 2 • (at • bt) = t 2 • abt = ababt 2 . (1.1.4)
However, the analogue of the Faà di Bruno algebra still exists in this context and is known as the noncommutative Faà di Bruno algebra. It is investigated in [START_REF] Brouder | Non-commutative Hopf algebra of formal diffeomorphisms[END_REF] in view of applications in quantum field theory. In [START_REF] Foissy | Faà di Bruno subalgebras of the Hopf algebra of planar trees from combinatorial Dyson-Schwinger equations[END_REF], Foissy also obtains an analogue of the family FdB γ in this context. Indeed, considering noncommutative generators S n (with deg(S n ) = n) instead of the h n , for all n 1, leads to a free noncommutative algebra FdB whose bases are indexed by integer compositions. This is the algebra of noncommutative symmetric functions [GKL + 95]. The addition of the coproduct ∆ γ defined by

∆ γ (S n ) := n k=0 S k ⊗ S n-k ((kγ + 1)A), (1.1.5)
where, for any α ∈ R and n ∈ N, S n (αA) is the coefficient of

t n in k 0 S k t k α
, forms a noncommutative Hopf algebra FdB γ . In particular,

∆ 0 (S n ) = n k=0 S k ⊗ S n-k , (1.1.6)
where S 0 is the unit. In this way, FdB with the coproduct ∆ 0 is the Hopf algebra of noncommutative symmetric functions Sym [GKL + 95, KLT97], and for all γ = 0, all the FdB γ are isomorphic to FdB 1 , which is the noncommutative Faà di Bruno algebra.

1.2. The natural Hopf algebra of an operad. We shall consider in this work only nonsymmetric operads in the category of sets. For this reason, we shall call these simply operads.

1.2.1. Operads. In our context, an operad is a triple (O, • i , 1) where

O := n 1 O(n) (1.2.1)
is a graded set,

• i : O(n) × O(m) → O(n + m -1), n, m 1, i ∈ [n], (1.2.2)
is a composition map, called partial composition, and 1 ∈ O(1) is a unit. These data have to satisfy the relations

(x • i y) • i+j-1 z = x • i (y • j z), x ∈ O(n), y ∈ O(m), z ∈ O(k), i ∈ [n], j ∈ [m], (1.2.3) (x • i y) • j+m-1 z = (x • j z) • i y, x ∈ O(n), y ∈ O(m), z ∈ O(k), 1 i < j n, (1.2.4) 1 • 1 x = x = x • i 1, x ∈ O(n), i ∈ [n]. (1.2.5)
Besides, we shall denote by

• : O(n) × O(m 1 ) × • • • × O(m n ) → O(m 1 + • • • + m n ), n, m 1 , . . . ,
T y ⊗ T z1 . . . T z .
(1.2.8)

The bialgebra H (O) can be graded by deg(T x ) := |x| -1. Note that with this grading, when O(1) = {1} and the O(n) are finite for all n 1, H (O) becomes a combinatorial Hopf algebra. 1.3. PROs and free PROs. We recall here the definitions of PROs and free PROs in terms of prographs and introduce the notions of reduced and indecomposable elements, which will be used in the following sections.

1.3.1. PROs. A PRO is a quadruple (P, * , •, 1 p ) where P is a bigraded set of the form

P := p 0 q 0 P(p, q), (1.3.1)
such that for any p, q 0, P(p, q) contains elements x with i(x) := p as input arity and o(x) := q as output arity, * is a map of the form * : P(p, q) × P(p , q ) → P(p + p , q + q ), p, p , q, q 0, (1.3.2) called horizontal composition, • is a map of the form

• : P(q, r) × P(p, q) → P(p, r), p, q, r 0, (1.3.3) called vertical composition, and for any p 0, 1 p is an element of P(p, p) called unit of arity p.

These data have to satisfy for all x, y, z ∈ P the six relations (x * y) * z = x * (y * z), x, y, z ∈ P, (1.3.4)

(x • y) • z = x • (y • z), x, y, z ∈ P, i(x) = o(y), i(y) = o(z), (1.3.5) (x • y) * (x • y ) = (x * x ) • (y * y ),
x, x , y, y ∈ P, i(x) = o(y), i(x ) = o(y ), (1.3.6)

1 p * 1 q = 1 p+q , p, q 0, (1.3.7) x * 1 0 = x = 1 0 * x, x ∈ P, (1.3.8) x • 1 p = x = 1 q • x, x ∈ P, p, q 0, i(x) = p, o(x) = q.
(1.3.9)

A PRO morphism is a map φ : P 1 → P 2 between two PROs P 1 and P 2 such that φ commutes with the horizontal and vertical compositions and preserves the input and output arities. A subset S of a PRO P is a sub-PRO of P if 1 p ∈ S for any p 0 and the horizontal and vertical compositions of P are stable in S. The sub-PRO of P generated by a subset G of P is the smallest sub-PRO of P containing G. An equivalence relation ≡ on P is a congruence of PROs if all the elements of a same ≡-equivalence class have the same input arity and the same output arity, and ≡ is compatible with the horizontal and the vertical composition. Any congruence ≡ of P gives rise to a PRO quotient of P denoted by P/ ≡ and defined in the expected way. 1.3.2. Free PROs. Let us now set our terminology about free PROs and its elements in terms of prographs. From now,

G := p 1 q 1 G(p, q) (1.3.10)
is a bigraded set. An elementary prograph e over G is a formal operator labeled by an element a of G(p, q). The input (resp. output) arity of e is p (resp. q). We represent e as a rectangle labeled by g with p incoming edges (below the rectangle) and q outgoing edges (above the rectangle).

For instance, if a ∈ G(2, 3), the elementary prograph labeled by a is depicted by

a 1 2 1 2 3 . (1.3.11)
A prograph over G is a formal operator defined recursively as follows. A prograph over G can be either an elementary prograph over G, or a special element, the wire depicted by ,

(1.3.12) or a combination of two prographs over G through the following two operations. The first one, denoted by * , consists in placing two prographs side by side. For instance, if x is a prograph with p inputs (resp. q outputs) and y is a prograph with p inputs (resp. q outputs), The second one, denoted by •, consists in connecting the inputs of a first prograph over the outputs of a second. For instance, if x is a prograph with p inputs (resp. q outputs) and y is a prograph with r inputs (resp. p outputs),

a 1 p 1 q . . . . . . • b 1 r 1 p . . . . . . = a b 1 r 1 q . . . . . . . . . . (1.3.14)
By definition, connecting the input (resp. output) of a wire to the output (resp. input) of a prograph x does not change x.

The input (resp. output) arity of a prograph x is its number of inputs i(x) (resp. outputs o(x)). The inputs (resp. outputs) of a prograph are numbered from left to right from 1 to i(x) (resp. o(x)), possibly implicitly in the drawings. The degree deg(x) of a prograph x is the number of elementary prographs required to build it. For instance,

a b a (1.3.15) is a prograph over G := G(2, 2) G(3, 1)
where G(2, 2) := {a} and G(3, 1) := {b}. Its input arity is 7, its output arity is 5, and its degree is 3.

The free PRO generated by G is the PRO Free(G) whose elements are all the prographs on G, the horizontal composition being the operation * on prographs, and the vertical composition being the operation •. Its unit 1 1 is the wire, and for any p 0, 1 p is the horizontal composition of p occurrences of the wire. Notice that by (1.3.10), there is no elementary prograph in Free(G) with a null input or output arity. Therefore, 1 0 is the only element of Free(G) with a null input (resp. output) arity. In this work, we consider only free PROs satisfying this property.

Lemma 1.1. Let P be a free PRO and x, y, z, t ∈ P such that x * y = z • t. Then, there exist four unique elements

x 1 , x 2 , y 1 , y 2 of P such that x = x 1 • x 2 , y = y 1 • y 2 , z = x 1 * y 1 , and t = x 2 * y 2 .
Proof. Let us prove the uniqueness. Assume that there are x 1 , x 2 , y 1 , y 2 ∈ P and

x 1 , x 2 , y 1 , y 2 ∈ P such that x = x 1 • x 2 = x 1 • x 2 , y = y 1 • y 2 = y 1 • y 2 , z = x 1 * y 1 = x 1 * y 1 , and t = x 2 * y 2 = x 2 * y 2 .
Then, we have in particular o(x 1 ) = o(x 1 ) and o(y 1 ) = o(y 1 ). This, together with the relation x 1 * y 1 = x 1 * y 1 and the fact that P is free, implies x 1 = x 1 and y 1 = y 1 . In the same way, we obtain x 2 = x 2 and y 2 = y 2 .

Let us now give a geometrical proof for the existence based upon the fact that prographs are planar objects. Since u := x * y = z • t, u is a prograph obtained by an horizontal composition of two prographs. Then, u = x * y depicted in a plane P can be split into two regions X and Y such that X contains the prograph x, Y contains the prograph y, and y is at the right of x. On the other hand, u = z • t depicted in the same plane P can be split into two regions Z and T such that Z contains the prograph z, T contains the prograph t, and t is below z, the inputs of z being connected to the outputs of t. We then obtain a division of P into four regions X ∩ Z, X ∩ T, Y ∩ Z, and Y ∩ T, respectively containing prographs x 1 , x 2 , y 1 , and y 2 , and such that

x 1 * y 1 = z, x 2 * y 2 = t, x 1 • x 2 = x, and y 1 • y 2 = y.
1.3.3. Reduced and indecomposable elements. Let P be a free PRO. Since P is free, any element x of P can be uniquely written as x = x 1 * • • • * x where the x i are elements of P different from 1 0 , and 0 is maximal. We call the word dec(x) := (x 1 , . . . , x ) the maximal decomposition of x and the x i the factors of x. Notice that the maximal decomposition of 1 0 is the empty word. We have, for instance,

dec   a b a   =    a , b a ,    .
(1.3.16)

An element x of P is reduced if all its factors are different from 1 1 . For any element x of P, we denote by red(x) the reduced element of P admitting as maximal decomposition the longest subword of dec(x) consisting in factors different from 1 1 . We have, for instance, (1.3.17)

By extension, we denote by red(P) the set of the reduced elements of P. Note that 1 0 belongs to red(P).

Besides, we say that an element x of P is indecomposable if its maximal decomposition consists in exactly one factor. Note that 1 0 is not indecomposable while 1 1 is.

Lemma 1.2. Let P be a free PRO and x, y ∈ P, such that x = red(y). Then, by denoting by (x 1 , . . . , x ) the maximal decomposition of x, there exists a unique sequence of nonnegative integers p 1 , . . . , p , p +1 such that

y = 1 p1 * x 1 * 1 p2 * x 2 * • • • * x * 1 p +1 .
(1.3.18)

Proof. The existence comes from the fact that, since x = red(y), the maximal decomposition of x is obtained from the one of y by suppressing the factors equal to the wire. The uniqueness comes from the fact that P is a free monoid for the horizontal composition * .

From PROs to combinatorial Hopf algebras

We introduce in this section the main construction of this work and review some of its properties. In all this section, P is a free PRO generated by a bigraded set G. Starting with P, our construction produces a bialgebra H(P) whose bases are indexed by the reduced elements of P. We shall also extend this construction over a class of non necessarily free PROs.

2.1. The Hopf algebra of a free PRO. The bases of the vector space

H(P) := Vect(red(P)) (2.1.1)
are indexed by the reduced elements of P. The elements S x , x ∈ red(P), form thus a basis of H(P), called fundamental basis. We endow H(P) with a product • : H(P) ⊗ H(P) → H(P) linearly defined, for any reduced elements x and y of P, by

S x • S y := S x * y , (2.1.2)
and with a coproduct ∆ : H(P) → H(P) ⊗ H(P) linearly defined, for any reduced elements Lemma 2.1. Let P be a free PRO. Then, the coproduct ∆ of H(P) is coassociative.

Proof. The bases of the vector space Vect(P) are indexed by the (non-necessarily reduced) elements of P. Then, the elements R x , x ∈ P, form a basis of Vect(P). Let us consider the coproduct ∆ defined, for any x ∈ P, by

∆ (R x ) := y,z∈P y•z=x R y ⊗ R z . (2.1.6)
The associativity of the vertical composition • of P (see (1.3.5)) implies that ∆ is coassociative and hence, that Vect(P) together with ∆ form a coalgebra.

Consider now the map φ : Vect(P) → H(P) defined, for any x ∈ P, by φ(R x ) := S red(x) . Let us show that φ commutes with the coproducts ∆ and ∆ , that is, (φ ⊗ φ)∆ = ∆φ. Let x ∈ P. By Lemma 1.2, by denoting by (x 1 , . . . , x ) the maximal decomposition of red(x), there is a unique way to write x as x = 1 p1 * x 1 * • • • * x * 1 +1 where the p i are some integers. Then, thanks to the associativity of * (see (1.3.4)), by iteratively applying Lemma 1.1, we have

(φ ⊗ φ)∆ (R x ) = y,z∈P y•z=x S red(y) ⊗ S red(z) (2.1.7) = y1,...,y ∈P z1,...,z ∈P (1p 1 * y1 * ••• * y * 1 +1 ) •(1p 1 * z1 * ••• * z * 1 +1 )= 1p 1 * x1 * ••• * x * 1 +1 S red(1p 1 * y1 * ••• * y * 1 +1 ) ⊗ S red(1p 1 * z1 * ••• * z * 1 +1 ) (2.1.8) = y1,...,y ∈P z1,...,z ∈P (y1 * ••• * y )•(z1 * ••• * z )=x1 * ••• * x S red(y1 * ••• * y ) ⊗ S red(z1 * ••• * z ) (2.1.9) = y,z∈P y•z=red(x) S red(y) ⊗ S red(z) (2.1.10) = ∆ (φ (R x )) . (2.1.11)
Now, the coassociativity of ∆ comes from the fact that φ is a surjective map commuting with ∆ and ∆ . In more details, if x is a reduced element of P and I is the identity map on H(P), we have

(∆ ⊗ I)∆ (S x ) = (∆ ⊗ I)∆(φ (R x )) (2.1.12) = (φ ⊗ φ ⊗ φ)(∆ ⊗ I)∆ (R x ) (2.1.13) = (φ ⊗ φ ⊗ φ)(I ⊗ ∆ )∆ (R x ) (2.1.14) = (I ⊗ ∆)∆(φ (R x )) (2.1.15) = (I ⊗ ∆)∆ (S x ) .
(2.1.16) Lemma 2.2. Let P be a free PRO. Then, the coproduct ∆ of H(P) is a morphism of algebras.

Proof. Let x and y be two reduced elements of P. We have

∆(S x • S y ) = z,t∈P z•t=x * y S red(z) ⊗ S red(t) (2.1.17) and ∆(S x )∆(S y ) = x1,x2,y1,y2∈P x1•x2=x y1•y2=y S red(x1) * red(y1) ⊗ S red(x2) * red(y2) . (2.1.18)
The coproduct ∆ is a morphism of algebras if (2.1.17) and (2.1.18) are equal. Let us show that it is the case.

Assume that there are two elements z and t of P such that z • t = x * y. Then, the pair (z, t) contributes to the coefficient of the tensor S red(z) ⊗ S red(t) in (2.1.17). Moreover, since P is free, by Lemma 1.1, there exist four unique elements x 1 , x 2 , y 1 , and y 2 of P such that x = x 1 • x 2 , y = y 1 • y 2 , z = x 1 * y 1 , and t = x 2 * y 2 . Then, since red(x 1 ) * red(y 1 ) = red(x 1 * y 1 ) = red(z) and red(x 2 ) * red(y 2 ) = red(x 2 * y 2 ) = red(t), the quadruple (x 1 , x 2 , y 1 , y 2 ), wholly and uniquely determined by the pair (z, t), contributes to the coefficient of the tensor S red(z) ⊗S red(t) in (2.1.18). Conversely, assume that there are four elements x 1 , x 2 , y 1 , and y 2 in P such that x 1 • x 2 = x and y 1 • y 2 = y. Then, the quadruple (x 1 , x 2 , y 1 , y 2 ) contributes to the coefficient of the tensor S red(x1) * red(y1) ⊗ S red(x2) * red(y2) in (2.1.18). Now, by (1.3.6), we have

x * y = (x 1 • x 2 ) * (y 1 • y 2 ) = (x 1 * y 1 ) • (x 2 * y 2 ).
(2.1.19)

Then, since red(x 1 ) * red(y 1 ) = red(x 1 * y 1 ) and red(x 2 ) * red(y 2 ) = red(x 2 * y 2 ), the pair (x 1 * y 1 , x 2 * y 2 ), wholly and uniquely determined by the quadruple (x 1 , x 2 , y 1 , y 2 ), contributes to the coefficient of the tensor S red(x1) * red(y1) ⊗ S red(x2) * red(y2) in (2.1.17).

Hence, the coefficient of any tensor is the same in (2.1.17) and in (2.1.18). Then, these expressions are equal.

Theorem 2.3. Let P be a free PRO. Then, H(P) is a bialgebra.

Proof. The associativity of • comes directly from the associativity of the horizontal composition * of P (see (1.3.4)). Moreover, by Lemmas 2.1 and 2.2, the coproduct of H(P) is coassociative and is a morphism of algebras. Thus, H(P) is a bialgebra.

Properties of the construction.

Let us now study the general properties of the bialgebras obtained by the construction H.

Algebraic generators and freeness.

Proposition 2.4. Let P be a free PRO. Then, H(P) is freely generated as an algebra by the set of all S g , where the g are indecomposable and reduced elements of P.

Proof. Any reduced element x of P can be written as x = x 1 * • • • * x where (x 1 , . . . , x ) is the maximal decomposition of x. This implies that in H(P), we have S x = S x1 • . . . • S x . Since for all i ∈ [ ], the S xi are indecomposable and reduced elements of P, the set of all S g generates H(P). The uniqueness of the maximal decomposition of x implies that H(P) is free on the S g .

Gradings.

There are several ways to define gradings for H(P) to turn it into a combinatorial Hopf algebra. For this purpose, we say that a map ω : red(P) → N is a grading of P if it satisfies the following four properties: (G1) for any reduced elements x and y of P, ω(x * y) = ω(x) + ω(y); (G2) for any reduced elements x of P satisfying x = y • z where y, z ∈ P, ω(x) = ω(red(y)) + ω(red(z)); (G3) for any n 0, the fiber

ω -1 (n) is finite; (G4) ω -1 (0) = {1 0 }.
A very generic way to endow P with a grading consists in providing a map ω : G → N \ {0} associating a positive integer with any generator of P, namely its weight; the degree ω(x) of any element x of P being the sum of the weights of the occurrences of the generators used to build x. For instance, the map ω defined by ω(a) := 3 and ω(b) := 2 is a grading of AB and we have (2.2.1) Proposition 2.5. Let P be a free PRO and ω be a grading of P. Then, with the grading

H(P) = n 0 Vect (S x : x ∈ red(P) and ω(x) = n) , (2.2.2)
H(P) is a combinatorial Hopf algebra.
Proof. Notice first that S 10 is the neutral element of the product of H(P), and, for any reduced element x of P of degree different from 0, the coproduct ∆(S x ) contains the tensors S 10 ⊗ S x and S x ⊗ S 10 . Then, together with the fact that by (G4), S 10 is an element of the homogeneous component of degree 0 of H(P), H(P) admits a unit and a counit. Moreover, (G3) implies that for all n 0, the homogeneous components of degree n of H(P) are finite, and (G4) implies that H(P) is connected.

Besides, respectively by (G1) and by (G2), the grading provided by ω is compatible with the product and the coproduct of H(P).

Hence, together with the fact that, by Theorem 2.3, H(P) is a bialgebra, it is also a combinatorial Hopf algebra. 2.2.3. Antipode. Since the antipode of a combinatorial Hopf algebra can be computed by induction on the degree, we obtain an expression for the one of H(P) when P admits a grading. This expression is an instance of the Takeuchi formula [START_REF] Takeuchi | Free Hopf algebras generated by coalgebras[END_REF] and is particularly simple since the product of H(P) is multiplicative.

Proposition 2.6. Let P be a free PRO admitting a grading. For any reduced element x of P different from 1 0 , the antipode ν of H(P) satisfies

ν(S x ) = x1,...,x ∈P, 1 x1•••••x =x red(xi) =10,i∈[ ] (-1) S red(x1 * ••• * x ) .
(2.2.3) Proof. By Proposition 2.5, H(P) is a combinatorial Hopf algebra, and hence, the antipode ν, which is the inverse of the identity morphism for the convolution product, exists and is unique. Then, for any reduced element x of P different from 1 0 ,

ν(S x ) = -S x - y,z∈P\{x} y•z=x ν S red(y) • S red(z) .
(2.2.4) Expression (2.2.3) for ν follows now by induction on the degree of x in P.

We have for instance in H(AB), ( (2.2.12) is a surjective bialgebra morphism. Moreover, H(Free(G )) is a quotient bialgebra of H(Free(G)).

Proof. Let V be the linear span of the S x where the x are reduced elements of Free(G) \ Free(G ).

Immediately from the definitions of the product and the coproduct of H(Free(G)), we observe that V is a bialgebra ideal of H(Free(G)). The map φ is the canonical projection from H(Free(G)) to H(Free(G))/ V H(Free(G )), whence the result.

2.3. The Hopf algebra of a stiff PRO. We now extend the construction H to a class a nonnecessarily free PROs. Still in this section, P is a free PRO.

Let ≡ be a congruence of P. For any element x of P, we denote by [x] ≡ (or by [x] if the context is clear) the ≡-equivalence class of x. We say that ≡ is a stiff congruence if the following three properties are satisfied: (C1) for any reduced element x of P, the set [x] is finite; (C2) for any reduced element x of P, [x] contains reduced elements only;

(C3) for any two elements x and x of P such that x ≡ x , the maximal decompositions of x and x are, respectively of the form (x 1 , . . . , x ) and (x 1 , . . . , x ) for some 0, and for any i ∈ [ ], x i ≡ x i .

We say that a PRO is a stiff PRO if it is the quotient of a free PRO by a stiff congruence.

For any ≡-equivalence class [x] of reduced elements of P, set

T [x] := x ∈[x] S x .
(2.3.1)

Notice that thanks to (C1) and (C2), T [x] is a well-defined element of H(P).

For instance, if P is the quotient of the free PRO generated by (2.3.3) Moreover, we can observe that ≡ is a stiff congruence.

G := G(1, 1) G(2,
If ≡ is a stiff congruence of P, (C2) and (C3) imply that all the elements of a same ≡equivalence class [x] have the same number of factors and are all reduced or all nonreduced. Then, by extension, we shall say that a ≡-equivalence class [x] of P/ ≡ is indecomposable (resp. reduced) if all its elements are indecomposable (resp. reduced) in P. In the same way, the wire of P/ ≡ is the ≡-equivalence class of the wire of P.

We shall now study how the product and the coproduct of H(P) behave on the T [x] .

Product. Let us show that the linear span of the T [x]

, where the [x] are ≡-equivalence classes of reduced elements of P, forms a subalgebra of H(P). The product on the T [x] is multiplicative and admits the following simple description. Proposition 2.9. Let P be a free PRO and ≡ be a stiff congruence of P. Then, for any ≡equivalence classes [x] and [y],

T [x] • T [y] = T [x * y] ,
(2.3.4)

where x (resp. y) is any element of [x] (resp.

[y]).

Proof. We have Conversely, assume that there is a reduced element z of P such that S z appears in (2.3.6). Then, one has z ∈ [x * y]. Since ≡ satisfies (C3), the maximal decomposition of z satisfies dec(z) = (x 1 , . . . , x k , y 1 , . . . , y ) where dec(x) = (x 1 , . . . , x k ), dec(y) = (y 1 , . . . , y ), x i ≡ x i , and y j ≡ y j for all i ∈ [k] and j ∈ [ ]. Moreover, as ≡ is a congruence of PROs, x := x 1 * • • • * x k ≡ x and y := y 1 * • • • * y ≡ y. We then have z = x * y with x ∈ [x] and y ∈ [y]. This shows that S z also appears in (2.3.5).

T [x] • T [y] = x ∈[x] y ∈[y] S x

Coproduct. To prove that the linear span of the T [x]

, where the [x] are ≡-equivalence classes of reduced elements of P, forms a subcoalgebra of H(P) and provides the description of the coproduct of a T [x] , we need the following notation. For any element x of P, Lemma 2.11. Let P be a free PRO, ≡ be a stiff congruence of P, and y and z be two elements of P such that y ≡ z. Then, red(y) = red(z) implies y = z.

Proof. By contraposition, assume that y = z. Since y ≡ z and ≡ satisfies (C3), dec(y) and dec(z) have the same length , and dec(y) i ≡ dec(z) i for all i ∈ [ ]. Moreover, as y = z, there exists a j ∈ [ ] such that dec(y) j = dec(z) j . Now, since ≡ satisfies (C2), dec(y) j and dec(z) j are both reduced elements. Moreover, for all i ∈ [ ], dec(y) i and dec(z) i are both reduced elements or are both wires. Hence, there is j 1 such that dec(red(y)) j = dec(y) j and dec(red(z)) j = dec(z) j . Since P is free, this implies that red(y) = red(z).

Proposition 2.12. Let P be a free PRO and ≡ be a stiff congruence of P. Then, for any

≡-equivalence class [x], ∆ T [x] = [y],[z]∈P/≡ [y]•[z]=[x] T red([y]) ⊗ T red([z]) .
(2.3.9)

Proof. We have

∆ T [x] = y,z∈P y•z∈[x] S red(y) ⊗ S red(z) (2.3.10) = y,z∈P [y]•[z]=[x] S red(y) ⊗ S red(z) (2.3.11) = [y],[z]∈P/≡ [y]•[z]=[x] y ∈[y] z ∈[z]
S red(y ) ⊗ S red(z ) (2.3.12) Proof. By Propositions 2.9 and 2.12, the product and the coproduct of H(P) are still well-defined on the T [x] . Then, since the T [x] are by (2.3.1) sums of some S x , this implies the statement of the theorem.

= [y],[z]∈P/≡ [y]•[z]=[x] y ∈red([y]) z ∈red([z]) S y ⊗ S z (2.3.13) = [y],[z]∈P/≡ [y]•[z]=[x] T red([y]) ⊗ T red([z]) . ( 2
We shall denote, by a slight abuse of notation, by H(P/ ≡ ) the sub-bialgebra of H(P) spanned by the T [x] , where the [x] are ≡-equivalence classes of reduced elements of P. Notice that the construction H as it was presented in Section 2.1 is a special case of this latter when ≡ is the most refined congruence of PROs.

Note that this construction of sub-bialgebras of H(P) by taking an equivalence relation satisfying some precise properties and by considering the elements obtained by summing over its equivalence classes is analog to the construction of certain sub-bialgebras of the Malvenuto-Reutenauer Hopf algebra [START_REF] Malvenuto | Duality between quasi-symmetric functions and Solomon descent algebra[END_REF]. Indeed, some famous Hopf algebras are obtained in this way, as the Loday-Ronco Hopf algebra [START_REF] Loday | Hopf Algebra of the Planar Binary Trees[END_REF] Here, ≡ is not a stiff congruence since it satisfies (C2) but not (C3).

We have

T a • T a = S a • S a = S a a
(2.3.16) but this last element cannot be expressed on the T

[x] .
Besides, by a straightforward computation, we have

∆T   a a a   = ∆S a a a + ∆S a b + ∆S b a = T [10] ⊗ T   a a a   + T   a a a   ⊗ T [10] + 2 T   a   ⊗ T   b   + 2 T   b   ⊗ T   a   + S a ⊗ S a a + S a a ⊗ S a , (2.3.17)
showing that the coproduct is neither well-defined on the T [x] .

2.3.5. Properties. By using similar arguments as those used to establish Proposition 2.4 together with the fact that ≡ satisfies (C3) and the product formula of Proposition 2.9, we obtain that H(P/ ≡ ) is freely generated as an algebra by the T [x] where the [x] are ≡-equivalence classes of indecomposable and reduced elements of P. Moreover, when ω is a grading of P so that all elements of a same ≡-equivalence class have the same degree, the bialgebra H(P/ ≡ ) is graded by the grading inherited from the one of H(P) and forms hence a combinatorial Hopf algebra.

Proposition 2.14. Let P be a free PRO and ≡ 1 and ≡ 2 be two stiff congruences of P such that ≡ 1 is finer than ≡ 2 . Then, H (P/ ≡2 ) is a sub-bialgebra of H (P/ ≡1 ).

Proof. Since ≡ 1 is finer that ≡ 2 , any T [x]≡ 2 , where [x] ≡2 is a ≡ 2 -equivalence class of reduced elements of P, is a sum of some T [x ]≡ 1 . More precisely, we have

T [x]≡ 2 = [x ]≡ 1 ⊆[x]≡ 2 T [x ]≡ 1 , (2.3.18)
implying the result.

Related constructions.

In this section, we first describe two constructions allowing to build stiff PROs. The main interest of these constructions is that the obtained stiff PROs can be placed at the input of the construction H. We next present a way to recover the natural Hopf algebra of an operad through the construction H and the previous constructions of stiff PROs.

2.4.1.

From operads to stiff PROs. Any operad O gives naturally rise to a PRO R(O) whose elements are sequences of elements of O (see [START_REF] Markl | Operads and PROPs[END_REF]).

We recall here this construction. Let us set R(O) := p 0 q 0 R(O)(p, q) where R(O)(p, q) := {x 1 . . . x q : x i ∈ O(p i ) for all i ∈ [q] and p 1 + • • • + p q = p}.

(2.4.1)

The horizontal composition of R(O) is the concatenation of sequences, and the vertical composition of R(O) comes directly from the composition map of O. More precisely, for any where for any i ∈ [r], x i ∈ O(q i ) and the occurrences of • in the right-member of (2.4.2) refer to the total composition map of O.

x 1 . . . x r ∈ R(O)(q,
For instance, if O is the free operad generated by a generator of arity 2, O is an operad involving binary trees. Then, the elements of the PRO R(O) are forests of binary trees. The horizontal composition of R(O) is the concatenation of forests, and the vertical composition

F 1 • F 2 in R(O),
defined only between two forests F 1 and F 2 such that the number of leaves of F 1 is the same as the number of trees in F 2 , consists in the forest obtained by grafting, from left to right, the roots of the trees of F 2 on the leaves of F 1 . This construction can be rephrased as follows. We have B(M) = p 0 q 0 B(M)(p, q) where

B(M)(p, q) = {x 1 . . . x p : x i ∈ M for all i ∈ [p]} if p = q, ∅ otherwise.
(2.4.4)

The horizontal composition of B(M) is the concatenation of sequences and the vertical composition

• : B(M)(p, p) × B(M)(p, p) → B(M)(p, p) of B(M) satisfies, for any x 1 . . . x p ∈ B(M)(p, p)
and y 1 . . . y q ∈ B(M)(q, q),

x 1 . . . x p • y 1 . . . y p = (x 1 • y 1 ) . . . (x p • y p ), (2.4.5)
where • is the product of M.

For instance, if M is the additive monoid of natural numbers, the PRO B(M) contains all words over N. The horizontal composition of B(M) is the concatenation of words, and the vertical composition of B(M), defined only on words with a same length, is the componentwise addition of their letters.

Proposition 2.16. Let M be a monoid that does not contain any nontrivial subgroup. Then, B(M) is a stiff PRO.

Proof. Since M does not contain any nontrivial subgroup, seen as an operad, the elements of arity one of M do not contain any nontrivial subgroup. Hence, by definition of the construction B passing by R and by Proposition 2.15, B(M) is a stiff PRO. 2.4.3. The natural Hopf algebra of an operad. We call abelianization of a bialgebra H the quotient of H by the bialgebra ideal spanned by the x • y -y • x for all x, y ∈ H.

Here is the link between our construction H and the construction H . Proposition 2.17. Let O be an operad such that the monoid (O(1), • 1 ) does not contain any nontrivial subgroup. Then, the bialgebra H (O) is the abelianization of H(R(O)).

Proof. By Proposition 2.15, R(O) is a stiff PRO, and then, by Theorem 2.13, H(R(O)) is a bialgebra. By construction, this bialgebra is freely generated by the T x where x ∈ O. Hence, the map φ : H(R(O)) → H (O) defined for any x ∈ O by φ(T x ) := T x can be uniquely extended into a bialgebra morphism, which we denote also by φ. Since H (O) is generated by the T x where x ∈ O, φ is surjective. Directly from the definition of the construction H , we observe that the kernel of φ is the bialgebra ideal I spanned by the T x * y -T y * x for all x, y ∈ R(O). Then, the associated map φ I : ) are injective (resp. surjective) PRO morphisms. The parameter γ is a positive integer. When γ = 0, PRF 0 = As 0 = Heap 0 = FHeap 0 and FBT 0 = BAs 0 . 3.1.1. PRO of forests with a fixed arity. Let γ be a nonnegative integer and PRF γ be the free PRO generated by G := G(γ + 1, 1) := {a}, with the grading ω defined by ω(a) := 1. Any prograph x of PRF γ can be seen as a planar forest of planar rooted trees with only internal nodes of arity γ + 1. Since the reduced elements of PRF γ have no wire, they are encoded by forests of nonempty trees.

H(R(O))/ I → H (O) is a bialgebra isomorphism.

Examples of application of the construction

H(PRF γ ) H(FBT γ ) H(As γ ) H(BAs γ ) H(Heap γ ) H(FHeap γ )
3.1.2. Hopf algebra. By Theorem 2.3 and Proposition 2.5, H(PRF γ ) is a combinatorial Hopf algebra. By Proposition 2.4, as an algebra, H(PRF γ ) is freely generated by the S T , where the T are nonempty planar rooted trees with only internal nodes of arity γ + 1. Its bases are indexed by planar forests of such trees where the degree of a basis element S F is the number of internal nodes of F .

Notice that the bases of H(PRF 0 ) are indexed by forests of linear trees and that H(PRF 0 ) and Sym are trivially isomorphic as combinatorial Hopf algebras. where Adm(T ) is the set of admissible cuts of T , that is, the empty tree or the subtrees of T containing the root of T and where T / T denotes the forest consisting in the maximal subtrees of T whose roots are leaves of T , by respecting the order of these leaves in T and by removing the empty trees. For instance, we have

∆S = S ∅ ⊗ S + S ⊗ S + S ⊗ S + S ⊗S + S ⊗S + S ⊗S + S ⊗S ∅ . (3.1.2)
This coproduct is similar to the one of the noncommutative Connes-Kreimer Hopf algebra CK [START_REF] Connes | Hopf algebras, renormalization and noncommutative geometry[END_REF]. The main difference between H(PRF γ ) and CK lies in the fact that in a coproduct of CK, the admissible cuts can change the arity of some internal nodes; it is not the case in H(PRF γ ) because for any T ∈ Adm(T ), any internal node x of T has the same arity as it has in T .

Dimensions. The series of the algebraic generators of H(PRF

γ ) is G(t) := n 1 1 nγ + 1 n(γ + 1) n t n (3.1.3)
since its coefficients are the Fuss-Catalan numbers, counting planar rooted trees with n internal nodes of arity γ + 1. Since H(PRF γ ) is free as an algebra, its Hilbert series is

H(t) := 1 1-G(t) .
The first dimensions of H(PRF 1 ) are The first sequence is listed in [Slo] as Sequence A001700 and the second as Sequence A047099.

3.1.5. PRO of general forests. We denote by PRF ∞ the free PRO generated by G := n 1 G(n, 1) := n 1 {a n }. Any prograph x of PRF ∞ can be seen as a planar forest of planar rooted trees. Since the reduced elements of PRF ∞ have no wire, they are encoded by forests of nonempty trees. Observe that for any nonnegative integer γ, PRF γ is a sub-PRO of PRF ∞ .

3.1.6. Hopf algebra. By Theorem 2.3, H(PRF ∞ ) is a bialgebra. By Proposition 2.4, as an algebra, H(PRF ∞ ) is freely generated by the S T , where the T are nonempty planar rooted trees. Its bases are indexed by planar forests of such trees. Besides, by Proposition 2.8, since PRF γ is generated by a subset of the generators of PRF ∞ , H(PRF γ ) is a bialgebra quotient of H(PRF ∞ ). Moreover, the coproduct of H(PRF ∞ ) satisfies (3.1.1).

To turn H(PRF ∞ ) into a combinatorial Hopf algebra, we cannot consider the grading ω defined by ω(a n ) := 1 because there would be infinitely many elements of degree 1. Therefore, we consider on H(PRF ∞ ) the grading ω defined by ω(a n ) := n. In this way, the degree of a basis element S F is the number of edges of the forest F . By Proposition 2.5, H(PRF ∞ ) is a combinatorial Hopf algebra.

3.1.7. Dimensions. The series of the algebraic generators of H(PRF ∞ ) is

G(t) := n 1 1 n + 1 2n n t n (3.1.6)
since its coefficients are the Catalan numbers, counting planar rooted trees with n edges. As H(PRF ∞ ) is free as an algebra, its Hilbert series is

H(t) := 1 1 -G(t) = 1 + n 1 1 2 2n n t n . (3.1.7)
The dimensions of H(PRF ∞ ) are then the same as the dimensions of H(PRF 1 ) (see (3.1.4)).

3.2. The Faà di Bruno algebra and its deformations. We shall give here a method to construct the Hopf algebras FdB γ of Foissy [START_REF] Foissy | Faà di Bruno subalgebras of the Hopf algebra of planar trees from combinatorial Dyson-Schwinger equations[END_REF] from our construction H in the case where γ is a nonnegative integer.

1 . . . 2 , k 1 + k 2 = γ, 1 + 2 = γ. (3.2.1)
We can observe that As γ is a stiff PRO because ≡ satisfies (C2) and (C3) and that As 0 = PRF 0 . Moreover, observe that, when γ 1, there is in As γ exactly one indecomposable element of arity nγ + 1 for any n 0. We denote by α n this element. We consider on As γ the grading ω inherited from the one of PRT γ . This grading is still well-defined in As γ since any ≡-equivalence class contains prographs of a same degree and satisfies, for all n 0, ω(α n ) = n. Any element of As γ is then a word α k1 . . . α k and can be encoded by a word of nonnegative integers k 1 . . . k . Since the reduced elements of As γ have no wire, they are encoded by words of positive integers.

3.2.2. Hopf algebra. By Theorem 2.13 and Proposition 2.5, H(As γ ) is a combinatorial Hopf algebra. As an algebra, H(As γ ) is freely generated by the T n , n 1, and its bases are indexed by words of positive integers where the degree of a basis element T k1...k is k 1 + • • • + k . 3.2.3. Coproduct. Since any element α n of As γ decomposes into α n = x • y if and only if x = α k and y = α i1 . . . α i kγ+1 with i 1 + • • • + i kγ+1 = n -k, by Proposition 2.12, for any n 1, the coproduct of H(As γ ) expresses as

∆(T n ) = n k=0 T k ⊗   i1+•••+i kγ+1 =n-k T i1 . . . T i kγ+1   , (3.2.2)
where T 0 is identified with the unity T of H(As γ ). For instance, in H(As 1 ), we have

∆(T 3 ) = T 0 ⊗ T 3 + T 1 ⊗ (T 0 T 2 + T 1 T 1 + T 2 T 0 ) + T 2 ⊗ (T 0 T 0 T 1 + T 0 T 1 T 0 + T 1 T 0 T 0 ) + T 3 ⊗ (T 0 T 0 T 0 T 0 ) = T ⊗ T 3 + 2 T 1 ⊗ T 2 + T 1 ⊗ T 11 + 3 T 2 ⊗ T 1 + T 3 ⊗ T , (3.2.3)
and in H(As 2 ), we have

∆(T 3 ) = T 0 ⊗ T 3 + T 1 ⊗ (T 0 T 0 T 2 + T 0 T 2 T 0 + T 2 T 0 T 0 + T 0 T 1 T 1 + T 1 T 0 T 1 + T 1 T 1 T 0 ) + T 2 ⊗ (T 0 T 0 T 0 T 0 T 1 + T 0 T 0 T 0 T 1 T 0 + T 0 T 0 T 1 T 0 T 0 + T 0 T 1 T 0 T 0 T 0 + T 1 T 0 T 0 T 0 T 0 ) + T 3 ⊗ T 0 T 0 T 0 T 0 T 0 T 0 T 0 = T ⊗ T 3 + 3 T 1 ⊗ T 2 + 3 T 1 ⊗ T 11 + 5 T 2 ⊗ T 1 + T 3 ⊗ T . ( 3
T k ⊗   i1+•••+i kγ+1 =n-k T i1 . . . T i kγ+1   (3.2.5) = k 0 T k ⊗   n k i1+•••+i kγ+1 =n-k T i1 . . . T i kγ+1   (3.2.6) = k 0 T k ⊗   i1+•••+i kγ+1 0 T i1 . . . T i kγ+1   (3.2.7) = k 0 T k ⊗   i 0 T i   kγ+1 (3.2.8) = k 0 T k ⊗ σ kγ+1 1 , (3.2.9)
showing that for any n 0, ∆(T n ) is the homogeneous component of degree

n in k 0 T k ⊗ σ kγ+1 1 .
Therefore, by the definition of the coproduct of FdB γ (see (1.1.5)), the map T n → S n from H(As γ ) to FdB γ is an isomorphism of Hopf algebras.

3.3. Hopf algebra of forests of bitrees. Let us describe here a general construction on PROs. If G is a bigraded set of the form G = p 1 q 1 G(p, q), we denote by G op the bigraded set defined by G op (p, q) := G(q, p), p, q 1. (3.3.1)

From a geometrical point of view, any elementary prograph over G op is obtained by reversing from bottom to top an elementary prograph over G. We moreover denote by rev : Free(G op ) → Free(G) the bijection sending any prograph x of Free(G op ) to the prograph rev(x) of Free(G) obtained by reversing x from bottom to top. Now, given a PRO P := Free(G)/ ≡ , we define S(P) as the PRO

S(P) := Free (G G op ) /∼ = , (3.3.2)
where ∼ = is the finest congruence of Free(G G op ) satisfying

x ∼ = y if (x, y ∈ Free(G) and x ≡ y) or (x, y ∈ Free(G op ) and rev(x) ≡ rev(y)).

(3.3.3)

Notice that in this definition, we consider Free(G) and Free(G op ) as sub-PROs of Free(G G op ) in an obvious way. Notice also that if P is a free PRO Free(G), then the congruence ≡ is trivial, so that ∼ = is also trivial, and S(P) = Free(G G op ). Besides, as an other immediate property of this construction, remark that when P is a stiff PRO, the congruence ∼ = satisfies (C2) and (C3), and then, S(P) is a stiff PRO.

We shall present here two Hopf algebras coming from the construction S applied on PRF γ and As γ .

. . . k 1 . . . k 2 ≡ b b . . . . . . 1 . . . 2 , k 1 + k 2 = γ, 1 + 2 = γ. (3.3.7)
We can observe that BAs γ is a stiff PRO because ≡ satisfies (C2) and (C3). Notice that S(As γ ) = BAs γ and BAs 0 = FBT 0 . We consider on BAs γ the grading ω inherited from the one of FBT γ . This grading is still well-defined in BAs γ since any ≡-equivalence class contains prographs of a same degree. Notice that BAs 1 is very similar to the PRO governing bialgebras (see [START_REF] Markl | Operads and PROPs[END_REF]). Indeed, it only lacks in BAs 1 the usual compatibility relation between its two generators. Notice also that the PRO governing bialgebras is not a stiff PRO. By Theorem 2.13 and Proposition 2.5, H(BAs γ ) is then a combinatorial Hopf algebra. Moreover, we can observe that H(As γ ) is a quotient bialgebra of H(BAs γ ).

Hopf algebra of heaps of pieces.

We present here the construction of a Hopf algebra depending on a nonnegative integer γ, whose bases are indexed by heaps of pieces.

3.4.1. PRO of heaps of pieces. Let γ be a nonnegative integer and Heap γ be the free PRO generated by G := G(γ + 1, γ + 1) := {a}, with the grading ω defined by ω(a) := 1. Any prograph x of Heap γ can be seen as a heap of pieces of width γ + 1 (see [START_REF] Viennot | Heaps of pieces. I. Basic definitions and combinatorial lemmas[END_REF] for some theory about these objects). For instance, the prograph 3.4.2. Hopf algebra. By Theorem 2.3 and Proposition 2.5, H(Heap γ ) is a combinatorial Hopf algebra. By Proposition 2.4, as an algebra, H(Heap γ ) is freely generated by the S λ where the λ are heaps of pieces that cannot be obtained by juxtaposing two heaps of pieces. Its bases are indexed by horizontally connected heaps of pieces of width γ + 1 where the degree of a basis element S Λ is the number of pieces of Λ.

3.4.3.

Coproduct. The coproduct of H(Heap γ ) can be described, like the one of CK on forests, by means of admissible cuts on heaps of pieces. Indeed, if Λ is a horizontally connected heap of pieces, by definition of the construction H,

∆(S Λ ) = Λ ∈Adm(Λ) S Λ ⊗ S Λ/ Λ , (3.4.3)
where Adm(Λ) is the set of admissible cuts of Λ, that is, the set of heaps of pieces obtained by keeping an upper part of Λ and by readjusting it so that it becomes horizontally connected and where Λ/ Λ denotes the heap of pieces obtained by removing from Λ the pieces of Λ and by readjusting the remaining pieces so that they form an horizontally connected heap of pieces. For instance, in H(Heap 1 ), we have

∆S = S ∅ ⊗ S + S ⊗ S + S ⊗ S + S ⊗ S + S ⊗ S + S ⊗ S ∅ . (3.4.4)
3.5. Hopf algebra of heaps of friable pieces. From a PRO being a special quotient of Heap γ , we construct a Hopf algebra structure on the (γ + 1)-st tensor power of the vector space Sym.

3.5.1. PRO of heaps of friable pieces. Let γ be a nonnegative integer and FHeap γ be the quotient of Heap γ by the finest congruence ≡ satisfying We can observe that FHeap γ is a stiff PRO because ≡ satisfies (C2) and (C3) and FHeap 0 = Heap 0 . We call FHeap γ the PRO of heaps of friable pieces of width γ + 1. This terminology is justified by the following observation. Any piece of width γ + 1 (depicted by ) consists in γ + 1 small pieces, called bursts, glued together. This forms a friable piece (depicted, for γ = 2 for instance, by

). The congruence ≡ of Heap γ can be interpreted by letting all pieces break under gravity, separating the bursts constituting these. For instance, the prographs of (3.5.3), respectively, encoded by the heaps of pieces obtained by replacing each piece of any heap of pieces of (3.5.4) by friable pieces.

The grading ω of FHeap γ is the one inherited from the one of Heap γ . This grading is still well-defined in Heap γ since any ≡-equivalence class contains prographs of a same degree. Since the reduced elements of FHeap γ have no wire, they are encoded by horizontally connected heaps of friable pieces.

Besides, FHeap γ admits the following alternative description using the B construction (see Section 2.4.2). Indeed, FHeap γ is the sub-PRO of B(N) generated by 1 γ+1 , where N denotes here the additive monoid of nonnegative integers and 1 γ+1 denotes the sequence of γ + 1 occurrences of 1 ∈ N. The correspondence between heaps of friable pieces and words of integers of this second description is clear since any element x of the sub-PRO of B(N) generated by 1 γ+1 encodes a heap of friable pieces consisting, from left to right, in columns of x i bursts for i ∈ [n], where n is the length of x. For instance, the word 122211 encodes the heap of friable pieces of (3.5.5).

3.5.2. Hopf algebra. By Theorem 2.13 and Proposition 2.5, H(FHeap γ ) is a combinatorial Hopf subalgebra of H(Heap γ ). The bases of H(FHeap γ ) are indexed by horizontally connected heaps of friable pieces of width γ + 1 where the degree of a basis element T Λ is the number of pieces of Λ.

3.5.3. Coproduct. The coproduct of H(FHeap γ ) can be described with the aid of the interpretation of FHeap γ as a sub-PRO of B(N). Indeed, if Λ is an horizontally connected heap of friable pieces, by Proposition 2.12,

∆(T Λ ) = Λ1,Λ2∈FHeap γ Λ=Λ1+Λ2 T Λ 1 ⊗ T Λ 2 , ( 3.5.6)
where Λ 1 + Λ 2 is the heap of friable pieces obtained by stacking Λ 2 onto Λ 1 and where Λ 1 (resp. Λ 2 ) is the readjustment of Λ 1 (resp. Λ 2 ) so that it is horizontally connected. Proof. Let us show that there are (γ + 2) n-1 reduced elements in FHeap γ .

Let x be a prograph of Heap γ . We say that x is a γ-falling staircase if x is of the form

x = (1 p1 * a * 1 q1 ) • (1 p1+p2 * a * 1 q2 ) • • • • • (1 p1+p2+•••+p * a * 1 q ), ( 3
.5.9)

where p 1 = 0, q = 0, and 0 p i γ for all 2 i . Any γ-falling staircase can be encoded by the sequence (p 2 , . . . , p ) involved in its decomposition (3.5.9). For instance, for x := Moreover, we say that x is a γ-standard form if x is an horizontal composition of γ-falling staircases. Any γ-standard form can be encoded by the sequence of the sequences encoding, from left to right, its falling staircases.

By definition of FHeap γ as a quotient of Heap γ , one can observe that two different γ-standard forms are sent to two different heaps of friable pieces by the canonical surjection Heap γ FHeap γ . Besides, one can straightforwardly prove by induction on the degree that any reduced element of Heap γ is ≡-equivalent to a γ-falling staircase. This shows that the reduced elements of FHeap γ are in bijection with the standard forms of Heap γ of a same degree. Hence, the reduced elements of FHeap γ of degree n can be encoded by sequences of k words on the alphabet {0} ∪ [γ], having a total of n -k letters. Whence the result.

3.5.5. Miscellaneous properties. By the dimensions of H(FHeap γ ) provided by Proposition 3.3, as a graded vector space, H(FHeap γ ) is the γ + 1-st tensor power of the underlying vector space of Sym. Indeed, the n-th homogeneous components of these two spaces have the same dimension. Besides, notice that since FHeap γ is by definition a sub-PRO of the PRO obtained by applying the construction B on a commutative monoid, H(FHeap γ ) is cocommutative.

Concluding remarks and perspectives

We have defined a construction H establishing a new link between the theory of PROs and the theory of combinatorial Hopf algebras, by generalizing a former construction from operads to bialgebras. By the way, we have exhibited the so-called stiff PROs which is the most general class of PROs for which our construction works.

By using H, we have defined some new and recovered some already known combinatorial Hopf algebras by starting with very simple PROs. Nevertheless, we are very far from having exhausted the possibilities, and it would not be surprising that H could reconstruct some other known Hopf algebras, maybe in an unexpected basis.

Computing the Hilbert series of a combinatorial Hopf algebra is, usually, a routine work. Nevertheless, in the general case, it is very difficult to compute the Hilbert series of HP when P is a free PRO. Indeed, this computation requires to know, given a free PRO P, the series F P (t) := x∈red(P) t deg(x) , (3.5.11) which seems difficult to explicitly describe in general and is not known to the knowledge of the authors.

As an other perspective, it is conceivable to go further in the study of the algebraic structure of the bialgebras obtained by H. The question of the potential autoduality of HP depending on some conditions on the PRO P is noteworthy. A way to solve this problem is to provide enough conditions on P to endow HP with a bidendriform bialgebra structure [START_REF] Foissy | Bidendriform bialgebras, trees, and free quasi-symmetric functions[END_REF]. In such algebraic structures, there are two products ≺ and and two coproducts ∆ ≺ and ∆ satisfying some precise axioms. This way to solve this perspective is based upon the fact that any bidendriform bialgebra is free and self-dual as a bialgebra [START_REF] Foissy | Bidendriform bialgebras, trees, and free quasi-symmetric functions[END_REF].

  x of P, by ∆ (S x ) := y,z∈P y•z=x S red(y) ⊗ S red(z) .(2.1.3)Throughout this section, we shall consider some examples involving the free PRO generated by G := G(2, 2) G(3, 1) where G(2, 2) := {a} and G(3, 1) := {b}, denoted by AB. For instance, we have in H(AB)

For⊗

  instance, we have in H(AB) S 10 . (2.2.11) 2.2.5. Quotient bialgebras. Proposition 2.8. Let G and G be two bigraded sets such that G ⊆ G. Then, the map φ : H(Free(G)) → H(Free(G )) linearly defined, for any reduced element x of Free(G), by φ(S x ) := S x if x ∈ Free(G ), 0 otherwise,

  2) where G(1, 1) := {a} and G(2, 2) := {b} by the finest congruence ≡ satisfying

  red([x]) := {red (x ) : x ∈ [x]} .(2.3.7)Lemma 2.10. Let P be a free PRO and ≡ be a stiff congruence of P. For any element x of P,red ([x]) = [red(x)] . (2.3.8)Proof. Let us denote by y the element red(x) and let y ∈ red([x]). Let us show that y ∈ [red(x)]. By Definition (2.3.7), there is an element x of P such that x ∈ [x] and red(x ) = y . Since ≡ satisfies (C3), dec(x ) and dec(x) have the same length and dec(x) i ≡ dec(x) i for all i ∈ [ ].Moreover, since ≡ satisfies (C2), for all i ∈ [ ], dec(x ) i and dec(x) i are both reduced elements or are both wires. Hence, since dec(y ) and dec(y) are, respectively subwords of dec(x ) and dec(x), they have the same length k and dec(y ) j ≡ dec(y) j for all j ∈ [k]. Finally, since ≡ is a congruence of PROs, y ≡ y. This shows that y ∈ [red(x)] and hence, red([x]) ⊆ [red(x)]. Again, let us denote by y the element red(x) and let y ∈ [red(x)]. Let us show that y ∈ red([x]). Since y ≡ y and ≡ satisfies (C3), dec(y ) and dec(y) have the same length and dec(y ) i ≡ dec(y) i for all i ∈ [ ]. Moreover, since y = red(x), by Lemma 1.2, for some p 1 , . . . , p +1 0, we have x = 1 p1 * dec(y) 1 * • • • * 1 p * dec(y) * 1 p +1 . Now, by setting x := 1 p1 * dec(y ) 1 * • • • * 1 p * dec(y ) * 1 p +1 , the fact that ≡ is a congruence of PROs implies x ≡ x. Since y = red(x ), this shows that y ∈ red([x]) and hence, [red(x)] ⊆ red([x]).

  by using the sylvester monoid congruence [HNT05], or the Poirier-Reutenauer Hopf algebra [PR95] by using the plactic monoid congruence [DHT02,HNT05]. 2.3.4. The importance of the stiff congruence condition. Let us now explain why the stiff congruence condition required as a premise of Theorem 2.13 is important by providing an example of a non-stiff congruence of PROs failing to produce a bialgebra. Consider the PRO P quotient of the free PRO generated by G := G(1, 1) G(2, 2) where G(1, 1) := {a} and G(2, 2) := {b} by the finest congruence ≡ satisfying

Proposition 2. 15 .

 15 Let O be an operad such that the monoid (O(1), • 1 ) does not contain any nontrivial subgroup. Then, R(O) is a stiff PRO. Proof. As any operad, O is the quotient by a certain operadic congruence ≡ of the free operad generated by a certain set of generators G. It follows directly from the definition of the construction R that the PRO R(O) is the quotient by the congruence of PROs ≡ of the free PRO generated by G where G (p, q) := G(p) if p 1 and q = 1, ∅ otherwise, (2.4.3) and ≡ is the finest congruence of PROs satisfying x ≡ y for any relation x ≡ y between elements x and y of the free operad generated by G. Since by hypothesis (O(1), • 1 ) does not contain any nontrivial subgroup, for all elements x and y of O(1) \ {1}, x • 1 y = 1. Then, ≡ satisfies (C2). Moreover, by definition of R, ≡ satisfies (C3). Hence, R(O) is a stiff PRO. 2.4.2. From monoids to stiff PROs. Any monoid M can be seen as an operad concentrated in arity one. Then, starting from a monoid M, one can construct a PRO B(M) by applying the construction R on M seen as an operad.

  We conclude this paper by presenting examples of application of the construction H. The PROs considered in this section fit into the diagram represented by Figure 1 and the obtained Hopf algebras fit into the diagram represented by Figure 2.3.1. Hopf algebras of forests. We present here the construction of two Hopf algebras of forests, one depending on a nonnegative integer γ, and with different gradings. The PRO we shall define in this section will intervene in the next examples.

Figure 1 .

 1 Figure 1. Diagram of PROs where arrows (resp. ) are injective (resp. surjective) PRO morphisms. The parameter γ is a positive integer. When γ = 0, PRF 0 = As 0 = Heap 0 = FHeap 0 and FBT 0 = BAs 0 .

Figure 2 .

 2 Figure 2. Diagram of combinatorial Hopf algebras where arrows (resp. ) are injective (resp. surjective) PRO morphisms. The parameter γ is a positive integer. When γ = 0, H(PRF 0 ) = H(As 0 ) = H(Heap 0 ) = H(FHeap 0 ) and H(FBT 0 ) = H(BAs 0 ).

  3.1.3. Coproduct. By definition of the construction H, the coproduct of H(PRF γ ) is given on a generator S T by ∆(S T ) = T ∈Adm(T ) S T ⊗ S T / T , (3.1.1)

  3.3.1. PRO of forests of bitrees.Let γ be a nonnegative integer and FBT γ be the free PRO generated by G := G(γ + 1, 1) G(1, γ + 1) where G(γ + 1, 1) := {a} and G(1, γ + 1) := {b}, with the grading ω defined by ω(a) := ω(b) := 1. One has S(PRF γ ) = FBT γ . Any prograph x of FBT γ can be seen as a forest of γ-bitrees, that are labeled planar trees where internal nodes labeled by a have γ + 1 children and one parent, and the internal nodes labeled by b have one child and γ + 1 parents. Since the reduced elements of FBT γ have no wire, they are encoded by forests of nonempty γ-bitrees.

2 , k 1

 21 + k 2 = γ, 1 + 2 = γ,

of

  Heap 2 is encoded by the heap of pieces of width 3 depicted by .(3.4.2)Notice that Heap 0 = PRF 0 . Besides, since the reduced elements of Heap γ have no wire, they are encoded by horizontally connected heaps of pieces of width γ + 1.

  for γ = 2, the ≡-equivalence class of

  For instance, we have in H(FHeap 1 ) For any nonnegative integer γ, the n-th homogeneous component of H(FHeap γ ) has dimension (γ + 2) n-1 .

  x = (1 0 * a * 1 3 ) • (1 0+1 * a * 1 2 ) • (1 0+1+2 * a * 1 0 ) so that x is a 2-fallingstaircase encoded by the sequence (1, 2).

1 and O 2 such that φ commutes with the partial composition maps and preserves the arities. A subset S of an operad O is a suboperad of O if 1 ∈ S and the composition of O is stable in S. The suboperad of O generated by a subset G of O is the

  The natural bialgebra of an operad. Let us recall a very simple construction associating a Hopf algebra with an operad. A slightly different version of this construction is considered in [vdL04, CL07, ML14]. Let O be an operad and denote by O + the set O \ {1}. The natural bialgebra of O is the free commutative algebra H (O) spanned by the T x , where the x are elements of O + . The bases of H (O) are thus indexed by finite multisets of elements of O + .

	smallest
	suboperad of O containing G.
	1.2.2. The unit of
	H (O) is denoted by T 1 and the coproduct of H (O) is the unique algebra morphism satisfying,
	for any element x of O + ,
	∆(T x ) =
	y,z1,...,z ∈O
	y•[z1,...,z ]=x

m n 1, (1.2.6) the total composition map of O. It is defined for any x ∈ O(n) and y 1 , . . . , y n ∈ O by x • [y 1 , . . . , y n ] := (. . . ((x • n y n ) • n-1 y n-1 ) . . . ) • 1 y 1 .

(1.2.7)

If x is an element of O(n), we say that the arity |x| of x is n. An operad morphism is a map φ : O 1 → O 2 between two operads O

  Duality. When P admits a grading, let us denote by H(P) the graded dual of H(P). By definition, the adjoint basis of the fundamental basis of H(P) consists in the elements S

			2.2.5)
	2.2.4. x ,y ∈P	S x •y	(2.2.6)
	x •y ∈red(P)
	red(x )=x,red(y )=y
	and
	∆ (S x ) = S Besides, again by duality, we have y,z∈P y * z=x
	∆(S x ) =
	y,z∈red(P)

x , x ∈ red(P).

Proposition 2.7. Let P be a free PRO admitting a grading. Then, for any reduced elements x and y of P, the product and the coproduct of H(P) satisfy

S x • S y = y ⊗ S z .

(2.2.7)

Proof. Let us denote by -, -: H(P) ⊗ H(P) → C the duality bracket between H(P) and its graded dual.

By duality, we have

S x • S y = z∈red(P) ∆(S z ), S x ⊗ S y S z . (

2

.2.8) Expression (2.2.6) follows from the fact that for any reduced element z of P, S x ⊗ S y appears in ∆(S z ) if and only if there exist x , y ∈ P such that x • y = z, red(x ) = x and red(y ) = y. S y • S z , S x S y ⊗ S z . (2.2.9) Expression (2.2.7) follows from the fact that for any reduced elements y and z of P, S x appears in S y • S z if and only if y * z = x.

  It is enough to check that these sums have the same support. Indeed, (2.3.6) is by definition multiplicity free and (2.3.5) is multiplicity free because P is free, and all elements of a ≡-equivalence class have the same input arity and the same output arity.Assume that there is a reduced element t of P such that S t appears in (2.3.5). Then, one has t = x * y for two reduced elements x and y of P such that x ∈ [x] and y ∈ [y]. Since ≡ is a congruence of PROs, we have [x * y ] = [x * y] and thus, t ∈ [x * y]. This shows that S t also appears in (2.3.6).

	and
	T [x * y] =	S z .	(2.3.6)
	z∈[x * y]
	Let us show that (2.3.5) and (2.3.6) are equal.
		* y	(2.3.5)

  r) and y 11 . . . y 1q1 . . . y r1 . . . y rqr ∈ R(O)(p, q), we have x 1 . . . x r • y 11 . . . y 1q1 . . . y r1 . . . y rqr := x 1 • [y 11 , . . . , y 1q1 ] . . . x r • [y r1 , . . . , y rqr ],(2.4.2)

  3.2.1. Associative PRO. Let γ be a nonnegative integer and As γ be the quotient of PRF γ by the finest congruence ≡ satisfying

		a			a
		a	≡		a
	. . .	. . .	. . .	. . .	. . .
	k 1		k 2

  Isomorphism with the deformation of the noncommutative Faà di Bruno Hopf algebra. For any nonnegative integer γ, the Hopf algebra H(As γ ) is the deformation of the noncommutative Faà di Bruno Hopf algebra FdB γ .

		.2.4)
	3.2.4. Theorem 3.1. Proof. Let us set σ 1 := n 0 T n . By (3.2.2), we have
		n
	∆(σ 1 ) =
	n 0	k=0

  3.3.2. Hopf algebra. By Theorem 2.3 and Proposition 2.5, H(FBT γ ) is a combinatorial Hopf algebra. By Proposition 2.4, as an algebra, H(FBT γ ) is freely generated by the S T , where the T are nonempty γ-bitrees. Its bases are indexed by planar forests of such bitrees where the degree of a basis element S F is the total number of internal nodes in the bitrees of F . Moreover, by Proposition 2.8, since PRF γ is generated by a subset of the generators of FBT γ , H(PRF γ ) is a quotient bialgebra of H(FBT γ ).3.3.3.Coproduct. The coproduct of H(FBT γ ) can be described, like the one of CK on forests, by means of admissible cuts on forests of γ-bitrees. We have for instance Dimensions. We only know the dimensions of H(FBT γ ) when γ = 0. In this case, 0-bitrees of size n are linear trees and can hence be seen as words of length n on the alphabet {a, b}. Therefore, as H(FBT γ ) is free as an algebra, the bases of H(FBT 0 ) are indexed by multiwords on {a, b} and its Hilbert series is PRO of biassociative operators and its Hopf algebra. Let BAs γ be the quotient of FBT γ by the finest congruence ≡ satisfying

	∆S	= S ∅ ⊗ S		+ S ⊗ S	+ S	⊗ S
			+ S		⊗ S	+ S	⊗ S	+ S	⊗ S ∅ . (3.3.4)
	3.3.4. H(t) := 1 +	2 2n-1 t n .	(3.3.5)
						n 1
	3.3.5. a			a
		a	≡		a
	. . .	. . .	. . .	. . .	. . .	. . .
	k 1		k 2	1

Dimensions.

Proposition 3.2. For any nonnegative integer γ, the Hilbert series C γ (t) of H(Heap γ ) satisfies C γ (t) = n 0 C γ,n (t), where C γ,n (t) := P γ,n (t) -

(3.4.5)

and

(3.4.7)

Proof. The proof of this statement uses the Inversion Lemma of Viennot [START_REF] Viennot | Heaps of pieces. I. Basic definitions and combinatorial lemmas[END_REF] and some ideas employed in [START_REF] Bousquet-Mélou | Lattice animals and heaps of dimers[END_REF] for the enumeration of the so-called connected heaps.

The first ingredient consists in the alternating generating series

of the heaps of pieces of Heap γ of height no greater than 1 (called trivial heaps in [START_REF] Viennot | Heaps of pieces. I. Basic definitions and combinatorial lemmas[END_REF] and [START_REF] Bousquet-Mélou | Lattice animals and heaps of dimers[END_REF]). This series is obviously F γ,n (t). By the Inversion Lemma, we have that P γ,n (t) is the generating series of the elements of Heap γ with exactly n inputs (and thus, also n outputs). Now, to count only the reduced elements of Heap γ , observe that any element x of Heap γ with n inputs is either reduced or is of the form x = y * 1 1 * z where y is a reduced element of Heap γ with k inputs and z is an element of Heap γ with n -k -1 inputs. Then, we have (3.4.13) Among these four integer sequences, only (3.4.12) is listed in [Slo] as Sequence A059715.


Adrian Dragos

Cédric Ciubotariu
email: adrian.ciubotariu@femto-st.fr

Philippe Cleévy
email: cclevy@femto-st.fr

Lutz
email: plutz@femto-st.fr

Ioan Alexandru Ivan
email: ivan@enise.fr

Actuated MOEMS Micro-Mirror based on PMN-PT Piezoelectric Material

This paper investigates the use of a PMN-PT [001] piezoelectric actuator to be integrated in smart Micro-Opto-Electrical-Mechanicals Systems (MOEMS). Unlike most piezoelectric materials, PMN-PT [001] can generate large-stroke out-of-plane displacement. This is due to its very high longitudinal piezoelectric coefficient of up to 4500pm/V. After an introduction on MOEMS actuation and a short description of the Reconfigurable Free Space Micro-Optical Bench (RFS-MoB) in which the studied actuator may be included is presented, a bulk actuator is proposed. FEM simulations are then presented highlighting some tradeoffs: increased displacement with the reduction in size while decreasing the optical aberration. It was observed that for actuators with a smaller surface than 800x800µm 2 and 200µm thick, displacement larger than 325nm is largely achievable and that the size of the usable area of the actuator varies in size with the applied voltage.

I.

INTRODUCTION

In micro-optical applications there is an ever growing demand for better micro-mirror control and better actuator integration. Related applications notably count optical switches [START_REF] Xu | Reconfigurable optical directed-logic circuits using microresonator-based optical switches[END_REF] [START_REF] Ramesh | Fabrication and characterization of a piezoelectric gallium nitride switch for optical MEMS applications[END_REF], variable optical attenuators [START_REF] Koh | Study of hybrid driven micromirrors for 3-D variable optical attenuator applications[END_REF] or biomedical imaging [START_REF] Ritter | A 30-MHz piezocomposite ultrasound array for medical imaging applications[END_REF] [START_REF] Shung | Piezoelectric materials for high frequency medical imaging applications: A review[END_REF]. Among the challenges encountered in MOEMS when aiming for increased functionality is the local displacement. Nowadays commonly used micro-actuators are either electrostatic [START_REF] Kim | Design and implementation of electrostatic microactuators in ultrasonic frequency on a flexible substrate, PEN (polyethylene naphthalate)[END_REF] or thermal [START_REF] Ogando | Design and characterization of a fully compliant out-of-plane thermal actuator[END_REF]. There is, however, a growing use of piezoelectric actuators in MOEMS due to their better understanding, also to the new developments regarding hysteresis reduction and the emergence of new improved materials. Having high bandwidth [START_REF] Huang | Wide-bandwidth piezoelectric energy harvester integrated with parylene-C beam structures[END_REF] and sub-nanometer resolution capabilities, piezoelectric actuators show interesting features when actuating micro-mirrors in optical applications. This is key in developing better performing MOEMS applications.

Commonly, piezoelectric actuators used in MOEMS are made of PZT, a piezoceramic material with a granular structure. It does present some drawbacks, one of which is its high hysteresis [START_REF] Wongdamnem | Comparative studies of dynamic hysteresis responses in hard and soft PZT ceramics[END_REF] that has great impact on accuracy. Novel materials aim not only at reducing the hysteresis but also at increasing performance. Lead-Magnesium-Niobate-Lead-Titanate (PMN-PT) is a piezoelectric material with a monocrystalline structure which presents high dynamic range and piezoelectric coefficients while reduced hysteretic behavior [START_REF] Chaipanich | Dielectric and ferroelectric hysteresis properties of 1-3 lead magnesium niobate-lead titanate ceramic/Portland cement composites[END_REF].

Among the advantages of using PMN-PT we note its ability of being used in bulk [START_REF] Tang | Development of high performance piezoelectric d33 mode MEMS vibration energy harvester based on PMN-PT single crystal thick film[END_REF] and the ease of fabrication [START_REF] Ivan | PMN-PT (lead magnesium niobate-lead titanate) piezoelectric material micromachining by excimer laser ablation and dry etching (DRIE)[END_REF]. This paper investigates how bulk PMN-PT actuators behave when integrated in MOEMS. The objective is to further investigate the usability of a bulk piezo-actuator made of PMN-PT in a MOEMS as a micro-mirror actuator. In [START_REF] Ciuboariu | Size-dependent Analysis and Experiments of Bulk PMN-PT [001] Piezoelectric Actuator for MOEMS Micro-Mirrors[END_REF] the connection between the decrease in measured displacement and the increase of the actuator width has been shown. Here, Finite Element simulation studies on how the usable surface varies with the applied voltage is presented. This is followed by a study on how the usable surface varies with the increase of the actuator size. Working domains are then defined. This paper is structured as follows: a brief introduction in MOEMS, the actuation principles and materials used are presented in Section I. A short description of the Reconfigurable Free Space Micro-Optical Bench (RFS-MoB) in which the studied actuator may be included is presented, along with its particularities in Section II. Section III investigates the design and simulations, while Section IV focuses on the experimental measures regarding the PMN-PT actuator. A conclusion ends the paper highlighting the results and the defined domain of actuation.

II. MOEMS APPLICATION

A. Reconfigurable Micr-Optical Bench

A Reconfigurable Free Space Micro-Optical Bench (RFS-MoB) has been designed [START_REF] Bargiel | Towards micro-assembly of hybrid MOEMS components on a reconfigurable silicon free-space micro-optical bench[END_REF] using removable and adjustable silicon holders for easy manipulation and alignment by a robotic micro-assembly station. While already having developed different components (Fig. 1.) such as hybrid micro-lenses, beam splitters, micro-apertures and micro-mirrors, there is a need for actuated micro-mirrors for enhancing the usability of the RFS-MoB, for instance in interferometer applications. This means adapting an actuation solution.

Fig. 2. Assembly proposition [START_REF] Bargiel | Towards micro-assembly of hybrid MOEMS components on a reconfigurable silicon free-space micro-optical bench[END_REF] The designed silicon micro-mirror support measures (Fig. 2.) 1.2 x 0.8 x 0.1 mm 3 (height x width x thickness) and presents an elastic structure at the base, for position holding in the RFS-MoB structure.

The objective of the actuator is to fit the micro-mirror with an out-of-plane perpendicular displacement and to be integrated on the silicon support for better dynamics and small space occupancy (Fig. 3).

B. Actuation approach

The actuator intended to achieve the out-of-plane motions falls under constraints regarding surface and thickness. Due to the design of the silicon support, the maximum usable surface measures 0.8 x 0.8 mm 2 (Figs. 12). The thickness of the actuator is also of importance as to not topple the holder due to its inertial mass or during actuation. The displacement needed in optical applications are related to the wavelength (λ) of the light used and as such a minimum is required. In the case of spectral interferometry the required displacement is reduced to meaning that for a traditional red laser beam (λ=~650nm) the minimum displacement is half the wavelength (~325nm). To achieve this while also maintaining the thickness of the material low, materials with high and very high piezoelectric coefficients are needed. PMN-PT cut and polled along the [001] crystalline direction stands out. Recent improvements in crystal growth techniques have shown the possibility of obtaining values of over 4500pm/V [START_REF] Ciuboariu | Size-dependent Analysis and Experiments of Bulk PMN-PT [001] Piezoelectric Actuator for MOEMS Micro-Mirrors[END_REF] for its piezoelectric coefficients. Studies on the actuation potential of PMN-PT [001] have shown that for a 200µm think film actuation can exceed the 325nm limit [START_REF] Yamamoto | Electrical and physical properties of repoled PMN-PT single-crystal sliver transducer[END_REF].

III. FINITE ELEMENTS SIMULATIONS

The goal of the Finite Elements (FEM) simulations is to provide guidelines for the expected behavior of PMN-PT micro actuators.

As the micro-actuator is intended for a micro-mirror, one more aspect in regards to the optical necessities to be met is the maximum accepted aberration for planar displacement which is 10% (or a maximum λ/20 in our case). The parameter values used in the FEM simulations are presented in Table I The actuator is simulated as being fixed on one side to represent the soldered side and free on the opposite side to simulate the mirror. The clamping has been done on the entire fixed surface, without any planar freedom. Due to this fixing, specific free-side behavior is noticed (Fig. 5). A curvature of the top surface arises, which is dependent on the bulk actuator size and also on the applied voltage. Fig. 5. Diagonal section view of free side behaviour for different actuator widths at an applied voltage of 400V: a)250x250µm 2 ; b)300x300µm 2 ; c)400x400µm 2 ; d)800x800µm 2 . PMN-PT thickness is 200µm.

The signal applied varies between 0V and 400V, a value that approaches the saturation limit of PMN-PT. As actuation is observed no matter the size of the actuator, the focus is on what the maximum diameter of a laser beam can be in order to maintain a maximum 10% aberration while still reaching the 325nm displacement threshold. Figure 6 presents a schematic view of the elements of interest: the displacement δZ, the aberration limit λ/20, the width of the actuator w and the maximum diameter of the usable surface Фmax. To observe the dependence of the maximum laser beam diameter that can be used without aberrations on a mirror actuated by PMN-PT four sizes were arbitrarily considered in order to 250x250µm 2 , 300x300µm 2 , 400x400µm 2 and 800x800µm 2 . Figure 7 presents the usable surface limits in relation to the minimum displacement needed. The top graph from Fig. 7 represents the usable diameter corresponding to actuators of different widths, as pointed out. The bottom graph represents the evolution of the displacement at the center of each individual actuator, as predicted by the FEM simulation. The points where each displacement curve intersects the minimum needed displacement of 325nm are then transferred to the top graph as being the minimum applied voltage required for each size actuator to reach 325nm. As there is a need for planar displacement, the usable area is defined as the displacement at the center of the actuator plus the max accepted aberration (32.5nm). The points where the minimum displacement value intersects the actuator displacement curve is correlated with the maximum value of the laser beam diameter. The curves in the top graph from Fig. 7 show the variation of Фmax. This means that phaseshifting interferometry is possible if the diameter value of the used laser beam is situated under and, at most, on the curve drawn for the chosen actuator size, while remaining inside the defined checkered area. It can be observed that for the 250x250µm 2 actuator the maximum diameter is that of the inscribed circle on the surface (79% of the available surface); for the 300x300µm 2 actuator the value decreases to ~180µm (29% of the available surface) while for the 400x400µm 2 only an area with a maximum diameter of ~110µm (6% of the available surface). Although the 800x800µm 2 actuator shows the largest planar surface, it does not reach the minimum displacement needs.

IV. EXPERIMENTAL RESULTS

A series of experimental measurements have been done on different size PMN-PT actuators in order to quantify the displacement. To ensure the best conductivity, the 200µm thick PMN-PT plate has been cleaned and recoated with a 140nm thick gold layer. It has then been soldered to a gold coated glass support using silver based solder 30µm thick. The PMN-PT samples have been cut using a saw dicing machine. The dimensions that were cut range from 200x200µm 2 to 800x800µm 2 , with 100µm increments for both the width and the length simultaneously. To ensure the separation between the actuators, the saw dicing was done 20µm from the glass baseplate. The connections of the actuators have been done using gold wire bonding, with 30µm in diameter wire. Figure 8 presents the fabrication process. Using an interferometer, individual measurements were done at the center of each PMN-PT actuator. The max measured displacements were then compared with the FEM simulations. Due to the wire-bonding characteristics, measurements on the smaller size actuators (200x200µm 2 to 500x500µm 2 ) failed directly. The interface between the gold wire and the actuator surface generated too significant noise and spurious reflections resulting in the disregard of the measurements. Fig. 9 presents the predicted maximum displacement curve of different size actuators coupled with the experimental measures of only the 600x600µm 2 , 700x700µm 2 and 800x800µm 2 . The measured displacement does, however prove consistent as the result for the 600x600µm 2 is very close to previously measured values [START_REF] Ciuboariu | Size-dependent Analysis and Experiments of Bulk PMN-PT [001] Piezoelectric Actuator for MOEMS Micro-Mirrors[END_REF]. The values for the measured displacement on the graph represent the average of 8 independent measures on the 600x600µm 2 , 700x700µm 2 and 800x800µm 2 respectively. The measures were done after repositioning the interferometer spot on the actuator surface. The maximum displacement measured at the center of the PMN-PT actuator is larger than the FEM predictions. This is due to the inherit elasticity of the silver based solder and its thickness. A plausible explanation for the decrease in the measured displacement of the PMN-PT actuator with its width is the faster saturation of the PMN-PT actuator, having a smaller volume.

The results lead to the following conclusions: first, the minimum desired displacement can be achieved with larger size actuators, making fabrication easier and allowing for larger diameter beams to be used and second, the free face surface presents a larger curvature radius, allowing again to add to the maximum diameter of a used laser beam.

V. CONCLUSION

The paper has presented how a bulk 200µm thick PMN-PT poled in [001] crystalline direction can be used for a MOEMS micro-mirror actuator by capturing its behavior through FEM simulations. A contribution of the paper is the definition of laser beam maximum usable diameter in regards to the size of the actuator, while achieving a minimum 325 nm required actuation. Another contribution is showing the direct influence of the clamping interface over the displacement of large micro-actuators.

Fig. 1 .

 1 Fig.1. Main components of the RF-MoB[START_REF] Bargiel | Towards micro-assembly of hybrid MOEMS components on a reconfigurable silicon free-space micro-optical bench[END_REF]

Fig. 3 .

 3 Fig. 3. Actuation in respect to the vertical support

Fig. 4 .

 4 Fig. 4. Toppling of the silicon support as a result of a too thick actuator. The thickness (h) has been exagerated.

  . The values for d31 and d33 were found experimentally by measuring multiple 200µm thick PMN-PT [001] actuators.

Fig. 6 .

 6 Fig. 6. Actuator free surface shape and variables of interest for an applied voltage of n V.

Fig. 7 .

 7 Fig. 7. Displacement curves for the selected size actuators (bottom graph) and the variation of the diameter of an usable laser beam (top graph)

Fig. 8 .

 8 Fig. 8. Key steps in the fabrication process of PMN-PT bulk micro-actuators: a) soldering; b) saw dicing; c) wire bonding

Fig. 9 .

 9 Fig. 9. Comparison between measured displacement and FEM simulation for PMN-PT actuators at 400V

ACKNOWLEDGMENT

  These works were partly supported under the National Projects UEFISCDI PN-II-RU-TE-2011-3-0299 (ADMAN), the ANR-11-EMMA-006 (MYMESYS) and the Franche-Comte REGION. We acknowledge the Labex ACTION project (contract ANR-11-LABX-01-01) and the French RENATECH network through its FEMTO-ST technological facility.

TABLE I .

 I VALUES OF PMN-PT [001] SPECIFIC COEFFICIENTS

		Constant	Unit	Value	Source
	s E	11		69.0
	s E	12		-11.1
	s E s E	13 33	x 10 -12 m 2 /N	-55.7 119.6	[16]
	s E	44		14.6
	s E	66		15.2
	d15		146
	d31 d33	x 10 -12 C/N	-980 2520	measured
	ε T 11 / ε0 ε T 33 / ε0	•	1600 8200	[16]