INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5 (2005), #A14

COMPLETE CHARACTERIZATION OF SUBSTITUTION INVARIANT STURMIAN SEQUENCES

Peter Baláži, Zuzana Masáková^{1}, Edita Pelantová

Department of Mathematics, Czech Technical University, Trojanova 13, 120 00 Praha 2, Czech Republic

Received: 2/18/04, Revised: 5/25/05, Accepted: 7/6/05, Published: 7/8/05

Abstract

We provide a complete characterization of substitution invariant inhomogeneous bidirectional pointed Sturmian sequences. The result is analogous to that obtained by Berthé et al. [5] and Yasutomi [21] for one-directional Sturmian words. The proof is constructive, based on the geometric representation of Sturmian words by a cut-and-project scheme.

1. Introduction

Sturmian words have been extensively studied from many aspects. Several equivalent definitions as aperiodic words of minimal complexity C(n) = n + 1, as balanced aperiodic sequences or as mechanical words have been derived already in [9, 16]. Recently, new characterizations have been developed using return words [20] or using palindromic structure [10]. For a survey of results known on Sturmian words we refer, for example, to [14, 4].

Among the properties of Sturmian words that have been in focus during the past few years is their invariance under non-trivial substitutions and a weaker property of substitutivity, according to the slope α and intercept β of the Sturmian word. If β = 0, the Sturmian word is called homogeneous, otherwise inhomogeneous. The first results of this kind are found in [7]. Then it has been shown independently by several authors [8, 12, 13, 3] that a homogeneous one-directional Sturmian word is invariant under a substitution if and only if the slope α is a Sturm number. Parvaix [17] has given a sufficient condition for an inhomogeneous one-directional Sturmian word to be substitution invariant. However, his condition does not include all substitution invariant Sturmian words. In another paper [18] he studies inhomogeneous bi-directional non-pointed Sturmian words and proves that they are invariant under substitution if and only if the slope α is a Sturm number and the intercept β belongs to the field ℚ(α). Yasutomi [21] solved the question of substitution invariance of inhomogeneous one-directional Sturmian sequences. Berthé et al. [5] give an alternative proof and describe the matrices of the corresponding substitutions.

1Corresponding author. Email: masakova@km1.fjfi.cvut.cz

The question of substitutivity of Sturmian words seems to be less difficult to solve. It has been derived in [6] that Sturmian words are substitutive if and only if their slope α is a quadratic number and the intercept β belongs to ℚ(α). This is in fact a result analogous to [1], which provides a characterization of substitutive words coding 3-interval exchanges.

In our paper we provide a complete characterization of substitution invariant inhomogeneous bi-directional pointed Sturmian sequences. The result is analogous to that of [21, 5]. However, the method used here is rather simpler and novel in the study of substitution properties of Sturmian words. It is based on the geometric representation of Sturmian words by a cut-and-project scheme. It is worth noting that similar reasoning can be used for characterizing substitution invariant infinite words that code an orbit under a 3-interval exchange transformation. An important advantage is that our paper is self-contained and does not use any deep results from elsewhere, except the simple fact that incidence matrix of Sturmian morphisms has unit determinant, which follows from [3]. The main result proved in our paper is the following.

Theorem 1.1. Let α be an irrational number, α ∈ (0, 1), β ∈ [0, 1). The pointed bidirectional Sturmian word with slope α and intercept β is invariant under a non-trivial substitution if and only if the following three conditions are satisfied:

(i) α is a quadratic irrational with conjugate α′ ∉ (0, 1), i.e. α is a Sturm number,

(ii) β ∈ ℚ(α),

(iii) α′ ≤ β′ ≤ 1 − α′ or 1 − α′ ≤ β′ ≤ α′, where β′ is the image of β under the Galois automorphism of the quadratic field ℚ(α).

For the proof of Theorem 1.1 we need to recall the basic notion of substitutions (Section 2), define a geometric representation of a Sturmian word and show that it can be recast in an algebraic formalism (Section 3). Then we prove a necessary and sufficient condition for substitution invariance of Sturmian words in terms of fixed points of a map g_{λ}. This result is stated as Theorem 4.5 in Section 4 and proved in Section 5. Using the study of fixed points of g_{λ} (Section 6) we show that the condition of Theorem 4.5 is equivalent to the simple algebraic criterion given in Theorem 1.1 (Section 7). Note that the proof given here is constructive. For a given Sturmian word with slope α and intercept β that satisfies conditions (i)–(iii) of Theorem 1.1 one can determine the substitution as described in Section 8.

We use the notation ℕ for the set of positive integers and ℕ_{0} = {0} ∪ ℕ.

2. Preliminaries

In this paper we study pointed bi-directional Sturmian words

(u_{n})_{n∈ℤ} = ⋯ u_{−2}u_{−1}|u_{0}u_{1}u_{2} ⋯

For every such word (u_{n})_{n∈ℤ} there exists an irrational α ∈ (0, 1) (slope) and a real β ∈ [0, 1) (intercept) such that

either  u_{n} = \underline{s}_{α,β}(n) := ⌊(n + 1)α + β⌋ − ⌊nα + β⌋ ,  for n ∈ ℤ,
or  u_{n} = \overline{s}_{α,β}(n) := ⌈(n + 1)α + β⌉ − ⌈nα + β⌉ ,  for n ∈ ℤ.

It is obvious that (u_{n})_{n∈ℤ} is a binary word on the alphabet {0, 1}. One can show that the densities of letters 0 and 1 in the word (u_{n})_{n∈ℤ} defined above are well defined

ϱ(0) := lim_{n→∞} \frac{number of 0 in the word u_{−n} ⋯ u_{−1}|u_{0}u_{1} ⋯ u_{n}}{2n + 1} = 1 − α ,
ϱ(1) := lim_{n→∞} \frac{number of 1 in the word u_{−n} ⋯ u_{−1}|u_{0}u_{1} ⋯ u_{n}}{2n + 1} = α .

Denote A^{∗} the free monoid generated by the alphabet A = {0, 1} endowed with the operation of concatenation. A map φ of A^{∗} into itself such that φ(uv) = φ(u)φ(v) for all pairs of finite words u, v is called a morphism. The morphism is non-erasing, if φ(i) is not an empty word for any i ∈ A. A non-erasing morphism φ is called a substitution. The action of φ can be extended to infinite words (u_{n})_{n∈ℤ} = ⋯ u_{−2}u_{−1}|u_{0}u_{1}u_{2} ⋯ by ⋯ φ(u_{−2})φ(u_{−1})|φ(u_{0})φ(u_{1})φ(u_{2}) · · ·. We say that the word (u_{n})_{n∈ℤ} is invariant under the substitution φ, if

⋯ φ(u_{−2})φ(u_{−1})|φ(u_{0})φ(u_{1})φ(u_{2}) ⋯ = ⋯ u_{−2}u_{−1}|u_{0}u_{1}u_{2} ⋯

One can associate with every substitution on a binary alphabet a matrix 𝔸 ∈ ℤ^{2×2} by

𝔸_{ij} = number of letters j in the word φ(i) , i, j ∈ {0, 1} .

This matrix is called the incidence matrix of the substitution. Note that the term incidence matrix is sometimes used for the transpose 𝔸^{T}. If φ is a morphism that maps a Sturmian word to a Sturmian word, it is called Sturmian morphism. Every Sturmian morphism is clearly non-erasing, i.e. is a substitution. As a consequence of [3] the incidence matrix 𝔸 of a non-trivial (i.e. non-identic) Sturmian morphism is irreducible and has determinant ±1.

If (u_{n})_{n∈ℤ} is invariant under substitution φ and if the densities of letters 0 and 1 are well defined, then the vector (ϱ(0), ϱ(1)) is a left eigenvector of 𝔸. In particular, if a bi-directional Sturmian word of slope α is invariant under a substitution, then (1 − α, α) is a left eigenvector of the non-negative irreducible integer matrix 𝔸. This eigenvector corresponds according to Perron-Frobenius theorem to the dominant eigenvalue, say λ, of 𝔸, which is called the substitution factor.

The characteristic polynomial of the matrix 𝔸 is a monic quadratic polynomial with integer coefficients. The substitution factor λ is thus a quadratic integer. Let us denote by λ′ the algebraic conjugate of λ, i.e. the other root of the characteristic polynomial. Since det 𝔸 = ±1, we have λλ′ = ±1. The substitution factor λ is thus an algebraic unit λ > 1 and λ′ ∈ (−1, 1). Without loss of generality we consider the matrix 𝔸 of determinant +1, hence λ′ ∈ (0, 1). (If (u_{n}) is invariant under some substitution φ with matrix 𝔸, then it is invariant also under φ^{2} with matrix 𝔸^{2}.)

Necessarily, the components of the eigenvector (1−α, α) belong to the quadratic field ℚ(λ) = {a + bλ | a, b ∈ ℚ}. The Galois automorphism on this field is defined by the prescription

x = a + bλ ↦ x′ = a + bλ′ .

Since 𝔸 has integer components, its second eigenvalue is λ′ and left eigenvectors corresponding to λ′ are scalar multiples of (1 − α′, α′). As a consequence of the Perron-Frobenius theorem, the components of this eigenvector must have opposite signs, i.e. α′(1 − α′) < 0, which implies that α′ ∉ (0, 1). We have thus derived by a simple argument a necessary condition in order that a Sturmian word is invariant under a nontrivial substitution.

Proposition 2.1. If a Sturmian word with irrational slope α ∈ (0, 1) and intercept β ∈ [0, 1) is invariant under a non-trivial substitution, then α is a quadratic irrational number with algebraic conjugate α′ ∉ (0, 1).

Note that the condition given in the above proposition means that α is a Sturm number. Sturm numbers can be defined using continued fractions [8], here we use the characterization of Allauzen [2]. For β = 0 the condition is also sufficient, as it was shown by several authors [3, 8, 12, 13]. From now on we consider Sturmian words the slope of which is a Sturm number.

As we have said, bi-directional Sturmian words can be described using mechanical words \underline{s}_{α,β} or \overline{s}_{α,β}. Let (u_{n})_{n∈ℤ} be a pointed bi-directional word in the alphabet {0, 1}. Let us define a word (v_{n})_{n∈ℤ} by v_{n} = u_{−n−1}, i.e. · · · v_{−2}v_{−1}|v_{0}v_{1}v_{2} ⋯ = ⋯ u_{2}u_{1}u_{0}|u_{−1}u_{−2} · · ·. We define also an infinite word (w_{n})_{n∈ℤ} by w_{n} = 1 − v_{n} for all n ∈ ℤ. Obviously, either all the three pointed bi-directional infinite words (u_{n})_{n∈ℤ}, (v_{n})_{n∈ℤ}, (w_{n})_{n∈ℤ} are invariant under a non-trivial substitution, or none of them is. It is easy to see that

u_{n} = \underline{s}_{α,β}(n) = ⌊(n + 1)α + β⌋ − ⌊nα + β⌋

implies

v_{n} = \overline{s}_{α,1−β}(n) = ⌈(n + 1)α + 1 − β⌉ − ⌈nα + 1 − β⌉ ,
w_{n} = \underline{s}_{1−α,β}(n) = ⌊(n + 1)(1 − α) + β⌋ − ⌊n(1 − α) + β⌋ .

Therefore in the study of invariance of pointed bi-directional Sturmian sequences under a substitution we shall focus on the words \underline{s}_{α,β}. Since \underline{s}_{α,β} is invariant under a non-trivial substitution if and only if \underline{s}_{1−α,β} is, we consider without loss of generality words

u_{n} = ⌊(n + 1)α + β⌋ − ⌊nα + β⌋, n ∈ ℤ,
α ∈ (0, 1) quadratic irrational, α′ < 0, (1)
β ∈ [0, 1).

If an infinite word is invariant under a non-trivial substitution, it can be geometrically represented using a selfsimilar set Σ ⊂ ℝ. We say that Σ is selfsimilar, if there exists λ > 1 (called the selfsimilarity factor of Σ) such that λΣ ⊂ Σ. The selfsimilar set which represents a substitution invariant word is defined in the following way. Denote by ℓ(0) and ℓ(1) the components of a positive right eigenvector of the incidence matrix 𝔸 corresponding to the dominant eigenvalue λ. Define

t_{0} = 0,
t_{n} = ∑_{i=0}^{n−1} ℓ(u_{i})  for n ≥ 1,
t_{n} = − ∑_{i=n}^{−1} ℓ(u_{i}) for n ≤ −1.

Then the set Σ = {t_{n} | n ∈ ℤ} satisfies

λΣ ⊂ Σ .  (2)

From the construction of the sequence (t_{n})_{n∈ℤ} we have

t_{n+1} − t_{n} = ℓ(u_{n}) for all n ∈ ℤ.

Remark 2.2. The fact that \binom{ℓ(0)}{ℓ(1)} is a right eigenvector of the incidence matrix 𝔸 corresponding to the eigenvalue λ ensures that for every n ∈ ℤ such that t_{n+1} − t_{n} = ℓ(0), the sequence of distances in the set Σ between points λt_{n} and λt_{n+1} is the same. Similar statement is true for all n ∈ ℤ such that t_{n+1} − t_{n} = ℓ(1). This fact is illustrated on Figure 1.

Recall that if (u_{n})_{n∈ℤ} satisfies conditions (1) and is invariant under a non-trivial substitution with matrix 𝔸, then (1−α, α) is a left eigenvector of 𝔸 corresponding to the eigenvalue λ, and (1 − α′, α′) is a left eigenvector of 𝔸 corresponding to the eigenvalue

[figure: 1; 1; 1; 1; 0; 0; 1; 1; 0; 0; 1; 1; 1; _{ℓ(1)}; _{ℓ(0)}; 1; 0; 0; 1; 1; 1; 1; 0; 0; 1; 1; 0; 0; \overbrace{λℓ(1)}; \overbrace{λℓ(0)}]

Figure 1: Action of a substitution on the geometric representation of its fixed point.

λ′. Since left and right eigenvectors corresponding to different eigenvalues are mutually orthogonal, every right eigenvector of the matrix 𝔸 corresponding to the eigenvalue λ must be orthogonal to (1 − α′, α′). However, this determines the eigenvector uniquely to be, up to a scalar multiple, \binom{−α′}{1−α′}. Since α is a Sturm number and satisfies (1), both components of this vector are positive, for the geometric representation Σ of the infinite word (u_{n})_{n∈ℤ} we can choose the lengths ℓ(0) = −α′ and ℓ(1) = 1 − α′.

3. Geometric representation of Sturmian words

Let the word (u_{n})_{n∈ℤ}, and numbers α, β satisfy conditions (1). The set

Σ_{α,β} := {t_{n} | n ∈ ℤ} ,

where

t_{0} = 0  and  t_{n+1} − t_{n} = \{ \begin{matrix}−α′, & if u_{n} = 0 , \\ 1 − α′, & if u_{n} = 1 , \end{matrix}

is called the geometric representation of the word (u_{n})_{n∈ℤ}. Note that the distances between adjacent points of Σ_{α,β} depend only on the slope and not on the intercept of the corresponding Sturmian word (u_{n})_{n∈ℤ}. The distance −α′ corresponding to the letter 0 is shorter, we will use the notation S = −α′. The longer distance corresponding to the letter 0 is denoted by L = 1 − α′.

Remark 3.1. From what has been said and from Remark 2.2 it is obvious that (u_{n})_{n∈ℤ} is invariant under a non-trivial substitution if and only if there exists a quadratic unit λ > 1, with conjugate λ′ ∈ (0, 1), such that λΣ_{α,β} ⊂ Σ_{α,β}, and for every n, such that u_{n} = 0, the segments of the set Σ_{α,β} between points λt_{n} and λt_{n+1} are the same, and for every n, such that u_{n} = 1, the segments of the set Σ_{α,β} between points λt_{n} and λt_{n+1} are the same.

Let us therefore study the properties of Σ_{α,β}.

Proposition 3.2. Let α, β satisfy (1). Then

Σ_{α,β} = {a − bα′ | a − bα ∈ (β − 1, β]} .

Proof. If a − bα ∈ (β − 1, β], then a = ⌊bα + β⌋. Therefore

{a − bα′ | a − bα ∈ (β − 1, β]} = {y_{n} := ⌊nα + β⌋ − nα′ | n ∈ ℤ} .

From (1), (y_{n})_{n∈ℤ} is a strictly increasing sequence and y_{0} = 0. Let us calculate the distances between consecutive points y_{n}, y_{n+1}.

y_{n+1} − y_{n} = ⌊(n + 1)α + β⌋ − ⌊nα + β⌋ − α′ = u_{n} − α′ .

Thus (y_{n})_{n∈ℤ} = (t_{n})_{n∈ℤ}, as desired.

It is useful to introduce for a quadratic α and its algebraic conjugate α′ the sets

ℤ[α] = {a + bα | a, b ∈ ℤ}  and  ℤ[α′] = {a + bα′ | a, b ∈ ℤ} .

The above sets are generally distinct additive abelian groups, generally not closed under multiplication. (For example, the Sturm number α, root of the polynomial 2x^{2} −1, is not an algebraic integer and satisfies α^{2} = \frac{1}{2} ∉ ℤ[α].) Clearly ℤ[α] and ℤ[α′] are subsets of the field ℚ(α) = ℚ(α′). Restriction of the Galois automorphism of ℚ(α) on ℤ[α], resp. ℤ[α′] is an isomorphism between these groups. Obviously, we have

(ℤ[α])′ = ℤ[α′]  and  (ℤ[α′])′ = ℤ[α].

The set Σ_{α,β} representing the Sturmian word (u_{n})_{n∈ℤ} can therefore be written as

Σ_{α,β} = {x ∈ ℤ[α′] | x′ ∈ (β − 1, β]}.

Let us mention that Σ_{α,β} is a particular case of the so-called cut-and-project set. In fact, the abelian groups ℤ[α], ℤ[α′] arise by projection of points of the lattice ℤ^{2} to the lines with slopes α′, α respectively. More precisely, every lattice point (−b, a) ∈ ℤ^{2} can be written as

(−b, a) = (a + bα)x⃗_{1} + (a + bα′)x⃗_{2} ,

where

x⃗_{1} = \frac{1}{α′ − α}(1, α′) and x⃗_{2} = \frac{1}{α − α′} (1, α) .

The isomorphism a + bα ↦ (a + bα)′ = a + bα′ between ℤ[α] and ℤ[α′] is a correspondence between two projections of the same lattice point. A cut-and-project sequence is constructed by first projection of lattice points which have the second projection in a bounded interval Ω; this amounts to

Σ_{α}(Ω) = {x ∈ ℤ[α′] | x′ ∈ Ω} .

[figure: Ω {; slope α′; slope α; Σ_{α,β}; L; S; L; S; L; L; S; L]

Figure 2: Construction of a cut-and-project sequence.

In this notation, we have Σ_{α,β} = Σ_{α}((β − 1, β]). The construction of Σ_{α,β} as a cut-and-project set is illustrated on Figure 2. For more details about the general definition of cut-and-project sets we refer to [15], the onedimensional case useful for our considerations is described together with its properties in [11].

The following proposition shows the relation of the selfsimilarity factor of Σ_{α,β} to the abelian group ℤ[α′].

Proposition 3.3. Let α, β satisfy conditions (1) and let λ > 1 be a quadratic unit with λ′ ∈ (0, 1). Then λΣ_{α,β} ⊂ Σ_{α,β} if and only if λℤ[α′] = ℤ[α′].

Proof. First let us show that the selfsimilarity of Σ_{α,β} implies λℤ[α′] = ℤ[α′]. Find n, m ∈ ℤ, so that t_{n+1} − t_{n} = −α′, t_{m+1} − t_{m} = 1 − α′.

\begin{matrix}λt_{n+1}, λt_{n} ∈ Σ_{α,β} ⊂ ℤ[α′] & ⟹ & −λ(t_{n+1} − t_{n}) = λα′ ∈ ℤ[α′] \\ λt_{m+1}, λt_{m} ∈ Σ_{α,β} ⊂ ℤ[α′] & ⟹ & λ(1 − α′) ∈ ℤ[α′] \end{matrix} \} ⟹ λ ∈ ℤ[α′].

Since λ · 1 and λα′ belong to ℤ[α′] and from the fact that ℤ[α′] is closed under addition, it follows that λℤ[α′] ⊂ ℤ[α′].

Since λ is a unit, it satisfies λ^{2} + Aλ + 1 = 0 for some A ∈ ℤ. We thus have λ^{−1} = −(λ+A) ∈ ℤ[α′] and λ^{−1}α′ = −(λ+A)α′ ∈ ℤ[α′], which together imply λ^{−1}ℤ[α′] ⊂ ℤ[α′], which completes the first part of the proof.

For the opposite implication let us show that λℤ[α′] = ℤ[α′] implies λΣ_{α}(Ω) = Σ_{α}(λ′Ω) for every bounded interval Ω. It is a consequence of the following equalities,

\begin{aligned}λΣ_{α}(Ω) & = λ\{x ∈ ℤ[α′] | x′ ∈ Ω\} = \{λx ∈ λℤ[α′] | λ′x′ ∈ λ′Ω\} = \\ & = \{y ∈ ℤ[α′] | y′ ∈ λ′Ω\} = Σ_{α}(λ′Ω) . \end{aligned}

Directly from the definition of Σ_{α}(Ω) it follows that Σ_{α}(Ω_{1}) ⊂ Σ_{α}(Ω_{2}) if Ω_{1} ⊂ Ω_{2}. Since 0 ∈ (β − 1, β] and λ′ ∈ (0, 1), we have λ′(β − 1, β] ⊂ (β − 1, β] and therefore

λΣ_{α,β} = Σ_{α}(λ′(β − 1, β]) ⊂ Σ_{α}((β − 1, β]) = Σ_{α,β} .

As a byproduct of the proof of the above proposition we have the following result.

Corollary 3.4. Let α satisfy (1) and let λℤ[α′] = ℤ[α′]. Then λΣ_{α}(Ω) = Σ_{α}(λ′Ω) for every bounded interval Ω.

4. A necessary and sufficient condition

Let us study the structure of the set Σ_{α,β}. Since Σ_{α,β} ⊂ ℤ[α′], every element of Σ_{α,β} is of the form x′, where x′ is the image of an x ∈ ℤ[α] ∩ (β − 1, β] under the Galois automorphism of ℚ(α). The distances between adjacent elements of Σ_{α,β} take values L = 1 − α′ or S = −α′. Therefore the right neighbour of a given x′ ∈ Σ_{α,β} is either x′ + 1 − α′ or x′ − α′, according to whether x + 1 − α ∈ (β − 1, β] or x − α ∈ (β − 1, β]. We can thus define a function f : (β − 1, β] → (β − 1, β] by

f(x) = \{ \begin{matrix}x + 1 − α & if & x ∈ (β − 1 , β − 1 + α] & =: Ω_{L}, \\ x − α & if & x ∈ (β − 1 + α , β] & =: Ω_{S}. \end{matrix}

From the graph of the function f, illustrated of Figure 3, it is obvious that f is a 2-interval exchange transformation [19]. The Sturmian word (u_{n})_{n∈ℤ}, defined by equation (1) and represented by Σ_{α,β} is a coding of the orbit of 0 under the map f, i.e. u_{n} = 0 if f^{n}(0) ∈ Ω_{S}, and u_{n} = 1 if f^{n}(0) ∈ Ω_{L}.

Remark 4.1. In terms of the sequence (t_{n})_{n∈ℤ}, which represents the set Σ_{α,β}, we have f(t′_{n}) = t′_{n+1}. For the left end-point of the short distance t_{n+1} − t_{n} = −α′ we have t′_{n} ∈ Ω_{S}. Similarly, for the left end-point of the long distance t_{n+1} − t_{n} = 1 − α′ we have t′_{n} ∈ Ω_{L}.

Remark 4.2. Since α is irrational, we have f^{n}(x) ≠ x for every n ∈ ℤ \ {0} and every x ∈ (β−1, β]. The reason is that since f^{n}(x) = x+n_{1}(−α)+n_{2}(1−α) for some n_{1}, n_{2} ∈ ℤ such that n_{1} + n_{2} = n, we obtain from f^{n}(x) = x that n_{1}(−α) + n_{2}(1 − α) = 0, which implies n_{1} = n_{2} = n = 0.

[figure: f(x); x; β − 1; β − 1 + α; β; β; β − α]

Figure 3: The graph of the function f.

As a motivation for definition of another important function g_{λ}(x), note another property of the geometric representation of the word (u_{n})_{n∈ℤ}. The selfsimilarity λΣ_{α,β} ⊂ Σ_{α,β} = {t_{n} | n ∈ ℤ} implies that

∀ t_{n} ∈ Σ_{α,β} ∃ m ∈ ℤ such that λt_{m} ≤ t_{n} < λt_{m+1} ,

see also Figure 1. This however implies that there exists an index i ≥ 0 such that λt_{m} = t_{n−i}. For such t_{n−i} we have

λ′t′_{m} = t′_{n−i} = f^{−i}(t′_{n}) ∈ λ′(β − 1, β]  ⟹  t′_{m} = \frac{1}{λ′} f^{−i}(t′_{n}) .

Definition 4.3. Let α, β satisfy conditions (1) and let λ > 1 be a quadratic unit with conjugate λ′ ∈ (0, 1) such that λℤ[α′] = ℤ[α′]. For x ∈ (β − 1, β] let

ind(x) := min\{i ∈ ℕ_{0} | f^{−i}(x) ∈ λ′(β − 1, β]\}  and  g_{λ}(x) = \frac{1}{λ′} f^{−ind(x)}(x) .

From what was said before the definition, it is obvious that the function g_{λ}(x) is well defined for x ∈ {t′_{n} | n ∈ ℤ} = ℤ[α] ∩ (β − 1, β]. Since ℤ[α] is dense in ℝ and the function f is piece-wise linear, the function g_{λ}(x) has sense for all x ∈ (β − 1, β]. The following remark identifies two fixed points of g_{λ} in ℤ[α] ∩ (β − 1, β].

Remark 4.4.

(a) Since ind(0) = 0, we have g_{λ}(0) = 0.

(b) Since t_{0} = 0, we have λt_{−1} < t_{−1} < λt_{0} which implies g_{λ}(t′_{−1}) = t′_{−1}.

The function g_{λ} plays a crucial role in the characterization of substitution invariant Sturmian sequences. A very important necessary and sufficient condition is stated in the following theorem.

Theorem 4.5. Let the sequence (u_{n})_{n∈ℤ} and numbers α, β satisfy conditions (1). Then (u_{n})_{n∈ℤ} is invariant under a non-trivial substitution, if and only if there exists a quadratic unit λ > 1 with conjugate λ′ ∈ (0, 1) such that λℤ[α′] = ℤ[α′] and

g_{λ}({β, β − 1 + α}) ⊂ {β, β − 1 + α} .

The proof of the above theorem is a technical one, but its ideas are rather important and novel. Therefore we put it in a separate Section 5.

Remark 4.6. Consider (u_{n})_{n∈ℤ}, α, β satisfying (1). If a quadratic unit λ > 1 with conjugate λ′ ∈ (0, 1) verifies λℤ[α′] = ℤ[α′] and g_{λ}({β, β − 1 + α}) ⊂ {β, β − 1 + α}, then (u_{n})_{n∈ℤ} is invariant under a non-trivial substitution, say φ and λ is its substitution factor. Therefore the sequence (u_{n})_{n∈ℤ} is invariant also under the substitution φ^{k} for arbitrary k ∈ ℕ, which has the substitution factor λ^{k}. According to Theorem 4.5, the substitution factor must satisfy g_{λ^{k}}({β, β − 1 + α}) ⊂ {β, β − 1 + α}. As a consequence, while verifying the necessary and sufficient condition of Theorem 4.5, we may limit our considerations, without loss of generality, to suitable powers λ^{k}.

Theorem 4.5 easily implies several facts proved by other authors by different means. We state them as Corollary 4.7 (cf. [18]) and Corollary 4.8 (cf. [8, 12, 13, 3]).

The definition of g_{λ} and the condition g_{λ}({β, β − 1 + α}) ⊂ {β, β − 1 + α} implies the following result.

Corollary 4.7. Let (u_{n})_{n∈ℤ} be a Sturmian word with slope α ∈ (0, 1) and intercept β. If (u_{n})_{n∈ℤ} is invariant under a non-trivial substitution, then β ∈ ℚ(α).

If β = 0, then t_{0} = β = 0. The definition of f implies f(β − 1 + α) = f(−1 + α) = 0 = β = t_{0}, and thus t_{−1} = −1 + α′. Since according to Remark 4.4, t_{0} and t_{−1} are fixed points of g_{λ}, we obtain g_{λ}{0, −1 + α} ⊂ {0, −1 + α}, by which the necessary and sufficient condition of Theorem 4.5 is satisfied. For the following corollary it suffices to realize that conditions (1) for α say that α is a Sturm number.

Corollary 4.8. Let (u_{n})_{n∈ℤ} be a Sturmian word with slope α ∈ (0, 1) and intercept β = 0. Then (u_{n})_{n∈ℤ} is invariant under a substitution if and only if α is a Sturm number.

We shall further discuss the case β ≠ 0. Then β ∉ λ′(β − 1, β], and therefore ind(β) ≠ 0. Since f^{−1}(β) = β − 1 + α, we have g_{λ}(β − 1 + α) = g_{λ}(β). The condition g_{λ}({β, β −1+α}) ⊂ {β, β −1+α} is therefore equivalent to the fact that either β −1+α or β is a fixed point of the function g_{λ}.

Remark 4.9. For intercept β ≠ 0, Theorem 4.5 can be stated as follows: Let the sequence (u_{n})_{n∈ℤ} and numbers α, β satisfy conditions (1) and let β ≠ 0. Then (u_{n})_{n∈ℤ} is invariant under a non-trivial substitution, if and only if there exists a quadratic unit λ > 1 with conjugate λ′ ∈ (0, 1) such that λℤ[α′] = ℤ[α′] and

β or β − 1 + α is a fixed point of g_{λ} .

Determining the fixed points of g_{λ} in ℚ(α) ∩ (β − 1, β] will be the subject of Section 6.

5. Proof of Theorem 4.5

The proof of Theorem 4.5 will be divided into two parts. The necessity of the condition is given as Proposition 5.1 and the sufficiency of the condition as Proposition 5.3.

Proposition 5.1. Let (u_{n})_{n∈ℤ}, α, β satisfy conditions (1) and let (u_{n})_{n∈ℤ} be invariant under a non-trivial substitution. Then there exists a quadratic unit λ > 1 with conjugate λ′ ∈ (0, 1) such that λℤ[α′] = ℤ[α′] and

g_{λ}({β, β − 1 + α}) ⊂ {β, β − 1 + α} .  (3)

Proof. In Section 2 we have explained that substitution invariance implies the existence of a factor λ > 1 being a quadratic unit, with conjugate λ′ ∈ (0, 1), such that λΣ_{α,β} ⊂ Σ_{α,β} = {t_{n} | n ∈ ℤ}. In fact, λ is the dominant eigenvalue of the incidence matrix. Proposition 3.3 implies that λℤ[α′] = ℤ[α′]. Let us show that the factor λ satisfies (3).

Important for our considerations is the partition of the interval (β − 1, β], given by the discontinuity of the function f, into (β − 1, β] = Ω_{L} ∪ Ω_{S}. Recall that

Ω_{L} = (β − 1, β − 1 + α] , Ω_{S} = (β − 1 + α, β] .

Recall also that if t_{n+1} − t_{n} = −α′, then according to Remark 4.1, the conjugate t′_{n} of t_{n} satisfies t′_{n} ∈ Ω_{S}. Using the invariance under substitution, as explained in Remark 3.1, we also know that the sequences of distances between points λt_{n} and λt_{n+1} for all such n coincide. It follows using Remark 4.1 that there exists an integer k_{S} given as the length of the word φ(0) such that

for i ∈ {0, 1, …, k_{S} − 1}  either f^{i}(λ′Ω_{S}) ⊂ Ω_{S} or f^{i}(λ′Ω_{S}) ⊂ Ω_{L} ,
and  f^{k_{S}}(λ′Ω_{S}) ⊂ λ′(β − 1, β] . (4)

Similarly, for all n such that t_{n+1} − t_{n} = 1 − α′, i.e. for all n such that t′_{n} ∈ Ω_{L}, there exists an integer k_{L} given as the length of the word φ(1) such that

for j ∈ {0, 1, …, k_{L} − 1}  either f^{j}(λ′Ω_{L}) ⊂ Ω_{S} or f^{j}(λ′Ω_{L}) ⊂ Ω_{L} ,
and  f^{k_{L}}(λ′Ω_{L}) ⊂ λ′(β − 1, β] . (5)

In the statements (4) and (5) we have used a simple fact which follows from the piecewise linearity of the function f, namely that if I_{1}, I_{2} ⊂ (β − 1, β] are right-semi-closed intervals, then f(I_{1} ∩ ℤ[α]) ⊂ I_{2} ∩ ℤ[α] implies f(I_{1}) ⊂ I_{2}.

Now realize that every element of (Σ_{α,β})′ = (β − 1, β] ∩ ℤ[α] is covered by an iteration

f^{i}(λ′t′_{n}) for some n ∈ ℤ and some i ∈ \{ \begin{matrix}\{0, 1, …, k_{S} − 1\} & if t_{n+1} − t_{n} = −α′ , \\ \{0, 1, …, k_{L} − 1\} & if t_{n+1} − t_{n} = 1 − α′ . \end{matrix}

Therefore

⋃_{i=0}^{k_{S}−1} f^{i}(λ′Ω_{S}) ∪ ⋃_{j=0}^{k_{L}−1} f^{j}(λ′Ω_{L}) = (β − 1, β] ,  (6)

where the union of k_{S} + k_{L} intervals on the left hand side is disjoint.

As a consequence of (4) and (5) the discontinuity point β − 1 + α of the function f and the boundary point β of the interval (β − 1, β] must be covered in the union (6) by the boundary point of some interval f^{i}(λ′Ω_{S}) or f^{j}(λ′Ω_{L}). More precisely, we must have

either  β = f^{i}(λ′β)  for some i ∈ {0, 1, …, k_{S} − 1} ,
or  β = f^{j}(λ′(β − 1 + α))  for some j ∈ {0, 1, …, k_{L} − 1} , (7)

and

either  β − 1 + α = f^{i}(λ′β)  for some i ∈ {0, 1, …, k_{S} − 1} ,
or  β − 1 + α = f^{j}(λ′(β − 1 + α))  for some j ∈ {0, 1, …, k_{L} − 1} . (8)

Let us study (7). If β = f^{i}(λ′β) for i ∈ {0, 1, …, k_{S} − 1}, then

ind(β) = i and β = \frac{1}{λ′} f^{−ind(β)}(β) = g_{λ}(β) .

On the other hand, if β = f^{j}(λ′(β − 1 + α)) for j ∈ {0, 1, …, k_{L} − 1}, then

ind(β) = j and β + α − 1 = \frac{1}{λ′} f^{−ind(β)}(β) = g_{λ}(β) .

This implies g_{λ}(β) ∈ {β, β−1+α}. In the same way we derive from (8) that g_{λ}(β−1+α) ∈ {β, β − 1 + α}.

Let us now show that the condition in Theorem 4.5 is sufficient. Thus from now on, until the end of the present section we assume that for (u_{n})_{n∈ℤ}, α, β satisfying (1) there exists a quadratic unit λ with conjugate λ′ ∈ (0, 1) such that λℤ[α′] = ℤ[α′] and g_{λ}({β, β − 1 + α}) ⊂ {β, β − 1 + α}. First we introduce an indicator of how many iterations of the function f are necessary to get from a point x ∈ λ′(β − 1, β] back to this interval. Formally, for an x ∈ λ′(β − 1, β] we let

rt(x) := min{i ∈ ℕ | f^{i}(x) ∈ λ′(β − 1, β]}.  (9)

The mapping which assigns to x ∈ λ′(β − 1, β] the image f^{rt(x)}(x) ∈ λ′(β − 1, β] is in symbolic dynamics known as the first return map. The assignment x ↦ rt(x) is called return time. The fact that this mapping is well defined follows from Corollary 3.4.

As a consequence of Corollary 3.4 and Remark 4.1 the function rt(x) is piece-wise constant. The following observation about the relation between rt(x) and ind(x) will be useful.

Observation 5.2. For all x ∈ λ′(β − 1, β] and all j ∈ {0, 1, …, rt(x) − 1},

ind(f^{j}(x)) = j .

We are now in position to complete the proof of Theorem 4.5 by showing the sufficiency of the condition.

Proposition 5.3. Let (u_{n})_{n∈ℤ}, α, β satisfy conditions (1). Let λ > 1 be a quadratic unit with conjugate λ′ ∈ (0, 1) such that λℤ[α′] = ℤ[α′] and

g_{λ}({β, β − 1 + α}) ⊂ {β, β − 1 + α} .

Then (u_{n})_{n∈ℤ} is invariant under a non-trivial substitution.

Proof. We show that there exists a substitution with the factor λ, under which the Sturmian word (u_{n})_{n∈ℤ} is invariant. From Proposition 3.3 it is clear that the geometric representation Σ_{α,β} = {t_{n} | n ∈ ℤ} of the word (u_{n})_{n∈ℤ} is selfsimilar with the selfsimilarity factor λ. According to Remark 3.1, for existence of a substitution with the factor λ under which (u_{n})_{n∈ℤ} is invariant, it suffices to prove that for every n ∈ ℤ such that u_{n} = 0, the segments of the set Σ_{α,β} between points λt_{n} and λt_{n+1} are the same, and for every n ∈ ℤ such that u_{n} = 1, the segments between points λt_{n} and λt_{n+1} are the same.

Let n_{0} ∈ ℤ be such that u_{n_{0}} = 0, i.e. t_{n_{0}+1} − t_{n_{0}} = S = −α′. Let us denote by p and q the number of distances S and L respectively in the segment of Σ_{α,β} between points λt_{n_{0}} and λt_{n_{0}+1}. As a consequence of Corollary 3.4 and Remark 4.1 it holds that rt(λ′t′_{n_{0}}) = p+q and λ(t_{n_{0}+1} −t_{n_{0}}) = −λα′ = p(−α′)+q(1−α′). Since −α′ and 1−α′ are linearly independent over ℚ, the expression of the number −λα′ in the base {−α′, 1−α′} is unique. Since λ(t_{n+1} − t_{n}) = −λα′ for all n such that u_{n} = 0, we have shown that the number of distances S, L between points λt_{n} and λt_{n+1} are constantly equal to p, q respectively for all n such that u_{n} = 0. We need to show that the ordering of these distances S and L between points λt_{n} and λt_{n+1} is constant. This ordering determines the substitution word for the letter 0.

Since rt(λ′t′_{n}) is equal to the number of distances between points λt_{n} and λt_{n+1}, we have rt(x) = p + q for all x ∈ λ′Ω_{S}. Let us denote this constant by j_{S}, i.e.

j_{S} := rt(x) for some x ∈ λ′Ω_{S} .

In order to show that the ordering of the distances S and L between points λt_{n} and λt_{n+1} is constant, it suffices to prove that

for all j ∈ {0, 1, …, j_{S} − 1}  either f^{j}(λ′Ω_{S}) ⊂ Ω_{S} or f^{j}(λ′Ω_{S}) ⊂ Ω_{L} . (10)

For contradiction, take the minimal index j ≤ j_{S} − 1 such that f^{j}(λ′Ω_{S}) ⊄ Ω_{S} and f^{j}(λ′Ω_{S}) ⊄ Ω_{L}. Then f^{j}(λ′Ω_{S}) is an interval and its interior contains the discontinuity point β − 1 + α. This means that there exists an x ∈ λ′(β − 1 + α, β) = (λ′Ω_{S})^{∘} such that f^{j}(x) = β − 1 + α. Therefore f^{−j}(β − 1 + α) = x ∈ λ′(β − 1 + α, β). Since j < j_{S} = rt(x), we derive using Observation 5.2 that ind(f^{j}(x)) = ind(β − 1 + α) = j. Hence

\frac{1}{λ′} f^{−j}(β − 1 + α) = g_{λ}(β − 1 + α) ∈ (β − 1 + α, β).

But this is a contradiction with the assumption g_{λ}(β − 1 + α) ∈ {β, β − 1 + α}.

Similarly we can show that rt(x) is constant on λ′Ω_{L}. We denote

j_{L} := rt(x) for some x ∈ λ′Ω_{L}

and by similar arguments as for j_{S} we show that

for all j ∈ {0, 1, …, j_{L} − 1}  either f^{j}(λ′Ω_{L}) ⊂ Ω_{S} or f^{j}(λ′Ω_{L}) ⊂ Ω_{L} . (11)

It is now clear that the finite word which the substitution assigns to the letter 0, represented by the distance S, is the coding of the trajectory of λ′Ω_{S} under the iterations f^{j} for j ∈ {0, 1, …, j_{S} − 1}. Similarly we construct the substitution word for the letter 1.

6. Fixed points of g_{λ}

A necessary condition so that a Sturmian word (u_{n})_{n∈ℤ} with parameters α, β is substitution invariant, is that β ∈ ℚ(α), see Corollary 4.7. Such β can be written in the form \frac{1}{q}(a + bα) for some q ∈ ℕ, a, b ∈ ℤ, i.e. β ∈ \frac{1}{q}ℤ[α].

We have seen in Remark 4.9 that in order to determine all substitution invariant Sturmian words, we have to study when β or β − 1 + α is a fixed point of the function g_{λ}. For that we shall study the fixed points of g_{λ} in \frac{1}{q}ℤ[α] ∩ (β − 1, β] for an arbitrary fixed q ∈ ℕ. Recall that g_{λ} was defined for a quadratic unit λ > 1 whose conjugate λ′ ∈ (0, 1) satisfies λ′ℤ[α] = ℤ[α] (cf. Definition 4.3). Therefore g_{λ} has \frac{1}{q}ℤ[α] ∩ (β − 1, β] as an invariant subset. Let us divide the set \frac{1}{q}ℤ[α] into a disjoint union of subsets - classes of the following equivalence.

Definition 6.1. Let q ∈ ℕ. We define an equivalence relation on \frac{1}{q}ℤ[α] by

x ∼_{q} y  ⟺  x − y ∈ ℤ[α]  for x, y ∈ \frac{1}{q}ℤ[α].

It is obvious that the equivalence classes of ∼_{q} are of the form

T_{ij} := \frac{i + jα}{q} + ℤ[α] , i, j ∈ \{0, 1, …, q − 1\} ,

and thus their number is q^{2}.

Recall that f acts as translation by 1 − α or α. Therefore for every equivalence class T_{ij}, the set T_{ij} ∩ (β − 1, β] is invariant under f. However, since the definition of g_{λ} uses except the function f also multiplication by the factor λ′, the set T_{ij} ∩ (β − 1, β] is generally not invariant under g_{λ}. In order to determine for which λ the set T_{ij} ∩(β −1, β] is invariant under g_{λ}, it suffices to study the conditions, under which the class T_{ij} is closed under multiplication by λ′.

Proposition 6.2. Let α satisfy (1), let γ ∈ ℝ such that γℤ[α] = ℤ[α] and let q ∈ ℕ. Then there exists an integer k ∈ ℕ such that γ^{k}T_{ij} = T_{ij} for every equivalence class T_{ij} of ∼_{q}.

Proof. First we show that the mapping ψ(T_{ij}) := γT_{ij} is a well defined map on the set of equivalence classes. For arbitrary i, j ∈ \{0, 1, …, q − 1\} we have γ \frac{i+jα}{q} ⊂ \frac{1}{q}ℤ[α] and therefore there exist l, m ∈ \{0, 1, …, q − 1\} and a z ∈ ℤ[α] such that γ \frac{i+jα}{q} = \frac{l+mα}{q} + z. For ψ(T_{ij}) we have

ψ(T_{ij}) = γ (\frac{i + jα}{q} + ℤ[α]) = \frac{l + mα}{q} + z + ℤ[α] = T_{lm} .

Now let us show that the map ψ is injective. For that it suffices to show

γ \frac{i_{1} + j_{1}α}{q} − γ \frac{i_{2} + j_{2}α}{q} ∈ ℤ[α]  ⟺  (i_{1}, j_{1}) = (i_{2}, j_{2}) ,  (12)

for all i_{1}, j_{1}, i_{2}, j_{2} ∈ {0, 1, …, q − 1}. A simple manipulation of the left hand side of (12) leads us to

\frac{i_{1} − i_{2} + (j_{1} − j_{2})α}{q} ∈ \frac{1}{γ} ℤ[α] = ℤ[α] ,

which implies that q divides i_{1} −i_{2} and j_{1} −j_{2}. This is possible only if i_{1} = i_{2} and j_{1} = j_{2}. The mapping ψ is therefore injective and hence a permutation on the set of q^{2} classes T_{ij}, i, j ∈ {0, 1, …, q − 1}. Necessarily there exists an exponent k so that ψ^{k} is the identity, i.e. ψ^{k}(T_{ij}) = γ^{k}T_{ij} = T_{ij}, which completes the proof.

For β of the form β = \frac{a+bα}{q} the numbers β and β−1+α belong to the same equivalence class T. Thus according to Remark 4.6 and Proposition 6.2 we may consider without loss of generality the quadratic unit λ such that λ′T = T, and study the fixed points of the function g_{λ} on its invariant subset (β − 1, β] ∩ T. In fact, in the proof of the main result, we need only the class T which contains β and β − 1 + α (cf. proof of Corollary 7.2). However, we prove the following statements for arbitrary class T_{ij}.

Let us study the image of the set (β − 1, β] ∩ T_{ij} under the Galois automorphism. Then

((β − 1, β] ∩ T_{ij})′ = {y′ | y ∈ T_{ij} ∩ (β − 1, β]} =

= \{\frac{i + jα′}{q} + z′ | z ∈ ℤ[α] ∩ (β − 1 − \frac{i + jα}{q}, β − \frac{i + jα}{q}]\} =

= \frac{i + jα′}{q} + Σ_{α} ((β − 1 − \frac{i + jα}{q}, β − \frac{i + jα}{q}]) .

This means that ((β −1, β]∩T_{ij})′ is the geometric representation of the Sturmian word of slope α, intercept β− \frac{1}{q}(i+jα), translated by \frac{1}{q}(i+jα′). Therefore the set ((β−1, β]∩T_{ij})′ is a discrete set where the distances of adjacent elements take values −α′, 1 − α′. Then there exists a strictly increasing sequence (s_{n})_{n∈ℤ} such that

((β − 1, β] ∩ T_{ij})′ = {s_{n} | n ∈ ℤ}  and  f(s′_{n}) = s′_{n+1} for every n ∈ ℤ .

Thus the sequence (s′_{n})_{n∈ℤ} is an orbit under the function f of a point in the interval (β − 1, β]. If T_{ij} = T_{00} = ℤ[α], then {s′_{n} | n ∈ ℤ} = {t′_{n} | n ∈ ℤ} is the orbit of 0. The sequence (s_{n})_{n∈ℤ} for a class T_{ij} ≠ ℤ[α] is illustrated on Figure 4.

[figure: 0; ; ; ; g_{λ}; g_{λ}; g_{λ}; s_{−3}; s_{−2}; λs_{2}; s_{−1}; s_{0}; s_{1}; s_{2}; s_{3}; s_{4}; s_{5}; λs_{3}; s_{6}; s_{7}; s_{8}; λs_{4}; s_{9}; s_{10}; s_{11}; s_{12}; s_{13}; s_{14}; s_{15}; λs_{5}]

Figure 4: Action of the mappings ind(x) : (β − 1, β] → ℕ_{0} and g_{λ} : (β − 1, β] → (β − 1, β] on the Galois image of points of (β − 1, β] ∩ T_{ij}.

Bold points represent elements of the set λ{s_{n} | n ∈ ℤ} ⊂ {s_{n} | n ∈ ℤ}. They are important for determination of the value ind(s′_{m}) for m ∈ ℤ. In fact, ind(s′_{m}) is the number of steps to the first left neighbour of s_{m} which belongs to the set λ{s_{n} | n ∈ ℤ}. For example,

ind(s′_{3}) = 5 , ind(s′_{7}) = 2 , ind(s′_{8}) = 0 .

If we divide the first left neighbour of s_{m} in λ{s_{n} | n ∈ ℤ} by the factor λ, we obtain the Galois conjugate of the value g_{λ}(s′_{m}). Clearly, several points may have the same image under the mapping g_{λ}. Such points are marked on Figure 4 by braces. For example, we have

g_{λ}(s′_{−2}) = g_{λ}(s′_{−1}) = g_{λ}(s′_{0}) = g_{λ}(s′_{1}) = g_{λ}(s′_{2}) = g_{λ}(s′_{3}) = g_{λ}(s′_{4}) = s′_{2} ,
g_{λ}(s′_{5}) = g_{λ}(s′_{6}) = g_{λ}(s′_{7}) = s′_{3} ,
g_{λ}(s′_{8}) = g_{λ}(s′_{9}) = g_{λ}(s′_{10}) = g_{λ}(s′_{11}) = g_{λ}(s′_{12}) = g_{λ}(s′_{13}) = g_{λ}(s′_{14}) = s′_{4} .

With this in mind it is simple to describe all fixed points of the function g_{λ}.

Proposition 6.3. Let α, β satisfy (1), β ∈ \frac{1}{q}ℤ[α], and let λ > 1 be a quadratic unit with conjugate λ′ ∈ (0, 1) such that all equivalences classes of ∼_{q} are closed under multiplication by λ′. Let (s_{n})_{n∈ℤ} be the strictly increasing sequence such that ((β − 1, β] ∩ T )′ = {s_{n} | n ∈ ℤ} for an equivalence class T. Then s′_{n} is a fixed point of g_{λ} if and only if s_{n} ≤ 0 and s_{n+1} ≥ 0.

Proof. Note that

g_{λ}(s′_{n}) = \frac{1}{λ′} f^{−ind(s′_{n})}(s′_{n}) = s′_{n}  ⟺  f^{−ind(s′_{n})}(s′_{n}) = λ′s′_{n} .

This means that s′_{n} being a fixed point of g_{λ} is equivalent to the fact that among the left neighbours of s_{n}, the point λs_{n} is the nearest one which has its Galois image in λ′(β − 1, β] ∩ T. This is characterized by the two inequalities

λs_{n} ≤ s_{n}  (13)
s_{n} < λs_{n+1}.  (14)

Since λ > 1, the inequality (13) is equivalent with s_{n} ≤ 0. Since s_{n+1} is the nearest right neighbour of s_{n}, inequality (14) can be equivalently written as s_{n+1} ≤ λs_{n+1}, which implies s_{n+1} ≥ 0.

Remark 6.4. Note that in Proposition 6.3, the necessary and sufficient condition for s_{n} to be a fixed point of the mapping g_{λ} does not depend on λ. Therefore s_{n} is either a fixed point of g_{λ} for all λ satisfying the assumptions of the proposition, or is not a fixed point of g_{λ} for any λ.

7. Substitution invariant Sturmian words

In this section we show that the necessary and sufficient condition of Theorem 4.5 is equivalent to the inequalities given in Theorem 1.1. At the end we explain how to construct a non-trivial substitution φ under which a given Sturmian word satisfying the conditions of Theorem 1.1 is invariant.

A part of the construction requires to find for a given quadratic α a quadratic unit λ such that λℤ[α′] = ℤ[α′]. Obviously, if ℤ[α] is the ring of integers in ℚ(α), then such λ trivially exists. However, in general α is even not an algebraic integer and thus ℤ[α] is not closed under multiplication. For completeness we prove the existence of the factor λ in the following simple lemma.

Lemma 7.1. For every quadratic irrational α there exists a quadratic unit λ > 1 such that λ′ ∈ (0, 1) and λℤ[α′] = ℤ[α′].

Proof. Let α satisfy the equation Aα^{2}+Bα+C = 0, where A, B, C ∈ ℤ, D = B^{2}−4AC > 0 and \sqrt{D} is irrational. For α and its conjugate α′ we have α + α′ = −\frac{B}{A}, αα′ = \frac{C}{A}. First we find an algebraic unit γ such that γℤ[α] = ℤ[α].

Let x, y ∈ ℤ be a non-trivial solution of the Pell equation x^{2} − Dy^{2} = 1. Set γ := x + By + 2Ayα. We have

\begin{aligned}γ + γ′ & = & 2x + 2By + 2Ay(α + α′) = 2x ∈ ℤ , \\ γγ′ & = & (x + By)^{2} + 2Ay(x + By)(α + α′) + 4A^{2}y^{2}αα′ = x^{2} − Dy^{2} = 1 , \end{aligned}

therefore γ is an algebraic unit. Since γ ∈ ℤ[α], for verifying the relation γℤ[α] = ℤ[α] it suffices that γα ∈ ℤ[α] and \frac{1}{γ}α ∈ ℤ[α]. We have

\begin{aligned}γα & = & (x + By)α + 2Ayα^{2} = (x + By)α + 2Ay (−\frac{B}{A}α − \frac{C}{A}) ∈ ℤ[α] , \\ \frac{1}{γ}α & = & γ′α = (x + By + 2Ayα′)α = (x + By)α + 2Ay \frac{C}{A} ∈ ℤ[α] . \end{aligned}

The relation γℤ[α] = ℤ[α], which we have just proven, is equivalent to γ′ℤ[α′] = ℤ[α′]. Since γ is a unit, we have also γℤ[α′] = ℤ[α′]. Now at least one of the numbers γ, γ′, −γ, −γ′ is greater than 1. We choose it for the desired quadratic unit λ. Clearly, since γ was found so that γγ′ = 1, we have λ′ ∈ (0, 1).

Corollary 7.2. Let (u_{n})_{n∈ℤ}, α, β satisfy conditions (1), and let 0 ≠ β ∈ ℚ(α). Then (u_{n})_{n∈ℤ} is invariant under a non-trivial substitution if and only if

α′ ≤ β′ ≤ 1 − α′ .  (15)

Proof. Let β ∈ \frac{1}{q}ℤ[α]. Due to Lemma 7.1 and Proposition 6.2 there exists a quadratic unit λ with conjugate λ′ ∈ (0, 1) such that λ′T_{ij} = T_{ij} for every equivalence class of ∼_{q}. (Note that the class of \frac{1}{q}ℤ[α] which contains 0 is ℤ[α], therefore the latter condition implies λ′ℤ[α] = ℤ[α].)

According to Theorem 4.5 and to Remarks 4.9 and 6.4, for invariance under substitution we have to show that inequality (15) is equivalent to the fact that β or β − 1 + α is a fixed point of the function g_{λ}.

Let us denote by T the equivalence class containing β and β − 1 + α, and by (s_{n})_{n∈ℤ} the strictly increasing sequence such that (T ∩ (β − 1, β])′ = {s_{n} | n ∈ ℤ}. Since f(β −1+α) = β, there exists an index n_{0} ∈ ℤ such that β′ −1+α′ = s_{n_{0}} and β′ = s_{n_{0}+1}. According to Proposition 6.3 at least one of the points s′_{n_{0}} or s′_{n_{0}+1} is a fixed point of g_{λ} if and only if

s_{n_{0}} ≤ 0  and  0 ≤ s_{n_{0}+2} .  (16)

We can substitute s′_{n_{0}} = β − 1 + α and s′_{n_{0}+2} = f(s′_{n_{0}+1}) = f(β) = β − α into (16) to obtain that β or β − 1 + α is a fixed point of g_{λ} if and only if β′ − 1 + α′ ≤ 0 and β′ − α′ ≥ 0, which completes the proof.

Proof of Theorem 1.1. Necessity of condition (i) (α being a Sturm number) has been derived in Proposition 2.1. Corollary 4.7 says that (ii) (β ∈ ℚ(α)) is also a necessary condition. Therefore it suffices to show that for Sturmian words with irrational slope α ∈ (0, 1) and intercept β ∈ [0, 1) satisfying (i) and (ii), invariance under a non-trivial substitution is equivalent to the condition (iii).

Recall that Sturmian words \underline{s}_{α,β}, \underline{s}_{1−α,β} and \overline{s}_{α,1−β} are either all substitution invariant, or none of them. Also condition (iii) is satisfied either for all pairs of parameters (α, β), (α, 1 − β) and (1 − α, β), or for none of them. Therefore it suffices to consider the Sturmian word (u_{n})_{n∈ℤ} = (\underline{s}_{α,β}(n))_{n∈ℤ} with α′ < 0. For such a slope α the condition (iii) has the form

α′ ≤ β′ ≤ 1 − α′ .

For β = 0 the latter is satisfied automatically. As a consequence of Corollary 7.2, for β ≠ 0, the above inequality is equivalent with (u_{n})_{n∈ℤ} being substitution invariant.

8. Construction of the substitution

The proof given in this paper is constructive. For a given Sturmian word (u_{n})_{n∈ℤ} with slope α and intercept β = \frac{1}{q}(a + bα) that satisfies conditions (i)–(iii) of Theorem 1.1 one can determine a non-trivial substitution φ under which (u_{n})_{n∈ℤ} is invariant.

If a Sturmian word is invariant under a non-trivial substitution, then it is invariant under many substitutions with different factors. All substitution factors λ are quadratic units with conjugate λ′ ∈ (−1, 1) and satisfy λ′ℤ[α] = ℤ[α]. It is convenient to choose the substitution with the smallest substitution factor λ_{0}, because then the substitution words φ(0), φ(1) are short. From the proof presented in the paper it follows that the smallest quadratic unit λ > 1 with conjugate λ′ ∈ (0, 1), satisfying λ′ℤ[α] = ℤ[α] and λ′T = T for T = β + ℤ[α′], is either λ = λ_{0} or λ = λ_{0}^{2}.

Let us describe explicitly the algorithm for determining a substitution to a given Sturmian word. This algorithm is a consequence of the proof of Proposition 5.3. First we find, according to the construction in proof of Lemma 7.1, a quadratic unit λ > 1 with conjugate λ′ ∈ (0, 1) which satisfies λ′ℤ[α] = ℤ[α]. Every power of λ satisfies these conditions, therefore we can assume that the chosen factor λ is such that λ′T = T for the equivalence class T of ∼_{q}, that contains β. If λ satisfies all of the above conditions, then we define the substitution φ : {0, 1} → {0, 1}^{∗} in the following way. Put φ(0) = v_{0} ⋯ v_{j_{S}−1}, where j_{S} = rt(λ′β) is the smallest positive index such that f^{j_{S}}(λ′β) ∈ λ′(β − 1, β], and let φ(1) = w_{0} ⋯ w_{j_{L}−1} where j_{L} = rt(λ′(β − 1 + α)) is the smallest positive index such that f^{j_{L}}(λ′(β − 1 + α)) ∈ λ′(β − 1, β]. Then we let

v_{i} := \{ \begin{matrix}0 & if f^{i}(λ′β) ∈ Ω_{S} , \\ 1 & if f^{i}(λ′β) ∈ Ω_{L} , \end{matrix}  for i ∈ \{0, 1, …, j_{S} − 1\} ,

w_{i} := \{ \begin{matrix}0 & if f^{i}(λ′(β − 1 + α)) ∈ Ω_{S} , \\ 1 & if f^{i}(λ′(β − 1 + α)) ∈ Ω_{L} , \end{matrix} for i ∈ \{0, 1, …, j_{L} − 1\} .

Let us illustrate the construction of a substitution to a given Sturmian word on an example.

Example 1. Let α = \frac{1}{\sqrt{2}}. Such α is a quadratic number, solution of 2x^{2} − 1 = 0. Its algebraic conjugate is α′ = −\frac{1}{\sqrt{2}}. Since α ∈ (0, 1) and α′ < 0, α is a Sturm number.

Let us first find a quadratic unit λ > 0 with conjugate λ′ ∈ (0, 1) such that λ′ℤ[α] = ℤ[α]. For that we use the constructive proof of Lemma 7.1. Since the coefficients of the equation Ax^{2} + Bx + C = 2x^{2} − 1 = 0 of α are A = 2, B = 0, C = −1, we have the discriminant D = B^{2} − 4AC = 8. For a solution of the Pell equation x^{2} − Dy^{2} = x^{2} − 8y^{2} = 1 we can choose x = 3, y = 1. Then γ = x + By + 2Ayα = 3 + 4α. Since γ > 1, we let λ = γ = 3 + 4α.

In order that the Sturmian word (u_{n})_{n∈ℤ} given by

u_{n} = ⌊(n + 1)α + β⌋ − ⌊nα + β⌋

be invariant under a substitution, we need to choose the intercept β ∈ ℚ(\sqrt{2}) so that

−\frac{1}{\sqrt{2}} = α′ ≤ β′ ≤ 1 − α′ = 1 + \frac{1}{\sqrt{2}} .

For simplicity, we consider the example of β = \frac{1}{q}, for some q ∈ ℕ, which clearly satisfies the condition.

Now we have to take a power λ^{s} of λ, such that the multiplication by λ′^{s} preserves the equivalence classes T_{ij} of ∼_{q} in \frac{1}{q}ℤ[α]. It is not difficult to calculate that the multiplication of T_{ij} by λ′ gives λ′T_{ij} = T_{kl}, where

k = 3i − 2j mod q  and  l = −4i + 3j mod q .

Clearly for q = 2 we have λ′T_{ij} = T_{ij}, whereas for q = 3 we have to take the fourth power, i.e. λ′^{4}T_{ij} = T_{ij}.

In order to illustrate the construction of a substitution, we let β = \frac{1}{2}. We will use the function f in our case defined as

f(x) = \{ \begin{matrix}x + 1 − α & if & x ∈ (−\frac{1}{2} , −\frac{1}{2} + \frac{1}{\sqrt{2}}] & =: Ω_{L}, \\ x − α & if & x ∈ (−\frac{1}{2} + \frac{1}{\sqrt{2}} , \frac{1}{2}] & =: Ω_{S}. \end{matrix}

We have to calculate iterations f^{i}(λ′β) = f^{i}(λ′ \frac{1}{2}), f^{i}(λ′(β − 1 + α)) = f^{i}(λ′(−\frac{1}{2} + \frac{1}{\sqrt{2}})) until the first return to the interval λ′(β − 1, β],

\begin{aligned}f^{0}(λ′ \frac{1}{2}) & = & \frac{3}{2} − 2α & ∈ & Ω_{L} , \\ f^{1}(λ′ \frac{1}{2}) & = & \frac{5}{2} − 3α & ∈ & Ω_{S} , \\ f^{2}(λ′ \frac{1}{2}) & = & \frac{5}{2} − 4α & ∈ & Ω_{L} , \\ f^{3}(λ′ \frac{1}{2}) & = & \frac{7}{2} − 5α & ∈ & λ′Ω , \end{aligned} thus j_{S} = 3 and φ(0) = 101 .

Similarly, we have

f^{0}(λ′(−\frac{1}{2} + \frac{1}{\sqrt{2}})) = −\frac{7}{2} + 5α ∈ Ω_{L} , f^{1}(λ′(−\frac{1}{2} + \frac{1}{\sqrt{2}})) = −\frac{5}{2} + 4α ∈ Ω_{S} , f^{2}(λ′(−\frac{1}{2} + \frac{1}{\sqrt{2}})) = −\frac{5}{2} + 3α ∈ Ω_{L} , f^{3}(λ′(−\frac{1}{2} + \frac{1}{\sqrt{2}})) = −\frac{3}{2} + 2α ∈ Ω_{L} , f^{4}(λ′(−\frac{1}{2} + \frac{1}{\sqrt{2}})) = −\frac{1}{2} + α ∈ Ω_{L} , f^{5}(λ′(−\frac{1}{2} + \frac{1}{\sqrt{2}})) = \frac{1}{2}  ∈ Ω_{S} , f^{6}(λ′(−\frac{1}{2} + \frac{1}{\sqrt{2}})) = \frac{1}{2} − α ∈ Ω_{L} , f^{7}(λ′(−\frac{1}{2} + \frac{1}{\sqrt{2}})) = \frac{3}{2} − 2α ∈ λ′Ω ,  thus j_{L} = 7 and φ(1) = 1011101 .

The infinite word (u_{n})_{n∈ℤ} is a fixed point of the substitution

φ(0) = 101 , φ(1) = 1011101 .

Therefore (u_{n})_{n∈ℤ} can be generated from the initial pair of letters 1|1 by repeated application of φ, i.e.

⋯ u_{−2}u_{−1}|u_{0}u_{1}u_{2} ⋯ = lim_{n→∞} φ^{n}(1)|φ^{n}(1) .

The Sturmian word (u_{n})_{n∈ℤ} is geometrically represented by the set

Σ_{α,β} = \{x ∈ ℤ[α′] | x′ ∈ (−\frac{1}{2}, \frac{1}{2}] \} .

Since the boundary point \frac{1}{2} of the interval is not an element of ℤ[α], the set Σ_{α,β} is symmetric with respect to the origin. This corresponds to the fact that the substitution words φ(0) and φ(1) are palindromes.

Acknowledgements

We acknowledge financial support of Czech Science Foundation GA ČR 201/05/0169.

References

[1] B. Adamczewski, Codages de rotations et phénomènes d’autosimilarité, J. Théor. Nombres Bordeaux 14 (2002), 351–386.

[2] C. Allauzen, Simple characterization of Sturm numbers, J. Théor. Nombres Bordeaux 10 (1998), 237–241.

[3] J. Berstel, P. Séébold, Morphismes de Sturm, Bull. Belg. Math. Soc. 1 (1994), 175–189.

[4] J. Berstel, Recent results on extensions of Sturmian words, Internat. J. Algebra Comput. 12 (2002), 371–385.

[5] V. Berthé, H. Ei, S. Ito, H. Rao, Invertible substitutions and Sturmian words: An application of Rauzy fractals, preprint (2003)

[6] V. Berthé, C. Holton, L. Q. Zamboni, Initial powers of Sturmian sequences, preprint (2003)

[7] T. C. Brown, A characterization of the quadratic irrationals, Canad. Math. Bull. 34 (1991), 36–41.

[8] D. Crisp, W. Moran, A. Pollington, P. Shiue, Substitution invariant cutting sequences, J. Théor. Nombres Bordeaux 5 (1993), 123-137.

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

[10] X. Droubay, G. Pirillo, Palindromes and Sturmian words, Theoret. Comput. Sci. 223 (1999), 73–85.

[11] L.S. Guimond, Z. Masáková, E. Pelantová, Combinatorial properties of infinite words associated with cut-and-project sequences, J. Théor. Nombres Bordeaux 15 (2003), pp. 697-725.

[12] S. Ito, S. Yasutomi, On continued fractions, substitutions and characteristic sequences [nx + y] − [(n − 1)x + y], Japan. J. Math. New Ser. 16 (1990), 287–306.

[13] T. Komatsu, A. J. van der Poorten, Substitution invariant Beatty sequences, Japan. J. Math. New Ser. 22 (1996), 349–354

[14] M. Lothaire, Algebraic combinatorics on words, Cambridge University Press (2002).

[15] Y. Meyer, Quasicrystals, Diophantine approximation and algebraic numbers, Beyond quasicrystals (Les Houches, 1994), 3–16, Springer, Berlin, 1995.

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

[17] B. Parvaix, Propriétés d’invariance des mots sturmiens, J. Théor. Nombres Bordeaux 9 (1997), 351–369.

[18] B. Parvaix, Substitution invariant Sturmian bisequences, J. Théor. Nombres Bordeaux 11 (1999), 201–210.

[19] G. Rauzy, Échanges d’intervalles et transformations induites, Acta Arith. 34 (1979), 315–328.

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

[21] S. Yasutomi, On Sturmian sequences which are invariant under some substitutions, Number theory and its applications (Kyoto, 1997), 347–373, Dev. Math. 2, Kluwer Acad. Publ., Dordrecht, 1999.