\documentclass[12pt]{amsart}
\usepackage[french]{babel}
\usepackage{amssymb,latexsym,amsmath}
\usepackage{euscript}
\usepackage{epstopdf}
%=======================================================
%le usepackage{euscript} produit des lettre style Kues...
%la macro commande est: {\EuScript}
%=======================================================
\usepackage{graphicx}
%\usepackage{pdfsync}
%\usepackage{theorem}
\usepackage[applemac]{inputenc}
%le usepackage[applemac]{inputenc} sert \`a avoir les accents
%pour les utilisateurs de window ou unix, je dois changer le [appelmac] par [latin1] pour unix et [ansinew] pour le window

\textwidth15cm
\hoffset-1.5truecm

%=======================================================
%Double jambe.  La macro commande est:{\Bbb}
%(definit par Rene. C'est deux lignes sont \'equivalentes a
%un usepackage)
%=======================================================
\DeclareSymbolFont{AMSb}{U}{msb}{m}{n}
\DeclareSymbolFontAlphabet{\Bbb}{AMSb}

\newtheorem{theorem}{Th\'eor\`eme}
\newtheorem{lemma}{Lemme}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollaire}
\theoremstyle{definition}
\newtheorem{defin}{D\'efinition}
\theoremstyle{remark}
\newtheorem{examp}{Exemple}
\newtheorem{remq}{Remarque}

\numberwithin{theorem}{section}
\numberwithin{lemma}{section}
\numberwithin{proposition}{section}
\numberwithin{corollary}{section}
\numberwithin{defin}{section}
\numberwithin{remq}{section}
\numberwithin{examp}{section}

\newenvironment{definition}
 {\begin{defin}}
 {\hfill {$\triangle$}\par\end{defin}}

\newenvironment{example}
 {\begin{examp}}
 {\hfill {$\Box$}\par\end{examp}}

\newenvironment{remark}
 {\begin{remq}}
 {\hfill \par\end{remq}}

%\newenvironment{proof}
%   {\par\noindent
%   \textbf{Preuve}\ }
%   {\hfill{\raisebox{+.2mm}{\rule{.21cm}{.21cm}}}}

\def\qedsymbol{{\raisebox{+.2mm}{\rule{.21cm}{.21cm}}}}

\newcommand{\ds}{\displaystyle}
\renewcommand{\thefootnote}{$\fnsymbol{footnote}$}

%Pour obtenir les guillemets fran{\c c}ais:
%\og pour ouvrir guillemet
%\fg pour fermer guillemet

%=======================================================
%Fin pr\'eambule
%=======================================================

\begin{document}
\title{Mots de Lyndon g\'en\'eralis\'es}
\author[Christophe Reutenauer]{Christophe Reutenauer*}
\dedicatory{D\'edi\'e \`a mon ami Xavier Viennot}
\thanks{*Universit\'e du Qu\'ebec \`a
Montr\'eal; D\'epartement de math\'ematiques; Case postale 8888,
succursale Centre-Ville, Montr\'eal (Qu\'ebec) Canada, H3C 3P8
(mailing address); e-mail: {\tt christo@math.uqam.ca}.}
\date{}
%today

\def\abstractname{Abstract}
\begin{abstract}
By choosing for each position $i$ of infinite words in $A^{\Bbb N}$ a
total order on $A$, one defines a lexicographical order on $A^{\Bbb
N}$.  It allows to define generalized Lyndon words.  They factorize
the free monoid, form Hall sets and give bases of the free Lie
algebras.  The main example, apart from usual Lyndon words, are the
Galois words, obtained through the alternate lexicographical order on
$A^{\Bbb N}$.  They have several number-theoretical applications:
Galois numbers, their homographics classes, binary indefinite
quadratic forms, Markoff numbers. 
\end{abstract}

\maketitle

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 54 \rms (2006), Article~B54h\hfill}
\def\thepage{}
%
%


\def\proofname{Preuve}

\setcounter{section}{0}
\section{Introduction}
Un mot $w$ sur l'alphabet totalement ordonn\'e $A$ est un {\it mot de Lyndon} si pour toute factorisation non triviale $w=uv$, la suite $w^\infty$ est strictement plus petite que la suite $(vu)^\infty$, pour l'ordre lexicographique sur $A^{\Bbb N}$.

Nous introduisons la variante suivante~: \'etant donn\'ee une suite $<_i, i=0,1,2,\ldots$ d'ordres totaux sur $A$, nous consid\'erons l'ordre lexicographique sur $A^{\Bbb N}$ obtenu en consid\'erant en chaque position $i$ l'ordre $<_i$.  Ainsi $a_0a_1a_2\ldots< b_0b_1b_2\ldots$ si~: $a_0<_0 b_0$, ou $a_0=b_0$ et $a_1<_1 b_1$, ou $a_0=b_0, a_1=b_1$ et $a_2<_2b_2$, etc\ldots  Un mot de Lyndon g\'en\'eralis\'e, pour cet ordre fix\'e $<$, s'obtient par la m\^eme d\'efinition que ci-dessus.

Nous montrons que ces mots de Lyndon g\'en\'eralis\'es forment une factorisation compl\`ete du mono\"\i de libre (Th.\,2.1).  Pour ce faire, nous avons recours aux ensembles de Hall, g\'en\'eralis\'es par Shirshov et Viennot.  Nous montrons que l'ensemble des mots de Lyndon g\'en\'eralis\'es est un ensemble de Hall (Th.\,2.2).  Le lemme crucial donne une propri\'et\'e combinatoire de l'ordre $<$ sur $A^{\Bbb N}$ (lemme~2.1).  Le th\'eor\`eme de Fine et Wilf se r\'ev\`ele \'egalement utile (voir lemme~2.2).  Une fois qu'on sait que l'ensemble des mots de Lyndon g\'en\'eralis\'es forme un ensemble de Hall, il s'ensuit directement que c'est une factorisation du mono\"\i de libre.  Comme autre cons\'equence, on tire que les polyn\^omes de Lie associ\'es forment une base de l'alg\`ebre de Lie libre.

L'exemple motivateur de ces ordres et de ces ensembles vient des fractions continues~: on prend sur $A^{\Bbb N}$ l'{\it ordre lexicographique altern\'e} (cf.\ \cite[p.~11]{Ca}), c'est-\`a-dire $<_i=<_0$ si $i$ pair, $<_i=<_1$ si $i$ impair, et de plus $<_0$ et $<_1$ sont des ordres oppos\'es.  Alors $a_0a_1a_2\ldots<b_0b_1b_2\ldots$ si et seulement si
$$\ds{a_0+\frac{\qquad 1\qquad}{a_1+\ds{\frac{\quad 1\quad}{a_2+\ds{\frac{\ 1\ }{\ddots}}}}}<
b_0+\frac{\qquad 1\qquad}{b_1+\ds{\frac{\quad 1\quad}{b_2+\ds{\frac{\ 1\ }{\ddots}}}}}},$$
l'o\`u l'on a suppos\'e que les $a_i,b_j$ sont des entiers strictement positifs, avec $<_0$ l'ordre usuel et $<_1$ l'ordre oppos\'e.  Nous appelons {\it mots de Galois} les mots de Lyndon g\'en\'eralis\'es correspondant \`a cet ordre.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL CHRISTOPHE REUTENAUER}{\SMALL MOTS DE LYNDON G\'EN\'ERALIS\'ES}
%
%

Les mots de Galois sont en bijection naturelle avec les classes homographiques de nombres de Galois~; $\alpha$ est un {\it nombre de Galois} si $\alpha$ est un r\'eel alg\'ebrique de degr\'e 2, si $\alpha>1$ et si son conjugu\'e est dans $]-1,0[$~: son d\'eveloppement en fraction continue est $w^\infty$, o\`u $w$ est le mot de Galois qui lui correspond dans la bijection ci-dessus.  Une classe homographique est une orbite sous le groupe des homographies $\frac{az+b}{cz+d}$, o\`u $a, b,c,d\in{\Bbb Z}, ad-bc=\pm 1.$

Dans une telle classe, le plus petit nombre de Galois correspond \`a un mot de Galois~; on peut donc le calculer en utilisant un algorithme de Sch\"utzenberger--Melan{\c c}on.  Les mots de Galois sont aussi en bijection avec les classes de formes quadratiques binaires ind\'efinies.  D'autre part, nous utilisons l'ordre lexicographique pour retrouver une partie des r\'esultats de Markoff \cite{M1}, \cite{M2} (voir aussi \cite{D2}, \cite{CF}).  Notre approche utilise les mots de Christoffel et leurs sym\'etries, et permet de retrouver le calcul des nombres de Markoff, entre autres une formule de Harvey Cohn \cite{C}.

  Nous concluons l'article en mentionnant le spectre de Cassaigne \cite{Ca} et les factorisations de Viennot.
%=====================================
%Section 2
%=====================================

\section{Mots de Lyndon g\'en\'eralis\'es}
Soit $A$ un alphabet et $A^{\Bbb N}$ l'ensemble des suites sur $A$.  Consid\'erons une suite $<_0,<_1,<_2,\ldots$ d'ordres totaux sur $A$.  Nous d\'efinissons l'ordre $<$ sur $A^{{\Bbb N}}$ par~: $s<t$ si $s_0<_0t_0$, ou $s_0=t_0$ et $s_1<_1t_1$, ou $s_0=t_0, s_1=t_1$ et $s_2<_2t_2$, etc\ldots

Si $w$ est un mot non vide dans $A^\ast$ (le mono\"\i de libre sur $A$), $w^\infty$ d\'esigne la suite dans $A^{{\Bbb N}}$ obtenue en r\'ep\'etant $w$ une infinit\'e de fois.  Nous dirons que $w$ est un {\it mot de Lyndon g\'en\'eralis\'e} (relatif aux ordres $<_0,<_1,<_2,\ldots$) si pour toute factorisation non triviale $w=uv$, on a $w^\infty<(vu)^\infty$.  Remarquons tout de suite que dans ce cas, $w$ est primitif, i.e. n'est pas une puissance pure~: en effet $w=x^n$ avec $n\geq 2$ implique une factorisation $w=uv=x^{n-1}x$ avec $w^\infty=(vu)^\infty$. 

\vspace{10pt}
\noindent
{\bf Exemples}

\vspace{5pt}
\noindent
1.\ \ Si nous prenons $<_i=<_0$ pour tout $i$ dans ${\Bbb N}$, nous obtenons l'ordre lexicographique usuel sur $A^{\Bbb N}$. Pour des mots $u,v$ d'\'egale longueur dans $A^\ast$, on a $u^\infty<v^\infty$ si et seulement si $u$ est plus petit que $v$ dans l'ordre lexicographique usuel sur $A^\ast$.  Donc un mot de Lyndon g\'en\'eralis\'e est un mot de Lyndon usuel, voir Lothaire \cite[p.~64]{L}.

\vspace{5pt}
\noindent
2.\ \ Nous choisissons ici l'{\it ordre lexicographique altern\'e} sur $A^{\Bbb N}$, c'est-\`a-dire~: $<_i=<_0$ si $i$ pair, $<_i=<_1$ si $i$ impair, et de plus $<_0$ est l'ordre oppos\'e \`a $<_1$.  Par exemple, pour $A={\Bbb P}$ (l'ensemble des nombres entiers naturels non nuls), on prend pour $<_0$ l'ordre naturel et pour $<_1$ l'ordre oppos\'e.  On a donc $1\ldots<2\ldots$ et $12\ldots<11\ldots$.

Nous appellerons {\it mot de Galois} un mot de Lyndon g\'en\'eralis\'e
pour ce choix des ordres $<_i$~;  nous justifierons cette terminologie
plus loin.  Avec $A={\Bbb P}$ comme ci-dessus, nous avons entre autres
les mots de Galois~: 
$$1,2,3,12,4,13,121,5,14,23,122,1211,\ldots,$$ 
\'enum\'er\'es par poids croissant (le poids est ici la somme des chiffres).

Nous allons donner une caract\'erisation des mots de Lyndon g\'en\'eralis\'es, semblable \`a celle des mots de Lyndon \cite[Prop.~5.1.2]{L}~: $w$ est un mot de Lyndon si et seulement si $w$ est plus petit que tous ses suffixes non triviaux pour l'ordre alphab\'etique.
\begin{proposition}
Un mot $w$ est un mot de Lyndon g\'en\'eralis\'e si et seulement si pour toute factorisation non triviale $w=uv$ on a $w^\infty<v^\infty$.
\end{proposition}
Nous aurons besoin du fait bien connu suivant~: pour $u,v$ dans $A^+=A^\ast \verb+\+\{\varepsilon\}$, o\`u $\varepsilon$ d\'esigne le mot vide, on a $u^\infty=v^\infty$ si et seulement si $u$ et $v$ sont puissances d'un m\^eme mot.

Par ailleurs, nous utiliserons la terminologie suivante~: si $s,t$ sont deux \'el\'ements distincts de $A^{\Bbb N}$, avec une factorisation $s=u_1\ldots u_k s^\prime$ ($u_1,\ldots,u_k$ sont des mots finis, et $s^\prime\in A^{\Bbb N}$), nous dirons que {\it la comparaison entre} $s$ et $t$ {\it se fait dans} $u_k$ si $u_1\ldots u_{k-1}$ est pr\'efixe de $t$, mais pas $u_1\ldots u_k$.  Avec ceci, on peut \'ecrire $t=u_1\ldots u_{k-1}u_k^\prime t^\prime$, o\`u $|u_k^\prime|=|u_k|, u_k^\prime\not= u_k$, et l'ordre entre $s$ et $t$ est le m\^eme qu'entre n'importe quelles suites $u_1\ldots u_k\ldots$ et $u_1\ldots u_{k-1}u_k^\prime\ldots$.  Nous utiliserons constamment cette remarque dans la suite.

\begin{proof}
\leavevmode

\noindent
0.\quad  Si $w,v\in A^+$ et $w^\infty\not= v^\infty$, nous pouvons \'ecrire $w^\infty=v^n s$, o\`u $n$ est maximum~; donc $v$ n'est pas pr\'efixe de $s$ et $s=v^\prime s^\prime, |v^\prime|=|v|, v^\prime\not=v$.

\vspace{4pt}
\noindent
1.\quad Soit $w$ un mot de Lyndon g\'en\'eralis\'e et $w=uv$ une factorisation non triviale. Alors $w$ n'est pas une puissance pure.  Donc $w$ et $v$ ne sont pas puissances d'un m\^eme mot, car ce mot devrait \^etre plus court que $w$, puisque $v$ l'est, et $w$ serait une puissance pure.  Donc $w^\infty\not=v^\infty$.

D'apr\`es 0., on peut donc \'ecrire $w=v^n s$ avec les conditions \'enonc\'ees dans 0.  Par hypoth\`ese $w^\infty<(vu)^\infty=v(uv)^\infty=vw^\infty=v^{n+1}s$, et comme $v^{n+1}$ n'est pas pr\'efixe de $w^\infty$, la comparaison entre $w^\infty$ et $v^{n+1}s$ se fait dans le $(n+1)-$\`eme facteur $v$.  Donc on a aussi $w^\infty<v^{n+1}v^\infty=v^\infty$.

\vspace{4pt}
\noindent
2.\quad Supposons qu'on ait $w^\infty<v^\infty$ pour toute factorisation non triviale $w=uv$.  D'apr\`es 0., on a alors $w^\infty=v^n v^\prime s^\prime$, o\`u $|v^\prime|=|v|,v^\prime\not= v$.  Alors la comparaison entre $w^\infty$ et $v^\infty$ se fait dans $v^\prime$.  On a donc aussi $w^\infty<v^{n+1}
s=vv^ns=vw^\infty=v(uv)^\infty=(vu)^\infty$.  Donc $w$ est un mot de Lyndon g\'en\'eralis\'e.
\end{proof}

Nous avons en vue de d\'emontrer le th\'eor\`eme de factorisation suivant.

\begin{theorem}
Les mots de Lyndon g\'en\'eralis\'es constituent une factorisation du mono\"\i de libre.  C'est-\`a-dire~: tout $w$ dans $A^\ast$ a une unique factorisation $w=w_1\ldots w_n$ o\`u chaque $w_i$ est un mot de Lyndon g\'en\'eralis\'e, avec $w_1^\infty\geq\ldots\geq w_n^\infty, n\geq 0$.
\end{theorem}

On notera que la condition $u^\infty\geq v^\infty$, qui n'induit pas un ordre sur $A^+$, mais un pr\'eordre, induit cependant un ordre total sur l'ensemble des mots de Lyndon g\'en\'eralis\'es~: ceci parce qu'un tel mot est primitif.

Pour d\'emontrer le th\'eor\`eme, nous nous ram\`enerons aux ensembles de Hall.  Un {\it ensemble de Hall} est un sous-ensemble $H$ du magma libre $M(A)$ engendr\'e par $A$ (i.e. la structure alg\'ebrique avec une loi non associative engendr\'ee librement par $A$~; ses \'el\'ements s'identifient aux arbres binaires complets \`a feuilles \'etiquet\'ees dans $A$) tel que~:
\begin{enumerate}
\item[$\bullet$]
$H$ est totalement ordonn\'e~;
\item[$\bullet$]
$H$ contient $A$~;
\item[$\bullet$]
tout \'el\'ement de $H\verb+\+ A$ est de la forme $t=(t_1,t_2)$ avec $t_1,t_2\in H$ et $t<t_2$~;
\item[$\bullet$]
plus pr\'ecis\'ement, si $t_1,t_2\in H$, alors $(t_1,t_2)\in H$ si et seulement si $t_1<t_2$ et~: soit $t_1\in A$, soit $t_1=(t_1^\prime,t_1^{\prime\prime})$ et $t_1^{\prime\prime}\geq t_2$.
\end{enumerate}

La d\'efinition que nous prenons ici des ensembles de Hall est plus g\'en\'erale que la d\'efinition de Marshall Hall~; elle provient des travaux de Shirshov \cite{S} et Viennot \cite{V} (voir \cite{R} pour un historique et la pr\'esente d\'efinition).

Il y a un homomorphisme (de magma) naturel de $M(A)$ vers $A^\ast$, qui consiste \`a oublier le parenth\'esage.  Un {\it ensemble de mots de Hall} est l'image sous cet homomorphisme d'un ensemble de Hall dans $M(A)$.

De mani\`ere plus intrins\`eque, un ensemble de mots de Hall peut \^etre d\'efini de la mani\`ere suivante.  C'est un sous-ensemble $H$ de $A^\ast$ tel que~:
\begin{enumerate}
\item[$\bullet$]
$H$ est totalement ordonn\'e~;
\item[$\bullet$]
$H$ contient $A$~;
\item[$\bullet$]
\`a tout \'el\'ement $w$ de $H\verb+\+A$ est associ\'ee une factorisation non triviale $w=uv$ appel\'ee sa {\it factorisation standard}~;
\item[$\bullet$]
pour tout $w\in H\verb+\+A$, de factorisation standard $w=uv$, on a $u,v\in H$ et $w<v$~;
\item[$\bullet$]
si $u,v\in H$, alors $w=uv$ est dans $H$ et $uv$ est sa factorisation standard si et seulement si $u<v$ et soit $u\in A$, soit $u$ a la factorisation standard $u_1u_2$ et $u_2\geq v$.
\end{enumerate}
L'\'equivalence des deux d\'efinitions des ensembles de mots de Hall d\'ecoule entre autres de ce que la fonction naturelle $M(A)\to A^\ast$ est toujours injective sur un ensemble de Hall (voir \cite[Cor.~4.5]{R}).

\vspace{10pt}
Nous allons donc d\'emontrer le th\'eor\`eme suivant.

\begin{theorem}
L'ensemble des mots de Lyndon g\'en\'eralis\'es est un ensemble de mots de Hall.
\end{theorem}

D'apr\`es \cite[Cor.~4.7]{R}, le th\'eor\`eme~2.1 se d\'eduit du th\'eor\`eme~2.2.  Commen{\c c}ons par quelques lemmes.

\begin{lemma}
Soient $u,v,w_1,w_2$ des mots non vides sur $A$. 
\begin{enumerate}
\item[\emph{1.}]
Si $(uw_1)^\infty<v^\infty<(uw_2)^\infty$ et $|u|\leq|v|$ alors $v=uv^\prime$.
\item[\emph{2.}]
Si $(uv)^\infty<v^\infty<u^\infty$, alors $v=u^nu^\prime, u=u^\prime u^{\prime\prime}, n\geq 0$.
\item[\emph{3.}]
On a $(uv)^\infty <v^\infty\Leftrightarrow u^\infty<v^\infty$.
\item[\emph{4.}]
On a $(uv)^\infty=v^\infty\Leftrightarrow u^\infty=v^\infty$.
\end{enumerate}
\end{lemma}

\begin{remark}Parmi les nombreux r\'esultats interm\'ediaires qui m\`enent \`a la d\'emon\-stration de son th\'eor\`eme du centralisateur, Bergman \cite[Lemma~5.1]{B} donne le r\'esultat suivant, pour l'ordre lexicographique usuel (dans nos notations, on choisit donc $<_i=<_0$ pour tout $i$)~: si $u^\infty<v^\infty$, alors $u^\infty<(uv)^\infty<(vu)^\infty<v^\infty$.  Il en donne une preuve simple et \'el\'egante.  Celle-ci ne se g\'en\'eralise pas \`a nos ordres lexicographiques, d'autant plus que la conclusion n'est pas vraie.  On peut en effet avoir $u^\infty< v^\infty$ sans qu'on ait $u^\infty<(uv)^\infty$ ou $(vu)^\infty<v^\infty$~; par exemple, reprenant l'exemple de l'ordre lexicographique altern\'e ci-dessus, nous avons $1^\infty<2^\infty$ mais $1^{\infty}>(12)^\infty$, et $(21)^{\infty}>2^\infty$.
\end{remark}

Nous avons cependant le r\'esultat suivant, qui d\'ecoule du lemme pr\'ec\'edent et de la derni\`ere partie de la preuve de la proposition 2.1.

\begin{corollary}
Si $u^\infty<v^\infty$, alors $u^\infty<(vu)^\infty,(uv)^\infty<(vu)^\infty,(uv)^\infty<v^\infty$.
\end{corollary}

Nous aurons besoin dans la preuve du lemme~2.1 d'un r\'esultat qui se d\'eduit facilement d'un th\'eror\`eme de Fine et Wilf (voir \cite[Prop.~1.3.5]{L}).

\begin{lemma}
Si $s=u^\infty\not=v^\infty=t$, alors il existe $i\in\{0,1,2,\ldots,|u|+|v|-2\}$ tel que $s_i\not=t_i$.  Autrement dit, la comparaison entre $s$ et $t$ se fait dans leur pr\'efixe de longueur $|u|+|v|-1$.
\end{lemma}

\begin{proof}
Dans le cas contraire, le mot $w$, pr\'efixe de longueur $|u|+|v|-1$ de $s$ et $t$, admet les p\'eriodes $|u|$ et $|v|$.  D'apr\`es le th\'eor\`eme de Fine et Wilf, $w$ a la p\'eriode $d=pgdc\,(|u|,|v|)$.  Comme $u$ et $v$ sont pr\'efixes de $w$, et que $d$ divise leur longueur, $u$ et $v$ sont puissances d'un m\^eme mot.  Donc $u^\infty=v^\infty$.
\end{proof}

\begin{proof}[Preuve du lemme 2.1]
\leavevmode

\noindent
1.\quad On peut \'ecrire $v=u^\prime v^\prime$ avec $|u^\prime|=|u|$.  On a $(uw_1)^\infty<(u^\prime v^\prime)^\infty=u^\prime v^\prime u^\prime v^\prime\ldots$.  Si la comparaison se fait dans le premier $u^\prime$, on aura aussi $(uw_2)^\infty<(u^\prime v^\prime)^\infty$, ce qui contredit l'hypoth\`ese. Donc la comparaison ne se fait pas dans cet $u^\prime$, ce qui signifie que $u=u^\prime$, ce qu'il fallait d\'emontrer.

\vspace{6pt}
\noindent
2.\quad Nous pouvons \'ecrire $v=u^nv^\prime$, o\`u $n$ est maximum, donc $u$ n'est pas pr\'efixe de $v^\prime$.  Nous avons donc $(uv)^\infty=(u^{n+1}v^\prime)^\infty<v^\infty<(u^{n+1})^\infty$.  Si l'on avait $|v^\prime|\geq |u|$, i.e. $|v|\geq |u^{n+1}|$, la premi\`ere partie du lemme montrerait que $u^{n+1}$ est pr\'efixe de $v$, contradiction.  Donc $|v^\prime|<|u|$.  ƒcrivons $u=u^\prime u^{\prime\prime}$ avec $|u^\prime|=|v^\prime|$.  Alors les in\'egalit\'es ci-dessus s'\'ecrivent  $(u^nu^\prime u^{\prime\prime}v^\prime)^\infty<v^\infty <(u^nu^\prime u^{\prime\prime})^\infty$.

Comme $|v|=|u^nu^\prime|$, la premi\`ere partie montre qu'on a $v=u^n u^\prime$, ce qu'il fallait d\'emontrer.

\vspace{6pt}
\noindent
4.\quad D'apr\`es la remarque faite avant la preuve de la proposition 2.1, on a $(uv)^\infty=v^\infty \Leftrightarrow u^\infty=v^\infty$, ce qui d\'emontre 4.

\vspace{6pt}
\noindent
3.\quad Nous supposons que $(uv)^\infty<v^\infty$.  Nous supposons dans un premier temps que $|v|\leq |u|$.  Si la comparaison entre $(uv)^\infty$ et $v^\infty$ se fait dans le premier $u$ de $(uv)^\infty$, on aura aussi $u^\infty<v^\infty$.  Si elle ne s'y fait pas, on aura $u=v^iv^\prime, v=v^\prime v^{\prime\prime}$ et $i\geq 1$ \`a cause de l'hypoth\`ese sur les longueurs.  Supposons qu'on ait $u^\infty>v^\infty$, c'est-\`a-dire $v^iv^\prime v\ldots>v^\infty$~; d'apr\`es le lemme~2.2, la comparaison se fait dans le pr\'efixe $v^iv^\prime v$ de $u^\infty$, puisqu'il est de longueur $|u|+|v|$.  Par suite, on a aussi $(v^iv^\prime v)^\infty>v^\infty$, c'est-\`a-dire $(uv)^\infty>v^\infty$, une contradiction.  Donc $u^\infty<v^\infty$.  


\vspace{4pt}
Il nous faut encore traiter le cas $|v|>|u|$.  Raisonnant encore par l'absurde, supposons que $v^\infty<u^\infty$, donc $(uv)^\infty<v^\infty<u^\infty$.  D'apr\`es la 2\`eme partie, on a donc $v=u^nu^\prime, u=u^\prime u^{\prime\prime}$ et $n\geq 1$ d'apr\`es l'hypoth\`ese sur les longueurs.  La derni\`ere \'egalit\'e se r\'e\'ecrit $u^nu^\prime u\ldots<u^{n+1}u^\prime\ldots$ et d'apr\`es le lemme~2.2, la comparaison se fait dans les pr\'efixes $u^nu^\prime u$ et $u^{n+1}u^\prime$ des mots $v^\infty$ et $u^\infty$, car $|u|+|v|=|u^{n+1}u^\prime|$.  Comme $u^{n+1}u^\prime=uv$, on a aussi $v^\infty<(uv)^\infty$, une contradiction.  En conclusion, on doit avoir $u^\infty<v^\infty$.

Nous venons de prouver que $(uv)^\infty<v^\infty$ implique $u^\infty<v^\infty$.  Comme ceci est valable pour l'ordre lexicographique associ\'e \`a toute suite $(<_i)_{i\geq 0}$, c'est aussi valable pour l'ordre oppos\'e, qui est associ\'e \`a la suite des ordres oppos\'es.  Donc on a aussi $(uv)^\infty>v^\infty\Rightarrow u^\infty>v^\infty$.  Comme ces ordres sont totaux, nous obtenons 3, puisque 4. est d\'ej\`a acquis.
\end{proof}

\begin{proof}[Preuve du th\'eor\`eme 2.2]
Soit $H$ l'ensemble des mots de Lyndon g\'en\'eralis\'es relatifs \`a l'ordre lexicographique $<$ associ\'e \`a la suite des ordres totaux $(<_i)_{i\in {\Bbb N}}$ sur $A$.  Comme nous l'avons vu apr\`es le th\'eor\`eme~2.1, la condition $u^\infty<v^\infty$ induit sur les $u,v$ dans $H$ un ordre total, car les mots dans $H$ sont primitifs.  Nous \'ecrirons $u<v$ pour $u^\infty<v^\infty$ et $u,v$ dans $H$.

Clairement, $H$ contient $A$.  Si $w\in H\verb+\+A$, nous appelons {\it factorisation standard} de $H$ la factorisation non triviale $w=uv$, o\`u $v$ satisfait \`a la condition suivante~: pour tout facteur droit propre non trivial $v^\prime$ de $w$, soit $v^\infty<v^{\prime\infty}$, soit $v^\infty=v^{\prime\infty}$ (i.e. $v,v^\prime$ sont puissances d'un m\^eme mot) et $v^\prime$ est puissance de $v$.

On a alors $u^\infty<v^\infty$~: en effet, comme $w$ est un mot de Lyndon g\'en\'eralis\'e, on a $w^\infty<v^\infty$ (Proposition 2.1), i.e. $(uv)^\infty<v^\infty$, ce qui implique par le lemme~2.1 que $u^\infty<v^\infty$.

Si $v^\prime$ est un facteur droit propre non trivial de $v$, on a $v^\infty<v^{\prime\infty}$ par construction de $v$~; donc $v$ est un mot de Lyndon g\'en\'eralis\'e d'apr\`es la Proposition 2.1.  De plus, $u$ est aussi un mot de Lyndon g\'en\'eralis\'e~: en effet, si $u=u_1u_2$ est une factorisation non triviale, on a $v^\infty\leq(u_2v)^\infty$ par construction de $v$.  Donc, par le lemme~2.1, $v^\infty\leq u_2^\infty$, et par ce qui pr\'ec\`ede, $u^\infty<u_2^\infty$.  Donc $u$ est un mot de Lyndon g\'en\'eralis\'e d'apr\`es la proposition 2.1.  Nous en concluons que pour tout mot de Lyndon g\'en\'eralis\'e $w$, qui n'est pas dans $A$, sa factorisation standard $w=uv$ satisfait \`a~: $u,v\in H$ et $w<v$ (cette derni\`ere \'egalit\'e d'apr\`es la proposition 2.1).

Supposons de plus que $u$ ne soit pas une lettre et ait la factorisation standard $u=u_1u_2$.  Il d\'ecoule alors de l'argument ci-dessus que $u_2^\infty\geq v^\infty$, donc que $u_2\geq v$ ($u_2, v$ sont dans $H$).

Pour finir, il faut montrer que si $u,v$ sont dans $H$, si $u<v$ et si, soit $u\in A$, soit $u$ a la factorisation standard $u=xy$ avec $y\geq v$, alors $w=uv$ est dans $H$ et a $uv$ comme factorisation standard.

Supposons d'abord que $u\in A$.  On a $u^\infty<v^\infty$ par l'hypoth\`ese, donc $w^\infty=(uv)^\infty<v^\infty$ d'apr\`es le lemme~2.1.  Si $v=v_1v_2$ est une factorisation non triviale, on aura $v^\infty<v_2^\infty$ d'apr\`es  la  proposition 2.1.  Donc $w^\infty<v^{\prime\infty}$ pour tout facteur droit propre non trivial $v^\prime$ de $w$ (car $u\in A$), et $w\in H$ d'apr\`es la proposition 2.1.  De plus $w=uv$ est sa factorisation standard.

Supposons maintenant que $u\not\in A$, avec factorisation standard $u=xy$ et $y\geq v$.  Comme ci-dessus, on a $w^\infty<v^\infty$.  Comme ci-dessus aussi, $w^\infty<v^\infty <v_2^\infty$ pour toute factorisation non triviale $v=v_1v_2$.  Soit maintenant $u=u_1u_2$ une factorisation non triviale de $u$.
On a $y^\infty\geq v^\infty$ par hypoth\`ese.  De plus $u_2^\infty\geq y^\infty$ par d\'efinition de la factorisation standard $u=xy$. Donc $u_2^\infty\geq v^\infty$, ce qui implique $(u_2v)^\infty\geq v^\infty$ par le lemme~2.1.  Enfin, $w^\infty<(u_2v)^\infty$.  Tout ceci montre que $w$ est dans $H$, par la proposition 2.1.  De plus, $w=uv$ est sa factorisation standard, car $v^\infty$ est minimum parmi les $v^{\prime\infty}$, pour $v^\prime$ suffixe propre non trivial de $w$, et de plus $|v|$ est de longueur minimum.
\end{proof}

\begin{remark}
Nous avons d\'efini la factorisation standard d'un mot de Lyndon g\'en\'eralis\'e $w$ par $w=uv$, o\`u $v^\infty$ est choisi minimum parmi les facteurs droits (propres non triviaux) de $w$, et $v$ de longueur minimum.  Comme pour les mots de Lyndon usuels, $v$ est aussi le plus long suffixe propre de $w$ qui est un mot de Lyndon g\'en\'eralis\'e.  En effet, s'il existait un suffixe $v_1$ de $w$, plus long que $v$, qui est un mot de Lyndon g\'en\'eralis\'e, on aurait par la proposition 2.1 $v_1^\infty<v^\infty$, une contradiction.

Ceci montre d'ailleurs que la factorisation standard des mots de Lyndon, telle que d\'efinie ici, lorsqu'on prend $<_i=<_0$ pour tout $i$, est la m\^eme que celle d\'efinie dans \cite[p.~66]{L}.
\end{remark}

\begin{corollary}
Soit $w=l_1\ldots l_n$, $l_1\geq\cdots\geq l_n$, o\`u les $l_i$ sont des mots de Lyndon g\'en\'eralis\'es.  Alors $l_n$ est le plus court parmi les suffixes non triviaux $v$ de $w$ r\'ealisant le minimum de $v^\infty$.
\end{corollary}

\begin{proof}
Notons $z$ le suffixe non trivial de $w$, le plus court parmi ceux qui r\'ealisent le minimum de $z^\infty$.  Si $w=z,w$ est un mot de Lyndon g\'en\'eralis\'e d'apr\`es la proposition 2.1.  Sinon $w=uz$, et nous d\'efinissons la factorisation $u=l_1\ldots l_{n-1}$ en mots de Lyndon g\'en\'eralis\'es avec $l_1\geq\cdots\geq l_{n-1}, n\geq 2$.  Il suffit de montrer que $l_{n-1}\geq z$, car $z$ est un mot de Lyndon g\'en\'eralis\'e, par construction et d'apr\`es la proposition 2.1.  Mais on a $(l_{n-1}z)^\infty\geq z^\infty$ par construction de $z$.  Le lemme~2.1 montre qu'alors $l_{n-1}^\infty\geq z^\infty$, et donc  $l_{n-1}\geq z$.
\end{proof}

Le corollaire~2.2, joint au th\'eor\`eme de factorisation de
Sch\"utzenberger\break \cite[Th.~5.4.1]{L}, d\'emontre encore une fois le th\'eor\`eme~2.1, sans passer par les ensembles de Hall.  Ceux-ci ont cependant l'avantage de permettre la construction de bases de l'alg\`ebre de Lie libre. En effet, par it\'eration de la factorisation standard, chaque mot de Lyndon g\'en\'eralis\'e vient avec un parenth\'esage complet.  Celui-ci d\'efinit un polyn\^ome de Lie dans l'alg\`ebre associative libre ${\Bbb Z}\langle A\rangle$.

\begin{corollary}
Les polyn\^omes de Lie ainsi d\'efinis forment une base de l'alg\`ebre de Lie libre.
\end{corollary}
Cela d\'ecoule de la th\'eorie des bases de Hall, voir \cite[Th.4.9]{R}.

%=====================================
%Section 3
%=====================================
\section{Mots de Galois et applications}
\subsection{Ordre lexicographique altern\'e}
Cet ordre a \'et\'e introduit au d\'ebut de la section pr\'ec\'edente.  La motivation en est la suivante~: cet ordre refl\`ete l'ordre des nombres r\'eels, d\'evelopp\'es en fraction continues.

Plus pr\'ecis\'ement, \'etant donn\'e une suite d'entiers $a_0,a_1,a_2,\ldots$ naturels strictement positifs, notons $\alpha=[a_0,a_1,a_2,\ldots]$ le nombre r\'eel ayant le d\'eveloppement en fraction continue
$$\alpha=a_0+\frac{1}
{a_1+\ds{\frac{1}{a_2+\cdots}}}.$$
Si $b_0,b_1,b_2,\ldots$ est une autre suite, il est bien connu et facile de v\'erifier que\break $[a_0,a_1,a_2,\ldots]<[b_0,b_1,b_2,\ldots]$ si et seulement si~: soit $a_0<b_0$, soit $a_0=b_0$ et $a_1>b_1$, soit $a_0=b_0, a_1=b_1$ et $a_2<b_2$, etc.~; autrement dit, si l'on a $a_0a_1a_2\ldots<b_0b_1b_2\ldots$ pour l'ordre lexicographique altern\'e.

La version finitaire de cet ordre permet de comparer avec une grande efficacit\'e les nombres rationnels (de mani\`ere \'equivalente, calculer le signe du d\'eterminant d'une matrice $2\times 2$ \`a coefficients entiers), voir \cite{Va}. 
\subsection{Mots de Galois}
Ceux-ci ont \'et\'e d\'efinis au paragraphe 2, Exemples.  Avant de poursuivre les applications, donnons-en une propri\'et\'e combinatoire.  Celle-ci est inspir\'ee du fait que les mots de Lyndon usuels sont sans bord (voir \cite[p.~65]{L}).  Une preuve tr\`es \'el\'egante en est donn\'ee par Duval \cite{Du}~; nous l'adaptons \`a notre cas ci-dessous.  Rappelons qu'un {\it bord} d'un mot $w$ est un mot $v$ tel qu'on ait une \'egalit\'e non triviale $w=uv=vu^\prime$, pour des mots $u,u^\prime$ (par exemple, $ababa$ a pour bords $a$ et $aba$).  Les exemples de mots de Galois donn\'es dans la section 2 montrent que ceux-ci peuvent avoir des bords.

\begin{proposition}
Si un mot de Galois $w\,a$ un bord $v$, alors $v$ est de longueur impaire.
\end{proposition} 

\begin{proof}
On a $w=uv=vu^\prime$.  Comme $w$ est un mot de Galois, on doit avoir $w^\infty=(uv)^\infty <(u^\prime v)^\infty$ et $w^\infty=(vu^\prime)^\infty<(vu)^\infty$.  Comme $u,u^\prime$ sont de m\^eme longueur, la comparaison pour la premi\`ere in\'egalit\'e se fait dans $u,u^\prime: uvuv\cdots< u^\prime vu^\prime v\ldots$  Si $v$ \'etait de longueur paire, \`a cause de la d\'efinition de l'ordre lexicographique altern\'e, on obtiendrait $vuvuv\ldots<vu^\prime vu^\prime v\ldots$, i.e. $(vu)^\infty<(vu^\prime)^\infty$, ce qui contredirait la deuxi\`eme in\'egalit\'e.
\end{proof}

\subsection{Nombres quadratiques}
D'apr\`es un th\'eor\`eme de Lagrange, un nombre r\'eel $\alpha>0$ a un d\'eveloppe\-ment en fraction continue p\'eriodique si et seulement si c'est un nombre quadratique, c'est-\`a-dire s'il n'est pas rationnel et annule un polyn\^ome de degr\'e 2 \`a coefficients entiers (autrement dit, si $\alpha=a+b\sqrt d,\, a,b\in{\Bbb Q},\, d\in{\Bbb N}$, non carr\'e).  Galois pr\'ecise les choses~: le d\'eveloppement est purement p\'eriodique si et seulement si de plus $\alpha>1$ et si son conjugu\'e est dans l'intervalle $]-1,0[$ (le conjugu\'e de $a+b\sqrt d$ est $a-b\sqrt d$).  Appelons {\it nombre de Galois} un tel nombre.

Il y a donc clairement une bijection entre les mots primitifs dans ${\Bbb P}^+$ et les nombres de Galois~: \`a tout $w\in{\Bbb P}^+$, primitif, est associ\'e le nombre de Galois dont le d\'eveloppement en fraction continue est $w^\infty$.

Rappelons que deux nombres r\'eels $\alpha,\beta$ ont m\^eme d\'eveloppement en fraction continue \`a partir d'un certain rang (i.e.. $\exists k\in{\Bbb Z}$ tel que $a_n=b_{n+k}$ pour $n$ assez grand) si et seulement s'ils sont reli\'es par une homographie enti\`ere~: $\beta=\frac{a\alpha+b}{c\alpha+d}, a,b,c,d\in{\Bbb Z}, ad-bc=\pm 1$.  Nous obtenons donc le r\'esultat suivant.
\begin{proposition}
Il y a une bijection naturelle entre mots de Galois et classes homographiques de nombres de Galois, qui associe \`a un mot de Galois $w$ le plus petit nombre de la classe.
\end{proposition}

Ceci justifie bien s\^ur notre terminologie.  Un exemple~: 121 est un mot de Galois 
et ses deux conjugu\'es satisfont $(121)^\infty<(112)^\infty<(211)^\infty$.  Les nombres quadratiques associ\'es sont respectivement $\frac{1+\sqrt{10}}{3},\frac{2+\sqrt{10}}{3},\frac{2+\sqrt{10}}{2}$.

On notera que les nombres de Galois ne co\"\i ncident pas avec les nombres de Sturm d\'ecrits dans \cite{CMPS}, \cite{A} et \cite{BS}.

\subsection{Algorithme de Sch\"utzenberger--Melan{\c c}on}
Il y a un algorithme pour calculer le mot de Galois contenu dans une classe de conjugaison primitive.  C'est un cas particulier d'un algorithme de Melan{\c c}on \cite{Me}, qui calcule pour tout mot $w$ l'unique puissance d'un mot de Hall conjugu\'e \`a $w$, et ceci pour tout ensemble de Hall (cet algorithme g\'en\'eralise un algorithme de Sch\"utzenberger \cite{S1}).

Nous l'\'enon{\c c}ons ci-dessous~; on en d\'eduit ais\'ement un algorithme pour calculer le plus petit \'el\'ement dans une classe homographique de nombres de Galois.

Une suite $\sigma=(h_1,\ldots,h_n)$ de mots de Galois est dite {\it circulairement standard} si pour tout $i=1,\ldots,n$, soit $h_i$ est une lettre, soit $h_i=h_i^\prime h_i^{\prime\prime}$ (factorisation standard) et $h_i^{\prime\prime}\geq h_1,\ldots,h_n$.  Une suite de lettres est clairement circulairement standard.  Une {\it mont\'ee} est un couple $(h_i,h_{i+1})$ tel que $h_i<h_{i+1}$ (les indices sont pris modulo $n$)~; une mont\'ee est dite {\it l\'egale} si $h_{i+1}\geq h_1,\ldots,h_n$.  Dans ce cas, on d\'efinit $\sigma^\prime$ par $\sigma^\prime=(h_1,\ldots,h_i h_{i+1},\ldots,h_n)$ si $i<n$ et $\sigma^\prime=(h_n h_1,h_2,\ldots,h_{n-1})$ si $i=n$.  En it\'erant cette construction, on obtient \`a partir de toute suite de lettres, repr\'esentant un mot $w$, l'unique puissance d'un mot de Galois conjugu\'ee \`a $w$.  Si $w$ est primitif, on obtient l'unique mot de Galois conjugu\'e \`a $w$.

%=====================================
%sous-section 3.5
%=====================================
\subsection{Formes quadratiques}
Nous consid\'erons des {\it formes quadratiques binaires ind\'efinies
\`a coefficients entiers} (nous dirons simplement forme dans la
suite)~; une telle forme s'\'ecrit $ax^2+bxy+cy^2$, $a,b,c\in{\Bbb Z}$
non tous nuls, et son {\it discriminant} $\triangle=b^2-4ac$ est $>0$.
Nous consid\'erons comme {\it \'equivalentes} deux formes
proportionnelles, et aussi deux formes qui s'obtiennent l'une de
l'autre par un changement de variable $(x,y)\mapsto (px+qy, rx+sy)$,
o\`u la matrice $\left(\begin{smallmatrix}p &q\\ r& s\end{smallmatrix}\right)$ est dans $SL_2({\Bbb Z})$~; on notera que cette \'equivalence n'est pas celle consid\'er\'ee g\'en\'eralement dans la litt\'erature (par exemple \cite[p.~5]{Bu}).

Une forme est dite {\it r\'eduite} si l'on a $|f|<1, |s|>1, fs<0$, avec
$$f=\frac{\sqrt\triangle-b}{2a},\quad s=\frac{-\sqrt\triangle-b}{2a}.$$
Bien s\^ur, $f$ et $s$ sont les racines de l'\'equation $ax^2+bx+c=0$.  De mani\`ere \'equivalente, une forme est r\'eduite si et seulement si $0<\sqrt\triangle-b<2|a|<\sqrt\triangle+b$ (voir \cite[p.~99--100]{D1}, \cite[p.~21]{Bu}). On notera qu'alors $b$ est $>0$. Toute forme est \'equivalente \`a une forme r\'eduite, non n\'ecessairement unique (\cite[p.~101]{D1}, \cite[p.~22]{Bu}).  Les formes r\'eduites \'equivalentes ont une structure cyclique naturelle~: la forme $a^\prime x^2+b^\prime xy+c^\prime y^2$ est dite {\it adjacente \`a droite} de la forme $ax^2+bxy+cy^2$ si $c=a^\prime$ et s'il existe $\delta\in{\Bbb Z}$ tel que $b^\prime=-b-2\delta c$, $c^\prime=a+b\delta+c\delta^2$ (ce qui signifie que $a^\prime x^2+b^\prime xy+c^\prime y^2$ s'obtient de $ax^2+bxy+cy^2$ en y faisant le changement de variables $x\mapsto y$, $y\mapsto -x+\delta y$).  La forme adjacente \`a droite est unique et tout forme r\'eduite est adjacente \`a droite \`a une unique forme r\'eduite (\cite[p.~103]{D1}, \cite[p.~22--33]{Bu}).  De plus, deux formes adjacentes ont m\^eme discriminant et les formes de m\^eme discriminant sont en nombre fini (\cite[p.~103]{D1}, \cite[p.~23]{Bu}).  Ainsi, une forme d\'efinit une suite bi-infinie p\'eriodique de formes, donc un cycle de telles formes.  Ë ce cycle on associe le mot circulaire obtenu en consid\'erant la suite des $|\delta|$, o\`u $\delta$ est le param\`etre ci-dessus.  On obtient ainsi un mot circulaire primitif sur ${\Bbb P}=\{1,2,3,\ldots\}$, donc un mot de Galois.

Pour r\'ecup\'erer une forme quadratique \`a partir de ce mot circulaire, on consid\`ere le nombre r\'eel quadratique dont le d\'eveloppement en fraction continue correspond \`a ce mot circulaire, ind\'efiniment r\'ep\'et\'e.  Il est racine d'une \'equation $a+by+cy^2=0$, $a,b,c\in{\Bbb Z}$, et la forme quadratique cherch\'ee est $ax^2+bxy+cy^2$ (voir \cite[p.~104--108]{D1}).

Le fait que deux formes \'equivalentes dans notre sens donnent le m\^eme mot circulaire provient de ce que deux formes {\it proprement \'equivalentes} (i.e. on consid\`ere des formes obtenues l'une de l'autre par changement de variables dans $SL_2(\Bbb Z)$) correspondent \`a la m\^eme cha\^\i ne (\cite[p.~108]{D1}, \cite[p.~24]{Bu}).

Voyons deux exemples, tir\'es de \cite[p.~29]{Bu}.  Nous repr\'esentons une forme $ax^2+bxy+cy^2$ par $(a,b,c)$.  Supposons-la r\'eduite, et que $(a^\prime,b^\prime,c^\prime)$ lui est adjacente \`a droite.  Alors le nombre $\delta$ qui permet de faire passer l'un \`a l'autre est \'egal \`a $-\frac{b+b^\prime}{2c}$ (voir ci-dessus).
\begin{enumerate}
\item[$\bullet$]
$\triangle=5$, le cycle de longueur $2$~: $(1,1,-1)$, $(-1,1,1)$.  Le mot circulaire des $\delta$ est~: $1,-1$ et par suite le mot circulaire est simplement 1, qui est le mot de Galois associ\'e.
\item[$\bullet$]
$\triangle=23$, le cycle de longueur $6$~: $(5,9,-12)$, $(-12,15,2)$,
$(2,17,-4)$,\break $(-4,15,6)$, $(6,9,-10)$, $(-10,11,5)$. Les
$\delta$ sont sucessivement~: $1,-8,4,-2,\break 1,-2$. Le mot de Galois est $184212$.
\end{enumerate}

%=====================================
%Sous-section 3.6
%=====================================
\subsection{Nombres de Markoff}
Soit $A$ une suite bi-infinie sur ${\Bbb P}$~: 
$$A=\ldots a_{-2}a_{-1}a_0 a_1a_2\ldots$$  
D\'efinissons $\lambda_i(A)=a_i+[0,a_{i+1},a_{i+2},\ldots]+
[0, a_{i-1},a_{i-2},\ldots]$ et $M(A)=\sup\{\lambda_i(A)\mid i\in{\Bbb Z}\}$.


Pour des raisons li\'ees \`a la th\'eorie de Markoff des approximations de fractions continues et des minima de formes quadratiques, on est amen\'e \`a consid\'erer des suites bi-infinies de la forme $A={} ^\infty W^\infty$, o\`u $W$ est un mot obtenu d'un mot de Christoffel sup\'erieur $w$ sur l'alphabet $\{1,2\}$ en lui appliquant la substitution $1\mapsto 11, 2\mapsto 22$.  Les {\it mots de Christoffel sup\'erieurs} sont des mots primitifs d\'efinis dans \cite{BS} (ce sont les mots not\'es $t_{pq}^\prime$ p.~59).  Pour usage ult\'erieur, notons qu'un mot de Christoffel sup\'erieur de longueur $\geq 2$ s'\'ecrit toujours $w=2m1$, o\`u $m$ est un palindrome (i.e. $m$ est \'egal \`a son image miroir $\tilde{m}$)~; le {\it mot de Christofffel inf\'erieur} associ\'e ($t_{pq}$ dans la r\'ef\'erence ci-dessus) est alors $1m2$, et ce mot est conjugu\'e \`a $w$.  Par ailleurs, dans la classe de conjugaison associ\'ee, $1m2$ est le plus petit et $2m1$ est le plus grand dans l'ordre lexicographique usuel (avec $1<2$).

\begin{proposition}
Soit $A={}^\infty W^\infty$ comme ci-dessus, o\`u $w=2m1$ est le mot de Christoffel sup\'erieur envoy\'e sur $W$ par la substitution $1\mapsto 11, 2\mapsto 22$.  Alors $A={}^\infty(\underline{2}2M11)^\infty={}^\infty(11M2\underline{2})^\infty$ et les indices $i$ tels que $M(A)=\lambda_i(A)$ sont ceux qui sont soulign\'es et ceux obtenus par la p\'eriode de $A$~; ici $M$ est l'image de $m$ sous la substitution $1\mapsto 11, 2\mapsto 22$.
\end{proposition}

\begin{proof}
Comme $1m2$ et $2m1$ sont conjugu\'es, $11M22$ et $22M11$ le sont aussi, et $A$ est \`a la fois \'egal \`a $^\infty(22M11)^\infty$ et $^\infty(11M22)^\infty$.  Si $i, i^\prime$ sont respectivement les deux positions soulign\'ees dans l'\'enonc\'e, on a $\lambda_i(A)=\lambda_{i^\prime}(A)$, car $\lambda_i(A)=\lambda_{-i}(\tilde{A})$, o\`u $\tilde{A}$ est l'image miroir de $A$.

Il suffit donc de montrer que $\lambda_i(A)>\lambda_j(A)$ pour toute autre position $j$ situ\'ee sur la premi\`ere des deux lettres $11$ ou $22$ de la factorisation canonique de $22M11$ en produit de $11$ et $22$.  Nous utilisons pour ce faire le fait que l'ordre lexicographique altern\'e correspond \`a l'ordre des fractions continues.  Comme $2m1$ (respectivement $1m2$) est le plus grand (respectivement petit) des conjugu\'es de $2m1$ et $1m2$ dans l'ordre lexicographique usuel on a que pour toute factorisation $A={}^\infty P^\infty$, o\`u la premi\`ere lettre de $P$ est en position $j$, $(22M11)^\infty>P^\infty$ et $^\infty P>{}^\infty(22M11)$ pour l'ordre lexicographique, qu'il soit altern\'e ou usuel, \`a cause des duplications des lettres.  Par cons\'equent $[a_i,a_{i+1},a_{i+2},\ldots]>[a_j,a_{j+1},a_{j+2},\ldots]$ et $[a_{i-1},a_{i-2},a_{i-3},\ldots]<[a_{j-1},a_{j-2},a_{j-3},\ldots]$.  Cette derni\`ere in\'egalit\'e implique\break $[0,a_{i-1},a_{i-2},\ldots]>[0,a_{j-1},a_{j-2},\ldots]$, d'o\`u $\lambda_i(A)>\lambda_j(A).$
\end{proof}

Dans les hypoth\`eses de la proposition, nous pouvons maintenant donner les valeurs de $M(A)$.  Pour cela rappelons la d\'efinition des {\it polyn\^omes continuants}~: $P(x_1,\ldots,x_n)$ est le coefficient $1,1$ de la matrice produit 
$$\hbox to15cm{$(\ast)\hfill
\hspace{2cm}
\left({\begin{array}{cc}
x_1&1\\
1&0
\end{array}}\right)
\left({\begin{array}{cc}
x_2&1\\
1&0
\end{array}}\right)
\cdots
\left({\begin{array}{cc}
x_n&1\\
1&0
\end{array}}\right).\hfill
$\hphantom{($\ast$)}}
$$

De mani\`ere \'equivalente, on a la r\'ecurrence
$$P(x_1,\ldots,x_n)=P(x_1,\ldots,x_{n-1})x_n+P(x_1,\ldots,x_{n-2}),$$
avec les conditions initiales $P(\ )=1, P(x_1)=x_1$.  Si $w$ est un mot sur l'alphabet ${\Bbb P}$, nous \'ecrirons simplement $P(w)$ pour $P(x_1,\ldots,x_n)$, o\`u $w=x_1\ldots x_n$.  Exemple~: $P(21111)=P(2111)+P(211)=2\cdot P(211)+P(21)=3\cdot P(21)+2\cdot P(2)=5\cdot P(2)+3\cdot P(\ )=5\cdot 2+3\cdot 1=13$.

Consid\'erons encore l'homomorphisme $\mu$ du mono\"\i de libre $\{1,2\}^\ast$ sur le mono\"\i de multiplicatif des matrices, qui envoie 1 sur 
$\left(\begin{smallmatrix}2& 1\\ 1& 1\end{smallmatrix}\right)$
 et 2 sur $\left(\begin{smallmatrix}5& 2\\ 2& 1\end{smallmatrix}\right)$.
 
\begin{corollary}
Soit $A,W,w$ comme ci-dessus, en excluant le cas $w=1$.  Alors $W=2W^\prime$ et $M(A)$ est \'egal \`a $\sqrt{9-\frac{4}{c^2}}$ o\`u $$c=P(W^\prime)=(\mu w)_{21}=\frac{1}{3}\mbox{tr} (\mu w).$$
\end{corollary} 
Les nombres $c$ ainsi obtenus s'appellent les nombres de Markoff~; par exemple, 13 est un  nombre de Markoff.  Une conjecture importante sur ces nombres est la suivante~: la fonction $w\mapsto c$ de l'ensemble des mots de Christoffel sup\'erieurs sur l'ensemble des nombres de Markoff est injective.  Cette conjecture est mentionn\'ee par Frobenius en 1913 \cite[p.~601]{F}, par Cusick et Flahive \cite[p.~11]{CF} et par Conway et Guy \cite[p.~188]{CG} (sous une formulation diff\'erente).  On notera que les {\it coordonn\'ees de Frobenius} (voir \cite[par.~8]{F}, \cite[p.~24]{CF}) du nombre de Markoff $c$ ci-dessus ne sont autres que les nombres de 1 et de 2 dans le mot de Christoffel $w$.

Nous utiliserons le r\'esultat bien connu suivant.
\begin{lemma}
Soit $u$ un mot primitif sur ${\Bbb P}$ et $\left(\begin{smallmatrix}a& b\\ c& d\end{smallmatrix}\right)$
 son image sous l'homomorphisme qui envoie $i$ sur $\left(\begin{smallmatrix}i& 1\\ 1& 0\end{smallmatrix}\right)$
 et $\varepsilon=ad-bc=\pm 1$.  Alors la somme des nombres r\'eels dont les d\'eveloppements en fractions continues sont $u^\infty$ et $0\; \tilde{u}^\infty$ est \'egale \`a $\frac{\sqrt{(a+d)^2-4\varepsilon}}{c}$.
\end{lemma}

\begin{proof}
Il est bien connu que, si $\alpha,\beta$ d\'esignent respectivement ces deux nombres, alors $\alpha$ est un nombre de Galois et $-\beta$ est son conjugu\'e.  Il s'agit donc de calculer $\alpha-\beta$.  Par ailleurs, on a $\alpha=\frac{a\alpha+b}{c\alpha+d}$, donc $c\alpha^2+(d-a)\alpha-b=0$.
Donc $\alpha-\beta=\frac{\sqrt{\triangle}}{c}$, o\`u $\triangle=(d-a)^2+4bc=d^2-2ad+a^2+4ad-4\varepsilon=(a+d)^2-4\varepsilon$.
\end{proof}

Le r\'esultat \'el\'ementaire suivant nous sera aussi bien utile.
\begin{lemma}
Si $M$ est une matrice $2\times 2$ sym\'etrique, alors la matrice 
$$N=\begin{pmatrix}5& 2\\ 2& 1\end{pmatrix}M
\begin{pmatrix}2& 1\\1& 1\end{pmatrix}$$  
satisfait \`a $3N_{21}=\mbox{tr}(N)$.
\end{lemma}

\begin{proof}
On a 
$$\begin{pmatrix}5& 2\\ 2& 1\end{pmatrix} 
\begin{pmatrix}p& q\\ q& r\end{pmatrix} 
\begin{pmatrix}2& 1\\ 1& 1\end{pmatrix} =
\begin{pmatrix}10p+9q+2r& 5p+7q+2r\\
 4p+4q+r& 2p+3q+r\hphantom{2}\end{pmatrix}$$
et la trace de cette matrice est $12p+12q+3r=3(4p+4q+r)$.
\end{proof}

\begin{proof}[Preuve du corollaire 3.1]
Comme $w\not=1,w$ commence par 2 et $W$ aussi.  La proposition montre que $M(A)=\lambda_i(A)$ avec la position $i$ indiqu\'ee.  On applique alors le lemme~3.1 avec $u=W$~: on a $M(A)=\frac{1}{c}\sqrt{(a+d)^2-4\varepsilon}$ o\`u 
$\left(\begin{smallmatrix}a& b\\ c& d\end{smallmatrix}\right)$
est l'image de $W$ par l'homomorphisme qui envoie 1 sur 
$\left(\begin{smallmatrix}1& 1\\ 1& 0\end{smallmatrix}\right)$
 et 2 sur 
$\left(\begin{smallmatrix}2& 1\\ 1& 0\end{smallmatrix}\right)$.  Mais le carr\'e de ces matrices est respectivement 
$\left(\begin{smallmatrix}2& 1\\ 1& 1\end{smallmatrix}\right)$
et
$\left(\begin{smallmatrix}5& 2\\ 2& 1\end{smallmatrix}\right)$.  Donc 
$\left(\begin{smallmatrix}a& b\\ c& d\end{smallmatrix}\right)=\mu w$.

  Mais $w=2v1$, o\`u $v$ est un palindrome.  Donc $\mu v$ est une matrice sym\'etrique puisque 
$\left(\begin{smallmatrix}2& 1\\ 1& 1\end{smallmatrix}\right)$
et
$\left(\begin{smallmatrix}5& 2\\ 2& 1\end{smallmatrix}\right)$ le sont.  Le lemme~3.2 montre qu'alors $a+d=3c$.  D'o\`u $M(A)=\frac{1}{c}\sqrt{9c^2-4}$, car $\varepsilon =1$.

Enfin, il est bien connu que le produit $(\ast)$ est \'egal \`a 
$$
\left({\begin{array}{cc}
P(x_1,\ldots,x_n)&P(x_1,\ldots,x_{n-1})\\
P(x_2,\ldots,x_n)&P(x_2,\ldots,x_{n-1})
\end{array}}\right),$$ ce qui conclut la preuve.
\end{proof}
\begin{remark}
Pour $w=1$, on obtient aussi le nombre de Markoff 1, \'egal \`a $c=\frac{1}{3}(a+d)$ pour la matrice $\mu w=$ 
$\left(\begin{smallmatrix}2& 1\\ 1& 1\end{smallmatrix}\right)$.
\end{remark}

\begin{remark}
Comme les matrices $\mu 1$ et $\mu2$ sont sym\'etriques, on a aussi $c=\frac{1}{3}\mbox{tr}(\mu\tilde{w})$, et $\tilde{w}$ est le mot de Christoffel inf\'erieur associ\'e au mot de Christoffel sup\'erieur $w$.

\end{remark}

Nous obtenons aussi un r\'esultat de Harvey Cohn \cite{C}.

\begin{corollary}
Les nombres de Markoff sont obtenus comme le tiers de la trace des matrices images des mots de Christoffel sup\'erieurs sur $\{1,2\}$ sous l'homomorphisme envoyant \emph{1} sur 
$\left(\begin{smallmatrix}1& -1\\ -1& 2\end{smallmatrix}\right)$
 et \emph{2} sur 
$\left(\begin{smallmatrix}-1& 2\\ -4& 7\end{smallmatrix}\right)$.
\end{corollary}

\begin{proof}
Avec les notations du corollaire~3.1, on a $c=\frac{1}{3}\mbox{tr}(\mu w)$, pour tout nombre de Markoff $c$ et $w$ le mot de Christoffel sup\'erieur appropri\'e. Le d\'eterminant de $\mu w$ est 1, donc $\mbox{tr}(\mu w)=\left({\mbox{tr}(\mu w)^{-1}}\right)=\mbox{tr}\; \left({^t(\mu w)^{-1}}\right)$.  Comme $A\mapsto \!\! \;^tA^{-1}$ est un automorphisme de $GL_2(\Bbb Z)$, on a que $c=\frac{1}{3}\mbox{tr} \left({\mu^\prime w}\right)$, o\`u $\mu^\prime$ envoie 1 sur 
$\left(\begin{smallmatrix}2& 1\\ 1& 1\end{smallmatrix}\right)^{-1}$
 et 2 sur 
$\left(\begin{smallmatrix}5& 2\\ 2& 1\end{smallmatrix}\right)^{-1}$.
Il suffit maintenant de remarquer que 
$\left(\begin{smallmatrix}2& 1\\ 1& 1\end{smallmatrix}\right)^{-1}=
\left(\begin{smallmatrix}\hphantom{-}1& -1\\ -1& \hphantom{-}2\end{smallmatrix}\right)$
 et que cette matrice conjugue 
$\left(\begin{smallmatrix}5& 2\\ 2& 1\end{smallmatrix}\right)^{-1}$
 et
$\left(\begin{smallmatrix}-1& 2\\ -4& 7\end{smallmatrix}\right)$~:
  on a en effet 
$\left(\begin{smallmatrix}-1& 2\\ -4& 7\end{smallmatrix}\right)=
\left(\begin{smallmatrix}2& 1\\ 1& 1\end{smallmatrix}\right)
\left(\begin{smallmatrix}5& 2\\ 2& 1\end{smallmatrix}\right)^{-1}
\left(\begin{smallmatrix}\hphantom{-}1& -1\\ -1& \hphantom{-}2\end{smallmatrix}\right)$.
\end{proof}
%=====================================
%Sous-section 3.7
%=====================================
\subsection{Spectre de Cassaigne}
Dans \cite{Ca} est consid\'er\'e l'ensemble des nombres r\'eels $\alpha=[a_0,a_1,a_2,\ldots]$ tels que $\alpha\geq[a_i,a_{i+1},a_{i+2},\ldots]$ pour tout $i\in{\Bbb N}$~; cet ensemble est lui-m\^eme li\'e \`a un ensemble de mots bi-infinis \'etudi\'e dans \cite{AC}.  Dans cet ensemble, les nombres de Galois qu'il contient sont denses (voir \cite[p.~12]{Ca}).  Par d\'efinition, ces nombres de Galois sont exactement les nombres de Galois maximums dans leur classe d'homographie.

Ces nombres sont donc ceux dont le d\'eveloppement en fraction continue est de la forme $w^\infty$, o\`u $w$ est un mot de Lyndon g\'en\'eralis\'e pour la suite d'ordre $(<_n)_{n\in{\Bbb N}}$, sur ${\Bbb P}$, avec $<_n=$ l'ordre naturel sur ${\Bbb P}$ si $n$ est impair, $=$ l'ordre oppos\'e si $n$ pair.  Ces $w$ constituent une variante des mots de Galois, en prenant l'ordre oppos\'e.
%=====================================
%Sous-section 3.8
%=====================================
\subsection{Factorisations de Viennot}
Selon \cite{L}, une {\it factorisation de Viennot\/} du mo\-no\-\"\i de libre $A^\ast$ est une factorisation compl\`ete $A^\ast=\prod\limits_{i\in I}l_i^\ast$, o\`u $I$ est totalement ordonn\'e, o\`u le produit est d\'ecroissant, et o\`u $l_i\in A^+$, avec en plus la condition suivante~: $i<j\Rightarrow\exists k$ tel que $l_il_j=l_k$.

Les mots de Lyndon usuels forment une factorisation de Viennot.  Cependant, dans cet article d\'edi\'e \`a Viennot, nous devons avouer que les mots de Galois ne forment pas une factorisation de Viennot~: par exemple $121$ et 3 sont des mots de Galois, on a $(121)^\infty <3^\infty$, mais $1213$ n'est pas un mot de Galois, puisque c'est son conjugu\'e $1312$ qui est un mot de Galois.



%
%=======================================================
%Bibilographie num\'erot\'ee
%Dans le texte, j'inscris \cite{ref1}
%=======================================================
%\bibliographystyle{plain}
%\begin{thebibliography}{4}
%\bibitem{ref1}
%R. Speicher, {\it Multiplicative functions on the lattice of non-crossing partitions and free convolution}, Annals Maths, 298, 1994, 611-628.
%\end{thebibliography}


%
%=======================================================
%Bibilographie pr\'esent\'ee avec des lettres
%Dans le texte, j'inscris \cite{A}
%=======================================================
\begin{thebibliography}{444444}

\bibitem[A]{A}
Allauzen, C., {\it Une description simple des nombres de Sturm}, Journal de Th\'eorie des Nombres de Bordeaux 10, 1998, 237--241.

\bibitem[AC]{AC}
Allouche, J.-P., Cosnard, M., {\it It\'eration de fonctions unimodales et suites engendr\'ees par automates}, Comptes Rendus de l'Acad\'emie des Sciences, Paris, S\'erie I, Math\'ematique 296, 1983, 159--162.

\bibitem[B]{B}
Bergman, G.M., {\it Centralizers in free associative algebras}, Transactions of the American Mathematical Society 137, 1969, 327--344.

\bibitem[BS]{BS}
Berstel, J., S\'e\'ebold, P., {\it Sturmian words dans~: M. Lothaire}, Algebraic Combinatorics on words, Cambridge, 2002, 45--110.

\bibitem[Bu]{Bu}
Buell, D.A., {\it Binary quadratic forms, classical theory and modern computations}, Springer Verlag, 1989.

\bibitem[C]{C}
Cohn, H., {\it Markoff forms and primitive words}, Mathematische Annalen 196, 1972, 8--22.

\bibitem[CMPS]{CMPS}
Crisp, D., Moran, W., Pollington, A., Shine, P., {\it Substitution invariant cutting sequences}, Journal de Th\'eorie des Nombres de Bordeaux 5, 1993, 123--137.

\bibitem[Ca]{Ca}
Cassaigne, J., {\it Limit values of the recurrence quotient of Sturmian sequences}, Theoretical Computer Science 218, 1999, 3--12.

\bibitem[CF]{CF}
Cusick, T.W., Flahive, M.E., {\it The Markoff and Lagrange spectra},
Amer.\ Math.\ Soc., 1989.

\bibitem[CG]{CG}
Conway, J.H., Gay, R.K., {\it The book of numbers}, Copernicus, Springer--Verlag, 1998.

\bibitem[D1]{D1}
Dickson, L.E., {\it Introduction to the theory of numbers}, Dover, 1957.

\bibitem[D2]{D2}
Dickson, L.E., {\it Studies in the theory of numbers}, Chelsea, New York 1930 (2\`eme \'ed. en 1957).

\bibitem[Du]{Du}
Duval, J.-P., {\it Factorizing words over and ordered alphabet}, Journal of Algorithms 4, 1983, 363--381.

\bibitem[F]{F}
Frobenius, G.F., {\it \"Uber die Markoffschen Zahlen}, Sitzungsberichte der K\"oniglich Preussischen Akademie der Wissenschaften zu Berlin 1913, 4\; 58--487; aussi dans~: Frobenius, G.F., {\it Gesammelte Abhandlungen}, Springer--Verlag 1968, vol.~3, 598--627, \'ed. J.-P.~Serre.

\bibitem[L]{L}
Lothaire, M., {\it Combinatorics on words}, Addison--Wesley, 1983.

\bibitem[M1]{M1}
Markoff, A.A., {\it Sur les formes quadratiques binaires ind\'efinis}, Mathematische Annalen 15, 1879, 381--496.

\bibitem[M2]{M2}
Markoff, A.A., {\it Sur les formes quadratiques binaires ind\'efinies}, Mathematische Annalen 17, 1880, 379--399.

\bibitem[Me]{Me}
Melan{\c c}on, G., {\it Combinatorics of Hall trees and Hall words}, Journal of Combinatorial Theory A, 59, 1992, 285--308.

\bibitem[R]{R}
Reutenauer, C., {\it Free Lie algebras}, Oxford University Press, 1993.

\bibitem[S]{S}
Shirshov, A.I., {\it Bases of free Lie algebras}, Algebra $i$ Logika 1, 1962, 14--19.

\bibitem[S1]{S1}
Sch\"utzenberger, M.-P., {\it Sur une propri\'et\'e combinatoire des alg\`ebres de Lie libres pouvant \^etre utilis\'ee dans un probl\`eme de math\'ematiques appliqu\'ees}, s\'eminaire P. Dubreil, Facult\'e des Sciences, Paris, 1978.

\bibitem[S2]{S2}
Sch\"utzenberger, M.-P., {\it On a factorization of free monoids}, Proceedings of the American Mathematical Society, 16, 1965, 21--24.

\bibitem[V]{V}
Viennot, X.G., {\it Alg\`ebres de Lie libres et mono\"\i des libres}, Lecture Notes in Mathematics 691, Springer.

\bibitem[Va]{Va}
Vall\'ee, B., {\it Algorithms for computing signs of $2\times 2$ determinants: dynamics and average-case analysis}, Lecture Notes in Computer Science 1284, 486--499, 1997.

\end{thebibliography}
\end{document}