Dgk.tex
% Ceci est le fichier PlainTeX de l'article
% "Groupes de Garside", precedemment initule
% "Petits groupes gaussiens"; cette version remplace
% celle transmise en mars 2001

\magnification1000
\tolerance 3000
\hsize = 125mm
\vsize= 200mm
\hoffset-0truecm
\voffset-1truecm
\overfullrule=0pt
\parindent=10pt

\font\VII=cmr7 
\font\sc=cmr10
\font\go=eufm10

\catcode`\�=\active\def�{\c c}        % option c
\catcode`\�=\active\def�{\"a}        % option u, then  a
\catcode`\�=\active\def�{\"e}        % option u, then  e
\catcode`\�=\active\def�{\"{\i}}     % option u, then  i
\catcode`\�=\active\def�{\"o}        % option u, then  o
\catcode`\�=\active\def�{\"u}        % option u, then  u
\catcode`\�=\active\def�{\"y}        % option u, then  y
\catcode`\�=\active\def�{\'e}        % option e, then  e
\catcode`\�=\active\def�{\'E}        % option e, then  E
\catcode`\�=\active\def�{\`a}        % option `, then  a
\catcode`\�=\active\def�{\`e}        % option `, then  e
\catcode`\�=\active\def�{\`u}        % option `, then  u
\catcode`\�=\active\def�{\`A}        % option `, then  A
\catcode`\�=\active\def�{\^a}        % option i, then  a
\catcode`\�=\active\def�{\^e}        % option i, then  e
\catcode`\�=\active\def�{\^{\i}}     % option i, then  i
\catcode`\�=\active\def�{\^o}        % option i, then  o
\catcode`\�=\active\def�{\^u}        % option i, then  u
\catcode`\�=\active\def�{\oe }        % option i, then  u

\catcode`\:=\active\catcode`\!=\active\catcode`\?=\active
\catcode`\:=\active\def:{\penalty500\hskip2pt\string:}
\catcode`\!=\active\def!{\penalty500\hskip2pt\string!}
\catcode`\?=\active\def?{\penalty500\hskip2pt\string?}
\frenchspacing

\font\cyrIX=wncyr9
\def\<<{\penalty-500{\cyrIX\char'074}\penalty500}
\def\>>{\penalty500{\cyrIX\char'076\ }\penalty-500}

\def\resp{{\it resp. }}
\def\Block{\hbox{\vrule width 7pt height 7pt depth 0pt}}

\newcount\SecNo
\SecNo=0
\newcount\PropNo
\newcount\EqNo

% COMMENT: \Displaylines and \Eqalign are similar to TeX's
% standard \displaylines and \eqalign, excepted that each line
% can receive an equation number, by using a second & sign.
% The boolean \Displaylines is true inside a \Displaylines or
% \Eqalign group.

\newif\ifDisplaylines\Displaylinesfalse
{\catcode`\@=11
\gdef\Displaylines#1{\Displaylinestrue\displ@y\halign{
\hbox to\displaywidth{$\@lign\hfil\displaystyle##\hfil$}%
&\llap{$##$}\crcr#1\crcr}}
\gdef\Eqalign#1{\Displaylinestrue\displ@y \tabskip=\centering
\halign to \displaywidth{\hfil$\@lign\displaystyle{##}$\tabskip=0pt
&$\@lign\displaystyle{{}##}$\hfil\tabskip=\centering
&\llap{$\@lign##$}\tabskip=0pt\crcr#1\crcr}}}


% COMMENT: cross-reference system. To give give a name or a
% number to a formula or a proposition. The command \�54�
% causes the content of \box0 to be stored in \box54, and then
% �54� lets this content be printed. Similarly \�\name� does 
% the same with a box named \name, and �\name� lets it be
% printed. These are the only possible parameters, namely a
% number (between 1 and 255, preferably between 100 and 255),
% or a command name, i.e., \ followed by letters.

\catcode`\�=\active
{\catcode`\@=11
\gdef\�#1#2�{\ifcat\noexpand#1\noexpand\%
\global\alloc@4\box\chardef\insc@unt{#1#2}\fi%
\global\setbox#1#2\box0\ignorespaces}}
\def�#1�#2{\leavevmode\copy#1\ifcat#2a\ \fi#2}

\def\Sec#1\par{\vskip0pt plus.2\vsize
\penalty-250\vskip0pt plus-.2\vsize 
\advance\SecNo by 1\global\PropNo=0\global\EqNo=0
\vskip30pt\centerline{\sc\the\SecNo. #1}}

\def\Parag#1\par{\vskip0pt plus.1\vsize
\penalty-250\vskip0pt plus -.1\vsize
\bigbreak{\bf #1}}

\def\Def{\global\advance\PropNo by 1%
\setbox0=\hbox{\the\SecNo.\the\PropNo}%
\bigbreak{\bf D�finition \the\SecNo.\the\PropNo.} \ignorespaces}

\def\Rem{\bigbreak{\bf Remarque. }}

\def\Conj{\global\advance\PropNo by 1%
\setbox0=\hbox{\the\SecNo.\the\PropNo}%
\bigbreak{\bf Conjecture \the\SecNo.\the\PropNo.} \ignorespaces}

\def\Question{\global\advance\PropNo by 1%
\setbox0=\hbox{\the\SecNo.\the\PropNo}%
\bigbreak{\bf Question \the\SecNo.\the\PropNo.} \ignorespaces}

\def\Cor{\global\advance\PropNo by 1%
\setbox0=\hbox{\the\SecNo.\the\PropNo}%
\bigbreak{\bf Corollaire \the\SecNo.\the\PropNo.} \ignorespaces}

\def\Ex{\global\advance\PropNo by 1%
\setbox0=\hbox{\the\SecNo.\the\PropNo}%
\bigbreak{\bf Exemple \the\SecNo.\the\PropNo.} \ignorespaces}

\def\Lem{\global\advance\PropNo by 1%
\setbox0=\hbox{\the\SecNo.\the\PropNo}%
\bigbreak{\bf Lemme \the\SecNo.\the\PropNo.} \ignorespaces}

\def\Prop{\global\advance\PropNo by 1%
\setbox0=\hbox{\the\SecNo.\the\PropNo}%
\bigbreak{\bf Proposition \the\SecNo.\the\PropNo.} \ignorespaces}

\def\Dem{\bigbreak{\it D�monstration. }}

\def\Eq{\global\advance\EqNo by 1
\global\setbox0=\hbox{\rm(\the\SecNo.\the\EqNo)}
\ifDisplaylines&\copy0\else\eqno{\copy0}\fi}

\def\FinDem\par{{\unskip\nobreak\hfil\penalty50%
\hskip1em\hbox{}\nobreak\Block
\parfillskip=0pt\finalhyphendemerits=0\par}}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% List processing
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

								% COMMENT: \rank(#1#2) writes the rank of the first
								% occurrence of the token #1 in the token list #2 (0 if #1 
								% does not occur.

\newif\iffound
\def\rank#1#2{{\foundfalse\count0=0 \getrank#1#2\end
\iffound\number\count0\else0\fi}} 
\def\getrank#1#2{\ifx#2\end\def\next#1{\relax}%
\else\iffound\else\advance\count0 by1\fi\let\next=\getrank
\ifx#2#1\foundtrue\fi\fi\next#1}

								% COMMENT: \List{ \a \b \c .... } causes \\\x to print the
								% rank of \x in the above list.  This strange macro is very
								% useful for references: one declares a list of references
								% at the beginning of the paper, and then typing a
								% reference with \\ in front gives the number of that
								% reference. In particular this automatically changes the
								% numbers when references are added or deleted.       					

\def\List#1{\def\\##1{\def##1{##1}\rank{##1}{#1}}}

\def\Ref#1; #2; #3; #4\par{\smallskip\noindent
\item{ [#1]}{\sc #2}, {\sl #3}, #4\par}
\def\Reff#1; #2; #3; #4; #5; #6; #7\par{\smallskip\noindent
\item{ [#1]}{\sc #2}, {\sl #3}, #4 {\bf #5} (#6) #7\par}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 9. Basic Postscript Commands
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

									% COMMENT: These TeX commands code for postcript
         					% commands and are used to describe simple drawings.
                    % All measures are in millimeters. The recommended
                    % syntax is to use a graphic box for each picture. Note
                    % that there is no PS previewer on Macintosh, and therefore
                    % the result of PS commands will not appear on the screen.
                    % However \Write is NOT a PS command.
                    % A typical example, where an external picture called "figure1"
                    % is inserted (from the file ....pictures)
                    %         $$\OpenGraphicBox width 65mm height 30mm depth 0mm;
                    %         \leavevmode\special{picture figure1 scaled 500} 
                    %         \Translate(0, 0);
                    %         \Write(35, 31, $i$);
                    %         \Write(42, 31, $i+1$);
                    %         \Write(-7, 25, $\s_i$);
                    %         \Write(-8, 10, $\s_i^{-1}$);
                    %         \CloseGraphicBox$$

\newdimen\Dwidth
\newdimen\Dheight
\newdimen\Ddepth

\def\OpenGraphicBox width#1 height#2 depth#3;
{\dimen100=\parindent\parindent=0pt
\Dwidth=#1\Dheight=#2\Ddepth=#3
\dimen104=\Dheight\advance\dimen104 by \Ddepth
\catcode`\;=14\leavevmode
\raise-\Ddepth\vbox to\dimen104\bgroup\hsize=\Dwidth
\vglue\Dheight}

\def\Translate(#1, #2){\dimen105=-#2mm\vglue\dimen105\hskip#1mm}

\def\CloseGraphicBox{\vfill\egroup\parindent=\dimen100\catcode`\;=12}

\def\Write(#1, #2, #3){\rlap{\smash{\raise#2mm\hbox{\kern#1mm #3}}}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\let\( = \langle 
\let\) = \rangle
\def\;{\, ; \,}

\def\card{{\rm card}}
\def\CCI{*}
\def\CCII{**}
\def\cl#1{\overline{\vrule height 5.5pt width 0pt #1}}
\def\cL{\mathord{/}}
\def\cLf{\cL_{\scriptscriptstyle \!\!\tilde f}\,}
\def\comp{\mathbin{\scriptscriptstyle\circ}}
\def\cR{\mathord{\backslash}}
\def\cRf{\cR_{\scriptscriptstyle f}}

\let\D=\Delta
\def\df{d_{\scriptscriptstyle f}\!}
\def\DivL{{\rm Div}}
\def\Dom{{\rm Dom}}
\def\dL{{}^*\hskip-0.4pt}
\def\DR{\Til D}

\let\e=\varepsilon
\def\eqf{\mathrel{\mathstrut\equiv}_{\!\scriptscriptstyle f}^{\!\scriptscriptstyle}}
\def\eqfp{\mathrel{\mathstrut\equiv}_{\!\scriptscriptstyle f}^{\!\scriptscriptstyle +}}
\def\eqfpp{\mathrel{\mathstrut\equiv}_{\!\scriptscriptstyle f}^{\!\scriptscriptstyle +\!+}}

\let\f = \phi
\def\fL{\phi_{\!\scriptscriptstyle L}}
\def\fR{\phi_{\!\scriptscriptstyle R}}
\def\Fr(#1){G_{\!_{#1}}}

\let\g=\gamma
\let\G=\Gamma
\def\GG(#1; #2){\langle #1; {#2}\rangle}
\def\gL{\mathbin{{\scriptstyle\wedge}}}
\def\gR{\mathbin{\Til{\scriptstyle\wedge}}}
\def\Gr#1{\(#1\)}

\let\Hat=\widehat

\def\id{{\rm id}}
\def\ii{^{-\!1}}
\let\ince=\subseteq

\def\jL{\mathbin{\Til{\scriptstyle\vee}}}
\def\jLf{\mathbin{\jL_{\!\scriptscriptstyle \tilde f}}}
\def\jR{\mathbin{\scriptstyle\vee}}
\def\JR{\mathbin{\bigvee}}
\def\jRf{\mathbin{\jR_{\!\scriptscriptstyle f}}}
\def\Mon#1{\(#1\)^{\scriptscriptstyle +}}
\def\MRf{\( X \; \Rf \)^{\scriptscriptstyle +}}
\def\Mo(#1){{\rm Mo}(#1)}

\let\n = \nu
\def\norm(#1){\vert\!\vert#1\vert\!\vert}
\def\NR{\Til N}

\let\o = \omega
\let\O = \Omega
\def\oL{\perp}
\def\om{\mathord{\cdot}}
\def\op{}
\def\oR{\mathrel{\Til\perp}}

\def\pp{\hbox{$\ldots$}}
\let\ppp=\cdots

\def\QQ{{\bf Q}}
\def\quot{\!/\!}

\let\ra=\rightarrow
\def\Rf{R_{\! f}}

\let\s=\sigma
\def\S{\Sigma}
\def\spe(#1){\mathbin{\mathstrut\equiv}_{\!\scriptscriptstyle
f, Y}^{(#1)}}
\def\SPE{\mathbin{\mathstrut\equiv}_{\!\scriptscriptstyle f, Y}^{\scriptscriptstyle +++}}
\def\Sym{\hbox{\go S}}

\let\Til=\widetilde

\def\vLf{\mathrel{\Til{\vR}_{\scriptscriptstyle \!\tilde f}}}
\def\vR{\mathrel{\hbox{\sb\char'171}}}  % reversing relation
\def\vR{\rightarrow}  % reversing relation
\def\vRf{\vR_{\scriptscriptstyle \!f}}
\def\vv{\hskip-1pt\raise5pt\hbox{$\scriptscriptstyle\vee$}}

\def\WX{\Mo(\Sigma \cup \Sigma\ii)}
 
\hyphenation{par-ti-cu-lier se-con-de}

      
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\List{\Adj \Adk \BaM \BDM \BrS \BMR \BuM \Cha \Chb \ClP
\Dfa \Dfb \Dff \Dfz \Dgc \Dgd \Dfx \Dlg \ElM \Eps \Gar \Mic
\Pic \Pid \Rmm \Tat \Thu}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\vskip 1 true cm 

\centerline{\bf GROUPES DE GARSIDE}

\bigskip\centerline{Patrick DEHORNOY}

\vskip 1 true cm 

{\narrower{\bf Abstract}. Define a Garside monoid
to be a cancellative monoid where right and left lcm's exist and
that satisfy additional finiteness assumptions, and a Garside
group to be the group of fractions of a Garside monoid.
The family of Garside groups contains the braid groups,
all spherical Artin groups, and various generalizations
previously considered\footnote{$^1$}{In particular, the
Garside groups considered in~[\\\Dfx] are special cases of
those considered here; the latter had been called "small
Gaussian" in earlier works; the name has been changed in
order to uniformize the terminology with works by Bessis,
Charney, Michel, and other authors}. Here we prove that
Garside groups are biautomatic, and that being a Garside
group is a recursively enumerable property, i.e., there exists an
algorithm constructing the (infinite) list of all small Gaussian
groups. The latter result relies on an effective, tractable
method for recognizing those presentations that define a 
Garside monoid.
\par}

{\narrower\bigskip{\bf R�sum�}. Les mono�des de Garside
sont introduits comme mono�des simplifiables o� existent
ppcm et pgcd et o� sont satisfaites des conditions convenables
de finitude, et les groupes de Garside comme groupes de
fractions de mono�des de Garside. La famille des groupes
de Garside  contient les groupes de tresses, les groupes d'Artin
sph�riques, et diverses g�n�ralisations consid�r�es
ant�rieurement\footnote{$^2$}{En particulier, les groupes de
Garside introduits dans~[\\\Dfx] sont un cas particulier de
ceux consid�r�s ici, qui, eux, avaient �t� appel�s petits
groupes gaussiens; ce changement de nom a �t� 
d�cid� afin d'uniformiser la terminologie avec d'autres
travaux r�cents de Bessis, Charney, Michel, entre autres.}.
Dans cet article, nous montrons que les groupes de Garside
sont bi-automatiques, et qu'�tre un groupe de Garside est une
propri�t� r�cursivement �num�rable, c'est-�-dire qu'il existe
un algorithme �num�rant la liste infinie de tous ces groupes.
Ce r�sultat repose sur une m�thode effective pour reconna�tre
les pr�sentations des mono�des de Garside.\par}

{\narrower\bigskip Key words: Presentations of monoids
and groups; word problem; rewriting systems; Cayley graph;
braid groups; Artin groups.

\bigskip MSC 2000: 20M05, 20F36, 05C25, 68Q42.\par}

\vskip 1 true cm


 L'objet de cet article est l'�tude par des m�thodes alg�briques et
combinatoires d'une classe de groupes, appel�s groupes de Garside, qui contient en parti\-culier  les groupes de tresses
classiques, tous les groupes d'Artin sph�riques, et
diverses extensions de ces groupes pr�c�demment introduites.
Les groupes de Garside sont d�finis comme groupes de
fractions des mono�des de Garside, ces derniers �tant
d�finis par l'existence de notions convenables de plus petit
commun multiple (ppcm) et de plus grand commun diviseur
(pgcd), et la satisfaction de conditions de noeth�rianit� et de
g�n�ration finie. On d�montre ici:

\bigskip {\bf Th�or�me A.} {\sl Tout groupe de Garside est
bi-automatique.}

\bigskip {\bf Th�or�me B.} {\sl Etre un groupe de Garside et un 
mono�de de Garside sont des propri�t�s~$\S_1^0$,
c'est-�-dire r�cursivement �num�rables.}

\bigskip Le th�or�me~A, qui r�sout positivement une
conjecture de~[\\\Dfx] (�nonc�e en termes de petit groupe
gaussien), implique en particulier que tout groupe de Garside
a un probl�me de mot et un probl�me de conjugaison
d�cidables, et qu'il satisfait une in�galit� isop�rim�trique
quadratique.

Le th�or�me~B signifie qu'il existe un algorithme (th�orique) qui
�num�re syst�matiquement toutes les pr�sentations de groupes
 de Garside et de mono�des de Garside. Il
repose sur l'existence d'un crit�re effectif caract�risant
certaines pr�sentations des mono�des de Garside.
Plus pr�cis�ment, il existe des conditions explicites~$(\CCII)$
de complexit�~$\S_1^0$ telle qu'on ait les r�sultats suivants,
dont les termes seront d�finis plus bas:

\bigskip {\bf Th�or�me B'.} {\sl (i) Si $M$ est un mono�de de Garside, et si $f$ est un s�lecteur de ppcm
sur une partie g�n�ratrice~$\Sigma$ de~$M$, alors $M$ admet la
pr�sentation compl�ment�e~$\Mon{\Sigma; \Rf}$, et celle-ci
satisfait  aux conditions~$(\CCII)$.

(ii) Inversement, si $\Mon{\Sigma; \Rf}$ est une pr�sentation
compl�ment�e satisfaisant aux conditions~$(\CCII)$, alors le
mono�de qu'elle d�finit est un mono�de de Garside, et
$f$ est un s�lecteur de ppcm sur~$\Sigma$.}

\bigskip Si la d�monstration du th�or�me~B', qui occupe
la plus grande partie de l'article, est assez d�licate, les
conditions~$(\CCII)$ qu'il met en jeu sont simples, et, en
particulier, leur implantation sur ordinateur est
ais�e. La conjonction des th�or�mes~A et~B' permet
donc  de construire de nombreux exemples de groupes
automatiques.

\bigskip Les propri�t�s alg�briques des groupes de tresses et de leurs
extensions ont fait l'objet de nombreux travaux. Dans le cas des
groupes de tresses, la plupart des r�sultats classiques sur les
probl�mes de mots et de conjugaison, les formes normales, et
l'automaticit� sont pr�sents ou implicites dans les travaux de Garside
[\\\Gar] et Thurston [\\\Thu] --- voir aussi [\\\Adk] [\\\ElM].
On sait que les m�thodes et les r�sultats s'�tendent � des
classes de groupes plus vastes: groupes d'Artin sph�riques
[\\\BrS] [\\\Dlg] [\\\Cha] [\\\Chb], groupes des tresses des
groupes de r�flexions complexes [\\\BMR], groupes de
Garside au sens de~[\\\Dfx] et~[\\\BDM] --- qu'on appellera
ici \<<groupes de Garside au sens restreint\>>. La classe des
groupes de Garside consid�r�s ici, et introduits dans~[\\\Dfx]
sous l'appellation \<<petits groupes gaussiens\>>, inclut
strictement toutes les classes pr�c�dentes. Par exemple, les
groupes $\Gr{a  , b  \; a  b^pa   = b^q}$ sont pour $q \ge p
\ge 1$ des groupes de Garside n'appartenant � aucune des
familles pr�c�dentes.

Un groupe de Garside est le groupe de fractions d'un
mono�de dans lequel existe une bonne th�orie de la
divisibilit� et des ppcm (la d�finition pr�cise sera
donn�e au d�but de la section~1). D�j� relev�e chez Garside et
Deligne, l'importance des ppcm dans les mono�des de tresses a
�t� d�gag�e explicitement par Thurston dans la construction de
formes normales et, de l�, de structures automatiques [\\\Thu]
[\\\Eps], et elle est au centre de l'�tude d�velopp�e
dans~[\\\Dfx] pour les groupes dits de Garside. En un sens, le
th�or�me~A n'est qu'une extension naturelle du r�sultat
analogue �tabli dans~[\\\Dfx] pour les groupes de Garside au
sens restreint, lequel ne fait que reprendre l'argument
de~[\\\Chb] pour les groupes d'Artin sph�riques, qui, � son
tour, n'est qu'une adaptation de l'argument original
de~[\\\Thu]. Le point nouveau consiste ici � s'affranchir d'une
hypoth�se technique superflue incluse dans la d�finition des
groupes de Garside au sens restreint, � savoir la propri�t�
(v�rifi�e dans le cas des tresses et des groupes d'Artin) que
l'�l�ment fondamental~$\D$ est le ppcm des g�n�rateurs
minimaux. L'int�r�t de la pr�sente approche ne tient pas tant �
l'affaiblissement des hypoth�ses obtenu qu'� l'argument
utilis� pour �tablir le r�sultat, � savoir l'utilisation
syst�matique des compl�ments: si $M$ est un mono�de
admettant la simplification � gauche, et o� deux �l�ments
quelconques admettent un unique ppcm � droite, nous
appellerons {\it compl�ment} (� droite) de~$x$ dans~$y$, et
noterons~$x  \cR y$, l'unique �l�ment~$z $ tel que
$x z $ est le ppcm � droite de~$x$ et~$y$. L'�tude
pour elles-m�mes de l'op�ration~$\cR$ et de sa contrepartie �
gauche~$\cL$ semble nouvelle. Nous montrons ici comment
construire � l'aide de ces op�rations des formes normales
explicites et des structures automatiques. De telles
constructions sont d�j� pr�sentes dans~[\\\Thu] et~[\\\Eps]
dans le cas des tresses, et le passage aux groupes de Garside serait une extension facile si  toutes les hypoth�ses
avaient �t� conserv�es. La t�che en fait n'est pas si ais�e, car
les constructions initiales utilisaient au moins trois conditions
que nous �liminons ici: pr�servation de la longueur dans les
relations d�finissant le groupe, existence d'une structure de
groupe de Coxeter sous-jacente (le groupe sym�trique et ses
op�rations de treillis dans le cas des tresses), centralit� de
l'�l�ment~$\D^2$. S'affranchir de telles hypoth�ses exige de
reprendre l'�tude du d�but, avec des arguments et un
encha�nement diff�rents, tout en aboutissant � des
d�monstrations plus simples et naturelles que celles
de~[\\\Cha] et~[\\\Dfx].  Il semble donc que les groupes de Garside constituent un cadre bien adapt�, ce que confirment
d'autres travaux r�cents: [\\\Dfz], o� il est montr� que les
groupes de Garside, et, plus g�n�ralement, les groupes
gaussiens sont sans torsion, [\\\Pic], o� est adapt�e la solution
du probl�me de conjugaison d�crite par Morton et ElRifai
[\\\ElM] dans le cas des tresses, [\\\Pid], o� il est montr� que
tout groupe de Garside se d�compose en produit crois� de
groupes de Garside avec centre monog�ne.

Sauf dans des cas triviaux, il est tr�s difficile de reconna�tre les
propri�t�s combinatoires d'un groupe � partir d'une pr�sentation, et de
nombreux r�sultats d'ind�cidabilit� sont connus~[\\\BaM]. Il existe
en particulier tr�s peu de crit�res permettant de reconna�tre qu'un
mono�de se plonge dans le groupe de m�me pr�sentation [\\\Adj]
[\\\Rmm], et on sait que la preuve d'un tel r�sultat par Garside dans
le  cas des groupes de tresses est � l'origine de la plupart des
d�veloppements alg�briques ult�rieurs sur ces groupes. Le
th�or�me~B repose sur une nouvelle m�thode dans cette
direction. L'outil essentiel utilis� ici est une op�ration
combinatoire sur les mots appel�e {\it redressement}.
Introduite dans~[\\\Dfa], et consid�r�e sous une forme
similaire dans~[\\\Tat], puis �tudi�e syt�matiquement
dans~[\\\Dff], cette op�ration est une contrepartie syntaxique
� l'op�ration de compl�ment: � partir d'une certaine
fonction~$f$ d�termin�e par la pr�sentation lorsque celle-ci
est d'un certain type dit compl�ment�, le redressement permet
de d�finir une op�ration binaire~$\cRf$ sur les mots de sorte
que, si $M$ est un mono�de engendr� par un
ensemble~$\Sigma$, et si $u, v$ sont des mots sur~$\Sigma$
repr�sentant respectivement les �l�ments~$x$ et~$y$ de~$M$,
alors le mot~$u \cRf v$ repr�sente l'�l�ment~$x  \cR
y$, sous la condition que la fonction~$f$, c'est-�-dire la
pr�sentation consid�r�e, v�rifie une certaine condition dite
propri�t� du cube, d�j� implicite dans le th�or�me~H
de~[\\\Gar]. Il a �t� montr� dans~[\\\Dfx] que tous les
groupes de Garside admettent une pr�sentation
compl�ment�e, et, r�ciproquement, on y a donn� des
conditions suffisantes pour qu'une pr�sentation
compl�ment�e d�finisse un groupe de Garside. Ces conditions
au demeurant sont d'int�r�t pratique limit�, car elles
n�cessitent d'une part d'�tablir la noeth�rianit� d'une relation
et, d'autre part, de v�rifier la propri�t� du cube pour une
infinit� de mots: dans les deux cas, il s'agit de conditions de
type infinitaire (conditions respectivement~$\Pi_1^1$ et
$\Pi_1^0$ dans le langage de la th�orie de la r�cursivit�, 
c'est-�-dire mettant en jeu une quantification universelle
portant respectivement sur les suites de mots et les mots).
Dans certains cas particuliers, comme celui des tresses et, plus
g�n�ralement, lorsque les relations de la pr�sentation
consid�r�e pr�servent la longueur, la condition de
noeth�rianit� est triviale, et la propri�t� du cube se r�duit �
une v�rification finie, qui constitue le travail de Garside
dans~[\\\Gar]. Notre travail ici consiste � montrer que, dans le
cas g�n�ral, la condition de noeth�rianit� peut �tre d�duite de
conditions effectives plus faibles, et qu'il est suffisant de
v�rifier la propri�t� du cube pour des triplets de mots pris
dans un certain ensemble fini. De la sorte, et comme �nonc�
dans le th�or�me~B', nous obtenons un crit�re algorithmique
--- et simple: si, par exemple, nous entrons la
pr�sentation standard d'un mono�de de tresses dans
l'algorithme, celui-ci r�pondra en un temps fini qu'il
s'agit d'un mono�de de Garside, et il fournira une
description explicite d'une structure automatique. Le
prix � payer pour ces r�sultats est une analyse fine du
processus de redressement des mots --- lequel jouait
d�j� un r�le technique essentiel dans la construction
d'un ordre total sur les tresses~[\\\Dgd].

\bigskip Le plan de l'article est le suivant. Dans la section~1, nous
d�finissons les notions de mono�de de Garside et
de groupe de Garside; nous �tablissons des propri�t�s de base
des op�rations de compl�ment, et nous d�crivons  un treillis fini
attach� � chaque mono�de de Garside et qui le caract�rise.
Dans la section~2,  on �tablit des formules de dualit� reliant
les op�rations
 de ppcm, pgcd, et compl�ment � gauche et � droite dans tout mono�de de Garside. En fait, on travaille ici dans un cadre plus
g�n�ral: ainsi, on obtient � la fois des formules de dualit� utiles pour la
preuve du th�or�me~A, et une caract�risation des mono�des de Garside par des hypoth�ses plus faibles (mais moins naturelles) que
celles de la d�finition initiale, lesquelles seront prises comme
point de d�part pour la preuve du th�or�me~B'. Dans la
section~3, on d�montre le th�or�me~A. Gr�ce au
pgcd, on d�finit une forme normale unique pour les �l�ments
de tout groupe de Garside: cette forme, la \<<mixed
canonical form\>> de~[\\\Eps], est bien
connue dans le cas des tresses, le point sp�cifique ici �tant la
simplicit� de la preuve d'automaticit�, ainsi que la possibilit�
de construire effectivement des automates (ou des
transducteurs) calculant les formes normales. En particulier,
on montre comment calculer le pgcd � gauche {\it et} le pgcd �
droite avec l'�l�ment~$\D$ au moyen d'un automate dont les
�tats sont des fonctions sur la cl�ture des atomes par
compl�ment (et non des diviseurs de~$\D$ ainsi qu'il est
classique pour le pgcd � gauche). Dans la section~4, on montre
que tout groupe de Garside admet une pr�sentation de
forme syntactique parti\-culi�re, dite compl�ment�e, et que
toutes les op�rations du mono�de, ppcm, pgcd, compl�ments,
peuvent se calculer � partir de l'op�ration de redressement
des mots d�duite de la pr�sentation. Ceci donne en particulier
une solution effective au probl�me de mot (du mono�de et du
groupe). Dans la section~5, et gr�ce � la caract�risation de la
section~2, on montre que les pr�sentations compl�ment�es
de groupes de Garside satisfont � certaines conditions
n�cessaires et suffisantes, dont la propri�t� du cube.
A ce stade, le th�or�me~B' n'est pas �tabli, car le crit�re
obtenu requiert de v�rifier la propri�t� du cube
pour tous les triplets de mots: l'objet de la
section~6 est alors de montrer qu'il suffit d'effectuer cette
v�rification pour un ensemble fini de mots, � savoir la
cl�ture des g�n�rateurs par l'op�ration~$\cRf$. Ceci
�tablit le r�sultat cherch�, et fournit un crit�re
pratique, ainsi que l'illustre un exemple.

\bigskip Si $\Sigma$ est un alphabet, et $R$ une famille de relations
sur~$\Sigma$, c'est-�-dire une famille de paires de mots sur~$\Sigma$, nous
noterons $\Mon{\Sigma \; R}$ le mono�de engendr� par~$\Sigma$ et
pr�sent� par les relations~$R$, et $\Gr{\Sigma \; R}$ le groupe
correspondant.

\bigskip L'auteur remercie Matthieu Picantin
pour ses remarques judicieuses. 


\Sec Calcul des compl�ments

\bigskip Si $M$ est un mono�de, et $x$, $y$ des �l�ments
de~$M$, on dira que $x$ est diviseur � gauche de~$y$, ou, de
fa�on �quivalente, que $y$ est multiple � droite de~$x$, s'il
existe~$z $ v�rifiant~$x  z  = y$; on parlera de diviseur ou de
multiple propre si, en outre, on a~$z  \not= 1$. De l� une
notion naturelle de plus petit multiple commun (ppcm) �
droite: $z $ est un ppcm � droite de~$x$ et~$y$ si
$z $ est un multiple � droite de~$x$ et de~$y$, et un diviseur
� gauche de tout multiple � droite commun �~$x$ et~$y$. De
la m�me fa�on, $z $ est un plus grand commun diviseur �
gauche, ou pgcd � gauche, de~$x$ et~$y$ si $z $ est un
diviseur � gauche de~$x$ et~$y$, et un multiple � droite de
tout diviseur � gauche commun �~$x$ et~$y$.

Il n'y a en g�n�ral aucune raison pour qu'un ppcm~$z $
de~$x$ et~$y$, s'il existe, soit unique, non plus
que l'�l�ment~$y '$ v�rifiant $z  = x  y '$. Cependant,
des conditions assez faibles garantissent cette unicit�.

\Lem\�\Uniqueness�
{\sl Soit $M$ un mono�de simplifiable �
gauche o� $1$ est le seul �l�ment inversible. Alors la
relation \<<�tre un diviseur � gauche propre\>> est un
ordre partiel sur~$M$, et les ppcm � droite et pgcd � 
gauche de deux �l�ments sont uniques quand ils existent.}

\Dem Par hypoth�se, la conjonction de $x  \not= 1$ et $y 
\not= 1$ implique $x y  \not= 1$ dans~$M$, donc la
relation \<<�tre un diviseur � gauche propre\>> est
transitive; que $M$ soit simplifiable � gauche entra�ne que
cette relation est irr�flexive, et c'est donc un ordre (strict).
Quand ils existent, le ppcm � droite et le pgcd � gauche de
deux �l�ments~$x , y$ sont la borne sup�rieure et la
borne inf�rieure de~$x$ et~$y$ dans l'ordre
ci-dessus.\FinDem

\Def Sous les hypoth�ses du lemme pr�c�dent, nous
noterons $x  \jR y$ le ppcm � droite de~$x$ et~$y$, quand il
existe; dans ce cas, l'unique �l�ment~$z $ v�rifiant $x  \jR
y  = x  z $ sera not�~$x  \cR y$, lu \<<$x$
sous~$y$\>>, et appel� {\it compl�ment � droite} de~$y$
sur~$x$. 

\bigskip On a donc
$$x  \jR y  = x  \op (x  \cR y ) = y  \op (y  \cR x ) \Eq\�100�$$
d�s que $x  \jR y$ est d�fini. De fa�on sym�trique (donc sous
l'hypoth�se que le mono�de est simplifiable � droite), nous
notons $x  \jL y$ le ppcm � gauche de~$x$ et~$y$ quand il
existe, et $x  \cL y$ l'unique �l�ment~$z $ v�rifiant
$x  \jL y  = z  x$. La contrepartie de~�100� est alors
$$x  \jL y  = (x  \cL y ) \op y  = (y  \cL x ) \op x 
\Eq\�200�$$ 
(Figure~1.1). Noter que $x$ est un diviseur � gauche
de~$y$ si et seulement si
$y  \cR x$ est d�fini et �gal �~$1$: dans ce cas, $x  \cR
y$ est le quotient~\<<$x \ii y$\>> et, de m�me, $x 
\cL y$ est le quotient~\<<$x  y \ii$\>> dans le cas o�
$y$ est un diviseur � droite de~$x$ --- ce qui explique et
justifie nos notations.

\midinsert
$$\OpenGraphicBox width 80mm height 30mm
depth0mm;
\leavevmode\special{illustration prod4.eps}
\CloseGraphicBox$$ 
\centerline{{\bf Figure 1.1.} Compl�ment � droite et � gauche}
\endinsert

L'objet de notre �tude est la famille des mono�des appel�s  gaussiens
dans~[\\\Dfx] et~[\\\Dfz]. Ceux-ci sont d�finis en termes de ppcm et
de pgcd: essentiellement, un mono�de gaussien est un mono�de avec
uniques ppcm et pgcd � droite et � gauche, et un mono�de de Garside est un mono�de gaussien satisfaisant une condition forte de
g�n�ration finie. Pour une d�finition pr�cise, nous aurons besoin
d'une notion suppl�mentaire:

\Def
Soit $M$ un mono�de. On dit qu'un �l�ment~$x$ de~$M$
est un {\it atome} si  $x$ est  distinct de~$1$ et que $x  =
y z $ entra�ne $y  = 1$ ou $z  = 1$. On dit que $M$ est
{\it atomique} si $M$ est engendr� par ses atomes et si, de
plus, pour tout~$x$ dans~$M$, la {\it
norme}~$\norm(x )$ de~$x$, d�finie comme la borne
sup�rieure des longueurs des d�compositions de~$x$ en
produit d'atomes, est finie.

\bigskip On remarquera que $1$ est n�cessairement le seul
�l�ment inversible dans un mono�de atomique, puisque,
par d�finition, on a $\norm(x  y ) \ge \norm(x ) +
\norm(y )$ pour tous~$x , y$, et $\norm(x ) \ge 1$ pour $x 
\not= 1$. 

La d�finition suivante d'un mono�de gaussien appara�t
dans~[\\\Dfx]:

\Def
(i) On dit qu'un mono�de~$M$ est {\it gaussien} si $M$ est
atomique, simplifiable, et si deux �l�ments quelconques
de~$M$ admettent un ppcm � droite et � gauche, et un pgcd �
droite et � gauche. 

(ii) On dit qu'un mono�de gaussien~$M$ est un {\it mono�de
de Garside} s'il contient un {\it �l�ment de Garside}, ce
dernier �tant d�fini comme un �l�ment~$\D$ tel que les
diviseurs � gauche de~$\D$ co�ncident avec les diviseurs �
droite de~$\D$, ils soient en nombre fini, et ils
engendrent~$M$.

(iii) Tout mono�de gaussien satisfait aux conditions de Ore,
et admet donc un groupe de fractions. On dit qu'un
groupe~$G$ est un {\it groupe gaussien} (\resp un {\it
groupe de Garside}) s'il existe un mono�de gaussien~$M$
(\resp un mono�de de Garside~$M$) tel que $G$ soit le groupe
de fractions de~$M$.

\Ex 
Les groupes de tresses [\\\Gar] et, plus g�n�ralement,
tous les groupes d'Artin sph�riques, c'est-�-dire associ�s
� un groupe de Coxeter fini, sont des groupes de Garside [\\\BrS] 
[\\\Dlg], l'�l�ment dit fondamental �tant un �l�ment de
Garside. Plus g�n�ralement, tous les groupes de Garside
au sens de~[\\\Dfx] sont des groupes de Garside au
sens ci-dessus, mais la r�ciproque est fausse: un groupe de
Garside au sens restreint de~[\\\Dfx] est un groupe de
Garside dans lequel, de surcro�t, le ppcm � droite des atomes
est un �l�ment de Garside. Un contre-exemple typique est
$\Mon{a  , b  \; a   b  a   = b^2 }$: il y a ici deux atomes, �
savoir~$a  $ et~$b$, dont le ppcm est~$b^2$, qui n'est pas un
�l�ment de Garside, puisque $a  b $ est un diviseur � gauche
mais pas � droite de~$b^2$; par contre, l'�l�ment $\D = b^3$
est un �l�ment de Garside.

\bigskip Nous allons dans la suite �tablir divers r�sultats sur les
mono�des de Garside, en particulier l'�quivalence de
la d�finition originale avec plusieurs d�finitions
alternatives. Tous ces r�sultats reposent sur les propri�t�s
alg�briques des op�rations de ppcm et de compl�ment, que
nous allons �tablir maintenant. Il sera utile de disposer de
telles propri�t�s dans un cadre plus g�n�ral que celui des mono�des de Garside. En particulier, nous consid�rerons le cas o�
l'op�ration de ppcm (� droite) n'est pas n�cessairement partout
d�finie. Pour ce faire,  nous utiliserons un symbole~$\bot$
signifiant \<<non d�fini\>>: de la sorte,  $x 
\jR y  = \bot$ signifie que $x$ et $y$ n'ont pas de ppcm,
et une �galit� telle que $x  \jR y  = x ' \jR y '$ signifie
que soit $x  \jR y$ et $x ' \jR y '$ sont d�finis et ils
sont �gaux, soit ni $x  \jR y$, ni $x ' \jR y '$ ne sont
d�finis. On convient qu'on a toujours $x  \bot = \bot x  =
\bot$. Ainsi les �galit�s~�100� et~�200� sont toujours
satisfaites, que les ppcm et compl�ments mentionn�s soient
d�finis ou non.

Pour formuler de fa�on compacte nos hypoth�ses,
nous utiliserons les abr�viations suivantes:

\Def On dira qu'un mono�de~$M$ satisfait la
condition

-  $(C_0)$ si l'�l�ment~$1$ est le seul
inversible de~$M$;

-  $(C_0^+)$ si $M$ est atomique;

-  $(C_1)$ si $M$ admet la simplification � gauche;

-  $(\Til C_1)$ si $M$ admet la simplification � droite;

-  $(C_2)$ si deux �l�ments de~$M$ admettant un multiple
� droite commun admettent un ppcm � droite;

-  $(C_2^+)$ si deux �l�ments quelconques de~$M$ admettent
un ppcm � droite;

-  $(C_3)$ si $M$ poss�de une partie g�n�ratrice finie~$P$
close par~$\cR$, c'est-�-dire telle que $x , y  \in P$
entra�ne~$x  \cR y  \in P$; 

-  $(C_3^+)$ si $M$ poss�de une partie g�n�ratrice finie~$S$
close par~$\cR$ et~$\jR$, c'est-�-dire telle que $x , y  \in
S$ entra�ne~$x  \cR y  \in S$ et $x  \jR y  \in S$. 

\bigskip Noter que $(C_0^+)$ entra�ne~$(C_0)$, et, de m�me,
$(C_2^+)$ entra�ne~$(C_2)$, et $(C_3^+)$ entra�ne~$(C_3)$.
La conjonction de~$(C_0)$, $(C_1)$ et $(C_2)$ est le cadre
naturel pour que les op�rations de ppcm et de compl�ment �
droite soient bien d�finies --- donc, en particulier, pour
que $(C_3)$ et $(C_3^+)$ aient un sens --- et $(C_2^+)$ est
la condition additionnelle garantissant que ces op�rations
soient partout d�finies. Sous l'hypoth�se que $(C_0)$,
$(C_1)$ et $(C_2)$ sont satisfaites, l'�galit�~�100� est
toujours valable, de m�me que $x  \jR y  = y  \jR x$, et
$$(x  y ) \jR (x  z ) = x  \op (y  \jR z ).\Eq\�101�$$ 

\Lem\�\Rules�
{\sl Soit $M$ un mono�de satisfaisant~$(C_0)$, $(C_1)$
et~$(C_2)$. Pour tous $x ,
y , z $ dans~$M$, on a:
$$\Displaylines{
(x  y ) \cR z  = y  \cR (x  \cR z ), \qquad 
z  \cR (x  y ) = (z  \cR x ) \cdot ((x  \cR z ) \cR y ) 
\Eq\�103�\cr 
(x  \jR y ) \cR z  = (x  \cR y ) \cR (x 
\cR z ) = (y  \cR x ) \cR (y  \cR z ), \qquad 
z  \cR (x  \jR y ) = (z  \cR x ) \jR (z  \cR y )
\qquad \Eq\�105�\cr }$$ 

}\Dem Pour~�103�, on a, en utilisant~�100�
et~�101�,
$$\displaylines{
x  y  ((x  y ) \cR z ) 
= (x  y ) \jR z  
= (x  y ) \jR (x  \jR z ) 
= (x  y ) \jR (x  (x  \cR z ))
= x (y  \jR (x  \cR z ))
= x  y (y  \cR (x  \cR z )), \cr
z  ((x  y ) \cR z ) 
= (x  y ) \jR z  
= x  y ((z  \cR x ) \cR y ) 
= x (z  \cR x )(y  \cR (z  \cR x )) 
= z (x \cR z )(y  \cR (z  \cR x )), \cr}$$
et on simplifie � gauche par~$x  y$ dans le premier
cas, et par~$z $ dans le second. Pour~�105�,
appliquer~�103�\ � $x  \jR y  = x (x  \cR y )$ donne
directement
$(x  \jR y ) \cR z  = (x  \cR y ) \cR (x  \cR z )$.
Comme $\jR$ est sym�trique, cette expression est
aussi~$(y  \cR x )
\cR (y  \cR z )$. Enfin, on trouve, en appliquant~�103�,
l'�galit� pr�c�dente, et~�100�,
$$z  \cR (x  \jR y )
= z  \cR (x (x  \cR y ))
= (z  \cR x ) ((x  \cR z ) \cR (x  \cR y )) 
= (z  \cR x ) ((z  \cR x ) \cR (z  \cR y )) 
= (z  \cR x ) \jR (z  \cR y ).$$
(Figure~1.2). Remarquer que les formules sont valides
lorsqu'un des ppcm n'est pas d�fini, chacune des expressions
ayant alors la valeur~$\bot$, c'est-�-dire �tant non
d�finie.\FinDem

\midinsert
$$\OpenGraphicBox width 65mm height 52mm
depth0mm;
\leavevmode\special{illustration comp4.eps}
\CloseGraphicBox$$ 
\centerline{{\bf Figure 1.2.} Compl�ment it�r�}
\endinsert

\bigskip Dans le contexte pr�c�dent, pour $X, Y \ince M$ et
$k \ge 1$, on pose $X \cR Y = \{ x  \cR y  ~; x  \in X,
y  \in Y\}$, $X^k =
\{x_1 \ppp x_k \,;\, x_1, \pp, x_k \in X\}$,
et $X^0 = \{1\}$.

\Lem\�\Compl� 
{\sl Soit $M$ un mono�de satisfaisant aux conditions~$(C_0)$,
$(C_1)$ et $(C_2)$, et $P$ une partie g�n�ratrice de~$M$ 
close par~$\cR$. Alors, pour tout~$k$, on a $M \cR P^k
\ince P^k$, $P^k$ est close par~$\cR$ et par diviseur � droite,
et $M$ satisfait � la condition~$(C_2^+)$.}

\Dem On montre par induction sur~$i + k$ que la conjonction de $x 
\in P^i$ et
$y  \in P^k$ entra�ne $x  \cR y  \in P^k$. Pour $k = 0$, c'est-�-dire pour $y  = 1$, on a $x  \cR y  =
1$, et le r�sultat est vrai. Supposons $k = 1$. Pour $i =
0$, soit $x  = 1$, le r�sultat est vrai. Pour $i = 1$, le r�sultat
est l'hypoth�se que $P$ est clos par~$\cR$. Pour $i \ge 2$,
�crivons $x  = x_1x '$ avec $x_1 \in P$ et $x ' \in P^{i-1}$.
Par~�103�, on a $x  \cR y  = x ' \cR (x_1 \cR y )$. L'hypoth�se
d'induction donne $x_1 \cR y  \in P$, d'o� $x ' \cR
(x_1 \cR y ) \in P$. Supposons enfin  $k \ge 2$. On �crit $y  =
y_1 y '$ avec $y ' \in P$ et $y ' \in P^{k-1}$. Par~�103�, on a
$x  \cR y  = (x  \cR y_1) \op ((y_1 \cR x ) \cR
y ')$. L'hypoth�se d'induction donne $x  \cR y_1 \in
P$ et $y_1 \cR x  \in P^i$. On d�duit $(y_1 \cR x ) \cR
y ' \in P^{k-1}$, d'o� $x  \cR y  \in P^k$. 

On a ainsi montr� $P^i \cR P^k \ince P^k$ pour
tout~$i$, d'o� $M \cR P^k \ince P^k$ si $P$
engendre~$M$, c'est-�-dire que $M$ est la r�union des
ensembles~$P^i$. On a aussi $P^k \cR P^k \ince P^k$,
donc $P^k$ est clos par l'op�ration~$\cR$.
De plus, supposons $y  \in P^k$ et $y  =z x$. On a alors
$x  = z  \cR y$, donc $x  \in P^k$.

Les calculs pr�c�dents montrent que $x  \cR
y$, donc aussi $x  \jR y$, existent pour tout~$x$
dans~$M$ et tout~$y$ dans~$P^k$, pour tout~$k$.
Comme $P$ engendre~$M$, on d�duit que $x  \cR y$
et $x  \jR y$ existent pour tous~$x , y$ dans~$M$,
et $M$ satisfait donc � la condition~$(C_2^+)$. \FinDem

\Lem\�\Closure� 
{\sl Soit $M$ un mono�de satisfaisant~$(C_0)$, $(C_1)$
et~$(C_2)$, et  $P$ un sous-ensemble de~$M$ clos
par~$\cR$. Soit $S$ la cl�ture de~$P$ par~$\jR$.

(i) L'ensemble~$S$ est clos par~$\cR$ et~$\jR$. Si $P$ est fini,
alors $S$ est fini, on a $\card(S) \le 2^{\card(P)}$; par
cons�quent, la condition~$(C_3)$ entra�ne la
condition~$(C_3^+)$.

(ii) Pour tous~$i, k$, on a $S^i \cR S^k \ince S^k$ et
$S^i \jR S^k \ince S^{\sup(i, k)}$; en
particulier, $S^k$ est clos par~$\cR$ et~$\jR$ pour tout~$k$.}

\Dem (i) Par construction, tout �l�ment de~$S$ peut �tre
exprim� comme ppcm � droite d'un sous-ensemble fini
de~$P$, donc, si $P$ a $n$~�l�ments, $S$ a au plus
$2^n$~�l�ments. Par construction, $S$ est clos par~$\jR$, et
il s'agit de montrer qu'il est �galement clos par~$\cR$.
Supposons $x  = x_1 \jR \ppp \jR x_p$, $y  = y_1
\jR \ppp \jR y_q$ avec $x_1$, \pp, $y_q \in P$. Nous
voulons �tablir $x  \cR y  \in S$. D'abord, �105�
entra�ne $x  \cR y  = (x  \cR y_1) \jR \ppp \jR (x 
\cR y_q)$, donc il suffit de montrer  $x  \cR y_j
\in P$ pour tout~$j$. On utilise une induction sur~$p \ge 1$.
Pour $p = 1$, le r�sultat est l'hypoth�se que $P$ est clos
par ppcm � droite. Sinon, posons $x ' = x_1 \jR \ppp \jR
x_{p-1}$. Par~�105�, nous obtenons
$$x  \cR y_j 
= (x ' \jR x_p) \cR y_j 
= (x ' \cR x_p) \cR (x ' \cR y_j);$$  
L'hypoth�se d'induction entra�ne $x ' \cR x_p
\in P$ et $x ' \cR y_j \in P$, d'o� $(x ' \cR x_p) \cR
(x ' \cR y_j) \in P$ puisque $P$ est clos par~$\cR$. 

(ii) L'ensemble~$S$ �tant clos par~$\cR$, le lemme~�\Compl�
donne $S^i \cR S^k \ince S^k$ directement. On �tablit la
relation $S^i \jR S^k \ince S^{\sup(i, k)}$ par r�currence sur
$\inf(i, k)$. Le r�sultat est trivial pour
$\inf(i, k) = 0$. Pour $\inf(i, k) = 1$, soit par exemple $k
= 1$, on utilise une r�currence sur~$i$: supposant $x \in S^i$
et $y \in S$, on pose $x = x_1 x'$ avec $x_1 \in S$ et $x' \in
S^{i-1}$. Par les formules du lemme~�\Rules�, on trouve
$$x \jR y = (x_1 \jR y) ((x_1 \cR y) \cR x') \in S \cdot S^{i-1}
= S^i.$$
Supposons enfin $\inf(i, k) \ge 2$. On
�crit $x = x_1 x'$, $y = y_1 y'$ avec $x_1, y_1 \in S$, $x_1
\in S^{u-1}$, et $y' \in S^{k-1}$. Les r�gles du 
lemme~�\Rules� donnent
$$x \jR y = (x_1 \jR y_1) \, (((x_1 \cR y_1) \cR x') \jR
((y_1 \cR x_1) \cR y')).$$
On a alors $x_1 \jR y_1 \in S$, puis, d'apr�s ce qui
pr�c�de, $(x_1 \cR y_1) \cR x' \in S^{i-1}$, et $(y_1 \cR x_1)
\cR y' \in S^{k-1}$, d'o� $((x_1
\cR y_1) \cR x') \jR ((y_1 \cR x_1) \cR y') \in S^{\inf(i-1,
k-1)}$ par hypoth�se de r�currence, et, finalement,
$x \jR y \in S^{\sup(i, ,)}$.\FinDem

\bigskip Sous les hypoth�ses pr�c�dentes, tout �l�ment
de~$S$ qui s'exprime comme le ppcm � droite de
$k$~�l�ments de~$P$ peut aussi s'exprimer comme produit
de $k$~�l�ments de~$P$. En effet, on peut �tablir par
r�currence une formule g�n�rale du type
$$x  \jR y  \jR z  \jR \ppp = x  \cdot (x  \cR y ) \cdot
((x  \cR y ) \cR (x  \cR z )) \cdot \ppp.$$
Nous allons dans la suite donner plusieurs
d�finitions �quivalentes des mono�des de Garside. La
premi�re provient de la remarque que, si $M$ est un
mono�de de Garside et que $\D$ est un �l�ment de
Garside dans~$M$, alors l'ensemble~$S$ des diviseurs
de~$\D$ est clos par les op�rations de ppcm, pgcd et
compl�ment � droite et � gauche. L'existence d'un tel ensemble peut en
fait �tre prise comme d�finition:

\Prop\�\Alternative�
{\sl Soit $M$ un mono�de gaussien, $\D$ est
�l�ment de~$M$, et $S$ une partie de~$M$. Alors il y a
�quivalence entre

(i) $\D$ est �l�ment de Garside, et $S$ est l'ensemble des
diviseurs (� gauche ou � droite) de~$\D$;

(ii) $S$ est une partie g�n�ratrice finie de~$M$ qui est close
par diviseur, ppcm, compl�ment et pgcd � droite et �
gauche, et $\D$ est le ppcm � droite de~$S$.}

\Dem Supposons~(i). Supposons $x  \in S$ et $x  =
y z $: alors il existe $x '$ v�rifiant $x x ' = \D$ , d'o�
$y  (z x ') = \D$, et $y$ est dans~$S$. Ainsi, $S$ est clos
par diviseur � gauche, et, par un argument sym�trique,
par diviseur � droite.

Soient maintenant $x$, $y$ dans~$S$. Par hypoth�se, $\D$
est multiple � droite de~$x$ et~$y$, donc de~$x  \jR y$. Par
cons�quent, $x  \jR y$ est dans~$S$, et il en est de m�me
de~$x  \cR y$, qui en est un diviseur � droite.
Le cas du ppcm et du compl�ment � gauche est
sym�trique; le cas des pgcd est trivial. Enfin, $\D$, �tant
�l�ment de~$S$, en est n�cessairement ppcm � droite et �
gauche puisque $S$ est clos par ces op�rations.

R�ciproquement, supposons~(ii). Le premier probl�me est
de montrer que l'ensemble~$\Til S$ des diviseurs � gauche
de~$\D$ co�ncide avec~$S$. D'abord, par construction, tout
�l�ment de~$S$ est diviseur � gauche de~$\D$, et $S$ est
donc inclus dans~$\Til S$. Soit $x$ un �l�ment quelconque
de~$\Til S$. Il existe donc~$x '$ v�rifiant $x x ' = \D$, d'o�
$x  = \D \cL x '$. Par le lemme~�\Closure�, on a $M \cR S
\ince S$, et donc, sym�triquement, $S \cL M \ince S$, d'o� en
particulier $x  = \D \cL x '  \in S$. Donc $S$ est
l'ensemble des diviseurs � gauche de~$\D$. 

Le second probl�me est de montrer de m�me que $S$
co�ncide avec l'ensemble des diviseurs � droite de~$\D$. Ce
point r�sultera du calcul pr�c�dent (renvers� par
sym�trie) pourvu qu'on montre que $\D$ est le ppcm �
gauche de~$S$. Comme $\D$ est dans~$S$, il s'agit de
montrer que tout �l�ment~$x$ de~$S$ est un diviseur �
droite de~$\D$. Soit $x$ un tel �l�ment. Par hypoth�se, 
$x  \jL \D$ existe et est dans~$S$: il existe $y$ v�rifiant $x 
\jL \D = y  \D$, et, puisque $y  \D$ est dans~$S$, il
existe~$z $ v�rifiant $y  \D z  = \D$. Comme $\D$ est dans~$S$,
et que $S$ est clos par diviseur � gauche et � droite, $y$ et~$z $
sont dans~$S$. Il existe donc $y '$ dans~$S$, � savoir $y ' = y 
\cR \D$, v�rifiant
$y  y ' = \D$, et, puisque la simplification � gauche est
possible, on d�duit $y ' = \D z $. Puisque $y '$ est
dans~$S$, il existe ensuite $y ''$ dans~$S$, � savoir $y '' =
y ' \cR \D$, v�rifiant $y ' y '' = \D$, d'o� $\D = \D z 
y ''$. Ceci entra�ne $z  y '' = 1$, d'o� $z  = y '' = 1$,
donc $y  \D = \D$, et, finalement, $y  = 1$, ce qui montre
que $x$ est diviseur � droite de~$\D$. \FinDem

\bigskip On notera que l'argument pr�c�dent utilise
seulement~$(C_0)$, et non~$(C_0^+)$.

\Def Si $M$ est un mono�de de Garside, on appelle
{\it primitifs � droite} les �l�ments de la cl�ture des atomes
de~$M$ par l'op�ration~$\cR$, et {\it simples} les �l�ments
de la cl�ture des �l�ments primitifs par l'op�ration~$\jR$ ---
qui est aussi la cl�ture des atomes par~$\cR$ et~$\jR$.

\bigskip Si $M$ est un mono�de de Garside, alors l'ensemble
des atomes de~$M$ est la partie g�n�ratrice minimale de~$M$,
l'ensemble des �l�ments primitifs � droite est la partie
g�n�ratrice close par~$\cR$ minimale, l'ensemble~$S$ des
�l�ments simples est la partie g�n�ratrice close par~$\cR$
et~$\jR$ minimale, et son ppcm est l'�l�ment de Garside de
norme minimale\footnote{$^1$}{dans le cas des groupes
d'Artin, les �l�ments simples sont aussi appel�s {\it r�duits}
dans la litt�rature}. Avec les notations pr�c�dentes, la
structure~$(S, \jR, \gL)$ est un treillis (fini), et il en est de
m�me de la structure sym�trique~$(S, \jL, \gR)$.

\Prop
{\sl Un mono�de de Garside est d�termin�
par l'ensemble de ses �l�ments primitifs � droite et
la restriction de l'op�ration~$\cR$ � ces �l�ments.}

\Dem Soit $M$ un mono�de de Garside, et $P$ l'ensemble
de ses �l�ments primitifs � droite. Par hypoth�se,  $P$
engendre~$M$, donc il suffit de montrer que, pour tous
$x_1, \pp, x_p$, $y_1, \pp, y_q$ dans~$P$, la
condition $x_1 \ppp x_p = y_1 \ppp y_q$ peut
s'exprimer en terme de la restriction de~$\cR$ �~$P$. Or
$x_1 \ppp x_p = y_1 \ppp y_q$ �quivaut � $(x_1
\ppp x_p) \cR (y_1 \ppp y_q) = (y_1
\ppp y_q) \cR (x_1 \ppp x_p) = 1$, et les r�gles de calcul du
lemme~�\Rules� montrent que $(x_1 \ppp x_p) \cR (y_1
\ppp y_q)$ s'exprime comme produit de $q$~�l�ments
de~$P$ d�termin�s de proche en proche � partir de~$x_1,
\pp, y_q$ � l'aide de l'op�ration~$\cR$. Par exemple, pour
$p = q = 2$, on trouve
$$(x_1 x_2) \cR (y_1 y_2) = (x_2 \cR (x_1 \cR y_1)) \om
(((x_1 \cR y_1) \cR x_2) \cR ((y_1 \cR x_1) \cR y_2)).$$
En vertu de la condition~$(C_0)$, le produit de ces
$q$~�l�ments vaut~$1$ si et seulement chacun d'eux
vaut~$1$, ce qui donne une condition du type requis. Par
exemple, $x_1x_2 = y_1 y_2$ est �quivalent
� la conjonction des quatre �galit�s
$$\Displaylines{
x_2 \cR (x_1 \cR y_1) = 1, \quad
((x_1 \cR y_1) \cR x_2) \cR ((y_1 \cR x_1) \cR y_2) = 1, \cr
y_2 \cR (y_1 \cR x_1) = 1, \quad
((y_1 \cR x_1) \cR y_2) \cR ((x_1 \cR y_1) \cR x_2) = 1. 
&\Block\cr
}$$

\Prop
{\sl Un mono�de de Garside	$M$ est d�termin� par son graphe
caract�ristique, d�fini comme la restriction aux �l�ments simples
du graphe de Cayley atomique, c'est-�-dire la famille des triplets
$(x , a  , y )$ o� $x$ et $y$ sont simples et $a  $ est un
atome v�rifiant $x  a   = y$.}

\Dem Notons~$S$ l'ensemble des �l�ments simples de~$M$, et~$\G$
son graphe caract�ristique. D'apr�s la proposition pr�c�dente, il suffit
de montrer que, pour $x$, $y$ dans~$S$, la valeur de~$x  \cR
y$ est d�termin�e par~$\G$. Soient $x$, $y$ des �l�ments
de~$S$, donc des sommets de~$\G$. Le ppcm � droite de~$x$
et~$y$ est la borne sup�rieure de~$x$ et~$y$ dans~$\G$,
c'est-�-dire l'unique sommet~$z $ accessible depuis~$x$ et~$y$
dans~$\G$ tel que, pour tout sommet~$z '$ accessible
depuis~$x$ et~$y$, $z '$ soit accessible
depuis~$z $. Alors $x  \cR y$ est l'unique
sommet~$y '$ de~$\G$ tel qu'il existe un chemin de~$1$
�~$y '$ qui porte les m�mes �tiquettes que le chemin
de~$x$ �~$z $. En effet, si $a  _1, \pp, a  _k$ est la
suite des �tiquettes du chemin de~$x$ �~$z $
dans~$\G$, on a
$x \cR y  = a  _1 \ppp a  _k$ dans~$M$. Le seul point �
justifier est l'existence d'un chemin �tiquet�~$a  _1, \pp,
a  _k$ depuis~$1$ dans~$\G$: or, pour $i \le k$, $a  _1 \ppp
a  _i$ est un diviseur � gauche de~$x  \cR y$, donc un
�l�ment de~$S$, et donc l'ar�te $(a  _1 \ppp a  _{i-1}, a  _i,
a  _1 \ppp a  _i)$ appartient bien �~$\G$.\FinDem

\Ex\�\ExMon�
La figure~1.3 montre le graphe caract�ristique dans
le cas du mono�de $\Mon{a  , b  \; a   b  a   = b^2}$,
dont les crit�res de la section~6 montreront qu'il est un
mono�de de Garside: il y a ici 8 �l�ments simples. Noter
que le ppcm � droite des atomes, � savoir~$b^2$, n'est
pas l'�l�ment~$\D$, qui est~$b^3$. 

\midinsert
$$\OpenGraphicBox width 48mm height 45mm
depth0mm;
\leavevmode\special{illustration Cayley4.eps}
\CloseGraphicBox$$ 
\centerline{{\bf Figure 1.3.} Graphe caract�ristique du mono�de
$\Mon{a  , b  \; a   b  a   = b^2}$}
\centerline{(Les ar�tes pleines repr�sentent~$a  $,
les tiret�es~$b $)} 
\endinsert

\bigskip En effa�ant les �tiquettes du graphe caract�ristique, on obtient
le diagramme de Hasse du treillis des �l�ments simples. Ce graphe
ne d�termine pas le mono�de � isomorphisme pr�s. Par exemple, les
mono�des $\Mon{a  ,
b  \; a  b  = b a  }$ et $\Mon{a  , b  \; a  ^2 =
b^2}$ sont tous deux des mono�des de Garside; les
graphes de Cayley associ�s sont respectivement
$$\OpenGraphicBox width 65mm height 21mm
depth0mm;
\leavevmode\special{illustration BiCayley4.eps}
\CloseGraphicBox$$ 
Les graphes non �tiquet�s sous-jacents sont identiques, alors que les
mono�des ne sont pas isomorphes, puisque les graphes �tiquet�s ne le
sont pas.

Lorsque $M$ est le mono�de d'Artin associ� � un groupe de
Coxeter fini~$W$, les �l�ments simples de~$M$ sont en bijection avec
les �l�ments de~$W$, et le graphe caract�ristique de~$M$
s'obtient � partir du graphe de Cayley de~$W$ en orientant les
fl�ches, c'est-�-dire en supprimant les relations de torsion~$x^2 =
1$. Cette propri�t� ne s'�tend pas au cas d'un mono�de de Garside
g�n�ral, puisque, dans l'exemple~�\ExMon�, tous les sommets du
graphe n'ont pas le m�me degr�, ce qui exclut que ce dernier
soit la projection du graphe de Cayley d'un groupe. 

\Question
Le graphe caract�ristique d'un mono�de de Garside est-il  la
projection du graphe de Cayley d'un mono�de quotient
de~$M$ obtenu en ajoutant des relations de torsion?

\bigskip Le r�ponse est positive dans le cas de l'exemple~�\ExMon�: si
$W$ est le mono�de obtenu en ajoutant � la pr�sentation les relations
de torsion $a  ^2 = 1$ et $b^4 = b $ (la seconde est en fait
cons�quence de la premi�re), alors le graphe caract�ristique
de~$M$ s'obtient � partir du graphe de Cayley de~$W$ en supprimant
des ar�tes de torsion (Figure~1.4). Le groupe
$\Gr{a  ,
b  \; a  b a   = b^2}$ est le groupe de tresses~$B_3$, pr�sent� �
partir des g�n�rateurs $a   = \s_1$ et $b  = \s_2\s_1$. Le
groupe~$B_3$ est �galement le groupe de fractions du mono�de de Garside~$B_3^+$, dont le groupe de Coxeter associ� est le groupe
sym�trique~$\Sym_3$. Remarquer que ce dernier admet la
pr�sentation $\Gr{a  , b  \; a   b  a   = b^2,
a  ^2 = 1, b^3 = 1}$, et qu'il s'obtient donc � partir du mono�de
$\Mon{a  , b  \; a   b  a   = b^2, a  ^2 = 1, b^4 = b }$ en
quotientant par la relation~$b^3 = 1$.

\midinsert
$$\OpenGraphicBox width 48mm height 45mm
depth0mm;
\leavevmode\special{illustration Coxeter4.eps}
\CloseGraphicBox$$ 
\centerline{{\bf Figure 1.4.} Graphe de Cayley
du mono�de $\Mon{a  , b  \; a   b  a   = b^2, a  ^2 =
1, b^4 = b }$}
\centerline{(Les ar�tes pleines repr�sentent~$a  $,
les tiret�es~$b $)} 
\endinsert


\Sec Dualit� dans les mono�des de Garside

\bigskip L'objet de cette section est � la fois d'�tablir des formules de
calcul valables dans tout mono�de de Garside (lemmes~2.5
et~2.6), et de donner une nouvelle ca\-rac\-t�risation de ceux-ci par
des conditions plus faibles que celles de la d�finition
initiale qui seront utilis�es dans la section~5. Le r�sultat est le suivant:

\Prop\�\Char�
{\sl Un mono�de est un mono�de de Garside si, et
seulement si, il v�rifie les conditions~$(C_0)$, $(C_1)$,
$(C_2)$, $(C_3)$, et $(\Til C_1)$.}

\bigskip Tout mono�de gaussien satisfait par d�finition aux
conditions~$(C_0)$, $(C_1)$, $(C_2)$ et $(\Til C_1)$, et tout
mono�de de Garside satisfait en outre la
condition~$(C_3)$ d'apr�s la proposition~�\Alternative�, donc les
conditions de la proposition~�\Char� sont n�cessaires. Le probl�me est
de montrer que ces conditions sont aussi suffisantes, et, en particulier,
de montrer qu'elles entra�nent l'existence des ppcm � gauche
qui n'y sont pas mentionn�s, non plus que
l'atomicit�. La d�monstration comporte plusieurs r�sultats
interm�diaires, et repose sur l'existence d'une dualit�
�changeant division � gauche et � droite pour les �l�ments
simples.

\Lem\�\Demep� 
{\sl Soit $M$ un mono�de satisfaisant aux
conditions~$(C_0)$, $(C_1)$ et~$(C_2^+)$, 
$S$ une partie g�n�ratrice de~$M$ close par~$\cR$
et~$\jR$, et admettant un ppcm � droite~$\D$.

(i) Pour tout entier~$k$, l'ensemble~$S^k$ est clos
par~$\cR$ et~$\jR$, tout diviseur � droite de~$\D^k$
appartient �~$S^k$, et tout �l�ment de~$S^k$ est un
diviseur � gauche de~$\D^k$.

(ii) Posons $x^* = x  \cR \D$ pour~$x  \in S$. Alors,
on a $x^* \in S$ et $x  x^* = \D$. Pour $x , y$
dans~$S$, $y^*$ est un diviseur � droite de~$x^*$ si
$x$ est un diviseur � gauche de~$y$, et l'implication
r�ciproque est vraie si $M$ admet la simplification � droite.

(iii) La fonction $x  \mapsto x^{**}$ s'�tend en un
endomorphisme~$\f$ de~$M$ qui envoie~$S^k$ dans
lui-m�me pour tout~$k$, et, pour tout~$x$ dans~$M$, on
a
$$x  \op \D = \D \op \f(x ). \Eq\�111�$$

}\Dem (i) Le lemme~�\Closure�(iii) affirme que $S^k$
est clos par~$\cR$ et~$\jR$, et le lemme~�\Compl� que tout
diviseur � droite de~$\D^k$ appartient �~$S^k$, puisque
$\D^k$ est �l�ment de~$S^k$ par construction.

Supposons $x  \in S^k$. On d�montre par r�currence
sur~$k$ que $x$ est un diviseur � gauche de~$\D^k$. Pour
$k = 0$, on a $x  = 1$, et le r�sultat est trivial. Pour $k = 1$,
le r�sultat d�coule de la d�finition de~$\D$. Supposons
$x  \in S^k$ avec $k \ge 2$. On �crit $x  =
x_1 x '$ avec $x_1 \in S$ et $x ' \in S^{k-1}$.
Par~�103�, on a
$$\D^k \cR x  = (\D^k \cR x_1) \cdot ((x_1 \cR
\D^k) \cR x ').$$ 
Puisque $x_1$ est dans~$S$, il est diviseur � gauche
de~$\D$, donc de~$\D^k$, donc on a $\D^k \cR x_1 = 1$, et,
d'autre part, toujours par~�103�,
$$x_1 \cR \D^k = (x_1 \cR \D) \om ((\D \cR x_1)
\cR \D^{k-1}) = (x_1 \cR \D) \om (1 \cR \D^{k-1}) = (x_1
\cR \D) \om \D^{k-1}.$$
On d�duit
$$\D^k \cR x  = ((x_1 \cR \D)  \op \D^{k-1}) \cR x '
= \D^{k-1} \cR ( (x_1 \cR \D) \cR x ' ).$$
Par le lemme~�\Compl�,  $(x_1 \cR \D) \cR x '$ est
dans~$S^{k-1}$, donc, par hypoth�se de r�currence, cet
�l�ment est un diviseur � gauche de~$\D^{k-1}$. On d�duit
$ \D^{k-1} \cR ( (x_1 \cR \D) \cR x ' ) = 1$, soit
finalement $\D^k \cR x  = 1$, et $x$ est
diviseur � gauche de~$\D^k$.

(ii) Supposons $x  \in S$. Comme $\D$ est dans~$S$, on a
$x^* = x  \cR \D \in S$ puisque, par hypoth�se, $S$ est
clos par~$\cR$. Par d�finition, $x$ est diviseur � gauche
de~$\D$, donc on a $x  x^* = x  \jR \D = \D$. Supposons
que $x$ et $y$ soient dans~$S$ et $x$ est un diviseur
� gauche de~$y$, disons $y  =x z $. On a alors $x 
x^*= \D = y  y^* = x  z  y^*$, d'o�
$x^* = z  y^*$, et $y^*$ est diviseur � droite
de~$x^*$. Inversement, $x^* = z  y^*$ entra�ne $y 
y^* = x  z  y^*$, donc $x  z  = y$ si la
simplification � droite par~$y^*$ est permise.

(iii) Supposons $x  \in S$. Alors $x^*$ est dans~$S$,
donc $x^{**}$ est d�fini, et on obtient
$$x  \op \D = x  \op (x^* \op x^{**}) = (x  \op x^*)
\op x^{**} = \D \op x^{**}. \Eq\�98�$$
Soit $x$ un �l�ment quelconque de~$M$. Puisque $S$
engendre~$M$, il existe une d�composition, en g�n�ral non
unique, de~$x$ comme produit d'�l�ments de~$S$.
Supposons $x  = x_1 \ppp x_p = y_1 \ppp y_q$, 
avec $x_1, \pp, x_p, y_1, \pp, y_q \in S$. Par~�98�,
on obtient
$$\D \op x_1^{**} \ppp x_p^{**}
= x_1 \ppp x_p \op \D 
= x  \op \D 
= y_1 \ppp y_q \op \D 
= \D \op y_1^{**} \ppp y_q^{**},$$
et, puisque $\D$ est simplifiable � gauche, il n'y a pas
d'ambigu�t� � d�finir~$\f$ par $\f(x ) = x_1^{**} \ppp
x_k^{**}$. Alors, par construction, $\f$ est un endomorphisme
de~$M$, et �111� est v�rifi�e pour tout~$x$ dans~$M$. Enfin, $x 
\in S^k$ entra�ne
$\f(x )
\in S^k$ par construction.\FinDem

\bigskip Nous introduisons d�sormais la condition de
finitude~$(C_3)$ dans les hypoth�ses. Notons que, m�me si
$M$ est un mono�de de type fini, les conditions~$(C_0)$,
$(C_1)$ et $(C_2^+)$ ne garantissent pas~$(C_3)$,
c'est-�-dire l'existence d'une partie g�n�ratrice finie close par~$\cR$: le
mono�de de Baumslag--Solitar $\Mon{a  , b  \; a  b^2 = b a  }$
est un contre-exemple, car on a alors $a   \cR
b^n = b^{2n}$ pour tout~$n$, et la cl�ture
par~$\cR$ de l'ensemble des atomes~$\{a  , b \}$ est infinie.

D'apr�s le lemme~�\Closure�, si $M$ est un mono�de
v�rifiant les conditions~$(C_0)$, $(C_1)$, $(C_2)$ et $(C_3)$, il
existe une partie finie~$S$ close par~$\cR$ et~$\jR$. En
particulier, $S$ admet un ppcm � droite~$\D$, qui est
�l�ment de~$S$, et $M$ v�rifie les hypoth�ses du
lemme~�\Demep�.

\Lem\�\Bijection�
{\sl Soit $M$ un mono�de v�rifiant les conditions~$(C_0)$,
$(C_1)$, $(C_2)$ et~$(C_3)$, et $S$ une partie
g�n�ratrice finie de~$M$ close par~$\cR$ et~$\jR$. Soient
$\dL$, $\f$ comme dans le lemme~�\Demep�. Alors les
conditions suivantes sont �quivalentes:

(i) Le mono�de~$M$ satisfait~$(\Til C_1)$, c'est-�-dire admet la
simplification � droite;

(ii) L'application $x  \mapsto x^*$ est une permutation
de~$S$;

(iii) Il existe~$m$ tel que $\f^m(x ) = x$ soit v�rifi�
pour tout~$x$ dans~$S$;

(iv) L'application~$\f$ est un automorphisme de~$M$, et
une permutation de~$S^k$ pour tout~$k$.}

\Dem Notons $\D$ le ppcm � droite de~$S$. Puisque $S$ est
fini, (ii) et (iii) sont �quivalents, et, puisque $\f$ est un
endomorphisme, que $S$ engendre~$M$, et que $\f$
envoie~$S^k$ dans lui-m�me pour tout~$k$, il en est de
m�me de~(ii) et~(iv).

Supposons $x , y  \in S$ et $x^* = y^*$. On a alors $x 
x^* = \D = y  y^* = y  x^*$, d'o� $x  = y$ si $M$
admet la simplification � droite. Donc (i) entra�ne
l'injectivit� de~${}^*$ sur~$S$,  donc~(ii) puisque $S$ est
fini. 

Inversement, supposons $x z  = y z $. Pour $k$ assez grand,
$x$, $y$ et $z $ sont dans~$S^k$, donc $z $ est un diviseur �
gauche de~$\D^k$, et $x z  = y z $ entra�ne $x  \D^k = y 
\D^k$. Par~�111�, on trouve
$$\D^k \op \f^k(x ) = x  \op \D^k = y  \op \D^k = \D^k \op
\f^k(y ),$$
d'o� $\f^k(x ) = \f^k(y )$, et $x  = y$ si (iv) est
v�rifi�e. Donc (iv) entra�ne~(i).\FinDem

\bigskip Nous supposons d�sormais, jusqu'� la fin de cette
section, que $M$ est un mono�de satisfaisant aux
conditions~$(C_0)$, $(C_1)$, $(C_2)$, $(C_3)$, et $(\Til C_1)$,
et que $S$ est une partie g�n�ratrice finie de~$M$ close
par~$\cR$ et~$\jR$. Gardant les conventions pr�c�dentes,
nous notons $\D$ le ppcm � droite de~$S$, et, pour $x$
dans~$S$, nous posons~$x^* = x  \cR \D$, et nous
notons~$\f$ l'automorphisme de~$M$ induit par~$x 
\mapsto x^{**}$.

\Lem\�\Simple�
{\sl (i) Les implications du lemme~�\Demep�(i) sont des
�quivalences: pour tout~$k$, il y a �quivalence entre �tre
diviseur � gauche de~$\D^k$, �tre diviseur � droite
de~$\D^k$, et appartenir �~$S^k$.

(ii) Tout �l�ment de~$S^k$ admet au plus $\card(S)^k$
diviseurs � gauche.

(iii) Le mono�de~$M$ est atomique, et $x  \in S^k$ entra�ne
$\norm(x ) \le \card(S)^k$; en parti\-cu\-lier, on a 
$\norm(\D) \le \card(S)$.

(iv) Deux �l�ments quelconques de~$M$ ont un pgcd �
gauche. La structure $(M, \jR, \gL)$ est un treillis, et $(S,
\jR, \gL)$ est un treillis fini de minimum~$1$ et de
maximum~$\D$.}

\Dem (i) Par le lemme~�\Bijection�, $\f$ est un
automorphisme de~$M$. Supposons que $x$ divise �
gauche~$\D^k$, soit $x z  = \D^k$. On a alors
$$\f^{-k}(z ) \op x  \op z  
= \f^{-k}(z ) \op \D^k = \D^k \op z ,$$
d'o�, en simplifiant � droite, $\D^k = \f^{-k}(z ) \op x$, et
$x$ divise � droite~$\D^k$.

(ii) D'apr�s~(i), tout diviseur � gauche d'un �l�ment
de~$S^k$ est lui-m�me �l�ment de~$S^k$, d'o� le
r�sultat puisqu'on a $\card(S^k) \le \card(S)^k$.

(iii) Supposons $x  \in S^k$, et $x  = x_1 \ppp x_n$
avec $x_1, \pp, x_n \not= 1$. Par construction, $x_1
\ppp x_i$ est un diviseur � gauche de~$x$, donc
de~$\D^k$, pour tout~$i$, ce qui entra�ne $x_1 \ppp x_i
\in S^k$. Les conditions~$(C_0)$ et~$(C_1)$ entra�nent
$x_1 \ppp x_i \not= x_1 \ppp x_j$ pour $i \not= j$.
On a donc $n \le \card(S^k) \le \card(S)^k$, soit $\norm(x )
\le \card(S)^k$.

(iv) D'apr�s le lemme~�\Simple�(ii), l'ensemble des
diviseurs � gauche de tout �l�ment de~$M$ est fini.
Donc, pour $x$, $y$ quelconques dans~$M$, l'ensemble
des diviseurs � gauche communs de~$x$ et~$y$ est fini,
et il admet un ppcm � droite, lequel est un pgcd � gauche
de~$x$ et~$y$ par construction. Que $(M, \jR, \gL)$ soit
un treillis est alors standard. Pour~$S$, nous remarquons
que, pour $x , y  \in S$, l'ensemble des diviseurs �
gauche de~$x$ et~$y$ est inclus dans~$S$ et donc que le
ppcm � droite de cet ensemble, qui est $x  \gL y$,
appartient �~$S$.\FinDem

\bigskip L'�tape suivante consiste � utiliser la dualit� $x 
\mapsto x^*$ pour montrer la sym�trie de la structure.
Par le lemme~�\Bijection�, nous savons que l'application 
$x  \mapsto x^*$ est une permutation de~$S$.
Pour~$x$ dans~$S$, nous noterons $\dL x$ l'unique
�l�ment de~$S$ v�rifiant $(\dL x )^* = x$. Alors, pour
tout~$x$ dans~$S$, nous avons
$$\D = x  \cdot x^* = \dL x  \cdot x ,\Eq\�119�$$
et, donc, $\dL(x^*) = x$. D'apr�s le lemme~�\Demep�(ii),
si $x$ et $y$ sont dans~$S$, $x$ est diviseur � gauche
de~$y$ si et seulement si $y^*$ est diviseur � droite
de~$x^*$, et, par cons�quent, $x$ est diviseur � droite
de~$y$ si et seulement si $\dL y$ est diviseur � gauche
de~$\dL x$.

\Lem\�\Dual�
{\sl (i) Deux �l�ments quelconques de~$M$ admettent un
ppcm � gauche et un pgcd � droite.

(ii) L'ensemble~$S$ est clos par les op�rations~$\cL$, $\jL$
et~$\gR$, et, pour $x , y  \in S$, on a
$$x  \cL y  = (\dL x  \gL \dL y ) \cR \dL y , \qquad 
x  \jL y  = (\dL x  \gL \dL y )^*, \qquad
x  \gR y  = (\dL x  \jR \dL y )^*.  \Eq\�122�$$

(iii) L'�l�ment~$\D$ est ppcm � gauche de~$S$, et, pour
tout~$x$ dans~$S$, on a\  $\dL x  = \D \cL x$.}

\Dem (i) Soient $x$, $y$ quelconques dans~$M$. Alors il
existe~$k$ tel que $x$ et $y$ appartiennent �~$S^k$, ce
qui, par le lemme~�\Simple�, entra�ne que $\D^k$ est un
multiple � gauche de~$x$ et de~$y$. D'apr�s~[\\\Dfx,
Proposition~2.4], ceci est suffisant pour assurer l'existence
d'un ppcm � gauche et d'un pgcd � droite pour~$x$
et~$y$

(ii) Par d�finition, $\dL x  \gL \dL y$ est un diviseur �
gauche de~$\dL x$ et~$\dL y$, donc $(\dL x  \gL \dL
y )^*$ est un multiple � gauche de~$x$ et~$y$, et donc
de~$x  \jL y$. Donc, en particulier, $x  \jL y$ est
dans~$S$, et $\dL(x  \jR y )$ est d�fini. Ensuite, $x$ et
$y$ sont des diviseurs � droite de~$x  \jL y$, donc
$\dL(x  \jL y )$ est un diviseur � gauche de~$\dL x$ et
de~$\dL y$, donc de~$\dL x  \gL \dL y$. Par
cons�quent, $(\dL x  \gL \dL y )^*$ est un diviseur �
droite de~$x  \jL y$, et nous d�duisons $x 
\jL y  = (\dL x  \gL \dL y )^*$.

On trouve ensuite
$$\dL y  \op y  = \D = \dL(x  \jL y ) \op (x  \jL y )  =
(\dL x  \gL \dL y ) \op (x  \cL y ) \op y ,$$ 
d'o� $\dL y  = (\dL x  \gL \dL y ) \op (x  \cL y )$, qui
donne $x  \cL y  = (\dL x  \gL \dL y ) \cR \dL y$.

L'argument est semblable pour le pgcd � droite. Comme
$\dL x$ et~$\dL y$ sont des diviseurs � gauche de
$\dL x  \jR \dL y$,  $(\dL x  \jR \dL y )^*$ est diviseur �
droite de~$x$ et de~$y$, donc de~$x  \gR y$. D'un
autre c�t�,  $x  \gR y$ est un diviseur � droite d'un
�l�ment de~$S$, donc il est �l�ment de~$S$. Puisque $x 
\gR y$ est diviseur � droite de~$x$ et~$y$, $\dL x$ et
$\dL y$ sont diviseurs � gauche de $\dL(x  \gR y )$,
donc $\dL x  \jR \dL y$ est diviseur � gauche de $\dL(x 
\gR y )$, et $x  \gR y$ est diviseur � droite de $(\dL x 
\jR \dL y )^*$. 

(iii) On a d�j� not� que $\D$ est multiple � gauche de tout
�l�ment de~$S$. Puisque $\D$ appartient �~$S$, ceci
entra�ne que $\D$ est ppcm � gauche de~$S$. Soit $x$
quelconque dans~$S$: on a alors $\dL x  x   = \dL x 
(\dL x )^*= \D = \D \jL x  = (\D \cL x ) x$, d'o� $\dL x  =
\D \cL x$.\FinDem

\bigskip Nous avons ainsi compl�t� la d�monstration de la
proposition~�\Char�. En effet, il s'agissait de montrer qu'un
mono�de~$M$ comme ci-dessus est un mono�de de Garside. Or, d'apr�s le lemme~�\Simple�(iii), $M$ est
atomique; par d�finition, deux �l�ments quelconques
de~$M$ admettent un ppcm � droite; ils admettent un pgcd
� gauche par le lemme~�\Simple�(iii), et un ppcm � gauche
et un pgcd � droite par le lemme~�\Dual�, donc $M$ est un
mono�de gaussien. Enfin, la partie~$S$ consid�r�e
ci-dessus est finie, elle engendre~$M$, et on a vu qu'elle est
close par chacune des op�rations~$\cR$, $\cL$, $\jR$
et~$\jL$. Par la proposition~�\Alternative�, on d�duit que
$M$ est un mono�de de Garside.\FinDem

\bigskip Les formules de dualit�~�122� sont valables dans
tout mono�de de Garside, et elles d�terminent
les op�rations~$\cL$, $\jL$ et~$\gR$ en termes de leurs
contreparties~$\cR$, $\jR$ et~$\gL$. Ces formules ne
s'appliquent qu'aux �l�ments de l'ensemble~$S$ consid�r�, ce
qui n'est pas une restriction v�ritable: pour des
�l�ments~$x$, $y$ arbitraires, on peut d�terminer les
valeurs de~$x  \cL
y$, $x  \jL y$ et $x  \gR y$ soit en utilisant une
d�composition de~$x$ et~$y$ en produit d'�l�ments
de~$S$, soit --- ce qui est essentiellement �quivalent ---
en rempla�ant~$S$ par une puissance~$S^k$ telle que $x$
et $y$ appartiennent �~$S^k$; on sait alors que
l'ensemble~$S^k$ a la m�mes propri�t�s de cl�ture que~$S$.
Nous terminerons cette section par une formule g�n�rale
exprimant le pgcd de deux �l�ments arbitraires en termes des
op�rations de compl�ment~$\cR$ et~$\cL$.

\Lem\�\Gcd�
{\sl Soit $M$ un mono�de gaussien. Alors,
pour tous~$x , y$ dans~$M$, on a
$$x  \jR y  = (x  \gL y ) \om ((x  \cR y ) \jL (y  \cR x )),\Eq\�120�$$
et, donc, $x  \gL y  = (x  \jR y ) \cL ((x  \cR y ) \jL (y  \cR x ))$.}

\Dem  Posons $x ' = y  \cR x$, $y ' = x  \cR y$, $x '' = x ' \cL y '$,
et $y '' = y ' \cL x '$. Par d�finition, nous avons
$$x  \jR y  = x  y ' = y  x ' 
\hbox{\quad et \quad} x ' \jL y ' = x '' y ' = y '' x '.$$
D'apr�s la premi�re �galit�, $x  \jR y$ est un multiple �
gauche de~$x '$ et~$y '$, donc il existe~$z $ v�rifiant
$x  \jR y  = z  (x ' \jL y ')$. On d�duit $x y ' = z 
x '' y '$, donc $x  = z  x ''$, et, de m�me, $y  =
z y ''$. Donc $z $ est un diviseur � gauche de~$x$
et~$y$, donc de~$x  \gL y$. 

R�ciproquement, supposons $x  = z_1 x_1$ et $y  =
z_1 y_1$. On a $z_1 x_1 y ' = z_1 y_1 x ' = x 
\jR y$, donc $x_1 y ' = y_1 x '$. Il existe donc $z ''$
v�rifiant $x_1 = z '' x ''$ et $y_1 = z '' y ''$. On
d�duit $z_1 z '' x '' y ' =z_1 z '' y '' x ' = x  \jR
y$, d'o� $z_1z '' = z $. Par cons�quent, $z_1$ est un
diviseur � gauche de~$z $, et on conclut que $z $ est le
pgcd � gauche de~$x$ et~$y$.\FinDem


\Sec Structure automatique

\bigskip Nous �tablissons ici que tout groupe de Garside est
bi-automatique (Th�or�me~A de l'introduction), et, de surcro�t, que
cette structure automatique s'explicite tr�s simplement en termes des
op�rations de compl�ment.

Dans un premier temps, nous allons construire une forme
normale dans tout groupe gaussien (de Garside ou non).
Soit $M$ un mono�de quelconque, et $S$ une
partie g�n�ratrice de~$M$. Alors tout �l�ment de~$M$
s'�crit comme produit fini d'�l�ments de~$S$. L'id�e pour obtenir une
d�composition distingu�e, classique pour les groupes de tresses
depuis  [\\\Dlg] [\\\Adk] [\\\Eps] [\\\ElM], consiste � pousser
les �l�ments de~$S$ par exemple vers la gauche, de sorte que le
premier �l�ment soit maximal. 

\Def
Soit $M$ un mono�de, et $S$ une partie de~$M$. Pour $x ,
y  \in M$, on dira que $x  \perp_S y$ est v�rifi� si, pour
tout diviseur � gauche~$s $ de~$y$ appartenant �~$S
\setminus \{1\}$, on a $x s  \notin S$.

\bigskip Le point crucial de la construction est le r�sultat
suivant, qui est une cons�quence imm�diate des r�gles
du calcul des compl�ments:

\Lem\�\Main�
{\sl Soit $M$ un mono�de v�rifiant les
conditions~$(C_0)$, $(C_1)$ et $(C_2)$, et $S$ une
partie de~$M$ close par~$\cR$ et~$\jR$. Soit
$(x_1, \pp, x_p)$ une suite d'�l�ments de~$S$ v�rifiant
$x_i \perp_S x_{i+1}$ pour tout~$i$.
Alors on a $x_1 \perp_S x_2 \ppp x_p$.}

\Dem (Figure~3.1) Supposons  $x_1 s_1 \in S$,
avec $s_1 \in S$  et $s_1 \not=1$. Il s'agit de montrer que
$s_1$ n'est pas un diviseur � gauche de~$x_2 \ppp
x_p$. Posons de proche en proche $s_i = x_i \cR s_{i-1}$
pour $2 \le i \le p$, et montrons par r�currence sur~$i$
qu'on a $x_i s_i \in S$, $s_i \in S$ et $s_i \not= 1$. Pour $i
= 1$, ce sont les hypoth�ses pos�es plus haut. Pour $i \ge
2$, on a
$s_i = x_i \cR s_{i-1}$ et $x_i s_i = x_i \jR s_{i-1}$, d'o� $s_i
\in S$ et $x_i s_i \in S$, puisque $x_i$ est dans~$S$, $s_{i-1}$
aussi par hypoth�se de r�currence, et $S$ est clos
par~$\cR$ et~$\jR$; par ailleurs, la conjonction de $x_{i-1}
s_{i-1} \in S$ et $x_{i-1} \perp_S x_i$ entra�ne que $s_{i-1}$
n'est pas un diviseur � gauche de~$x_i$, c'est-�-dire que $x_i \cR
s_{i-1}$, qui est~$s_i$, ne vaut pas~$1$. On a donc $s_p \not=
1$. Or, par les r�gles du lemme~�\Rules�, on a $s_p = (x_2 \ppp
x_p) \cR s_1$, et
$s_p \not= 1$ signifie donc que $s_1$ n'est pas un diviseur
� gauche de~$x_2 \ppp x_p$.\FinDem

\midinsert
$$\OpenGraphicBox width 67mm height 18mm depth0mm;
\leavevmode\special{illustration Norm4.eps}
\CloseGraphicBox$$
\centerline{{\bf Figure 3.1.} D�composition normale}
\endinsert

\Prop\�\Decomposition�
{\sl Soit $M$ un mono�de gaussien --- ou,
plus g�n�ralement, un mono�de v�rifiant $(C_0^+)$,
$(C_1)$, et $(C_2^+)$ --- et $S$ une partie
g�n�ratrice de~$M$ close par~$\cR$ et~$\jR$. Alors tout
�l�ment de~$M$ poss�de une unique
d�composition~$x_1 \ppp x_p$ avec $x_1,
\pp, x_p \in S$ et $x_i \perp_S x_{i+1}$
pour tout~$i$.}

\Dem On prouve d'abord l'existence d'une
d�composition comme ci-dessus pour tout �l�ment~$x$
de~$M$ par r�currence sur la norme~$\norm(x )$. Pour
$\norm(x ) = 0$, on a $x  = 1$, et le r�sultat est vrai.
Supposons $x  \not= 1$. Notons $\DivL(x )$ l'ensemble
des diviseurs � gauche de~$x$. Soit $x_1$ un �l�ment
de norme maximale dans~$\DivL(x )$. Comme $y  \in
\DivL(x )$ entra�ne $\norm(y ) \le \norm(x )$, un tel
�l�ment~$x_1$ existe, et, comme $\DivL(x )$ contient au
moins un atome, on a $x_1
\not= 1$. Ecrivons $x  = x_1 x '$. On a alors $\norm(x ') \le
\norm(x ) - \norm(x_1) < \norm(x )$, donc, par hypoth�se
de r�currence, $x '$ poss�de une d�composition $x ' = x_2
\ppp x_p$ avec $x_i \in S$ et $x_i \perp_S x_{i+1}$ pour~$i
\ge 2$. On a alors $x  = x_1 x_2 \ppp x_p$, et il s'agit de
montrer $x_1 \perp_Sx_2$. Soit $x$ un diviseur � gauche
propre de~$x_2$ appartenant �~$S$. Alors $x_1 x$ est un
diviseur � gauche de~$x_1 x_2$, donc de~$x$, et on a
$\norm(x_1 x) \ge \norm(x_1) + \norm(x) > \norm(x_1)$,
ce qui, par d�finition de~$x_1$, entra�ne $x_1 x \notin S$.

Pour l'unicit�, il suffit de montrer que, si $(x_1, \pp, x_p)$
est une suite d'�l�ments de~$S$ v�rifiant $x_i \perp_S x_{i+1}$
pour~$1 \le i < p$, alors $x_1$ est d�termin� par le produit~$x_1
\ppp x_p$. En effet, puisque $M$ est simplifiable � gauche,
une r�currence montre ensuite que $x_2$, \pp, $x_p$ sont
d�termin�s de m�me. Posons $x  = x_1 \ppp x_p$. Par
construction, $x_1$ appartient � $\DivL(x ) \cap S$. Supposons
que $x_1s $ soit un diviseur � gauche de~$x$: alors
$s $ est un diviseur � gauche de~$x_2 \ppp x_p$, par le
lemme~�\Main�, on a $x_1 \perp_Sx_2 \pp
x_p$, et donc on d�duit $x_1s  \notin S$. Ceci signifie
que $x_1$ est un �l�ment de norme maximale
dans~$\DivL(x ) \cap S$, ce qui d�termine $x_1$ de
fa�on unique, car $\DivL(x ) \cap S$ est clos par ppcm �
droite et, si $x_1$ et $x '_1$ �taient deux �l�ments
distincts de norme maximale dans $\DivL(x ) \cap S$,
l'�l�ment $x_1 \jR x '_1$ contredirait cette
maximalit�.\FinDem

\bigskip On consid�re maintenant le cas des mono�des de Garside.
Supposons que $M$ soit un mono�de de Garside. Nous
savons que $M$ admet une unique partie g�n�ratrice
minimale, � savoir l'ensemble~$A$ de ses atomes, et que la
cl�ture~$S$ de~$A$ par~$\cR$ et~$\jR$ est la plus petite
partie g�n�ratrice de~$M$ qui soit close par ces op�rations.
Notons que $S$ est �galement la cl�ture de~$A$ par les
op�rations � gauche~$\cL$ et~$\jL$. En effet, d'apr�s le
lemme~�\Dual�(ii), l'ensemble~$S$ est clos par~$\cL$
et~$\jL$, donc, si $\Til S$ d�signe la cl�ture de~$A$
par~$\cL$ et~$\jL$, nous avons $\Til S \ince S$. Comme les
hypoth�ses sont sym�triques, un argument similaire donne $S
\ince
\Til S$, d'o� $S = \Til S$. On note~$\D$ le ppcm de~$S$, et les
op�rations de dualit� r�f�rent au compl�ment dans~$\D$: pour~$x$
dans~$S$, on pose $x^* = x  \cR \D$, et $\dL x  = \D \cL x$. 

Nous allons appliquer la proposition~�\Decomposition� en
prenant pour~$S$ l'ensemble des �l�ments simples. En fait, la
minimalit� n'est requise nulle part, et nous pourrions aussi bien
utiliser � la place de~$S$ une partie g�n�ratrice quelconque qui soit
close pour~$\cR$ et~$\jR$, en particulier toute partie~$S^k$ avec $k
\ge 1$.

La condition d'orthogonalit� mentionn�e dans la
construction s'exprime simplement en termes de pgcd.

\Lem\�\Orthogonal�
{\sl Soit $M$ un mono�de de Garside, et $S$
l'ensemble de ses �l�ments simples. Pour $x , y$ dans~$S$, $x 
\perp_Sy$ �quivaut � $x^* \gL y  = 1$.}

\Dem On a $x  \perp_S y$ si et seulement si, pour tout diviseur �
gauche simple~$s $ de~$y$ distinct de~$1$, $x s $ n'est pas
simple, c'est-�-dire que $x s $ n'est pas un diviseur � gauche
de~$\D$ de~$S$, soit encore que $s $ n'est pas un diviseur �
gauche de~$x  \cR \D$, qui est~$x^*$.\FinDem

\Prop\�\Normal�
{\sl Soit $M$ un mono�de de Garside.
Tout �l�ment~$x$ de~$M$ admet une unique
d�composition de la forme~$x_1 \ppp x_p$ avec
$x_1, \pp, x_p$ simples distincts de~$1$ et $x_i^* \gL
x_{i+1} = 1$ pour tout~$i$. Pour $x  \not= 1$, le premier
facteur de la d�composition est ~$x  \gL \D$.}

\Dem D'apr�s la proposition~�\Decomposition� et le
lemme~�\Orthogonal�, seule la derni�re assertion reste �
d�montrer. Supposons $x  \not= 1$, et soit $x_1 \ppp
x_p$ la d�composition de~$x$ donn�e par la
proposition. Par construction, $x_1$ est un diviseur �
gauche simple de~$x$ de norme maximale. Puisqu'il est
simple, $x_1$ est un diviseur � gauche de~$\D$, donc
de~$x  \gL \D$, et, de l�, nous avons $\norm(x_1) \le
\norm(x  \gL \D)$. D'un autre c�t�, $x  \gL \D$ est
un diviseur � gauche simple de~$x$, donc, par d�finition
de~$x_1$, on doit avoir $\norm(x_1) = \norm(x  \gL
\D)$, d'o� $x_1 = x  \gL \D$  puisque $x_1$ est
un diviseur � gauche de~$x  \gL \D$. \FinDem

\bigskip La forme normale pr�c�dente sera appel�e forme
normale � gauche pour~$M$. De fa�on sym�trique, nous
avons une forme normale � droite:

\Prop\�\Normal�
{\sl Soit $M$ un mono�de de Garside. Tout
�l�ment~$x$ de~$M$ admet une unique d�composition
de la forme~$x_q \ppp x_1$ avec $x_1, \pp, x_q$ simples et
$\dL x_i \gR x_{i+1} = 1$ pour tout~$i$. Pour $x  \not=
1$, le dernier facteur de la d�composition est ~$x 
\gR \D$.}

\bigskip Consid�rons maintenant le cas des groupes de Garside.
 Il se ram�ne � celui des mono�des gr�ce �
l'existence de fractions irr�ductibles.

\Lem\�\Fraction�
{\sl Soit $M$ un mono�de de Garside, et $G$ son groupe
de fractions. Alors tout �l�ment~$z $ de~$G$ admet une
unique d�composition $z  = x \ii y$ avec
$x , y  \in M$ et $x  \gL y  = 1$, et, sym�triquement, une
unique d�composition $z  = x ' {y '}\ii$ avec $x ', y ' \in M$ et $x '
\gR y ' = 1$.}

\Dem Par d�finition, tout �l�ment~$z $ de~$G$ admet une
d�composition $z  = {x '}\ii y '$ avec $x ' , y ' \in M$. 
Posant $x ' = z ' x$ et $y ' = z ' y$ avec $z ' = x '
\gL y '$, on a $x  \gL y  = 1$ et $z  = x \ii y$ par
construction. Par le lemme~�\Gcd�, on obtient
$x  \jR y  = x  (x  \cR y ) = y  (y  \cR x ) = (x  \cR
y ) \jL (y  \cR x )$.  Supposons alors $z  = {x ''}\ii
y ''$ avec $x '', y '' \in M$. De $x \ii y  = (x  \cR y )
(y  \cR x )\ii$ on d�duit $x '' (x  \cR y ) = y '' (y 
\cR x )$, donc, puisque $x  (x  \cR y )$  est le ppcm �
gauche de $x  \cR y$ et $y  \cR x$, l'existence
de~$z ''$ v�rifiant $x '' = z '' x$ et
$y '' = z '' y$. Alors $x '' \gL y '' = 1$ entra�ne $z '' =
1$, soit $x '' = x$ et $y '' = y$.\FinDem

\Def
Dans le contexte du lemme pr�c�dent, les �l�ments~$x$
et~$y$ seront appel�s le {\it d�nominateur} et
le {\it num�rateur gauches} de~$z $, et not�s~$D (z )$
et~$N (z )$; sym�triquement, $x '$ et~$y '$
seront appel�s num�rateurs et d�nominateurs � droite, et
not�s~$\NR(z )$ et~$\DR(z )$. Ainsi, pour tout~$z $ dans~$G$,
on a
$$z  = D (z )\ii N (z ) = \NR(z ) \DR(z )\ii,$$
avec $D (z ) \gL N (z ) = \NR(z ) \gR \DR(z ) = 1$.

\bigskip En rassemblant les �l�ments, nous obtenons
l'existence des formes normales appel�es \<<mixed canonical
forms\>> dans~[\\\Eps, Chap.~9]:

\Prop
{\sl Soit $G$ le groupe de fractions d'un mono�de de Garside~$M$.

(i) Tout �l�ment de~$G$ admet une unique
d�composition de la forme $x_p\ii \ppp x_1\ii y_1 \ppp
y_q$, avec $x_1, \pp, x_p, y_1, \pp, y_q$ �l�ments
simples de~$M$ v�rifiant
$x_1 \gL y_1 = 1$,  et, pour tout~$k$, $x_k^* \gL
x_{k+1} = 1$, et $y_k^* \gL y_{k+1} = 1$.

(ii)  Tout �l�ment de~$G$ admet une unique
d�composition de la forme $x_p \ppp x_1 y_1\ii \ppp
y_q\ii$, avec $x_1, \pp, x_p, y_1, \pp, y_q$ �l�ments
simples de~$M$ v�rifiant $x_1 \gR y_1
= 1$, et, pour tout~$k$, ${}^*x_k \gR x_{k+1} = 1$, et
${}^*y_k \gR y_{k+1} = 1$.}

\bigskip Dans le contexte pr�c�dent, nous dirons que la suite
$(x_p\ii, \pp,  x_1\ii , y_1, \pp,  y_q)$ est la forme
normale � gauche de l'�l�ment~$z $, et que $(x_p, \pp,
x_1, y_1\ii, \pp, y_q\ii)$ en est la forme normale �
droite.

Nous allons montrer que les formes normales pr�c�dentes sont
associ�es � une structure (bi)-automatique. La d�monstration est
extr�mement simple, qui contraste avec les calculs de~[\\\Chb], repris
dans~[\\\Dfx]. Les seuls r�sultats dont nous aurons besoin
sont les suivants:

\Lem\�\Prelim�
{\sl Soit $M$ un mono�de gaussien.

(i) Supposons que $x '$ divise � gauche~$z  x$, et $y '$
divise � gauche~$z  y$. Alors $x ' \gL y '$ divise �
gauche $z  (x  \gL y )$; donc, en particulier, $x  \gL y 
= 1$ entra�ne $x ' \gL y ' = x ' \gL y ' \gL z $.

(ii) Si $\D$ est un �l�ment de Garside de~$M$, on a $(x y )
\gL \D = (x (y  \gL \D)) \gL \D$ pour tous~$x, y$
dans~$M$.}

\Dem (i) Par d�finition, $x ' \gL y '$ divise �
gauche $z x$ et $z y$, donc il divise leur pgcd �
gauche, qui est $z (x  \gL y )$. Pour $x  \gL y  = 1$, on
d�duit que $x ' \gL y '$ divise � gauche $z $, donc
$x ' \gL y ' \gL z $.

(ii) Posons $y ' = y  \gL \D$. Alors $(x y )�
\gL \D$ est le ppcm � droite des diviseurs de~$\D$ qui
divisent � gauche~$x y$, soit $(x y ) \gL \D = \JR \{s \; \D
\cR s = (x y ) \cR s = 1\}$. On a $(x y ) \cR s = y  \cR
(x  \cR s)$; or, pour $s$ divisant~$\D$, $x  \cR s$
divise~$\D$, donc la condition $y  \cR (x  \cR s) = 1$ dans
la formule pr�c�dente est �quivalente � $y ' \cR (x  \cR s) =
1$, d'o�
$$x y  \gL \D 
= \JR \{s \; \D \cR s = y  \cR (x  \cR s) = 1\}
= \JR \{s \; \D \cR s = y ' \cR (x  \cR s) = 1\}
= x y ' \gL \D. \eqno{\Block}$$

\bigskip Il est alors tr�s facile de calculer, pour $s $ simple, la
forme normale d'un �l�ment~$z s ^{\pm 1}$ � partir de celle
de~$z $. Dans le cas de la forme normale � gauche, il est
commode de d�crire le passage de la forme normale de~$z $ �
celle de~$z  s \ii$, et � celle de~$z  \D$:  le passage
de~$z $ �~$z s $ s'en d�duit en �crivant $z  s  = z  \D
(s ^*)\ii$.

\Lem\�\Normale�
{\sl Soit $G$ le groupe de fractions d'un mono�de de Garside~$M$, et $(y_q\ii, \pp, y_1\ii,
x_1, \pp, x_p)$ la forme normale � gauche d'un
�l�ment~$z $ de~$G$. 

(i) Pour $s $ simple, la forme normale � gauche
de~$z s \ii$ est $({y '}_{\!\!q+1}\ii, \pp, y '_1{}\ii,
x '_1, \pp, x '_p)$, avec $s_{p+1} = s $, puis $x '_i = x_i \cL
s_{i+1}$ et $s_i = s_{i+1} \cL x_i$ pour
$p \ge i \ge 1$, ensuite $t_1 = s_1$, $y '_j = t_jy_j \gL
\D$ et $t_{j+1} = y_j \cR (t_jy_j)$ pour $1 \le j
\le q$, et, enfin, $y '_{q+1} = t_{q+1}$.

(ii) La forme normale � gauche de~$z \D$ est
$(y_q\ii, \pp, y_2\ii, y_1^*, x_1^{**}, \pp,
x_p^{**})$.

(iii) La forme normale � gauche de~$z \D\ii$ est
$(y_q\ii, \pp, y_1\ii, ({}^*x_1)\ii, {}^{**}x_2, \pp,
{}^{**}x_p)$.}

\Dem (i) Par construction, on a $x '_i s_{i+1} = s_i
x_i$ pour tout~$i$, et $y '_j t_{j+1} = t_j
y_j$ pour tout~$j$, donc le diagramme
$$\OpenGraphicBox width 102mm height 19mm depth0mm;
\leavevmode\special{illustration NormMul4.eps}
\CloseGraphicBox$$ 
\vglue-3mm\noindent
commute, et on obtient ${y '}_{\!\!q+1}\ii
\ppp y '_1{}\ii x '_1 \ppp x '_p =  y_{q}\ii \ppp
y_1\ii x_1 \ppp x_p s \ii = z  s \ii$. La seule
question est de montrer que la suite  $({y '}_{\!\!q+1}\ii, \pp,
y '_1{}\ii, x '_1, \pp, x '_p)$ est bien une forme normale �
gauche. Par construction, tous les facteurs sont simples, et il
s'agit de v�rifier les conditions de pgcd. 

Consid�rons d'abord le cas de~$x '_i$ et~$x '_{i+1}$.
Par d�finition, on a 
$$x '_i x '_i{}^* s_i^{**} 
= \D s_i^{**} 
= s_i \D
= s_i x_i x_i^*
= x '_i s_{i+1} x_i^*,$$
donc $x '_i{}^* s_i^{**} = s_{i+1} x_i^*$,
ce qui montre que $x '_i{}^*$ est un diviseur �
gauche de~$s_{i+1} x_i^*$. Par ailleurs, on a $x '_{i+1}
s_{i+2} = s_{i+1} x_i$, donc $x '_{i+1}$ est un diviseur �
gauche de~$s_{i+1} x_{i+1}$. Comme on a $s_{i+1} \gL
x '_{i+1} = 1$ par construction, et $x_i^* \gL x_{i+1} =
1$ par hypoth�se, le lemme~�\Prelim�(i) donne $x '_i{}^* \gL
x '_{i+1} = 1$, comme souhait�.

Consid�rons maintenant le cas de~$y '_1$ et~$x '_1$. A
nouveau, $x '_1$ est diviseur � gauche de~$s_1 x_1$, et,
de m�me, $y '_1$ est diviseur � gauche de~$s_1 y_1$.
On a $s_1 \gL x '_1 = 1$ par construction, et $x_1 \gL
y_1 = 1$ par hypoth�se, d'o� $x '_1 \gL y '_1 = 1$ par le
lemme~�\Prelim�(i).

Consid�rons finalement le cas de~$y '_j$ et~$y '_{j+1}$. Par
d�finition, on a $y '_j = t_j y_j \gL \D$. Or, par
hypoth�se, on a aussi $y_j = (y_j \ppp y_q) \gL \D$. Par
le lemme~�\Prelim�(ii), on  d�duit $y '_j = (t_j y_j \ppp
y_q) \gL \D = (y '_j y '_{j+1} \ppp y '_{q+1}) \gL \D$,
donc, en particulier, $y '_j{}^* \gL (y '_{j+1} \ppp
y '_{q+1}) = 1$, et, a fortiori, $y '_j{}^* \gL y '_{j+1} =1$.

(ii) On a $x_i \D = \D x_i^{**}$ pour tout~$i$, et,
par ailleurs, $y_1 y_1^* = \D$, donc le diagramme
$$\OpenGraphicBox width 92mm height 19mm depth0mm;
\leavevmode\special{illustration NormDelta4.eps}
\CloseGraphicBox$$ 
\vglue-3mm\noindent
est commutatif, et on obtient $y_q\ii \ppp y_2\ii
y_1^* x_1^{**} \ppp x_p^{**} = z  \D$. La seule
question est � nouveau de montrer que la suite
$(y_q\ii, \pp, y_2\ii, y_1^*, x_1^{**}, \pp,
x_p^{**})$ est une forme normale � gauche, soit, les facteurs
�tant clairement simples, de montrer que les conditions de pgcd
entre deux termes cons�cutifs sont v�rifi�es. Or, pour tout~$i$,
on a $(x_i^{**})^* \gL x_{i+1}^{**} = (x_i^* \gL
x_{i+1})^{**} = 1^{**} = 1$, puisque l'application $x 
\mapsto x^{**}$ induit un automorphisme de~$M$. Ensuite,
on a $y_1^* \gL y_2 = 1$ par hypoth�se, puis, pour $j \ge
2$, $y_j^* \gL y_{j+1} = 1$, toujours par hypoth�se.

(iii) L'argument est similaire. On a cette fois ${}^{**}x_i \D =
\D x_i$ pour tout~$i$, et ${}^*x_1 x_1 = \D$, d'o� le
diagramme commutatif
$$\OpenGraphicBox width 92mm height 19mm depth0mm;
\leavevmode\special{illustration NormDeltaInv4.eps}
\CloseGraphicBox$$ 
\vglue-3mm\noindent
qui donne $y_q\ii \ppp y_1\ii ({}^*x_1)\ii{}^{**}x_2
\ppp {}^{**}x_p = z  \D\ii$. Il s'agit encore de v�rifier les
conditions de pgcd entre termes voisins: pour tout~$i$, on a 
$({}^{**}x_i)^* \gL {}^{**}x_{i+1} = {}^{**}(x_i^* \gL
x_{i+1}) = {}^{**}1 = 1$, et, enfin, $({}^*x_1)^* \gL y_1
= x_1 \gL y_1 = 1$.\FinDem

\Prop
{\sl Tout groupe de Garside est bi-automatique.}

\Dem Soit $M$ un mono�de de Garside, et $G$ son
groupe de fractions. Soit $S$ l'ensemble des �l�ments simples
de~$M$. Consid�rons le langage~$L$ form� par les formes
normales � gauche, consid�r�es comme mots sur
l'alphabet~$S \cup S\ii$. D'abord $L$ est un langage r�gulier,
car l'appartenance d'un mot �~$L$ est d�finie par des
conditions locales consistant en une liste (finie) de lettres
permises apr�s chaque lettre: apr�s une lettre
n�gative~$y \ii$, les lettres autoris�es sont les lettres
positives~$x$ v�rifiant $x  \gL y  = 1$, et les lettres
n�gatives~$y '{}\ii$ v�rifiant $y '{}^* \gL y  = 1$; apr�s
une lettre positive~$x$, les lettres autoris�es sont les lettres
positives~$x '$ v�rifiant $x^* \gL x ' = 1$.

Ensuite la formule explicite du lemme~�\Normale�(i) montre
que la distance entre la forme normale d'un �l�ment~$z $ et
celle de~$z  s \ii$ est uniform�ment born�e par~$2$ (en
termes de l'alphabet~$S$), ce qui �tablit la propri�t� du
$2$-compagnon de route --- ou \<<$2$-fellow traveller
property\>>. On d�duit que le langage des formes normales �
gauche est associ� � une structure automatique.

Enfin, la sym�trie de la forme normale entra�ne une propri�t�
de compagnon de route similaire pour la multiplication �
gauche, et donc le langage~$L$ est associ� � une structure
bi-automatique. \FinDem

\bigskip A c�t� du r�sultat d'existence pr�c�dent, qui ne
d�crit pas explicitement les automates mis en jeu, nous
allons maintenant construire des automates tr�s simples calculant les
formes normales. Nous consid�rerons ici seulement le cas des
mono�des. Le cas des groupes n'est pas directement couvert par cette
approche, mais les algorithmes d�crits � la section~4
montrent comment se ramener � des fractions
irr�ductibles, et, de l�, du groupe au mono�de.

Le cas de la forme normale � droite est le plus facile, et la
solution est une extension naturelle de celle d�crite dans 
[\\\Eps, chapitre~9] pour les groupes de tresses. Nous allons
d�crire un automate fini d'alphabet~$A$ et d'ensemble
d'�tats~$S$ calculant le dernier facteur de la forme normale �
droite, au sens o� l'�tat final obtenu apr�s lecture d'un mot~$u$
par l'automate est $\cl u \gR \D$, o� $\cl u$ d�signe la classe du
mot~$u$ dans le mono�de. On rappelle qu'un tel automate est la
donn�e d'une fonction~$T: S \times A \ra S$ et d'un �tat initial~$q$;
l'�tat final de l'automate apr�s lecture du mot~$u$ est, par d�finition,
l'�tat~$T(q, u)$ d�fini inductivement, en notant $\e$ le mot vide, par
$T(q, \e) = q$ et $T(q, ux) = T(T(q, u), x)$. On part de
formules de calcul de pgcd.

\Lem\�\Pgcd�
{\sl Soit $M$ un mono�de de Garside. Pour
$s , t $ simples, on a
$$s t  \gL \D = {}^*(t^* \cL s^{**}), 
\hbox{\qquad et \qquad}
s t  \gR \D = ({}^{**}t  \cR {}^*s )^*.\Eq\�200�$$

}\Dem La forme normale � gauche de~$s $ est $(s )$, donc,
par le lemme~�\Normale�(ii), celle de~$s  \D$ est $(\D,
s ^{**})$, et celle de~$s  t $, qui est $s  \D (t ^*)\ii$, est 
$({}^*(t^* \cL s^{**}), s^{**} \cL t^*)$. Or, par d�finition, le
premier terme de cette suite est~$s t  \gL \D$.

Un argument sym�trique montre que la forme normale � droite
de~$\D t $ est $({}^{**}t , \D)$, et que celle de~$s t $ est
$({}^*s  \cR {}^{**}t , ({}^{**}t  \cR {}^*s )^*)$. Par
d�finition, le dernier terme de cette derni�re suite est~$s t 
\gR \D$.\FinDem

\Prop
{\sl Soit $M$ un mono�de de Garside, $A$ l'ensemble de
ses atomes, $S$ l'ensemble de ses simples, et $\D$ l'�l�ment
simple maximal. D�finissons
$T: S \times A \ra S$ par $T(s , a  ) = ({}^{**}a   \cR
{}^*s)^*$. Alors, pour tout mot~$u$ sur~$A$, on a $\cl u \gR \D
= T(1, u)$, c'est-�-dire que le r�sultat de la lecture de~$u$
par l'automate~$(T, 1)$ est le dernier terme de la forme
normale � droite de~$\cl u$.}

\Dem On a trivialement $\cl\e \gR \D = 1 = T(1, \e)$,
donc, pour montrer le r�sultat inductivement, il suffit de
d�montrer l'�galit�
$$x a   \gR \D = T(x  \gR \D, a  )$$
pour $x$ dans~$M$ et $a  $ dans~$A$. Par le
lemme~�\Prelim�(ii) (en fait, sa contrepartie pour le pgcd �
droite), on a $(x a  ) \gR \D = ((x  \gR \D)a  ) \gR
\D$. Comme $x  \gR \D$ et $a  $ sont simples, le r�sultat
d�coule alors imm�diatement de la formule~�200�.\FinDem

\Rem
Comme dans~[\\\Eps], nous pouvons consid�rer un
transducteur, d�fini comme un automate muni d'une
fonction de sortie~$O$ envoyant $S \times A$ dans l'ensemble des
mots sur~$A$. On d�finit alors la sortie produite par la lecture du
mot~$u$ comme le mot~$O(q, u)$ inductivement d�fini par $O(q,
\e) = \e$ et $O(q, ua  ) = O(q, u) O(T(q, u), a  )$. La
d�monstration pr�c�dente montre que, si nous posons $O(s, a  ) =
{}^*s \cR {}^{**}a    $, alors, pour tout  mot~$u$ sur~$A$, on a $\cl u
= \cl{O(1, u)} \om T(1, u)$: c'est dire que le mot~$O(1, u)$ repr�sente
le reste du mot~$u$ lorsque le dernier terme de la forme
normale � droite a �t� retir�. En faisant lire par le
transducteur le mot~$O(1, u)$, on obtiendra de m�me
l'avant-dernier terme de la forme normale � droite de~$\cl u$,
et ainsi de suite. Cette it�ration fournit un algorithme de
complexit� quadratique d�terminant la forme normale � droite.

\Ex
La figure~3.1 repr�sente le transducteur calculant la forme normale
� droite pour le mono�de $\Mon{a  , b  \; a  b a   =
b^2}$. Les �tats (domaines cercl�s) correspondent aux �l�ments
simples. Les fl�ches pleines repr�sentent la lecture de~$a  $, les
tiret�es la lecture de~$b $; la pr�sence d'une �tiquette~$u$ sur
une fl�che~$x$ entre les �tats~$s $ et~$t $ signifie qu'on a
$T(s , x) = t $ et $O(s , x) = u$, c'est-�-dire que, partant de
l'�tat~$s $ et lisant la lettre~$x$, on passe dans l'�tat~$t $ en
produisant le mot~$u$.

\midinsert
$$\OpenGraphicBox width 55mm height 48mm depth0mm;
\leavevmode\special{illustration Transducteur4.eps}
\CloseGraphicBox$$ 
\centerline{{\bf Figure 3.2.} Transducteur pour $\Mon{a  , b  \;
a  b a   = b^2}$}
\endinsert

\bigskip Pour la forme normale � gauche, nous pouvons trivialement
obtenir des r�sultats analogues en consid�rant des
pseudo-automates lisant les mots de droite � gauche, mais la v�ritable
question est l'existence d'automates standard lisant de
gauche � droite. L'approche pr�c�dente �choue, car il est en g�n�ral
faux que la valeur de~$(x a  ) \gL \D$ ne d�pende que des valeurs
de~$x  \gL \D$ et de~$a  $: dans le groupe de
tresses~$B_3$, on a $\s_1\s_2 \gL \D = \s_1
\s_2^2 \gL \D = \s_1 \s_2$, mais $\s_1 \s_2 \s_1 \gL
\D = \D \not= \s_1 \s_2^2 \s_1 \gL \D = \s_1 \s_2$. Par
contre, la construction est encore possible en prenant comme
ensemble d'�tats l'ensemble~$P^{P}$, o� $P$ est l'ensemble des
�l�ments primitifs � droite de~$M$, c'est-�-dire la cl�ture des atomes
par l'op�ration~$\cR$. 

\Prop
{\sl Soit $M$ un mono�de de Garside, $A$
l'ensemble de ses atomes, et $P$ l'ensemble de ses
�l�ments primitifs � droite. D�finissons $T: P^{P} \times A
\ra P^{P}$ par 
$$T(f, a  ) = r_a   \comp f \Eq\�170�$$
o� $r_a  $ est d�finie pour $a   \in A$ et $p \in P$ par
$r_a  (p) = a   \cR p$. Alors, pour tout mot~$u$ sur~$A$,
on a 
$$\cl u \gL \D = \bigvee \{p \in P \; T(\id, u)(p) = 1\}$$
--- et donc l'automate $(T, \id)$ d�termine le premier
facteur de la forme normale � gauche de~$\cl u$.}

\Dem Pour~$x$ dans~$M$, notons $f_x$ l'application
de~$P$ dans~$P$ d�finie par $f_x (p) = x  \cR p$.
On a $f_1 = \id$ par d�finition, et, d'apr�s les formules des
compl�ments, il vient, pour~$x  \in M$, $a   \in A$ et $p \in
P$,
$$f_{x a  }(p) = (x a  ) \cR p = a   \cR (x  \cR p) =
a   \cR f_x (p) = r_a  (f_x (p)),$$ 
soit $f_{x a  } = r_a   \comp f_x$, et, inductivement,
$f_{\overline u} = T(\id, u)$ pour tout mot~$u$
sur~$A$. Or, pour $p$ primitif, $p$ est un diviseur �
gauche de~$x$ si et seulement si on a $x  \cR p = 1$,
soit $f_x (p) = 1$. Le seul point � montrer est donc que
$x  \gL \D$ est �gal au ppcm � droite~$x '$ des
�l�ments primitifs divisant~$x$ � gauche. Or, tout
�l�ment primitif est simple, donc $x '$ est un diviseur �
gauche de~$x  \gL \D$. Inversement, $x  \gL \D$ est
simple, donc, d'apr�s les r�sultats de la section~1, il est un
ppcm � droite d'�lements primitifs, lesquels sont
n�cessairement des diviseurs � gauche de~$x$.\FinDem

\Rem
L'approche pr�c�dente s'applique �galement � la
forme normale � droite. Introduisons l'ensemble~$\Til P$
des �l�ments {\it primitifs � gauche} comme la
cl�ture des atomes par l'op�ration~$\cL$. Pour~$x  \in M$,
d�finissons $\Til f_x  : \Til P \ra \Til P$ par $\Til f_x (p) = p \cL
x$. Alors la fonction~$\Til f_x$ est calcul�e inductivement par la
r�gle $\Til f_{x a  }(p) = \Til f_x (p \cL a  )$. On obtient donc
$\Til f_{\overline u} =
\Til T(\id, u)$, o�
$\Til T = \Til P^{\Til P} \times A \ra \Til
P^{\Til P}$ est d�termin�e par
$$\Til T(f, a  ) = f \comp \Til r_a  , \Eq\�171�$$
avec $r_a   : p \mapsto p \cL a  $, formule qui est la
contre-partie exacte de~�170�. On obtient alors, pour tout
mot~$u$ sur~$A$,
$$\cl u \gR \D = \Til{\bigvee} \{p \in \Til P \; \Til
T(\id, u)(p) = 1\}:$$
l'automate~$(\Til T, \id)$ d�termine le dernier facteur de la
forme normale � droite de~$\cl u$.
Ces r�sultats montrent � nouveau le r�le central des
op�rations~$\cR$ et~$\cL$: les automates pr�c�dents sont
essentiellement la table de ces op�rations sur les cl�tures des atomes. 

\Ex 
La figure~3.2 montre l'automate calculant le pgcd � gauche avec~$\D$
dans le cas du mono�de de tresses~$B_3^+$, de pr�sentation
$\Mon{a  , b  \;
a  b a   = b a  b }$. Il y a deux atomes, � savoir $a  $ et~$b $,
et cinq �l�ments primitifs � droite (et � gauche), � savoir $1,
a  , b , a  b , b a  $. On obtient un automate � 20~�tats,
repr�sent� sur la figure~3.2 (les fl�ches en plein
repr�sentent~$a  $, les fl�ches en tiret� repr�sentent~$b $).

\midinsert
$$\OpenGraphicBox width 135mm height 45mm
depth0mm;
\leavevmode\special{illustration Pgcd4.eps}
\CloseGraphicBox$$ 
\centerline{{\bf Figure 3.2.} Automate pour le pgcd � gauche
dans~$B_3$}
\endinsert


\Sec Pr�sentations

\bigskip On montre ici que tout groupe de Garside admet une
pr�sentation d'un certain type, dit compl�ment�, et que toutes
les op�rations du mono�de se calculent � partir d'une telle
pr�sentation au moyen d'une op�ration combinatoire appel�e
redressement de mots. Les r�sultats du d�but de la section
figurent, avec des notations diff�rentes, dans~[\\\Dfx], 
auquel nous renvoyons pour d'autres d�tails et les
d�monstrations manquantes. 

Pour tout ensemble~$\Sigma$, nous noterons~$\Mo(\Sigma)$
l'ensemble des mots sur~$\Sigma$, c'est-�-dire le mono�de libre
de base~$\Sigma$; le mot vide est not�~$\e$. Si $\Sigma$ est
une partie g�n�ratrice d'un mono�de~$M$, alors, par
d�finition, tout �l�ment~$x$ de~$M$ admet des
d�compositions comme produit d'�l�ments de~$\Sigma$:
pour $w$ dans~$\Mo(\Sigma)$, on notera comme
pr�c�demment $\cl w$ l'image~$x$ de~$w$ dans~$M$; on
dira alors que $w$ est une expression de~$x$, et que $x$ est
l'�valuation de~$w$ dans~$M$.

\Def
Soit $M$ un mono�de v�rifiant les
conditions~$(C_0)$, $(C_1)$ et $(C_2)$, et  $\Sigma$ est une
partie g�n�ratrice de~$M$. On appelle {\it s�lecteur de ppcm}
sur~$\Sigma$ toute application (partielle)~$f$ de~$\Sigma \times
\Sigma$ dans~$\Mo(\Sigma)$ tel que, pour $a  , b  \in \Sigma$,
$f(a  , b )$ est une expression de~$a   \cR b $ lorsque ce
dernier existe.

\bigskip Par d�finition, on a $a   \cR a   = 1$
pour tout~$a  $ dans~$\Sigma$, donc, si $f$ est un
s�lecteur de ppcm sur~$\Sigma$, et si $M$ satisfait � la
condition~$(C_0)$, c'est-�-dire n'admet pas
d'inversible autre que~$1$, alors, n�cessairement,
$f(a  , a  )$ est le mot vide~$\e$. Par ailleurs, par
d�finition, $a   \cR b $ existe si et seulement si $b 
\cR a  $ existe, et, par cons�quent, le domaine de tout
s�lecteur de ppcm est un sous-ensemble sym�trique
de~$\Sigma \times \Sigma$.

\Def 
Soit $\Sigma$ un ensemble non vide. On appelle
{\it fonction de redressement} sur~$\Sigma$ une application
partielle de~$\Sigma \times \Sigma$ dans~$\Mo(\Sigma)$ v�rifiant
$f(a  , a  ) = \e$ pour tout~$a  $, et telle que le domaine
de~$f$ est sym�trique. On note alors $\Rf$ la famille des
relations $a   f(a  , b ) = b  f(b , a  )$ pour $(a  , b )
\in \Dom(f)$, et $\eqfp$ la congruence sur~$\Mo(\Sigma)$
engendr�e par~$\Rf$. On dit qu'une pr�sentation de mono�de
est {\it compl�ment�e} si elle est associ�e � une
(n�cessairement unique) fonction de redressement.

\Prop [\\\Dfx]
{\sl Soit $M$ un mono�de gaussien --- ou,
plus g�n�ralement, un mono�de v�rifiant les
conditions~$(C_0^+)$, $(C_1)$ et $(C_2)$. Soit
$\Sigma$ une partie g�n�ratrice quelconque de~$M$, et $f$ un
s�lecteur de ppcm sur~$\Sigma$. Alors $f$ est une
fonction de redressement sur~$\Sigma$ et $\Mon{\Sigma
\; \Rf}$ est une pr�sentation compl�ment�e de~$M$.}

\Dem Notons $\sim$ la congruence sur~$\Mo(\Sigma)$ telle que
$M$ est $\Mo(\Sigma) / \! \sim$. Par d�finition d'un s�lecteur
de ppcm, on a $a   f(a  , b ) \sim b  f(b , a  )$
pour $a  $, $b  \in \Dom(f)$, donc $u \eqfp v$
entra�ne $u \sim v$ puisque les paires $\{a   f(a  ,
b ), b  f(b , a  )\}$ engendrent~$\eqfp$.

R�ciproquement, nous montrons que $u \sim v$ entra�ne $u
\eqfp v$ par r�currence sur~$\norm(\cl u)$. Pour $\norm(\cl
u) = 0$, on a  $\cl u = \cl v = 1$, donc, par~$(C_0)$, $u = v =
\e$, et $u \eqfp v$. Supposons
$u, v \not= \e$. On �crit $u = a   u_1$, $v = b  v_1$, avec
$a   , b  \in \Sigma$. L'hypoth�se $\cl u = \cl v$ signifie que
$\cl u$ est un multiple commun � droite de~$a  $
et~$b $. Par~$(C_2)$, il existe un mot~$w$ v�rifiant $\cl
u = \cl v = (a   \jR b ) \cl w$, d'o� $u = a   u_1  \sim
a   f(a  , b ) w \sim b  f(b , a  ) w \sim b  v_1 = v$.
Par~$(C_1)$, on d�duit $u_1 \sim f(a  , b ) w$ et $v_1 \sim
f(b , a  ) w$. Or, par~$(C_0^+)$, on a
$\norm(\cl{f(a  , b )w}) \le \norm(\cl u) - \norm(a  ) <
\norm(\cl u)$, et, de m�me, $\norm(\cl{f(b , a  )w}) <
\norm(\cl u)$. Appliquant l'hypoth�se de
r�currence, on d�duit $u_1 \eqfp f(a  , b ) w$, et $v_1 \eqfp
f(b , a  ) w$, d'o� $u = a   u_1 \eqfp a   f(a  ,
b ) w \eqfp b  f(b , a  ) w \eqfp b  v_1 = v$, et donc $u
\eqfp v$.\FinDem

\Question
{\sl Le r�sultat pr�c�dent reste-t-il valable lorsque la
condition~$(C_0^+)$ (atomicit�) est affaiblie en~$(C_0)$ (pas
d'inversible autre que~$1$)?}

\bigskip Si $M$ est un mono�de gaussien, $\Sigma$ une partie
g�n�ratrice de~$M$, et $f$ un s�lecteur de ppcm sur~$\Sigma$,
alors toutes les op�rations de~$M$ se calculent � partir de~$f$
de fa�on effective. Pour le d�montrer, nous introduisons une
op�ration combinatoire sur les mots appel�e {\it
redressement} (\<<reversing\>> en anglais). 

Par d�finition, si $f$ est un s�lecteur de ppcm sur~$\Sigma$, le
mot $f(a  , b )$ est une expression de l'�l�ment~$a   \cR
b $ de~$M$ pour tous~$a  $, $b $ dans~$\Sigma$. L'id�e est
d'�tendre l'application~$f$ en une op�ration binaire
partielle not�e~$\cRf$ sur~$\Mo(\Sigma)$ de sorte que, pour tous
mots~$u$, $v$ sur~$\Sigma$, le mot~$u \cRf v$ soit une
expression du compl�ment~$\cl u \cR \cl v$, quand ce dernier
existe.

Dans toute la suite, lorsque $\Sigma$ est un alphabet, nous
introduirons une copie disjointe not�e~$a  \ii$ pour
chaque lettre~$a  $ de~$\Sigma$, et nous noterons~$\Sigma\ii$
l'ensemble des lettres~$a  \ii$. Pour tout mot~$w$
sur~$\Sigma \cup \Sigma\ii$, on note $w\ii$ le mot obtenu en
�changeant chaque lettre~$a  $ avec la lettre~$a  \ii$
correspondante, et en renversant l'ordre des lettres. Ainsi, si
$G$ est un groupe engendr� par~$\Sigma$ et si le mot~$w$
repr�sente l'�l�ment~$x$ de~$G$, alors $w\ii$
repr�sente~$x \ii$.

\Def [\\\Dff] [\\\Dfx]
Soit $f$ une fonction de redressement
sur~$\Sigma$. Pour~$w$, $w'$ mots sur~$\Sigma \cup
\Sigma\ii$, on dit que $w$ est {\it $f$-redressable} en~$w'$, not�
$w \vRf w'$, si on peut passer de~$w$ �~$w'$ en un nombre 
fini d'�tapes consistant � remplacer un sous-mot de la
forme~$a  \ii b $ avec $a  , b  \in \Sigma$ par le mot $f(a  ,
b ) f(b , a  )\ii$ correspondant. Pour $u$, $v$ mots
sur~$\Sigma$, on d�finit $u \cRf v$ comme l'unique mot~$u'$
sur~$\Sigma$ tel qu'il existe un mot~$v'$ sur~$\Sigma$ v�rifiant
$u\ii v \vRf v' {u'}\ii$, s'il existe, et $u \jRf v$ comme $u \om
(u \cRf v)$.

\bigskip On associe � chaque redressement de mot un graphe 
planaire (voisin d'un diagramme de Dehn) compos� de fl�ches
verticales et horizontales �tiquet�es par des �l�ments
de~$\Sigma$, et tel que le redressement du mot~$a  \ii b $ en
$f(a  , b ) f(b , a  )\ii$ se traduit par la fermeture du motif
$$\OpenGraphicBox width 88mm height 19mm depth0mm;
\leavevmode\special{illustration Rev4.eps}
\CloseGraphicBox$$ 
Nous renvoyons �~[\\\Dgd, chapitre~II], et
consid�rons ici simplement un exemple.

\Ex
Soit $\Sigma = \{a  , b \}$, et soit $f$ l'application de~$\Sigma^2$
dans~$\Mo(\Sigma)$ d�finie par $f(a  , b ) = b a  $, $f(b ,
a  ) =
b $, $f(a  , a  ) =  f(b , b ) = \e$. Le
mono�de~$\Mon{\Sigma \; \Rf}$ est ici
$\Mon{a  , b  \; a  b a   = b^2}$. La figure ci-dessous
illustre le redressement du mot $a  \ii
b  a  ^2$ en le mot $b  a   b^2 a  
b \ii a  \ii b \ii$, qui donne donc $a   \cRf b a  ^2 =
b a  b^2a  $ et $b a  ^2 \cRf a   = b a  b $.
$$\OpenGraphicBox width 50mm height 33mm
depth0mm;
\leavevmode\special{illustration RevEx4.eps}
\CloseGraphicBox$$ 

\bigskip L'op�ration~$\cRf$
est en g�n�ral une op�ration partielle sur~$\Mo(\Sigma)$, non
n�cessairement d�finie pour tous les mots: comme $\cRf$
co�ncide avec~$f$ sur $\Sigma \times \Sigma$, c'est le cas si
$f$ n'est pas partout d�finie sur~$\Sigma
\times \Sigma$, mais, m�me si $f$ est partout d�finie, il se peut
que le redressement d'un mot ne se termine pas en un
nombre fini d'�tapes. Comme dans la section~1, nous
noterons $u \cRf v = \bot$ quand $u \cRf v$ n'existe pas, et
nous �tendons $\cRf$ en une op�ration partout d�finie
sur~$\Mo(\Sigma) \cup \{\bot\}$ en posant $u
\cRf \bot = \bot
\cRf u = \bot \cRf \bot = \bot$ pour tout~$u$, et de m�me
pour le produit des mots. De m�me, nous
�tendons~$\eqfp$ en une congruence sur~$\Mo(\Sigma)
\cup \{\bot\}$ en d�clarant $\bot \eqfp \bot$ vrai,
et $u \eqfp \bot$ faux pour tout~$u$ dans~$\Mo(\Sigma)$. 

\Lem\�\Equivalence� [\\\Dff] 
{\sl Soit $f$ une fonction de redressement
sur~$\Sigma$. Alors, pour tous mots~$u, v$ sur~$\Sigma$, on a $u(u
\cRf v) \eqfp v (v \cRf u)$.}

\bigskip D'apr�s nos conventions, le r�sultat pr�c�dent
signifie que soit $u \cRf v$ et $v \cRf u$ sont d�finis et 
on a l'�quivalence annonc�e, soit ni l'un ni l'autre n'est
d�fini. La d�monstration est une induction facile sur le
nombre d'�tapes �l�mentaires de redressement.

\Prop [\\\Dfx] \�\Expression�
{\sl Soit $M$ un mono�de gaussien --- ou,
plus g�n�ralement, un mono�de v�rifiant les
conditions~$(C_0^+)$, $(C_1)$ et $(C_2)$ ---, $\Sigma$ une
partie g�n�ratrice de~$M$, et $f$ un s�lecteur de
ppcm sur~$\Sigma$. Alors, pour tous mots~$u$, $v$
dans~$\Mo(\Sigma)$, le mot~$u \cRf v$ existe
dans~$\Mo(\Sigma)$ si et seulement si l'�l�ment $\cl u \cR
\cl v$ existe dans~$M$, et, dans ce cas, $u \cRf v$ est une
expression de $\cl u \cR \cl v$, et $u \jRf v$ est une
expression de~$\cl u \jR \cl v$.}

\Dem Le lemme~�\Equivalence� montre que, si $u \cRf v$
est d�fini, alors la classe de~$u \jRf v$ est un multiple �
droite commun des classes de~$u$ et~$v$, donc,
par~$(C_2)$, le ppcm � droite de ces classes existe.

Inversement, montrons par induction sur~$n$ que, si $u$ et
$v$ sont deux mots tels que $\cl u \jR \cl v$ existe et qu'on
ait $\norm(\cl u \jR \cl v) = n$, alors $u \cRf v$ existe
et repr�sente~$\cl u \cR \cl v$. Pour $n = 0$, on a  $u = v =
\e$, et les r�sultats ont triviaux. Supposons $n \ge 1$. Pour $u
= \e$ ou $v = \e$, les r�sultats sont � nouveau triviaux.
Supposons
$u =
a   u_1$ et $v = b  v_1$ avec $a  , b  \in \Sigma$, et soit
$z  = \cl u \jR \cl v$. Par hypoth�se, $z $ est
multiple � droite commun �~$a  $ et~$b $, donc $f(a  ,
b )$ et $f(b , a  )$ sont d�finis. Ensuite $z$ est multiple
� droite commum de $\cl{\mathstrut a   u_1}$ et $\cl{a  
f(a  , b )}$, donc $\cl{\mathstrut u_1}$ et $\cl{f(a  ,
b )}$ ont un multiple � droite commun, donc un ppcm �
droite. Or, par construction, on a $\norm(\cl{\mathstrut
u_1} \jR \cl{f(a  , b )}) \le \norm(z) - \norm(a  ) = n-1$,
donc, par hypoth�se de r�currence, $u_1 \cRf f(a  , b )$
existe et il repr�sente $\cl{\mathstrut u_1} \cR \cl{f(a  ,
b )}$. De m�me, $v_1 \cRf f(b , a  )$
existe et  repr�sente $\cl{\mathstrut v_1} \cR
\cl{f(b , a  )}$; finalement, en posant $u_2 = f(a  , b )
\cRf u_1$ et $v_2 = f(xy, a  ) \cRf v_1$, on a de
m�me que $u_2 \cRf v_2$ existe et  repr�sente
$\cl{u_2} \cR \cl{v_2}$. Donc  $u \cRf v$ est
d�fini, et il repr�sente
$$(\cl{\mathstrut v_1} \cR
\cl{f(b , a  )}) \om ((\cl{f(b , a  )} \cR \cl{\mathstrut
v_1}) \cR (\cl{f(a  , b )} \cR \cl{\mathstrut u_1})),$$
lequel est, d'apr�s les formules de compl�ment, $\cl u \cR \cl
v$.\FinDem

\Def
Soit $f$ une fonction de redressement
sur~$\Sigma$. Pour $u, v$ mots sur~$\Sigma$, on dit que $u \eqfpp
v$ est v�rifi� si on a $u \cRf v = v \cRf u = \e$, c'est-�-dire
$u\ii v \vRf \e$. On �tend~$\eqfpp$ de sorte que $\bot
\eqfpp \bot$ soit vrai, et $u \eqfpp \bot$ et $\bot \eqfpp u$
faux pour tout mot~$u$.

\bigskip Par le lemme~�\Equivalence�, $u \eqfpp v$
entra�ne~$u \eqfp v$. Dans le cas d'un mono�de
gaussien, la proposition~�\Expression� affirme que cette
implication est une �quivalence. Nous allons en d�duire une
solution pour le probl�me de mot du mono�de par
redressement, et, pour celui du groupe associ�, par double
redressement. On notera
$\eqf$ la congruence sur~$\WX$ engendr�e
par~$\eqfp$ et les paires $\{a   a  \ii, \e\}$ et $\{a  \ii a  ,
\e\}$ pour~$a  $ dans~$\Sigma$, de sorte que le groupe
$\Gr{\Sigma \; \Rf}$ est $\WX / \!\! \eqf$. Remarquons
que, par construction, $w \vRf w'$ entra�ne
$w \eqf w'$ pour tous~$w, w'$ mots sur~$\Sigma \cup \Sigma\ii$.

\Prop\�\WordProblem�
{\sl Soit $M$ un mono�de gaussien --- ou,
plus g�n�ralement, un mono�de v�rifiant les
conditions~$(C_0^+)$, $(C_1)$ et $(C_2)$ ---, $\Sigma$ une
partie g�n�ratrice de~$M$, et $f$ un s�lecteur de
ppcm sur~$\Sigma$. 

(i) Deux mots~$u, v$ sur~$\Sigma$ repr�sentent le
m�me �l�ment de~$M$ si et seulement on a $u \eqfpp v$,
c'est-�-dire $u\ii v \vRf \e$.

(ii) Supposons que $M$ v�rifie de surcro�t la
condition~$(C_2^+)$, et soit $G$ le groupe de fractions
de~$M$. Alors un mot~$w$ sur~$\Sigma \cup \Sigma\ii$
repr�sente~$1$ dans~$G$ si et seulement si il existe deux
mots~$u, v$ sur~$\Sigma$ v�rifiant $w \vRf uv\ii$ et $u\ii v \vRf
\e$.}

\Dem (i) Par le lemme~�\Equivalence�, la condition est
suffisante. Inversement, $\cl u = \cl v$ entra�ne
$\cl u \cR \cl v = \cl v \cR \cl u = 1$, d'o� $u \cRf v = v
\cRf u = \e$ par la proposion~�\Expression�.

(ii) La condition est suffisante, car $w \vRf w'$ entra�ne
$w \eqf w'$. Inversement, supposons $w \vRf u v\ii$. Alors $w \eqf \e$
entra�ne $u \eqf v$, donc $u \eqfp v$ puisque $M$ se plonge
dans~$G$, d'o� $u\ii v \vRf \e$ par~(i). \FinDem

\bigskip Si $M$ est un mono�de gaussien, les
op�rations~$\cR$ et~$\jR$ de~$M$ se d�terminent par
redressement � partir de tout s�lecteur de ppcm. Le pgcd, ainsi
que les op�rations sym�triques de ppcm � gauche et de pgcd �
droite, peuvent �galement �tre calcul�es � l'aide de
redressements, � condition d'introduire, � c�t� d'un
s�lecteur � droite associ� au ppcm � droite comme
ci-dessus, une notion sym�trique de s�lecteur � gauche
et de redressement � gauche: supposant $\Sigma$ 
partie g�n�ratrice de~$M$, on appellera {\it
s�lecteur de ppcm � gauche} sur~$\Sigma$ une
application~$\Til f$ de $\Sigma \times \Sigma$ dans~$\Mo(\Sigma)$
telle que, pour tous~$a  , b $ dans~$\Sigma$, $\Til
f(a  , b )$ repr�sente l'�l�ment	$a   \cL b $, s'il
existe. Si $\Til f$ est une fonction de redressement
sur~$\Sigma$, et si $w, w'$ sont deux mots sur~$\Sigma
\cup \Sigma\ii$, on dira que~$w$ est $\Til f$-redressable �
gauche en~$w'$, not� $w \vLf w'$, si on peut passer de~$w$
�~$w'$ en un nombre fini d'�tapes consistant � remplacer un
factuer du type~$a   b \ii$ avec $a  , b  \in \Sigma$ par le
facteur $\Til f(b , a  )\ii \Til f(a  , b )$ correspondant. Les
r�sultats sont alors sym�triques: introduisant $u \cLf v$
comme l'unique mot~$u'$ tel qu'il existe $v'$ v�rifiant $u v\ii
\vLf v'{}\ii u'$, et $u \jLf v$ comme $(u \cLf v) \om v$, on
obtient que $u \cLf v$ repr�sente l'�l�ment~$\cl u \cL \cl v$,
et $u \jLf v$ l'�l�ment~$\cl u \jL \cl v$.  On d�duit alors du
lemme~�\Gcd�:

\Prop
{\sl Soit $M$ un mono�de gaussien, $\Sigma$
une partie g�n�ratrice de~$M$, et $f$ et $\Til f$
respectivement un s�lecteur de ppcm � droite et �
gauche sur~$\Sigma$. Alors, pour tous mots~$u$, $v$
sur~$\Sigma$, le mot~$(u \jRf v) \cLf ((u
\cRf v) \jLf (v \cRf u))$ repr�sente $\cl u \gL \cl v$.}

\bigskip On obtient donc le pgcd � gauche de~$\cl u$
et~$\cl v$ par un triple redressement: on redresse � droite
$u\ii v$ en $v' u'{}\ii$, qu'on redresse � gauche  en~$u''{}\ii v''$, et
un repr�sentant du pgcd � gauche de~$\cl u$ et~$\cl v$ est obtenu en
redressant � gauche le mot~$u u''{}\ii$. Les op�rations du
groupe de fractions se calculent de fa�on semblable. En
particulier, d�nominateurs et num�rateurs se d�terminent par
double redressement.

\Prop
{\sl Soit $G$ le groupe de fractions d'un mono�de
gaussien~$M$, $\Sigma$ une partie g�n�ratrice de~$M$, et
$f$ et $\Til f$ respectivement un s�lecteur de ppcm � droite et
� gauche sur~$\Sigma$. Soit $z $ un �l�ment quelconque
de~$G$, et $w$ un mot sur~$\Sigma \cup \Sigma\ii$
repr�sentant~$z $. Soient
$u, v, u', v'$ les mots sur~$\Sigma$ v�rifiant $w \vRf v u\ii \vLf
u'{}\ii v'$. Alors $u'$ repr�sente~$D (z )$, et $v'$
repr�sente~$N (z )$.}

\Dem Par construction, on a $z  = \cl{u'}{}\ii \cl{v'}$, donc,
d'apr�s le lemme~�\Fraction�, il suffit de montrer $\cl{u'} \gL
\cl{v'} = 1$. Or, par construction, on a $u' = u \cLf v$ et $v' = v
\cLf u$: si $\cl{u'}$ et $\cl{v'}$ avaient un diviseur � gauche
non trivial commun, $u' v$ et $v' u$ ne pourraient  repr�senter
un ppcm � gauche de~$\cl u$ et~$\cl v$.
\FinDem

\bigskip Comme $z  = 1$ �quivaut � $D (z ) = N (z ) =
1$, nous en d�duisons une solution alternative du probl�me de
mot. 

\Cor
{\sl Sous les m�mes hypoth�ses, un mot~$w$ sur~$\Sigma \cup \Sigma\ii$
repr�sente~$1$ dans~$G$ si, et seulement si, il existe deux mots~$u,
v$ sur~$\Sigma$ v�rifiant $w \vRf u v\ii \vLf \e$.}

\bigskip Enfin, le lemme~�\Normale� montre comment calculer
par redressement la forme normale (� gauche) de tout �l�ment d'un
groupe de Garside: supposant que $(\cl{v_q}\,\ii, \pp,
\cl{v_1}\,\ii, \cl{u_1}, \pp, \cl{u_p})$ soit la forme normale
de~$z $, on obtient la forme normale de~$z  \D$ en
d�terminant les �l�ments~${\cl u_i}^{**}$, donc par double
redressement face � un mot repr�sentant~$\D$. Pour~$w$
repr�sentant un �l�ment simple, on obtient le num�rateur de
la forme normale de~$z  \cl w{}\ii$ en redressant � gauche
le mot $u_1 \ppp u_p w\ii$; le d�nominateur s'obtient alors
par une succession de calculs de pgcd, donc �galement par
redressement. Noter que le lemme~�\Pgcd� permet de
d�terminer successivement chaque facteur du d�nominateur �
l'aide d'un unique redressement.


\Sec Reconna�tre les mono�des de Garside

\bigskip Nous avons vu dans la section pr�c�dente que tout
mono�de de Garside admet une pr�sentation
compl�ment�e $\Mon{\Sigma; \Rf}$, o� $f$ est une
fonction de redressement sur~$\Sigma$, et qu'alors toutes les
op�rations du mono�de et celles de son groupe de fractions se
d�terminent par $f$-redressement. Nous abordons ici la
question r�ciproque de reconna�tre quand une pr�sentation
compl�ment�e d�finit un mono�de de Garside.

Le fait d'admettre une pr�sentation compl�ment�e est
une hypoth�se faible, et des conditions sur la fonction de
redressement consid�r�e doivent �tre ajout�es pour que le
mono�de associ� ait de bonnes propri�t�s. Nous allons �tablir
une liste de conditions n�cessaires v�rifi�es par tout s�lecteur
de ppcm dans un mono�de de Garside, puis montrer
que ces conditions sont suffisantes. Nous partirons
(une fois encore) des propri�t�s de l'op�ration~$\cR$.

\Lem\�\PreCoherence�
{\sl Soit $M$ un mono�de gaussien --- ou,
plus g�n�ralement, un mono�de v�rifiant les
conditions~$(C_0)$, $(C_1)$ et $(C_2)$. Alors, pour
tous~$x , y , z $ dans~$M$, on a
$$(x  \cR y ) \cR (x  \cR z ) = (y  \cR x ) \cR (y  \cR
z ). \Eq\�200�$$

}\Dem D'apr�s le lemme~�\Rules�, le membre de gauche
dans~�200� est �gal � $(x  \jR y ) \cR z $, et celui de droite
� $(y  \jR x ) \cR z $: comme $\jR$ est une op�ration
commutative, les deux sont �gaux. Par ailleurs, si l'une des
expressions n'est pas d�finie, il en est de m�me de
l'autre.\FinDem

\Lem\�\Coherent�
{\sl Soit $M$ un mono�de gaussien --- ou,
plus g�n�ralement, un mono�de v�rifiant les
conditions~$(C_0^+)$, $(C_1)$ et $(C_2)$ ---, 
$\Sigma$ une partie g�n�\-ratrice quelconque de~$M$, et $f$ un
s�lecteur de ppcm sur~$\Sigma$. Alors, pour tous
mots~$u$, $v$, $w$ dans~$\Mo(\Sigma)$, on a
$$(u \cRf v) \cRf (u \cRf w) \eqfpp (v \cRf u) \cRf (v \cRf
w). \Eq\�\COH�$$

}\Dem Compte tenu de la proposition~�\Expression�, la
formule~�\COH� est la traduction directe de la
formule~�200�.\FinDem

\Def
Soit $f$ une fonction de redressement sur~$\Sigma$. 

(i) Pour $X \ince \Mo(\Sigma) \cup \{\bot\}$, on dit que $f$ 
a la {\it propri�t� du cube} (\resp la {\it propri�t� du cube
faible}) sur~$X$ si la relation~�\COH�\ (\resp la relation
$$(u \cRf v) \cRf (u \cRf w) \eqfp (v \cRf u) \cRf (v \cRf
w)~) \Eq\�\wCOH�$$
est v�rifi�e pour tous~$u$, $v$, $w$ dans~$X$.

(ii) On dit que $f$ v�rifie la condition~$(\CCI)$ s'il existe une
partie finie~$X$ de~$\Mo(\Sigma)$ qui est close par~$\cRf$,
c'est-�-dire telle que, pour tous~$u, v$ dans~$X$, $u \cRf v$ existe
et appartient �~$X$, et si, de plus, la cl�ture~$X \vv$ de~$X$
par~$\jRf$ est finie et il existe~$\O$ dans~$X\vv$ tel que,
pour tout~$u$ dans~$X\vv$, on  ait $\O \cRf  u = \e$ et il
existe~$v$ dans~$X \vv$ v�rifiant $v \cRf \O \eqfpp u$.

\bigskip Affirmer que $f$ a la propri�t� du cube sur
un triplet~$\{u, v, w\}$ signifie, lorsque tous les mots mis en
jeu sont d�finis, que le cube repr�sent� sur la figure~5.1 se
ferme au sens o�, partant des trois ar�tes �tiquet�es~$u, v, w$
et utilisant le redressement de mots pour construire les six
faces, le redressement des trois petites faces triangulaires
restantes se termine avec des mots vides.

\midinsert
$$\OpenGraphicBox width 50mm height 48mm depth0mm;
\leavevmode\special{illustration Cube4.eps}
\CloseGraphicBox$$
\centerline{{\bf Figure 5.1.} Propri�t� du cube}
\endinsert

\Prop\�\Necess�
{\sl Soit $M$ un mono�de de Garside, $\Sigma$ une partie
g�n�ratrice finie de~$M$, et $f$ un s�lecteur de ppcm
sur~$\Sigma$. Alors la fonction~$f$ a la propri�t� du cube
sur~$\Mo(\Sigma)$ et elle v�rifie la condition~$(\CCI)$.}

\Dem Le lemme~�\Coherent� exprime que $f$ a la propri�t�
 du cube sur~$\Mo(\Sigma)$. Notons~$X$ l'ensemble des
expressions des �l�ments primitifs � droite de~$M$. Comme
$\Sigma$ est fini, et que la longueur des expressions
dans~$\Mo(\Sigma)$ de chaque �l�ment~$x$ de~$M$ est
born�e sup�rieurement par~$\norm(x )$, l'ensemble~$X$ est
fini. Supposons $u , v \in X$. Par la
proposition~�\Expression�, le mot $u \cRf v$ est une
expression de~$\cl u \cR \cl v$: comme $\cl u$ et $\cl v$ sont
primitifs � droite, il en est de m�me de~$\cl u \cR
\cl v$, et $u \cRf v$ appartient �~$X$. Donc $X$
est clos par~$\cRf$.

Par le m�me raisonnement, l'ensemble~$Y$ des expressions
des �l�ments simples de~$M$ est un ensemble fini de mots
qui est clos par les op�rations~$\cRf$ et~$\jRf$, et qui
inclut~$X$. Par cons�quent, la cl�ture~$X \vv$ de~$X$
par~$\jRf$ est finie, et elle contient au moins une expression
pour chaque �l�ment simple de~$M$. Soit $\O$ une
expression quelconque de l'�l�ment~$\D$ dans~$X \vv$. Pour
tout mot~$u$ dans~$X \vv$, le mot~$\O
\cRf u$ repr�sente $\D \cR \cl u$, qui est~$1$, et on a donc
n�cessairement $\O \cRf u = \e$. Inversement, si $\O$ v�rifie $\O
\cRf u = \e$ pour tout~$u$ dans~$X \vv$, $\O$ repr�sente
n�cesairement~$\D$, puisqu'il repr�sente un �l�ment
qui est un multiple de tous les �l�ments simples.

D'apr�s la proposition~�\Char�, l'application~$s  \mapsto s  \cR
\D$ est surjective sur les simples de~$M$. Donc, pour tout mot~$u$
dans~$X \vv$, il doit exister un �l�ment simple~$s $ 
v�rifiant $\cl u = s  \cR \D$. Cet �l�ment~$s $ a au moins
une expression~$v$ dans~$X \vv$, et la condition $\cl u =
\cl v \cR \D$ entra�ne $u \eqfpp v \cRf \O$. Par cons�quent, la
condition~$(\CCI)$ est v�rifi�e.\FinDem

\bigskip Nous allons maintenant montrer que les conditions
n�cessaires de la proposition~�\Necess� sont aussi
suffisantes, et, pour cela, utiliser la caract�risation de la
proposition~�\Char� en termes des conditions~$(C_i)$. La
condition~$(C_0)$ est gratuite.

\Lem\�\Conical�
{\sl Soit $f$ une fonction de redressement sur~$\Sigma$. Alors le
mono�de $\Mon{\Sigma \; \Rf}$ satisfait � la condition~$(C_0)$,
c'est-�-dire n'a d'autre inversible que~$1$.}

\Dem Par construction, $u \eqfp \e$ n'est possible que
pour $u = \e$.\FinDem

\bigskip Le point crucial est le r�sultat suivant, qui montre
l'importance de la propri�t� du cube.

\Prop\�\CohComp�
{\sl Soit $f$ une fonction de redressement sur~$\Sigma$. Alors
les conditions suivantes sont �quivalentes:

(i) La fonction~$f$ a la propri�t� du cube sur~$\Mo(\Sigma)$;

(ii) Les relations~$\eqfp$ et~$\eqfpp$ co�ncident;

(iii) La relation~$\eqfp$ est compatible avec
l'op�ration~$\cRf$, au sens o� la conjonction de $u'
\eqfp u$ et $v' \eqfp v$ entra�ne $u' \cRf v' \eqfp u
\cRf v$.}

\Dem Supposons~(i), et montrons~(ii). Par le
lemme~�\Equivalence�, la relation~$\eqfpp$ est toujours
incluse dans la relation~$\eqfp$. Pour prouver l'inclusion
r�ciproque, puisque, par d�finition, $\eqfp$ est la relation
d'�quivalence engendr�e par les paires~$(ua   f(a  , b )v,
u b  f(b , a  )v)$ avec $a  , b  \in \Sigma$ et
$u, v \in \Mo(\Sigma)$, il suffit de montrer qu'on a $u a   f(a  ,
b )v
\eqfpp  u b  f(b , a  )v$, soit
$$v\ii f(b , a  )\ii b \ii u\ii u a   f(a  , b ) v \vRf \e,$$
ce qui est trivial, et que $\eqfpp$ est une relation
d'�quivalence. R�flexivit� et sym�trie sont claires, et
seule la transitivit� fait probl�me. Supposons $u
\eqfpp v \eqfpp w$. Par hypoth�se, les mots $v \cRf u$, $u
\cRf v$, $v \cRf w$ et $w \cRf v$ existent et sont vides.
Donc $(v \cRf u) \cRf (v \cRf w)$ existe, et il est vide.
Comme $f$ a la propri�t� du cube sur~$\{v, u, w\}$, ceci
entra�ne $(u
\cRf v) \cRf (u \cRf w) \eqfp \e$, donc $(u \cRf v) \cRf (u
\cRf w) = \e$. L'existence du mot $(u \cRf v) \cRf (u \cRf w)$
entra�ne en particulier celle de $u \cRf w$. De plus, $u \cRf
v = \e$ entra�ne $(u \cRf v) \cRf (u \cRf w) = u \cRf w$.
Nous avons donc $u \cRf w = \e$. Un argument sym�trique
donne $w \cRf u = \e$, donc $u \eqfpp w$. Donc $\eqfpp$ est
transitive, et (i) entra�ne~(ii).

Supposons maintenant (ii), et montrons~(iii). Puisque la
relation~$\eqfp$ est sym�trique et transitive, il suffit de montrer
que, si $u \cRf v$ existe et qu'on a $v'
\eqfp v$, alors $u \cRf v'$ existe aussi et on a $u \cRf v' \eqfp u \cRf
v$ et $v' \cRf u \eqfp v \cRf u$. Or, sous ces hypoth�se,  le
lemme~�\Equivalence� entra�ne $u(u \cRf v) \eqfp v(v \cRf
u)$, donc 
$u(u \cRf v) \eqfp v'(v \cRf u)$,  soit, par~(ii), $u(u
\cRf v) \eqfpp v'(v \cRf u)$, et donc
$(v' (v \cRf u)) \cRf (u (u \cRf v)) = \e$. Ceci entra�ne
en particulier $(v' (v \cRf u)) \cRf u = \e$, soit, par~�103�, 
$$(v \cRf u) \cRf (v' \cRf u) = \e. \Eq\�147�$$ 
Nous d�duisons que $v' \cRf u$, et, par cons�quent, $u \cRf
v'$, existent. Comme $v$ et $v'$ jouent maintenant des
r�les sym�triques, le calcul pr�c�dent donne $(v' \cRf u)
\cRf (v \cRf u) = \e$, ce qui, conjugu� �~�147�,
d�montre $v' \cRf u \eqfpp v \cRf u$, donc  $v'
\cRf u \eqfp v \cRf u$. Un calcul semblable donne
$(u \cRf v) \cRf (u \cRf v') = \e$ et
$(u \cRf v') \cRf (u \cRf v) = \e$, d'o�  $u \cRf v
\eqfpp u' \cRf v$, et, finalement $u \cRf v \eqfp u'
\cRf v$. Donc (ii) implique~(iii).

On sait que $u' \eqfpp u$ entra�ne $u' \eqfp u$. Inversement,
supposons $u' \eqfp u$. Par construction, on a 
$u\ii u \vRf \e$, c'est-�-dire $u \cRf u = \e$. Si (iii) est vraie, on
d�duit que $u' \eqfp u$ entra�ne l'existence de $u \cRf u'$ et
$u' \cRf u$, et qu'on a $u' \cRf u \eqfp u
\cRf u = \e$, et $u \cRf u' \eqfp u \cRf u = \e$, soit $u'
\eqfpp u$. Ceci montre que (iii) entra�ne~(ii).

Finalement, supposons~(ii) et~(iii), et soient $u, v, w$ des
mots quelconques sur~$\Sigma$. Si $u \cRf v$ n'est pas d�fini, $v
\cRf u$ ne l'est pas non plus, et $(u \cRf v) \cRf
(u \cRf w)$ et $(v \cRf u) \cRf (v \cRf w)$ sont tous
deux~$\bot$, donc �\COH� est vraie. Supposons que $u
\cRf v$ et $v \cRf u$ soient d�finis. Par~�103�, on a
$(u \cRf v) \cRf (u \cRf w) = (u(u \cRf v)) \cRf w$ et $(v
\cRf u) \cRf (v \cRf w) = (v(v \cRf u)) \cRf w$. Supposons
$(u(u \cRf v)) \cRf w$ d�fini. Par le
lemme~�\Equivalence�, on a $u(u \cRf v) \eqfp v(v
\cRf u)$, donc $u \,(u \cRf v) \eqfp v\, (v \cRf u)$. Alors
(iii) entra�ne que $(v(v \cRf u)) \cRf w$ est �galement
d�fini, et qu'on a $(v(v \cRf u)) \cRf w \eqfp (u(u \cRf v))
\cRf w$. Par~(ii), on d�duit $(v(v \cRf u)) \cRf
w \eqfpp (u(u \cRf v)) \cRf w$, donc en particulier $((u(u
\cRf v)) \cRf w) \cRf ((v(v \cRf u)) \cRf w) = \e$. Un calcul
sym�trique donne $((v(v \cRf u)) \cRf w) \cRf ((u(u \cRf
vu)) \cRf w) = \e$, d'o� $(u(u \cRf v)) \cRf w \eqfpp (v(v
\cRf u)) \cRf w$, qui est la condition~�\COH� pour~$u, v,
w$. Donc (ii) et~(iii) entra�nent~(i). \FinDem

\bigskip Il est alors facile d'�tablir les conditions~$(C_1)$
et~$(C_2)$.

\Lem\�\Cancel�
{\sl Soit $f$ une fonction de redressement sur~$\Sigma$
ayant la propri�t� du cube sur~$\Mo(\Sigma)$. Alors le
mono�de~$\Mon{\Sigma \; \Rf}$ satisfait � la
condition~$(C_1)$, c'est-�-dire admet la simplification �
gauche.}

\Dem Soit $M$ le mono�de $\Mon{\Sigma \; \Rf}$. Supposons 
$\cl u \, \cl v = \cl{\mathstrut u} \,
\cl{\mathstrut v'}$ dans~$M$, soit
$uv \eqfp uv'$. Par la proposition~�\CohComp�, on a $uv
\eqfpp uv'$, c'est-�-dire $(uv)\ii(uv') \vRf \e$. Par
construction, on a $(uv)\ii(uv') \vRf v\ii v'$, donc, par
unicit� du r�sultat du redressement, $v\ii v' \vRf \e$, soit $v
\eqfpp v'$, qui entra�ne $v \eqfp v'$, et $\cl v =
\cl{v'}$. \FinDem

\Lem\�\Lcm�
{\sl Soit $f$ une fonction de redressement sur~$\Sigma$
ayant la propri�t� du cube sur~$\Mo(\Sigma)$. Alors, quels
que soient les mots~$u$, $v$ sur~$\Sigma$, il y a �quivalence
entre 

(i) les mots $u \cRf v$ et $v \cRf u$ sont d�finis;

(ii) les �l�ments~$\cl u$ et $\cl v$ admettent un multiple �
droite commun dans le mono�de~$\Mon{\Sigma; \Rf}$.

Dans ce cas, $\cl u$ et $\cl v$ admettent un ppcm �
droite, � savoir $\cl{u \jRf v}$, et $u \cRf v$
repr�sente~$\cl u \cR \cl v$.}

\Dem Supposons~(i). Par le lemme~�\Equivalence�, on a
$u(u \cRf v) \eqfp v(v \cRf u)$, et la classe commune de ces
deux mots est un multiple � droite commun pour les
classes de~$u$ et~$v$. Donc (ii) est v�rifi�e.  

Inversement, supposons (ii). Il existe des mots
$u'$ et $v'$ v�rifiant $u v' \eqfp v u'$. Puisque
$f$ a la propri�t� du cube, ceci implique $u v' \eqfpp v u'$
par la proposition~�\CohComp�, soit ${v'}\ii u\ii v u' \vRf \e$.
Ainsi, le redressement du mot ${v'}\ii u\ii v u'$ converge,
et, {\it  a fortiori}, celui du sous-mot~$u\ii v$ converge
aussi, ce qui est dire que les mots $u \cRf v$ et $v \cRf u$
existent, et on a~(i). De plus, l'hypoth�se ${v'}\ii u\ii v u'
\vRf \e$ implique l'existence de mots~$u''$, $v''$ satisfaisant
$${v'}\ii (u \cRf v) \vRf {v''}\ii, \quad
(v \cRf u)\ii u' \vRf u'', \quad
{v''}\ii u'' \vRf \e.$$
Ainsi, $\cl u'$ est un multiple � droite de la classe
de~$v \cRf u$, et, donc, $\cl{vu'}$ est un multiple � droite
de la classe de~$v \jRf u$: cette derni�re est donc
ppcm � droite de~$\cl u$ et~$\cl v$.\FinDem

\Lem\�\CII�
{\sl Soit $f$ une fonction de redressement sur~$\Sigma$
ayant la propri�t� du cube sur~$\Mo(\Sigma)$. Alors le
mono�de~$\Mon{\Sigma \; \Rf}$ satisfait � la
condition~$(C_2)$: toute paire d'�l�ments ayant un multiple �
droite commun admet un ppcm � droite.}

\Dem Supposons que $\cl u$ et $\cl v$ admettent un
multiple � droite commun dans~$M$. Par le lemme~�\Lcm�,
les mots $u \cRf v$ et $v \cRf u$ sont d�finis, et $u \jRf v$
et $v \jRf u$ repr�sentent un ppcm � droite de~$\cl u$
et~$\cl v$.\FinDem

\bigskip Nous passons � la condition~$(C_3)$.

\Lem\�\Convergent�
{\sl Soit $f$ une fonction de redressement sur~$\Sigma$, telle
qu'il existe une partie~$X$ de~$\Mo(\Sigma)$ close
par~$\cRf$. Alors le $f$-redressement converge toujours, et
donc l'op�ration~$\cRf$ est partout d�finie sur~$\Mo(\Sigma)$. 
 De plus, si le redressement de tout mot~$u\ii v$ avec $u, v
\in X$ requiert au plus $k$~�tapes et se termine avec un
mot de longueur au plus~$\ell$, alors le redressement
d'un mot quelconque sur~$\Sigma \cup \Sigma\ii$ requiert au plus ${1
\over 4}k \om \lg(w)^2$ �tapes, et il se termine avec un
mot de longueur au plus~$\ell \om \lg(w)$.}

\Dem Soit $w$ un mot sur $\Sigma \cup \Sigma\ii$. Ecrivons $w =
u_1^{e_1} \ppp u_r^{e_r}$ avec $u_i \in X$,
$e_i = \pm 1$ pour chaque~$i$, et $r \le \lg(w)$. Soit $p$
le nombre d'exposants~$e_i$ positifs. Un argument inductif
illustr� sur la figure~5.2 montre qu'il existe des mots
 $v_1$, \pp, $v_r$ dans~$X$ tels que $w$
soit $f$-redressable en $v_1 \ppp v_p v_{p+1}\ii \ppp
v_r\ii$, et que le redressement se d�compose en $p(r -p)$
redressements de mots de la forme $w_1\ii w_2$ avec
$w_1$, $w_2$ dans~$X$. Les bornes en r�sultent, puisqu'on
a toujours $p(r -p) \le r^2/4$.\FinDem

\midinsert
$$\OpenGraphicBox width 50mm height37mm depth0mm;
\leavevmode\special{illustration Convergence4.eps};
\CloseGraphicBox$$
\centerline{{\bf Figure 5.2.} Convergence du
redressement}
\endinsert

\Lem\�\CIII�
{\sl Soit $f$ une fonction de redressement sur~$\Sigma$,
ayant la propri�t� du cube sur~$\Mo(\Sigma)$, et telle que
$f$ satisfasse � la condition~$(\CCI)$. Alors le
mono�de~$\Mon{\Sigma \; \Rf}$ satisfait � la
condition~$(C_3)$.}

\Dem Soit $X$ la cl�ture de~$\Sigma$ par l'op�ration~$\cRf$.
D'apr�s le lemme~�\Convergent�, l'op�ration~$\cRf$ est
partout d�finie sur~$\Mon{\Sigma \; \Rf}$. Il r�sulte du
lemme~�\Lcm� que l'ensemble des �l�ments du mono�de
repr�sent�s par un mot de~$X$ est clos par l'op�ration~$\cR$,
et qu'il engendre le mono�de puisqu'il inclut~$\Sigma$. \FinDem

\bigskip Finalement, nous d�duisons la r�ciproque de la
proposition~�\Necess�:

\Prop\�\Suffis�
{\sl Soit $f$ une fonction de redressement  sur~$\Sigma$,
ayant la propri�t� du cube sur~$\Mo(\Sigma)$, et satisfaisant
� la condition~$(\CCI)$. Alors le mono�de~$\Mon{\Sigma
\; \Rf}$ est un mono�de de Garside, et, donc, le
groupe~$\Gr{\Sigma \; \Rf}$ est un groupe de Garside.}

\Dem Par la proposition~�\Char�, il suffit d'�tablir que le
mono�de~$\Mon{\Sigma \; \Rf}$ satisfait aux
conditions~$(C_0)$, $(C_1)$, $(C_2)$, $(C_3)$ et $(\Til C_1)$.
Les quatre premi�res conditions r�sultent des
lemmes~�\Conical�, �\Cancel�, �\CII� et �\CIII�. Enfin,
pour~$(\Til C_1)$, d'apr�s le lemme~�\Bijection�, il suffit
d'�tablir la surjectivit� de l'application $x  \mapsto x^*$
sur les �l�ments simples; compte tenu de la correspondance 
entre op�ration~$\cR$ sur~$M$ et op�ration~$\cRf$
sur~$\Mo(\Sigma)$, et entre �galit� dans~$M$ et
$\eqfpp$-equivalence dans~$\Mo(\Sigma)$ due � la
satisfaction par~$f$ de la priori�t� du cube, la
condition~$(\CCI)$ donne le r�sultat.
\FinDem


\Sec Crit�res pour la propri�t� du cube

\bigskip La propri�t� du cube pour la fonction~$f$ est
primordiale pour l'�tude du mono�de $\Mon{\Sigma \; \Rf}$:
si elle n'est pas satisfaite, on ne sait essentiellement rien dire,
alors que, si elle l'est, on peut contr�ler la divisibilit� et
l'�galit� � l'aide de redressements de mots et, en particulier,
�tablir assez simplement l'�ventuel caract�re petit gaussien du
mono�de. Il est donc crucial de savoir reconna�tre si une
fonction de redressement donn�e satisfait ou non la
propri�t� du cube. 

Si $f$ est une fonction de redressement sur un ensemble (fini)~$\Sigma$,
et $u, v, w$ des mots sur~$\Sigma$, �tablir la propri�t� du
cube en~$u, v, w$ se fait de fa�on effective � l'aide de
redressements. Plus pr�cis�ment, il existe un processus
consistant en une suite finie de redressements tel que, si la
condition est v�rifi�e, alors le processus se termine en un
nombre fini d'�tapes et il donne une preuve de la condition
cherch�e. Cette situation, plus faible que la d�cidabilit�
puisqu'il se peut, si la condition n'est pas v�rifi�e, qu'on
n'obtienne pas de r�ponse en un temps fini, est typique d'une
condition r�cursivement �num�rable --- ou semi-d�cidable, ou
$\S^0_1$ [\\\BaM].

Consid�rons maintenant la propri�t� du cube sur
l'ensemble~$\Mo(\Sigma)$ entier: comme il existe une infinit� de
triplets de mots dans~$\Mo(\Sigma)$, �num�rer ceux-ci
syst�matiquement et v�rifier la condition pour chacun d'eux
ne permet pas d'�tablir, m�me de fa�on th�orique, la
propri�t� en un nombre fini d'�tapes. On ne peut
obtenir un crit�re effectif que si on sait par avance que la
propri�t� du cube sur un certain sous-ensemble fini
de~$\Mo(\Sigma)$ entra�ne la propri�t� du cube partout. 

Nous rappellons d'abord deux r�sultats partiels  dans cette
direction obtenus ant�rieurement. Le premier est implicite
dans la preuve de Garside que le mono�de des
tresses~$B_n^+$ satisfait aux conditions~$(C_1)$ et~$(C_2)$.

\Prop\�\CritI� [\\\Dff] [\\\Dgc]
{\sl Soit $f$ une fonction de redressement 
sur~$\Sigma$ telle que le mono�de~$\Mon{\Sigma \; \Rf}$
satisfasse~$(C_0^+)$. Alors $f$ a la propri�t� du cube
sur~$\Mo(\Sigma)$ si et seulement si elle a la propri�t� du
cube sur~$\Sigma$, si et seulement si elle a la propri�t� du
cube faible sur~$\Sigma$.}

\bigskip Le crit�re pr�c�dent s'applique aux pr�sentations
standards des groupes d'Artin, la condition~$(C_0^+)$ �tant
v�rifi�e puisque les relations pr�servent la longueur: les
r�sultats de [\\\BrS] montrent alors la propri�t� du cube sur
les g�n�rateurs. Il en est de m�me pour les pr�sentations
de groupe consid�r�s dans~[\\\BuM]: elles sont associ�es �
des fonctions de redressement~$f$ telles que $f(a, b)$ n'est 
d�fini que pour $a$ dans~$A$ et $b$ dans~$B$, $\{A, B\}$
�tant une partition de l'ensemble des g�n�rateurs: la
propri�t� du cube sur les lettres est triviale car tout triplet
contient n�cessairement deux lettres de~$A$, ou deux lettres
de~$B$, pour lesquelles aucun redressement n'est possible; les
groupes ainsi pr�sent�s ne sont pas gaussiens, puisque, dans le
mono�de associ�, deux �l�ments de~$A$, ou de~$B$, n'ont pas
de multiple commun.

Mis � part de tels cas, il est en g�n�ral difficile d'�tablir 
la condition~$(C_0^+)$, et aucune m�thode uniforme
n'est connue --- voir [\\\Pic] pour un exemple mettant en jeu
l'algorithme de Knuth-Bendix.

Un autre crit�re pour la propri�t� du cube est �tabli
dans~[\\\Dgc], � partir d'une d�finition alternative de celle-ci:

\Lem\�\Alternative�
{\sl Soit $f$ une fonction de redressement sur~$\Sigma$, et
$X$ une partie de~$\Mo(\Sigma)$. Alors $f$ a la propri�t� du
cube sur~$X$ si et seulement si on a
$$w \cRf (u(u \cRf v)) \eqfp w \cRf (v(v \cRf u)), \quad
\hbox{et}
\quad (u(u \cRf v)) \cRf w \eqfp (v(v \cRf u)) \cRf
w\Eq\�55�$$
pour tous~$u$, $v$, $w$ dans~$X$.} 

\Dem La relation~�103� donne $(u \cRf v) \cRf (u \cRf
w) = (u(u \cRf v)) \cRf w$ et $(v \cRf u) \cRf (v \cRf w) =
(v(v \cRf u)) \cRf w$, donc �\COH� est �quivalente � la
seconde des relations~�55�. Pour la premi�re, en
utilisant~�103� et le lemme~�\Equivalence�, et en supposant 
�\COH� satisfaite pour $(u, w, v)$ et pour $(w, v, u)$, on
obtient
$$\Eqalign{
w \cRf (u(u \cRf v)) 
&= (w \cRf u) \cdot ((u \cRf w) \cRf (u \cRf v)) \cr
&\eqfp (w \cRf u) \cdot ((w \cRf u) \cRf (w \cRf v)) \cr
&\eqfp (w \cRf v) \cdot ((w \cRf v) \cRf (w \cRf u)) \cr
&\eqfp (w \cRf v) \cdot ((v \cRf w) \cRf (v \cRf u)) 
=w \cRf (v(v \cRf u)). &\Block\cr}$$

\Def
Soit $f$ une fonction de redressement sur~$\Sigma$, et 
$X$ une partie de~$\Mo(\Sigma)$. Pour $u \eqfp v$,
d�finissons $\df(u, v)$ comme le nombre minimal de
$\Rf$-relations n�cessaires pour transformer~$u$ en~$v$. On
dit alors que $f$ est {\it $k$-coh�rente} sur~$X$ si, pour
tous~$u, v, w$ dans~$X$, on a
$$\df(w \cRf u(u \cRf v), w \cRf v(v \cRf u)) + \df((u(u \cRf
v)) \cRf w, (v(v \cRf u)) \cRf w) \le k \Eq\�57�$$

\bigskip Par d�finition, si $X$ est fini, et si $f$ a la propri�t�
du cube (faible) sur~$X$, alors elle est $k$-coh�rente pour un
certain~$k$. Un crit�re suffisant mais non n�cessaire est:

\Prop\�\CritII� [\\\Dgc]
{\sl Si $f$ est une fonction de redressement sur~$\Sigma$ 
qui est $1$-coh�rente sur~$\Sigma$, alors $f$ a la propri�t� du
cube sur~$\Mo(\Sigma)$.}

\bigskip Le crit�re de la proposition~�\CritII� est
automatiquement v�rifi� dans le cas de deux g�n�rateurs,
mais il l'est rarement dans le cas g�n�ral. 

Nous allons maintenant �tablir un nouveau crit�re, qui
s'applique dans tous les cas et ne n�cessite aucune v�rification
pr�alable.

\Prop\�\CritIII�
{\sl Soit $f$ une fonction de redressement sur~$\Sigma$, et
$X$ une partie de~$\Mo(\Sigma) \cup \{\bot\}$ qui
inclut~$\Sigma$ et est close par~$\cRf$. Alors $f$ a la propri�t� du
cube sur~$\Mo(\Sigma)$ si, et seulement si, elle a la propri�t� du
cube sur~$X$.}

\bigskip Il est �vident que la condition est n�cessaire, et tout
le travail consiste � montrer qu'elle est suffisante. La
d�monstration est d�compos�e en plusieurs �tapes.
Jusqu'� la fin de la section, nous supposons que $f$ est une
fonction de redressement fix� sur~$\Sigma$, que $X$ est
une partie de~$\Mo(\Sigma) \cup \{\bot\}$ qui inclut~$\Sigma$ et
est close par~$\cRf$, et que $f$ a la propri�t� du cube
sur~$X$. D'apr�s la proposition~�\CohComp�, il suffit que
nous montrions la compatibilit� de l'op�ration~$\cRf$ et de la
relation~$\eqfp$.

\Lem\�\CompatI� 
{\sl Pour $u, v, v' \in X$, la relation $v' \eqfpp v$
entra�ne $v' \cRf u \eqfpp v \cRf u$ et $u \cRf v' \eqfpp u
\cRf v$.}

\Dem Suppsons que $v \cRf u$ existe. Par hypoth�se, nous
avons $v' \cRf v = v \cRf v' = \e$. Comme $f$ a la propri�t� du
cube sur~$\{v, v', u\}$, nous d�duisons
$$v' \cRf u = \e \cRf (v' \cRf u)  = (v' \cRf v) \cRf (v' \cRf u)
\eqfpp (v \cRf v') \cRf (v \cRf u) = \e \cRf (v \cRf u) =  v
\cRf u.$$ 
Ceci entra�ne en particulier que $v' \cRf u$ et donc $u \cRf
v'$ existent. Utilisant la propri�t� du cube en~$\{u, v, v'\}$, nous
trouvons
$$(u \cRf v) \cRf (u \cRf v') \eqfpp (v \cRf u) \cRf (v \cRf v') = (v
\cRf u) \cRf \e = \e,$$
qui entra�ne $(u \cRf v) \cRf (u \cRf v')  = \e$. On obtient
$(u \cRf v') \cRf (u \cRf v)  = \e$ sym�triquement, d'o�
on d�duit $u \cRf v' \eqfpp u \cRf v$. \FinDem

\Lem\�\Transit� 
{\sl (i) La relation~$\eqfpp$ est transitive sur~$X$.

(ii) Pour $u, v, u', v'$ dans~$X$, la conjonction de $u'
\eqfpp u$ et $v' \eqfpp v$ entra�ne $v' \cRf u' \eqfpp v \cRf
u$.}

\Dem (i) Supposons $u, v, w \in X$ et $u \eqfpp v \eqfpp
w$.  Par hypoth�se, on a $u \cRf v = v \cRf u = \e$.
Appliquant le lemme~�\CompatI�\ � $v \eqfpp w$, on
obtient $u
\cRf w \eqfpp \e$ et $w \cRf u \eqfpp \e$, donc $u \cRf w = w
\cRf u = \e$, soit $u \eqfpp w$. 

(ii) Supposons que $v \cRf u$ existe. En appliquant
le lemma~�\CompatI�, on obtient
$$v' \cRf u' \eqfpp v' \cRf u \eqfpp v \cRf u,$$
qui entra�ne $v' \cRf u' \eqfpp v \cRf u$ par~(i), puisque
$v' \cRf u'$, $v' \cRf u$ et $v \cRf u$ appartiennent �~$X$, ce
dernier �tant suppos� clos par~$\cRf$.\FinDem

\bigskip Nous introduisons maintenant des raffinements de la
relation~$\eqfpp$.

\Def Pour $u$, $u'$ dans~$\Mo(\Sigma) \cup \{\bot\}$, on dira
que $u \spe(0) u'$ est v�rifi� si on a  $u = u' = \e$, et, pour 
$p \ge 1$, que $u \spe(p) u'$ est v�rifi� s'il existe deux
d�compositions $u = u_1 \ppp u_p$, $u'= u'_1 \ppp u'_p$
telles qu'on ait $u_1$, \pp, $u'_p \in X$ et $u'_j \eqfpp u_j$
pour tout~$j$.

\bigskip Ainsi, $u' \spe(1) u$ est la conjonction de~$u' \eqfpp
u$ et de $u, u' \in X$. 

\Lem\�\FineI� 
{\sl (i) Toute relation $u \spe(p) u'$ entra�ne $u \eqfpp u'$.

(ii) La conjonction des relations $u' \spe(p) u$ et $v' \spe(q) v$
entra�ne $u' \cRf v' \spe(q) u \cRf v$ et $v'
\cRf u' \spe(p) v \cRf u$.}

\Dem (i) Le r�sultat est clair par r�currence sur~$p$
(noter que, m�me pour $u, u' \in X$, il n'y a en g�n�ral
aucune raison pour que, r�ciproquement, $u \eqfpp u'$
entra�ne $u \spe(p) u'$).

(ii) Observons d'abord que le r�sultat est vrai pour $p =
0$ et pour $q = 0$. En effet, pour $p = 0$, on a $u' = u =
\e$, donc $u' \cRf v' = \e = u \cRf v$, et, pour $q = 0$, on a
$v' = v = \e$, donc $v' \cRf u' = u'$ et $v \cRf u = u$.

Ensuite, nous utilisons une r�currence sur~$p + q$.
Supposons $u' \spe(p) u$ et $v' \spe(q) v$. D'apr�s ce qui
pr�c�de, nous pouvons supposer $p \ge 1$ et
$q \ge 1$. Alors, on peut �crire $u = u_1 u_2$, $u' = u'_1
u'_2$ avec $u'_1 \eqfpp u_1$ et $u'_2 \spe(p-1) u_2$,
et, de m�me, $v = v_1 v_2$, $v' = v'_1 v'_2$ avec $v'_1
\eqfpp v_1$ et $v'_2 \spe(q-1) v_2$. Posons $u_{0, j} = u_j$
et $v_{i, 0} = v_i$, puis $u_{i, j} = v_{i-1, j} \cRf u_{i, j-1}$ et
$v_{i, j} = u_{i, j-1} \cRf v_{i-1, j}$ (Figure~6.1). L'hypoth�se
que $X$ est close par~$\cRf$ entra�ne inductivement que
tous les mots~$u_{i, 1}$, $u'_{i, 1}$, $v_i$, et $v'_i$ sont
dans~$X  \cup \{\bot\}$. Le lemme~�\Transit�(ii) donne
$u'_{1, 1} \eqfpp u_{1, 1}$ et $v'_{1, 1} \eqfpp v_{1, 1}$.
Ensuite, l'hypoth�se de r�currence donne $u'_{1, 2}
\spe(p-1) u_{1, 2}$ et $v'_{1, 2} \eqfpp v_{1, 2}$. Elle donne de
m�me $u'_{2, 1} \eqfpp  u_{2, 1}$ et $v'_{2, 1}
\spe(q-1) v_{2, 1}$, et, finalement, $u'_{2, 2} \spe(p-1)
u_{2, 2}$ et $v'_{2, 2} \spe(q-1) v_{2, 2}$. R�unissant les
relations, on d�duit $u' \cRf v' = u'_{2, 1} u'_{2, 2}
\spe(p) u_{2, 1} u_{2, 2} = u \cRf v$, et $v' \cRf u' = v'_{1, 2}
v'_{2, 2} \spe(q) v_{1, 2} v_{2, 2} = v \cRf u$.
\FinDem

\midinsert
$$\OpenGraphicBox width 45mm height24mm depth0mm;
\leavevmode\special{illustration Quadra4.eps}
\CloseGraphicBox$$ 
\centerline{{\bf Figure 6.1.} D�monstration du
lemme~�\FineI�}
\endinsert

\Def\�\DefSPE�
Pour $v$, $v'$ dans~$\Mo(\Sigma) \cup \{\bot\}$, on dira
que $v \SPE v'$ est v�rifi� s'il existe deux d�compositions
$v = v_0 v_1 v_2 v_3$, $v'= v'_0 v'_1 v'_2 v'_3$ et
deux entiers~$q, r$ v�rifiant

(i) $v'_0 \spe(q) v_0$, et $v'_3 \spe(r) v_3$, 

(ii) $v_1, v_2, v'_1, v'_2 \in X$, et $v'_2 \eqfpp
v_1 \cRf v'_1$, et $v_2 \eqfpp v'_1 \cRf v_1$.

\Lem 
{\sl La relation $v \SPE v'$ entra�ne $v \eqfpp v'$.}

\Dem Avec les notations de la d�finition, on a d'abord $v'_0
\eqfpp v_0$ et $v'_3 \eqfpp v_3$ par le lemme~�\FineI�(i),
soit $v_0\ii v'_0 \vRf \e$ et $v_3\ii v'_3 \vRf \e$. De m�me,
par hypoth�se, on a $v_2 \eqfpp v'_1 \cRf v_1$, soit
$v_2\ii (v'_1 \cRf v_1) \vRf \e$, et, sym�triquement, 
${v'_2}\ii(v'_1 \cRf v_1) \vRf \e$. On trouve alors
$$\eqalign{
v\ii v' 
&= v_3\ii v_2\ii v_1\ii v_0\ii v'_0 v'_1 v'_2 v'_3 \cr
& \vRf v_3\ii v_2\ii v_1\ii v'_1 v'_2 v'_3
\vRf v_3\ii v_2\ii (v_1 \cRf v'_1) (v'_1 \cRf v_1)\ii v'_2 v'_3
\vRf v_3\ii v'_3 \vRf \e, \cr}$$ 
lorsque tous les mots~$v_i$, $v'_i$ sont dans~$\Mo(\Sigma)$, et on
conclut que $v \eqfpp v'$ est vrai. D'un autre c�t�, si au
moins un des mots~$v_i$ est~$\bot$, le mot~$v'_i$
correspondant est �galement~$\bot$, et on a
$v = v' = \bot$, donc $v \eqfpp v'$.\FinDem

\Lem\�\FineII�
{\sl La conjonction de $u' \spe(p) u$ et $v' \SPE v$ entra�ne
$u' \cRf v' \SPE u \cRf v$ et $v' \cRf u' \spe(p) v \cRf u$.}

\Dem Nous raisonnons par r�currence sur~$p$. Supposons
$u' \spe(p) u$ et $v' \SPE v$. Pour $p = 0$, la seule
possibilit� est $u' = u = \e$, donc $u' \cRf v' = v' \SPE v = u
\cRf u$, et le r�sultat est vrai. Supposons $p = 1$. Fixons
des d�compositions $v = v_0 v_1 v_2 v_3$, $v' = v'_0 v'_1
v'_2 v'_3$ comme dans la d�finition~�\DefSPE�. On pose
$u_0 = u$ et $u'_0 = u'$, et on d�finit de proche en proche
$u_j = v_{j-1} \cRf u_{j-1}$ et $w_{j} = u_j \cRf v_j$, et, de
m�me, $u'_j = v'_{j-1} \cRf u'_{j-1}$ et $w'_{j} = u'_j \cRf
v'_j$. 
$$\OpenGraphicBox width 85mm height 15mm depth0mm;
\leavevmode\special{illustration Special4.eps}
\CloseGraphicBox$$ 
Par hypoth�se, nous avons $u'
\spe(1) u$ et $v'_0 \spe(q) v_0$, donc le lemme~�\FineI�
donne
$$\Displaylines{
u'_1 \spe(1) u_1, \Eq\�69� \cr
w'_{0} \spe(q) w_{0}.\Eq\�70� \cr}$$
Par hypoth�se, $v_1$ et~$v'_1$ sont dans~$X$, donc il en
est de m�me de $v_1 \cRf v'_1$ et $v'_1 \cRf v_1$.
Toujours par hypoth�se, nous avons $v_2 \eqfpp v_1
\cRf v'_1$ et $v'_2 \eqfpp v'_1 \cRf v_1$, donc, par le
lemme~�\CompatI�, nous obtenons
$$\Displaylines{
u_3 = v_2 \cRf u_2 \eqfpp (v_1 \cRf v'_1) \cRf u_2
= (v_1 \cRf v'_1) \cRf (v_1 \cRf u_1), \Eq\�71�\cr
w_{2} = u_2 \cRf v_2 \eqfpp u_2 \cRf (v_1 \cRf v'_1)
= (v_1 \cRf u_1) \cRf (v_1 \cRf v'_1), \Eq\�72�\cr
}$$
et, {\it mutatis mutandis},
$$\Displaylines{
u'_3 \eqfpp = (v'_1 \cRf v_1) \cRf (v'_1 \cRf u'_1), \Eq\�73�\cr
w'_{2} \eqfpp (v'_1 \cRf u'_1) \cRf (v'_1 \cRf v_1), \Eq\�74�\cr
}$$
Comme $f$ a la propri�t� du cube sur~$X$, le mot de droite
dans~�71� est $\eqfpp$-�quivalent � $(v'_1 \cRf v_1) \cRf
(v'_1 \cRf u_1)$, et, comme tous les mots concern�s sont
dans~$X$ et que $\eqfpp$ est transitive sur~$X$ d'apr�s le
lemme~�\Transit�(ii), nous d�duisons
$$u_3 \eqfpp (v'_1 \cRf v_1) \cRf (v'_1 \cRf u_1). \Eq\�75�$$
Nous avons vu que $u'_1 \eqfpp u_1$ est vrai, et $u_1$,
$u'_1$, $v'_1$ et $v'_1 \cRf v_1$ sont dans~$X$,
donc, en appliquant le lemme~�\CompatI� deux fois
en partant de~�73� et de~�75�, nous obtenons
$u'_3 \eqfpp u_3$, et m�me $u'_3 \spe(1) u_3$
puisque $u_3$ et $u'_3$ sont dans~$X$ par construction.

En appliquant de m�me la propri�t� du cube et la transitivit�
de~$\eqfpp$ sur~$X$, nous obtenons � partir de~�72� et
�74� les relations
$$\Displaylines{
w_{2} \eqfpp (u_1 \cRf v_1) \cRf (u_1 \cRf v'_1) 
= w_{1} \cRf (u_1 \cRf v'_1),\Eq\�76�\cr
w'_{2} \eqfpp (u'_1 \cRf v'_1) \cRf (u'_1 \cRf v_1) 
= w'_{1} \cRf (u'_1 \cRf v_1).\Eq\�77�\cr}$$ 
Comme on a $u'_1 \eqfpp u_1$, le lemme~�\CompatI�
donne d'abord $u_1 \cRf v'_1 \eqfpp u'_1 \cRf v'_1 = w'_{1}$, d'o�, 
en utilisant~�76�, le lemme~�\CompatI�\ � nouveau, et la transitivit�
de~$\eqfpp$ sur~$X$, 
$$w_{2} \eqfpp w_{1} \cRf w'_{1},\Eq\�78�$$
et, par un argument sym�trique en partant de~�77�,
$$w'_{2} \eqfpp w'_{1} \cRf w_{1}.\Eq\�79�$$
Maintenant, nous avons vu que $u'_3 \spe(1) u_3$ est
v�rifi�e, et, par hypoth�se, nous avons $v'_3
\spe(r) v_3$. En appliquant le lemme~�\FineI�, nous
d�duisons
$$\Displaylines{
u'_4 \spe(1) u_4, \Eq\�80� \cr
w'_{3} \spe(r) w_{3}. \Eq\�81� \cr}$$
Par construction, on a $u \cRf v = w_{0} w_1 w_2 w_{3}$
et $v \cRf u = u_4$, et, de m�me, $u' \cRf v' = w'_{0} w'_1 w'_2
w'_{3}$ et $v' \cRf u' = u'_4$. Alors, la conjonction
de~�69�, �78�, �79� et �81� donne $u' \cRf v' \SPE u
\cRf v$, et �80� donne $v' \cRf u' \spe(1) v \cRf u$, ce qui
est le r�sultat escompt�.

Supposons finalement $p \ge 2$. On �crit $u = u_1 u_2$, $u'
= u'_1 u'_2$ avec $u'_1 \spe(1) u_1$ et $u'_2 \spe(p-1)
u_2$. En appliquant l'hypoth�se de r�currence �~$u_1$,
$u'_1$, $v$ et~$v'$, nous obtenons
$$\Displaylines{
u'_1 \cRf v' \SPE u_1 \cRf v \Eq\�80�\cr
v' \cRf u'_1 \spe(1) v \cRf u_1. \Eq\�81�\cr}$$
Ensuite, en utilisant~�80� et en appliquant
l'hypoth�se de r�currence �~$u_2$, $u'_2$, $u_1 \cRf v$
et $u'_1 \cRf v'$, nous obtenons
$$\Displaylines{
u'_2 \cRf (u'_1 \cRf v') \SPE u_2 \cRf (u_1 \cRf v) \Eq\�82�\cr
(u'_1 \cRf v') \cRf u'_2 \spe(p) (u_1 \cRf v) \cRf u_2.
\Eq\�83�\cr}$$  
La relation~�82� est $u' \cRf v' \SPE u \cRf v$, tandis que
la concat�nation de~�81� et~�83� donne $v' \cRf
u' \spe(p) v \cRf u$. La d�monstration est donc
compl�te.\FinDem

\bigskip Nous pouvons maintenant compl�ter la
d�monstration de la Proposition~�\CritIII�. 

\Dem Soit $f$ une fonction de redressement sur~$\Sigma$,
$X$ une partie de~$\Mo(\Sigma) \cup \{\bot\}$ close
par~$\cRf$, et telle que $f$ ait la propri�t� du cube sur~$X$.
D'apr�s la proposition~�\CohComp�, il suffit que nous
montrions que la conjonction de $u' \eqfp u$ et $v' \eqfp v$
entra�ne $u' \cRf v' \eqfp u \cRf v$ et $v' \cRf u' \eqfp v
\cRf u$. Comme $\eqfp$ est une relation transitive, il suffit
de prouver l'implication dans le cas o� on a utilis� exactement
une relation de~$\Rf$ pour transformer~$uv$ en~$u'v'$. 
Supposons donc, sans perte de g�n�ralit� puisque la
conclusion cherch�e est sym�trique, $u' = u$ et que $v'$ soit
obtenu � partir de~$v$ en utilisant une relation de la
pr�sentation, c'est-�-dire en rempla�ant un facteur~$a   f(a  ,
b )$ par le facteur~$b  f(b , a  )$ correspondant. On a donc
des d�compositions $v = v_0 a   f(a  , b ) v_3$ et $v' = v_0
b  f(b , a  ) v_3$. Soient $p$, $q$, $r$ les longueurs des
mots~$u$, $v_0$ et $v_3$. Par hypoth�se, $\Sigma$ est inclus
dans~$X$, donc $u' = u$ entra�ne $u' \spe(p) u$, et, de
m�me, on a $v_0 \spe(q) v_0$ et $v_3 \spe(r) v_3$, et, par
cons�quent, on a $v' \SPE v$ par d�finition. Par le
lemme~�\FineII�, on d�duit $u \cRf v' \SPE u \cRf v'$ et
$v' \cRf u \spe(p) v \cRf u$, et, de l�, en particulier, $u \cRf v'
\eqfp u \cRf v'$ et $v' \cRf u \eqfp v \cRf u$, ce qui
est exactement ce que nous voulions d�montrer.\FinDem 

\Rem
Au lieu d'utiliser la relation~$\eqfpp$, et ses
raffinements~$\spe(p)$ et~$\SPE$, nous pourrions esp�rer
n'utiliser partout que la relation~$\eqfp$, ce qui
simplifierait la d�monstration, notamment
parce que $\eqfp$ est partout transitive. Il est douteux
qu'une telle approche na�ve puisse aboutir, car la
contrepartie du lemme~�\CompatI� n'a aucune raison
d'�tre vraie: {\it a priori}, l'hypoth�se $u' \eqfp u$
n'implique aucune cons�quence directe pour les mots~$u
\cRf u'$ et $u' \cRf u$. 

\Question
{\sl Soit $f$ une fonction de redressement 
sur~$\Sigma$, et $X$ une partie de~$\Mo(\Sigma) \cup
\{\bot\}$ close par~$\cRf$. Que peut-on d�duire de
l'hypoth�se que $f$ a la propri�t� du cube faible sur~$X$ ---
en particulier dans le cas $X  = \Mo(\Sigma)$?}

\bigskip Cette question, qui est ouverte, est de peu d'int�r�t
algorithmique car la seule m�thode syst�matique connue
pour �tablir la propri�t� du cube faible~�\wCOH� est d'�tablir
la propri�t� du cube forte~�\COH�.

En rapprochant les propositions~�\Necess�, �\Suffis�, et
�\CritIII�, nous obtenons une version explicite du
th�or�me~B' de l'introduction:

\Prop\�\CritFinal�
{\sl Pour~$f$ fonction de redressement sur~$\Sigma$,
notons $(\CCII)$ la conjonction des conditions
suivantes:

(i) la cl�ture~$\Til\Sigma$ de~$\Sigma$ pour~$\cRf$ existe et
elle est finie;

(ii) la fonction~$f$ a la propri�t� du cube sur~$\Til\Sigma$;

(iii) notant~$\Til\Sigma\vv$ la cl�ture de~$\Til\Sigma$
par~$\jRf$ --- qui n�cessairement existe et est finie si
(i) et (ii) sont v�rifi�es --- il existe un mot~$\O$
dans~$\Til\Sigma\vv$ tel que, pour tout~$u$
dans~$\Til\Sigma\vv$, on ait $\O \cRf u = \e$ et il
existe~$v$ dans~$\Til\Sigma\vv$ v�rifiant
$v \cRf \O \eqfpp u$.

Si $M$ est un mono�de de Garside, et si
$f$ est un s�lecteur de ppcm sur une partie
g�n�ratrice~$\Sigma$ de~$M$,  alors $f$ est une fonction de 
redressement sur~$\Sigma$, elle satisfait aux
conditions~$(\CCII)$ et $M$ admet la
pr�sentation~$\Mon{\Sigma; \Rf}$. Inversement, si $f$ est une
fonction de redressement sur~$\Sigma$ satisfaisant aux
conditions~$(\CCII)$, alors le mono�de~$\Mon{\Sigma; \Rf}$ est
un mono�de de Garside, et $f$ est un s�lecteur de ppcm
sur~$\Sigma$.}

\bigskip Les conditions mises en jeu dans la proposition
pr�c�dente sont de type~$\S^0_1$: si le mono�de~$\Mon{\Sigma \;
\Rf}$ est un mono�de de Garside, alors les conditions~(i), (ii)
et~(iii) sont v�rifi�es, donc, partant de l'ensemble fini~$\Sigma$, on
d�terminera en un nombre fini d'�tapes la cl�ture de~$\Sigma$
pour~$\cRf$, puis on �tablira la propri�t� du cube pour~$f$
sur cette cl�ture, et, enfin, la condition~(iii), toujours par un
nombre fini de redressements qui, par hypoth�se, convergent
tous en un nombre fini d'�tapes.

\Ex
Consid�rons la pr�sentation $\Mon{a  , b  \; a  b a   = b^2}$,
associ�e au compl�ment~$f$ d�fini par $f(a  , b ) = b a  $ et
$f(b , a  ) = b $. La cl�ture de~$\{a  , b \}$ par~$\cRf$
est l'ensemble $\{a  , b , b a  , b a  b , \e, a  b \}$. Que $f$ ait
la propri�t� du cube sur cet ensemble se v�rifie
directement --- en fait, on peut aussi appliquer ici le crit�re de
la proposition~�\CritII� car l'alphabet est r�duit � deux lettres.
Enfin, la cl�ture de~$\{a  , b , b a  , b a  b , \e, a  b \}$
par~$\jRf$ est l'ensemble
$\{a  , b , b a  , b a  b , \e, a  b , a  b a  ,
b b , a  b a  b , b a  b a  \}$, et il est imm�diat de
v�rifier que les choix$\O = a  b a  b $ et $\O =
b a  b a  $ conviennent pour la condition~(iii). (Noter que
le groupe $\Gr{a  , b  \; a  b a   =
b^2}$ est le groupe de tresses~$B_3$ rapport� aux
g�n�rateurs $a = \s_1$ et $b =
\s_2\s_1$.)

\bigskip Il est alors facile de d�duire le th�or�me~B de l'introduction.
Partant d'une pr�sentation suppos�e finie  d'un
groupe~$G$ (\resp d'un mono�de~$M$), nous
pouvons �num�rer syst�matiquement toutes les
pr�sentations de~$G$ (\resp de~$M$) en appliquant
les transformations de Tietze, et, pour chacune d'elles,
tester si elle est compl�ment�e, c'est-�-dire associ�e � une
fonction de redressement, et si cette derni�re satisfait aux
conditions de la proposition~�\CritFinal�. Alors $G$ est un
groupe de Garside (\resp $M$ est un mono�de de Garside) si et seulement si la r�ponse est positive
pour au moins une des pr�sentationss, ce qui se
trouvera �tabli en un nombre fini d'�tapes pour autant
que les tests des diverses pr�sentations soient men�s
en parall�le, c'est-�-dire sans attendre l'hypoth�tique
fin d'un test pour passer au suivant.

\Rem Un groupe de Garside peut
s'exprimer comme groupe de fractions de plusieurs
mono�des: par d�finition, au moins un de ceux-ci est
un mono�de de Garside, mais ce n'est pas
n�cessairement le cas des autres. Par exemple, le
groupe de tresses~$B_3$ est � la fois le groupe de
fractions des mono�des $\Mon{a  , b  \;
a  b a   =
b  a   b }$ et $\Mon{a  , b  \; a  b a   = b^2}$, qui sont
petits gaussiens, et du mono�de $\Mon{a  , b  \; a  b a   =
b  a  a   b }$, qui n'est pas atomique. De la m�me
fa�on, un mono�de de Garside peut admettre
plusieurs pr�sentations associ�es � des compl�ments
diff�rents, et les conditions de la
proposition~�\CritFinal� ne valent que pour ceux de ces
compl�ments qui sont des s�lecteurs de ppcm: ainsi,
le mono�de de Garside $\Mon{a, b, c; ab = bc =
ca}$ admet aussi la pr�sentation $\Mon{a, b, c; ab =
bc = ca, aba = caa}$, pour laquelle le redressement n'est
pas toujours convergent. Il serait donc incorrect
d'�noncer la proposition~�\CritFinal�  sous la forme
\<<Le mono�de~$\Mon{\Sigma; \Rf}$ est un mono�de de Garside si et seulement si  $f$ satisfait aux
conditions~$(\CCII)$\>>.


\penalty-2000\bigskip \centerline{{\sc R�f�rences}}\bigskip
\parindent=20pt

\Ref \\\Adj; S.I. Adjan;  On the embeddability of
semigroups ; Soviet. Math. Dokl., 1-4; 1960;
819--820.

\Reff \\\Adk; ---; Fragments of the word Delta in a
braid group; Mat. Zam. Acad. Sci. SSSR; 36-1; 1984;
25--34; traduction: Math. Notes of the Acad. Sci. USSR;
36-1 (1984) 505--510.

\Ref \\\BaM; G. Baumslag \& C.F. Miller III (eds); {\rm Algorithms
and Classification in Combinatorial Group Theory}; MSRI
Publications 23, Springer Verlag (1992).

\Ref\\\BDM; D. Bessis, F. Digne, \& J. Michel;
Springer theory in braid groups and the
Birman-Ko-Lee monoid; pr�publication (2000).

\Reff \\\BrS; E. Brieskorn \& K. Saito; Artin-Gruppen und
Coxeter-Gruppen; Invent. Math.; 17; 1972; 245--271.

\Reff \\\BMR; M. Brou\'e, G. Malle \& R. Rouquier; Complex
reflection groups, braid groups, Hecke algebras; J. Reine
Angew. Math.; 500; 1998; 127--190.

\Reff\\\BuM; M. Burger \& S. Mozes; Finitely presented
simple groups and product of trees; C. R. Acad. Sci. Paris;
324--1; 1997; 747--752.

\Reff \\\Cha; R. Charney; Artin groups of finite type are
biautomatic; Math. Ann.; 292-4; 1992; 671--683.

\Reff \\\Chb; ---; Geodesic automation and growth
functions for Artin groups of finite type; Math. Ann.;
301-2; 1995; 307--324.

\Ref \\\ClP; A.H. Clifford \& G.B. Preston; {\rm The algebraic
theory of semigroups, vol.~1}; AMS Surveys {\bf 7}, (1961).
  
\Reff \\\Dfa; P. Dehornoy; Deux propri\'et\'es des
groupes de tresses; C. R. Acad. Sci. Paris; 315; 1992;
633--638.

\Reff \\\Dfb; ---; Braid groups and left
distributive operations; Trans. Amer. Math. Soc.; 345-1;
1994; 115--151. 

\Reff \\\Dff; ---; Groups with a complemented
presentation; J. Pure Appl. Algebra; 116; 1997; 115--137.

\Reff \\\Dfz; ---; Gaussian groups are torsion free;
J. of Algebra; 210; 1998; 291--297.

\Reff \\\Dgc; ---; On completeness of word
reversing; Discrete Math.; 225; 2000; 93--119.

\Ref \\\Dgd; ---; {\rm Braids and Self-Distributivity}; Progress 
in Math. vol.~192, Birkh\"auser (2000).

\Reff \\\Dfx; P. Dehornoy \& L. Paris; Garside groups, a
generalization of Artin groups; Proc. London Math. Soc.;
79-3; 1999; 569--604.

\Reff \\\Dlg; P. Deligne; Les immeubles des groupes de
tresses g\'en\'eralis\'es; Invent. Math.; 17; 1972;
273--302.

\Reff \\\ElM; E. A. Elrifai \& H. R. Morton; Algorithms for
positive braids; Quart. J. Math. Oxford; 45-2; 1994;
479--497.

\Ref \\\Eps; D. Epstein \& {\it al.}; Word Processing in
Groups; Jones \& Barlett Publ. (1992).

\Reff \\\Gar; F. A. Garside; The braid group and
other groups; Quart. J. Math. Oxford; 20 {\rm No.78}; 1969;
235--254.

\Reff \\\Mic; J. Michel; A note on words in braid monoids; J.
of Algebra; 215; 1999; 366--377.

\Ref\\\Pic; M. Picantin; The conjugacy problem in small
Gaussian groups; Comm. in Algebra, � para�tre.

\Ref\\\Pid; ---; The center of small Gaussian groups; J. of
Algebra, � para�tre.

\Reff \\\Rmm;  J.H. Remmers; On the geometry of semigroup
presentations; Advances in Math.; 36; 1980; 283--296.

\Reff \\\Tat; K.~Tatsuoka; An isoperimetric inequality for Artin
groups of finite type; Trans. Amer. Math. Soc.; 339--2;
1993; 537--551. 

\Ref \\\Thu; W.~Thurston; Finite state algorithms for the
braid group; notes en circulation (1988).



\bigskip\hfill SDAD FRE 2271 CNRS, Math\'ematiques

\hfill Universit\'e de Caen, 14~032 Caen, France

\hfill dehornoy@math.unicaen.fr

\hfill http://www.math.unicaen.fr/$\sim$dehornoy/


\bye


