\documentstyle[11pt,english]{article} %\nopagenumber \textwidth 140mm \textheight 240mm \topmargin -20mm \font\twelvesym=msbm10 at 12pt \font\tensym=msbm10 \font\sevensym=msbm7 \font\fivesym=msbm5 \font\twelvegoth=eufb10 at 12pt \font\tengoth=eufb10 \font\sevengoth=eufb7 \font\fivegoth=eufb5 \newfam\symfam \textfont\symfam=\tensym \scriptfont\symfam=\sevensym \scriptscriptfont\symfam=\fivesym \def\sym{\fam\symfam\tensym} \newfam\gothfam \textfont\gothfam=\tengoth \scriptfont\gothfam=\sevengoth \scriptscriptfont\gothfam=\fivegoth \def\goth{\fam\gothfam\tengoth} \setcounter{section}{0} \newtheorem{theorem}{Theorem} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{definition}[theorem]{Definition} \newtheorem{note}{Note} \newtheorem{remark}[note]{Remark} \newtheorem{algorithm}{Algorithm} \newtheorem{example}{Example} \def\Preuve{\medskip\noindent {\it Preuve --- \ }} \def\cqfd{\hfill \\ \hbox{ }\hfill$\Box$ \bigskip} \def\shuf{\sqcup\!\!\sqcup} \def\bb{\sym} \def\B{{\sym B}} \def\Q{{\sym Q}} \def\Z{{\sym Z}} \def\M{{\sym M}} \def\F{{\sym F}} \def\Ma{{\goth M}} \def\GG{{\sym G}} \def\L{{\sym L}} \def\OV#1{\overline{#1}} \def\bs{$\backslash$} \def\G{\Gamma} \def\g{\gamma} \def\S{\Gamma^{(1)}} \def\H{{\goth H}} \def\ep{\epsilon} \def\al{\alpha} \def\A{{\bb A}} \def\C{{\bb C}} \def\R{{\bb R}} \def\N{{\bb N}} \def\bx{\bar x} \def\nat{{\tt nat}} \def\s{s} \def\CQFD{\\ \hbox{ }\hfill$\Box$} \def\preceq{\underline{\prec}} \def\Alph{\mbox{Alph}} \title{{\bf Transitive factorizations of free partially commutative monoids and Lie algebras}} \author{G. {\sc Duchamp} J.G. {\sc Luque} \thanks{LIFAR, Facult\'e des Sciences et des Techniques, 76821 Mont-Saint-Aignan CEDEX, France. Emails: {\tt ged,luque@dir.univ-rouen.fr}}} \begin{document} \maketitle \begin{abstract} Let $\M(A,\theta)$ be a free partially commutative monoid. We give here a necessary and sufficient condition on a subalphabet $B\subset A$ such that the right factor of a bisection $\M(A,\theta)=\M(B,\theta_B).T$ be also partially commutative free. This extends strictly the (classical) elimination theory on partial commutations and allows to construct new factorizations of $\M(A,\theta)$ and associated bases of $L_K(A,\theta)$. \end{abstract} \begin{center}{\small\bf R\'esum\'e}\end{center} \begin{quote} \small Soit $\M(A,\theta)$ un mono\"\i de partiellement commutatif libre. Nous donnons une condition n\'ecessaire et suffisante sur un sous alphabet $B\subset A$ pour que le facteur droit d'une bisection de la forme $\M(A,\theta)=\M(B,\theta_B).T$ soit partiellement commutatif libre. Ceci nous permet d'\'etendre strictement la th\'eorie (classique) de l'\'elimination avec commutations partielles et de construire de nouvelles factorisations de $\M(A,\theta)$ ainsi que les bases de $L_K(A,\theta)$ associ\'ees. \end{quote} \baselineskip = 15pt \section{Introduction} A factorization of a monoid is a direct decomposition $$ M=\prod^{\leftarrow}_{i\in I} M_i $$ where $M$ and the $M_i$ are monoids and $I$ is totally ordered. This notion is due to {\sc Sch\"utzenberger} (see [14] and [15] where the link with the free Lie algebra is studied). Then, in his Ph. D. [17], {\sc Viennot} showed how combinatorial bases of the free Lie algebra could be constructed by composition of bisections (i.e. $|I|=2$) obtained by elimination of generators (ideas initiated by {\sc Lazard} \cite{Laz} and {\sc Shirshov} \cite{Shi}). One of the authors with D. Krob found similar decompositions for the free partially commutative monoid into free factors and studied the link with Lie algebras and groups [8].\\ Here, we study the general problem of eliminating generators in these structures and first remark that a direct decomposition $$ M(A,\theta)=M(B,\theta_B).T $$ (with $B\subset A$, a subalphabet) is always monoidal. We get a criterium to characterize the case when $T$ is free partially commutative and construct bases of the associated Lie algebras. The case of the group is also mentionned. \section{Definitions and background} We recall that the free partially commutative monoid is the monoid presented defined by generators and relations $$ \M(A,\theta)=\langle A|ab=ba, (a,b)\in \theta\rangle_{Mon} $$ where $A$ is an alphabet and $\theta\subset A\times A$ is an antireflexive (i.e. without loops) and symmetric graph on $A$ ($\theta$ is called an independence relation). Thus, $\M(A,\theta)$ is the quotient $A^*/_{\equiv_\theta}$ where $\equiv_\theta$ is the congruence generated by the set $\{(ab,ba)|(a,b)\in \theta\}$.\\ If $X$ is a subset of $\M(A,\theta)$, we set $$\theta_{X}=\{(x_1,x_2)\in X^2 | \Alph(x_1)\times \Alph(x_2)\subset \theta\}.$$ Note that this implies $\Alph(x_1)\cap \Alph(x_2)=\emptyset$. Similarly, we set $\theta_\M=\theta_{\M(A,\theta)}$.\\ As in \cite{DK2}, we denote $IA(t)=\{z\in M|t=zw\}$ and $TA(t)=\{z\in M|t=wz\}$. \\ In \cite{CH} and \cite{DR}, Choffrut introduces the partially commutative codes as generator sets of free partially commutative submonoids. Let $X$ be a set, we can prove easily that this definition is equivalent to the fact that each trace $t\in\langle X\rangle$ admits a unique decomposition on $X$ up to the commutations (i.e. $(X,\theta_X)$ is the independence alphabet of $\langle X\rangle$ the submonoid generated by $X$). \begin{example} (i) Each subalphabet $B$ of $A$ is a partially commutative code.\\ (ii) Let $(A,\theta)= a-b\quad c$. The set $\{c,cb,ca\}$ is a code but not the set $\{b,a,ca,cb\}$. \end{example} \section{Transitive bisections} \subsection{Generalities} We recall the definition of a factorization in the sense of Sch\"utzenberger (cf. Viennot in \cite{Vi1} and \cite{Vi2}), this notion will be reused extensively at the end of the paper. \begin{definition} (i) Let $\M$ be a monoid and $(\M_i)_{i\in J}$ an ordered family of submonoids (the total ordering on $J$ will be denoted $<$). The family $(M_i)_{i\in J}$ will be called a {\rm factorization} of $\M$ if and only if every $m\in\M^+=\M-\{1\}$ can be written uniquely for some $n$ as \[m=m_{i_1}m_{i_2} \dots m_{i_n}\] with $i_1>i_2> \dots >i_k$ and for each $k\in[1..n]$, $m_{i_k}\in\M^+_{i_k}$.\\ (ii) In the case of a free partially commutative monoid, a factorization will be denoted by the sequence of the minimal generator sets of its components. \end{definition} In the maximal case (each monoid has a unique generator), the factorization is called {\it complete}. \begin{example} (Complete factorizations in free and free partially commutative monoids.)\\ In the free monoid, it exists many complete factorizations. The most famous being the Lyndon factorization (defined as the set of primitive words minimal in their conjugacy classes) is an example of complete factorization. The Hall sets defined in \cite{Sc} give us a wider example.\\ The set of Lyndon traces (i.e. the generalization of Lyndon words to the partially commutative case, defined by Lalonde in \cite{La}) endowed with the lexicographic ordering is a complete factorization of the free partially commutative monoid. \end{example} In the smallest case ($|J|=2$), the factorization is called {\it bisection}. Let $M$ be a monoid, then $(M_1,M_2)$ is a bisection of $M$ if and only if the mapping \[M_1\times M_2\rightarrow M \] \[(m_1,m_2)\rightarrow m_1m_2\] is one to one.\\ \begin{remark} Not every submonoid is a left (right) factor of a bisection. If $M=M_1M_2$ is a bisection then $M_1$ satisfies $(u,uv\in M_1)\Rightarrow (v\in M_1)$ (see \cite{Dub}), however, this condition is not sufficient as shown by $M_1=2\Z\subset\Z=M$. \end{remark} In case $M=\M(A,\theta)$, one prove the following property. \begin{proposition}\label{PFACT2} Let $(A,\theta)$ be an independence relation and $B\subset A$. Then $\M(B,\theta_B)$ is the left (resp. right) factor of a bisection of $\M(A,\theta)$. \end{proposition} {\bf Proof } It suffices to prove that $\underline{\M(B,\theta_B)}^{-1}\underline{\M(A,\theta)}$ (resp. $\underline{\M(A,\theta)}.\underline{\M(B,\theta_B)}^{-1}$) is the characteristic series of a monoid.\CQFD\\ In the left case, the right submonoid above has a minimal generating subset \[\beta_Z(B)=\{zw/z\in Z, w\in \M(B,\theta_B), IA(zw)= \{z\}\}\] where $IA(t)=\{b\in A/t=bw\}$. \begin{remark}The monoid $\langle \beta_Z(B)\rangle$ may not be free partially commutative. For example, if $A=\{a,b,c\}$, \[ \theta: a-b\quad c \] and $B=\{c\}$ then $a,b,ac,bc\in \beta_Z(B)$ and $a.bc=b.ac$.\\ \\ \end{remark} \subsection{Transitively factorizing subalphabet} Here we discuss a criterium for the complement $\langle \beta_Z(B)\rangle$ to be a free partially commutative submonoid. \begin{definition} Let $B\subset A$, we say that $B$ is a {\rm transitively factorizing subalphabet} (TFSA) if and only if for each $z_1\neq z_2\in Z$ and $w_1, w_2, w'_1, w'_2\in\M(A,\theta)$ such that $IA(z_1w_1)=IA(z_1w'_1)=\{z_1\}$ and $IA(z_1w_2)=IA(z_2w'_2)=\{z_2\}$ we have \[z_1w_1z_2w_2=z_2w'_2z_1w'_1\Rightarrow w_1=w'_1, w_2=w'_2. \] \end{definition} We prove the following theorem. \begin{theorem} Let $B\subset A$. The following assertions are equivalent. \begin{quote} (i) The monoid $\langle \beta_Z(B)\rangle$ is free partially commutative\\ (ii) The subalphabet $B$ is TFSA.\\ (iii) For each $(z,z')\in Z^2\cap \theta$, the dependence\footnote{The dependence graph is defined by $A\times A-\Delta-\theta$ where $\Delta=\{(a,a)/a\in A\}$.} graph has no partial graph\footnote{We repeat here the notion of partial graph. A graph $G'=(S',A')$ is a partial graph of $G=(S,A)$ if and only if $S'\subset S$ and $A'\subset A\cap S'\times S'$ ($G'$ is a subgraph of $G$ when equality occurs).} like \[z-b_1-\dots-b_n-z'.\] with $b_1,\dots,b_n\in B$.\\ (iv) For each $(z,z')\in Z^2$ we have \[(z,z')\in\theta\Leftrightarrow \beta_z(B)\times\beta_{z'}(B)\subseteq \theta_\M\] \end{quote} \end{theorem} {\bf Proof} It is easy to see that (i)$\Rightarrow$(ii) : by contraposition, if $B$ is not a TFSA we can find $z_1w_1,z_2w_2, z_1w'_1, z_2w'_2\in \beta_Z(B)$ such that $z_1w_1.z_2w_2=z_2w'_2.z_1w'_1$ with $w_1\neq w'_1$ and $w_2\neq w'_2$ and this implies that $\beta_Z(B)$ is not a partially commutative code.\\ Let us proof that (ii)$\Rightarrow$(iii). Suppose that \[z-b_1-\dots-b-n-z'\] is a partial graph of the dependance graph, then it exists a subgraph of the dependence graph under the form \[z-c_1-\dots-c_m-z'\] with $c_i\in B$. Consider the smallest integer $k$ such that $(c_{k+1},z')\not\in\theta$. Then we have $zc_1\dots c_k.z'c_{k+1}\dots c_{m}=z'.zc_1\dots c_m$, which proves that $B$ is not a TFSA.\\ Conversely, suppose that $zw_1.z'w_2=z'w'_2.zw'_1$ with $zw_1,z'w_2, zw'_1, z'w'_2\in \beta_Z(B)$ and $w'_2\neq w_2$ , $w'_1\neq w_1$. Using Levi's lemma it exists $w'\in \M(B,\theta_B)-\{1\}$ such that $w'_1=w_1w'$ and $w_2=w'_2w'$. Furthermore, if $zw\in\beta_Z(B)$ and $b\in \Alph(w)$, it exists a partial graph of the dependence graph under the form \[z-b_1-\dots-b_n-b.\] Hence, if we take $c\in\Alph(w')$ the dependence graph admits a partial graph under the form \[z-b_1-\dots-b_n-c-b'_m-\dots-b'_1-z'.\] Which implies (iii)$\Rightarrow$ (i).\\ Let us proof that (iii) $\Rightarrow$ (iv). Suppose (iii) occurs. If $\beta_z(B)\times\beta_{z'}(B)\subseteq \theta_\M$ then easily $(z,z')\in \theta$. Conversely, suppose that $(z,z')\in\theta$ and let $zw\in\beta_z(B)$ and $z'w'\in\beta_{z'}(B)$. If $(zw,z')\not\in\theta_\M$, as $z\neq z'$ and $|w|_Z=0$, we have necessarily $zw.z'\neq z'.zw$. Hence, it exists a partial graph of the dependence graph under the form \[z-b_1-\dots-b_n-z'\] with $b_1\in \Alph(w)\subseteq B$ which contradicts our hypothesis. If $(z',zw)\in\theta_\M$ and $(z'w',zw)\not\in\theta_\M$, we can write $zw.z'w'=z'u.zwv$ where $w'=uv$ and $u$ is the great prefix of $w'$ such that $(u,zw)\in \theta_\M$. Which implies that $zwv,z'u\in\beta_Z(B)$ and then $B$ is not a TFSA which contradicts our hypothesis and proof the assertion.\\ Finally, we prove that (iv)$\Rightarrow$ (i). Consider the mapping $\mu$ from $Z$ into $K\langle\langle A,\theta\rangle\rangle$ defined by $\mu(z)=\underline{\beta_Z(B)}$. As $(z,z')\in \theta_Z\Rightarrow [\mu(z),\mu(z')]=[\underline{\beta_z(B)},\underline{\beta_{z'}(B)}]=0$ and $\langle \mu(z),1\rangle=0$, we can extend $\mu$ as a continuous morphism from $K\langle\langle Z,\theta_Z\rangle\rangle$ in $K\langle\langle A,\theta\rangle\rangle$. Let $s$ be the morphism from $\langle \beta_z(B)\rangle$ in $\M(Z,\theta_Z)$ defined by $s(zw)=z$ for each $zw\in\beta_Z(B)$. We have \[\begin{array}{rcccc} \underline{\langle\beta_z(B)\rangle}&=&s^{-1}(\underline{\M(Z,\theta_Z))}&=& \sum_{w\in\M(Z,\theta_Z)}s^{-1}(w)\\ &=&\sum_{w\in\M(Z,\theta_Z)}\mu(w)&=&\mu(\underline{\M(Z,\theta_Z)}) \end{array}\] Let $P(\theta_Z)$ be the polynomial such that \[\underline{\M(Z,\theta_Z)}=\frac 1 {P(\theta_Z)}.\] As $\mu$ is a continuous morphism, we have \[\underline{\langle\beta_Z(B)\rangle}=\frac1{\mu(P(\theta_Z))}=\frac1{P(\th eta_{\beta_Z(B)})}\] which is the characteristic series of $\M(\beta_Z(B),\theta_{\beta_Z(B)})$. \CQFD \begin{remark} (i) Elimination in \cite{DK2} deals with the particular case when $A- B$ is totally non commutative, in this case $B$ is a TFSA of $A$.\\ (ii) As an example of other case, consider the independance alphabet given by the graph\[\theta=a-b-c.\] The monoid $\langle \beta_{a,b}(c)\rangle$ is free partially commutative, its alphabet is $\beta_{a,b}(c)=\{b\}\cup\{ac^n/n\geq0\}$ and its independance graph is \[\theta_{\beta_{a,b}(c)}=\begin{array}{ccccc} & &c& & \\ & &|&\ddots& \\ a&-&b&- &ac^n\\ & & & &\vdots \end{array}\] \end{remark} \section{Factorizations and bases of free partially commutative Lie algebra} \subsection{Transitive factorizations} We recall some definitions given by Viennot in \cite{Vi1}. \begin{definition} Let $\M$ be a monoid, $\M'$ a submonoid of $\M$ and $\F=(\M_i)_{i\in J}$ a factorization of $\M$. We denote $\F|_{\M'}=(\M_{i_k})_{k\in K}$ where $K=\{k/in J/\M_k\subseteq \M'\}$ (in the general case it is not a factorization). \end{definition} \begin{definition}\label{DDD5} Let $\prec$ be the partial order on the set of all the factorizations of a monoid $\M$ defined by $\F=(\M_i)_{i\in J}\prec\F'=(\M'_i)_{i\in J'}$ ($\F'$ is finer than $\F$) if and only if $J'$ admits a decomposition $J'=\sum_{i\in J} J_i$ as an ordered sum of intervals such that for each $i\in J$, $(\M'_j)_{j\in J_i}$ is a factorization of $\M_i$. \end{definition} The following property is straightforward. \begin{proposition}\label{PPP1} Let $\F=(\M_i)_{i\in I}$ be a factorization and $\F'$ be a factorization such that $\F\preceq\F'$ then for each $i\in I$, $\F'|_{\M_i}$ is a factorization of $\M_i$. \end{proposition} \begin{definition} Let $\B=(B_1,B_2)$ be a bisection and $\F=(Y_i)_{i\in J}$ a factorization. We say that $Y_i$ is {\rm cut} by $\B$ if and only if $\L_i(\B)=\langle B_1\rangle\cap\langle Y_i\rangle$ and $\R_i(\B)=\langle B_2\rangle\cap \langle Y_i\rangle$ are not trivial. \end{definition} We need the following lemma.\\ \begin{lemma}\label{LLL1} Let $\B=(B_1,B_2)$ be a bisection of \hspace{1mm}$\M(A,\theta)$ and $\F=(Y_i)_{i\in[1,n]}$ a factorization with $n>1$, such that it exists a factorization $\GG=(G_k)_{k\in K}$ such that $\B,\F\preceq\GG$ then $\B\preceq\F$ if and only if no $Y_i$ is cut by $\B$. \end{lemma} {\bf Proof } We use the decomposition of K as an ordered sum of intervals $K=J_1+J_2=\sum_{i\in[1,n]}I_i$ as in definition \ref{DDD5}. The assertion $(ii)$ implies the existence of an integer $k\in [1,n]$ such that $J_1=\sum_{i\in[1,k]}I_i$ and $J_2=\sum_{i\in[k+1,n]}I_i$. This allows us to conclude.\CQFD In the sequel, we use the notion of composition of factorizations as it is defined by Viennot in \cite{Vi1}. We recall it here. \begin{definition} Let $\F=(\M_i)_{i\in I}$ be a factorization of a monoid $\M$ and for some $k\in I$, $\F'=(\M'_i)_{i\in I'}$ a factorization of $\M_k$. The {\rm composition} of $\F$ and $\F'$ is the factorization $\F'\circ \F=(\M''_i)_{i\in I''}$ where $I''=I\cup I'-\{k\}$ is ordered by $i_Ik$ and $j\in I$ \end{quote} and \[\M''_i=\left\{\begin{array}{ll} \M_i&\mbox{if }i\in I\\ \M'_i&\mbox{if }i\in I'\end{array}\right.\] \end{definition} \begin{definition} We call {\rm transitive factorization} a factorization which is composed of transitive bisections. \end{definition} \begin{lemma}\label{LLL3} Let $\F=(Y_i)_{i\in[1,p]}$ be a transitive factorization and Let $\B=(B,\beta_Z(B))$ be a transitive bisection such that it exists a factorization $\GG$ finer that $\B$ and $\F$. Then it exists at most one $Y_i$ cut by $\B$ and for a such $i$ we have \begin{quote} (i) The subset $T=Y_i\cap\M(B,\theta_B)$ is a TFSA of $Y_i$ and $\R_i(\B)$ is the right monoid of the associated bisection.\\ (ii) The sequence $(Y_p, \dots ,Y_{i+1},T)$ is a transitive factorization of $\M(B,\theta_B)$.\\ (iii) The sequence $(\beta_{Y_i-T}(T),Y_{i-1}, \dots ,Y_1)$ is a transitive factorization of $\M(\beta_Z(B),\theta_{\beta_Z(B)})$ \end{quote} \end{lemma} {\bf Sketch of the proof} First it suffices to remark that if $i>j$ are two indices such that $Y_i$ and $Y_j$ are cut by $\B$ then $\L_j(\B)\subseteq \M(B,\theta_B)\cap\M(\beta_Z(B),\theta_Z(B))=\{1\}$ and this contradicts our hypothesis, hence $i=j$.\\ Let us prove assertion (i).\\ 1) First, we remark that \[\underline{\M(Y_i,\theta_{Y_i})}=\underline{\L_i(\B)}.\underline{\R_i(\B)} \] and using the equality $\L_i(\B)=\M(T,\theta_T)$ we prove that $\R_i(\B)=\langle \beta_{Y_i-T}(Y_i)\rangle$.\\ 2) We show that if $T$ is not a TFSA of $Y_i$ then $\B$ is not a TFSA of $A$ and this implies the result.\\ Let us prove (ii) and (iii) by induction on $p$. If $p=1$ the result is trivial otherwise we can write $\F$ under the form $\F=\F_1\circ\F_2\circ\B'$ where $\B'=(B',\beta_{Z'}(B'))$ is a transitive bisection, $\F_1=(Y_p, \dots ,Y_{k+1})$ a transitive factorization of $\M(B',\theta_{B'})$ and $\F_2=(Y_{k}, \dots ,Y_1)$ a transitive factorization of the monoid $\M(\beta_{Z'}(B'),\theta_{\beta_{Z'}(B')})$. If $\B=\B'$ the result is trivial otherwise we have necessarily $B\subset B'$ or $B'\subset B$. We suppose that $B'\subset B$ (the other case is symmetric), and we consider the transitive trisection $(B',\beta_{B-B'}(B'),\beta_Z(B))$. Using the induction hypothesis we find that $(Y_k, \dots ,Y_i,T)$ and $(\beta_{Y_i-T}(T),Y_{i-1}, \dots ,Y_1)$ are transitive factorizations (respectively of the monoid $\M(\beta_{B-B'},\theta_{\beta_{B-B'}(B)})$ and $\M(\beta_Z(B),\theta_{\beta_Z(B)})$). And then \[(Y_p, \dots ,Y_{i+1},T)=\F_1\circ(Y_k, \dots ,Y_{i+1},T)\circ(B',\beta_{B-B'}(B))\] is a transitive factorization. \CQFD \begin{lemma}\label{LLL4} Let $\B=(B,\beta_Z(B))$ be a transitive bisection and $\F=(Y_i)_{i\in[1,n]}$ be a transitive factorization such that $\B\preceq\F$. Then the factorizations $\F|_{\M(B,\theta_B)}$ and $\F|_{\M(\beta_Z(B),\theta_{\beta_Z(B)})}$ are transitive. \end{lemma} {\bf Proof } We can prove the result by induction on $n$. \CQFD \begin{proposition}\label{PPP2} Let $\F=(Y_i)_{i\in J}$ and $\F'=(Y'_j)_{j\in J'}$ be two finite transitive factorizations such that it exists a factorization $\GG$ with $\F,\F'\preceq\GG$ then it exists a transitive finite factorization $\GG'$ such that \begin{quote} (i) $\F,\F'\preceq \GG'\preceq\GG$\\ (ii) For each $j\in J$, $\GG'|_{\M(Y_j,\theta_{Y_j})}$ is a transitive finite factorization.\\ (iii) For each $j\in J'$, $\GG'|_{\M(Y'_j,\theta_{Y'_j})}$ is a transitive finite factorization.\\ \end{quote} \end{proposition} {\bf Sketch of the proof } We set $J=[1,n]$, $J'=[1,n']$ and we prove the result by induction on $n$. If $n=1$ the result is trivial. If $n=2$, lemmas \ref{LLL1}, \ref{LLL3} and \ref{LLL4} give us the proof. If $n\geq 2$, we set $\F=\F_1\circ\F_2\circ\B$ where $\B=(B,\beta_Z(B))$ is a transitive bisection of $\M(A,\theta)$, $\F_1$ a transitive factorization of $\M(B,\theta_B)$ and $\F_2$ a transitive factorization of $\M(\beta_Z(B),\theta_{\beta_Z(B)})$. Using lemmas \ref{LLL1}, \ref{LLL3} and \ref{LLL4} we define a factorization \[\F''=\left\{\begin{array}{ll} \F'&\mbox{If } B\preceq\F'\\ (Y'_{n'}, \dots ,Y'_{i+1},T,\beta_Z(T),Y'_{i-1}, \dots ,1)&\mbox{Otherwise} \end{array} \right.\] such that $\F',\B\preceq\F''\preceq\GG$, $\F''|_{\M(Y'_j,\theta_{Y'_j})}$ is transitive for each $j\in [1,n]$ (in fact this factorization is trivial for all $j\in[1,n]$ but at least one where it is a transitive bisection), $\F''|_{\M(B,\theta_B)}$ and $\F''|_{\M(\beta_Z(B),\theta_{\beta_Z(B)})}$ are transitive. Using the induction hypothesis we can construct two factorizations $\F''_1$ and $\F''_2$ such that \[\F_1,\F''|_{\M(B,\theta_B)}\preceq\F''_2\preceq\GG|_{\M(B,\theta_B)}\] and \[\F_2,\F''|_{\M(\beta_Z(B),\theta_{\beta_Z(B)})}\preceq\F''_2\preceq\GG|_{\ M(\beta_Z(B),\theta_{\beta_Z(B)})}\] and satisfying (ii) and (iii). We set $\GG'=\F''_1\circ\F''_2\circ\B$, then $\F,\F'\preceq\GG'\preceq\GG$ and the induction hypothesis, the construction of $\F''$ and lemma \ref{LLL4} allow us to conclude. \CQFD \begin{corollary}\label{CCC1} Let $\F=(Y_i)_{i\in I}\preceq\F'$ be two transitive finite factorizations then for each $i\in I,\F'|_{\M(Y_i,I_{Y_i})}$ is a transitive finite factorization. \end{corollary} {\bf Proof } It suffices to use proposition \ref{PPP2} with $\F,\F'\preceq\F'$.\CQFD The following definition is an adaptation to partial commutations of a definition given by Viennot in \cite{Vi1}. \begin{definition}\label{D1} A factorization $(Y_i)_{i\in I}$ of $\M(A,\theta)$ has {\rm locally the property $\goth P$} if and only if for each finite subalphabet $B\subset A$ and $n\geq 0$ it exists a factorization $(Y'_i)_{i\in I'}$ with the property $\goth P$ such that there is an strictly increasing mapping $\phi: I'\rightarrow I$ satisfying \begin{center} $\displaystyle Y'_i\cap B^{\leq n}= Y_{\phi(i)}\cap B^{\leq n}$ and $ Y_j\cap B^{\leq n}=\emptyset$ if $j\not\in \phi(I')$ \end{center} \end{definition} \begin{definition} We denote $CLTF(A,\theta)$ the set of the complete locally transitive finite factorizations. \end{definition} \begin{example} Consider the following independance graph \[a-b-c-d.\] We construct a complete locally transitive finite factorization as follow. We eliminate successively the traces $c, ac^2, b, d, ac$ and $a$. So we have \[M(A,\theta)=c^*.(ac^2)^*.b^*.d^*.(ac)^*.a^*.M\] where $M$ is a (non-commutative) free monoid. It suffices to take a Lazard factorization on $M$ to construct a complete locally transitive finite factorization of $\M(A,\theta)$. Furthermore, one can prove that we can not obtain this factorization using only transitive bisections with a non commutative right member. \end{example} \subsection{Transitive elimination in $L_K(A,\theta)$} The following theorem proves that elimination in $L_K(A,\theta)$ and transitive factorization of $\M(A,\theta)$ occur under the same condition. \begin{theorem}\label{LieTh1} Let $(B,Z)$ be a partition of $A$ \begin{quote} (i) We have the decomposition \[L_K(A,\theta)=L_K(B,\theta_B)\oplus J\] where $J$ is a Lie ideal with generating set \[\tau_Z(B)=\{[ \dots [z,b_1], \dots b_n]\quad|\quad zb_1 \dots b_n\in \beta_Z(B)\}. \] (ii) The subalgebra $J$ is a free partially commutative Lie algebra if $B$ is a TFSA of $A$.\\ (iii) Conversely if $\tau_Z(B)$ is a basic family of $J$ then $B$ is TFSA. \end{quote} \end{theorem} {\bf Proof} $(i)$ We have the classical Lazard bisection \[L_K(A)=L_K(B)\oplus L_K(T_Z(B))\] where $T_Z(B)=\{[ \dots [z,b_1], \dots ],b-n]\quad |\quad z\in Z, b_1, \dots ,b_n\in B\}$. Then using the natural mapping $L_K(A)\rightarrow L_K(A,\theta)$ (as $[ \dots [z,b_1], \dots ],b_n]$ maps to $0$ if $zb_1 \dots b_n\not\in\beta_Z(B)$) we get the claim.\\ $(ii)$ The proof goes as in \cite{DK2}, we sketch it here. We define a mapping $\partial_b$ from $\beta_Z(B)$ to $L_K(\beta_Z(B),\theta_{\beta_Z(B)})$ by \[\partial_b=\left\{ \begin{array}{ll} zwb&\mbox{if } zwb\in \beta_Z(B),\\ 0&\mbox{otherwise}. \end{array}\right. \] a) We prove that if $B$ is TFSA, $\partial_b$ can be extended as a derivation of the Lie algebra $L_K(\beta_Z(B),\theta_{\beta_Z(B)})$.\\ b) We define $\partial$ a mapping from $B$ to $Der(L_K(\beta_Z(B),\theta_{\beta_Z(B)}))$ by $\partial(b)=\partial_b$ and we prove that it exists a Lie morphism from $L_K(B,\theta_B)$ into $Der(L_K(\beta_Z(B),\theta_{\beta_Z(B)}))$ which extends $\partial$.\\ c) We prove that the semi-direct product $L_K(B,\theta_B)\propto_\partial L_K(\beta_Z(B),\theta_{\beta_Z(B)})$ and the Lie algebra $L_K(A,\theta)$ are isomorphic. Hence, $J$ is a free partially commutative Lie algebra isomorphic to $L_K(\beta_Z(B),\theta_{\beta_Z(B)})$.\\ (iii) If the dependence graph admits the following subgraph \[z-b_1- \dots -b_n-z'\] with $b_i\in B$ and $z,z'\in Z$ we have the identity \[[z,[[ \dots [z',b_n] \dots ,b_2],b_1]]=[ \dots [z',b_n] \dots b_2],[z,b_1]].\] This implies that $\tau_Z(B)$ is not a basic family of $J$.\CQFD \subsection{Construction of bases of $L_K(A,\theta)$} In this section, we define a class of bases which contains the bases found by Duchamp and Krob in \cite{DK1}, \cite{DK2} and \cite{DR} using chromatic partitions and the partially commutative Lyndon bases found by Lalonde (see Lalonde \cite{La}, Krob and Lalonde \cite{KL}).\\ \begin{definition} Let $\F=(Y_i)_{i\in[1,n+1]}$ be a finite transitive factorization. We denote $\widetilde \F$, the set of the n-uplets $(\B_1, \dots ,\B_n)$ of transitive bisections such that $\F=\B_n\circ \dots \circ\B_1$.\\ Let $\F$ be a transitive factorization and ${\goth f}=(\B_1, \dots ,\B_n)\in\widetilde\F$, we denote ${\goth f}\B_n^{- 1}=(\B_1, \dots ,\B_{n-1})$. \end{definition} \begin{definition} Let $\F=(Y_i)_{i\in[1,n+1]}$ be a finite transitive factorization. A bracketing of $\F$ along ${\goth f}\in\widetilde\F$ is a mapping $\Pi_{\goth f}$ from $\bigcup_{i\in[1,n+1]}Y_i$ to $L_K(A,\theta)$ inductively defined as follows. If $n=1$, then $\goth f$ is a sequence of length 1 under the form $((B,\beta_Z(B)))$ and \[\Pi_{\goth f}(w)=\left\{\begin{array}{l} w \mbox{ if } w\in B,\\ {[ \dots [z,b_1] \dots b_k]} \mbox{ if } w=zb_1 \dots b_k \in \beta_Z(B)\mbox{ and } z\in Z. \end{array}\right. \] If $n>1$, let ${\goth f}=(\B_1, \dots ,\B_n)\in\widetilde\F$. We set $\B_{n-1}\circ \dots \circ \B_1=(Y'_i)_{i\in[1,n]}$ and $j\in[1,n]$ such that $\B_n=(Y''_j,\beta_{Y'_j-Y''_j}(Y''_j))$. And \[\Pi_{\goth f}(w)=\left\{\begin{array}{ll} \Pi_{{\goth f}\B_n^{-1}}(w) \mbox{ if } w\in \displaystyle\bigcup_{i\in[1,n]-j}Y'_i,&\\ {[ \dots [\Pi_{{\goth f}\B_n^{-1}}(y_1),\Pi_{{\goth f}\B_n^{-1}} (v_1)], \dots \Pi_{{\goth f}\B_n^{-1}}(v_k)]}& \mbox{if } w=y_1v_1 \dots v_k,\\ &w \in \beta_{X_j}(Y''_j),\\ & y_1\in X_j\\ &\mbox{and } v_1 \dots v_k\in Y''_j. \end{array}\right. \] \end{definition} Using theorem \ref{LieTh1} in an induction on $n$ we prove the following proposition. \begin{proposition}\label{LieP1} Let $\F=(Y_i)_{i\in[1,n]}$ be a transitive factorization. For each ${\goth f}\in\widetilde\F$, we have the following decomposition \[L_K(A,\theta)=\displaystyle\bigoplus_{i\in[1,n-1]}L_K(\Pi_{\goth f}(Y_i),\theta_i)\] where \[\theta_i=\{(\Pi_{\goth f}(y_1),\Pi_{\goth f}(y_2))|(y_1,y_2)\in \theta_\M\}. \] \end{proposition} \begin{definition} Let $\F=(Y_i)_{i\in J}$ be a locally transitive finite factorization, a {\it bracketing} of $\F$ is a mapping $\Pi$ from $\bigcup_{i\in J}Y_i$ to $L_K(A,\theta)$ such that for each finite subalphabet $B\subset A$ and each integer $n\geq 0$, it exists a transitive finite factorization $\F_{n,B}=(Y_i^{n,B})_{i\in J_{n,B}}$ and ${\goth f}_{n,B}\in\widetilde\F_{n,B}$ such that for each $t\in\bigcup_{i\in J_{n,B}}Y_i^{n,B}\cap B^{\leq n}$, $\Pi(t)=\Pi_{{\goth f}_{n,B}}(t)$. \end{definition} \begin{lemma}\label{LF3} Let $\F=(Y_i)_{i\in J}\preceq \F'$ be two finite transitive factorizations. Then, for each ${\goth f}\in \widetilde\F$, it exists ${\goth f'}\in\widetilde\F'$ such that for each $t\in \bigcup_{i\in J}Y_i$, $\Pi_{\goth f}(t)=\Pi_{\goth f'}(t)$. \end{lemma} {\bf Proof } It is a direct consequence of corollary \ref{CCC1}. \CQFD \begin{theorem} Let $(A,\theta)$ be an independence alphabet. Each locally finite transitive factorization of $\M(A,\theta)$ admits a bracketing. \end{theorem} {\bf Proof } Omitted.\CQFD \\ We have easily the following result. \begin{proposition} Let $\F=(\{l_i\})_{i\in I}\in CLTF(A,\theta)$ and $\Pi$ be a bracketing of $\F$ then the family $(\Pi(l_i))_{i\in I}$ is a basis of $L_K(A,\theta)$ as K-module. \end{proposition} \begin{example} We set $A=\{a,b,c,d\}$ and $\theta=a-b-c-d$. We construct locally (for $n\leq 3$) the following basis. \end{example} [[a,d],b], [[a,d],d], [[a,d],a], [a,d], [a,[a,c]], a, [a,c], [[a,c],c], [[a,d],c], [b,d], [[b,d[,b[, [[b,d],d], b, c, d. \section{The case of the group} The following result extends the classical partially commutative Lazard's elimination (\cite{DK2}) in the free partially commutative group to the elimination with partially commutative complement. \begin{proposition} If $B$ is TFSA, it exists a morphism $\sigma$ of group from $\F(B,\theta_B)$ into $Aut(\F(\beta_Z(B),\theta_{\beta_Z(B)}))$ such that $\F(A,\theta)$ and $\F(B,\theta_B)\propto_\sigma \F(\beta_Z(B),\theta_{\beta_Z(B)})$ are naturally isomorphic. \end{proposition} {\bf Proof } The proof goes as in theorem \ref{LieTh1} replacing derivations by automorphisms.\CQFD \begin{thebibliography}{ABC} % \bibitem{BP} J. Berstel and D. Perrin, {\em Theory of codes\/} (Academic Press, New-York, 1985). % \bibitem{Bo1} N.Bourbaki, {\em \'El\'ements de math\'ematiques, Groupes et alg\`ebres de Lie, Chap. 1\/} (Hermann, Paris, 1972). % % \bibitem{Bo} N.Bourbaki, {\em \'El\'ements de math\'ematiques, Groupes et alg\`ebres de Lie, Chap. 2 et 3\/} (Hermann, Paris, 1972). % \bibitem{CH} C.Choffrut, {\em Free partially commutative monoids\/} (Technical Report 86, LITP, Universit\'e Paris 7, 1986). % \bibitem{DR} V. Diekert and G. Rozenberg, {\em The book of traces\/} (World Scientific, Singapour, 1995). % \bibitem{Du} C.Duboc, {\em Commutations dans les mono\"{\i}des libres : un cadre th\'eorique pour l'\'etude du parall\'elisme\/} (Th\`ese, Universit\'e de Rouen, 1986). % \bibitem{Dub} P.Dubreuil,{\em Contribution \`a la th\'eorie des demi-groupes, \/} Mem.Acad.Sc.Inst, France, 63 1941. % \bibitem{DK1} G.Duchamp, D.Krob, {\em The free partially commutative Lie algebra: bases and ranks\/} , Advances in Mathematics, {\bf 95}-1 (1992) 92-126. % \bibitem{DK2} G.Duchamp and D.Krob, {\em Free partially commutative structures\/} {\em J. Algebra\/} {\bf 156}{-2} (1993) 318--361. % \bibitem{KL} D. Krob and P.Lalonde, {\em Partially commutative Lyndon words\/} {\em Lect. Notes in Comput. Sci.\/} {\bf 665} (1993) 237--246. % \bibitem{La} P.Lalonde, {\em Contribution \`a l'\'etude des empilements} (Th\`ese de doctorat, LACIM, 1991). % \bibitem{Laz} M.Lazard, {\em Groupes, anneaux de Lie et probl\`eme de Burnside}, Istituto Matematico dell' Universit\`a di Roma,1960. % \bibitem{Lo} M.Lothaire, {\em Combinatorics on words\/}, Addison Wesley, 1983. % \bibitem{Re} C. Reutenauer, {\em Free Lie algebras\/} (Oxford University Press, New-York, 1993). % \bibitem{SC1} M.P. Sch\"utzenberger, {\em On a factorization of free monoids\/}, {\em Proc. Amer. Math. Soc.\/} {\bf 16} (1965) 21-24. % \bibitem{Sc} M.P. Sch\"utzenberger, {\em Sur une propri\'et\'e combinatoire des alg\`ebres de Lie libre pouvant \^etre utilis\'ee dans un probl\`eme de Math\'ematiques appliqu\'ees}, seminaire Dubreuil-Pisot Ann\'ee 1958-1959, Paris, 1958. % \bibitem{Shi} A.I. Shirshov, {\em Bases of free Lie algebra}, Algebra i Logika ,{\bf 1}(1962), 14-9. % \bibitem{Vi1} G. Viennot, {\em Alg\`ebres de Lie libres et Mono\"\i des Libres} Th\`ese d'\'Etat, Paris 7,1974. % \bibitem{Vi2} G. Viennot, {\em Alg\`ebres de Lie libres et Mono\"\i des Libres} {\em Lecture Notes in Mathematics}, {\bf 691} (1978). \end{thebibliography} \end{document}