Fabien Durand

A generalization of Cobham's Theorem

If a non-periodic sequence X is the image by a morphism of a fixed point of both a primitive substitution σ and a primitive substitution τ , then the dominant eigenvalues of the matrices of σ and of τ are multiplicatively dependent. This is the way we propose to generalize Cobham's Theorem.

Introduction

In 1969 A. Cobham [START_REF] Cobham | On the base-dependence of sets of numbers recognizable by finite automata[END_REF] proved the following result (latter called Cobham's Theorem): Let p and q be multiplicatively independent positive integers and E a subset of IN. The set E is recognizable by both a p-automaton and a q-automaton if and only if E is ultimately periodic.

Later A. Cobham [START_REF] Cobham | Uniform tag sequences[END_REF] showed that a subset E of IN is p-recognizable for some integer p if and only if its characteristic sequence (x n ) n∈IN (i.e. x n = 1 if n belongs to E and 0 otherwise) is p-substitutive (i.e. the image by a letter to letter morphism of a fixed point of a substitution of constant length p). There are several equivalent definitions of p-substitutive sequences, see for instance [START_REF] Cobham | Uniform tag sequences[END_REF], [START_REF] Christol | Suites Algébriques et Substitutions[END_REF] and [START_REF] Allouche | q-regular sequences and other generalizations of qautomatic sequences[END_REF]. Hence Cobham's Theorem can be formulated as follows: Let p and q be multiplicatively independent positive integers and X be a sequence on a finite alphabet. The sequence X is both p-substitutive and q-substitutive if and only if it is ultimately periodic.

A classical result concerning matrices asserts that a square matrix with non-negative coefficients always has a real eigenvalue which is larger (not 1 necessarily strictly) than the modulus of all other eigenvalues of M; moreover such an eigenvalue is a Perron number (see for instance [START_REF] Lind | An introduction to symbolic dynamics and coding[END_REF]). We say that it is the dominant eigenvalue of M.

One can check that the dominant eigenvalue of the matrix of a substitution of constant length p is p. To extend the notion of p-substitutive sequences we will say that a sequence is α-substitutive if and only if it is the image by a letter to letter morphism of a fixed point of a substitution σ such that α is the dominant eigenvalue of the matrix of σ.

Consequently a natural generalization of Cobham 's Theorem is:

Let α and β be two multiplicatively independent Perron numbers and X a sequence on a finite alphabet. The sequence X is both α-substitutive and β-substitutive if and only if it is ultimately periodic.

An answer to this conjecture has been given by S. Fabre [START_REF] Fabre | Substitutions et indépendance des systèmes de numération[END_REF][START_REF] Fabre | Une généralisation du Théorème de Cobham[END_REF][START_REF] Fabre | Substitutions et β-systèmes de numération[END_REF] in the case where α is a pisot number and β a positive integer. Recently, using the formalism of the first order logic A. Bès [START_REF] Bès | An extension of Cobham-Semënov Theorem[END_REF] and I. Fagnot [START_REF] Fagnot | Cobham's Theorem and automaticity in non-standard bases[END_REF] obtained a partial answer in the case where α and β are pisot numbers.

In this paper we give a positive answer to this conjecture in the case where the substitutions are primitive without any assumption concerning the eigenvalues α and β:

Let α and β be two multiplicatively independent Perron numbers and X a sequence on a finite alphabet. If a sequence X is both α-substitutive and β-substitutive then X is periodic.

There are other ways to generalize Cobham's Theorem, some of them can be found in [START_REF] Bès | An extension of Cobham-Semënov Theorem[END_REF], [START_REF] Fabre | Une généralisation du Théorème de Cobham[END_REF], [START_REF] Fagnot | Cobham's Theorem and automaticity in non-standard bases[END_REF], [START_REF] Michaux | Presburger arithmetic and recognizability of natural numbers by automata: new proofs of Cobham's and Semenov's Theorems[END_REF] and [START_REF] Semenov | The Presburger nature of predicates that are regular in two number systems[END_REF]. Related works can be found in [START_REF] Bruyère | Logic and precognizable sets of integers[END_REF], [START_REF] Hansel | A propos d'un théorème de Cobham[END_REF] or [START_REF] Michaux | Cobham's Theorem seen through Büchi Theorem[END_REF]. Section 2 of this paper contains the basic definitions we need. In Section 3 we define the main notion of this paper, the return word, which was first introduced in [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF]. We review some properties of return words obtained in [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF]. Section 4 is an intermediate step to prove the main result where we establish helpful morphism relations. Section 5 is split into two subsections. In the first one we prove a result (Theorem 13) stronger than our main theorem though only valid for fixed points:

If two primitive substitutions have the same non-periodic fixed point, then they have some powers which have the same eigenvalues, except perhaps 0 and the roots of the unity.

In the second one we prove the main theorem. An example is used to show that for substitutive primitive sequences we cannot have a better result. The aim of Section 6 is to show that there is more than only relations between eigenvalues. Primitive substitutions sharing a same fixed point have some powers which coincide on some sets of return words.

Definition and terminology

Words and sequences

We call alphabet a finite set of elements called letters. Let A be an alphabet, a word on A is an element of the free monoid on A, denoted by A * , i.e. a finite (possibly empty) sequence of letters. Let x = x 0 x 1 • • • x n-1 be a word, its length is n and is denoted by |x|. The empty-word is denoted by ǫ, |ǫ| = 0. The set of non-empty words on A is denoted by A + . The elements of

A IN are called sequences. If X = X 0 X 1 • • • is a sequence (with X i ∈ A, i ∈ IN),
and l, k are two non-negative integers, with l ≥ k, we denote the word X k X k+1 • • • X l by X [k,l] and we say that X [k,l] is a factor of X. If k = 0, we say that X [0,l] is a prefix of X and we write X [0,l] ≺ X. The set of factors of length n of X is written L n (X), and the set of factors of X, or language of X, is represented by L(X). If u is a factor of X, we will call occurrence of u in X every integer i such that X [i,i+|u|-1] = u. When X is a word, we use the same terminology with the similar definitions. Let u and v be two words, we denote by L u (v) the number of occurrences of u in v. A word u is a suffix of the word v if v = xu for some x belonging to A * .

The sequence X is ultimately periodic if there exist a word u and a nonempty word v such that X = uv ω , where v ω is the infinite concatenation of the word v. Otherwise we say that X is non-periodic. It is periodic if u is the empty-word.

A sequence X is uniformly recurrent if for each factor u the greatest difference of two successive occurrences of u is bounded.

Morphisms and matrices

Let A, B and C be three alphabets. A morphism τ is a map from A to B * . Such a map induces by concatenation a map from A * to B * . If τ (A) is included in B + , it induces a map from A IN to B IN . All these maps are written τ also.

To a morphism τ , from A to B * , is naturally associated the matrix M τ = (m i,j ) i∈B,j∈A where m i,j is the number of occurrences of i in the word τ (j). To the composition of morphisms corresponds the multiplication of matrices. For example, let τ 1 : B → C * , τ 2 : A → B * and τ 3 : A → C * be three morphisms such that τ 1 τ 2 = τ 3 , then we have the following equality:

M τ 1 M τ 2 = M τ 3 . In particular if τ is a morphism from A to A * we have M τ n = M n τ .
A non-negative square matrix M always has a non-negative eigenvalue r such that the modulus of all its other eigenvalues do not exceed r. We call it the dominant eigenvalue of M (see for instance [START_REF] Gantmacher | Theory of matrices[END_REF]). A square matrix is called primitive if it has a power with positive coefficients. A morphism from A to A * is called primitive if its associated matrix is primitive. In this case the dominant eigenvalue is a simple root of the characteristic polynomial, and is strictly larger than the modulus of all other eigenvalues. This is Perron's Theorem ( [START_REF] Gantmacher | Theory of matrices[END_REF], p. 53).

Substitutions and substitutive sequences

Definition 1 A substitution is a triple τ = (τ, A, a), where A is an alphabet, τ is a morphism from A to A + and a is a letter of A such that the first letter of τ (a) is a.

Let τ = (τ, A, a) be a substitution. There exists a unique sequence X = (x n ) n∈IN of A IN such that x 0 = a and τ (X) = X (for more details we refer the reader to [START_REF] Queffélec | Substitution dynamical systems-Spectral analysis[END_REF]). We will say that X is the fixed point of τ and we will denote it by X τ .

In this article we only consider primitive substitutions, i.e. substitutions with primitive associated matrices. If τ = (τ, A, a) is a primitive substitution it is not difficult to see that its fixed point is uniformly recurrent (see [START_REF] Queffélec | Substitution dynamical systems-Spectral analysis[END_REF]).

Let A and B be two alphabets, we say that a morphism σ from A to B * is a letter to letter morphism when σ(A) is a subset of B. A sequence Y is substitutive if there exist a primitive substitution τ and a letter to letter morphism φ such that Y = φ(X τ ). We will also say that Y arises from τ . It is α-substitutive if α is the dominant eigenvalue of τ . We can remark that each substitutive sequence is uniformly recurrent. In particular, it is periodic whenever it is ultimately periodic.

From the proof of Proposition 9 in [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF] we deduce the following proposition: Proposition 1 Let A and B be two alphabets, X be a α-substitutive sequence on A and ϕ : A → B + be a morphism. There exists a positive integer k such that the sequence ϕ(X) is α k -substitutive.

This proposition allows us to consider only letter to letter morphisms without loss of generality.

Return words

In this section we define the main notion used in this paper, the return words. It was introduced in [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF] where we stated and proved some of its properties we recall here. We will use them very often in the sequel.

Definition

Let X be a uniformly recurrent sequence on the alphabet A and u a nonempty prefix of X. We call return word on u every factor X [i,j-1] , where i and j are two successive occurrences of u in X. For example let X = ababcababbbabababcababbbababaccababacc • • • be a sequence. The words ababc, ababbb, ab, ababacc are return words on abab of X.

The reader can check that a word v is a return word on u of X if and only if vu belongs to L(X), u is a prefix of vu and u has exactly two occurrences in vu. For the details we refer the reader to [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF]. The set of return words on u is finite, because X is uniformly recurrent, and is denoted by R X,u . The sequence X can be written naturally as a concatenation

X = m 0 m 1 m 2 • • • , m i ∈ R X,u , i ∈ IN,
of return words on u, and this decomposition is unique. We enumerate the elements of R X,u in the order of their first appearance in (m n ) n∈IN . This defines a bijective map

Θ X,u : R X,u → R X,u ⊂ A * where R X,u = {1, • • • , Card(R X,u )}.
The map Θ X,u defines a morphism and the set Θ X,u (R * X,u ) consists of all concatenations of return words on u. We denote by D u (X) the unique sequence on the alphabet R X,u characterized by

Θ X,u (D u (X)) = X.
We call it the derived sequence of X on u. It is clearly uniformly recurrent. We remark that

L(X) Θ X,u (R * X,u ) = Θ X,u (L(D u (X))).
When it does not create confusion we will forget the "X" in the symbols Θ X,u , R X,u and R X,u .

Some properties of return words

The following proposition points out the basic properties of return words which are of constant use throughout the paper.

Proposition 2 (Proposition 6 in [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF]) Let X be a uniformly recurrent sequence and u a non-empty prefix of X.

1. The set R X,u is a code, i.e. Θ X,u : R * X,u → Θ X,u (R * X,u
) is one to one.

2. If u and v are two prefixes of X such that u is a prefix of v then each return word on v belongs to Θ X,u (R * X,u ), i.e. it is a concatenation of return words on u.

3. Let v be a non-empty prefix of D u (X) and w = Θ X,u (v)u. Then • w is a prefix X, • Θ X,u Θ Du(X),v = Θ X,w and • D v (D u (X)) = D w (X).
Lemma 3 (Lemma 10 in [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF]) Let X be a non-periodic uniformly recurrent sequence, then

m n = Inf{|v|; v ∈ R X,X [0,n] } → +∞ when n → +∞.

Substitutive sequences and return words

When we apply return words to primitive substitutions we obtain some useful results. The following proposition states that each derived sequence of a fixed point of a primitive substitution is a fixed point of a primitive substitution too.

Proposition 4 (Proposition 19 in [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF]) Let τ = (τ, A, a) be a primitive substitution and u be a non-empty prefix of X τ . The derived sequence D u (X τ ) is the fixed point of a primitive substitution τ u = (τ u , R u , 1) where τ u satisfies

Θ u τ u = τ Θ u .
The map Θ u being one to one the previous equality completely characterized τ u . Such a substitution is called return substitution (on u). Moreover we can remark that (τ l ) u = (τ u ) l .

The two following theorems were established in [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF] to obtain a characterization of substitutive sequences: A non-periodic uniformly recurrent sequence Y is substitutive if and only if the set of its derived sequences is finite.

Theorem 5 (Theorem 18 in [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF]) Let Y be a non-periodic substitutive sequence. There exist three positive constants H 1 , H 2 and H 3 such that: For all non-empty prefixes u of Y ,

1. for all words v belonging to R Y,u , H 1 |u| ≤ |v| ≤ H 2 |u|, and 2. Card(R Y,u ) ≤ H 3 .
Theorem 6 (Theorem 20 in [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF]) Let τ = (τ, A, a) be a primitive substitution. The set of the return substitutions of τ is finite.

Eigenvalues and return words

We establish some morphism relations between the substitutions and their return substitutions, then we find their common eigenvalues.

In this section τ = (τ, A, a) will be a primitive substitution and u, v two prefixes of X τ such that |u| < |v|. We recall that we have

Θ u τ u = τ Θ u and Θ v τ v = τ Θ v . (1)
The word u is a prefix of v, hence a return word on v is a concatenation of return words on u. This allows us to define the morphism λ, from R v to R + u , by Θ u λ = Θ v . Thus we obtain the relation

τ u λ = λτ v .
Let k be an integer such that |v| < |τ k (u)|. The image by τ k of a return word on u is a concatenation of return words on v. We define a new morphism

κ, from R u to R + v , by Θ v κ = τ k Θ u .
We deduce the following morphism relations:

τ v κ = κτ u , κλ = τ k v and λκ = τ k u .

Consequently we have the following proposition:

Proposition 7 Let τ = (τ, A, a) be a primitive substitution and u, v be two prefixes of X τ such that |u| < |v|. Then there exist an integer k ≥ 1 and two morphisms λ : R v → R + u and κ :

R u → R + v such that τ v κ = κτ u , τ u λ = λτ v , κλ = τ k v and λκ = τ k u .
Corollary 8 All the return substitutions of a primitive substitution have all the same non-zero eigenvalues.

Proof: This is a straightforward consequence of Proposition 7. The details are left to the reader. 2

By primitivity, there exists an integer n 0 such that for all n ≥ n 0 all images by τ n of letters have at least two occurrences of u. Let l be an integer larger than n 0 and K l be the matrix defined by

K l = (L Θu(c)u (τ l (b)u)) c∈Ru,b∈A ; we recall that L Θu(c)u (τ l (b)u) is the number of occurrences of Θ u (c)u in τ l (b)u. Let b be an element of A. We set τ l (b)u = a 0 a 1 • • • a k a k+1 • • • a k+|u| .
Let i be the first occurrence of u in τ l (b) and j the greatest occurrence of u in

τ l (b)u such that a i • • • a j-1 is a concatenation of elements of R Xτ ,u . We set x = a 0 a 1 • • • a i-1 , y = a j a j+1 • • • a k+|u| and w = a i a i+1 • • • a j-1 .
The word w is a concatenation of return words on u and L Θu(d)u (wu) = L Θu(d)u (τ l (b)u). We remark that the length of x is less than H 2 |u| and that the length of y is less than (H 2 + 2)|u| where H 2 is the constant given by Theorem 5.

Let c be a letter of A,

L c (τ l (b)) = L c (x) + d∈Ru L c (Θ u (d))L Θu(d)u (wu) + L c (y) = L c (x) + d∈Ru L c (Θ u (d))L Θu(d)u (τ l (b)u) + L c (y).
We observe that the number of occurrences of c in both x and y is less (H 2 + 2)|u|. Then we have

M τ l = M l τ = M Θu K l + Q l , (2)
where Q l is a non-negative integral matrix whose coefficients are less than (H 2 + 2)|u|. For this reason the set {Q l ; l ∈ IN} is finite. Let b and c be two elements of R u . We set

p c,b = L Θu(c)u (τ l (Θ u (b))u) - d∈A L Θu(c)u (τ l (d)u)L d (Θ u (b)) .
We can bound p c,b independently of l. Let xy be a word of length 2 occurring in Θ u (b). We set τ l (xy

) = v 0 • • • v k-1 v k • • • v n where k = |τ l (x)|.
Let j be the greatest occurrence of u in τ l (xy) less or equal to k -1 and i be the smallest occurrence of u in τ l (xy) larger or equal to k. We have

|L Θu(c)u (v i • • • v j-1 u) -(L Θu(c)u (v i • • • v k-1 u) + L Θu(c)u (v k • • • v j-1 u))| ≤ 2(H 2 + 1)|u| H 1 |u| = 2(H 2 + 1) H 1 .
Where H 1 is the constant given by Theorem 5. Hence

p c,b ≤ 2(H 2 + 1) H 1 |Θ u (b)| ≤ 2(H 2 + 1)H 2 |u| H 1 .
Moreover we have

L c (τ l u (b)) = L Θu(c)u (τ l (Θ u (b))u) = d∈A L Θu(c)u (τ l (d)u)L d (Θ u (b)) + p c,b .
Consequently we have

M τ l u = M l τu = K l M Θu + P l . (3)
where P l is an integral matrix; the absolute values of its coefficients are less than 2(H 2 + 1)H 2 |u|/H 1 . Therefore the set {P l ; l ∈ IN} is finite.

Proposition 9 Let τ be a primitive substitution and u a prefix of X τ . The substitutions τ and τ u have the same eigenvalues, except perhaps 0 and roots of the unity.

Proof: Let u be a prefix of X τ and α a non-zero eigenvalue of M τ which is not a root of the unity. There exists a vector x = 0 such that ( T x)M τ = α( T x).

According to the relation (1), we have

( T x)M Θu M τu = α( T x)M Θu .
We have to prove that ( T x)M Θu is different from zero. Suppose it is false. From equality (2) it follows that α l ( T x) = ( T x)Q l for all integers l larger than n 0 . But the set {Q l , l ∈ IN} is finite. Hence there exist two distinct integers l 1 and l 2 , larger than n 0 , such that Q l 1 = Q l 2 . And finally we have α = 0 or α l 1 -l 2 = 1, which contradicts our assumption on α.

In the same way, it follows from equality (3) that if µ is a non-zero eigenvalue of M τu which is not a root of the unity, then µ is an eigenvalue of M τ . This completes the proof.

2

It is easy to check that if τ : {0, 1} → {0, 1} + is the Fibonacci substitution, i.e. τ (0) = 01 and τ (1) = 0, then we have τ = τ 01 . Hence τ and τ 01 have the same eigenvalues. On the other hand the set of eigenvalues of the Morse substitution, σ(0) = 01 and σ(1) = 10, is {0, 2} and the eigenvalues of σ 011 are 0, 0, -1 and 2.

A generalization of Cobham's Theorem

The proof of the generalization we announced requires several steps. In Proposition 10 and Proposition 11 we work under special assumptions. Proposition 11 shows why these assumptions are relevant for our purpose and Lemma 12 proves that it is always possible to work under these assumptions. This leads to a stronger theorem than the generalization though only valid for fixed points as announced in the introduction.

For convenience in the sequel we will use alphabets {1, 2, • • • , k}.

Some technical results

Proposition 10 Let τ = (τ, A, 1) be a primitive substitution and u be a prefix of X τ such that: Let J be an infinite set of positive integers. Then there exist an infinite subset I of J, a strictly increasing sequence of positive integers (l p ) p∈I and a morphism γ : A → A + such that for all p in I.

Θ lp u γ = γΘ lp u = τ p .
Proof: Hypothesis 2 says that A = R u . It is easy to check that the morphism Θ u : A → A * defines a substitution Θ u = (Θ u , A, 1). We put Θ = Θ u . Hypothesis 4 implies that this substitution is primitive.

As the substitutions τ u and τ are identical (hypothesis 2), they have the same fixed point X τ and we have seen that the fixed point of τ u is D u (X τ ) (Proposition 4), hence D u (X τ ) = X τ . Consequently, we have X τ = Θ(X τ ), i.e. X τ is the fixed point of Θ = (Θ, A, 1).

Moreover we can remark that τ Θ = Θτ . The word u is a prefix of D u (X τ ), hence we can consider the sequences (D n u (X τ )) n≥1 defined by

D 1 u (X τ ) = D u (X τ ) and D n+1 u (X τ ) = D u (D n u (X τ )) for all n ≥ 1.
Let us prove by induction that for all n ≥ 1 we have:

i) D n u (X τ ) = D wn (X τ ) = X τ , with w n = Θ n-1 (u) • • • Θ(u)u,
ii) Θ n = Θ wn and iii) τ = τ wn .

For n = 1 it suffices to remark that w 1 = u. Now suppose that points i), ii) and iii) are satisfied for some positive integer n. We have

D n+1 u (X τ ) = D u (D n u (X τ )) = D u (X τ ) = X τ
and Proposition 2 implies that:

• D n+1 u (X τ ) = D u (D wn (X τ )) = D w (X τ ) and • Θ w = Θ wn Θ Dw n (Xτ ),u = Θ n Θ Xτ ,u = Θ n+1 where w = Θ wn (u)w n = Θ n (u)Θ n-1 (u) • • • Θ(u)u = w n+1 .
Hence points i), ii) are satisfied for n + 1.

The substitution τ w n+1 is the return substitution on u of τ wn consequently Θτ w n+1 = τ wn Θ; that is to say Θτ w n+1 = τ Θ. But Θτ u = τ Θ and the map Θ is one to one hence τ w n+1 = τ u = τ . This completes the proof by induction of points i), ii) and iii).

We denote the dominant eigenvalues of M τ and M Θ respectively by α and β. We recall (see for instance [START_REF] Queffélec | Substitution dynamical systems-Spectral analysis[END_REF]) that there exists a positive number r such that for all b in A and all k in

IN 1 r α k ≤ |τ k (b)| ≤ rα k and 1 r β k ≤ |Θ k (b)| ≤ rβ k .
From this we deduce that there exists two constants c 1 and c 2 such that for all positive integers n

c 1 β n ≤ |w n | = |Θ n-1 (u) • • • Θ(u)u| ≤ c 2 β n .
From hypothesis 1 it follows that there exists an integer k 0 such that u is a prefix of all images of letters by τ k 0 . For every integer k, larger than k 0 , we define l k to be the greatest integer n such that w n is a prefix of τ k-1 (1). For all positive integers we have

c 1 β l k ≤ |w l k | ≤ |τ k-1 (1)| ≤ |w l k +1 | ≤ c 2 β l k +1 .
Thus we obtain

|τ k-1 (1)| ≤ βc 2 c 1 c 1 β l k ≤ βc 2 c 1 |w l k |.
Let k be an integer larger than k 0 . For all letters b of A the word w l k is a prefix of τ k (b). Hence all images by τ k of words are concatenations of return words on w l k . This remark allows us to define the morphism γ k , from A to A + , by Θ w l k γ k = τ k . We have:

Θ w l k γ k Θ w l k = τ k Θ l k = Θ l k τ k . The map Θ w l k = Θ l k is one to one hence γ k Θ w l k = τ k and finally Θ w l k γ k = γ k Θ w l k . (4)
Moreover for all b in A

|γ k (b)| = L w l k (τ k (b)w l k ) -1 ≤ |τ k (b)| + |w l k | H 1 |w l k | ≤ 2βc 2 |τ k (b)| H 1 c 1 |τ k-1 (1)| ≤ 2c 2 r 2 αβ H 1 c 1 ,
where H 1 is the constant of Theorem 5. We have proved that the length of the images by γ k of letters are bounded independently of k. Hence the set {γ k ; k ≥ k 0 } is finite. Thus there exists an infinite set I, included in J, such that γ p = γ q for all elements p and q of I.

Let p be an element of I, we write γ = γ p . Equality (4) gives Θ lp γ = γΘ lp = τ p . From this last equality it follows that the sequence (l p ) p∈I is strictly increasing.

2

Proposition 11 Let τ = (τ, A, 1) be a primitive substitution and u be a prefix of X τ satisfying the hypothesis of Proposition 10. Let J be an infinite set of positive integers. Then there exist an infinite subset I of J and a strictly increasing sequence of positive integers (l p ) p∈I such that, for all distinct integers p and q belonging to I, p < q, we have:

• The non-zero eigenvalues of τ q-p are eigenvalues of Θ lq-lp u ,

• Θ u is a primitive substitution and the non-zero eigenvalues of Θ lq-lp u , except perhaps roots of the unity, are eigenvalues of τ q-p .

Proof: We set Θ = Θ u . As in the proof of Proposition 10 we can remark that Θ defines a primitive substitution Θ = (Θ, A, 1). There exist an infinite set I of integers, a strictly increasing sequence of integers (l p ) p∈I and a morphism γ from A to A + such that for all p in I Θ lp γ = γΘ lp = τ p .

Let p < q be two elements of I. From the previous equalities and from the fact that Θτ = τ Θ (because τ = τ u ) we obtain

τ q = Θ lq-lp Θ lp γ = Θ lq-lp τ p = τ p Θ lq-lp . (5)
Let α be a non-zero eigenvalue of M τ q-p = M q-p τ and x one of its eigenvectors. Equality (5) implies

M lq-lp Θ M p τ x = M q τ x = αM p τ x. But the vector M (q-p)p τ
x is different from zero and therefore so is M p τ x. Thus α is an eigenvalue of Θ lq-lp . This completes the first part of the proof.

It remains to prove the second part. Let k 0 be an integer such that min b∈A |Θ k 0 (b)| > 2max b∈A |τ p (b)|. Let k be a positive integer such that k(l ql p ) > k 0 . For all letters b of A we can write Θ k(lq-lp) (b) = uτ p (w)v, where u and v are respectively a suffix and a prefix of an element of τ p (A), and w is a non-empty word of L(X τ ). Hence there exist two integral matrices with non-negative coefficients, S k and P k , such that

M k(lq -lp) Θ = M p τ S k + P k , (6)
where the coefficients of P k are less than 2max b∈A |τ p (b)|. The set {P j ; j > k(l q -l p )} is finite because the coefficients are bounded independently of k.

Consequently there exist two integers k 1 and k 2 such that

P k 1 = P k 2 .
Let α be a non-zero eigenvalue of M lq-lp Θ which is not a root of the unity, and x one of its associated left eigenvectors. Equality (5) leads to

xM p τ M q-p τ = xM q τ = xM lq -lp Θ M p τ = αxM p τ .
But P k 1 = P k 2 , so xM p τ is different from zero. Otherwise, by equality (6) we would have α k 1 x = α k 2 x. Which contradicts our hypothesis on α.

2

Lemma 12 Let (τ, A, 1) and σ = (σ, A, 1) be two primitive substitutions having the same non-periodic fixed point X. There exist an integer l, a prefix v of X, and an arbitrarily long prefix u of D v (X) such that the word u and the substitution τ l v , and u and the substitution σ l v , both satisfy the hypothesis of Proposition 10.

Proof: Let (X (n) ) n∈IN be the sequences defined by: X (0) = X and X (n+1) is the derived sequence of X (n) on the prefix 1 (the first letter of X (n) ). For all integers n we call A (n) the alphabet of X (n) . Let (u (n) ) n≥1 be the sequence of words defined by:

u (1) = 1 and u (n+1) = Θ X,u (n) (1)u (n) .
According to Proposition 2, for all integers n larger than 1, the word u

(n) is a prefix of X τ such that Θ X,1 Θ X (1) ,1 • • • Θ X (n-1) ,1 = Θ X,u (n) and X (n) = D u (n) (X).
The sets {τ u , u ≺ X} and {σ u , u ≺ X} are finite by Theorem 6. Hence, there exists an infinite set I of positive integers such that for all integers p and q of I, we have τ u (p) = τ u (q) and σ u (p) = σ u (q) . We remark that the fixed point of the substitutions τ u (p) = (τ u (p) , A (p) , 1) and σ u (p) = (σ u (p) , A (p) , 1) is

X (p) = D u (p) (X).
Let p and q be two elements of I with p < q. By definition of (X (n) ) n∈IN we have

X (q) = D 1 • • • D 1 (q-p) times (X (p) )
Hence (Proposition 2) there exists a prefix u of X (p) such that

• D u (X (p) ) = X (q) , • Θ X (p) ,1 Θ X (p+1) ,1 • • • Θ X (q-1) ,1 = Θ X (p) ,u , • Θ X (p) ,u τ u (q) = τ u (p) Θ X (p) ,u and Θ X (p) ,u σ u (q) = σ u (p) Θ X (p) ,u .
From the last equalities it is clear that (τ u (p) ) u = τ u (q) and (σ u (p) ) u = σ u (q) ; where (τ u (p) ) u and (σ u (p) ) u are respectively the return substitutions on u of τ u (p) and σ u (p) .

From the definition of (u (n) ) n≥1 we deduce that the sequence (|u (n) |) n≥1 is strictly increasing. Thus it follows from Lemma 3 that

lim j→+∞ min{|Θ X (0) ,u (j) (b)| = |Θ X (0) ,1 Θ X (1) ,1 • • • Θ X (j) ,1 (b)|; b ∈ A (j+1) } = +∞. and consequently that lim j→+∞ min{|Θ X (p) ,1 Θ X (p+1) ,1 • • • Θ X (j) ,1 (b)|; b ∈ A (j+1) } = +∞.
Therefore we can suppose that q, and consequently u, is such that each letter of A (p) (the alphabet of X (p) ) has at least one occurrence in each return word on u of X (p) . (We recall that the set of return words on u of

X (p) is {Θ X (p) ,u (b) = Θ X (p) ,1 Θ X (p+1) ,1 • • • Θ X (q-1) ,1 (b); b ∈ A (q) }.)
The word Θ X,u (p) (1)u (p) is a prefix of X hence we can choose an integer l such that the word Θ X,u (p) (1)u (p) is a prefix of τ l (1) and σ l (1). Thus the first letter of each image of τ l u (p) and σ l u (p) is 1. We set v = u (p) and γ = τ l v . The substitution (γ, A (p) , 1) and the prefix u of X (p) (which is the fixed point of γ) fulfill the hypotheses of Proposition 10. Indeed we chose the integer l to satisfy hypothesis 1. Hypothesis 2 is also satisfied because

γ u = (τ u (p) ) u = τ u (q) = τ u (p) = γ,
where γ u is the return substitution on u. Hypothesis 3 does not set any difficulty. Hypothesis 4 follows from the choice of q.

It is clear that σ l u (p) and u also satisfy the same hypotheses. 2

Theorem 13 If two primitive substitutions have the same non-periodic fixed point, then they have some powers which have the same eigenvalues, except perhaps 0 and roots of the unity.

Proof: It follows from Lemma 12, Proposition 11 and Proposition 9. 2

Proof of the main result

Theorem 14 Let X be a substitutive sequence arising from τ = (τ, B, 1), and also from σ = (σ, C, 1). If X is non-periodic then the dominant eigenvalues of τ and of σ are multiplicatively dependent.

Proof: Let A be the alphabet of X. There exist a morphism φ, from B to A, and a morphism ϕ from C to A such that φ(X τ ) = ϕ(X σ ) = X.

Recall that by Theorem 6, if a sequence is substitutive then its set of derived sequences is finite. Hence there exist three sequences, (u (n) ) n∈IN , (v (n) ) n∈IN and (w (n) ) n∈IN , of prefixes of respectively X τ , X and X σ such that for all integers n we have:

• D u (n) (X τ ) = D u (n+1) (X τ ), • D v (n) (X) = D v (n+1) (X), • D w (n) (X σ ) = D w (n+1) (X σ ), • φ(u (n) ) = ϕ(w (n) ) = v (n) and |v (n) | < |v (n+1) |.
Let n be an integer. The images of words by φΘ u (n) are concatenations of return words on v (n) . The map Θ v (n) : R * v (n) → A * being one to one, this allows us to define a morphism λ n by Θ v (n) λ n = φΘ u (n) . In the same way we define the morphism γ n by Θ v (n) γ n = ϕΘ w (n) . In the proof of Theorem 21 in [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF], it is proved that the set {λ n ; n ∈ IN}, and also the set {γ n ; n ∈ IN}, are finite. For this reason we can suppose that for all integers n we have λ n = λ n+1 and γ n = γ n+1 .

Let i be an integer. The sequence X τ (resp. X σ ) is uniformly recurrent hence, according to Lemma 3, there exists an integer j larger than i such that each word wu (i) , where w is a return word on u (i) , has at least one occurrence in each return word on u (j) . Consequently we can define a primitive substitution δ by Θ u (i) δ = Θ u (j) . In the same way we define a primitive substitution

ρ by Θ v (i) ρ = Θ v (j) . We have ρλ j = λ j δ. Indeed Θ v (i) ρλ j = Θ v (j) λ j = φΘ u (j) = φΘ u (i) δ = Θ v (i) λ i δ = Θ v (i) λ j δ.
A standard application of Perron's Theorem ( [START_REF] Gantmacher | Theory of matrices[END_REF], p. 53) shows that δ and ρ have the same dominant eigenvalue.

We recall that D u (i) (X τ ) = D u (j) (X τ ). Hence δ has the same fixed point as τ u (i) , that is to say D u (i) (X τ ). It follows from Theorem 13 and Proposition 9 that the dominant eigenvalues of δ and τ are multiplicatively dependent.

In the same way we prove that ρ and σ have multiplicatively dependent dominant eigenvalues. This completes the proof.

2

Could we obtain a result analogous to Theorem 13? That is to say concerning all eigenvalues. The answer is negative. Here is a counterexample: Let τ = (τ, {a, b}, a) and σ = (σ, {a, b, c}, a) be two substitutions defined respectively by a → abab b → abbb and

     a → abab b → accc c → abbc .
Eigenvalues of the substitution τ are 1 and 4. Those of σ are 1, -2 and 4. Let φ : {a, b, c} → {a, b} be the morphism defined by φ(a) = a and φ(b) = φ(c) = b, then φ(X σ ) = X τ . The sequence X τ arises from two substitutions, one has the eigenvalue -2 and the other does not.

To prove the reciprocal of Theorem 14 we need a result due to D. Lind (Theorem 15). A Perron number is an algebraic integer that strictly dominates all its other algebraic conjugates. It follows easily from Perron's Theorem that the dominant eigenvalue of an integral primitive matrix is a Perron number. The following theorem shows the reciprocal is true.

Theorem 15 ([14]) If α is a Perron number then there exists a primitive integral matrix with dominant eigenvalue α.

Here is the reciprocal of Theorem 14.

Proposition 16 Let Y be a periodic sequence on the alphabet B and α a Perron number. There exists an integer k such that Y is α k -substitutive.

Proof: There exists a word m such that Y = m ω . According to Theorem 15 there exists an integral primitive matrix M with dominant eigenvalue α. There exists an integer k such that:

1. The matrix M k has strictly positive coefficients and 2. The sum of the coefficients of any column of M k is larger than the length of m.

It is easy to construct a primitive substitution τ = (τ, A, 1) with associated matrix M k . The dominant eigenvalue of this substitution is α k .

Let D be the alphabet {(b, i); b ∈ A , 0 ≤ i ≤ |m| -1}. We define the morphism ψ : In this last section we use the circularity of primitive substitutions, proved in [START_REF] Mignosi | If a D0L language is k-power free then it is circular[END_REF][START_REF] Mossé | Puissances de mots et reconnaissabilité des points fixes d'une substitution[END_REF], to obtain further results about substitutions sharing the same fixed point.

Definition 2 Let τ = (τ, A, 1) be a substitution and x a factor of X τ . We say that (u, w, v) is an interpretation of x if x = uτ (w)v and u, v are respectively a suffix and a prefix of the image, by τ , of some letters and w is a factor of X τ .

Definition 3

We say that a substitution τ is circular with synchronization delay D when: If a factor of X τ admits two distinct interpretations, (u, w, v) and (x, y, z), and i is an integer such that |uτ (w [0,i-1] )| > D and |τ (w [i+1,|w|-1] )v| > D, then there exists an integer j such that uτ (w [0,i-1] ) = xτ (y [0,j-1] ) and w i = y j .

Theorem 17 ([18, 19]) A primitive substitution is circular.

1 . 2 . 3 . 4 .

 1234 For all letters b of A, τ (b) begins by 1, The substitutions τ and τ u are defined on the same alphabet and are identical, The fixed point of τ is non-periodic, For all letters b and c of A, b has at least one occurrence in Θ u (c).

2 6

 2 A → D + by ψ(b) = (b, 0) • • • (b, |m| -1). The length of an element of τ (A) is larger than |m|. This allows us to define the substitution ζ = (ζ, D, (1, 0)) in the following way: For all (b, k) of D ζ((b, k)) = ψ(τ (b) [k,k] ) if k < |m| -1, ζ((b, |m| -1)) = ψ(τ (b) [|m|-1,|τ (b)|-1] ) otherwise.These morphisms are such that ζψ = ψτ . Hence the substitution ζ is primitive. Its fixed point is ψ(X τ ) and its dominant eigenvalue is α k .Let ϕ : D → B be the letter to letter morphism defined by ϕ((b, i)) = m [i,i] . It is easy to see that ϕ(X ζ ) = Y . It follows that Y is α k -substitutive.Substitutions sharing the same fixed point

In the following proposition we prove that a primitive substitution is one to one on the set of return words on a sufficiently long prefix of its fixed point.

Proposition 18 Let τ be a primitive substitution with a non-periodic fixed point X. There exists an integer n 0 such that for all prefixes u of X of length larger than n 0 the substitution τ is one to one on L(X) Θ X,u (R * X,u ).

Proof: The substitution τ is circular with synchronization delay D (Theorem 17). According to Lemma 3, there exists an integer n 0 such that for all prefixes u satisfying |u| > n 0 the length of all return words on u is larger than D.

Let u be a prefix of X larger than max(n 0 , D) and v, w be two elements of L(X) Θ X,u (R + X,u ) such that τ (v) = τ (w). Let l be the smallest integer n such that |τ (v [0,n] )| > D. This integer is smaller than |u| because

Corollary 19 Let τ be a primitive substitution with a non-periodic fixed point X. There exists an integer n 0 such that, for all prefixes u of X of length larger than n 0 , the substitution τ u is one to one on L(X).

Proof: It follows directly from Proposition 18. 2

To obtain the main result of this section we need an intermediate lemma.

Lemma 20 Let τ = (τ, A, 1) be a primitive substitution, with fixed point X, and u be a prefix of X satisfying the hypothesis of Proposition 10. Let J be an infinite set of positive integers. There exist a subset I of J and a strictly increasing sequence of positive integers (l p ) p∈I such that for all integers p and q, p < q, belonging to I, we have τ q-p = Θ lq-lp u .

Proof: There exist an infinite subset of J, and a strictly increasing sequence (l p ) p∈I such that for all integers p and q, p < q, we have

This follows from equality (5) obtained in the proof of Proposition 11. Let p and q be two elements of I. It follows from Proposition 2 that X τ has a prefix w such that Θ w = Θ lq-lp u . Remark that the substitutions τ and τ w are identical. From Lemma 3 and Corollary 19 we deduce that we can choose q sufficiently large in order that τ w is one to one on L(X τw ). But τ = τ w , hence τ is one to one on its language. This implies that τ q-p = Θ lq-lp u .

2

To end this paper we prove a strong relation between two primitive substitutions sharing the same fixed point.

Proposition 21 Let τ and σ be two primitive substitutions having the same non-periodic fixed point X. There exist a prefix u of X and two integers i and j such that τ i u = σ j u . Proof: There exist a prefix u of X and a prefix v of D u (X) such that τ u and v, and σ u and v, both satisfy the hypothesis of Proposition 10. This is Lemma 12. It follows from Lemma 20 that there exist two integers i and j such that

With the same hypothesis an equivalent formulation of the previous result is: There exists a prefix u and two integers i and j such that τ i and σ j coincide on L(X) Θ X,u (R * X,u ). Aknowledgements I am grateful to B. Host for the time and the energy he spent on this work. I would like to thank the referees for their valuable advices and constructive comments.