\input amstex
\input amsppt.sty

\hsize13cm
\vsize19cm
\newdimen\fullhsize
\newdimen\fullvsize
\newdimen\halfsize
\fullhsize13cm
\fullvsize19cm
\halfsize=0.5\fullhsize
\advance\halfsize by-0.5em
\magnification1200


\NoBlackBoxes

\font\Bf=cmbx12
\font\Rm=cmr12
\def\Dbar{\hbox{--\kern-3.5ptD}}
\def\LL{\leavevmode\setbox0=\hbox{L}\hbox to\wd0{\hss\char'40L}}
\def\al{\alpha}
\def\be{\beta}
\def\ga{\gamma}
\def\de{\delta}
\def\ep{\varepsilon}
\def\ze{\zeta}
\def\et{\eta}
\def\th{\theta}
\def\vt{\vartheta}
\def\io{\iota}
\def\ka{\kappa}
\def\la{\lambda}
\def\rh{\rho}
\def\si{\sigma}
\def\ta{\tau}
\def\ph{\varphi}
\def\ch{\chi}
\def\ps{\psi}
\def\om{\omega}
\def\Ga{\Gamma}
\def\De{\Delta}
\def\Th{\Theta}
\def\La{\Lambda}
\def\Si{\Sigma}
\def\Ph{\Phi}
\def\Ps{\Psi}
\def\Om{\Omega}
\def\row#1#2#3{#1_{#2},\ldots,#1_{#3}}
\def\rowup#1#2#3{#1^{#2},\ldots,#1^{#3}}
\def\x{\times}
\def\crf{}            %used for crossreferencing, Tex should ignore.
\def\rf{}             %used for refencing (section-numbers)
\def\rfnew{}          %used for new-section numbers
\def\P{{\Bbb P}}
\def\R{{\Bbb R}}
\def\X{{\Cal X}}
\def\C{{\Bbb C}}
\def\Mf{{\Cal Mf}}
\def\FM{{\Cal F\Cal M}}
\def\F{{\Cal F}}
\def\G{{\Cal G}}
\def\V{{\Cal V}}
\def\T{{\Cal T}}
\def\A{{\Cal A}}
\def\N{{\Bbb N}}
\def\Z{{\Bbb Z}}
\def\Q{{\Bbb Q}}
\def\ddt{\left.\tfrac \partial{\partial t}\right\vert_0}
\def\dd#1{\tfrac \partial{\partial #1}}
\def\today{\ifcase\month\or
 January\or February\or March\or April\or May\or June\or
 July\or August\or September\or October\or November\or December\fi
 \space\number\day, \number\year}
\def\nmb#1#2{#2} %zum Nummerieren
\def\iprod#1#2{\langle#1,#2\rangle}
\def\pder#1#2{\frac{\partial #1}{\partial #2}}
\def\iint{\int\!\!\int}
\def\({\left(}
\def\){\right)}
\def\[{\left[}
\def\]{\right]}
\def\supp{\operatorname{supp}}
\def\Df{\operatorname{Df}}
\def\dom{\operatorname{dom}}
\def\Ker{\operatorname{Ker}}
\def\Tr{\operatorname{Tr}}
\def\Res{\operatorname{Res}}
\def\Aut{\operatorname{Aut}}
\def\kgV{\operatorname{kgV}}
\def\ggT{\operatorname{ggT}}
\def\diam{\operatorname{diam}}
\def\Im{\operatorname{Im}}
\def\Re{\operatorname{Re}}
\def\ord{\operatorname{ord}}
\def\rang{\operatorname{rang}}
\def\rng{\operatorname{rng}}
\def\grd{\operatorname{grd}}
\def\inv{\operatorname{inv}}
\def\maj{\operatorname{maj}}
\def\des{\operatorname{des}}
\def\varmaj{\operatorname{\overline{maj}}}
\def\vardes{\operatorname{\overline{des}}}
\def\pvarmaj{\operatorname{\overline{maj}'}}
\def\pmaj{\operatorname{maj'}}
\def\ln{\operatorname{ln}}
\def\der{\operatorname{der}}
\def\Hom{\operatorname{Hom}}
\def\tr{\operatorname{tr}}
\def\Span{\operatorname{Span}}
\def\grad{\operatorname{grad}}
\def\div{\operatorname{div}}
\def\rot{\operatorname{rot}}
\def\Sp{\operatorname{Sp}}
\def\sgn{\operatorname{sgn}}
\def\liml{\lim\limits}
\def\supl{\sup\limits}
\def\bigcupl{\bigcup\limits}
\def\bigcapl{\bigcap\limits}
\def\limsupl{\limsup\limits}
\def\liminfl{\liminf\limits}
\def\intl{\int\limits}
\def\suml{\sum\limits}
\def\maxl{\max\limits}
\def\minl{\min\limits}
\def\prodl{\prod\limits}
\def\tg{\operatorname{tan}}
\def\ctg{\operatorname{cot}}
\def\arctg{\operatorname{arctan}}
\def\arccot{\operatorname{arccot}}
\def\arcctg{\operatorname{arccot}}
\def\tgh{\operatorname{tanh}}
\def\ctgh{\operatorname{coth}}
\def\arcsinh{\operatorname{arcsinh}}
\def\arccosh{\operatorname{arccosh}}
\def\arctgh{\operatorname{arctanh}}
\def\arcctgh{\operatorname{arccoth}}
\def\3{\ss}
\catcode`\@=11
\def\dddot#1{\vbox{\ialign{##\crcr
      .\hskip-.5pt.\hskip-.5pt.\crcr\noalign{\kern1.5\p@\nointerlineskip}
      $\hfil\displaystyle{#1}\hfil$\crcr}}}

\newif\iftab@\tab@false
\newif\ifvtab@\vtab@false
\def\tab{\bgroup\tab@true\vtab@false\vst@bfalse\Strich@false%
   \def\\{\global\hline@@false%
     \ifhline@\global\hline@false\global\hline@@true\fi\cr}
   \edef\l@{\the\leftskip}\ialign\bgroup\hskip\l@##\hfil&&##\hfil\cr}
\def\endtab{\cr\egroup\egroup}
\def\vtab{\vtop\bgroup\vst@bfalse\vtab@true\tab@true\Strich@false%
   \bgroup\def\\{\cr}\ialign\bgroup&##\hfil\cr}
\def\endvtab{\cr\egroup\egroup\egroup}
\def\stab{\D@cke0.5pt\null 
 \bgroup\tab@true\vtab@false\vst@bfalse\Strich@true\Let@@\vspace@
 \normalbaselines\offinterlineskip
  \openup\spreadmlines@
 \edef\l@{\the\leftskip}\ialign
 \bgroup\hskip\l@##\hfil&&##\hfil\crcr}
\def\endstab{\crcr\egroup
 \egroup}
\newif\ifvst@b\vst@bfalse
\def\vstab{\D@cke0.5pt\null
 \vtop\bgroup\tab@true\vtab@false\vst@btrue\Strich@true\bgroup\Let@@\vspace@
 \normalbaselines\offinterlineskip
  \openup\spreadmlines@\bgroup}
\def\endvstab{\crcr\egroup\egroup
 \egroup\tab@false\Strich@false}

\newdimen\htstrut@
\htstrut@8.5\p@
\newdimen\htStrut@
\htStrut@12\p@
\newdimen\dpstrut@
\dpstrut@3.5\p@
\newdimen\dpStrut@
\dpStrut@3.5\p@
\def\openup{\afterassignment\@penup\dimen@=}
\def\@penup{\advance\lineskip\dimen@
  \advance\baselineskip\dimen@
  \advance\lineskiplimit\dimen@
  \divide\dimen@ by2
  \advance\htstrut@\dimen@
  \advance\htStrut@\dimen@
  \advance\dpstrut@\dimen@
  \advance\dpStrut@\dimen@}
\def\Let@@{\relax\iffalse{\fi%
    \def\\{\global\hline@@false%
     \ifhline@\global\hline@false\global\hline@@true\fi\cr}%
    \iffalse}\fi}
\def\matrix{\null\,\vcenter\bgroup
 \tab@false\vtab@false\vst@bfalse\Strich@false\Let@@\vspace@
 \normalbaselines\openup\spreadmlines@\ialign
 \bgroup\hfil$\m@th##$\hfil&&\quad\hfil$\m@th##$\hfil\crcr
 \Mathstrut@\crcr\noalign{\kern-\baselineskip}}
\def\endmatrix{\crcr\Mathstrut@\crcr\noalign{\kern-\baselineskip}\egroup
 \egroup\,}
\def\smatrix{\D@cke0.5pt\null\,
 \vcenter\bgroup\tab@false\vtab@false\vst@bfalse\Strich@true\Let@@\vspace@
 \normalbaselines\offinterlineskip
  \openup\spreadmlines@\ialign
 \bgroup\hfil$\m@th##$\hfil&&\quad\hfil$\m@th##$\hfil\crcr}
\def\endsmatrix{\crcr\egroup
 \egroup\,\Strich@false}
\newdimen\D@cke
\def\Dicke#1{\global\D@cke#1}
\newtoks\tabs@\tabs@{&}
\newif\ifStrich@\Strich@false
\newif\iff@rst

\def\Stricherr@{\iftab@\ifvtab@\errmessage{\noexpand\s not allowed
     here. Use \noexpand\vstab!}%
  \else\errmessage{\noexpand\s not allowed here. Use \noexpand\stab!}%
  \fi\else\errmessage{\noexpand\s not allowed
     here. Use \noexpand\smatrix!}\fi}
\def\format{\ifvst@b\else\crcr\fi\egroup\iffalse{\fi\ifnum`}=0 \fi\format@}
\def\format@#1\\{\def\preamble@{#1}%
 \def\Str@chfehlt##1{\ifx##1\s\Stricherr@\fi\ifx##1\\\let\Next\relax%
   \else\let\Next\Str@chfehlt\fi\Next}%
 \def\c{\hfil\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi\iftab@\else$\m@th\fi\the\hashtoks@\iftab@\else$\fi\hfil}%
 \def\r{\hfil\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi\iftab@\else$\m@th\fi\the\hashtoks@\iftab@\else$\fi}%
 \def\l{\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi\iftab@\else$\m@th\fi\the\hashtoks@\iftab@\else$\fi\hfil}%
 \def\s{\ifStrich@\ \the\tabs@\vrule width\D@cke\the\hashtoks@%
          \fi\the\tabs@\ }%
 \def\sa{\ifStrich@\vrule width\D@cke\the\hashtoks@%
            \the\tabs@\ %
            \fi}%
 \def\se{\ifStrich@\ \the\tabs@\vrule width\D@cke\the\hashtoks@\fi}%
 \def\cd{\hfil\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi$\dsize\m@th\the\hashtoks@$\hfil}%
 \def\rd{\hfil\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi$\dsize\m@th\the\hashtoks@$}%
 \def\ld{\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi$\dsize\m@th\the\hashtoks@$\hfil}%
 \ifStrich@\else\Str@chfehlt#1\\\fi%
 \setbox\z@\hbox{\xdef\Preamble@{\preamble@}}\ifnum`{=0 \fi\iffalse}\fi
 \ialign\bgroup\span\Preamble@\crcr}
\newif\ifhline@\hline@false
\newif\ifhline@@\hline@@false
\def\hlinefor#1{\multispan@{\strip@#1 }\leaders\hrule height\D@cke\hfill%
    \global\hline@true\ignorespaces}
\def\Item "#1"{\par\noindent\hangindent2\parindent%
  \hangafter1\setbox0\hbox{\rm#1\enspace}\ifdim\wd0>2\parindent%
  \box0\else\hbox to 2\parindent{\rm#1\hfil}\fi\ignorespaces}
\def\ITEM #1"#2"{\par\noindent\hangafter1\hangindent#1%
  \setbox0\hbox{\rm#2\enspace}\ifdim\wd0>#1%
  \box0\else\hbox to 0pt{\rm#2\hss}\hskip#1\fi\ignorespaces}
\def\item"#1"{\par\noindent\hang%
  \setbox0=\hbox{\rm#1\enspace}\ifdim\wd0>\the\parindent%
  \box0\else\hbox to \parindent{\rm#1\hfil}\enspace\fi\ignorespaces}
\let\plainitem@\item
\catcode`\@=13


\def\rightheadtext{} 
\def\leftheadtext{}


\font\bbf=cmbx10 scaled\magstep1


\head{\bbf ELIMINATION DE GENERATEURS\\\vskip-5pt
 DANS LES STRUCTURES\\\vskip-5pt
 PARTIELLEMENT COMMUTATIVES} \endhead
\vskip 0.3 cm 
\centerline{\it par}
\vskip 0.5 cm 
\centerline{\smc G\'erard Duchamp}
\vskip 1 cm
\centerline{\it LITP/LIR, Institut Blaise Pascal}
\centerline{\it Universit\'e Paris 7}
\centerline{\it 2, place Jussieu, 75251 Paris Cedex 05}
\vskip 1,5cm

{\bf Introduction}
\vskip0,2cm

Les proc\'ed\'es d'\'elimination se retrouvent en alg\`ebre dans de
nombreuses structures diff\'erentes. Eliminer un g\'en\'erateur $x_n$
c'est typiquement \'ecrire, pour une structure $STRUCT$ (selon une
formulation \`a la {\smc Zeilberger} \cite {Z})~:
$$STRUCT \langle x_1, x_2, \dots, x_n \rangle \cong NICE  \langle x_1,
x_2, \dots, x_n \rangle \diamond STRUCT_1  \langle x_1, x_2, \dots,
x_{n-1} \rangle ,$$
o\`u $NICE$ et $STRUCT_1$ d\'esignent des structures alg\'ebriques
engendr\'ees par les g\'en\'erateurs $x_1$. Le losange, selon les cas,
est un produit tensoriel, un produit semi-direct ou une simple
factorisation. On peut ainsi \'ecrire pour le groupe sym\'etrique
$\frak S_n$ et le groupe des tresses pures $P_n$ \cite {Bi}~:
$$\frak S_n \cong \Z / n \Z \diamond \frak S_{n-1} \quad  \text
{et} \quad P_n \cong F_{n-1} \diamond P_{n-1}.$$
Dans la premi\`ere de ces factorisations le losange est un simple
produit et la d\'e\-com\-po\-si\-tion it\'er\'ee peut servir \`a montrer que
le groupe sym\'etrique est un groupe de Coxeter ou bien \`a donner une
base du groupe sym\'etrique particuli\`erement bien adapt\'ee au
d\'eveloppement du projecteur de {\smc Dynkin} \cite {D1}, dans la seconde
c'est un produit semi-direct et $F_{n-1}$ est le groupe libre sur
$n-1$ g\'en\'erateurs. 

Les structures libres se pr\hataccent etent bien \`a l'\'elimination
de g\'en\'erateurs. Par exemple, la formule $k [X_1, X_2, \dots, X_n]
\cong k [X_1] \otimes_k k [X_2, \dots, X_n]$ qui est si utile en
alg\`ebre commutative, provient de l'\'elimination de $X_1$ dans le
mono\"\i de libre commutatif $\N ^{\{X_1, X_2, \dots, X_n\}}$. De
m\hataccent eme, lorsqu'on partage un alphabet donn\'e $A$ en $A = B +
Z$ on peut \'ecrire, por le mono\"\i de libre, le groupe libre et
l'alg\`ebre de Lie libre~:
$$A ^\ast = (B ^\ast Z) ^\ast B ^\ast, \quad F(A) \cong F(F(B)Z)
\diamond F(B) ,\quad L(A) \cong L((B ^\ast Z)) \diamond L(B).$$
Les deux derniers losanges sont des produits semi-directs et
constituent l'\'elimination de {\smc M.~Lazard} \cite {Laz} \`a proprement
parler. Ces d\'ecompositions sont \'etendues au cas partiellement
commutatif et nous devons maintenant en dire quelques mots.
\vskip0,2cm

Les structures partiellement commutatives sont interm\'ediaires entre
les structures commutatives et non commutatives libres. On a, par
exemple, pour un alphabet donn\'e $A$, le tableau~:
\vskip0,2cm

$$\matrix\\
& &  \text{commutatif} & & & \text{noncommutatif} \\
& \\
\text{mono\"\i de} & & \Bbb N ^{A} & & & A ^\ast \\
\text{groupe} & & \Bbb Z ^{A} & & & F(A) \\
\text{$k$-alg. de Lie} & &   k ^{A} & & & L_k(A) \\
\text{$k$-alg. assoc.} & &  k[A] & & & k \langle A \rangle \\
\text{(polyn\^omes)}\endmatrix$$
\vskip0,2cm

La premi\`ere structure partiellement commutative pr\'esent\'ee telle
est certainement le mono\"\i de de r\'earrangements que {\smc P.~Cartier} 
et {\smc D.~Foata} 
ont d\'efini en 1969 \`a des fins combinatoires, statistiques et
probabilistes \cite{CF}.

Depuis, l'histoire de ces structures est \`a lire parall\`element sur
les trois pistes que sont l'alg\`ebre, la combinatoire (alg\'ebrique
et \'enum\'erative) et la th\'eorie des langages.

Pour ce qui est de la combinatoire, signalons que le mono\"\i de
partiellement commutatif libre a re\c cu une repr\'esentation
g\'eom\'etrique suggestive en terms d'empilements \cite {Vi} qui se
pr\hataccent ete bien \`a l'adjonction de structures suppl\'ementaires
sur l'alphabet des ind\'etermin\'ees. Cette repr\'esentation,
essentiellement \'equivalente \`a la notion de mono\"\i de partiellement
commutatif (\cite {Vi, prop~4.5}), a d\'ej\`a fait ses preuves dans la
r\'esolution de plusieurs probl\`emes combinatoires tels que les
hexagones durs de {\smc Baxter}, les polyn\hataccent omes orthogonaux et
l'\'enum\'eration des tresses simples.

En th\'eorie des langages, le mono\"\i de partiellement commutatif a
\'et\'e essentiellement employ\'e comme mod\`ele du parall\'ellisme.
En effet, de m\hataccent eme qu'une suite d'actions $a_1, a_2,
\dots,a_n$ peut se repr\'esenter par le mot $w = a_1 a_2 \cdots a_n$
et la juxtaposition (dans le temps) de deux telles suites, par leur
concat\'enation dans le mono\"\i de libre, de m\hataccent eme des actions
dont certaines se traitent ``en parall\'ele" ou ``ind\'ependamment"
peuvent \hataccent etre repr\'esent\'ees par des \'el\'ements du
mono\"\i de partiellement commutatif (ou ``traces") et leur composition.
Cette th\'eorie des langages, toute jeune, s'interesse donc \`a ce qui
est parfois appell\'e ``langage trace". On peut citer les travaux
fondateurs de {\smc Arnold, Cori, Mazurkiewicz, Perrin, M\'etivier, Olchanski}
et {\smc Zielonka} \cite {Du}\cite{CP}\cite {HK}.

Dans une note \`a T.C.S., {\smc Jean-Yves Thibon} \cite{T} montre que 
l'alg\`ebre des po\-ly\-n\hataccent omes partiellement commutatifs (c'est
\graveaccent a dire l'alg\`ebre du mono\"\i de partiellement
commutatif) est int\`egre d\`es que l'anneau des coefficients 
l'est. Ce fait est reli\'e \graveaccent a la propri\'et\'e que
$k\langle A,\vt\rangle$ est l'alg\`ebre enveloppante de
$L_k(A,\vt)$; mais la libert\'e de $k\langle A,\vt\rangle$
(c'est \graveaccent a dire l'existence de bases) n'implique nullement
celle de $L_k(A,\vt)$ ni la construction de bases combinatoires de
celle-ci. La r\'esolution de cette question d'apparence purement
esth\'etique devait d'ailleurs (en 1990) avoir quelque utilit\'e en
th\'eorie des langages \cite{DK2} et \cite{Va}. En fait, c'est une
version partiellement commutative du proc\'ed\'e d'\'elemination de
{\smc M.~Lazard} qui perment une d\'emonstration constructive de l'existence da
bases \footnote{J'avais donn\'e quelque temps avant une preuve de
l'existence de bases \cite{D2}. Mais cette preuve a deux d\'efauts~:
d'abord elle n'est pas constructive et ensuite elle ne peut \hataccent
etre g\'en\'eralis\'ee telle quelle \graveaccent a d'autre
pr\'esentations, m\hataccent eme par des mots de Lie, car celles-ci
peuvent introduire de la torsion (cf\. Remarque~III.5).}.

Nous devons maintenant dire quelques mots du proc\'ed\'e
lui-m\hataccent eme dans le cas partiellement commutatif et, bien
qu'il soit apparu pour la premi\`ere fois (par la n\'ecessit\'e
combinatoire du probl\'eme) pour l'alg\`ebre de Lie il est plus
suggestif de le voir dans le mono\"\i de.

On se souvient de la factorisation $A^\ast=(B^\ast Z)^\ast B^\ast$ 
o\`u $A=B+Z)$ qui consiste \graveaccent a dire que, $Z$
\'etant un sous alphabet de $A$, tout mot de $A^\ast$ est ``rythm\'e"
par des lettres de $Z$ et donc doit s'\'ecrire de fa\c con unique~:
$w=w_1z_1w_2z_2\cdots w_nz_nw_{n+1}$ o\`u $w_i\in B^\ast$ et $z_i\in
Z$. On observe alors facilement que les \'el\'ements $w_iz_i$ forment
un code \cite{Lo}\cite{BP}. La factorisation de $M(A,\vt)$ par
\'elimination est l'analogue parfait de ce qui pr\'ec\graveaccent ede,
moyennant quelques pr\'ecautions techniques n\'ecessaires. D'ailleurs
l'\'elimination est toujours possible et fournit une m\'ethode de
descente dans les structures partiellement commutatives. \footnote{Pour
une mise en sc\`ene des m\'ethodes d'\'elimination partiellement
commutatives on pourra se reporter \graveaccent a leur expos\'e sous
forme d'une pi\'ece de th\'e\hataccent atre dans \cite{K}.} 

Ceci perment aussit\hataccent ot de montrer que le mono\"\i de
partiellement commutatif libre admet une factorisation en mono\"\i des
libres et donc une factorisation compl\`ete \cite{DK3}\cite{DK5}. Les
codes de ces mono\"\i des sont les analogues de $(BZ)^\ast$, ils sont
ap\'e\-rio\-diques \cite{D3}, et dans le cas d'un alphabet ordonn\'e,
l'\'elimination successive des lettres de poids croissant permet de
montrer que la forme normale lexicographique est une section
rationelle. Ces codes seront appell\'es ``codes $Z$". Par example pour
l'alphabet $A=\{a,b,c,d\}$, l'ordre $a<b<c<d$, et le graphe de
commutation $a$----$b$----$c$----$d$ on a~:
$$
A^\ast=((d^\ast b)^\ast(cc^\ast d^\ast+dd^\ast)a)^\ast(d^\ast b)^\ast
c^\ast d^\ast
$$
L'alg\`ebre de Lie (partiellement commutative) admet une
d\'ecomposition homog\`ene (pour l'\'evaluation) en somme directe
d'alg\`ebres de Lie libres dont les codes sont pr\'ecis\'ement les
codes $Z$, cette d\'e\-com\-po\-si\-tion permet alors de montrer la libert\'e
de $L(A,\vt)$ pour tous les anneaux de coefficients, de donner des
algorithmes de calcul des bases et est compatibles avec toutes les
bases multihomog\`enes, comme par exemple la base de Lyndon
partiellement commutative (cf\. \cite{La}).\footnote{La d\'ecomposition
de l'alg\`ebre de Lie correspondant \graveaccent a la suite centrale
descendante de $P_n$ \cite{Ca} en alg\`ebres de Lie libres est une
image de l'\'elimination partiellement commutative que nous
construisons en III.3.} Ces bases sont ``universelles" (c'est
\graveaccent a dire ind\'ependantes de l'anneau des coefficients) de
l'alg\`ebre de Lie partiellement commutative libre. Des cas
particuliers d'\'elimination et de calcul de {\smc Witt} \cite{DK1} avaient
d'ailleurs \'et\'e trait\'es quelque temps avant par {\smc \Dbar okovi\' c}
(cf\. \cite{Do1} et \cite{Do2}).
\vskip5pt

{\bf I. Pr\'eliminaires}
\vskip5pt

Au cours de ce texte, nous ferons appel \graveaccent a la notion de
{\it structure pr\'esent\'ee} pour les quatre cat\'egories suivantes~:
mono\"\i des ({\bf Mon}), groupes ({\bf Grp}), $k$-alg\`ebres de Lie
libres ($k$-{\bf Lie Alg}) et $k$-alg\`ebres associatives avec
\'el\'ement unit\'e ($k$-{\bf Alg}).

Soit $X$ un ensemble (un alphabet) et $X^\ast$ le mono\"\i de libre,
$F(X)$ le groupe libre, $L_k(X)$ l'alg\`ebre de Lie libre, $k\langle
X\rangle$ l'alg\`ebre libre c'est \graveaccent a dire les structures
librement engendr\'ees par $X$ dans les cat\'egories pr\'ec\'edentes.
Chacun de ces objects, de fa\c con \'evidente sera not\'e $Lib_j(X)$
o\`u $j\in \{${\bf Mon, Grp,} $k$-\hbox{\bf Lie Alg}, $k$-{\bf Alg}$\}$.
Appellons {\it relateur} une famille de couples {\bf R}$=(u_i,
v_i)_{i\in I}\in(Lib_j(X)\times Lib_j(X))^I$, on peut
alors se poser la question de la factorisation des morphismes qui
co\"\i ncident sur les \'el\'ements de {\bf R}. Plus
pr\'ecis\'ement~:
Existe-t-il un couple $(\alpha, \Cal A)$ avec $\Cal A\in \Cal O b(j)$
et $\alpha\in Mor_j(Lib_j(X),\Cal A)$ qui v\'erifie les conditions
suivantes~?

\medskip
SP1) $(\forall i\in I)(\alpha(u_i)=\alpha(v_i))$


SP2) Pour tout $\Phi\in Mor_j(Lib_j(X),Y)$ tel que $(\forall i\in
I)(\Phi(u_i)=\Phi(v_i))$ il existe $\bar\Phi\in Mor_j(\Cal A,Y)$ tel
que le diagramme suivant soit commutatif~:

\vskip10pt
\vbox{
$$
\CD 
Lib_j(X) @>\Phi>>Y\\
@V\alpha VV @.\\
\Cal A @.
\endCD
\kern-40pt\nearrow\raise-3pt\hbox{\kern-5pt$\ssize\bar\Phi$}
$$
\centerline{\eightpoint Figure 1}
}
\vskip10pt

La r\'eponse est positive dans chacune des cat\'egories
consid\'er\'ees, on a~: 

\proclaim{Proposition I.1} Pour chacune des cat\'egories $j\in
\{${\bf Mon, Grp}, $k$-{\bf Lie Alg}, $k$-{\bf Alg}$\}$ et relateur
{\bf R}, il existe un objet $\langle X;\text {\bf R}\rangle_j$, unique
\graveaccent a un isomorphisme pr\'es, qui r\'esout le probl\`eme
pr\'ec\'edent.
\endproclaim

\demo{\bf Preuve} Ces r\'esultats sont classiques.


Dans le cas des mono\"\i des on montre que $\langle X;\text {\bf
R}\rangle_{\text{\bf Mon}}=X^\ast/\equiv_{R}$ o\`u $\equiv_R$ est la congruence
la plus fine telle que $(\forall i\in I)(u_i\equiv v_i)$.

Pour les groupes c'est $F(X)/H_{\text {\bf R}}$ qui r\'esout la
question, o\`u $H_R$
est le sous-groupe distingu\'e (normal) engendr\'e par la famille
$(u_iv_i^{-1})_{i\in I}$.

Dans le cas des alg\`ebres (resp\. alg\`ebres de Lie) c'est $k\langle
X\rangle/\Cal J$ (resp\. $L_k(X)/\Cal J)$ o\`u $\Cal J$ est l'id\'eal
bilat\`ere (resp\. l'id\'eal de Lie) engendr\'e par les diff\'erences
$(u_i-v_i)_{i\in I}$ qui est solution du probl\'eme.\qed
\enddemo


\remark{\bf Remarques I.2} 1) Un morphisme qui v\'erifie la condition (SP2)
$((\forall i\in I)(\Phi(u_i)=\Phi(v_i)))$ est dit {\it compatible}
avec le relateur {\bf R} ou qu'il {\it respecte} les relations de {\bf
R}.

2) Soit $\phi$ une application $X\to M$ o\`u $M$ est un objet donn\'e
de la cat\'egorie $\Cal C_j$ et $\Phi$~: $Lib_j(X)\to M$son extension
\graveaccent a $Lib_j(X)$. Si $\Phi$ respecte les relateurs de {\bf R}
et que $\bar\Phi:\langle X;\text {\bf R}\rangle_j\to M$ est un
isomorphisme. On dira que $M$ admet la pr\'esentation
$\langle(\phi(x))_{x\in X};\text {\bf R}\rangle_j$.
\endremark


\pagebreak
{\bf II. Examples d'\'elimination}
\vskip5pt
{\bf 1. Mots et autres structures libres}

\vskip1pt
a) {\smc Mono\"\i de libre}

Soit $A$, un alphabet, $Z$, un sous-alphabet de A, et $B=A-Z$. Tout
$w\in A$, peut se factoriser de fa\c con unique~:
$$
w=w_1z_1w_2z_2\cdots w_nz_nw_{n+1}
$$
avec $w_i\in B^\ast$ et $z_i\in Z$. Ce qui revient \graveaccent a
\'ecrire~:
$$
A^\ast=(B^\ast Z)^\ast B^\ast.\tag II.1.1
$$

b) {\smc Groupe et alg\`ebre de Lie}

Pour le groupe libre sur A, on a un analogue de (II.1.1)~:
$$
F(A)\cong F(FB)Z\times F(B).
$$
Et pour l'alg\`ebre de Lie~:
$$
L(A)\cong L(B^\ast Z)\times L(B)
$$
Les deux \'eliminations pr\'ec\'edentes sont dues \graveaccent a {\smc
M.~Lazard} \cite{Laz}.
\vskip1pt
c) {\smc Groupe sym\'etrique}

Si $c$ d\'esigne n'importe quel cycle de longueur maximale dans le
groupe sym\'etrique $\frak S_n$ on a~:
$$
\frak S_n=\langle c\rangle\cdot\frak S_{n-1},
$$
o\`u $\langle c\rangle$ d\'esigne le sous-groupe (d'ordre $n$)
engendr\'e par $c$. Ce fait est partiquement \'evident mais nous le
mentionnons parce qu'il ne s'agit pas d'un produit semi-direct.
L'\'egalit\'e pr\'ec\'edente montre que, si on se donne des cycles
$(c_k)_{k\in\{2,\dots, n\}}$ chacun de longueur $k$ tel que
$supp(c_k)\subseteq supp(c_{k+1})$ (``supports emboit\'es") tout
\'el\'ement $\sigma\in\frak S_n$ s'\'ecrit de fa\c con unique~:
$$
\sigma=c_2^{\alpha_2}\cdots c_n^{\alpha_n}\ \text {avec}\ \alpha_i< i,
$$
ceci fournit une base de l'alg\`ebre $\Q[\frak S_n]$ bien adapt\'ee qu
d\'eveloppement de l'idem\-po\-tent de {\smc Dynkin} \cite{D1} qui est done\'e
par la formule~:
$$
nD(x_1x_2x_3\cdots x_n)=[\cdots[[x_1,x_2],x_3],\cdots x_n]
$$
\vskip5pt
{\bf 2. Tresses pures}

\vskip1pt

Le groupe des tresses \graveaccent a $n$ brins $B_n$ a \'et\'e introduit
par {\smc E.~Artin} \cite{Ar} en 1925 dans une construction
to\-po\-lo\-gique. En
fait, le groupe de tresses \graveaccent a $n$ brins, $B_n(M)$, d'une
vari\'et\'e connexe $M$ est tout simplement le groupe fondamental de
la vari\'et\'e des parties de $M$ \graveaccent a $n$ points distincts
(cf\. \cite{Ca}). Le groupe des tresses classiques est $B_n(\R^2)$. On
peut repr\'esenter graphiquement une tresse par un diagramme plan
form\'e de $n$ chemins r\'eguliers joignant $n$ points $A_1,\dots, A_n$ sur
une m\hataccent eme verticale \graveaccent a $n$ autres points
$B_1,\dots, B_n$ aussi align\'es verticalement et \graveaccent a droite
des $A_i$, les points $A_i$ et $B_i$ \'etant sur une m\hataccent eme
horizontale, pour chaque $i$. Les chemins se coupent transversalement
en des points distincts et, \graveaccent a chaque croisement on doit
indiquer le brin qui est ``au-dessus" et celui qui est ``en-dessous"
\cite{fig.~2}. Deux tresses se composent par juxtaposition et ``oublier"
des points interm\'ediaires \cite{fig.~3}. Deux tresses sont
\'equivalentes si l'on peut passer de l'une \graveaccent a l'autre par
des op\'erations qui reproduisent, par projection les isotopies de
l'espace \cite{fig.~4}. Les intuitions que l'on peut avoir sur ce genre
de diagramme sont en g\'en\'eral confirm\'ees par le calcul.%
\footnote{On en verra un exemple en avec l'\'elimination dans le
groupe des tresses pures [cf\. fig.~5].}

$B_n$ est engendr\'e par les tresses \'el\'ementaires $(t_i)_{1\leq
i\leq n-1}$ o\`u $t_i$ d\'esigne la tresse obtenue en joignant par des
segments de droite les points $A_j$ \graveaccent a $B_j$ pour
$j\not\in \{i,i+1\}$ ainsi que $A_i$ \graveaccent a $B_{i+1}$ et
$A_{i+1}$ \graveaccent a $B_i$ ce dernier brin passant sous le
pr\'ec\'edent \cite{fig.~2}. Ces g\'en\'erateurs v\'erifient le
syst\'eme $(\Sigma)$ suivant, qui constitue, comme l'a montr\'e
{\smc E.~Artin} une pr\'esentation de $B_n$ \cite{Ar}.
$$
\left\{\matrix\format \r&\l&\quad \l\\
t_it_j &= t_jt_i&\text {pour}\ |i-j|\geq 2,\\
t_it_{i+1}t_i&=t_{i+1}t_it_{i+1}& \text {pour}\ i\leq
n-2.\endmatrix\right. \tag$\Sigma_B$
$$
De m\hataccent eme on peut montrer que le groupe sym\'etrique $\frak
G_n$ adment la pr\'esentation
$$
\left\{\matrix\format \r&\l&\quad \l\\
\sigma_i\sigma_j&=\sigma_j\sigma_i&\text {pour}\ |i-j|\geq 2,\\
\sigma_i\sigma_{i+1}\sigma_i&= \sigma_{i+1}\sigma_i\sigma_{i+1}& \text
{pour}\ i\leq n-2,\\
\sigma_i^2&= 1& \text {pour tout}\ i,\endmatrix\right. 
\tag$\Sigma_\frak S$
$$
o\`u, pour $i\leq n-1, \sigma_i$ est la transposition $(i,i+1)$. Le
fait que la famille $(\sigma_i)$ v\'erifie $(\Sigma_B)$ entraine,
l'existence d'un morphisme $\phi:B_n\to\frak S_n$ tel que $(\forall
i\in I)(\phi(\sigma_i)=t_i)$. Ce morphisme a un sens g\'eom\'etrique
tr\`es simple~:

dans une tresse $\tau$, le chemin qui part du point $A_i^{(0)}$
aboutit \graveaccent a un point $A_{\pi(i)}^{(1)}$ o\`u $\pi\in\frak
S_n$ est justement la permutation $\phi(\tau)$.

Le noyau de $\phi$ est donc form\'e des tresses qui partent et
aboutissent aux points de m\hataccent eme indice, on le notera $P_n$.
C'est le groupe des tresses pures.

Comme la pr\'esentation de $\frak S_n$ s'obtient \graveaccent a partir
de celle de $P_n$ en ajoutant les relateurs $(t_i^2=1)$, $P_n$ est le
sous-groupe distingu\'e engendr\'e par les $(t_i^2)$. On se convainc
assez facilement g\'eom\'etriquement que $P_n$ est engendr\'e par les
tresses suivantes [cf\. fig.~6]~:
$$
g_{ij}=t_{j-1}^{-1}t_{j-2}^{-1}\cdots t_i^2t_{i-1}^{-1}\cdots t_{j-1}\
\text {avec}\ i<j.
$$

\proclaim{Proposition II.1} {\rm i)} $P_n=\langle g_{ij}\rangle_{i<j\leq n}$
et plus pr\'ecis\'em\'ent

{\rm ii)} $P_n=\langle g_{i,n}\rangle_{i<n}\times\langle g_{i,j}\rangle_{j<n-1}$
le produit
\'etant semi-direct. Le premier facteur 
$(\langle g_{i,n}\rangle_{i<n})$ 
est isomorphe \graveaccent a $F_{n-1}$ et le
second ($\langle g_{i,j}\rangle_{j<n-1}$) \graveaccent a
$P_{n-1}$
\endproclaim

\demo{\bf Preuve} Ces r\'esultats sont classiques et on en trouvera une
d\'emonstration to\-po\-lo\-gique dans \cite{Bir}. Une d\'emonstration
combinatoire peut se faire par une m\'ethode analogue \graveaccent a
celle de prop.~III.15 (``recomposition semi-directe'').


1): On montre les formules~:
$$\matrix\format\r&\l\\ 
t_i^{-1}g_{r,s}t_i &=g_{r,s}\quad \text{si}~i\not\in\{r-1,s-1,s\}\\
t_{r-1}^{-1}g_{r,s}t_{r-1} &=g_{r,s}g_{r-1,s}g_{r,s}^{-1}\\
t_{r-1}g_{r,s}t_{r-1}^{-1} &=g_{r-1,s}\\
t_{s-1}g_{r,s}t_{s-1}^{-1} &=g_{r,s-1}\\
t_{s-1}^{-1} g_{r,s}t_{s-1}^{-1} &=g_{s-1,s}^{-1}g_{r,s-1}g_{s-1,s}\\
t_s^{-1}g_{r,s}t_s &=g_{r,s+1}\\
t_sg_{r,s}t_s^{-1} &=g_{s,s+1}g_{r,s+1}g_{s,s+1}^{-1}
\endmatrix$$
ce qui prouve (i).

2): Les formules pr\'ec\'edentes permettent de d\'efinir une
action de $F(g_{i,j},i<j<n)$ sur $F_{n-1}=F(g_{i,n},i<n)$ c'est
\graveaccent a dire un homomorphisme $\alpha:F(g_{ij},i<j<n)\to Aut
(F(g_{i,n},i<n)$. On v\'erifie que cet homomorphisme est compatible
avec les relateurs de $P_{n-1}$ (cf\. Remarques~I.2.2) et on a donc
ainsi une action de $P_{n-1}$ sur $F_{n-1}$. Ceci permet de d\'efinir
le produit semi-direct $F_{n-1}\times P_{n-1}$ puis de montrer qu'il
est isomorphe \graveaccent a $P_n$ gr\hataccent ace \graveaccent a la
pr\'esentation de celui-ci \cite{MKS}.\qed
\enddemo

\vskip10pt
{\bf III. \'Elimination dans le cas partiellement commutatif}
\vskip5pt

{\bf 1. L'alg\`ebre de Lie partiellement commutative}

La notion d'alg\`ebre de Lie est historiquement li\'ee \graveaccent a
celle de d\'erivation.

\definition{D\'efinition III.1}
Soit $k$ un anneau et $\Cal A$, une
$k$-alg\`ebre (non n\'ecessairement associative \cite{Bo2}). Une {\it
d\'erivation} est un \'el\'ement $D\in End_k(\Cal A)$ v\'erifiant
identiquement~:
$$
D(xy)=D(x)y+xD(y).
$$
\enddefinition

\remark{\bf Remarques III.2} 1) La compos\'ee de deux d\'erivations n'est
en g\'en\'eral pas une d\'erivation.

2) Par contre le crochet (de Lie) de deux d\'erivations
$$
\[D_1,D_2\]=D_1D_2-D_2D_1
$$
est une d\'erivation. L'ensemble des d\'erivations de $\Cal A$ est
donc une sous-alg\`ebre de Lie de $End_k(\Cal A)$ qui sera not\'ee
$\frak {Der}(\Cal A)$.

3) Dans un anneau (ou une alg\`ebre associative) l'application~; $x\to
ax-xa=ad_a(x)$ est une d\'erivation pour les op\'erations $\bullet$ et
[~,~]. Cette derni\`ere (le crochet de Lie) \'etant d\'efinie par la
formule $\[x,y\]=xy-yx$. On a donc, dans ce cas, les identit\'es~: 
$$\align 
\[x,\[y,z\]\]&=\[\[x,y\],z\]+\[y,\[x,z\]\],\tag{\it JAC}\\
\[x,x\]&=0.\tag{\it ALT}
\endalign$$

4) La premi\`ere de ces identit\'es s'appelle {\it identit\'e de
Jacobi} et la seconde exprime que l'application bilin\'eaire d\'efinie
par [~,~] est {\it altern\'ee}.\footnote{Contrairement \graveaccent a
ce que l'on pourrait croire, cette identit\'e est essentielle. On
pourra consulter par exemple \cite{Cu} pour ce rendre compte de ce qui
advient lorsqu'on la supprime.} 
\endremark

Ceci conduit \graveaccent a la
d\'efinition suivante~: 

\definition{D\'efinition III.3}
On appelle $k$-alg\`ebre de Lie une
$k$-alg\`ebre qui v\'erifie identiquement {\it (JAC)} et
{\it (ALT)}.
\enddefinition

Il r\'esulte des travaux de {\smc Hall, Witt} 
et {\smc Magnus} \cite{Bo1}\cite{Lo}
que l'alg\`ebre de Lie libre peut se r\'ealiser come une alg\`ebre de
Lie de polyn\hataccent omes non commutatifs. 

\proclaim{Proposition III.4} Soit $A$, un alphabet et $k$ un anneau.
On consid\`ere $k\langle A\rangle$ ($=k\[A^\ast\]$) muni de sa structure
d'alg\`ebre de Lie pour $\[P,Q\]=PQ-QP$. Alors~:

La sous-alg\`ebre de Lie $L_k(A)$ de $k\langle A\rangle$ engendr\'ee
par $A$ est libre en tant qu'alg\`ebre de Lie. C'est \graveaccent a
dire que toute application $\Phi: A\to \frak g$ (o\`u $\frak g$ est
une alg\`ebre de Lie) se prolonge \graveaccent a $L_k(A)$ de fa\c con
que le diagramme suivant soit commutatif~:

\vskip10pt
\vbox{
$$
\CD 
A @>\Phi>>\frak g\\
@Vnat VV @.\\
L_k(A) @.
\endCD
\kern-40pt\nearrow\raise-3pt\hbox{\kern-5pt$\ssize\bar\Phi$}
$$
\centerline{\eightpoint Figure 7}
}
\vskip10pt
\endproclaim

Conform\'ement \graveaccent a la preuve de prop.~I.1, on peut
r\'ealiser une alg\`ebre de Lie pr\'esent\'ee $\langle A; {\text {\bf
R}}\rangle_{\text{\bf Lie}}$ comme un quotient de l'alg\`ebre de 
Lie libre. Comme
cas particulier on a 
$$L_k(A,\vartheta)\overset\text{def}\to=\langle
A;(\[a,b\]=0)_{(a,b)\in\vartheta}\rangle_{\text{\bf Lie}},$$ 
l'alg\`ebre de Lie
partiellement commutative libre associ\'ee \graveaccent a un alphabet
\graveaccent a commutation $(A,\vartheta)$. On peut alors se poser les
questions suivantes~:

{\smc Question 1}: L'alg\`ebre de Lie $L_\Z(A,\vartheta)$ est-elle libre (en
tant que $\Z$-module)~?   

{\smc Question 2}: Si ``oui'' comment en constuire des bases~?

{\smc Question 3}: Quelle est l'utilit\'e de r\'esoudre Q1 et Q2~?

{\smc Reponse 3}: Le groupe partiellement commutatif libre est
$$
F(A,\vartheta)\overset\text{def}\to=\langle A;(ab=ba)_{(a,b)\in\vartheta
}\rangle_{\text{\bf Grp}}.
$$
Si $L_\Z(A,\vartheta)$ est sans torsion, $F(A,\vartheta)$ est
ordonnable (cf\. \cite{DK2}) ce qui permet de montrer la
d\'ecidabilit\'e de l'\'equivalence des s\'eries partiellement
commutatives rationnelles (cf\. \cite{Va}). 


\remark{\bf Remarques III.5} 1) Certaines relateurs, {\it m\hataccent
eme compos\'es uniquement de mots de Lie}, introduisent de la torsion.
Par example~:
$$
\left\{\matrix\format\r&\l\\
\[\[\[x_1,x_2\],x_3\],x_3\] &=0\\
\[\[\[x_1,x_3\],x_3\],x_2\] &=0\\
\[x_1,\[\[x_2,x_3\],x_3\]\] &=0 \endmatrix\right.\tag{\text {\bf R}}
$$
En effet, on montre que, dans l'alg\`ebre de Lie $\langle
x_1,x_2,x_3;\text {\bf R}\rangle_{\Z-\text {\bf Lie Alg}}$ on a
$P=\[\[x_1,x_3\],\[x_2,x_3\]\]\neq 0$ mains $2P=0$. 

La solution de Q2 (et donc de Q1) s'obtient gr\hataccent ace
\graveaccent a une adaptation du {\it proc\'ed\'e d'\'elimination de}
M. LAZARD au cas partiellement commutatif.
\endremark

{\bf  2.  Elimination  dans  $M(A,\vartheta)$}


Soit $A$, un alphabet, on a muni $A$ d'un graphe $\vartheta$,
irr\'eflexif et sym\'etrique $(\vartheta\subseteq A^2-\Delta_A$ et
$\vartheta=\vartheta^{-1})$, un tel couple $(A, \vartheta)$ sera
appell\'e {\it alphabet \graveaccent a commutations}. On pose~:
$$
M(A, \vartheta)\overset\text{def}\to=\langle
A;(xy=yx)_{(x,y)\in\vartheta}\rangle_{\text{\bf Mon}}
$$
$M(A,\vartheta)$ est le {\it mono\"\i de partiellement commutatif}
librement engendr\'e par $(A,\vartheta)$, ses \'el\'ements seront
appell\'es ``mots'', ``mon\hataccent omes'' ou ``traces''. On note
$\equiv_\vartheta$, la congruence (sur $A^\ast$) engendr\'ee par le
relateur $(xy=yx)_{(x,y)\in\vartheta}$. Par exemple, pour
$\vartheta=\{(a,b),(b,a),(c,d),(d,c)\}$ (soit graphiquement
$a$----$b$ \  $c$----$d$) on a
$cabacd\equiv_\vartheta ca^2bdc$. De m\hataccent eme que les tresses,
les mots partiellement commutatifs admettent une repr\'esentation
graphique qui permet des intuitions justes, ce sont les empilements
d\'evelopp\'es par {\smc G.~X.~Viennot} et son \'ecole \cite{Vi}.

L'\'elimination dans $M(A,\vartheta)$ est l'analogue de la formule
(II.1.1) et fait appel \graveaccent a la notion de {\it sous-alphabet
non-commutatif} et d'{\it alphabet terminal}.

\definition{D\'efinition III.6}
 i) On dira que $Z\subseteq A$ est un
sous-alphabet {\it non-commutatif} si 
$$
(x,y)\in Z^2\Longrightarrow (x,y)\not\in\vartheta.
$$
ii) Soit $w\in M(A,\vartheta)$, le sous-alphabet~; $AT(w)=\{a\in A\mid w\in
M(A,\vartheta)a\}$ sera appell\'e {\it alphabet terminal de
$w$}.

iii) Soit $Z$ un sous-alphabet non-commutatif de $A$ et $B$ {\it telle
que} $B\cap Z=\emptyset$. On appelle code ``$Z$'' la partie~:
$C_Z(B)=\{wz\mid w\in\langle B\rangle, z\in Z\ \text{et} \ AT(wz)=\{z\}\}$.
\enddefinition

On a alors la d\'ecomposition suivante de $M(A, \vartheta)$. 

\proclaim{Th\'eor\`eme III.7} Si $A=B+Z$, et que $Z$ est une partie
non-com\-mu\-ta\-tive de $A$, tout mot $w\in M(A,\vartheta)$ s'\'ecrit de
fa\c con unique~:
$$
w=w_1z_1w_2z_2\cdots w_nz_nw_{n+1}
$$
avec $w_i\in\langle B\rangle$ pour $1\leq i\leq n+1$ et $w_iz_i\in
C_Z(B)$.
\endproclaim

\demo{\bf Preuve} On peut la trouver, par exemple dans \cite{DK3} ou
\cite{DK5}.\qed
\enddemo

\remark{\bf Remarques III.8} 1): On voit facilement que pour toute
partie $B\subseteq A$ on a $\langle B\rangle\cong M(B,\vartheta_B)$
o\`u $\vartheta_B$ d\'esigne le sous-graphe $\vartheta\cap
B^2$.

2): Le th\'eor\`eme pr\'ec\'edent entraine l'\'egalit\'e
$M(A,\vartheta)=C_Z(B)^\ast\langle B\rangle$ ce qui, compte tenu de la
remarque pr\'ec\'edente, revient \graveaccent a
$M(A,\vartheta)=C_Z(B)^\ast M(B,\vartheta_B)$. Nous sommes donc dans
le cadre de la formulation de l'introduction avec 
$STRUCT=STRUCT_1$.

3): En consid\'erant une {\it partition chromatique} $(Z_i)_{i\in I}$
de $A$ (c'est \graveaccent a dire en parties non-commutatives) on voit
que, dans le cas o\`u $I$ est fini, (ce qui est toujours possible si
$A$ l'est) on a~:
$$
M(A,\vartheta)=C_{Z_{i_1}}(B_{i_1})^\ast C_{Z_{i_2}}(B_{i_2})^\ast\cdots
C_{Z_{i_n}} (B_{i_n})^\ast
$$
avec $I=\{i_1,i_2,\dots, i_n\}$ et
$B_{i_k}=\bigcup_{j>k}Z_{i_j}$.
\endremark

\vskip5pt
{\bf  3.  Application   \graveaccent a  l'alg\`ebre  de  Lie
$L_k(A,\vartheta)$}

$1^{\text {\`ere}}$ Etape: Soit $(A,\vartheta)$, un alphabet \graveaccent a
commutations et $Z$ une partie non-com\-mu\-ta\-tive de $A$ (on posera
$B=A-Z$).

Si $wz\in C_Z(B)$ on v\'erifie que, pour toute \'ecriture
$wz=b_1b_2\cdots b_pz$, le mot de Lie
$\[b_1,\dots,\[b_{p-1},\[b_p,z\]\]\]$ a la m\hataccent eme valeur dans
$L_k(A,\vartheta)$. Ce mot sera not\'e $\alpha(wz)$.

On a donc une factorisation de $\alpha$~:

\vskip10pt
\vbox{
$$
\CD 
C_Z(B) @>\alpha>>L_k(A,\vartheta)\\
@Vnat VV @.\\
L_k(C_Z(B))\kern-10pt @.
\endCD
\kern-60pt\nearrow\raise-3pt\hbox{\kern-5pt$\ssize\bar\alpha$}
$$
\centerline{\eightpoint Figure 8}
}
\vskip10pt

$2^{\text {\`eme}}$ Etape: L'application naturelle
$\beta:B\to L_k(A,\vartheta)$ respecte les commutations de
$\vartheta_B$ d'o\`u une factorisation~:

\vskip10pt
\vbox{
$$
\CD 
B @>\beta>>L_k(A,\vartheta)\\
@Vnat VV @.\\
\kern-20ptL_k(B,\vartheta_B)\kern-20pt @.
\endCD
\kern-60pt\nearrow\raise-3pt\hbox{\kern-5pt$\ssize\bar\beta$}
$$
\centerline{\eightpoint Figure 9}
}
\vskip10pt


$3^{\text {\`eme}}$ Etape: (Action de $L_k(B,\vartheta_B)$ sur
$L_k(A,\vartheta)$).

On d\'efinit des d\'erivations par les formules suivantes~:
$$
\partial_b(\alpha(wz)) =\cases
\alpha(bwz) &\text{si} \ bwz\neq wzb,\\
0 &\text{sinon.}\endcases
$$
L'application $\partial_b$ s'\'etend en une d\'erivation de
$L_k(C_Z(B))$ qui v\'erifie~:
$$
(b,b')\in\vartheta\quad \Longrightarrow\quad 
\partial_b\partial_{b'}=\partial_{b'}\partial_b
$$
et, \graveaccent a cause de la pr\'esentation de $L_k(B,\vartheta_B)$
(qui est donn\'ee par\linebreak $\langle B;
(\[b,b'\]=0)_{(b,b')\in\vartheta_B}\rangle$, on a une factorisation~:

\vskip10pt
\vbox{
$$
\CD 
B @>>>\frak D\frak e\frak r(L_k(C_Z(B)))\\
@Vnat VV @.\\
\kern-20ptL_k(B,\vartheta_B)\kern-20pt @.
\endCD
\kern-90pt\nearrow\raise-3pt\hbox{\kern-5pt$\ssize\partial$}
$$
\centerline{\eightpoint Figure 10}
}
\vskip10pt

$4^{\text {\`eme}}$ Etape: On d\'efinit alors sur $\frak
g=L_k(C_Z(B))\oplus L_k(B,\vartheta_B)$ le crochet suivant
\footnote{Cette formule est, comme en th\'eorie des groupes, une
imitation des \'egalit\'es que l'on obtient lorsque l'on a un produit
semi-direct interne c'est \graveaccent a dire que $\frak g=\frak
h\oplus\frak g'$ o\`u $\frak h$ est un id\'eal de $\frak g$.} (produit
semi-direct)~:
$$
\[P+Q,P'+Q'\]=\[P,P'\]+\partial_Q(P')-\partial_{Q'}(P)+\[Q,Q'\].
$$

\proclaim{Th\'eor\`eme III.9 \rm\cite{DK1}}  L'application $\gamma:\frak
g\to L_k(A,\vartheta)$ d\'efinie par
$\gamma(P+Q)=\bar\alpha(P)+\bar\beta(Q)$ est un isomorphisme
d'alg\`ebres de Lie.
\endproclaim

\demo{\bf Preuve} On pourra trouver, dans \cite{DK1}, une preuve qui
consiste \graveaccent a examiner le noyau du morphisme naturel
$L(A)\to L_k(A,\vartheta)$, et une autre dans \cite{DK4} proche dans
son esprit de celle qui est \'evoqu\'ee \graveaccent a la proposition
II.1.\qed
\enddemo
\vskip5pt

{\bf \ 4. \ Quelques \ cons\'equences}

\proclaim{Corollaire III.10} Pour tout anneau $k$, $L_k(A,\vartheta)$
se plonge naturellement dans\linebreak $k\[M(A,\vartheta)\]=k\langle
A,\vartheta\rangle$ (polyn\hataccent omes partiellement commutatifs),
et s'identifie \graveaccent a la sous-alg\`ebre de Lie engendr\'ee par
les lettres.
\endproclaim


\remark{\bf Remarque III.11} $L_k(A,\vartheta)$ est gradu\'ee. En effet,
si on pose~:
$$
L_k^\nu(A,\vartheta)=L_k(A,\vartheta)\cap k^\nu\langle A,\vartheta\rangle
$$
pour tout $\nu\in\N^{A}$ on a facilement que~:
$$
Im(\bar\alpha)=\bigoplus_{z\in alph(\nu)} L_k^\nu(A,\vartheta)
$$
$$
Im(\bar\beta)=\bigoplus_{z\not\in alph(\nu)}L_k^\nu(A,\vartheta)
$$
ceci premet de construire facilement des bases de $L_k(A,\vartheta)$,
par \'eliminations successives puisque $Im(\bar\alpha)$ est libre et
que $Im(\bar\beta)\cong L_k(B,\vartheta_B)$.
\endremark

\proclaim{Corollaire III.12} $F(A,\vartheta)=\langle
A;(ab=ba)_{(a,b)\in\vartheta}\rangle$, le groupe partiellement
commutatif libre, est ordonnable \footnote{C'est \graveaccent a dire
peut \hataccent etre muni d'un ordre total compatible avec sa loi
\cite{Bo3}\cite{Mu}\cite{Neu}}.
\endproclaim

\demo{\bf Preuve} On forme la suite centrale descendante d\'efinie par
$$
F_1=F \ \ \ \text {et} \ \ \ F_{n+1}=(F_n,F)
$$
o\`u $(H,K)$ d\'esigne le sous-groupe engendr\'e par les
commutateurs 
$$(hkh^{-1}k^{-1})_{(h,k)\in H\times K}.$$ 
Le $\Z$-module gradu\'e
$Gr(F) = \bigoplus_{n\geq1}F_n/F_{n+1}$ peut \hataccent etre muni d'un
crochet de Lie qui ``lin\'earise'' l'op\'eration commutateur
\cite{MKS} et on peut montrer qu'on a un isomorphisme d'alg\`ebres de
Lie gradu\'ees $Gr(F)\cong L_\Z(A,\vartheta)$. Ce qui prouve que les
quotients $F_n/F_{n+1}$ sont des groupes ab\'eliens libres (donc
ordonnables). On en d\'eduit alors que $F(A,\vartheta)$ est ordonnable
comme dans \cite{Neu}.\qed
\enddemo

\remark{\bf Remarque III.13} On peut ordonner $F(A,\vartheta)$ par une
m\'ethode plus directe \cite{DT}. 
\endremark

On a $\dim (k^\nu\langle A,\vartheta\rangle)=|M^\nu (A,\vartheta)|$. Il
r\'esulte donc du travail de {\smc P.~Cartier} 
et {\smc D.~Foata} \cite{CF} que la
s\'erie de Hilbert da l'alg\`ebre gradu\'ee $k\langle
A,\vartheta\rangle=\bigoplus_{\nu\in\N^{A}} k^\nu\langle
A,\vartheta\rangle$ s'exprime simplement~:
$$
\suml_{\nu\in\N^{A}} \dim (k^\nu\langle A,\vartheta\rangle)\ \text
{\bf T}^\nu=\left(\suml_{{w}\in\Cal C\ell(\vartheta)} (-1)^{|w|}
\text {\bf T}_{{w}}\right)^{-1},
$$
o\`u {\bf T}$=((T_a)_{a\in A})$ d\'esigne une famille
d'ind\'etermin\'ees commutatives, $\Cal C\ell(\vartheta)$ est
l'en\-semble des mots compl\`etement commutatifs sans multiplicit\'e
soit~:
$$
\Cal C\ell(\vartheta)=\{a_1a_2\cdots a_n\in
M(A,\vartheta)\mid i<j\Longrightarrow(a_i,a_j)\in\vartheta\}
$$
et $\text {{\bf T}}_{a_1a_2\cdots a_n}=T_{a_1}T_{a_2}\cdots T_{a_n}$.
D'autre part, on a l'isomorphisme gradu\'e 
$k\langle A,\vartheta\rangle\overset{\text {$k$-\bf alg.}}\to {\cong}\Cal U(L_k(A,\vartheta))$
et donc gr\hataccent ace au th\'eor\graveaccent eme de
{\smc Poincar\'e--Birkhoff--Witt} \cite{Bo1} aussi l'isomorphisme gradu\'e
$k\langle A,\vartheta\rangle\overset{\text {$k$-\bf mod.}}\to {\cong}
S((L_k(A,\vartheta))$. On en d\'eduit~:


\proclaim{Corollaire III.14 \rm(Rangs)}  Soit
$l(\nu)=\dim (L_k^\nu(A,\vartheta))$ pour tout $\nu\in \N^{A}$. Alors~:
$$
\suml_{\nu\in\N^{A}}\dim(k^\nu\langle
A,\vartheta\rangle)\bold T^\nu=\bigg(\suml_{w\in\Cal
C\ell(\vartheta)}(-1)^{\vert w\vert}\bold T_w\bigg)^{-1}=\prod_{\nu\neq 0}
(1-\bold T^\nu)^{-l(\nu)}.
$$
\endproclaim
\demo{\bf Preuve} Cf\. \cite{DK1}.\qed
\enddemo

On d\'eduit de ce qui pr\'ec\graveaccent ede des formules pour le
calcul des rangs qui g\'en\'eralisent celles de {\smc Witt}.
\vskip10pt

{\bf  4. Le  groupe  partiellement  commutatif libre}

\vskip5pt

a) {\smc \'Eliminiation}

On a, l\`a aussi, une formule d'\'elimination dans
$F(A,\vartheta)=\langle
A;(ab=ba)_{(a,b)\in\vartheta}\rangle_{\text{\bf Grp}}$.
Soit, comme en III.2, $Z\subseteq A$ un sous-alphabet non-commutatif
et $B$ une partie disjointe de $Z$. On notera $D_Z(B)$ l'orbite
$\{wzw^{-1}\}_{w\in\langle B\rangle}$ de $Z$ par les conjugaisons de
$B$.

\proclaim{Proposition III.15}{\rm i)} $F(A,\vartheta)=\langle
D_Z(B)\rangle\times\langle B\rangle$, le produit \'etant
semi-direct.

{\rm ii)} $\langle D_Z(B)\rangle\cong F(D_Z(B))$ et $\langle B\rangle\cong
F(B,\vartheta_B\rangle$.
\endproclaim
\demo{\bf Preuve} La d\'emonstration est analogue \graveaccent a celle de
l'alg\'ebre de Lie libre en rempla\c cant les d\'erivations par des
automorphismes int\'erieurs.\qed
\enddemo

\remark{\bf Remarque III.16} Avec les notations de II.2, si l'on
consid\`ere l'alphabet \graveaccent a commutations
$A=(g_{ij})_{i<j\leq n}$ et le sous-alphabet $Z=(g_{in})_{i<n}$ on
voit que l'\'elimination dans le groupe des tresse pures est une image
de celle qui pr\'ec\graveaccent ede.
\endremark

\pagebreak
\vskip5pt

b) {\smc Transformation de Magnus}

On peut d\'efinir l'{\it alg\`ebre large} du mono\"\i de partiellement
commutatif libre puisque pour tout $w\in M(A,\vartheta)$ l'ensemble
des solutions de $w=uv$ est fini \cite{Bo2}. Elle a pour support le
module $k^{M(A,\vartheta)}$ et son produit est~:
$$
(f\ast g)(w)=\suml_{uv=w} f(u)g(v).
$$
Notons $k\langle\langle A,\vartheta\rangle\rangle$ cette alg\`ebre.
Pour un anneau de coefficients $k$ donn\'e (``s\'eries formelles
pariellement commutatives'') et $\frak M_k\langle\langle
A,\vartheta\rangle\rangle$ l'id\'eal $\{S\in k\langle\langle
A,\vartheta\rangle\rangle\mid S(1))=0\}$. L'application $a\longrightarrow 1+a$ prend
ses valeurs dans le groupe $1+\frak M_k\langle\langle
A,\vartheta\rangle\rangle$ des s\'eries de terme constant 1, cette
application respecte les relateurs de $F(A,\vartheta)$ si bien qu'on a
une factorisation~:

\vskip10pt
\vbox{
$$
\CD 
A @>>>1+\frak M_k\langle\langle A,\vartheta\rangle\rangle\\
@Vnat VV @.\\
\kern-10ptF(A,\vartheta)\kern-10pt @.
\endCD
\kern-90pt\nearrow\raise-3pt\hbox{\kern-5pt$\ssize\mu$}
$$
\centerline{\eightpoint Figure 11}
}
\vskip10pt

On peut montrer que $\mu$ est injective. C'est la transformation de
Magnus. On dira qu'une congruence $\equiv$ sur $A^\ast$ est {\it
compatible} avec la transformation de Magnus si et seulement si~:
$$
u\equiv v\Longrightarrow\mu(u)\equiv_k \mu(v)
$$
o\`u $\mu$ est la transformation de Magnus de $A^\ast(\mu(a_1a_2\cdots
a_n=(1+a_1)(1+a_2)\cdots(1+a_n))$ et $\equiv_k$ l'extension par
lin\'earit\'e de $\equiv$ \graveaccent a $k\langle A\rangle$. On peut
alors pr\'eciser les congruences qui, en caract\'eristique z\'ero,
sont compatibles avec la transformation de Magnus.


\proclaim{Proposition III.17 \smc (Duchamp 1991)} Soit $k$, un anneau de
caract\'eristique z\'ero, $A$ un alphabet et $\equiv$ une congruence
sur $A^\ast$. Les conditions suivantes sont \'equivalentes~: 
\roster
\item $\equiv$ est compatible avec la transformation de Magnus. 
\item $\equiv$ est engendr\'ee par des diff\'erences du type $a-b$ ou
$ab-ba$ o\`u $a$ et $b$ sont des lettres.
\endroster
\endproclaim

\demo{\bf Preuve} Remarquons d'abord qu'on se ram\`ene aussit\hataccent ot
\graveaccent a $k=\Z$ puisque les images de la transformation de
Magnus sont des polyn\hataccent omes \graveaccent a coefficients dans
$\Z.1_k$. Montrons alors le sens~: 
$$
\text {compatible} \ \to \text {relateurs du type} \ (a_i=b_i) \ \text
{et} \ (a_jb_j=b_ja_j)
$$
(la r\'eciproque \'etant une simple v\'erification) et pla\c cons nous
sous l'hypoth\`ese o\`u $\equiv$ est compatible avec la transformation
de Magnus.

La d\'emonstration comprend 6 \'etapes.

1): La congruence $\equiv$ est homog\'ene.

En effet, si $u\equiv v$ alors $\mu_k(u)\equiv\mu_k(v)$ et donc
$\pi^ k _\equiv(\mu_k(u))=\pi^ k
_\equiv(\mu_k(v))$ et, en sp\'ecialisant tous les mots de
$A^\ast/\equiv$ en $1_\Z,2^{|u|}=2^{|v|}$ c'est \graveaccent a dire
$|u|=|v|$.

La congruence \'etant homog\`ene on notara $\equiv^n$ la relation
d'\'equi\-va\-lence induite sur $A^n$ et $\equiv^{\leq n}$ la congruence
engendr\'ee par les relations $u\equiv v$ pour $|u|,|v|\leq n$.

2): R\'eduction du probl\`eme

Consid\'erons un sous-alphabet $S\subseteq A$ qui soit une section de
la relation d'\'equi\-va\-lence $\equiv^1$ on a alors un isomorphisme
naturel $S^\ast/\equiv_S\longrightarrow A^\ast/\equiv(\equiv_S$ d\'esigne la
congruence induite sur $S^\ast)$ et on v\'erifie facilement que
$\equiv_S$ est aussi compatible avec la transformation de Magnus. Le
r\'esultat sera donc prouv\'e si on d\'emontre que $\equiv_S$ est un
congruence partiellement commmutative.

3): $\equiv_S$ est multihomog\`ene.

En effet $\mu_\Z(u)=1+\sum_{a\in S}|u|_aa+\sum$  termes  de  longueur
$\geq 2$ o\`u $|~|_a$ d\'esigne le degr\'e partiel en la lettre $a$. La
comparaison avec $\mu_\Z(v)$ montre que 
$\sum_{a\in S}|u|_aa=\sum_{a\in S}|v|_aa$ ce
qui, en raison de l'ind\'ependance lin\'eaire des lettres entraine, la
propri\'et\'e~:
$$
u\equiv_Sv\Longrightarrow(\forall a\in A)(|u|_a=|v|_a).
$$
Une telle congruence est dite {\it multihomog\`ene}.

Dans la suite on notera $\equiv$ au lieu de $\equiv_S$.

4): $\equiv$ est simplifiable.

En fait, on a la propri\'et\'e plus forte que $S^\ast/\equiv$ se plonge
dans un groupe, puisque le fait que $\equiv$ soit compatible avec la
transformation de Magnus entraine que $S^\ast/\equiv$ se plonge, via
cette transformation dans le groupe des \'el\'ements $f$ de son
alg\`ebre large tels que $f(1)=1$.

5): Contradiction

Il suffit maintenant de montrer que $\equiv =\equiv^{\leq 2}$.
Supposons que ce ne soit pas le cas, on aurait alors un contrexemple
de longueur minimale $u\equiv v$ tel que l'on ait pas $u\equiv^{\leq
2}v$ et donc $|u|\geq 3$. On peut \'ecrire $u=u_1a_n$ avec $a_n\in A$
et $v=v_1a_nw$ avec $a_n\notin Alph(w)$. On ne peut avoir $w=1$ sans
quoi, comme $\equiv$ est simplifiable, ceci entrainerait $u_1\equiv
v_1$ puis $u_1\equiv^{\leq 2} v_1$ en raison de la minimalit\'e du
contrexemple et enfin $u\equiv^{\leq 2} v$, contredisant l'hypoth\`ese.
En (6) on va montrer qu'on peut toujours se ramener \graveaccent a ce
cas, ce qui entrainera l'impossibilit\'e d'un contrexemple minimal,
d\'emontrant ainsi la proposition.

6) $a_n$ commute avec $w$.

Posons $d=|u|_{a_n}=|v|_{a_n}$ et $w=w_1w_2\cdots w_k$. Pour toute
lettre $w_i$, le mon\hataccent ome $a_n  ^dw_i$ qui figure dans
$\mu(v)$ figure aussi dans $\mu(u)$. On a donc, en raison de la
multihomog\'en\'e\"\i t\'e, $a_n  ^dw_i\equiv a_n  ^{d-j}w_ia_n 
^j$ et $j\geq 1$ \graveaccent a cause de la forme de $u$. Ceci
entraine $w_ia_n  ^j\equiv a_n ^jw_i$. En prenant les logarithmes
des transform\'es dans $1+\frak M_\Q\[\[S^\ast/\equiv\]\]$, on en
d\'eduit que $w_ia_n\equiv a_nw_i$.
\enddemo
\vskip5pt 

{\bf Conclusion}
\vskip5pt

Les structures partiellement commutatives sont \'etroitement li\'ees
les unes aux autres. Par exemple on a~:
$$
k\langle A,\vartheta\rangle =k\[M(A,\vartheta)\]\cong\Cal
U(L_k(A,\vartheta))
$$
cela tient \graveaccent a ce que les commutations partielles sont
\graveaccent a la fois des relations mono\"\i dales $(ab=ba)$ et des
relations de Lie $(\[a,b\]=0)$ et, d'une certaine fa\c con, en
caract\'eristique z\'ero, ce sont les seules. En fait, on a le
th\'eor\graveaccent eme suivant~:

\proclaim{Th\'eor\graveaccent eme de limitation \rm\cite{DK3}\cite{DK4}} 
Soit $A$, un alphabet et $k$ un anneau de caract\'eristique z\'ero
\footnote{Le th\'eor\`eme ne vaut plus en caract\'eristique $p$.}. 
On suppose qu'un id\'eal bilat\`ere $\frak I$ est engendr\'e (en
tant qu'id\'eal bilat\`ere) par des polyn\hataccent omes de Lie et
aussi par des diff\'erences de mots. Alors il existe deux familles
doubles de lettres $(a_i,b_i)_{i\in I}$ et $(a_j,b_j)_{j\in J}$ tel
que $\frak J$ soit aussi engendr\'e par les polyn\hataccent omes
$(a_i-b_i)_{i\in I}$ et $(a_jb_j-b_ja_j)_{j\in J}$.
\endproclaim

Ceci implique que $k\langle A\rangle/\frak I$ est une alg\`ebre de
polyn\hataccent omes partiellement commutatifs et montre le
caract\`ere tr\`es particulier de ces alg\`ebres.

\widestnumber\key{MKS}
\Refs
\ref \key Ar\by ARTIN, E.\paper Theorie der Z\"opfe\inbook Collected
papers \eds S.~Lang et J.~Tate\publ Addison--Wesley\yr1965 \endref
\ref\key BP\by BERSTEL, J., PERRIN, D.\book Theory of codes\publ
Academic Press\yr1985\endref
\ref\key Bir\by BIRMAN, J.S.\paper Recent developments in braid and
link theory\jour Math\. Intelligencer\vol 13\yr 1991\pages
51--60\endref
\ref\key Bo1\by BOURBAKI, N.\book Groupes et alg\`ebres de Lie
\bookinfo Ch.~2 et 3
\publ Hermann\yr 1972\endref
\ref\key Bo2\by BOURBAKI, N.\book Alg\`ebres\bookinfo Ch.~1 \`a 3
\publ Hermann\yr 1970\endref
\ref\key Bo3\by BOURBAKI, N.\book Alg\`ebre\bookinfo Ch.~6.1
\publ Masson\yr 1981\endref
\ref\key Ca\by CARTIER, P.\paper Developpements r\'ecents sur les
groupes de tresses. Applications \`a la topologie et
\`a l'alg\`ebre\inbook
S\'eminaire Bourbaki, Vol. 1989/90\publ
Ast\'erisque  No.~189-190, Exp. No. 716\yr 1990\pages 17--67\endref
\ref\key CF\by CARTIER, P., FOATA, D.\book
 Probl\`emes combinatoires de commutation et r\'earrangements\publ
Lecture Notes in Mathematics, No.~85\publaddr
Springer-Verlag, Berlin--New York\yr 1969\endref
\ref\key CP\by CORI, R., PERRIN, D.\paper Automates et commutations
partielles \jour RAIRO Inform\. Theor\.\vol 19\yr 1985\pages
21--32\endref
\ref\key Cu\by CUVIER, C.\book Homologie des alg\`ebres de Leibniz
\publ Th\`ese Univ\. de Strasbourg\yr 1991\endref
\ref\key Do1\by \Dbar OKOVI\'C, D.Z.\paper   
A generalization of Witt's formulae\jour
J. Algebra \vol 111\yr 1987\pages 262--278\endref
\ref\key Do2\by \Dbar OKOVI\'C, D.Z.\paper  
On some inner derivations of free Lie algebras over commutative rings
\jour J. Algebra\vol 119 \yr 1988\pages 233--245\endref
\ref\key Du\by DUBOC, C.\book Commutations dans les mono\"\i des
libres\publ Th\`ese Univ\. de Rouen\yr 1986\endref
\ref\key D1\by DUCHAMP, G.\paper Orthogonal projection onto the free 
Lie algebra\jour  Theoret\. Comput\. Sci\.\vol  79 \yr 1991\pages
227--239\endref 
\ref\key D2\by DUCHAMP, G.\paper On the partially comutative free Lie
algebra\jour Rapport LITP~89.74\endref
\ref\key D3\by DUCHAMP, G.\paper Factorisations partiellement
commutativs et ap\'eriodicit\'e \jour Rapport LITP 91.08 et actes des
journ\'ees Montoises 1990\pages pp.~42--48\endref
\ref\key DK1\by DUCHAMP, G., KROB, D.\paper The free partially
commutative Lie algebra: bases and ranks \jour  Adv\. Math\.\vol
95\yr 1992\pages 92--126\endref
\ref\key DK2\by DUCHAMP, G., KROB, D.\paper The lower central series
of the free partially commutative group\jour  Semigroup Forum \vol
45\yr 1992\pages 385--394\endref
\ref\key DK3\by DUCHAMP, G., KROB, D.\paper Factorisations dans le 
mono\"\i de partiellement commutatif libre\jour
C. R. Acad\. Sci\. Paris S\'er.~I Math\.\vol  312 \yr 1991\pages
189--192\endref 
\ref\key DK4\by DUCHAMP, G., KROB, D.\paper Free partially commutative
structures\jour  J. Algebra\vol  156\yr 1993\pages 318--361\endref
\ref\key DK5\by DUCHAMP, G., KROB, D.\paper Lazard's factorizations of
free partially commutative monoids\inbook  Automata, languages and
programming (Madrid, 1991)\pages 242--253\publ Lecture Notes in
Comput\. Sci\., 510, \publaddr Springer, Berlin\yr 1991 \endref
\ref\key DT\by DUCHAMP, G., THIBON, J.-Y.\paper Decidable orderings
for free groups\jour manuscrit, 1991\endref
\ref\key HK\by HARJU, T., KARHUM\"AKI, J.\paper The equivalence
problem of multitape finite automata\jour  Theoret\. Comput\. Sci\.\vol  78
\yr 1991\pages 347--355 \endref
\ref\key K\by KROB, D.\paper L'alg\`ebre de Lie partiellement
commutative libre\jour Rapport LITP~90.74\endref
\ref\key laz\by LAZARD, M.\book Groupes, anneaux de Lie et probl\`eme
de Burnside\publ Inst\. Math\. dell\. Univ\. Roma\yr 1960\endref
\ref\key La\by LALONDE, P.\book Contributions \`a l'\'etude des
empilements\publ Publications du LACIM~4, UQAM Montr\'eal\yr 1991\endref
\ref\key Lo\by LOTHAIRE, M.\book Combinatorics on words\publ
Addison--Wesley \yr 1983\endref
\ref\key MKS\by MAGNUS, W., KARRASS, A., SOLITAR, D.\book
Combinatorial group theory\bookinfo Second revised edition\publ 
Dover Publications, Inc.\publaddr New York\yr 1976\endref
\ref\key Mu\by MURA, R.B., RHEMTULLA, A.\book Orderable groups\publ
Marcel Dekker\yr 1977\endref
\ref\key Neu\by NEUMANN, B.H.\paper  On ordered division rings\jour
Trans\. Amer\. Math\. Soc\.\vol 66 \yr 1949\pages 202--252\endref
\ref\key T\by THIBON, J.-Y.\paper  Integrit\'e des
alg\`ebres de s\'eries formelles sur un alphabet partiellement
commutatif\jour  Theoret\. Comput\. Sci\.\vol  41\yr 1985\pages
109--112\endref 
\ref\key Va\by VARRICCHIO, S.\paper  On the decidability of the
equivalence problem for partially commutative rational power series\jour
Theoret\. Comput\. Sci\.\vol 99 \yr 1992\pages 291--299\endref
\ref\key Vi\by VIENNOT, G.X.\paper Heaps of pieces. I. Basic
definitions and combinatorial lemmas\inbook  Graph theory and its
applications: East and West (Jinan, 1986)\pages  542--570\publ Ann. New York
Acad. Sci., 576\publaddr New York Acad. Sci., New York\yr 1989 \endref
\ref\key Z\by ZEILBERGER, D.\paper Identities in search of
identity\jour Theoret\. Comput\. Sci\.\vol  117\yr 1993\pages 23--38\endref 
\endRefs

\end







