The Constant of Recognizability is Computable for Primitive Morphisms

Fabien Durand

Laboratoire Amiénois de Mathématiques Fondamentales et Appliquées

CNRS-UMR 7352 Université de Picardie Jules Verne

33 rue Saint Leu 80000 Amiens

France

fabien.durand@u-picardie.fr

Julien Leroy^{1} Institut de mathématique

Université de Liège Allée de la découverte 12 (B37)

4000 Liège Belgium

J.Leroy@ulg.ac.be

Abstract

Mossé proved that primitive morphisms are recognizable. In this paper we give a computable upper bound for the constant of recognizability of such a morphism. This bound can be expressed using only the cardinality of the alphabet and the length of the longest image of a letter under the morphism.

1J. Leroy is an FNRS post-doctoral fellow.

1 Introduction

Infinite words, i.e., infinite sequences of symbols from a finite set, usually called the alphabet, form a classical object of study. They have an important power of representation: they provide a natural way to code elements of an infinite set using finitely many symbols, e.g., the coding of an orbit in a discrete dynamical system or the characteristic sequence of a set of integers. A rich family of infinite words, with a simple algorithmic description, consists of the words obtained by iterating a morphism σ : A^{∗} → A^{∗} [3], where A^{∗} is the free monoid generated by the finite alphabet A.

If σ is prolongable on some letter a ∈ A, that is, if σ(a) = au for some non-empty word u and lim_{n→+∞} |σ^{n}(a)| = +∞, then σ^{n}(a) converges to an infinite word x = σ^{ω}(a) ∈ A^{ℕ} that is a fixed point of σ. Two-sided fixed points are similarly defined as infinite words of the form σ^{ω}(a · b) ∈ A^{ℤ}, where σ(a) = ua and σ(b) = bv with u, v ∈ A^{+} and lim_{n→+∞} |σ^{n}(a)| = lim_{n→+∞} |σ^{n}(b)| = +∞. Such a fixed point is said to be admissible if ab occurs in σ^{n}(c) for some n ∈ ℕ and some c ∈ A. When the morphism is primitive, i.e., there exists k ∈ ℕ such that b occurs in σ^{k}(c) for all b, c ∈ A, then x is uniformly recurrent: each finite word u that occurs in x occurs infinitely many times in x and the gaps between two consecutive occurrences of u in x are bounded [16]. The converse almost holds: if x = σ^{ω}(a) is uniformly recurrent, then there exist a primitive morphism φ : B^{∗} → B^{∗}, a letter b ∈ B and a morphism ψ : B^{∗} → A^{∗} such that x = ψ(φ^{ω}(b)) [4]. We let L(x) denote the set of factors of x, i.e., L(x) = {u ∈ A^{∗} | ∃p ∈ A^{∗}, w ∈ A^{ℕ} : x = puw} (with an analogous definition for twosided fixed points). We also let p_{x} : ℕ → ℕ denote the complexity function of x defined by p_{x}(n) = Card L_{n}(x) where L_{n}(x) = L(x) ∩ A^{n}. A primitive morphism σ is aperiodic if its fixed points are not periodic, i.e., are not of the form u^{ω} = uuu · · ·.

Recognizability is a central notion when dealing with fixed points of morphisms. It roughly means that any sufficiently long finite word that occurs in σ^{ω}(a) has a unique pre-image under σ, except for a prefix and a suffix of bounded length. Recognizability of a morphism is linked to the existence of long powers u^{k} in L(x) [13]. An infinite word x ∈ A^{ℤ} is said to be k-power-free if there is no non-empty word u such that u^{k} belongs to L(x). We refer, for example, to [1, 5, 7, 8]. A fundamental result concerning recognizability is due to Mossé, who proved that aperiodic primitive morphisms are recognizable [14, 15]. In this paper, we present a detailed proof of this result. This allows us to give a bound on the constant of recognizability.

2 Recognizability

Recognizability of a morphism deals with uniqueness of pre-images of words. More precisely, given a morphism σ, an admissible fixed point x of σ and a sufficiently long word w ∈ L(x), we would like to find some word u ∈ L(x) such that w appears in σ(u) and such that any other word u′ ∈ L(x) satisfying the same property has a large part in common with u. This large common part is the pre-image that the notion of recognizability is concerned with.

To find such a pre-image, it suffices to consider the pre-images of the letters. As a letter a can appear in several images σ(b) and at different positions in σ(b), we need to consider it in some context of length ℓ, i.e., to consider a word uav ∈ L(x) with |u| = |v| = ℓ. We would like that the length of the context ensures the uniqueness of b and of the position i ∈ {0, 1, …, |σ(b)| − 1} such that (σ(b))_{i} = a. This length ℓ will be defined as the constant of recognizability in Definition 1.

Let us consider an example with the morphism τ defined by τ(0) = τ(1) = 021 and τ(2) = 0. The letter 0 appears at the first position in the image of 0, 1 and 2. The contexts of length 4 of 0 are the words of length 9 that occur in x = τ^{ω}(1 · 0) and that have 0 for central letter, i.e.,

c_{1} = 0021 0 2100;
c_{2} = 0021 0 2102;
c_{3} = 0210 0 2102;
c_{4} = 1021 0 0210;
c_{5} = 1021 0 2100.

In the contexts c_{1}, c_{2} and c_{5}, the central occurrence of 0 is the first letter in the image τ(0). Indeed, the first occurrence of 0 in the word 00 can only be the image of 2 and the words 12, 22 and 20 do not occur in x. Therefore we necessarily have the following factorization for c_{1}:

c_{1} = \underbrace{0}_{τ(2)} \underbrace{021}_{τ(1)} \underbrace{021}_{τ(0)} \underbrace{0}_{τ(2)} 0.

Similar arguments show that in c_{3} (resp., in c_{4}) the central occurrence of 0 is the first letter in the image τ(1) (resp., τ(2)). We have

c_{3} = \underbrace{021}_{τ(0)} \underbrace{0}_{τ(2)} \underbrace{021}_{τ(1)} 02 and c_{4} = 1 \underbrace{021}_{τ(0)} \underbrace{0}_{τ(2)} \underbrace{021}_{τ(1)} 0.

Let us now formalize the precise definition of recognizability. Let x = (x_{n})_{n∈ℤ} ∈ A^{ℤ} be an infinite word. Given two integers i, j with i ≤ j, we let x_{[i,j]} (resp., x_{[i,j)}) denote the factor x_{i}x_{i+1} ⋯ x_{j} (resp., x_{i}x_{i+1} ⋯ x_{j−1}) x_{[i,i)} = ε, where ε is the empty word, i.e., the identity element of A^{∗}.

Assume that the morphism σ : A^{∗} → A^{∗} is non-erasing and has an admissible fixed point x = (x_{n})_{n∈ℤ} ∈ A^{ℤ}. For all p ∈ ℕ, we let f_{x}^{(p)} denote the function

f_{x}^{(p)} : ℤ → ℤ, i ↦ f_{x}^{(p)}(i) = \begin{cases}|σ^{p}(x_{[0,i)})|, & if i > 0; \\ 0, & if i = 0; \\ |σ^{p}(x_{[i,0)})|, & if i < 0. \end{cases}

We set E(x, σ^{p}) = f_{x}^{(p)}(ℤ). When it is clear from the context, we write f^{(p)} instead of f_{x}^{(p)}. Observe that σ being non-erasing, all functions f_{x}^{(p)} are increasing.

Definition 1. We say that σ is recognizable on x if there exists some constant L > 0 such that for all i, m ∈ ℤ,

(x_{[m−L,m+L]} = x_{[f^{(1)}(i)−L,f^{(1)}(i)+L]}) ⇒ (∃j ∈ ℤ)((m = f^{(1)}(j)) ∧ (x_{i} = x_{j})).  (1)

We say that the factor x_{[f^{(1)}(i)−L,f^{(1)}(i)+L]} uniquely determines the letter x_{i}. By extension, we say that the factor x_{[f^{(1)}(i)−L,f^{(1)}(j)+L]} uniquely determines the factor x_{[i,j]}.

The smallest L satisfying Equation (1) is called the constant of recognizability of σ for x. When σ is recognizable on all its admissible fixed points, we say that it is recognizable and its constant of recognizability is the greatest one.

In the example above, the arguments given for the contexts of the letter 0 can be similarly applied for the contexts of length 4 of the letters 1 and 2. Thus those contexts also have unique factorizations as images of τ. Therefore the constant of recognizability of τ on the admissible fixed point τ^{ω}(1 · 0) is at most 4. A careful inspection of the contexts of length 4 actually shows that the constant is at most 3 (no context of length 3 appears as a subword of two contexts of length 4 having different factorization). We can finally show that it cannot be equal to 2. Indeed, the word 21 0 21 is a context of length 2 of 0 but appears as a subword of c_{1} and c_{3} that have different decompositions as images of τ. The constant of recognizability of τ is thus equal to 3.

The following result shows that any primitive aperiodic morphism is recognizable.

Theorem 2. Let σ : A^{∗} → A^{∗} be an aperiodic primitive morphism and let x ∈ A^{ℤ} be an admissible fixed point of σ.

1. [14] There exists M > 0 such that, for all i, m ∈ ℤ,

x_{[f^{(1)}(i)−M,f^{(1)}(i)+M]} = x_{[m−M,m+M]} ⇒ m ∈ E(x, σ).

2. [15] There exists L > 0 such that, for all i, j ∈ ℤ,

x_{[f^{(1)}(i)−L,f^{(1)}(i)+L]} = x_{[f^{(1)}(j)−L,f^{(1)}(j)+L]} ⇒ x_{i} = x_{j}.

By a careful reading of the proofs of Mossé’s results, we can improve the statements as follows. The proof of Theorem 3 is given in Section 3. Given a morphism σ : A^{∗} → A^{∗}, we define |σ| and ⟨σ⟩ by, respectively,

|σ| = max_{a∈A} |σ(a)| and ⟨σ⟩ = min_{a∈A} |σ(a)|.

Theorem 3. Let σ : A^{∗} → A^{∗} be a morphism with an admissible fixed point x ∈ A^{ℤ}. If x is k-power-free and if there is some constant N such that for all n ∈ ℕ, |σ^{n}| ≤ N⟨σ^{n}⟩, then σ is recognizable on x and its constant of recognizability for x is at most R|σ^{dQ}| + |σ^{d}|, where

• R = ⌈N^{2}(k + 1) + 2N⌉; • Q = 1 + p_{x}(R) (∑_{\frac{R}{N} ≤i≤RN+2} p_{x}(i));

• d ∈ {1, 2, …, Card A} is such that for all words u, v ∈ L(x), we have

σ^{d−1}(u) ≠ σ^{d−1}(v) ⇒ ∀n, σ^{n}(u) ≠ σ^{n}(v).

Then, we give some computable bounds for N, R, k, Q and d in the case of primitive morphisms. These bounds are not sharp but can be expressed using only the cardinality of the alphabet and the maximal length |σ|. The proof is given in Section 4.

Theorem 4. Each aperiodic primitive morphism σ : A^{∗} → A^{∗} that has an admissible fixed point x ∈ A^{ℤ} is recognizable on x and the constant of recognizability for x is at most

2|σ|^{6(Card A)^{2}+6(Card A)|σ|^{28(Card A)^{2}}} + |σ|^{(Card A)}.

The bound given in the previous theorem is far from being sharp. When the morphism σ is injective on A, we can take d = 1 in Theorem 3 and the computation in the proof of Theorem 4 gives the bound

2|σ|^{6(Card A)^{2}+6|σ|^{28(Card A)^{2}}} + |σ|.

The notion of recognizability is also known as circularity in the terminology of D0Lsystems [10]. Assume that σ : A^{∗} → A^{∗} is non-erasing (i.e., σ(a) ≠ ε for all a ∈ A) and that a ∈ A is a letter such that the language Fac(σ, a) defined as the set of factors occurring in σ^{n}(a) for some n is infinite. Given a word u = u_{1} ⋯ u_{|u|} ∈ Fac(σ, a), we say that a triple (p, v, q) is an interpretation of u if v ∈ Fac(σ, a) and σ(v) = puq. Two interpretations (p, v, q), (p′, v′, q′) are said to be synchronized at position k if there exist i, j such that 1 ≤ i ≤ |v|, 1 ≤ j ≤ |v′| and

σ(v_{1} ⋯ v_{i}) = pu_{1} ⋯ u_{k} and σ(v′_{1} ⋯ v′_{j}) = p′u_{1} ⋯ u_{k}.

The word u has a synchronizing point (at position k) if all its interpretations are synchronized (at position k). The pair (σ, a) is said to be circular if σ is injective on Fac(σ, a) and if there is a constant C such that all words of length at least C have a synchronizing point. The smallest such C is called the synchronizing delay of σ. Thus, despite some considerations about whether we deal with fixed points or languages, recognizability and circularity are roughly the same notion and the synchronizing delay C is associated with the constant of recognizability L through L ≤ C ≤ 2L + |σ| + 1. Using the terminology of D0L-systems, Klouda and Medková obtained the following result which greatly improves our bounds, but for restricted cases.

Theorem 5 ([11]). If Card A = 2 and if (σ, a) is circular with σ : A^{∗} → A^{∗} a k-uniform morphism for some k ≥ 2, then the synchronizing delay C of (σ, a) is bounded as follows, where d is the least divisor of k greater than 1:

1. C ≤ 8, if k = 2;

2. C ≤ k^{2} + 3k − 4, if k is an odd prime number;

3. C ≤ k^{2} (\frac{k}{d} − 1) + 5k − 4, otherwise.

3 Proof of Theorem 3

As is the case in Mossé’s original proof, the proof of Theorem 3 goes in two steps.

As a first step, we express the constant M of Theorem 2 in terms of the constants N, R, k and Q of Theorem 3. This is done in Proposition 7 with a proof following the lines of the proof of [12, Proposition 4.35]. The difference is that we take care of all the needed bounds to express the constant of recognizability.

As a second step, we show that the constant L of Theorem 2 can be taken equal to M′ + |σ^{d}|, where d is defined as in Theorem 3 and M′ is such that for all i, m ∈ ℤ,

x_{[f^{(d)}(i)−M′,f^{(d)}(i)+M′]} = x_{[m−M,m+M]} ⇒ m ∈ E(x, σ^{d}).

We first start with the following lemma.

Lemma 6. Let σ : A^{∗} → A^{∗} be a non-erasing morphism, u ∈ A^{∗} be a word and n be a positive integer. If v = v_{0} ⋯ v_{t+1} ∈ A^{∗} is a word of length t + 2 such that σ^{n}(v[1, t]) is a factor of σ^{n}(u), and σ^{n}(u) is a factor of σ^{n}(v), then

\frac{⟨σ^{n}⟩}{|σ^{n}|}|u| − 2 ≤ t ≤ \frac{|σ^{n}|}{⟨σ^{n}⟩}|u|.

Proof. Indeed, since σ^{n}(v[1, t]) is a factor of σ^{n}(u) we have t⟨σ^{n}⟩ ≤ |σ^{n}(v_{[1,t]})| ≤ |σ^{n}(u)| ≤ |u||σ^{n}|. Hence t ≤ |u||σ^{n}|/⟨σ^{n}⟩. Similarly, since σ^{n}(u) is a factor of σ^{n}(v), we have |u| ≤ (t + 2)|σ^{n}|/⟨σ^{n}⟩. We thus have

|u|\frac{⟨σ^{n}⟩}{|σ^{n}|} − 2 ≤ t ≤ |u|\frac{|σ^{n}|}{⟨σ^{n}⟩}.

Proposition 7. Let σ : A^{∗} → A^{∗} be a morphism with an admissible fixed point x ∈ A^{ℤ}. Assuming that x is k-power-free and that there is some constant N such that for all n ∈ ℕ, |σ^{n}| ≤ N⟨σ^{n}⟩, we consider the constants

• R = ⌈N^{2}(k + 1) + 2N⌉;

• Q = 1 + p_{x}(R) (∑_{\frac{R}{N} ≤i≤RN+2} p_{x}(i)).

The constant M = R|σ^{Q}| is such that for all i, m ∈ ℤ,

x_{[f^{(1)}(i)−M,f^{(1)}(i)+M]} = x_{[m−M,m+M]} ⇒ m ∈ E(x, σ).  (2)

Proof. We follow the lines of the proof of [12, Theorem 2]. Obviously, if Equation (2) is true when we replace M by some l ≤ M, then it is true with M. Let us show such an l exists. We proceed by contradiction, assuming that for all l ≤ M, there exist i, j such that x_{[i−l,i+l]} = x_{[j−l,j+l]} with i ∈ E(x, σ) and j ∉ E(x, σ). For each integer p such that 0 < p ≤ Q, we consider the integer l_{p} = R|σ^{p}| ≤ M. Let i_{p} and j_{p} be some integers such that

x_{[i_{p}−l_{p},i_{p}+l_{p}]} = x_{[j_{p}−l_{p},j_{p}+l_{p}]}, with i_{p} ∈ E(x, σ) and j_{p} ∉ E(x, σ).

We let r_{p} and s_{p} denote the smallest integers such that

Card ([i_{p} − r_{p}, i_{p}) ∩ E(x, σ^{p})) = ⌈\frac{R}{2}⌉;
Card ([i_{p}, i_{p} + s_{p}] ∩ E(x, σ^{p})) = ⌊\frac{R}{2}⌋ + 1.

There is an integer i′_{p} such that

f^{(p)}(i′_{p}) = i_{p} − r_{p} and f^{(p)}(i′_{p} + R) = i_{p} + s_{p}.

We set

u_{p} = x_{[i′_{p},i′_{p}+R)}.

We have σ^{p}(u_{p}) = x_{[i_{p}−r_{p},i_{p}+s_{p})}.

Notice that any interval of length l_{p} contains at least R − 1 elements of E(x, σ^{p}). We thus have i_{p} − l_{p} ≤ i_{p} − r_{p} ≤ i_{p} + s_{p} ≤ i_{p} + l_{p}. Consequently we also have

x_{[j_{p}−r_{p},j_{p}+s_{p})} = σ^{p}(u_{p}).  (3)

However, j_{p}−r_{p} does not need to belong to E(x, σ^{p}). Let j′_{p} and t_{p} denote the unique integers such that

\begin{aligned}f^{(p)}(j′_{p}) < & j_{p} − r_{p} & ≤ f^{(p)}(j′_{p} + 1); \\ f^{(p)}(j′_{p} + t_{p} + 1) ≤ & j_{p} + s_{p} & < f^{(p)}(j′_{p} + t_{p} + 2). \end{aligned}  (4)

Consequently, the word σ^{p}(x_{[j′_{p}+1,j′_{p}+t_{p}]}) is a factor of σ^{p}(u_{p}) and the word σ^{p}(u_{p}) is a factor of σ^{p}(x_{[j′_{p},j′_{p}+t_{p}+1]}). By Lemma 6, we have

R\frac{⟨σ^{p}⟩}{|σ^{p}|} − 2 ≤ t_{p} ≤ R\frac{|σ^{p}|}{⟨σ^{p}⟩}.  (5)

Hence

\frac{R}{N} − 2 ≤ t_{p} ≤ RN.

Let v_{p} = x_{[j′_{p},j′_{p}+t_{p}+1]}. The number of possible pairs of words (u_{p}, v_{p}) is at most

p_{x}(R) ( ∑_{\frac{R}{N} ≤i≤RN+2} p_{x}(i)) < Q.

Therefore, there exist p and q in [1, Q] such that p < q and (u_{p}, v_{p}) = (u_{q}, v_{q}). In particular, we also have t_{p} = t_{q}. We write

t = t_{p},  u = u_{p},  v = v_{p},  ṽ = x_{[j′_{p}+1,j′_{p}+t]}.

Using the above notation we recall that we have

u = x_{[i′_{p},i′_{p}+R)} = x_{[i′_{q},i′_{q}+R)};  (6)
v = x_{[j′_{p},j′_{p}+t+1]} = x_{[j′_{q},j′_{q}+t+1]}.  (7)

Let A_{p}, B_{p}, A_{q} and B_{q} be the words

A_{p} = x_{[j_{p}−r_{p},f^{(p)}(j′_{p}+1))};
B_{p} = x_{[f^{(p)}(j′_{p}+t+1),j_{p}+s_{p})};
A_{q} = x_{[j_{q}−r_{q},f^{(q)}(j′_{q}+1))};
B_{q} = x_{[f^{(q)}(j′_{q}+t+1),j_{q}+s_{q})}.

We thus have

x_{[j_{p}−r_{p},j_{p}+s_{p})} = A_{p}σ^{p}(ṽ)B_{p} and x_{[j_{q}−r_{q},j_{q}+s_{q})} = A_{q}σ^{q}(ṽ)B_{q},  (8)

with, using (4),

max{|A_{p}|, |B_{p}|} ≤ |σ^{p}| and  max{|A_{q}|, |B_{q}|} ≤ |σ^{q}|.  (9)

From (3) and (8), we obtain

σ^{q−p}(A_{p})σ^{q}(ṽ)σ^{q−p}(B_{p}) = A_{q}σ^{q}(ṽ)B_{q}.

We claim that

A_{q} = σ^{q−p}(A_{p}) (and hence B_{q} = σ^{q−p}(B_{p})).  (10)

If not, the word σ^{q}(ṽ) has a prefix which is a power w^{r} with r = ⌊\frac{|σ^{q}(ṽ)|}{||A_{q}|−|σ^{q−p}(A_{p})||}⌋. Since, using (5) and (9),

|σ^{q}(ṽ)| ≥ t⟨σ^{q}⟩ ≥ (\frac{R}{N} − 2) ⟨σ^{q}⟩ and ||A_{q}| − |σ^{q−p}(A_{p})|| ≤ |σ^{q}|,

we deduce from the choice of R that r ≥ k + 1, which contradicts the definition of k. We thus have A_{q} = σ^{q−p}(A_{p}) and B_{q} = σ^{q−p}(B_{p}).

We now show that the elements of E(x, σ) occur in the two intervals [i_{q} − r_{q}, i_{q} + s_{q}] and [j_{q} − r_{q}, j_{q} + s_{q}] at the same relative positions, i.e.,

[j_{q} − r_{q}, j_{q} + s_{q}] ∩ E(x, σ) = ([i_{q} − r_{q}, i_{q} + s_{q}] ∩ E(x, σ)) − (i_{q} − j_{q}).  (11)

This will contradict the fact that i_{q} belongs to E(x, σ) and j_{q} does not.

By (7), we have

σ^{p}(v) = x_{[f^{(p)}(j′_{p}),f^{(p)}(j′_{p}+t+2))} = x_{[f^{(p)}(j′_{q}),f^{(p)}(j′_{q}+t+2))}.

Since σ^{p}(u) is a factor of σ^{p}(v), we deduce from (4) that there exists m_{q} ∈ ℤ such that

f^{(p)}(j′_{q}) < m_{q} − r_{p} < m_{q} + s_{p} < f^{(p)}(j′_{q} + t + 2)  (12)

and

x_{[m_{q}−r_{p},m_{q}+s_{p})} = σ^{p}(u) = A_{p}σ^{p}(ṽ)B_{p}.

By applying σ^{q−p}, we obtain

x_{[f^{(q−p)}(m_{q}−r_{p}),f^{(q−p)}(m_{q}+s_{p}))} = A_{q}σ^{q}(ṽ)B_{q},

and, from (12),

f^{(q)}(j′_{q}) < f^{(q−p)}(m_{q} − r_{p}) < f^{(q−p)}(m_{q} + s_{p}) < f^{(q)}(j′_{q} + t + 2).

As we also have

x_{[j_{q}−r_{q},j_{q}+s_{q})} = A_{q}σ^{q}(ṽ)B_{q}

with, by (4),

f^{(q)}(j′_{q}) < j_{q} − r_{q} ≤ f^{(q)}(j′_{q} + 1) ≤ f^{(q)}(j′_{q} + t + 1) ≤ j_{q} + s_{q} < f^{(q)}(j′_{q} + t + 2),

we apply the same argument as to show (10) and get j_{q} − r_{q} = f^{(q−p)}(m_{q} − r_{p}) (hence j_{q} + s_{q} = f^{(q−p)}(m_{q} + s_{p})). We thus get that j_{q} − r_{q} belongs to E(x, σ^{q−p}) ⊂ E(x, σ). Since we also have

x_{[f^{(1)}^{−1}(j_{q}−r_{q}),f^{(1)}^{−1}(j_{q}+s_{q}))} = σ^{q−p−1}(x_{[m_{q}−r_{p},m_{q}+s_{p})}) = σ^{q−p−1}(A_{p}σ^{p}(ṽ)B_{p}),
x_{[f^{(1)}^{−1}(i_{q}−r_{q}),f^{(1)}^{−1}(i_{q}+s_{q}))} = σ^{q−1}(x_{[i′_{q},i′_{q}+R)}) = σ^{q−p−1}(A_{p}σ^{p}(ṽ)B_{p}),

we get

x_{[f^{(1)}^{−1}(j_{q}−r_{q}),f^{(1)}^{−1}(j_{q}+s_{q}))} = x_{[f^{(1)}^{−1}(i_{q}−r_{q}),f^{(1)}^{−1}(i_{q}+s_{q}))},

with j_{q} − r_{q}, i_{q} − r_{q} belonging to E(x, σ). By applying σ to these two words, we thus obtain (11), which ends the proof.

Proposition 7 gives a more precise statement than Item 1 in Theorem 2. It also makes Item 2 more precise in the case of morphisms that are injective on A by taking L = M + |σ|. For non-injective morphisms, a key argument in Mossé’s original proof is to prove the existence of an integer d such that for all a, b ∈ A, if σ^{n}(a) = σ^{n}(b) for some n, then σ^{d}(a) = σ^{d}(b). Theorem 8 below ensures that we can take d = (Card A) − 1.

Theorem 8 ([6, Theorem 3]). Let σ : A^{∗} → A^{∗} be a morphism such that σ(A) ≠ {ε}. For all words u, v ∈ A^{∗}, we have

σ^{(Card A)−1}(u) ≠ σ^{(Card A)−1}(v) ⇒ ∀n, σ^{n}(u) ≠ σ^{n}(v).

We now give the proof of Item 2 in Theorem 2.

Proposition 9. Let σ : A^{∗} → A^{∗} be a morphism with an admissible fixed point x ∈ A^{ℤ}. Let d ∈ {1, 2, …, Card A} be such that for all words u, v ∈ L(x),

σ^{d−1}(u) ≠ σ^{d−1}(v) ⇒ ∀n, σ^{n}(u) ≠ σ^{n}(v).

If M is a constant such that for all i, m ∈ ℤ,

x_{[f^{d}(i)−M,f^{d}(i)+M]} = x_{[m−M,m+M]} ⇒ m ∈ E(x, σ^{d}),

then σ is recognizable on x and its constant of recognizability for x is at most M + |σ^{d}|.

Proof. Let i, m ∈ ℤ such that

x_{[f^{(1)}(i)−M−|σ^{d}|,f^{(1)}(i)+M+|σ^{d}|]} = x_{[m−M−|σ^{d}|,m+M+|σ^{d}|]}.

By the definition of M, there exists j ∈ ℤ such that m = f^{(1)}(j). Our goal is to show that x_{i} = x_{j}.

There exists k ∈ ℤ such that

f^{(1)}(i) − |σ^{d}| < f^{(d)}(k) ≤ f^{(1)}(i) < f^{(d)}(k + 1) ≤ f^{(1)}(i) + |σ^{d}|.

In particular, this implies that f^{(d−1)}(k) ≤ i < f^{(d−1)}(k + 1).

Consider c = f^{(1)}(i) − f^{(d)}(k) and d = f^{(d)}(k + 1) − f^{(1)}(i). We have

x_{[f^{(d)}(k)−M,f^{(d)}(k)+M]} = x_{[f^{(1)}(j)−c−M,f^{(1)}(j)−c+M]};
x_{[f^{(d)}(k+1)−M,f^{(d)}(k+1)+M]} = x_{[f^{(1)}(j)+d−M,f^{(1)}(j)+d+M]}.

By the definition of M, there exists l ∈ ℤ such that

f^{(d)}(l) = f^{(1)}(j) − c and f^{(d)}(l + 1) = f^{(1)}(j) + d.

We thus have f^{(d−1)}(l) ≤ j < f^{(d−1)}(l + 1), and,

x_{[f^{(d)}(k),f^{(d)}(k+1))} = x_{[f^{(d)}(l),f^{(d)}(l+1))}.

Hence σ^{d}(x_{k}) = σ^{d}(x_{l}). By the definition of d, we also have σ^{d−1}(x_{k}) = σ^{d−1}(x_{l}). Hence

x_{[f^{(d−1)}(k),f^{(d−1)}(k+1))} = x_{[f^{(d−1)}(l),f^{(d−1)}(l+1))}.

Since we have f^{(1)}(i) − f^{(d)}(k) = f^{(1)}(j) − f^{(d)}(l), we also have i − f^{(d−1)}(k) = j − f^{(d−1)}(l). Hence x_{i} = x_{j}.

4 Proof of Theorem 4

In this section, we show that the constants appearing in Theorem 3 can all be bounded by some computable constants. In all what follows, we assume that σ : A^{∗} → A^{∗} is a primitive morphism. By taking a power of σ if needed, we can assume that it has an admissible fixed point x ∈ A^{ℤ}. Furthermore, we have L(x) = L(y) for all admissible fixed points y of σ. We let L(σ) denote this set and we write L_{n}(σ) = L(σ) ∩ A^{2}. The constants appearing in Theorem 3 are thus the same whatever the admissible fixed point we consider and the morphism is recognizable.

With the morphism σ, one associates its incidence matrix M_{σ} defined by (M_{σ})_{a,b} = |σ(b)|_{a}, where |u|_{a} denotes the number of occurrences of the letter a in the word u. If σ is a primitive morphism, it is well known that for all a ∈ A there exists a constant c_{a} such that |σ^{n}(a)| ≤ c_{a}α^{n} for all n, where α is the dominant eigenvalue of M_{σ} (see [2] for a detailed study of |σ^{n}(a)|).

Lemma 10 ([9]). A d×d matrix M is primitive if and only if there is an integer k ≤ d^{2}−2d+2 such that M^{k} contains only positive entries.

Given an infinite word x ∈ A^{ℤ} and a word u ∈ L(x), a return word to u in x is a word r such that ru belongs to L(x), u is a prefix of ru and ru contains exactly two occurrences of u. The infinite word x is linearly recurrent if it is recurrent (all words in L(x) appear infinitely many times in x) and there exists some constant K such that for all u ∈ L(x), any return word to u has length at most K|u|.

The next two results give bounds on the constants appearing in Theorem 3.

Theorem 11 ([5]). If x ∈ A^{ℤ} is a aperiodic and linearly recurrent sequence for the constant K, then x is (K + 1)-power-free and p_{x}(n) ≤ Kn for all n.

Proposition 12 ([4]). Let σ : A^{∗} → A^{∗} be an aperiodic primitive morphism and x be one of its admissible fixed points. Then, for all n, we have

|σ^{n}| ≤ |σ|^{(Card A)^{2}}⟨σ^{n}⟩.

Furthermore, x is linearly recurrent for some constant

K_{σ} < |σ|^{4(Card A)^{2}}.

Proof. Durand [4] showed that the constant of linear recurrence K_{σ} is at most equal to T N|σ|, where

• N is a constant such that |σ^{n}| ≤ N⟨σ^{n}⟩ for all n;

• T is the maximal length of a return word to a word in L_{2}(σ).

Here we only prove that N ≤ |σ|^{(Card A)^{2}} and T ≤ 2|σ|^{2(Card A)^{2}}. The constant of linear recurrence is thus at most 2|σ|^{1+3(Card A)^{2}} < |σ|^{4(Card A)^{2}}.

Let us write d = Card A. By Lemma 10, the matrix M_{σ}^{d^{2}} contains only positive entries. For all n ≥ 0 and all a ∈ A, we have |σ^{n+d^{2}}(a)| = ∑_{b∈A} |σ^{d^{2}}(a)|_{b}|σ^{n}(b)| ≥ |σ^{n}|. Since this is true for all a, we get |σ^{n}| ≤ ⟨σ^{n+d^{2}}⟩ ≤ |σ^{d^{2}}|⟨σ^{n}⟩, so N ≤ |σ^{d^{2}}|.

Let a ∈ A such that σ is prolongable on a. Thus for all n, any word that occurs in σ^{n}(a) also occurs in σ^{n+1}(a). Let us show that for all n > d^{2}, any word u ∈ L_{2}(σ) occurs in σ^{n}(a). For all n, the words of L_{2}(σ) that occur in σ^{n+1}(a) occur in images under σ of the words of L_{2}(σ) that occur in σ^{n}(a). As any word occurring in σ^{n}(a) also occurs in σ^{n+1}(a), the words of L_{2}(σ) that occur in σ^{n+1}(a) are those that occur in σ^{n}(a) together with those occurring in the images under σ of these words. Thus, if there is a word of L_{2}(σ) that does not occur in σ^{n}(a), there is a sequence (u_{1}, u_{2}, …, u_{n}) of words in L_{2}(σ) such that for all i ≤ n, u_{i} occurs in σ^{i}(a) and does not occur in σ^{i−1}(a). Hence all words u_{1}, …, u_{n} are distinct. For n > d^{2}, this is a contradiction since there are at most d^{2} words in L_{2}(σ). Thus, for any letter b ∈ A, all words u ∈ L_{2}(σ) occur in σ^{2d^{2}}(b). We deduce that T ≤ 2|σ^{2d^{2}}|.

Proof of Theorem 4. We just have to carry out the computation. Using Theorem 11, Proposition 12 and the notation of Theorem 3, we can take d = Card A and we successively have

k ≤ 1 + K_{σ} ≤ |σ|^{4d^{2}};
N ≤ |σ|^{d^{2}};
R = ⌈N^{2}(k + 1) + 2N⌉ ≤ |σ|^{2d^{2}}(|σ|^{4d^{2}} + 1) + 2|σ|^{d^{2}} ≤ 2|σ|^{6d^{2}};
Q = 1 + p_{x}(R) ( ∑_{\frac{R}{N} ≤i≤RN+2} p_{x}(i)) ≤ K_{σ}2|σ|^{6d^{2}} ( ∑_{0≤i≤2+2|σ|^{7d^{2}}} iK_{σ}) ≤ 6|σ|^{28d^{2}}.

We finally get that the constant of recognizability of σ is at most

2|σ|^{6d^{2}}|σ|^{6d|σ|^{28d^{2}}} + |σ|^{d} = 2|σ|^{6d^{2}+6d|σ|^{28d^{2}}} + |σ|^{d}.

5 Recognizability of powers of morphisms

Theorem 3 gives a general bound on the constant of recognizability of recognizable morphisms. Powers of a recognizable morphism σ are obviously recognizable. However, the bound given in Theorem 3 applied to σ^{p} is far from being optimal. In this section we give two results concerning the constant of recognizability of σ^{p}.

Proposition 13. If σ : A^{∗} → A^{∗} is recognizable on x ∈ A^{ℤ} and if L is the constant of recognizability of σ for x, then for all p > 0, σ^{p} is recognizable on x and its constant of recognizability for x is at most L ∑_{i=0}^{p−1} |σ^{i}|.

Proof. The result holds by induction on p > 0. The case p = 1 is trivial. Let us assume that the result holds for p − 1 and let us prove it for p. The infinite word x is obviously an admissible fixed point of σ^{p}. With L_{p} = L ∑_{i=0}^{p−1} |σ^{i}|, let us show that for all i ∈ ℤ, the word

x_{[f^{(p)}(i)−L_{p},f^{(p)}(i)+L_{p}]}

uniquely determines the letter x_{i}.

Let m and M be, respectively, the smallest and the largest integer such that

f^{(p)}(i) − L_{p} ≤ f^{(p−1)}(m) − L_{p−1} < f^{(p−1)}(M) + L_{p−1} ≤ f^{(p)}(i) + L_{p}  (13)

and let us show that

m ≤ f^{(1)}(i) − L < f^{(1)}(i) + L ≤ M.  (14)

We consider the first inequality with m > 0; the other cases are similar. The integer m being the smallest one satisfying (13), we have

f^{(p−1)}(m − 1) − L_{p−1} < f^{(p)}(i) − L_{p}.

Since we have f^{(p−1)}(m) = f^{(p−1)}(m − 1) + |σ^{p−1}(x_{m−1})| and L_{p} − L_{p−1} = L|σ^{p−1}|, we get

f^{(p)}(i) > f^{(p−1)}(m) + L|σ^{p−1}| − |σ^{p−1}(x_{m−1})| ≥ f^{(p−1)}(m) + (L − 1)|σ^{p−1}|.  (15)

Assume by contradiction that f^{(1)}(i) < m + L, hence that f^{(1)}(i) ≤ m + L − 1. The function f^{(p−1)} being increasing, we have

f^{(p−1)}(f^{(1)}(i)) = f^{(p)}(i) ≤ f^{(p−1)} (m + L − 1) = f^{(p−1)}(m) + |σ^{p−1}(x_{[m,m+L−1)})|.

We thus get

f^{(p)}(i) ≤ f^{(1)}(m) + (L − 1)|σ^{p−1}|,

which contradicts (15).

Let us now finish the proof of the result. Using the induction hypothesis, the word x_{[f^{(p−1)}(m)−L_{p−1},f^{(p−1)}(M)+L_{p−1}]} uniquely determines x_{[m,M]}. As x_{[f^{(p−1)}(m)−L_{p−1},f^{(p−1)}(M)+L_{p−1}]} is a factor of x_{[f^{(p)}(i)−L_{p},f^{(p)}(i)+L_{p}]} by (13) and x_{[f^{(1)}(i)−L,f^{(1)}(i)+L]} is a factor of x_{[m,M]} by (14), the word x_{[f^{(p)}(i)−L_{p},f^{(p)}(i)+L_{p}]} uniquely determines x_{[f^{(1)}(i)−L,f^{(1)}(i)+L]}. We conclude by the definition of recognizability.

Corollary 14. If σ : A^{∗} → A^{∗} is aperiodic primitive and if L is its constant of recognizability on x ∈ A^{ℤ}, then σ^{p} is recognizable on x and its constant of recognizability for x is at most LC \frac{α^{p}−1}{α−1}, where α is the dominant eigenvalue of M_{σ} and C is a constant such that |σ^{p}| ≤ Cα^{p} for all p. In particular, the constant C can be taken equal to

\frac{max_{1≤k≤Card A} y_{k}}{min_{1≤k≤Card A} y_{k}} ,

where y = (y_{k})_{1≤k≤Card A} is a positive eigenvector of M_{σ}.

Proof. The proof directly follows from [9, Corollary 8.1.33].

6 Acknowledgments

This work was supported by the Hubert Curien Partnership Tournesol entitled “Algorithmique des substitutions et systèmes de numération”.

References

[1] V. Canterini and A. Siegel, Geometric representation of substitutions of Pisot type, Trans. Amer. Math. Soc. 353 (2001), 5121–5144.

[2] É. Charlier, J. Leroy, and M. Rigo, Asymptotic properties of free monoid morphisms, Linear Algebra Appl. 500 (2016), 119–148.

[3] C. Choffrut and J. Karhumäki, Combinatorics of words. In Handbook of Formal Languages, Vol. 1, Springer, 1997, pp. 329–438.

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

[5] F. Durand, B. Host, and C. Skau, Substitutional dynamical systems, Bratteli diagrams and dimension groups, Ergodic Theory Dynam. Systems 19 (1999), 953–993.

[6] A. Ehrenfeucht and G. Rozenberg, Simplifications of homomorphisms, Inform. and Control 38 (1978), 298–309.

[7] N. P. Fogg, Substitutions in Dynamics, Arithmetics and Combinatorics, Lecture Notes in Mathematics, Vol. 1794, Springer-Verlag, 2002.

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

[9] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, 1990.

[10] L. Kari, G. Rozenberg, and A. Salomaa, L systems. In Handbook of Formal Languages, Vol. 1, Springer, 1997, pp. 253–328.

[11] K. Klouda and K. Medková, Synchronizing delay for binary uniform morphisms, Theoret. Comput. Sci. 615 (2016), 12–22.

[12] P. Kůrka, Topological and Symbolic Dynamics, Cours Spécialisés, Vol. 11, Société Mathématique de France, 2003.

[13] F. Mignosi and P. Séébold, If a D0L language is k-power free then it is circular. In Automata, Languages and Programming, Lecture Notes in Comput. Sci., Vol. 700, Springer, 1993, pp. 507–518.

[14] B. Mossé, Puissances de mots et reconnaissabilité des points fixes d’une substitution, Theoret. Comput. Sci. 99 (1992), 327–334.

[15] B. Mossé, Reconnaissabilité des substitutions et complexité des suites automatiques, Bull. Soc. Math. France 124 (1996), 329–346.

[16] M. Queffélec, Substitution Dynamical Systems—Spectral Analysis, Lecture Notes in Mathematics, Vol. 1294, Springer-Verlag, 2nd edition, 2010.

2010 Mathematics Subject Classification: Primary 68R15, Secondary 68Q01. Keywords: combinatorics on words, substitution, recognizability, circularity.

Received October 14 2016; revised versions received November 9 2016; January 26 2016; February 6 2017. Published in Journal of Integer Sequences, February 10 2017.

Return to Journal of Integer Sequences home page.