, on a writing of the classical Magnus expansion in L(E), using the pre-Lie structure.

Résumé

Dans cette thèse, nous étudions le concept d'algèbre pré-Lie libre engendrée par un ensemble (non-vide). Nous rappelons la construction par A. Agrachev et R. Gamkrelidze [START_REF] Agrachev | Chronological algebras and nonstationary vector fields[END_REF] des bases de monômes dans les algèbres pré-Lie libres. Nous décrivons la matrice des vecteurs d'une base de monômes en termes de la base d'arbres enracinés exposée par F. Chapoton et M. Livernet [START_REF] Chapoton | Pre-Lie algebras and the rooted trees operad[END_REF]. Nous montrons que cette matrice est unipotente et trouvons une expression explicite pour les coefficients de cette matrice, en adaptant une procédure suggérée par K. Ebrahimi-Fard et D. Manchon pour l'algèbre magmatique libre. Nous construisons une structure d'algèbre pré-Lie sur l'algèbre de Lie libre L(E) engendrée par un ensemble E, donnant une présentation explicite de L(E) comme quotient de l'algèbre pré-Lie libre T E , engendrée par les arbres enracinés (non-planaires) E-décorés, par un certain idéal I. Nous étudions les bases de Gröbner pour les algèbres de Lie libres dans une présentation à l'aide d'arbres. Nous décomposons la base d'arbres enracinés planaires E-décorés en deux parties O(J) et T (J), où J est l'idéal définissant L(E) comme quotient de l'algèbre magmatique libre engendrée par E. Ici, T (J) est l'ensemble des termes maximaux des éléments de J, et son complément O(J) définit alors une base de L(E). Nous obtenons un des résultats importants de cette thèse (Théorème 3.12) sur la description de l'ensemble O(J) en termes d'arbres. Nous décrivons des bases de monômes pour l'algèbre pré-Lie (respectivement l'algèbre de Lie libre) L(E), en utilisant les procédures de bases de Gröbner et la base de monômes pour l'algèbre pré-Lie libre obtenue dans le Chapitre 2. Enfin, nous étudions les développements de Magnus classique et pré-Lie, discutant comment nous pouvons trouver une formule de récurrence pour le cas pré-Lie qui intègre déjà l'identité pré-Lie. Nous donnons une vision combinatoire d'une méthode numérique proposée par S. Blanes, F. Casas, et J. Ros dans [START_REF] Blanes | Improved High Order Integrators based on the Magnus Expansion[END_REF], sur une écriture du développement de the enveloping algebra of L. [START_REF] Cayley | On the Theory of Analytical Forms called Trees[END_REF][START_REF] Chapoton | Pre-Lie algebras and the rooted trees operad[END_REF][START_REF] Chapoton | Enveloping algebras of pre-Lie algebras, Solomon Idempotents and the Magnus Formula[END_REF][START_REF] Connes | Hopf algebras, renormalization and noncommutative geometry[END_REF][START_REF] Jacobson | Basic Algebra II: Second Edition[END_REF][START_REF] Kac | Infinite dimensional Lie algebras[END_REF][START_REF] Koszul | Domaines bornés homogènes et orbites de groupes de transformations affines[END_REF]. ϕ 0 the canonical Lie algebra homomorphism from L to U(L).

13, 14.

T (V) the tensor algebra of a vector space V. 13, 14, 33.

S (V)

the symmetric algebra of a vector space V.

L(E)

the free K-Lie algebra generated by a set E. T e1 pl the subset of all planar rooted trees with "even or 1 fertility".

68, 71, 78.

T e1 pl the linear span of T e1 pl . 68.

T E, e1 pl the subset of all planar E-decorated rooted trees with "even or 1 fertility".

78, 79.

F forest of (non-planar) rooted trees.

w(F)

the weight of a forest F.

F

the linear span of the set of all (non-planar) forests.

Introduction en Français

Les structures d'algèbre pré-Lie apparaissent dans des domaines divers des mathématiques : la géométrie différentielle, la théorie quantique des champs , les équations différentielles. Elles ont été étudiées intensivement récemment; nous nous référons e.g. aux articles de survol : [START_REF] Burde | Left symmetric algebras, or pre-Lie algebras in geometry and physics[END_REF][START_REF] Cartier | Vinberg Algebras, Lie groups and combinatorics[END_REF][START_REF] Manchon | Algebraic Background for Numerical Methods, Control Theory and Renormalization[END_REF]. Les algèbres pré-Lie libres avaient déjà été étudiées dès 1981 par A. Agrachev et R. V. Gamkrelidze dans leur travail conjoint "Chronological algebras and nonstationary vector fields" [1], et aussi par D. Segal dans [46]. En particulier, ces deux articles donnent une con- struction de bases de monômes, avec des approches différentes. En outre, les arbres enracinés sont un sujet classique, étroitement lié aux algèbres pré-Lie. Ils apparaissent par exemple dans l'étude des champs de vecteurs [START_REF] Cayley | On the Theory of Analytical Forms called Trees[END_REF], l'analyse numérique [START_REF] Ch | Runge-Kutta methods and renormalization[END_REF], et plus récemment dans la théorie quantique des champs [START_REF] Connes | Hopf algebras, renormalization and noncommutative geometry[END_REF]. Des bases pour les algèbres pré-Lie libres en termes d'arbres en- racinés ont été introduites par F. Chapoton et M. Livernet dans [START_REF] Chapoton | Pre-Lie algebras and the rooted trees operad[END_REF], utlisant le point de vue des opérades. A. Dzhumadil'Daev et C. Löfwall ont décrit indépendamment deux bases pour des algèbres pré-Lie libres, une base utilisant le concept d'arbres enracinés, et l'autre obtenue en considérant une base pour l'algèbre (non-associative) libre modulo la relation pré-Lie [19].

Cette thèse consiste en quatre chapitres principaux. Le Chapitre 1 est un chapitre préliminaire qui contient, à son tour, quatre sections, dans lesquelles nous rappelons certaines notions importantes dont nous avons besoin dans cette thèse : les algèbres magmatiques libres, les arbres enracinés, les algèbres de Lie, les algèbres pré-Lie, les bases de Gröbner, . . . . Le Chapitre 2 est une version généralisée de notre travail dans un article publié au Séminaire Lotharingien de Combinatoire [START_REF] Mahdi | Monomial Bases for Free Pre-Lie Algebras[END_REF]. Le contenu de ce chapitre est détaillé dans son introduction. Dans ce chapitre, nous décrivons une méthode explicite pour trouver des bases de monômes convenables pour les algèbres pré-Lie libres avec plusieurs générateurs, utilisant le travail conjoint [START_REF] Agrachev | Chronological algebras and nonstationary vector fields[END_REF] de A. Agrachev et R. Gamkrelidze, l'article [START_REF] Mahdi | Monomial Bases for Free Pre-Lie Algebras[END_REF] s'en tenant au cas d'un seul générateur.

Rappelons que l'éspace T E engendré par les arbres enracinés (non-planaires) décorés par un ensemble E forme avec l'opération de greffe "→" l'algèbre pré-Lie libre engendrée par E [START_REF] Chapoton | Pre-Lie algebras and the rooted trees operad[END_REF]19]. Un monôme dans l'algèbre pré-Lie libre engendrée par E est un mot parenthésé constitué des générateurs { a : a ∈ E} et l'opération de greffe pré-Lie " → ", par exemple, dans le cas avec un seul générateur :

( → ) → → ( → ) = → → = → + = + 2 + + + .
Nous sommes intéressés en particulier à des bases de monômes que nous appellerons "bases arborescentes". A chaque monôme nous pouvons associer un "terme d'énergie minimale" en remplaçant l'opération de greffe " → " par le produit de Butcher " ". Une base de monômes de T E sera appelée une "base arborescente" si les termes d'énergie minimale de chaque monôme redonnent la base d'arbres de Chapoton-Livernet de T E . Nous montrons que les bases arborescentes sont en correspondance biunivoque avec les choix t → S (t) d' un représentant planaire pour chaque arbre t. Nous donnons une expression explicite pour les coefficients de ces monômes dans la base d'arbres enracinés, présentant ainsi une matrice carrée [[β S (s, t)]] s, t∈T E n pour chaque degré n > 0, utilisant un travail de K. Ebrahimi-Fard et D. Manchon (non publié) rappelé dans Section 2.1. Ici nous allons supposer que chaque générateur est de degré 1, sauf dans les Paragraphes 2.2.1 et 2.2.2.

Le Chapitre 3 contient trois sections principales. Dans ce chapitre, nous considérons à la fois l'algèbre pré-Lie libre T E , → et l'algèbre de Lie libre L(E), [•, •] engendrées par un ensemble :

E = E 1 ⊔ E 2 ⊔ E 3 ⊔ • • • ,
où chaque E j est un ensemble fini de générateurs de degré j. Il s'avère que l'algèbre de Lie libre L(E) possède une structure pré-Lie naturelle. Ce résultat semble être nouveau (rappelons que si n'importe quelle algèbre pré-Lie induit une structure de Lie correspondante par antisymétrisation du produit pré-Lie, l'inverse est rarement vrai [START_REF] Burde | Left symmetric algebras, or pre-Lie algebras in geometry and physics[END_REF]). Nous donnons une présentation explicite de L(E) comme le quotient T E /I, où I est l'idéal de T E engendré par des "relations d'anti-symétrie pondérée" :

|s|s → t + |t|t → s.
Nous rappelons le travail de T. Mora [START_REF] Mora | An introduction to commutative and non-commutative Gröbner bases[END_REF] sur les bases de Gröbner, et nous l'adaptons à un contexte non-associatif magmatique, en suivant [START_REF] Drensky | Planar trees, free non-associative algebras, invariants, and elliptic integrals[END_REF]. Dans ce chapitre, nous décrivons des bases de monômes pour l'algèbre pré-Lie (respectivement de Lie libre) L(E), utilisant les procédures de bases de Gröbner et notre travail du Chapitre 2, sur la base de monômes pour l'algèbre pré-Lie libre T E .

Le Chapitre 4 est détaillé dans son introduction et se compose de quatre sections. Il est consacré au développement de Magnus, un outil important pour résoudre l'équation différentielle linéaire bien connue :

ẏ(t) := d dt y(t) = a(t)y(t), y(0) = 1.
De nombreux travaux ont été dédiés à l'écriture du développement de Magnus classique en terme de structures algèbriques et combinatoires : les algèbres de Rota-Baxter, les algèbres dendriformes, les algèbres pré-Lie, . . ., voir par exemple [START_REF] Ebrahimi-Fard | A Magnus-and Fer-type Formula in Dendriform Algebras[END_REF][START_REF] Ebrahimi-Fard | Dendriform Equations[END_REF][START_REF] Chapoton | Enveloping algebras of pre-Lie algebras, Solomon Idempotents and the Magnus Formula[END_REF]. Nous étudions ici une généralisation de ce dernier appelé le développement de Magnus pré-Lie, et nous donnons une étude brève sur ce développement dans ce chapitre. Un codage des termes du développement de Magnus classique et pré-Lie utilisant les arbres binaires planaires a été proposé par A. Iserles et S. P. No / rsett [START_REF] Iserles | No / rsett, On the solution of linear differential equations in Lie groups[END_REF]. K. Ebrahimi-Fard et D. Manchon ont proposé un autre codage par les arbres enracinés planaires [START_REF] Ebrahimi-Fard | Dendriform Equations[END_REF]. Certaines tentatives ont été faites pour réduire le nombre de termes de ce développement : nous discutons cette réduction dans les Sections 4.2, 4.3 en utilisant le codage de K. Ebrahimi-Fard avec D. Manchon [START_REF] Ebrahimi-Fard | A Magnus-and Fer-type Formula in Dendriform Algebras[END_REF], [START_REF] Ebrahimi-Fard | Dendriform Equations[END_REF], et un travail de F. Chapoton avec F. Patras [START_REF] Chapoton | Enveloping algebras of pre-Lie algebras, Solomon Idempotents and the Magnus Formula[END_REF]. La formule introduite par F. Chapoton et F. Patras dans leur travail [START_REF] Chapoton | Enveloping algebras of pre-Lie algebras, Solomon Idempotents and the Magnus Formula[END_REF] sur l'écriture du développement de Magnus pré-Lie, utilisant l'algèbre de Grossman-Larson, attire notre attention. Nous étudions cette formule brièvement dans les Sections 4.2, 4.3, et nous comparons ses termes avec d'autres termes du développement de Magnus pré-Lie obtenu par K. Ebrahimi-Fard et D. Manchon dans leur travail [START_REF] Ebrahimi-Fard | Dendriform Equations[END_REF]. Nous observons que cette formule est optimale jusqu'au degré 5, en ce qui concerne le nombre de termes du développement de Magnus pré-Lie.

Introduction

Pre-Lie algebra structures appear in various domains of mathematics: differential geometry, quantum field theory, differential equations. They have been studied intensively recently; we refer e.g. to the survey papers: [START_REF] Burde | Left symmetric algebras, or pre-Lie algebras in geometry and physics[END_REF][START_REF] Cartier | Vinberg Algebras, Lie groups and combinatorics[END_REF][START_REF] Manchon | Algebraic Background for Numerical Methods, Control Theory and Renormalization[END_REF]. Free pre-Lie algebras had already been studied as early as 1981 by A. Agrachev and R. V. Gamkrelidze in their joint work "Chronological algebras and nonstationary vector fields" [1], and also by D. Segal in [46]. In particular, both papers give a construction of monomial bases, with different approaches. Besides, rooted trees are a classical topic, closely connected to pre-Lie algebras. They appeared for example in the study of vector fields [START_REF] Cayley | On the Theory of Analytical Forms called Trees[END_REF], numerical analysis [START_REF] Ch | Runge-Kutta methods and renormalization[END_REF], and more recently in quantum field theory [START_REF] Connes | Hopf algebras, renormalization and noncommutative geometry[END_REF]. Bases for free pre-Lie algebras in terms of rooted trees were introduced by F. Chapoton and M. Livernet in [START_REF] Chapoton | Pre-Lie algebras and the rooted trees operad[END_REF], using the point of view of operads. A. Dzhumadil'Daev and C. Löfwall described independently two bases for free pre-Lie algebras, one using the concept of rooted trees, and the other obtained by considering a basis for the free (non-associative) algebra modulo the pre-Lie relation [19]. This thesis consists in four main chapters. Chapter 1 is a preliminary chapter that contains, in turn, four sections, in which we recall some important topics that we need in this thesis: free magmatic algebras, rooted trees, Lie algebras, pre-Lie algebras, Gröbner bases and others.

Chapter 2 is a generalized version of our work in a published paper in Séminaire Lotharingien de Combinatoire [START_REF] Mahdi | Monomial Bases for Free Pre-Lie Algebras[END_REF]. The contents of this chapter are detailed in its introduction. In this chapter, we describe an explicit method for finding suitable monomial bases for free pre-Lie algebras with several generators, using the joint work [START_REF] Agrachev | Chronological algebras and nonstationary vector fields[END_REF] of A. Agrachev and R. Gamkrelidze, the paper [START_REF] Mahdi | Monomial Bases for Free Pre-Lie Algebras[END_REF] sticking to the single generator case.

Recall that the space T E spanned by (non-planar) rooted trees decorated by a set E forms with the grafting operation " → " the free pre-Lie algebra generated by E [START_REF] Chapoton | Pre-Lie algebras and the rooted trees operad[END_REF]19]. A monomial in the free pre-Lie algebra generated by E is a parenthesized word built up from the generators { a : a ∈ E} and the pre-Lie grafting operation " → ", for example, in the single generator case:

0. INTRODUCTION ( → ) → → ( → ) = → → = → + = + 2 + + + .
We are interested in particular monomial bases which will be called "tree-grounded". To each monomial we can associate a "lower-energy term" by replacing the grafting operation "→" by the Butcher product " ". A monomial basis of T E will be called "tree-grounded" if the lower-energy terms of each monomial give back the Chapoton-Livernet tree basis of T E . We show that tree-grounded monomial bases are in one-to-one correspondence with choices t → S (t) of a planar representative for each tree t. We give an explicit expression for the coefficients of these monomials in the basis of rooted trees, thus exhibiting a square matrix [[β S (s, t)]] s, t∈T E n for each degree n > 0, using the joint work of K. Ebrahimi-Fard and D. Manchon (unpublished) reviewed in Section 2.1. Here we will suppose that each generator is of degree 1, except in Paragraphs 2.2.1 and 2.2.2.

Chapter 3 contains three main sections. In this chapter, we consider both the free pre-Lie algebra T E , → and the free Lie algebra L(E), [•, •] generated by a set:

E = E 1 ⊔ E 2 ⊔ E 3 ⊔ • • • ,
where each E j is a finite set of generators of degree j. It turns out that the free Lie algebra L(E) possesses a natural pre-Lie structure. This result seems to be new (recall that if any pre-Lie algebra yields a corresponding Lie structure by antisymmetrizing the pre-Lie product, the converse is rarely true [START_REF] Burde | Left symmetric algebras, or pre-Lie algebras in geometry and physics[END_REF]). We give the explicit presentation of L(E) as the quotient T E /I, where I is the ideal of T E generated by "weighted anti-symmetry relations":

|s|s → t + |t|t → s.
We review the work of T. Mora [START_REF] Mora | An introduction to commutative and non-commutative Gröbner bases[END_REF] on Gröbner bases, and adapt it to non-associative, magmatic context, following [START_REF] Drensky | Planar trees, free non-associative algebras, invariants, and elliptic integrals[END_REF]. In this chapter, we describe monomial bases for the pre-Lie (respectively free Lie) algebra L(E), using the procedures of Gröbner bases and our work described in Chapter 2, in the monomial basis for the free pre-Lie algebra T E . Chapter 4 is detailed in its introduction by four sections. It is dedicated to study the so-called Magnus expansion, an important tool to solve the well-known linear differential equation:

ẏ(t) := d dt y(t) = a(t)y(t), y(0) = 1. (0.1)
Many works have been raised to write the classical Magnus expansion in terms of algebrocombinatorial structures: Rota-Baxter algebras, dendriform algebras, pre-Lie algebras and others, see for example [START_REF] Ebrahimi-Fard | A Magnus-and Fer-type Formula in Dendriform Algebras[END_REF][START_REF] Ebrahimi-Fard | Dendriform Equations[END_REF][START_REF] Chapoton | Enveloping algebras of pre-Lie algebras, Solomon Idempotents and the Magnus Formula[END_REF] for more details about these works. Particularly, we study a generalization of the latter called pre-Lie Magnus expansion, and we give a brief survey about this expansion in this chapter. An approach has been developed to encode the terms of the classical and pre-Lie Magnus expansions respectively, by A. Iserles with S. P. No / rsett using planar binary trees [START_REF] Iserles | No / rsett, On the solution of linear differential equations in Lie groups[END_REF], and by K. Ebrahimi-Fard with D. Manchon using planar rooted trees [START_REF] Ebrahimi-Fard | Dendriform Equations[END_REF] respectively. Some attempts have been made to reduce the number of terms of this expansion: we discuss in Sections 4.2, 4.3 this reduction, using the pre-Lie structure corresponding to the works of K. Ebrahimi-Fard with D. Manchon [START_REF] Ebrahimi-Fard | A Magnus-and Fer-type Formula in Dendriform Algebras[END_REF], [START_REF] Ebrahimi-Fard | Dendriform Equations[END_REF], and F. Chapoton with F. Patras [START_REF] Chapoton | Enveloping algebras of pre-Lie algebras, Solomon Idempotents and the Magnus Formula[END_REF].

The formula introduced by F. Chapoton and F. Patras in their work [START_REF] Chapoton | Enveloping algebras of pre-Lie algebras, Solomon Idempotents and the Magnus Formula[END_REF] on the writing of the pre-Lie Magnus expansion, using the so-called Grossman-Larson algebra, attracts our attention. We study this formula briefly in Sections 4.2, 4.3, and we compare its terms with another pre-Lie Magnus expansion terms obtained by K. Ebrahimi-Fard and D. Manchon in their work [START_REF] Ebrahimi-Fard | Dendriform Equations[END_REF]. We observe that this formula can be considered as optimal up to degree five, with respect to the number of terms in the pre-Lie Magnus expansion.

In the last section of Chapter 4, we look at the pre-Lie Magnus expansion in the free Lie algebra L(E). The weighted anti-symmetry relations lead to a further reduction of the number of terms. The particular case of one single generator in each degree is closely related to the work of S. Blanes, F. Casas and J. Ros [START_REF] Blanes | Improved High Order Integrators based on the Magnus Expansion[END_REF]. We give a combinatorial version of this work of the three authors, using our work described in Chapter 3, in the monomial basis of free Lie algebra L(E).

CHAPTER 1

Preliminaries

The aim of this preliminary chapter is to review some basics that we need in this thesis.

Free magmas and free magmatic algebras

Definition 1.1. A magma is a set M together with a binary operation "•", without any property imposed.

Let E be a set. The free magma over E is the magma M(E) generated by E. The free magma M(E) has the following universal property: for any other magma N with a map f : E → N there is a unique magmatic extension of f from M(E) into N. It can be presented as the set of well-parenthesized words on E with letters in the alphabet E, endowed with the concatenation product [START_REF] Bourbaki | Groupes et algèbres de Lie, 2: Algèbres de Lie libres[END_REF] [START_REF] Ch | Free Lie algebras[END_REF].

Denote by M E the linear span (over some base field K) of the free magma M(E). The space M E forms a free algebra, together with the product "•" of the magma, which is called the free magmatic algebra.

Trees

In graph theory, a tree is a undirected connected finite graph, without cycles [START_REF] Ebrahimi-Fard | On an extension of Knuth's rotation correspondence to reduced planar trees[END_REF]. A rooted tree is defined as a tree with one designated vertex called the root. The other remaining vertices are partitioned into k ≥ 0 disjoint subsets such that each of them in turn represents a rooted tree, and a subtree of the whole tree. This can be taken as a recursive definition for rooted trees, widely used in computer algorithms [START_REF] Knuth | The art of computer programming I. Fundamental algorithms[END_REF]. Rooted trees stand among the most important structures appearing in many branches of pure and applied mathematics.

In general, a tree structure can be described as a "branching" relationship between vertices, much like that found in the trees of nature. Many types of trees defined by all sorts of constraints on properties of vertices appear to be of interest in combinatorics and in related areas such as formal logic and computer science.

Planar binary trees. Definition 1.2.

A planar binary tree is a finite oriented tree embedded in the plane, such that each internal vertex has exactly two incoming edges and one outgoing edge. One of the internal vertices, called the root, is a distinguished vertex with two incoming edges and one edge, like a tail at the bottom, not ending at a vertex.

The incoming edges in this type of trees are internal (connecting two internal vertices), or external (with one free end). The external incoming edges are called the leaves. We give here some examples of planar binary trees:

. . . , where the single edge " " is the unique planar binary tree without internal vertices. The degree of any planar binary tree is the number of its leaves. Denote by T bin pl (respectively T bin pl ) the set (respectively the linear span) of planar binary trees.

Define the grafting operation "∨" on the space T bin pl to be the operation that maps any planar binary trees t 1 , t 2 into a new planar binary tree t 1 ∨ t 2 , which takes the Y-shaped tree replacing the left (respectively the right) branch by t 1 (respectively t 2 ), see the following examples:

∨ = , ∨ = , ∨ = , ∨ = , ∨ = .
The number of binary trees of degree n is given by the Catalan number c n = (2n)! (n+1)!n! , where the first ones are 1, 1, 2, 5, 14, 42, 132, . . .. This sequence of numbers is the sequence A000108 in [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF].

Let E be a (non-empty) set. The free magma M(E) generated by E can be described as the set of planar binary trees with leaves decorated by the elements of E, together with the "∨" product described above [START_REF] Knuth | The art of computer programming I. Fundamental algorithms[END_REF][START_REF] Ph | Analytic Combinatorics[END_REF]. Moreover, the linear span T bin,E pl , generated by the trees of the magma M(E) = T bin,E pl defined above, equipped with the grafting "∨" is a description of the free magmatic algebra.

Planar and non-planar rooted trees.

Definition 1.3. For any positive integer n, a rooted tree of degree n, or simply n-rooted tree, is a finite oriented tree together with n vertices. One of them, called the root, is a distinguished vertex without any outgoing edge. Any vertex can have arbitrarily many incoming edges, and any vertex distinct from the root has exactly one outgoing edge. Vertices with no incoming edges are called leaves.

A rooted tree is said to be planar, if it is endowed with an embedding in the plane. Otherwise, its called a (non-planar) rooted tree. Definition 1.4. Let E be a (non-empty) set. An E-decorated rooted tree is a pair (t, d) of a rooted tree t together with a map d : V(t) → E, which decorates each vertex v of t by an element a of E, i.e. d(v) = a, where V(t) is the set of all vertices of t.

Here are the planar (undecorated) rooted trees up to five vertices:

• • •

From now on, we will consider that all our trees are decorated, except for some cases in which we will state the property explicitly. Denote by T E pl (respectively T E ) the set of all planar (respectively non-planar) decorated rooted trees, and T E pl (respectively T E ) the linear space spanned by the elements of T E pl (respectively T E ). Any rooted tree σ with branches σ 1 , . . . , σ k and a root a , can be written as:

σ = B +, a (σ 1 • • • σ k ), (1.1)
where B +, a is the operation which grafts a monomial σ 1 • • • σ k of rooted trees on a common root decorated by an element a in E, which gives a new rooted tree by connecting the root of each σ i , by an edge, to the new root. The planar rooted tree σ in formula (1.1) depends on the order of the branch planar trees σ j , whereas this order is not important for the corresponding (non-planar) tree.

The number of trees in T E pl is the same than in T bin,E pl , there is a one-to-one bijection between them (see the Subsection 1.2.3). On the other hand, for any homogeneous component T n of (non-planar) undecorated rooted trees of degree "n", for n ≥ 1, the number of trees in T n is given by the sequence: 1, 1, 2, 4, 9, 20, 48, . . . , which is sequence A000081 in [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF].

Definition 1.5. The (left) Butcher product " • ց" of any planar rooted trees σ and τ is defined by:

σ • ցτ := B +, a (στ 1 • • • τ k ), (1.2)
where τ 1 , . . . , τ k ∈ T E pl , such that τ = B +, a (τ 1 • • • τ k ). It maps the pair of trees (σ, τ) into a new planar rooted tree induced by grafting the root of σ, on the left via a new edge, on the root of τ.

The usual product " " in the non-planar case, given by the same formula (1.2), is known as the Butcher product. It is non-associative permutative (NAP), i.e. it satisfies the following identity:

s (s ′ t) = s ′ (s t),
for any (non-planar) trees s, s ′ , t. Indeed, for t = B +, a (t 1 • • • t k ), where t 1 , ..., t k in T E , we have:

s (s ′ t) = s (B +, a (s ′ t 1 • • • t k )) = B +, a (ss ′ t 1 • • • t k ) = B +, a (s ′ s t 1 • • • t k ) = s ′ (B +, a (s t 1 • • • t k )) = s ′ (s t).

Rotation correspondence of Knuth.

D. E. Knuth in his work [START_REF] Knuth | The art of computer programming I. Fundamental algorithms[END_REF] described a relation between the planar binary trees and the planar rooted trees, in the case of non-decorated trees. He introduced a bijection Φ : T bin pl -→ T pl called the rotation correspondence 1 , recursively defined by: Φ( ) = , and Φ(t

1 ∨ t 2 ) = Φ(t 1 ) • ց Φ(t 2 ), ∀t 1 , t 2 ∈ T bin pl . (1.3)
Let us compute a few terms:

Φ( ) = Φ( ) • ց Φ( ) = , Φ( ) = Φ( ) • ց Φ( ) = , Φ( ) = , Φ( ) = , Φ( ) = , Φ( ) = , Φ( ) = , Φ( ) = .
The bijection given in (1.3) realizes the free magma M(E) as the set of planar rooted trees with E-decorated vertices, endowed with the left Butcher product. Also, the linear span T E pl , generated by the planar trees of the magma M(E), forms with the product " • ց" another description of the free magmatic algebra.

Lie algebras

In the spirit of Felix Klein's (1849-1925) "Erlangen Program", any Lie group G is a group of symmetries of some class of differentiable manifolds. The corresponding infinitesimal transformations are given by the Lie algebra of G, which is the set of left-invariant vector fields on G. The problem of classification of groups of transformations has been considered by S. Lie (1842-1899) not only for subgroups of GL n , but also for infinite dimensional groups [START_REF] Kac | Infinite dimensional Lie algebras[END_REF].

The problem of classification of simple finite-dimensional Lie algebras over the field of complex numbers was solved at the end of the 19th century by W. Killing (1847Killing ( -1923) and E. Cartan (1869Cartan ( -1951)). The central figure of the origins of the theory of the structure of Lie algebras is W. Killing, whose paper in four parts laid the conceptual foundations of the theory. In 1884, Killing introduced the concept of a Lie algebra independently of Lie and formulated the problem of determining all possible structures for real, finite dimensional Lie algebras. The joint work of Killing and Cartan establishes the foundations of the theory. Killing's work contained many gaps which Cartan succeeded in filling [START_REF] Hawkins | Wilhelm Killing and the structure of Lie algebras[END_REF], [START_REF] Kac | Infinite dimensional Lie algebras[END_REF]. An attempt has been made by Killing and Cartan as well as others, such as S. Lie and F. Engel and many others, to provide the basis for a better historical appreciation of the early development of the theory and some of its various applications.

In this section, we recall some basics in Lie algebras that we need in this thesis. 1 For more details about the rotation correspondence see [START_REF] Knuth | The art of computer programming I. Fundamental algorithms[END_REF]Paragraph 2.3.2], [START_REF] Marckert | The rotation correspondence is asymptotically a dilatation[END_REF] and [START_REF] Ph | Analytic Combinatorics[END_REF]Paragraph 1.5.3].

Definition 1.6. A Lie algebra over a field K, of characteristic different from 2, is a K-vector space L , with a K-bilinear mapping [• , •] : L × L → L, (x, y) -→ [x, y] called a Lie bracket, satisfying the following properties:

[x, x] = 0 (1.4) [[x, y], z] + [[y, z], x] + [[z, x], y] = 0 (1.5)
for all x, y, z ∈ L. The identity (1.5) is called the Jacobi identity.

The identity (1.4) induces the following identity, which is called the anti-symmetry identity:

[x, y] + [y, x] = 0 (1.6)
Indeed, using (1.4) and the bilinearity of [ One of the important properties possessed by Lie algebras, is that we can associate to each Lie algebra L an associative algebra which has a universal property stated in the following Proposition.

Proposition 1.1. Let L be a Lie algebra over K. There exists an associative algebra U(L) over K and a Lie algebra homomorphism ϕ 0 : L → U(L) having the following property: for any associative algebra A and any Lie algebra homomorphism ϕ : L → A, there is a unique algebra homomorphism f : U(L) → A making the diagram in Figure 1 Proof. This algebra U(L) is called the enveloping algebra of L. The reader can find the proof of this Proposition detailed in [44, Proposition 0.1]. In the following, we shall review the part of the proof corresponding to the existence of the algebra U(L), to understand what means this type of algebras, i.e. the enveloping algebra: denote by T = T (L) the tensor algebra of L over K, where:

T (L) = n≥0 L ⊗n .
The algebra T has a natural structure of associative algebra with unit. Define I to be the (twosided) ideal of T generated by the elements on the form:

x ⊗ yy ⊗ x -[x, y], for any x, y ∈ L.

(1.8)

Set U(L) = T/I, and let ϕ 0 : L → U(L) be the composition ϕ 0 = q • i, where i is the canonical inclusion L → T (L) and q is the canonical quotient map T → T/I that is a surjective algebra homomorphism. The map ϕ 0 is a Lie algebra homomorphism. Indeed, for any x, y ∈ L, we have:

ϕ 0 ([x, y]) = q([x, y])
= q(x ⊗ yy ⊗ x) , by (1.8), and since Ker q =I, = q(x)q(y)q(y)q(x)

= [q(x), q(y)] , using (1.7),

= [q • i(x), q • i(y)] = [ϕ 0 (x), ϕ 0 (y)].
The map f is defined as follows: the linear map ϕ uniquely extends to an algebra morphism f : T (L) → A, defined by:

f (x 1 ⊗ • • • ⊗ x n ) := ϕ(x 1 ) • • • ϕ(x n ),
which factorizes through the ideal I.

Here, we give the well known Theorem called the Poincaré-Birkhoff-Witt Theorem which we need it in our next work in this thesis, without giving its proof. We refer the reader to the references [START_REF] Cartier | La théoreme de Poincaré-Birkhoff-Witt. Séminaire Sophus Lie[END_REF][START_REF] Jacobson | Lie algebras[END_REF][START_REF] Humphreys | Introduction to Lie algebras and representation theory[END_REF][START_REF] Dixmier | Algèbres Enveloppantes[END_REF] for more details about this Theorem. Theorem 1.2. Let L be a K-Lie algebra, such that the K-vector space L is endowed with a totally ordered basis {x i } i∈I . Then the enveloping algebra U(L) of L is a K-vector space with basis the set of decreasing products ϕ 0 (x i 1 )

• • • ϕ 0 (x i n ), for i 1 , . . . , i n ∈ I, i 1 ≥ • • • ≥ i n , n ≥ 0,
where ϕ 0 : L → U(L) is the natural Lie algebra homomorphism. Corollary 1.3. Let L be a K-Lie algebra. Let U(L) be its enveloping algebra and ϕ 0 : L → U(L) be the canonical Lie homomorphism. Then ϕ 0 is injective. By Corollary 1.3, we can consider a Lie algebra as a Lie subalgebra of its enveloping algebra [START_REF] Ch | Free Lie algebras[END_REF].

Free Lie algebras.

The Lie algebra of Lie polynomials, showed by E. Witt (1911Witt ( -1991)), is actually the free Lie algebra. The first appearance of Lie polynomials was at the turn of the century in the work of Campbell, Baker and Hausdorff on the exponential mapping in a Lie group, when the well-known result "Campbell-Baker-Hausdorff formula" appeared. For more details about a historical review of free Lie algebras, we refer the reader to the reference [START_REF] Ch | Free Lie algebras[END_REF] and the references therein.

Definition 1.7. Let L be a Lie algebra over a field K and E be a (non-empty) set , and let i : E → L be a map. A free Lie algebra is a pair L, i , satisfying the following universal property: for any Lie algebra L ′ and any mapping f : E → L ′ , there is a unique Lie algebra homomorphism f : L → L ′ which makes the following diagram commute:

E i / / f @ @ @ @ @ @ @ @ L f L ′ Figure 1.2.
The universal property of the free Lie algebra.

It is unique up to an isomorphism. If L is a K-Lie algebra and E ⊆ L, then we say that E freely generates L if L, i is free, where i is the canonical injection from E to L.

We give here some important properties of the free Lie algebra, presented as Theorems without giving the complete proofs, just some details that we need in this thesis. We refer the reader to the reference [44, Theorem 0.4, Theorem 0.5] for more details about these Theorems.

Theorem 1.4. For any (non-empty) set E, there exists a free Lie algebra, call it L(E), on E, which is unique up to isomorphism. Moreover, this free Lie algebra is naturally a graded Kvector space, the mapping i, in Figure 1.2, is injective. The free vector subspace generated by E = i(E) is the component of elements of L(E) of degree "1", and L(E) itself generated, as a Lie algebra, by E.

Proof. We will review here the part of the proof, that we need, corresponding to the existence or the construction of this type of Lie algebras. The details of this proof exist in [44, Theorem 0.4]. Let E be any (non-empty) set, and A E be the free (non-commutative, non-associative) K-algebra. Here, we can consider A E as the free magmatic algebra M E generated linearly by M(E), the free magma over E. Define I to be the (two-sided) ideal of M E generated by the elements:

(xy)z + (yz)x + (zx)y, and xx, for x, y, z ∈ M E .

(1.9)

Set L(E) := M E /I. Obviously, L(E) with the multiplication inherited from M E forms a Lie algebra over K. Moreover, L(E), with the canonical mapping E → L(E), is the free Lie algebra over E.

Theorem 1.5. The enveloping algebra U(L) of the free Lie algebra L(E) is a free associative algebra on E. The Lie algebra homomorphism ϕ 0 : L(E) → U(L) is injective, and ϕ 0 (L(E)) is the Lie subalgebra of U(L) generated by j(E), where j := ϕ 0 • i.

Gröbner bases.

The Gröbner bases theory was introduced in 1965 by Bruno Buchberger for ideals in polynomial rings and an algorithm called Buchberger algorithm for their computation. This theory contributed, since the end of the seventies, in the development of computational techniques for the symbolic solution of polynomial systems of equations and in the development of effective methods in Algebraic Geometry and Commutative Algebra. Moreover, this theory has been generalized to free non-commutative algebra and to various non-commutative algebras of interest in Differential Algebra, e.g. Weyl algebras, enveloping algebras of Lie algebras [START_REF] Mora | An introduction to commutative and non-commutative Gröbner bases[END_REF], and so on.

The attempt to imitate Gröbner basis theory for non-commutative algebras works fine up to the point where the termination of the analogue to the Buchberger algorithm can be proved. Gröbner bases and Buchberger algorithm have been extended, for the first time, to ideals in free non-commutative algebras by G. Bergman in 1978. Later, F. Mora in 1986 made precise in which sense Gröbner bases can be computed in free non-commutative algebras [START_REF] Mora | An introduction to commutative and non-commutative Gröbner bases[END_REF]. The construction of finite Gröbner bases for arbitrary finitely generated ideals in non-commutative rings is possible in the class of solvable algebras2 . This class comprises many algebras arising in mathematical physics such as: Weyl algebras, enveloping algebras of finite-dimensional Lie algebras, and iterated skew polynomial rings. Gröbner bases were studied, in these algebras, for special cases by Apel and Lassner in 1985, and in full generality by Kandri-Rody and Weispfenning in 1990 [START_REF] Becker | Gröbner Bases[END_REF].

Recently, V. Drensky and R. Holtkamp used Gröbner theory in their work [START_REF] Drensky | Planar trees, free non-associative algebras, invariants, and elliptic integrals[END_REF] for a nonassociative, non-commutative case (the magmatic case). Whereas, L. A. Bokut, Yuqun Chen and Yu Li, in their work [START_REF] Bokut | Gröbner-Shirshov bases for Vinberg-Koszul-Gerstenhaber right-symmetric algebras[END_REF], give Gröbner-Shirshov basis for a right-symmetric algebra (pre-Lie algebra). The theory of Gröbner-Shirshov bases was invented by A. I. Shirshov for Lie algebras in 1962 [START_REF] Shirshov | Some Algorithmic Problems for Lie Algebras[END_REF].

We try in our work, in section 3.2, to describe a monomial basis in tree version for the free Lie (respectively pre-Lie) algebras using the procedures of Gröbner bases, comparing with the one (i.e. the monomial basis) obtained for the free pre-Lie algebra in section 2.2. We need here to review some basics for the theory of Gröbner bases. Definition 1.8. Let M(E), • be the free magma generated by E. A total order < on M(E) is said to be monomial if it satisfies the following property:

for any x, y, z ∈ M(E), if x < y, then x • z < y • z and z • x < z • y, ( 1.10)
i.e. it is compatible with the product in M(E).

This property, in (1.10), implies that for any x, y ∈ M(E) then x < x • y. An order is called a well-ordering if every strictly decreasing sequence of monomials is finite, or equivalently if every non-empty set of monomials has a minimal element.

Let M E be the K-linear span of the free magma M(E), and I be any magmatic (two-sided) ideal of M E . For any element f = x∈M(E) λ x x (finite sum) in I, define T ( f ) to be the maximal term of f with respect to a given monomial order defined on M(E), namely

T ( f ) = λ x 0 x 0 , with x 0 = max{x ∈ M(E), λ x 0}. Denote T (I) := {T ( f ) : f ∈ I} the set
of all maximal terms of elements of I. Note that the set T (I) forms a (two-sided) ideal of the magma M(E) [START_REF] Mora | An introduction to commutative and non-commutative Gröbner bases[END_REF]. Define the set O(I) := M(E)\T (I). We have that the magma M(E) = T (I) ∪ O(I) is the disjoint union of T (I), O(I) respectively. As a consequence, we get that:

M E = Span K (T (I)) ⊕ Span K (O(I)).
(1.11)

Define a linear mapping ϕ from I into Span K (T (I)), which makes the following diagram commute:

I i / / ϕ M E = / / Span K (T (I)) ⊕ Span K (O(I)) P Span K (T (I)) Figure 1.3. Definition of ϕ.
where P is the projection map. Then the mapping ϕ is defined by: 12), we note that ϕ is surjective. Hence, ϕ is an isomorphism of vector spaces. Thus, we can deduce from the formula (1.11):

ϕ( f ) = x∈T (I) α x x, for f ∈ I, ( 1
M E = I ⊕ Span K (O(I)). (1.13)
In Section 3.2, we will give a tree version of the monomial well-ordering with a review of Mora's work [START_REF] Mora | An introduction to commutative and non-commutative Gröbner bases[END_REF], in the case of rooted trees.

Pre-Lie algebras

The concept of "Pre-Lie algebras" appeared in many works under various names. E. B. Vinberg and M. Gerstenhaber in 1963 independently presented the concept under two different names; "right symmetric algebras" and "pre-Lie algebras" respectively [START_REF] Vinberg | The Theory of homogeneous convex cones[END_REF][START_REF] Gerstenhaber | The cohomology structure of an associative ring[END_REF]. Other denominations, e.g. "Vinberg algebras", appeared since then. "Chronological algebras" is the term used by A. Agrachev and R. V. Gamkrelidze in their work on nonstationary vector fields [START_REF] Agrachev | Chronological algebras and nonstationary vector fields[END_REF]. The term "pre-Lie algebras" is now the standard terminology. The Lie algebra of a real connected Lie group G admits a compatible pre-Lie structure if and only if G admits a left-invariant affine structure [START_REF] Burde | Left symmetric algebras, or pre-Lie algebras in geometry and physics[END_REF]Proposition 2.31], see also the work of J. L. Koszul [START_REF] Koszul | Domaines bornés homogènes et orbites de groupes de transformations affines[END_REF] for more details about the pre-Lie structure, in a geometrical point of view. We shall now review some basics and topics related to pre-Lie algebras. Definition 1.9. Let PL be a vector space over a field K together with a bilinear operation "⊲". Then PL is said to be a left pre-Lie algebra, if the map ⊲ satisfies the following identity:

(x ⊲ y) ⊲ z -x ⊲ (y ⊲ z) = (y ⊲ x) ⊲ z -y ⊲ (x ⊲ z), ∀x, y, z ∈ PL.
(1.14)

The identity (1.14) is called the left pre-Lie identity, and it can be written as:

L [x,y] = [L x , L y ], ∀x, y ∈ PL, (1.15)
where for every element x in PL, the linear transformation L x of the vector space PL is defined by L x (y) = x ⊲ y, ∀y ∈ PL, and [x, y] = x ⊲ yy ⊲ x is the commutator of the elements x and y in PL. The usual commutator [L x , L y ] = L x L y -L y L x of the linear transformations of PL defines a structure of Lie algebra over K on the vector space L(PL) of all linear transformations of PL. For any pre-Lie algebra PL, the bracket [•, •] satisfies the Jacobi identity, hence induces a structure of Lie algebra on PL.

As a particular example of pre-Lie algebras, take the linear space of the set of all (nonplanar) E-decorated rooted trees T E which has a structure of pre-Lie algebra together with the product "→" defined as follows:

Definition 1.10. The grafting product " → " is a bilinear map defined on the vector space T E such that:

s → t = v ∈V(t) s → v t, (1.16)
for any s, t ∈ T E , where "s → v t" is the (non-planar) decorated rooted tree obtained by grafting the tree s on the vertex v of the tree t.

Example 1.1. For the case with one generator, we have:

→ = + , → = + .
In the space T spanned by the rooted trees, the grafting operation " → " satisfies the pre-Lie identity, since for any s, t, t ′ ∈ T, we have:

s → (t → t ′ ) -(s → t) → t ′ = s → ( v∈V(t ′ ) t → v t ′ ) -( u∈V(t) s → u t) → t ′ = v∈V(t ′ ) s → (t → v t ′ ) - u∈V(t) (s → u t) → t ′ = v∈V(t ′ ) v ′ ∈V(t ′′ ) s → v ′ (t → v t ′ ) - v∈V(t ′ ) u∈V(t) (s → u t) → v t ′ , [t ′′ = t → v t ′ ] = v∈V(t ′ ) v ′ ∈V(t ′ ) s → v ′ (t → v t ′ ),
Obviously symmetric in s and t. The same thing holds in the vector space T E spanned by E-decorated rooted trees.

Completed pre-Lie algebras.

In this paragraph, we recall some topics that we need in our work in Chapter 4, following the references [START_REF] Jacobson | Basic Algebra II: Second Edition[END_REF][START_REF] Agrachev | Chronological algebras and nonstationary vector fields[END_REF][START_REF] Manchon | Algebraic Background for Numerical Methods, Control Theory and Renormalization[END_REF]. Definition 1.11. Let V be a K-vector space endowed with a norm

|| • || : V → R + . A sequence {v n } of elements of V is called Cauchy sequence if given any real ε > 0, there exists a positive integer N = N(ε) such that: ||v m -v n || < ε, (1.17)
for all m, n ≥ N. V is said to be complete relative to the norm || • || if every Cauchy sequence of elements of V converges.

Let PL := n∈N PL n be a graded pre-Lie algebra, where PL n is the n-th component of this algebra. Denote by:

PL := ∞ n=1 PL n = a = ∞ n=1 a n : a n ∈ PL n , for n ≥ 1 ,
the completion of the graded algebra PL, where the elements of PL are formal series. This completion possesses a structure of pre-Lie algebra given by the natural extension of the product ⊲ defined as follows: for any a =

∞ n=1 a n , b = ∞ n=1 b n ∈ PL, a ⊲ b := ∞ n=2 n-1 i=1 a i ⊲ b n-i := lim N→∞ N n=2 n-1 i=1 a i ⊲ b n-i . (1.18)
Indeed, the right-hand side of (1.18) is the limit of a Cauchy sequence. The graded pre-Lie algebra PL is endowed with a compatible decreasing filtration PL = PL (1) ⊃ PL (2) ⊃ PL (3) ⊃ • • • , where: Val(a) := sup q : a ∈ PL (q) .

PL (q) := n≥q PL n , for all q ≥ 1, such that PL (p) ⊲ PL (q) ⊂ PL (p+q)
(1.19)

Let a, b be elements in PL, such that a ∈ PL p , b ∈ PL q with p < q, then:

(i) Val(a + b) = p, (ii) Val(a ⊲ b) ≥ Val(a) + Val(b) = p + q, this property is true for all a, b ∈ PL.
A metric function d(•, •) : PL × PL → R + can be defined on PL, using the map Val defined above, as follows:

d(a, b) = 2 -Val(a-b) , for any a, b ∈ PL.
(1.20)

The corresponding norm || • || on PL is defined by:

||a|| := 2 -Val(a)
, for any a ∈ PL.

(1.21)

The pre-Lie product ⊲ is continuous with respect to the metric d(•, •). Indeed, for given real numbers ε 1 , ε 2 > 0, and for any

a 1 , a 2 , b 1 , b 2 ∈ PL, if d(a 1 , b 1 ) < ε 1 and d(a 2 , b 2 ) < ε 2 , then: d(a 1 ⊲ a 2 , b 1 ⊲ b 2 ) ≤ d(a 1 ⊲ b 1 , a 2 ⊲ b 1 ) + d(a 2 ⊲ b 1 , a 2 ⊲ b 2 ), (by the triangle inequality of the metric), = 2 -Val(a 1 ⊲ b 1 -a 2 ⊲ b 1 ) + 2 -Val(a 2 ⊲ b 1 -a 2 ⊲ b 2 ) , (from the definition of d(•, •) above), = 2 -Val (a 1 -a 2 ) ⊲ b 1 + 2 -Val a 2 ⊲ (b 1 -b 2 ) , (since ⊲ is a bilinear), ≤ 2 -N , (where N = -log 2 (ε 1 + ε 2 )) = ε = ε 1 + ε 2 .
The space PL = ∞ k=1 PL (k) is a completed pre-Lie algebra, with respect to the norm ||•|| defined in (1.21) above. Any continuous bilinear operation extends the same way to the completion.

Free pre-Lie algebras.

Free pre-Lie algebras have been handled in terms of rooted trees by F. Chapoton and M. Livernet [START_REF] Chapoton | Pre-Lie algebras and the rooted trees operad[END_REF], who also described the pre-Lie operad explicitly, and by A. Dzhumadil'daev and C. Löfwall independently [19]. For an elementary version of the approach by Chapoton and Livernet without introducing operads, see e.g. [39, Paragraph 6.2]: Theorem 1.6. [START_REF] Chapoton | Pre-Lie algebras and the rooted trees operad[END_REF]19] Let E be a (non-empty) set. The free pre-Lie algebra generated by E is the vector space T E of (non-planar) E-decorated rooted trees, endowed with grafting.

The prehistory of those notions can be traced back to A. Cayley in 1857 [START_REF] Cayley | On the Theory of Analytical Forms called Trees[END_REF], who introduced rooted trees to study vector fields on R n . We give below its definition in terms of a universal property, along the lines of [START_REF] Agrachev | Chronological algebras and nonstationary vector fields[END_REF]. Definition 1.12. Let PL be a pre-Lie algebra and E be a (non-empty) set with a map i : E → PL. A free pre-Lie algebra is a pair PL, i , satisfying the following universal property: for any pre-Lie algebra B and any map f • : E -→ B there is a unique pre-Lie algebra homomorphism f : PL -→ B, which makes the following diagram commute:

E i / / f • PL f } } } }} } B Figure 1.4.
The universal property of the free pre-Lie algebra.

It is unique up to isomorphism. A pre-Lie algebra PL is said to be freely generated by E ⊆ PL, if PL, i is free, where i : E ֒→ PL is the canonical injection.

The free pre-Lie algebra can be obtained as the quotient of the free magmatic algebra M E with generating set E by the two-sided ideal generated by elements on the form:

x • (y • z) -y • (x • z) -(x • y -y • x) • z, f or x, y, z ∈ M E . (1.22)
From Definition 1.12, we have that any pre-Lie algebra B generated by a subset E ⊂ B is isomorphic to a quotient of the free pre-Lie algebra PL, generated by E, by some ideal. Indeed, from the freeness universal property of PL, there is a unique homomorphism f , which is surjective. The quotient of PL by the kernel of f is isomorphic to B, as in the following commutative diagram:

1. PRELIMINARIES E i / / p j A A A A A A A A PL q / / / / f PL/Ker f =t t t t z z t t t t t B Figure 1.5.
The uniqueness property, up to isomorphism, of the free pre-Lie algebra.

where q is the quotient map.

Denote by PL(E) the free pre-Lie algebra generated by the (non-empty) set E. The magmatic algebra M E has a natural grading, where the elements of degree 1 are linear combinations of the elements of E. The algebra PL(E) can be defined as the quotient of M E by the ideal (1.22). This induces a grading on PL(E), in which the elements of degree 1 are again the linear combinations of the elements of E, by identifying the set E with its image under the factorization.

CHAPTER 2

Monomial Bases for Free Pre-Lie Algebras

This chapter is an adaptation of a published paper in Séminaire Lotharingien de Combinatoire [START_REF] Mahdi | Monomial Bases for Free Pre-Lie Algebras[END_REF]. It consists in two main sections. Section 2.1 contains some preliminaries on planar and non-planar rooted trees, Butcher products and grafting products. In this section, we also review the joint work of K. Ebrahimi-Fard and D. Manchon (unpublished) who described an explicit algebra isomorphism Ψ between two structures of free magmatic algebras defined on the space T E pl of all decorated planar rooted trees, by the left Butcher product " • ց" and the left grafting product " ց " respectively. We give the explicit expression of the coefficients c(σ, τ) of this isomorphism in the planar rooted tree basis. Using their work, and by defining a bijective linear map Ψ S which depends on the choice of a section S of the "forget planarity" projection π, we find a formula for the coefficients β S (s, t) of Ψ S in the decorated (non-planar) rooted tree basis. This can be visualized on the following diagram: for any homogeneous components T E pl, n and T E n .

τ = m i=1,...,n ( a i , • ց) ∈ T E pl, n Ψ / / π T E pl, n ∋ m i=1,...,n ( a i , ց) π t = m i=1,...,n ( a i , ) ∈ T E n Ψ S / / S O O T E n ∋ m i=1,...,n ( a i , →)
In Section 2.2, we recall some basic topics on free pre-Lie algebras. We describe the construction of a monomial basis for each homogeneous subspace PL n in free pre-Lie algebras PL(E) generated by a (non-empty) set E, using a type of algebra isomorphism obtained by A. Agrachev and R. V. Gamkrelidze [START_REF] Agrachev | Chronological algebras and nonstationary vector fields[END_REF]. Finally, the constructions in Sections 2.1 and 2.2 can be related as follows: we show that a tree-grounded monomial basis in a free pre-Lie algebra defines a section S of the projection π : T E pl -→ -→ T E and, conversely, that any section of π defines a tree-grounded monomial basis.

Butcher and grafting products

2.1.1. On planar rooted trees. Definition 2.1. The left grafting " ց " is a bilinear operation defined on the vector space T E pl , such that for any planar rooted trees σ and τ:

σ ց τ = v vertex o f τ σ ց v τ, (2.1)
where "σ ց v τ" is the tree obtained by grafting the tree σ, on the left, on the vertex v of the tree τ, such that σ becomes the leftmost branch, starting from v, of this new tree.

Example 2.1. For the non-decorated case, we have:

ց = + + .
This type of grafting again provides the space T E pl with a structure of free magmatic algebra: K. Ebrahimi-Fard and D. Manchon showed that the two structures defined on T E pl , one by the product " • ց" and the other by " ց ", are linearly isomorphic, as follows: define the potential energy p(σ) of a planar rooted tree σ to be the sum of the heights of its vertices multiplied by the degree:

p(σ) = v∈V(σ) |v|h(v), (2.2)
where h(v) is the height of the vertex v in σ. Introduce the decreasing filtration

T E pl = T E, (0) pl ⊃ T E, (1) pl ⊃ T E, (2) pl ⊃ • • • , where T E, (k)
pl is the vector space spanned by planar rooted trees σ with p(σ) ≥ k.

Theorem 2.1.

There is a unique linear isomorphism Ψ from T E pl onto T E pl , defined as:

Ψ( a ) = a
, for any a ∈ E, and

Ψ(σ 1 • ց σ 2 ) = Ψ(σ 1 ) ց Ψ(σ 2 ), for all σ 1 , σ 2 ∈ T E pl . (2.
3)

It respects the graduation given by the number of vertices, and the associated graded map Gr Ψ (with respect to the potential energy filtration above) reduces to the identity. Also, it respects the graduation defined by the degree of elements of E.

Proof. The linear map Ψ is uniquely determined by virtue of the universal property of the free magmatic algebra (T E pl , • ց). Obviously, it respects the number of vertices and the degree of trees (in terms of the degree of elements of E). For any planar rooted trees σ 1 , σ 2 , the equality

σ 1 ց σ 2 = σ 1 • ց σ 2 + σ ′ holds, with σ ′ ∈ T E, (p(σ 1 • ց σ 2 )+1) pl
. Then, for σ = σ 1 • ց σ 2 , we have:

Ψ(σ) = σ + σ ′′ , (2.4)
with σ ′′ ∈ T E, (p(σ)+1) pl , which proves the Theorem.

From Theorem 2.1, one can note that the matrix of Ψ restricted to any homogeneous component T E pl, n is upper triangular unipotent. More precisely, c(σ, τ) = 0 if the potential energy p(σ) of σ is strictly smaller than the potential energy of τ, and c(σ, τ) = δ τ σ if p(σ) = p(τ). In the single generator case, we can calculate the sum of the entries of this matrix as follows: for any planar rooted tree σ ∈ T n pl , let N(σ) be the number of trees (with the multiplicities) in Ψ(σ). Let σ = σ 1 • ցσ 2 , where σ 1 ∈ T p pl , σ 2 ∈ T q pl , such that p + q = n, for p, q ≥ 1. Since σ 2 has q vertices, and from the definition of the left grafting product " ց ", we get that:

N(σ) = N(σ 1 ) N(σ 2 ) q.
(2.5)

Now, define:

N(T n pl ) = σ∈T n pl N(σ), (2.6)
then using (2.5), we obtain that:

N(T n pl ) = p+q=n p, q≥1 σ 1 ∈T p pl σ 2 ∈T q pl N(σ 1 ) N(σ 2 ) q = p+q=n p, q≥1 q            σ 1 ∈T p pl N(σ 1 )                       σ 2 ∈T q pl N(σ 2 )            = p+q=n p, q≥1 N(T p pl ) N(T q pl ) q.
Here, we find some terms of the formula (2.6):

N(T 1 pl ) = N(T 2 pl ) = 1 N(T 3 pl ) = N(T 2 pl ) N(T 1 pl ) 1 + N(T 1 pl ) N(T 2 pl ) 2 = 3 N(T 4 pl ) = N(T 3 pl ) N(T 1 pl ) 1 + N(T 2 pl ) N(T 2 pl ) 2 + N(T 1 pl ) N(T 3 pl ) 3 = 14 N(T 5 pl ) = N(T 4 pl ) N(T 1 pl ) 1 + N(T 3 pl ) N(T 2 pl ) 2 + N(T 2 pl ) N(T 3 pl ) 3 + N(T 1 pl ) N(T 4 pl ) 4 = 85.
This is sequence A088716 in [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF]. The generating series A(x) := n≥1 a n x n , modulo the shift a n := N(T n+1 pl ), verifies the differential equation:

A(x) = 1 + xA(x) 2 + x 2 A(x)A ′ (x).
M 3 =       1 1 0 1       , M 4 =                         1 1 1 1 1 0 1 0 1 1 0 0 1 0 1 0 0 0 1 2 0 0 0 0 1                         . Corollary 2.2. (T E pl , ց
) is another description of the free magmatic algebra generated by E. Here is the explicit expression of Ψ and Ψ -1 on the following planar undecorated rooted trees:

Ψ(σ) Ψ -1 (σ) p(σ) σ 0 1 3 2 + - 6 5 + - 4 + - 4 + + - 3 + + 2 + + --2 + +
Now, we shall review the (unpublished) joint work of K. Ebrahimi-Fard and D. Manchon on finding a formula for the coefficient c(σ, τ) of tree σ in Ψ(τ), for any trees σ and τ in T pl . Let σ be any planar rooted tree, and v, w be two vertices in the set V(σ) of its vertices, define a partial order "<" as follows: v < w if there is a path from the root to w through v. The root is the minimal element, and leaves are the maximal elements. Define a refinement "≪" of this order to be the transitive closure of the relation R defined by: vRw if v < w, or both v and w are linked to a third vertex u ∈ V(σ), such that v lies on the right of w, like this:

u w v
. A further refinement "≪" on V(σ) is the total order recursively defined as follows: v ≪ w if and only if v ≪ w inside V(σ 1 ) or V(σ 2 ), or v ∈ V(σ 2 ) and w ∈ V(σ 1 ), where σ = σ 1 • ց σ 2 . It is the "depth-first search" ordering, up to an inversion of left and right. A planar rooted tree with its vertices labeled according to total order "≪". Now suppose that our trees are decorated by some set E, i.e. for any tree σ ∈ T E pl we have a map: V(σ) → E. A bijection ψ : V(σ) → V(τ) respects the decorations if the decoration of ψ(v) is the same as the decoration of v for any v ∈ V(σ).

Theorem 2.3. For any planar decorated rooted tree τ we have:

Ψ(τ) = σ∈T E pl c(σ, τ)σ, (2.7)
where c(σ, τ) are non-negative integers. An explicit expression for c(σ, τ) is given by the number of bijections ψ : V(σ) -→ V(τ) which respect the decorations, and which are increasing from

(V(σ), ≪) to (V(τ), ≪), such that ψ -1 is increasing from (V(τ), <) to (V(σ), <).
Proof. This Theorem is proved using the induction on the degree n of trees. The proof is trivial for n = 1, 2. Given any planar rooted trees σ, τ ∈ T E pl, n , such that τ can be written in a unique way as τ = τ 1 • ցτ 2 , we have:

c(σ, τ 1 • ցτ 2 ) = v∈V(σ) c(σ v , τ 1 )c(σ v , τ 2 ), (2.8)
where σ v is the leftmost branch of σ starting from v, and σ v is the corresponding trunk, i.e. what remains when the branch σ v is removed. This is immediate from the following computation:

Ψ(τ) = Ψ(τ 1 • ցτ 2 ) = Ψ(τ 1 ) ց Ψ(τ 2 ) = σ ′ , σ ′′ ∈T E pl c(σ ′ , τ 1 )c(σ ′′ , τ 2 ) σ ′ ց σ ′′ .
Denote by b(σ, τ) the number of bijections from V(σ) onto V(τ) respecting the decorations and satisfying the growing conditions of Theorem 2.3. Let ψ be an increasing bijection from (V(σ), ≪) to (V(τ), ≪) compatible with the decorations. The decomposition τ = τ 1 • ցτ 2 defines a partition of V(σ) into two parts

V i = ψ -1 (V(τ i )), i = 1, 2 such that V 2 ≪ V 1 ,
which means that for any v ∈ V 1 and w ∈ V 2 , either w ≪ v or they are incomparable. Such partitions are nothing but left admissible cuts [START_REF] Munthe-Kaas | On the Hopf Algebraic Structure of Lie Group Integrators[END_REF]. Put σ V 1 and σ V 2 to be the corresponding pruning and the trunk respectively.

As the inverse ψ -1 moreover respects the order "<", there is a unique minimal element in V 1 for "<", namely ψ -1 (v 1 ) where v 1 is the root of τ 1 . This means that the left cut considered here is also elementary, i.e. the pruning σ V 1 is a tree. It is then clear that the restriction ψ i of ψ to σ V i is a bijection from V(σ V i ) onto V(τ i ) which respects both the decorations and the growing conditions of the Theorem, for i = 1, 2. Conversely, any vertex v of σ defines an elementary left cut by taking the leftmost branch σ v starting from v and the corresponding trunk σ v , and if ψ ′ : V(σ ′ ) -→ V(τ 1 ) and ψ ′′ : V(σ ′′ ) -→ V(τ 2 ) are two bijections compatible with the decorations and satisfying the growing conditions of the Theorem, then the bijection ψ : V(σ) -→ V(τ) obtained from ψ ′ and ψ ′′ also satisfies these conditions. Thus, we arrive at:

b(σ, τ 1 • ցτ 2 ) = v∈V(σ) b(σ v , τ 1 )b(σ v , τ 2 ), (2.9)
hence, the coefficients c(•, •) and b(•, •) satisfy the same recursive relations. This ends the proof of Theorem 2.3.

Example 2.3. For E = { }, we have c( , ) = 2 according to the table above. Let us name the vertices as follows:

v 1 v 3 v 2 v 4
,

w 1 w 4 w 3 w 2 . Take ϕ : V( ) → V( ) be a bijective map.We have v 1 ≪ v 3 , v 1 ≪ v 2 ≪ v 4 , v 2 ≪ v 3 , as well as w 1 ≪ w 2 ≪ w 3 ≪ w 4 .
The growing conditions of Theorem 2.3 impose:

ϕ(v 1 ) = w 1 , ϕ(v 2 ) ≪ ϕ(v 3 ).
Hence we have:

ϕ(v 1 ) = w 1 ϕ(v 1 ) = w 1 ϕ(v 2 ) = w 2 ϕ(v 2 ) = w 2 ϕ(v 3 ) = w 3 or ϕ(v 3 ) = w 4 ϕ(v 4 ) = w 4 ϕ(v 4 ) = w 3
The inverse of both bijections obviously respect the order " < ". Hence we find two bijections verifying the growing conditions of Theorem 2.3, thus recovering b( , ) = c( , ) = 2.

From planar to non-planar rooted trees.

Corresponding to the coefficients c(σ, τ), with their explicit expressions, in the matrix of the restriction of the linear map Ψ to any homogeneous component T E pl, n , we try to find a similar expression in the non-planar case: in other words, we build up and explicitly describe the map Ψ S in Figure 2.1.

Recall that the space T E endowed with the grafting "→", is a pre-Lie algebra. Recall that the symmetry factor of any (non-planar) decorated rooted tree s is the number sym(s) of all automorphisms Θ : V(s) -→ V(s) which are increasing from (V(s), <) onto (V(s), <) and which respect the decorations. This definition is equivalent to the recursive definition in [START_REF] Ch | Trees, Renormalization and differential equations[END_REF].

Let Ψ = π • Ψ be the linear map from T E pl onto T E , where π is the "forget planarity" projection.

T E pl Ψ / / Ψ A A A A A A A T E pl π T E Figure 2.3.
Obviously, Ψ is a morphism of algebras from (T E pl , • ց) into (T E , →). One of the important results we obtained is the following: Theorem 2.4. Let τ be any planar decorated rooted tree, we have:

Ψ(τ) = s∈T E α(s, τ)s, (2.10)
where α(s, τ) are nonnegative integers. The coefficients α(s, τ) coincide with the numbers b(s, τ) = b(s, τ)/sym(s), where sym(s) is the symmetry factor of s described above and b(s, τ) is the number of bijections ϕ : V(s) -→ V(τ) which respect the decorations and which are increasing from (V(s), <) into (V(τ), ≪), such that ϕ -1 is increasing from (V(τ), <) into (V(s), <).

Proof. Note that the restriction of Ψ to any homogeneous component T E pl, n reduces the square matrix of the coefficients c(σ, τ) to a rectangular matrix [[α(s, τ)]] s∈T E n , τ∈T E pl, n . For any planar decorated rooted tree τ, we have:

α(s, τ) = σ∈T E pl π(σ)=s c(σ, τ), (2.11)
where s is a (non-planar) decorated rooted tree. We prove Theorem 2.4 using the induction on the degree of trees. The proof is trivial in the cases n = 1, 2. Let τ ∈ T E pl, n , with τ = τ 1 • ցτ 2 , then:

α(s, τ 1 • ցτ 2 ) = σ∈T E pl π(σ)=s, v∈V(σ) c(σ v , τ 1 )c(σ v , τ 2 ), (2.12)
which is immediate from (2.11), where σ v is the leftmost branch of σ starting from v, and σ v is the corresponding trunk. Now, let s be any (non-planar) decorated rooted tree in T E n and ϕ : V(s) → V(τ) be a bijection which respects the decorations and satisfies the growing conditions given in Theorem 2.4. Then we can define from these conditions a structure of poset on the set V(s) of vertices of s , as follows: for v, w ∈ V(s), vRw if and only if v < w or there is u ∈ V(s) such that each of v and w are related with u by an edge, and ϕ(v) ≪ ϕ(w). We denote by ≪ ϕ the transitive closure of the relation R.

This structure determines a planar decorated rooted tree σ such that π(σ) = s, with the associated partial order ≪ on the set V(σ) of vertices of σ, together with a decoration-preserving poset isomorphism ϑ : (V(σ), ≪) → (V(s), ≪ ϕ ), which in turn defines a decoration-preserving bijection ϕ ! := ϕ • ϑ : V(σ) → V(τ), which is increasing from (V(σ), ≪) into (V(τ), ≪), such that ϕ ! -1 is increasing from (V(τ), <) into (V(σ), <). The planar decorated rooted tree σ is unchanged if we replace ϕ by ϕ • ϑ ′ with ϑ ′ ∈ Aut(s). Moreover, for any decoration-preserving ϕ, ψ : V(s) → V(τ) satisfying the growing conditions of Theorem 2.4, we have:

ϕ ! = ψ ! ⇔ ϕ = ψ • γ, for γ ∈ Aut(s).
(2.13)

Indeed, if ϕ ! = ψ ! , then γ := ψ -1 • ϕ : V(s) → V(s)
is a decoration-preserving bijection which respects the partial order " < ", hence an element of Aut(s), such that ϕ = ψ • γ. The inverse implication is obvious.

Let B(s, τ) (respectively B(σ, τ)) be the set of decoration-preserving bijections ϕ : We also have for Example 2.4. In the case E = { }, we have α( , ) = 1 in the formula of Ψ( ). Name the vertices as follows:

V(s) → V(τ) (respectively ψ : V(σ) → V(τ))
τ = τ 1 • ցτ 2 : b(s, τ 1 • ցτ 2 ) = σ∈T E pl π(σ)=s, v∈V(σ) b(σ v , τ 1 )b(σ v , τ 2 ). ( 2
v 1 v 2 v 3
,

w 1 w 3 w 2 .
Let ψ : V( ) → V( ) be a bijective map. We have v 1 < v 2 , v 1 < v 3 , as well as w 1 ≪ w 2 ≪ w 3 . The growing conditions of Theorem 2.4 impose ψ(v 1 ) = w 1 . Hence we have:

ψ(v 1 ) = w 1 ψ(v 1 ) = w 1 ψ(v 2 ) = w 2 or ψ(v 2 ) = w 3 ψ(v 3 ) = w 3 ψ(v 3 ) = w 2
The inverse of these bijections obviously respect the order " < ". Hence we find two bijections verifying the growing conditions of Theorem 2.4, thus b( , ) = 2, but sym( ) = 2, then we obtain b( , ) = 1.

We want to describe a family of linear isomorphisms Ψ : T E -→ T E , which make the following diagram commute:

T E pl Ψ / / Ψ A A A A A A A π T E pl π T E Ψ / / T E Figure 2.4. Description of Ψ.
For any (non-planar) decorated rooted tree t, choose σ = S (s) to be a planar decorated rooted tree with π(σ) = s. This defines a section S : T E -→ T E pl of the projection π, i.e. π • S = Id T E . One can note that the map S is not unique, for example, if n = 4, we have in the single generator case: Let S be a section of π. Define Ψ S := Ψ • S to be the linear map from T E into T E , which makes the following diagram commute:

T 4 = { ,
T E pl Ψ / / Ψ A A A A A A A π T E pl π T E Ψ S / / S O O T E Figure 2.5. Description of Ψ S .
Corollary 2.5. For any (non-planar) decorated rooted tree t, we have:

Ψ S (t) = s∈T E β S (s, t)s, (2.16)
where β S (s, t) are nonnegative integers. The coefficients β S (s, t), which depend on the section map S, can be expressed by the numbers b(s, τ) = b(s, τ)/sym(s) described in Theorem 2.4, with τ = S (t).

Proof. Note that the restriction of Ψ S to any homogeneous component T E n reduces the matrix of the coefficients α(s, τ) to a upper triangular unipotent matrix [[β S (s, t)]] s, t∈T E n . Let t be any (non-planar) decorated rooted tree, and let us choose the section map S such that S (t) = τ is a planar decorated rooted tree, then:

Ψ S (t) = Ψ(τ) = s∈T E α(s, τ)s,
which means that the coefficients β S (s, t) and α(s, τ) are the same. Hence, it can be expressed by the number b(s, τ) in the same way than the coefficients α(s, τ). From Theorem 2.4, we found that the restriction of Ψ to any homogeneous component T E pl, n reduces the matrix of the coefficients c(σ, τ) to a rectangular matrix. Now, the restriction of Ψ S to any homogeneous component T E n can be represented by the restriction of Ψ on the component S (T E n ) (this representation depends on the section map S ), which means that the matrix of β S (s, t)'s is a upper triangular unipotent matrix, because we have: Ψ S (t) = t + terms of higher energy.

Tree-grounded monomial bases

The approach by A. Agrachev and R. Gamkrelidze.

A. Agrachev and R. V. Gamkrelidze, in their work "Chronological algebras and nonstationary vector fields" [1], described a pre-Lie algebra isomorphism between the free pre-Lie algebra generated by a (non-empty) set and the tensor product of the universal enveloping algebra of the underlying Lie algebra with the linear span of the generating set. This pre-Lie algebra isomorphism will be the focus of our attention in this section. Using this isomorphism, we shall review the construction by A. Agrachev and R. Gamkrelidze of monomial bases in free pre-Lie algebras.

Denote by [PL(E)] the underlying Lie algebra of the free pre-Lie PL(E), and U[E] its universal enveloping algebra. The structure of algebra defined on U[E] is endowed with the grading deduced from the grading of PL(E).

The representation of the

PL(E) i / / L & & N N N N N N N N N N T (PL(E)) q / / / / L ′ w w o o o o o o o o o o o U[E] L ,
x x q q q q q q q q q q End(PL(E))

= / / End(PL(E)) Figure 2.6.
where T (PL(E)) is the tensor algebra of PL(E), and L ′ is the linear extension of L that is induced by the universal property of the tensor algebra.

Lemma 2.6. The linear span of the set

L U[E] E = {L u a : u ∈ U[E], a ∈ E} ⊂ PL(E) (2.17)
coincides with the entire algebra PL(E).

Proof. See [1, Lemma 1.1].
Define B E = U[E]⊗E to be the tensor product of the vector space U[E] with the linear span E of the set E. The space B E has a structure of algebra over K with the following multiplication:

(u 1 ⊗ a 1 )(u 2 ⊗ a 2 ) = ((L u 1 a 1 ) • u 2 ) ⊗ a 2 , ∀u 1 , u 2 ∈ U[E], a 1 , a 2 ∈ E, ( 2.18)
where "•" is the bilinear associative product in U[E].

Suppose first that any generator a ∈ E is given degree 1. The grading of the algebra U[E] uniquely determines a grading of B E , by setting the degree of the element u ⊗ a equal to the degree of u plus 1. One can verify that the multiplication defined in (2.18) satisfies the pre-Lie identity, which means that B E is a graded pre-Lie algebra.

Theorem 2.7. The graded pre-Lie algebra B E is isomorphic to the free pre-Lie algebra (PL(E), ⊲).

Proof. Let f • : E -→ B E be a map defined by f • (a) = 1 ⊗ a , ∀a ∈ E, where 1 is the unit element of U[E].
Using the freeness property of the pre-Lie algebra PL(E), there is a unique homomorphism f : PL(E) -→ B E , such that:

f (a) = f • (a) = 1 ⊗ a, ∀a ∈ E ⊂ PL(E).
From Lemma 2.6, we have that for any element x in PL(E) there exists u ∈ U[E] and a ∈ E, such that x = L u a. Now, define f as:

f (L u a) = u ⊗ a, ∀x = L u a ∈ PL(E).
(

2.19)

Then the map f with (2.19) is bijective (see [1, Theorem 1.1]), hence it is an isomorphism, which proves the Theorem.

Remark 2.8. The fact that B E = U[E] ⊗ E is isomorphic, as a module, to PL(E) can also be seen using the Grossman-Larson description of U[E]

1 : it consists to identify a tensor t ⊗ a, where t is a rooted tree with undecorated root and a ∈ E, to the tree obtained by decorating the root of t by a.

Choose a total order on the elements of E. Then as a corollary of Theorem 2.7 and the Poincaré-Birkhoff-Witt Theorem, we obtain that:

PL n =B n = U n-1 ⊗ E, ∀n ≥ 1, (2.20)
where, for any n ≥ 2, a basis of U n-1 is given by:

       x e 1 j 1 • • • • • x e r j r : r k=1 j k = n -1, and x e 1 j 1 ≥ • • • ≥ x e r j r        . (2.21)
Here we use a monomial basis x 1 j , . . . , x d j j of the subspace PL j , for any j = 1, . . . , n -1, given by the induction hypothesis. We endow this basis with the total order x 1 j < . . . < x d j j , which in turn defines a total order on the basis of PL 1 ⊕ . . . ⊕ PL n-1 , obtained by the disjoint union, by asking that x r j > x r ′ j ′ if j > j ′ . 1 For further details about Grossman-Larson algebra see Paragraph 4.3.1.

Hence, using formula (2.20) and the isomorphism f described in (2.19) , we get the following monomial basis for the homogeneous component PL n :

       x e 1 j 1 ⊲ x e 2 j 2 ⊲ (• • • ⊲ (x e r j r ⊲ a j ) • • • ) : r k=1 j k = n -1, x e 1 j 1 ≥ • • • ≥ x e r j r and a j ∈ E        . (2.22)
Here is a description of these monomial bases up to degree 5:

PL 1 = U 0 ⊗ E = ≺ 1 ⊗ a : 1 ∈ K, a ∈ E ≻, ⇒ PL 1 = ≺ L 1 a = a : a ∈ E ≻= E. PL 2 = U 1 ⊗ PL 1 = ≺ a 1 ⊗ a 2 : a 1 , a 2 ∈ E ≻, ⇒ PL 2 = ≺ L a 1 a 2 = a 1 ⊲ a 2 : a 1 , a 2 ∈ E ≻. PL 3 = U 2 ⊗ PL 1 = ≺ x e 2 ⊗ a, (x e 1 1 • x e 2 1
) ⊗ a ′ : e = 1, . . . , d 2 , e 1 , e 2 = 1, . . . , d, e 1 ≥ e 2 , a, a ′ ∈ E ≻, ⇒ A monomial basis of PL 3 is then given by:

{(a 1 ⊲ a 2 ) ⊲ a 3 : a 1 , a 2 , a 3 ∈ E} ⊔ {a 1 ⊲ (a 2 ⊲ a 3 ) : a 1 , a 2 , a 3 ∈ E, a 1 ≥ a 2 } . PL 4 =U 3 ⊗ PL 1 =≺ x e 3 ⊗ a, (x e ′ 2 • x e 1 1 ) ⊗ a ′ , (x e 2 1 • x e 3 1 • x e 4 1
) ⊗ a ′′ : e = 1, . . . , d 3 , e ′ = 1, . . . , d 2 , e 1 , e 2 , e 3 , e 4 = 1, . . . , d 1 , e 2 ≥ e 3 ≥ e 4 , a, a ′ , a ′′ ∈ E ≻, ⇒ A monomial basis of PL 4 is then given by: ⇒ A monomial basis of PL 5 is then given by: ((a 1 ⊲ a 2 ) ⊲ a 3 ) ⊲ a 4 ) ⊲ a 5 : a j ∈ E, for j = 1, . . . , 5 ⊔ (a 1 ⊲ (a 2 ⊲ a 3 )) ⊲ a 4 ) ⊲ a 5 : a j ∈ E, for j = 1, . . . , 5, a 1 ≥ a 2 ⊔ ((a 1 ⊲ a 2 ) ⊲ (a 3 ⊲ a 4 )) ⊲ a 5 : a j ∈ E, for j = 1, . . . , 5 ⊔ (a 1 ⊲ (a 2 ⊲ (a 3 ⊲ a 4 ))) ⊲ a 5 :

((a 1 ⊲ a 2 ) ⊲ a 3 ) ⊲ a 4 : a j ∈ E, for j = 1, 2, 3, 4 ⊔ (a 1 ⊲ (a 2 ⊲ a 3 )) ⊲ a 4 : a j ∈ E, for j = 1, 2, 3, 4, a 1 ≥ a 2 ⊔ (a 1 ⊲ a 2 ) ⊲ (a 3 ⊲ a 4 ) : a j ∈ E, for j = 1, 2, 3, 4 ⊔ a 1 ⊲ (a 2 ⊲ (a 3 ⊲ a 4 )) : a j ∈ E, for j = 1, 2, 3, 4, a 1 ≥ a 2 ≥ a 3 . PL 5 =U 4 ⊗ PL 1 =≺ x e 4 ⊗
a j ∈ E, for j = 1, . . . , 5, a 1 ≥ a 2 ≥ a 3 ⊔ ((a 1 ⊲ a 2 ) ⊲ a 3 ) ⊲ (a 4 ⊲ a 5 ) : a j ∈ E, for j = 1, . . . , 5 ⊔ (a 1 ⊲ (a 2 ⊲ a 3 )) ⊲ (a 4 ⊲ a 5 ) : a j ∈ E, for j = 1, . . . , 5, a 1 ≥ a 2 ⊔ (a 1 ⊲ a 2 ) ⊲ ((a 3 ⊲ a 4 ) ⊲ a 5 ) : a j ∈ E, for j = 1, . . . , 5, a 1 ⊲ a 2 ≥ a 3 ⊲ a 4 ⊔ (a 1 ⊲ a 2 ) ⊲ (a 3 ⊲ (a 4 ⊲ a 5 )) : a j ∈ E, for j = 1, . . . , 5, a 3 ≥ a 4 ⊔ a 1 ⊲ (a 2 ⊲ (a 3 ⊲ (a 4 ⊲ a 5 ))) : a j ∈ E, for j = 1, . . . , 5, a 1 ≥ a 2 ≥ a 3 ≥ a 4 . . . .

etc.

This adapts to the case when the generators are of various degrees: suppose E = i∈N E i is a disjoint union of subsets E i , where E i is the subset of generators of degree i. Then the grading of the algebra B E is determined by the grading of U[E], by setting the degree of the element u ⊗ a equal to the degree of u plus the degree of the generator a in E. The Theorem 2.7 remains true. The formula in (2.20) will be changed as:

PL n = B n = n ℓ=1 U n-ℓ ⊗ E ℓ , for all 1 ≤ ℓ ≤ n, (2.23)
where E ℓ is the subspace of all elements of E of degree ℓ. For any 1 < ℓ ≤ n -1, a basis of U n-ℓ is given by:

       x e 1 j 1 • • • • • x e r j r : r k=1 j k = n -ℓ, and x e 1 j 1 ≥ • • • ≥ x e r j r        . (2.24)
Hence, by (2.23) and (4.21), the monomial basis for the homogeneous component PL n becomes:

n ℓ=1 x e 1 j 1 ⊲ x e 2 j 2 ⊲ (• • • ⊲ (x e r j r ⊲ a j ) • • • ) : r k=1 j k = n -ℓ, x e 1 j 1 ≥ • • • ≥ x e r j r and a j ∈ E ℓ . (2.25)

Base change to the rooted tree basis.

We relate now any Agrachev-Gamkrelidze type monomial basis in a free pre-Lie algebra, obtained from the formula (2.20), with the presentation of the free pre-Lie algebra as the linear span T of the (non-planar) rooted trees with one generator { }, endowed with the grafting " → ". In the following, we give the tree expansions of the first five homogeneous components of such a monomial basis, in the case of one single generator: Now, for any homogeneous component T n , each vector in the monomial basis described above is defined as a monomial m( , →) of the tree with one vertex " " multiplied (by itself) using the pre-Lie grafting " → " with the parentheses. This monomial in turn determines two monomials in the algebras (T pl , • ց) and (T , ) respectively. One of these monomials is obtained by replacing the grafting " → " by the left Butcher product " • ց", which induces a planar rooted tree τ. The other monomial is deduced by replacing the product " → " by the usual Butcher product, which in turn defines a (non-planar) rooted tree t. This adapts straightforwardly to several generators of various degrees.

T 1 =≺ e 1 = ≻. T 2 =≺ → ≻ = ≺ e 1 = ≻. T 3 =≺ ( → ) → , → ( → ) ≻ = ≺ e 1 = , e 2 = + ≻. T 4 =≺ (( → ) → ) → , ( → ( → )) → , ( → ) → ( → ), → ( → ( → )) ≻ =≺ e 1 = , e 2 = + , e 3 = + , e 4 = + + 3 + ≻. T 5 =≺ ((( → ) → ) → ) → , (( → ( → )) → ) → , (( → ) → ( → )) → , ( → ( → ( → ))) → , ((( → ) → ) → ( → ), (( → ( → )) → ( → ), ( → ) → (( → ) → ), ( → ) → ( → ( → )), → ( → ( → ( → ))) ≻ =≺ e 1 = ,

Definition 2.2.

A monomial basis for a free pre-Lie algebra is said to be a "tree-grounded" monomial basis if we obtain the Chapoton-Livernet tree basis when we replace the pre-Lie product in each monomial in this basis by the Butcher product " ". For any positive integer n, a monomial basis of T E n will also be called tree-grounded if this property holds in T E n .

Example 2.5. In the space of all (non-planar) undecorated rooted trees T , the homogeneous component T 4 has four types of monomial bases, which are:

B 1 = (( → ) → ) → , ( → ( → )) → , ( → ) → ( → ), → ( → ( → ))
= e 1 = , e 2 = + , e 3 = + , e 4 = + + 3 + .

B 2 = (( → ) → ) → , ( → ( → )) → , → (( → ) → ), → ( → ( → ))
= e 1 = , e 2 = + , e 3 = + + , e 4 = + + 3 + .

B 3 = (( → ) → ) → , ( → ) → ( → ), → (( → ) → ), → ( → ( → ))
= e 1 = , e 2 = + , e 3 = + + , e 4 = + + 3 + .

B 4 = ( → ( → )) → , ( → ) → ( → ), → (( → ) → ), → ( → ( → ))
= e 1 = + , e 2 = + , e 3 = + + , e 4 = + + 3 + .

We find that the monomial bases , ) is the lower-energy term of x. By Definition 2.2, these lower-energy terms form a basis of T E , hence S is uniquely defined that way, and it is a section of π, as in the following diagram:

B
m i=1,...,n ( a i , • ց) ∈ T E pl Ψ / / π T E pl ∋ m i=1,...,n ( a i , ց) π t = m i=1,...,n ( a i , ) ∈ T E Ψ S / / S O O T E ∋ x = m i=1,...,n ( a i , →) Figure 2.7.
On the other hand, any monomial basis induced by a section map S is obviously a treegrounded monomial basis.

Lemma 2.10. The Agrachev-Gamkrelidze monomial bases are tree-grounded.

Proof. From the construction of Agrachev-Gamkrelidze monomial bases, and using the presentation of the free pre-Lie algebra in terms of rooted trees (see Theorem 1.6), we have:

T E n = U n-1 ⊗ E, ∀n ≥ 1
such that for a homogeneous component T E n , the monomial basis in (2.22) becomes:

       x e 1 j 1 → x e 2 j 2 → (• • • → (x e r j r → a ) • • • ) : r k=1 j k = n -1, x e 1 j 1 ≥ • • • ≥ x e r j r , for a ∈ E        . (2.26)
The monomial basis for T E 1 , namely { a : a ∈ E}, is obviously tree-grounded in the sense of Definition 2.2. Suppose, by the induction hypothesis, that the monomial basis {x e 1 j , . . . , x e j j } is a tree-grounded basis of T E j , for j = 1, . . . , n -1. Consider the corresponding lower-energy terms t e 1 j , . . . , t e j j obtained by replacing the grafting "→" by the Butcher product " " in each monomial. The lower-energy term of the monomial

x e 1 j 1 → x e 2 j 2 → (• • • → (x e r j r → a ) • • • ) (2.27)
is given by :

t e 1 j 1 t e 2 j 2 (• • • (t e r j r a ) • • • ) = B +, a (t e 1 j 1 . . . t e r j r ).
Hence we recover the tree basis of T E n by taking the lower-energy term of each monomial (2.27), thus proving Lemma 2.10.

Remark 2.11. The Agrachev-Gamkrelidze monomial basis B, described in (2.26), determines a section S , this section is defined as follows: let x = x e 1 j 1 → x e 2 j 2 → (• • • → (x e r j r → a ) • • • ) be a basis element in B, and t = t e 1 j 1 t e 2 j 2 (• • • (t e r j r a ) • • • ) be its lower-energy term, we can associate with t:

S (t) = τ = τ e 1 j 1 • ց τ e 2 j 2 • ց(• • • • ց(τ e r j r • ց a ) • • • ) ,
such that π(τ e i j i ) = t e i j i , Ψ(τ e i j i ) = x e i j i , for all i = 1, . . . , r, and then Ψ(S (t)) = Ψ S (t) = x.

Lemma 2.10 remains true in the case of several generators with various degrees. As a particular case of our general construction, an Agrachev-Gamkrelidze monomial basis, by means of the isomorphism (2.19), gives rise to some particular section S . Conversely, any section S of π defines a tree-grounded monomial basis for the free pre-Lie algebra (T E , →). For any integer n ≥ 1, the matrix of the coefficients of the tree-grounded monomial of T E n associated with the section S is exactly the matrix [[β S (s, t)]] s, t ∈ T E n described in Corollary 2.5. See appendix A for an explicit expression for those matrices in some particular cases in one generator.

Remark 2.12. We have seen that the map Ψ respects both graduations: the one given by the number of vertices, and the one given by the sum of the degree of the vertices. The restriction of Ψ to homogeneous components for the second graduation is also upper-triangular unipotent.

CHAPTER 3

Monomial Bases and pre-Lie structures for free Lie algebras

This chapter contains three main sections. In Section 3.1, we construct a structure of pre-Lie algebra on the free Lie algebra L(E) generated by a set E, and we give the explicit presentation of L(E) as the quotient of the free pre-Lie algebra T E by some ideal.

Recall that T E pl is the linear span of the set T E pl of all planar E-decorated rooted trees, which forms together with the left Butcher product " • ց", and the left grafting "ց" respectively two magmatic algebras. In Section 3.2, we give a tree version of a monomial well-order on T E pl . We adapt the work of T. Mora [START_REF] Mora | An introduction to commutative and non-commutative Gröbner bases[END_REF] on Gröbner bases to a non-associative, magmatic context, using the descriptions of the free magmatic algebras T E pl , • ց and T E pl , ց respectively, following [START_REF] Drensky | Planar trees, free non-associative algebras, invariants, and elliptic integrals[END_REF]. We split the basis of E-decorated planar rooted trees into two parts O(J ′ ) and T (J ′ ), where J ′ is the ideal of T E pl generated by the pre-Lie identity and by "weighted anti-symmetry relations":

|σ|σ • ցτ + |τ|τ • ցσ.
Here T (J ′ ) is the set of maximal terms of elements of J ′ , and its complement O(J ′ ) then defines a basis of L(E). We get one of the important results in this thesis (Theorem 3.12), on the description of the set O(J ′ ) in terms of trees.

In Section 3.3, we give a non-planar tree version of the monomial well-order above. We describe monomial bases for the pre-Lie (respectively free Lie) algebra L(E), using the procedures of Gröbner bases and our work described in Chapter 2, in the monomial basis for the free pre-Lie algebra T E .

A pre-Lie structure on free Lie algebras

Let L(E) be the free Lie algebra generated by a (non-empty) set E = i∈N E i , a disjoint union of subsets E i , where E i is the subset of elements a i 1 , . . . , a i d i of degree i, and #E i = d i . The free Lie algebra L(E) can be graded, using the grading of E:

L(E) = i∈N L i , (3.1)
where L i is the subspace of all elements of L(E) of degree i. In particular E i ⊂ L i .

Define an operation "⊲" on L(E) by:

x ⊲ y := 1 |x| [x, y], (3.2)
for x, y ∈ L(E).

Proposition 3.1. The operation " ⊲ " defined by (3.2) is a bilinear product which satisfies the pre-Lie identity.

Proof. For x, y, z ∈ L(E), we have:

(x ⊲ y) ⊲ z -x ⊲ (y ⊲ z) = 1 |x| [x, y] ⊲ z - 1 |y| x ⊲ [y, z] = 1 |x| |x| + |y| [[x, y], z] - 1 |x||y| [x, [y, z]] = 1 |x| |x| + |y| [[x, y], z] - 1 |x||y| [[x, y], z] -[y, [z, x]] , since [x, [y, z]] + [z, [x, y]] + [y, [z, x]] = 0 (the Jacobi identity) = 1 |x| |y| -|x| + |y| |y| |x| + |y| [[x, y], z] + 1 |x||y| [y, [z, x]] = 1 |y| |x| + |y| [[y, x], z] - 1 |x||y| [y, [x, z]] = (y ⊲ x) ⊲ z -y ⊲ (x ⊲ z).
Then L(E) together with " ⊲ " forms a graded pre-Lie algebra generated by E.

This construction of pre-Lie algebra on the Lie algebra can be applied to any N-graded Lie algebra L, such that L 0 = {0}. Another construction of pre-Lie algebra proposed on L by T. Schedler [START_REF] Schedler | Connes-Kreimer quantizations and PBW theorems for pre-Lie algebras[END_REF] 1 , given by the following pre-Lie product:

x ◮ y = |y| |x| + |y| [x, y], for any x, y ∈ L. (3.3)
These two constructions are isomorphic, via the linear map:

α :        L, ◮ -→ L, ⊲ , x -→ |x|x.
Indeed, α is a bijection, and for any x, y ∈ L we have: For any (non-planar) rooted tree t, we can decorate the vertices of t by elements of E, by means of a map d : V(t) → E, where V(t) is the set of vertices of t. Denote by T E the set of all (non-planar) rooted trees decorated by the elements of E, define the degree |t| of a decorated tree t in T E by:

α(x ◮ y) = α( |y| |x| + |y| [x, y]), (
|t| := v∈V(t) |d(v)| (3.6)
The linear span of T E , call it T E , together with the grafting product " → " is the free pre-Lie algebra generated by the set a ; a ∈ E [START_REF] Chapoton | Pre-Lie algebras and the rooted trees operad[END_REF], which is graded by the degree of trees defined in (3.6). In particular, there is a unique pre-Lie homomorphism Φ from T E , → onto L(E), ⊲ , such that: (i) The anti-symmetry identity: for any s, t ∈ T E , we have

Φ( a ) = a for any a ∈ E. (3.7) If we take t = t 1 → (t 2 → (• • • → (t k → a ) • • • )) ∈ T E , then: Φ(t) = x 1 ⊲ (x 2 ⊲ (• • • ⊲ (x k ⊲ a) • • • )), ( 3
[s, t] = -[t, s], since, |s|(s → t) + |t|(t → s) ∈ I.
(ii) The Jacobi identity: for any s, t, t ′ ∈ T E , then

[s, [t, t ′ ]] + [[s, t ′ ], t] = |s||t| s → (t → t ′ ) + |s|(|s| + |t ′ |) (s → t ′ ) → t) (using the anti-symmetry identity) -→ = |s||t| (s → (t → t ′ )) -(t → (s → t ′ )) (using the pre-Lie identity) -→ = |s||t| (s → t) → t ′ -(t → s) → t ′ = |s||t| (s → t -t → s) → t ′ (using the anti-symmetry identity) -→ = |s||t| (s → t + |s| |t| s → t) → t ′ = |s||t| |s| + |t| |t| (s → t) → t ′ = |s|(|s| + |t|) (s → t) → t ′ = [[s, t], t ′ ].
Proposition 3.3. I = Ker Φ.

Let M(E), • be the free magma generated by E, and let M E be the free magmatic algebra generated by E, i.e. the linear span of the magma M(E). Define a new magmatic product " * " on M(E) by:

x * y := |x|x • y (3.12)
for any x, y ∈ M(E), and extend bilinearly. We need, to prove Proposition 3.3, to introduce the following lemmas.

Lemma 3.4. The two magmatic algebras M E , • and M E , * are isomorphic.

Proof. By universal property of the free magmatic algebra, there is a unique morphism γ : M E , • → M E , * such that γ(a) = a, for any a ∈ E. For any x, y ∈ M E , we have:

γ(x • y) = γ(x) * γ(y) = |γ(x)| γ(x) • γ(y). (3.13)
Hence one can see, by induction on the degree of elements of the magma M(E), that we have for any z ∈ M(E):

γ(z) = f (z) z, (3.14)
where f : M(E) → N is recursively given by: f (a) = 1, for any a ∈ E, and f (x • y) = |x| f (x) f (y) for x, y ∈ M(E) (for more details about this mapping see Example 3.1 below). Hence γ is an isomorphism.

Now, let J be the two-sided ideal generated by the the anti-symmetry and the Jacobi identities on M E , * , and let J ′ be the two-sided ideal of M E , • generated by the pre-Lie identity and the elements on the form:

|x|x • y + |y|y • x, for x, y ∈ M(E).
(3.15) Lemma 3.5. J = J ′ .

Proof. Let J ′ 1 be the ideal generated by the elements (3.15). Equivalently, J ′ 1 is generated by the elements x * y + y * x, for x, y ∈ M(E). We have:

x • (y • z) -(x • y) • z -y • (x • z) + (y • x) • z = 1 |x||y| x * (y * z) - 1 |x|(|x| + |y|) (x * y) * z - 1 |x||y| y * (x * z) + 1 |y|(|x| + |y|) (y * x) * z = 1 |x||y|(|x| + |y|) (|x| + |y|)x * (y * z) -|y|(x * y) * z -(|x| + |y|)y * (x * z) + |x|(y * x) * z = 1 |x||y| -y * (x * z) + (y * x) * z + x * (y * z) - 1 |x|(|x| + |y|) (y * x + x * y) * z = 1 |x||y| x * (y * z) + y * (z * x) + z * (x * y) modulo J ′ 1 , hence x • (y • z) -(x • y) • z -y • (x • z) + (y • x) • z ∈ J. This means J ′ ⊂ J. Conversely, x * (y * z)+y * (z * x)+z * (x * y) = |x||y| x• (y• z)-(x• y)• z -y• (x• z)+(y• x)• z modulo J ′ 1 , (3.16)
hence the left-hand side of (3.16) belongs to J ′ , which proves the inverse inclusion.

proof of Proposition 3.3. The free pre-Lie algebra generated by E is given by T E [START_REF] Chapoton | Pre-Lie algebras and the rooted trees operad[END_REF], [19]. Hence, the quotient L ′ (E) = M E , • /J ′ = T E /I is a pre-Lie (respectively Lie) algebra. The Lie algebra L(E) = M E , * /J carries a pre-Lie algebra structure induced by the product defined in (3.2), such that the free pre-Lie algebra PL(E) := M E /J ′ 2 = T E , where J ′ 2 is the two-sided ideal generated by the pre-Lie identity on M E , • , is homomorphic to L(E) by Φ described in (3.7) and (3.8), as pre-lie algebras, as in the following commutative diagram:

E i / / q j " " E E E E E E E E E M E , • q ′ $ $ $ $ I I I I I I I I I Id M E , * q $ $ $ $ I I I I I I I I I T E Φ L(E) Figure 3.1.
where q, q ′ are quotient maps. From Figure 3.1 above and Lemmas 3.4, 3.5, we get that: Ker Φ • q ′ = J ′ = J = Ker q, and then Ker Φ = q ′ (J ′ ) = q ′ (J) = I. Therefore Proposition 3.3 is proved.

Note that the Lie product on L(E) is the image of " * " by Φ • q ′ . The pre-Lie product "⊲" is the image of "•" by Φ • q ′ . Hence, we recover Proposition 3.1 this way.

Example 3.1. The free magma M(E) can also be identified with the set of all planar binary rooted trees, with leaves decorated by the elements of E, together with the product "∨" defined in Section 2.1. For instance,

a • b = a b , (a • b) • c = a b c , a • (b • c) = a b c
, and z

= x • y = (a • b) • c • (d • e) =
f (z) = f (x • y) = |x| f (x) f (y) = |x| |a • b| f (a • b) f (c) |d| f (d) f (e) = |x| (|a| + |b|) |d| |a| f (a) f (b) f (c) f (d) f (e) = |a| |d| (|a| + |b|) (|a| + |b| + |c|) since, f (a) f (b) f (c) f (d) f (e) = 1 .
There is another description of f , detailed as follows: in a planar binary tree, there are two types of edges, going on the left (from bottom to top) or going on the right. Consequently, except the root, there are two types of vertices, the left ones (the incoming edge on the left) and the right ones. Let t be a planar binary tree, with leaves decorated by elements of E, then f (t) is the product over all left vertices v of the sums of the degree of the decorations of the leaves l with a path from v to l.

Consequently, from Propositions , 3.1, 3.2, 3.3, we get the following result.

Corollary 3.6.

There is a unique pre-Lie (respectively Lie) isomorphism between L ′ (E) and L(E), such that Φ(a mod.J ′ ) = a mod.J, for any a ∈ E.

A monomial well-order on the planar rooted trees, and applications

Let E be a disjoint union

E := n≥1 E n of finite subsets E n = {a n 1 , . . . , a n d n }
, where E n is the subset of all elements of E of degree n. Let us order the elements of E by:

a 1 1 < • • • < a 1 d 1 < a 2 1 < • • • < a 2 d 2 < • • • < a i 1 < • • • < a i d i < • • • (3.18)
Some particular sets E of generators can be considered:

(i) E = n≥1 E n ,
where #E i = 0 or 1. A particular situation is:

(a) take E = {a 1 , . . . , a s }, with a i ∈ E i , and |a i | = i, for i = 1, . . . , s.

(ii

) E = E 1 , where #E 1 = d 1 = d, as a special case: (a) take d 1 = d = 2.
The set T E pl forms the free magma generated by the set { a : for a ∈ E}, under the left Butcher product " • ց". Define a total order " " on T E pl as follows:

for any σ, τ ∈ T E pl , then σ τ if and only if

(3.19) (i) |σ| < |τ|, or : (ii) |σ| = |τ| and b(σ) < b(τ), or: (iii) |σ| = |τ|, b(σ) = b(τ) and (σ 1 , . . . , σ k ) (τ 1 , . . . , τ k ) lexicographically, where σ = B +,r (σ 1 . . . σ k ), τ = B +,r ′ (τ 1 . . . τ k ) , or: (iv) |σ| = |τ|, b(σ) = b(τ), (σ 1 , . . . , σ k ) = (τ 1 , .
. . , τ k ) and the root r of σ is strictly smaller than the root r ′ of τ.

where k = b(σ) is the number of branches of σ starting from the root. This order depends on an ordering of the generators, here we order them by:

a 1 1 ≺ • • • ≺ a 1 d 1 ≺ • • • ≺ a i 1 ≺ • • • ≺ a i d i ≺ • • • (3.20)
like in (3.18). The first terms in T E pl , when E = {a 1 , a 2 }, are ordered by " ≺ " as follows:

1 ≺ 2 ≺ 1 1 ≺ 2 1 ≺ 1 2 ≺ 1 1 1 ≺ 1 1 1 ≺ 2 2 ≺ 2 1 1 ≺ 1 2 1 ≺ 1 1 2 ≺ 2 1 1 ≺ 1 1 2 ≺ 1 2 1 ≺ 2 2 1 ≺ 2 1 2 ≺ 1 2 2 ≺ 2 1 2 ≺ 2 2 1
≺

1 2 2 ≺ 2 2 2 ≺ 2 2 2 ≺ • • • ,
where i is a shorthand notation for a i .

Proposition 3.7. The order " " defined in (3.19) is a monomial well-order.

Proof. Let σ, σ ′ ∈ T E pl , such that σ σ ′ . For any τ ∈ T E pl , we have:

|τ • ցσ| < |τ • ցσ ′ |, if |σ| < |σ ′ |,
(σ) < b(σ ′ ), then b(τ • ցσ) < b(τ • ցσ ′ ). But, if b(σ) = b(σ ′ ) = k, then b(τ • ցσ) = b(τ • ցσ ′ ) = k + 1. Lexicographically, (τ, σ 1 , . . . , σ k ) (τ, σ ′ 1 , . . . , σ ′ k ) when (σ 1 , . . . , σ k ) (σ ′ 1 , . . . , σ ′ k ).
The root of τ • ցσ is the root of σ, the same thing for τ • ցσ ′ holds. Then τ • ցσ τ • ցσ ′ . By the same way, one can verify that σ • ցτ σ ′• ցτ. Hence, the order " " is a monomial. Obviously, this order is a well-order.

The linear span of T E pl , call it T E pl , forms together with the product " • ց" the free K-magmatic algebra generated by a ; a ∈ E . In following, we review the work of T. Mora [START_REF] Mora | An introduction to commutative and non-commutative Gröbner bases[END_REF] on the Gröbner bases for the free Lie algebras in tree version. For any element f ∈ T E pl , define T ( f ) to be the maximal term of f with respect to the order " " defined in (3.19), and let lc( f ) be the coefficient of T ( f ) in f , for example:

if f = 1 1 1 + 2 1 1 + 2 1 1 2 , then T ( f ) = 1 1 2
, and lc( f ) = 2.

Let I be any (two-sided) ideal of T E pl . Define:

T (I) := T ( f ) ∈ T E pl : f ∈ I , O(I) := T E pl \T (I) (3.21)
to be subsets of the magma T E pl , where T (I) forms a (two-sided) ideal of T E pl .

Theorem 3.8. If I is a (two-sided) ideal of T E pl , then:

(i) T E pl = I ⊕ Span K (O(I)). (ii) T E, * pl := T E pl /I is isomorphic, as a K-vector space, to Span K (O(I)). (iii) For each f ∈ T E pl there is a unique g := Can( f, I) ∈ Span K (O(I)), such that f -g ∈ I. Moreover: (a) Can( f, I) = Can(g, I) if and only if f -g ∈ I. (b) Can( f, I) = 0 if and only if f ∈ I.
The symbol Can( f, I), which satisfies the identities above, is called the canonical form of f in Span K (O(I)).

Proof. The proof of this Theorem is detailed in [41, Theorem 1.1]. The procedure followed in the proof of (i) is by using the following algorithm:

f 0 := f, φ 0 := 0, h 0 := 0, i := 0 while f i 0 do If T ( f i ) / ∈ T (I) then φ i+1 := φ i , h i+1 := h i + lc( f i )T ( f i ), f i+1 := f i -lc( f i )T ( f i ) else %T ( f i ) ∈ T (I)% choose g i ∈ I, such that T (g i ) = T ( f i ), lc(g i ) = 1 φ i+1 := φ i + lc( f i )g i , h i+1 := h i , f i+1 := f i -lc( f i )g i i := i + 1 φ := φ i , h := h i .
The correctness of this algorithm is based on the following observations: ∀i :

φ i ∈ I, h i ∈ Span K (O(I)), f i + φ i + h i = f. Termination is guaranteed by the easy observation that if f n 0 then T ( f n ) < T ( f n-1
) and by the fact that < is a well-ordering.

Let J ′ be the two-sided ideal of T E pl generated by the pre-Lie identity and all elements on the form:

|σ|σ • ցτ + |τ|τ • ցσ, for any (non-empty) trees σ, τ ∈ T E pl . (3.22)
then we obtain that Can( f, J

′ ) = 3 2 1 2 1 + 2 3 3 1 -1 2 2 1 .
One can note that choosing different g's at each step in the procedures above while changing the intermediate computations would not change the final result. Theorem 3.8 does not describe the contents of each of T (I) and O(I). We try here to get a description of them, using the magma of planar rooted trees T E pl with its K-linear span T E pl . Let J be the (two-sided) ideal of T E pl generated by the pre-Lie identity with respect to the magmatic product " • ց". By Theorem 3.8, we have:

T E pl = J ⊕ Span K (O(J)). (3.23)
Proposition 3.9. O(J) = σ ∈ T E pl : for any v ∈ V(σ) the branches starting from v are displayed in non decreasing order from left to right .

We introduce the following lemma, which helps us to prove Proposition 3.9. Lemma 3.10. For any tree σ in T E pl , which does not verify the condition of Proposition 3.9, then σ is in T (J).

Proof. Let σ = B +, , r (σ 1 • • • σ k ) be a tree in T E
pl , with k branches for k ≥ 2 starting from the root, such that σ i-1 ≻ σ i , for some i = 1, . . . , k -1. We find that:

f = r σ 1 σ i-1 σ i . . . . . . σ k - r σ 1 σ i σ i-1 . . . . . . σ k + r σ 1 σ i-1 σ i . . . . . . σ k - r σ 1 σ i σ i-1 . . . . . . σ k , (3.24)
is an element in J such that T ( f ) = σ. If the branches start from a vertex v different from the root, the subtree σ v , obtained by taking v as a root, is a factor of the tree σ. It is easily seen that σ is the leading term of the element f ∈ J obtained by replacing the factor σ v by the corresponding factor given by (3.24).

As a consequence of Lemma 3.10, we get the following natural result.

Corollary 3.11. O(J) is contained in the set σ ∈ T E pl : σ has non decreasing branches .

Proof of Proposition 3.9. Using the graduation of T E pl , with respect to the degree of trees therein, there is a one-to-one bijection between the subset σ ∈ T E pl : σ has non decreasing branches n and the the homogeneous component T E n of all E-decorated (non-planar) rooted trees of degree n, i.e.:

# σ ∈ T E pl : σ has non decreasing branches n = #T E n , for all n ≥ 1. But, O(J) n =T E n , for all n ≥ 1, have the same cardinality, hence coincide according to Corollary 3.11:

O(J) = σ ∈ T E pl : σ has non decreasing branches . (3.25)
This proves the Proposition 3.9.

In the next Theorem, we try to describe the set O(J ′ ) for the ideal J ′ defined above by (3.22).

Theorem 3.12. The set O(J ′ ) is a set of ladders, or equivalently, the magmatic ideal T (J ′ ) contains all the trees which are not ladders.

Proof. We use here the induction on the number "n" of vertices. Let σ be a tree in T E pl , which is not a ladder, with k branches (starting from the root) and n vertices. Since σ is not a ladder, then n must be greater than or equal to 3. If n = 3, and k = 1 then σ is a ladder. Hence, for k = 2, we have that:

σ = r x y is an element of T (J ′ ), since there is f = |x| r x y + |y| + |r| x r y in J ′ , such that T ( f ) = σ, for any x, y, r ∈ E. Also, for any τ ∈ T E pl , the elements σ • ցτ and τ • ցσ are in T (J ′ ) (since T (J ′ ) is an ideal).
Suppose that any (no-ladder) tree in T E pl with q vertices, where q < n, is an element in T (J ′ ), let σ ∈ T E pl with "n" vertices and "k" branches, which is not a ladder, then: (i) If k = 1, the tree σ is written σ • ց r , where σ is not a ladder. Then σ ∈ T (J ′ ) by the induction hypothesis, hence σ ∈ T (J ′ ) because T (J ′ ) is an ideal. (ii) The case k = 2. This corresponds to the case σ = σ • ցl m , where l m is a ladder in T E pl , with m vertices for m ≥ 2. If σ is an element of T (J ′ ) then so is σ. If not, σ is a ladder by the induction hypothesis. See the discussion below. (iii) The case k ≥ 3. These are trees σ = σ • ցτ where τ ∈ T E pl , with k -1 branches, is not a ladder. We have then σ ∈ T (J ′ ) by induction hypothesis.

Let us discuss the case (ii) when σ is a ladder and the ladder l m does not belong to T (J ′ ). Let l 1 , l 2 be ladders in T E pl with n 1 , n 2 vertices respectively, where n 1 , n 2 < n, and let:

σ = r l 1 l 2 = l 1 • ց(l 2 • ց r ), σ ′ = r l 2 l 1 = l 2 • ց(l 1 • ց r ). (3.26)
By the pre-Lie identity, with respect to the left Butcher product " • ց", we find the following element:

f 0 = r l 1 l 2 - r l 1 l 2 + r l 2 l 1 - r l 2 l 1 (3.27)
in J ′ , such that σ, σ ′ are bigger trees, with respect to the order defined in (3.19), than the two other trees in f 0 . Let |l i | = p i , where p i > 0, for i = 1, 2. We have the following cases for p i :

(i) Either p 1 = p 2 , then in this case we take the elements:

g = p 2 r l 2 l 1 + (p 1 + |r|) l 2 l 1 r , f 1 = r 1 l (1) 2 l 1 r - r 1 l (1) 2 l 1 r + r 1 l 1 l (1) 2 r - r 1 r l 1 l (1) 2 , (3.28)
in J ′ , where

l 2 = l (1) 2 • ց r 1
. Then we get the element:

f = p 2 f 0 + g -(p 1 + |r|) f 1 ∈ J ′ , (3.29)
such that T ( f ) = σ, since:

r 1 r l 1 l (1) 2 ≺ r l 1 l 2
, for the order " ".

(ii) Or, p 2 < p 1 , then σ = T ( f 0 ), where f 0 is the element described in (3.27), hence σ ∈ T (J ′ ). (iii) Or, p 1 < p 2 , here we have that σ ≺ σ ′ and the element f 0 described in (3.27) is an element in J ′ such that T ( f 0 ) = σ ′ , hence σ ′ ∈ T (J ′ ). Now, for σ we can get an element in J ′ such that σ becomes the leading term of this element, as follows: we replace the tree σ ′ = l 2 • ց(l 1 • ց r ) in f 0 by the tree:

σ ′′ := l 1 • ց r • ցl 2 = l 2 l 1 r , (3.30)
using the element g described in (3.28). This new tree σ ′′ is also greater than σ with respect to the order " ". By the pre-Lie identity, we can get the element f described in (3.29) such that:

σ and σ ′ 1 := l (1) 2 • ց l 1 • ց r • ց r 1 = r 1 r l 1 l (1)
2 are the two biggest trees appearing in this element.

We verify whether p

1 = |l 1 | > |l (1) 2 | = p 2 -|r 1 |, i.e. σ ′ 1 σ, or not. If so, then σ ∈ T (J ′ ). If not, we replace σ ′
1 in f by the tree:

σ ′′ 1 := l 1 • ց r • ց r 1 • ցl (1) 2 = l (1) 2 r 1 l 1 r . (3.31)
If n 2 = 1, the tree σ ′′ 1 is a ladder. If n 2 ≥ 2, then σ ′′ 1 is not a ladder and is greater than σ. Then we need to apply the pre-Lie identity once again to the tree σ ′′ 1 in (3.31), and replace it by:

σ ′ 2 := l (2) 2 • ց l 1 • ց r • ց r 1 • ց r 2 = r 2 r 1 r l 1 l (2) 2
, where l (2) 2

• ց r 2 = l (1) 2 . Let p (i) 2 = |l (i) 2 |, where l 2 = (• • • ((l (i) 2 • ց r i ) • ց r i-1 ) • • • ) • ց r 1
, for i ≥ 1. After a finite number s of steps applying the pre-Lie identity in the expression:

σ ′′ s := • • • (l 1 • ց r ) • ց r 1 • • • • ց r s-1 • ց l (s) 2 • ց r s = r s l (s) 2 r l 1 r s-1
, where

σ ′ s = r s r s-1 r l 1 l (s) 2 (3.32)
which can be formulated as:

f s = r s l (s) 2 r l 1 r s-1 - r s l (s) 2 r s-1 r l 1 + r s r s-1 r l 1 l (s) 2 - r s r s-1 r l 1 l (s) 2 ∈ J ′ , (3.33)
we can find an element f ∈ J ′ , such that σ and σ ′ s become bigger trees of f with p (s) 2 < p 1 , i.e. σ ′ s ≺ σ. Hence, σ described in (3.26) is in T (J ′ ). Then, Theorem 3.12 is proved.

A monomial basis for the free Lie algebra

The set T E forms the free Non-Associative Permutive (NAP) magma generated by the set { a : for a ∈ E}, under the usual Butcher product . Corresponding to the total order defined in (3.19)

(iv) |s| = |t|, b(s) = b(t) = k, s l = t l
, for all l = 1, . . . , k and r ≤ r ′ , where r (respectively r ′ ) is the root of s (respectively t).

By the same way as in Proposition 3.7, we observe that the order " " defined in (3.34) is a monomial well order. The space T E forms with the Butcher product the free NAP algebra generated by E [START_REF] Livernet | A rigidity theorem for pre-Lie algebras[END_REF]. We introduced, in our preceding work in Section 2.1.2, a section S from the NAP algebra (T E , ) into the magmatic algebra (T E pl , • ց):

(T E pl , • ց) π / / / / (T E , ).

S o o

Here, we choose S (t) = S min (t) := Min τ ∈ T E pl : π(τ) = t , for any t ∈ T E , where Min {-} means that we choose the minimal element τ in T E pl with respect to the order " " with π(τ) = t. Proposition 3.13. The section map S min defined above is an increasing map.

Proof. Take two trees s and t in T E with s t. The section S min , obviously, respects the degree and the number of branches of the trees. Hence, we can suppose |s| = |t| and b(s) = b(t) = l. We have then:

s = B +,r (s 1 , . . . , s l ), t = B +,r ′ (t 1 , . . . , t l ), with s 1 • • • s l , t 1 • • • t l . ( 3
, t ∈ T E , if s ′ s then s ′ → v t s → v t, for v ∈ V(t).
Proof. Immediate from the definition (3.34) of the order " ". Lemma 3.16. Let s, s ′ ∈ T E , if s R s ′ then s ′ ≺ s. Proof. For s, s ′ ∈ T E , if sRs ′ , then by definition of the relation R in (3.36), there are t, t ′ ∈ T E and v, w ∈ V(t) such that s = t → v t ′ , s ′ = t → w t ′ , and an edge v w in t ′ . Obviously, the tree obtained by grafting t on the tree t ′ at v is greater, with respect to the order " ", than the tree deduced by grafting t on t ′ at w, i.e s ′ ≺ s. The passage from R to R is obvious. Proposition 3.17. The Butcher product " " is compatible with the relation R, i.e. for s, s ′ , t ∈ T E , if sRs ′ then (s t)R(s ′ t) and (t s)R(t s ′ ). Also, if sRs ′ and tRt ′ then (s t) R (s ′ t ′ ), for t ′ ∈ T E .

Proof. For any s, s ′ , t, t ′ ∈ T E , if sRs ′ and tRt ′ , then by definition of R we have:

s = s 1 → v s 2 , s ′ = s 1 → w s 2 , for v, w ∈ V(s 2 ), with v w in s 2 , and t = t 1 → u t 2 , t ′ = t 1 → w ′ t 2 , for u, w ′ ∈ V(t 2 ), with u w ′ in t 2 . Let: s t = (s 1 → v s 2 ) (t 1 → u t 2 ) = s 1 → v s ′′ , for v ∈ V(s ′′ )
, where s ′′ = s 2 t, and

s ′ t = (s 1 → w s 2 ) (t 1 → u t 2 ) = s 1 → w s ′′ , for v w in s ′′ , then: s t = (s 1 → v s ′′ )R(s 1 → w s ′′ ) = s ′ t.
(3.37) Also, for

s ′ t ′ = (s 1 → w s 2 ) (t 1 → w ′ t 2 ) = t 1 → w ′ s ′′′ , where s ′′′ = s ′ t 2 , with w ′ ∈ V(t 2 ) ⊂ V(s ′′′ ), and s ′ t = (s 1 → w s 2 ) (t 1 → u t 2 ) = t 1 → u s ′′′ , for u ∈ V(s ′′′
). Then we have:

s ′ tRs ′ t ′ . ( 3
Ψ S min (t) = s∈[t] R β S min (s, t)s, (3.40)
(T E pl , • ց)

Ψ / / π (T E pl , ց) π (T E , ) Ψ S min / / S min O O (T E , →) Figure 3.2.
where the map Ψ S min and the coefficients β S min (s, t) are described in Corollary 2.5.

Proof. We prove this Lemma by the induction on the number of vertices of the tree. Suppose that (3.40) is realized for any tree in T E with a number of vertices less than or equal to n. Take t ∈ T E be a tree, such that #V(t) = n + 1 and t = t 1 t 2 , where t 1 is the minimal branch of t with respect to the order " ". Then we have:

Ψ S min (t) = Ψ S min (t 1 t 2 ) = Ψ • S min (t 1 t 2 ) = Ψ S min (t 1 ) • ցS min (t 2 ) = π Ψ • S min (t 1 ) ց Ψ • S min (t 2 ) = Ψ S min (t 1 ) → Ψ S min (t 2 ) =              s ′ ∈[t 1 ] R β S min (s ′ , t 1 )s ′              →              s ′′ ∈[t 2 ] R β S min (s ′′ , t 2 )s ′′              = s ′ ∈[t 1 ] R s ′′ ∈[t 2 ] R β S min (s ′ , t 1 ) β S min (s ′′ , t 2 ) s ′ → s ′′ .
From Proposition 3.17, we have that:

t = t 1 t 2 R s := s ′ s ′′ R s ′ → v s ′′ , for v ∈ V(s ′′ ). (3.41)
Let s v be the smallest branch of the tree s, defined above in (3.41), starting from v, and s v be the corresponding trunk (what remains when the branch s v is removed). Then we have:

β S min (s, t) = v∈V(s) β S min (s v , t 1 ) β S min (s v , t 2 ). (3.42)
The formula (3.42) above is induced by the formula (2.8) and the definition of the coefficients β S min (s, t) described in Corollary 2.5. Hence, we get:

Ψ S min (t) = s∈[t] R
β S min (s, t)s.

Corollary 3.19. Let t ∈ T E , then the maximal term T Ψ S min (t) , with respect to the order defined in (3.34), of Ψ S min (t) is the tree t itself.

From our preceding work in Chapter 2, we have that the set B = Ψ S min (t) : t ∈ T E forms a monomial basis for the free pre-Lie algebra T E , → . Let I be the (two-sided) ideal generated by the elements on the form described in (3.9), then we have the following commutative diagram:

T E , → q / / / / Φ L ′ (E), ⊲ * = q q q q q x x q q q q q L(E), ⊲ where L ′ (E) = T E /I, and the product ⊲ * is the pre-Lie product defined in (3.10). L(E) is the free Lie algebra generated by E which carries the pre-Lie algebra structure by the product ⊲ defined in (3.2). The restriction of Φ to Span K (O(I)) is an injective map. Indeed, for any

h 1 , h 2 , ∈ Span K (O(I)), Φ(h 1 ) = Φ(h 2 ) ⇒ Φ(h 1 -h 2 ) = 0 ⇒ (h 1 -h 2 ) ∈ Ker Φ = I ⇒ (h 1 -h 2 ) ∈ Span K (O(I)) ∩ I = 0 ⇒ h 1 -h 2 = 0 ⇒ h 1 = h 2 .
Also, since Φ : T E -→ L(E) is a surjective map, then we have: Proof. The property (3.43) is induced from Theorem 3.12 and the definition of Ψ S min . We obviously have that the set B ′ = O(I) is a basis for Span K (O(I)). Therefore, as Φ : Span K (O(I)) -→ L(E) is an isomorphism of vector spaces, B := Φ(B ′ ) forms a basis for the pre-Lie algebra L(E), ⊲ . This basis is monomial thanks to (3.43), such that:

L(E) = Φ T E = Φ I ⊕
Φ(t) = Φ Ψ S min (t) , for all t ∈ O(I).
This proves Theorem 3.20.

Consequently, we get the following immediate result.

B T E 1 = { a 1 : a 1 ∈ E} . B T E 2 = { a 2 : a 2 ∈ E} ⊔ a 1 a 1 : a 1 ∈ E . B T E 3 = { a 3 : a 3 ∈ E} ⊔ a 2 a 1 , a 1 a 2 : a 1 , a 2 ∈ E ⊔            a 1 a 1 a 1 , a 1 a 1 a 1 + a 1 a 1 a 1 : a 1 ∈ E            . B T E 4 = { a 4 : a 4 ∈ E} ⊔ a 3 a 1 , a 1 a 3 , a 2 a 2 : a 1 , a 2 , a 3 ∈ E ⊔            a 2 a 1 a 1 , a 1 a 2 a 1 , a 1 a 1 a 2 , a 2 a 1 a 1 + a 2 a 1 a 1 , a 1 a 1 a 2 + a 1 a 2 a 1 : a 1 , a 2 ∈ E            ⊔                    a 1 a 1 a 1 a 1 , a 1 a 1 a 1 a 1 + a 1 a 1 a 1 a 1 , a 1 a 1 a 1 a 1 + a 1 a 1 a 1 a 1 + a 1 a 1 a 1 a 1 , a 1 a 1 a 1 a 1 + 3 a 1 a 1 a 1 a 1 + a 1 a 1 a 1 a 1 + a 1 a 1 a 1 a 1 : a 1 ∈ E                    .
Then, we get the following monomial bases B n for L n , up to n = 4: identity described in (3.9), we have, drawing non-planar trees explicitly:

f 1 = Ψ • ց • ց -• ց -• ց • ց + • ց • ց = Ψ - - + , f 2 = Ψ • ց + 2 • ց • ց = Ψ + 2 , and f 3 = Ψ • ց + 3 • ց = Ψ + 3 are elements in I, hence f 4 = f 1 + f 2 -f 3 = Ψ 3 -3 - ∈ I. But, f 5 = Ψ ∈ I, hence f = f 4 + f 5 = 3 -3 ∈ I.
Then, we have:

Φ( f ) = 3 (x ⊲ y) ⊲ x ⊲ y -3 (x ⊲ y) ⊲ y ⊲ x -(x ⊲ y) ⊲ (y ⊲ x) = [[x, y], x], y -[[x, y], y], x + [[x, y], [x, y] = 0 ,

Pre-Lie Magnus expansion

Wilhelm Magnus (1907Magnus ( -1990) is a topologist, an algebraist, an authority on differential equations and on special functions, a mathematical physicist. He worked in a wide variety of fields in mathematics and mathematical physics. One of his long-lasting constructions is the so-called Magnus expansion, it is a tool to solve the classical linear differential equations for linear operators [START_REF] Magnus | On the Exponential Solution of Differential Equations for a Linear Operator[END_REF]. This expansion has found applications in numerous areas, in particular in quantum chemistry and theoretical physics.

Many attempts have been made to derive the expansion in explicit form. We refer the reader to the recent works, e.g. [START_REF] Iserles | No / rsett, On the solution of linear differential equations in Lie groups[END_REF], [START_REF] Iserles | Expansions that grow on trees[END_REF], [START_REF] Chapoton | Enveloping algebras of pre-Lie algebras, Solomon Idempotents and the Magnus Formula[END_REF], and the references therein, for more details about this expansion and some of its applications.

The aim of this chapter is to discuss how we can find a recursion for the pre-Lie Magnus expansion which already incorporates the pre-Lie identity. For this purpose, we study some methods for writing Magnus expansion, in classical and pre-Lie versions. Here, we skip the analytical and numerical aspects of this expansion, and take an algebro-combinatorial perspective. A numerical method has been studied by three authors S. Blanes, F. Casas, and J. Ros, in their joint work [START_REF] Blanes | Improved High Order Integrators based on the Magnus Expansion[END_REF], of writing the classical Magnus expansion. We give, in section 4.4 of this chapter, a combinatorial vision of this numerical method. This chapter contains four sections: we give, in section 4.1, a short survey of the classical Magnus expansion. In section 4.2, we recall some basics on the pre-Lie Magnus expansion, and show how the classical Magnus expansion is a particular case of it. Also, we review in this section a part of the joint work [START_REF] Chapoton | Enveloping algebras of pre-Lie algebras, Solomon Idempotents and the Magnus Formula[END_REF] of F. Chapoton and F. Patras, where they introduced a concrete formula for the pre-Lie Magnus expansion. We study, in section 4.3, some encodings of Magnus expansion terms using planar binary rooted trees, proposed by A. Iserles and S. P. No / rsett in their work [START_REF] Iserles | No / rsett, On the solution of linear differential equations in Lie groups[END_REF] for the classical version, and an encoding using planar rooted trees which has been studied by K. Ebrahimi-Fard and D. Manchon for the pre-Lie version [START_REF] Ebrahimi-Fard | Dendriform Equations[END_REF]. Also, in this section, we give a formula with the minimal number of terms up to order seven, and we compare it with the pre-Lie Magnus formula proposed by F. Chapoton and F. Patras in [START_REF] Chapoton | Enveloping algebras of pre-Lie algebras, Solomon Idempotents and the Magnus Formula[END_REF], using Grossman-Larson algebra. The question, raised by K. Ebrahimi-Fard, of writing an optimal (i.e. with a minimal number of terms) pre-Lie Magnus expansion at any order remains open. In section 4.4, we review a part of the joint work of S. Blanes, F. Casas, and J. Ros [START_REF] Blanes | Improved High Order Integrators based on the Magnus Expansion[END_REF], in 63 where Ω 1 (t) = t 0 A(s) ds, and in general:

Ω n (t) = n-1 j=1 B j j! t 0 S ( j) n (s) ds, for n ≥ 2, ( 4.5)
where S (1) n = [Ω n-1 , A], S (n-1) n = ad n-1 Ω 1 A , and:

S ( j) n = n-j m=1 Ω m , S ( j-1) n-m , for 2 ≤ j ≤ n -1.
The formula (4.5) can be found in [START_REF] Magnus | On the Exponential Solution of Differential Equations for a Linear Operator[END_REF], [START_REF] Blanes | The Magnus expansion and some of its applications[END_REF].

Pre-Lie Magnus expansion

In this section, we study an important generalization of the Magnus expansion in the pre-Lie setting: let (PL, ⊲) be a pre-Lie algebra defined over a field K. The linear transformations L A , for A ∈ PL, described in Section 1.4, can be detailed as L A : PL → PL, such that L A (B) := A ⊲ B, for all B ∈ PL. Define Ω := Ω(λA), for A ∈ PL, to be a formal power series in λPL [[λ]]. Now, the classical Magnus expansion, described in (4.3), can be rewritten as:

Ω(λA)(x) = L ⊲ [ Ω] exp(L ⊲ [ Ω]) -1 (λA)(x) = m≥0 B m m! L ⊲ [ Ω] m (λA)(x), (4.6)
where

L ⊲ [ Ω] λA (x) = Ω⊲λA (x) = [ x 0
Ω(s)ds, λA(x)], B m are Bernoulli numbers, this formula is called pre-Lie Magnus expansion [START_REF] Agrachev | Chronological algebras and nonstationary vector fields[END_REF], [START_REF] Ebrahimi-Fard | A Magnus-and Fer-type Formula in Dendriform Algebras[END_REF].

Lemma 4.1. Let A, B be linear operators depending on a real variable x, then the product:

(A ⊲ B)(x) := x 0 A(s)ds, B(x) , (4.7)
verifies the pre-Lie identity, where

[A(x), B(x)] = (A • B -B • A)(x).
Proof. Let A, B, C be linear operators depending on a real variable x. Set I(A)(x) :=

x 0 A(s)ds, then we have:

I(A) • I(B) = I I(A) • B + A • I(B) , (4.8)
In other words, I is a weight zero Rota-Baxter operator 1 . Hence, 1 For more details about Rota-Baxter operator, Rota-Baxter algebras see [20, Paragraph 5.2] and the references therein.

terms can be reduced as follows:

Ω4 (λA) = λ 4 1 8 ((A ⊲ A) ⊲ A) ⊲ A + 1 24 (A ⊲ (A ⊲ A)) ⊲ A + A ⊲ ((A ⊲ A) ⊲ A) + (A ⊲ A) ⊲ (A ⊲ A) (4.
12) and, by pre-Lie identity, we have:

(A ⊲ A) ⊲ (A ⊲ A) = ((A ⊲ A) ⊲ A) ⊲ A -(A ⊲ (A ⊲ A)) ⊲ A + A ⊲ ((A ⊲ A) ⊲ A),
then (4.12) equals:

λ 4 1 6 ((A ⊲ A) ⊲ A) ⊲ A + 1 12 x ⊲ ((A ⊲ A) ⊲ A) .
At fifth order, Ω5 (λA), three terms out of ten can be removed [START_REF] Ebrahimi-Fard | A Magnus-and Fer-type Formula in Dendriform Algebras[END_REF]. For more details about this reduction of pre-Lie Magnus expansion terms, see the next sections.

A beautiful way of writing the pre-Lie Magnus expansion is proposed by F. Chapoton and F. Patras in their joint work [START_REF] Chapoton | Enveloping algebras of pre-Lie algebras, Solomon Idempotents and the Magnus Formula[END_REF]. We review here a part of their work corresponding to pre-Lie Magnus element, as follows: let PL(a), ⊲ be the free pre-Lie algebra with one generator "a", and PL(a) be its completion2 . The Magnus element in PL(a) is the (necessarily unique) solution Ω to the equation:

Ω = Ω exp( Ω) -1 ⊲ a. ( 4.13)
The exponential series exp(a) := n≥0 a n n! belongs to S PL , the completion of the symmetric algebra over PL(a), endowed with its usual commutative algebra structure. We give in following an important result obtained by F. Chapoton and F. Patras in [START_REF] Chapoton | Enveloping algebras of pre-Lie algebras, Solomon Idempotents and the Magnus Formula[END_REF]. where * is the Grossman-Larson product 3 . The notation log * means that the logarithm is computed with respect to the product * .

Proof. See [START_REF] Chapoton | Enveloping algebras of pre-Lie algebras, Solomon Idempotents and the Magnus Formula[END_REF]Theorem 4].

An approach for Magnus expansion terms using rooted trees

A. Iserles and S. P. No / rsett have developed an alternative approach, using planar binary rooted trees to encode the classical Magnus expansion terms [START_REF] Iserles | No / rsett, On the solution of linear differential equations in Lie groups[END_REF]. K. Ebrahimi-Fard and D. Manchon, in their joint work [START_REF] Ebrahimi-Fard | Dendriform Equations[END_REF], used planar rooted trees to represent the pre-Lie Magnus expansion. This encoding of expansion terms, using planar binary rooted trees, is defined as:

x , x ⊲ x .
Hence, the pre-Lie Magnus expansion, described in (4.11), can be denoted in the shorthand as:

Ω( ) = - 1 2 + 1 4 + 1 12 - 1 8 + 1 24 + + + • • • (4.15)
and the reduction in expansion terms at the fourth order can be described as:

Ω4 ( ) = - 1 6 - 1 12 ,
thanks to the pre-Lie identity:

- = - .
The approach proposed by K. Ebrahimi-Fard and D. Manchon is more in the line of noncommutative Butcher series 4 . In following, we shall review the joint work of K. Ebrahimi-Fard and D. Manchon, published in [START_REF] Ebrahimi-Fard | Dendriform Equations[END_REF], on finding an explicit formula, in planar rooted tree version, for pre-Lie Magnus expansion. Let σ = B + (σ 1 • • • σ k ) be any (undecorated) planar rooted tree, denote f (v), for v ∈ V(σ), by the number of outgoing edges, i.e. the fertility of the vertex v of σ. The degree |σ| of a tree here is given by the number of its vertices. Define the linear map γ : T pl → K as:

γ(σ) := B k k! k i=1 γ(σ i ) = v ∈V(σ) B f (v) f (v)! , (4.16)
where B k are Bernoulli numbers.

Lemma 4.3. For any planar rooted tree τ, such that there exists v ∈ V(τ) of fertility 2n+1, n > 0, we have γ(τ) = 0.

Proof. It is immediate from the definition of γ in (4.16), and the fact that B 2n+1 = 0, for all n > 0.

Define a subspace T e1 pl of all planar rooted trees excluding trees with at least one vertex of fertility 2n + 1, with n > 0. The tree functional F is defined recursively by:

F[ ](x) = x, and F[τ](x) := r (k+1) ⊲ F[τ 1 ](x), . . . , F[τ k ](x), x , (4.17)
where

τ = B + (τ 1 • • • τ k ), and
r (k+1) ⊲ F[τ 1 ](x), . . . , F[τ k ](x), x := F[τ 1 ](x) ⊲ (F[τ 2 ](x) ⊲ (• • • ⊲ (F[τ k ](x) ⊲ x) • • • )).
Theorem 4.4. The pre-Lie Magnus expansion can be written: Proof. Immediate from Theorem 4.4 and Lemma 4.5, and using the formula:

Ω(x) = τ∈T e1 pl γ(τ)F[τ](x). ( 4
Ψ(τ) = s ∈T α(s, τ)s, that is introduced by [2, Theorem 4].
Now for any τ ∈ T e1 pl , let e τ := Ψ(τ). The planar rooted tree τ is uniquely written as a monomial expression m( , • ց) involving the root and the left Butcher product. Then Ψ(τ) is m( , →), i.e. the same monomial expression where the left Butcher product is replaced by the pre-Lie grafting of (non-planar) rooted trees. Here, we display optimal (with respect to the number of terms) formulas of pre-Lie Magnus expansion up to order seven: Due to the recursive nature of the pre-Lie Magnus expansion at the orders calculated above, and thanks to the pre-Lie identity, we observe that many terms e τ are omitted in this expansion, for example: (i) At order four, two terms e τ out of 4 can be removed in Ω4 ( ), namely e , e .

Ω1 ( ) = Ω2 ( ) = B 1 e Ω3 ( ) = B 2 1 e + B 2 2! e Ω4 ( ) = B 1 3 e + B 1 B 2 e Ω5 ( ) = -B 1 B 2 2! 5 2 e -B 1 B 2 2! 1 2 e + B 2 1 B 2 e + B 2 1 B 2 2! e + B 2
(ii) At order five, three terms e τ out of 10 can be removed in Ω5 ( ), the trees of these omitted terms are:

, , .

(iii) At order six, the terms of 11 out of 26 trees can be removed in Ω6 ( ), these trees are:

, , , , , , , , , , .

(iv) At order seven, the terms of 23 out of 73 trees can be removed in Ω7 ( ).

Remark 4.7. This reduction of pre-Lie Magnus expansion terms is not unique, for example, at order five, we can write the formula Ω5 ( ) with another seven reduced terms, as follows:

Ω5 ( ) = B 2 1 B 2 3 2 e + B 2 1 B 2 3 2 e + B 2 1 B 2 e + B 2 1 B 2 2! e + B 2 2 2!2! (e + e ) + B 4 4! e .
Now, from the joint works of F. Patras with F. Chapoton [START_REF] Chapoton | Enveloping algebras of pre-Lie algebras, Solomon Idempotents and the Magnus Formula[END_REF], and with K. Ebrahimi-Fard [START_REF] Ebrahimi-Fard | The pre-Lie structure of the time-ordered exponential[END_REF], recall that: a (non-planar) forest F = t 1 • • • t n is a commutative product of (non-planar) rooted trees t i . Denote w(F) by the number of trees in F, which is called the weight of a forest F, for example w(t 1 • • • t n ) = n. Let F be the linear span of the set of (non-planar) forests, it forms together with the concatenation an associative commutative algebra. Define another product " * " on F by:

(t 1 • • • t n ) * (t ′ 1 • • • t ′ m ) := f F 0 (F 1 → t 1 ) • • • (F n → t n ), (4.22)
where the sum is over all function f from {1, . . . , m} to {0, . . . , n}, and

F i := j ∈ f -1 (i) t ′ j .
The space F forms an associative non-commutative algebra together with the product " * " defined above. This algebra can be provided with a unit element, sometimes it is the empty tree. This unital algebra is called the Grossman-Larson algebra and denoted by GL := F . This algebra acts naturally on T by the extending pre-Lie product "→". This action can be defined recursively by:

F * F ′ → t := F ′ → F → t , (4.23)
for any F, F ′ ∈ GL and t is a (non-planar) rooted tree.

Example 4.1. For any t, t 1 , t 2 (non-planar) rooted trees, we have:

(t 1 t 2 ) → t = t 2 → (t 1 → t) -(t 2 → t 1 ) → t.
The Grossman-Larson algebra GL, * is isomorphic to the enveloping algebra of the underlying Lie algebra of T , → . This construction also works for the enveloping algebra of any pre-Lie algebra [START_REF] Guin | On the Lie enveloping algebra of a pre-Lie algebra[END_REF]. We refer the reader to the references [START_REF] Guin | On the Lie enveloping algebra of a pre-Lie algebra[END_REF], [START_REF] Chapoton | Enveloping algebras of pre-Lie algebras, Solomon Idempotents and the Magnus Formula[END_REF], [START_REF] Ebrahimi-Fard | The pre-Lie structure of the time-ordered exponential[END_REF], for more details about this type of algebras and some of its applications. Hence, the formula of pre-Lie Magnus expansion described in (4. where e = exp( ) := n≥0 n n! , for F = n is a forest of one-vertex trees with weight w(F) = n, and " * " is the Grossman-Larson product.

Ω 1 = q 1 + 1 12 q 3 + 1 80 q 5 + 1 448 q 7

.

Ω 2 = -1 12
[q 1 , q 2 ] + -1 80 [q 1 , q 4 ] + 1 240

[q 2 , q 3 ] + -1 448 [q 1 , q 6 ] + 1 2240

[q 2 , q 5 ] -1 1344

[q 3 , q 4 ] .

Ω 3 = 1 360
[q 1 , [q 1 , q 3 ]] -1 240 [q 2 , [q 1 , q 2 ]] + 1 1680

[q 1 , [q 1 , q 5 ]] -1 2240

[q 1 , [q 2 , q 4 ]] + 1 6720

[q 2 , [q 2 , q 3 ]]+ 1 6048

[q 3 , [q 1 , q 3 ]] -1 840

[q 4 , [q 1 , q 2 ]] .

Ω 4 = 1 720
[q 1 , [q 1 , [q 1 , q 2 ]]] + 1 6720

[q 1 , [q 1 , [q 1 , q 4 ]]] -1 7560

[q 1 , [q 1 , [q 2 , q 3 ]]] + 1 4032

[q 1 , [q 3 , [q 1 , q 2 ]]]+ 11 60480

[q 2 , [q 1 , [q 1 , q 3 ]]] -1 6720

[q 2 , [q 2 , [q 1 , q 2 ]]] .

Ω 5 = -1 15120 [q 1 , [q 1 , [q 1 , [q 1 , q 3 ]]]] - 1 30240 [q 1 , [q 1 , [q 2 , [q 1 , q 2 ]]]] + 1 7560 [q 2 , [q 1 , [q 1 , [q 1 , q 2 ]]]]
.

Ω 6 = -1 30240
[q 1 , [q 1 , [q 1 , [q 1 , [q 1 , q 2 ]]]]],

where q i = a i-1 h i , for i ≥ 1, are matrices.

The set E := {q i : i ∈ N} can be considered as a generating set of a graded free Lie algebra, with |q i | = i [START_REF] Munthe-Kaas | Computations in a free Lie algebra[END_REF]. In their computations, S. Blanes, F. Casas, and J. Ros computed the dimensions of the graded free Lie algebra L(E) generated by the set E, according to Munthe-Kaas and Owren's work [START_REF] Munthe-Kaas | Computations in a free Lie algebra[END_REF]. Also, they computed the number of elements of the Lie algebra L(E) appearing in the Magnus expansion, when a Taylor series of A(t) around t = t 0 and t = t 1 2 respectively.

Here, we review some of their computations as follows: at the order s = 4, we have dim ≤ 4 L = 7, with basis elements q 1 , q 2 , q 3 , q 4 , [q 1 , q 2 ], [q 1 , q 3 ], [q 1 , [q 1 , q 2 ]], such that six of these elements appear in Magnus expansion around t = t 0 , that are: q 1 , q 2 , q 3 , q 4 , [q 1 , q 2 ], [q 1 , q 3 ], with two commutators. Whereas, three elements, q 1 , q 3 , [q 1 , q 2 ], only appear in Magnus expansion around t = t 1 2 , with one commutator, as it is shown above. For more details about these results see [4, section 3, pages 439-441]. Now, we try to introduce a combinatorial vision of the work above, using the notion of the monomial basis for free Lie algebra L(E), that we obtained in Chapter 3. Let PL( ) (respectively PL(E)) be the free pre-Lie algebra with one generator " " (respectively generated by the set a i : a i ∈ E ), together with the grafting "→". Denote PL( ) (respectively PL(E)) by the completion of PL( ) (respectively PL(E)) with respect to the filtration given by the degree, which are pre-Lie algebras together with the pre-Lie grafting. Let a = e∈E λ e e be an element in PL(E), that is an infinite linear combination of the generators e , e ∈ E.

Define the map G a : PL( ) → PL(E) to be the unique pre-Lie homomorphism that is induced by the universal property of the freeness of PL( ): where Ψ : T E pl → T E , in the right hand side, is defined in Subsection 2.1.2 (we use the same letter for the undecorated version from T pl onto T ), and where τ δ ∈ T E pl is the tree τ decorated according to the map δ.

{ } i / / f " " E E E E E E E E PL( ) G a PL(E)
Proof. Let τ be any (undecorated) planar rooted tree, we have that Ψ(τ) = m( , →) is a monomial, in PL( ), of the one-vertex tree " " multiplied (by itself) using the pre-Lie product "→". From the definition of G a above, we get:

G a Ψ(τ) = G a m( , →) = m(a, →), (4.28)
where m(a, →) is the monomial of "a", in PL(E), induced from the monomial m( , →) by sending the one-vertex tree into its image G a ( ) = a.

We proceed by induction on the number n of vertices, the case n = 1 being obvious. Suppose that the formula (4.27) is true up to n -1 vertices. Let τ ∈ T n pl , we have that τ can be written in a unique way as τ = τ 1 • ցτ 2 , hence:

G a Ψ(τ) = G a Ψ(τ 1 • ցτ 2 )
= G a Ψ(τ 1 ) → Ψ(τ 2 )

= G a Ψ(τ 1 ) → G a Ψ(τ 2 ) = Consequently, we can get the following result. This proves the Proposition. Remark 4.12. The formula for the pre-Lie Magnus expansion in (4.32) can be considered as a generalization of the formula (4.18). In other words, it is a decorated version of (4.18), taking into account the relation between the maps F and Ψ described in Lemma 4.5.

The pre-Lie homomorphism Φ : PL(E), → -→ L(E), ⊲ , described in (3.7) and (3.8), respects the degree, it is then continuous for the topologies defined by the corresponding decreasing filtrations 7 . We denote by the same letter Φ the pre-Lie homomorphism from the completed pre-Lie algebra PL(E) onto L(E): As a particular case, let us take E = i∈N E i , with #E i = 1, for all i ∈ N, i.e. E = {a i : i ∈ N}, such that |a i | = i, and the generators are ordered by:

PL(E) i / / Φ PL(E) Φ L(E) i / / L(E)
a 1 < a 2 < • • • < a s < • • • .
For any σ ∈ T E, e1 pl , Φ Ψ(σ) is an element in L(E). But, from Theorem 3.20 and its Corollary 3.21, we have that the set B = Φ(t) : t ∈ O(I) forms a monomial basis for the pre-Lie algebra L(E), ⊲ (respectively for the free Lie algebra L(E), [•, •] ), where the pre-Lie product "⊲" is defined in (3.2), hence:

Φ Ψ(σ) = α 1 Φ(t 1 ) + α 2 Φ(t 2 ) + • • • + α k Φ(t k ),
is a linear combination of basis elements Φ(t i ), t i ∈O(I), multiplied by coefficients α i ∈ K, for all i = 1, . . . , k, where I is the (two-sided) ideal defined by (3.9). Thus, the pre-Lie Magnus expansion in (4.33) can be expressed using the monomial basis elements Φ(t), for t ∈ O(I).

Here, we calculate the few first reduced pre-Lie Magnus elements Ωn (x) in L(E), up to n = 5: Here, we link between our work in Chapter 3, on the pre-Lie construction of the Lie algebras, and the work of S. Blanes, F. Casas and J. Ros [START_REF] Blanes | Improved High Order Integrators based on the Magnus Expansion[END_REF], on the writing of Magnus expansion. Firstly, we shall consider the generators {q i : i ≥ 1}, of the Lie algebra L(E) in their work, as matrix-valued functions in h. Define a pre-Lie product on the set of formal power series hR [[h]] by:

Ω1 (x) = λ 1 a 1 . Ω2 (x) = λ 2 a 2 . Ω3 (x) = λ 3 a 3 -B 2
( f ⊲ g)(h) := [ h 0 f (s)
s ds, g(h)], for any f, g ∈ hR [[h]]. (4.34) This pre-Lie product described in (4.34) can be visualized as in the following diagram:

hR[[h]] ⊗ hR[[h]]

⊲ / / where f ⊲g(h) = [ h 0 f (s)ds, g(h)]. Hence, for q i (h) = a i-1 h i , q j (h) = a j-1 h j any two generators of L(E), we can apply the pre-Lie product defined above in (4.34) as follows:

1 h ⊗ 1 h hR[[h]] O O h R[[h]] ⊗ R[[h]] ⊲ / / R[[h]]
(q i ⊲ q j )(h) = [ h 0 q i (s) s ds, q j (h)]

= [a i-1 h 0 s i-1 ds, q j (h)]

= [ 1 i a i-1 h i , q j (h)]

= 1 i [q i , q j ](h),
where |q i | = i, for i ≥ 1. Simply, we shall write q i ⊲ q j = 1 |q i | [q i , q j ], for all i, j ≥ 1. In following, we rewrite the calculations of the three authors for the components Ω k up to k = 6, using the pre-Lie product defined above: Ω = q 1 + 1 12 q 3 + 1 80 q 5 + 1 448 q 7 . Ω = -1 12 (q 1 ⊲ q 2 ) + -1 80 (q 1 ⊲ q 4 ) + 1 120 (q 2 ⊲ q 3 ) + -1 448 (q 1 ⊲ q 6 ) + 1 1120 (q 2 ⊲ q 5 ) -1 448 (q 3 ⊲ q 4 ) . Ω = 1 360 (q 1 ⊲ (q 1 ⊲ q 3 )) -1 120 (q 2 ⊲ (q 1 ⊲ q 2 )) + 1 1680 (q 1 ⊲ (q 1 ⊲ q 5 )) -1 1120 (q 1 ⊲ (q 2 ⊲ q 4 ))+ 1 1680 (q 2 ⊲ (q 2 ⊲ q 3 )) + 1 2016 (q 3 ⊲ (q 1 ⊲ q 3 )) -1 210 (q 4 ⊲ (q 1 ⊲ q 2 )) .

Ω = 1 720 (q 1 ⊲ (q 1 ⊲ (q 1 ⊲ q 2 ))) + 1 6720 (q 1 ⊲ (q 1 ⊲ (q 1 ⊲ q 4 ))) -1 3780 (q 1 ⊲ (q 1 ⊲ (q 2 ⊲ q 3 ))) + 1 1344 (q 1 ⊲ (q 3 ⊲ (q 1 ⊲ q 2 ))) + 11 30240 (q 2 ⊲ (q 1 ⊲ (q 1 ⊲ q 3 ))) -1 1680 (q 2 ⊲ (q 2 ⊲ (q 1 ⊲ q 2 ))) .

Ω 5 = -1 15120 (q 1 ⊲ (q 1 ⊲ (q 1 ⊲ (q 1 , q 3 )))) -1 15120 (q 1 ⊲ (q 1 ⊲ (q 2 ⊲ (q 1 ⊲ q 2 )))) + 1 3780 (q 2 ⊲ (q 1 ⊲ (q 1 ⊲ (q 1 ⊲ q 2 )))) .

Ω 6 =
-1 30240 (q 1 ⊲ (q 1 ⊲ (q 1 ⊲ (q 1 ⊲ (q 1 ⊲ q 2 ))))).

M 6 =                                                                                                                    
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 3 1 0 0 1 3 0 0 0 0 1 3 1 0 0 3 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 3 0 0 0 0 0 0 1 0 0 3 0 0 0 0 0 1 1 2 4 1 1 0 0 0 0 0 1 1 4 0 0 0 0 0 0 1 0 4 0 1 0 0 0 0 0 0 1 4 0 0 0 0 0 0 0 1 6 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 2 1 1 10 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 10 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 2 2 5 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 2 5 0 0 0 0 0 0 0 0 0 0 0 0 0 1 3 0 0 0 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

                                                                                                                   
.

Figure 1 . 1 .

 11 Figure 1.1. The universal property of the algebra U(L).

. 12 )

 12 where f = x∈T (I) α x x + corrective term in Span K (O(I)), and α x ∈ K for all x ∈ T (I). The map ϕ is obviously injective. Indeed, for any f ∈ I and ϕ( f ) = 0, then f ∈ Span K (O(I)), and from Theorem 3.8, Span K (O(I)) I = {0}. Also, according to Theorem 3.8 and by the definition of ϕ in (1.

  , and k≥1 PL (k) = {0}. Define the valuation map Val : PL → N by:

Figure 2 . 1 .

 21 Figure 2.1. The description of Ψ and Ψ S .

Example 2 . 2 .

 22 (Undecorated case) We display here the matrices M 3 , in the basis { , }, and M 4 , in the basis { , , , , }, of the restrictions of Ψ to the homogeneous components T 3 pl and T 4 pl respectively:

  Figure 2.2.A planar rooted tree with its vertices labeled according to total order "≪".

  verifying the growing conditions of Theorem 2.4 (respectively Theorem 2.3), and suppose π(σ) = s. Denote by b(s, τ) (respectively b(σ, τ)) the cardinal number of B(s, τ) (respectively B(σ, τ)). Now, define : b(s, τ) := σ∈T E pl , π(σ)=s b(σ, τ). (2.14) Then, according to (2.13), we have: b(s, τ) = b(s, τ)/sym(s).

. 15 )

 15 The coefficients c(•, •) and b(•, •) coincide by Theorem 2.3. So, from (2.12) and (2.15), the coefficients α(•, •) and b(•, •) satisfy the same recursive relations, which proves the Theorem.

  , , } and T 4 pl = { , , , , }, then we can define S as: S ( ) = , S ( ) = , S ( ) = , and one can choose for S ( ) between and .

  Lie algebra [PL(E)] by the linear transformations (x → L x , for x ∈ PL(E)) of PL(E) is uniquely extended to a representation by the linear transformations (u → L u , for u ∈ U[E]) of the enveloping algebra U[E] of the Lie algebra [PL(E)], which makes the following diagram commute:

e 2 =

 2 + , e 3 = + , e 4 = + + 3 + , e 5 = + , e 6 = + + + , e 7 = + + , e 8 = + + 2 + + , e 9 = + + 3 + + 4 + 4 + 3 + 6 + ≻.

  by the definition of "◮" in (3.3)), = |y| |x| + |y| α([x, y]) = |y| |x| + |y| (|x| + |y|)[x, y], (by the definition of α above), = |y|[x, y] = |x||y| |x| [x, y] = (|x||y|)x ⊲ y, (by the definition of "⊲" in (3.2)),= |x|x ⊲ |y|y = α(x) ⊲ α(y).Denote by [•,•] ⊲ the underlying Lie bracket induced by the pre-Lie product "⊲", which defined by:[x, y] ⊲ = x ⊲ yy ⊲ x, for x, y ∈ L. (3.4) Then the two Lie structures defined on L by the Lie brackets [•, •], [•, •] ⊲ respectively, are also isomorphic via α. Indeed, by substituting the pre-Lie product "⊲", described in (3.2), by the Lie bracket [•, •] in the definition of the Lie bracket [•, •] ⊲ in (3.4), we get: [x, y] ⊲ = 1 |x| [x, y] -1 |y| [y, x] = |x| + |y| |x| |y| [x, y], for any x, y ∈ L, (3.5) but, α [x, y] = |[x, y]| [x, y] = |x| + |y| [x, y] = |x||y|[x, y] ⊲ (by (3.5)) = [|x|x, |y|y] ⊲ = [α(x), α(y)] ⊲ (by (3.1)).

  with x := (a • b) • c, and y := d • e. Then:

  and they are equal when the degrees of σ and σ ′ are equal. If b

Figure 3

 3 Figure 3.3.

Theorem 3 . 20 .

 320 Span K (O(I)) ( by Theorem 3.8 ) = Φ Span K (O(I)), since Ker Φ = I and Φ I = 0 .Hence, Φ : Span K (O(I)) -→ L(E) is a surjective and an injective map. Then it is an isomorphism of vector spaces. For any t ∈ O(I), we have:Ψ S min (t) = Can Ψ S min (t), I = t. (3.43)Moreover, the set B := {Φ(t) : t ∈ O(I)} is a monomial basis for the pre-Lie algebra L(E), ⊲ .

  and then,[[x, y], x], y = [[x, y], y], x .CHAPTER 4

Theorem 4 . 2 .

 42 The Magnus element Ω(a) in PL(a) can be written: Ω(a) = log * exp(a) , (4.14)

  [START_REF] Chapoton | Pre-Lie algebras and the rooted trees operad[END_REF]) can be rewritten:Ω( ) = log * (e ) = n>0 (-1) n-1 n (e -1) * n-1 → ,(4.24)

Figure 4 . 1 .Lemma 4 . 9 .

 4149 Figure 4.1.

δ 1 :Lemma 4 . 10 . 30 )

 141030 V(τ 1 )→E δ 2 :V(τ 2 )→E v∈V(τ 1 ) λ δ 1 (v) v ′ ∈V(τ 2 ) λ δ 2 (v ′ ) Ψ(τ 1, δ 1 ) → Ψ(τ 2, δ 2 ) = δ:V(τ)→E v∈V(τ) λ δ(v) Ψ(τ δ ), (by setting τ δ = τ 1, δ 1 • ցτ 2, δ 2 ). The pre-Lie Magnus element Ω(a) in PL(E) can be rewritten as:Ω(a) = τ∈T e1 pl γ(τ) G a Ψ(τ) ,(4.29)where a = e∈E λ e e ∈ PL(E).Proof. From Theorem 4.4 and lemma 4.5, we have that:We have that Ω( ) is an element in PL( ), and the map G a can be extended linearly from PL( ) into PL(E), such that:Ω(a) := G a Ω( ) = τ∈T e1 pl γ(τ) G a Ψ(τ) .This proves the Lemma.In Lemma 4.9 above, let us denote λ(τ δ ) := v∈V(τ) λ δ(v) . Hence, we can simplify the formula (4.27) as: G a Ψ(τ) = δ:V(τ)→E λ(τ δ ) Ψ(τ δ ). (4.31)

Proposition 4 . 11 .

 411 The pre-Lie Magnus expansion can be rewritten:Ω(a) = σ ∈T E, e1 pl γ(σ) λ(σ) Ψ(σ),(4.32)for any σ ∈ T E, e1 pl . Here γ : T E pl → K defined as in (4.16), forgetting the decoration.Proof. From Lemma 4.10, and by substituting G a Ψ(τ) obtained in (4.31), we get:Ω(a) = τ ∈T e1 pl δ:V(τ)→E γ(τ) λ(τ δ ) Ψ(τ δ ) = σ ∈T E, e1pl γ(σ) λ(σ) Ψ(σ).

Figure 4 . 2 .

 42 Figure 4.2.

Corollary 4 . 13 .

 413 The pre-Lie Magnus expansion in L(E) can be rewritten as:Ω(x) = σ ∈T E, e1 pl γ(σ) λ(σ) Φ Ψ(σ) , (4.33) where x = Φ(a) = e∈E λ e e ∈ L(E), for e = Φ( e ) ∈ E.

Figure 4 . 3 .

 43 Figure 4.3. The description of ⊲.

  Magnus classique, utilisant la structure pré-Lie de L(E). all planar E-decorated rooted trees. 11, 24, 27, 29, 31, 39, 48, 49, 51, 52, 54, 77.

	xvi		NOTATIONS
	B +	the usual operator which grafts a monomial	68, 70.
		σ 1 , • • • , σ k of (undecorated) rooted trees on a
		common root.
	"NAP"	Non-Associative Permutive.		11, 54.
	L U(L)	K-Lie algebra.	Notations	13, 14, 15, 42, 43, 74.
	Symbol Description			Pages
	K	field with characteristic zero.		9, 13, 14, 15, 17, 18, 19, 33, 48, 49, 51, 58,
					65, 68, 78.
	M(E)	free magma generated by a set E.	9, 10, 11, 15, 17, 45, 46.
	M E	the linear span of M(E).		9, 15, 17, 22, 45, 46.
	A	an associative K-algebra.		13.
	T bin pl	the set of all planar binary trees.		10, 11.
	T bin pl	the linear span of T bin pl .			10.
	T bin, E pl	the set of all planar binary trees with leaves	10, 11.
		decorated by elements of a set E.
	T bin, E pl	the linear span of T bin, E pl	.		10.
	∨	magmatic product in T bin pl , T bin, E pl	respectively. 10, 47.
	T pl	the set of all planar rooted trees.		10, 11.
	T pl	the linear span of T pl .			37, 68, 77.
	T E pl the set of T E pl the linear span of T E pl .			11, 23, 24, 26, 28, 31, 32, 38, 39, 49, 51, 54,
					56, 77, 78.
	• ց	the left Butcher product.		11, 13, 23, 24, 25, 26, 27, 28, 29, 30, 37, 38,
					39, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 62,
					70, 71, 78.
	ց	the left grafting.			23, 24, 25, 26, 27, 38, 39, 56, 57.
	T	the set of all (non-planar) rooted trees.	71.
	T	the linear span of T .			19, 36, 37, 38, 70, 71, 73, 77.
	T E	the set of all (non-planar) E-decorated rooted	11, 28, 32, 43, 54, 55, 56, 58, 60.
		trees.
	T E	the linear span of T E .			5, 6, 11, 18, 21, 23, 28, 31, 32, 38, 39, 43, 45,
					46, 54, 56, 58, 77.
		the usual Butcher product.		6, 11, 23, 37, 38, 39, 54, 55, 56, 57.
	B +, a	the operator which grafts a monomial	11, 39, 48, 51, 54.
		σ 1 , • • • , σ k of rooted trees on a common root
		decorated by an element a.
				ix xv

  Id T E . 6, 23, 31, 32, 38, 39, 54. Ψ S the linear map " Ψ • S " from T E into T E . 23, 28, 31, 32, 38, 39, 56, 57, 58, 83. β

	V(σ)	the set of all vertices of a rooted tree σ.	10, 19, 24, 26, 27, 28, 29, 30, 31, 43, 51, 55,
					56, 57, 68, 77, 78, 79.
	|σ|		degree of a rooted tree σ.		6, 41, 43, 44, 48, 49, 52, 53, 54, 68.
	b(σ)	the number of branches of a rooted tree σ.	48, 54.
	Ψ		magmatic algebra isomorphism between	23, 24, 25, 26, 27, 28, 29, 31, 38, 40, 56, 57.
			T E pl , • ց and T E pl , ց .
	c(σ, τ)	the coefficient of a planar rooted tree σ in	23, 25, 26, 27, 28, 29, 30.
			Ψ(τ).
	sym(s)	the symmetry factor of a (non-planar) rooted	28, 29, 30, 31.
			tree s.
	Ψ		the linear map " π • Ψ " from T E pl onto T E .	6, 7, 15, 16, 39, 42, 44, 46, 47, 58, 59, 64, 76, 29, 30, 31, 32, 39, 57, 62, 70, 71, 77, 78, 79,
					77, 79, 80, 81. 80.
	L(E) α(s, τ)	completed free Lie algebra. the coefficient of a (non-planar) rooted tree s	79, 80. 29, 30, 32, 71.
	T ( f )	the maximal term of an element f with respect in Ψ(τ).	17, 48, 49, 50, 51, 52, 53, 57, 61.
			to a monomial order "<".
	T (I)	the set of all maximal terms T ( f ) of element	17, 39, 49, 50, 51, 52, 53, 54, 61.
			of an ideal I.
	G		Lie group.		12, 18, 74.
	PL		K-pre-Lie algebra.		18, 19, 20, 21, 22, 65, 70. 54, 55, 56, 57.
	PL		completed pre-Lie algebra.		19, 20, 67, 77, 78, 79.
	→		the pre-Lie grafting for (non-planar) rooted	5, 6, 18, 19, 23, 28, 29, 37, 38, 39, 43, 45, 56,
	R		trees. the transitive closure of a relation R.	57, 58, 70, 71, 73, 77, 78, 79. 55, 56, 57.
	PL(E) [t] R	the free K-pre-Lie algebra generated by a set the set of all trees s in T E that t is related with	22, 23, 33, 34, 46, 67, 77, 79. 56, 57.
			E. s by R .
	Ker f Ω(t)	kernel of a mapping f . Magnus expansion.		22, 44, 47, 58. 64, 65, 66, 67, 68, 69, 71, 73, 78, 79.
	m i=1,...,n ( exp(t) a i , ց) monomial of generators the exponential function of t. a 1 , • • • ,	a n multiplied	23, 38. 64, 65, 67, 73.
	B n		each with other by ց. Bernoulli numbers.		64, 65, 66, 68, 71, 72, 73, 74, 80.
	m i=1,...,n ( λA[[λ]] formal power series with coefficients in an al-a i , • ց) the lower-energy term of m ( a i , ց). i=1,...,n m ( a i , →) monomial of generators a 1 , • • • , a n multiplied gebra A, without constant term. i=1,...,n each with other by →. log * the logarithm computed with respect to a	23. 38. 65, 80, 81. 23, 38. 67, 73.
	m i=1,...,n (	a i , ) the lower-energy term of m i=1,...,n ( product * .	a i , →).	23, 38.
	π		the natural "forget planarity" projection be-	23, 29, 30, 31, 38, 39, 54, 56.
			tween T E pl and T E .
	p(σ)	potential energy of a rooted tree σ.	24, 25, 26.

O(I)

the complement set of T (I) in a magma M(E), i.e. O(I) = M(E)\T (I). 17, 39, 49, 51, 52, 55, 58, 59, 61, 79, 80. Span K (E) the linear span of a set E over a field K. 17, 18, 49, 51, 58. S section of π which maps T E into T E pl , such that π • S = S (s, t) the coefficient of a (non-planar) rooted tree s in Ψ S (t). 6, 23, 32, 39, 56, 57. #E the cardinal of a set E. 41, 47, 48, 51, 56, 79. Can( f, I) the canonical form of f in Span K O(I) . 49, 50, 51, 58. S min

section of π which chooses for any tree t in T E the minimal element τ in T E pl , with respect to an order "<", such that π(τ) = t.

1.3.1. Enveloping algebra of Lie algebras.

	• , •], we have: 0 = [x + y, x + y] = [x, x] + [x, y] +
	[y, x] + [y, y] = [x, y] + [y, x]. Relations (1.4) and (1.6) are equivalent because the characteristic
	of the base field K is different from 2. Every associative K-algebra A has a natural structure of
	Lie algebra with a Lie bracket defined by:
	[x, y] = xy -yx.	(1.7)

  a, (x e ′ 3 • x e 1 1 ) ⊗ a ′ , (x ′′′′ : e = 1, . . . , d 4 , e ′ = 1, . . . , d 3 , e ′ 2 , e ′′ 2 , e ′′′ 2 = 1, . . . , d 2 , e i = 1, . . . , d 1 , ∀i = 1, . . . , 7, e ′ 2 ≥ e ′′ 2 , e 2 ≥ e 3 , e 4 ≥ e 5 ≥ e 6 ≥ e 7 , a, a ′ , a ′′ , a ′′′ , a ′′′′ ∈ E ≻,

	e ′ 2 2 • x e ′′ 2 2 ) ⊗ a ′′ , (x e ′′′ 2 2 • x e 2 1 • x e 3 1 ) ⊗ a ′′′ , (x e 4 1 • x e 5 1 • x e 6 1 • x e 7 1 ) ⊗ a

  .8) with x i = Φ(t i ), and |t i | = |x i |, ∀i = 1, . . . , k. Let I be the two-sided ideal of T E generated by all elements on the form: |s| s → t + |t| t → s , for s, t ∈ T E . The quotient L ′ (E) := T E /I has structures of pre-Lie algebra and Lie algebra, respectively.

	(3.9)
	The ideal I satisfies the following properties:
	Proposition 3.2.

Proof. Using the pre-Lie grafting "→" defined on T E , we can define the following operations on L ′ (E):

s ⊲ * t := s → t := s → t, (3.10) [s, t] := [s, t] := |s|s → t, (

3.11)

for any s, t ∈ T E , where the bar stands for the class modulo I. The product in (3.10) is pre-Lie by definition. The bracket defined in (3.11) is well-defined and satisfies the following identities:

  , we can define a non-planar version of this order, as follows:|s| = |t|, b(s) = b(t) = k and s = B +,r (s 1 . . . s k ), t = B +,r ′ (t 1 . . . t k ) such that ∃ j ≤ k, with s i = t i , for i < j, s j t j where s 1 • • • s k , t 1• • • t k are the branches of s, t respectively, or:

	for any s, t ∈ T E , then s t if and only if	(3.34)
	(i) |s| < |t|, or :
	(ii) |s| = |t| and b(s) < b(t), or:
	(iii)

  .[START_REF] Knuth | The art of computer programming I. Fundamental algorithms[END_REF] Condition (iii) of the definition, in(3.34), of the order exactly means that the l-tuple of branches of S min (s) is lexicographically smaller than the l-tuple of branches of S min (t). If s and t have the same branches and s t, we also have S min (s) S min (t), as one can see by comparing the roots. This proves Proposition 3.13. The section map S min on T E is a bijection onto O(J), where J is the (twosided) ideal generated by the pre-Lie identity in T E pl , • ց .Proof. Clear from Proposition 3.9.Define a relation R on T E as follows:sRs ′ if and only if there are t, t ′ ∈ T E and v, w ∈ V(t ′ ) such that s = t → v t ′ , s ′ = t → w t ′ (3.36) for s, s ′ ∈ T E , and w is related with v by an edge Let R be the transitive closure of the relation R defined in (3.36), i.e. for s, s ′ ∈ T E , we say that s R s ′ if and only if there is s 1 , . . . , s l ∈ T E such that sRs 1 R . . . Rs l Rs ′ .

	w with w above v. Lemma 3.15. Let s, s ′ Proposition 3.14. v

  .38) One can verify that s tRs t ′ by following the same steps as above. So, from (3.37) and(3.38), we obtain that s t R s ′ t ′ .For any t ∈ T E , define a class of t with respect to R by:

				[t]	R	:= {s ∈ T E : t R s}.	(3.39)
	This class has the following properties:
	(i) t is maximal among the representative elements in the class [t] then s t. This property is deduced from Lemma 3.15.	R	, i.e. for any s ∈ [t]	R
	(ii) For any s ∈ [t]	R	, then [s]	R	⊂ [t]	R	.
	Lemma 3.18. For any t ∈ T E , then:

  Corollary 3.21. The set B := {Φ(t) : t ∈ O(I)} is a monomial basis for the free Lie algebra L(E), [•, •] . As a particular case, take E = {a i : i ∈ N}, such that |a i | = i, for all i ∈ N, with an ordering "<" on the generators a 1 < a 2 < • • • < a s < • • • . From our preceding work in Chapter 2, we have:

	Examples 3.22. Here,we calculate few first bases B n for homogeneous components L n of the
	free Lie algebra L(E) up to n = 4, using Corollary 3.21, as follows:
	(i)

  1 λ 1 λ 2 a 1 ⊲ a 2 . Ω4 (x) = λ 4 a 4 + B 1 2 3 λ 1 λ 3 a 1 ⊲ a 3 + B 2 ⊲ a 2 ) ⊲ a 1 . Ω5 (x) = λ 5 a 5 + B 1 3 4 λ 1 λ 4 a 1 ⊲ a 4 + 1 3 λ 2 λ 3 a 2 ⊲ a 3 + B 1 5 9 λ 2 1 λ 3 (a 1 ⊲ a 3 ) ⊲ a 1 + B 2 Ω3 (x) = λ 3 a 3 -B 2 1 λ 1 λ 2 [a 1 , a 2 ]. Ω4 (x) = λ 4 a 4 + B 1 2 3 λ 1 λ 3 [a 1 , a 3 ] + B 2

				1 1 λ 1 1 2 λ 2 1 λ 2 (a 1 1 11 12 λ 3 1 6 λ 2 1 λ 2 [[a 1 , a 2 ], a 1 ].
	Ω5 (x) = λ 5 a 5 + B 1	3 4	λ 1 λ 4 [a 1 , a 4 ] +	1 6	λ 2 λ 3 [a 2 , a 3 ] + B 1	5 36	λ 2 1 λ 3 [[a 1 , a 3 ], a 1 ] + B 2 1	11 144	λ 3 1 λ

2 (a 1 ⊲ a 2 ) ⊲ a 1 ⊲ a 1 ,

and using a i ⊲ a j = 1 |a i | [a i , a j ],

for all i, j, we get:

Ω1 (x) = λ 1 a 1 . Ω2 (x) = λ 2 a 2 . 2 [[a 1 , a 2 ], a 1 ], a 1 .

PRELIMINARIES

1.3. LIE ALGEBRAS

For more details about the solvable algebras see [3, Appendix: Non-Commutative Gröbner Bases, pages 526-528].

MONOMIAL BASES FOR FREE PRE-LIE ALGEBRAS

For more details about this construction of pre-Lie algebra see[START_REF] Schedler | Connes-Kreimer quantizations and PBW theorems for pre-Lie algebras[END_REF] Proposition 3.3.3] and[START_REF] Foissy | Algèbres pré-Lie et algèbres de Lie tordues[END_REF].

MONOMIAL BASES AND PRE-LIE STRUCTURES FOR FREE LIE ALGEBRAS

For further details about the completed pre-Lie algebra see Paragraph 1.4.1.

Grossman-Larson algebra is defined in the next section, Paragraph

4.3.1.

For more details about Butcher series see [8, section 4.1].

A real-valued function f is said to be a Lipschitz function if and only if it satisfies:| f (x)f (y)| ≤ c|x -y|,for all x and y , where c is a constant independent of x and y.

For more details about this property see[START_REF] Blanes | Improved High Order Integrators based on the Magnus Expansion[END_REF].

PRE-LIE MAGNUS EXPANSION

These topologies are induced by metrics defined on pre-Lie algebra using compatible decreasing filtrations described in Paragraph 1.4.1.

Acknowledgments

I would to extend my sincere thanks and appreciation to my supervisors Mr. Dominique Manchon and Mr. Frédéric Patras for their proposition to this subject and supervision during these three years. They were very helpful and devoted much time to guide me in my work. They have always supported and encouraged me. All my thanks and my respect to them for everything they gave to enrich this work.

I would like to thank Mr. Jean-Christophe Novelli, Professor in the university of Paris-Est Marne-la-Vallée, and Mr. Loïc Foissy, Professor in the University Center of la Mi-Voix, for agreeing to be the reporters of my thesis. My thanks to Mr. Jean-Yves Thibon, Professor in the university of Paris-Est Marne-la-Vallée, and Mr. Michael Heusener, Professor in the university Blaise Pascal, to have agreed to be part of this jury and to examine this work. Thank you to all the jury members for the interest that they have shown to my work and for all their comments and suggestions.

Example 3.2. In this example we calculate Can( f, J ′ ), where f = and J ′ is the ideal defined by (3.22), using the algorithm described in the proof of Theorem 3.8 above:

, φ 0 = 0, h 0 = 0

∈ T (J ′ ), choose g 0 = 3 ∈ J ′ , lc(g 0 ) = 1

, h 1 = 0,

• ց a 1 ∈ J ′ , lc(g 1 ) = 1

∈ T (J ′ ), then:

,

) ∈ J ′ φ 4 = 3 ,

/

∈ T (J ′ ), then:

/

∈ T (J ′ ), then:

(ii) Let us take E = {x, y} ordered by x < y, such that |x| = |y| = 1. Denote " " by the vertex decorated by x, and " " the vertex decorated by y, such that < . Using the order defined in (3.34), we arrange the first terms of T E as follows:

Also, we calculate here the monomial bases for the homogeneous components T E n up to n = 4: .

Hence, we have: the tree is not in O(I), since there is an element f = that belongs to I such that T ( f ) = ∈ T (I). Indeed, from the pre-Lie identity, and the so-called weighted anti-symmetry which they proposed a numerical strategy to reproduce the classical Magnus expansion terms. The free Lie algebra L(E) with one single generator in each degree naturally appears in this context. We introduce, in this section, a combinatorial pre-Lie version of the work of S. Blanes, F. Casas, and J. Ros, using the pre-Lie structure on L(E) and the monomial basis described in chapter 3 of this thesis.

Classical Magnus expansion

W. Magnus provides an exponential representation of the solution of the well-known classical initial value problem:

where Y(t), A(t) are linear operators depending on a real variable t, and "1" is the identity operator. Magnus considers the problem (4.1) in a non-commutative context. The problem, according to Magnus' point of view, is to define an operator Ω(t), depending on A, with Ω(0) = 0 such that :

He obtains a differential equation leading to the recursively defined expansion named after him:

where B n are the Bernoulli numbers defined by:

and ad Ω is a shorthand for an iterated commutator:

and, in general, ad m+1

. Taking into account the numerical values of the first few Bernoulli numbers, the formula in (4.3) can be written:

where Ω(t) := Ω ′ (t) = d dt Ω(t). Also, we can write the expansion in (4.3) as:

, (by the Jacobi identity),

This proves the Lemma.

Also, the formula (4.6) can be represented as:

where Ω1 (λA) = λA, and in general:

Here, we give few first terms of the pre-Lie Magnus expansion described above:

There are many ways of writing the Magnus expansion, for pre-Lie and classical formulas, in various settings using Baker-Campbell-Hausdorff series, dendriform algebras, Rota-Baxter algebras, Solomon Idempotents and others, for more details about these works see [START_REF] Agrachev | Chronological algebras and nonstationary vector fields[END_REF], [START_REF] Ebrahimi-Fard | A Magnus-and Fer-type Formula in Dendriform Algebras[END_REF], [START_REF] Chapoton | Enveloping algebras of pre-Lie algebras, Solomon Idempotents and the Magnus Formula[END_REF] and the references therein.

Using the pre-Lie identity, the pre-Lie Magnus expansion terms can be reduced: for the terms at third order, Ω3 (λA), no further reduction of terms is possible. At fourth order, two

For n ≥ 1, the numbers of trees in T e1, n pl , the subset of all planar rooted trees with "1 or even fertility " of degree n, is given by the sequence "A049130" in [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF]. Here, we give few of first terms of this sequence: 1, 1, 2, 4, 10, 26, 73, 211, 630, . . .. We give here some examples of the formula of pre-Lie Magnus expansion described in (4.18), as follows:

. At order four, we have:

but, thanks to pre-Lie identity, we have:

x , then the formula Ω4 (x) can be reduced into two terms, as follows:

Eight trees from ten appear in the pre-Lie Magnus expansion at order five, due to the recursive nature of this expansion, which are: ,,,,,,, .

Using the pre-Lie identity as:

we obtain a reduced formula of pre-Lie Magnus expansion at order five, with seven terms described as:

The reduced formulas at orders four and five, described in (4.19), (4.20) respectively, are considered as best (or optimal) formulas for the pre-Lie Magnus expansion at these orders.

Some calculations in pre-Lie Magnus expansion.

Let us consider the free pre-Lie algebra PL = T with one generator " ", together with the pre-Lie grafting "→". Then, we can represent pre-Lie Magnus expansion in terms of rooted trees as in the following. We need first to introduce the following result. Lemma 4.5. For any planar rooted tree τ, we have:

where F is the function described in (4.17), and

Proof. Let τ be any planar rooted tree with k branches, then it can be written in a unique way as τ = B + (τ 1 . . . τ k ). Using the induction hypothesis on the number k of branches, we have:

Suppose that the hypothesis of this Lemma is true for all planar rooted trees τ ′ with n -1 branches, for all n ≤ k, i.e. F[τ ′ ]( ) = Ψ(τ ′ ), hence:

, (from definition of F in (4.17)),

This proves the Lemma.

In fact, we study here the undecorated case, with respect to the forests and trees, of the joint works of F. Patras with F. Chapoton, and with K. Ebrahimi-Fard respectively. The decorated version has been studied in [START_REF] Chapoton | Enveloping algebras of pre-Lie algebras, Solomon Idempotents and the Magnus Formula[END_REF], [START_REF] Ebrahimi-Fard | The pre-Lie structure of the time-ordered exponential[END_REF].

Here, we calculate the few first pre-Lie Magnus elements Ωn ( ), up to n = 5, according to the formula (4.24) above:

Remark 4.8. We observe that the formula (4.24) reduces the number of terms in the pre-Lie Magnus expansion the same way as the reduction induced by the pre-Lie identity in formula (4.21). In other words, formula (4.24) can be considered as a best formula for the reduced pre-Lie Magnus expansion. It would be interesting to have an explanation of this striking fact.

A combinatorial approach for Magnus expansion using a monomial basis for free Lie algebra

A. Iserles and S. P. No / rsett, in their joint work [START_REF] Iserles | No / rsett, On the solution of linear differential equations in Lie groups[END_REF], studied the differential equation:

where G is a Lie group, a ∈ Lip[R + → L], the set of all Lipschitz functions 5

where h is the time step size. They observed that this numerical method requires the evaluation of a large number of these commutators, which can be accomplished in tractable manner by exploiting the structure of the Lie algebra.

Different strategies have been developed to reduce the total number of commutators, e.g. the use of so-called time symmetry property 6 and the concept of a graded free Lie algebra [START_REF] Munthe-Kaas | Computations in a free Lie algebra[END_REF]. In their joint work [START_REF] Blanes | Improved High Order Integrators based on the Magnus Expansion[END_REF], the three authors S. Blanes, F. Casas, and J. Ros proposed to apply directly the recurrence of Magnus expansion, described in (4.3), in numerical version to a Taylor series expansion of the matrix A(t). They reproduced the Magnus expansion terms with a linear combination of nested commutators involving A.

These authors pursued this strategy with a careful analysis of the different terms of the Magnus expansion by considering its behaviour with respect to the time-symmetry. In the following, we review the part of their work corresponding to their strategy of rewriting Magnus expansion terms, as follows: by taking advantage of the time-symmetry property, they considered a Taylor expansion of A(t) around t 1 2 = t 0 + h 2 as:

and computed the corresponding terms of the component Ω k (t 0 +h, t 0 ) in the Magnus expansion, where: by taking into account the linear relations between different nested commutators due to the Jacobi identity. We give here the calculation for the components Ω k , up to k = 6, obtained by their code [4, Section 3]:

APPENDIX A Here, we calculate the matrices M 5 , M 6 , described below, of the restriction of Ψ S to the homogeneous component T 5 and T 6 respectively, in the case of undecorated rooted trees corresponding to our work in this thesis in Chapter 2, Subsection 2.2.2:

(i) The matrix M 5 , in the tree basis , , ,

1 1 1 1 1 1 1 1 1 0 1 0 1 0 0 1 0 1 0 0 1 3 1 0 0 1 3 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 3 0 0 0 0 0 1 1 2 4 0 0 0 0 0 0 1 0 4 0 0 0 0 0 0 0 1 6 0 0 0 0 0 0 0 0 1

(ii) The matrix M 6 , in the tree basis

: 83