<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">
%\usepackage[colorlinks=true]{hyperref}
%\usepackage{setspace}
%\newcommand{\binom}[2]{{#1 \choose #2}}

\documentclass[12pt,reqno]{article}


\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\usepackage{tikz}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\makeatletter
\newcommand{\miniscule}{\@setfontsize\miniscule{1}{2}}
\makeatother

\begin{center}
\vskip 1cm{\LARGE\bf On a Class of Lyndon Words Extending  \\
\vskip .01in
Christoffel Words and Related to a  \\
\vskip .03in
Multidimensional Continued Fraction \\
\vskip .17in
Algorithm}
\vskip 1cm
\large
Guy Melan\c{c}on\\
Labri\\  
Universit\'e de Bordeaux \\ 
351, cours de la Lib\'eration \\
33405 Talence\\ 
France \\
\href{mailto:melancon@labri.fr}{\tt melancon@labri.fr}\\
\ \\
Christophe Reutenauer\\
D\'epartement de Math\'ematiques \\
UQAM\\
Case Postale 8888, Succ.\ Centre-ville\\
Montr\'eal, Qu\'ebec H3C 3P8 \\
Canada \\
\href{mailto:Reutenauer.Christophe@uqam.ca}{\tt Reutenauer.Christophe@uqam.ca}
\end{center}

\vskip .2 in


\begin{abstract}
We define a class of Lyndon words, called {\em Christoffel-Lyndon
words}. We show that they are in bijection with $n$-tuples of
relatively prime natural numbers. We give a geometrical interpretation
of these words. They are linked to an algorithm of Euclidean type. It
admits an extension to $n$-tuples of real numbers; we show that if the
algorithm is periodic, then these real numbers are algebraic of degree
at most $n$ and that the associated multidimensional continued fraction
converges to these numbers.
\end{abstract}

\section{Introduction}
\label {introduction}

Lyndon words are defined using a simple property: they are strictly smaller than all of their nontrivial cyclic permutations, with respect to lexicographic order; equivalently, (but non-trivially) they are strictly smaller than all of their nonempty proper
right factors (suffixes), with respect to alphabetical order\footnote{In comparing cyclic permutations of a word, lexicographical order suffices; but in order to compare a word and its suffixes, 
one needs alphabetical order.}. Lyndon words can be recursively built as follows: given two Lyndon words $u &lt; v$, their product $uv$ is a Lyndon word; conversely, it can be shown that any Lyndon word, which is not a letter,  factorizes into an increasing product of two Lyndon words. 

Among factorizations of a given Lyndon word into a product of two
Lyndon words, special ones, called \emph{standard} factorizations, have
been considered in the literature\footnote{The motivation is to obtain
by iteration a complete parenthesization of the Lyndon word, that is, a
nonassociative expression; this in turn is motivated by the
construction of Lie polynomials (giving a basis of the free Lie
algebra), and of group commutators.}. One, considered by Chen-Fox-Lyndon
\cite{CFL} and Lothaire \cite{L}, takes the longest suffix which is a
Lyndon word; the other, considered by \v{S}ir\v{s}ov \cite{S} and
Viennot \cite{V}, takes the longest prefix which is a Lyndon word. We
call these two factorizations the right and left standard
factorizations. These two factorizations are distinct in general.

Christoffel words are defined using a simple geometrical property: they are words encoding integer paths with slope $p/q$, such that the region formed by the path and the line with slope $p/q$ encloses no integer points. Consequently, Christoffel words are characterized by their slope, which is a nonnegative rational number, or $\infty$. Equivalently, they are mapped bijectively on pairs $(a,b)$ of relatively prime natural numbers.

It turns out that Christoffel words are very particular Lyndon words on a two-letter alphabet: Christoffel words are those Lyndon words for which the right and left standard factorization coincide (recursively) (see Theorem \ref{Christ}); this was proved in an unpublished work by the first author \cite{M}. The present work started from a very simple idea, that of considering the unique recursive decomposition of Lyndon words over any an alphabet in a quest for generalizing Christoffel words to higher dimensions. We thus consider \emph{Christoffel-Lyndon words}, defined recursively as those Lyndon words admitting a unique standard factorization into a product of two Christoffel-Lyndon words (see Section \ref{regular}).

As said before, Christoffel words are naturally in bijection with pairs of relatively prime pairs of natural numbers. Surprisingly enough, the bijection between Christoffel words and pairs of relatively prime numbers generalizes to any alphabet (Theorem \ref{prime}); for a three-letter alphabet, this result was proved by the first author \cite{M}.

To prove this we have to generalize the classical Euclidean algorithm ($n=2$) and the Euclidean algorithm of \cite{M} ($n=3$) to arbitrary $n$-tuples of natural integers, see Section \ref{Euclidean}. Similar algorithms have been considered in the realm of multidimensional continued fractions \cite{Be,Sc}, but our algorithm seems to be new. It is a two-case algorithm, which allows us to generalize the Stern-Brocot tree ($n=2$). In one of its instances, our tree is an infinite binary tree whose vertices are all nonvanishing $(n-1)$-tuples of nonnegative rational numbers (see Figure \ref{treer} for $n=3$). 

We introduce two substitutions on $n$ letters, which for $n=2$ are classical, and for $n=3$ were considered in \cite{M}; they are automorphisms of the free group. They are related to the algorithm in that the inverses of their incidence matrix are the two operations of the algorithm. The algorithm and the substitutions are used to prove that the commutative image of words maps Christoffel-Lyndon words bijectively onto $n$-tuples of relatively prime natural numbers (Theorem \ref{prime}). One tool is a theorem of Richomme \cite{R}, that characterizes Lyndon morphisms (substitutions that preserve Lyndon words), Theorem \ref{morphism}. A consequence of the theorem is a formula allowing to count Christoffel-Lyndon words, which extends the classical one for Christoffel words (which is essentially the Euler totient function).

Christoffel words may be defined geometrically, as said before; equivalently, the Christoffel word of slope $r$ encodes a discrete path in the plane that stays below the half-line of slope $r$, but maximizes the slope at each step. We may define a multidimensional slope in a similar way; these slopes are in bijection with Christoffel-Lyndon words, and inherit the alphabetic order of the latter. We then show that then Christoffel-Lyndon words have the same geometrical interpretation, Theorem \ref{max}.

To each $n$-tuple of reals numbers $(a_1,\ldots,a_n)$, which are not of rank $1$ over $\mathbb Q$, the algorithm associates an infinite word. The finite prefixes of this word allow to compute, by a process familiar in the theory of multidimensional continued fractions, a sequence $((\alpha_1(k),\ldots,\alpha_n(k)))_{k\geq 0}$ of $n$-tuples of integers, generalizing the convergents of usual continued fractions. Guided by this classical case, one expects that, for any $i=1,\ldots,n$, the limit when $k$ tends to $\infty$ of the quotients $\alpha_i(k)/\alpha_1(k)$ is equal to $a_i/a_1$. We could prove this only in the special case where the infinite word is periodic; in this case, we also obtain that the numbers $a_i/a_1$ are in a number field of degree at most $n$, Theorem \ref{periodic}. This is of course an analogue of one implication of the Lagrange theorem for continued fractions. Our proof uses the Perron-Frobenius theory.


\section{Christoffel-Lyndon words and tuples of relatively prime natural numbers}

\subsection{Lyndon words and standard factorizations}

A {\em Lyndon word} is a word on a totally ordered alphabet which is
the smallest among all its cyclic conjugates, ordered alphabetically;
see \cite[Chapter 5]{L}. Formally, $w$ is a Lyndon word if and only if
for all nontrivial factorization $w=uv$, one has $w&lt;vu$. It is
equivalent that for each such factorization $w&lt;v$; see \cite[Prop.\ 5.1.2]{L}.

Note that each letter is a Lyndon word. Let $w$ be a Lyndon word which
is not a letter. Let $v$ be its longest proper suffix which is a Lyndon
word; we call the corresponding factorization $w=uv$ the {\em right
standard factorization} of $w$; it is known that then $u,v$ are Lyndon
words and that $u&lt;v$ (see \cite[Prop.\ 5.1.3]{L}, where it is called the
{\em standard factorization}).

Similarly, let now $u$ be the longest proper prefix of $w$ which is a Lyndon word;  we call the corrresponding factorization $w=uv$ the {\em left standard factorization} of $w$; it is known that then $u,v$ are Lyndon words and that $u&lt;v$ (see \cite[Exercise 5.1.6]{L} or \cite[p.\ 15]{V}).
 
We note that if $w$ is a Lyndon word with left or right standard factorization $w=w'w''$, then 
\begin{equation}\label{&lt;0}
w'&lt;w''.
\end{equation}

Moreover, let $w=w'w''$ be a Lyndon word written as the product of two Lyndon words. Then this factorization is the right standard factorization of $w$ if and only if Eq.~(\ref{&lt;0}) holds and if either $w'$ is a letter, or $w'$ has the right standard factorization $w'=(w')'(w')''$ with

\begin{equation}\label{&lt;''0}
(w')''\geq w''.
\end{equation}
See \cite[Prop.\ 5.1.4]{L}.

Similarly, this factorization is the left standard factorization of $w$ if and only if Eq.~(\ref{&lt;0}) holds and if either $w''$ is a letter, or if $w''$ has the left standard factorization $w''=(w'')'(w'')''$ with
\begin{equation}\label{'&lt;0}
w'\geq (w'')'.
\end{equation}
See \cite[p.\ 48]{V}.

\subsection{Lyndon morphisms}\label{morphisms}

Let $f:X^*\rightarrow Y^*$ be a monoid homomorphism, where $X,Y$ are two finite totally ordered alphabets. It is called {\em order-preserving} if $u\leq v$ implies $f(u)\leq f(v)$ for any words $u,v$ in $X^*$, where $\leq $ is the alphabetic order. Moreover, $f$ is called a {\em Lyndon morphism} if for any Lyndon word $w$ in $X^*$, $f(w)$ is a Lyndon word.

We use several results due to Gwena\"el Richomme. He shows first that
if $f$ is nonempty (that is, the image of $f$ is not the empty word of
$Y^*$) and order-preserving, then $f$ is injective 
\cite[Lemma 3.2]{R}. In particular, a nonempty order-preserving morphism sends
any letter onto some nonempty word, so that $k$ in (i) below is
well-defined.

\begin{theorem} \label{morphism}
(i) \cite[Prop.\ 3.3]{R}  A nonempty morphism $f:X^*\rightarrow Y^*$ is order-preserving if and only if for any letter $b$ in $X$, distinct from its largest letter $z$, one has: $f(bz^k)&lt;f(c)$, where $c$ is the letter next to $b$ in $X$ and where $k$ is the smallest natural number such that the length of $f(bz^k)$ is at least equal to that of $f(c)$.

(ii) \cite[Prop.\ 4.2]{R} A homomorphism $f:X^*\rightarrow Y^*$ is a Lyndon morphism if and only if it is order-preserving and if it sends each letter onto a Lyndon word.
\end{theorem}

We consider two endomorphisms of the free monoid $X^*$, with $X=\{x_1&lt;\ldots &lt;x_n\}$, $n\geq 2$. They are written $L$ and $R$ and defined as follows: 
\begin{itemize}
\item $L$ sends the $n$-tuple $(x_1,\ldots,x_n)$ onto $(x_1, x_1x_n, x_2,..., x_{n-1})$;
\item $R$ sends the $n$-tuple $(x_1,\ldots,x_n)$ onto $(x_1x_n, x_2,..., x_n)$.
\end{itemize}

\begin{corollary}\label{mstandard}
The endomorphisms $L$ and $R$ are Lyndon morphisms, which preserve left and right standard factorizations.
\end{corollary}

\begin{proof}
The fact that $L$ and $R$ are Lyndon morphisms follows by inspection from the previous theorem (for $L$ one has to distinguish the cases $n=2$ and $n\geq 3$).

Note that $x_1$ is the smallest Lyndon word and $x_n$ the largest.

Let $f=L$ or $f=R$. Suppose that $w=w'w''$ is a Lyndon word with its right standard factorization. If $w'$ is not a letter, then $w'=uv$ (right standard factorization) and we have $v\geq w''$ by Eq.~(\ref{&lt;''0}). By induction on the length of $w$, we know that $f(w')$ has the right standard factorization $f(u)f(v)$. Since $f$ is a Lyndon morphism, $f(w')&lt;f(w'')$ by Eq.~(\ref{&lt;0}) and these two words are Lyndon words; moreover, we have $f(v)\geq f(w'')$ and this implies by Eq.~(\ref{&lt;''0}) that $f(w)$ has the right standard factorization $f(w)=f(w')f(w'')$. If $w'$ is a letter, then either $f(w')$ is a letter so that we have still the same right standard factorization; or $f(w')$ is not a letter, in which case $f(w')=x_1x_n$, so that, since $x_n\geq f(w'')$, we have still the same right standard factorization.

The proof for left standard factorizations is quite similar.
\end{proof}

\subsection{Christoffel-Lyndon words}\label{regular}

We define recursively 
{\em Christoffel-Lyndon words}\footnote{They are called {\em \'equilibr\'es} in \cite{M}, and {\em balanced$_2$} in \cite{BLRS}; since the word ``balanced" has another precise meaning in classical combinatorics on words, we prefer to adopt another terminology.}: a letter is a Christoffel-Lyndon word; otherwise, a Lyndon word $w$ is a Christoffel-Lyndon word if its left and right standard factorizations coincide, say $w=uv$, and if moreover $u,v$ are both Christoffel-Lyndon words.

Note that this recursive definition cannot be replaced by the condition that only the left and right standard 
factorizations of $w$ coincide: an example of this is the word $w=aabaabb$, which satisfies the latter 
condition ($w=aab.aabb$ is its left and right standard factorization), but is not Christoffel-Lyndon, since the right factor $aabb$ does not satisfy this condition.

If $w$ is a Christoffel-Lyndon word, then we call {\em standard factorization} of $w$ its left and right standard factorization, which are identical. We write
it as $w=w'w''$. We note that
\begin{equation}\label{&lt;}
w'&lt;w''.
\end{equation}
If $w'$ is not a letter, then
\begin{equation}\label{&lt;''}
(w')''\geq w''.
\end{equation}
And if $w''$ is not a letter, then
\begin{equation}\label{'&lt;}
w'\geq (w'')'.
\end{equation}

\begin{theorem}\cite{M}\label{Christ}
On a totally ordered two-letter alphabet, Christoffel-Lyndon words and Christoffel words coincide.
\end{theorem}

\begin{lemma}\label{anb}
Let $w$ be a Christoffel-Lyndon word on the alphabet $\{a&lt;b\}$, with standard factorization $w=w'w''$. If $w'=a$, then $w=a^nb$. If $w''=b$, then $w=ab^n$.
\end{lemma}

Note that the words $a^nb$ and $ab^n$ are Christoffel-Lyndon words for any alphabet containing the letters $a,b$ with $a&lt;b$.

\begin{proof}
Suppose that $w'=a$. If $w''$ is a letter, then we must have $w''=b$ by Eq.~(\ref{&lt;}), which proves the result; if $w''$ is not a letter, since any Lyndon word is either $b$ or begins by $a$, we must have by Eq.~(\ref{'&lt;}), $(w'')'=a$; by induction, $w''=a^nb$ and we conclude the proof in this case.

Suppose that $w''=b$. Then the proof is similar, using Eq.~(\ref{&lt;''}).
\end{proof}         

\begin{proof} (of Theorem~\ref{Christ})
We show first that if $w$ is a Christoffel word written as a product of
two Lyndon words, then this factorization is unique. Indeed, since $w$
is a factor of some Sturmian sequence, so are the two Lyndon words. But
by \cite[Definition 2 and Theorem 3.2]{BdL},
a Lyndon word which is
the factor of some Sturmian sequence is a Christoffel word. Hence the
two factors are Christoffel words. Next, in \cite[Theor\`eme 1]{BL},
the authors show that each Christoffel word, which is not a letter, is
uniquely the product of two Christoffel words (also see \cite[Corollary 3.2]{BdL}).
Hence our factorization above is unique. In particular
the two standard factorizations of $w$ coincide; moreover the two
factors are Christoffel words, so are inductively Christoffel-Lyndon
words, and we conclude that $w$ is a Christoffel-Lyndon word.

Conversely, let $w$ be a Christoffel-Lyndon word on the alphabet
$\{a&lt;b\}$. We claim that $w$ is of the form $L(u)$ or $R(u)$, for some
Christoffel-Lyndon word $u$, where $L$ (resp., $R$) is the substitution
sending $(a,b)$ onto $(a,ab)$ (resp., onto $(ab,b))$.  This will imply
that each Christoffel-Lyndon word is a Christoffel word; indeed, either
$w$ is a letter, and it is is clear; or $w$ is not a letter and then,
supposing $w=L(u)$, we cannot have $u=a$, so that $u$, not being a
proper power of $a$, must have the letter $b$ and be shorter than $w$;
if $w=R(u)$ the argument is similar. By induction, $u$ is a Christoffel
word, and so is $w$, since, as is well-known (see 
\cite[Corollary 2.2]{BLRS}), $L$ and $R$ preserve Christoffel words.

We do not prove the claim here, since it is a particular case of Lemma \ref{image}, which will be proved independently.
\end{proof}

\subsection{$n$-tuples of relatively prime natural numbers}

The following result is well-known when the alphabet $X$ has 2 letters (see \cite{B,BL}), and has been 
obtained for a 3-letter alphabet in \cite{M}. Recall that the commutative image of a word $w\in X^*$, $X=\{x_1,\ldots,x_n\}$, is the $n$-tuple $(n_i)_{1\leq i\leq n}\in \mathbb N^n$, where $n_i$ is the number of occurrences of the letter $x_i$ in $w$. 

\begin{theorem}\label{prime}
Let $X$ be the totally ordered alphabet $\{x_1&lt;\cdots&lt;x_n\}$. The mapping from the set of Christoffel-Lyndon words on $X$ into $\mathbb N^n$, associating to $w$ its commutative image, is a bijection onto the set of $n$-tuples of relatively prime natural numbers.
\end{theorem}

The proof of the theorem will be done in Section \ref{proof}.

\begin{corollary}
The number of Christoffel-Lyndon words of length $l$ on an alphabet of cardinality $n$ is equal to $\sum_{d| l} \mu(d)\binom{n-1+l/d}{n-1}$.
\end{corollary}

In particular, it follows that, as is well-known, the number of Christoffel words of length 1 is 2, and when $l&gt;1$, it is $\phi(l)$, the number of integers $i$, relatively prime to $l$, with $1\leq i\leq l$. Indeed, 
$\phi(d)=\sum_{d| l}\mu(d)l/d=\sum_{d| l}\mu(d)(1+l/d)=\sum_{d| l} \mu(d)\binom{1+l/d}{1}$; the first equality is well-known, and the second follows from $\sum_{d| l}\mu(d)=0$.


\begin{proof}
Let $m_l$ denote this number. By Theorem~\ref{prime} it is equal to the number of $n$-tuples of relatively prime natural numbers of sum $l$. By adding 1 to each component, we see that the number of $n$-tuples of natural numbers and of sum $l$ is equal to the number of compositions\footnote{A {\em composition} is a tuple of positive integers; compositions of length $n$ and of sum $k$ are in bijection with subsets of $\{1,\ldots,k-1\}$ of cardinality $n-1$.} of length $n$ and of sum $l+n$. It is well-known that this number is equal to $\binom{l+n-1}{n-1}$. An $n$-tuple of natural numbers of sum $l$ has a gcd $d$, which is a divisor of $l$. Hence, we obtain
$$
\binom{l+n-1}{n-1} = \sum_{d| l} m_{l/d}=\sum_{d| l} m_{d}.
$$
By M\"obius inversion, we obtain the corollary.
\end{proof}

For example, for an alphabet of cardinality 3, we have the following values of $m_l$, for $l=1,\ldots,10$: 3,3,7,9,18,15,33,30,45,42. The corresponding Christoffel-Lyndon words on the alphabet $\{x&lt;y&lt;z\}$ are, up to length 4, $$x,y,z,xy,xz,yz,xxy,xxz,xyy,xzy,xzz,yyz,yzz,$$$$xxxy,xxxz,xyxz,xyyy,xzyy,xzzy,xzzz,yyyz,yzzz.$$

\subsection{An Euclidean algorithm for $n$-tuples of natural numbers}\label{Euclidean}
We assume that $n\geq 2$.
We define a deterministic rewriting system on the set of $n$-tuples of real numbers by the following two rules:
\begin{itemize}
\item Rule $L$: if $a_1&gt;a_n$, $(a_1,\ldots,a_n)\rightarrow_L (a_1-a_n,a_n,a_2,\ldots,a_{n-1})$;
\item Rule $R$: if $a_1\leq a_n$, $(a_1,\ldots,a_n)\rightarrow_R (a_1,\ldots,a_{n-1},a_n-a_1)$.
\end{itemize}

\begin{lemma}\label{rewriting}
Suppose that $(a_1,\ldots,a_n)$ is an $n$-tuple of natural numbers with $a_1&gt;0$. Let $d$ be their greatest common divisor. Then the rewriting system produces the final $n$-tuple $(d,0,\ldots,0)$. If moreover $a_i&gt;0$ for at least one $i\in\{2,\ldots,n\}$, then the $n$-tuple obtained just before the first occurrence of $(d,0,\ldots,0)$ in the rewriting system is $(d,0,\ldots,0,d)$. 
\end{lemma}
Note that the rewriting system stabilizes on the $n$-tuple $(d,0,\ldots,0)$, since only rule $L$ can be applied to it.
\begin{proof}
In the rewriting system, note that if the first component of an $n$-tuple is positive, it remains positive. This implies that applying rule $R$ always decreases the sum of the $n$-tuple. Moreover, if $(a_1,\ldots,a_n)\neq (a_1,0,\ldots,0)$, and if rule $L$ is applied, then it is applied several times until the sum decreases (the exact number of times being $n+1-max\{i,a_i\neq 0\}$). This proves the first assertion, since the gcd never changes.

Now suppose that  $a_i&gt;0$ for at least one $i\in\{2,\ldots,n\}$. Let $(b_1,\ldots,b_n)$ be the $n$-tuple preceding $(d,0,\ldots,0)$ in the rewriting system. If we had $(b_1,\ldots,b_n)\rightarrow_L(d,0,\ldots,0)$, then $(b_1-b_n,b_n,b_2,\ldots,b_{n-1})=(d,0,\ldots,0)$, so that $(b_1,\ldots,b_n)=(d,0,\ldots,0)$, which contradicts the assumption of the lemma.
Thus we have $(b_1,\ldots,b_n)\rightarrow_R(d,0,\ldots,0)$, so that $(b_1,\ldots,b_{n-1},b_n-b_1)=(d,0,\ldots,0)$. Thus $b_1=d$, $b_2=\ldots =b_{n-1}=0$ and $b_n=d$, which proves the lemma.
\end{proof}

\subsection{Two substitutions}
We consider the two endomorphisms $L,R$ of the free monoid $\{x_1&lt;\cdots &lt;x_n\}^*$ introduced in Section \ref{morphisms}.

These two substitutions are related to the rewriting system of the previous section. In order to see this, given a word $W$ in the free monoid generated by $L$ and $R$, we let $W$ denote the substitution which is the corresponding composition of the substitutions $L$ and $R$; for example, $LR$ denotes the mapping $L\circ R$ with $LR(x_1)=L(x_1x_n)=x_1x_{n-1}$, whereas $RL$ maps $x_1$ onto $RL(x_1)=R(x_1)=x_1x_n$. 

For an $n$-tuple $(a_1,\ldots,a_n)$ of real numbers, we write $(a_1,\ldots,a_n)\rightarrow_W (b_1,\ldots,b_n)$ if $(b_1,\ldots,b_n)$ is the $n$-tuple of real numbers obtained by applying the rewriting rules detemined by $W$, by taking the letters of $W$ from left to right; for example, $(a_1,\ldots,a_n)\rightarrow_{LR} (b_1,\ldots,b_n)$ means $(a_1,\ldots,a_n)\rightarrow_L (c_1,\ldots,c_n) \rightarrow_{R} (b_1,\ldots,b_n)$, so that $(c_1,\ldots,c_n)=(a_1-a_n,a_n,a_2,\ldots,a_{n-1})$ and $(b_1,\ldots,b_n)=(c_1,\ldots,c_{n-1},c_n-c_1)=(a_1-a_n,a_n,a_2,\ldots,a_{n-2},a_{n-1}-a_1+a_n)$.

\begin{lemma} \label{letters}
Let $W\in\{L,R\}^*$ and $u,v \in\{x_1,\ldots,x_n\}^*$ be such that $v=W(u)$ and $|u|_{x_1}&gt;0$. Then $(| v|_{x_1},\ldots,| v|_{x_n})\rightarrow_W (| u|_{x_1},\ldots,| u|_{x_n})$.
\end{lemma}

\begin{proof}
It is easy to see that if $x_1$ appears in a word, then it also appears in the image of $L,R$, and hence of any of their products.

We prove the lemma by induction on the length of the word $W$. If $W$ is the empty word, there is nothing to prove. Suppose that $W=TW'$, where $T=L$ or $R$. Define $v'=W'(u)$. Then by induction $(| v'|_{x_1},\ldots,| v'|_{x_n})\rightarrow_{W'} (| u|_{x_1},\ldots,| u|_{x_n})$. 

Thus it remains to show that $(| v|_{x_1},\ldots,| v|_{x_n})\rightarrow_T (| v'|_{x_1},\ldots,| v'|_{x_n})$. 
We have $v=W(u)=T(W'(u))=T(v')$. Suppose that $T=L$. Then by definition of $L$, $| v|_{x_1}=| v'|_{x_1}+| v'|_{x_2}$, $| v|_{x_2}=| v'|_{x_3}$,....,$| v|_{x_{n-1}}=| v'|_{x_n}$, $| v|_{x_n}=| v'|_{x_2}$. Thus, one obtains that $(| v|_{x_1},\ldots,| v|_{x_n})\rightarrow_L (| v'|_{x_1},\ldots,| v'|_{x_n})$, since $| v|_{x_1}&gt;| v|_{x_n}$, because $| v'|_{x_1}&gt;0$.

Similarly, if $T=R$, then $| v|_{x_i}=| v'|_{x_i}$ for $i=1,\ldots, n-1$ and $| v|_{x_n}=| v'|_{x_1}+| v'|_{x_n}$. Hence $(| v|_{x_1},\ldots,| v|_{x_n})\rightarrow_R (| v'|_{x_1},\ldots,| v'|_{x_n})$ since $| v|_{x_1}=| v'|_{x_1}\leq| v|_{x_n}$.

\end{proof}

\begin{lemma}\label{send}
The substitutions $L$ and $R$ send Christoffel-Lyndon words onto Christoffel-Lyndon words and preserve the standard factorization. Moreover they preserve also Christoffel-Lyndon words by inverse image.
\end{lemma}

\begin{proof}
By Corollary \ref{mstandard}, these two substitutions are Lyndon morphisms. They send each letter onto a Christoffel-Lyndon word, as is easily checked. If $w=w'w''$ is a Christoffel-Lyndon word with its standard factorization, then, for $f=L$ or $R$, the Lyndon word $f(w)$ has the left and right standard factorization $f(w')f(w'')$, by Corollary \ref{mstandard}; hence $f(w)$ is a Christoffel-Lyndon word by induction on the length. 

Now, suppose that $f(w)$ is a Christoffel-Lyndon word. Let $w=uv$ be a nontrivial factorization. Since $f$ is injective, $f(w)=f(u)f(v)$ is a nontrivial factorization. Thus $f(w)&lt;f(v)f(u)=f(vu)$ and we conclude that $w&lt;vu$ since $f$ is order-preserving and the order is total. Thus $w$ is a Lyndon word.
It remains to prove that it is a Christoffel-Lyndon word. Let $w=w'w''$ be its left or right standard factorization. Then $f(w)=f(w')f(w'')$ is the standard factorization of $f(w)$ since the latter is a Christoffel-Lyndon word and since $f$ preserves left and right standard factorizations. Thus the left and right standard factorization of $w$ coincide. Since $w'$ and $w''$ are shorter than $w$, we conclude by induction that $w$ is a Christoffel-Lyndon word, because $f(w')$ and $f(w'')$ are Christoffel-Lyndon words.
\end{proof}

\begin{lemma} \label{image}
Let $w$ be a Christoffel-Lyndon word on the alphabet $\{x_1&lt;\cdots&lt;x_n\}$. 

(i) Then $w$ is in the image of either $L$ or $R$. 

(ii) If $w$ contains the letter $x_1$ and at least another letter, then there exists $W\in \{L,R\}^*$ such that $w=W(x_1x_n)$.
\end{lemma}

Note that we have $n\geq 2$.

\begin{proof}
We use several simple facts, which are easily established, using the fact that the image of $L$ (resp., $R$) is the submonoid generated by $x_1x_n$ and the letters $x_i$, $i=1,\ldots,n-1$ (resp., $i=2,\ldots,n$):
\begin{itemize}
\item Each letter $\neq x_n$ is in the image of $L$;
\item Each letter $\neq x_1$ is in the image of $R$;
\item If $x_1$ does not appear in $u$, then $L(u)$ is in the image of $R$ (since $L$ maps $\{x_2,\ldots,x_n\}$ into $\{x_1x_n,x_2,\ldots,x_{n-1}\})$.
\end{itemize}
(i) If $w$ is a letter, $w$ is clearly in the image of $L$ or $R$. 

Suppose that $w$ has the standard factorization $w=w'w''$. 
By induction on the length, $w',w''$ are in the image of $L$ or $R$. It is enough to show that they are image of the same substitution $R$ or $L$. So we have only to consider the two cases A. and B. below. We use the fact that $L$ and $R$ preserve the standard factorization.

\noindent A. $w'=L(u)$ and $w''=R(v)$. We have several cases and subcases.

Case 1: $x_1$ appears in $v$. 

1.1: $v=x_1$. Then $w''=x_1x_n$, hence $w''=L(x_2)$ and we are done. 

1.2: $v$ begins by $x_1$ and has length at least 2. Then $v'$ begins by $x_1$, so that $(w'')'$ begins by $x_1x_n$. 

1.2.1: $x_1$ appears in $u$. Then either $u=x_1$ and $w'=x_1$; or $u$ begins by $x_1x_i$, $i=1,\ldots,n$ and then $w'$ begins by $x_1x_j$, $j=1,\ldots,n-1$; in both cases $w'&lt;(w'')'$, contradicting Eq.~(\ref{'&lt;}). 

1.2.2: $x_1$ does not appear in $u$, so that $w'$ is in the image of $R$ and we are done.

Case 2: $x_1$ does not appear in $v$. Thus $v=w''$ is in the free monoid generated by $x_2,\ldots,x_n$.

2.1: $x_1$ does not appear in $u$. Then $L(u)$ is in the image of $R$ and we are done. 

2.2: $x_1$ appears in $u$. Thus $w'$ begins by $x_1$.

2.2.1: $w''$ is of length $&gt;1$, then $(w'')'$ begins by $x_i$, $i=2,\ldots,n$; thus $w'&lt;(w'')'$, contradicting  Eq.~(\ref{'&lt;}). 

2.2.2: $w''$ is a letter.

2.2.2.1: $w''\neq x_n$. Then $w''$ is in the image of $L$ and we are done. 

2.2.2.2: $w''=x_n$. 

2.2.2.2.1: $w'$ is not a letter. Then $(w')''$ begins by $x_i$, $i=1,\ldots, n-1$: indeed, $u$ is not a letter, otherwise, since $w'=L(u)$ is not a letter, we must have $u=x_2$, contradicting the fact that $x_1$ appears in $u$; then $u''$ begins by some letter $x_1,\ldots,x_n$, so that $(w')''=L(u'')$ begins by $x_1,\ldots,x_{n-1}$.
Therefore $(w')''&lt;w''$ and we reach a contradiction with Eq.~(\ref{&lt;''}).

2.2.2.2.2: $w'$ is a letter. Then $w'=x_1$ (since $w'=L(u)$ and $x_1$ appears in $u$) and $w=w'w''=x_1x_n$ is in the image of $L$.

\noindent B. $w'=R(u)$ and $w''=L(v)$. 

Case 1: $x_1$ appears in $v$. 

1.1: $v$ is not a letter. Then $v$ begins by $x_1x_i$, $i=1,\ldots,n$, so that $w''$ begins by $x_1x_i$, $i=1,\ldots,n-1$; since $w'$ begins by $x_1x_n$ or $x_j$, $j=2,\ldots,n$, we have $w''&lt;w'$, a contradiction with Eq.~(\ref{&lt;}). 

1.2: $v$ is a letter. Then $v=x_1$; in this case $w''=x_1\leq w'$, a contradiction again. 

Case 2: $x_1$ does not appear in $v$. Then $w''$ is in the image of $R$.

\noindent (ii) We know that $w=R(u)$ or $w=L(u)$.

Case 1: $w=R(u)$. Since $w$ contains $x_1$, $u$ contains $x_1$.

1.1: $u=x_1$. Then $w=x_1x_n$ and we are done.

1.2: $u\neq x_1$. Since $u$ is not a nontrivial power of $x_1$ (otherwise $w$ is not a Lyndon word), $u$ contains another letter, and we conclude by induction on the length, because $u$ is shorter than $w$ and $u$ is a Christoffel-Lyndon word by Lemma \ref{send}.

Case 2: $w=L(u)$. 

2.1: $u$ does not contain $x_1$. Then $w$ is in the image of $R$, which takes us to Case 1. 

2.2: $u$ contains $x_1$. Since $w\neq x_1$, $u$ contains another letter. 

2.2.1: $u$ contains $x_2$. Then $u$ is shorter than $w$, and we conclude by induction. 

2.2.2: $u$ does not contain $x_2$. Let $i$ be maximum such that $x_i$ appears in $u$. Then $u\in \{x_1,x_3,\ldots,x_i\}^*$, hence $u=L^{n-i}(v)$ with $v\in \{x_1,x_{3+n-i},\ldots,x_n\}^*$ and $x_1,x_n$ appear in $v$. 

2.2.2.1: $v=x_1x_n$. Then $w=L^{1+n-i}(x_1x_n)$ and we are done. 

2.2.2.2: $v=R(m)$ and we are done by Case 1.

2.2.2.3: $v=L(m)$ and $v\notin Im(R)$. Then $x_1$ appears in $m$ (otherwise $v$ is in the image of $R$) and $x_2$ appears in $m$, since $x_n$ appears in $v$; then by Case 2.2.1, $m=W(x_1x_n)$ for some $W\in \{L,R\}^*$, thus $w=L^{1+n-i}W(x_1x_n)$ and we are done.
\end{proof}

\subsection{Proof of Theorem \ref{prime}}\label{proof}

Consider the set $\mathbb T_n$ of $n$-tuples $(a_1,\ldots, a_n)$ of relatively prime natural numbers such that $a_1&gt;0$ and that $a_i&gt;0$ for some $i=2,\ldots ,n$. It is enough (by induction on $n$) to define a bijection from $\mathbb T_n$ onto the set of Christoffel-Lyndon words $w$ containing the letter $x_1$ and at least another letter, such that if $w$ corresponds to $(a_1,\ldots, a_n)$, then $| w|_{x_i}=a_i$. This bijection will be described by an algorithm. 

The algorithm takes as input an $n$-tuple in $\mathbb T_n$ and outputs a Christoffel-Lyndon word $w$ as above; this defines the mapping and shows that it is injective. Then we show that, for any Christoffel-Lyndon word $w$ containing the letter $x_1$ and at least another letter, to the input $(a_1,\ldots, a_n)$ with $a_i=| w|_{x_i}$ corresponds the output $w$ itself. This shows that the mapping is surjective.

The algorithm is the rewriting system of Section \ref{Euclidean}. It takes as input an $n$-tuple $t=(a_1,\ldots, a_n)$ in $\mathbb T_n$; by Lemma \ref{rewriting}, there exists a unique $W\in \{L,R\}^*$ such that $t\rightarrow_W (1,0,\ldots 0,1)$ and we define $w=W(x_1x_n)$. Then by Lemma \ref{letters}, we have $(| w|_{x_1},\ldots,| w|_{x_n})\rightarrow_W (1,0,\ldots 0,1)$. Now, the rewriting system is clearly reversible (in the sense that $t\rightarrow_W u$ and $t'\rightarrow_W u$ imply $t=t'$, see Lemma \ref{matrix relation}, which will be proved independently), so that we must have $t=(| w|_{x_1},\ldots,| w|_{x_n})$. Furthermore, $x_1x_n$ is a Christoffel-Lyndon word, and so is $w$ too, by Lemma \ref{send}.

Consider now any Christoffel-Lyndon word containing the letter $x_1$ and at least another letter. Then by Lemma \ref{image}, there exists $W\in \{L,R\}^*$ such that $W(x_1x_n)=w$. Then, as above, $(| w|_{x_1},\ldots,| w|_{x_n})\rightarrow_W (1,0,\ldots 0,1)$, which shows that the algorithm outputs $w$ on the input $(| w|_{x_1},\ldots,| w|_{x_n})$.

\subsection{Trees}

The previous section shows that the five infinite binary trees which are defined below are essentially identical.

First, we define the tree whose nodes are the words in $L$ and $R$, in such a way that this word indicates the path from the root to the node, with $L=$ ``left" and $R=$ ``right". See Figure \ref{LRword}, where $n=3$, as in the three other figures, where the alphabet is $\{a&lt;b&lt;c\}$.

\begin{figure}
\centering
\begin{tikzpicture}[
	scale=1, transform shape,
	level distance=10mm,
	level 1/.style={sibling distance=50mm},
	level 2/.style={sibling distance=25mm},
	level 3/.style={sibling distance=12.5mm}
]
 \node {I}
 	child {
		node {L}
		child {
			node{LL}
			child {node {LLL}}
			child {node{LLR}}
		}
		child {
			node {LR}
			child {node{LRL}}
			child {node{LRR}}
		}
 	}
 	child {
		node {R}
		child {
			node{RL}
			child {node {RLL}}
			child {node{RLR}}
		}
		child {
			node {RR}
			child {node{RRL}}
			child {node{RRR}}
		}
 	}
;
\end{tikzpicture}
\caption{The tree of $L,R$-words}\label{LRword}
\end{figure}


The second tree is obtained from the latter by interpreting each word $W\in\{L,R\}^*$ as the corresponding product of the substitutions $L,R$, written as the $n$-tuple $(W(x_1),\ldots, W(x_n))$. We call this tree the {\em tree of standard $n$-tuples}; see Figure \ref{standard}. This tree generalizes the {\em Christoffel tree} of \cite[p.\ 200]{BdL}, in the case $n=2$. Moreover, it has been defined for $n=3$ in \cite{M}. 

\begin{figure}
\centering
\begin{tikzpicture}[
	scale=1, transform shape,
	level distance=10mm,
	level 1/.style={sibling distance=60mm},
	level 2/.style={sibling distance=30mm},
	level 3/.style={sibling distance=15mm,font=\footnotesize}
]
 \node {$a,b,c$}
 	child {
		node {$a,ac,b$}
		child {
			node{$a,ab,ac$}
			child {node {$a,a^2c,ab$}}
			child {node{$a^2c,ab,ac$}}
		}
		child {
			node {$ab,ac,b$}
			child {node{$ab,ab^2,ac$}}
			child {node{$ab^2,ac,b$}}
		}
 	}
 	child {
		node {$ac,b,c$}
		child {
			node{$ac,ac^2,b$}
			child {node {$ac,acb,ac^2$}}
			child {node{$acb,ac^2,b$}}
		}
		child {
			node {$ac^2,b,c$}
			child {node{$ac^2,ac^3,b$}}
			child {node{$ac^3,b,c$}}
		}
 	}
;
\end{tikzpicture}
\caption{The tree of standard triples}\label{standard}
\end{figure}


The third tree is obtained from the latter by replacing each $n$-tuple $(w_1,\ldots,w_n)$ by the word $w_1w_n=W(x_1x_n)$, which is a Christoffel-Lyndon word. We call this tree the {\em tree of Christoffel-Lyndon words}. See Figure \ref{treeL}, where dotted edges have been added for later use. 

\begin{figure}
\centering
\begin{tikzpicture}[
	scale=0.8, transform shape,
	every node/.style={anchor=south},
	level distance=10mm,
	level 1/.style={sibling distance=80mm},
	level 2/.style={sibling distance=40mm},
	level 3/.style={sibling distance=20mm,font=\footnotesize},
	level 4/.style={sibling distance=10mm,font=\miniscule}
]
 \node (ac) {$ac$}
 	child {
		node {$ab$}
		child {
			node{$a^2c$}
			child {node {$a^2b$}
				child { node{$a^3c$}}
				child { node{$a^2bab$}}
			}
			child {node{$a^2cac$}
				child { node{$a^2cab$}}
				child { node{$a^2cacac$}}
			}
		}
		child {
			node {$ab^2$}
			child {node{$abac$}
				child { node{$abab^2$}}
				child { node{$abacac$}}
			}
			child {node{$ab^3$}
				child { node{$ab^2ac$}}
				child { node{$ab^4$}}
			}
		}
 	}
 	child {
		node {$ac^2$}
		child {
			node{$acb$}
			child {node {$acac^2$}
				child { node{$acacb$}}
				child { node{$acac^2ac^2$}}
			}
			child {node{$acb^2$}
				child { node{$acbac^2$}}
				child { node{$acb^3$}}
			}
		}
		child {
			node {$ac^3$}
			child {node{$ac^2b$}
				child { node{$ac^2ac^3$}}
				child { node{$ac^2b^2$}}
			}
			child {node{$ac^4$}
				child { node{$ac^3b$}}
				child { node{$ac^5$}}
			}
		}
 	}
;
\node[minimum size=3mm,
	every node/.style={anchor=south},
	] at (ac) {}
	child[dotted,grow=north west]{
		node {$a$}
	}
	child[dotted, grow=north east]{
		node {$b$}
		child[dotted] { node {$c$}}
	}
;
\end{tikzpicture}
\caption{The tree of Christoffel-Lyndon words}\label{treeL}
\end{figure}

The fourth tree is obtained by replacing in the latter each word $w$ by the $n$-tuple $(|w|_{x_1},\ldots,|w|_{x_n})$. We call this tree the {\em tree of $n$-tuples}; see Figure \ref{treet}. It generalizes the Stern-Brocot tree. Note that $\mathbb T_n$ is the set of nodes of this tree.

\begin{figure}
\centering
\begin{tikzpicture}[
	scale=0.8, transform shape,
	every node/.style={anchor=south},
	level distance=10mm,
	level 1/.style={sibling distance=80mm},
	level 2/.style={sibling distance=40mm},
	level 3/.style={sibling distance=20mm,font=\footnotesize},
	level 4/.style={sibling distance=10mm,font=\miniscule}
]
 \node (ac) {$1,0,1$}
 	child {
		node {$1,1,0$}
		child {
			node{$2,0,1$}
			child {node {$2,1,0$}
				child { node{$3,0,1$}}
				child { node{$3,2,0$}}
			}
			child {node{$3,0,2$}
				child { node{$3,1,1$}}
				child { node{$4,0,3$}}
			}
		}
		child {
			node {$1,2,0$}
			child {node{$2,1,1$}
				child { node{$2,3,0$}}
				child { node{$3,1,2$}}
			}
			child {node{$1,3,0$}
				child { node{$2,2,1$}}
				child { node{$1,4,0$}}
			}
		}
 	}
 	child {
		node {$1,0,2$}
		child {
			node{$1,1,1$}
			child {node {$2,0,3$}
				child { node{$2,1,2$}}
				child { node{$3,0,5$}}
			}
			child {node{$1,2,1$}
				child { node{$2,1,3$}}
				child { node{$1,3,1$}}
			}
		}
		child {
			node {$1,0,3$}
			child {node{$1,1,2$}
				child { node{$2,0,5$}}
				child { node{$1,2,2$}}
			}
			child {node{$1,0,4$}
				child { node{$1,1,3$}}
				child { node{$1,0,5$}}
			}
		}
 	}
;
\node[minimum size=3mm,
	every node/.style={anchor=south},
	] at (ac) {}
	child[dotted,grow=north west]{
		node {1,0,0}
	}
	child[dotted, grow=north east]{
		node {0,1,0}
		child[dotted] { node {0,0,1}}
	}
;
\end{tikzpicture}
\caption{The tree of $3$-tuples}\label{treet}
\end{figure}

The fifth tree may be called a generalized Stern-Brocot tree, since it has as vertices all nonvanishing $(n-1)$-tuples of nonnegative rational numbers. It is obtained from the tree of $n$-tuples by replacing each $(a_1,\ldots,a_n)$ by $(a_2/a_1,\ldots,a_n/a_1)$; see Figure \ref{treer} for the case $n=3$.

\begin{figure}
\centering
\begin{tikzpicture}[
	scale=0.8, transform shape,
	every node/.style={anchor=south},
	level distance=10mm,
	level 1/.style={sibling distance=80mm},
	level 2/.style={sibling distance=40mm},
	level 3/.style={sibling distance=20mm,font=\footnotesize},
	level 4/.style={sibling distance=10mm,font=\miniscule}
]
 \node (ac) {$0,1$}
 	child {
		node {$1,0$}
		child {
			node{$0,1/2$}
			child {node {$1/2,0$}
				child { node{$0,1/3$}}
				child { node{$2/3,0$}}
			}
			child {node{$0,2/3$}
				child { node{$1/3,1/3$}}
				child { node{$0,3/4$}}
			}
		}
		child {
			node {$2,0$}
			child {node{$1/2,1/2$}
				child { node{$3/2,0$}}
				child { node{$1/3,2/3$}}
			}
			child {node{$3,0$}
				child { node{$1,1/2$}}
				child { node{$4,0$}}
			}
		}
 	}
 	child {
		node {$0,2$}
		child {
			node{$1,1$}
			child {node {$0,3/2$}
				child { node{$1/2,1$}}
				child { node{$0,5/3$}}
			}
			child {node{$2,1$}
				child { node{$1/2,3/2$}}
				child { node{$3,1$}}
			}
		}
		child {
			node {$0,3$}
			child {node{$1,2$}
				child { node{$0,5/2$}}
				child { node{$2,2$}}
			}
			child {node{$0,4$}
				child { node{$1,3$}}
				child { node{$0,5$}}
			}
		}
 	}
;
\end{tikzpicture}
\caption{The generalized Stern-Brocot tree for nonvanishing pairs of nonnegative rational numbers}\label{treer}
\end{figure}


Consider the same node in these trees, with labels $W$, $w$ and $t$ in,
respectively, the first, third and fourth trees. Then we remark that
$W(x_1x_n)=w$ and $t\rightarrow_W (1,0,\ldots,0,1)$; this follows
indeed from the previous section.

Given a node $N$ in any such tree, let the path from the root to $N$ be
$W=UV$ with $V=LR^{i_1}LR^{i_2}\cdots LR^{i_k}$. Let $N'$ be the node
attained after $U$ on this path. Then $N'$ is called the {\em upward
$k$-th right node from $N$}.
Note that in going upwards, ``left" and ``right" turns are
interchanged with respect to downward paths, which explains the form
of $V$ above. Similarly, we define the {\em upward $k$-th left node
from $N$}.


For example, in the tree of Christoffel-Lyndon words (Figure \ref{treeL}) with $n=3$, the node $abacac$ has $abac$ as first upward left node and $ac$ as second upward right node.

By abuse of notation, the path may go higher than the root, by using the dotted edges of Figure \ref{treeL} or \ref{treet}. As an example, the node $acb$ has $ac$ as first upward left node and $b$ as second upward right node. 

We have not yet formally defined the supplementary vertices and the dotted edges for general $n$ and do it as follows: in the tree of Christoffel-Lyndon words, there is one vertex $x_1$ north-west of the root, and north-east, the vertices are successively $x_2,\ldots,x_n$. For the tree of $n$-tuples, each $x_i$ is replaced by $e_i$, the canonical basis element. The case $n=3$ in the figures may explain these definitions.

\begin{proposition} Let the alphabet be $\{x_1,\ldots, x_n\}$.
Each Christoffel-Lyndon word $w$ on the tree of Christoffel-Lyndon words has the standard factorization $w=uv$, where $u$ is the upward first left node from $w$ and $v$ is the upward $n-1$-th right node from $w$.
\end{proposition}

As an example, see Figure \ref{treeL}: the word $abacac$ has the standard factorization $abac.ac$ and $acb$ has the standard factorization $ac.b$.

The following consequence is then immediate. It extends a classical property of the Stern-Brocot tree \cite{GKP,BLRS} (case $n=2$) and is from \cite{M} for $n=3$.
 
\begin{corollary}
Each $n$-tuple $t$ on the tree of $n$-tuples is the sum of the upward first left $n$-tuple from $t$ and of the upward $(n-1)$-th right $n$-tuple from $t$.
\end{corollary} 

As an example with $n=3$, on Figure \ref{treet}, the node $2,2,1$ is the sum of the nodes $1,2,0$ and of $1,0,1$. And $1,4,0$ is the sum of $1,3,0$ and of $0,1,0$.

\begin{lemma}\label{calcul}
Let $0\leq j\leq n-1$. Then $LR^{i_{j}}\cdots LR^{i_2}LR^{i_1}(x_n)=x_{n-j}$ if $j&lt;n-1$, and $=x_1x_n$ if $j=n-1$.
\end{lemma}

\begin{proof} 
This follows since $R$ fixes $x_2,\ldots, x_n$, since $L(x_k)=x_{k-1}$ for $k=3,\ldots,n$ and since $L(x_2)=x_1x_n$.
\end{proof}

\begin{proof} (of the Proposition)
Let $W\in\{L,R\}^*$ be the word downwards from the root corresponding to $w$ on the tree of Christoffel-Lyndon words. Then by construction of the tree, $w=W(x_1x_n)$ and by Corollary \ref{mstandard}, $w$ has the standard factorization $w=W(x_1)W(x_n)$. We have to show that $W(x_1)=u$ and $W(x_n)=v$.

Then either $W$ contains the letter $R$, in which case $W=URL^i$, with 
$U\in \{L,R\}^*$; or $W=L^i$.

In the first case, the word downwards from the root corresponding to $u$ is $U$ (so that $U(x_1x_n)=u$) and we have $W(x_1)=URL^i(x_1)=UR(x_1)=U(x_1x_n)=u$. In the second case, $u=x_1$ and $W(x_1)=L^i(x_1)=x_1=u$. This proves the assertion for $u$.
 
Now, either W has the letter $L$ at least $n-1$ times or only $j&lt;n-1$ times. In the first case, we may write $W=VLR^{i_{n-1}}\cdots LR^{i_2}LR^{i_1}$ and $V$ is the word downwards from the root corresponding to $v$ (so that $V(x_1x_n)=v$); in the second case, we have $W=LR^{i_{j}}\cdots LR^{i_2}LR^{i_1}$ and $v=x_{n-j}$. Thus in the first case, by Lemma \ref{calcul}, $W(x_n)=V(x_1x_n)=v$. And in the second case, by the lemma, $W(x_n)=x_{n-j}=v$.
\end{proof}

 
\section{The order on tuples and a geometrical interpretation}\label{GEOM}
The motivation of this section goes as follows. The alphabetical order of Christoffel words is equivalent to the order of their slopes \cite{B,BL}, where the {\em slope} of a Christoffel word $w$ on the alphabet $\{x&lt;y\}$ is by definition the quotient $|w|_y/|w|_x$. Moreover, Christoffel words have a geometrical interpretation; an example is given in Figure \ref{path}.
The discrete path coded by $w$ is obtained step by step, starting from the origin, by maximizing the slope but staying under the slope of $w$. 
\begin{center}
\begin{figure}
[!ht]
{\centering
\includegraphics[width=2.3in]{figure.eps}
\caption{the Christoffel word $xxxyxxyxxy$ of slope 3/7}
\label{path}
}
\end{figure}
\end{center}

\subsection{The order on tuples}

We begin by a result on the ordering of Christoffel-Lyndon words.

\begin{lemma} \label{descrip-order} Let the alphabet be $\{x_1,\ldots,x_n\}$.

(i) Let $u,v$ be Christoffel-Lyndon words containing the letter $x_1$ and of length at least 2. Then $L(u)&lt;x_1x_n&lt;R(v)$.

(ii) Let $W,U,V\in \{L,R\}^*$. Then $WLU(x_1x_n)&lt;W(x_1x_n)&lt;WRV(x_1x_n)$.
\end{lemma}

\begin{proof} (i) We have $u=x_1x_i\cdots$, so that $L(u)=x_1x_j$ with $j&lt;n$. Thus $L(u)&lt;x_1x_n$. Moreover, $v=x_1x_k\cdots$, so that $R(v)=x_1x_nR(x_k)\cdots &gt;x_1x_n$.

(ii) Let $u=U(x_1x_n), v=V(x_1x_n)$. Then by Lemma \ref{send}, $u,v$ are Christoffel-Lyndon words; they both contain the letter $x_1$ and are of length at least 2. Thus by (i), $LU(x_1x_n)&lt;x_1x_n&lt;RV(x_1x_n)$. Thus (ii) follows, since $W$ is order-preserving by Corollary \ref{mstandard}.

\end{proof}

We order tuples of relatively prime natural numbers according to the alphabetical order of their associated Christoffel-Lyndon word; this is well-defined by Theorem \ref{prime}. 
The lemma implies the following result, which completely describes the order on $\mathbb T_n$.

\begin{proposition}\label{description-order} Let $t_1,t_2$ be two $n$-tuples on the tree of $n$-tuples and let $t$ be their first common ancestor; the following conditions are equivalent:

(i) $t_1\leq t_2$;

(ii) $t_1$ is in the left subtree under $t$ or equal to $t$, and $t_2$ is in the right subtree under $t$ or equal to $t$.

(iii) one of the two following conditions holds:
\begin{itemize}
\item
rule $L$ is applicable to $t_1$ or $t_1=(1,0,\ldots,0,1)$, and rule $R$ is applicable to $t_2$ or $t_2=(1,0,\ldots,0,1)$;
\item
$t_1\rightarrow_T t'_1$, $t_2\rightarrow_T t'_2$, with $T=L$ or $R$ and $t'_1\leq t'_2$.
\end{itemize}
\end{proposition}

In other words, by (ii), the order (for Christoffel-Lyndon words, and for $n$-
tuples) corresponds to the so-called infix order of the corresponding tree.

\begin{proof}
Let $W_i$ be the word on $L,R$ which codes the path from the root to $t_i$. Let $w_i=W_i(x_1x_n)$. Then by Lemma \ref{letters}, $t_i\rightarrow_{W_i} (1,0,\ldots,0,1)$. Moreover, $t_1\leq t_2$ is equivalent to $w_1\leq w_2$. Let $W$ be the longest common prefix of $W_1,W_2$. Then $W$ corresponds to the first common ancestor of $w_1,w_2$ in the tree.  

Suppose first that $t_1\leq t_2$ and argue by contradiction. Since $t$ is their smallest common ancestor, they are not in the same left or right subtree under $t$ and we must have: either $t_2$ is in the left subtree under $t$ or equal to $t$, and $t_1$ is in the right subtree under $t$ or equal to $t$; moreover $t_1=t=t_2$ does not hold. Then $W_1=WRU$ or $W_1=W$, and $W_2=WLV$ or $W_2=W$ and moreover $W_1=W=W_2$ does not hold. Then by Lemma \ref{descrip-order}, we reach the contradiction $w_2&lt;w_1$. Thus (ii) must hold.

Suppose now that (ii) holds. Then we may write $W_1=WLU$ or $W_1=W$, and $W_2=WRV$ or $W_2=W$. Suppose that $W$ is the empty word (which means that $t$ is the root); then $W_1=LU$ or $W_1$ is the empty word; in the first case, we have by Lemma \ref{letters}, $t_1\rightarrow_{LU}(1,0,\ldots,0,1)$ so that rule $L$ is applicable to $t_1$; in the second case, $t_1=(1,0,\ldots,0,1)$. Thus, arguing similarly for $t_2$, the first condition in (iii) holds. Suppose now that $W$ is nonempty and let $T$ be its first letter. Then by the same lemma, rule $T$ is applicable to both tuples $t_1,t_2$, giving two tuples $t'_1,t'_2$. Let $W=TW'$. One has either $t_1\rightarrow_T t'_1\rightarrow_{W'LU} (1,0,\ldots,0,1)$, or $t_1\rightarrow_T t'_1\rightarrow_{W'} (1,0,\ldots,0,1)$. Let $t'$ be the node corresponding to $W'$. Then $t'_1$ is in the left subtree under $t'$ or equal to $t'$. Similarly, $t'_2$ is in the right subtree under $t'$ or equal to it. Thus by induction, we see that $t'_1\leq t'_2$ so that the second condition in (iii) holds.

Suppose now that (iii) holds. If the first condition holds, then, using Lemma \ref{letters}, we see that $w_1=L(u)$ or $w_1=x_1x_n$, and $w_2=R(v)$ or $w_2=x_1x_n$ for some Christoffel-Lyndon words $u,v$ of length at least 2 , and which contain both the letter $x_1$. Thus (i) holds by Lemma \ref{descrip-order}. Suppose that the second condition holds. If $W_1,W_2$ are both nonempty, then by lemma \ref{letters} and this condition, they must begin by the same letter $T$;
then $w_1=T(w'_1)$, $w_2=T(w'_2)$ with $w'_1\leq w'_2$, so that $w_1\leq w_2$ since $T$ preserves the order; then (i) holds. If $W_i$ is empty, then $t_i=(1,0,\ldots,0,1)$ and the only applicable rule is $R$, giving the tuple $t'_i=(1,0,\ldots,0)$. Since this tuple corresponds to the word $x_1$, which is the smallest Christoffel-Lyndon word, and since $t'_1\leq t'_2$, we must have $t'_1=(1,0,\ldots,0)$. Thus $t_1=(1,0,\ldots,0,1)$, rule $R$ is applicable to $t_2$ (since rule $L$ is not applicable to $t_1$). Then either $W_2$ begins by $R$ and we deduce $t_1\leq t_2$ by Lemma \ref{descrip-order} (i), or $W_2$ is the empty words and $t_1=t_2$. Thus (i) holds.
\end{proof}

For reasons which appear later, we need to extend this total order on tuples of relatively prime natural numbers to a preorder on the set of all nonvanishing tuples of natural numbers, by the following rule: for each such tuples $t,t'$, we write $t\leq t'$ if $s\leq s'$, where $s$ (resp., $s'$) is obtained from $t$ 
(resp., $t'$) by dividing it by its gcd.

In other words, call {\em slope} of a nonvanishing tuple of natural numbers the unique proportional tuple of relatively prime natural numbers. Then we have $t\leq t'$ if and only if $s\leq s'$ where $s,s'$ are the slopes of $t,t'$. 

We let $\bar{\mathbb T}_n$ denote the set of all $n$-tuples of natural numbers having at least two nonzero components, one of them being the first. 
We deduce the following result, which completely describes the preorder of these $n$-tuples.  

\begin{corollary}\label{LR}
Let $t_1,t_2$ be two $n$-tuples in $\bar{\mathbb T}_n$. Then $t_1\leq t_2$ if and only if one of the following conditions holds:

(i) Rule $L$ is applicable to $t_1$ or $t_1=(d,0,\ldots,0,d)$ for some natural number $d$, and rule $R$ is applicable to $t_2$ (this includes the case $t_2=(e,0,\ldots,0,e)$ for some natural number $e$);

(ii) $t_1\rightarrow_T t'_1$, $t_2\rightarrow_T t'_2$, with $T=L$ or $R$ and $t'_1\leq t'_2$.
\end{corollary}

\begin{proof}
Let $s_i$ be the unique $n$-tuple in ${\mathbb T}_n$ proportional to $t_i$. Then $t_1\leq t_2$ if and only if $s_1\leq s_2$; a rule is applicable to $s_i$ 
if and only if its is applicable to $t_i$; $s_i=(1,0,\ldots,0,1)$ if and only if $t_i=(d,0,\ldots,0,d)$. Moreover, condition (ii) is equivalent to the similar condition for the $s_i$'s. Hence the corollary follows from the proposition.
\end{proof}

As noticed above, the order on $2$-tuples $(a,b)$ is completely described by the natural order on their slopes $b/a$, which are nonnegative rational numbers or $\infty$. We do not know of a similar characterization of the order on $n$-tuples.

For later use, we prove the lemma below. 

\begin{lemma}\label{property}
Let $t\in \bar{\mathbb T}_n$ and let $e_i$ denote the canonical basis. Then
$t+e_1\leq t\leq t+e_2\leq \ldots\leq t+e_n$ and $t+e_1+e_n\leq t+e_2$.
\end{lemma}

\begin{proof}
For $n=2$, this follows easily from the definition of the order recalled above: $(a,b)\leq (a',b')$ if and only if $b/a\leq b'/a'$ for the natural order of real numbers. Indeed, all we have to show is that if $(a,b)$ is a nonvanishing pair of nonnegative integers, then $b/(a+1)\leq b/a\leq(b+1)/a$ and $(b+1)/(a+1)\leq(b+1)/a$; the case $a=0$ is treated separately, and the other cases are easy.

We claim that all the inequalities also hold for $t=de_1$ (which is not in $\bar {\mathbb T}_n$) for any nonzero natural number $d$. This is easily verified by inspection. Indeed, the tuples are, respectively, $(d+1)e_1,de_1,de_1+e_2,\ldots,de_1+e_n$ and $(d+1)e_1+e_n, de_1+e_2$, which after division by their gcd correspond to the Christoffel-Lyndon words $x_1,x_1,x_1^dx_2,\ldots,x_1^dx_n$ and $x_1^{d+1}x_n, x_1^dx_2$.

We associate to each $t\in \bar {\mathbb T}_n$ the pair $(l,m)$, its {\em width}, where $l$ is the sum of the components of $t$, and $m$ is equal to $(n+1)-$ the highest index of a nonzero component of $t$; note that $m\in \{1,\ldots,n-1\}$. These pairs are ordered lexicographically and we prove the lemma by induction on this order.

Let $t=(a_1,\ldots,a_n)$. If $a_1&gt;a_n$, then we have $t+e_1=(a_1+1,\ldots,a_n)\rightarrow_L (a_1-a_n+1,a_n,a_2,\ldots,a_{n-1})$ and $t\rightarrow_L t'=(a_1-a_n,a_n,a_2,\ldots,a_{n-1})$; then the two tuples on the right-hand side of the arrows may be written, respectively, $t'+e_1$ and $t'$; then $t'\in \bar{\mathbb T}_n$, with width $(l',m')$ say; then either $a_n&gt;0$ and $l'&lt;l$, or $a_n=0$, $l'=l$ and $m'&lt;m$; then we conclude by induction and Corollary \ref{LR} that $t+e_1\leq t$.
If we have $a_1=a_n$, then rule $L$ is applicable to $t+e_1$ and rule $R$ is applicable to $t$, so that again $t+e_1\leq t$ by Corollary \ref{LR}. 
Finally, if $a_1&lt; a_n$, the tuples $t+e_1$ and $t$ are rewritten under rule $R$ into $(a_1+1,a_2,\ldots,a_{n}-a_1-1)$ and $(a_1,a_2,\ldots,a_{n}-a_1)$; these may be written as $t'+e_1$ and 
$t'+e_n$ with $t'=(a_1,a_2,\ldots,a_{n}-a_1-1)$, so that we conclude either by induction (since $a_1&gt;0$, so that $l$ decreases) and Corollary \ref{LR} that $t+e_1\leq t$ if $t'\in \bar{\mathbb T}_n$, or by the 
claim otherwise (since if $t'\notin \bar{\mathbb T}_n$, we must have $t'=a_1e_1$ because its first component $a_1$ is nonzero).  This proves the first inequality in all cases.

We prove now that $t\leq t+e_2$, under the hypothesis that $n&gt;2$. If $a_1&gt;a_n$, then rule $L$ is applicable to both tuples, giving the tuples $(a_1-a_n,a_n, a_2,\ldots,a_{n-1})$ and $(a_1-a_n,a_n, a_2+1,\ldots,a_{n-1})$, which may be written as $t'$ and $t'+e_3$, $t'\in \bar{\mathbb T}_n$, and we conclude by induction (here $l$ in the width does not decrease, but $m$ does). If $a_1\leq a_n$, then rule $R$ is applicable to both tuples, giving the tuples $t'=(a_1,a_2,\ldots,a_{n}-a_1)$ and $(a_1,a_2+1,\ldots,a_{n}-a_1)$. They may be written $t'$ and $t'+e_2$ and we conclude either by induction if $t'\in \bar{\mathbb T}_n$, or by the claim otherwise.

We prove now that $t+e_i\leq t+e_{i+1}$ for $2\leq i\leq n-2$. If $a_1&gt;a_n$, then rule $L$ is applicable to both tuples, giving the tuples $t'+e_{i+1}$ and $t'+e_{i+2}$, with $t'=(a_1-a_n,a_n, a_2,\ldots,a_{n-1})$ and we conclude by induction. If $a_1\leq a_n$, then rule $R$ is applicable to both tuples, giving the tuples $t'+e_i$ and $t'+e_{i+1}$, with $t'=(a_1,a_2,\ldots,a_{n}-a_1)$ and we conclude by induction if $t'\in \bar{\mathbb T}_n$, or by the claim otherwise.

We prove now that $t+e_{n-1}\leq t+e_{n}$. If $a_1&gt;a_n+1$, then rule $L$ is applicable to both tuples and gives, respectively, $(a_1-a_n,a_n,\ldots,a_{n-2},a_{n-1}+1)$ and $(a_1-a_n-1,a_n+1,\ldots,a_{n-2},a_{n-1})$; these tuples may be written as $t'+e_1+e_n$ and $t'+e_2$, with $t'=(a_1-a_n-1,a_n,\ldots,a_{n-2},a_{n-1})\in \bar{\mathbb T}_n$, which allows to conclude by induction. If $a_1=a_n+1$, then rule $L$ is applicable to $t+e_{n-1}$ and rule $R$ is applicable to $t+e_n$, so that $t+e_{n-1}\leq t+e_{n}$ by the corollary. If $a_1\leq a_n$, then rule $R$ is applicable to both tuples, giving the tuples $t'+e_{n-1}$ and $t+e_{n}$, with $t'=(a_1,a_2,\ldots,a_{n}-a_1)$ and we conclude either by induction if $t'\in \bar{\mathbb T}_n$, or by the claim otherwise.

It remains to prove that $t+e_1+e_n\leq t+e_2$. If $a_1&gt;a_n$, then rule $L$ is applicable to both tuples, giving the tuples $(a_1-a_n,a_n+1, a_2,\ldots,a_{n-1})$ and $(a_1-a_n,a_n, a_2+1,\ldots,a_{n-1})$ which may be written as $t'+e_2$ and $t'+e_3$, with $t'=(a_1-a_n,a_n, a_2,\ldots,a_{n-1})$ and we conclude by induction. If $a_1\leq a_n$, then rule $R$ is applicable to both tuples, giving the tuples $(a_1+1,a_2,\ldots,a_{n}-a_1)$ and $(a_1,a_2+1,\ldots,a_{n}-a_1)$, which may written $t'+e_1$ and $t'+e_2$, and we conclude either by induction if $t'\in \bar{\mathbb T}_n$, or by the claim otherwise.
\end{proof}

\subsection{A geometrical property of Christoffel-Lyndon words}\label{geom}

We call {\em slope} of any word on the letters $x_1,\ldots,x_n$ the slope of the $n$-tuple $(|w|_{x_1},\ldots,|w|_{x_n})$, as defined in the previous section. Slopes are in bijection with Christoffel-Lyndon words (Theorem \ref{prime}) and ordered as them. 

\begin{theorem}\label{max}
Let $w$ be a Christoffel-Lyndon word. For each prefix $ux$ of $w$, with $u$ a word and $x$ a letter, the letter $x$ is uniquely defined by the condition that the slope of $ux$ is $\leq$ than the slope of $w$ and that it is maximum subject to this condition.
\end{theorem}

This result generalizes the geometrical interpretation of Christoffel words (see \cite{B,BL}) recalled at the beginning of Section \ref{GEOM}.

For any word $w$, let $\sl(w)$ denote its slope, considered as a Christoffel-Lyndon word. Hence, $\sl(w)$ is the unique Christoffel-Lyndon word such that $w$ and $\sl(w)$ have proportional commutative images. In particular, if $w$ is a Christoffel-Lyndon word, then $\sl(w)=w$. Observe also that $\sl(w)=\sl(w')$ if $w'$ is a rearrangement of $w$. For further use, note that by Lemma \ref{property}, for any word $u$, we have 
\begin{equation}\label{ineq}
\sl(ux_1)\leq \sl(u)\leq \sl(ux_2)\leq \cdots\leq \sl(ux_n). 
\end{equation}

\begin{lemma}\label{slT=Tsl}
If $T$ is the substitution $L$ or $R$, then $\sl(T(w))=T(\sl(w))$ for any word $w$.
\end{lemma}

\begin{proof}
We know by Lemma \ref{send} that $T$ preserves Christoffel-Lyndon words; thus $T(\sl(w))$ is a Christoffel-Lyndon word. Since $\sl(w)$ and $w$ have proportional commutative images, so do $T(\sl(w))$ and $T(w)$. The lemma follows.
\end{proof}

\begin{lemma}\label{factor}
If $w=R(m)$ or $w=L(m)$ and $x_jx_n$ is a factor of $w$ for some $j$ satisfying $2\leq j\leq n-1$, it is also a factor of $m$. Consequently, this cannot happen if $w$ is on the tree of Christoffel-Lyndon words
\end{lemma}

\begin{proof}
If $w=L(m)$, then each $x_n$ in $w$ is preceded by $x_1$; hence this cannot happen. If $w=R(m)$, then its factor $x_jx_n$ must come from the same factor in $m$, since $2\leq j\leq n-1$. The final assertion follows, since the root $x_1x_n$ does not have the factor $x_jx_n$. 
\end{proof}


\begin{proof} (of the theorem)
We may assume that $n\geq 3$, since for $n=2$, this is the property of Christoffel words recalled after the theorem. By induction on the size of the alphabet, we may assume that $w$ has the letter $x_1$, together with some other letter.
In view of Eq.~(\ref{ineq}), it is enough to show that 

(i) $\sl(v)\leq w$ for each nontrivial prefix $v$ of $w$;

(ii) if $ux_i$ is a prefix of $w$, $i&lt;n$, then $\sl(ux_{i+1})&gt;w$.

We know that $w$ appears on the tree of Christoffel-Lyndon words, and we argue by induction on its depth in the tree. If $w$ is the root, then $w=x_1x_n$ and we are done, since $\sl(x_1)=x_1&lt;x_1x_n$ and $\sl(x_2)=x_2&gt;x_1x_n$. 

In general, we have $w=T(m)$ for $T=R$ or $L$ and we may assume by induction that the theorem holds for $m$. Let $v$ be a prefix of $w$. If $v=T(p)$ for some prefix $p$ of $m$, then we have by induction $\sl(p)\leq m$; thus $\sl(v)=\sl(T(p))=T(\sl(p))$ (by Lemma \ref{slT=Tsl}) $\leq T(m)=w$, since $T$ preserves the order. If there is no prefix of $m$ sent onto $v$ by $T$, then, due to the special form of $L$ or $R$, we must have $w=v_1x_1x_nv_2$ with $v=v_1x_1$ and $T(px_j)=v_1x_1x_n$ for some prefix $px_j$ of $m$, with $j=2$ if $T=L$ and $j=1$ if $T=R$. Note that $T(p)=v_1$. By induction, we have $\sl(p)\leq m$. Thus, as before, $\sl(v_1)=\sl(T(p))=T(\sl(p))\leq T(m)=w$. Since $\sl(v)=\sl(v_1x_1)\leq \sl(v_1)$ by Eq.~(\ref{ineq}), we deduce that $\sl(v)\leq w$. This proves (i).

Suppose that $T=R$. Suppose that $i=1$. Then $ux_1$ is followed by $x_n$ in $w$ and $ux_1x_n=R(px_1)$, with $px_1$ a prefix of $m$ and $R(p)=u$. By induction, $\sl(px_2)&gt;m$ thus $\sl(ux_2)=\sl(R(px_2))=R(\sl(px_2))&gt;R(m)=w$, which proves (ii) in this case. Suppose that $i&gt;1$. Then $ux_i=R(px_i)$ with $px_i$ prefix of $m$ and $R(p)=u$. Then by induction $\sl(px_{i+1})&gt;m$, which implies $\sl(ux_{i+1})=\sl(R(px_{i+1}))=R(\sl(px_{i+1}))&gt;R(m)=w$. This proves (ii) in this case. 

We assume now that $T=L$, that is, $w=L(m)$. Suppose that $ux_1$ is a prefix of $w$. Then either $px_1$ is a prefix of $m$ with $L(p)=u$ or $px_2$ is a prefix of $m$ with $L(p)=u$; in both cases $\sl(px_3)&gt;m$ by induction and Eq.~(\ref{ineq}). Thus we deduce that $\sl(ux_2)=\sl(L(px_3))=L(\sl(px_3))&gt;L(m)=w$ which proves (ii) in this case.

Suppose now that $ux_i$ is a prefix of $w$ with $i=2,\ldots, n-2$. Then $px_{i+1}$ is prefix of $m$ with $L(p)=u$; then by induction $\sl(px_{i+2})&gt;m$ and we deduce that $\sl(ux_{i+1})=\sl(L(px_{i+2}))=L(\sl(px_{i+2}))&gt;L(m)=w$, which proves (ii) in this case.

Finally, suppose that $ux_{n-1}$ is a prefix of $w$. Then $u$ is not the empty word ($w$ must begin by $x_1$ and $n-1&gt;1$) and let $x_j$ be its last letter; thus $u=vx_j$ and $x_jx_{n-1}$ is a factor of $w$.

Suppose that $j=n$. Then $m$ must have the factor $x_2x_n$, which is not possible by Lemma \ref{factor}.

Suppose that $1&lt;j&lt;n-1$. Then $m$ must have $x_{j+1}x_n$ as factor, which again is not possible by Lemma \ref{factor}. 

Thus $j=1$ or $n-1$ and we deduce by iterating this argument that $ux_{n-1}=vx_1x_{n-1}^r$, $r\geq 1$, hence $u=vx_1x_{n-1}^{r-1}$. 

\medskip

Case 1: $r=1$, that is $vx_1x_{n-1}=ux_{n-1}$ is a prefix of $w$. Then $px_1x_n$ is a factor of $m$, with $L(p)=v$. Then by induction $\sl(px_2)&gt;m$, thus $\sl(ux_n)=\sl(vx_1x_n)=\sl(L(px_2))=L(\sl(px_2))&gt;L(m)=w$, which proves (ii) in this case. 

\medskip

Case 2: $r&gt;1$. Then $\sl(ux_n)=\sl(vx_1x_{n-1}^{r-1}x_n)=\sl(vx_1x_nx_{n-1}^{r-1})$ (by rearrangement) $\geq \sl(vx_1x_{n})$ (by Eq.~(\ref{ineq}) since $n-1\geq 2$) $&gt;w$, by the $r=1$ case, since $vx_1x_{n-1}$ is a prefix of $w$, because $ux_{n-1}=vx_1x_{n-1}x_{n-1}^{r-1}$.
\end{proof}

\begin{figure}
\centering
\includegraphics[width=2in]{acbacbb_3D_Lyndon_Christofell.eps}
\includegraphics[width=2in]{acbacc_3D_Lyndon_Christofell.eps}
\caption{Paths corresponding to the Christoffel-Lyndon words $acbacbb$ and $acbacc$}
\end{figure}

\section{The infinite algorithm: periodicity and convergence}

We may apply the rewriting system of Section \ref{Euclidean} to any $n$-tuple of real numbers. We consider only $n$-tuples of nonnegative real numbers whose first component is positive. Note that the first component will remain positive during the algorithm.We say that the algorithm, applied to $(a_1,\ldots, a_n)$, is {\em infinite} if one never obtains an $n$-tuple of the form $(d,0,\ldots,0)$. Equivalently, by Lemma \ref{rewriting}, the $n$-tuple is not of the form $\alpha(b_1,\ldots,b_n)$ for some real $\alpha$ and some integers $b_1,\ldots,b_n$; equivalently, the $\mathbb Q$-subspace spanned by the $a_i$'s is not of dimension 1.

There is an infinite word over the alphabet $L,R$ generated by the algorithm, assumed to be infinite, applied to some given $n$-tuple $t$ as above: this word is defined by the condition that its prefix $W_k$  of length $k$ satisfies $t\rightarrow_{W_k} t_k$ for some $n$-tuple $t_k$.
Let $w_k$ be the Christoffel-Lyndon word $W_k(x_1x_n)$, where $W_k$ is the corresponding substitution. 
In analogy with the case $n=2$ 
(Christoffel words and continued fractions, see e.g., \cite{BLRS}), one is tempted to conjecture that for $i=2,\ldots,n$ (we let $\mid w\mid_i$ denote the number of $x_i$'s in the word $w$):

\begin{equation}\label{limit1}
\lim_{k\rightarrow \infty} \frac{\mid w_k\mid_i}{\mid w_k\mid_1}=\frac{a_i}{a_1}.
\end{equation}

There is an equivalent statement, using incidence matrices. Recall that the {\em incidence matrix} (or commutative image) of the substitution $f$ is defined to be the matrix $(\mid f(x_j)\mid_{x_i})_{1\leq i,j\leq n}$. We take the same notation for a substitution and its incidence matrix. See the proof of Lemma \ref{matrix relation} where the incidence matrices $L$ and $R$ are shown explicitly. Let

\begin{equation}\label{suite}
\left( \begin{array}{c}\alpha_1(k)\\ \vdots \\ \alpha_n(k)\end{array} \right)
=W_k \left( \begin{array}{c}1\\ 0 \\ \vdots \\0\\1\end{array} \right).
\end{equation}

Then the conjecture in Eq.~(\ref{limit1})is equivalent to
\begin{equation}\label{limit2}
\lim_{k\rightarrow \infty} \frac{\alpha_i(k)}{\alpha_1(k)}=\frac{a_i}{a_1}.
\end{equation}

We prove this conjecture in the case where $W$ is {\em ultimately periodic}, that is, for some $p&gt;0$ and some $k_0\geq 0$, one has $w_k=w_{k+p}$ for any $k\geq k_0$. In this case, we also obtain that the limits are algebraic numbers.

\begin{theorem}\label{periodic}
Suppose that the algorithm applied to the $n$-tuple of nonnegative real numbers $(a_1,\ldots,a_n)$ generates the ultimately periodic infinite word $W$ over the alphabet $\{L,R\}$. Then Eq.~(\ref{limit1}) and (\ref{limit2}) hold and the limits are algebraic numbers belonging to the same number field of degree at most $n$. 
\end{theorem}

The theorem will be proved after several lemmas. The next lemma is a particular case of a well-known result, and is a partial converse of Lemma \ref{letters}.
\begin{lemma}\label{matrix relation}
Let $W$ be a finite word over $L,R$ such that $(a_1,\ldots,a_n)\rightarrow_W(b_1,\ldots,b_n)$. Then$$
\left( \begin{array}{c}a_1 \\ \vdots \\ a_n \end{array} \right)=W\left( \begin{array}{c}b_1 \\ \vdots \\ b_n \end{array} \right).
$$
\end{lemma}

Note that in accordance with our abuse of notation, here $W$ represents the incidence matrix of the substitution $W$.

\begin{proof}
Let $W=TV$ with $T=L$ or $R$. Denote by $a,b$ the two $n$-tuples in the statement. Let $a'$ be the $n$-tuple such that $a\rightarrow_Ta'\rightarrow_Vb$. Then by induction, we have 
$$
\left( \begin{array}{c}a'_1 \\ \vdots \\ a'_n \end{array} \right)=V\left( \begin{array}{c}b_1 \\ \vdots \\ b_n \end{array} \right).
$$
We claim that 
$^ta=T\,{}^ta'$. This implies that $^ta=T\,{}^ta'=TV\,{}^tb=W\,{}^tb$, which ends the proof.

Let us prove this claim. If $T=L$, then $a'_1=a_1-a_n$, $a'_2=a_n$, $a'_3=a_2$,$\ldots$, $a'_n=a_{n-1}$. Moreover, 
$$
L=\left( \begin{array}{cccccc}
1 &amp; 1 &amp; 0 &amp; \ldots &amp;  0 \\ 
0 &amp; 0 &amp; 1 &amp; \ddots &amp; \vdots \\ 

\vdots &amp; \vdots &amp; &amp; \ddots &amp;  0 \\
0 &amp; 0 &amp;&amp;&amp;1 \\
0 &amp; 1 &amp; 0 &amp; \ldots &amp;  0
\end{array} \right).
$$
Thus 
$$
L\left( \begin{array}{c}a'_1 \\ \vdots \\ a'_n \end{array} \right)=\left( \begin{array}{c}a'_1+a'_2\\ a'_3 \\\vdots \\ a'_n \\ a'_2 \end{array} \right) = \left( \begin{array}{c}a_1 \\ a_2 \\ \vdots \\ a_{n-1} \\ a_n \end{array} \right).
$$

If $T=R$, then $a'_i=a_i$ for $i=1,\ldots, n-1$ and $a'_n=a_n-a_1$. Moreover,
$$
R=\left( \begin{array}{cccccc}
1 &amp; 0 &amp; \ldots &amp; \ldots &amp; 0 \\ 
0 &amp; 1 &amp;  \ddots &amp; &amp;\vdots \\ 

\vdots &amp; 0 &amp;  \ddots &amp; \ddots &amp; \vdots \\
0 &amp;  &amp;\ddots&amp;1&amp;0 \\
1 &amp; 0&amp; \ldots &amp; 0 &amp;  1
\end{array} \right).
$$
Thus

$$
R\left( \begin{array}{c}a'_1 \\ \vdots \\ a'_n \end{array} \right)=\left( \begin{array}{c}a'_1\\ a'_2 \\\vdots \\ a'_{n-1} \\ a'_1+a'_n \end{array} \right) = \left( \begin{array}{c}a_1 \\ a_2 \\ \vdots \\ a_{n-1} \\ a_n \end{array} \right),
$$
which proves the claim.
\end{proof}

Recall that a nonnegative square matrix is called {\em primitive} if one of its powers is positive (that is, all its entries are $&gt;0$). Recall that, by the Perron theorem, $M$ then has a nonnegative eigenvector, unique up to positive factors, which is associated to the so-called {\em Perron eigenvalue} of $M$. The latter is positive, simple and has maximum modulus among all eigenvalues of $M$;
see \cite[Theorem 2.6, p.\ 27]{DZ}.  The next result is certainly well-known.

\begin{lemma} \label{number field}
Let $M$ be a primitive $n$ by $n$ matrix with $m_{11}\neq 0$. Let $\alpha_i(k)$, $i=1,\ldots,n$ denote $n$ nonnegative sequences, with $\alpha_1(k)$ positive, such that
\begin{equation}\label{sequences}
\left( \begin{array}{c}\alpha_1(k+1)\\ \vdots \\ \alpha_n(k+1) \end{array} \right)=M\left( \begin{array}{c}\alpha_1(k)\\ \vdots \\ \alpha_n(k) \end{array} \right)
\end{equation}
and such that the limits in Eq.~(\ref{limit2}) exist. Then these limits are in the number field generated by the Perron eigenvalue of $M$. Moreover they do not depend on the initial values $\alpha_1(0),\ldots,\alpha_n(0)$.
\end{lemma}   

\begin{proof}
Let $l_i$, $i=1,\ldots, n$, be these limits; note that $l_1=1$. Let $l=(1,0,\ldots,0)M\left( \begin{array}{c}\l_1\\ \vdots \\ \l_n \end{array} \right)=\sum_jm_{1j}l_j$. Note that $l&gt;0$. We have 
$$
\frac{\alpha_i(k+1)}{\alpha_1(k+1)}=\frac{\sum_j m_{ij}\alpha_j(k)}{\sum_j m_{1j}\alpha_j(k)}=\frac{\sum_jm_{ij}\frac{\alpha_j(k)}{\alpha_1(k)}}{\sum_jm_{1j}\frac{\alpha_j(k)}{\alpha_1(k)}}.
$$

Taking the limit, we obtain $l_i=(1/l) \sum_j m_{ij}l_j$. Thus
$$
\left( \begin{array}{c}\l_1\\ \vdots \\ \l_n \end{array} \right)=(1/l)M\left( \begin{array}{c}\l_1\\ \vdots \\ \l_n \end{array} \right).
$$
Since $l_1=1$ and $l_i\geq 0$, we have found a nonnegative eigenvector and $1/l$ is the Perron eigenvalue. Now note that if $\lambda$ is an eigenvalue of $M$, then there is an eigenvector $^t(a_1,\ldots,a_n)$ for $\lambda$ whose coefficients $a_i$ are in the field generated by $\lambda$. By unicity of the nonnegative eigenvector, $^t(l_1,\ldots,l_n)={}^t(1,a_2/a_1,\ldots, a_n/a_1)$, which proves the lemma.
\end{proof}

\begin{lemma}\label{limits exist}
Let $M$ be a primitive matrix with Perron eigenvalue $\lambda &gt;1$ and consider a matrix of the form $A=\left( \begin{array}{cc}M&amp;B\\0&amp;I \end{array} \right)$, where $I$ is an identity matrix, B is nonnegative with no zero column. Then for any indices $i,i',j$, with $i'$ within the row indices of $M$, the sequence $(A^k)_{ij}/(A^k)_{i'j}$ is defined for $k$ large enough and has a limit when $k\rightarrow\infty$, independent of $j$. This limit is 0 if $i$ is not within the row indices of $M$. Moreover, for any indices $i,i',j,j'$ with $i'$ within the row indices of $M$, the limit of $((A^k)_{i'j'}(A^k)_{ij}-(A^k)_{i'j}(A^k)_{ij'})/(A^k)_{i'j'}(A^k)_{i'j}$ is 0.
\end{lemma}

\begin{proof}
It follows from the theorem of Perron that for some rank 1 matrix $M'$ one has $M^k\sim \lambda^k M'$, see Section ''Perron projection as a limit'' in: http://en.wikipedia.org
/wiki/Perron-Frobenius\_theorem. 
The matrix $M'$ is positive since $M$ is primitive and $\lambda&gt;1$. Now, one has $A^k= \left( \begin{array}{cc}M^k&amp;B_k\\0&amp;I \end{array} \right)$, where $B_k=\sum_{0\leq i\leq k-1} M^iB$. We have $\sum_{0\leq i\leq k-1} M^i \sim \frac{\lambda^k}{\lambda-1}M'$. Moreover, $M^k$ is positive for $k$ large enough, so that $B_k$ too, by the assumption on the columns. Thus $B_k\sim \lambda^k C$ for some positive matrix $C=\frac{1}{\lambda-1}M'B$ of rank 1. Thus the first statement follows when the index $i$ is within the row indices of $M$. Now, when the index $i$ is not within the row indices of $I$, then the sequence has limit 0. This is due to $\lambda &gt; 1$, so that the coefficients of $M^k$ and $B_k$ tend to $\infty$, while those of $0$ and $I$ are bounded.

Recall that each entry of the $k$-th power of a square matrix is given, for $k$ large enough, by an {\em exponential polynomial}, which is  a linear combination over $\mathbb C$ of terms, each of which is of the form $P(k)\mu^k$, where $P(k)$ is a polynomial in $k$ and $\mu$ a nonzero complex number. In our case, each $i,j$-entry of $A^k$, with $i$ within the row indices of $M$, is of the form $s_{ij}\lambda^k$ $+$ a linear combination of $P(k)\mu^k$ with $\mid\mu\mid&lt;\lambda$. What precedes implies that the matrix $(s_{ij})$ is of rank 1. Hence, if $i,i'$ are both within the row indices of $M$, then $(A^k)_{i'j'}(A^k)_{ij}-(A^k)_{i'j}(A^k)_{ij'}$ is given by an exponential polynomial having only $\mu$'s with $\mid \mu \mid&lt;\lambda^2$. Since the exponential polynomials for $(A^k)_{i'j'}$ and $(A^k)_{i'j}$ both have a term with $\lambda$, the final assertion is proved in this case, because $s_{ij}&gt;0$.

Suppose now that $i'$ is within the row indices of $M$ and $i$ is not. Then we conclude similarly, since $(A^k)_{ij}$ and $(A^k)_{ij'}$ are constants independent of $k$.
\end{proof}

\begin{lemma}\label{subsequence}
Let $A(k)$, $k\in \mathbb P$, be a sequence of nonnegative $n$ by $n$ matrices taken from a finite set of matrices. Let $M(k)=A(1)\cdots A(k)$. Let $(p_k)_{k\geq 0}$ be a stricty increasing sequence of natural integers such that the differences $p_{k+1}-p_k$ are bounded. Suppose that $M(k)_{1j}$ is $&gt;0$ for any $j$ and for $k$ large enough. Suppose further that for any indices $i,j$ in $\{1,\ldots,n\}$, the sequence $M(p_k)_{ij}/M(p_k)_{1j}$ has a limit when $k\rightarrow\infty$, independent of $j$. Then for any indices $i,j$ in $\{1,\ldots,n\}$, the sequence $M(k)_{ij}/M(k)_{1j}$ has the same limit, independent of $j$.
\end{lemma}

\begin{proof}
1. Suppose that $f(k),g_1(k),\ldots,g_s(k)$ are sequences such that the $g_i$ have the same limit $l$ and that for any $k$, $f(k)$ is equal to $g_i(k)$ for some $i=1,\ldots,s$. Then clearly $f$ has the limit $l$, too.

2. With the $p_k$ as in the statement, suppose that for some sequence $x(k)$, and any natural number $h$, the sequence $x(p_k+h)$ has the limit $l$ when $k$ tends to infinity. It is then standard to show that the sequence $x(k)$ converges to $l$, using the fact that the differences $p_{k+1}-p_k$ are bounded, so that only finitely many $h$'s have to be considered.
 
3. We claim that if $2n$ nonnegative sequences $u_i(k),v_i(k)$, $i=1,\ldots,n$, are such that the sequences $u_i(k)/v_i(k)$ have the same limit $l$ (with the $v_i(k)$ positive), then for any nonnegative numbers $a_1,\ldots,a_n$, not all 0, the sequence $(a_1u_1(k)+\ldots+a_nu_n(k))/(a_1v_1(k)+\ldots+a_nv_n(k))$ also has the limit $l$. We may assume that the $a_n$ are positive.
We have $u_i(k)=lv_i(k)+v_i(k)\epsilon_i(k)$ where $\lim_{k\rightarrow \infty}\epsilon_i(k)=0$. Then
$$
\frac{a_1u_1(k)+\ldots+a_nu_n(k)}{a_1v_1(k)+\ldots+a_nv_n(k)}$$
$$=\frac{a_1lv_1(k)+\ldots+a_nlv_n(k)+a_1v_1(k)\epsilon_1(k)+\ldots+a_nv_n(k)\epsilon_n(k)}{a_1v_1(k)+\ldots+a_nv_n(k)}=l+r(k),$$
where $r(k)=\sum_{i}\frac{a_iv_i(k)\epsilon_i(k)}{a_1v_1(k)+\ldots+a_nv_n(k)}$ is bounded by $\sum_i\frac{a_iv_i(k)\epsilon_i(k)}{a_iv_i(k)}=\sum_i\epsilon_i(k)$, which proves the claim.

4. Now, let $H$ be any nonnegative matrix $H=(h_{rs})$ and put $N(k)=M(p_k)H$; we show that the sequence $N(k)_{ij}/N(k)_{1j}$ has the same limit as the sequence $M(p_k)_{ij}/M(p_k)_{1j}$.
We have $N(k)_{ij}=\sum_s M(p_k)_{is}h_{sj}$ and $N(k)_{1j}=\sum_s M(p_k)_{1s}h_{sj}$. By assumption, the sequences $M(p_k)_{is}/M(p_k)_{1s}$ have, for any $s$, the same limit $l$. Thus we conclude with the claim in 3.

5. Fix $i$ and $j$ and let $x(k)=M(k)_{ij}/M(k)_{1j}$. To prove the lemma, it is enough by 2. to show that for each $h$, the sequence $x(p_k+h)$ converges, when $k$ tends to infinity, to a limit $l$, independent of $j$. An element $x(p_k+h)$ has the form $N(k)_{ij}/N(k)_{1j}$, with the notations in 4., by the definition of $M(k)$, with $H=A(p_k+1)\cdots A(p_k+h)$; for fixed $h$, there are finitely many possible $H$'s. Hence we conclude using 1. and 4.
\end{proof}

\begin{lemma}\label{shift}
Let $A(k)$, $k\in \mathbb N$, be a sequence of nonnegative $n$ by $n$ matrices taken from a finite set of matrices. Let $M(k)=A(1)\cdots A(k)$. Suppose that $M(k)_{1j}&gt;0$ for $k$ large enough and $A(0)_{11}&gt;0$. Suppose further that for any indices $i,j$ in $\{1,\ldots,n\}$, the sequence $M(k)_{ij}/M(k)_{1j}$ has a limit $l_i$, independent of $j$. Let $M'(k)=A(0)M(k)$.  Then the sequence $M'(k)_{ij}/M'(k)_{1j}$ has a limit $l'_i$, and the limits are related by
$$
l'_i=\frac{\sum_jA(0)_{ij}l_j}{\sum_jA(0)_{1j}l_j}.
$$
\end{lemma}

\begin{proof}
We have 
$$
M'(k)_{ij}/M'(k)_{1j}=\frac{\sum_q A(0)_{iq}M(k)_{qj}}{\sum_q A(0)_{1q}M(k)_{qj}}
=\frac{\sum_q A(0)_{iq}\frac{M(k)_{qj}}{M(k)_{1j}}}{\sum_q A(0)_{1q}\frac{M(k)_{qj}}{M(k)_{1j}}}.
$$
Note that $M'(k)_{1j}\geq A(0)_{11}M(k)_{1j}&gt;0$ for $k$ large enough. The limit of this is clearly $\frac{\sum_q A(0)_{iq}l_q}{\sum_q A(0)_{1q}{l_q}}$. Note that the denominator is $&gt;0$, since $A(0)_{11}&gt;0$ and $l_1=1$.
\end{proof}

Let $X=\{x_1,\ldots,x_n\}$. Let $\gamma$ be the substitution $\gamma=(x_1,x_n,x_2,\ldots,x_{n-1})$; note that $\gamma^{n-1}$ is the identity. 

\begin{lemma} \label{form of substitution}
Let $k&gt;0$ and $i_1,\ldots,i_k,j_1,\ldots ,j_k &gt;0$ and let $f$ be the substitution $f=R^{j_k}L^{i_k}\cdots R^{j_1}L^{i_1}$ with $i_1+\cdots +i_k \equiv 0
$ (mod $n-1$). 
Let $S$ be 
the set of partial sums, 
$S=\{i_{k},i_{k}+i_{k-1},\ldots,i_k+\cdots + i_1\}$. 
Let $Y=\{x_1\}\cup\{\gamma^s(x_{n}), s\in S\}$. Then

(i) $x_1,x_n\in Y$;

(ii) for any $x\in Y$, $f(x)\in Y^*$ and each $y\in Y$ appears in $f(x_1)$.

(iii) $x_1$ appears in each $f(x)$, $x\in X$;

(iv) for each $x \in X\setminus Y$, $f(x)\in Y^*x$.
\end{lemma}

For example, if $n=5$, let $f=RL^5RL^3$. Then $Y=\{x_1,\gamma^5(x_5),\gamma^8(x_5)\}=\{x_1,x_4,x_5\}$. One verifies that (we write $i$ instead of $x_i$) 
$$f=(15154,1515415{\bf 2},1515415{\bf 3},15154154, 15155).$$

\begin{proof}
By construction, $x_1$ is in $Y$ and by hypothesis on the sum of the $i_j$'s, $Y$ contains $x_n$. This proves (i). 

We claim that for $i,j&gt;0$, $$R^jL^i=(x_1x_n^j,(x_1x_n^j)^{q+1}x_{n+1-s},\ldots,(x_1x_n^j)^{q+1}x_{n},(x_1x_n^j)^{q}x_{2},\ldots,(x_1x_n^j)^{q}x_{n-s}),$$
where $i=s+(n-1)q$, $s\in\{1,\ldots,n-1\}$. This is proved as follows: $$L=(x_1,x_1x_n,x_2,\ldots,x_{n-1}), L^s=(x_1,x_1x_{n+1-s},\ldots,x_1x_n,x_2,\ldots,x_{n-s}),$$ 
$$L^{n-1}=(x_1,x_1x_2,\ldots,x_1x_{n}), L^{(n-1)q}=(x_1,x_1^qx_2,\ldots,x_1^qx_{n}),$$ 
$$L^{i}=L^{s+(n-1)q}=(x_1,x_1^{q+1}x_{n+1-s},\ldots,x_1^{q+1}x_n,x_1^qx_2,\ldots,x_1^qx_{n-s}),$$ 
$$R=(x_1x_n,x_2,\ldots,x_n), R^j=(x_1x_n^j,x_2,\ldots,x_n),$$ 
and the claim follows by multiplying $R^j$ and $L^i$, that is, by replacing in $L^i$ above each $x_1$ by $x_1x_n^j$.


We claim now that for $i_1,\ldots,i_k,j_1,\ldots j_k &gt;0$, $f=R^{j_k}L^{i_k}\cdots R^{j_1}L^{i_1}$ is of the form
$f=(u_1,u_2\gamma^{I}(x_2),\ldots,u_n\gamma^I(x_n))$ where $I=i_1+\cdots +i_k$ and each $u_h$ is a word whose alphabet is a subset of $$\{x_1,x_n,\gamma^{i_k}(x_n),\ldots,\gamma^{i_k+\cdots +i_{2}}(x_n)\},$$
while for $u_1$ it is exactly this set.
This is true by the previous claim for $k=1$: indeed, since $\gamma^i=\gamma^s$, and $\gamma^s(x_2)=x_{n+1-s}, \ldots,\gamma^s(x_n)=x_{n-s}$, we have
$$R^jL^i=(x_1x_n^j,(x_1x_n^j)^{q+1}\gamma^i(x_2),\ldots,(x_1x_n^j)^{q}\gamma^{i}(x_n)).$$
Suppose now it is true for $k$ and let $g=R^{j}L^{i}f$. Then $g(x_1)=R^jL^i(u_1)$; since the alphabet of $u_1$ is as above, we see by the  form of $R^jL^i$, that the alphabet of $g(x_1)$ is $\{x_1,x_n,\gamma^i(x_n),\gamma^{i+i_k}(x_n),\ldots,\gamma^{i+i_k+\cdots+i_2}(x_n)\}$. Next, $g(x_2)=R^jL^i(u_2\gamma^{I}(x_2))=R^jL^i(u_2)R^jL^i(\gamma^{I}(x_2))$; the alphabet of $R^jL^i(u_2)$ is, similarly, a subset of the alphabet of $g(x_1)=R^jL^i(u_1)$; moreover, $R^jL^i(\gamma^{I}(x_2))$ is the product of a word on $x_1,x_n$ by the letter $\gamma^{i+I}(x_2)$, which shows that $g(x_2)$ is of the required form. For the letters $x_3,\ldots,x_n$ the argument is similar.

Suppose now that $i_1+\cdots +i_k\equiv 0$ (mod $n-1$). Then we have 
$$\{x_1,x_n,\gamma^{i_k}(x_n),\ldots,\gamma^{i_k+\cdots +i_{2}}(x_n)\}=Y.$$
This proves (ii) and (iv). Now, in order to prove property (iii), it is enough to show that the incidence matrix of $f$ has a positive first row. The incidence matrix of $R$ is the identity matrix $+$ an elementary matrix. Hence the incidence matrix of $f$ is coefficientwise $\geq$ the incidence matrix of some positive power of $L^{n-1}$. The latter has a positive first row, as shown in a previous calculation. Thus we conclude that property (iii) holds.
\end{proof}

\begin{corollary}\label{form of matrix}
Let $f$ be as in Lemma \ref{form of substitution}. Then its incidence matrix has the following properties, for some subset $I$ of $\{1,\ldots,n\}$ such that $1,n\in I$:

(i) its first row is positive;

(ii) each $e_i$, $i\in I$, is sent to a linear combination of $e_j$, $j\in I$, and the submatrix corresponding to rows and columns in $I$ is primitive;

(iii) the submatrix corresponding to rows and columns not indexed by $I$ is the identity matrix.
\end{corollary}

As an example, the incidence matrix of $f$ given after Lemma \ref{form of substitution} is
$$
\left(\begin{array}{ccccc}
\bf 2&amp;3&amp;3&amp;\bf 3&amp;\bf 2\\
0&amp;\it 1&amp;\it 0&amp;0&amp;0\\
0&amp;\it 0&amp;\it 1&amp;0&amp;0\\
\bf 1&amp;1&amp;1&amp;\bf 2&amp;\bf 0\\
\bf 2&amp;3&amp;3&amp;\bf 3&amp;\bf 3\\
\end{array} \right)
$$
The italicized submatrix is the identity matrix and the boldfaced submatrix is primitive, since it has positive entries on the first row and column; the subset $I$ is $\{1,4,5\}$; (ii) is true as show  the regular 0's.
\begin{proof} (of Theorem \ref{periodic})
Suppose first that the infinite word $W$ is strictly periodic, of the form $W=V^\infty$ for some nonempty finite word $V$ beginning by $R$ and finishing by $L$ and such that the number of $L$'s in $V$ is divisible by $n-1$. Then by Corollary \ref{form of matrix}, the incidence matrix of $V$, which we still denote by $V$, is after applying some permutation of rows and columns, without moving the first row (which is positive), of the form of the matrix $A$ indicated in Lemma \ref{limits exist}.
Thus the limits $\lim_{k\rightarrow \infty}(V^k)_{ij}/V^k)_{1j}$ exist and are independent of $j$. Hence, by Lemma \ref{subsequence}, the limits $\lim_{k\rightarrow \infty}(W_k)_{ij}/(W_k)_{1j}$ exist and are independent of $j$.

Now take the notation of Eq.~(\ref{suite}). It follows that the limits in Eq.~(\ref{limit2}) exist, since $\alpha_i(k)=(W_k)_{i1}+(W_k)_{in}$, so that $\frac{\alpha_i(k)}{\alpha_1(k)}=\frac{(W_k)_{i1}+(W_k)_{in}}{(W_k)_{11}+(W_k)_{1n}}$, whose limit is the same as the common limit of $(W_k)_{i1}/(W_k)_{11}$ and of $(W_k)_{in}/(W_k)_{1n}$ (as follows from the claim in part 3. of the proof of Lemma \ref{subsequence}).

It follows from Lemma \ref{number field} that the limits are in the number field generated by the Perron eigenvalue of $M$; the degree of this field is at most the order of $M$, which by Lemma \ref{form of substitution} is equal to the cardinality of $Y$, with the notation of this lemma.

To prove Eq.~(\ref{limit2}), it is enough to show that $\lim_{k\rightarrow \infty}(V^k)_{i1}/V^k)_{11}=a_i/a_1$. Define a sequence of real row vectors by $(a_1,\ldots,a_n)\rightarrow_{V^k}(b_i(k),\ldots,b_n(k))$. Using Lemma \ref{matrix relation},
we have
$$
a_i/a_1-(V^k)_{i1}/(V^k)_{11}=\frac{\sum_{j}(V^k)_{ij}b_j(k)}{\sum_{h}(V^k)_{1h}b_h(k)}-\frac{(V^k)_{i1}}{(V^k)_{11}}
$$
$$
=\frac{\sum_j b_j(k)((V^k)_{ij}(V^k)_{11}-(V^k)_{i1}(V^k)_{1j})}{(V^k)_{11}(\sum_{h}(V^k)_{1h}b_h(k))}
$$
$$
=\frac{\sum_j \frac{b_j(k)}{b_1(k)}((V^k)_{ij}(V^k)_{11}-(V^k)_{i1}(V^k)_{1j})}{(V^k)_{11}(\sum_{h}(V^k)_{1h}\frac{b_h(k)}{b_1(k)})}
$$
$$
=\sum_j\frac{\frac{b_j(k)}{b_1(k)}((V^k)_{ij}(V^k)_{11}-(V^k)_{i1}(V^k)_{1j})}{(V^k)_{11}(\sum_{h}(V^k)_{1h}\frac{b_h(k)}{b_1(k)})}.
$$
In absolute value, this is bounded by
$$
\sum_j\frac{\frac{b_j(k)}{b_1(k)}\mid (V^k)_{ij}(V^k)_{11}-(V^k)_{i1}(V^k)_{1j}\mid}{(V^k)_{11}(V^k)_{1j}\frac{b_j(k)}{b_1(k)}}
=\sum_j\frac{\mid (V^k)_{ij}(V^k)_{11}-(V^k)_{i1}(V^k)_{1j}\mid}{(V^k)_{11}(V^k)_{1j}}
$$
The limit when $k \rightarrow \infty$ of each term in the previous sum is 0, by Lemma \ref{limits exist}. Thus Eq.~(\ref{limit2}) holds.

The general case, when $W$ is ultimately periodic, follows from Lemma \ref{shift} and Lemma \ref{matrix relation}, since $W$ may be written as $W=UV^\infty$, for some finite words $U,V$ such that $V$ begins by $R$ and ends with $L$ and that the number of $L$'s in $V$ is divisible by $n-1$. Indeed, this follows from periodicity and from the fact that $W$ has infinitely many $L$'s and $R$'s, since in the algorithm, a given rule can be applied only finitely many times.
\end{proof}

\section{Acknowledgments}
We thank Val\'erie Berth\'e for useful mail exchanges, Damien Jamet
for several discussions, and Alejandro Morales for stylistic help.
Thanks are due also to the anonymous referee for careful reading and
useful suggestions.

\begin{thebibliography}{20}

\bibitem{B}
J. Berstel.
\newblock Trac\'e de droites, fractions continues et distances discr\`etes, in
M. Lothaire, {\it Mots: M\'elanges Offerts \`a Sch\" utzenberger},
\newblock Herm\`es, Paris, 1990, pp.\ 298--309.

\bibitem{BLRS}
J. Berstel, A. Lauve, C. Reutenauer, and F. Saliola.
\newblock \emph{ Combinatorics on Words: Christoffel words and Repetitions in Words},
CRM Monograph series, American Mathematical Society, 2008.

\bibitem{BdL}
J.-P. Berstel and A. de Luca.
\newblock Sturmian words, Lyndon words and trees,
\newblock {\it Theoret. Comput. Sci.}
\textbf{178} (1997), 171--203 

\bibitem{Be}
V. Berth\'e,
\newblock Multidimensional Euclidean algorithms,
numeration and substitutions,
\newblock {\it Integers}
\textbf{11B} (2011), Paper A2.

\bibitem{BL}
J.-P. Borel and F. Laubie,
\newblock Quelques mots sur la droite projective r\'eelle,
\newblock {\it J. Th\'eorie Nombres Bordeaux}
\textbf{5} (1993), 23--51.

\bibitem{CFL}
K. T. Chen, R. H. Fox, and R. C. Lyndon.
\newblock Free differential calculus, IV. The quotient groups of the lower central series,
\newblock {\it Ann. Math.}
\textbf{68} (1958), 81--95.

\bibitem{DZ}
J. Ding and A. Zhou.
\newblock {\it Nonnegative Matrices, Positive Operators and Applications},
\newblock World Scientific, 2009.

\bibitem{GKP}
R. L. Graham, D. Knuth, and O. Patashnik.
\newblock {\it Concrete Mathematics}, 
\newblock Addison Wesley, 2nd edition, 1994.

\bibitem{L}
M. Lothaire.
\newblock {\it Combinatorics on Words},
\newblock Addison Wesley 1983, 2nd edition, Cambridge University Press, 1997.

\bibitem{M}
G. Melan\c{c}on.
\newblock {\it Visualisation de graphes et combinatoire des
mots},
\newblock  Habilitation \`a
diriger des recherches,
\newblock Universit\'e de Bordeaux 1, 1999.

\bibitem{R}
G. Richomme.
\newblock {\it Lyndon morphisms},
\newblock {\it Bull. Belg. Math. Soc. Simon Stevin}
\textbf{10} (2003), 761--785.

\bibitem{Sc}
F. Schweiger.
\newblock {\it Multidimensional Continued Fractions},
\newblock Oxford University Press, 2008.

\bibitem{S}
A. I. \v{S}ir\v{s}ov.
\newblock Bases of free Lie algebras,
\newblock {\it Algebra i Logika} \textbf{1} (1962), 14--19.

\bibitem{V}
G. Viennot.
\newblock {\it Alg\`ebres de Lie Libres et Mono\" ides Libres},
\newblock Lecture Notes in Mathematics, Vol.\ 691, Springer, 1978.

\end{thebibliography}
\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 68R15, 11J70.

\noindent \emph{Keywords: } Christoffel word, Lyndon word,
discretization, multidimensional continued fraction, Stern-Brocot tree,
tuple of relatively prime numbers, algebraic number, periodic
expansion.


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received March 26 2013;
revised version received  November 15 2013.
Published in {\it Journal of Integer Sequences}, 
November 17 2013.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

</pre></body></html>