On a Class of Lyndon Words Extending Christoffel Words and Related to a Multidimensional Continued Fraction

Algorithm

Guy Melançon Labri Université de Bordeaux 351, cours de la Libération 33405 Talence France

                   melancon@labri.fr

Christophe Reutenauer Département de Mathématiques UQAM Case Postale 8888, Succ. Centre-ville Montréal, Québec H3C 3P8 Canada

             Reutenauer.Christophe@uqam.ca

Abstract

We define a class of Lyndon words, called 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.

1 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 nontrivially) they are strictly smaller than all of their nonempty proper right factors (suffixes), with respect to alphabetical order^{1}. 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 standard factorizations, have been considered in the literature^{2}. One, considered by Chen-Fox-Lyndon [6] and Lothaire [9], takes the longest suffix which is a Lyndon word; the other, considered by Širšov [13] and Viennot [14], 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 ∞. 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 3); this was proved in an unpublished work by the first author [10]. 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 Christoffel-Lyndon words, defined recursively as those Lyndon words admitting a unique standard factorization into a product of two Christoffel-Lyndon words (see Section 2.3).

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 5); for a three-letter alphabet, this result was proved by the first author [10].

To prove this we have to generalize the classical Euclidean algorithm (n = 2) and the Euclidean algorithm of [10] (n = 3) to arbitrary n-tuples of natural integers, see Section 2.5. Similar algorithms have been considered in the realm of multidimensional continued fractions [4, 12], 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 5 for n = 3).

1In comparing cyclic permutations of a word, lexicographical order suffices; but in order to compare a word and its suffixes, one needs alphabetical order.

2The 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.

We introduce two substitutions on n letters, which for n = 2 are classical, and for n = 3 were considered in [10]; 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 5). One tool is a theorem of Richomme [11], that characterizes Lyndon morphisms (substitutions that preserve Lyndon words), Theorem 1. 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 18.

To each n-tuple of reals numbers (a_{1}, …, a_{n}), which are not of rank 1 over ℚ, 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 ((α_{1}(k), …, α_{n}(k)))_{k≥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, …, n, the limit when k tends to ∞ of the quotients α_{i}(k)/α_{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 21. This is of course an analogue of one implication of the Lagrange theorem for continued fractions. Our proof uses the Perron-Frobenius theory.

2 Christoffel-Lyndon words and tuples of relatively prime natural numbers

2.1 Lyndon words and standard factorizations

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

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 right standard factorization of w; it is known that then u, v are Lyndon words and that u < v (see [9, Prop. 5.1.3], where it is called the 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 left standard factorization of w; it is known that then u, v are Lyndon words and that u < v (see [9, Exercise 5.1.6] or [14, p. 15]).

We note that if w is a Lyndon word with left or right standard factorization w = w′w′′, then

w′ < w′′.  (1)

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. (1) holds and if either w′ is a letter, or w′ has the right standard factorization w′ = (w′)′(w′)′′ with

(w′)′′ ≥ w′′.  (2)

See [9, Prop. 5.1.4].

Similarly, this factorization is the left standard factorization of w if and only if Eq. (1) holds and if either w′′ is a letter, or if w′′ has the left standard factorization w′′ = (w′′)′(w′′)′′ with

w′ ≥ (w′′)′.  (3)

See [14, p. 48].

2.2 Lyndon morphisms

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

We use several results due to Gwenaël 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 [11, Lemma 3.2]. In particular, a nonempty order-preserving morphism sends any letter onto some nonempty word, so that k in (i) below is well-defined.

Theorem 1. (i) [11, Prop. 3.3] A nonempty morphism f : X^{∗} → 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}) < 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) [11, Prop. 4.2] A homomorphism f : X^{∗} → Y^{∗} is a Lyndon morphism if and only if it is order-preserving and if it sends each letter onto a Lyndon word.

We consider two endomorphisms of the free monoid X^{∗}, with X = {x_{1} < … < x_{n}}, n ≥ 2. They are written L and R and defined as follows:

• L sends the n-tuple (x_{1}, …, x_{n}) onto (x_{1}, x_{1}x_{n}, x_{2}, ..., x_{n−1});

• R sends the n-tuple (x_{1}, …, x_{n}) onto (x_{1}x_{n}, x_{2}, ..., x_{n}).

Corollary 2. The endomorphisms L and R are Lyndon morphisms, which preserve left and right standard factorizations.

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 ≥ 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 ≥ w′′ by Eq. (2). 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′) < f(w′′) by Eq. (1) and these two words are Lyndon words; moreover, we have f(v) ≥ f(w′′) and this implies by Eq. (2) 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_{1}x_{n}, so that, since x_{n} ≥ f(w′′), we have still the same right standard factorization.

The proof for left standard factorizations is quite similar.

2.3 Christoffel-Lyndon words

We define recursively Christoffel-Lyndon words^{3}: 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 standard factorization of w its left and right standard factorization, which are identical. We write it as w = w′w′′. We note that

w′ < w′′.  (4)

If w′ is not a letter, then

(w′)′′ ≥ w′′.  (5)

And if w′′ is not a letter, then

w′ ≥ (w′′)′.  (6)

Theorem 3. [10] On a totally ordered two-letter alphabet, Christoffel-Lyndon words and Christoffel words coincide.

Lemma 4. Let w be a Christoffel-Lyndon word on the alphabet {a < b}, with standard factorization w = w′w′′. If w′ = a, then w = a^{n}b. If w′′ = b, then w = ab^{n}.

3They are called équilibrés in [10], and balanced_{2} in [2]; since the word “balanced” has another precise meaning in classical combinatorics on words, we prefer to adopt another terminology.

Note that the words a^{n}b and ab^{n} are Christoffel-Lyndon words for any alphabet containing the letters a, b with a < b.

Proof. Suppose that w′ = a. If w′′ is a letter, then we must have w′′ = b by Eq. (4), 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. (6), (w′′)′ = a; by induction, w′′ = a^{n}b and we conclude the proof in this case.

Suppose that w′′ = b. Then the proof is similar, using Eq. (5).

Proof. (of Theorem 3) 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 [3, Definition 2 and Theorem 3.2], a Lyndon word which is the factor of some Sturmian sequence is a Christoffel word. Hence the two factors are Christoffel words. Next, in [5, Theorème 1], the authors show that each Christoffel word, which is not a letter, is uniquely the product of two Christoffel words (also see [3, Corollary 3.2]). 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 < 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 [2, Corollary 2.2]), L and R preserve Christoffel words.

We do not prove the claim here, since it is a particular case of Lemma 10, which will be proved independently.

2.4 n-tuples of relatively prime natural numbers

The following result is well-known when the alphabet X has 2 letters (see [1, 5]), and has been obtained for a 3-letter alphabet in [10]. Recall that the commutative image of a word w ∈ X^{∗}, X = {x_{1}, …, x_{n}}, is the n-tuple (n_{i})_{1≤i≤n} ∈ ℕ^{n}, where n_{i} is the number of occurrences of the letter x_{i} in w.

Theorem 5. Let X be the totally ordered alphabet {x_{1} < ⋯ < x_{n}}. The mapping from the set of Christoffel-Lyndon words on X into ℕ^{n}, associating to w its commutative image, is a bijection onto the set of n-tuples of relatively prime natural numbers.

The proof of the theorem will be done in Section 2.7.

Corollary 6. The number of Christoffel-Lyndon words of length l on an alphabet of cardinality n is equal to ∑_{d|l} μ(d)\binom{n−1+l/d}{n−1}.

In particular, it follows that, as is well-known, the number of Christoffel words of length 1 is 2, and when l > 1, it is ϕ(l), the number of integers i, relatively prime to l, with 1 ≤ i ≤ l. Indeed, ϕ(d) = ∑_{d|l} μ(d)l/d = ∑_{d|l} μ(d)(1 + l/d) = ∑_{d|l} μ(d)\binom{1+l/d}{1}; the first equality is well-known, and the second follows from ∑_{d|l} μ(d) = 0.

Proof. Let m_{l} denote this number. By Theorem 5 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^{4} 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} = ∑_{d|l} m_{l/d} = ∑_{d|l} m_{d}.

By Möbius inversion, we obtain the corollary.

For example, for an alphabet of cardinality 3, we have the following values of m_{l}, for l = 1, …, 10: 3,3,7,9,18,15,33,30,45,42. The corresponding Christoffel-Lyndon words on the alphabet {x < y < 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.

2.5 An Euclidean algorithm for n-tuples of natural numbers

We assume that n ≥ 2. We define a deterministic rewriting system on the set of n-tuples of real numbers by the following two rules:

• Rule L: if a_{1} > a_{n}, (a_{1}, …, a_{n}) →_{L} (a_{1} − a_{n}, a_{n}, a_{2}, …, a_{n−1});

• Rule R: if a_{1} ≤ a_{n}, (a_{1}, …, a_{n}) →_{R} (a_{1}, …, a_{n−1}, a_{n} − a_{1}).

Lemma 7. Suppose that (a_{1}, …, 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, …, 0). If moreover a_{i} > 0 for at least one i ∈ {2, …, n}, then the n-tuple obtained just before the first occurrence of (d, 0, …, 0) in the rewriting system is (d, 0, …, 0, d).

Note that the rewriting system stabilizes on the n-tuple (d, 0, …, 0), since only rule L can be applied to it.

4A composition is a tuple of positive integers; compositions of length n and of sum k are in bijection with subsets of {1, …, k − 1} of cardinality n − 1.

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}, …, a_{n}) ≠ (a_{1}, 0, …, 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} ≠ 0}). This proves the first assertion, since the gcd never changes.

Now suppose that a_{i} > 0 for at least one i ∈ {2, …, n}. Let (b_{1}, …, b_{n}) be the n-tuple preceding (d, 0, …, 0) in the rewriting system. If we had (b_{1}, …, b_{n}) →_{L} (d, 0, …, 0), then (b_{1} − b_{n}, b_{n}, b_{2}, …, b_{n−1}) = (d, 0, …, 0), so that (b_{1}, …, b_{n}) = (d, 0, …, 0), which contradicts the assumption of the lemma. Thus we have (b_{1}, …, b_{n}) →_{R} (d, 0, …, 0), so that (b_{1}, …, b_{n−1}, b_{n} − b_{1}) = (d, 0, …, 0). Thus b_{1} = d, b_{2} = … = b_{n−1} = 0 and b_{n} = d, which proves the lemma.

2.6 Two substitutions

We consider the two endomorphisms L, R of the free monoid {x_{1} < ⋯ < x_{n}}^{∗} introduced in Section 2.2.

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 ∘ R with LR(x_{1}) = L(x_{1}x_{n}) = x_{1}x_{n−1}, whereas RL maps x_{1} onto RL(x_{1}) = R(x_{1}) = x_{1}x_{n}.

For an n-tuple (a_{1}, …, a_{n}) of real numbers, we write (a_{1}, …, a_{n}) →_{W} (b_{1}, …, b_{n}) if (b_{1}, …, 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}, …, a_{n}) →_{LR} (b_{1}, …, b_{n}) means (a_{1}, …, a_{n}) →_{L} (c_{1}, …, c_{n}) →_{R} (b_{1}, …, b_{n}), so that (c_{1}, …, c_{n}) = (a_{1} − a_{n}, a_{n}, a_{2}, …, a_{n−1}) and (b_{1}, …, b_{n}) = (c_{1}, …, c_{n−1}, c_{n}−c_{1}) = (a_{1}−a_{n}, a_{n}, a_{2}, …, a_{n−2}, a_{n−1}− a_{1} + a_{n}).

Lemma 8. Let W ∈ {L, R}^{∗} and u, v ∈ {x_{1}, …, x_{n}}^{∗} be such that v = W (u) and |u|_{x_{1}} > 0. Then (|v|_{x_{1}}, …, |v|_{x_{n}}) →_{W} (|u|_{x_{1}}, …, |u|_{x_{n}}).

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 = T W′, where T = L or R. Define v′ = W′(u). Then by induction (|v′|_{x_{1}}, …, |v′|_{x_{n}}) →_{W′} (|u|_{x_{1}}, …, |u|_{x_{n}}).

Thus it remains to show that (|v|_{x_{1}}, …, |v|_{x_{n}}) →_{T} (|v′|_{x_{1}}, …, |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}}, …, |v|_{x_{n}}) →_{L} (|v′|_{x_{1}}, …, |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, …, n − 1 and |v|_{x_{n}} = |v′|_{x_{1}} + |v′|_{x_{n}}. Hence (|v|_{x_{1}}, …, |v|_{x_{n}}) →_{R} (|v′|_{x_{1}}, …, |v′|_{x_{n}}) since |v|_{x_{1}} = |v′|_{x_{1}} ≤ |v|_{x_{n}}.

Lemma 9. 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.

Proof. By Corollary 2, 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 2; 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) < f(v)f(u) = f(vu) and we conclude that w < 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.

Lemma 10. Let w be a Christoffel-Lyndon word on the alphabet {x_{1} < ⋯ < 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 ∈ {L, R}^{∗}

such that w = W (x_{1}x_{n}).

Note that we have n ≥ 2.

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_{1}x_{n} and the letters x_{i}, i = 1, …, n − 1 (resp., i = 2, …, n):

• Each letter ≠ x_{n} is in the image of L;

• Each letter ≠ x_{1} is in the image of R;

• If x_{1} does not appear in u, then L(u) is in the image of R (since L maps {x_{2}, …, x_{n}} into {x_{1}x_{n}, x_{2}, …, x_{n−1}}).

(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. 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_{1}x_{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_{1}x_{n}.

1.2.1: x_{1} appears in u. Then either u = x_{1} and w′ = x_{1}; or u begins by x_{1}x_{i}, i = 1, …, n and then w′ begins by x_{1}x_{j}, j = 1, …, n − 1; in both cases w′ < (w′′)′, contradicting Eq. (6).

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}, …, 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 > 1, then (w′′)′ begins by x_{i}, i = 2, …, n; thus w′ < (w′′)′,

contradicting Eq. (6).

2.2.2: w′′ is a letter. 2.2.2.1: w′′ ≠ 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, …, 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}, …, x_{n}, so that (w′)′′ = L(u′′) begins by x_{1}, …, x_{n−1}. Therefore (w′)′′ < w′′ and we reach a contradiction with Eq. (5).

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_{1}x_{n} is in the image of L. 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_{1}x_{i}, i = 1, …, n, so that w′′ begins by x_{1}x_{i},

i = 1, …, n−1; since w′ begins by x_{1}x_{n} or x_{j}, j = 2, …, n, we have w′′ < w′, a contradiction with Eq. (4).

1.2: v is a letter. Then v = x_{1}; in this case w′′ = x_{1} ≤ w′, a contradiction again. Case 2: x_{1} does not appear in v. Then w′′ is in the image of R.

(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_{1}x_{n} and we are done. 1.2: u ≠ 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 9.

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 ≠ 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 ∈ {x_{1}, x_{3}, …, x_{i}}^{∗}, hence u = L^{n−i}(v) with v ∈ {x_{1}, x_{3+n−i}, …, x_{n}}^{∗} and x_{1}, x_{n} appear in v.

2.2.2.1: v = x_{1}x_{n}. Then w = L^{1+n−i}(x_{1}x_{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 ∉ 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_{1}x_{n}) for some W ∈ {L, R}^{∗}, thus w = L^{1+n−i}W (x_{1}x_{n}) and we are done.

2.7 Proof of Theorem 5

Consider the set 𝕋_{n} of n-tuples (a_{1}, …, a_{n}) of relatively prime natural numbers such that a_{1} > 0 and that a_{i} > 0 for some i = 2, …, n. It is enough (by induction on n) to define a bijection from 𝕋_{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}, …, 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 𝕋_{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}, …, 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 2.5. It takes as input an n-tuple t = (a_{1}, …, a_{n}) in 𝕋_{n}; by Lemma 7, there exists a unique W ∈ {L, R}^{∗} such that t →_{W} (1, 0, … 0, 1) and we define w = W (x_{1}x_{n}). Then by Lemma 8, we have (|w|_{x_{1}}, …, |w|_{x_{n}}) →_{W} (1, 0, … 0, 1). Now, the rewriting system is clearly reversible (in the sense that t →_{W} u and t′ →_{W} u imply t = t′, see Lemma 22, which will be proved independently), so that we must have t = (|w|_{x_{1}}, …, |w|_{x_{n}}). Furthermore, x_{1}x_{n} is a Christoffel-Lyndon word, and so is w too, by Lemma 9.

Consider now any Christoffel-Lyndon word containing the letter x_{1} and at least another letter. Then by Lemma 10, there exists W ∈ {L, R}^{∗} such that W (x_{1}x_{n}) = w. Then, as above, (|w|_{x_{1}}, …, |w|_{x_{n}}) →_{W} (1, 0, … 0, 1), which shows that the algorithm outputs w on the input (|w|_{x_{1}}, …, |w|_{x_{n}}).

2.8 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 1, where n = 3, as in the three other figures, where the alphabet is {a < b < c}.

The second tree is obtained from the latter by interpreting each word W ∈ {L, R}^{∗} as the corresponding product of the substitutions L, R, written as the n-tuple (W (x_{1}), …, W (x_{n})). We call this tree the tree of standard n-tuples; see Figure 2. This tree generalizes the Christoffel tree of [3, p. 200], in the case n = 2. Moreover, it has been defined for n = 3 in [10].

The third tree is obtained from the latter by replacing each n-tuple (w_{1}, …, w_{n}) by the word w_{1}w_{n} = W (x_{1}x_{n}), which is a Christoffel-Lyndon word. We call this tree the tree of I L LL {LLL \atop LLR} LR {LRL \atop LRR} R

RL {RLL \atop RLR} RR {RRL \atop RRR}

Figure 1: The tree of L, R-words

a, b, c a, ac, b \begin{matrix}a, ab, ac & \begin{matrix}a, a^{2}c, ab \\ a^{2}c, ab, ac \end{matrix} \\ ab, ac, b & \begin{matrix}ab, ab^{2}, ac \\ ab^{2}, ac, b \end{matrix} \end{matrix} ac, b, c ac, ac^{2}, b_{\begin{matrix}ac, acb, ac^{2} \\ acb, ac^{2}, b \end{matrix}} ; ac^{2}, b, c_{\begin{matrix}ac^{2}, ac^{3}, b \\ ac^{3}, b, c \end{matrix}}

Figure 2: The tree of standard triples

Christoffel-Lyndon words. See Figure 3, where dotted edges have been added for later use.

The fourth tree is obtained by replacing in the latter each word w by the n-tuple (|w|_{x_{1}}, …, |w|_{x_{n}}). We call this tree the tree of n-tuples; see Figure 4. It generalizes the Stern-Brocot tree. Note that 𝕋_{n} is the set of nodes of this tree.

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}, …, a_{n}) by (a_{2}/a_{1}, …, a_{n}/a_{1}); see Figure 5 for the case n = 3.

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_{1}x_{n}) = w and t →_{W} (1, 0, …, 0, 1); this follows indeed from the previous section.

ac ab a^{2}c_{a^{2}b_{\begin{matrix}a^{3}c \\ a^{2}bab \end{matrix}} ; a^{2}cac_{\begin{matrix}a^{2}cab \\ a^{2}cacac \end{matrix}}} ; ab^{2}_{abac \begin{matrix}abab^{2} \\ abacac \end{matrix} ab^{3}_{\begin{matrix}ab^{2}ac \\ ab^{4} \end{matrix}}} \begin{matrix}ac^{2} \\ acb acac^{2}_{acacb acac^{2}ac^{2}} ; acb^{2}_{\begin{matrix}acbac^{2} \\ acb^{3} \end{matrix}} & ac^{3}_{ac^{2}b_{\begin{matrix}ac^{2}ac^{3} \\ ac^{2}b^{2} \end{matrix}} ; ac^{4}_{\begin{matrix}ac^{3}b \\ ac^{5} \end{matrix}}} \end{matrix} ; a ; \begin{matrix}b \\ c \end{matrix}

Figure 3: The tree of Christoffel-Lyndon words

1, 0, 1 ; 1, 1, 0 ; 2, 0, 1_{2, 1, 0_{\begin{matrix}3, 0, 1 \\ 3, 2, 0 \end{matrix}} ; 3, 0, 2_{\begin{matrix}3, 1, 1 \\ 4, 0, 3 \end{matrix}}} ; 1, 2, 0_{2, 1, 1_{\begin{matrix}2, 3, 0 \\ 3, 1, 2 \end{matrix}} ; 1, 3, 0_{\begin{matrix}2, 2, 1 \\ 1, 4, 0 \end{matrix}}} ; 1, 0, 2 ; 1, 1, 1_{2, 0, 3_{\begin{matrix}2, 1, 2 \\ 3, 0, 5 \end{matrix}} ; 1, 2, 1_{\begin{matrix}2, 1, 3 \\ 1, 3, 1 \end{matrix}}} ; 1, 0, 3_{1, 1, 2_{\begin{matrix}2, 0, 5 \\ 1, 2, 2 \end{matrix}} ; 1, 0, 4_{\begin{matrix}1, 1, 3 \\ 1, 0, 5 \end{matrix}}} ; 1,0,0 {0,1,0 \atop 0,0,1}

Figure 4: The tree of 3-tuples

0, 1 1, 0 0, 1/2_{1/2, 0_{\begin{matrix}0, 1/3 \\ 2/3, 0 \end{matrix}} ; 0, 2/3_{\begin{matrix}1/3, 1/3 \\ 0, 3/4 \end{matrix}}} ; 2, 0_{1/2, 1/2_{\begin{matrix}3/2, 0 \\ 1/3, 2/3 \end{matrix}} ; 3, 0_{\begin{matrix}1, 1/2 \\ 4, 0 \end{matrix}}} 0, 2 1, 1_{0, 3/2_{\begin{matrix}1/2, 1 \\ 0, 5/3 \end{matrix}} ; 2, 1_{\begin{matrix}1/2, 3/2 \\ 3, 1 \end{matrix}}} ; 0, 3_{1, 2_{\begin{matrix}0, 5/2 \\ 2, 2 \end{matrix}} ; 0, 4_{\begin{matrix}1, 3 \\ 0, 5 \end{matrix}}}

Figure 5: The generalized Stern-Brocot tree for nonvanishing pairs of nonnegative rational numbers

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}} ⋯ LR^{i_{k}}. Let N′ be the node attained after U on this path. Then N′ is called the 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 upward k-th left node from N.

For example, in the tree of Christoffel-Lyndon words (Figure 3) 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 3 or 4. 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}, …, 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.

Proposition 11. Let the alphabet be {x_{1}, …, 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.

As an example, see Figure 3: 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 [8, 2] (case n = 2) and is from [10] for n = 3.

Corollary 12. 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.

As an example with n = 3, on Figure 4, 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.

Lemma 13. Let 0 ≤ j ≤ n − 1. Then LR^{i_{j}} ⋯ LR^{i_{2}}LR^{i_{1}}(x_{n}) = x_{n−j} if j < n − 1, and = x_{1}x_{n} if j = n − 1.

Proof. This follows since R fixes x_{2}, …, x_{n}, since L(x_{k}) = x_{k−1} for k = 3, …, n and since L(x_{2}) = x_{1}x_{n}.

Proof. (of the Proposition) Let W ∈ {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_{1}x_{n}) and by Corollary 2, 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 ∈ {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_{1}x_{n}) = u) and we have W (x_{1}) = URL^{i}(x_{1}) = UR(x_{1}) = U(x_{1}x_{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 < n − 1 times. In the first case, we may write W = V LR^{i_{n−1}} ⋯ LR^{i_{2}}LR^{i_{1}} and V is the word downwards from the root corresponding to v (so that V (x_{1}x_{n}) = v); in the second case, we have W = LR^{i_{j}} ⋯ LR^{i_{2}}LR^{i_{1}} and v = x_{n−j}. Thus in the first case, by Lemma 13, W (x_{n}) = V (x_{1}x_{n}) = v. And in the second case, by the lemma, W (x_{n}) = x_{n−j} = v.

3 The order on tuples and a geometrical interpretation

The motivation of this section goes as follows. The alphabetical order of Christoffel words is equivalent to the order of their slopes [1, 5], where the slope of a Christoffel word w on the alphabet {x < y} is by definition the quotient |w|_{y}/|w|_{x}. Moreover, Christoffel words have a geometrical interpretation; an example is given in Figure 6. 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.

Figure 6: the Christoffel word xxxyxxyxxy of slope 3/7

3.1 The order on tuples

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

Lemma 14. Let the alphabet be {x_{1}, …, x_{n}}.

(i) Let u, v be Christoffel-Lyndon words containing the letter x_{1} and of length at least 2. Then L(u) < x_{1}x_{n} < R(v).

(ii) Let W, U, V ∈ {L, R}^{∗}. Then W LU(x_{1}x_{n}) < W (x_{1}x_{n}) < W RV (x_{1}x_{n}).

Proof. (i) We have u = x_{1}x_{i} ⋯, so that L(u) = x_{1}x_{j} with j < n. Thus L(u) < x_{1}x_{n}. Moreover, v = x_{1}x_{k} ⋯, so that R(v) = x_{1}x_{n}R(x_{k}) ⋯ > x_{1}x_{n}.

(ii) Let u = U(x_{1}x_{n}), v = V (x_{1}x_{n}). Then by Lemma 9, 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_{1}x_{n}) < x_{1}x_{n} < RV (x_{1}x_{n}). Thus (ii) follows, since W is order-preserving by Corollary 2.

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 5. The lemma implies the following result, which completely describes the order on 𝕋_{n}.

Proposition 15. 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} ≤ 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:

• rule L is applicable to t_{1} or t_{1} = (1, 0, …, 0, 1), and rule R is applicable to t_{2} or t_{2} = (1, 0, …, 0, 1);

• t_{1} →_{T} t′_{1}, t_{2} →_{T} t′_{2}, with T = L or R and t′_{1} ≤ t′_{2}.

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.

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_{1}x_{n}). Then by Lemma 8, t_{i} →_{W_{i}} (1, 0, …, 0, 1). Moreover, t_{1} ≤ t_{2} is equivalent to w_{1} ≤ 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} ≤ 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} = W RU or W_{1} = W, and W_{2} = W LV or W_{2} = W and moreover W_{1} = W = W_{2} does not hold. Then by Lemma 14, we reach the contradiction w_{2} < w_{1}. Thus (ii) must hold.

Suppose now that (ii) holds. Then we may write W_{1} = W LU or W_{1} = W, and W_{2} = W RV 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 8, t_{1} →_{LU} (1, 0, …, 0, 1) so that rule L is applicable to t_{1}; in the second case, t_{1} = (1, 0, …, 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 = T W′. One has either t_{1} →_{T} t′_{1} →_{W′LU} (1, 0, …, 0, 1), or t_{1} →_{T} t′_{1} →_{W′} (1, 0, …, 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} ≤ t′_{2} so that the second condition in (iii) holds.

Suppose now that (iii) holds. If the first condition holds, then, using Lemma 8, we see that w_{1} = L(u) or w_{1} = x_{1}x_{n}, and w_{2} = R(v) or w_{2} = x_{1}x_{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 14. Suppose that the second condition holds. If W_{1}, W_{2} are both nonempty, then by lemma 8 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} ≤ w′_{2}, so that w_{1} ≤ w_{2} since T preserves the order; then (i) holds. If W_{i} is empty, then t_{i} = (1, 0, …, 0, 1) and the only applicable rule is R, giving the tuple t′_{i} = (1, 0, …, 0). Since this tuple corresponds to the word x_{1}, which is the smallest Christoffel-Lyndon word, and since t′_{1} ≤ t′_{2}, we must have t′_{1} = (1, 0, …, 0). Thus t_{1} = (1, 0, …, 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} ≤ t_{2} by Lemma 14 (i), or W_{2} is the empty words and t_{1} = t_{2}. Thus (i) holds.

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 ≤ t′ if s ≤ s′, where s (resp., s′) is obtained from t (resp., t′) by dividing it by its gcd.

In other words, call slope of a nonvanishing tuple of natural numbers the unique proportional tuple of relatively prime natural numbers. Then we have t ≤ t′ if and only if s ≤ s′ where s, s′ are the slopes of t, t′.

We let 𝕋̄_{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.

Corollary 16. Let t_{1}, t_{2} be two n-tuples in 𝕋̄_{n}. Then t_{1} ≤ 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, …, 0, d) for some natural number d, and rule R is applicable to t_{2} (this includes the case t_{2} = (e, 0, …, 0, e) for some natural number e);

(ii) t_{1} →_{T} t′_{1}, t_{2} →_{T} t′_{2}, with T = L or R and t′_{1} ≤ t′_{2}.

Proof. Let s_{i} be the unique n-tuple in 𝕋_{n} proportional to t_{i}. Then t_{1} ≤ t_{2} if and only if s_{1} ≤ s_{2}; a rule is applicable to s_{i} if and only if its is applicable to t_{i}; s_{i} = (1, 0, …, 0, 1) if and only if t_{i} = (d, 0, …, 0, d). Moreover, condition (ii) is equivalent to the similar condition for the s_{i}’s. Hence the corollary follows from the proposition.

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 ∞. We do not know of a similar characterization of the order on n-tuples.

For later use, we prove the lemma below.

Lemma 17. Let t ∈ 𝕋̄_{n} and let e_{i} denote the canonical basis. Then t + e_{1} ≤ t ≤ t + e_{2} ≤ … ≤ t + e_{n} and t + e_{1} + e_{n} ≤ t + e_{2}.

Proof. For n = 2, this follows easily from the definition of the order recalled above: (a, b) ≤ (a′, b′) if and only if b/a ≤ 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) ≤ b/a ≤ (b + 1)/a and (b + 1)/(a + 1) ≤ (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 𝕋̄_{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}, …, 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}^{d}x_{2}, …, x_{1}^{d}x_{n} and x_{1}^{d+1}x_{n}, x_{1}^{d}x_{2}.

We associate to each t ∈ 𝕋̄_{n} the pair (l, m), its 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 ∈ {1, …, n − 1}. These pairs are ordered lexicographically and we prove the lemma by induction on this order.

Let t = (a_{1}, …, a_{n}). If a_{1} > a_{n}, then we have t + e_{1} = (a_{1} + 1, …, a_{n}) →_{L} (a_{1} − a_{n} + 1, a_{n}, a_{2}, …, a_{n−1}) and t →_{L} t′ = (a_{1} − a_{n}, a_{n}, a_{2}, …, a_{n−1}); then the two tuples on the righthand side of the arrows may be written, respectively, t′ + e_{1} and t′; then t′ ∈ 𝕋̄_{n}, with width (l′, m′) say; then either a_{n} > 0 and l′ < l, or a_{n} = 0, l′ = l and m′ < m; then we conclude by induction and Corollary 16 that t + e_{1} ≤ 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} ≤ t by Corollary 16. Finally, if a_{1} < a_{n}, the tuples t+e_{1} and t are rewritten under rule R into (a_{1} +1, a_{2}, …, a_{n} −a_{1} −1) and (a_{1}, a_{2}, …, a_{n}−a_{1}); these may be written as t′+e_{1} and t′+e_{n} with t′ = (a_{1}, a_{2}, …, a_{n}−a_{1}−1), so that we conclude either by induction (since a_{1} > 0, so that l decreases) and Corollary 16 that t + e_{1} ≤ t if t′ ∈ 𝕋̄_{n}, or by the claim otherwise (since if t′ ∉ 𝕋̄_{n}, we must have t′ = a_{1}e_{1} because its first component a_{1} is nonzero). This proves the first inequality in all cases.

We prove now that t ≤ 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}, …, a_{n−1}) and (a_{1} − a_{n}, a_{n}, a_{2} + 1, …, a_{n−1}), which may be written as t′ and t′ + e_{3}, t′ ∈ 𝕋̄_{n}, and we conclude by induction (here l in the width does not decrease, but m does). If a_{1} ≤ a_{n}, then rule R is applicable to both tuples, giving the tuples t′ = (a_{1}, a_{2}, …, a_{n} − a_{1}) and (a_{1}, a_{2} + 1, …, a_{n} − a_{1}). They may be written t′ and t′ + e_{2} and we conclude either by induction if t′ ∈ 𝕋̄_{n}, or by the claim otherwise.

We prove now that t+e_{i} ≤ t+e_{i+1} for 2 ≤ i ≤ 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}, …, a_{n−1}) and we conclude by induction. If a_{1} ≤ 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}, …, a_{n} − a_{1}) and we conclude by induction if t′ ∈ 𝕋̄_{n}, or by the claim otherwise.

We prove now that t+e_{n−1} ≤ 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}, …, a_{n−2}, a_{n−1}+1) and (a_{1}−a_{n}−1, a_{n}+1, …, 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}, …, a_{n−2}, a_{n−1}) ∈ 𝕋̄_{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} ≤ t + e_{n} by the corollary. If a_{1} ≤ 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}, …, a_{n} − a_{1}) and we conclude either by induction if t′ ∈ 𝕋̄_{n}, or by the claim otherwise.

It remains to prove that t + e_{1} + e_{n} ≤ 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}, …, a_{n−1}) and (a_{1} − a_{n}, a_{n}, a_{2} + 1, …, 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}, …, a_{n−1}) and we conclude by induction. If a_{1} ≤ a_{n}, then rule R is applicable to both tuples, giving the tuples (a_{1} + 1, a_{2}, …, a_{n} − a_{1}) and (a_{1}, a_{2} + 1, …, a_{n} − a_{1}), which may written t′ + e_{1} and t′ + e_{2}, and we conclude either by induction if t′ ∈ 𝕋̄_{n}, or by the claim otherwise.

3.2 A geometrical property of Christoffel-Lyndon words

We call slope of any word on the letters x_{1}, …, x_{n} the slope of the n-tuple (|w|_{x_{1}}, …, |w|_{x_{n}}), as defined in the previous section. Slopes are in bijection with Christoffel-Lyndon words (Theorem 5) and ordered as them.

Theorem 18. 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 ≤ than the slope of w and that it is maximum subject to this condition.

This result generalizes the geometrical interpretation of Christoffel words (see [1, 5]) recalled at the beginning of Section 3.

For any word w, let (w) denote its slope, considered as a Christoffel-Lyndon word. Hence,

(w) is the unique Christoffel-Lyndon word such that w and (w) have proportional commutative images. In particular, if w is a Christoffel-Lyndon word, then (w) = w. Observe also that (w) = (w′) if w′ is a rearrangement of w. For further use, note that by Lemma 17, for any word u, we have

(ux_{1}) ≤ (u) ≤ (ux_{2}) ≤ ⋯ ≤ (ux_{n}).  (7)

Lemma 19. If T is the substitution L or R, then (T (w)) = T ((w)) for any word w.

Proof. We know by Lemma 9 that T preserves Christoffel-Lyndon words; thus T ((w)) is a Christoffel-Lyndon word. Since (w) and w have proportional commutative images, so do T ((w)) and T (w). The lemma follows.

Lemma 20. If w = R(m) or w = L(m) and x_{j}x_{n} is a factor of w for some j satisfying 2 ≤ j ≤ n − 1, it is also a factor of m. Consequently, this cannot happen if w is on the tree of Christoffel-Lyndon words

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_{j}x_{n} must come from the same factor in m, since 2 ≤ j ≤ n − 1. The final assertion follows, since the root x_{1}x_{n} does not have the factor x_{j}x_{n}.

Proof. (of the theorem) We may assume that n ≥ 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. (7), it is enough to show that

(i) (v) ≤ w for each nontrivial prefix v of w;

(ii) if ux_{i} is a prefix of w, i < n, then (ux_{i+1}) > 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_{1}x_{n} and we are done, since (x_{1}) = x_{1} < x_{1}x_{n} and (x_{2}) = x_{2} > x_{1}x_{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 (p) ≤ m; thus (v) = (T (p)) = T ((p)) (by Lemma 19) ≤ 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_{1}x_{1}x_{n}v_{2} with v = v_{1}x_{1} and T (px_{j}) = v_{1}x_{1}x_{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 (p) ≤ m. Thus, as before, (v_{1}) = (T (p)) = T ((p)) ≤ T (m) = w. Since (v) = (v_{1}x_{1}) ≤ (v_{1}) by Eq. (7), we deduce that (v) ≤ w. This proves (i).

Suppose that T = R. Suppose that i = 1. Then ux_{1} is followed by x_{n} in w and ux_{1}x_{n} = R(px_{1}), with px_{1} a prefix of m and R(p) = u. By induction, (px_{2}) > m thus (ux_{2}) = (R(px_{2})) = R((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 (px_{i+1}) > m, which implies (ux_{i+1}) = (R(px_{i+1})) = R((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 (px_{3}) > m by induction and Eq. (7). Thus we deduce that (ux_{2}) = (L(px_{3})) = L((px_{3})) > L(m) = w which proves (ii) in this case.

Figure 7: Paths corresponding to the Christoffel-Lyndon words acbacbb and acbacc

Suppose now that ux_{i} is a prefix of w with i = 2, …, n − 2. Then px_{i+1} is prefix of m with L(p) = u; then by induction (px_{i+2}) > m and we deduce that (ux_{i+1}) = (L(px_{i+2})) = L((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_{j}x_{n−1} is a factor of w.

Suppose that j = n. Then m must have the factor x_{2}x_{n}, which is not possible by Lemma 20.

Suppose that 1 < j < n − 1. Then m must have x_{j+1}x_{n} as factor, which again is not possible by Lemma 20.

Thus j = 1 or n − 1 and we deduce by iterating this argument that ux_{n−1} = vx_{1}x_{n−1}^{r}, r ≥ 1, hence u = vx_{1}x_{n−1}^{r−1}.

Case 1: r = 1, that is vx_{1}x_{n−1} = ux_{n−1} is a prefix of w. Then px_{1}x_{n} is a factor of m, with L(p) = v. Then by induction (px_{2}) > m, thus (ux_{n}) = (vx_{1}x_{n}) = (L(px_{2})) = L((px_{2})) > L(m) = w, which proves (ii) in this case.

Case 2: r > 1. Then (ux_{n}) = (vx_{1}x_{n−1}^{r−1}x_{n}) = (vx_{1}x_{n}x_{n−1}^{r−1}) (by rearrangement) ≥ (vx_{1}x_{n}) (by Eq. (7) since n − 1 ≥ 2) > w, by the r = 1 case, since vx_{1}x_{n−1} is a prefix of w, because ux_{n−1} = vx_{1}x_{n−1}x_{n−1}^{r−1}.

4 The infinite algorithm: periodicity and convergence

We may apply the rewriting system of Section 2.5 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}, …, a_{n}), is infinite if one never obtains an n-tuple of the form (d, 0, …, 0). Equivalently, by Lemma 7, the n-tuple is not of the form α(b_{1}, …, b_{n}) for some real α and some integers b_{1}, …, b_{n}; equivalently, the ℚ-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 →_{W_{k}} t_{k} for some n-tuple t_{k}. Let w_{k} be the Christoffel-Lyndon word W_{k}(x_{1}x_{n}), where W_{k} is the corresponding substitution. In analogy with the case n = 2 (Christoffel words and continued fractions, see e.g., [2]), one is tempted to conjecture that for i = 2, …, n (we let | w |_{i} denote the number of x_{i}’s in the word w):

lim_{k→∞} \frac{| w_{k} |_{i}}{| w_{k} |_{1}} = \frac{a_{i}}{a_{1}} .  (8)

There is an equivalent statement, using incidence matrices. Recall that the incidence matrix (or commutative image) of the substitution f is defined to be the matrix (| f(x_{j}) |_{x_{i}} )_{1≤i,j≤n}. We take the same notation for a substitution and its incidence matrix. See the proof of Lemma 22 where the incidence matrices L and R are shown explicitly. Let

( α_{1}(k) ; ⋮ ; α_{n}(k) ) = W_{k} ( 1 0 ⋮ 0 1 ) .  (9)

Then the conjecture in Eq. (8)is equivalent to

lim_{k→∞} \frac{α_{i}(k)}{α_{1}(k)} = \frac{a_{i}}{a_{1}} .  (10)

We prove this conjecture in the case where W is ultimately periodic, that is, for some p > 0 and some k_{0} ≥ 0, one has w_{k} = w_{k+p} for any k ≥ k_{0}. In this case, we also obtain that the limits are algebraic numbers.

Theorem 21. Suppose that the algorithm applied to the n-tuple of nonnegative real numbers (a_{1}, …, a_{n}) generates the ultimately periodic infinite word W over the alphabet {L, R}. Then Eq. (8) and (10) hold and the limits are algebraic numbers belonging to the same number field of degree at most n.

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 8.

Lemma 22. Let W be a finite word over L, R such that (a_{1}, …, a_{n}) →_{W} (b_{1}, …, b_{n}). Then

( a_{1} ; ⋮ ; a_{n} ) = W ( b_{1} ; ⋮ ; b_{n} ) .

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

Proof. Let W = T V 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 →_{T} a′ →_{V} b. Then by induction, we have

( a′_{1} ; ⋮ ; a′_{n} ) = V ( b_{1} ; ⋮ ; b_{n} ) .

We claim that ^{t}a = T ^{t}a′. This implies that ^{t}a = T ^{t}a′ = T V ^{t}b = W ^{t}b, 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},…, a′_{n} = a_{n−1}. Moreover,

L = ( \begin{matrix}1 & 1 & 0 & … & 0 \\ 0 & 0 & 1 & ... & ⋮ \\ ⋮ & ⋮ & & ... & 0 \\ 0 & 0 & & & 1 \\ 0 & 1 & 0 & … & 0 \end{matrix} ) .

Thus

L ( a′_{1} ; ⋮ ; a′_{n} ) = ( a′_{1} + a′_{2} ; a′_{3} ; ⋮ ; a′_{n} ; a′_{2} ) = ( a_{1} ; a_{2} ; ⋮ ; a_{n−1} ; a_{n} ) .

If T = R, then a′_{i} = a_{i} for i = 1, …, n − 1 and a′_{n} = a_{n} − a_{1}. Moreover,

R = ( \begin{matrix}1 & 0 & … & … & 0 \\ 0 & 1 & ... & & ⋮ \\ ⋮ & 0 & ... & ... & ⋮ \\ 0 & & ... & 1 & 0 \\ 1 & 0 & … & 0 & 1 \end{matrix} ) .

Thus

R ( a′_{1} ; ⋮ ; a′_{n} ) = ( a′_{1} ; a′_{2} ; ⋮ ; a′_{n−1} ; a′_{1} + a′_{n} ) = ( a_{1} ; a_{2} ; ⋮ ; a_{n−1} ; a_{n} ) ,

which proves the claim.

Recall that a nonnegative square matrix is called 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 Perron eigenvalue of M. The latter is positive, simple and has maximum modulus among all eigenvalues of M; see [7, Theorem 2.6, p. 27]. The next result is certainly well-known.

Lemma 23. Let M be a primitive n by n matrix with m_{11} ≠ 0. Let α_{i}(k), i = 1, …, n denote n nonnegative sequences, with α_{1}(k) positive, such that

( α_{1}(k + 1) ; ⋮ ; α_{n}(k + 1) ) = M ( α_{1}(k) ; ⋮ ; α_{n}(k) )  (11)

and such that the limits in Eq. (10) 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 α_{1}(0), …, α_{n}(0).

Proof. Let l_{i}, i = 1, …, n, be these limits; note that l_{1} = 1. Let l = (1, 0, …, 0)M ( l_{1} ; ⋮ ; l_{n} ) =

∑_{j} m_{1j}l_{j}. Note that l > 0. We have

\frac{α_{i}(k + 1)}{α_{1}(k + 1)} = \frac{∑_{j} m_{ij}α_{j}(k)}{∑_{j} m_{1j}α_{j}(k)} = \frac{∑_{j} m_{ij} \frac{α_{j}(k)}{α_{1}(k)}}{∑_{j} m_{1j} \frac{α_{j}(k)}{α_{1}(k)}} .

Taking the limit, we obtain l_{i} = (1/l) ∑_{j} m_{ij}l_{j}. Thus

( l_{1} ; ⋮ ; l_{n} ) = (1/l)M ( l_{1} ; ⋮ ; l_{n} ) .

Since l_{1} = 1 and l_{i} ≥ 0, we have found a nonnegative eigenvector and 1/l is the Perron eigenvalue. Now note that if λ is an eigenvalue of M, then there is an eigenvector^{t}(a_{1}, …, a_{n}) for λ whose coefficients a_{i} are in the field generated by λ. By unicity of the nonnegative eigenvector, ^{t}(l_{1}, …, l_{n}) = ^{t}(1, a_{2}/a_{1}, …, a_{n}/a_{1}), which proves the lemma.

Lemma 24. Let M be a primitive matrix with Perron eigenvalue λ > 1 and consider a

matrix of the form A = ( \begin{matrix}M & B \\ 0 & I \end{matrix} ), 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 → ∞, 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.

Proof. It follows from the theorem of Perron that for some rank 1 matrix M′ one has M^{k} ∼ λ^{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 λ > 1. Now, one

has A^{k} = ( \begin{matrix}M^{k} & B_{k} \\ 0 & I \end{matrix} ), where B_{k} = ∑_{0≤i≤k−1} M^{i}B. We have ∑_{0≤i≤k−1} M^{i} ∼ \frac{λ^{k}}{λ−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} ∼ λ^{k}C for some positive matrix C = \frac{1}{λ−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 λ > 1, so that the coefficients of M^{k} and B_{k} tend to ∞, 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 exponential polynomial, which is a linear combination over ℂ of terms, each of which is of the form P (k)μ^{k}, where P (k) is a polynomial in k and μ 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}λ^{k} + a linear combination of P (k)μ^{k} with | μ |< λ. 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 μ’s with | μ |< λ^{2}. Since the exponential polynomials for (A^{k})_{i′j′} and (A^{k})_{i′j} both have a term with λ, 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.

Lemma 25. Let A(k), k ∈ ℙ, be a sequence of nonnegative n by n matrices taken from a finite set of matrices. Let M(k) = A(1) ⋯ A(k). Let (p_{k})_{k≥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, …, n}, the sequence M(p_{k})_{ij}/M(p_{k})_{1j} has a limit when k → ∞, independent of j. Then for any indices i, j in {1, …, n}, the sequence M(k)_{ij}/M(k)_{1j} has the same limit, independent of j.

Proof. 1. Suppose that f(k), g_{1}(k), …, 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, …, 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, …, 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}, …, a_{n}, not all 0, the sequence (a_{1}u_{1}(k)+…+a_{n}u_{n}(k))/(a_{1}v_{1}(k)+…+a_{n}v_{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)ϵ_{i}(k) where lim_{k→∞} ϵ_{i}(k) = 0. Then

\frac{a_{1}u_{1}(k) + … + a_{n}u_{n}(k)}{a_{1}v_{1}(k) + … + a_{n}v_{n}(k)}

= \frac{a_{1}lv_{1}(k) + … + a_{n}lv_{n}(k) + a_{1}v_{1}(k)ϵ_{1}(k) + … + a_{n}v_{n}(k)ϵ_{n}(k)}{a_{1}v_{1}(k) + … + a_{n}v_{n}(k)} = l + r(k),

where r(k) = ∑_{i} \frac{a_{i}v_{i}(k)ϵ_{i}(k)}{a_{1}v_{1}(k)+...+a_{n}v_{n}(k)} is bounded by ∑_{i} \frac{a_{i}v_{i}(k)ϵ_{i}(k)}{a_{i}v_{i}(k)} = ∑_{i} ϵ_{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} = ∑_{s} M(p_{k})_{is}h_{sj} and N(k)_{1j} = ∑_{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) ⋯ A(p_{k} + h); for fixed h, there are finitely many possible H’s. Hence we conclude using 1. and 4.

Lemma 26. Let A(k), k ∈ ℕ, be a sequence of nonnegative n by n matrices taken from a finite set of matrices. Let M(k) = A(1) ⋯ 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, …, 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{∑_{j} A(0)_{ij}l_{j}}{∑_{j} A(0)_{1j}l_{j}} .

Proof. We have

M′(k)_{ij}/M′(k)_{1j} = \frac{∑_{q} A(0)_{iq}M(k)_{qj}}{∑_{q} A(0)_{1q}M(k)_{qj}} = \frac{∑_{q} A(0)_{iq} \frac{M(k)_{qj}}{M(k)_{1j}}}{∑_{q} A(0)_{1q} \frac{M(k)_{qj}}{M(k)_{1j}}} .

Note that M′(k)_{1j} ≥ A(0)_{11}M(k)_{1j} > 0 for k large enough. The limit of this is clearly \frac{∑_{q} A(0)_{iq}l_{q}}{∑_{q} A(0)_{1q}l_{q}}. Note that the denominator is > 0, since A(0)_{11} > 0 and l_{1} = 1.

Let X = {x_{1}, …, x_{n}}. Let γ be the substitution γ = (x_{1}, x_{n}, x_{2}, …, x_{n−1}); note that γ^{n−1} is the identity.

Lemma 27. Let k > 0 and i_{1}, …, i_{k}, j_{1}, …, j_{k} > 0 and let f be the substitution f = R^{j_{k}}L^{i_{k}} ⋯ R^{j_{1}}L^{i_{1}} with i_{1} + ⋯ + i_{k} ≡ 0 (mod n − 1). Let S be the set of partial sums, S = {i_{k}, i_{k} + i_{k−1}, …, i_{k} + ⋯ + i_{1}}. Let Y = {x_{1}} ∪ {γ^{s}(x_{n}), s ∈ S}. Then

(i) x_{1}, x_{n} ∈ Y;

(ii) for any x ∈ Y, f(x) ∈ Y^{∗} and each y ∈ Y appears in f(x_{1}).

(iii) x_{1} appears in each f(x), x ∈ X;

(iv) for each x ∈ X \ Y, f(x) ∈ Y^{∗}x.

For example, if n = 5, let f = RL^{5}RL^{3}. Then Y = {x_{1}, γ^{5}(x_{5}), γ^{8}(x_{5})} = {x_{1}, x_{4}, x_{5}}. One verifies that (we write i instead of x_{i})

f = (15154, 15154152, 15154153, 15154154, 15155).

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^{j}L^{i} = (x_{1}x_{n}^{j}, (x_{1}x_{n}^{j})^{q+1}x_{n+1−s}, …, (x_{1}x_{n}^{j})^{q+1}x_{n}, (x_{1}x_{n}^{j})^{q}x_{2}, …, (x_{1}x_{n}^{j})^{q}x_{n−s}),

where i = s + (n − 1)q, s ∈ {1, …, n − 1}. This is proved as follows:

L = (x_{1}, x_{1}x_{n}, x_{2}, …, x_{n−1}), L^{s} = (x_{1}, x_{1}x_{n+1−s}, …, x_{1}x_{n}, x_{2}, …, x_{n−s}),
L^{n−1} = (x_{1}, x_{1}x_{2}, …, x_{1}x_{n}), L^{(n−1)q} = (x_{1}, x_{1}^{q}x_{2}, …, x_{1}^{q}x_{n}),
L^{i} = L^{s+(n−1)q} = (x_{1}, x_{1}^{q+1}x_{n+1−s}, …, x_{1}^{q+1}x_{n}, x_{1}^{q}x_{2}, …, x_{1}^{q}x_{n−s}),
R = (x_{1}x_{n}, x_{2}, …, x_{n}), R^{j} = (x_{1}x_{n}^{j}, x_{2}, …, 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_{1}x_{n}^{j}.

We claim now that for i_{1}, …, i_{k}, j_{1}, … j_{k} > 0, f = R^{j_{k}}L^{i_{k}} ⋯ R^{j_{1}}L^{i_{1}} is of the form f = (u_{1}, u_{2}γ^{I}(x_{2}), …, u_{n}γ^{I}(x_{n})) where I = i_{1} + ⋯ + i_{k} and each u_{h} is a word whose alphabet is a subset of

{x_{1}, x_{n}, γ^{i_{k}}(x_{n}), …, γ^{i_{k}+···+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 γ^{i} = γ^{s}, and γ^{s}(x_{2}) = x_{n+1−s}, …, γ^{s}(x_{n}) = x_{n−s}, we have

R^{j}L^{i} = (x_{1}x_{n}^{j}, (x_{1}x_{n}^{j})^{q+1}γ^{i}(x_{2}), …, (x_{1}x_{n}^{j})^{q}γ^{i}(x_{n})).

Suppose now it is true for k and let g = R^{j}L^{i}f. Then g(x_{1}) = R^{j}L^{i}(u_{1}); since the alphabet of u_{1} is as above, we see by the form of R^{j}L^{i}, that the alphabet of g(x_{1}) is {x_{1}, x_{n}, γ^{i}(x_{n}), γ^{i+i_{k}}(x_{n}), …, γ^{i+i_{k}+···+i_{2}}(x_{n})}. Next, g(x_{2}) = R^{j}L^{i}(u_{2}γ^{I}(x_{2})) = R^{j}L^{i}(u_{2})R^{j}L^{i}(γ^{I}(x_{2})); the alphabet of R^{j}L^{i}(u_{2}) is, similarly, a subset of the alphabet of g(x_{1}) = R^{j}L^{i}(u_{1}); moreover, R^{j}L^{i}(γ^{I}(x_{2})) is the product of a word on x_{1}, x_{n} by the letter γ^{i+I}(x_{2}), which shows that g(x_{2}) is of the required form. For the letters x_{3}, …, x_{n} the argument is similar.

Suppose now that i_{1} + ⋯ + i_{k} ≡ 0 (mod n − 1). Then we have

{x_{1}, x_{n}, γ^{i_{k}}(x_{n}), …, γ^{i_{k}+···+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 ≥ 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.

Corollary 28. Let f be as in Lemma 27. Then its incidence matrix has the following properties, for some subset I of {1, …, n} such that 1, n ∈ I:

(i) its first row is positive;

(ii) each e_{i}, i ∈ I, is sent to a linear combination of e_{j}, j ∈ 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.

As an example, the incidence matrix of f given after Lemma 27 is

( \begin{matrix}2 & 3 & 3 & 3 & 2 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 2 & 0 \\ 2 & 3 & 3 & 3 & 3 \end{matrix} )

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.

Proof. (of Theorem 21) Suppose first that the infinite word W is strictly periodic, of the form W = V^{∞} 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 28, 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 24. Thus the limits lim_{k→∞}(V^{k})_{ij}/V^{k})_{1j} exist and are independent of j. Hence, by Lemma 25, the limits lim_{k→∞}(W_{k})_{ij}/(W_{k})_{1j} exist and are independent of j.

Now take the notation of Eq. (9). It follows that the limits in Eq. (10) exist, since α_{i}(k) = (W_{k})_{i1} + (W_{k})_{in}, so that \frac{α_{i}(k)}{α_{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 25).

It follows from Lemma 23 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 27 is equal to the cardinality of Y, with the notation of this lemma.

To prove Eq. (10), it is enough to show that lim_{k→∞}(V^{k})_{i1}/V^{k})_{11} = a_{i}/a_{1}. Define a sequence of real row vectors by (a_{1}, …, a_{n}) →_{V^{k}} (b_{i}(k), …, b_{n}(k)). Using Lemma 22, we have

a_{i}/a_{1} − (V^{k})_{i1}/(V^{k})_{11} = \frac{∑_{j}(V^{k})_{ij}b_{j}(k)}{∑_{h}(V^{k})_{1h}b_{h}(k)} − \frac{(V^{k})_{i1}}{(V^{k})_{11}}

= \frac{∑_{j} b_{j}(k)((V^{k})_{ij}(V^{k})_{11} − (V^{k})_{i1}(V^{k})_{1j})}{(V^{k})_{11}(∑_{h}(V^{k})_{1h}b_{h}(k))}

= \frac{∑_{j} \frac{b_{j}(k)}{b_{1}(k)}((V^{k})_{ij}(V^{k})_{11} − (V^{k})_{i1}(V^{k})_{1j})}{(V^{k})_{11}(∑_{h}(V^{k})_{1h} \frac{b_{h}(k)}{b_{1}(k)})}

= ∑_{j} \frac{\frac{b_{j}(k)}{b_{1}(k)}((V^{k})_{ij}(V^{k})_{11} − (V^{k})_{i1}(V^{k})_{1j})}{(V^{k})_{11}(∑_{h}(V^{k})_{1h} \frac{b_{h}(k)}{b_{1}(k)})}.

In absolute value, this is bounded by

∑_{j} \frac{\frac{b_{j}(k)}{b_{1}(k)} | (V^{k})_{ij}(V^{k})_{11} − (V^{k})_{i1}(V^{k})_{1j} |}{(V^{k})_{11}(V^{k})_{1j} \frac{b_{j}(k)}{b_{1}(k)}} = ∑_{j} \frac{| (V^{k})_{ij}(V^{k})_{11} − (V^{k})_{i1}(V^{k})_{1j} |}{(V^{k})_{11}(V^{k})_{1j}}

The limit when k → ∞ of each term in the previous sum is 0, by Lemma 24. Thus Eq. (10) holds.

The general case, when W is ultimately periodic, follows from Lemma 26 and Lemma 22, since W may be written as W = UV^{∞}, 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.

5 Acknowledgments

We thank Valérie Berthé 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.

References

[1] J. Berstel. Tracé de droites, fractions continues et distances discrètes, in M. Lothaire, Mots: Mélanges Offerts à Schützenberger, Hermès, Paris, 1990, pp. 298–309.

[2] J. Berstel, A. Lauve, C. Reutenauer, and F. Saliola. Combinatorics on Words: Christoffel words and Repetitions in Words, CRM Monograph series, American Mathematical Society, 2008.

[3] J.-P. Berstel and A. de Luca. Sturmian words, Lyndon words and trees, Theoret. Comput. Sci. 178 (1997), 171–203

[4] V. Berthé, Multidimensional Euclidean algorithms, numeration and substitutions, Integers 11B (2011), Paper A2.

[5] J.-P. Borel and F. Laubie, Quelques mots sur la droite projective réelle, J. Théorie Nombres Bordeaux 5 (1993), 23–51.

[6] K. T. Chen, R. H. Fox, and R. C. Lyndon. Free differential calculus, IV. The quotient groups of the lower central series, Ann. Math. 68 (1958), 81–95.

[7] J. Ding and A. Zhou. Nonnegative Matrices, Positive Operators and Applications, World Scientific, 2009.

[8] R. L. Graham, D. Knuth, and O. Patashnik. Concrete Mathematics, Addison Wesley, 2nd edition, 1994.

[9] M. Lothaire. Combinatorics on Words, Addison Wesley 1983, 2nd edition, Cambridge University Press, 1997.

[10] G. Melançon. Visualisation de graphes et combinatoire des mots, Habilitation à diriger des recherches, Université de Bordeaux 1, 1999.

[11] G. Richomme. Lyndon morphisms, Bull. Belg. Math. Soc. Simon Stevin 10 (2003), 761–785.

[12] F. Schweiger. Multidimensional Continued Fractions, Oxford University Press, 2008.

[13] A. I. Širšov. Bases of free Lie algebras, Algebra i Logika 1 (1962), 14–19.

[14] G. Viennot. Algèbres de Lie Libres et Monoïdes Libres, Lecture Notes in Mathematics, Vol. 691, Springer, 1978.

2010 Mathematics Subject Classification: Primary 68R15, 11J70. Keywords: Christoffel word, Lyndon word, discretization, multidimensional continued fraction, Stern-Brocot tree, tuple of relatively prime numbers, algebraic number, periodic expansion.

Received March 26 2013; revised version received November 15 2013. Published in Journal of Integer Sequences, November 17 2013.

Return to Journal of Integer Sequences home page.