Ján Maňuch
email: manuch@cs.utu.fi

Defect Effect of Bi-infinite Words in the Two-element Case

Keywords:

Let X be a two-element set of words over a finite alphabet. If a bi-infinite word possesses two X-factorizations which are not shiftequivalent, then the primitive roots of the words in X are conjugates. Note, that this is a strict sharpening of a defect theorem for bi-infinite words stated in [KMP2].

Moreover, we prove that there is at most one bi-infinite word possessing two different X-factorizations and give a necessary and sufficient conditions on X for the existence of such a word. Finally, we prove that the family of sets X for which such a word exists is parameterizable.

Introduction

Defect theorem is one of the fundamental results on words, cf [Lo]. Intuitively it states that if n words satisfy a nontrivial relation, then these words can be expressed as products of at most n -1 words. Actually, as discussed in [CK], for example, there does not exist just one defect theorem but several ones depending on restrictions put on the required n -1 words.

It is also well-known that the nontrivial relation above can be replaced by a weaker condition, namely by the nontrivial one-way infinite relation, cf. [Br] and [HK]. The goal of this note is to look for defect theorems for bi-infinite words. In a strict sense such results do not exist: the set X = {ab, ba} of words satisfies a bi-infinite nontrivial relation since (ab) Z = (ba) Z , but there exists no word ρ such that X ⊆ ρ + . However, in [START_REF] Karhumäki | A defect theorem for bi-infinite words[END_REF] there was proved one result and we are going to prove another one in a special case which both can be viewed as defect theorems for bi-infinite words.

In terms of factorizations of words defect theorem can be stated as follows: Let X ⊆ Σ + be a finite set of words. If there exists a word w ∈ Σ + having two different X-factorizations, then the rank of X is at most card(X) -1. Here the rank of X can be defined in different ways, cf again [CK]. For example, it can be defined as a combinatorial rank r c (X) denoting the smallest number k such that X ⊆ Y + with card(Y ) = k.

Our paper is organized as follows.

In Section 2 we fix our terminology and present the auxiliary results needed for our proofs. In Section 3 we prove, as our main result, a defect theorem for binary sets X satisfying a nontrivial bi-infinite relation. To prove this seems to be quite complicated. In Section 4 we prove the second part of our result, i.e., the uniqueness of the X-ambiguous bi-infinite word in the two-element case. In Section 5 we give a characterization of two-element sets X, which allow an X-ambiguous bi-infinite word. The last section contains conclusions and open problems.

The extended abstract of this paper and paper [START_REF] Karhumäki | A defect theorem for bi-infinite words[END_REF] has appeared in [START_REF] Karhumäki | On defect effect of bi-infinite words[END_REF].

Preliminaries

In this section we fix our terminology and recall a few lemmas on combinatorics of words needed for the proofs of our results. For undefined notions we refer to [Lo] or [CK].

Let Σ be a finite alphabet and X a finite subset of Σ + . The sets of all finite, infinite and bi-infinite words over Σ are denoted by Σ * , Σ N and Σ Z , respectively. Formally, a representation of bi-infinite word is a mapping f w : Z → Σ, usually written as

w = . . . a -1 a 0 a 1 . . . with a i = f w (i) .
Representations f : Z → Σ and f ′ : Z → Σ represent the same bi-infinite word if there exists an integer i 0 such that for all integers i, f

(i) = f ′ (i 0 + i).
Let f w be a representation of a bi-infinite word w. We say that a bi-infinite word is periodic if there exists a positive integer i 0 , called a period, such that f w (i) = f w (i 0 + i) for all integers i. Note that a non-periodic bi-infinite word has infinitely many representations, while a periodic one has exactly π(w) representations, where π(w) is the smallest period of w.

An X-factorization of w is any sequence of words from X yielding w as their products. Formally, let f w be a fixed representation of w ∈ Σ Z . An X-factorization of w is a mapping F : Z → X × Z such that for each k ∈ Z if F(k) = (α, i) and F(k + 1) = (β, j), then a i a i+1 . . . a j-1 = α, i.e., the position i is a starting position of the factor α in w. We say that two X-factorizations F 1 and F 2 of a bi-infinite word are

• different, whenever there is a k 0 ∈ Z such that for each k ∈ Z, F 1 (k 0 ) = F 2 (k),
• disjoint, whenever the starting positions of all factors in F 1 are distinct from the ones in F 2 ,

• shiftequivalent, if there is a k 0 such that whenever

F 1 (k) = (α, i) and F 2 (k 0 + k) = (β, j), then α = β.
Notice that the above definitions are independent on the choice of a representation of w.

An X-ambiguous bi-infinite word is a bi-infinite word, which has two different X-factorizations. Let amb (X) be the set of all X-ambiguous bi-infinite words and let sum(X) be the sum of lengths of words in X, i.e., the size of X. We define the combinatorial rank of X ⊆ Σ + by the formula

r c (X) = min{card(Y ) | X ⊆ Y + } .
For the sake of completeness we remind that

r c (X) ≤ r f (X) ≤ card(X) ,
where r f (X) denotes the free rank (or simply the rank) of X defined as the cardinality of the base of the smallest free semigroup containing X, cf [CK].

Example 1 (continued). Clearly, r c (X) = 2, since X ⊆ {a, b} + , but for no word ρ the inclusion X ⊆ ρ + holds. On the other hand, since X is a code we conclude that r f (X) = 3.

Ján Maňuch

We say that a finite word w = w 1 . . . w m has a period n ∈ N, if there is a word u such that w = u n . The shortest period is called the period of w, denoted as π(w). If w = u π(w) , then u is called the root of w, denoted as ρ(w). A word w is primitive if ρ(w) = w. The mirror image of w, denoted w R , is the word w m . . . w 1 .

Next we recall a few basic results on words that we shall need in our later considerations, for their proofs the reader is referred to [Lo] or [CK]. Lemma 3. If two words u and v satisfy the relation ut = tv for some u, v,t ∈ Σ + , i.e., if they are conjugates, then there exist words p and q such that pq is primitive and u = (pq) i , v = (qp) i and t ∈ p(qp) * for some i ≥ 1 .

In Section 4 we shall need also the following result which has been proved in [LyS].

Lemma 4. Consider nonempty words x, y, z satisfying equation x m = y n z p , where m, n, p ≥ 2. Then all words x, y, z are powers of a common word.

In order to formulate our fifth, and most crucial lemma, we need some terminology, cf [CK] or [HK].

We associate a finite set X ⊆ Σ + with a graph G X = (V X , E X ), called the dependency graph of X, as follows: the set V X of vertices of G X equals to X, and the set E X of edges of G X is defined by the condition

(x, y) ∈ E X iff xX N ∩ yX N = / 0 .

Then we have

Lemma 5. For each finite set X ⊆ Σ + , the combinatorial rank of X is at most the number of connected components of G X .

As we shall see, Lemma 5 is particularly suitable for our subsequent considerations. Indeed, in that lemma it is crucial that words in X are nonempty, and that indeed is satisfied in the proofs of our Theorem 2.

The Two-element Case

In this section we generalize the following result of [START_REF] Karhumäki | A defect theorem for bi-infinite words[END_REF] in the case of two-element sets.

Theorem 1. Consider a set X = {α 1 , . . . , α n } ⊆ Σ + . Let w be a bi-infinite word over Σ and F 1 , F 2 two different X-factorizations of w. Then the combinatorial rank of X is at most n -1, or both the word w and the X-factorizations F 1 , F 2 are periodic. Moreover, if the rank of X is n, then the number of periodic bi-infinite words with two different X-factorizations is finite.

A restriction of Theorem 1 to two-element sets yields the following consequence. Corollary 1. Consider set X = {α, β} ⊆ Σ + . Let w be a bi-infinite word over Σ and F 1 , F 2 two different X-factorizations of w. Then the words α, β commute or both the word w and the X-factorizations F 1 , F 2 are periodic.

First we recall that in a strict sense we cannot have a defect theorem for bi-infinite words even in this simple case.

Example 2. The set X = {ab, ba} is of combinatorial rank 2 although the word (ab) Z has two disjoint, and even non-shiftequivalent, X-factorizations.

As a main result of this paper we, however, show that the above example, and its natural variants, are the only exceptions which may occur. And even in these cases the roots of words in X are conjugates, i.e., they are cyclic permutations of powers of a common word.

To prove our main result we will need also one partial result from [START_REF] Karhumäki | A defect theorem for bi-infinite words[END_REF], which can be stated as follows:

Lemma 6. Let X ⊆ Σ + and let w = . . . w -2 w -1 w 0 w 1 w 2 . . . be a bi-infinite word. If there exists words f 1 , f 2 , f ′ 1 , f ′ 2 ∈ X + , a word t ∈ Σ + and integers i < j < k < l, i ′ < j ′ < k ′ < l ′ , such that t = w i . . . w j-1 = w k . . . w l-1 = w i ′ . . . w j ′ -1 = w k ′ . . . w l ′ -1 , f 1 = w j . . . w l-1 , f ′ 1 = w j ′ . . . w l ′ -1 , f 2 = w i . . . w k-1 , f ′ 2 = w i ′ . . . w k ′ -1 , then either f 1 and f ′ 1 (resp. f 2 and f ′ 2 ) commute, or r c (X) < card(X).
In the notation of [START_REF] Karhumäki | A defect theorem for bi-infinite words[END_REF] this lemma claims that the situation when w possesses two different minimal t-pairs implies a defect effect. This situation is depicted in Figure 1. Theorem 2. Consider set X = {α, β} with α, β ∈ Σ + . Let w be a bi-infinite word over Σ and F 1 , F 2 two different X-factorizations of w containing together both elements of X. Then one of the following possibilities holds:

✄ t t t t f 2 f 1 f ′ 2 f ′ 1
(i) α and β commute, or (ii) the roots of α and β are conjugates and

F 1 ∈ α Z , F 2 ∈ β Z , or vice versa, or (iii) the two X-factorizations F 1 , F 2 are shiftequivalent and there exists an n ≥ 1 such that F 1 , F 2 ∈ (αβ n ) Z and α is primitive or F 1 , F 2 ∈ (βα n ) Z and β is primitive.
Proof. We can assume that α and β do not commute. Then, by Lemma 5, the factorizations F 1 , F 2 must be disjoint. Indeed, if factorizations F 1 and F 2 are not disjoint, then we can take the parts of factorizations to the right (respectively, to the left) from a

Ján Maňuch

place where they are joint to obtain an infinite equation

x 1 x 2 • • • = y 1 y 2 . . . over X (respectively, x R 1 x R 2 • • • = y R 1 y R 2 . . . over X R ).
Since the factorizations are different, at least one of these two equations is nontrivial. Hence, by Lemma 5, the words α and β commute, a contradiction.

Further, by Corollary 1, the factorizations F 1 , F 2 are periodic. By Lemma 1 the periods of F 1 and F 2 have the same length and are conjugates. Whenever we find the situation which is shown in Figure 2, since the factorizations are periodic with the same length of the periods, this situation occurs infinitely many times. Using Lemma 6 we get that f 1 , f 2 are periods of F 1 , F 2 .

☎ t t f 2 ∈ X + f 1 ∈ X + Fig. 2. In the situation depicted in the picture f 1 ( f 2 ) is a part of the factorization F 1 (of the factorization F 2 ).
If both α and β are not primitive, we can replace them by powers of their roots ρ(α) π(α) , ρ(β) π(β) and explore the situation over a slightly different set X = {ρ(α), ρ(β)}. If we prove that the claim holds for ρ(α), ρ(β), then, as is obvious, it must hold also for α and β and, moreover, in case (iii) we have either π(α) = 1, i.e., α is primitive, or π(β) = 1, i.e., β is primitive. So it is enough to consider only the case when α and β are primitive. Without loss of generality we can also assume that |α| ≤ |β|. Now, if F 2 does not contain the factor αβ, then it contains only α's or only β's or there is a point inside F 2 from which to the left there are only β's and to the right only α's. In the last case the factorization F 2 is clearly nonperiodic -a contradiction with Corollary 1. Consider now, for example, the case F 2 = α Z . If F 1 contains any α, then we have the situation depicted in Figure 3 which, by Lemma 2, contradicts the primitiveness of α. So we have F 1 = β Z , and, by Lemma 1, α and β must be conjugates, which is case (ii).

✝ α β α ✞ α β β ✟ α β β Fig. 4. All possible coverings of factor αβ in F 2 .
From now on we may assume that F 2 contains the factor αβ. In Figure 4 we can see all possibilities how F 1 covers the border between the above occurrences of α and β. We shall analyze all three cases. Case 1,2. We can analyze first two cases simultaneously, because when we forget about the relation between lengths of α and β, then they are clearly symmetric. So consider the second case of 3 possibilities drawn in Figure 4. If the word to the right of the β in the factorization F 1 is also β, then β is not primitive which is not the case. Hence, we have the situation shown in Figure 5. Now if z R = α or z L = α, then v 1 = v 2 and we arrive into the situation depicted in Figure 2 with f 1 = βα and f 2 = αβ which is case (iii) of our claim. So consider the other case when z R = z L = β. We can continue in this way inductively until sequences of β's exceed α's (on both sides at the same time) or we obtain the situation in Figure 2 with

✠ v 1 v 2 α β z R z L β α
f 1 = β n α, f 2 = αβ n , for some n ≥ 1, which is again case (iii).
The first possibility is shown in Figure 6. Now again if z R = β, then we have v 1 = v 2 , and hence we are again in case (iii). So assume that z R = α. We have β = v 3 t = tv 4 , which by Lemma 3 allows us to write v 3 = (pq) k , v 4 = (qp) k , t = p(qp) n , where pq is primitive and k ≥ 1, n ≥ 0. We can see that α ends with pq and starts with qp. This means that the word pqqp matches the word β = (pq) k+n p around the black point shown in Figure 6. Since the factorizations are disjoint, the black point must lie inside β. There are 5 possibilities where the black point inside β can be. In case (1) the black point matches with the end of the first p in β, in case (2) it matches with the end of any pq in β, in case (3) it occurs inside the first p of β, in case (4) inside the first q, and, finally, in the last case it occurs in the rest of β, as it is shown in Figure 7.

✡ v 1 v 2 v 3 t v 4 z L α β i≥2 β β β β β α z R ( = α) . . . . . .
☛ p q p β (3) (4) (5)
(1) (2) . . . . . . In case (1) we have, according to Figure 6, the following two equations with unknowns Y = {α, p, q}:

α = v 4 β i-2 p = qw 1 , α = pβ i-2 v 3 = pw 2 , where w 1 , w 2 ∈ Y * .

Ján Maňuch

The dependency graph of this system is then connected which implies that unknowns in Y , and hence also α and β, commute, which is a contradiction.

Similarly, in case (2) we can write

α = v 4 β i-2 (pq) l , αe 1 β i α = p(qp) k+n-l e 2 αβ i-1 (pq) l ,
where l ≥ 1, e 1 , e 2 ∈ X * and the second equation is obtained by taking parts of F 1 , F 2 between the black point and the next occurrence (to the right) of the black point, so e i is a part of the factorization F i . We can rewrite these two equations as a system of equations with unknowns Y = {α, p, q}:

α = qpw 1 , αw 2 = pw 3 , where w 1 ∈ {p, q} * , w 2 , w 3 ∈ Y * ,
and, by Lemma 5, we have again a contradiction.

In case (3) the qp, which follows the black point, lies inside the first pqp in β. But this is a contradiction because then pq cannot be primitive. In case (5) we can use the same argument with the pq which precedes the black point. The situation around the black point in case ( 4) is shown in Figure 8. It follows, by Lemma 2, that q is not primitive, and that there is an s such that u 1 = s i , u 2 = s j and q = s i+ j with i, j ≥ 1. Now, as above, we have two equations with unknowns Y = {α, p, s}:

☞ u 1 u 2 u 1 u 2 p q p p q q p α α u 1 u 2 u 1 u 2 p q p p q q p α α
α = v 4 β i-2 pu 2 = s i+ j w 1 , s j w 1 e 1 α = u 1 -1 αe 1 α = (pq) k+n-1 pe 2 αβ i-1 pu 2 = pw 2 ,
where w 1 , w 2 ∈ Y * and e 1 , e 2 ∈ X * are parts of the X-factorizations. Note that the second equation deals with the word starting with the first u 2 after the black point and ending in the next occurrence of the black point.

Case 3. Now we shall analyze the third possibility shown in Figure 4. Since β is primitive there must be α to the right of the β on the upper line. Using the same considerations as in the previous case we come to Figure 9, or we end up in case (iii) with f 1 = βα n , f 2 = α n β for some n ≥ 1. In the first case we have Assume first that z R = α. We know that β starts with v 3 v 1 , so, as it is shown in Figure 10, v 3 v 1 lies inside αα = v 1 v 3 v 1 v 3 . This implies that either α is not primitive, or v 3 v 1 matches with v 3 v 1 in αα. In the first case we have a contradiction. In the second case it is obvious from Figure 10 that v 2 = v 3 , say equal to p, and v 1 = v 4 , say equal to q, and moreover that |p| = |v 3 | = |v 4 | = |q|. So we have pα i-1 β = βα i-1 q, which means that v = pα i-1 = p(qp) i-1 conjugates with u = α i-1 q = q(pq) i-1 . We shall show that this is again a contradiction with the primitiveness of α = qp. We have already analyzed this situation. Since the word u is a conjugate with v, a factor of the word uu must be equal to the word v. The word u starts with qp and ends with pq, so the middle point of the word pqqp lies inside the word v = p(qp) i-1 . There are again 5 possibilities (see Figure 7). Since |p| = |q| in cases ( 1) and ( 2) we have p = q, so that α = v 1 v 3 = qp = p 2 proving that α is not primitive, a contradiction. In cases ( 3) and ( 5) we also have a contradiction with the primitiveness of α as we already proved. In case (4) we have u 1 = s i , u 2 = s j , q = s i+ j (see Figure 8), and since |p| = |q| we also have p = u 2 u 1 = s i+ j = q, which is again a contradiction.

α = v 1 v 3 = v 4 v 2 ,
✌ v 1 v 2 v 3 v 4 β i≥2 α α α α β β z R . . . . . .
✍ v 4 v 2 v 4 v 2 β v 3 v 1 β α z R = α . . .
✎ v 4 v 2 v 4 t β β z ( = α) α v 2 v 4 z R = β . . .
v 2 v 4 = v 4 t = v 4 v 1 .
According to Figure 9 and Figure 11 we have the following system of equations with unknowns

Y = {β, v 1 , v 2 , v 3 , v 4 }: v 2 v 4 = v 4 v 1 , v 3 (v 1 v 3 ) i-1 β = β(v 4 v 2 ) i-1 v 4 , (α = ) v 1 v 3 = v 4 v 2 , v 2 β = βv 1 .
The dependency graph associated with this system is connected, and hence all unknowns commute, in particular α commutes with β. This completes the proof of the theorem.

Ján Maňuch

Theorem 2 deserves a few comments. The number of different X-factorizations of the bi-infinite word w having an X-factorization is very different in cases (i)-(iii). In case (i) there exist non-denumerably many such X-factorizations, in case (ii) there are finitely many different X-factorizations, and if we consider all shiftequivalent X-factorizations as the one, then there are exactly two of them. Finally, in case (iii) there are also finitely many different X-factorizations, which are all shiftequivalent. This actually means that in case (iii) no bi-infinite word can be expressed in two different ways as a product of words from X. Hence, indeed, Theorem 2 shows a defect effect of a two-element set for bi-infinite factorizations.

In Theorem 2 we showed that if the words of X do not commute and their roots are not conjugates, then only the case (iii) is possible. But if they do not commute and are conjugates Theorem 2 allows either case (ii) or (iii). Now we shall prove that in this situation only case (ii) is possible. According to the last part of the proof of Theorem 2, we can formulate the following lemma.

Lemma 7. If pq is primitive and p, q are nonempty, then p(qp) n and q(pq) n are not conjugates for any n ≥ 1.

This yields easily

Corollary 2. If α and β are different conjugates, then αβ must be primitive.

Proof. Assume the contrary that αβ is not primitive, so we have αβ = t i , where t is primitive and i ≥ 2. Now if i is even, then immediately α = β, which is a contradiction. For odd i = 2n + 1 we have α = t n p, β = qt n , where t = pq. But α and β are conjugates and so, by Lemma 7, we have a contradiction.

In fact Corollary 2 is a special case of the claim in [LeS] which states under the additional assumption that α, β are primitive, that αβ m is primitive for all natural numbers m. The proof is not difficult, but we need only this special case to prove the next result. Corollary 3. Consider set X = {α, β} with α, β ∈ Σ + . Let w be a bi-infinite word over Σ and F 1 , F 2 two different X-factorizations of w containing together both elements of X. If the roots of α, β are noncommuting conjugates, then F 1 ∈ α Z , F 2 ∈ β Z , or vice versa.

Proof. Again as in the proof of Theorem 2, we can assume that α, β are primitive. We have to show that the one of the X-factorizations F 1 , F 2 consists only of α's and the other only of β ′ s. So assume the contrary that the lower factorization contains both α and β. Without loss of generality we have the situation shown in Figure 12. Since β is primitive we have z = α, by Lemma 2. We can write β = u 2 u 3 = u 3 u 4 , and so, by Lemma 3, we have

✏ u 1 u 2 u 3 u 4 u 5 z L β α z = α β
u 2 = (pq) i , u 4 = (qp) i , i ≥ 1 , u 3 = p(qp) n , n ≥ 0 ,
where pq is primitive. If z L = α, then, by Lemma 2, αβ is not primitive, which contradicts Corollary 2. Hence assume z L = β, which implies u 1 = u 3 . Similarly u 5 = u 3 and we have p(qp) n (pq) i = u 1 u 2 = α = u 4 u 5 = (qp) i p(qp) n . By Lemma 5, then p and q commute, which is again a contradiction.

4 The Uniqueness of the Bi-infinite Word

In [START_REF] Karhumäki | A defect theorem for bi-infinite words[END_REF], cf. Theorem 1 it was proved that if the rank of the set X equals to card(X), then the number of X-ambiguous bi-infinite words is finite. In this section we shall prove that in the two-element case, for each set X, there is at most one X-ambiguous bi-infinite word. This holds also in the case when r c (X) = 1, since then both elements of X are powers of a common word t and the only possible bi-infinite word is t Z . The situation is also trivial in the case when roots of elements of X = {α, β} are conjugates: by Corollary 3 the only possible bi-infinite word is w = α Z = β Z . So we need to consider only the case when the roots of α and β are not conjugates.

In this case, by Theorem 2, we know that an X-ambiguous bi-infinite word must be of the form (αβ n ) Z or (α n β) Z . Moreover, since w has two X-factorizations, the word αβ n or the word α n β cannot be primitive, by Lemma 2.

As we stated in the previous section, if α and β are conjugates, then the words αβ n and α n β are primitive for all n. Now, we shall show a similar result for α, β being non-conjugates, i.e., we shall show that at most one word in the set of words {αβ n ; n ≥ 1} ∪ {α m β; m ≥ 1} is not primitive. By this result, we have that also in the last case there is at most one X-ambiguous bi-infinite word. We need two lemmas.

Lemma 8. Let α, β be primitive and not conjugates. Then for any n, m ≥ 0 with n = m, at most one of the words αβ n and αβ m is not primitive.

Proof. Assume the contrary that both αβ n , αβ m are non-primitive with m < n. For m = 0 the claim is obvious, so we can assume m ≥ 1, and so n ≥ 2. We can write

αβ n = s i αβ m = t j
and therefore also

s i = t j β n-m , (1)
where s,t are primitive and i, j ≥ 2. Now if nm ≥ 2, then, by Lemma 4, s, t and β are powers of a common word, and so are α and β, which is a contradiction. So we can assume m = n -1, and thus equation (1) simplifies to s i = t j β. loss of generality, we can assume that |t| > |β|. We have the situation depicted in Figure 13, where Since u 2 α ′ = α ′ u 1 , Lemma 3 gives us

β = u 1 u 2 with |u 1 | = |u 2 | = 1 2 |β| and α = α ′ u 1 = u 2 α ′ . ✑ α ′ u 1 u 2 α ′ u 1 u 2 u 1 u 2 u 2 . . .
u 2 = (pq) k u 1 = (qp) k α ′ = p(qp) l      and therefore α = p(qp) k+l β = (qp) k (pq) k ,
where k ≥ 1, l ≥ 0 and pq is primitive. We may assume p, q = 1. Now considering the last occurrence of s in Figure 13 we can, by (6), write s = s ′ β = s ′ (qp) k (pq) k . We also have

|s| = |α| + n|β| -(i -1)|s| ≤ |α| + n|β| -|s| (6) < |α| + |β| , which yields s ′ (qp) k (pq) k r = sr = αβ = p(qp) 2k+l w (pq) k ,
for some r = 1. The first occurrence of qp in s after s ′ must match with qp in w, otherwise qp is not primitive. But then, since r = 1, the first occurrence of pq in s after s ′ (qp) k matches with some qp in w, so we have pq = qp, which is again a contradiction with the primitiveness of pq.

As a consequence of Lemmas 8 and 9 we have the following corollary:

Corollary 4. Let α, β be primitive and not conjugates. Then at most one word in the set {αβ n ; n ≥ 1} ∪ {α m β; m ≥ 1} is not primitive.

Finally, we can state the result of this section, which is a consequence of Corollary 4 and the considerations in the beginning of this section. Theorem 3. Consider set X = {α, β} with α, β ∈ Σ + . There is at most one X-ambiguous bi-infinite word over Σ.

The Existence of the Bi-infinite Word

We consider again only the two-element case in this section. In the previous section we proved that there is at most one X-ambiguous bi-infinite word. It is natural to ask when such a word exists. It is easy to see that there are sets X for which there is no X-ambiguous bi-infinite word. For example, take a set which implies u 1 = u 3 u 2 v = u 3 (u 2 u 3 ) m-1 pq. We obtained exactly solution (10), which completes the proof.

The following lemma gives us the characterization of solutions of equation ( 8) and hence also of sets X allowing an X-ambiguous bi-infinite word in case (iii).

Lemma 12. Assume that α and β do not commute. All solutions of the equation

αβ n = s i satisfying n ≥ 1, i ≥ 2 are β = p(qp) j , s = qpβ n-1 , α = s i-1 β -1 pq , (11)
where p, q ∈ Σ + , j ≥ 0 and j < i if n = 1.

Proof. It is easy to check that ( 11) is a solution of equation ( 8). For the converse implication we analyze 3 cases. Case 1. Assume that |s| > |β n |. Then we have α = s i-1 q and s = qβ n for some q = 1. This is solution (11) for j = 0, p = β. Directly from the figure we can write β = p(qp) j , s = qp , α = q(pq) i-j-1 , where p, q = 1 and j < i. Since s i-1 β -1 pq = (qp) i-1 p(qp) j -1 pq = (qp) i-j-1 q = α , we have solution (11) for n = 1.

✓ u 1 u 2 u 3 . . . According to this figure we can write β = u 2 u 3 , α = s i-2 u 1 and u 1 u 2 = s = u 3 β n-1 = u 3 (u 2 u 3 ) n-1 , which is equation ( 9). Now, Lemma 11 implies β = u 2 u 3 = p(qp) k+1 = p(qp) j , for j = k + 1, s = u 1 u 2 = u 3 (u 2 u 3 ) n-2 pqp(qp) k = qpβ n-2 β = qpβ n-1 , and α = s i-2 u 1 = s i-2 u 3 (u 2 u 3 ) n-2 pq = s i-2 qpβ n-2 ββ -1 pq = s i-1 β -1 pq .

This is exactly solution (11).

The following theorem summarizes the previous results.

Theorem 4. Consider set X ⊆ Σ + with card(X) = 2. There exists an X-ambiguous bi-infinite word if and only if one of the following conditions is satisfied:

(i) X = {p n , p m }, where p ∈ Σ + and n, m ≥ 1, (ii) X = {(pq) n , (qp) m }, where p, q ∈ Σ + and n, m ≥ 1, (iii) X = {α, β}, where β = p(qp) j , α = (qpβ n-1 ) i-1 β -1 pq , for p, q ∈ Σ + , n ≥ 1, i ≥ 2, j ≥ 0 and if n = 1, then j < i.

Notice, that in the last case of Theorem 4 the occurrence of β -1 can be eliminated, but we prefer this form for its simplicity. This theorem shows that the family of the two-element sets X, such that there exists an X-ambiguous bi-infinite word, is parameterizable. Such a characterization does not help us, if we want to decide whether there is an X-ambiguous bi-infinite word for the certain set X, but we can use it to generate all such sets.

Conclusions and Open Problems

Our Theorem 2 is closely related to the main result of [lRlR], where it is characterized when a finite word can have two disjoint X-interpretations for a binary set X. Our result could be concluded, with some effort, from the considerations in this paper. However, our proof is simpler, due to the use of the graph lemma (Lemma 5), and moreover directly formulated to obtain a defect type of theorems.

We pose an open problem asking whether Theorem 2 can be extended to arbitrary sets.

Example 1 .

 1 Let X = {a, bab, baab}. The word (baa) Z has two different X-factorizations, namely the ones depicted as: ✁ . . . b a a b a a b . . . They are clearly shiftequivalent. On the other hand the word w = . . . bababaabaab • • • = N (ba)b(aab) N also has two different X-factorizations, which, however, are not shiftequivalent: ✂ . . . a b a b a b a b a a b a a b a a b a a . . . Clearly, in both of the above cases the two factorizations are disjoint.

Lemma 1 .

 1 (Fine and Wilf) Let u, v ∈ Σ + . If the words u N and v N have a common prefix of length at least |u| + |v|gcd(|u|, |v|), then u and v are powers of a common word. Lemma 2. No primitive word r satisfies a relation rr = srp with s = 1 and p = 1.

Fig. 1 .

 1 Fig. 1. An illustration of the situation considered in Lemma 6.

Fig. 3 .

 3 Fig. 3. An illustration of the situation when F 2 = α Z and F 1 contains α.

Fig. 5 .

 5 Fig. 5. The second case of 3 cases shown in Figure 4.

Fig. 6 .

 6 Fig. 6. The situation when sequences of β's exceed α's on both sides.

Fig. 7 .

 7 Fig. 7. 3 possibilities where the black point can occur in β.

Fig. 8 .

 8 Fig. 8. The situation around the black point in case (4).

  where |v 1 | = |v 2 | and |v 3 | = |v 4 |. There are again two possibilities.

Fig. 9 .

 9 Fig. 9. The situation in Case 3.

Fig. 10 .

 10 Fig. 10. The case z R = α.

Fig. 11 .

 11 Fig. 11. The case z R = β. So it remains the case z R = β. The situation is drawn in Figure 11. Since β is not primitive z must be α. It is obvious that |t| = |v 2 | = |v 1 |, which implies t = v 1 . We know that β ends with v 2 v 4 , and hence there is v 2 v 4 at the end of the last upper β in Figure 11, and v 4 at the end of the last lower β. But since |v 2 v 4 | = |v 4 t| we have the equation v 2 v 4 = v 4 t = v 4 v 1 . According to Figure 9 and Figure 11 we have the following system of equations with unknowns Y = {β, v 1 , v 2 , v 3 , v 4 }:

Fig. 12 .

 12 Fig. 12. The situation when α and β are conjugates and the lower factorization contains both α and β.

  Now if |s| ≤ (n -1)|β|, then |β| + |s| ≤ |β n |, so that, by the equation αβ n = s i , words N β and N s have a common suffix of a length at least |β| + |s|. Applying Lemma 1 we conclude that words s and β are powers of a common word, which again yields to a contradiction. So we have |s| > (n -1)|β| ≥ |β| , and similarly, (2) |t| > (m -1)|β| = (n -2)|β| .(3) Inequality (2) together with equation (1) implies|t j | = i|s|-|β| > (i-1)|s|. So, if i ≥ 3 we have |t j | > 2|s|,and since j ≥ 2 also that |t j | > |s| + |t|. Then equation (1) and Lemma 1 implies that s and t commutes which leads to a contradiction. Hence we can assume i = 2.

Fig. 13 .

 13 Fig. 13. The situation when α 2 β = t 2 and αβ n = s i with n ≥ 2.

Fig. 14 .

 14 Fig. 14. The situation when |s| < |β n | and n = 1.

Fig. 15 .

 15 Fig. 15. The situation when |s| < |β n | and n ≥ 2.

Example 3 .

 3 Let us choose in (11) p = a, q = b, n = 2, i = 2 and j = 2. We haveβ = ababa , s = baababa , α = baab .The bi-infinite word (αβ 2 ) Z has two different X-factorizations: ✔ . . . b a a b a b a b a a b a b a . . .

Acknowledgment

The author is grateful to Professor Juhani Karhumäki and to Wojciech Plandowski for useful discussions.

under Grant No. 14047. 1365-8050 c 2001 Maison de l'

Ján Maňuch

If |t| + |β| ≤ |s|, then using equation (1) we derive inequality |t j | ≥ (i -1)|s| + |t| and, by Lemma 1, we have a contradiction again. Hence we may assume that |t| + |β| > |s| .

(4)

Now consider the case n ≥ 3. We have

> |s|

(1)

= j|t| + |β| -|s| The last case we have to analyze is n = 2. Now if |t| ≥ |β|, then, by (5), we have 2|t| ≥ |t| + |β| > ( j -1)|t| and j = 2, which is again the previous case. So consider the case |t| < |β| < |s|, where the second inequality comes from (2). By the equations αβ = t j and αβ 2 = s 2 we can write β = xt and s = yt for some x, y = 1. Hence equation (1) leads to ytyt = t j β. We have |yt| = |s| = |t j | + |β| -|s| < |t j |, so that we can write ytz = t j , z = 1. Now either t is not primitive by Lemma 2, or t matches with some t in t j , but then we have y = t k , and hence also s = t k+1 , so that words t, s are powers of a common word. In both cases we arrive to a contradiction. Lemma 9. Let α, β be primitive and not conjugates. Then for any n, m ≥ 0 with (n, m) = (1, 1), at most one of the words αβ n and α m β is not primitive.

Proof. Cases m = 0 and n = 0 are trivial. The case m = 1 is a special case of Lemma 8. In the case n = 1 we can exchange α and β and take reverses of words, and we are again in the case m = 1. We shall use this reasoning again later, so let us call it the reverse argument. Consider n, m ≥ 2 and assume the contrary that αβ n = s i , α m β = t j , where i, j ≥ 2 and s,t are primitive. Using the same argument as in the proof of the previous lemma we have

which implies that

So we have either i = n = 2, or j = m = 2. Now by the reverse argument the first case is equivalent to the second one, so it is enough to consider only the case j = m = 2. If |t| < |β|, then, by ( 6), we obtain

Together with (7) we have (i -1)(n -1) -1 < 1, which implies that also i = n = 2. Now again we can apply the reverse argument and the inequality |s| > |α| transforms to the inequality |t| > |β|. So, without X = Σ = {a, b}. We say that a family of sets of words with the same cardinality t is parameterizable if it can be described in terms of t formulas with word and integer parameters. We shall prove now that the family of binary sets X for which there exists an X-ambiguous bi-infinite word is parameterizable.

In case (i) of Theorem 2, when words of X are powers of a common word t, the bi-infinite word t Z has infinitely many X-factorizations. In particular, in the case there is always an X-ambiguous bi-infinite word. In case (ii), when roots of words in X = {α, β} are conjugates, the bi-infinite word α Z = β Z has exactly two different X-factorizations, so it is X-ambiguous.

Consider now the last case (iii), and the set X = {α, β}. By Theorem 2, an X-ambiguous bi-infinite word is of the form (αβ n ) Z , where αβ n is not primitive, or (α n β) Z , where α n β is not primitive, i.e., there are n ≥ 1, i ≥ 2 and s ∈ Σ + such that

Conversely, if for some n ≥ 1 and i ≥ 2 at least one of equations ( 8) has a solution, then clearly the bi-infinite word (αβ n ) Z (resp. (α n β) Z ) has exactly i shiftequivalent, but different X-factorizations. We formalize this as a lemma.

Lemma 10. Let X = {α, β} ⊆ Σ + be a set of two non-commuting words such that their roots are not conjugates. Then there is an X-ambiguous bi-infinite word if and only if one of the equations αβ n = s i and α n β = s i , with n ≥ 1, i ≥ 2, has a solution.

We shall also give a characterization of the solutions of the equations ( 8). We need the following lemma.

Lemma 11. The all nonperiodic solutions of the equation

are of the form u 3 = qp ,

where p, q ∈ Σ + , k ≥ 0.

Proof. It is easy to check that ( 10) is really a solution of equation ( 9). Now we shall prove that if equation (9) has a nonperiodic solution, then it is of the form (10). We proceed by induction. Consider first the case m = 1. We have the equation u 1 u 2 = u 3 u 2 u 3 . It is obvious that |u 1 | > |u 3 |, so we can write u 1 = u 3 t. The equation transforms into tu 2 = u 2 u 3 , which has, by Lemma 3, the only solutions t = pq, u 3 = qp and u 2 = p(qp) k , k ≥ 0. This implies that u 1 = qppq, so we have a solution of the form (10) for m = 1.

Consider now equation ( 9) with m ≥ 2. Again we have |u 1 | > |u 3 |, so we can substitute u 1 = u 3 t and equation (9

This implies that u = u 3 = 1, which leads to a periodic solution. Hence, consider the case l = 0. We have u 2 = u, u 1 = u 3 u 2 v and vu 2 = u 3 (u 2 u 3 ) m-1 . Now we can apply induction hypothesis on the last equation and we obtain that all noncommuting solutions are of the form

Open problem 1. Let X ⊆ Σ + be a finite set such that r c (X) = card(X). Does there exist a bi-infinite word w having two X-factorizations F 1 and F 2 satisfying:

(i) both F 1 and F 2 contain all elements of X, and (ii) F 1 and F 2 are not shiftequivalent?

Observe here that in the case of a two-element set X the answer to this problem is negative, but without the assumption that all elements of X occur in both factorizations the answer is trivially positive.

The answer is also positive if the condition r c (X) = card(X) is replaced by a weaker one involving the free rank: r f (X) = card(X). This is verified by Example 1.

Another open problem asks whether Corollary 3 can be generalized for an arbitrary finite X.

Open problem 2. Let X ⊆ Σ + be a finite set satisfying r c (X) = card(X). Suppose that primitive roots of all elements of X are conjugates and that a bi-infinite word w has at least two different X-factorizations. Are all X-factorizations of w of the form α Z , where α ∈ X?

Example 4. The answer to the above question is negative if we omit the assumption r c (X) = card(X). Indeed, let X = {α 1 , α 2 , α 3 }, where α 1 = baa, α 2 = aba, α 3 = aab. Then clearly α 1 ∼ α 2 ∼ α 3 and the word (abaaab) Z has two different, and even non-shiftequivalent, X-factorizations: (α 1 α 2 ) Z and (α 2 α 3 ) Z .


Pascal Koiran
email: pascal.koiran@ens-lyon.fr

The Topological Entropy of Iterated Piecewise Affine Maps is Uncomputable

Keywords: topological entropy, piecewise affine functions, saturated linear functions, cellular automata

We show that it is impossible to compute (or even to approximate) the topological entropy of a continuous piecewise affine function in dimension four. The same result holds for saturated linear functions in unbounded dimension. We ask whether the topological entropy of a piecewise affine function is always a computable real number, and conversely whether every non-negative computable real number can be obtained as the topological entropy of a piecewise affine function. It seems that these two questions are also open for cellular automata.

Introduction

There is an active line of research in which dynamical systems are studied from an effective point of view. Here one main goal is to clarify the boundary between decidable and undecidable properties of dynamical systems. Cellular automata and iterated piecewise-affine maps are two classes of systems for which this endeavour has been particularly successful. The present paper is devoted to iterated piecewise-affine continuous maps. We show that it is undecidable whether the topological entropy of such a function defined on the fourdimensional cube [-1, 1] 4 is equal to zero (precise definitions are given in section 2). A similar result was obtained several years ago for one-dimensional cellular automata [START_REF] Hurd | The topological entropy of cellular automata is uncomputable[END_REF] by a reduction from the nilpotency problem, which was proved undecidable in [START_REF] Kari | The nilpotency problem of one-dimensional cellular automata[END_REF]. We also use a reduction from the nilpotency problem, albeit of piecewise-affine maps instead of cellular automata. The undecidability of this problem was only established recently in [START_REF] Blondel | The stability of saturated linear dynamical systems is undecidable[END_REF]. As in [START_REF] Hurd | The topological entropy of cellular automata is uncomputable[END_REF] it follows from the proof that the topological entropy cannot be computed, even approximately. We also give an undecidability result for saturated linear systems, which are a restricted class of iterated piecewise-affine maps. These systems have been of interest in control theory, see for instance [START_REF] Sontag | From linear to nonlinear: some complexity comparisons[END_REF]. Finally we show that there exists a dimension n and nilpotent saturated linear maps f : R n → R n such that f k (the k-th iterate of f ) is not identically zero, where k is an arbitrarily large integer. This clarifies an observation of [START_REF] Blondel | The stability of saturated linear dynamical systems is undecidable[END_REF]. It is however still unknown whether there exists n such that the nilpotency problem for saturated linear functions in dimension n is undecidable.

We conclude this introduction with an open problem: is the topological entropy of a piecewise-affine map always a computable real number? The concept of computable real number is explained in many texts on recursive function theory or recursive analysis, see e.g. [START_REF] Ker | Complexity Theory of Real Functions[END_REF][START_REF] Weihrauch | Computability[END_REF]. Here as elsewhere we assume that the piecewise-affine map has only rational 1365-8050 c 2001 Maison de l'Informatique et des Mathématiques Discrètes (MIMD), Paris, France coefficients, see section 2.2. Our undecidability result does not seem to provide an answer to this question. It is however clear from the definition of topological entropy that this number is always in the arithmetical hierarchy of real numbers studied in [START_REF] Zheng | The arithmetical hierarchy of real numbers[END_REF]. Conversely, one can ask whether every computable real number can be obtained as the topological entropy of an iterated piecewise-affine map. These two questions also make sense for cellular automata, and it seems that they have not been addressed so far.

Dynamical Systems

We consider dynamical systems defined by iteration of a map f : X → X. A trajectory of such a system is a sequence (x t ) t∈N of points of X such that x t+1 = f (x t ) for all t ∈ N. We are mainly interested in the case where f is piecewise affine and X is the

d-dimensional cube [-1, 1] d .

The Topological Entropy

Let (X, d) be a compact metric space and f : X → X an arbitrary (possibly discontinuous) map. From d and f we can construct a family (d n ) of distance functions as follows:

d n (x, y) = max 0≤i≤n d( f i (x), f i (y)).
We say that a subset F of X is an ε-spanning set for (X, d n ) if for all x ∈ X there exists y ∈ F such that d n (x, y) ≤ ε. There is a dual notion of ε-separated set: this is a subset F of X such d n (x, y) > ε for any distinct points x and y of F.

We denote by r n (ε) the smallest cardinality of any ε-spanning set of (X, d n ), and by s n (ε) the largest cardinality of any ε-separated set. We also write r n (ε, f ) and s n (ε, f ) when f is not clear from the context. It follows from the compactness of X that r n (ε) and s n (ε) are always finite.

One can show that the two limits exist and are equal (they may be infinite). This common limit is called the topological entropy of f , and is denoted h( f ). For more details we refer the reader to [START_REF] Mañé | Ergodic Theory and Differentiable Dynamics[END_REF] and [START_REF] Walters | An Introduction to Ergodic Theory[END_REF] (the latter reference defines the topological entropy only for uniformly continuous maps). Consider for instance the case where f is a nilpotent map. This means that there exists an integer m such that f m (X) = {0}, where 0 is a distinguished point of X. Then h( f ) = 0 since r n (ε) is bounded independently from n by r m (ε).

As a second example, consider the "tent map" φ :

[0, 1] → [0, 1] defined by: φ(x) = 2x for x ∈ [0, 1/2] and φ(x) = 2(1 -x) for x ∈ [1/2, 1].
The n-th iterate of φ is made of 2 n "laps" (monotone pieces). This implies that h(φ) = ln 2 [START_REF] Misiurewicz | Entropy of piecewise monotone mappings[END_REF] (this can also be checked directly from the definition of topological entropy). Here as in the remainder of the paper, the topological entropy is computed with respect to the Euclidean distance. The example of the tent map will be used later. In fact we will only need to know that the topological entropy of φ is nonzero.

Piecewise-affine maps

A function f : R p → R q is piecewise affine if its graph is a semilinear subset of R p ×R q (i.e., a boolean combination of halfspaces). We will assume that the corresponding halfspaces are defined by affine inequalities with rational coefficients only. Also we will work only with continuous piecewise affine maps.

Let σ : R → R be the piecewise affine map such that σ(x) = x for x ∈ [-1, 1], σ(x) = 1 for x ≥ 1, and σ(x) = -1 for x ≤ -1. A saturated linear map is a piecewise affine function f : R p → R q of the form f (x) = σ(Ax). Here σ is applied componentwise. Naturally, we say that A is the matrix associated to f . Theorem 3, our undecidability result for saturated linear maps, is obtained by a reduction from the problem of Theorem 2: deciding whether the entropy of a continuous piecewise affine map is equal to zero. In order to obtain this reduction, we find it convenient to prove Theorem 2 for a restricted class of continuous piecewise affine maps: the so-called σ * 0functions. We recall from [START_REF] Blondel | The stability of saturated linear dynamical systems is undecidable[END_REF] that a σ * 0 -function of depth d is a composition of d saturated linear functions. Note that f : R p → R q is a σ * 0 -function iff each of its q components is a σ * 0 -function (for the if part, note that we may assume that the q components have the same depth since σ(g) = g for any σ * 0 -function g : R p → R).

Undecidable Properties

Our undecidability results are based on reductions from the "hyperplane problem" [START_REF] Blondel | The stability of saturated linear dynamical systems is undecidable[END_REF].

Theorem 1 (Theorem 7 of [1])

The following decision problem is undecidable.

• Instance: three σ * 0 -functions f , g, Z : R 3 → R. • Question:
does there exist a trajectory of the system (x t+1 , y t+1 ) = ( f (x t , y t , 1), g(x t , y t , 1)) which satisfies Z(x t , y t , 1) = 0 for all t?

Let us recall some constructions from [START_REF] Blondel | The stability of saturated linear dynamical systems is undecidable[END_REF]. Sel : R 2 → R is a σ * 0 -function which is zero in a neighbourhood of 0, and satisfies

1. Sel(1, e) = e 2. Sel(0, e) = 0 for all e ∈ [-1, 1].
In the same paper we constructed a σ * 0 -function Stab : R 2 → R which is zero in a neighbourhood of 0, and satisfies the following property. For all z 0 ∈ R and for all functions e : N → R, the sequence z t+1 = Stab(z t , e t ) falls into one of the following three mutually exclusive cases:

1. The sequence z t , t ≥ 1 is constant, always equal to 1. This case happens only when σ(z 0 ) = 1 and when e t = 0 for all t.

2. The sequence z t , t ≥ 1 is constant, always equal to -1. This case happens only when σ(z 0 ) = -1 and when e t = 0 for all t.

3. The sequence z t is eventually null: there exists t 0 with z t = 0 for all t ≥ t 0 .

It is shown in [START_REF] Blondel | The stability of saturated linear dynamical systems is undecidable[END_REF] that one may take Sel(z, e) = σ(2h(3z/4 + e/4)h(z)) where h denotes the function h(x) = σ(2σ(x) -σ(2x)). For Stab one may take Stab(z, e) = h(σ(σ(z)) -Abs(z, e)/2), where Abs(z, e) = σ(σ(ez) -σ(e + z) + 2σ(z)).

Theorem 2 It is undecidable whether the topological entropy of a given σ

* 0 -function F : [-1, 1] 4 → [-1, 1] 4 is equal to zero.
This problem remains unsolvable even if we are promised that F satisfies the following condition: if h(F) = 0 then F is nilpotent.

Proof. We reduce the problem of Theorem 1 to this problem. let f , g, Z : R 3 → R be three σ * 0 -functions. Consider the following four-dimensional system X t+1 = F(X t ):

w t+1 = Sel(z t , ψ(w t , z t )) x t+1 = Sel(z t , f (x t , y t , z t )) y t+1 = Sel(z t , g(x t , y t , z t )) z t+1 = Stab(z t , Z(x t , y t , z t ))
Here ψ is the σ * 0 -function ψ(w, z) = σ((σ(4w-z)+σ(3z-4w))/2). For w ∈ [0, 1], note that ψ(w, 1) is equal to φ(w), the tent map from section 2.1. Note also that F is a σ * 0 -function since its four components are σ * 0 -functions. We claim that the four following properties are equivalent.

(i) No trajectory of the system (x t+1 , y t+1 ) = ( f (x t , y t , 1), g(x t , y t , 1)) satisfies Z(x t , y t , 1) = 0 for all t.

(ii) F is mortal.

(iii) F is nilpotent.

(iv) The topological entropy of F is equal to zero.

Theorem 2 then follows immediately from Theorem 1 and the equivalence of (i), (iii) and (iv). Assume first that (i) holds. To show that F is mortal, we only need to consider trajectories with z 1 ∈ [0, 1] since F is an odd function. If z t is always constant and equal to 1 then by construction of Sel and Stab, (x t , y t ) is a trajectory of the system (x t+1 , y t+1 ) = ( f (x t , y t , 1), g(x t , y t , 1)) which satisfies Z(x t , y t , 1) = 0 for all t. This is impossible by hypothesis. By construction of Stab, z t must therefore be eventually null. By construction of Sel, this implies that w t , x t and y t are also eventually null: the system's trajectory is indeed mortal.

Since Sel and Stab are zero in a neighbourhood of zero, the same is true of F: there exists an open neighbourhood U of 0 such that F(U) = {0}. The implication from mortality to nilpotency then follows by compactness: if

F is mortal then [-1, 1] 4 = n≥0 F -n (U). Hence there is a finite cover of the form [-1, 1] 4 = N n=0 F -n (U), which implies F N+1 ([-1, 1] 4 ) = {0}.
As pointed out in section 2.1, (iii) implies (iv). Finally, in order to show that (iv) implies (i) we show that ¬ (i) implies ¬ (iv). Consider a trajectory of the system (x t+1 , y t+1 ) = ( f (x t , y t , 1), g(x t , y t , 1)) which satisfies Z(x t , y t , 1) = 0 for all t. For any initial value w 0 ∈ [0, 1] we obtain a trajectory of F which satisfies w t+1 = φ(w t ) and z t = 1 for all t. This implies that s t (ε, F) ≥ s t (ε, φ) for all t, ε > 0, so that h(F) ≥ h(φ) > 0. ✷ Note that the piecewise-affine function F constructed in this proof either satisfies h(F) = 0 or h(F) ≥ ln 2. This implies that for ε < ln 2 no algorithm can approximate the topological entropy of a piecewise-affine with an absolute error bounded by ε. A variation on this construction would show just as in [START_REF] Hurd | The topological entropy of cellular automata is uncomputable[END_REF] that the topological entropy cannot be approximated up to ε, no matter how large ε is.

Theorem 3 It is undecidable whether the topological entropy of a given saturated linear function is equal to zero.

This problem remains unsolvable even if we are promised that the saturated linear function is nilpotent if its topological entropy is equal to zero.

Proof. We reduce the problem of Theorem 2 to this problem. Let F : [-1, 1] 4 → [-1, 1] 4 be a σ * 0 -function. To this function we can associate a saturated linear function F ′ as in [START_REF] Blondel | The stability of saturated linear dynamical systems is undecidable[END_REF]. This is done as follows. Assume that F is of the form

f k • f k-1 • . . . • f 1 for some σ 0 -functions f j (x) = σ(A j x),
A =        0 0 . . . 0 A k A 1 0 . . . 0 0 0 A 2 . . . 0 0 . . . . . . 0 0 0 0 . . . A k-1 0        . (1)
As pointed out in [START_REF] Blondel | The stability of saturated linear dynamical systems is undecidable[END_REF], it is clear that if F m ≡ 0 for some integer m then F ′ km ≡ 0, so that h(F ′ ) = 0. Conversely, consider a trajectory X t+1 = F(X t ) of F, and a trajectory X ′ t+1 = F ′ (X ′ t ) such that the first d 0 components of X ′ 0 are equal to X 0 . The first d 0 components of X ′ kt are then equal to X t for all t ≥ 0. This implies that s tk (ε, F ′ ) ≥ s t (ε, F) so that h(F ′ ) ≥ h(F)/k.

We can now conclude. Assume that we are promised that F is nilpotent if h(F) = 0. We have shown that:

(i) if h(F) = 0 then h(F ′ ) = 0 and F ′ is nilpotent. (ii) if h(F) > 0 then h(F ′ ) > 0.
The problem of Theorem 3 is therefore undecidable. ✷

Nilpotent Systems in Fixed Dimension

It was pointed out in [START_REF] Blondel | The stability of saturated linear dynamical systems is undecidable[END_REF] that our undecidability results have "purely mathematical" consequences. For instance, there is no recursive function s(n) such that all saturated linear maps f : R n → R n satisfy f s(n) = 0. Note in contrast that the bound s(n) = n is valid for nilpotent linear maps. The existence of such a bound for saturated linear maps would imply the decidability of their nilpotency problem, but this problem is undecidable [START_REF] Blondel | The stability of saturated linear dynamical systems is undecidable[END_REF]. This observation leaves us with the following alternative: (i) either there is for all n a finite bound s(n) such that all saturated linear maps f : R n → R n satisfy f s(n) = 0 (and in this case s must be a very fast growing function).

(ii) or for some integer n no finite bound exists.

We now show that the second branch of the alternative is the correct one.

Proposition 1 There exists an integer n such that for any integer k there exists a nilpotent saturated linear map f : R n → R n with f k = 0.

This follows from Lemma 1 below (note again the contrast with the case of linear maps).

Lemma 1 Let Nil n be the set of matrices of nilpotent saturated linear maps in dimension

n. There exists an integer n such that Nil n is not a closed subset of R n 2 .

Proof. Consider the one dimensional system z t+1 = F ε (z t ), where F ε is the σ * 0 -function z t → Stab(z t , εz t ). Here ε is a real parameter. For ε = 0 the system is not nilpotent since 1 is a fixed point. For ε = 0 the system is mortal by the third property of Stab. Since F ε is identically zero in a neighborhood of zero, this implies by compactness (as in the proof of Theorem 3) that F ε is in fact nilpotent.

Consider now as in (1) the matrix A ε of the saturated linear map F ′ ε which is associated to F ε . This σ * 0 -function is nilpotent if and only if F ′ ε is nilpotent, and as a consequence A ε is in Nil n if and only if ε = 0. ✷ Proof of Theorem 1. Let Nil n,k be the set of matrices of saturated linear maps f : R n → R n such that f k = 0. By continuity each Nil n,k is a closed subset of R n 2 , but we have just seen that Nil = ∪ k≥1 Nil n,k is not closed. We conclude that Nil n \ Nil n,k = / 0 for all k. ✷ It follows from the explicit formula for Stab given before Theorem 2 that one may take n = 9 in Lemma 1 and Proposition 1.

  where f j : R d j-1 → R d j with d 0 , d 1 , . . . , d k ∈ N, and d 0 = d k = 4. Let d = d 0 +d 1 +• • •+d k , and consider the saturated linear function F ′ : R d → R d defined by F ′ (x) = σ(Ax) where