%\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 < 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 $w1$, 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 $\{xa_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>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>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>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<\cdots 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}>| v|_{x_n}$, because $| v'|_{x_1}>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)1$, then $(w'')'$ begins by $x_i$, $i=2,\ldots,n$; thus $w'<(w'')'$, contradicting Eq.~(\ref{'<}).
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')''0$ and that $a_i>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**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)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>0$ and $l'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>2$. If $a_1>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>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>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>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$, $iw$.
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_1x_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)>m$ thus $\sl(ux_2)=\sl(R(px_2))=R(\sl(px_2))>R(m)=w$, which proves (ii) in this case. Suppose that $i>1$. Then $ux_i=R(px_i)$ with $px_i$ prefix of $m$ and $R(p)=u$. Then by induction $\sl(px_{i+1})>m$, which implies $\sl(ux_{i+1})=\sl(R(px_{i+1}))=R(\sl(px_{i+1}))>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)>m$ by induction and Eq.~(\ref{ineq}). Thus we deduce that $\sl(ux_2)=\sl(L(px_3))=L(\sl(px_3))>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})>m$ and we deduce that $\sl(ux_{i+1})=\sl(L(px_{i+2}))=L(\sl(px_{i+2}))>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>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 $1m$, thus $\sl(ux_n)=\sl(vx_1x_n)=\sl(L(px_2))=L(\sl(px_2))>L(m)=w$, which proves (ii) in this case.
\medskip
Case 2: $r>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$) $>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>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 & 1 & 0 & \ldots & 0 \\
0 & 0 & 1 & \ddots & \vdots \\
\vdots & \vdots & & \ddots & 0 \\
0 & 0 &&&1 \\
0 & 1 & 0 & \ldots & 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 & 0 & \ldots & \ldots & 0 \\
0 & 1 & \ddots & &\vdots \\
\vdots & 0 & \ddots & \ddots & \vdots \\
0 & &\ddots&1&0 \\
1 & 0& \ldots & 0 & 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 $>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>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 >1$ and consider a matrix of the form $A=\left( \begin{array}{cc}M&B\\0&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>1$. Now, one has $A^k= \left( \begin{array}{cc}M^k&B_k\\0&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 > 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<\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<\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}>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 $>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}>0$ for $k$ large enough and $A(0)_{11}>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}>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 $>0$, since $A(0)_{11}>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>0$ and $i_1,\ldots,i_k,j_1,\ldots ,j_k >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>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 >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&3&3&\bf 3&\bf 2\\
0&\it 1&\it 0&0&0\\
0&\it 0&\it 1&0&0\\
\bf 1&1&1&\bf 2&\bf 0\\
\bf 2&3&3&\bf 3&\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}
**