Some Properties of Abelian Return Words

M. Rigo, P. Salimov,^{1} and E. Vandomme Department of Mathematics University of Liège Grande traverse 12 (B37) B-4000 Liège Belgium

             M.Rigo@ulg.ac.be E.Vandomme@ulg.ac.be

Abstract

We investigate some properties of abelian return words as recently introduced by Puzynina and Zamboni. In particular, we obtain a characterization of Sturmian words with nonzero intercept in terms of the finiteness of the set of abelian return words to all prefixes. We describe this set of abelian returns for the Fibonacci word but also for the 2-automatic Thue–Morse word. We also investigate the relationship existing between abelian complexity and finiteness of the set of abelian returns to all prefixes.

1 Introduction

Many notions occurring in combinatorics on words have been recently and fruitfully extended to an abelian context. Two words u and v are said to be abelian equivalent if u is a permutation of the letters in v and usually, the corresponding concepts are defined up to such an equivalence. This framework gives rise to many challenging questions in combinatorics on words: what kind of information is preserved in the abelian context? To what extent can the classical results be applied? What kind of characterization can we obtain? For instance, consider the classical notion of factor complexity p_{x} which maps an integer n ≥ 0 to the number of distinct factors of length n occurring in an infinite word x. The well-known theorem of Morse–Hedlund gives a characterization of the ultimately periodic words. See for instance [13]. Sturmian words are defined by the property p_{x}(n) = n + 1 for all n ≥ 0. The analogue to factor complexity is the abelian complexity of x which maps n ≥ 0 to the number of distinct abelian classes partitioning the set of factors of length n occurring in x.

1The second author is supported by the Russian President’s grant no. MK-4075.2012.1, the Russian Foundation for Basic Research grant no. 11-01-00997 and by a University of Liège post-doctoral grant.

This latter notion was already introduced in the 1970’s [5]. Some other important questions in combinatorics on words such as avoiding abelian repetitions, were initiated at the same period. See for instance [6]. See also the reference [18] on abelian complexity which contains many relevant bibliographic pointers.

The return word is a classical notion in combinatorics on words and symbolic dynamical systems [11, 12, 20]. For instance, Durand obtained a characterization of primitive substitutive sequences in terms of return words and derived sequences [9]. Let u be a recurrent factor of x, i.e., a factor occurring infinitely many times in x. A return word to u is a factor separating two consecutive occurrences of u. In this paper, we consider the abelian analogue of this notion of return word. Such a study has been recently presented by Puzynina and Zamboni during the WORDS 2011 conference. Here we focus on different aspects of abelian returns and we hope that our results can be seen as complementary to those found by Puzynina and Zamboni [17].

The main difference is that we usually consider the set of abelian returns with respect to all the factors of an infinite word x, while Puzynina and Zamboni [17] study the set of abelian returns with respect to each factor taken separately. In particular, their main contribution is a characterization of Sturmian words: a recurrent infinite word is Sturmian if and only if each of its factors has two or three abelian returns. Sturmian words have been extensively studied and, in particular, every Sturmian word can be obtained by coding the orbit (R_{α}^{n}(ρ))_{n≥0} of a point ρ on a circle under a rotation R_{α} by an irrational angle α when the circle is partitioned in a suitable way into two complementary intervals. The irrational α is called the slope of the Sturmian word and the initial point ρ is its intercept. See for instance [14, 16]. Many of our results on Sturmian words rely on this definition of Sturmian words.

This paper is organized as follows. In Section 2, we present the main definitions and notation used in this paper. In Section 3, we discuss the relationship with periodicity and we prove that a recurrent word is periodic if and only if its set of abelian returns is finite. We also construct an abelian uniformly recurrent word which is not eventually recurrent. In Section 4, we restrict ourselves to the set APR_{x} of abelian returns to all prefixes. In particular, this set is finite for any uniformly recurrent and abelian periodic word. We study the special case of the Thue–Morse word t [1] and show that the set of abelian returns to all prefixes of t contains 16 elements. Next, we obtain a characterization of Sturmian words with (non)zero intercept as follows. Let x be a Sturmian word coding an orbit (R_{α}^{n}(ρ))_{n≥0}. The set APR_{x} of abelian returns to the prefixes of x is finite if and only if x does not have a null intercept (see Theorem 19). The celebrated Fibonacci word f can be defined with a slope and an intercept both equal to 1/τ^{2} where τ is the Golden mean. Therefore our result implies that APR_{f} is finite. We show that this set contains exactly 5 elements. Interestingly, our developments can be related to the lengths of the palindromic prefixes of f. See for instance [7, 10]. By contrast the set of abelian returns to all prefixes for the word 0f is infinite. Then we show that if x is an abelian recurrent word such that APR_{x} is finite, then x has bounded abelian complexity. In the last section of this paper, we introduce the notion of abelian derived sequence. If a word x is uniformly recurrent, then x can be factored in terms of abelian returns to a given prefix of x. This gives rise to a coding that allows one to define a new sequence. Contrary to the non-abelian case and the characterization obtained by Durand, the Thue–Morse word is an example of word having infinitely many derived sequences.

2 Preliminaries

An infinite word x is said to be recurrent if every factor u of x appears infinitely often in x. An infinite word x is said to be uniformly recurrent, if it is recurrent and the distance between any two consecutive occurrences of any of its factors u is bounded by a constant depending only on u. The language of all the finite factors (resp. prefixes) of an infinite word x is denoted by Fac(x) (resp. Pref(x)). Let i, j be such that i ≤ j. The factor x_{i}x_{i+1} ⋯ x_{j} of x = x_{0}x_{1} ⋯ is denoted by x[i, j]. The notation x[i, i] is shortened to x_{i}.

2.1 Return words

The classical notion of return word has been used by Durand [9] but was previously introduced by Boshernitzan [4] (see also [8] for the notion of induced transformation in a dynamical context). Let u be a prefix of a uniformly recurrent word x. A nonempty factor w of x is a return word to u, if there exists some i ≥ 0 such that

• x[i, i + |w| − 1] = w,

• x[i, i + |u| − 1] = u = x[i + |w|, i + |w| + |u| − 1],

• x[i + j, i + j + |u| − 1] ≠ u for all j ∈ {1, …, |w| − 1}.

We denote by R_{x,u} the set of return words to u. Since x is uniformly recurrent, this set is finite because the length of the longest return word to u is bounded by the maximal distance between two successive occurrences of u. If we order the return words to u with respect to their first occurrence in x, then the corresponding map is Λ_{x,u} : R_{x,u} → {1, …, #(R_{x,u})} =: R_{x,u}. Since R_{x,u} is a code [9], i.e., any element in R_{x,u}^{∗} has a unique factorization as return words to u, x can be written in a unique way as x = m_{0}m_{1}m_{2} ⋯ and the derived sequence D_{u}(x) is an infinite word Λ_{x,u}(m_{0})Λ_{x,u}(m_{1})Λ_{x,u}(m_{2}) ⋯ over R_{x,u}.

2.2 Abelian returns

Recently, the notion of return words has been generalized to an abelian framework [17]. In this paper, we will distinguish two cases: abelian return to a prefix and abelian return to a factor. We make such a distinction to be able to define in the first case the abelian derived sequence. Let us start with a few definitions.

Let A = {a_{1}, …, a_{k}} be a k-letter alphabet. We denote by |w|_{a_{i}} the number of occurrences of the letter a_{i} in a word w ∈ A^{∗}. The Parikh mapping Ψ : A^{∗} → ℕ^{k} is defined by Ψ(w) = (|w|_{a_{1}}, …, |w|_{a_{k}}). Let u, v be two finite words of the same length. We say that u and v are abelian equivalent and we write u ∼_{ab} v if Ψ(u) = Ψ(v).

An infinite word x is abelian periodic (of period m), if it can be factored as x = u_{1}u_{2}u_{3} ⋯ where, for all i, j, the finite words u_{i} and u_{j} have the same length m and are abelian equivalent. The smallest m for which such a factorization exists is called the abelian period of x. For instance, the Thue–Morse word is an infinite concatenation of 01 and 10 and is thus abelian periodic of period 2.

Let x be an infinite word. If, for each factor u of x, there exist infinitely many i such that x[i, i + |u| − 1] ∼_{ab} u, then x is said to be abelian recurrent.

If x is abelian recurrent and if, for each factor u of x, the distance between any two consecutive occurrences of factors abelian equivalent to u is bounded by a constant depending only on u, then x is said to be abelian uniformly recurrent.

Remark 1. Note that uniform recurrence implies obviously abelian uniform recurrence. We will show in Proposition 6 that the converse does not hold.

Definition 2. Let u be a prefix of an abelian uniformly recurrent word x. We say that a nonempty factor w of x is an abelian return to u, if there exists some i ≥ 0 such that

• x[i, i + |w| − 1] = w,

• x[i, i + |u| − 1] ∼_{ab} u ∼_{ab} x[i + |w|, i + |w| + |u| − 1],

• x[i + j, i + j + |u| − 1] ≁_{ab} u, for all j ∈ {1, …, |w| − 1}.

We denote by APR_{x,u} the set of abelian returns to the prefix u. Since x is abelian uniformly recurrent, then the set APR_{x,u} is finite. We define the set of abelian returns to prefixes as

APR_{x} := ⋃_{u∈Pref(x)} APR_{x,u}.

Observe that if x is uniformly recurrent, then the length of the longest element in APR_{x,u} is bounded by the length of the longest element in R_{x,u}.

We will also consider a more general situation where u is not restricted to be a prefix of x. Puzynina and Zamboni [17] called this notion a semi-abelian return to the abelian class of u and the number of abelian returns is the number of distinct abelian classes of semi-abelian returns.

Definition 3. If x is abelian recurrent and if u is a factor of x, we can define as above the notion of abelian return to u. The corresponding set AR_{x,u} of abelian returns to u is well defined. We define the set of abelian returns as

AR_{x} := ⋃_{u∈Fac(x)} AR_{x,u}.

Remark 4. Let x be an abelian recurrent word. The set AR_{x,u} is finite, for each factor u of x, if and only if x is abelian uniformly recurrent.

3 Finiteness of the set of abelian returns

Puzynina and Zamboni [17] provided a discussion between periodicity and the number of abelian returns. Here we take the finiteness of the set of abelian returns to characterize periodicity.

Theorem 5. Let x be a recurrent word. The set AR_{x} is finite if and only if x is periodic.

Proof. The “if” part is obvious. We prove the “only if” part.

Suppose that AR_{x} is finite and that x is recurrent but not periodic. In this case, for each k, there exists a word u satisfying |u| > k such that au, bu ∈ Fac(x) for some letters a ≠ b. Hence there exist i, j such that i < j, x[i, i + |u|] = au and x[j, j + |u|] = bu. Define v = x[i, j − 1]. Since x[i + d, j − 1 + d] ≁_{ab} v for all d ∈ {1, …, |u|}, there is an abelian return to v in x of length at least k. As we can do the same for arbitrarily large k, the set AR_{x} is infinite.

Obviously, uniform recurrence implies abelian uniform recurrence, but the converse is not true. Recall that an eventually recurrent word is an infinite word having a recurrent suffix.

Proposition 6. There exists an abelian uniformly recurrent word which is not eventually recurrent.

Proof. Let t = t_{0}t_{1} ⋯ = 01101001 ⋯ be the Thue–Morse word and φ_{T M} be the Thue– Morse morphism, φ_{T M}(t) = t. Define the set I = {i_{0} < i_{1} < …} of all positions where an isolated 1 occurs. That is, for all n, we have t_{i_{n}} = 1 and t_{i_{n}−1} = t_{i_{n}+1} = 0. Moreover we set J = {i_{2^{k}} | k > 0}.

Let y = y_{0}y_{1} ⋯ be the word defined by y_{j} = 0, if j ∈ J, and y_{j} = t_{j} otherwise. Define x = φ_{T M}(y).

The word x coincides with y almost everywhere, except for positions from the set 2J ∪ (2J + 1). Hence, each factor of the Thue–Morse word occurs in x uniformly, i.e., with bounded gaps. At the same time, the factor φ_{T M}(000) occurs in x with strictly growing gaps. Hence x is not eventually recurrent.

Let us now prove that x is abelian uniformly recurrent. First we point out a property of the Thue–Morse word: for all d > 0 and all a ∈ {0, 1}, there exists k such that t_{k} = a ≠ t_{k+d}. This property follows from the well-known fact that the Thue–Morse word does not contain any constant infinite arithmetical subsequence [15].

As x is abelian periodic (of period 2), the weight (i.e., the sum of digits) of each factor u of x of odd length is either \frac{|u|+1}{2} or \frac{|u|−1}{2}. Note that y_{i} = 0 implies |x[2i + 1, 2i + |u|]|_{1} = \frac{|u|+1}{2} and y_{i} = 1 implies |x[2i + 1, 2i + |u|]|_{1} = \frac{|u|−1}{2}. Since 0 (resp. 1) occurs with bounded gaps in y, gaps between abelian occurrences in x of a factor of odd length are bounded.

The weight of a factor u of even length of x can take values \frac{|u|}{2}, \frac{|u|}{2} + 1 and \frac{|u|}{2} − 1. The first case takes place when u occurs at an even position in x, meaning that the gaps between abelian occurrences of u of weight \frac{|u|}{2} in x are bounded. The last two cases take place if u occurs in x at an odd position i and if y_{\frac{i−1}{2}} = 1 and y_{\frac{i−1+|u|}{2}} = 0 or, y_{\frac{i−1}{2}} = 0 and y_{\frac{i−1+|u|}{2}} = 1. Due to the mentioned property of the Thue–Morse word, there exists k such that t_{k} = 1 ≠ t_{k+ \frac{|u|}{2}} (resp. t_{k} = 0 ≠ t_{k+ \frac{|u|}{2}} ) and since t is uniformly recurrent, the factor t[k, k + \frac{|u|}{2}] occurs infinitely often with bounded gaps in t. Hence abelian occurrences of u in x appear infinitely often with bounded gaps.

4 Finiteness of the set of abelian returns to prefixes

Contrary to the finiteness of AR_{x}, the finiteness of APR_{x} does not imply periodicity nor abelian periodicity of x. Moreover, if x is uniformly recurrent, it is well-known that

min_{v∈R_{x,u}} |v| → ∞, if |u| → ∞,

meaning that taking longer prefixes eventually leads to longer return words. Here we show that such a result does not hold for abelian returns to prefixes. Indeed, for the Thue–Morse word the corresponding set APR_{t} is finite and can be described precisely. Such a result also holds for the Fibonacci word. In particular, amongst the set of Sturmian words, the finiteness of APR_{x} characterizes Sturmian words with nonzero intercept.

Lemma 7. If x is a uniformly recurrent and abelian periodic word, then the set APR_{x} is finite.

Proof. Let m be the (minimal) abelian period of x. Let us find an upper bound for the length of an abelian return u to a prefix p of x.

Suppose first that |p| = mk. In this case, due to abelian periodicity, for all i, we have x[mi, m(i + k) − 1] ∼_{ab} p. Hence we get |u| ⩽ m.

Suppose now that |p| = mk + ℓ, where 0 < ℓ < m. Let us denote the word x[mk, m(k + 1) − 1] by s. As the word x is abelian periodic, if there exists i such that the equality x[mi, m(i + 1) − 1] = s holds, then x[m(i − k), mi + ℓ − 1] ∼_{ab} p. Hence, it is sufficient to prove that the set

{i ≥ 0 | x[mi, m(i + 1) − 1] = s}

has bounded gaps.

Let us consider the word x′ on the alphabet of factors of x of length m, such that x′_{i} = x[mi, m(i + 1) − 1]. It is well-known that the uniform recurrence of x implies uniform recurrence of x′ (see for instance [19]). Hence, for each letter of x′ there is an upper bound on the gap between two consecutive occurrences of it in x′. Denoting the maximum of such constants by D, we get |u| ⩽ mD.

Remark 8. In Lemma 7, the condition on a word x to be uniformly recurrent is essential: there exists an abelian periodic word x which is not uniformly recurrent and such that APR_{x,u} is infinite for some prefix u of x. Consider the abelian periodic word of period 4 given by x = ϕφ^{ω}(0) where φ : 0 ↦ 010, 1 ↦ 111 and ϕ : 0 ↦ 01230123, 1 ↦ 0213:

                x = 01230123 0213 01230123 0213 0213 0213 · · ·

In x there are unbounded gaps between consecutive abelian occurrences of its prefix 012301 that correspond to the occurrences of ϕ(1^{m}).

Remark 9. In Lemma 7, the condition on abelian periodicity of x is not necessary to get finiteness of APR_{x}. We shall give an example below when discussing the case of Sturmian words. Indeed, Sturmian words are not abelian periodic (see Lemma 20) but for instance, the Fibonacci word f is uniformly recurrent and the corresponding set APR_{f} is finite.

Proposition 10. A word x is periodic if and only there exists some prefix u such that infinitely many factors of x are abelian equivalent to u and all the abelian returns in APR_{x,u} have length 1.

Proof. If x = u^{ω}, then x[i, i+|u|−1] ∼_{ab} u for all i ≥ 0. Conversely, if all the abelian returns to some prefix u in APR_{x,u} have length 1, then x[i, i + |u| − 1] ∼_{ab} u ∼_{ab} x[i + 1, i + |u|] for all i ≥ 0. There is an abelian return a of length 1 at position i in x and it also occurs in position i + |u|. It follows that |u| is a period of x.

4.1 Finiteness of APR_{t} for the Thue–Morse word

We already know from Lemma 7 that the Thue–Morse word has a finite set of abelian returns to all its prefixes. Here we describe precisely this set.

Lemma 11. Let x be a uniformly recurrent word. Let n ≥ 1 and i, j be such that i < j. Assume that x[i, i + n − 1] ∼_{ab} x[j, j + n − 1] and there exists a prefix u of length j − i of x such that u ∼_{ab} x[i, j − 1]. The word x[i, i + n − 1]is an occurrence of an abelian return to the prefix u if and only if, for all ℓ ∈ {0, …, n − 2}, x[i, i + ℓ] ≁_{ab} x[j, j + ℓ].

Proof. Since |u| = j − i, by assumption we have x[i, i + |u| − 1] ∼_{ab} u. Observe first that there exists ℓ ∈ {0, …, n − 1} such that x[i, i + ℓ] ∼_{ab} x[j, j + ℓ] if and only if x[i + ℓ + 1, i + ℓ + |u|] ∼_{ab} u. In particular, since x[i, i + n − 1] ∼_{ab} x[j, j + n − 1], we get x[i + n, i + n + |u| − 1] = x[i + n, j − 1 + n] ∼_{ab} u. Moreover, ℓ ∈ {0, …, n − 2} is such that x[i + ℓ + 1, i + ℓ + |u|] ≁_{ab} u if and only if x[i, i + ℓ] ≁_{ab} x[j, j + ℓ].

Remark 12. From this lemma, we can derive a necessary condition for a word to be an abelian return to a prefix. If a word w = w_{1} ⋯ w_{n} of length n is an abelian return to a prefix, then there exists some factor y = y_{1} ⋯ y_{n} of x such that

w ∼_{ab} y and, for all ℓ ∈ {1, …, n − 1}, w_{1} ⋯ w_{ℓ} ≁_{ab} y_{1} ⋯ y_{ℓ}.  (1)

This condition is not sufficient. For instance, w = 001011 and y = 110010 are two factors of length 6 satisfying(1) and occurring in the Thue–Morse word t. But, as shown in the following proposition, w is not an abelian return to any prefix.

Theorem 13. The set APR_{t} of abelian returns to prefixes for the Thue–Morse word t is

{0, 1, 01, 10, 001, 011, 100, 110, 0011, 0101, 1010, 1100, 00101, 01011, 10100, 11010}.

Proof. One can check with some computer experiments that the factors given above appear as abelian returns to some prefix of t. Moreover, one can also check that these are the only factors of length 2, …, 5 in t satisfying condition (1).

Assume that there exists some abelian return w = w_{1} ⋯ w_{n} = t[i, i + n − 1] of length n ≥ 2 to a prefix of t occurring at position i. In particular, we may assume that w is an abelian return to the prefix u of length j − i > 0 and y = y_{1} ⋯ y_{n} = t[j, j + n − 1] satisfies (1). We will show that the length of w is at most 5. Recall that t[2k, 2k + 1] ∈ {01, 10} for all k ≥ 0.

Assume first that i, j are even. Since t[i, i + 1] and t[j, j + 1] belong to {01, 10}, we conclude that t[i, i + 1] ∼_{ab} t[j, j + 1] and, in that situation, we can only have an abelian return of length at most 2.

Assume now that i is odd and j is even and that t_{i} = 0 (symmetric cases can be treated in the same way). Our aim is to build the longest possible abelian return. Since t_{i} = 0 and j is even, we consider t[j, j + 1] = 10 because otherwise, t[j, j + 1] = 01 and w_{1} = y_{1} (i.e., t[i + 1, j + 1] ∼_{ab} t[i, j] ∼_{ab} u and we get directly an abelian return of length n = 1). Now t[i, i + 2] = 001 because otherwise, t[i, i + 2] = 010 and w_{1}w_{2} ∼_{ab} y_{1}y_{2}. Continuing this way, we have t[j, j + 3] = 1010 and t[i, i + 4] = 00101. Since (10)^{3} is not a factor of t, we have t[j, j + 5] = 101001 and t[i, i + 4] ∼_{ab} t[j, j + 4]. In that situation, we can only have an abelian return of length at most 5.

The last case is when i and j are odd. Assume t_{i} = 0 and t_{j} = 1. We have t_{i} = 0 and t_{j−1} = 0 because t[j − 1, j] = 01. Moreover, z = t[i + 1, j − 2] ∈ {01, 10}^{∗} and thus v = t[i, j − 1] = 0z0 is a word of even length such that |v|_{0} = 2 + |v|_{1}. Therefore v cannot be abelian equivalent to a prefix u of t. So in such a situation, we cannot have an abelian return to some prefix of t.

Proposition 14. If a factor of length n ≥ 6 of the Thue–Morse word satisfies (1), then n is even.

Proof. Let w = t[i, i + n − 1] and y = t[j, j + n − 1] be factors of t of length n ≥ 6 satisfying (1). As n ≥ 6, i and j are odd. Hence, to satisfy the condition (1), we must have

(\begin{matrix}t[i, i + n − 1] \\ t[j, j + n − 1] \end{matrix}) ∈ (\begin{matrix}0 \\ 1 \end{matrix}) \{(\begin{matrix}01 \\ 01 \end{matrix}) , (\begin{matrix}10 \\ 10 \end{matrix}) , (\begin{matrix}01 \\ 10 \end{matrix})\}^{∗} (\begin{matrix}1 \\ 0 \end{matrix})∪(\begin{matrix}1 \\ 0 \end{matrix}) \{(\begin{matrix}01 \\ 01 \end{matrix}) , (\begin{matrix}10 \\ 10 \end{matrix}) , (\begin{matrix}10 \\ 01 \end{matrix})\}^{∗} (\begin{matrix}0 \\ 1 \end{matrix}) .

So n must be even.

For n = 6, 8, 10, …, 104, with a computer search, we get the following number of factors of length n satisfying (1): 6, 4, 8, 12, 12, 4, 8, 8, 4, 0, 0, 8, 0, 0, 4, 8, 4, 0, 0, 0, 0, 0, 4, 0, 4, 0, 0, 0, 0, 0, 4, 8, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0.

4.2 Sturmian words

Sturmian words form one of the most studied classes of infinite words. It can be defined in several ways. For our purpose, the definition in terms of rotations is convenient.

Let C be the one-dimensional torus ℝ/ℤ identified with the interval [0, 1). As usual, we denote by {x} the fractional part of x. The rotation R_{α} defined for a real number α is a mapping C → C that maps an x to {x + α}.

Theorem 15 (Kronecker [2]). If a number α is irrational, then the set of points {R_{α}^{i}(ρ) | i ∈ ℕ} is dense in C for all initial points ρ ∈ C.

By an interval (resp. half-interval) of C we mean a set of points that is an image of an interval (resp. half-interval) of ℝ under operation {·}. For instance, if 0 ≤ b < a < 1, then [a, 1) ∪ [0, b) is denoted by [a, b).

Let α be irrational and ρ be real. Without loss of generality we can assume 0 ≤ α, ρ < 1. A Sturmian word x = St(α, ρ) (resp. x = St′(α, ρ)) can be defined as

x_{i} = \begin{cases}0, & if R_{α}^{i}(ρ) ∈ I_{0}; \\ 1, & if R_{α}^{i}(ρ) ∈ I_{1}, \end{cases}  (2)

where I_{0} = [0, 1 − α) and I_{1} = [1 − α, 1) (resp. I_{0} = (0, 1 − α] and I_{1} = (1 − α, 1]). See [2, 14].

If ρ = 0, then

St(α, 0) = 0c_{α} and St′(α, 0) = 1c_{α}

and c_{α} is said to be the characteristic Sturmian word of slope α [14]. If x = St(α, 0), we say that x is a Sturmian word with null intercept.

Example 16. If τ = (1 + \sqrt{5})/2 is the Golden mean, then St(1/τ^{2}, 0) = 0f where f is the Fibonacci word 0100101001 ⋯ which is the unique fixed point of the morphism φ : 0 ↦ 01, 1 ↦ 0. In particular, we have f = St(1/τ^{2}, 1/τ^{2}).

Theorem 17. [14, Theorem 2.1.5] An infinite word x ∈ {0, 1}^{ω} is Sturmian if and only if it is aperiodic and balanced, i.e., for all u, v ∈ F ac(x) of same length, we have ||u|_{1} − |v|_{1}| ≤ 1.

Let x = St(α, ρ) be a Sturmian word. For a binary word v = v_{0}v_{1} ⋯ v_{m}, we define a half-interval I_{v} of C as

I_{v} := I_{v_{0}} ∩ R_{α}^{−1}(I_{v_{1}}) ∩ ⋯ ∩ R_{α}^{−m}(I_{v_{m}}).  (3)

Hence x[i, i + m] = v if and only if R_{α}^{i}(ρ) ∈ I_{v}. See [14, Section 2.1.2].

Definition 18. Let x = St(α, ρ) be a Sturmian word. For each k the number of 1’s in a factor of length k in x can only take the values ⌈kα⌉ or ⌈kα⌉ − 1. The corresponding factors will be called respectively heavy and light. If x is understood from the context, H(k) (resp. L(k)) will denote the set of heavy (resp. light) factors of length k in x. Define

I_{H}(k) := ⋃_{v∈H(k)} I_{v} and I_{L}(k) := ⋃_{v∈L(k)} I_{v}.

So, the word x[i, i + k − 1] is heavy if and only if R_{α}^{i}(ρ) ∈ I_{H}(k).

Theorem 19. Let x be a Sturmian word. The set APR_{x} is finite if and only if x does not have a null intercept.

Proof. For the sake of convenience, let x be defined as St(α, ρ) for half-intervals I_{0} = [0, 1−α) and I_{1} = [1 − α, 1). Let us prove by induction on k ≥ 1 that

I_{H}(k) = [1 − {kα}, 1) and I_{L}(k) = [0, 1 − {kα}).  (4)

It holds true for k = 1. Suppose now that the statement holds true for some k ≥ 1. We consider two cases.

• Assume that 0 ∉ R_{α}^{−k}(I_{1}). Therefore we get R_{α}^{−k}(I_{1}) = [1 − {(k + 1)α}, 1 − {kα}) with 1−{(k +1)α} < 1−{kα}. By the induction hypothesis, we have I_{H}(k) = [1−{kα}, 1) and consequently,

R_{α}^{−k}(I_{1}) ∩ I_{H}(k) = ∅.

This means that all the heavy factors of length k of x can only be extended with 0 to factors of length k + 1 of x. In particular, the weights of heavy factors of length k and k + 1 are the same. At the same time, we have R_{α}^{−k}(I_{1}) ∩ I_{L}(k) = R_{α}^{−k}(I_{1}), which means that the factors corresponding to elements belonging to this latter set are the light factors of length k that are extended with 1 to heavy factors of length k + 1. We conclude that

I_{H}(k + 1) = I_{H}(k) ∪ R_{α}^{−k}(I_{1}) = [1 − {(k + 1)α}, 1)

and I_{L}(k + 1) = I_{L}(k)\R_{α}^{−k}(I_{1}) = [0, 1 − {(k + 1)α}).

• Assume now that 0 ∈ R_{α}^{−k}(I_{1}), i.e., 1 − {(k + 1)α} > 1 − {kα}. In this case, using again the induction hypothesis, R_{α}^{−k}(I_{1}) ∩ I_{H}(k) = [1 − {(k + 1)α}, 1) is nonempty. This interval corresponds to the heavy factors of length k having an extension with 1 making them the only heavy factors of length k + 1 in x.

Now we are ready to prove the main part of the statement. First of all, let us prove that, if x has a null intercept, then APR_{x} is infinite. Let k ≥ 1 and p be the prefix of length k of x. As ρ = 0, we have 0 ∈ I_{p}. Since the interval I_{p} corresponds exactly to one word p which is either light or heavy, we have I_{p} ⊆ I_{L}(k) or I_{p} ⊆ I_{H}(k). As 0 ∈ I_{p}, we conclude that I_{p} ⊆ I_{L}(k) using (4). In other words, we have just shown that each prefix of x is a light factor.

Now we show that, for all n, there exists a length ℓ such that gaps between consecutive occurrences of light factors of length ℓ in x can be larger than n. Let n ≥ 1. Define the set of points

S_{n} := {R_{α}^{i}(0) | 0 ⩽ i ⩽ n}

and denote by d the minimal length of intervals having endpoints in S_{n}. Due to Kronecker’s theorem, we can find some ℓ such that |I_{L}(ℓ)| < d and it follows that I_{L}(ℓ) ∩ S_{n} = {0}. With our definitions, it means that the light prefix of x of length ℓ is followed by at least n heavy consecutive factors of length ℓ. Since this can be done for any n, the set APR_{x} is infinite.

Let us prove that, if x does not have a null intercept, then APR_{x} is finite. The main difference with the previous situation is that a prefix can now be a heavy or a light factor depending on its length: ρ ≥ 1 − {kα} if and only the prefix of length k is heavy. We will show that there exists a constant c such that, for all prefixes p of x, the gap between consecutive occurrences of factors abelian equivalent to p is bounded by c.

Let n ≥ 1. Consider as before the set S_{n} and order its elements 0 = s_{0} < s_{1} < ⋯ < s_{n}. Denote by D(n) the maximal length of the intervals [s_{0}, s_{1}), …, [s_{n−1}, s_{n}), [s_{n}, s_{0}) whose endpoints are consecutive points in S_{n}. Due to Kronecker’s theorem, there exists some c such that 2D(c) < min{ρ, 1 − ρ}.

Suppose that the prefix of length k of x is a light word. Then we have ρ ∈ I_{L}(k) and, consequently, |I_{L}(k)| > ρ. Assume that there is a light factor of length k occurring at position i in x, i.e., R_{α}^{i}(ρ) ∈ I_{L}(k). We consider two cases. If R_{α}^{i}(ρ) ≥ D(c), there exists j ∈ {1, …, c} such that R_{α}^{j}(0) = s_{c} and θ = 1 − R_{α}^{j}(0) ∈ (0, D(c)]. Hence the point R_{α}^{j}(R_{α}^{i}(ρ)) = R_{α}^{i+j}(ρ) = R_{α}^{i}(ρ) − θ belongs to I_{L}(k), i.e., the factor of length k at position i + j in x is light again. If R_{α}^{i}(ρ) < D(c), there exists j ∈ {1, …, c} such that R_{α}^{j}(0) = s_{1} ≤ D(c) < ρ/2. Hence the point R_{α}^{j}(R_{α}^{i}(ρ)) = R_{α}^{i+j}(ρ) = R_{α}^{i}(ρ) + s_{1} is less than ρ and belongs to I_{L}(k).

A similar proof can be done for the case of a heavy prefix of length k. Assume that ρ ∈ I_{H}(k) and that, for some i ≥ 0, R_{α}^{i}(ρ) ∈ I_{H}(k). If R_{α}^{i}(ρ) < 1−D(c), then R_{α}^{i}(ρ)+s_{1} < 1. If R_{α}^{i}(ρ) ≥ 1−D(c), then R_{α}^{i}(ρ)−(1−s_{c}) ≥ 1−2D(c) > ρ. We can derive the same conclusion as above.

Hence the number c is an upper bound on the length of abelian returns to any prefix and therefore APR_{x} is finite.

Lemma 20. No Sturmian word is abelian periodic.

Proof. Proceed by contradiction and assume that x = St(α, ρ) is abelian periodic of period m with α irrational. Then all factors of the kind x[tm, (t+1)m−1], t ∈ ℕ, are abelian equivalent, i.e., have the same weight. Assume that, for all t, R_{α}^{tm}(ρ) = R_{mα}^{t}(ρ) ∈ I_{L}(m). But since α is irrational, mα is also irrational and thanks to Kronecker’s theorem, {R_{mα}^{t}(ρ) | t ≥ 0} is dense in C contradicting the fact that {R_{mα}^{t}(ρ) | t ≥ 0} ∩ I_{H}(m) should be empty.

4.3 Finiteness of APR_{f} for the Fibonacci word

From Theorem 19, since the Fibonacci word f is given by St(1/τ^{2}, 1/τ^{2}), we already know that APR_{f} is finite. Here we exhibit exactly the elements of this set in Theorem 22. As a first attempt, (1) gives a necessary condition that allows one to exclude some words as abelian returns. This condition will not be used in the proof of Theorem 22 but, interestingly, our developments can be related to the lengths of the palindromic prefixes of f, [7, 10].

Proposition 21. For the Fibonacci word, there exist exactly two factors of length n satisfying (1) if n is a Fibonacci number. Otherwise, no factor of length n satisfies such a condition.

Proof. Consider two factors x, y of length n satisfying (1) and occurring in

                            f = 010010100100 · · · .

Assume that x starts with 0. Then to fulfill (1), y starts with 1. Since f is Sturmian, for any two words of the same length x′ and y′ which are prefixes of x and y respectively, we have ||x′|_{1} − |y′|_{1}| ≤ 1. Therefore, we deduce that x and y must be of the form x = 0u1 and y = 1u0 for some u ∈ {0, 1}^{∗}. This means that u is a bispecial factor of the Fibonacci word.

Recall that the left special factors in f are its prefixes and its right special factors are the mirror images of its prefixes [3, Prop. 4.10.3]. So bispecial factors of f are its palindromic prefixes. If (ℓ_{i})_{i≥1} denotes the increasing sequence of all lengths of palindromic prefixes in f, it is well-known that (ℓ_{i})_{i≥1} = (0, 1, 3, 6, 11, …) is given by ℓ_{i} = F_{i+1} − 2 where F_{i} is the ith Fibonacci number. See [7, Thm. 5] and [10]. Hence n must be a Fibonacci number.

Conversely, for any bispecial factor u of f, it is easy to show that either 0u0 or 1u1 is not a factor occurring in f (see for instance [14, p. 47]). Therefore, amongst the four words 0u0, 1u1, 0u1 and 1u0, the last two must occur in f and we get exactly two factors of length |u| + 2 satisfying (1). Indeed, assume that 0u0 does not occur in f. Then for u to be left (resp. right) special, 0u1 (resp. 1u0) must occur in f.

The reader may notice that the computations carried out in the proofs of the next two results could also be adapted to other Sturmian words.

Theorem 22. The set APR_{f} of abelian returns to prefixes for the Fibonacci word f contains exactly the words 0, 1, 01, 10, 001.

Proof. Using the same notation as in Theorem 19, for c = 7, we have D(7) ≈ 0.145898 which is such that 2D(7) < min{1/τ^{2}, 1 − 1/τ^{2}} ≈ 0.381. Hence, all abelian returns to prefixes of the Fibonacci word have length at most 7. Actually, this value can be reduced:

Lemma 23. There is no abelian return of length greater than 3 to prefixes in the Fibonacci word.

Proof. With the notation of the proof of Theorem 19, we set ρ = α = 1/τ^{2} ≈ 0.381. Let i be a natural number. Define the four points ρ_{i,t} = R_{α}^{i+t}(ρ) for t = 0, 1, 2, 3.

Recall that, for all k ≥ 1, the unit circle [0, 1) is split into two half-intervals I_{H}(k) = [1 − {kα}, 1) and I_{L}(k) = [0, 1 − {kα}) such that two factors f[i, i + k − 1] and f[j, j + k − 1] are abelian equivalent if and only if the points R_{α}^{i}(ρ) and R_{α}^{j}(ρ) belong to the same interval I_{H}(k) or I_{L}(k).

Let I be any of the two intervals I_{H}(k) or I_{L}(k). What we are going to prove is that if ρ and ρ_{i,0} belong to I, then either ρ_{i,2} or ρ_{i,3} belongs to I. In other words, if f[i, i + k − 1] ∼_{ab} f[0, k −1], then either f[i+2, i+k +1] or f[i+3, i+k +2] is abelian equivalent to f[i, i+k −1] which gives the upper bound on the length of any abelian return to a prefix of f.

Note, that ρ_{i,0} = R_{δ}(ρ_{i,2}), ρ_{i,2} = R_{−δ}(ρ_{i,0}) and ρ_{i,3} = R_{α−δ}(ρ_{i,0}), where δ = 1 − 2α ≈ 0.2361. Assume that the factor of length k starting in position i is abelian equivalent to the prefix of f of length k, i.e., ρ and ρ_{i,0} are both light or heavy words. We consider two cases. Suppose first that ρ, ρ_{i,0} ∈ I_{L}(k). In this case, we have [0, ρ] ⊆ I_{L}(k).

• If ρ ≤ ρ_{i,0} < 1, then [0, ρ_{i,0}] ⊆ I_{L}(k) and 0 < ρ_{i,2} = R_{−δ}(ρ_{i,0}) < ρ_{i,0}. Thus ρ_{i,2} belongs also to I_{L}(k).

• If ρ > ρ_{i,0} > 0, either ρ_{i,0} ≥ δ and then ρ_{i,2} = R_{−δ}(ρ_{i,0}) ∈ [0, ρ) meaning that ρ_{i,2} ∈ I_{L}(k) or, 0 < ρ_{i,0} < δ, i.e., −δ < ρ_{i,2} − 1 < 0 and then 0 < α − δ < ρ_{i,3} = R_{α}(ρ_{i,2}) < ρ meaning that ρ_{i,3} ∈ I_{L}(k).

Suppose now that ρ, ρ_{i,0} ∈ I_{H}(k). In this case, as ρ ∈ I_{H}(k), we have [ρ, 1) ⊆ I_{H}(k).

• If ρ > ρ_{i,0} > 0, then [ρ_{i,0}, 1) ⊆ I_{H}(k) and ρ_{i,3} = R_{α−δ}(ρ_{i,0}) belongs to I_{H}(k).

• If ρ ≤ ρ_{i,0} < 1, either ρ_{i,0} ≥ ρ+δ and then ρ_{i,2} = R_{−δ}(ρ_{i,0}) ∈ I_{H}(k) or, ρ ≤ ρ_{i,0} < ρ+δ, i.e., ρ − δ ≤ ρ_{i,2} < ρ and then ρ < ρ − δ + α ≤ ρ_{i,3} = R_{α}(ρ_{i,2}) < ρ + α < 1 meaning that ρ_{i,3} ∈ I_{H}(k).

The factors of length at most 3 occurring in f are ε, 0, 1, 00, 01, 10, 001, 010, 100 and 101. Clearly, 00, 010 and 101 do not satisfy (1) and cannot be abelian returns. To conclude the proof, we just have to show that 100 is also forbidden.

Lemma 24. The set APR_{f} of abelian returns to prefixes for the Fibonacci word f does not contain 100.

Proof. We continue with notation of Lemma 23. Suppose that 100 ∈ APR_{f}. There exists a prefix p of f of length k and a position i ≥ 0 such that

1. f[i, i + 2] = 100,

2. f[i, i + k − 1] ∼_{ab} p, i.e., ρ and ρ_{i,0} belong to the same interval I ∈ {I_{L}(k), I_{H}(k)},

3. for t = 1, 2, f[i + t, i + t + k − 1] ≁_{ab} p, i.e., ρ_{i,1} and ρ_{i,2} do not belong to I,

4. f[i + 3, i + 2 + k] ∼_{ab} p.

To get a contradiction, let us prove that either ρ_{i,1} or ρ_{i,2} belongs to I. Since f_{i} = 1, ρ_{i,0} belongs to I_{1} = [1 − α, 1). If I = I_{L}(k), then we have ρ_{i,1} ∈ [0, ρ) ⊆ I_{L}(k). If I = I_{H}(k), then we have ρ_{i,2} ∈ [ρ, ρ + α) ⊆ I_{H}(k).

That concludes the proof of Theorem 22.

4.4 Link with abelian complexity

The abelian complexity of an infinite word x is the function p_{x}^{ab} : ℕ → ℕ that maps n ≥ 0 to the number of distinct abelian equivalence classes of factors of length n in x. Let C > 0. Recall that an infinite word x ∈ A^{ω} is C-balanced, if for all u, v ∈ Fac(x) such that |u| = |v|, we have ||u|_{a} − |v|_{a}| ≤ C for all a ∈ A.

Lemma 25. [18] An infinite word has bounded abelian complexity if and only if it is Cbalanced for some C > 0.

Proposition 26. If x is an abelian recurrent word such that APR_{x} is finite, then x has bounded abelian complexity.

Proof. Suppose x satisfies the assumptions of the proposition but that x has unbounded abelian complexity. From the previous lemma, we deduce that there exists a symbol a such that the maximum of differences |u|_{a} − |v|_{a} for factors u, v in x having equal length can be arbitrarily large.

Let δ > 0. There exist u, v ∈ Fac(x) of equal length n such that |u|_{a} − |v|_{a} ≥ δ. Let p = x_{0}x_{1} … x_{n−1} be the prefix of length n of x. Without loss of generality, we may assume that

||u|_{a} − |p|_{a}| ⩾ \frac{δ}{2}.

Indeed, if ||u|_{a}−|p|_{a}| < δ/2 and ||v|_{a}−|p|_{a}| < δ/2, then one would deduce that ||u|_{a}−|v|_{a}| < δ.

As x is abelian recurrent, factors abelian equivalent to p (resp. to u) occur infinitely often in x. Therefore there exist i < j < k such that 1. x[i, i + n − 1] ∼_{ab} p, x[k, k + n − 1] ∼_{ab} p,

2. for all t such that i < t < k, we have x[t, t + n − 1] ≁_{ab} p,

3. x[j, j + n − 1] ∼_{ab} u.

This just means that we can consider two consecutive factors abelian equivalent to p separated by a factor abelian equivalent to u. Note that, for all t,

||x[t + c, t + n − 1 + c]|_{a} − |x[t, t + n − 1]|_{a}| ⩽ c, ∀c ≤ n.

Hence, j −i ≥ δ/2 and k −j ⩾ δ/2. Therefore we get k −i ≥ δ which means that the abelian return x[i, k − 1] to the prefix p has length at least δ. As δ can be chosen arbitrarily large, the set APR_{x} is infinite and that is a contradiction.

Note that any Sturmian word x satisfies p_{x}^{ab}(n) = 2 for all n ≥ 1 : there are exactly two kinds of factors of length n, the light ones and the heavy ones. But thanks to Theorem 19, if x is a Sturmian word with null intercept, then APR_{x} is infinite. In other words, bounded abelian complexity does not imply the finiteness of APR_{x}.

5 Abelian derived sequences

We refer the reader to definitions and notation introduced in Section 2.1. As was studied by Durand [9] for classical return words, we introduce the notion of abelian derived sequence which is the factorization of an infinite word with respect to its abelian returns to prefixes in their order of occurrence. The next result allows us to define such a sequence.

Lemma 27. Let u be a prefix of a uniformly recurrent word x. The word x has a factorization as a sequence m_{0}m_{1}m_{2} ⋯ of elements in APR_{x,u} computed as follows. Consider the sequence of indices (i_{n})_{n≥0} such that, for all j ≥ 0, x[i_{j}, i_{j} + |u| − 1] ∼_{ab} u and, for all i ∉ {i_{n} | n ≥ 0}, we have x[i, i + |u| − 1] ≁_{ab} u. Set m_{n} := x[i_{n}, i_{n+1} − 1].

As shown in Example 29, the factorization of x with elements in APR_{x,u} is not necessarily unique.

Definition 28. We define a map μ_{x,u} : APR_{x,u} → {1, …, #(APR_{x,u})} =: A_{x,u} analogous to Λ_{x,u}. The abelian derived sequence E_{u}(x) is the corresponding infinite word

μ_{x,u}(m_{0})μ_{x,u}(m_{1})μ_{x,u}(m_{2}) ⋯

over A_{x,u} where the sequence m_{0}m_{1}m_{2} ⋯ ∈ APR_{x,u}^{ω} is the one computed in the previous lemma. The inverse map μ_{x,u}^{−1} defines a morphism θ_{x,u} from A_{x,u}^{∗} to APR_{x,u}^{∗}

Observe that E_{u}(x) is uniformly recurrent. Indeed, if a_{1} ⋯ a_{n} is a factor occurring in E_{u}(x), it comes from a factor m_{1} ⋯ m_{n} ∈ APR_{x,u}^{∗} such that m_{1} ⋯ m_{n}v occurs in x for some v ∼_{ab} u and μ_{x,u}(m_{1}) ⋯ μ_{x,u}(m_{n}) = a_{1} ⋯ a_{n}. Since x is uniformly recurrent, m_{1} ⋯ m_{n}v occurs infinitely often with bounded gaps in x.

Example 29. Consider the Thue–Morse word where the first few symbols are

         t = 01101001100101101001011001101001100101100110100101 · · · .

Take the prefix u = 011. We get the derived sequence over R_{t,u} = {1, …, 4}

        D_{u}(t) = 12341243123431241234124312412343123412431234312412 · · ·

where the set of return words to u in order of occurrence in t is given by

                   R_{t,u} = {011010, 011001, 01101001, 0110}.

The abelian derived sequence over A_{t,u} = {1, …, 6} is

        E_{u}(t) = 12314212521612314216125212314212521612521231421612 · · ·

where the set of abelian returns to u in order of occurrence in t is given by

                   APR_{t,u} = {0, 1, 1010, 1100, 10100, 110}.

Note that, since 0, 1 ∈ APR_{t,u}, there are infinitely many factorizations of t in terms of elements belonging to APR_{t,u}.

Proposition 30. Let u be a prefix of a uniformly recurrent word x. There exists a morphism h_{u} from R_{x,u} to A_{x,u}^{∗} such that h_{u}(D_{u}(x)) = E_{u}(x).

Proof. Each return word m occurring in x is followed by u. Consider the procedure of Lemma 27 applied to mu. It will define the image by h_{u} of Λ_{x,u}(m). Indeed, one has to take into account a factor u appended to m because some suffix of m and a prefix of u can give a word v ∼_{ab} u leading to some abelian return in the decomposition of m. More precisely, we consider all the occurrences 0 = i_{1} < ⋯ < i_{t} = |m| of factors abelian equivalent to u in w = mu. Then

h_{u}(Λ_{x,u}(m)) := μ_{x,u}(w[i_{1}, i_{2} − 1]) ⋯ μ_{x,u}(w[i_{t−1}, i_{t} − 1]).

Example 31 (Example 29 continued). There exists a morphism h_{u} from R_{t,u} to A_{t,u}^{∗} such that h_{u}(D_{u}(t)) = E_{u}(t). Take

h_{u}(1) = 123, h_{u}(2) = 142, h_{u}(3) = 1252, h_{u}(4) = 16.

Let us explain how to get h_{u}(2). We have the following factorization where the vertical bars indicate the occurrence of a factor abelian equivalent to u:

Λ_{t,u}^{−1}(2) u = (|0|1100|1) 011.

Definition 32. A map h : A^{ω} → B^{ω} is a t-block morphism, if there exists some map f : A^{t} → B^{∗} such that, for all w ∈ A^{ω},

h(w) = f(w[0, t − 1])f(w[1, t])f(w[2, t + 1]) · · · .

By abuse of notation, the second map f will also be denoted by h.

Proposition 33. Let u be a prefix of a uniformly recurrent word x. Let v be a prefix of y = E_{u}(x). There exist t ≤ |u| − 1 and a t-block morphism h_{u,v} : (A_{y,v})^{t} → A_{x,u}^{∗} such that

h_{u,v}(E_{v}(E_{u}(x))) = E_{u}(x).

Proof. Note that any element θ_{x,u}(θ_{y,v}(a)) with a ∈ A_{y,v} is a concatenation of abelian returns to u. Now consider a factor a_{0}a_{1} ⋯ a_{t−1} occurring in E_{v}(E_{u}(x)). We have to determine the unique factorization of θ_{x,u}(θ_{y,v}(a_{0})) with abelian returns to u given by Lemma 27. This one is completely determined when one knows the |u| − 1 symbols occurring next. Without that extra knowledge we cannot uniquely determine the factorization for the last |u| − 1 symbols possibly occurring in θ_{x,u}(θ_{y,v}(a_{0})). This is the reason to consider the suffix a_{1} ⋯ a_{t−1} in such a way that θ_{x,u}(θ_{y,v}(a_{1})) ⋯ θ_{x,u}(θ_{y,v}(a_{t−1})) has length at least |u| − 1. One takes t large enough to ensure this property for any initial symbol a_{0} ∈ A_{y,v}. More precisely, consider all the occurrences 0 = i_{1} < ⋯ < i_{s} of factors abelian equivalent to u in w = θ_{x,u}(θ_{y,v}(a_{0})) ⋯ θ_{x,u}(θ_{y,v}(a_{t−1})). Let r be the largest integer such that i_{r} < |θ_{x,u}(θ_{y,v}(a_{0}))|. Then

h_{u,v}(a_{0} ⋯ a_{t−1}) := μ_{x,u}(w[i_{1}, i_{2} − 1]) ⋯ μ_{x,u}(w[i_{r}, i_{r+1} − 1]).

Note that the above definition is only meaningful if a_{0} ⋯ a_{t−1} is a factor of E_{v}(E_{u}(x)). Since this is the only relevant situation, in any other case, the image of h_{u,v} is set to ε.

Observe that if we iterate the process, since the composition of a t-block morphism and an s-block morphism is an (st)-block morphism, then there exists an r-block morphism h such that h(E_{u_{k}}(⋯ (E_{u_{2}}(E_{u_{1}}(x))) ⋯)) = E_{u_{1}}(x) where prefixes u_{1}, …, u_{k} are considered accordingly.

Example 34 (Example 29 continued). We can iterate the process of computing the abelian derived sequence, for instance by taking each time the corresponding prefix of length 3:

     E_{123}(E_{011}(t)) = 12131415121315141213141514121315121314151213151412 · · · ,
  E_{121}(E_{123}(E_{011}(t))) = 12341243123431241234124312412343123412431234312412 · · · ,
E_{123}(E_{121}(E_{123}(E_{011}(t)))) = 12341432123432141234143214123432123414321234321412 · · · .

Let us illustrate the previous result. Take again u = 011, y = E_{u}(t), v = 123. We have

       APR_{y,v} = {1, 23142125216, 23142161252, 231421252161252, 2314216}.

Observe that θ_{t,u}(θ_{y,v}(1)) = θ_{t,u}(1) = 0 and, for all a ∈ {2, …, 5}, θ_{y,v}(a) has a prefix 23, so θ_{t,u}(θ_{y,v}(a)) has prefix 110 ∼_{ab} u. Let us assume that h_{u,v} is a 3-block morphism. We define h_{u,v}(1ab) = 1, for all a, b ∈ A_{y,v} and a ≠ 1. We get h_{u,v}(213) = 23142125216 because, if vertical bars denote occurrences of a factor abelian equivalent to u, we get the following factorization:

θ_{t,u}(θ_{y,v}(2)) θ_{t,u}(θ_{y,v}(13)) =

          (|1|1010|0|1100|1|0|1|10100|1|0|110) |011010011001011001101001.

Proposition 35. Let σ be a primitive substitution and u be a prefix of its fixed point x = σ(x) ∈ A^{ω}. There exists a 2-block morphism σ_{u} : A_{x,u}^{∗} → A_{x,u}^{∗} such that E_{u}(x) is fixed point of σ_{u} and

θ_{x,u}(σ_{u}(E_{u}(x))) = σ(θ_{x,u}(E_{u}(x))).

Proof. We may replace σ by a convenient power of σ in such a way that, for all a ∈ A, σ(a) contains an occurrence of a factor abelian equivalent to u. For all a, b ∈ A_{x,u}, consider all the occurrences i_{1} < ⋯ < i_{t} of a factor abelian equivalent to u occurring in w = σ(θ_{x,u}(ab)). With our choice of σ, at least one of these i_{j} belongs to [0, |σ(θ_{x,u}(a))|−1] (resp. [|σ(θ_{x,u}(a))|, |w| − 1]). Let r be the largest integer such that i_{r} < |σ(θ_{x,u}(a))|. We define

σ_{u}(ab) = μ_{x,u}(w[i_{1}, i_{2} − 1]) ⋯ μ_{x,u}(w[i_{r}, i_{r+1} − 1]).

Corollary 36. Let σ be a primitive substitution and u be a prefix of its fixed point x = σ(x) ∈ A^{ω}. The sequence E_{u}(x) is primitive substitutive, i.e., there exists a primitive morphism τ_{u} : B → B^{∗} and a coding ϕ : B → A_{x,u} such that E_{u}(x) = ϕ(τ_{u}^{ω}(b)) for some b ∈ B.

Proof. We may replace σ by a convenient power of σ in such a way that, for all a ∈ A, σ(a) contains occurrences of two factors abelian equivalent to u. Consider the alphabet

B = {(a, b) | a, b ∈ A_{x,u} ∧ ab is a factor of E_{u}(x)}.

For all a, b ∈ A_{x,u} such that (a, b) ∈ B, consider all the occurrences i_{1} < ⋯ < i_{t} of a factor abelian equivalent to u occurring in w = θ_{x,u}(ab). Let r be the smallest integer such that i_{r} ≥ |θ_{x,u}(a)|. Note that r ≥ 3. We define

τ_{u}((a, b)) = (μ_{x,u}(w[i_{1}, i_{2}−1]), μ_{x,u}(w[i_{2}, i_{3}−1])) ⋯ (μ_{x,u}(w[i_{r−1}, i_{r} −1]), μ_{x,u}(w[i_{r}, i_{r+1}−1])).

Let e_{0}e_{1} be the prefix of length 2 of E_{u}(x). We have

E_{u}(x) = ϕ(τ_{u}^{ω}((e_{0}, e_{1})))

where ϕ : B → A_{x,u} is the coding that maps (a, b) ∈ B to a.

Observe that, for all (a, b) ∈ B, |τ_{u}^{n}((a, b))| ≥ 2^{n}. Let us show that τ_{u} is primitive. Since E_{u}(x) is uniformly recurrent, there exists K such that any factor of length K of E_{u}(x) contains all elements in {cd | (c, d) ∈ B}. Therefore any factor of length K of τ_{u}^{ω}((e_{0}, e_{1})) contains all the elements of B. Take N such that 2^{N} ≥ K. Then, for all (a, b), (c, d) ∈ B, τ_{u}^{N}((a, b)) contains (c, d) which means that τ_{u} is primitive.

Example 37 (Example 29 continued). Take again u = 011 and the morphism σ : 0 ↦ 01101001, 1 ↦ 10010110 generating t. We have

σ(θ_{t,u}(12)) = (|0|1|1010|0|1)100|1|0|110 and σ_{u}(12) = 12314
σ(θ_{t,u}(23)) = (100|1|0|1|10)100|1|0|110 ⋯ and σ_{u}(23) = 2125

       σ(θ_{t,u}(31)) = (100|1|0|110|0|1|1010|0|1100|1|0|110|0|1|10100|1)|0|1|101001
                        and σ_{u}(21) = 216123142161252.

Using the above corollary, we get

τ_{u}(1, 2) = (1, 2)(2, 3)(3, 1)(1, 4)(4, 2), τ_{u}(2, 3) = (2, 1)(1, 2)(2, 5)(5, 2), ….

5.1 Abelian derivatives of the Thue–Morse word

Proposition 38. For the Thue–Morse word t, the set {E_{u}(t) | u ∈ Pref(t)} is infinite.

Proof. It is sufficient to show that the set {E_{u}(t) | u ∈ Pref(t) : |u| ≡ 1 (mod 2)} is infinite. Proceed by contradiction and suppose that the set {E_{u}(t) | u ∈ Pref(t) : |u| ≡ 1 (mod 2)} is finite. Then there exist u and v distinct prefixes of odd length of the Thue–Morse word t such that E_{u}(t) = E_{v}(t). Since APR_{t} is finite, we can moreover assume that θ_{t,u} = θ_{t,v}. Indeed, infinitely many sequences of the kind E_{u}(t) are equal and thus defined on the same alphabet A_{t,u}. For all such sequences, there are finitely many morphisms of the kind θ_{t,u} associating with each element of A_{t,u} an element of the finite set APR_{t}. So we can impose the extra condition on θ_{t,u}. Let

I(w) := {i ∈ ℕ | t[i, i + |w| − 1] ∼_{ab} w}

denote the set of occurrences of factors of t abelian equivalent to a word w. We have I(u) = I(v) as θ_{t,u} = θ_{t,v}. Without loss of generality, we may suppose that |u| = 2k + 1, |v| = 2ℓ + 1 with k < ℓ. We have Ψ(u) = (k, k + 1) or Ψ(u) = (k + 1, k) and Ψ(v) = (ℓ, ℓ + 1) or Ψ(v) = (ℓ+1, ℓ). Let a_{u} (resp. a_{v}) denote the letter having k +1 (resp. ℓ+1) occurrences in the prefix u (resp. v). Note that a_{u} and a_{v} are respectively the last letters of u and v.

For any odd position j, recalling that t[2m, 2m + 1] ∈ {10, 01}, we have

t_{j} = a_{u} ⇔ t[j, j + |u| − 1] ∼_{ab} u ⇔ t[j, j + |v| − 1] ∼_{ab} v ⇔ t_{j} = a_{v}

where the central equivalence comes from the fact that I(u) = I(v). As there exists at least one such j, we have a_{u} = a_{v} =: a.

For any even position j, we have

t_{j+|u|−1} = a ⇔ j ∈ I(u) ⇔ j ∈ I(v) ⇔ t_{j+|v|−1} = a

since I(u) = I(v). Using this observation, we can show by induction that

t_{|u|−1+n(|v|−|u|)} = a

for all n ∈ ℕ. In other words, there exists a constant infinite arithmetical subsequence in t, which is a contradiction, since it is well-known that the Thue-Morse word does not contain any such subsequence. Indeed, for n = 0, it is clear that the last letter of u is a. Suppose now that the result holds true for n ≥ 0. We have t_{|u|−1+n(|v|−|u|)} = a. Since |u|, |v| are odd, n(|v| − |u|) is an even number and belongs to I(u) = I(v). Therefore t_{|v|−1+n(|v|−|u|)} = a and |v| − 1 + n(|v| − |u|) = |u| − 1 + (n + 1)(|v| − |u|).

Remark 39. Using the same notation as in the previous proof, we show that the set {E_{u}(t) | u ∈ Pref(t) : |u| ≡ 0 (mod 2)} is infinite. Proceed by contradiction. Then there exist u and v distinct prefixes of even length of t such that E_{u}(t) = E_{v}(t) and θ_{t,u} = θ_{t,v}. Hence I(u) = I(v). Note that 2ℕ ⊆ I(u) = I(v). Suppose that |u| = 2k, |v| = 2ℓ, with k < ℓ. Since a prefix of even length has a Parikh vector of the kind (r, r), 2i+1 is in I(u) if and only if t_{i} = t_{i+k}. Similarly, 2i + 1 is in I(v) if and only if t_{i} = t_{i+ℓ}. From I(u) \ 2ℕ = I(v) \ 2ℕ, we deduce that, for all i ∈ ℕ, t_{i} = t_{i+k} implies t_{i} = t_{i+ℓ} and conversely. This leads to the contradiction that t is ultimately periodic of period ℓ − k. Indeed, suppose to the contrary that for some i, t_{i+k} ≠ t_{i+ℓ}. In this case, either t_{i+k} or t_{i+ℓ} is equal to t_{i}. From our last deduction, we get that all three letters t_{i}, t_{i+k}, t_{i+ℓ} are equal.

Remark 40. Using the same notation as in the previous remark, there exist no prefixes u, v of t such that |u| is even, |v| is odd and I(u) = I(v). (The symmetric case can be treated in the same way.) Assume that |u| = 2k, |v| = 2ℓ + 1 for some positive integers k ≠ ℓ. We get Ψ(u) = (k, k) and Ψ(v) = (ℓ, ℓ + 1) or Ψ(v) = (ℓ + 1, ℓ). Let a denote the letter that has ℓ + 1 occurrences in v. As v ∈ Pref(t), t_{|v|−1} = a. Note that, for all even positions j, if j is in I(v), then t_{j+|v|−1} = a. Moreover, for all even j, we have j ∈ I(u). Since I(u) = I(v), we get 2ℕ ⊆ I(v) and thus t_{j+|v|−1} = a for all even j. Therefore, for all even j ≥ |v| − 1, we have t_{j} = a and also t_{j+1} = 1 − a since t is made up of blocks 01 or 10. This means that the Thue–Morse word is ultimately periodic of period 2 which is a contradiction.

6 Acknowledgment

The authors are very pleased to contribute to this special issue in honor of Jean-Paul Allouche. This is a nice way to wish him a happy birthday with some combinatorial flavor. In particular, the first author is very grateful to Jean-Paul Allouche who is always enthusiastic, positive and ready to usefully comment on his research work.

References

[1] J.-P. Allouche and J. Shallit, The ubiquitous Prouhet-Thue-Morse sequence. Sequences and their Applications (Singapore, 1998), 1–16, Springer Ser. Discrete Math. Theor. Comput. Sci., Springer, London, (1999).

[2] J.-P. Allouche and J. Shallit, Automatic Sequences, Theory, Applications, Generalizations, Cambridge University Press (2003).

[3] J. Cassaigne and F. Nicolas, Factor complexity, in V. Berthé and M. Rigo, eds., Combinatorics, Automata and Number Theory, Encyclopedia Math. Appl., 135, Cambridge Univ. Press, 2010, pp. 163–247.

[4] M. Boshernitzan, A condition for minimal interval exchange maps to be uniquely ergodic, Duke Math. J. 52 (1985), 723–752.

[5] E. M. Coven and G. A. Hedlund, Sequences with minimal block growth, Math. Systems Theory 7 (1973), 138–153.

[6] F. M. Dekking, Strongly non-repetitive sequences and progression-free sets, J. Comb. Theory Ser. A 27 (1979), 181–185.

[7] A. de Luca, Sturmian words: structure, combinatorics, and their arithmetics, Theoret. Comput. Sci. 183 (1997), 45–82.

[8] M. Denker, C. Grillenberger, and K. Sigmund, Ergodic Theory on Compact Spaces, Lecture Notes in Mathematics, Vol. 527, Springer-Verlag, (1976).

[9] F. Durand, A characterization of substitutive sequences using return words, Discrete Math. 179 (1998), 89–101.

[10] S. Fischler, Palindromic prefixes and episturmian words, J. Combin. Theory Ser. A 113 (2006), 1281–1304.

[11] C. Holton and L. Q. Zamboni, Descendants of primitive substitutions, Theory Comput. Syst. 32 (1999), 133–157.

[12] J. Justin and L. Vuillon, Return words in Sturmian and episturmian words, Theor. Inform. Appl. 34 (2000), 343–356.

[13] M. Lothaire, Combinatorics on Words, Cambridge Mathematical Library, Cambridge University Press, 1997.

[14] M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications 90, Cambridge University Press, 2002.

[15] J. F. Morgenbesser, J. Shallit, and T. Stoll, Thue-Morse at multiples of an integer, J. Number Theory 131 (2011), 1498–1512.

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

[17] S. Puzynina and L. Q. Zamboni, Abelian returns in Sturmian words, J. Combin. Theory Ser. A 120 (2013), 390–408.

[18] G. Richomme, K. Saari, and L. Q. Zamboni, Abelian complexity of minimal subshifts, J. London Math. Soc. 83 (2011), 79–95.

[19] P. Salimov, Uniform recurrence of a direct product, Discrete Math. Theor. Comput. Sci. 12 (2010), 1–8.

[20] L. Vuillon, A characterization of Sturmian words by return words, European J. Combin. (2001) 22, 263–275.

2010 Mathematics Subject Classification: Primary 68R15; Secondary 68Q68. Keywords: return word, recurrence, abelian equivalence, Sturmian word.

(Concerned with sequences \underline{A001911}, \underline{A003622}, \underline{A003849}, \underline{A010060}, and \underline{A022342}.)

Received June 2 2012; revised version received September 24 2012. Published in Journal of Integer Sequences, March 2 2013.

Return to Journal of Integer Sequences home page.