Alessandra Frabetti
email: frabetti@math.univ-lyon1.fr

Dominique Manchon
email: manchon@math.univ-bpclermont.fr

Five interpretations of Faà di Bruno's formula

Keywords: 2010 Mathematics Subject Classification: 16T05, 05E15, 20G15, 22E65, 81R10 Proalgebraic groups, Hopf algebras, Operads

In these lectures we present five interpretations of the Faà di Bruno formula which computes the n-th derivative of the composition of two functions of one variable: in terms of groups, Lie algebras and Hopf algebras, in combinatorics and within operads.

Introduction

In these lectures we present five interpretations of the Faà di Bruno formula which computes the n-th derivative of the composition of two functions of one variable.

(1) This formula tells explicitly how to compute the composition law in the group of formal diffeomorphisms in one variable. It is therefore related to the Lagrange inversion formula, which computes the inverse of a formal diffeomorphism in this group.

(2) In terms of Hopf algebras, it gives the coproduct of the so-called Faà di Bruno Hopf algebra, which can be seen as the coordinate ring of the previous group. It is one of the renormalization Hopf algebras which appeared recently in quantum field theory, and being related to the composition of formal series it is expected to appear, in its one-variable or several-variables form, in any perturbative theory. The Faà di Bruno Hopf algebra allows a non-commutative lift, but unlike what happens for the group of invertible formal series endowed with the product law, this non-commutative Hopf algebra does not represent a pro-algebraic group as a functor on non-commutative associative algebras. Its nature is then still an open question.

(3) The Lie algebra of the formal diffeomorphisms group is a well-known subalgebra of the Witt (and therefore also of the Virasoro) Lie algebra: the Faà di Bruno formula is therefore related to the well-known Lie bracket on these Lie algebras. The Faà di Bruno Hopf algebra is obtained from the Lie algebra of the formal diffeomorphisms group by considering the graded dual of its envoloping algebra (Cartier-Milnor-Moore correspondence).

(4) In combinatorics, the Faà di Bruno Hopf algebra is an important example of incidence Hopf algebra [START_REF] Schmitt | Incidence Hopf algebras[END_REF].

It is also a right-sided combinatorial Hopf algebra [START_REF] Loday | Combinatorial Hopf algebras[END_REF], and therefore its associated Lie bracket is the commutator of a brace product. It would be interesting to extend this brace product to the Witt algebra, which is the Lie algebra of vector fields on the circle.

(5) Finally, an interpretation of the Faà di Bruno formula in operadic terms is also possible. We recall in Section ?? the definition of a prounipotent group (and its corresponding pronilpotent Lie algebra) associated to a large class of linear operad [START_REF] Chapoton | Rooted trees and exponential-likes series[END_REF][START_REF] Van Der Laan | Operads and the Hopf algebras of renormalization[END_REF], the group law being related to the operadic composition.

Then, the group of formal diffeomorphisms (hence the Faà di Bruno formula) is the group associated to the operad Assoc governing associative algebras.

2 Faà di Bruno's formula

Francesco Faà di Bruno

The "Cavaliere" Francesco Faà di Bruno was born on March 9, 1825, in Alessandria (Italy), and was the youngest of twelve children. He died on March 27, 1888, in Torino (Italy). He joined the Military Academy of Torino at the age of 15, took part in the first Italian independence war in 1848, and then went to Paris for two years, during which he studied mathematics with Augustin-Louis Cauchy and with the astronomer Urbain Jean Joseph Le Verrier. Back in Torino, he left the army in 1853. He gave mathematics lectures at Torino University and at the Military Academy, and was appointed Professor in 1876.

Besides his official teaching and research job, he carried out a lot of scientific and human activities such as mechanics (he invented, among other things, an electric alarm clock for his blind sister), music, and, above all, social and philanthropic activities inspired by his Christian faith. He became a catholic priest in 1876, and was beatified by John-Paul II in 1988 for his courageous fight against the hard living conditions of female workers in Torino in the 19th century. The interested reader can consult the biography by L. Giacardi [START_REF] Giacardi | Ricerca scientifica, insegnamento e divulgazione, Deputazione subalpina di storia patria[END_REF] (in Italian).

Faà di Bruno's and Lagrange's formulae

Let us consider the set of smooth functions in one variable, endowed with the composition. If f and g are smooth functions of t, their composition is the smooth function f • g defined by (f • g)(t) = f g(t) . The Faà di Bruno formula tells how to compute the n-th derivative of the composite function f • g in terms of the derivatives of f and g. This famous formula was published by F. Faà di Bruno in the dense two-page paper "Sullo sviluppo delle funzioni" in 1855 [START_REF] Di | Sullo sviluppo delle funzioni[END_REF], and says that

d n dt n f g(t) = n m=1 n! k 1 !k 2 ! • • • k n ! f (m) g(t) g ′ (t) 1! k1 g ′′ (t) 2! k2 • • • g (n) (t) n! kn , (2.1)
where the second sum is taken over the non-negative integers k 1 , ..., k n such that

k 1 + k 2 + • • • + k n = m and k 1 + 2k 2 + • • • + nk n = n.
For instance, for n = 3, there are three possible sequences of such numbers: (k 1 , k 2 , k 3 ) = (0, 0, 1), (1, 1, 0) and (3, 0, 0). Then

d 3 dt 3 f g(t) = 3! 1! f ′ g(t) g ′′′ (t) 3! + 3! 1! f ′′ g(t) g ′ (t) 1! g ′′ (t) 2! + 3! 3! f ′′′ g(t)
g ′ (t) 3 (1!) 3 = f ′ g(t) g ′′′ (t) + 3f ′′ g(t) g ′ (t)g ′′ (t) + f ′′′ g(t) g ′ (t) 3 .

The most direct approach at this stage is to prove (2.1) directly by induction on n. Although it does not show particular difficulties, it is rather cumbersome. A very elegant alternative proof of (2.1) can be found in [START_REF] Frenkel | Vertex operator algebras and the Monster Pure and Appl[END_REF] (Proposition 8.3.4 therein), which heuristically goes as follows: we can extend any smooth function f to a smooth functional f from R [[y]] to R [[y]] by Taylor expansion:

f   k≥0 t k y k   = f   t 0 + k≥1 t k y k   := n≥0 k≥1 t k y k n n! ∂ n f (t 0 ).
Functionals like T → f (T ) can be seen as smooth functions depending on the infinite set of variables {t 0 , t 1 , t 2 , . . .

f • g = f • g, (2.2)
e y∂0 ( f • g)(t 0 ) = f • (e y∂0 g)(t 0 ) = f • g(t 0 + y) (2.3)
together yield:

e y∂0 ( f • g)(t 0 ) = f g(t 0 + y) = f   g(t 0 ) + k≥1 g (k) (t 0 ) k! y k   = e k≥1 g (k) (t 0 ) k! y k d dt 0 f g(t 0 ) . (2.4)
Formula (2.1) is then obtained by taking n! times the coefficient of y n in (2.4) above. Formula (2.4) is valid in greater generality, replacing ∂ 0 with any derivation X, with g (k) now standing for X k (g).

In order to make the proof above completely rigorous, we have to prove properties (2.2) and (2.3). A proof of these can be found in [START_REF] Frenkel | Vertex operator algebras and the Monster Pure and Appl[END_REF], based uniquely on formal-variable calculus (see [38, Sections 2.1, 2.2, 8.1-8.3]). One far-reaching application of this formal-variable calculus is the associativity principle for lattice vertex operators ( [START_REF] Frenkel | Vertex operator algebras and the Monster Pure and Appl[END_REF], Equation (8.4.32), Theorem 8.4.2, Theorem 8.8.9 and Proposition 8.10.5). We won't go further into this direction, referring the interested reader to [START_REF] Frenkel | Vertex operator algebras and the Monster Pure and Appl[END_REF][START_REF] Lepowsky | Introduction to vertex operator algebras and their representations[END_REF] for an introduction to the theory of vertex operator algebras. See also [START_REF] Kac | Vertex algebras for beginners[END_REF] for a different approach to this vast topic.

Our interpretation of the formal variable argument alluded to above is the following: for any Taylor expansion functional F = f as above, where f : R → R is a smooth function, and for any S, T ∈ R[[y]] we have: F (T + yS) = e yS∂0 F (T ).

(2.5)

The case T = t 0 ∈ R is a simple rephrasing of the definition, and the case for general T follows easily. Taking the linear part with respect to S in (2.5) successively for S = 1, y, y 2 , . . ., we get an explicit expression for the differential DF of F at T in terms of DF (T )[∂ 0 ]. Namely, for any k ≥ 1:

DF (T )[∂ k ] = y k DF (T )[∂ 0 ]. (2.6)
We can identify R[[y]] with its tangent space at each point T , via ∂ k ≃ y k . We have then a coordinate-free formulation of (2. Writing down the Taylor formula for the one-variable function h → F (T + hyS) we see that (2.6) implies (2.5).

Hence any F verifying (2.6) can be written as F = f , with f (t 0 ) = F (t 0 ) for any t 0 ∈ R. Now consider two functionals F = f and G = g. We claim that F • G verifies (2.6): indeed,

D(F • G)(T )(∂ k ) = DF G(T ) • DG(T )[∂ k ] = DF G(T ) • y k DG(T )[∂ 0 ] = y k DF G(T ) • DG(T )[∂ 0 ] = y k D(F • G)(T )[∂ 0 ].
Hence there exists h ∈ C ∞ (R) such that F • G = h, and evaluating it at t 0 ∈ R yields h = f • g, which proves (2.2). Property (2.3) follows immediately:

f • e y∂0 g(t 0 ) = f • e ∂1 g(t 0 ) = f • g(t 0 + y) = e ∂1 ( f • g)(t 0 ) = e y∂0 ( f • g)(t 0 ).
Surprisingly enough, F. Faà di Bruno wrote this formula almost a century after a similar one was established: the equally famous Lagrange inversion formula of 1770 [START_REF] Lagrange | Nouvelle méthode pour résoudre les équations littérales par le moyen des séries[END_REF], which computes the compositional inverse of a smooth function. If u = f (t) and t = g(u) are two smooth functions, inverse to each other, with f (0) = g(0) = 0 and f ′ (0) = 0, then Lagrange's inversion formula says that, for u in a neighborhood of zero,

g(u) = N n=1 1 n! d n-1 dt n-1 f (t) t -n t=0 u n + O(u N +1 ) (2.9)
for any N ≥ 0. For instance, for u = f (t) = t e t , this formula allows us to compute t as

t = g(u) = ∞ n=1 (-1) n-1 n n-1 n! u n , (2.10)
because

d n-1 dt n-1 f (t) t -n t=0 = d n-1 (e -nt ) dt n-1 t=0 = (-n) n-1 .
The series (2.10) defines Lambert's W-function on its domain of convergence, with radius of convergence equal to 1/e (see e.g. [START_REF] Titchmarsh | Theory of Functions[END_REF]). Similarly to the logarithm, this function admits a multivalued analytic extension to the whole complex plane with 1/e removed.

In the two-page paper [START_REF] Di | Sullo sviluppo delle funzioni[END_REF], Faà di Bruno also expresses d n dt n f g(t) as the determinant of the following n × n matrix:

                 f g ′ (n -1)f g ′′ n-1 2 f g ′′′ n-1 3 f g (4) • • • n-1 n-3 f g (n-2) (n -1)f g (n-1) f g (n) -1 f g ′ (n -2)f g ′′ n-2 2 f g ′′′ • • • n-2 n-4 f g (n-3) (n -2)f g (n-2) f g (n-1) 0 -1 f g ′ (n -3)f g ′′ • • • n-3 n-5 f g (n-4) (n -3)f g (n-3) f g (n-2) . . . . . . . . . . . . • • • . . . . . . . . . 0 0 0 0 • • • -1 f g ′ f g ′′ 0 0 0 0 • • • 0 -1 f g ′                 
Unlike the Faà di Bruno formula (2.1), this beautiful matrix formula seemingly did not get any echo among mathematicians, nor any further development.

Some points of history

It has been pointed out that Formula (2.1) was certainly known before Faà di Bruno's paper [START_REF] Di | Sullo sviluppo delle funzioni[END_REF]: quoting W. P. Johnson [START_REF] Johnson | The curious history of Faà di Bruno's formula[END_REF], several formulas of the same type were established in the middle of the 19th century, by Hoppe (1845), Meyer (1847), J.F.C. Tiburce Abadie alias T.A. (1850) and Scott (1861). Moreover, as highlighted by A. D. D. Craik [START_REF] Craik | Prehistory of Faà di Bruno's formula[END_REF], formula (2.1) appears nearly as such, as early as 1800, in the remarkable book of Louis François Antoine Arbogast (1759-1803), professor of Mathematics in Strasbourg [1, "Remarques", pp. [START_REF] Gelfand | Noncommutative symmetric functions[END_REF][START_REF] Giacardi | Ricerca scientifica, insegnamento e divulgazione, Deputazione subalpina di storia patria[END_REF]. This work on differential calculus for composite functions inspired in turn several French and British mathematicians of the first half of the 19th century, e.g. [START_REF] Knight | On the expansion of any functions of multinomials[END_REF][START_REF] Lacroix | Traité du calcul différentiel et du calcul intégral[END_REF]. To sum up, although we won't change a well-established terminology, let us cite the following sentence from the conclusion of Craik's historical survey [START_REF] Craik | Prehistory of Faà di Bruno's formula[END_REF]:

"Faà di Bruno's formula" was first stated by Arbogast in 1800, and it might as appropriately be named after one of the ten or more authors who obtained versions of it before Faà di Bruno. Only the determinantal formulation of it ought to be called "Faà di Bruno's formula".

In the middle of the 20th century the Faà di Bruno formula is enriched with a combinatorial interpretation. In 1946, J. Riordan recognizes the Bell polynomials [START_REF] Bell | Exponential polynomials[END_REF]:

B n,m x 1 , x 2 , ..., x l ) = k 1 +k 2 +•••+k l =m, k 1 +2k 2 +•••+lk l =n n! k 1 ! • • • k l ! x 1 1! k1 • • • x l l! k l , l = n -m + 1
and rewrites Faà di Bruno's formula as [START_REF] Riordan | Derivatives of composite functions[END_REF]:

d n dt n f g(t) = n m=1 f (m) g(t) B n,m g ′ (t), g ′′ (t), . . . , g (n-m+1) (t) . (2.11)
In 1965, R. Frucht and G-C. Rota [START_REF] Frucht | Polinomios de Bell y particiones de conjuntos finitos[END_REF] propose a purely combinatorial formulation of Faà di Bruno's formula:

d n dt n f g(t) = n m=1 f (m) g(t) g ′ (t) k1 g ′′ (t) k2 • • • g (n) (t) kn ,
where the second sum is taken over the partitions of {1, ..., n} with m blocks having k i blocks with i elements.

For instance, for n = 3, there are 5 partitions, {1, 2, 3}, {1}{2, 3}, {2}{1, 3}, {3}{1, 2} and {1}{2}{3}:

• {1, 2, 3} has a single block with 3 elements, therefore to this partition corresponds the sequence (k 1 , k 2 , k 3 ) = (0, 0, 1);

• {1}{2, 3}, {2}{1, 3} and {3}{1, 2} have two blocks, one with 1 element and the other one with 2, therefore there are three sequences (k 1 , k 2 , k 3 ) = (1, 1, 0);

• {1}{2}{3} has three blocks with 1 element each, therefore there is a corresponding sequence (k 1 , k 2 , k 3 ) = (3, 0, 0).

The number of resulting sequences matches with the coefficient in Faà di Bruno's formula. The proof of the Frucht-Rota formula starting from Riordan's formula resides in the following combinatorial interpretation of the Bell polynomials: the coefficient of

x j1 1 • • • x j l l in B n,m (x 1 , . . . x l ) (with l = n -m + 1
) is equal to the number of partitions of a set of cardinality n with j r blocks of size r, r ∈ {1, . . . , l} (and therefore m blocks altogether).

Group interpretation

Formal diffeomorphisms

The composition of functions of one variable is an associative operation, for which the identity id(t) = t is the unit. Therefore the set of smooth functions which have a compositional inverse forms a group, called the group of smooth diffeomorphisms on the real line, and denoted by Diff(R). Groups of diffeomorphisms on a manifold are infinite dimensional groups, not locally compact, with many connected components classified by the mapping class group. Even for the simplest ones, like Diff(R) or Diff(S 1 ), very little is known.

Up to composition by a translation, a diffeomorphism on the real line fixes the origin. Up to a scalar factor, one can also assume that a diffeomorphism is tangent to the identity at the fixed point. In other words, the group of diffeomorphisms of the real line is the semi-direct product of the group of diffeomorphisms tangent to the identity by the group of affine transformations.

Thinking in terms of Taylor expansions, we will rather consider the group of formal diffeomorphisms tangent to the identity:

G dif (K) = f (t) = f n t n ∈ K[[t]], f 0 = 0 and f 1 = 1 , (3.1)
whose definition makes sense for any field K of characteristic zero. Faà di Bruno's formula then expresses the n-th coefficient of the series f • g in terms of the coefficients of f and g:

(f • g) n = 1 n! (f • g) (n) (0) = n m=1 m! k 1 !k 2 ! • • • k n ! f m g k1 1 • • • g kn n , (3.2)
where the second sum runs over n-uples (k 1 , . . . , k n ) of non-negative integers such that

k 1 + k 2 + • • • + k n = m and k 1 + 2k 2 + • • • + nk n = n.
In terms of Bell's polynomial, this coefficient becomes:

(f • g) n = n m=1 m! n! f m B n,m (g 1 , 2!g 2 , ..., (n -m + 1)!g n-m+1
).

(3.3) Formula (3.2) can be directly checked by computing the coefficient of t n in the composition of the two formal series:

(f • g)(t) = m≥1 f m k≥1 g k t k m ,
expanding each power by means of the multinomial formula. The Faà di Bruno formula (2.1) is then directly derived from (3.2).

This group admits finite dimensional representations, none of which is faithful. Its smallest faithful representation is infinite dimensional, and presents G dif (K) as the group of infinite matrices of the form

M (g) =                  g 1 g 2 g 3 g 4 g 5 • • • 0 g 1 2g 2 g 2 2 + 2g 3 2g 4 + 2g 2 g 3 • • • 0 0 g 1 3g 2 3g 3 + 3g 2 2 • • • 0 0 0 g 1 4g 2 • • • 0 0 0 0 g 1 • • • . . . • • • . . .                 
, with g 1 = 1 here. In view of formula (3.3), the coefficients (M (g) ij ) i≤j are defined as:

M (g) ij = j! i! B i,j g 1 , 2!g 2 , . . . , (i -j + 1)!g i-j+1 .
4 Hopf algebra interpretation

Hopf algebras

We give here a brief account of the subject. A standard reference on Hopf algebras is Sweedler's monograph [START_REF] Sweedler | Hopf algebras[END_REF]. An associative unital algebra, which we will abbreviate as algebra (in the symmetric monoidal category of vector spaces over a field K, the morphisms being linear maps), is a K-vector space A together with:

• a multiplication m : A ⊗ A -→ A, (a, b) → m(a, b) = a • b such that m(m ⊗ id) = m(id ⊗ m), i.e. (a • b) • c = a • (b • c) for any a, b ∈ A;
• a unit i : K ֒→ A such that i(ts) = i(t) • i(s) for any s, t ∈ K and such that, if we set 1

A = i(1 K ), we have a • 1 A = a = 1 A • a for any a ∈ A.
A (coassociative counital) coalgebra is a K-vector space C together with:

• a comultiplication (or coproduct) ∆ :

C -→ C ⊗ C, c → ∆(c) = c (1) ⊗ c (2) such that (∆ ⊗ id)∆ = (id ⊗ ∆)∆. • a counit ε : C -→ K such that (ε ⊗ I)∆ = (I ⊗ ε)∆ = Id C .
For example, if C is any coalgebra with comultiplication ∆ and counit ε, its linear dual A = C * is an algebra with product m = ∆ * and unit i = ε * . Similarly, if A is a finite-dimensional algebra with product m and unit i, then

C = A * = Hom K (A, K) is a coalgebra with comultiplication ∆ = m * : A * -→ A * ⊗ A * ∼ = (A ⊗ A) * given by ∆(f )(a ⊗ b) = f (a • b), and counit ε = i * : A * -→ K given by ε(f ) = f (1 A ).
A Hopf algebra is a K-vector space H which is both an algebra and a coalgebra, such that:

• The comultiplication ∆ and the counit ε are algebra morphisms, i.e:

∆(a • b) = ∆(a) • ∆(b), ∆(1) = 1 ⊗ 1 ε(a • b) = ε(a) • ε(b), ε(1) = 1,
where the product on H ⊗ H is given by (a

1 ⊗ a 2 ) • (b 1 ⊗ b 2 ) = (a 1 • b 1 ) ⊗ (a 2 • b 2 ) for any a 1 , a 2 , b 1 , b 2 ∈ H.
• There is a linear map S : H -→ H, called the antipode, such that m(S ⊗ id)∆ = iε = m(id ⊗ S)∆.

• The antipode is both an antimorphism of algebras and an antimorphism of coalgebras, i.e., for any a, b ∈ H, we have

S(a • b) = S(b) • S(a), S(1 H ) = 1 H , ∆(S(a)) = (S ⊗ S)∆ op (a), ε(S(a)) = ε(a),
where

∆ op = τ • ∆, with τ (u ⊗ v) = v ⊗ u.
The dual A * of any finite-dimensional Hopf algebra (A, m, i, ∆, ε, S) is also a Hopf algebra, with mutiplication ∆ * , comultiplication m * , unit ε * , counit i * and antipode S * . Let us give some classical examples of Hopf algebras:

(1) The universal enveloping algebra U (g) of a Lie algebra g. By definition, U (g) = T (g)/J is the quotient of the free associative algebra on the vector space g by the two-sided ideal J generated by {x ⊗ yy ⊗ x -[x, y], x, y ∈ g}. The comultiplication, the counit and the antipode are the algebra morphisms (antimorphism for the antipode) given on the generators x ∈ g by

∆(x) = x ⊗ 1 + 1 ⊗ x, ε(x) = 0, S(x) = -x.
The elements of g are said to be primitive in the Hopf algebra, because of the special form the comultiplication∆ takes on them. This Hopf algebra is cocommutative, i.e. ∆(u) = ∆ op (u) for any u ∈ U (g).

(2) The group algebra KG of a finite group G. By definition, KG is the vector space freely generated by the elements of G, with multiplication bilinearly induced from the group law. The comultiplication, the counit and the antipode are the algebra morphisms (antimorphism for the antipode) given on the generators x ∈ G by

∆(x) = x ⊗ x, ε(x) = δ x,1G , S(x) = x -1 .
The elements of G are said to be group-like in the Hopf algebra, because of the special form the ∆ takes on them. This Hopf algebra is also cocommutative.

(3) The algebra of representative functions R[G] of a group G. By definition, R[G] is the algebra generated by the matrix elements of finite-dimensional representations of G. The remarkable property R [START_REF] Cartier | A primer of Hopf algebras[END_REF]Lemma 3.1.1]) allows us to define the coproduct of a function (of one variable) as being a function of two variables. Explicitly, the coproduct, the counit and the antipode of any representative function f on G are defined as follows, for any x, y ∈ G:

[G] ⊗ R[G] ∼ = R[G × G] (see
∆(f )(x, y) = f (xy), ε(f ) = f (1 G ), Sf (x) = f (x -1 ).
This Hopf algebra is commutative and is also called the coordinate Hopf algebra of the group G.

If G is a finite group, any function on G is representative, and the Hopf algebra R[G] is dual to the Hopf algebra KG. If G is a compact Lie group over k = R, "almost all" functions on G are representative, in the sense that there is a nondegenerate pairing •, • between R[G] and the enveloping algebra U (g), where g is the Lie algebra of G, such that δ(f ), u ⊗ v = f, uv and f ⊗ g, ∆u = f g, u for any f, g ∈ R[G] and any u, v ∈ U (g). The pairing is given by f, u := u.f (e), where u acts on f as a (left-invariant) differential operator, and where e is the unit of the group [17, 3.3 and 3.4].

Affine group schemes and proalgebraic groups

Let H be a commutative Hopf algebra and A a commutative unital algebra over some field K. Then, the vector space L(H, A) of K-linear maps from H to A inherits a canonical unital algebra structure. The multiplication is given by the convolution product, defined, for any two α, β ∈ L(H, A) as

α * β := m A • (α ⊗ β) • ∆ H .
The convolution unit is the linear map e A := i A • ε H . The vector space L(H, A) is often huge and not easy to handle. However it contains a subgroup which is, roughly speaking, equivalent to H. In fact, let CAlg be the category of commutative and unital associative K-algebras and consider the subset

G H (A) := Hom CAlg (H, A)
of A-valued characters of H, i.e. unital algebra morphisms from H to A. It can easily be checked that the convolution of two characters is still a character and that the convolution inverse of a character is still a character, because H and A are commutative algebras. The unit e A = i A • ε H of L(H, A) is also a character, and the inverse is given by ϕ → ϕ • S where S is the antipode. This construction is functorial, that is, for any unital commutative algebras A, B and for any commutative unital algebra morphism f : A → B, there is a group morphism G H (f ) :

G H (A) → G H (B).
An affine group scheme [START_REF] Waterhouse | Introduction to affine group schemes[END_REF] is a functor from the category of commutative algebras to the category of groups, representable by a commutative Hopf algebra H.

The group G H (A) has the particular property that H can then be regarded as an algebra of A-valued functions on the group, because any element h ∈ H can be seen as a function acting on α ∈ G H (A) as h(α) := α(h), and the fact that α is an algebra morphism, that is α(h • h ′ ) = α(h) • α(h ′ ) for any h, h ′ ∈ H, guarantees that we recover the usual definition of the product of functions, that is, (h

• h ′ )(α) = h(α) • h ′ (α)
. Moreover, the coproduct on H then coincides with the coproduct on functions induced by the group law in G H (A), that is, ∆(h)(α, β) = h(α * β), because of the definition of the convolution product in G H (A). Therefore, any group G H (A) behaves like a compact Lie group, and H like the algebra of its representative functions.

An algebraic group is by definition a functor G from the category of commutative algebras to the category of groups, having the property that there exists a commutative and finitely generated Hopf algebra H such that the group G(A) is isomorphic to G H (A) for any commutative unital algebra A. In other words, an algebraic group is a representable functor from the category of commutative algebras to the category of groups, such that the Hopf algebra which represents it is finitely generated. In this case, the algebra H is the algebra of A-valued polynomial functions on the group G H (A), and its generators can be seen as coordinate functions on the group. Classical examples of algebraic groups are the matrix groups GL n , SL n , SO n and SU n .

A pro-algebraic group is a projective limit of algebraic groups. It can be viewed as a representable functor from the category of commutative algebras to the category of groups, such that the Hopf algebra which represents it is an inductive limit of finitely generated Hopf algebras. Hence the group has infinitely many coordinate functions. As any commutative Hopf algebra is an inductive limit of finitely generated hopf algebras, any affine group scheme is pro-algebraic [START_REF] Waterhouse | Introduction to affine group schemes[END_REF]Theorem 3.3].

Finally, a pro-algebraic group G H is called prounipotent (see e.g. [START_REF] Cartier | A primer of Hopf algebras[END_REF]Paragraph 3.9]) if the Hopf algebra H is connected, which means that there exists an increasing filtration of vector spaces

H 0 ⊂ • • • ⊂ H n ⊂ • • • with H = n≥0
H n , such that the vector space H 0 is one-dimensional, i.e. H 0 = K • 1 H , and such that the multiplication and the coproduct are of filtration degree zero, i.e. for any p, q ≥ 0 we have

H p • H q ⊂ H p+q and ∆(H n ) ⊂ p+q=n H p ⊗ H q .
It is well known that the antipode of a connected Hopf algebra "comes for free" by recursive relations (in other words, any connected filtered bialgebra is a Hopf algebra), and is also of filtration degree zero, i.e. S(H n ) ⊂ H n for any n ≥ 0 [START_REF] Figueroa | Faà di Bruno Hopf algebras[END_REF][START_REF] Manchon | Hopf algebras and renormalisation[END_REF].

4.2.1

The Hopf algebra of symmetric functions A basic example of a pro-algebraic group is the group G inv of invertible series in one variable with pointwise multiplication: for any commutative unital algebra A, the group G inv (A) is the set of formal series

f (t) = 1 A + n≥1 f n t n , f n ∈ A, endowed with the product (f g)(t) = f (t)g(t) = 1 A + n≥1 n k=0 f k g n-k t n ,
with the convention f 0 = g 0 = 1 A . Its representing Hopf algebra is the polynomial ring

H inv = K[x 1 , x 2 , x 3 . . .]
on infinitely many variables x n , n ≥ 1, which play the role of A-valued coordinate functions on each group G inv (A), that is,

x n : G inv (A) → A, f → x n (f ) := f n .
The coproduct and the counit on H inv are defined, for any f, g ∈ G inv (A), as

∆ inv (x n )(f, g) = x n (f g) and ε(x n ) = x n (1),
where the constant series 1(t) = 1 A is the unit in G inv (A), and can be easily computed as

∆ inv (x n ) = n p=0 x p ⊗ x n-p and ε(x n ) = δ n,0 ,
where we assume that x 0 = 1. The resulting bialgebra is graded, if we set the degree of a monomial

x d1 n1 • • • x d k n k ∈ H inv to be k i=1 n i d i ,
that is, if we require the generators x n to be graded, with degree |x n | = n. In degree zero there are only scalars, therefore H inv is connected and the antipode is automatically defined by the recursive formula

S(x n ) = - n-1 p=0 S(x p )x n-p .
Hence G inv is a pronilpotent group. The Hopf algebra H inv is both commutative and cocommutative, and coincides with the well-known Hopf algebra of symmetric functions.

The Faà di Bruno Hopf algebra

Another key example of a pro-algebraic group is the group G dif of formal diffeomorphisms tangent to the identity, and it is also prounipotent. Indeed, it is a functor: for any commutative unital algebra A, the group G dif (A) is the set of formal series with coefficients in A, of the form

f (t) = t + n≥2 f n t n ∈ tA[[t]],
equipped with the usual composition law. It is the projective limit of the algebraic groups

G dif (n) (A), for n ≥ 1, which are the image of G dif (A) in the quotient tA[[t]]/t n+1 A[[t]].
Furthermore, the functor G dif is representable: its representing Hopf algebra H is the Hopf algebra of A-valued polynomial functions on G dif (A), freely generated as a commutatve algebra by the functions

x n : G dif (A) → A, f → x n (f ) := f n+1 , for n ≥ 1.
The coproduct is induced by the composition of series:

∆(x n )(f ⊗ g) = x n (f • g) for any f, g ∈ G dif (A),
counit is induced by the unit id(t) = t of the group:

ε(x n ) = x n (id),
and antipode is induced by the composition-inversion of series:

S(x n ) = x n (f -1 ) for any f ∈ G dif (A). (4.1)
The Lagrange inversion formula (2.9) gives an explicit formula for S(x n ). Using eq. ( 3.2) we can explicitly compute the coproduct. Up to a flip between left and right terms in the tensor product H ⊗ H (caused by the fact tht we write composition of functions from right to left), this Hopf algebra coincides with the Faà di Bruno Hopf algebra

H FdB = K[x 1 , x 2 , x 3 , ...],
with coproduct and counit given, on the generators, by

∆ FdB (x n ) = n m=0 (m + 1)! (n + 1)! B n+1,m+1 (1, 2!x 1 , 3!x 2 , ..., (n -m + 1)!x n-m ) ⊗ x m = n m=0     k0+k1+•••+kn=m+1, k1+2k2+•••+nkn=n-m (m + 1)! k 0 !k 1 ! • • • k n ! x k1 1 • • • x kn n     ⊗ x m , (4.2)
ε(x n ) = δ n,0 ,
where we use the convention x 0 = 1, and where B denotes the Bell polynomial. The antipode can be found recursively, because H FdB is a graded and connected bialgebra, where the generators have degree |x n | = n, for n ≥ 0. The left-right flip of factors means that H FdB is in fact the representative Hopf algebra of the opposite pro-algebraic group (G dif ) op , with opposite composition law f • op g = g • f . For any commutative algebra A, the group G dif (A) can then be seen as the group of A-valued characters of H FdB with reversed convolution product:

any formal series f ∈ G dif (A) is identified with a linear map f : H FdB → A satisfying the properties f (1) = 1 A and f (xy) = f (x)f (y) for any x, y ∈ H FdB .
The composition of two series f, g ∈ G dif (A), then, coincides with their opposite convolution product, namely

f • g = m A • (g ⊗ f ) • ∆ FdB .
Detailed explanations can also be found in [START_REF] Figueroa | Combinatorial Hopf algebras in quantum field theory I[END_REF]Section II]. The Faà di Bruno Hopf algebra first appeared under this name in 1974 (P. Doubilet, [START_REF] Doubilet | A Hopf algebra arising from the lattice of partitions of a set[END_REF]), and in 1979 (S.A. Joni and G.-C. Rota, [START_REF] Joni | Coalgebras and bialgebras in combinatorics[END_REF]), as an example of a Hopf algebra structure obtained from the lattice of set partitions. We say more about such Hopf algebras in section 6. It is also worth mentioning that the Faà di Bruno Hopf algebra is a Hopf subalgebra of the Connes-Moscovici Hopf algebra, which is neither commutative nor cocommutative (see [23, Paragraph III] for a detailed account, see also [START_REF] Menous | Formulas for the Connes-Moscovici Hopf algebra[END_REF]). The Faà di Bruno Hopf algebra also plays a role in applied mathematics, e.g. in control theory [START_REF] Gray | A Faà di Bruno Hopf algebra for a group of Fliess operators with applications to feedback[END_REF].

Two more examples

4.4.1 The Hopf algebra of rooted trees [START_REF] Connes | Hopf Algebras, Renormalization and Noncommutative Geometry[END_REF][START_REF] Foissy | Les algèbres de Hopf des arbres enracinés décorés I,II[END_REF][START_REF] Manchon | Hopf algebras and renormalisation[END_REF] A rooted tree is a class of oriented (non planar) graphs with a finite number of vertices, among which one is distinguished and called the root, such that any vertex admits exactly one incoming edge, except the root which has no incoming edges. Any tree yields a poset structure on the set of its vertices: two vertices x and y verify x ≤ y if and only if there is a path from a root to y passing through x. Two graphs are equivalent (hence define the same rooted tree) if and only if the two underlying posets are isomorphic. Here is the list of rooted trees up to five vertices:

A rooted forest is a finite collection of rooted trees. The empty set is the forest with containing no trees, and is denoted by 1. The grafting operator B + takes any forest and returns the tree obtained by grafting all components onto a common root. In particular, B + (1) = .

Let T denote the set nonempty rooted trees and let H RT = K[T ] be the free commutative and unital algebra generated by the elements of T . We identify a product of trees with the forest consisting of these trees. Therefore the vector space underlying H RT is the linear span of rooted forests. This algebra is a graded and connected Hopf algebra, called the Hopf algebra of rooted trees, with the following structure. The grading is given by the number of vertices of trees. The coproduct on a rooted forest u (i.e. a product of rooted trees) is described as follows: the set V(u) of vertices of a forest u is endowed with the partial order defined by x ≤ y if and only if there is a path from a root to y passing through x. Any subset W of the set of vertices V(u) of u defines a subforest u | W of u in an obvious manner, i.e. by keeping the edges of u which link two elements of W . The poset structure is given by restriction of the partial order to W , and the minimal elements are the roots of the subforest. The coproduct is then defined by:

∆ RT (u) = V ∐W =V(u) W <V u | V ⊗ u | W . (4.3)
Here the notation W < V means that y < x for any vertex x in V and any vertex y in W such that x and y are comparable. Note that both ∅ < V and V < ∅. Such a couple (V, W ) is also called an admissible cut, with crown (or pruning) u | V and trunk u | W . We have for example:

∆ RT = ⊗ 1 + 1 ⊗ + ⊗ ∆ RT = ⊗ 1 + 1 ⊗ + 2 ⊗ + ⊗ .
The counit is ε(1) = 1 and ε(u) = 0 for any non-empty forest u. The coassociativity of the coproduct is easily checked using an iterated formula for the restricted coproduct

∆ RT (u) = ∆ RT (u) -u ⊗ 1 -1 ⊗ u = V ∐W =V(u) W <V, V,W =∅ u | V ⊗ u | W ,
where the restriction that V and W are nonempty means that V and W give rise to an ordered partition of V(u) into two blocks. In fact, the iterated restricted coproduct writes in terms of ordered partitions of V(u) into n blocks:

∆ n-1 RT (u) = V 1 ∐•••∐Vn =V(u) Vn <•••<V 1 , V j =∅ u | V1 ⊗ • • • ⊗ u | Vn ,
and we get the full iterated coproduct ∆ n-1 RT (u) by allowing empty blocks in the formula above. Note that the relation < on subsets of vertices is not transitive. The notation

V n < • • • < V 1 is to be understood as V i < V j for any i > j, with i, j ∈ {1, . . . , n}.
This Hopf algebra first appeared in the work of A. Dür in 1986 [START_REF] Dür | Möbius functions, incidence algebras and power series representations[END_REF], as an incidence Hopf algebra (see section 6). It has been rediscovered and intensively studied by D. Kreimer in 1998 [START_REF] Kreimer | On the Hopf algebra structure of perturbative quantum field theories[END_REF], as the Hopf algebra describing the combinatorial part of the BPHZ renormalization procedure of Feynman graphs in a scalar ϕ 3 quantum field theory. D. Kreimer and A. Connes also proved in [START_REF] Connes | Hopf Algebras, Renormalization and Noncommutative Geometry[END_REF] that the operator B + satisfies the property

∆ RT B + (t 1 • • • t n ) = B + (t 1 • • • t n ) ⊗ 1 + (Id ⊗B + ) • ∆ RT (t 1 • • • t n ), (4.4)
for any t 1 , ..., t n ∈ T . This means that B + is a 1-cocycle in the Hochschild cohomology of H RT with values in H RT , and the couple (H RT , B + ) is then proved to be universal among commutative Hopf algebras endowed with a 1-cocycle.

The corresponding proalgebraic group G RT = Hom CAlg (H RT , -) first appeared in numerical analysis in the work of J. Butcher in 1963 [START_REF] Butcher | Coefficients for the study of Runge-Kutta integration processes[END_REF][START_REF] Butcher | An algebraic theory of integration methods[END_REF][START_REF] Brouder | On the trees of quantum fields[END_REF], where it was related to the change of Runge-Kutta methods for solving ordinary differential equations. It was then studied by F. Chapoton, who related this group to the pre-Lie operad [START_REF] Chapoton | Rooted trees and exponential-likes series[END_REF][START_REF] Chapoton | Pre-Lie algebras and the rooted trees operad[END_REF], see section ??.

For any commutative and unital algebra A, the group G RT (A) can be identified with the set of formal series expanded over rooted trees with coefficients in A, i.e. the set of maps form the set of nonempty rooted trees to A. These B-series are by now widely used in the study of approximate solutions of nonlinear differential equations1 [START_REF] Hairer | Geometric numerical integration: structure-preserving algorithms for ordinary differential equations[END_REF]. Such a map extends multiplicatively in a unique way to an A-valued character of H RT . There is an injective morphism of graded Hopf algebras

Ψ : H FdB ֒--→ H RT , (4.5)
as proven in Paragraph 5.2.2 below. This in turn induces a surjective group homomorphism

G RT (A) → → G dif (A).
for any commutative algebra A.

Feynman graphs and diffeographisms [22]

A Feynman graph is a (non planar) graph with a finite number of vertices, together with internal edges (with both ends attached to a vertex) and external edges (with one loose end, the other one being attached to a vertex). A graph is connected if any vertex can be reached from any other vertex by following internal edges. A connected graph is called one-particle irreducible (1PI) if it remains connected after removing any internal edge [START_REF] Connes | Renormalization in quantum field theory and the Riemann-Hilbert problem. I. The Hopf algebra structure of graphs and the main theorem[END_REF][START_REF] Manchon | Hopf algebras and renormalisation[END_REF].

In quantum field theory, Feynman graphs are a useful tool to describe some integrals, the amplitudes of the graphs, which compute the expectation value of the events schematically represented by the graphs. The Feynman rules, which recover the amplitude from a given graph, associate to loose ends (viewed as external vertices) some fixed points in the space-time manifold, to (internal) vertices some variable points to be integrated over the space-time manifold, and to edges the propagators of the field theory considered. After a Fourier transform, external edges are associated to fixed external momenta, and internal edges to variable momenta, which are to be integrated. A field theory is prescribed through a Lagrangian, which determines the types of Feynman graphs to be considered: the valence of the internal edges and the possible types of edges. The physically most interesting field theories give rise to Feynman graphs whose amplitude is a divergent integral, and which are therefore called divergent graphs. Physicists have developed some techniques, called renormalization, to extract a meaningful finite contribution from such graphs. A common step of any renormalization process consists in a purely combinatorial manipulation of graphs, in order to take care of possible divergent subgraphs. D. Kreimer proved in [START_REF] Kreimer | On the Hopf algebra structure of perturbative quantum field theories[END_REF] that this step can be efficiently described in terms of the Hopf algebra of rooted trees presented in section 4.4.1, where rooted trees encode the hierarchy of divergent subgraphs. A. Connes and D. Kreimer then proved in [START_REF] Connes | Hopf Algebras, Renormalization and Noncommutative Geometry[END_REF][START_REF] Connes | Renormalization in quantum field theory and the Riemann-Hilbert problem. I. The Hopf algebra structure of graphs and the main theorem[END_REF][START_REF] Connes | Renormalization in quantum field theory and the Riemann-Hilbert problem. II. The β-function, diffeomorphisms and the renormalization group[END_REF] that the renormalization Hopf algebra can be defined directly on Feynman graphs.

The so-called Connes-Kreimer Hopf algebra, or Hopf algebra of Feynman graphs, is the free commutative and unital algebra H FG = K[F ] generated by the set F of connected and 1PI graphs which are superficially divergent, i.e. graphs which are divergent even after having renormalized any divergent subgraph. For any given field theory, the superficial divergence of a Feynman graph can be stated as a combinatorial constraint, and implies, for instance, that the number of external legs does not exceed some critical number. The product of 1PI divergent graphs is given by their disjoint union. Hence H FG is the vector space generated by superficially divergent locally 1PI graphs, connected or not, including the empty graph. The coproduct on H FG is given on any generator Γ ∈ F by: ∆

(Γ) = 1 ⊗ Γ + Γ ⊗ 1 + ∅ γ Γ Γ/γ,
where the sum runs over the set of proper and non-empty subgraphs of Γ having connected components which are 1PI and superficial divergent. The contracted graph Γ/γ is obtained by shrinking each connected component of γ onto a point [START_REF] Connes | Renormalization in quantum field theory and the Riemann-Hilbert problem. I. The Hopf algebra structure of graphs and the main theorem[END_REF][START_REF] Manchon | Hopf algebras and renormalisation[END_REF]. Note that the condition which ensures that a contracted graph Γ/γ belongs to H FG coincides with the requirement that γ only has superficially divergent connected components [START_REF] Connes | Renormalization in quantum field theory and the Riemann-Hilbert problem. I. The Hopf algebra structure of graphs and the main theorem[END_REF][START_REF] Agarwala | The Geometry of Renormalization[END_REF].

The counit on H FG is given on any generator Γ ∈ F by ε(Γ) = 0, and the bialgebra thus obtained is graded by the loop number of the graphs2 , and connected. Therefore it is automatically a (commutative) Hopf algebra, with antipode defined recursively. The convolution group G FG = Hom CAlg (H FG , -) is another example of a prounipotent group, called the group of diffeographisms by Connes and Kreimer in [START_REF] Connes | Renormalization in quantum field theory and the Riemann-Hilbert problem. II. The β-function, diffeomorphisms and the renormalization group[END_REF]. This affine group scheme plays a key role in the description of the renormalization of quantum fields. Indeed, any splitting A = A -⊕ A + of the target algebra into two subalgebras (with 1 ∈ A + ) yields a Birkhoff decomposition:

G FG = G FG-• G FG+ ,
with G FG± = Hom CAlg (H FG , A ± ). For any ϕ = ϕ -1 -ϕ + ∈ G FG , the renormalized character is the component ϕ + , whereas the component ϕ -is the counterterm character [START_REF] Connes | Renormalization in quantum field theory and the Riemann-Hilbert problem. I. The Hopf algebra structure of graphs and the main theorem[END_REF]. The combinatorics underlying this renormalization process relies on a Rota-Baxter property for the projection A → → A -, and applies to any connected graded Hopf algebra in full generality (see [START_REF] Ebrahimi-Fard | Rota-Baxter Algebras in Renormalization of Perturbative Quantum Field Theory[END_REF][START_REF] Manchon | Hopf algebras and renormalisation[END_REF] and see [START_REF] Ebrahimi-Fard | Exponential renormalization[END_REF][START_REF] Ebrahimi-Fard | Exponential Renormalization II: Bogoliubov's R-operation and momentum subtraction schemes[END_REF] for a generalization outside the Rota-Baxter framework).

The Hopf algebra of Feynman graphs is naturally endowed with several operators analogous to the grafting operator B + defined on the Hopf algebra of rooted trees. In fact, for any primitive graph γ, i.e. such that ∆ FG (γ) = γ ⊗ 1 + 1 ⊗ γ, one can define an insertion operator δ → B γ (δ) by summing up all possibilities to insert γ inside δ, and taking into account some appropriate symmetry factors (see L. Foissy's notes in the present volume). The insertions are so chosen that, for the resulting graph Γ, the subgraph δ appears as the contracted graph Γ/γ. For scalar or fermionic field theories, each operator B γ satisfies the same cocycle property (4.4) as B + , namely:

∆ B γ (δ) = B γ (δ) ⊗ 1 + (Id ⊗B γ ) • ∆(δ). (4.6)
For gauge theories, equation (4.6) takes place in the quotient H FG of H FG by the ideal describing the Ward-Takahashi identities of the gauge theory [START_REF] Van Suijlekom | Multiplicative renormalization and Hopf algebras[END_REF]. Due to the universal property of the Hopf algebra H RT with the operator B + [START_REF] Foissy | Les algèbres de Hopf des arbres enracinés décorés I,II[END_REF], for any primitive graph γ ∈ H FG there is a unique graded Hopf algebra morphism

Φ γ : H RT -→ H FG resp. to H FG (4.7) such that Φ γ • B + = B γ • Φ γ . Composing Φ γ with the embedding Ψ : H FdB ֒--→ H RT , we get an injective Hopf algebra morphism Φ γ • Ψ : H FdB ֒--→ H FG resp. to H FG .
This embedding was first found by Connes and Kreimer in [START_REF] Connes | Renormalization in quantum field theory and the Riemann-Hilbert problem. II. The β-function, diffeomorphisms and the renormalization group[END_REF]. The reader will again find a more detailed exposition in L. Foissy's note in the present volume. See also [START_REF] Bellon | Renormalization group functions for the Wess-Zumino model: up to 200 loops through Hopf algebras[END_REF] for a concrete application of these Hopf algebra morphisms in quantum field theory. Finally, the map Φ γ • Ψ yields a surjective morphism from the group of diffeographisms (resp. a subgroup) to the group of formal diffeomorphisms: for any commutative and unital algebra A, there is a canonical projection of groups

G FG (A) → → G dif (A) resp. G FG (A) → → G dif (A) .

The non-commutative Faà di Bruno Hopf algebra

Many of the free commutative Hopf algebras related to the Faà di Bruno Hopf algebra admit a natural noncommutative analogue, which in general turns out to be simpler from a combinatorial and from an operadic point of view.

In [START_REF] Foissy | Les algèbres de Hopf des arbres enracinés décorés I,II[END_REF], L. Foissy introduced a non-commutative version of the Hopf algebra H RT based on planar rooted trees, and therefore denoted by H PRT , which has the remarkable property that it is self-dual. The set of generators of H PRT as a free noncommutative algebra (planar rooted trees) canonically projects itself onto the set of generators of H RT as a free commutative algebra (non-planar rooted trees).

In the case of the Faà di Bruno Hopf algebra, the generators are labeled by natural numbers, and it is also the case for the non-commutative lift described in [START_REF] Brouder | Non-commutative Hopf algebra of formal diffeomorphisms[END_REF]. This non-commutative Faà di Bruno Hopf algebra is defined as the free associative algebra on the same generators as H FdB , that is H nc FdB = K x 1 , x 2 , ... , with the usual counit ε(x n ) = δ n,0 , where x 0 = 1, and the coproduct lifted as

∆ nc FdB (x n ) = n m=0    k 0 +•••+km =n-m k i ≥0 x k0 • • • x km    ⊗ x m .
It is still a graded and connected bialgebra, and the recursive relation for the antipode yields the following non-commutative Lagrange formula (see (4.1) and remark therein), quite involved compared to its commutative counterpart (2.9):

S(x n ) = -x n - n-1 k=1 (-1) k n 1 +•••+n k+1 =n n i >0 λ(n 1 , ..., n k ) x n1 • • • x n k+1 ,
where

λ(n 1 , ..., n k ) = m 1 +•••+m k =k m 1 +•••+m h ≥h for h<k n 1 + 1 m 1 • • • n k + 1 m k .
It is then easy to check that H FdB coincides with the abelian quotient H nc FdB /[H nc FdB , H nc FdB ], and therefore that the surjective algebra morphism π : H nc FdB → → H FdB which identify the generators is a Hopf algebra morphism.

The commutative Hopf algebra H inv admits a similar non-commutative lift H nc inv = K x 1 , x 2 , ... , with exactly the same coproduct formula ∆ inv (x n ) = n p=0 x p ⊗ x n-p . The resulting non-commutative but still co-commutative Hopf algebra is well known under the name of Hopf algebra of non-commutative symmetric functions, the graded dual of which is the Hopf algebra of quasi-symmetric functions [START_REF] Gelfand | Noncommutative symmetric functions[END_REF].

Proalgebraic groups on non-commutative algebras

Proalgebraic groups on non-commutative unital algebras in fact do exist, and should be exhibited by means of free products of algebras. This well-established fact [START_REF] Berstein | On co-groups in the category of graded algebras[END_REF][START_REF] Voiculescu | Dual algebraic structures on operator algebras related to free products[END_REF][START_REF] Zhang | H-algebras[END_REF]] deserves some explanation, as it may be not so well-known to non-specialists. Although the functor G inv can be naturally extended to noncommutative algebras along these lines, there seem however to be no means to extend the functor G dif to non-commutative algebras in this framework: we come back to this point in Paragraph 4.7 below.

Cogroups [6]

The free product of associative algebras can be defined as the unique operation ⋆ between associative algebras such that for any two vector spaces V and W , there is a canonical algebra isomorphism

T (V ) ⋆ T (W ) ∼ = T (V ⊕ W )
between associated tensor algebras. For any unital K-algebras A and B, the free product A ⋆ B can explicitely be defined as the algebra A ⋆ B := T (A ⊕ B)/J, where A = A/K • 1 A and B = B/K • 1 B are the augmentation ideals, and where J is the ideal of the tensor algebra T (A ⊕ B) generated by {a ⊗ a ′aa ′ , a, a ′ ∈ A} and {b ⊗ b ′bb ′ , b, b ′ ∈ B}. Any element of A ⋆ B is represented by an element of T (A ⊕ B), which can be written as a finite sum of terms of the type:

x 1 ⊗ • • • ⊗ x r , (4.8)
where x j is in A if and only if x j+1 is in B for j = 1, . . . , r -1, and vice-versa. We write such a term

x 1 • • • x r .
The product of two elements in A ⋆ B is given by the concatenation of their representative elements in T (A⊕ B).

In particular, there are canonical algebra embeddings A ∼ = A ⋆ K ⊂ A ⋆ B and B ∼ = K ⋆ B ⊂ A ⋆ B, and therefore also an embedding of vector spaces

j : A ⊗ B ֒--→ A ⋆ B,
where j(A ⊗ B) contains exactely the terms

x 1 ⊗ x 2 ∈ A ⋆ B with x 1 ∈ A and x 2 ∈ B.
Note however that the map j is not an algebra morphism, because the multiplication in

A ⊗ B is (m A ⊗ m B ) • τ 23 , while the multiplication in A ⋆ B is the concatenation.
The free product is characterized by the following universal property: for any associative unital algebras A, B, C and for any unital algebra morphisms f : A → C and g : B → C, there is a unique algebra morphism f ⋆ g : A ⋆ B → C which extends both f and g. The algebra morphism f ⋆ g is defined by

f ⋆ g([x 1 ⊗ • • • ⊗ x r ]) := h(x 1 ) • • • h(x r ), where h : A ⊕ B → C is defined as h(x) = f (x) if x ∈ A, and as h(x) = g(x) if x ∈ B.
This implies that there exists also a canonical projection of vector spaces

π : A ⋆ B → → A ⊗ B,
which consists in "putting the elements of A on the left and the elements of B on the right", namely:

π([x 1 ⊗ • • • ⊗ x r ]) =      x 1 x 3 • • • ⊗ x 2 x 4 • • • if x 1 ∈ A, x 2 x 4 • • • ⊗ x 1 x 3 • • • if x 1 ∈ B.
It is easily checked that, contrarily to the embedding j, the projection π is an algebra morphism.

Finally, the free product ⋆ is a bifunctor: given two unital algebra morphisms f : A → A ′ and g : B → B ′ , there exists a straightforward algebra morphism f ⋆ g : A ⋆ B → A ′ ⋆ B ′ . The multiplication m A : A ⊗ A → A uniquely extends to an algebra morphism m A : A⋆A → A such that m A = m A •π. We also have m A = Id A ⋆ Id A , and for any unital algebra morphisms f : A → C and g : B → C we have:

f ⋆g = m C • (f ⋆ g).
A cogroup in the category of unital associative K-algebras [START_REF] Eckmann | Group-like structures in general categories I, II and III[END_REF][START_REF] Berstein | On co-groups in the category of graded algebras[END_REF][START_REF] Bergman | Co-groups and co-rings in categories of associative rings[END_REF], also called H-algebra in [START_REF] Zhang | H-algebras[END_REF], is a unital associative K-algebra H together with a "coproduct" ∆ : H → H ⋆ H, a "counit" ε : K → H and an "antipode" S : H → H such that:

(id ⋆ ∆) • ∆ = (∆ ⋆ id)∆ : H → H ⋆ H ⋆ H, (ε ⋆ id) • ∆ = (id ⋆ ε) • ∆ = id, m H • (S ⋆ id) • ∆ = m H • (id ⋆ S) • ∆ = i • ε.
A similar notion has been developed by D. Voiculescu under the name "dual group" in the context of operator algebras [START_REF] Voiculescu | Dual algebraic structures on operator algebras related to free products[END_REF]. The following proposition, which can be easily derived from the Yoneda lemma (see e.g. [70, Paragraph III.2]), is well-known to experts. However we give a pedestrian proof adapted to our context: Proposition 1. Let Sets and Alg stand for the category of sets and unital associative algebras respectively. Let H be a unital algebra and let G be the functor

Alg -→ Sets A -→ G(A) = Hom Alg (H, A).
Then G takes its values in the category of groups if and only if the representing object H is a cogroup in the category of unital K-algebras.

Proof. Suppose that H is a cogroup in the category of unital K-algebras, and consider any associative unital algebra A. Then we set g * h = m A • (g ⋆ h) • ∆ for any unital algebra morphisms g, h : H → A. The associativity of this product is obvious, as well as the fact that 1 A • ε is the unit. The fact that g * h is still an algebra morphism comes from the fact that m A , g ⋆ h and ∆ are. The inverse of any g is given by g • S, which proves that Hom Alg (H, A) is a group.

Conversely, if the functor G takes its values in the category of groupes and is representable as Hom Alg (H, -), consider the two embeddings j 1 , j 2 : H → H ⋆ H, which are algebra morphisms, obtained from the two obvious embeddings of H into T (H ⊕ H). Then j 1 ⋆ j 2 : H ⋆ H → H ⋆ H is manifestly equal to the identity. It is then easy to check that the "coproduct" ∆ is given by the product j 1 • j 2 in the group Hom Alg (H, H ⋆ H). The "counit" is the unit of the group Hom Alg (H, K), and the "antipode" is the inverse in the group Hom Alg (H, H).

Note that any cogroup H is also a Hopf algebra, by composing the "coproduct" ∆ on the left by the projection π : H ⋆ H → → H ⊗ H, thus getting a genuine coproduct on H. The converse is not true: if H is a Hopf algebra with coproduct ∆, the lift ∆ = j • ∆ : H → H ⋆ H is not necessary an algebra morphism, because j : H ⊗ H ֒--→ H ⋆ H is not. Note also that any cogroup in the category of associative unital algebras is a free algebra [6, Theorem 1.2] or [START_REF] Zhang | H-algebras[END_REF].

The cogroup of invertible series

One can note that the proalgebraic group G inv still makes sense on associative unital algebras which are not commutative: for any algebra A of this type, the pointwise multiplication of two formal series of the form f (t) = 1 A + n≥1 f n t n with coefficients f n ∈ A is still an associative operation, and gives rise to a group G inv (A) which is no longer abelian. One may then wonder about the existence of a functor which associates to any unital algebra A (commutative or not) a convolution group Hom Alg (H, A) represented by a non-commutative Hopf algebra H, which would reproduce the group G inv (A) for H = H nc inv , and which would give rise to a new group of formal diffeomorphisms for H = H nc FdB . Such a functor cannot exist, because if A is a non-commutative algebra, the convolution product of two elements in Hom Alg (H, A) has no reason to be an algebra morphism. In the next section we give an explanation of the existence of the non-abelian group G inv (A) for A non-commutative, but our argument does not justify the existence of the non-commutative Hopf algebra H nc FdB in terms of groups. We come back to this point in Paragraph 4.7 below.

For the non-commutative Hopf algebra H nc inv = K x 1 , x 2 , ... , the free product H nc inv ⋆ H nc inv can be described as the free algebra on two types of variables, one for each copy of H nc inv , that is,

H nc inv ⋆ H nc inv = K x 1 , y 1 , x 2 , y 2 ... . The coproduct ∆ * inv : H nc inv -→ H nc inv ⋆ H nc inv defined on generators as ∆ * inv (x n ) = n p=0 x p y n-p ∈ H nc inv ⊗ H nc inv ⊂ H nc inv ⋆ H nc inv ,
is obviously coassociative, and makes H nc inv into a cogroup. Its associated functor G inv = Hom Alg (H nc inv , -) : Alg -→ Groups then defines the proalgebraic group of invertible series with non-commutative coefficients, namely, for any non-commutative unital associative algebra A, the non-abelian group

G inv (A) = f (t) = f n t n | f 0 = 1 ⊂ A[[t]] with pointwise product (f g)(t) = f (t)

Lie algebra interpretation 5.1 Vector fields, Witt and Virasoro Lie algebras

The reader will find a comprehensive treatment of these infinite-dimensional Lie algebras and their representation theory in [START_REF] Kac | Bombay lectures on highest weight representations of infinite-dimensional Lie algebras[END_REF] or in [START_REF] Guin | On the Lie enveloping algebra of a pre-Lie algebra, J. of K-theory: K-theory and its applications to algebra[END_REF]. The Lie algebra Vect(S 1 ) of regular vector fields on the circle is, by definition, the Lie algebra of derivations of the ring of Laurent polynomials R[z, z -1 ]. It can be seen as the real vector space

Vect(S 1 ) = Span R e n = 1 2iπ e 2iπnt d dt , n ∈ Z ,
where z = e 2iπt . The Lie bracket is given by: [e m , e n ] = (nm) e n+m .

The same Lie algebra can be considered over any base field K, and in the case of a field of characteristic p > 0 it was first introduced by E. Witt in a Hamburg Seminar in 1939, and reported by H. Zassenhaus in [START_REF] Zassenhaus | Über Liesche Ringe mit Primzahlcharakteristik[END_REF], with generators restricted to 1 ≤ n ≤ p -2.

By extension, the complex Lie algebra Vect(S 1 ) C , which can be understood as the Lie algebra of polynomial complex functions on the circle, is now called the Witt Lie algebra and denoted by W(C). Its one-dimensional central extension is the so-called Virasoro Lie algebra, first found in positive characteristic by R. E. Block in 1966 [START_REF] Block | On the Mills-Seligman axioms for Lie algebras of classical type[END_REF], and then in characteristic zero by I.M. Gelfand and D.B. Fuks in 1968 [START_REF] Fuks | Cohomology of Lie algebras of vector fields on the circle[END_REF]. These two Lie algebras describe the infinitesimal conformal transformations in two real dimensions (with or without anomaly), and play a central role in conformal field theory and in string theory [START_REF] Guin | On the Lie enveloping algebra of a pre-Lie algebra, J. of K-theory: K-theory and its applications to algebra[END_REF]. Two-dimensional conformal field theory is deeply related to the theory of vertex operator algebras (see e.g. the introduction of [START_REF] Frenkel | Vertex operator algebras and the Monster Pure and Appl[END_REF]).

The Lie algebra of formal vector fields on a line was defined by E. Cartan as early as 1909 [START_REF] Cartan | Les groupes de transformations continus, infinis, simples[END_REF]:

W + (K) = Span K e n = t n+1 d dt , n ≥ -1 . 3
When K = C, W + (C) gives the vector fields on S 1 which extend holomorphically to the unit disk. In his book, Fuks considers as well the following Lie subalgebras of W + (K):

L k = Span K e n = t n+1 d dt , n ≥ k ,
satisfying the properties

W + (K) = L -1 ⊃ L 0 ⊃ L 1 ⊃ • • • , and [L m , L n ] ⊂ L m+n for m, n ≥ 0.
In particular, the Lie algebra L 1 is pronilpotent [START_REF] Cartier | A primer of Hopf algebras[END_REF]. We show in the next section that L 1 is the Lie algebra of the group of formal diffeomorphisms G dif (K).

Lie algebra of algebraic and proalgebraic groups

Let G H be a proalgebraic group represented by a commutative Hopf algebra H over a field K. For any commutative unital K-algebra A, an A-valued infinitesimal character of H, or A-valued derivation on H [START_REF] Connes | Hopf Algebras, Renormalization and Noncommutative Geometry[END_REF][START_REF] Manchon | Hopf algebras and renormalisation[END_REF], is a linear map α : H → A such that, for any x, y ∈ H, the following relation holds:

α(xy) = α(x)e A (y) + e A (x)α(y),
where e A = i A • ε. Since e A (1 H ) = 1 A , this implies that α(1 H ) = 0. Then, it is easily checked that the set g H (A) = Der (H, A) of A-valued derivations on H is a Lie algebra, with bracket given by [α, β] := α * ββ * α, for any α, β ∈ g H (A). Moreover, the map A → g H (A) is clearly a functor g H from the category of commutative unital algebras into the category of Lie algebras. If H is a finitely generated algebra (resp. inductive limit of finitely generated algebras), the functor g H is by definition the Lie algebra of the algebraic (resp. proalgebraic) group G H . Proposition 2. Let G H be a prounipotent group, with Lie algebra g H , and suppose that the base field K is of characteristic zero. For any commutative unital algebra A, the exponential map

exp : g H (A) -→ G H (A) α -→ exp(α) := e A + n≥1 α * n n!
is a bijection, and we have exp(α) * exp(β) = exp(α + β) if [α, β] = 0. The inverse of the exponential map is the logarithm, defined by

log : G H (A) -→ g H (A) ϕ = e A + γ -→ log(ϕ) = n≥1 (-1) n-1 γ * n n .
Proof. Let m be a positive integer. For any x ∈ H m we have:

∆(x) = x ⊗ 1 H + 1 H ⊗ x + (x)
x ′ ⊗ x ′′ , where x ′ , x" ∈ H m-1 . As a consequence, for any linear map α : H → A such that α(1 H ) = 0, we have α * n (x) = 0 for any n ≥ m + 1. This applies in particular when α is an infinitesimal character. Hence the exponential of α is well-defined, as the sum which defines it is locally finite. The same argument applies to the logarithm. The fact that the exponential of an infinitesimal character is a character is checked by direct inspection, as well as the last assertion. Finally let us consider any character ϕ ∈ G H (A). The powers ϕ * m are also characters for any positive integer m. Now let us define for any λ ∈ K:

ϕ * λ := exp λ log(ϕ) .
For any x, y ∈ H, the expression ϕ * λ (x)ϕ * λ (y)-ϕ * λ (xy) is polynomial in λ and vanishes at any positive integer, hence vanishes identically. It follows that ϕ * λ is a character for any λ ∈ K. Differentiating with respect to λ at λ = 0 immediately gives the infinitesimal character equation for log(ϕ). A standard direct computation then shows that the logarithm and the exponential are mutually inverse.

Suppose now that the proalgebraic group G H is represented by a graded Hopf algebra H = ⊕ n≥0 H n , such that each graded component H n is finite-dimensional. Then one can define the graded dual Hopf algebra

H * := n H *
n with the operations given in section 4.1. Since H is commutative, its dual H * is a cocommutative Hopf algebra. By the Cartier-Milnor-Moore theorem, then, H * is the universal enveloping algebra of the Lie algebra formed by its primitive elements,

Prim H * = α : H -→ K linear, m * (α) = α ⊗ ε + ε ⊗ α .
Applying the definition of m * one sees immediately that such primitive elements are K-valued infinitesimal characters on H, and that Prim H * is a Lie subalgebra of the Lie algebra g H (K). In fact, g H (K) is the completion of Prim H * .

5.2.1

Lie algebra for the Faà di Bruno Hopf algebra As we saw, the group of formal diffeomorphisms is a prounipotent group represented by the Faà di Bruno Hopf algebra H FdB = K[x 1 , x 2 , ...]. This algebra is the free commutative algebra (i.e. the symmetric algebra) on the vector space spanned by the graded variables x n , with degree |x n | = n. Therefore it is graded, and its graded dual space H * FdB is the universal enveloping algebra of a Lie algebra that we now describe.

The dual Hopf algebra H *

FdB is the cofree graded cocommutative coalgebra (the so-called symmetric coalgebra) on the vector space spanned by the dual elements of the variables x n , that we denote by e n . To be more precise, H * FdB is isomorphic, as a graded vector space, to the symmetric algebra S(V ) where V is the span of linear maps e n : H FdB -→ K such that e n (x m ) = δ nm . The grading is induced by the grading on V given by |e n | = -n.

Elements of V are clearly infinitesimal characters of H FdB , i.e. elements of g H FdB (K). The Hopf algebra structure on H * FdB is induced by that of H FdB : the free commutative product on H FdB gives the unshuffle coproduct [START_REF] Ree | Lie elements and the algebra associated with shuffles[END_REF] on H * FdB , defined by:

∆(e i1 • • • e i k ) = I∐J={1,...k} e I ⊗ e J ,
where I and J are complementary parts of {1, . . . , k} and e I (resp. e J ) stands for the symmetric product of e ij 's with j ∈ I (resp. j ∈ J). The Faà di Bruno coproduct on H FdB gives the (noncommutative) multiplication on H * FdB (of course different from the symmetric product we used just above). It is easy to check that the generators e n are the only primitive elements with respect to the unshuffle coproduct, therefore Prim H * FdB = Span K {e 1 , e 2 , ...}. On the other hand, the multiplication induced by ∆ FdB on H * FdB coincides with the convolution product when it is restricted to L(H, K). By direct computations (or see [START_REF] Brouder | Combinatorial Hopf algebras from renormalization[END_REF] about H nc FdB op ), we then obtain, for any p, q ∈ N -{0}:

[e p , e q ] := e p * e qe q * e p = (qp)e p+q .

(5.1)

This means that L 1 is the Lie algebra of the group G dif (K) op .

Finally note that the convolution product restricted to the generators of L 1 can be written as e p * e q = e p ✄ e q + ϕ, where ϕ is any element of L 1 which, seen as a linear map on H FdB , vanishes on the x n 's for any n ∈ N, and where we set e p ✄ e q := (q + 1)e p+q .

The binary operation ✄ is a left pre-Lie product [START_REF] Gerstenhaber | The cohomology structure of an ass-ociative ring[END_REF][START_REF] Vinberg | The theory of convex homogeneous cones[END_REF], which means that it satisfies the condition e p ✄ (e q ✄ e r ) -(e p ✄ e q ) ✄ e r = e q ✄ (e p ✄ e r ) -(e q ✄ e p ) ✄ e r , (5.2)

for any p, q, r > 0. Such products are discussed in section 6.2.2. Going further, there is even a family (✄ λ ) λ∈K of left pre-Lie products on L 1 , given by e p ✄ λ e q = (p + λ)e p+q , whose antisymmetrization gives back the Lie bracket 5.1. See L. Foissy's notes in the present volume for more details.

Lie algebra for the Hopf algebra of rooted trees

The graded dual H * RT of the Hopf algebra of rooted trees is called Grossman-Larson Hopf algebra, after the first authors who considered it [START_REF] Grossman | Hopf-algebraic structure of families of trees[END_REF]. Being a cocommutative Hopf algebra, it is the enveloping algebra of a Lie algebra that we now describe.

The Hopf algebra H RT is the free commutative algebra on the vector space spanned by rooted trees. It is a graded Hopf algebra, if we consider the trees to be graded by the number of their vertices. A basis of H RT is given by monomials of trees, i.e. forests (s). Denote by (δ s ) the dual basis in H * RT . The correspondence δ : s → δ s extends linearly to a unique vector space isomorphism from H RT onto H * RT . For any tree t, the corresponding δ t is a primitive element of H * RT . In particular, it is an infinitesimal character of H RT , i.e. an element of g H RT (K). The Lie algebra of the group G RT (K) is then the vector space

Lie(G RT (K)) = Span K {δ t , t ∈ T } with Lie bracket [δ t , δ u ] := δ t * δ u -δ u * δ t = δ t u-u t ,
where t u is the tree obtained by grafting t on u according to the rule

t u = T ∈T N ′ (t, u, T ) T,
where N ′ (t, u, T ) is the number of partitions V(T ) = V ∐ W of the set of vertices of the tree T into two subsets with W < V , and such that

T | V = v and T | W = u.
(K)) ∼ = Span K ( δ t , t ∈ T ) with Lie bracket [ δ t , δ u ] := δ t * δ u -δ u * δ t = δ t→u-u→t ,
given in terms of the grafting operation

t → u = T ∈T M ′ (t, u, T ) T,
where the factor M ′ (t, u, T ) = σ(t)σ(u) σ(T ) N ′ (t, u, T ) can be interpreted as the number of ways to graft the tree t on the tree u in order to get the tree T . Otherwise said, t → u is the sum of the trees obtained by grafting t on u at any vertex v:

t → u = v∈V(u) t → v u.
The interesting aspect of the last presentation of Lie(G RT (K)) is that the binary operation → on trees is a left pre-Lie product, i.e., for any trees s, t, u, we have:

s → (t → u) -(s → t) → u = t → (s → u) -(t → s) → u.
This identity is easily checked by remarking that the left-hand side is obtained by summing up all the trees obtained by grafting s and t on two (distinct or equal) vertices of u. This procedure is obviously symmetric in s and t. Moreover, it has been shown by F. Chapoton and M. Livernet [START_REF] Chapoton | Pre-Lie algebras and the rooted trees operad[END_REF] that the vector space spanned by the rooted trees T , endowed with the binary product →, is in fact the free pre-Lie algebra with one generator.

Let us consider the pre-Lie algebra (L 1 , ✄) with basis (e n ) n≥1 introduced in Paragraph 5.2.1. Using the universal property of the free pre-Lie algebra, there is a unique pre-Lie algebra morphism

φ : (T , →) -→ (W, ✄) such that φ( ) = e 1 .
It is a fortiori a Lie algebra morphism, and it is obviously surjective: indeed e n is the image of 1 n! ℓ n , where ℓ n is the ladder tree with n vertices. It extends to a surjective Hopf algebra morphism between the corresponding enveloping algebras. Finally, the transposed map gives rise to the Hopf algebra embedding (4.5), namely Ψ : H FdB ֒--→ H RT , of section 4.4.1.

Combinatorial interpretation 6.1 Incidence Hopf algebras

Incidence Hopf algebras are Hopf algebras built from suitable families of partially ordered sets. They have been elaborated by W. R. Schmitt in 1994 [START_REF] Schmitt | Incidence Hopf algebras[END_REF], following the track opened by S. A. Joni and G.-C. Rota when they defined incidence algebras and coalgebras ( [START_REF] Rota | On the foundations of combinatorial theory I: theory of Möbius functions[END_REF][START_REF] Joni | Coalgebras and bialgebras in combinatorics[END_REF], see also [START_REF] Stanley | Enumerative combinatorics[END_REF]). They form a large family of Hopf algebras, which includes those on trees and the Faà di Bruno one. We quickly describe here the subfamily of "standard reduced" incidence Hopf algebras, which are always commutative.

A poset is a partially ordered set P , with order relation denoted by ≤ For any x, y ∈ P , the interval [x, y] is the subset of P formed by the elements z such that x ≤ z ≤ y. Let P be a family of finite posets P such that there exists a unique minimal element 0 P and a unique maximal element 1 P in P (hence P coincides with the interval P = [0 P , 1 P ]). This family is called interval closed if for any poset P ∈ P and for any x ≤ y ∈ P , the interval [x, y] is an element of P. Let P be the quotient P/ ∼, where P ∼ Q if and only if P and Q are isomorphic as posets 4 . The equivalence class of any poset P ∈ P is denoted by P (notation borrowed from [START_REF] Ehrenborg | On posets and Hopf algebras[END_REF]). The standard reduced incidence coalgebra of the family of posets P is the K-vector space freely generated by P, with coproduct given by ∆

[P ] = x∈P [0 P , x] ⊗ [x, 1 P ],
and counit given by ε({ * }) = 1 and ε(P ) = 0 if P contains two elements or more.

Given two posets P and Q, the direct product P × Q is the set-theoretic cartesian product of the two posets, with partial order given by (p, q) ≤ (p ′ , q ′ ) if and only if p ≤ p ′ and q ≤ q ′ . A family of finite posets P is called hereditary if the product P × Q belongs to P whenever P, Q ∈ P. The quotient P is then a commutative semigroup generated by the set P 0 of classes of indecomposable posets, i.e. posets R ∈ P such that for any P, Q ∈ P of cardinality ≥ 2, P × Q is not isomorphic to R. The commutativity comes from the obvious isomorphism P × Q ∼ Q × P for any P, Q ∈ P. The unit element 1 is the class of any poset with only one element.

Proposition 3. [78, Theorem 4.1] If P is a hereditary family of finite posets, the standard reduced coalgebra H(P) of P is a Hopf algebra.

Proof. The semigroup product extends bilinearly to an associative product on H(P). The compatibility of the coproduct with this product is obvious. The unit is a coalgebra morphism and the counit is an algebra morphism. The existence of the antipode comes from the fact that for any poset P ∈ P of cardinal, say, n, we obviously have: ∆(P ) = P ⊗ 1 + 1 ⊗ P + (P )

P ′ ⊗ P ", where P ′ and P " contain strictly less than n elements (note that the fact that P is the interval [0 P , 1 P ] is crucial here). Considering the reduced coproduct ∆(P ) = ∆(P )-P ⊗ 1-1⊗ P , the iterated reduced coproduct ∆ m (P ) therefore vanishes for m > n. It is well-known (see e.g. [START_REF] Manchon | Hopf algebras and renormalisation[END_REF]) that this conilpotence property allows us to define the convolution inverse of the identity, and even of any linear map ϕ : H(P) → H(P) with ϕ(1) = 1.

Many of the Hopf algebras encountered so far are incidence Hopf algebras. We give three examples, all of them borrowed from [START_REF] Schmitt | Incidence Hopf algebras[END_REF].

6.1.1 The binomial and the divided power Hopf algebras Let B be the family of finite boolean algebras. An element of B is any poset isomorphic to the set P(A) of all subsets of a finite set A. The partial order on P(A) is given by the inclusion. If B and C are two subsets of A with B ⊂ C, the interval [B, C] in P(A) is isomorphic to P(C\B), hence B is interval-closed. Moreover the obvious property:

P(A) × P(B) ∼ P(A ∐ B) (6.1)
implies that B is hereditary. The incidence Hopf algebra H(B) is the so-called binomial Hopf algebra, because of the expression of the coproduct on generators. In fact, as a vector space H(B) is clearly spanned by {x 0 , x 1 , x 2 , . . .}, where x n stands for the isomorphism class of P({1, . . . , n}). The product is obviously given by x m x n = x m+n , the unit is 1 = x 0 , the counit is given by ε(x n ) = 0 for n ≥ 1, and the coproduct is entirely defined by ∆(x 1 ) = x 1 ⊗ 1 + 1 ⊗ x 1 . Explicitly we have:

∆(x n ) = n k=0 n k x k ⊗ x n-k .
The graded dual Hopf algebra H(B) * is known as the divided power algebra: it can be represented as the vector space K{y 0 , y 1 , y 2 , . . .} with multiplication

y m ⋆ y n = m + n m y m+n
and unit 1 = y 0 . The counit is ε(y n ) = 0 if n > 0, and the coproduct is given by ∆(y n ) = p+q=n y p ⊗ y q .

6.1.2 The Faà di Bruno Hopf algebra Let SP be the family of posets isomorphic to the set SP(A) of all partitions of some nonempty finite set A. The partial order on set partitions is given by refinement. We denote by 0 A or 0 the partition by singletons, and by 1 A or 1 the partition with only one block. Let Q be the family of posets isomorphic to the cartesian product of a finite number of elements in SP. If S and T are two partitions of a finite set A with S ≤ T (i.e. S is finer than T ), the partition S restricts to a partition of any block of T . Denoting by W/S the set of those blocks of S which are included in some block W of T , any partition U such that S ≤ U ≤ T yields a partition of the set W/S for any block W of T . This in turn yields the following obvious poset isomorphism:

[S, T ] ∼ W ∈A/T SP(W/S). (6.2)
This shows that Q is interval closed (and hereditary by definition). Proof. Denote by X n the isomorphism class of SP({1, . . . , n + 1}). Note that X 0 is the unit of the Hopf algebra.

In view of (6.2), we have:

∆(X n ) = S∈SP({1,...,n+1}) [0, S] ⊗ [S, 1] = S∈SP({1,...,n+1})   W ∈{1,...,n+1}/S SP(W )   ⊗ SP({1, . . . , n + 1}/S). (6.3)
The coefficient in front of

X k1 1 • • • X kn n ⊗ X m in (6.
3) is equal to the number of partitions of {1, • • • , n + 1} with k j blocks of size j + 1 (for j = 1 to n), m + 1 blocks altogether, and

k 0 = m + 1 -k 1 -• • • -k n blocks of size 1.
By definition of the Bell polynomials in terms of partitions, we have then:

∆(X n ) = n m=0 B m+1,n+1 (X 0 , X 1 , X 2 , . . .) ⊗ X m , (6.4)
which in turn gives (4.2) with x j := 1 (j+1)! X j .

6.1.3 The Hopf algebra of rooted trees Let P be a finite poset not assumed tobe isomorphic to an interval.

As an example, we can take as poset P the vertex set V(F ) of a rooted forest F , in which v ≤ w if and only if there is a path from one root to w through v. An order ideal (or initial segment) in P is a subset I of P such that for any w ∈ I, if v ≤ w, then v ∈ I. For a rooted forest F , an initial segment in V(F ) is a subforest such that any connected component of it contains a root of F . For any finite poset P , we denote by J(P ) the poset of all initial segments of P , ordered by inclusion [START_REF] Schmitt | Incidence Hopf algebras[END_REF]Paragraph 16]. The minimal element 0 J(P ) is the empty set, and the maximal element 1 J(P ) is P . For two finite posets P and Q one obviously has:

J(P ∐ Q) ∼ J(P ) × J(Q). (6.5)
The isomrphism class of a poset P is uniquely determined by the isomorphism class of the poset J(P ). To see this, consider two posets P and Q, and suppose there is an isomorphism Φ : J(P ) → J(Q). For any x ∈ P , consider the initial segment P ≤x := {y ∈ P, y ≤ x}. It has x as unique maximal element. Now, Φ(P ≤x ) has a unique maximal element which we denote by ϕ(x), and it is not hard to see that the map ϕ : P → Q thus constructed is a poset isomorphism.

For a poset P and two initial segments I 1 ⊂ I 2 ⊂ P with I 1 fixed, the correspondence I 2 → I 2 \I 1 defines a poset isomorphism:

[I 1 , I 2 ] ⊂ J(P ) -→ J(I 2 \I 1 ). (6.6)

Differences Q = I 2 \I 1 are convex subsets of P , i.e. such that for any x, y ∈ Q, we have [x, y] ≤ Q. Conversely, any convex subset Q ⊂ P can be written as a difference P ≤Q \P <Q of two unique initial segments:

P ≤Q := {x ∈ P, ∃y ∈ Q, x ≤ y}, P <Q := {x ∈ P, ∀y ∈ Q, x < y}.
Now let F be a family of finite posets which is closed by disjoint unions and such that for any poset P ∈ F , convex subsets of P also belong to F . Then the corresponding family:

J(F ) := {J(P ), P ∈ F }
is hereditary by virtue of isomorphisms (6.5) and (6.6).

Proposition 5. The family F of rooted forests is stable by taking disjoint unions and convex subposets, and the associated incidence Hopf algebra H J(F ) is isomorphic to H RT .

Proof. Via the isomorphism Φ defined above, the vector space H J(F ) can be identified with the vector space freely generated be the rooted forests. By (6.5), the product is then given by disjoint union, and the coproduct writes: ∆(P ) = I∈J(P )

(P \I) ⊗ I,
which is just the coproduct (4.3) modulo flipping the terms (we have denoted by the same letter a forest and its underlying poset). The counit is given by ε(1) = 1 and ε(P ) = 0 for any nontrivial forest P .

This example can be extended, still in the context of incidence Hopf algebras, to oriented cycle-free graphs [START_REF] Manchon | On bialgebras and Hopf algebras of oriented graphs[END_REF]. Hopf algebras of Feynman graphs do not enter strictly speaking into this framework (see however [START_REF] Schmitt | Incidence Hopf algebras[END_REF]Paragraph 14] about Hopf algebras of simple 3-connected graphs). For other examples of incidence coalgebras and Hopf algebras, see [START_REF] Joni | Coalgebras and bialgebras in combinatorics[END_REF][START_REF] Schmitt | Incidence Hopf algebras[END_REF].

Combinatorial Hopf algebras

The Faà di Bruno Hopf algebra has some important properties also satisfied by almost all examples of graded Hopf algebras we have encountered so far (see [START_REF] Joni | Coalgebras and bialgebras in combinatorics[END_REF]). These properties are:

• to be connected,

• to be free or free commutative (or, dually, cofree or cofree cocommutative),

• to have an explicit basis,

• to have the "right-sided property":

∆(x n ) = (polynomial in x k ) ⊗ x m (6.7)
or its left analogue.

Hopf algebras of this type have been called combinatorial Hopf algebras5 by J.-L. Loday and M. Ronco in [START_REF] Loday | Combinatorial Hopf algebras[END_REF].

In particular, any combinatorial Hopf algebra fits into one of the four types below:

T a (V ), ⊗, ∆?)

S a (V ), •, ∆? ⇐⇒ graded Hopf algebra duality T c (V ), ∆ ⊗ , * ? S c (V ), ∆ , * ? free type cofree type

Let us explain the diagram above: here, V is a graded vector space with finite-dimensional homogeneous components, T a (V ) stands for the free algebra on V endowed with the tensor product ⊗ (also called concatenation on words), and T c (V ) stands for the graded cofree coalgebra on V endowed with the deconcatenation coproduct ∆ ⊗ defined by:

∆ ⊗ (v 1 ⊗ • • • ⊗ v n ) = n k=0 (v 1 ⊗ • • • ⊗ v k ) (v k+1 ⊗ • • • ⊗ v n ).
It can be seen as the graded dual of T a (V * ), where V * is the graded dual of V . In the same spirit, S a (V ) stands for the free commutative algebra on V endowed with the symmetrized tensor product •, and S c (V ) stands for the the graded cofree cocommutative coalgebra endowed with the unshuffle coproduct defined by:

∆ (v) = v ⊗ 1 + 1 ⊗ v
for any v ∈ V , and extended multiplicatively (see (6.9) below). The operations ∆? and * ? stand for a priori unknown coproducts and products which the give rise to Hopf algebras of the desired type.

J.-L. Loday and M. Ronco classified combinatorial Hopf algebras in [START_REF] Loday | Combinatorial Hopf algebras[END_REF]. The simplest examples are the coordinate rings of the pro-algebraic groups G inv and G dif and their graded duals, which are of the symmetric type, and their non-symmetric lifts. In particular, their results imply the existence of a brace bracket on the enveloping algebras of L 1 and W + , which reproduces the pre-Lie bracket already mentioned in section 5.2.1 on the Lie algebras. We briefly discuss these examples.

The non-commutative Faà di Bruno Hopf algebra and the brace bracket

The simplest examples of combinatorial Hopf algebras are the non-commutative lifts of the coordinate rings of the pro-algebraic groups G inv and G dif , and their graded duals. In the case of the group G inv , we obtain two combinatorial Hopf algebras:

T a (V ) = H nc inv = K x 1 , x 2 , x 3 , ... , with product ⊗ and coproduct ∆ inv , T c (V ) = (H nc inv ) * = K x 1 , x 2 , x 3
, ... , with coproduct t ⊗ = ∆ ⊗ and product * = ∆ * inv . We have already encountered the Hopf algebra H nc inv in section 4.5: it is endowed with the same coproduct ∆ inv as H inv , and it is therefore cocommutative. Dually, the operation * = ∆ * inv is the commutative product:

x n * x m = x n+m ,
and (H nc inv ) * is then isomorphic to the tensor coalgebra on the polynomial ring K[T ] in one variable T = x 1 , with isomorphism given by x n → T n . In the case of the group G dif , we obtain two combinatorial Hopf algebras:

T a (V ) = H nc FdB = K x 1 , x 2 , x 3
, ... , with product ⊗ and coproduct ∆ FdB , T c (V ) = (H nc FdB ) * = K e 1 , e 2 , e 3 , ... , with coproduct t ⊗ = ∆ ⊗ and product * = ∆ * FdB .

The Hopf algebra H nc FdB , and its mysterious nature, has already been discussed in sections 4.5 and 4.7. For its dual Hopf algebra (H nc FdB ) * , we shall refer to the general classification theorem established by Loday and Ronco: if H ∼ = T c (V ) for some graded vector space V , with cofree coassociative coproduct ∆ ⊗ and product * satisfying the dual of the right-sided property (6.7), then V is a (right) brace algebra [START_REF] Lada | Symmetric brace algebras[END_REF], i.e. is equipped with a bilinear map { ; } : V ⊗ T (V ) -→ V , called (right) brace product, such that {{x;

y 1 • • • y p }; z 1 • • • z q } = {x; z 1 • • • z i1 {y 1 ; z i1+1 • • • z j1 }z j1+1 • • • z ip {y p ; z ip+1 • • • z jp }z jp+1 • • • z q }, (6.8)
where the sum runs over all sequences 0 ≤ i 1 ≤ j 1 ≤ • • • ≤ i p ≤ j p ≤ q. In the case T c (V ) = (H nc FdB ) * , the right-sided property is fulfilled by the opposite algebra (H nc,op FdB ) * , with product ∆ op FdB * : in this case the brace product on the vector space V = Span K {x 1 , x 2 , x 3 , ...} has been computed in [START_REF] Brouder | Combinatorial Hopf algebras from renormalization[END_REF]. If we omit the symbol ⊗ of the tensor product in the monomials, the brace product reads:

{x n ; x m1 • • • x mq } = n + 1 q x n+m1+•••+mq .
For the algebra T c (V ) = (H nc FdB ) * , which satisfies the left-sided property, one gets a left brace product { ; } : T (V ) ⊗ V -→ V satisfying the obvious analogue properties of (6.8).

6.2.2

The Faà di Bruno Hopf algebra and the pre-Lie bracket The symmetric versions of the two previous examples of combinatorial Hopf algebras are the coordinate rings of the pro-algebraic groups G inv and G dif (or G dif,op ), and their graded duals. In the case of the group G inv , we get the two combinatorial Hopf algebras

S a (V ) = H inv = K[x 1 , x 2 , x 3 , ...], with free commutative product • and coproduct ∆ inv , S c (V ) = H * inv = K x 1 , x 2 , x 3
, ... , with coproduct ∆ and product * = ∆ * inv . The unshuffle coproduct is defined on a monomial x n1 • • • x n k ∈ K x 1 , x 2 , x 3 , ... (where we omit the tensor product ⊗ for simplicity) in the following way:

∆ (x n1 • • • x n k ) = p+q=k σ∈Sh(p,q) x n σ(1) • • • x n σ(p) ⊗ x n σ(p+1) • • • x n σ(p+q) , (6.9)
where Sh(p, q) is the set of (p, q)-shuffles, i.e. the permutations σ of p + q numbers such that

σ(1) < • • • < σ(p) and σ(p + 1) < • • • < σ(p + q).
Both Hopf algebras are commutative and cocommutative: H inv is the coordinate ring of the abelian group G inv (K), and H * inv is the enveloping algebra of the Lie algebra Lie G inv (K) , which is in fact the free abelian Lie algebra spanned by the variables x 1 , x 2 , x 3 , ..., and is obviously isomorphic to the polynomial ring K[T ] in one variable.

In the case of the group G dif , we get the two combinatorial Hopf algebras

S a (V ) = H FdB = K[x 1 , x 2 , x 3 , ...], with free commutative product • and coproduct ∆ FdB , S c (V ) = H * FdB = K e 1 , e 2
, e 3 , ... , with coproduct ∆ and product * = ∆ * FdB . In the symmetric case, the Loday-Ronco classification theorem (studied before also by T. Lada, M. Markl [START_REF] Lada | Symmetric brace algebras[END_REF] and by D. Guin, J.-M. Oudom [START_REF] Guin | On the Lie enveloping algebra of a pre-Lie algebra, J. of K-theory: K-theory and its applications to algebra[END_REF]) says the following: if H ∼ = S c (V ) is endowed with the unshuffle coproduct ∆ , and if the product * satisfies the dual of the right-sided property (6.7), then V is a right pre-Lie algebra, i.e. is equipped with a binary product ✁ : V ⊗ V -→ V such that:

(x ✁ y) ✁ z -x ✁ (y ✁ z) = (x ✁ z) ✁ y -x ✁ (z ✁ y).
(6.10)

Comparing with the results in the non-symmetric case, a pre-Lie product is an example of a brace product

{ ; } : V ⊗ T (V ) -→ V , which vanishes outside the subspace V ⊗ V , that is {x; y} = x ✁ y and {x, y 1 • • • y m } = 0 if m = 1.
On the other side, any pre-Lie product on V gives rise to a symmetric brace product { ; } : V ⊗ S(V ) -→ V , recursively defined by {x; 1} = x, {x; y} = x ✁ y, and {x;

y 1 • • • y p } = {x; y 1 • • • y p-1 } ✁ y p -{x; {y 1 ; y 2 • • • y p-1 }}.
Details can be found in [START_REF] Guin | On the Lie enveloping algebra of a pre-Lie algebra, J. of K-theory: K-theory and its applications to algebra[END_REF] and [START_REF] Lada | Symmetric brace algebras[END_REF].

This general result applies in particular to the Hopf algebra H * FdB = U (L 1 ) (modulo a switch between right and left properties), and tells that the Lie algebra of vector fields L 1 is a symmetric left brace algebra, and thus a left pre-Lie algebra [START_REF] Brouder | Combinatorial Hopf algebras from renormalization[END_REF]: the opposite of the brace bracket given in (6.8) is in fact symmetric, and induces on L 1 the left pre-Lie product e n ✁ e m = {e n ; e m } op = (m + 1) e n+m that we saw in section 5.2.1.

Note that the pre-Lie bracket defined on L 1 can be extended to a left pre-Lie bracket on the Lie algebra Vect(S 1 ) = Span K {e n , n ∈ Z}.

6.2.3

The shuffle Hopf algebra A last example of a combinatorial Hopf algebra is the shuffle Hopf algebra T c (V ) = K x 1 , x 2 , ... endowed with the deconcatenation ∆ ⊗ and the shuffle product

(x n1 ⊗ • • • ⊗ x np ) (x np+1 ⊗ • • • ⊗ x np+q ) = σ∈Sh(p,q) x n σ(1) ⊗ • • • ⊗ x n σ(p+q) .
We give the degree n to the letter x n . This commutative graded Hopf algebra represents the prounipotent group scheme A → G A , whose Lie algebra is g A = g ⊗ A, where g is the free Lie algebra over the alphabet {x 1 , x 2 , . . .}.

Operadic interpretation

sect:operad Operads are combinatorial devices which appeared in algebraic topology, coined for coding "types of algebras". Hence, for example, a Lie algebra is an algebra over some operad denoted by Lie, an associative algebra is an algebra over some operad denoted by Assoc, a commutative algebra is an algebra over some operad denoted by Com, etc. The term "operad" has been invented by J.-P. May [START_REF] May | The Geometry of Iterated Loop Spaces[END_REF], although the notion itself appears a few years before in an article by J. M. Boardman and R. M. Vogt [START_REF] Boardman | Homotopy-everything H-spaces[END_REF]. For a comprehensive and recent textbook on operads, we refer the reader to [START_REF] Loday | Algebraic operads[END_REF]. See also [START_REF] Loday | La renaissance des opérades[END_REF] for a more concise overview.

Manipulating algebraic operations

For any n ∈ N, an n-ary operation on a vector space V is an n-multilinear map

a : V ⊗n -→ V , (v 1 , ..., v n ) → a(v 1 , ..., v n ) suitably represented by a box: a Graphical representation of an n-ary operation 1 • • • • • • i n
where the n inputs represent the variables v 1 , ..., v n and the output represents the result a(v 1 , ..., v n ) of the operation. For n = 1 there is a canonical operation, namely the identity map Id : V → V . One can even consider 0-ary operations, as being just distinguished elements of V .

Given an n-ary operation a, one can consider new n-ary operations by permuting the inputs of a, that is, by setting

a σ (v 1 , ..., v n ) = a(v σ(1) , ..., v σ(n) ),
for any permutation σ ∈ S n . For instance, given a binary operation a

(v 1 , v 2 ) = v 1 * v 2 , one can consider the opposite operation v 1 * op v 2 = v 2 * v 1 = a (12) (v 1 , v 2 ).
Given a ternary operation b(v 1 , v 2 , v 3 ), one can define algtogether six operations b σ simply by permuting the inputs with a permutation σ ∈ S 3 . In all cases, the symmetric group S n obviously acts (from the right) on the set of n-ary operations, by permuting their entries.

Given any two operations a and b on V , one also obtains new operations by applying them one after the other. For instance, if a is an n-ary operation, and b is an m-ary operation, we get an (n + m -1)-ary operation by applying first b on any subset of m variables among the n + m -1 available, and then applying a to the n variables thus obtained. The operation thus obtained is the partial composition a • i b, for any choice of i = 1, ..., n where the result of b is inserted as a variable of a, namely (a

• i b)(v 1 , ..., v n+m-1 ) := a(v 1 , • • • , v i-1 , b(v i , ...., b i+m-1 ), v i+m , ..., v n+m-1 ). Graphically: b a Partial composition a • i b 1 1 • • • • • • i n + m -1 n For instance, if we compose a binary operation a(v 1 , v 2 ) = v 1 * v 2 with itself, we obtain two ternary operations (v 1 , v 2 , v 3 ) → (v 1 * v 2 ) * v 3 , and (v 1 , v 2 , v 3 ) → v 1 * (v 2 * v 3 )
which do not change the order of the inputs, and twelve operations if we allow the permutations of the entries.

The "types of algebras" that one may wish to consider are characterized by the properties of the operations that one can perform. The concept of operad emerges when one tries to write such properties only in terms of the operations, discarding the entries. For example, a vector space V is an associative algebra if it is endowed with a binary operation a : V ⊗2 → V , denoted by * , which is associative, i.e. for any x, y, z ∈ V we have:

(x * y) * z = x * (y * z) that is a • 1 a = a • 2 a.
Similarly, a vector space V is a Lie algebra if it is endowed with a binary operation a : V ⊗2 → V , denoted by [ , ], which is antisymmetric and satisfies the Jacobi identity, i.e. for any x, y, z ∈ V we have:

[x, y] + [y, x] = 0 that is a + a (12) = 0, [[x, y], z] + [[y, z], x] + [[z, x], y] = 0 that is a • 1 a + (a • 1 a) τ + (a • 1 a) τ 2 = 0,
where τ is the circular permutation (123) ∈ S 3 .

Algebraic operads

An algebraic operad, or linear operad, is a collection P = P(n) n≥0 of K-vector spaces P(n) on which the symmetric group S n acts from the right, together with a distinguished element e ∈ P(1), called the identity, and a collection of linear maps, called partial compositions,

• i : P(k) ⊗ P(l) -→ P(k + l -1), i = 1, . . . , k (a, b) -→ a • i b
satisfying the following associativity, unit and equivariance axioms:

• The nested and the disjoint associativity: for any a ∈ P(k), b ∈ P(l), c ∈ P(m) one has:

(a • i b) • i+j-1 c = a • i (b • j c), i ∈ {1, . . . , k}, j ∈ {1, . . . , l}, (7.1)
(a • i b) • l+j-1 c = (a • j c) • i b, i, j ∈ {1, . . . , k}, i < j. (7.2)
Graphically, these compositions produce the following operations:

Nested associativity

Disjoint associativity

1 i k k • • • 1 1 j l m • • • 1 i j 1 l • • • • • • • • • • • • • The unit property: e • a = a (7.3) a • i e = a, i = 1, . . . , k. (7.4)
• The equivariance property:

a σ • σ(i) b τ = (a • i b) ηi(σ,τ ) (7.5)
where η i (σ, τ ) ∈ S k+l-1 is defined by letting τ permute the set E i = {i, i + 1, . . . , i + l -1} of cardinality l, and then by letting σ permute the set {1, . . . , i -1, E i , i + l, . . . , k + l -1} of cardinality k.

The prototype of algebraic operads is the endomorphism operad on a vector space V , denoted by End(V ). For any n ≥ 0, it is given by the vector space of n-multilinear maps on V , that is,

End(V )(n) = L(V ⊗n , V ).
The right action of the symmetric group S n on End(V )(n) is induced by the left action of S n on V ⊗n given by:

σ.(v 1 ⊗ • • • ⊗ v n ) = v σ -1 1 ⊗ • • • ⊗ v σ -1
n . The unit element is the identity map e : V → V , and the partial compositions are given by true compositions of linear maps.

Given an operad P, a P-algebra is a vector space A together with a morphism of operads from P to End(A), that is, for any n ≥ 0, an equivariant linear map P(n) -→ End(A)(n) = L(A ⊗n , A) which identifies each element a of P(n) with an n-ary operation on A, and which preserves the partial compositions. Given two P-algebras A and B, a morphism of P-algebras from A to B is a linear map f : A → B such that, for any n ≥ 0 and for any a ∈ P(n), the following diagram commutes, Such a map allows us to regard an operad P as a Schur functor [START_REF] Macdonald | Symmetric functions and Hall polynomials[END_REF][START_REF] Loday | Algebraic operads[END_REF] on K-vector spaces:

P : Vect K -→ Vect K , V -→ P(V ) = n≥0 P(n) ⊗ Sn V ⊗n
endowed with an associative composition γ : P • P -→ P and with a unit i : I ֒→ P from the trivial operad I(n) = δ n,1 Ke. A P-algebra can then be also seen as a vector space A endowed with an associative linear map γ A : P • P(A) -→ P(A), i.e. such that γ A (γ A • I) = γ A (I • γ A ) : P • P • P(A) -→ P(A). The usual type of algebras give rise to the following operads:

• Assoc for associative algebras:

Assoc(n) = K[S n ].
• Com for associative and commutative algebras: Com(n) is given by the trivial representation of S n .

• Lie for Lie algebras: the vector space Lie(n) is the representation of S n induced from the one-dimensional representation ρ of C n = Z/Z n given by a primitive n-th root of unity, i.e. Lie(n) = Ind Sn Cn (ρ).

• preLie for right pre-Lie algebras [START_REF] Gerstenhaber | The cohomology structure of an ass-ociative ring[END_REF][START_REF] Vinberg | The theory of convex homogeneous cones[END_REF]: as a vector space preLie(n) = Span K {T n } is spanned by the rooted trees with n labeled vertices, and the symmetric groups S n acts by permuting the labels [START_REF] Chapoton | Pre-Lie algebras and the rooted trees operad[END_REF].

For more details about operads, see e.g. [START_REF] Loday | La renaissance des opérades[END_REF][START_REF] Loday | Algebraic operads[END_REF].

Pre-Lie algebras, Lie algebras and groups associated to operads

For operads P such that P(0) = {0}, there is a canonical way to construct a pronilpotent Lie algebra and, dually, a prounipotent group. For simplicity, let us illustrate this construction for regular operads.

An operad P is regular [68, Paragraph 5.2.9] if for any n ≥ 0 we have P(n) = P n ⊗ K[S n ], where P n is some vector space. In this case, the operad P gives rise to the non-symmetric operad P ′ = (P n ) n≥0 , which verifies axioms similar to those of an operad, except that the actions of symmetric groups are not required. Any operad is also a non-symmetric operad, if we forget the symmetric group actions. An algebra over a non-symmetric operad P ′ is a vector space A together with a non-symmetric operad morphism from P ′ into the underlying non-symmetric operad of End(A).

An operad P is regular if the relations defining the P-algebras can be written without switching the arguments. For example, the associativity identity (x * y) * z = x * (y * z) does not change the order of the variables: thus Assoc is regular. Indeed Assoc(n) = K[S n ], and the associated non-symmetric operad Assoc ′ is given by Assoc ′ n = K. The operads Com, Lie and preLie are not regular.

spaces P(n) generated by some sets P set (n). The collection P set = P set (n) n≥1 gives rise to a set operad, that is, an operad in the category of sets. The axioms for set operads are the same as for linear operads, except that the tensor product of vector spaces is replaced by the cartesian product of sets, and the direct sum is replaced by the disjoint union. If moreover the set-like operad is regular, the associated set operad is regular as well, i.e. P set (n) = P set,n × S n for any n ≥ 1.

If P is a regular set-like operad, the proalgebraic group G P was called the group of P-expanded series in [START_REF] Frabetti | Groups of tree-expanded formal series[END_REF]:

G P (A) = f (x) = p∈Pn f p x p f p ∈ A ,
where x p is just a symbol, with product given by a formal composition law (f • g)(x) = p∈P q1,...,q |p| ∈P f p g q1 • • • g q |p| x γ(p,q1,...,q |p| ) .

The simplest example of a regular set-like operad is Assoc, with one single n-ary operation up to permutation for any n ≥ 1 which is denoted by n -1. Hence the non-symmetric set operad Assoc ′ set can be identified with the set N of (non-negative) natural numbers. The operadic partial composition of two operations p and q (which is unique by virtue of the associativity) coincides with the sum p + q. Similarly, the total composition γ(n; m 0 , m 1 , ..., m n ) coincides with the sum m 0 + • • • + m n . For any unital commutative algebra A, the group G Assoc ′ set (A) is again the group of formal diffeomorphisms G dif (A). In [START_REF] Frabetti | Groups of tree-expanded formal series[END_REF] it was shown also that, for any regular set operad P, the order map P -→ Assoc ′ set , p → |p| induces a canonical surjective morphism of groups G P (A) → → G dif (A). Moreover, any element p 2 ∈ P 2 which satisfies the associativity axiom, if it exists, gives an operad morphism Assoc ′ set -→ P, n -→ p n = γ(p 2 ; p n-1 , e) which induces a section G dif (A) -→ G P (A).

7.3.2

The QED charge Hopf algebra on planar binary trees and the duplicial operad Another example of a regular set operad is the operad Dup which defines duplicial algebras [START_REF] Zinbiel | Encyclopedia of types of algebras 2010[END_REF], that is, algebras A endowed with two binary operations over / and under \, satisfying the following identities: (x/y)/z = x/(y/z) (x/y)\z = x/(y\z) (x\y)\z = x\(y\z), for any x, y, z ∈ A. The operad Dup is described by means of planar binary trees [START_REF] Frabetti | Groups of tree-expanded formal series[END_REF][START_REF] Loday | Generalized bialgebras and triples of operads[END_REF], that is, planar rooted trees with internal vertices of valence 3. For any n ≥ 0, Dup n is the set of trees with n internal vertices:

Dup 0 = { } , Dup 1 = { } , Dup 2 = , , Dup 3 = , , , , .
The operations over and under are defined on any two trees t and s as the following grafting of the root of a tree onto the left-most or onto the right-most leaf of the other one:

t over s: t/s = s t t under s: t\s = t s

The operadic composition in Dup is then given by the following rule: for any trees t and s 1 , ..., s |t| , the tree γ(t; s 1 , ..., s |t| ) is obtained by replacing each internal vertex of t by the trees s 1 , ..., s |t| , in the order given by the decomposition of t as a monomial in the vertex tree , using the over and under products and suitable parentheses. For instance, = ( \ )/ hence µ (s 1 , s 2 , s 3 ) = (s 1 \s 2 )/s 3 = s 3 s 1 s 2

.

The group G Dup (A) of tree-expanded series of the form f (x) = t∈Dup f t x t , with f t ∈ A and f Y = 1 was studied extensively in [START_REF] Frabetti | Groups of tree-expanded formal series[END_REF]. Since the operad Dup contains a binary associative operation , the group G Dup (A) projects onto the group G dif (A) and at the same time contains a copy of G dif (A). Moreover, this proalgebraic group is represented by a commutative Hopf algebra H Dup on planar binary trees which admits a non-commutative lift different from the Loday-Ronco Hopf algebra on planar binary trees [START_REF] Loday | Hopf algebra of the planar binary trees[END_REF], and different from its linear dual.

Finally, the group G Dup (C) contains a proalgebraic subgroup G α (C) whose representative Hopf algebra H α was used in [START_REF] Brouder | Renormalization of QED with planar binary trees[END_REF][START_REF] Brouder | QED Hopf algebras on planar binary trees[END_REF] to describe the renormalization of the electric charge in massless quantum electrodynamics. The algebra H α is a suitable quotient of the algebra H Dup , such that the group G α (C) can be seen as the set of tree-expanded series of the form

α f (x) = x -x \f (x) -1 /x ,
for any tree-expanded series f (x) = f t x t . Here the inversion of the series xx \f (x) is performed in the group of tree-expanded invertible series, which is the set of tree-expanded series starting with the term x , and considered with the product over.

  }, with T = t 0 +t 1 y +t 2 y 2 +• • • . Set now ∂ k := d dt k for short and collect all the powers ∂ n 0 in the formal translation operator e y∂0 = k≥0 y k k! ∂ k 0 . The crucial properties:

  6): DF (T )[S] = S.DF (T )[∂ 0 ] (2.7) for any S ∈ R[[y]]. Conversely, any smooth functional F : R[[y]] → R[[y]] which satisfies (2.7) also satisfies the following identities involving higher-order differentials:D r F (T )[S 1 , . . . , S r ] = S 1 • • • S r .D r F (T )[∂ 0 , . . . , ∂ 0 ]. (2.8)

Proposition 4 .

 4 [START_REF] Schmitt | Incidence Hopf algebras[END_REF] Example 14.1] The incidence Hopf algebra H(Q) is isomorphic to the Faà di Bruno Hopf algebra.

  where we have denoted by the same letter a the element of P(n) and its images in End(A)(n) and End(B)(n).Using the partial compositions one can also define a total compositionγ : P(n) ⊗ P(k 1 ) ⊗ • • • ⊗ P(k n ) -→ P(k 1 + • • • + k n ) (a, b 1 , . . . , b n ) -→ γ(a; b 1 , . . . , b n ) = ... (a • n b n ) • n-1 b n-1 • • • • 1 b 1 ,which is graphically represented as follows:Total composition γ(a; b 1 , b 2 , . . . , b n )

  Open questions about the non-commutative Faà di Bruno Hopf algebra Contrarily to invertible series with ordinary multiplication, formal diffeomorphisms G dif (A) with non-commutative coefficients do not form a group. Indeed, the composition is not associative! As a consequence, the noncommutative Faà di Bruno coproduct ∆ nc FdB cannot be derived from a cogroup coproduct ∆ :H nc FdB -→ H ncFdB * H nc FdB by composing it on the left with the projection π onto H nc FdB ⊗ H nc FdB . One may then ask the following questions:• Which properties do characterise the set G dif (A) of formal series with coefficients in a non-commutative algebra A, generalizing those of a group, which would allow to define G dif as a functor represented by H nc FdB ? • Is there a cogroup coproduct ∆ : H -→ H * H such that π • ∆ : H → H ⊗ H gives ∆ FdB , which would then allow to define a proalgebraic group of formal seriesG(A) = {f (t) = t + n≥2 f n t n+1 | f n ∈ A}with coefficients in non-commutative algebras A, with group law induced by ∆ and therefore different from the composition (f • g)(t) = f n g(t) n+1 ? If such a group exists, it is probably necessary to rearrange the terms f n t n+1 of each series in some non-commutative fashion. These questions are still open.

	4.7
	g(t). The Hopf algebra coproduct ∆ inv : H nc inv -→ H nc inv ⊗ H nc inv is then just the composition of the cogroup coproduct ∆ * inv by the canonical projection H nc inv ⋆ H nc inv → → H nc inv ⊗ H nc inv .

A B-series is map from the set of rooted trees, including the empty one, to the base field R or C of real or complex numbers. A B-series can be identified with an element of the Butcher group if and only if the coefficient of the empty tree is equal to one.

The loop number is defined by L(Γ) = I(Γ) -V (Γ) + |π 0 (Γ)|, where I(Γ) stands for the number of internal edges, V (Γ) stands for the number of vertices, and |π 0 (Γ)| denotes the number of connected components of the graph.

This Lie algebra is denoted W 1 (K) by D.B. Fuks in[START_REF] Fuks | Cohomology of infinite-dimensional Lie algebras[END_REF], who considers also the Lie algebras of formal vector fields on any n-dimensional space, Wn(K).

W. Schmitt allows more general equivalence relations, called order-compatible relations.

A different definition of combinatorial Hopf algebras was proposed, for commutative ones, by F. Hivert, J.-C. Novelli and J.-Y. Thibon in[START_REF] Hivert | Commutative combinatorial Hopf algebras[END_REF].

Acknowledgements We thank the referees for their careful reading and their pertinent suggestions which greatly helped us to improve the text.

Let P be a regular operad, hence P(n) = P n ⊗ K[S n ]. The Lie algebra associated to P was introduced by M. Kapranov in 2000, see [START_REF] Kapranov | Modules and Morita theorem for operads[END_REF], as the vector space

with Lie bracket [p, q] = p ✁ qq ✁ p induced by the right pre-Lie product p ✁ q = γ(q; id, ..., p, ..., id),

where the sum runs on the possible places to put p. Since P n ✁ P m ⊂ P n+m-1 , the above pre-Lie and Lie products are graded by |p| = n -1 for p ∈ P n . As the sum starts at n = 2, this Lie algebra is pronilpotent.

The completion L P of the Lie algebra L P , with respect to this graduation, contains formal series, i.e. possibly infinite sums n≥2 p n , with p n ∈ P n .

If the operad P is not regular, a similar construction makes sense if we consider the sum of coinvariant spaces, with respect to the action of the symmetric group, that is, if we set:

Pre-Lie and Lie products are defined similarly, as the sum of all partial compositions still makes sense modulo the symmetric group actions.

Let P be a regular operad which satisfies P(0) = {0} and P(1) = Ke. The group associated to P was defined independently by F. Chapoton [START_REF] Chapoton | Rooted trees and exponential-likes series[END_REF] and P. van der Laan [START_REF] Van Der Laan | Operads and the Hopf algebras of renormalization[END_REF] as the set

with the composition law:

γ(p n ; q m1 , ..., q mn ). A similar construction is again possible for non-regular operads, if we replace P n by P(n)/S n . The group G (P) is prounipotent, with associated pronilpotent Lie algebra L P . Two Hopf algebras can then be associated to P: the co-commutative Hopf algebra U (L P ), and its graded dual H P , which is commutative and represents the proalgebraic group G P , i.e. G P (A) = Hom CAlg (H P , A) for any unital and commutative algebra A.

7.3.1

The Faà di Bruno Hopf algebra and the associative operad F. Chapoton and P. van der Laan proved [START_REF] Chapoton | Rooted trees and exponential-likes series[END_REF][START_REF] Van Der Laan | Operads and the Hopf algebras of renormalization[END_REF] that the group G P is the group of formal diffeomorphisms G dif if P is the non-symmetric operad Assoc of associative algebras. In this case, in fact, in each degree n ≥ 1 there is only one possible operation, up to a scalar factor and permutation. If we choose a generator p n for each vector space Assoc ′ n (with the notation introduced in the beginning of Section 7.3), an element of the group G P is a formal series

and the operadic composition of two such series gives exactly the Faà di Bruno composition of diffeomorphisms. If P is the (non-regular) operad Com of commutative algebras, the construction above gives back the group G inv [START_REF] Chapoton | Rooted trees and exponential-likes series[END_REF].

A similar construction of the group G dif was done in [START_REF] Frabetti | Groups of tree-expanded formal series[END_REF] for set-operads. In this case, there was proven a general criterion to compare the group G dif with the group G P associated to suitable operads. An operad P is a set-like operad if the relations defining the operations do not involve sums or multiplications by scalars. For instance, the operads Assoc and Com are set-like. A set-like operad P is then the collection of the vector