\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<j$ if
and only if
\begin{quote}
(i)  ($i,j\in I$ and $i<_I j$) or ($i,j\in I'$ and  $i<_{I'}j$))\\
(ii)  $i\in I$, $i<_Ik$ and $j\in I'$  \\
(iii)  $i\in I'$, $j>_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}



