CHARACTERISATIONS OF BALANCED WORDS VIA ORDERINGS

Oliver Jenkinson and Luca Q. Zamboni

Queen Mary, University of London and University of North Texas

Abstract. Three new characterisations of balanced words are presented. Each of these characterisations is based on the ordering of a shift orbit, either lexicographically or with respect to the norm | · |_{1} (which counts the number of occurrences of the symbol 1).

1. Statement of Results

Sturmian^{1} sequences were first studied by Morse & Hedlund [MoHe] in the second of their fundamental papers on the symbolic coding of geodesic flows. Since then there have been numerous works dedicated to the study of Sturmian sequences and their generalisations from various points of view including combinatorics, number theory, ergodic theory and dynamical systems. Some of these are listed as references, while for a recent survey on the theory of Sturmian sequences we refer the reader to the chapter by J. Berstel and P. Séébold in [BeSe].

In this paper we study certain finite factors of Sturmian sequences which we call balanced words (see below for precise definitions). We obtain three new characterisations of balanced words in terms of different orderings on words. An unrelated connection between balanced words and the lexicographic ordering was recently studied by S. Gan [Ga], and later generalised by J. Justin and G. Pirillo [JuPi] to Arnoux-Rauzy words.

Throughout this article, ℕ will denote the set of non-negative integers. We begin by recalling some basic definitions concerning infinite words (or sequences) ω = ω_{0}ω_{1}ω_{2} … ∈ A^{ℕ} on a finite alphabet A. We say ω is periodic if there exists n ≥ 1 such that ω_{k} = ω_{k+n} for every k ≥ 0. In this case we say n is a period of ω. The least period of ω is the smallest such period. We say ω is eventually periodic if there exist n ≥ 1 and K ≥ 0 such that ω_{k} = ω_{k+n} for all k ≥ K. We say ω is aperiodic if it is not eventually periodic.

A length-m factor of ω is a finite subword ω_{j}ω_{j+1} … ω_{j+m−1}, for some j ∈ ℕ. We say ω is recurrent if each factor of ω occurs in ω an infinite number of times. It is easy to see that every recurrent sequence is either aperiodic or periodic. Finally, ω is said to be balanced if for each symbol a ∈ A and all pairs of factors u and v of ω of equal length, we have ||u|_{a} − |v|_{a}| ≤ 1, where |u|_{a} and |v|_{a} denote the number of occurrences of a in u

Typeset by AMS-TEX

Keywords: balanced, Sturmian, lexicographic order

1The nomenclature was originally motivated by a connection with differential equations.

and v respectively. Thus a recurrent balanced sequence is either periodic or aperiodic. A recurrent aperiodic balanced sequence in {0, 1}^{ℕ} is called a Sturmian sequence.

Henceforth we will restrict to the binary alphabet {0, 1}. Define {0, 1}^{∗∗} to be {0, 1}^{ℕ}∪ ∪_{q=0}^{∞}{0, 1}^{q}. We now introduce some terminology pertaining to finite words w ∈ {0, 1}^{q}. We say w is a Sturmian word if w is a factor of a Sturmian sequence. We say w is balanced if the periodic sequence w^{∞} = wwww ⋯ is balanced. Every balanced word is a Sturmian word but not conversely.

Example 1. The word 00101 is balanced, and hence Sturmian.

The word w = 001010 is Sturmian but is not balanced; the periodic sequence w^{∞} = www … has factors z = 101, z′ = 000, for which ||z|_{1} − |z′|_{1}| = 2.

The word 0011 is not Sturmian.

Define the shift σ : {0, 1}^{ℕ} → {0, 1}^{ℕ} by σ(ω)_{i} = ω_{i+1}. Similarly define σ : {0, 1}^{q} → {0, 1}^{q} by σ(w_{0} … w_{q−1}) = w_{1} … w_{q−1}w_{0}.

For any real number β ≥ 1, and any length-m word z = z_{0} … z_{m−1} ∈ {0, 1}^{m}, define

|z|_{β} = ∑_{k=0}^{m−1} z_{k}β^{m−k}.

We will refer to | · |_{β} as the β-norm, though strictly speaking it is not a norm. Define the order <_{β} on length-m words by

z <_{β} z′ if and only if |z|_{β} < |z′|_{β}.

Similarly

z =_{β} z′ if and only if |z|_{β} = |z′|_{β}.

We say z ≤_{β} z′ if and only if either z <_{β} z′ or z =_{β} z′. The choices β = 1 and β = 2 will be particularly important. Another ordering is the lexicographic ordering, denoted by <_{L}. We say z <_{L} z′ if and

only if there exists j = j(z, z′) ∈ {0, …, m − 1} such that z_{k} = z′_{k} for all k = 0, …, j − 1, and z_{j} < z′_{j}. We say z =_{L} z′ if and only if z = z′. We say z ≤_{L} z′ if and only if either z <_{L} z′ or z =_{L} z′.

The proof of the following result is easy, and is left as an exercise.

Lemma 1. Let m ∈ ℕ. The orderings <_{β} and <_{L} on {0, 1}^{m} are related by the following properties.

(1) If β ≥ 2 then the order <_{β} (resp. ≤_{β}) is the same as <_{L} (resp. ≤_{L}).

(2) If β ≥ 2 then z =_{β} z′ if and only if z = z′. In particular, this is the case for β = 2.

(3) If 1 ≤ β < 2 then there exist words z ≠ z′ such that |z|_{β} = |z′|_{β}. In particular, this is the case for β = 1.

Henceforth suppose p and q are positive integers, with p < q. For simplicity we will suppose p and q to be coprime, although suitable modifications of all our results hold without this assumption.

Definition. Suppose 1 ≤ p < q are positive integers such that gcd(p, q) = 1. Let W_{p,q} denote the set of all words w ∈ {0, 1}^{q} with |w|_{1} = p. If w ∈ W_{p,q} then the symbol 1 occurs with frequency \frac{p}{q} in w, so we say that \frac{p}{q} is the frequency of the word w.

Since gcd(p, q) = 1 then any element of W_{p,q} has least period q under the shift map σ. We will write w ∼ w′ if there exists 0 ≤ k ≤ q − 1 such that w′ = σ^{k}w. In this case we say that w, w′ are cyclically conjugate, or that w, w′ are cyclic shifts of one another. The equivalence class {σ^{i}w : 0 ≤ i ≤ q − 1} of each w ∈ W_{p,q} contains exactly q elements. Let

𝕎_{p,q} = W_{p,q}/ ∼

denote the corresponding quotient. Elements of 𝕎_{p,q} are called orbits. It will usually be convenient to denote an equivalence class in 𝕎_{p,q} by one of its elements w.

Remark. It is a well known fact (cf. [BuSe]; see also Proposition 1 and the Remark following it) that there are precisely q balanced words in W_{p,q}, all of which are in the same orbit. That is, there is a unique balanced orbit in each 𝕎_{p,q}.

Definition. Suppose v ∈ W_{p,q}. For 0 ≤ j ≤ q − 1, a length-(j + 1) factor of v is a factor of ω = v^{∞} of the form ω_{i}ω_{i+1} … ω_{i+j}, where 0 ≤ i ≤ q − 1. So the collection of length-(j + 1) factors of v has cardinality q (i.e. some of the factors might be the same but we count them with multiplicity). We will write

v^{(0)}(j) ≤_{1} v^{(1)}(j) ≤_{1} … ≤_{1} v^{(q−1)}(j)

to denote a ≤_{1}-ordering of this collection. Although such a ≤_{1}-ordering is not unique (see Example 2), the vector

N(v, j) = (|v^{(0)}(j)|_{1}, …, |v^{(q−1)}(j)|_{1})

and the partial sums

S(v, i, j) = ∑_{k=0}^{i} |v^{(k)}(j)|_{1}

are both well-defined (i.e. independent of the choice of ≤_{1}-ordering of the orbit of v).

Example 2. Let v = 0001011 ∈ W_{3,7}. If j = 4 then a 1-norm ordering of the length-(j + 1) factors of v is

00010 ≤_{1} 00101 ≤_{1} 01100 ≤_{1} 10001 ≤_{1} 11000 ≤_{1} 01011 ≤_{1} 10110 .

This ≤_{1}-ordering is not unique. For example an alternative is

00010 ≤_{1} 11000 ≤_{1} 01100 ≤_{1} 00101 ≤_{1} 10001 ≤_{1} 10110 ≤_{1} 01011 .

We have N(v, 4) = (1, 2, 2, 2, 2, 3, 3), and the partial sums S(v, i, 4) are given by

\begin{matrix}i : & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ S(v, i, 4) : & 1 & 3 & 5 & 7 & 9 & 12 & 15 \end{matrix}

Given 1 ≤ p < q with gcd(p, q) = 1, an elementary observation (see Lemma 7) is that for any 0 ≤ j ≤ q − 1, the final sum S(v, q − 1, j) (i.e. the sum of all entries in N(v, j)) is the same for every v ∈ W_{p,q}. The value of this sum is (j + 1)p. A natural problem, then, is to consider the possible values of the partial sums S(v, i, j) for 0 ≤ j < q − 1, as v varies over the set 𝕎_{p,q}. This leads us to our first characterisation of balanced words: the unique balanced orbit in 𝕎_{p,q} (we shall see that such an orbit always exists) is precisely the one which maximises every partial sum.

Theorem A. (Dominance of 1-norm partial sums)

Let w be a balanced word in W_{p,q} and v a non-balanced word in W_{p,q}. Then

S(w, i, j) ≥ S(v, i, j)

for all 0 ≤ i, j ≤ q − 1.

Moreover, there exist 0 ≤ i_{1}, j_{1} ≤ q − 1 such that

S(w, i_{1}, j_{1}) > S(v, i_{1}, j_{1}).

Example 3. The word v = 0001011 ∈ W_{3,7} is not balanced. The vector N(v, 4) = (1, 2, 2, 2, 2, 3, 3) and the partial sums S(v, i, 4) were computed in Example 2.

The word w = 0010101 ∈ W_{3,7} is balanced. A ≤_{1}-ordering of the length-5 factors of w is

00101 ≤_{1} 01001 ≤_{1} 01010 ≤_{1} 01010 ≤_{1} 10010 ≤_{1} 10100 ≤_{1} 10101 .

Therefore N(w, 4) = (2, 2, 2, 2, 2, 2, 3), and we can compare the partial sums of v and w:

\begin{matrix}i : & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ S(v, i, 4) : & 1 & 3 & 5 & 7 & 9 & 12 & 15 \\ S(w, i, 4) : & 2 & 4 & 6 & 8 & 10 & 12 & 15 \end{matrix}

We observe that S(w, i, 4) ≥ S(v, i, 4) for all i, and that S(w, i_{1}, 4) > S(v, i_{1}, 4) for various i_{1}, consistent with Theorem A.

Our second characterisation of balanced words involves a connection between the ≤_{1}- ordering and the lexicographic ordering.

Notation. Given an orbit [w] ∈ 𝕎_{p,q}, let

w_{(0)} <_{L} w_{(1)} <_{L} … <_{L} w_{(q−1)}  (1.1)

denote the lexicographic ordering of its elements. Define the lexicographic array A[w] of the orbit [w] to be the q × q matrix whose i^{th} row is w_{(i)}. We will index this array by 0 ≤ i, j ≤ q − 1, so that A[w] = (A[w]_{ij})_{i,j=0}^{q−1}.

For 0 ≤ i, j ≤ q − 1, let w_{(i)}[j] denote the length-(j + 1) prefix of w_{(i)}; so the w_{(i)}[j] are the length-(j + 1) factors of w, counted with multiplicity. For each j this induces the following lexicographic ordering:

w_{(0)}[j] ≤_{L} w_{(1)}[j] ≤_{L} … ≤_{L} w_{(q−1)}[j] .  (1.2)

Although the inequalities in (1.1) are all strict, since w_{(0)}, w_{(1)}, …, w_{(q−1)} are all distinct, in general the same is not true of (1.2).

Example 4. Consider again the balanced word w = 0100101 ∈ W_{3,7}. The lexicographic ordering of [w] is

0010101 <_{L} 0100101 <_{L} 0101001 <_{L} 0101010 <_{L} 1001010 <_{L} 1010010 <_{L} 1010100,

so that the corresponding lexicographic array is

A[w] = ( \begin{matrix}0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 \end{matrix} ) .

The lexicographic ordering w_{(0)}[4] ≤_{L} … ≤_{L} w_{(6)}[4] of the length-5 prefixes in the orbit [w] is

00101 ≤_{L} 01001 ≤_{L} 01010 ≤_{L} 01010 ≤_{L} 10010 ≤_{L} 10100 ≤_{L} 10101 .

We observe that this lexicographic ordering is also a ≤_{1}-ordering (coinciding with that of Example 3).

By contrast, let us next consider the non-balanced word v = 0001011, whose lexicographic array is

A[v] = ( \begin{matrix}0 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 & 0 \end{matrix} ) .

The lexicographic ordering v_{(0)}[4] ≤_{L} … ≤_{L} v_{(6)}[4] of the length-5 prefixes in the orbit [v] is

00010 ≤_{L} 00101 ≤_{L} 01011 ≤_{L} 01100 ≤_{L} 10001 ≤_{L} 10110 ≤_{L} 11000 .

This time the lexicographic ordering of the length-5 prefixes is not a ≤_{1}-ordering. For example 01011 <_{L} 01100, yet 01100 <_{1} 01011.

These observations, namely the coincidence (resp. non-coincidence) of lexicographic orderings and ≤_{1}-orderings for the balanced (resp. non-balanced) word, are manifestations of the following theorem.

Theorem B. (Compatibility of lexicographic and 1-norm orderings)

Suppose w ∈ {0, 1}^{q}. The following are equivalent:

(1) w is a balanced word,

(2) w_{(i)}[j] ≤_{1} w_{(i+1)}[j] for all 0 ≤ i ≤ q − 2 and 0 ≤ j ≤ q − 1 .

Our third characterisation of balanced words connects the lexicographic ordering to the dynamic ordering of the corresponding orbit. For general words w ∈ W_{p,q}, the relation between the dynamic ordering w, σw, … σ^{q−1}w and the lexicographic ordering w_{(0)} <_{L} w_{(1)} <_{L} … <_{L} w_{(q−1)} is not well understood; indeed we are not aware of any literature on this subject. The general problem is to understand the permutation π_{w} on the set {0, …, q − 1} defined by

w_{(i)} = σ^{π_{w}(i)}(w).

We call π_{w} the lexidynamic permutation for the word w.

Unlike lexicographic ordering, the notion of dynamic ordering is not quite well-defined on the orbit space 𝕎_{p,q}, due to the ambiguity in choosing equivalence class representatives. However, if w, w′ are in the same shift orbit, with w′ = σ^{k}(w), say, then

w′_{(i)} = w_{(i)} = σ^{π_{w}(i)}(w) = σ^{π_{w}(i)−k}(w′),

where π_{w}(i) − k is understood modulo k, so that the permutations π_{w} and π_{w′} are easily related. For consistency we shall therefore, unless stated otherwise, always choose the word w_{(0)}, which we call the lexicographically minimal representation, as the representative of its orbit.

Of course for any given word, the determination of the lexidynamic permutation is a finite problem, the obvious algorithm being to generate both the lexicographic and dynamic orderings, then simply compare them. The defect of this approach is twofold: on the one hand it is algorithmically inefficient, while on the other it is unlikely to yield any conceptual insight into the relation between dynamical and lexicographic orderings.

For balanced words, however, we can do much better; in this case the relation between dynamic and lexicographic orderings is completely understood. First we need a definition.

Definition. We say a word w ∈ {0, 1}^{q} has the lexicographic constant shift property if its lexidynamic permutation π_{w} is a power of the cyclic permutation (0, 1, …, q − 1) on {0, …, q − 1}; that is, if there exists an integer 𝔪 = 𝔪(w) ∈ {1, …, q − 1} such that

w_{(i)} = σ^{i𝔪}w_{(0)} for all 0 ≤ i ≤ q − 1.

We call 𝔪 = 𝔪(w) the lexicographic shift constant associated to w; if it exists then it is clearly unique, and is relatively prime to q.

Example 5. Consider the balanced word w = 0010101. This word is the lexicographically minimal representation of its orbit. From the lexicographic ordering in Example 4 we see that w has the lexicographic constant shift property, with lexicographic shift constant 𝔪(w) = 5.

The non-balanced word v = 0001011 is also the lexicographically minimal representation of its orbit. Its lexidynamic permutation π_{v} is given by

( \begin{matrix}0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 0 & 1 & 2 & 4 & 6 & 3 & 5 \end{matrix} ) ,

which is not a power of a cyclic permutation. Hence v does not have the lexicographic constant shift property.

It turns out that the words with the lexicographic constant shift property are precisely the balanced words, and that moreover there is a simple formula for the associated lexicographic shift constant. This is the content of the following theorem.

Theorem C. (The lexicographic constant shift property)

A word w ∈ W_{p,q} is balanced if and only if it has the lexicographic constant shift property. Moreover the lexicographic shift constant 𝔪(w) is defined by the congruence 𝔪(w) p ≡ 1 (mod q); that is, 𝔪(w) is the multiplicative inverse of p modulo q.

The organisation of this article is as follows. Section 2 consists of some preparatory material on balanced words. Theorem A is proved in Section 3, while Theorem B is proved in Section 4. Section 5 is devoted to the proof of Theorem C, and to a study of the fine structure of the lexicographic array of a balanced orbit. This structure is described in Theorem D, and readily leads to the proof of Theorem C.

2. Balanced words

This section is preparatory. We begin by introducing notation, then go on to show (Proposition 1 and the Remark following it) that for each pair of positive integers 1 ≤ p < q with gcd(p, q) = 1, there exists a unique balanced orbit in 𝕎_{p,q}. In other words, if w, w′ ∈ W_{p,q} are balanced, then they are necessarily cyclic permutations of one another. This result is well known (see [BuSe] for example), though our proof appears to be new. We then examine more closely the unique balanced orbit in 𝕎_{p,q}. We organise our ideas around a particular word in this orbit, the post-minimal balanced word w_{p,q}, which plays a central rôle in our later proof of Theorem C.

Notation. Throughout this section, whenever we write a positive rational number in the form \frac{p}{q}, we understand that the integers p and q are both positive and gcd(p, q) = 1. For instance, if \frac{p}{q} = 0 · 2 then p = 1 and q = 5.

A rational number \frac{p}{q} < 1 has exactly two possible continued fraction expansions. The number of digits in these expansions are j and j + 1, for some j ∈ ℕ. To remove this ambiguity we will always choose the continued fraction expansion with an even number of digits. More precisely, there exists a unique k ∈ ℕ and unique positive integers n_{0}, n_{1}, …, n_{2k+1} such that

\frac{p}{q} = \frac{1}{n_{0} + \frac{1}{n_{1} + \frac{1}{n_{2} + \frac{1}{⋯ \frac{1}{n_{2k+1}.}}}}}

We call this the even length continued fraction expansion of \frac{p}{q}, and henceforth write it as \frac{p}{q} = [n_{0}, n_{1}, …, n_{2k+1}]

For any \frac{p}{q} = [n_{0}, n_{1}, …, n_{2k+1}] ≠ \frac{1}{2} we define its predecessor \frac{p′}{q′} by:

\frac{p′}{q′} = \{ \begin{matrix}[n_{0} − 1, n_{1}, n_{2}, …, n_{2k+1}] & if 0 < \frac{p}{q} < \frac{1}{2} \\ [n_{0}, n_{1} − 1, n_{2}, …, n_{2k+1}] & if \frac{1}{2} < \frac{p}{q} < 1 with n_{1} ≥ 2 \\ [n_{2} + 1, n_{3}, …, n_{2k+1}] & if \frac{1}{2} < \frac{p}{q} < 1 with n_{1} = 1. \end{matrix}

Note that if \frac{1}{2} < \frac{p}{q} < 1 with n_{1} = 1 then necessarily 2k + 1 ≥ 3.

A straightforward computation gives:

Lemma 2. If \frac{p}{q} ≠ \frac{1}{2} has predecessor \frac{p′}{q′} then

\frac{p}{q} = \{ \begin{matrix}\frac{p′}{p′+q′} & if 0 < \frac{p}{q} < \frac{1}{2} \\ \frac{q′}{2q′−p′} & if \frac{1}{2} < \frac{p}{q} < 1. \end{matrix}

Alternatively, we have \frac{p′}{q′} = f(\frac{p}{q}) where

f(x) = \{ \begin{matrix}\frac{x}{1−x} & if x ∈ (0, \frac{1}{2}) \\ \frac{2x−1}{x} & if x ∈ (\frac{1}{2}, 1) \end{matrix}

Since by assumption gcd(p′, q′) = 1, it follows that gcd(p′, p′+q′) = gcd(q′, 2q′−p′) = 1. In other words the above expressions give both p and q as functions of p′ and q′. It is easy to see that in each case q′ < q. Some of the results that follow will be proved by induction on the integer q, and hence the inductive hypothesis will be applied to the integer q′.

Definition. Define the morphisms τ_{0}, τ_{1} : {0, 1}^{∗∗} → {0, 1}^{∗∗} by

τ_{0} : \{ \begin{matrix}0 ↦ 0 \\ 1 ↦ 01 \end{matrix} τ_{1} : \{ \begin{matrix}0 ↦ 10 \\ 1 ↦ 1 \end{matrix} .

That is (cf. [BeSe]), τ_{0} = φ ∘ E and τ_{1} = E ∘ φ where E is the exchange morphism 0 ↦ 1, 1 ↦ 0, and φ is the Fibonacci morphism 0 ↦ 01, 1 ↦ 0.

Then for any positive integers p, q with 1 ≤ p < q and gcd(p, q) = 1, we define the post-minimal balanced word w_{p,q} ∈ {0, 1}^{∗∗} by

w_{p,q} = τ_{0}^{n_{0}−1} ∘ τ_{1}^{n_{1}} ∘ τ_{0}^{n_{2}} ∘ ⋯ ∘ τ_{1}^{n_{2k+1}}(0),

where \frac{p}{q} = [n_{0}, n_{1}, n_{2}, …, n_{2k+1}] is the even length continued fraction expansion.

The reason for calling w_{p,q} post-minimal and balanced will become apparent later. In Proposition 1 we will show that w_{p,q} belongs to W_{p,q} and is indeed balanced. In Lemma 6 we will show that w_{p,q} is the shift image of the lexicographically minimal word in the unique balanced orbit in 𝕎_{p,q}.

This definition of w_{p,q} immediately gives:

Lemma 3. If \frac{p′}{q′} is the predecessor of \frac{p}{q} ≠ \frac{1}{2} then

w_{p,q} = \{ \begin{matrix}τ_{0}(w_{p′,q′}) & if 0 < \frac{p}{q} < \frac{1}{2} \\ τ_{1}(w_{p′,q′}) & if \frac{1}{2} < \frac{p}{q} < 1 . \end{matrix}

The first important property of the post-minimal balanced word w_{p,q} is the following.

Proposition 1. Let p, q be positive integers with 1 ≤ p < q and gcd(p, q) = 1. Then w_{p,q} is a balanced word in W_{p,q}.

Proof. It is a basic fact that the morphisms τ_{i} preserve balance. That is, a {0, 1}-word u is balanced if and only if τ_{i}(u) is balanced (see [BeSe], Proposition 2.3.1). Since w_{p,q} is defined by applying a certain composition of these morphisms to the balanced word 0, it follows that w_{p,q} is itself balanced.

It remains to show that w_{p,q} belongs to W_{p,q}. Our proof of this will be by induction on q.

First consider the case \frac{p}{q} = \frac{1}{2} = [1, 1]. Here we have w_{1,2} = τ_{1}(0) = 10, which is clearly an element of W_{1,2}, as required.

Next suppose \frac{p}{q} ≠ \frac{1}{2}, and let \frac{p′}{q′} be the predecessor of \frac{p}{q}, where 1 ≤ p′ < q′ and gcd(p′, q′) = 1. Since q′ < q, we will take our inductive hypothesis to be that w_{p′,q′} ∈ W_{p′,q′}, and show that this implies w_{p,q} ∈ W_{p,q}.

If 0 < \frac{p}{q} < \frac{1}{2} then Lemma 3 gives

w_{p,q} = τ_{0}(w_{p′,q′}),

so by definition of τ_{0}, and from Lemma 2, we have

|w_{p,q}|_{1} = |w_{p′,q′}|_{1} = p′ = p

and

|w_{p,q}| = |w_{p,q}|_{0} + |w_{p,q}|_{1} = |w_{p′,q′}| + |w_{p′,q′}|_{1} = q′ + p′ = q,

so indeed w_{p,q} ∈ W_{p,q}.

If \frac{1}{2} < \frac{p}{q} < 1 then Lemma 3 gives

w_{p,q} = τ_{1}(w_{p′,q′}),

so by definition of τ_{1} we have

|w_{p,q}|_{1} = |w_{p′,q′}| = q′ = p

and

|w_{p,q}| = |w_{p,q}|_{0} + |w_{p,q}|_{1} = |w_{p′,q′}|_{0} + |w_{p′,q′}| = (q′ − p′) + q′ = 2q′ − p′ = q,

and as before we see that w_{p,q} ∈ W_{p,q}. □

Remark. Using the morphisms τ_{i} and induction on q, it is easy to see that if w is a balanced word in W_{p,q} then w is a cyclic permutation of w_{p,q}. Consequently the orbit set 𝕎_{p,q} contains one and only one balanced orbit. This orbit consists of precisely q points, since gcd(p, q) = 1.

Example 6. For \frac{p}{q} = \frac{3}{7}, the even length continued fraction expansion is \frac{p}{q} = \frac{3}{7} = [2, 3].

Therefore its predecessor is \frac{p′}{q′} = [1, 3] = \frac{3}{4}. Hence w_{3,7} = τ_{0} ∘ τ_{1}^{3}(0) = τ_{0}(1110) = 0101010.

The following lemma gives more information on the structure of the post-minimal balanced word w_{p,q}. We first need some definitions.

Definitions. A {0, 1}-word x is called Sturmian left special (resp. Sturmian right special) if there exists a Sturmian sequence ω such that 0x and 1x (resp. x0 and x1) are both factors of ω. We say x is Sturmian bispecial if there exists a Sturmian sequence ω such that 0x, 1x, x0, and x1 are each factors of ω.

A Sturmian sequence ω ∈ {0, 1}^{ℕ} is called characteristic if each prefix ω_{0}ω_{1} … ω_{n} is left special. For any α ∈ [0, 1] \ ℚ, it is well known that there is a unique characteristic Sturmian sequence of frequency α (where the frequency of a Sturmian sequence ω is defined to be lim_{n→∞} \frac{1}{n}|ω_{0} … ω_{n−1}|_{1}).

The mirror image of a {0, 1}-word x = x_{0} … x_{n} is the word x̃ defined by x̃_{i} = x_{n−i}. We say that x is a palindrome if x̃ = x.

Lemma 4. Let 1 ≤ p < q be positive integers with gcd(p, q) = 1. Then

w_{p,q} = x10

where x is a Sturmian bispecial word.

In particular the word x is a palindrome.

Proof. It is a basic fact that all Sturmian bispecial words are palindromes, and that if x is a bispecial Sturmian word (or the empty word), then both τ_{0}(x)0 and τ_{1}(x)1 are Sturmian bispecial (see [BeSe], Propositions 2.1.19 and 2.1.23). The result will now follow by induction on q.

If \frac{p}{q} = \frac{1}{2}, then w_{1,2} = 10 and hence the result holds with x the empty word.

If \frac{p}{q} ≠ \frac{1}{2} then it has a predecessor \frac{p′}{q′}. As inductive hypothesis let us suppose we can write w_{p′,q′} = x′10 with x′ either empty or Sturmian bispecial. If 0 < \frac{p}{q} < \frac{1}{2} then Lemma 3 gives

w_{p,q} = τ_{0}(w_{p′,q′}) = τ_{0}(x′10) = τ_{0}(x′)010,

and as noted above τ_{0}(x′)0 is Sturmian bispecial. Similarly if \frac{1}{2} < \frac{p}{q} < 1 then

w_{p,q} = τ_{1}(w_{p′,q′}) = τ_{1}(x′10) = τ_{1}(x′)110,

and τ_{1}(x′)1 is Sturmian bispecial, as required. □

Example 7. For \frac{p}{q} = \frac{3}{7} we have w_{3,7} = 0101010 from Example 6, and in this case x = 01010.

Notation. Given a {0, 1}-word x = x_{0} … x_{n}, where x_{n} ∈ {0, 1}, we will write x_{n}xx_{n}^{−1} to denote the word x_{n}x_{0} … x_{n−1}.

We will need the following lemma of Pirillo [Pir2] (see also the earlier [Pir1]).

Lemma 5. [Pir2] Let x ∈ {0, 1}^{n} for some n ∈ ℕ. Then 0x1 is cyclically conjugate to 1x0 if and only if x is Sturmian bispecial.

We are now ready to justify calling w_{p,q} the post-minimal balanced word: the following result characterises it as the shift image of the lexicographically minimal point in the unique balanced orbit of frequency \frac{p}{q}.

Proposition 6. Let 1 ≤ p < q be positive integers with gcd(p, q) = 1. Let

w_{(0)} <_{L} w_{(1)} <_{L} ⋯ <_{L} w_{(q−1)}

be the lexicographic ordering of the unique balanced orbit in 𝕎_{p,q}.

If we write w_{p,q} = x10, where x is Sturmian bispecial then

w_{(0)} = 0x1  and  w_{(q−1)} = 1x0.

In particular,

w_{p,q} = σ(w_{(0)}).

Moreover, w_{(0)} and w_{(q−1)} are mirror images of one another, i.e., w̃_{(0)} = w_{(q−1)}.

Proof. First observe that 0x1 = 0w_{p,q}0^{−1} = σ^{−1}(w_{p,q}) is a cyclic shift of w_{p,q} since w_{p,q} ends in 10, by Lemma 4. From Lemma 5 we deduce that 1x0 is a cyclic shift of 0x1, and hence of w_{p,q}.

We will next show that 0x1 = 0w_{p,q}0^{−1} is the lexicographically smallest cyclic shift of w_{p,q}. The proof that 1x0 is the largest cyclic shift of w_{p,q} is almost identical, and is left as an exercise for the reader.

The periodic sequence generated by the word w_{p,q} can be written as the infinite composition

w_{p,q}^{∞} = lim_{n→∞} τ_{0}^{n_{0}−1} ∘ τ_{1}^{n_{1}} ∘ τ_{0}^{n_{2}} ∘ ⋯ ∘ τ_{1}^{n_{2k+1}} ∘ τ_{0}^{n}(1).

To prove that 0w_{p,q}0^{−1} is the lexicographic smallest cyclic shift of w_{p,q} it suffices to show that

0w_{p,q}^{∞} = (0w_{p,q}0^{−1})^{∞} ≤_{L} σ^{i}(0w_{p,q}^{∞})

for each i ≥ 1. Suppose to the contrary that for some i ≥ 1 we had 0w_{p,q}^{∞} >_{L} σ^{i}(0w_{p,q}^{∞}). Then there exists a word u (possibly empty) such that 0u1 is a prefix of 0w_{p,q}^{∞} and 0u0 a prefix of σ^{i}(0w_{p,q}^{∞}). It follows that there exists a prefix U of w_{p,q}^{∞} which begins in u1 and contains 0u0 as a subfactor. It is well known (see Proposition III.7 in [RiZa] for example) that for each n the word τ_{0}^{n_{0}−1} ∘ τ_{1}^{n_{1}} ∘ τ_{0}^{n_{2}} ∘ ⋯ ∘ τ_{1}^{n_{2k+1}} ∘ τ_{0}^{n}(1) is a prefix of a characteristic Sturmian sequence, and therefore each prefix of w_{p,q}^{∞} is a prefix of some characteristic Sturmian sequence. Hence there exists a characteristic Sturmian sequence ω beginning in U and hence in u1. Since each prefix of ω is left special, we deduce that both 1u1 and 0u0 are factors of ω, contradicting the fact that ω is balanced. Hence 0w_{p,q}^{∞} is less than or equal to all of its shifts, as required. □

Example 8. For \frac{p}{q} = \frac{3}{7} we have seen that w_{3,7} = 0101010 = x10, where x = 01010. Now w_{(0)} = 0010101, w_{(q−1)} = 1010100 (cf. Example 4). So indeed w_{(0)} = 0x1, w_{(q−1)} = 1x0, and w_{3,7} = σ(w_{(0)}), consistent with Proposition 6.

3. Proof of Theorem A

We first collect together some obvious facts, which the reader will easily verify.

Lemma 7. Suppose w ∈ W_{p,q}. Let A[w] = (A[w]_{ij})_{i,j=0}^{q−1} be the corresponding lexicographic array. Then

(1) The sum of the entries in any row of A[w] is p,

(2) The sum of the entries in any column of A[w] is p,

(3) S(w, q − 1, j) = (j + 1)p for every 0 ≤ j ≤ q − 1,

(4) ∑_{k=0}^{q−1} |w_{(k)}[j]|_{1} = (j + 1)p for every 0 ≤ j ≤ q − 1.

We are now ready to prove Theorem A. For convenience we first recall its statement.

Theorem A. (Dominance of 1-norm partial sums)

Let w be a balanced word in W_{p,q} and v a non-balanced word in W_{p,q}. Then

S(w, i, j) ≥ S(v, i, j)

for all 0 ≤ i, j ≤ q − 1.

Moreover, there exist 0 ≤ i_{1}, j_{1} ≤ q − 1 such that

S(w, i_{1}, j_{1}) > S(v, i_{1}, j_{1}).

Proof of Theorem A. Suppose w ∈ W_{p,q} is balanced, and v ∈ W_{p,q} is non-balanced. We will first show that S(w, i, j) ≥ S(v, i, j) for all 0 ≤ i, j ≤ q − 1. If the result is false then there exist 0 ≤ i_{0}, j_{0} ≤ q − 1 such that S(w, i_{0}, j_{0}) < S(v, i_{0}, j_{0}). If w^{(0)}(j_{0}) ≤_{1} … ≤_{1} w^{(q−1)}(j_{0}) is any ≤_{1}-ordering of the length-(j_{0} + 1) factors of w, and v^{(0)}(j_{0}) ≤_{1} … ≤_{1} v^{(q−1)}(j_{0}) is any ≤_{1}-ordering of the length-(j_{0} + 1) factors of v, this means that

∑_{k=0}^{i_{0}} |w^{(k)}(j_{0})|_{1} < ∑_{k=0}^{i_{0}} |v^{(k)}(j_{0})|_{1}.  (3.1)

We may suppose that i_{0} is chosen as small as possible, in the sense that

∑_{k=0}^{i} |w^{(k)}(j_{0})|_{1} ≥ ∑_{k=0}^{i} |v^{(k)}(j_{0})|_{1} for all i < i_{0}.  (3.2)

Taking i = i_{0} − 1 in (3.2), and subtracting from (3.1), we obtain

|w^{(i_{0})}(j_{0})|_{1} ≤ |v^{(i_{0})}(j_{0})|_{1} − 1.  (3.3)

Now w is balanced, so there exists N_{j_{0}} such that |w^{(k)}(j_{0})|_{1} equals either N_{j_{0}} or N_{j_{0}} +1 for all 0 ≤ k ≤ q − 1. Thus

|w^{(k)}(j_{0})|_{1} ≤ |w^{(i_{0})}(j_{0})|_{1} + 1 for all k > i_{0}.  (3.4)

By definition of ≤_{1} we know that

|v^{(i_{0})}(j_{0})|_{1} ≤ |v^{(k)}(j_{0})|_{1} for all k > i_{0}.  (3.5)

Combining (3.3), (3.4) and (3.5) gives

|w^{(k)}(j_{0})|_{1} ≤ |v^{(k)}(j_{0})|_{1} for all k > i_{0}.

Hence

∑_{k=i_{0}+1}^{q−1} |w^{(k)}(j_{0})|_{1} ≤ ∑_{k=i_{0}+1}^{q−1} |v^{(k)}(j_{0})|_{1}.  (3.6)

Combining (3.1) and (3.6) gives

∑_{k=0}^{q−1} |w^{(k)}(j_{0})|_{1} < ∑_{k=0}^{q−1} |v^{(k)}(j_{0})|_{1}.

This is a contradiction, since by part (3) of Lemma 7 we know that

∑_{k=0}^{q−1} |w^{(k)}(j_{0})|_{1} = S(w, q − 1, j_{0}) = (j_{0} + 1)p = S(v, q − 1, j_{0}) = ∑_{k=0}^{q−1} |v^{(k)}(j_{0})|_{1}.

This contradiction completes the proof of the first part of Theorem A.

The proof of the second part will also be by contradiction. Let us suppose that there do not exist 0 ≤ i_{1}, j_{1} ≤ q − 1 for which S(w, i_{1}, j_{1}) > S(v, i_{1}, j_{1}). In view of the first part of the theorem this means that S(w, i, j) = S(v, i, j) for all 0 ≤ i, j ≤ q − 1. Consequently

|w^{(i)}(j)|_{1} = |v^{(i)}(j)|_{1} for all 0 ≤ i, j ≤ q − 1  (3.7)

where w^{(0)}(j) ≤_{1} … ≤_{1} w^{(q−1)}(j) and v^{(0)}(j) ≤_{1} … ≤_{1} v^{(q−1)}(j) are any choices of ≤_{1}-orderings.

However v is not balanced, so we can find some 0 ≤ j_{0} ≤ q − 1, and some 0 ≤ i_{0} < i′_{0} ≤ q − 1 such that |v^{(i′_{0})}(j_{0})|_{1} ≥ v^{(i_{0})}(j_{0})|_{1} + 2. Now w is balanced, so there exists N_{j_{0}} such that |w^{(i)}(j_{0})|_{1} equals either N_{j_{0}} or N_{j_{0}} + 1 for every 0 ≤ i ≤ q − 1. In particular, |w^{(i_{0})}(j_{0})|_{1} equals either N_{j_{0}} or N_{j_{0}} + 1, and |w^{(i′_{0})}(j_{0})|_{1} equals either N_{j_{0}} or N_{j_{0}} + 1. Therefore either v^{(i_{0})}(j_{0})|_{1} < |w^{(i_{0})}(j_{0})|_{1} or |v^{(i′_{0})}(j_{0})|_{1} > |w^{(i′_{0})}(j_{0})|_{1}. This contradicts (3.7), so we are done. □

4. Proof of Theorem B

The following result gives a very practical way of writing down the lexicographic array associated to a balanced word.

Proposition 2. Let [w] be the unique balanced orbit in 𝕎_{p,q}. Define u = u_{p,q} ∈ W_{p,q} by

u = 0 … 0 \underbrace{1 … 1}_{p} .

Then, for 0 ≤ i, j ≤ q − 1, (1) A[w]_{ij} = (σ^{jp}u)_{i},

(2) The j^{th} column of A[w] is (the vector transpose of) the word σ^{jp}u

(3) w_{(i)} = u_{i}(σ^{p}u)_{i}(σ^{2p}u)_{i} … (σ^{(q−1)p}u)_{i}.

Example 9. Consider the balanced word w = 0010101 ∈ W_{3,7}. By definition u_{3,7} = 0000111. The lexicographic array A[w] is given in Example 4, and we see that successive columns of A[w] are given by rotating upwards the block of 1’s.

Proof of Proposition 2. The conditions (1), (2), (3) are clearly equivalent, so it will suffice to check condition (3).

A well known characterisation of the balanced orbit in 𝕎_{p,q}, due to Morse & Hedlund [MoHe], is as the symbolic coding of the rotation by angle p/q on the circle (see also Lemmas 2.1.14 and 2.1.15 of [BeSe]). More precisely, let T : [0, 1) → [0, 1) be the rational rotation T (x) = x + p/q (mod 1), and let I = [(q − p)/q, 1). For each 0 ≤ i ≤ q − 1, associate to the rational number i/q the length-q word c = c(i, q) defined by c_{k} = χ_{I}(T^{k}(i/q)) (where χ_{I} is the characteristic function for the subinterval I). Each c(i, q) is balanced, and the words c(0, q), …, c(q − 1, q) are all distinct. Moreover, each c(i, q) is lexicographically smaller than c(i + 1, q), in fact if χ_{I}(T^{k}(i/q)) = 1, then either χ_{I}(T^{k}((i + 1)/q)) = 1 or χ_{I}(T^{k−1}((i + 1)/q)) = 1. So in fact c(i, q) = w_{(i)} for 0 ≤ i ≤ q − 1.

The definition of u = u_{p,q} means that u_{i} = 1 if and only if i/q ∈ I, and more generally, (σ^{kp}u)_{i} = 1 if and only if T^{k}(i/q) ∈ I. But we also know that c(i, q)_{k} = 1 if and only if T^{k}(i/q) ∈ I. Combining these observations gives c(i, q)_{k} = (σ^{kp}u)_{i} for all 0 ≤ k ≤ q − 1.

But we know that c(i, q) = w_{(i)}, hence (w_{(i)})_{k} = (σ^{kp}u)_{i}, concluding the proof of the proposition. □

We are now ready to prove Theorem B. For convenience we first recall its statement.

Theorem B. (Compatibility of lexicographic and 1-norm orderings)

Suppose w ∈ {0, 1}^{q}. The following are equivalent:

(1) w is a balanced word,

(2) w_{(i)}[j] ≤_{1} w_{(i+1)}[j] for all 0 ≤ i ≤ q − 2 and 0 ≤ j ≤ q − 1 .

Proof of Theorem B. We first prove that (1) ⇒ (2). Let w ∈ W_{p,q} be balanced. From the definition of u = u_{p,q} we see that, for each 0 ≤ i ≤ q − 2,

∑_{k=0}^{j}(σ^{kp}u)_{i} ≤ ∑_{k=0}^{j}(σ^{kp}u)_{i+1} for any 0 ≤ j ≤ q − 1.  (4.1)

In fact, if (σ^{kp}u)_{i} = 1, then either (σ^{kp}u)_{i+1} = 1 or (σ^{(k−1)p}u)_{i+1} = 1. But by part (3) of Proposition 2, we know that w_{(i)}[j] = u_{i}(σ^{p}u)_{i}(σ^{2p}u)_{i} … (σ^{jp}u)_{i} and w_{(i+1)}[j] = u_{i+1}(σ^{p}u)_{i+1}(σ^{2p}u)_{i+1} … (σ^{jp}u)_{i+1}.

Thus the lefthand side of (4.1) is precisely |w_{(i)}[j]|_{1}, and the righthand side of (4.1) is precisely |w_{(i+1)}[j]|_{1}. So (4.1) asserts that w_{(i)}[j] ≤_{1} w_{(i+1)}[j], as required.

Now we prove that (2) ⇒ (1). Suppose w is not balanced. We would like to show there exist equal length subwords v, v′ of w such that v <_{L} v′ yet v′ <_{1} v. For convenience we will say that a word is allowed (resp. disallowed) if it is a subword (resp. not a subword) of the period-q sequence w^{∞}.

A well known result (see Proposition 2.1.3 in [BeSe]) guarantees the existence of a subword a =: a^{[1]} of w such that both 0a0 and 1a1 are allowed.

Now if there exists some allowed word c such that both 0c1a1 and 1c0a0 are allowed, then we can set v = 0c1a1 and v′ = 1c0a0 and we are done, since v <_{L} v′ yet v′ <_{1} v.

So let us suppose, for a contradiction, that there does not exist c such that both 0c1a1 and 1c0a0 are allowed.

Let b be the longest subword of w such that both b0a0 and b1a1 are allowed. Our assumption above means, however, that either 1b0a0 or 0b1a1 (or possibly both) are disallowed.

We claim that indeed 1b0a0 or 0b1a1 are both disallowed, and hence that 0b0a0 and 1b1a1 are both allowed.

To prove this claim, first suppose that 0b1a1 is disallowed. Then clearly 1b1a1 must be allowed, since b1a1 must have a prefix symbol, and our alphabet is binary.

But now this implies that 1b0a0 is also disallowed, since if it were allowed then 1b would be a common prefix to both 1a1 and 0a0, contradicting the choice of b as the longest such common prefix. Hence 0b0a0 must be allowed.

An analogous argument shows that if 1b0a0 is disallowed then necessarily 0b1a1 is also disallowed, and hence that 0b0a0 and 1b1a1 are both allowed. Therefore the claim is proved.

But now we have proved the existence of a word b =: a^{[2]} such that both 0b0 and 1b1 are allowed, and moreover such that 0b0a0 and 1b1a1 are both allowed. That is, both 0a^{[2]}0a^{[1]}0 and 1a^{[2]}1a^{[1]}1 are allowed.

We can now repeat our argument. That is, we suppose, for a contradiction, that there does not exist c such that both 0c1b1a1 and 1c0b0a0 are allowed.

In this way, we show that if the (2) ⇒ (1) part of the theorem is false then for any r ∈ ℕ we can find subwords a^{[1]}, …, a^{[r]} of w such that both v_{0}^{[r]} := 0a^{[r]}0a^{[r−1]}0 … 0a^{[2]}0a^{[1]}0 and v_{1}^{[r]} := 1a^{[r]}1a^{[r−1]}1 … 1a^{[2]}1a^{[1]}1 are subwords of w (i.e. are subwords of the period-q sequence w^{∞} ∈ {0, 1}^{ℕ}). That is, for arbitrarily large r we can find equal length subwords v_{0}^{[r]}, v_{1}^{[r]} of w^{∞} such that |v_{1}^{[r]}|_{1}−|v_{0}^{[r]}|_{1} = r+1. This contradicts the periodicity of w^{∞}, since clearly for any periodic sequence the difference in 1-norm of any two length-n subwords is bounded independently of n. Therefore Theorem B is proved. □

5. Proof of Theorem C

To prove Theorem C we will need several preliminary results. The proof of the following lemma is left as an exercise.

Lemma 8. Let p, q be positive integers with 1 ≤ p ≤ q and gcd(p, q) = 1. Given w ∈ W_{p,q}, and the corresponding lexicographic array A[w] = (A[w]_{i,j})_{i,j=0}^{q−1}. Then

( \begin{matrix}A[w]_{i,0} \\ A[w]_{i+1,0} \end{matrix} ) = ( \begin{matrix}(w_{(i)})_{0} \\ (w_{(i+1)})_{0} \end{matrix} ) = \{ \begin{matrix}( \begin{matrix}0 \\ 0 \end{matrix} ) & if 0 ≤ i ≤ q − p − 2 \\ ( \begin{matrix}0 \\ 1 \end{matrix} ) & if i = q − p − 1 \\ ( \begin{matrix}1 \\ 1 \end{matrix} ) & if q − p ≤ i ≤ q − 2 \\ ( \begin{matrix}1 \\ 0 \end{matrix} ) & if i = q − 1. \end{matrix}

Moreover,

( \begin{matrix}A[w]_{q−p−1,0} & A[w]_{q−p−1,1} \\ A[w]_{q−p,0} & A[w]_{q−p,1} \end{matrix} ) = ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) .

Lemma 9. Suppose w ∈ W_{p,q} has the lexicographic constant shift property. Let

w_{(0)} <_{L} w_{(1)} <_{L} … <_{L} w_{(q−1)}

be the lexicographic ordering of w.

For any 0 ≤ i ≤ q − 2, there exists a unique k_{0} = k_{0}(i) such that

( \begin{matrix}(w_{(i)})_{k_{0}} & (w_{(i)})_{k_{0}+1} \\ (w_{(i+1)})_{k_{0}} & (w_{(i+1)})_{k_{0}+1} \end{matrix} ) = ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) .

If k ∉ {k_{0}, k_{0} + 1} then (w_{(i)})_{k} = (w_{(i+1)})_{k}.

Example 10. Let w = 0010101. We noted in Example 5 that w has the constant lexicographic shift property. From the lexicographic array in Example 4 it is readily verified that w satisfies the conclusion of Lemma 9.

Proof of Lemma 9. The definition of the lexicographic shift constant 𝔪 = 𝔪(w) means that the k^{th} digit of w_{(i)} equals the (k − i𝔪 (mod q))^{th} digit of w_{(0)}. Now there is some unique 0 ≤ r ≤ q − 1 such that k − i𝔪 = r𝔪 (mod q). Thus the k^{th} digit of w_{(i)} equals the (r𝔪 (mod q))^{th} digit of w_{(0)}, which in turn equals the 0^{th} digit of w_{(r)}.

Analogously, the k^{th} digit of w_{(i+1)} equals the (r𝔪 (mod q))^{th} digit of w_{(1)}, which in turn equals the 0^{th} digit of w_{(r+1)}.

That is,

( \begin{matrix}(w_{(i)})_{k} \\ (w_{(i+1)})_{k} \end{matrix} ) = ( \begin{matrix}(w_{(r)})_{0} \\ (w_{(r+1)})_{0} \end{matrix} ) .

By Lemma 8 we deduce that (w_{(i)})_{k} = (w_{(r)})_{0} = (w_{(r+1)})_{0} = (w_{(i+1)})_{k} unless r = q − p − 1 or r = q − 1.

If r = q − p − 1 then again by Lemma 8 we see that

( \begin{matrix}(w_{(i)})_{k_{0}} & (w_{(i)})_{k_{0}+1} \\ (w_{(i+1)})_{k_{0}} & (w_{(i+1)})_{k_{0}+1} \end{matrix} ) = ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) ,

as required. □

We are now able to prove one half of Theorem C, namely that if a word w ∈ W_{p,q} has the lexicographic constant shift property then it must be balanced.

Proof of the “if” part of Theorem C.

Suppose w ∈ W_{p,q} has the lexicographic constant shift property. Let i = 0 and apply Lemma 9. This means there exists k_{0} such that w_{(0)} and w_{(1)} (the first and second words in the lexicographic ordering of w) satisfy (w_{(0)})_{k} = (w_{(1)})_{k} for all k ∉ {k_{0}, k_{0} + 1}, and that

( \begin{matrix}(w_{(0)})_{k_{0}} & (w_{(0)})_{k_{0}+1} \\ (w_{(1)})_{k_{0}} & (w_{(1)})_{k_{0}+1} \end{matrix} ) = ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) .

Therefore there exist words u, v such that

w_{(0)} = u01v , w_{(1)} = u10v.

But w_{(0)}, w_{(1)} are cyclic shifts of each other, so that 1vu0 is a cyclic shift of 0vu1.

Applying Lemma 5 we see that vu is Sturmian bispecial, so that w is balanced as required. □

The rest of the article is devoted to the proof of the “only if” part of Theorem C: showing that every balanced orbit has the lexicographic constant shift property, and verifying the formula for the lexicographic shift constant.

Let [w_{p,q}] denote the orbit of the post-minimal balanced word w_{p,q}. Clearly [w_{p,q}] has cardinality q. For i ∈ {0, 1} let [w_{p,q}]_{i} denote all cyclic shifts of w_{p,q} ending in an i. The next lemma shows how the morphisms τ_{i} may be used to generate the orbit of w_{p,q} from the orbit of w_{p′,q′}, where \frac{p′}{q′} is the predecessor of \frac{p}{q}.

Lemma 10. Let p, q be positive integers with 1 ≤ p < q ≠ 2 and gcd(p, q) = 1. If \frac{p′}{q′} is the predecessor of \frac{p}{q}, where 1 ≤ p′ < q′ and gcd(p′, q′) = 1, then

(1) If 0 < \frac{p}{q} < \frac{1}{2} then each w ∈ [w_{p,q}] is either of the form w = τ_{0}(w′) for some w′ ∈ [w_{p′,q′}] (there are q′ such w) or of the form w = 1τ_{0}(w′)1^{−1} for some w′ ∈ [w_{p′,q′}]_{1} (there are p′ such w).

(2) If \frac{1}{2} < \frac{p}{q} < 1 then each w ∈ [w_{p,q}] is either of the form w = τ_{1}(w′) for some w′ ∈ [w_{p′,q′}] (there are q′ such w) or of the form w = 0τ_{1}(w′)0^{−1} for some w′ ∈ [w_{p′,q′}]_{0} (there are q′ − p′ such w).

Proof. We prove (1) and leave the proof of (2), which is essentially identical, as an exercise for the reader. If 0 < \frac{p}{q} < \frac{1}{2} then w_{p,q} = τ_{0}(w_{p′,q′}), by Lemma 3. Since τ_{0}(0) = 0 and τ_{0}(1) = 01, it follows that if w ∈ [w_{p,q}] begins in a 0, then it is the image under τ_{0} of a cyclic permutation of w_{p′,q′}, while if w begins in a 1 then 1^{−1}w1 is the image under τ_{0} of a cyclic permutation of w_{p′,q′}.

To see that there are q′ such w beginning in a 0 we will show that if w_{1}, w_{2} ∈ [w_{p′,q′}] with w_{1} <_{L} w_{2}, then τ_{0}(w_{1}) <_{L} τ_{0}(w_{2}). But, if w_{1} <_{L} w_{2}, then there exist words u, u_{1}, u_{2} (with u possibly empty) such that w_{1} = u0u_{1} and w_{2} = u1u_{2}. Since w_{1}, w_{2} have equal numbers of 0s and 1s, it follows that |u_{1}| = |u_{2}| > 0. Applying τ_{0} to both w_{1} and w_{2}, we see that τ_{0}(u)00 is a prefix of τ_{0}(w_{1}) while τ_{0}(u)01 is a prefix of τ_{0}(w_{2}), whence τ_{0}(w_{1}) <_{L} τ_{0}(w_{2}).

Similarly, to see that there are p′ words w of the form w = 1τ_{0}(w′)1^{−1} with w′ ∈ [w_{p′,q′}]_{1}, it suffices to show that if w_{1} <_{L} w_{2} with w_{1}, w_{2} ∈ [w_{p′,q′}]_{1}, then 1τ_{0}(w_{1})1^{−1} <_{L} 1τ_{0}(w_{2})1^{−1}. But if w_{1} <_{L} w_{2} then there exist words u, u_{1}, u_{2} (u possibly empty) with w_{1} = u0u_{1}1 and w_{2} = u1u_{2}1, and |u_{1}| = |u_{2}| > 0. It follows that τ_{0}(u)00 is a prefix of τ_{0}(w_{1}) while τ_{0}(u)01 is a prefix of τ_{0}(w_{2}). Thus 1τ_{0}(u)00 is a prefix of 1τ_{0}(w_{1})1^{−1} while 1τ_{0}(u)01 is a prefix of 1τ_{0}(w_{2})1^{−1}, whence 1τ_{0}(w_{1})1^{−1} <_{L} 1τ_{0}(w_{2})1^{−1}. □

Example 11. If \frac{p}{q} = \frac{3}{7} = [2, 3] then we are in case (1) of Lemma 10. Now w_{3,7} = 0101010, so

[w_{3,7}] = {0010101, 0100101, 0101001, 0101010, 1001010, 1010010, 1010100 } .

The predecessor is \frac{p′}{q′} = [1, 3] = \frac{3}{4}, and we have w_{3,4} = τ_{1}^{3}(0) = 1110. Therefore

[w_{3,4}] = [w_{3,4}]_{0} ∪ [w_{3,4}]_{1} = {1110} ∪ {0111, 1011, 1101} .

We now see that

τ_{0} : \{ \begin{matrix}0111 ↦ 0010101 \\ 1011 ↦ 0100101 \\ 1101 ↦ 0101001 \\ 1110 ↦ 0101010 \end{matrix} ,

hence also

1τ_{0}(0111)1^{−1} = 1001010 , 1τ_{0}(1011)1^{−1} = 1010010 , 1τ_{0}(1101)1^{−1} = 1010100 ,

as predicted by Lemma 10.

Definition. Let \frac{p}{q} = [n_{0}, n_{1}, …, n_{2k+1}] be the even length continued fraction expansion for \frac{p}{q}, where p, q are positive integers such that 1 ≤ p < q and gcd(p, q) = 1.

If p ≠ 1, then define a word z_{p,q} ∈ {0, 1}^{∗∗} by

z_{p,q} = \{ \begin{matrix}τ_{0}^{n_{0}−1} ∘ τ_{1}^{n_{1}} ∘ ⋯ ∘ τ_{0}^{n_{2k}} ∘ τ_{1}^{n_{2k+1}−1}(0) & if n_{2k+1} ≥ 2 \\ τ_{0}^{n_{0}−1} ∘ τ_{1}^{n_{1}} ∘ ⋯ ∘ τ_{0}^{n_{2k−2}} ∘ τ_{1}^{n_{2k−1}}(0) & if n_{2k+1} = 1 \end{matrix} .

We then define the positive integer 𝔪_{p,q} by:

𝔪_{p,q} = \{ \begin{matrix}1 & if p = 1 \\ |z_{p,q}| & otherwise \end{matrix} .

It follows then that 𝔪_{p,q} is simply the penultimate convergent of \frac{p}{q} where we express \frac{p}{q} in terms of its odd length continued fraction expansion. Using the well known formula (see for example [HaWr, Theorem 150]) p_{n}q_{n−1} − p_{n−1}q_{n} = (−1)^{n+1} relating consecutive convergents, we deduce that p 𝔪_{p,q} − p_{n−1}q = 1 (since n = 2k + 1 is odd). Therefore the quantity 𝔪_{p,q} defined above is simply the multiplicative inverse of p modulo q.

The “only if” part of Theorem C will follow from part (4) of the following Theorem D, which gives a very precise description of the lexicographic array for balanced periodic orbits.

Theorem D. ^{2} Let \frac{p}{q} = [n_{0}, n_{1}, …, n_{2k+1}] be the even length continued fraction expansion for \frac{p}{q}, where p, q are positive integers with 1 ≤ p < q and gcd(p, q) = 1. Let

w_{(0)} <_{L} w_{(1)} <_{L} ⋯ <_{L} w_{(q−1)}

denote the lexicographic ordering of the unique balanced orbit in 𝕎_{p,q}.

For each 0 ≤ i ≤ q − 1, let u_{(i)} denote the length-𝔪_{p,q} prefix of w_{(i)}, and define v_{(i)} by w_{(i)} = u_{(i)}v_{(i)}. Then

(1) |u_{(i)}|_{1} = |u_{(0)}|_{1} for all 0 ≤ i < q − 1, and |u_{(q−1)}|_{1} = |u_{(0)}|_{1} + 1.

(2) u_{(q−1)} begins and ends in 1, and v_{(0)}, …, v_{(p−1)} all end in 1, while v_{(p)}, …, v_{(q−1)} all end in 0.

(3) If p ≠ 1, then u_{(0)}, …, u_{(p−2)} all end in 1, u_{(p−1)} ends in 10, and u_{(0)} = 0z_{p,q}0^{−1}. If p = 1, then u_{(i)} = 0 for 0 ≤ i < q − 1, and u_{(q−1)} = 1.

(4) w_{(i+1)} = v_{(i)}u_{(i)} for 0 ≤ i < q − 1, and w_{(0)} = v_{(q−1)}u_{(q−1)}.

(5) u_{(q−1)} and v_{(q−1)} are both palindromes.

Example 12. Suppose \frac{p}{q} = \frac{3}{7} = [2, 3]. Then z_{3,7} = τ_{0} ∘ τ_{1}^{2}(0) = τ_{0}(110) = 01010, so that 𝔪_{p,q} = |z_{p,q}| = 5. The balanced orbit in 𝕎_{3,7} is generated by w = 0010101, and in the notation of Theorem D we have

\begin{matrix}i & w_{(i)} & u_{(i)} & v_{(i)} \\ 0 & 0010101 & 00101 & 01 \\ 1 & 0100101 & 01001 & 01 \\ 2 & 0101001 & 01010 & 01 \\ 3 & 0101010 & 01010 & 10 \\ 4 & 1001010 & 10010 & 10 \\ 5 & 1010010 & 10100 & 10 \\ 6 & 1010100 & 10101 & 00 \end{matrix}

We can easily check the conclusions of Theorem D for this example:

(1) |u_{(i)}|_{1} = 2 = |u_{(0)}|_{1} for 0 ≤ i ≤ 5, and |u_{(6)}|_{1} = 3 = |u_{(0)}|_{1} + 1.

(2) u_{(6)} = 10101 begins and ends in 1, and v_{(0)}, v_{(1)}, v_{(2)} all equal 01, hence all end in 1. Also v_{(0)}, v_{(1)}, v_{(2)}, v_{(3)} all end in 0.

(3) u_{(0)} = 00101 = 0z_{3,7}0^{−1} and u_{(1)} = 01001 both end in 1, while u_{(2)} ends in 10.

(4) The key properties w_{(i+1)} = v_{(i)}u_{(i)} for 0 ≤ i < q − 1, and w_{(0)} = v_{(q−1)}u_{(q−1)} are readily verified.

(5) u_{(6)} = 10101 and v_{(6)} = 00 are both palindromes.

Proof of Theorem D. We first verify the result in case p = 1, or equivalently when the even length continued fraction expansion of \frac{p}{q} is of the form \frac{p}{q} = [n_{0}, 1]. In this case w_{(i)} = 0^{q−(1+i)}10^{i} and hence u_{(i)} = 0 (for 0 ≤ i < q − 1), u_{(q−1)} = 1, and v_{(i)} = 0^{q−(1+i+1)}10^{i}, establishing (1), (2), and (3). Moreover for 0 ≤ i < q − 1 we have

2cf. work of deLuca and Mignosi [dLMi] on related properties of Sturmian words.

w_{(i+1)} = 0^{q−(1+i+1)}10^{i+1}
= 0^{q−(1+i+1)}10^{i}0
= v_{(i)}u_{(i)},

thereby establishing (4).

Finally we see that u_{(q−1)} = 1 while v_{(q−1)} = 0^{q−1}, thus establishing (5).

Next suppose p ≠ 1. We will proceed by induction on q. The base case here is \frac{p}{q} = \frac{2}{3} = [1, 2]. In this case 𝔪_{p,q} = |z_{p,q}| = |τ_{1}(0)| = |10| = 2, and w_{(0)} = 011, w_{(1)} = 101, and w_{(2)} = 110, from which it follows that u_{(0)} = 01, u_{(1)} = 10, u_{(2)} = 11, v_{(0)} = v_{(1)} = 1 and v_{(2)} = 0, thereby establishing (1)-(5), as required.

Suppose \frac{p′}{q′} is the predecessor of \frac{p}{q}, where 1 ≤ p′ < q′ and gcd(p′, q′) = 1. Our inductive hypothesis will be that Theorem D holds for \frac{p′}{q′}, and we will deduce that it also holds for \frac{p}{q}. The proof will differ according to whether 0 < \frac{p}{q} < \frac{1}{2} or \frac{1}{2} < \frac{p}{q} < 1. We shall consider only the first of these cases, leaving the almost identical proof of the second case as an exercise for the reader.

Suppose then that 0 < \frac{p}{q} < \frac{1}{2}, and that \frac{p}{q} = [n_{0}, n_{1}, …, n_{2k+1}] is its even length continued fraction expansion. We recall this means that n_{0} ≥ 2, \frac{p′}{q′} = [n_{0}−1, n_{1}, …, n_{2k+1}] (and hence also p′ ≠ 1), p = p′ and q = p′ + q′.

Let

z_{p′,q′} = \{ \begin{matrix}τ_{0}^{n_{0}−2} ∘ τ_{1}^{n_{1}} ∘ ⋯ ∘ τ_{1}^{n_{2k+1}−1}(0) & if n_{2k+1} ≥ 2 \\ τ_{0}^{n_{0}−2} ∘ τ_{1}^{n_{1}} ∘ ⋯ ∘ τ_{1}^{n_{2k−1}}(0) & if n_{2k+1} = 1 \end{matrix} ,

and set 𝔪_{p′,q′} = |z_{p′,q′}|. Let w′_{(0)} <_{L} w′_{(1)} <_{L} ⋯ <_{L} w′_{(q′−1)} be the q′ cyclic permutations of w_{p′,q′} in increasing lexicographic order, and for 0 ≤ i ≤ q′ − 1 we write w′_{(i)} = u′_{(i)}v′_{(i)} where u′_{(i)} is the prefix of w′_{(i)} of length 𝔪_{p′,q′}. From the inductive hypothesis we have:

(1′) |u′_{(i)}|_{1} = |u′_{(0)}|_{1} for 0 ≤ i < q′ − 1, and |u′_{(q′−1)}|_{1} = |u′_{(0)}|_{1} + 1.

(2′) u′_{(q′−1)} begins and ends in a 1, and v′_{(0)}, …, v′_{(p′−1)} all end in a 1, and v′_{(p′)}, …, v′_{(q′−1)}

all end in a 0. (3′) u′_{(0)}, …, u′_{(p′−2)} all end in a 1, u′_{(p′−1)} ends in 10, and u′_{(0)} = 0z_{p′,q′}0^{−1}. (4′) w′_{(i+1)} = v′_{(i)}u′_{(i)} for 0 ≤ i < q′ − 1, and w′_{(0)} = v′_{(q′−1)}u′_{(q′−1)}. (5′) u′_{(q′−1)} and v′_{(q′−1)} are both palindromes. Let w_{(0)} <_{L} w_{(1)} <_{L} ⋯ <_{L} w_{(q)} be the q cyclic permutations of the post-minimal balanced word w_{p,q}. From Lemma 10 and (2′) we have

w_{(0)} = τ_{0}(w′_{(0)}) = τ_{0}(u′_{(0)})τ_{0}(v′_{(0)})
w_{(1)} = τ_{0}(w′_{(1)}) = τ_{0}(u′_{(1)})τ_{0}(v′_{(1)})
⋮
w_{(q′−2)} = τ_{0}(w′_{(q′−2)}) = τ_{0}(u′_{(q′−2)})τ_{0}(v′_{(q′−2)})
w_{(q′−1)} = τ_{0}(w′_{(q′−1)}) = τ_{0}(u′_{(q′−1)})τ_{0}(v′_{(q′−1)})
w_{(q′)} = 1τ_{0}(w′_{(0)})1^{−1} = 1τ_{0}(u′_{(0)})τ_{0}(v′_{(0)})1^{−1}
⋮
w_{(q′+p′−1)} = 1τ_{0}(w′_{(p′−1)})1^{−1} = 1τ_{0}(u′_{(p′−1)})τ_{0}(v′_{(p′−1)})1^{−1}.

Recall that 𝔪_{p,q} = |z_{p,q}| where z_{p,q} = τ_{0}^{n_{0}−1} ∘ τ_{1}^{n_{1}} ∘ ⋯ ∘ τ_{1}^{n_{2k+1}−1}(0) if n_{2k+1} ≥ 2, and z_{p,q} = τ_{0}^{n_{0}−1} ∘ τ_{1}^{n_{1}} ∘ ⋯ ∘ τ_{1}^{n_{2k−1}}(0) if n_{2k+1} = 1. Then

𝔪_{p,q} = |z_{p,q}| = |τ_{0}(z_{p′,q′})| = |τ_{0}(u′_{(0)})|,

where the last equality follows from (3′). We now compute the length-𝔪_{p,q} prefixes u_{(i)} of w_{(i)}, and show they satisfy the conditions (1), (2), (3), and (4) of the proposition. Using (1′), (2′), and (3′) we deduce that

u_{(0)} = τ_{0}(u′_{(0)})
⋮
u_{(q′−2)} = τ_{0}(u′_{(q′−2)})
u_{(q′−1)} = τ_{0}(u′_{(q′−1)})1^{−1}
u_{(q′)} = 1τ_{0}(u′_{(0)})1^{−1}
⋮
u_{(q′+p′−2)} = 1τ_{0}(u′_{(p′−2)})1^{−1}
u_{(q′+p′−1)} = 1τ_{0}(u′_{(p′−1)})0^{−1}.

It is clear from the above expressions that each u_{(i)} is a prefix of w_{(i)} of length 𝔪_{p,q}, and that |u_{(i)}|_{1} = |u_{(0)}|_{1} for 0 ≤ i ≤ q − 2 = p′ + q′ − 2 while |u_{(q−1)}|_{1} = |u_{(0)}|_{1} + 1, thus establishing (1).

Since u′_{(p′−1)} ends in 10 it follows that u_{(q−1)} begins and ends in a 1. Since p = p′, and v′_{(0)}, …, v′_{(p′−1)} all end in a 1, we deduce that w_{(0)}, …, w_{(p′−1)} all end in a 1, and hence that v_{(0)}, …, v_{(p′−1)} all end in a 1. This establishes (2).

Clearly u_{(0)} = τ_{0}(u′_{(0)}) = 0τ_{0}(z_{p′,q′})0^{−1} = 0z_{p,q}0^{−1}, and since u_{(i)} = τ_{0}(u′_{(i)}) for i ≤ 0 ≤ p − 1 = p′ − 1 we see that (3) follows directly from (3′).

22 OLIVER JENKINSON AND LUCA Q. ZAMBONI

To verify (4) we compute the prefixes v_{(i)} and show that u_{(i+1)}v_{(i+1)} = v_{(i)}u_{(i)}. We have

v_{(0)} = τ_{0}(v′_{(0)})
⋮
v_{(q′−2)} = τ_{0}(v′_{(q′−2)})
v_{(q′−1)} = 1τ_{0}(v′_{(q′−1)})
v_{(q′)} = 1τ_{0}(v′_{(0)})1^{−1}
⋮
v_{(q′+p′−2)} = 1τ_{0}(v′_{(p′−2)})1^{−1}
v_{(q′+p′−1)} = 0τ_{0}(v′_{(p′−1)})1^{−1}.

For 0 ≤ i ≤ q′ − 2 we have

w_{(i+1)} = τ_{0}(w′_{(i+1)}) = τ_{0}(v′_{(i)}u′_{(i)}) = v_{(i)}u_{(i)}.

Next

w_{(q′−1)} = 1τ_{0}(w′_{(0)})1^{−1} = 1τ_{0}(v′_{(q′−1)}u′_{(q′−1)})1^{−1} = v_{(q′−1)}u_{(q′−1)}.

Next for 0 ≤ i ≤ p′ − 2 we have

\begin{matrix}w_{(q′+i+1)} = & 1τ_{0}(w′_{(i+1)})1^{−1} \\ = & 1τ_{0}(v′_{(i)}u′_{(i)})1^{−1} \\ = & 1τ_{0}(v′_{(i)})1^{−1} · 1τ_{0}(u′_{(i)})1^{−1} \\ = & v_{(q′+i)}u_{(q′+i)} . \end{matrix}

To establish (5) we will need two additional lemmas: Lemma D.1. Under the hypotheses of Theorem D, if p ≠ 1, then

w_{p,q} = \{ \begin{matrix}τ_{0}^{n_{0}−1} ∘ τ_{1}^{n_{1}} ∘ ⋯ ∘ τ_{1}^{n_{2k+1}−1}(0)τ_{0}^{n_{0}−1} ∘ τ_{1}^{n_{1}} ∘ ⋯ ∘ τ_{1}^{n_{2k−1}} ∘ τ_{0}^{n_{2k}−1} ∘ τ_{1}(0) & if n_{2k+1} ≥ 2 \\ τ_{0}^{n_{0}−1} ∘ τ_{1}^{n_{1}} ∘ ⋯ ∘ τ_{1}^{n_{2k−1}}(0)τ_{0}^{n_{0}−1} ∘ τ_{1}^{n_{1}} ∘ ⋯ ∘ τ_{1}^{n_{2k−1}} ∘ τ_{0}^{n_{2k}−1} ∘ τ_{1}(0) & if n_{2k+1} = 1 \end{matrix} .

Proof. If n_{2k+1} ≥ 2 then the right hand side of the first equation equals

τ_{0}^{n_{0}−1} ∘ τ_{1}^{n_{1}} ∘ ⋯ ∘ τ_{0}^{n_{2k}−1} (τ_{0} ∘ τ_{1}^{n_{2k+1}−1}(0)τ_{1}(0)) .

But

\begin{matrix}τ_{0} ∘ τ_{1}^{n_{2k+1}−1}(0)τ_{1}(0) = & (01)^{n_{2k+1}−1}010 \\ = & (01)^{n_{2k+1}}0 \\ = & τ_{0} ∘ τ_{1}^{n_{2k+1}}(0), \end{matrix}

thereby establishing the first case. Similarly if n_{2k+1} = 1, then the right hand side of the second equation is equal to

τ_{0}^{n_{0}−1} ∘ τ_{1}^{n_{1}} ∘ ⋯ ∘ τ_{1}^{n_{2k−1}} (0τ_{0}^{n_{2k}−1} ∘ τ_{1}(0)) .

But

\begin{matrix}0τ_{0}^{n_{2k}−1} ∘ τ_{1}(0) = & 00^{n_{2k}−1}10 \\ = & 0^{n_{2k}}10 \\ = & τ_{0}^{n_{2k}} ∘ τ_{1}(0) \\ = & τ_{0}^{n_{2k}} ∘ τ_{1}^{n_{2k+1}}(0), \end{matrix}

thereby establishing the second case.

In either of the factorisations of w_{p,q} in Lemma D.1, the first factor is of length 𝔪_{p,q}. Using the well known fact (see for instance Proposition III.7 in [RiZa]) that for each choice of positive integers n_{0}, n_{1}, …, n_{2k+1} there exists a palindrome x (depending on n_{0}, n_{1}, …, n_{2k+1}) such that τ_{0}^{n_{0}−1}∘τ_{1}^{n_{1}}∘τ_{0}^{n_{2}}∘⋯∘τ_{1}^{n_{2k+1}}(0) = x10. Moreover the palindrome x is a Sturmian bispecial word. Therefore we can combine Lemmas 3 and D.1 to obtain

Lemma D.2. Under the hypotheses of Theorem D, if p ≠ 1, then there exist palindromes x and y such that w_{p,q} = x10y10, and 𝔪_{p,q} = |x10|.

We now return to the proof of part (5) of Theorem D. By Lemma D.2 we know there exist palindromes x and y such that w_{p,q} = x10y10, with 𝔪_{p,q} = |x10|. By Proposition 6 we deduce that w_{(q−1)} = 1(x10y)0 so that u_{(q−1)} = 1x1 and v_{(q−1)} = 0y0, and hence u_{(q−1)} and v_{(q−1)} are both palindromes, as required. This concludes our proof of Theorem D. □

Proof of the “only if” part of Theorem C. Let w be the balanced orbit in 𝕎_{p,q}, and let w_{(0)} <_{L} w_{(1)} <_{L} … <_{L} w_{(q−1)} denote its lexicographic ordering. From part (4) of Theorem D we have w_{(i+1)} = v_{(i)}u_{(i)} for all 0 ≤ i ≤ q −1. But u_{(i)}v_{(i)} = w_{(i)} by definition, and u_{(i)} is of length 𝔪 = 𝔪_{p,q}, so we see that w_{(i+1)} = σ^{𝔪}(w_{(i)}) for all 0 ≤ i ≤ q − 1. That is, w has the lexicographic constant shift property, and the lexicographic shift constant is precisely 𝔪_{p,q}.

Since w_{(i+1)} = σ^{𝔪}(w_{(i)}), and the first q − p of the w_{(i)} begin in 0, we deduce that:

Corollary. The arithmetic sequence {r 𝔪_{p,q}}_{r=0}^{q−p−1} taken modulo q gives the positions of the 0’s in the lexicographically minimal balanced word in W_{p,q}. Similarly, if w′ ∈ W_{p,q} denotes the lexicographically smallest balanced word whose first digit is a 1, then the arithmetic sequence {r 𝔪_{p,q}}_{r=0}^{p−1} taken modulo q gives the positions of the 1’s in w′.

References

[BeSe] J. Berstel, P. Séébold, Sturmian words, in: Algebraic Combinatorics on Words (Chapter 2), vol. 90 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, UK, 2002, pp. 45–110.

[Bou] T. Bousch, Le poisson n’a pas d’arêtes, Ann. Inst. Henri Poincaré (Proba. et Stat.) 36 (2000), 489–508.

[BuSe] S. Bullett & P. Sentenac, Ordered orbits of the shift, square roots, and the devil’s staircase,, Math. Proc. Camb. Phil. Soc. 115 (1994), 451–481.

[dLMi] A. de Luca & F. Mignosi, Some combinatorial properties of Sturmian words, Theor. Comp. Sci. 136 (1994), 361–385.

[Ga] S. Gan, Sturmian sequences and the lexicographic world, Proc. of the A.M.S. 129, 1445–1451.

[HaWr] G. H. Hardy & E. M. Wright, An introduction to the theory of numbers, 5th edition, Oxford University Press, 1979.

[Jen] O. Jenkinson, Frequency locking on the boundary of the barycentre set, Experimental Mathematics 9 (2000), 309–317.

[JuPi] J. Justin & G. Pirillo, On a characteristic property of Arnoux Rauzy sequences, Theoretical Informatics & Applications, to appear.

[Kel] K. Karsten, Symbolic dynamics for angle-doubling on the circle. III: Sturmian sequences and the quadratic map., Ergod. Th. & Dyn. Sys. 14 (1994), 787–805.

[MoHe] M. Morse & G. A. Hedlund, Symbolic dynamics, II: Sturmian trajectories, Amer. J. Math. 62 (1940), 1–42.

[Pir1] G. Pirillo, A new characteristic property of the palindrome prefixes of a standard Sturmian word, (see http://www.mat.univie.ac.at/∼slc/ ), Seminaire Lotharingien de Combinatoire 43 (1999), 3 pp.

[Pir2] G. Pirillo, A curious characteristic property of standard Sturmian words, Algebraic Combinatorics and Computer Science, A tribute to Gian-Carlo Rota, (H. Crapo and D. Senato Eds), Springer Italia, Milan, 2001, pp. 541–546.

[RiZa] R. Risley, L.Q. Zamboni, A generalization of Sturmian sequences: combinatorial structure and transcendence, Acta Arith. XCV.2 (2000), 167–184.

[Ser] C. Series, The geometry of Markoff numbers, Math. Intelligencer 7 (1985), 20–29.

O. Jenkinson, School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London, E1 4NS, UK.

    E-mail address: omj@maths.qmul.ac.uk

L. Q. Zamboni, Department of Mathematics, University of North Texas, Denton, TX 76203-1430, USA.

E-mail address: luca@unt.edu