\begin{document}

\title{Free brace algebras are free pre-Lie algebras}

ABSTRACT. Let $\mathfrak{g}$ be a free brace algebra. This structure implies that $\mathfrak{g}$ is also a pre-Lie algebra and a Lie algebra.
It is already known that $\mathfrak{g}$ is a free Lie algebra. We prove here that $\mathfrak{g}$ is also a free pre-Lie algebra,
using a description of $\mathfrak{g}$ with the help of planar rooted trees, a permutative product, and manipulations on the Poincaré-Hilbert series of $\mathfrak{g}$.\\

KEYWORDS. Pre-Lie algebras, brace algebras.\\

AMS CLASSIFICATION. 17A30, 05C05, 16W30.\\

\tableofcontents

\section*{Introduction}

Let ${\cal D}$ be a set. The Connes-Kreimer Hopf algebra of rooted trees ${\cal H}_R^{\cal D}$ is introduced in \cite{Connes3}
in the context of Quantum Field Theory and Renormalization. It is a graded, connected, commutative, non-cocommutative Hopf algebra. 
If the characteristic of the base field is zero, the Cartier-Quillen-Milnor-Moore theorem insures that its dual $({\cal H}_R^{\cal D})^*$ is the enveloping algebra 
of a Lie algebra, based on rooted trees (note that $({\cal H}_R^{\cal D})^*$ is isomorphic to the Grossman-Larson Hopf algebra \cite{Grossman3,Grossman2},
as proved in \cite{Hoffman,Panaite}). This Lie algebra admits an operadic interpretation: it is the free pre-Lie algebra ${\cal PL}({\cal D})$ generated by ${\cal D}$, 
as shown in \cite{Chapoton}; recall that a (left) pre-Lie algebra, also called a Vinberg algebra or a left-symmetric algebra, is a vector space
$V$ with a product $\circ$ satisfying:
$$(x \circ y)\circ z-x\circ (y\circ z)=(y\circ x)\circ z-y\circ (x \circ z).$$

A non-commutative version of these objects is introduced in \cite{Foissy3,Holtkamp}. Replacing rooted trees by planar rooted trees, 
a Hopf algebra ${\cal H}_{PR}^{\cal D}$ is constructed. This self-dual Hopf algebra is isomorphic to the Loday-Ronco free dendriform algebra based 
on planar binary trees \cite{Loday}, so  by the dendriform Milnor-Moore theorem \cite{Chapoton2,Ronco}, the space of its primitive elements, 
or equivalently the space of the primitive elements of its dual, admits a structure of brace algebra, described in terms of trees in \cite{Foissy6} 
by graftings of planar forests on planar trees, and is in fact the free brace algebra ${\cal B}r({\cal D})$ generated by ${\cal D}$. 
This structure implies also a structure of pre-Lie algebra on ${\cal B}r({\cal D})$.

As a summary, the brace structure of ${\cal B}r({\cal D})$ implies a pre-Lie structure on ${\cal B}r({\cal D})$, which implies a Lie structure on ${\cal B}r({\cal D})$.
It is already proved in several ways that ${\cal PL}({\cal D})$ and ${\cal B}r({\cal D})$ are free Lie algebras in characteristic zero \cite{Chapoton3,Foissy6}.
A remaining question was the structure of ${\cal B}r({\cal D})$ as a pre-Lie algebra. The aim of the present text is to prove that ${\cal B}r({\cal D})$ is a free pre-Lie algebra.
We use for this the notion of non-associative permutative algebra \cite{Livernet} and a manipulation of formal series.
More precisely, we introduce in the second section of this text a non-associative permutative product $\star$ on ${\cal B}r({\cal D})$ and we show
that $({\cal B}r({\cal D}),\star)$ is free. As a corollary, we prove that the abelianisation of ${\cal H}_{PR}^{\cal D}$ (which is not ${\cal H}_R^{\cal D}$), is isomorphic to 
a Hopf algebra ${\cal H}_R^{{\cal D}'}$ for a good choice of ${\cal D}'$. This implies that $({\cal H}_{PR}^{\cal D})_{ab}$ is a cofree coalgebra and we recover in a different way
the result of freeness of ${\cal B}r({\cal D})$ as a Lie algebra in characteristic zero.
Note that a similar result for algebras with two compatible associative products is proved with the same pattern in \cite{Dotsenko}.
\\

{\bf Notations.} We denote by $K$ a commutative field of characteristic zero. All objects (vector spaces, algebras\ldots) will be taken over $K$.

\section{A description of free pre-Lie and brace algebras}

\subsection{Rooted trees and planar rooted trees}

\begin{defi} \textnormal{ \begin{enumerate}
\item A {\it rooted tree} $t$ is a finite graph, without loops, with a special vertex called the {\it root} of $t$. 
The {\it weight} of $t$ is the number of its vertices.  The set of rooted trees will be denoted by ${\cal T}$.
\item A {\it planar rooted tree} $t$  is a rooted tree with an imbedding in the plane. 
the set of planar rooted trees will be denoted by ${\cal T}_P$.
\item Let ${\cal D}$ be a nonempty set. A rooted tree decorated by ${\cal D}$ is a rooted tree
with an application from the set of its vertices into ${\cal D}$. 
The set of rooted trees decorated by ${\cal D}$ will be denoted by ${\cal T}^{\cal D}$.
\item Let ${\cal D}$ be a nonempty set. A planar rooted tree decorated by ${\cal D}$ is a planar tree
with an application from the set of its vertices into ${\cal D}$. 
The set of planar rooted trees decorated by ${\cal D}$ will be denoted by ${\cal T}_P^{\cal D}$.
\end{enumerate}} \end{defi}

{\bf Examples.} \begin{enumerate}
\item Rooted trees with weight smaller than $5$:
$$\tun,\tdeux,\ttroisun,\ttroisdeux,\tquatreun, \tquatredeux,\tquatrequatre,\tquatrecinq,
\tcinqun, \tcinqdeux,\tcinqcinq,\tcinqsept,
\tcinqneuf,\tcinqdix,\tcinqonze,\tcinqtreize,\tcinqquatorze.$$
\item Rooted trees decorated by ${\cal D}$ with weight smaller than $4$:
$$\tdun{$a$},\: a\in {\cal D},{\cal H}space{1cm} \tddeux{$a$}{$b$},\: (a,b)\in {\cal D}^2,{\cal H}space{1cm}
\tdtroisun{$a$}{$c$}{$b$}=\tdtroisun{$a$}{$b$}{$c$},\: \tdtroisdeux{$a$}{$b$}{$c$},\:(a,b,c)\in {\cal D}^3,$$
$$ \tdquatreun{$a$}{$d$}{$c$}{$b$}=\tdquatreun{$a$}{$c$}{$d$}{$b$}
=\tdquatreun{$a$}{$d$}{$b$}{$c$}=\tdquatreun{$a$}{$b$}{$d$}{$c$}
=\tdquatreun{$a$}{$c$}{$b$}{$d$}=\tdquatreun{$a$}{$b$}{$c$}{$d$},\: \tdquatredeux{$a$}{$d$}{$b$}{$c$},\:
 \tdquatrequatre{$a$}{$b$}{$d$}{$c$}= \tdquatrequatre{$a$}{$b$}{$c$}{$d$},\:
\tdquatrecinq{$a$}{$b$}{$c$}{$d$},\:(a,b,c,d)\in {\cal D}^4.$$
\item Planar rooted trees with weight smaller than $5$:
$$\tun,\tdeux,\ttroisun,\ttroisdeux,\tquatreun, \tquatredeux,\tquatretrois,\tquatrequatre,\tquatrecinq,
\tcinqun, \tcinqdeux,\tcinqtrois,\tcinqquatre,\tcinqcinq,\tcinqsix,\tcinqsept,\tcinqhuit,
\tcinqneuf,\tcinqdix,\tcinqonze,\tcinqdouze,\tcinqtreize,\tcinqquatorze.$$
\item Planar rooted trees decorated by ${\cal D}$ with weight smaller than $4$:
$$\tdun{$a$},\: a\in {\cal D},{\cal H}space{1cm} \tddeux{$a$}{$b$},\: (a,b)\in {\cal D}^2,{\cal H}space{1cm}
\tdtroisun{$a$}{$c$}{$b$},\: \tdtroisdeux{$a$}{$b$}{$c$},\:(a,b,c)\in {\cal D}^3,$$
$$ \tdquatreun{$a$}{$d$}{$c$}{$b$},\: \tdquatredeux{$a$}{$d$}{$b$}{$c$},\:
\tdquatretrois{$a$}{$c$}{$d$}{$b$},\: \tdquatrequatre{$a$}{$b$}{$d$}{$c$},\:
\tdquatrecinq{$a$}{$b$}{$c$}{$d$},\:(a,b,c,d)\in {\cal D}^4.$$
\end{enumerate}

Let $t_1,\ldots,t_n$ be elements of ${\cal T}^{\cal D}$ and let $d\in {\cal D}$. We denote by $B_d(t_1\ldots t_n)$ the rooted tree obtained by grafting 
$t_1,\ldots,t_n$ on a common root decorated by $d$. For example, $B_d(\tddeux{$a$}{$b$}\tdun{$c$})=\tdquatredeux{$d$}{$c$}{$a$}{$b$}$.
This application $B_d$ can be extended in an operator:
$$B_d: \left\{ \begin{array}{rcl}
K[{\cal T}^{\cal D}] &\longrightarrow & K{\cal T}^{\cal D}\\
t_1\ldots t_n&\longrightarrow &B_d(t_1\ldots t_n),
\end{array}\right.$$
where $K[{\cal T}^{\cal D}]$ is the polynomial algebra generated by ${\cal T}^{\cal D}$ over $K$ and $K{\cal T}^{\cal D}$ is the $K$-vector space generated by ${\cal T}^{\cal D}$.
This operator is monic, and moreover $K{\cal T}^{\cal D}$ is the direct sum of the images of the $B_d$'s, $d\in {\cal D}$.

Similarly, let $t_1,\ldots,t_n$ be elements of ${\cal T}_P^{\cal D}$ and let $d\in {\cal D}$. We denote by $B_d(t_1\ldots t_n)$ the planar rooted tree obtained by
grafting $t_1,\ldots,t_n$ in this order from left to right on a common root decorated by $d$. For example, 
$B_a(\tddeux{$b$}{$c$}\tdun{$d$})=\tdquatredeux{$a$}{$d$}{$b$}{$c$}$ 
and $B_a(\tdun{$d$}\tddeux{$b$}{$c$})=\tdquatretrois{$a$}{$b$}{$c$}{$d$}$. 
This application $B_d$ can be extended in an operator:
$$B_d: \left\{ \begin{array}{rcl}
K\langle {\cal T}_P^{\cal D}\rangle &\longrightarrow & K{\cal T}_P^{\cal D}\\
t_1\ldots t_n&\longrightarrow &B_d(t_1\ldots t_n),
\end{array}\right.$$
where $K\langle{\cal T}_P^{\cal D}\rangle$ is the free associative algebra generated by ${\cal T}_P^{\cal D}$ over $K$ and $K{\cal T}_P^{\cal D}$ is the $K$-vector space generated
by ${\cal T}_P^{\cal D}$. This operator is monic, and moreover $K{\cal T}_P^{\cal D}$ is the direct sum of the images of the $B_d$'s, $d\in {\cal D}$.

\subsection{Free pre-Lie algebras}

\begin{defi}\textnormal{A (left) pre-Lie algebra is a couple $(A,\circ)$ where $A$ is a vector space and $\circ :A\otimes A\longrightarrow A$ 
satisfying the following relation: for all $x,y,z \in A$, 
$$(x\circ y) \circ z-x \circ (y\circ z)=(y\circ x) \circ z-y \circ (x\circ z).$$}
\end{defi}

Let ${\cal D}$ be a set. A description of the free pre-Lie algebra ${\cal PL}({\cal D})$ generated by ${\cal D}$ is given in \cite{Chapoton}. 
As a vector space, it has a basis given by ${\cal T}^{\cal D}$, and its pre-Lie product is given, for all $t_1,t_2 \in {\cal T}^{\cal D}$, by:
$$t_1 \circ t_2=\sum_{\mbox{\scriptsize $s$ vertex of $t_2$}} \mbox{grafting of $t_1$ on $s$}.$$
For example:
$$\tdun{$a$} \circ \tdtroisun{$d$}{$c$}{$b$}
=\tdquatreun{$d$}{$c$}{$b$}{$a$}+\tdquatredeux{$d$}{$c$}{$b$}{$a$}+\tdquatretrois{$d$}{$c$}{$a$}{$b$}
=\tdquatreun{$d$}{$c$}{$b$}{$a$}+\tdquatredeux{$d$}{$c$}{$b$}{$a$}+\tdquatredeux{$d$}{$b$}{$c$}{$a$}.$$
In other terms, the pre-Lie product can be inductively defined by:
$$ \left\{ \begin{array}{rcl}
t \circ \tdun{$d$}&\longrightarrow & B_d(t),\\
t\circ B_d(t_1\ldots t_n)&\longrightarrow &\displaystyle B_d(tt_1\ldots t_n)+\sum_{i=1}^n B_d(t_1\ldots (t \circ t_i) \ldots t_n).
\end{array}\right.$$

\begin{lemma} \label{3}
Let ${\cal D}$ a set. We suppose that ${\cal D}$ has a gradation $({\cal D}(n))_{n\in \mathbb{N}}$ such that, for all $n\in \mathbb{N}$, ${\cal D}(n)$ is finite set of 
cardinality denoted by $d_n$, and ${\cal D}(0)$ is empty. We denote by $F_{\cal D}(x)$ the Poincaré-Hilbert series of this set:
$$F_{{\cal D}}(x)=\sum_{n=1}^\infty d_n x^n.$$
This gradation induces a gradation $({\cal PL}({\cal D})(n))_{n\in \mathbb{N}}$ of ${\cal PL}({\cal D})$. Moreover, for all $n \mathfrak{g}eq 0$,
${\cal PL}({\cal D})(n)$ is finite-dimensional. We denote by $t^{\cal D}_n$ its dimension. Then the Poincaré-Hilbert series of ${\cal PL}({\cal D})$ satisfies:
$$F_{{\cal PL}({\cal D})}(x)=\sum_{n=1}^\infty t^{\cal D}_n x^n=\frac{F_{{\cal D}}(x)}{\displaystyle \prod_{i=1}^\infty (1-x^i)^{t^{\cal D}_i}}.$$
\end{lemma}

\begin{proof} The formal series of the space $K[{\cal T}^{\cal D}]$ is given by:
$$F(x)=\prod_{i=1}^\infty \frac{1}{(1-x^i)^{t^{\cal D}_i}}.$$
Moreover, for all $d\in {\cal D}(n)$, $B_d$ is homogeneous of degree $n$, so the Poincaré-Hilbert series of $Im(B_d)$
is $x^n F(x)$. As ${\cal PL}({\cal D})=K{\cal T}^{\cal D}=\bigoplus Im(B_d)$ as a graded vector space, its Poincaré-Hilbert formal series is:
$$F_{{\cal PL}({\cal D})}(x)=F(x)\sum_{n=1}^\infty d_nx^n=F(x)F_{{\cal D}}(x),$$
which gives the announced result. \end{proof}

\subsection{Free brace algebras}

\begin{defi}\textnormal{\cite{Aguiar,Chapoton2,Ronco}
A brace algebra is a couple $(A,\langle\rangle)$ where $A$ is a vector space and $\langle \rangle$ is a family of operators
$A^{\otimes n}\longrightarrow A$ defined for all $n \mathfrak{g}eq 2$:
$$\left\{ \begin{array}{rcl}
A^{\otimes n} &\longrightarrow & A\\
a_1\otimes \ldots \otimes a_n &\longrightarrow &\langle a_1,\ldots,a_{n-1};a_n\rangle,
\end{array}\right.$$
 with the following compatibilities: for all $a_1,\ldots,a_m$, $b_1,\ldots,b_n$, $c \in A$,
$$\langle a_1,\ldots,a_m;\langle b_1,\ldots, b_n; c \rangle \rangle
=\sum \langle \langle A_0,\langle A_1;b_1\rangle,A_2,\langle A_3;b_2\rangle,A_4,\ldots,A_{2n-2},\langle A_{2n-1};b_n\rangle,A_{2n};c\rangle,$$
where this sum runs over partitions of the ordered set $\{a_1,\ldots,a_n\}$ into (possibly empty) consecutive intervals
$A_0\sqcup \ldots \sqcup A_{2n}$. We use the convention $\langle a \rangle=a$ for all $a\in A$.} \end{defi}

For example, if $A$ is a brace algebra and $a,b,c \in A$:
$$\langle a; \langle b;c \rangle \rangle=\langle a,b;c \rangle+\langle b,a;c \rangle +\langle \langle a;b \rangle;c \rangle.$$
As an immediate corollary, $(A,\langle-;-\rangle)$ is a pre-Lie algebra.
Here is another example of relation in a brace algebra: for all $a,b,c,d \in A$,
$$\langle a,b;\langle c;d \rangle \rangle=\langle a,b,c;d\rangle+\langle a,\langle b;c\rangle; d\rangle
+\langle \langle a,b;c \rangle;d\rangle +\langle a,c,b;d \rangle+\langle \langle a;c \rangle, b;d\rangle
+\langle c,a,b;d\rangle.$$

Let ${\cal D}$ be a set. A description of the free brace algebra ${\cal B}r({\cal D})$ generated by ${\cal D}$ is given in \cite{Chapoton2,Foissy3}.
As a vector space, it has a basis given by ${\cal T}_P^{\cal D}$ and the brace structure is given, for all $t_1,\ldots,t_n \in {\cal T}_P^{\cal D}$, by:
$$\langle t_1,\ldots;t_n \rangle =\sum \mbox{graftings of $t_1\ldots t_{n-1}$ over $t_n$.}$$
Note that for any vertex $s$ of $t_n$, there are several ways of grafting a planar tree on $s$. For example:
$$\langle \tdun{$a$},\tdun{$b$};\tddeux{$d$}{$c$} \rangle
=\tdquatreun{$d$}{$c$}{$b$}{$a$}+\tdquatretrois{$d$}{$c$}{$b$}{$a$}+\tdquatreun{$d$}{$b$}{$c$}{$a$}
+\tdquatrequatre{$d$}{$c$}{$b$}{$a$}+\tdquatredeux{$d$}{$b$}{$c$}{$a$}+\tdquatreun{$d$}{$b$}{$a$}{$c$}.$$

As a consequence, the pre-Lie product of ${\cal B}r({\cal D})$ can be inductively defined in this way:
$$ \left\{ \begin{array}{rcl}
\langle t;\tdun{$d$} \rangle &\longrightarrow & B_d(t),\\
\langle t;B_d(t_1\ldots t_n) \rangle &\longrightarrow &\displaystyle \sum_{i=0}^n B_d(t_1\ldots t_i t t_{i+1} \ldots t_n)
+\sum_{i=1}^n B_d (t_1\ldots t_{i-1}\langle t;t_i \rangle t_{i+1}\ldots t_n).
\end{array}\right.$$

\begin{prop}
${\cal B}r({\cal D})$ is the free brace algebra generated by ${\cal D}$.
\end{prop}

\begin{proof} From \cite{Chapoton2,Foissy3}. \end{proof}

\begin{lemma} \label{5}
Let ${\cal D}$ a set, with the hypotheses and notations of lemma \ref{3}. The gradation of ${\cal D}$ induces a gradation $({\cal B}r({\cal D})(n))_{n\in \mathbb{N}}$ 
of ${\cal B}r({\cal D})$. Moreover, for all $n \mathfrak{g}eq 0$, ${\cal B}r({\cal D})(n)$ is finite-dimensional. Then the Poincaré-Hilbert series of ${\cal B}r({\cal D})$ is:
$$F_{{\cal B}r({\cal D})}(x)=\sum_{n=1}^\infty t'^{\cal D}_n x^n=\frac{\displaystyle 1-\sqrt{1-4F_{{\cal D}}(x)}}{2}.$$
\end{lemma}

\begin{proof} The Poincaré-Hilbert formal series of $K\langle {\cal T}_P^{\cal D}\rangle$ is given by:
$$F(x)=\frac{1}{1-F_{{\cal B}r({\cal D})}(x)}.$$
Moreover, for all $d\in {\cal D}(n)$, $B_d$ is homogeneous of degree $n$, so the Poincaré-Hilbert series of $Im(B_d)$
is $x^n F(x)$. As ${\cal B}r({\cal D})=K{\cal T}_P^{\cal D}=\bigoplus Im(B_d)$ as a graded vector space, its Poincaré-Hilbert formal series is:
$$F_{{\cal B}r({\cal D})}(x)=F(x) \sum_{n=1}^\infty d_nx^n=F(x)F_{\cal D}(x).$$
As a consequence, $F_{{\cal B}r({\cal D})}(x)-F_{{\cal B}r({\cal D})}(x)^2=F_{\cal D}(x),$ which implies the announced result. \end{proof}

\section{A non-associative permutative product on ${\cal B}r({\cal D})$}

\subsection{Definition and recalls}

The following definition is introduced in \cite{Livernet}:

\begin{defi} \textnormal{
A (left) non-associative permutative algebra is a couple $(A,\star)$, where $A$ is a vector space and $\star:A\otimes A\longrightarrow A$
satisfies the following property: for all $x,y,z \in A$,
$$x \star (y \star z)=y \star (x \star z).$$
}\end{defi}

Let ${\cal D}$ be a set. A description of the free non-associative permutative algebra ${\cal NAP}erm({\cal D})$ generated by ${\cal D}$ is given in \cite{Livernet}. As a vector space,
${\cal NAP}erm({\cal D})$ is equal to $K{\cal T}^{\cal D}$. The non-associative permutative product is given in this way: for all $t_1 \in {\cal T}^D$, $t_2=B_d(F_2) \in {\cal T}^D$,
$$t_1 \star t_2=B_d(t_1F_2).$$
 In other terms, $t_1 \star t_2$ is the tree obtained by grafting $t_1$ on the root of $t_2$.
 As ${\cal NAP}erm({\cal D})={\cal PL}({\cal D})$ as a vector space, lemma \ref{3} is still true when one replaces ${\cal PL}({\cal D})$ by ${\cal NAP}erm({\cal D})$.

\subsection{Permutative structures on planar rooted trees}

Let us fix now a non-empty set ${\cal D}$. We define the following product on ${\cal B}r({\cal D})=K{\cal T}_P^{\cal D}$:
for all $t \in {\cal T}_P^{\cal D}$, $t'=B_d(t_1\ldots t_n) \in {\cal T}_P^{\cal D}$,
$$t \star t'=\sum_{i=0}^n B_d (t_1\ldots t_i t t_{i+1}\ldots t_n).$$

\begin{prop}
$({\cal B}r({\cal D}),\star)$ is a non-associative permutative algebra.
\end{prop}

\begin{proof} Let us give $K\langle {\cal T}_P^{\cal D} \rangle$ its shuffle product: for all $t_1,\ldots,t_{m+n} \in {\cal T}_P^{\cal D}$,
$$(t_1\ldots t_m)*(t_{m+1}\ldots t_{m+n})=\sum_{\sigma \in Sh(m,n)} t_{\sigma^{-1}(1)} \ldots t_{\sigma^{-1}(m+n)},$$
where $Sh(m,n)$ is the set of permutations of $S_{m+n}$ which are increasing on $\{1,\ldots,m\}$ and $\{m+1,\ldots,m+n\}$.
It is well known that $*$ is an associative, commutative product. For example, for all $t,t_1,\ldots,t_n \in {\cal T}_P^{\cal D}$:
$$t *(t_1\ldots t_n)=\sum_{i=0}^n t_1\ldots t_i t t_{i+1}\ldots t_n.$$
As a consequence, for all $x \in K{\cal T}_P^{\cal D}$, $y \in K\langle {\cal T}_P^{\cal D} \rangle$, $d \in {\cal D}$:
\begin{equation}
\label{E1} x \star B_d(y)=B_d(x *y).
\end{equation}

Let $t_1,t_2,t_3=B_d(F_3) \in {\cal T}_P^{\cal D}$. Then, using (\ref{E1}):
\begin{eqnarray*}
t_1 \star (t_2 \star t_3)&=&t_1 \star B_d(t_2* F_3)\\
&=&B_d(t_1*(t_2*F_3))\\
&=&B_d((t_1*t_2)*F_3)\\
&=&B_d((t_2*t_1)*F_3)\\
&=&B_d(t_2*(t_1*F_3))\\
&=&t_2 \star (t_1 \star t_3).
\end{eqnarray*}
So $\star$ is a non-associative permutative product on ${\cal B}r({\cal D})$. \end{proof}

\subsection{Freeness of ${\cal B}r({\cal D})$ as a non-associative permutative algebra}

We now assume that ${\cal D}$ is finite, of cardinality $D$. We can then assume that ${\cal D}=\{1,\ldots,D\}$.

\begin{theo} \label{8}
$({\cal B}r({\cal D}),\star)$ is a free non-associative permutative algebra.
\end{theo}

\begin{proof} We graduate ${\cal D}$ by putting ${\cal D}(1)={\cal D}$. Then ${\cal B}r({\cal D})$ is graded, the degree of a tree $t \in {\cal T}_P^{\cal D}$ being the number 
of its vertices. By lemma \ref{5}, as the Poincaré-Hilbert series of ${\cal D}$ is $F_{\cal D}(x)=Dx$, the Poincaré-Hilbert series of ${\cal B}r({\cal D})$ is:
\begin{equation}
\label {E2} F_{{\cal B}r({\cal D})}(x)=\sum_{i=1}^\infty t'^{\cal D}_i x^i=\frac{1-\sqrt{1-4Dx}}{2}.
\end{equation}
We consider the following isomorphism of vector spaces:
$$B: \left\{ \begin{array}{rcl}
(K\langle {\cal T}_P^{\cal D}\rangle)^d &\longrightarrow & {\cal B}r({\cal D})\\
(F_1,\ldots,F_D)&\longrightarrow & \displaystyle \sum_{i=1}^d B_i(F_i).
\end{array}\right.$$
Let us fix a graded complement $V$ of the graded subspace ${\cal B}r({\cal D}) \star {\cal B}r({\cal D})$ in ${\cal B}r({\cal D})$.
Because ${\cal B}r({\cal D})$ is a graded and connected (that is to say ${\cal B}r({\cal D})(0)=(0)$), $V$ generates ${\cal B}r({\cal D})$ as a non-associative permutative algebra.
By (\ref{E1}), ${\cal B}r({\cal D})\star {\cal B}r({\cal D})=B(({\cal T}_P^{\cal D} * K\langle {\cal T}_P^{\cal D} \rangle)^D)$.

Let us then consider ${\cal T}_P^{\cal D} * K\langle {\cal T}_P^{\cal D}\rangle$, that is to say the ideal of $(K\langle {\cal T}_P^{\cal D} \rangle,*)$ generated by ${\cal T}_P^{\cal D}$.
It is known that $(K\langle {\cal T}_P^{\cal D} \rangle,*)$ is isomorphic to a symmetric algebra (see \cite{Ree}). Hence, there exists a graded subspace $W$
of $K\langle {\cal T}_P^{\cal D} \rangle$, such that $(K\langle {\cal T}_P^{\cal D} \rangle,*)\approx S(W)$ as a graded algebra. We can assume that $W$ contains
$K{\cal T}_P^{\cal D}$. As a consequence:
\begin{equation}
\label{E3} \frac{K\langle {\cal T}_P^{\cal D} \rangle}{{\cal T}_P^{\cal D}*K\langle {\cal T}_P^{\cal D} \rangle}
\approx \frac{S(W)}{S(W){\cal T}_P^{\cal D}}\approx S\left(\frac{W}{K{\cal T}_P^{\cal D}} \right).
\end{equation}
We denote by $w_i$ the dimension of $W(i)$ for all $i\in \mathbb{N}$. 
Then, the Poincaré-Hilbert formal series of $S\left(\frac{W}{K{\cal T}_P^{\cal D}} \right)$ is:
\begin{equation}
\label{E4} F_{S\left(\frac{W}{K{\cal T}_P^{\cal D}} \right)}(x)=\prod_{i=1}^\infty \frac{1}{(1-x^i)^{w_i-t'^{\cal D}_i}}.
\end{equation}
Moreover, the  Poincaré-Hilbert formal series of $K\langle {\cal T}_P^{\cal D} \rangle\approx S(W)$ is, by (\ref{E2}):
\begin{equation}
\label{E5} F_{S(W)}(x)=\frac{1}{1-F_{{\cal B}r({\cal D})}(x)}=\frac{1-\sqrt{1-4Dx}}{2Dx}=\frac{F_{{\cal B}r({\cal D})}(x)}{Dx}=\prod_{i=1}^\infty \frac{1}{(1-x^i)^{w_i}}.
\end{equation}
So, from (\ref{E3}), using (\ref{E4}) and (\ref{E5}), the Poincaré-Hilbert series of ${\cal T}_P^{\cal D}*K\langle {\cal T}_P^{\cal D} \rangle$ is:
\begin{eqnarray*}
F_{{\cal T}_P^{\cal D}*K\langle {\cal T}_P^{\cal D} \rangle}(x)&=&F_{S(W)}(x)-F_{S\left(\frac{W}{K{\cal T}_P^{\cal D}} \right)}(x)\\
&=&\prod_{i=1}^\infty \frac{1}{(1-x^i)^{w_i}}\left( 1-\prod_{i=1}^\infty (1-x^i)^{t'^{\cal D}_i}\right)\\
&=&\frac{F_{{\cal B}r({\cal D})}(x)}{Dx}\left( 1-\prod_{i=1}^\infty (1-x^i)^{t'^{\cal D}_i}\right).
\end{eqnarray*}
As $B$ is homogeneous of degree $1$, the Poincaré-Hilbert formal series of ${\cal B}r({\cal D}) \star {\cal B}r({\cal D})$ is:
$$F_{{\cal B}r({\cal D})\star {\cal B}r({\cal D})}(x)=Dx F_{{\cal T}_P^{\cal D}*K\langle {\cal T}_P^{\cal D} \rangle}(x)=F_{{\cal B}r({\cal D})}(x)\left( 1-\prod_{i=1}^\infty (1-x^i)^{t'^{\cal D}_i}\right).$$
Finally, the Poincaré-Hilbert formal series of $V$ is:
$$\ F_V(x)=F_{{\cal B}r({\cal D})}(x)-F_{{\cal B}r({\cal D})\star {\cal B}r({\cal D})}(x)=F_{{\cal B}r({\cal D})}(x) \prod_{i=1}^\infty (1-x^i)^{t'^{\cal D}_i}.$$

Let us now fix a basis $(v_i)_{i\in I}$ of $V$, formed of homogeneous elements. There is a unique epimorphism of non-associative permutative algebras:
$${\cal T}heta: \left\{ \begin{array}{rcl}
{\cal NAP}erm(I)&\longrightarrow & {\cal B}r({\cal D})\\
\tdun{$i$} &\longrightarrow & v_i.
\end{array}\right.$$
We give to $i\in I$ the degree of $v_i\in {\cal B}r({\cal D})$. With the induced gradation of ${\cal NAP}erm(I)$, ${\cal T}heta$ is a graded epimorphism.
In order to prove that it is an isomorphism, it is enough to prove that the Poincaré-Hilbert series of ${\cal NAP}erm(I)$ and ${\cal B}r({\cal D})$ are equal.
By lemma \ref{3}, the formal series of ${\cal NAP}erm(I)$, or, equivalently, of ${\cal PL}(I)$, is:
\begin{equation}
\label{E6} F_{{\cal NAP}erm(I)}(x)=\sum_{n=1}^\infty t^{\cal D}_ix^i=\frac{F_V(x)}{\displaystyle \prod_{i=1}^\infty (1-x^i)^{t^{\cal D}_i}}
=F_{{\cal B}r({\cal D})}(x) \prod_{i=1}^\infty (1-x^i)^{t'^{\cal D}_i-t^{\cal D}_i}.
\end{equation}
Let us prove inductively that $t_n=t'_n$ for all $n \in \mathbb{N}$. It is immediate if $n=0$, as $t_0=t'_0=0$.
Let us assume that $t^{\cal D}_i=t'^{\cal D}_i$ for all $i<n$. Then:
$$ \prod_{i=1}^\infty (1-x^i)^{t^{\cal D}_i-t'^{\cal D}_i}=1+\mathcal{O}(x^n).$$
As $t'_0=0$, the coefficient of $x^n$ in (\ref{E6}) is $t_n=t'_n$. So $F_{{\cal NAP}erm(I)}(x)=F_{S(W)}(x)$, and ${\cal T}heta$ is an isomorphism. \end{proof}

\section{Freeness of ${\cal B}r({\cal D})$ as a pre-Lie algebra}

\subsection{Main theorem}

\begin{theo}
Let ${\cal D}$ be a finite set. Then ${\cal B}r({\cal D})$ is a free pre-Lie algebra.
\end{theo}

\begin{proof} We give a $\mathbb{N}^2$-gradation on ${\cal B}r({\cal D})$ in the following way:
$${\cal B}r({\cal D})(k,l)=Vect(t\in {\cal T}_P^{\cal D}\:/\: \mbox{$t$ has $k$ vertices and the fertility of its root is $l$}).$$
The following points are easy:
\begin{enumerate}
\item For all $i,j,k,l \in \mathbb{N}$, ${\cal B}r({\cal D})(i,j)\star {\cal B}r({\cal D})(k,l)\subseteq {\cal B}r({\cal D})(i+k,l+1)$.
\item For all $i,j,k,l \in \mathbb{N}$, $t_1 \in {\cal B}r({\cal D})(i,j)$, $t_2 \in {\cal B}r({\cal D})(k,l)$, $\langle t_1;t_2 \rangle-t_1 \star t_2 \in Br({\cal D})(i+k,l)$.
\end{enumerate}
Let us fix a complement $V$ of ${\cal B}r({\cal D}) \star {\cal B}r({\cal D})$ in ${\cal B}r({\cal D})$ which is $\mathbb{N}^2$-graded. Then ${\cal B}r({\cal D})$ is isomorphic 
as a $\mathbb{N}$-graded non-associative permutative algebra to ${\cal NAP}erm(V)$, the free non-associative permutative algebra generated by $V$.

Let us prove that $V$ also generates ${\cal B}r({\cal D})$ as a pre-Lie algebra. As ${\cal B}r({\cal D})$ is $\mathbb{N}$-graded, with ${\cal B}r({\cal D})(0)$, it is enough to prove
that ${\cal B}r({\cal D})=V+\langle {\cal B}r({\cal D});{\cal B}r({\cal D}) \rangle$. Let $x\in {\cal B}r({\cal D})(k,l)$, let us show that $x\in V+\langle {\cal B}r({\cal D});{\cal B}r({\cal D}) \rangle$ by induction on $l$.
If $l=0$, then $t \in {\cal B}r({\cal D})(1)=V(1)$. If $l=1$,  we can suppose that $x=B_d(t)$, where $t\in {\cal T}_P^{\cal D}$. 
Then $x=\langle t;\tdun{$d$}\rangle \in \langle {\cal B}r({\cal D});{\cal B}r({\cal D}) \rangle$.  Let us assume the result for all $l'<l$. 
As $V$ generates $({\cal B}r({\cal D}),\star)$, we can write $x$ as:
 $$x=x'+\sum_i  x_i \star y_i,$$
 where $x' \in V$ and $x_i,y_i \in {\cal B}r({\cal D})$. By the first point, we can assume that:
$$\sum_i x_i \otimes y_i \in \bigoplus_{i+j=k} {\cal B}r({\cal D})(i) \otimes {\cal B}r({\cal D})(j,l-1).$$
So, by the second point:
\begin{eqnarray*}
x-x'-\sum_i \langle x_i;y_i \rangle&=&\sum_i x_i \star y_i -\langle x_i;y_i \rangle\\
&\in& \sum_{i+j=k} {\cal B}r({\cal D})(i+j,l-1)\\
&\in& V+\langle {\cal B}r({\cal D});{\cal B}r({\cal D}) \rangle,
\end{eqnarray*}
by the induction hypothesis. So $x \in V+\langle {\cal B}r({\cal D});{\cal B}r({\cal D}) \rangle$.
 
 Hence, there is an homogeneous epimorphism:
 $$ \left\{ \begin{array}{rcl}
{\cal PL}(V)&\longrightarrow & {\cal B}r({\cal D})\\
v \in V&\longrightarrow & v.
\end{array}\right.$$
As ${\cal PL}(V)$, ${\cal NAP}erm(V)$ and ${\cal B}r({\cal D})$ have the same Poincaré-Hilbert formal series, this is an isomorphism. \end{proof}\\

We now give the number of generators of ${\cal B}r({\cal D})$ in degree $n$ when $card({\cal D})=D$ for small values of $n$, computed using lemmas \ref{3} 
and \ref{5}:
\begin{enumerate}
\item For $n=1$, $D$.
\item For $n=2$, $0$.
\item For $n=3$, $\displaystyle \frac{D^2(D-1)}{2}$.
\item For $n=4$, $\displaystyle \frac{D^2(2D-1)(2D+1)}{3}$.
\item For $n=5$, $\displaystyle \frac{D^2(31D^3-2D^2-3D-2)}{8}$.
\item For $n=6$, $\displaystyle \frac{D^2(356D^4-20D^3-5D^2+5D-6)}{30}$.
\item For $n=7$, $\displaystyle \frac{D^2(5441D^5-279D^4-91D^3-129D^2-22D-24)}{144}$.
\end{enumerate}

\subsection{Corollaries}

\begin{cor}
Let ${\cal D}$ be any set. Then ${\cal B}r({\cal D})$ is a free pre-Lie algebra.
\end{cor}

\begin{proof} We graduate ${\cal B}r({\cal D})$ by putting all the $\tdun{$d$}$'s homogeneous of degree $1$.
Let $V$ be a graded complement of $\langle {\cal B}r({\cal D}),{\cal B}r({\cal D})\rangle$. There exists an epimorphism of graded pre-Lie algebras:
$$ {\cal T}heta: \left\{ \begin{array}{rcl}
{\cal PL}(V)&\longrightarrow & {\cal B}r({\cal D})\\
\tdun{$v$}&\longrightarrow & v.
\end{array}\right.$$
Let $x$ be in the kernel of ${\cal T}heta$. There exists a finite subset ${\cal D}'$ of ${\cal D}$, such that all the decorations of the vertices of the trees appearing in
$x$ belong to ${\cal B}r({\cal D}')$. By the preceding theorem, as ${\cal B}r({\cal D}')$ is a free pre-Lie algebra, $x=0$. So ${\cal T}heta$ is an isomorphism. \end{proof}

\begin{cor}
Let ${\cal D}$ be a graded set, satisfying the conditions of lemma \ref{3}. There exists a graded set ${\cal D}'$,  such that $({\cal H}_{PR}^{\cal D})_{ab}$ is isomorphic, 
as a graded Hopf algebra, to ${\cal H}_R^{{\cal D}'}$.
\end{cor}

\begin{proof} $({\cal H}_{PR}^{\cal D})_{ab}$ is isomorphic, as a graded Hopf algebra, to ${\cal U}({\cal B}r({\cal D}))^*$. 
For a good choice of ${\cal D}'$, ${\cal B}r({\cal D})$ is isomorphic to ${\cal PL}({\cal D}')$ as a pre-Lie algebra, so also as a Lie algebra.
So ${\cal U}({\cal B}r({\cal D}))$ is isomorphic to ${\cal U}({\cal PL}({\cal D}'))$. Dually, $({\cal H}_{PR}^{\cal D})_{ab}$ is isomorphic to ${\cal H}_R^{{\cal D}'}$. \end{proof}

\begin{cor}
Let ${\cal D}$ be graded set, satisfying the conditions of lemma \ref{3}. Then $({\cal H}_{PR}^{\cal D})_{ab}$ is a cofree coalgebra. Moreover, ${\cal B}r({\cal D})$ is free as a Lie algebra.
\end{cor}

\begin{proof} It is proved in \cite{Foissy} that $({\cal H}_R^{{\cal D}'})^*$ is a free algebra, so $Prim(({\cal H}_R^{{\cal D}'})^*)={\cal PL}({\cal D}')$ is a free Lie algebra and
${\cal H}_R^{{\cal D}'}$ is a cofree coalgebra. So $Prim(({\cal H}_{PR}^{\cal D})^*)={\cal B}r({\cal D})$ is a free Lie algebra and ${\cal H}_{PR}^{\cal D}$ is a cofree coalgebra. \end{proof}

\end{document}