Fabien Durand
email: fabien.durand@u-picardie.fr

Michel Rigo
email: m.rigo@ulg.ac.be

On Cobham's theorem

Keywords: 2010 Mathematics Subject Classification: 68Q45, 68R15, 11B85, 11A67, 11U05, 37B20 Numeration systems, recognizable sets of integers, Cobham's theorem, ultimate periodicity, substitutions, dynamical systems

Introduction

In this chapter we essentially focus on the representation of non-negative integers in a given numeration system. The main role of such a system -like the usual integer base k numeration system -is to replace numbers or more generally sets of numbers by their corresponding representations, i.e., by words or by languages. First we consider integer base numeration systems to present the main concepts but rapidly we will introduce nonstandard systems and their relationships with substitutions.

Let k ∈ N 2 be an integer where N 2 denotes the set of non-negative integers larger or equal to 2. The set {0, . . . , k} is denoted by [[0, k]]. If we do not allow leading zeroes when representing numbers, the function mapping a non-negative integer n onto its k-ary

representation rep k (n) ∈ [[0, k -1]
] * is a one-to-one correspondence. In the literature, one also finds notation like n k , (n) k or ρ k (n) instead of rep k (n). In particular, 0 is assumed to be represented by the empty word ε. Hence any set X ⊆ N is associated with the language rep k (X) consisting of the k-ary representations of the elements of X.

It is natural to study the relation existing between the arithmetic or number-theoretic properties of integers and the syntactical properties of the corresponding representations in a given numeration system. We focus on those sets X ⊆ N for which a finite automaton can be used to decide for any given word w over [[0, k -1]] whether or not w belongs to rep k (X). Sets having the property that rep k (X) is regular 1 are called k-recognizable sets. Such a set can be considered as a particularly simple set because using the k-ary numeration system it has a somehow elementary algorithmic description. In the framework of infinite-state systems verification, one also finds the terminology of Number Decision Diagram or NDD [START_REF] Wolper | Verifying systems with infinite but regular state spaces[END_REF].

The essence of Cobham's theorem is to express that the property for a set to be recognizable by a finite automaton strongly depends on the choice of the base and more generally on the considered numeration system. Naturally this fact leads to and motivates the introduction and the study of recognizable sets in non-standard numeration systems. Considering alternative numeration systems may provide new recognizable sets and these non-standard systems also have applications in computer arithmetic [START_REF] Frougny | Non-standard number representation: computer arithmetic, beta-numeration and quasicrystals[END_REF]. Last but not least, the proof of Cobham's theorem is non-trivial and relies on quite elaborate argu-ments. Now let us state this celebrated result from 1969 and give all the needed details and definitions. Several surveys have been written on the same subject, see [START_REF] Bruyère | Automata and numeration systems[END_REF][START_REF] Bruyère | On Cobham's theorem[END_REF][START_REF] Bruyère | Logic and p-recognizable sets of integers[END_REF][START_REF] Perrin | Finite automata[END_REF].

Theorem 1.1 (Cobham's theorem [START_REF] Cobham | On the base-dependence of sets of numbers recognizable by finite automata[END_REF]). Let k, ℓ 2 be two multiplicatively independent integers. A set X ⊆ N is both k-recognizable and ℓ-recognizable if and only if it is ultimately periodic.

In the various contexts that we will describe, showing that an ultimately periodic set is recognizable is always the easy direction to prove. See Remark 1.3. So we focus on the other direction. Definition 1.1. A subset of N is ultimately periodic if it is the union of a finite set and a finite number of infinite arithmetic progressions. In particular, X is ultimately periodic if and only if there exist N 0 and p 1 such that for all n N , n ∈ X ⇔ n + p ∈ X.

Recall that an arithmetic progression is a set of the kind aN + b := {an + b | n 0}. Definition 1.2. Let α, β > 1 be two real numbers. If the equation α m = β n with m, n ∈ N has only the trivial integer solution m = n = 0, then α and β are said to be multiplicatively independent. Otherwise, α and β are said to be multiplicatively dependent.

Let k, ℓ 2 be two integers. Notice that k and ℓ are multiplicatively independent if and only if log k/ log ℓ is irrational. Note that for k and ℓ to be multiplicatively dependent it is not enough that k and ℓ share exactly the same prime factors occurring in their decomposition. For instance, 6 and 18 are multiplicatively independent. But coprime integers are multiplicatively independent.

The irrationality of log k/ log ℓ is a crucial point in the proof of Cobham's theorem (see Subsection 5.3). Recall that if θ > 0 is irrational, then the set {{nθ} | n > 0} of fractional parts of the multiples of θ is dense in [0, 1]. For a proof of the so-called Kronecker's theorem, see [START_REF] Hardy | An Introduction to the Theory of Numbers[END_REF].

Remark 1.2. The fact for two integers to be multiplicatively dependent is an equivalence relation M over N 2 . If k and ℓ are multiplicatively dependent, then there exist a minimal q 2 and two positive integers m, n such that k = q m and ℓ = q n . Let us give the first (with respect to their minimal element) few equivalence classes for M partitioning N 2 :

[2] M , [START_REF] Alexeev | Minimal DFAs for testing divisibility[END_REF] M , [START_REF] Allouche | Periodicity, repetitions, and orbits of an automatic sequence[END_REF] M , [START_REF] Allouche | The ring of k-regular sequences[END_REF] M , [START_REF] Allouche | The ring of k-regular sequences[END_REF] M , [START_REF] Bell | A generalization of Cobham's theorem for regular sequences[END_REF] M , [START_REF] Bell | A decision problem for ultimately periodic sets in non-standard numeration systems[END_REF] M , [START_REF] Berthé | Combinatorics, Automata and Number Theory[END_REF] M , . . . . Remark 1.3. We show that if a set X ⊆ N is ultimately periodic then, for all k 2, X is k-recognizable. In the literature, one also finds the terminology of a recognizable set X (without any mention to a base), meaning that X is k-recognizable for all k 2. Note that a finite union of regular languages is again a regular language. Hence it is enough to check that rep k (aN + b) is regular with 0 b < a. We can indeed assume that b < a because if we add or remove a finite number of words to a regular language, we still have a regular language. Consider a DFA having Q = [[0, a -1]] as its set of states. For all i ∈ Q, d ∈ [[0, k -1]], the transitions are given by

i d -→ ki + d mod a.
The initial state is 0 and the unique final state is b. As an example, a DFA accepting exactly binary representations of the integers congruent to 3 mod 4 is given in Figure 1. A study of the minimal automaton recognizing such divisibility criteria expressed in an integer base is given in [START_REF] Alexeev | Minimal DFAs for testing divisibility[END_REF]. See also the discussion in [START_REF] Sakarovitch | Éléments de théorie des automates[END_REF]Prologue]. The fact that a divisibility criterion exists in every base for any fixed divisor was already observed by Pascal in [97, pp. 84-89].

Numeration basis

It is remarkable that the recognizability of ultimately periodic sets extends to wider contexts (see Proposition 2.6 and Theorem 5.1). Let us introduce a first generalization of the integer base numeration system.

Definition 2.1.

A numeration basis is a sequence U = (U n ) n 0 of integers such that U is increasing, U 0 = 1 and that the set {U i+1 /U i | i 0} is bounded. This latter condition ensures the finiteness of the alphabet of digits used to represent integers. If w = w ℓ • • • w 0 is a word over a finite alphabet A ⊂ Z then the numerical value of w is

π A,U (w) = ℓ i=0 w i U i .
Using the greedy algorithm [START_REF] Fraenkel | Systems of numeration[END_REF], any integer n has a unique (normal) U -representation rep U (n) = w ℓ • • • w 0 which is a finite word over a minimal finite alphabet called the canonical alphabet of U and denoted by A U . The normal U -representation satisfies

π AU ,U (rep U (n)) = n and for all i ∈ [[0, ℓ -1]], π AU ,U (w i • • • w 0 ) < U i+1 . Again, rep U (0) = ε. See [
]. A subset X ⊆ N is U -recognizable if rep U (X) is accepted by a finite automaton. Let B ⊂ Z be a finite alphabet. If w ∈ B * is such that π B,U (w) 0, then the function mapping w onto rep U (π B,U (w)) is called normalization. Definition 2.2. A numeration basis U is said to be linear if there exist k ∈ N \ {0}, d 1 , . . . , d k ∈ Z, d k = 0, such that, for all n k, U n = d 1 U n-1 + • • • + d k U n-k . The polynomial P U (X) = X k -d 1 X k-1 -• • • -d k-1 X -d k is called the characteristic polynomial of U .
Definition 2.3. Recall that a Pisot-Vijayaraghavan number is an algebraic integer β > 1 whose Galois conjugates have modulus strictly less than one. We say that U = (U n ) n 0 is a Pisot numeration system if the numeration basis U is linear and P U (X) is the minimal polynomial of a Pisot number β. Integer base numeration systems are particular cases of Pisot systems. For instance, see [START_REF] Bruyère | Bertrand numeration systems and recognizability[END_REF] where it is shown that most properties related to k-recognizable sets, k ∈ N 2 , can be extended to Pisot systems. In such a case, there exists some c > 0 such that |U n -c β n | → 0, as n tends to infinity.

Example 2.1. Consider the Fibonacci sequence defined by U 0 = 1, U 1 = 2 and U n+2 = U n+1 +U n for all n 0. A word over {0, 1} is a U -representation if and only if it belongs to the language L = 1{0, 01} * ∪ {ε}. For instance 10110 is not a U -representation. Since π AU ,U (10110) = 13, the normalization maps 10110 to rep U (13) = 100000. The characteristic polynomial of this linear numeration basis is the minimal polynomial of the Pisot number (1 + √ 5)/2. This Pisot numeration system is presented in [START_REF] Zeckendorf | Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres Lucas[END_REF].

The following result is an easy exercise but also can be carried on in a wider context.

Theorem 2.1. [START_REF] Shallit | Numeration systems, linear recurrences, and regular sets[END_REF] Let U be a numeration basis. If N is U -recognizable, then U is linear.

Definition 2.4. [START_REF] Bertrand-Mathis | Développement en base θ; répartition modulo un de la suite (xθ n ) n 0 ; langages codés et θ-shift[END_REF] A Bertrand numeration basis U is a numeration basis satisfying the following property: w ∈ rep U (N) if and only if, for all n ∈ N, w0 n ∈ rep U (N). It is a natural condition satisfied by all integer base k 2 systems. For instance, the sequence defined by U 0 = 1, U 1 = 3 and, for all n 0,

U n+2 = U n+1 + U n is not a Bertrand numeration basis because rep U (2) = 2, but π AU ,U (20) = 6 and rep U (6) = 102.
Let α > 1 be a real number. The notion of α-expansion was introduced by Parry in [START_REF] Parry | On the β-expansions of real numbers[END_REF], (also see Rényi's paper [START_REF] Rényi | Representations for real numbers and their ergodic properties[END_REF]). See again [START_REF] Lothaire | Algebraic Combinatorics on Words, volume 90 of Encyclopedia of Mathematics and Its Applications[END_REF]Chapter 7]. All x ∈ [0, 1] can be uniquely written in the following way:

x = n 1 a n α -n , (2.1)
with x 1 = x and for all n 1, a n = ⌊α x n ⌋ and x n+1 = {αx n }, where ⌊•⌋ stands for the integer part. The sequence d α (x) = (a n ) n 1 is the α-expansion of x and L(α) denotes the set of finite words having an occurrence in some sequences

d α (x), x ∈ [0, 1]. Let d α (1) = (t n ) n 1 .
If there exist N 0, p > 0 such that, for all n N , t n+p = t n then α is said to be a Parry number, sometimes called a β-number (for more details or information about these numbers, see [START_REF] Parry | On the β-expansions of real numbers[END_REF] or [START_REF] Frougny | Representations of numbers and finite automata[END_REF]). Observe that integers greater or equal to 2 are Parry numbers.

The following result relates Bertrand numeration systems to languages defined by some real number. [START_REF] Bertrand-Mathis | Comment écrire les nombres entiers dans une base que n'est pas entière[END_REF]). Let U be a numeration basis. It is a Bertrand numeration basis if and only if there exists a real number α > 1 such that rep U (N) = L(α). In this case, if U is linear then α is a root of the characteristic polynomial of U . Theorem 2.3 (A. Bertrand-Mathis [START_REF] Bertrand-Mathis | Développement en base θ; répartition modulo un de la suite (xθ n ) n 0 ; langages codés et θ-shift[END_REF]). Let α > 1 be a real number. The language L(α) is regular if and only if α is a Parry number.

Theorem 2.2 (A. Bertrand-Mathis

Associated with a Parry number β, one can define the notion of beta-polynomial. For details see [START_REF] Hollander | Greedy numeration systems and regularity[END_REF] or [START_REF] Berthé | Combinatorics, Automata and Number Theory[END_REF]Chapter 2]. First we define the canonical beta-polynomial. If d β (1) is eventually constant and equal to 0:

d β (1) = t 1 • • • t m 0 ω , with t m = 0, then we set G β (X) = X m - m i=1 t i X m-i and r = m. Otherwise, d β (1) is eventually periodic: d β (1) = t 1 • • • t m (t m+1 • • • t m+p ) ω , with m and p being minimal. Then we set G β (X) = X m+p -m+p i=1 t i X m+p-i -X m + m i=1 t i X m-i and r = p. Let β be a Parry number. An extended beta-polynomial is a polynomial of the form H β (X) = G β (X)(1 + X r + • • • + X rk )X n for k, n ∈ N.
Proposition 2.4. [START_REF] Hollander | Greedy numeration systems and regularity[END_REF] Let U be a linear numeration basis with dominant root β, i.e.,

lim n→∞ U n+1 /U n = β for some β > 1. If rep U (N) is regular, then β is a Parry number.
Theorem 2.5 (M. Hollander [START_REF] Hollander | Greedy numeration systems and regularity[END_REF]). Let U be a linear numeration basis whose dominant root β is a Parry number.

(X m -1)H β (X).
Ultimately periodic sets are recognizable for any linear numeration basis.

Proposition 2.6 (Folklore [START_REF] Berthé | Combinatorics, Automata and Number Theory[END_REF][START_REF] Lothaire | Algebraic Combinatorics on Words, volume 90 of Encyclopedia of Mathematics and Its Applications[END_REF]). Let a, b 0.

If U = (U n ) n 0 is a linear numeration basis, then π -1 AU ,U (a N + b) = c ℓ • • • c 0 ∈ A * U | ℓ k=0 c k U k ∈ a N + b
is accepted by a DFA that can be effectively constructed. In particular, if N is U -recognizable, then any ultimately periodic set is U -recognizable.

To conclude this section, consider again the integer base numeration systems.

Example 2.2. The set P 2 = {2 n | n 0} of powers of two is trivially 2-recognizable because rep 2 (P 2 ) = 10 * . Since the difference between any two consecutive elements in P 2 is of the kind 2 n+1 -2 n = 2 n , P 2 is not ultimately periodic. As a consequence of Cobham's theorem, P 2 is for instance neither 3-recognizable nor 5-recognizable.

One could also consider the case when the two bases k and ℓ are multiplicatively dependent. This case is much easier and can be considered as an exercise.

Proposition 2.7. Let k, ℓ 2 be two multiplicatively dependent integers. A set X ⊆ N is k-recognizable if and only if it is ℓ-recognizable.
The theorem of Cobham implies that ultimately periodic sets are the only infinite sets that are k-recognizable for every k 2. We have seen so far that there exist sets (like the set P 2 of powers of two) that are only recognizable for some specific bases: exactly all bases belonging to a unique equivalence class for the equivalence relation M over N 2 . To see that a given infinite ordered set X = {x 0 < x 1 < x 2 < • • • } is k-recognizable for no base k 2 at all, we can use results like the following one, where the behavior of the ratio (resp. difference) of any two consecutive elements in X is studied through the quantities

R X = lim sup i→∞ x i+1 x i and D X = lim sup i→∞ (x i+1 -x i ) .
Theorem 2.8 (Gap theorem [START_REF] Cobham | Uniform tag sequences[END_REF]). Let k

2. If X ⊆ N is a k-recognizable infinite subset of N, then either R X > 1 or D X < +∞.
Corollary 2.9. Let a ∈ N 2 . The set of primes and the set {n a | n 0} are never k-recognizable for any integer base k 2.

Proofs of the Gap theorem and its corollary can also be found in [START_REF] Eilenberg | Automata, Languages, and Machines[END_REF]. For more results on primes, see also the chapter "Automata in number theory" of this handbook. Definition 2.5. An infinite ordered set

X = {x 0 < x 1 < x 2 < • • • } such that D X <
+∞ is said to be syndetic or with bounded gaps: there exists C > 0 such that for all n 0, x n+1 -x n < C. In particular, any ultimately periodic set is syndetic. The converse does not hold, see for instance Example 3.1.

Remark 2.10. Note that syndeticity occurs in various contexts like in ergodic theory. As an example, a subset of an Abelian group G is said to be syndetic if finitely many translates of it cover G. The term "syndetic" was first quoted in [START_REF] Gottschalk | Topological Dynamics[END_REF]. Note that in [START_REF] Hansel | Systèmes de numération indépendants et syndéticité[END_REF] the following result is proved. Let α, β > 1 be multiplicatively independent real numbers. If a set X ⊆ N is α-recognizable and β-recognizable, for the Bertrand numeration systems based respectively on the real numbers α and β in the sense of [START_REF] Bertrand-Mathis | Comment écrire les nombres entiers dans une base que n'est pas entière[END_REF] and Theorem 2.2, then X is syndetic.

Cobham's original proof of Theorem 1.1 appeared in [START_REF] Cobham | On the base-dependence of sets of numbers recognizable by finite automata[END_REF] and we quote [START_REF] Eilenberg | Automata, Languages, and Machines[END_REF] "The proof is correct, long and hard. It is a challenge to find a more reasonable proof of this fine theorem". Then G. Hansel proposed a simpler presentation in [START_REF] Hansel | A propos d'un théorème de Cobham[END_REF], also one can see [START_REF] Perrin | Finite automata[END_REF] or the dedicated chapter in [START_REF] Allouche | Automatic Sequences, Theory, Applications, Generalizations[END_REF] for an expository presentation. Prior to these last two references, one should read [START_REF] Rigo | A note on syndeticity, recognizable sets and Cobham's theorem[END_REF]. Usually a first step to prove Cobham's theorem is to show the syndeticity of the considered set. See Section 5.3.

Automatic sequences

As explained in Corollary 3.3 presented in this section, the formalism of k-recognizable sets is equivalent to the one of k-automatic sequences2 . Let us recall briefly what they are.

An infinite word x = (x n ) n 0 ∈ B N over an alphabet B is said to be k-automatic if there exists a DFAO (deterministic finite automaton with output) over the alphabet

[[0, k -1]], (Q, [[0, k -1]],
•, q 0 , B, τ ) such that, for all n 0,

x n = τ (q 0 • rep k (n)) .
The transition function is

• : Q × [[0, k -1]] → Q and can easily be extended to Q × [[0, k -1]] * by q • ε = q and q • wa = (q • w) • a. The output function is τ : Q → B.
Roughly speaking, the nth term of the sequence is obtained by feeding a DFAO with the k-ary representation of n. For a complete and comprehensive exposition on kautomatic sequences and their applications see the book [START_REF] Allouche | Automatic Sequences, Theory, Applications, Generalizations[END_REF]. We equally use the terms of sequences or (right-) infinite words. For more information about combinatorics on words, see [START_REF] Lothaire | Combinatorics on Words[END_REF][START_REF] Lothaire | Algebraic Combinatorics on Words, volume 90 of Encyclopedia of Mathematics and Its Applications[END_REF] or also J. Cassaigne and F. Nicolas' chapter in [START_REF] Berthé | Combinatorics, Automata and Number Theory[END_REF]Chapter 4]. Definition 3.1. Let σ : A * → A * be a morphism, i.e., σ(uv) = σ(u)σ(v) for all u, v ∈ A * . Naturally such a map can be defined on A ω . A finite or infinite word x such that σ(x) = x is said to be a fixed point of σ. A morphism σ : A * → A * is completely determined by the images of the letters in A. In particular, if there exists k 0 such that for all a ∈ A, |σ(a)| = k, then σ is said to be of k-uniform or simply uniform. A 1-uniform morphism is called a coding. If there exist a letter a ∈ A and a word u ∈ A + such that σ(a) = au and moreover, if lim n→+∞ |σ n (a)| = +∞, then σ is said to be prolongable on a or to be a substitution. Let σ : A * → A * be a morphism prolongable on a. We have

σ(a) = a u, σ 2 (a) = a u σ(u), σ 3 (a) = a u σ(u) σ 2 (u), . . . .
Since for all n ∈ N, σ n (a) is a prefix of σ n+1 (a) and because |σ n (a)| tends to infinity when n → +∞, the sequence (σ n (a)) n 0 converges (for the usual product topology on words, see for instance (6.2)) to an infinite word denoted by σ ∞ (a) and given by

σ ∞ (a) := lim n→+∞ σ n (a) = a u σ(u) σ 2 (u) σ 3 (u) • • • .
This infinite word is a fixed point of σ. An infinite word obtained in this way by iterating a prolongable morphism is said to be purely substitutive (or pure morphic). If σ : A * → B * is a non-erasing morphism, it can be extended to a map from A N to B N as follows. If x = x 0 x 1 • • • is an infinite word over A, then the sequence of words (σ(x 0 • • • x n-1 )) n 0 is easily seen to be convergent towards an infinite word over B. Its limit is denoted by σ

(x) = σ(x 0 )σ(x 1 )σ(x 2 ) • • • . If x ∈ A N is
purely substitutive and if τ : A → B is a coding, then the word y = τ (x) is said to be substitutive.

Another result due to A. Cobham is the following one, see [START_REF] Cobham | Uniform tag sequences[END_REF]. The idea is to canonically associated with any k-uniform morphism a DFA over

[[0, k -1]]. Theorem 3.1. Let k 2. A sequence x = (x n ) n 0 ∈ B N is k-automatic if and only if there exists a k-uniform morphism σ : A * → A * prolongable on a letter a ∈ A and a coding τ : A → B such that x = τ (σ ∞ (a)). Theorem 3.2 (Eilenberg [51]). A sequence x = (x n ) n 0 is k-automatic if and only if its k-kernel N k (x) = {(x k e n+d ) n 0 | e 0, 0 d < k e } is finite. Definition 3.2. The characteristic sequence ½ X ∈ {0, 1} N of a set X ⊆ N is defined by ½ X (n) = 1 if and only if n ∈ X.
An infinite word x ∈ A ω is ultimately periodic if there exist two finite words u ∈ A * and v ∈ A + such that x = uv ω . If u = ε, x is periodic. Obviously, a set X ⊆ N is ultimately periodic if and only if ½ X is an ultimately periodic word over {0, 1}. In that case, there exist two finite words u ∈ {0, 1} * and v ∈ {0, 1} + such that ½ X = uv ω . In particular, |v| is a period of X. If u and v are chosen of minimal length, then |u| (resp. |v|) is said to be the preperiod or index of X (resp. the period of X). If u = ε, X is (purely) periodic. Periodic sets are in particular ultimately periodic.

Corollary 3.3. Let k 2. If x = (x n ) n 0 ∈ B N is a k-automatic sequence then, for all b ∈ B, the set {n 0 | x n = b} is k-recognizable. Conversely, if a set X ⊆ N is k-recognizable, then its characteristic sequence is k-automatic. Theorem 3.4 (Cobham's theorem, version 2). Let k, ℓ
2 be two multiplicatively independent integers. An infinite word x = (x n ) n 0 ∈ B N is both k-automatic and ℓautomatic if and only if it is ultimately periodic. Remark 3.5. Using the framework of k-automatic sequences instead of the formalism of k-recognizable sets turns out to be useful. For instance, consider the complexity function of an infinite word x which maps n ∈ N onto the number p x (n) of distinct factors of length n occurring in x. Morse-Hedlund's theorem states that x is ultimately periodic if and only if p x is bounded by some constant. This result appeared first in [START_REF] Morse | Symbolic dynamics[END_REF]. Proofs can be found in classical textbooks like [START_REF] Allouche | Automatic Sequences, Theory, Applications, Generalizations[END_REF][START_REF] Lothaire | Combinatorics on Words[END_REF].

It is also well known that for a k-automatic sequence x, p x ∈ O(n), again see the seminal paper [START_REF] Cobham | Uniform tag sequences[END_REF]. This latter result can be used to show that particular sets are not krecognizable for any k 2: for instance, those sets whose characteristic sequence ½ X has a complexity function such that lim n→+∞ p ½X (n)/n = +∞. For the behavior of p x in the substitutive case, see the survey [START_REF] Allouche | Sur la complexité des suites infinies[END_REF] or [START_REF] Berthé | Combinatorics, Automata and Number Theory[END_REF]Chapter 4].

Example 3.1. Iterating the morphism σ : 0 → 01, 1 → 10, we get the Thue-Morse word

(t n ) n 0 = σ ∞ (0) = 0110100110010110100101100110 • • •.
For an account on this celebrated word, see [START_REF] Allouche | The ubiquitous Prouhet-Thue-Morse sequence[END_REF] and [START_REF] Fogg | Substitutions in dynamics, arithmetics and combinatorics[END_REF]Chapter 2]. It is a 2-automatic word, the nth letter in the word is 0 if and only if rep 2 (n) contains an even number of 1's. This word is generated by the DFAO represented in Figure 2. In particular, the set

0 1 0 0 1 1 Figure 2.
A DFAO generating the Thue-Morse word.

X 2 = n ∈ N | rep 2 (n) = c t • • • c 0 and t i=0 c i ≡ 0 (mod 2)
is 2-recognizable. The Thue-Morse word is not ultimately periodic (see for instance [START_REF] Brlek | Enumeration of factors in the Thue-Morse word[END_REF] or [START_REF] De Luca | Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups[END_REF] where the complexity function of this word is studied carefully) and therefore X 2 is k-recognizable only for those k of the form 2 m , m ∈ N 1 . Nevertheless, one can notice that X 2 is syndetic.

Multidimensional extension and first order logic 4.1 Subsets of N d

To extend the concept of k-recognizability to subsets of N d , d 2, it is natural to consider d-tuples of k-ary representations. To get d words of the same length that have to be read simultaneously by an automaton, the shortest ones are padded with leading zeroes. We extend the definition of rep k to a map of domain N d as follows. If n 1 , . . . , n d are nonnegative integers, we consider the word

rep k (n 1 , . . . , n d ) :=    0 m-| rep k (n1)| rep k (n 1 )
. . .

0 m-| rep k (n d )| rep k (n d )    ∈ [[0, k -1]] d * where m = max{| rep k (n 1 )|, . . . , | rep k (n d )|}. A subset X of N d is k-recognizable if the corresponding language rep k (X) is accepted by a finite automaton over the alphabet [[0, k -1]] d which is the Cartesian product of d copies of [[0, k -1]
]. This automaton is reading d digits at a time (one for each component): this is why we need d words of the same length.

Example 4.1. Consider the automaton depicted in Figure 3 (the sink is not represented). It accepts (ε, ε) and all pairs of words of the kind (u0, 0u) where u ∈ 1{0, 1} * . This means that the set

{(2n, n) | n 0} is 2-recognizable. 0 0 1 1 1 0 0 1 1 0 Figure 3. A DFA recognizing {(2n, n) | n 0}.
Note that the notion of k-automatic sequence and Theorem 3.1 have been extended accordingly in [START_REF] Salon | Suites automatiques à multi-indices[END_REF][START_REF] Salon | Suites automatiques à multi-indices et algébricité[END_REF] where the images by a morphism of letters are d-dimensional cubes of size k.

Extending the concept of ultimately periodic sets to subsets of N d , with d 2, is at first glance not so easy. We use bold face letters to represent elements in N d . For instance, one could take the following definition of a (purely) periodic subset X ⊆ N d . There exists a non-zero element p ∈ N d such that x ∈ X if and only if x + p ∈ X. As we will see (Remark 4.2, Proposition 6.9 and Theorem 6.11), it turns out that this definition does not fit to the extension of Cobham's theorem in d dimensions. Therefore we will consider sets definable in N, + . Let us mention Nivat's conjecture connecting such a notion of periodicity in higher dimensions with the notion of block complexity as introduced in Remark 3.5: let X ⊂ Z 2 , if there exist positive integers n 1 , n 2 such that p X (n 1 , n 2 ) n 1 n 2 then X is periodic, where p X (n 1 , n 2 ) counts the number of distinct blocks of size n 1 × n 2 occurring in X. See [START_REF] Nivat | invited talk at ICALP[END_REF] and in particular [START_REF] Quas | Periodicity and local complexity[END_REF] for details and pointers to the existing bibliography.

Logic and k-definable sets

The formalism of first order logic is probably the best suited to present a natural extension (in the sense of Cobham's theorem) of the definition of ultimately periodic sets in d dimensions. See [START_REF] Presburger | Über die volständigkeit eines gewissen systems der arithmetik ganzer zahlen, in welchem die addition als einzige operation hervortritt[END_REF][START_REF] Presburger | On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation[END_REF] or the survey [START_REF] Bès | A survey of arithmetical definability[END_REF]. In the Presburger arithmetic N, + , the variables range over N and we have at our disposal the connectors ∧, ∨, ¬, →, ↔, the equality symbol = and the quantifiers ∀ and ∃ that can only be applied to variables. This is the reason we speak of first order logic; in second order logic, quantifiers can be applied to relations, and in monadic second order logic, only variables and unary relations, i.e., sets, may be quantified. If a variable is not within the scope of any quantifier, this variable is said to be free. Formulas are build inductively from terms and atomic formulas. Here details have been omitted, see for instance [START_REF] Bruyère | Logic and p-recognizable sets of integers[END_REF]Section 3.1]. For instance, order relations <, , and > can be added to the language by noticing that x y is equivalent to

(∃z)(y = x + z). (4.1)
In the same way, constants can also be added. For instance, x = 0 is equivalent to (∀y)(x y) and x = 1 is equivalent to ¬(x = 0) ∧ (∀y)(¬(y = 0) → (x y)). In general, the successor function S(x) = y of x is defined by

(x < y) ∧ (∀z)((x < z) → (y z)) .
For a complete account on the interactions between first order logic and k-recognizable sets, see the excellent survey [START_REF] Bruyère | Logic and p-recognizable sets of integers[END_REF].

Remark 4.1. We mainly discuss the case N, + but all developments can be made for Z, +, . Note that if the variables belong to Z then it is no longer possible to define as in (4.1). So this order relation has to be added to the structure. The constant 0 can be defined by x + x = x.

Let ϕ(x 1 , . . . , x d ) be a formula with d free variables x 1 , . . . , x d . Interpreting ϕ in N, + permits one to define the set of d-tuples of non-negative integers for which the formula holds true:

{(r 1 , . . . , r d ) | N, + |= ϕ[r 1 , . . . , r d ]}. We write N, + |= ϕ[r 1 , . . . , r d ] if ϕ(x 1 , . . . , x d ) is satisfied in N, + when interpreting
x i by r i for all i ∈ {1, . . . , d}. For the reader having no background in logic and model theory, the first chapters of [START_REF] Ebbinghaus | Mathematical logic. Undergraduate Texts in Mathematics[END_REF] are worth reading.

Remark 4.2. The ultimately periodic sets of N are exactly the sets that are definable in the Presburger arithmetic. It is obvious that ultimately periodic sets of N are definable. For instance, the set of even integers can be defined by ϕ(x) ≡ (∃y)(x = y + y). Since constants can easily be defined, it is easy to write a formula for any arithmetic progression. As an example, the formula ϕ(x) ≡ (∃y)(x = S(S(y + y + y))) defines the progression 3N + 2. In particular, multiplication by a fixed constant is definable in N, + . Note that it is a classical result that the theory of N, +, × is undecidable, see for instance [START_REF] Bès | An extension of the Cobham-Semënov theorem[END_REF].

Adding congruences modulo any integer m permits quantifier elimination, which means that any formula expressed in the Presburger arithmetic is equivalent to a formula using only ∧, ∨, =, < and congruences, see [START_REF] Presburger | Über die volständigkeit eines gewissen systems der arithmetik ganzer zahlen, in welchem die addition als einzige operation hervortritt[END_REF][START_REF] Presburger | On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation[END_REF]. Presentations can also be found in [START_REF] Enderton | A mathematical introduction to logic[END_REF][START_REF] Latour | Presburger Arithmetic: from Automata to Formulas[END_REF]. (Presburger). The structure N, +, <, (≡ m ) m>0 admits elimination of quantifiers.

Theorem 4.3
This result can be used to prove that the theory of N, + is decidable. This can be done using the formalism of automata, see for instance [START_REF] Bruyère | Logic and p-recognizable sets of integers[END_REF].

Let k

2. We add to the structure N, + a function V k defined by V k (0) = 1 and for all x > 0, V k (x) is the greatest power of k dividing x. As an example, we have

V 2 (6) = 2, V 2 (20) = 4 and V 2 (2 n ) = 2 n for all n 0.
Again the theory of N, +, V k can be shown to be decidable [START_REF] Bruyère | Logic and p-recognizable sets of integers[END_REF]. The next result shows that, as for the kautomatic sequences, the logical framework within the richer structure N, +, V k gives an equivalent presentation of the k-recognizable sets in any dimension. Proofs of the next three theorems can again be found in [START_REF] Bruyère | Logic and p-recognizable sets of integers[END_REF] where a full account of the different approaches used to prove Theorem 4.5 is presented. For Büchi's original paper, see [START_REF] Büchi | Weak secord-order arithmetic and finite automata[END_REF]. Theorem 4.5 (Büchi's theorem). Let k 2 and d 1. A set X ⊆ N d is k-recognizable if and only if it can be defined by a first order formula ϕ(x 1 , . . . , x d ) of N, +, V k .

For instance the set P 2 introduced in Example 2.2 can be defined by the formula ϕ(x) ≡ V 2 (x) = x. Note that Theorem 4.5 holds for Pisot numeration systems given in Definition 2.3, see [START_REF] Bruyère | Bertrand numeration systems and recognizability[END_REF] where the function V k is modified accordingly. This is partially based on the fact that in a Pisot numeration system the normalization function is realized by a finite automaton, see [START_REF] Frougny | Representations of numbers and finite automata[END_REF], which allows one to consider addition of integers: first perform addition digit-wise without any carry, then normalize the result.

Theorem 4.6 (Cobham's theorem, version 3). Let k, ℓ

2 be two multiplicatively independent integers. A set X ⊆ N can be defined by a first order formula in N, +, V k and by a first order formula in N, +, V ℓ if and only if it can be defined by a first order formula in N, + . This theorem still holds in higher dimensions and is called the Cobham-Semenov theorem. In this respect, the notion of subset of N d definable in the Presburger arithmetic N, + is the right extension of periodicity in a multidimensional setting. For Semenov's original paper, see [START_REF] Semenov | The Presburger nature of predicates that are regular in two number systems[END_REF]. Theorem 4.7 (Cobham-Semenov theorem). Let k, ℓ 2 be two multiplicatively independent integers. A set X ⊆ N d can be defined by a first order formula in N, +, V k and by a first order formula in N, +, V ℓ if and only if it can be defined by a first order formula in N, + .

Subsets of N d defined by a first order formula in N, + are characterized in [START_REF] Ginsburg | Semigroups, Presburger formulas, and languages[END_REF]. The nice criterion of Muchnik appeared first in 1991 and is given in [START_REF] Muchnik | The definable criterion for definability in Presburger arithmetic and its applications[END_REF]. See Proposition 6.9 for its precise statement. Using this latter characterization, a proof of Theorem 4.7 is presented in [START_REF] Bruyère | Logic and p-recognizable sets of integers[END_REF]. The logical framework has given rise to several works. Let us mention chronologically [START_REF] Villemaire | Joining kand l-recognizable sets of natural numbers[END_REF][START_REF] Villemaire | The theory of N, +, V k , V l is undecidable[END_REF] and [START_REF] Michaux | Cobham's theorem seen through Büchi's theorem[END_REF][START_REF] Michaux | Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems[END_REF]. In [89, Section 5] the authors interestingly show how to reduce Semenov's theorem to Cobham's theorem: "Nothing new in higher dimensions". Also extensions to non-standard numeration systems are considered in [START_REF] Point | On the Cobham-Semenov theorem[END_REF] and [START_REF] Bès | An extension of the Cobham-Semënov theorem[END_REF]. In this latter paper, the Cobham-Semenov theorem is proved for two Pisot numeration systems.

Numeration systems and substitutions

Substitutive sets and abstract numeration systems

In Sections 4.1 and 4.2, we have mainly extended the notion of recognizability to subsets of N d . Now we consider another extension of recognizability. In Corollary 3.3, we have seen that a k-recognizable set has a characteristic sequence generated by a uniform substitution and the application of an extra coding. It is pretty easy to define sets of integers encoded by a characteristic sequence generated by an arbitrary substitution and an extra coding, that is whose characteristic sequence is morphic. This generalization permits one to reach a larger class of infinite words, hence a larger class of sets of integers.

(n + 1)st b in σ ∞ (a) is 2n + 1. Hence τ (σ ∞ (a))
is the characteristic sequence of the set of squares and it is substitutive. From Corollary 2.9 the set of squares is never k-recognizable for any integer base k. Definition 5.1. As a natural extension of the concept of recognizability, we may consider sets X ⊆ N having a characteristic sequence ½ X which is (purely) substitutive. Such a set is said to be a (purely) substitutive set. In particular k-recognizable sets are substitutive. With Theorem 5.2 it will turn out that the formalism of substitutive sets is equivalent to the one of abstract numeration systems. Definition 5.2. [START_REF] Lecomte | Numeration systems on a regular language[END_REF] An abstract numeration system or ANS is a triple S = (L, A, <) where L is an infinite regular language over a totally ordered alphabet (A, <). The map rep S : N → L is the one-to-one correspondence mapping n ∈ N onto the (n + 1)th word in the genealogically ordered language L, which is called the S-representation of n. In particular, a set X ⊆ N is S-recognizable, if rep S (X) is regular, and, N is trivially S-recognizable because rep S (N) = L. Recall that in the genealogical order (also called radix or military order), words are first ordered by increasing length and for words of the same length, one uses the lexicographic ordering induced by the order < on A.

Example 5.2. Consider the language L = a * b * ∪ a * c * with a < b < c. The first words in L are ε, a, b, c, aa, ab, ac, bb, cc, aaa, aab, aac, abb, . . .. This means that for the ANS S built on L, 0 is represented by ε, 1 by a, 2 by b, 3 by c, 4 by aa, etc. Since L contains exactly 2n + 1 words of length n for all n 0, we have that n 2 is represented by a n for all n 0. In particular, the set {n 2 | n 0} is S-recognizable because a * is regular. It is well known that in a regular language L, the set of the first words of each length in the genealogically ordered language L is regular, see [START_REF] Shallit | Numeration systems, linear recurrences, and regular sets[END_REF].

Pisot numeration systems are special cases of ANS. Indeed, if the numeration basis U = (U n ) n 0 defines a Pisot numeration system, then rep U (N) is regular.

Example 5.3. Consider the Fibonacci sequence and the language L = 1{0, 01} * ∪ {ε} defined in Example 2.1. To get the representation of an integer n, one can either decompose n using the greedy algorithm or, order genealogically the words in L and take the (n + 1)th element. Theorem 5.1. [START_REF] Lecomte | Numeration systems on a regular language[END_REF] Let S = (L, A, <) be an abstract numeration system. Any ultimately periodic set is S-recognizable.

Note that in [START_REF] Krieger | Decimations of languages and state complexity[END_REF], it is in particular proved that this latter result cannot be extended to context-free languages. Specific cases of S-recognizable sets are discussed in P. Lecomte and M. Rigo's chapter in [START_REF] Berthé | Combinatorics, Automata and Number Theory[END_REF]Chapter 3]. We have an extension of Theorem 3.1.

Theorem 5.2. Let x = (x n ) n 0 be an infinite word over an alphabet B. This word is substitutive if and only if there exists an abstract numeration system S = (L, A, <) such that x is S-automatic, i.e., there exists a DFAO (Q, A, •, {q 0 }, B, τ ) such that for all n 0, x n = τ (q 0 • rep S (n)).

A proof of this result is given in [START_REF] Rigo | Generalization of automatic sequences for numeration systems on a regular language[END_REF][START_REF] Rigo | More on generalized automatic sequences[END_REF] and a comprehensive treatment is given in [START_REF] Berthé | Combinatorics, Automata and Number Theory[END_REF]Chapter 3]. In that context, we also obtain an extension of Corollary 3.3.

Corollary 5.3. Let x = (x n ) n 0 be an infinite substitutive word over an alphabet B.

There exists an ANS S such that for all b ∈ B, {n

0 | x n = b} is S-recognizable. Conversely, if a set X ⊆ N is S-recognizable, then its characteristic sequence is S- automatic.
Corollary 5.4. A set X ⊆ N is substitutive if and only if there exists an ANS S such that X is S-recognizable.

Cobham's theorem for substitutive sets

In the context of substitutive sets of integers, how could a Cobham-like theorem be expressed, i.e., what is playing the role of a base? Assume that there exist two purely substitutive infinite words x ∈ A ω and y ∈ B ω respectively generated by the morphisms σ : A * → A * prolongable on a ∈ A and τ : B * → B * prolongable on b ∈ B, i.e., σ ∞ (a) = x and τ ∞ (b) = y. Consider two codings λ : A → {0, 1} and µ : B → {0, 1} such that λ(x) = µ(y). This situation corresponds to the case where a set (here, given by its characteristic word) is recognizable in two a priori different numeration systems.

If A = B and τ = σ m for some m 1, nothing particular can be said about the infinite word λ(x): iterating σ or σ m from the same prolongable letter leads to the same fixed point. So we must introduce a notion analogous to the one of multiplicatively independent bases related to the substitutions σ and λ. A square matrix M ∈ R n×n with entries in R 0 is irreducible if, for all i, j, there exists k such that (M k ) i,j > 0. A square matrix M ∈ R n×n with entries in R 0 is primitive if there exists k such that, for all i, j, we have (M k ) i,j > 0. Similarly, a substitution over the alphabet A is irreducible (resp. primitive) if its incidence matrix is irreducible (resp. primitive). Otherwise stated, a substitution σ : A * → A * is primitive, if there exists an integer n 1 such that, for all a ∈ A, all the letters in A appear in the image of σ n (a).

Let us denote by P the abelianisation map (or Parikh map) which maps a word w over A = {a 1 , . . . , a r } on the r-tuple t (|w| a1 , . . . , |w| ar ). The matrix M σ can be defined by its columns:

M σ = P(σ(a 1 )) • • • P(σ(a r )) ,
and it satisfies: for all w ∈ A * , P(σ(w)) = M σ P(w) .

Remark 5.5. If a matrix M is primitive, the celebrated theorem of Perron can be used, see standard textbooks like [START_REF] Horn | Matrix analysis[END_REF] or [START_REF] Gantmacher | The Theory of Matrices[END_REF][START_REF] Seneta | Non-negative matrices and Markov chains[END_REF]. A presentation is also given in [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF]. To recap some of the key points, M has a unique dominating real eigenvalue β > 0 and there exists an eigenvector with positive entries associated with β. Also, for all i, j, there exists Hence, for all n 0, |σ n (a j )| is obtained by summing up the entries in the jth column of M n σ . If σ is primitive then there exists some C j such that |σ n (a j )| = C j β n + o(β n ). In particular, if σ is prolongable on a, then |σ n (a)| ∼ Cβ n , for some C > 0.

c i,j such that (M n ) i,j = c i,j β n + o(β n ).
In the general case of a matrix M with non-negative entries, one can use the Perron-Frobenius theorem for each of the irreducible components of M (they correspond to the strongly connected components of the associated graph, also called communicating classes). Thus any non-negative matrix M has a real eigenvalue α which is greater or equal to the modulus of any other eigenvalue. We call α the dominating eigenvalue of M. Moreover, if we exclude the case where α = 1, then there exists a positive integer p such that M p has a dominating eigenvalue α p which is a Perron number, see [83, p. 369]. A Perron number is an algebraic integer α > 1 such that all its algebraic conjugates have modulus less than α. In particular, if we replace a prolongable substitution σ such that M σ has a dominating eigenvalue α > 1, with a convenient power σ p of σ, we can assume that the dominating eigenvalue of σ is a Perron number. Definition 5.4. Let σ : A * → A * be a substitution prolongable on a ∈ A such that all letters of A have an occurrence in σ ∞ (a). Let α > 1 be the dominating eigenvalue of the incidence matrix of σ. Let φ : A → B * be a coding. We say φ(σ ∞ (a)) is an α-substitutive infinite word (with respect to σ). In view of Definition 5.1, this notion can be applied to subsets of N. If moreover σ is primitive, then φ(σ ∞ (a)) is said to be a primitive α-substitutive infinite word (w.r.t. σ).

Observe that k-automatic infinite words are k-substitutive infinite words.

Example 5.4. Consider the substitution σ defined by σ(a) = aa0a, σ(0) = 01 and σ(1) = 10. Its dominating eigenvalue is 3. It is prolongable both on a, 0 and 1. The fixed point x of σ starting with 0 is the Thue-Morse sequence (see Example 3.1). Definition 5.4 does not implies that x is 3-substitutive because a does not appear in x. But the fixed point y of σ starting with a is 3-substitutive.

Example 5.5. Consider the so-called Tribonacci word, which is the unique fixed point of σ : a → ab, b → ac, c → a. See [START_REF] Tan | Some properties of the Tribonacci sequence[END_REF][START_REF] Fogg | Substitutions in dynamics, arithmetics and combinatorics[END_REF]. The incidence matrix of σ is

M σ =   1 1 1 1 0 0 0 1 0   .
One can check that M 3 σ contains only positive entries. So the matrix is primitive. Let α T ≃ 1.839 be the unique real root of the characteristic polynomial -

X 3 + X 2 + X + 1 of M σ . The Tribonacci word T = abacabaab • • • is primitive α T -substitutive. Let τ : a → 1,
b, c → 0 be a coding. The word τ (T ) is the characteristic sequence of a primitive α T -substitutive set of integers {0, 2, 4, 6, 7, . . .}.

To explain the substitutive extension of Cobham's theorem we need the following definition.

Definition 5.5. Let S be a set of prolongable substitutions and x be an infinite word. If x is an α-substitutive infinite word w.r.t. a substitution σ belonging to S, then x is said to be α-substitutive with respect to S.

Let us consider the following Cobham-like statement depending on two sets S and S ′ of prolongable substitutions. It is useful to describe chronologically known results generalizing Cobham's theorem in terms of substitutions leading to the most general statement for all substitutions.

Statement (S, S ′ ). Let S and S ′ be two sets of prolongable substitutions. Let α and β be two multiplicatively independent Perron numbers. Let x ∈ A ω where A is a finite alphabet. Then the following are equivalent:

(1) the infinite word x is both α-substitutive w.r.t. S and β-substitutive w.r.t. S ′ ;

(2) the infinite word x is ultimately periodic.

Note that this statement excludes 1-substitutions, i.e., substitutions with a dominating eigenvalue equal to 1, because Perron numbers are larger than 1. The case of 1-substitutive infinite words will be mentioned in Subsection 5.6. Also notice that the substitutions we are dealing with can be erasing, i.e., at least one letter is sent onto the empty word. But from a result in [START_REF] Cobham | On the Hartmanis-Stearns problem for a class of tag machines[END_REF][START_REF] Allouche | Automatic Sequences, Theory, Applications, Generalizations[END_REF][START_REF] Honkala | On the simplification of infinite morphic words[END_REF], we can assume that the substitutions are non-erasing. Note that α and α k are multiplicatively dependent. Proposition 5.6. [START_REF] Durand | Syndeticity and independent substitutions[END_REF] Let x be an α-substitutive infinite word. Then, there exists an integer k 1 such that x is α k -substitutive with respect to a non-erasing substitution.

The implication (2) ⇒ (1) in the above general statement is not difficult to obtain as mentioned in Remark 1.3 for the uniform situation. Proposition 5.7. [START_REF] Durand | A theorem of Cobham for non primitive substitutions[END_REF] Let x be an infinite word over a finite alphabet and α be a Perron number. If x is periodic (resp. ultimately periodic) then x is primitive α-substitutive (resp. α-substitutive). Definition 5.6. Let σ : A * → A * and τ : B * → B * be two substitutions. We say that σ projects on τ if there exists a coding φ : A → B such that

φ • σ = τ • φ .
(5.

2)

The implication (1) ⇒ (2) in Statement (S, S ′ ) is known in many cases described below:

(i) When S = S ′ is the set of uniform substitutions, this is the classical theorem of Cobham. (ii) In [START_REF] Fabre | Une généralisation du théorème de Cobham[END_REF] S. Fabre proves the statement when S is the set of uniform substitutions and S ′ is a set of non-uniform substitutions related to some non-standard numeration systems. (iii) When S = S ′ is the set of primitive substitutions, the statement is proved in [START_REF] Durand | A generalization of Cobham's theorem[END_REF].

The proof is based on a characterization of primitive substitutive sequences using the notion of return word [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF]. (iv) When S = S ′ is the set of substitutions projecting on primitive substitutions, the statement is proved in [START_REF] Durand | Sur les ensembles d'entiers reconnaissables[END_REF]. This result is applied to generalize (ii). Using a characterization of U -recognizable sets of integers for a Bertrand numeration basis U

[54], the main result of [START_REF] Durand | Sur les ensembles d'entiers reconnaissables[END_REF] extends Cobham's theorem for some large family of non-standard numeration systems. This latter result includes a result obtained previously in [START_REF] Bès | An extension of the Cobham-Semënov theorem[END_REF] for Pisot numeration systems. (v) Definition 5.8 and Theorem 5.17 describe the situation where S = S ′ = S good (defined later). It includes all known and previously described situations for substitutions. (vi) In [START_REF] Durand | Cobham's theorem for substitutions[END_REF], Statement (S, S ′ ) is proven for the most general case that is S and S ′ are both the set of all substitutions. The final argument is based on a fine study of return words for non-primitive substitutive sequences.

Example 5.6. The Tribonacci word T is purely substitutive but is k-automatic for no integer k 2. Proceed by contradiction. Assume that there exists an integer k 2 such that T is k-automatic. Then T is both k-substitutive and primitive α T -substitutive. By Theorem 5.17, T must be ultimately periodic but it is not the case. The factor complexity of T is p T (n) = 2n + 1. By the Morse-Hedlund theorem, see Remark 3.5, T is not ultimately periodic.

Let L(x) be the set of all factors of the infinite word x. In [START_REF] Fagnot | Sur les facteurs des mots automatiques[END_REF], the following generalization of Cobham's theorem is proved. Theorem 5.8. Let k, ℓ 2 be two multiplicatively independent integers. Let x be a kautomatic infinite word and y be a ℓ-automatic infinite word. If L(x) ⊂ L(y), then x is ultimately periodic.

The same result is valid in the primitive case. Theorem 5.9. [START_REF] Durand | A generalization of Cobham's theorem[END_REF] Let x and y be respectively a primitive α-substitutive infinite word and a primitive β-substitutive infinite word such that L(x) = L(y). If α and β are multiplicatively independent, then x and y are periodic.

Note that under the hypothesis of Theorem 5.9 x and y are primitive substitutive infinite words. Thus L(x) = L(y) whenever L(x) ⊂ L(y). Observe that if y is the fixed point starting with a and x the fixed point starting with 0 of the substitution σ defined in Example 5.4, then L(x) ⊂ L(y) but x is not ultimately periodic.

In Sections 5.3 and 5.4 we give the main arguments to prove Statement (S good , S good ).

Density, syndeticity and bounded gaps

The proofs of most of the generalizations of Cobham's theorem are divided into two parts.

(i) Dealing with a subset X of integers, we have to prove that X is syndetic. Equivalently, dealing with an infinite word x, we have to prove that the letters occurring infinitely many times in x appear with bounded gaps. (ii) In the second part of the proof, the ultimate periodicity of X or x has to be carried out.

This section is devoted to the description of the main arguments that lead to the complete treatment of (i).

In the original proof of Cobham one of the main arguments is that as k and ℓ are multiplicatively independent (we refer to Theorem 1.1) the set {k n /ℓ m | n, m ∈ N} is dense in [0, +∞). In the uniform case these powers refer to the length of the iterates of the substitutions. Indeed, suppose σ : A * → A * is a k-uniform substitution. Then for any a ∈ A we have |σ n (a)| = k n . Unsurprisingly, to be able to treat the non-uniform case, it is important to know that the set

| σ n (a) | | τ m (b) | | n, m ∈ N
is dense in [0, +∞), for some a, b ∈ A. We explain below that |σ n (a)| and |τ m (b)| are governed by the dominating eigenvalue of their incidence matrices. First we focus on part (i) and consider infinite words.

The length of the iterates

The length of the iterates are described in the following lemma. Note that it includes erasing substitutions and substitutions with a dominating eigenvalue equal to 1. Observe that for the substitution σ defined by 0 → 001 and 1 → 11 We say that the letters of A max are of maximal growth and that (D, Θ) is the growth type of σ. Consequently, we say that a substitutive infinite word y is (D, Θ)-substitutive if the underlying substitution is of growth type (D, Θ). Observe that, due to Lemma 5.10, any substitutive sequence is (D, Θ)-substitutive for some pair (D, Θ).

Observe that if Θ = 1, then in view of the last part of Lemma 5.10, there exists at least one non-growing letter of growth type (0, 1). Otherwise stated, if a letter has polynomial growth, then there exists at least one non-growing letter. Consequently σ is growing (i.e., all its letters are growing) if and only if θ(a) > 1 for all a ∈ A. We define

λ σ : A * → R, u 0 • • • u n-1 → n-1 i=0 c(u i ) ½ Amax (u i ) ,
where c : A → R + is defined in Lemma 5.10. From Lemma 5.10 we deduce the following lemma.

Lemma 5.11. For all u ∈ A * , we have

lim n→+∞ |σ n (u)|/n D Θ n = λ σ (u).
We say that the word u ∈ A * is of maximal growth if λ σ (u) = 0. Corollary 5.12. Let σ be a substitution of growth type (D, Θ). For all k 1, the growth type of σ k is (D, Θ k ).

Letters and words appear with bounded gaps

Recall that the first step for Cobham's theorem is to prove that the letters occurring infinitely many times appear with bounded gaps. In our context, this implies the same property for words. Moreover, we can relax the multiplicative independence hypothesis in order to include 1-substitutions. Note that 1 and α > 1 are multiplicatively dependent. The main argument used to prove this in [START_REF] Durand | Syndeticity and independent substitutions[END_REF] is the following. Sketch of the proof of Theorem 5.13. We only consider the case where α and β are multiplicatively independent. Let σ : A * → A * be a substitution prolongable on a letter a ′ having growth type (d, α). Let τ : B * → B * be a substitution prolongable on a letter b ′ having growth type (e, β). Let φ : A → C and ψ : B → C be two codings such that φ(σ ∞ (a ′ )) = ψ(τ ∞ (b ′ )) = x. Using Proposition 5.6 we may assume that σ and τ are non-erasing. Suppose there is a letter a having infinitely many occurrences in x but that appears with unbounded gaps. Then the letters in φ -1 ({a}) appear with unbounded gaps. To avoid extra technicalities (a complete treatment is considered in [START_REF] Durand | Syndeticity and independent substitutions[END_REF]), we assume that there is a letter in φ -1 ({a}) having maximal growth. Then, it is quite easy to construct, for all n ∈ N, a word w n of length c 1 n d α n , appearing in y at the index c 2 n d α n , that does not contain any letter of φ -1 ({a}). On the other hand, using a kind of pumping lemma for substitutions, one can show that there is a letter of ψ -1 ({a}) in z at the index c 3 n e β n . Therefore, using Theorem 5.14, the letter a appears in a word φ(w n ) for some n. This is not possible. Now let us explain how to extend this result for a single letter to words. It uses what is called in [START_REF] Queffélec | Substitution dynamical systems-spectral analysis[END_REF] the substitutions of the words of length n. Let u be a word of length n occurring infinitely often in x. To prove that u appears with bounded gaps in x, it suffices to prove that the letter 1 appears with bounded gaps in the infinite word t ∈ {0, 1} N defined by

t i = 1, if x i • • • x i+n-1 = u; 0, otherwise.
Let A n be the set of words of length n over A. The infinite word y

(n) = (y i • • • y i+n-1 ) i 0 over the alphabet A n is a fixed point of the substitution σ n : (A n ) * → (A n ) * defined, for all (a 1 • • • a n ) in A n , by σ n ((a 1 • • • a n )) = (b 1 • • • b n )(b 2 • • • b n+1 ) • • • (b |σ(a1)| • • • b |σ(a1)|+n-1 )
where σ(a

1 • • • a n ) = b 1 • • • b k .
For details, see Section V.4 in [START_REF] Queffélec | Substitution dynamical systems-spectral analysis[END_REF]. Let ρ : A n → A * be the coding defined by ρ((b

1 • • • b n )) = b 1 for all (b 1 • • • b n ) ∈ A n . We have ρ • σ n = σ • ρ, and then ρ • σ k n = σ k • ρ. Hence, if σ is of growth type (d, α) then y (n) is (d, α)-substitutive. Let f : A n → {0, 1} be the coding defined by f ((b 1 • • • b n )) = 1, if b 1 • • • b n = u; 0, otherwise.
It is easy to see that f (y (n) ) = t, hence t is (d, α)-substitutive. Then one proceeds in the same way with τ and uses the result for letters to conclude the proof. The substitution σ having α as dominating eigenvalue is a "good" substitution, if it has a primitive sub-substitution whose dominating eigenvalue is α. So let us stress the fact that to be a "good" substitution, the sub-substitution has to be primitive and have the same dominating eigenvalue as the original substitution. We let S good denote the set of good substitutions.

Ultimate periodicity

Remark 5.15. For all growing substitutions σ, there exists an integer k such that σ k has a primitive sub-substitution. Hence by taking a convenient power of σ, the substitution can always be assumed to have a primitive sub-substitution.

Note that primitive substitutions and uniform substitutions are good substitutions. Now consider the substitution σ : {a, 0, 1} * → {a, 0, 1} * given by σ : a → aa0, 0 → 01, 1 → 0. Its dominating eigenvalue is 2 and it has only one primitive sub-substitution (0 → 01, 1 → 0) whose dominating eigenvalue is (1 + √ 5)/2, hence it is not a good substitution.

Remark 5.16. Let σ : A * → A * and τ : B * → B * be two substitutions such that σ projects on τ , recall (5.2) for the definition of projection. There exists a coding φ :

A → B such that φ • σ = τ • φ. Note that φ • σ n = τ n • φ.
If τ is primitive, then it follows that σ belongs to S good . Theorem 5.17. Let α and β be two multiplicatively independent Perron numbers. Let x ∈ A ω where A is a finite alphabet. Then the following are equivalent:

(i) the infinite word x is both α-substitutive w.r.t. S good and β-substitutive w.r.t. S good ;

(ii) the infinite word x is ultimately periodic.

Proof. Let σ : B * → B * (resp. τ : C * → C * ) be a substitution in S good having α (resp. β) as its dominating eigenvalue and φ (resp. ψ) be a coding such that

x = φ(σ ∞ (b)) for some b ∈ B (resp. x = ψ(τ ∞ (c)) for some c ∈ C).
Let us first suppose that both substitutions are growing. In this way, taking a power if needed, we can suppose that they have primitive sub-substitutions.

By Theorem 5.13, the factors occurring infinitely many times in x appear with bounded gaps. Hence for any primitive and growing sub-substitutions σ and τ of σ and of τ respectively, we have φ(L(σ)) = ψ(L(τ )) = L. Using Theorem 5.9 it follows that L is periodic, i.e., there exists a shortest word u, appearing infinitely many times in x, such that L = L(u ω ). Thus u appears with bounded gaps. Let R u be the set of return words to u. A word w is a return word to u if wu ∈ L(x), u is a prefix of wu and u has exactly two occurrences in wu. Since u appears with bounded gaps, the set R u is finite. There exists an integer N such that all words wu ∈ L(x N x N +1 • • • ) appear infinitely many times in x for all w ∈ R u . Hence these words appear with bounded gaps in x. We set t = x N x N +1 • • • and we will prove that t is periodic. Consequently x would be ultimately periodic. We can suppose that u is a prefix of t. Then t is a concatenation of return words to u. Let w be a return word to u. It appears with bounded gaps hence it appears in some φ(σ n (a)), where σ is a primitive and growing sub-substitution, and there exist two words, p and q, and an integer i such that wu = pu i q. As |u| is the least period of L it must be that wu = u i . It follows that t = u ω .

If, for example, σ is non-growing, then a result of J.-J. Pansiot [START_REF] Pansiot | Complexité des facteurs des mots infinis engendrés par morphismes itérés[END_REF] asserts that either by modifying in a suitable way σ and φ (in that case α could be replaced by a power of α) we can suppose σ is growing or L(σ ∞ (b)) contains the language of a periodic infinite word. We have treated the first case before. For the second case it suffices to use Theorem 5.13. Suppose α and β are multiplicatively independent real numbers and that x is a αsubstitutive infinite word w.r.t. S good and y is a β-substitutive infinite word w.r.t. S good satisfying L(x) ⊂ L(y). Then the conclusion of Theorem 5.8 is far from true. It suffices to look at Example 5.4 and the observation made after Theorem 5.9.

Remark 5.18. The Statement (S, S ′ ) remains open when S is the set of substitutions which are not good. Nevertheless there are cases where we can say more. For example, if x is both α-substitutive and β-substitutive (with α and β being multiplicatively independent), and, L(x) contains the language of a periodic sequence then, from Theorem 5.13, we deduce that x is ultimately periodic.

Moreover, as we will see in the next section, this statement holds true in the purely substitutive context.

The case of fixed points

Now let restrict ourselves to the purely substitutive case. In this setting Cobham's theorem holds true. Note that in the statement of the following result, α and β are necessarily Perron numbers. Moreover, since the substitutions are growing, then α and β must be larger than one. Theorem 5.19. Let σ : A * → A * and τ : A * → A * be two non-erasing growing substitutions prolongable on a ∈ A with respective dominating eigenvalues α and β. Suppose that all letters of A appear in σ ∞ (a) and in τ ∞ (a) and that α and β are multiplicatively independent. If x = σ ∞ (a) = τ ∞ (a), then x is ultimately periodic.

Proof. Thanks to Remark 5.15, we may assume that σ has a primitive sub-substitution. Using Theorem 5.13, the letters appearing infinitely often in x appear with bounded gaps. Let σ : A → A be a primitive sub-substitution of σ. Let c ∈ A. Suppose that there exists a letter b, appearing infinitely many times in x, which does not belong to A. Then the word σ n (c) = σ n (c) does not contain b and b could not appear with bounded gaps. Consequently all letters (and in particular a letter of maximal growth) appearing infinitely often in x belong to A. Hence σ also has α as dominating eigenvalue and σ is a "good" substitution. In the same way τ is a "good" substitution. Theorem 5.17 concludes the proof.

Back to numeration systems

Let S be an abstract numeration system. There is no reason for the substitutions describing characteristic words of S-recognizable sets (see Corollary 5.4) to be primitive. To obtain a Cobham type theorem for families of abstract numeration systems, one has to interpret Theorem 5.17 in this formalism.

Polynomially growing abstract numeration systems

Here we only mention the following result. The paper [START_REF] Diekert | Some remarks about stabilizers[END_REF] is also of interest. It is well-known that the growth function counting the number of words of length n in a regular language is either polynomial, i.e., in O(n k ) for some integer k or exponential, i.e., in Ω(θ n ) for some θ > 1.

Proposition 5.20. [START_REF] Durand | Syndeticity and independent substitutions[END_REF] Let S = (L, A, <) (resp. T = (M, B, ≺)) be an abstract numeration system where L is a polynomial regular language (resp. M is an exponential regular language). A set X of integers is both S-recognizable and T -recognizable if and only if X is ultimately periodic.

Bertrand basis and ω α -substitutive words

Let U be a Bertrand numeration basis such that rep U (N) = L(α) where α is a Parry number which is not an integer. In [START_REF] Fabre | Substitutions et β-systèmes de numération[END_REF] a substitution denoted by ω α is defined. The importance of this substitution is justified by Theorem 5.21.

If d α (1) = t 1 • • • t n 0 ω , t n = 0, then ω α is defined on the alphabet {1, . . . , n} by 1 → 1 t1 2, . . . , n -1 → 1 tn-1 n, n → 1 tn . If d α (1) = t 1 • • • t n (t n+1 t n+2 • • • t n+m ) ω
, where n and m are minimal and where

t n+1 + t n+2 + • • • + t n+m = 0, then ω α is defined on the alphabet {1, • • • , n + m} by 1 → 1 t1 2, . . . , n + m -1 → 1 tn+m-1 (n + m), n + m → 1 tn+m (n + 1) .
In both cases the substitution ω α is primitive and has α as dominating eigenvalue. A substitution that projects (see Definition 5.6) on ω α is called a ω α -substitution and we call each infinite word which is the image under a coding of a fixed point of a ω α -substitution a ω α -substitutive infinite word (α-automatic infinite word in [START_REF] Fabre | Substitutions et β-systèmes de numération[END_REF]). only if its characteristic sequence ½ X is ω α -substitutive.

Remark 5.16 and Theorem 5.17 imply the following result.

Theorem 5.22. [START_REF] Durand | Sur les ensembles d'entiers reconnaissables[END_REF] Let U and V be two Bertrand numeration systems. Let α and β be two multiplicatively independent Parry numbers such that rep U (N) = L(α) and rep V (N) = L(β). A set X ⊆ N is U -recognizable and V -recognizable if and only if X is ultimately periodic.

Cobham's theorem in various contexts

Regular sequences

Regular sequences as presented in [START_REF] Allouche | The ring of k-regular sequences[END_REF][START_REF] Allouche | The ring of k-regular sequences[END_REF][START_REF] Allouche | Automatic Sequences, Theory, Applications, Generalizations[END_REF] are a generalization of automatic sequences for sequences taking infinitely many values. Many examples of such sequences are given in the first two references. Also see [START_REF] Dress | A semigroup approach to automaticity[END_REF] for a generalization of the notion of automaticity in the framework of group actions. Let R be a commutative ring. Let k 2. Consider a sequence x = (x n ) n 0 taking values in some R-module. If the R-module generated by all sequences in the k-kernel N k (x) is finitely generated (recall Theorem 3.2) then the sequence x is said to be (R, k)-regular. Theorem 6.1 ). Let R be a commutative ring 3 . Let k, ℓ be two multiplicatively independent integers. If a sequence x ∈ R N is both (R, k)-regular and (R, ℓ)-regular, then it satisfies a linear recurrence over R.

Algebraic setting and quasi-automatic functions

In [START_REF] Christol | Ensembles presque périodiques k-reconnaissables[END_REF] G. Christol characterized p-recognizable sets in terms of formal power series. Theorem 6.2. Let p be a prime number and F p be the field with p elements. A subset

A ⊂ N is p-recognizable if and only if f (X) = n∈A X n ∈ F p [[X]] is algebraic over F p (X).
This was applied to Cobham's theorem in [START_REF] Christol | Suites algébriques, automates et substitutions[END_REF] to obtain an algebraic version. Theorem 6.3. Let A be a finite alphabet, x ∈ A N , and, K 1 and K 2 be two finite fields with different characteristics. Let α 1 : A → K 1 and α 2 : A → K 2 be two one-to-one maps

. If f (X) = n∈N α 1 (x n )X n ∈ K 1 [[X]] is algebraic over K 1 (X) and f (X) = n∈N α 2 (x n )X n ∈ K 2 [[X]] is algebraic over K 2 (X) then f (X) is rational.
Quasi-automatic functions are introduced by Kedlaya in [START_REF] Kedlaya | The algebraic closure of the power series field in positive characteristic[END_REF]. Also see [START_REF] Kedlaya | Finite automata and algebraic extensions of function fields[END_REF] where Christol's theorem is generalized to Hahn's generalized power series. In this algebraic setting, an extension of Cobham's theorem is proved by Adamczewski and Bell in [START_REF] Adamczewski | Function fields in positive characteristic: expansions and Cobham's theorem[END_REF]. Details are given in the chapter "Automata in number theory" of this handbook.

Real numbers and verification of infinite-state systems

Sets of numbers recognized by finite automata arise when analyzing systems with unbounded mixed variables taking integer or real values. Therefore systems such as timed or hybrid automata are considered [START_REF] Boigelot | An improved reachability analysis method for strongly linear hybrid systems[END_REF]. One needs to develop data structures representing sets manipulated during the exploration of infinite state systems. For instance, it is often needed to compute the set of reachable configurations of such a system. Let k 2 be an integer. Considering separately integer and fractional parts, a real number x > 0 can be decomposed as

x = d i=0 c i k i + +∞ i=1 c -i k -i , c i ∈ [[0, k -1]], i d, (6.1)
and gives rise to the infinite word

c d • • • c 0 ⋆ c -1 c -2 • • • over [[0, k -1]] ∪ {⋆} which is a k-ary representation of x.
Note that rational numbers of the kind p/k n have two k-ary representations, one ending with 0 ω and one with (k -1) ω . For the representation of negative elements, one can consider base k-complements or signed number representations [START_REF] Knuth | The art of computer programming[END_REF], the sign being determined by the most significant digit which is thus 0 or k -1 (and this digit may be repeated an arbitrary number of times). For definition of Büchi and Muller automata, see the first part of this handbook. Definition 6.1. A set X ⊆ R is k-recognizable if there exists a Büchi automaton accepting all the k-ary representations of the elements in X. Such an automaton is called a Real Number Automaton or RNA.

These notions extend naturally to subsets of R d and to Real Vector Automata or RVA. Also the Büchi theorem 4.5 holds for a suitable structure R, Z, +, <, V k , see [START_REF] Boigelot | On the expressiveness of real and integer arithmetic automata[END_REF]. Theorem 6.4. [START_REF] Boigelot | An effective decision procedure for linear arithmetic over the integers and reals[END_REF] If X ⊆ R d is definable by a first-order formula in R, Z, +, < , then X written in base k 2 is accepted by a weak deterministic RVA A.

Weakness means that each strongly connected component of A contains only accepting states or only non-accepting states. Theorem 6.5. [START_REF] Boigelot | A generalization of Cobham's theorem to automata over real numbers[END_REF] Let k, ℓ 2 be two multiplicatively independent integers. If X ⊆ R is both kand ℓ-recognizable by two weak deterministic RVA, then it is definable in R, Z, +, < .

The extension of the Cobham-Semenov theorem for subsets of R d in this setting is discussed in [START_REF] Boigelot | A generalization of Semenov's theorem to automata over real numbers[END_REF], see also [START_REF] Brusten | On the sets of real vectors recognized by finite automata in multiple bases[END_REF] for a comprehensive presentation. The case of two coprime bases was first considered in [START_REF] Boigelot | A generalization of Cobham's theorem to automata over real numbers[END_REF]. Surprisingly, if the multiplicatively independent bases k, ℓ 2 share the same prime factors, then there exists a subset of R that is both kand ℓ-recognizable but not definable in R, Z, +, < , see [START_REF] Boigelot | On the sets of real numbers recognized by finite automata in multiple bases[END_REF]. This shows a main difference between recognizability of subsets of real numbers written in base k for (general) Büchi automata and weak deterministic RVA. Though written in a completely different language, a similar result was independently obtained in [START_REF] Adamczewski | An analogue of Cobham's theorem for fractals[END_REF]. This latter paper is motivated by the study of some fractal sets.

Dynamical systems and subshifts

In this section we would like to express a Cobham-type theorem in terms of dynamical systems called substitutive subshifts. Theorem 5.9 will appear as a direct corollary of these developments.

We first need some definitions.

A dynamical system is a pair (X, S) where X is a compact metric space and S a continuous map from X onto itself. The dynamical system (X, S) is minimal whenever X and the empty set are the only S-invariant closed subsets of X, that is, S(X) = X. We say that a minimal system (X, S) is periodic whenever X is finite.

Let (X, S) and (Y, T ) be two dynamical systems. We say that (Y, T ) is a factor of (X, S) if there is a continuous and onto map φ : X → Y such that φ • S = T • φ (φ is called a factor map). If φ is one-to-one we say that φ is an isomorphism and that (X, S) and (Y, T ) are isomorphic.

Let A be an alphabet. We endow A ω with the infinite product of the discrete topologies. It is a metric space where the metric is given by

d(x, y) = 1 2 n with n = inf{k | x k = y k }, (6.2)
where x = (x n ) n 0 and y = (y n ) n 0 are two elements of A ω . A subshift on A is a pair (X, T |X ) where X is a closed T -invariant subset of A ω and T is the shift transformation

T : A ω → A ω , (x n ) n 0 → (x n+1 ) n 0 .
Let u be a word over A. The set

[u] X = {x ∈ X | x 0 • • • x |u|-1 =
u} is a cylinder. The family of these sets is a base of the induced topology on X. When there is no misunderstanding, we write [u] and T instead of [u] X and T |X .

Let x ∈ A ω . The set {y ∈ A ω | L(y) ⊆ L(x)} is denoted Ω(x). It is clear that (Ω(x), T ) is a subshift. We say that (Ω(x), T ) is the subshift generated by x. When x is a sequence, we have Ω(x) = {T n x | n ∈ N}. Observe that (Ω(x), T ) is minimal if and only if x is uniformly recurrent, i.e., all its factors occur infinitely often in x and for each factor u of x, there exists a constant K such that the distance between two consecutive occurrences of u in x is bounded by K.

Let φ be a factor map from the subshift (X, T ) on the alphabet A onto the subshift (Y, T ) on the alphabet B. Here x [i,j] denotes the word x i • • • x j , i j. The Curtis-Hedlund-Lyndon theorem [83, Thm. 6.2.9] asserts that φ is a sliding block code: there exists an r-block map f :

A r → B such that (φ(x)) i = f (x [i,i+r-1]
) for all i ∈ N and x ∈ X. We shall say that f is a block map associated to φ and that f defines φ.

If u = u 0 u 1 • • • u n-1 is a word of length n r we define f (u) by (f (u)) i = f (u [i,i+r-1] ), i ∈ {0, 1, • • • , n -r + 1}. Let C denote the alphabet A r and Z = {(x [i,r+i-1] ) i 0 | (x n ) n 0 ∈ X}.
It is easy to check that the subshift (Z, T ) is isomorphic to (X, T ) and that f induces a 1-block map (a coding) from C onto B which defines a factor map from (Z, T ) onto (Y, T ).

We can now state a Cobham-type theorem for subshifts generated by substitutive sequences. Observe that it implies Theorem 5.9 and Statement (S, S ′ ) when S = S ′ is the set of primitive substitutions. Theorem 6.6. Let (X, T ) and (Y, T ) be two subshifts generated respectively by a primitive α-substitutive sequence x and by a primitive β-substitutive sequence y. Suppose (X, T ) and (Y, T ) both factorize to the subshift (Z, T ). If α and β are multiplicatively independent then (Z, T ) is periodic.

Below we give a sketch of the proof, which involves the concept of an ergodic measure. An invariant measure for the dynamical system (X, S) is a probability measure µ, on the σ-algebra B(X) of Borel sets, with µ(S -1 B) = µ(B) for all B ∈ B(X); the measure is ergodic if every S-invariant Borel set has measure 0 or 1. The set of invariant measures for (X, S) is denoted by M(X, S). The system (X, S) is uniquely ergodic if #(M(X, S)) = 1. For expository books on subshifts and/or ergodic theory, see [START_REF] Cornfeld | Ergodic theory[END_REF][START_REF] Kitchens | Symbolic dynamics. Universitext[END_REF][START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF][START_REF] Queffélec | Substitution dynamical systems-spectral analysis[END_REF][START_REF] Kůrka | Topological and symbolic dynamics[END_REF].

It is well known that the subshifts generated by primitive substitutive sequences are uniquely ergodic [START_REF] Queffélec | Substitution dynamical systems-spectral analysis[END_REF].

Let φ : X → Z and ψ : Y → Z be two factor maps. Suppose that (Z, T ) is not periodic. We will prove that α and β are multiplicatively independent.

Let µ and λ be the unique ergodic measures of (X, T ) and (Y, T ) respectively. It is not difficult to see that (Z, T ) is also generated by a primitive substitutive sequence and consequently is uniquely ergodic. Let δ be its unique ergodic measure. We notice that φµ defined by φµ(A) = µ(φ -1 (A)), for all Borel sets A of Z, and ψλ defined by ψλ(A) = µ(ψ -1 (A)), for all Borel sets A of Z, are invariant measures for (Z, T ). Hence φµ = δ = ψλ. Let us give more details about these measures in order to conclude the proof. Theorem 6.7. [START_REF] Holton | Directed graphs and substitutions[END_REF] Let (Ω, T ) be a subshift generated by a primitive purely γ-substitutive sequence and m be its unique ergodic measure. Then, the measures of cylinders in Ω lie in a finite union of geometric progressions. There exists a finite set F of positive real numbers such that {m

(C) | C cylinder of X} ⊂ n∈N γ -n F .
In conjunction with the next result and using the pigeon hole principle we will conclude the proof. Proposition 6.8. [START_REF] Durand | Linearly recurrent subshifts have a finite number of non-periodic subshift factors[END_REF] Let (Ω, T ) be a subshift generated by a primitive substitutive sequence on the alphabet A. There exists a constant K such that for any block map f :

A 2r+1 → B, we have #(f -1 ({u}))
K for all u appearing in some sequences of f (Ω).

From these last two results we deduce that there exist two sets of numbers F X and

F Y such that {δ(C) | C cylinder of Z} ={µ(φ -1 (C)) | C cylinder of Z} ={λ(ψ -1 (C)) | C cylinder of X} ⊂ n∈N α -n F X n∈N β -n F Y .
The sets F X and F Y being finite, there exist two cylinder sets U and V of Z, a ∈ F X , b ∈ F Y and n, m, r, s four distinct positive integers, such that

aα -n = δ(U ) = bβ -m and aα -r = δ(V ) = bβ -s .
Consequently α and β are multiplicatively dependent.

Tilings

From definable sets

Let A be a finite alphabet. An array in N d is a map T : N d → A. It can be viewed as a tiling of R d + . The collection of all these arrays is A N d . For all x ∈ N d , let |x| denote the sum of the coordinates of x and B(x, r) be the set

{(y 1 , . . . , y d ) ∈ N d | 0 y i -x i < r, 1 i d}.
We say T is periodic (resp. ultimately periodic) if there exists p ∈ N d such that T (x + p) = T (x) for all x ∈ N d (resp. for all large enough x). We also need another notion of periodicity. We say that Z ⊂ N d is p-periodic inside X ⊂ N d if for any x ∈ X with x + p ∈ X we have x ∈ Z if and only if x + p ∈ Z .

We say that Z is locally periodic if there exists a non-empty finite set V ⊂ N d of non-zero vectors such that for some K > max{|v| | v ∈ V } and L 0 one has:

(∀x ∈ N d , |x| L)(∃v ∈ V )(Z is v-periodic inside B(x, K)) .
Observe that for d = 1, local periodicity is equivalent to ultimate periodicity. We say T is pseudo-periodic if for all a ∈ A, T -1 (a) is locally periodic and every (d -1)-

section of T -1 (a), say S(i, n) = {x ∈ T -1 (a) | x i = n}, 1
i d and n ∈ N, is pseudo-periodic (ultimately periodic when d -1 = 1). The following criterion is due to Muchnik, see [START_REF] Muchnik | The definable criterion for definability in Presburger arithmetic and its applications[END_REF] for the proof. Proposition 6.9. Let E ⊂ N d and T : N d → {0, 1} be its characteristic function. The following are equivalent:

(i) E is definable in the Presburger arithmetic;

(ii) T is pseudo-periodic;

(iii) for all a ∈ {0, 1}, there exist n ∈ N, v i ∈ N d and finite sets

V i ⊂ N d , 0 i n such that T -1 (a) = V 0 ∪   1 i n v i + v∈Vi Nv   .
Let p be a positive integer and A be a finite alphabet. In the same way, we can define S : A B p n → A B p n+1 . We remark that S n (a) = S(S n-1 (a)) for all a ∈ A and n > 0. We say T is generated by a p-substitution if there exist a coding φ and a fixed point T 0 of a p-substitution such that T = φ • T 0 .

In [START_REF] Černý | Modular trellises[END_REF] the authors proved the following theorem, which is analogous to Theorem 3. Hence we can reformulate the Cobham-Semenov theorem as follows [START_REF] Semenov | The Presburger nature of predicates that are regular in two number systems[END_REF].

Theorem 6.11 (Cobham-Semenov theorem, Version 2). Let p and q be two multiplicatively independent integers greater or equal to 2. Then, the array T is generated by both a p-substitution and a q-substitution if and only if T is pseudo-periodic.

The equivalence between (i) and (iii) is proven in [START_REF] Hansel | Vers un théorème de Cobham pour les entiers de Gauss[END_REF] from an easy computation. The equivalence between (i) and (ii) comes from the fact that p 2 + 1 and q 2 + 1 are multiplicatively independent, see [START_REF] Hansel | Vers un théorème de Cobham pour les entiers de Gauss[END_REF]Prop. 2]. As an example, take p = 1 and p = 2. Then, a = √ 2, b = √ 5, θ = 3π 4 and φ = arctan(-1 2 ). Proving the density of D 1,2 is equivalent to proving that ln 5/ ln 2 , arctan(1/2)/π and 1 are rationally independent. In [START_REF] Hansel | Vers un théorème de Cobham pour les entiers de Gauss[END_REF] the authors observe that the Four Exponential Conjecture, see [START_REF] Waldschmidt | Diophantine approximation on linear algebraic groups[END_REF], would imply that D p,q is dense in C. Conjecture 6.15 (Four Exponential Conjecture). Let {λ 1 , λ 2 } and {x 1 , x 2 } be two pairs of rationally independent complex numbers. Then, one of the numbers e λ1x1 , e λ1x2 , e λ2x1 , e λ2x2 is transcendental.

Recognizability over F q [X]

Using the analogy existing between Z and the ring of polynomials over a finite field F q of positive characteristic, one can easily define B-recognizable sets of polynomials [START_REF] Rigo | Syntactical and automatic properties of sets of polynomials over finite fields[END_REF]. In [121] characterization of these sets in a convenient logical structure analogous to Theorem 4.5 is given. A family of sets of polynomials recognizable in all polynomial bases is described in [START_REF] Rigo | Syntactical and automatic properties of sets of polynomials over finite fields[END_REF]121]. We can again conjecture a Cobham-like theorem.

Decidability issues

So far we have seen that ultimately periodic sets have a very special status in the context of numeration systems (recall Proposition 2.6, Theorem 5.1 or Theorems 5.17 and 5.19). They can be described using a finite amount of data (two finite words for the preperiodic and the periodic parts). Let us settle down once more to the usual integer base numeration system. Let X ⊆ N be a k-recognizable set of integers given by a DFA accepting rep k (X). Is there an algorithmic decision procedure which permits one to decide for any such set X, whether or not X is ultimately periodic? For an integer base, the problem was solved positively in [START_REF] Honkala | A decision method for the recognizability of sets defined by number systems[END_REF]. The main ideas are the following ones. Given a DFA A accepting a k-recognizable set X ⊆ N, the number of states of A gives an upper bound on the possible index and period for X. Consequently, there are finitely many candidates to check. For each such pair (i, p) of candidates, produce a DFA for all possible corresponding ultimately periodic sets and compare it with A. Using non-deterministic finite automata, the same problem was solved in [START_REF] Allouche | Periodicity, repetitions, and orbits of an automatic sequence[END_REF]. With the formalism of first order logic the problem becomes trivial. If a set X ⊆ N is k-recognizable, then using Theorem 4.5 it is definable by a formula ϕ(x) in N, +, V k and X is ultimately periodic if and only if (∃p)(∃N )(∀x)(x N ∧ (ϕ(x) ↔ ϕ(x + p))). Since we have a decidable theory, it is decidable whether this latter sentence is true [START_REF] Bruyère | Logic and p-recognizable sets of integers[END_REF]Prop. 8.2]. The problem can be extended to Z d and was discussed in [START_REF] Muchnik | The definable criterion for definability in Presburger arithmetic and its applications[END_REF]. It is solved in polynomial time in [START_REF] Leroux | A polynomial time Presburger criterion and synthesis for number decision diagrams[END_REF]. In view of Theorem 5.1 the question is extended to any abstract numeration system. Let S be an abstract numeration system. Given a DFA accepting an S-recognizable set X ⊆ N. Decide whether or not X is ultimately periodic. Some special cases have been solved positively in [START_REF] Charlier | A decision problem for ultimately periodic sets in non-standard numeration systems[END_REF][START_REF] Bell | A decision problem for ultimately periodic sets in non-standard numeration systems[END_REF]. Using Corollary 5.3, the same question can be asked in terms of morphisms. Given a morphism σ : A * → A * prolongable on a letter a and a coding τ : A → B, decide whether or not τ (σ ∞ (a)) is ultimately periodic. It is the HD0L (ultimate) periodicity problem. The purely substitutive case was solved independently in [START_REF] Pansiot | Decidability of periodicity for infinite words[END_REF] and [START_REF] Harju | On the periodicity of morphisms on free monoids[END_REF]. Note that the general substitutive case is still open (one has to give a decision procedure for any abstract numeration system). Also see [START_REF] Maes | Morphisms and almost-periodicity[END_REF][START_REF] Maes | More on morphisms and almost-periodicity[END_REF] where decidability questions about almost-periodicity are considered. A word is almost periodic if factors occurring infinitely often have a bounded distance between occurrences (but some factors may occur only finitely often).

Abstract. Let k 2 be an integer. A set X of integers is k-recognizable if the language of k-ary representations of the elements in X is accepted by a finite automaton. The celebrated theorem of Cobham from 1969 states that if a set of integers is both k-recognizable and ℓ-recognizable, then it is a finite union of arithmetic progressions. We present several extensions of this result to nonstandard numeration systems, we describe the relationships with substitutive and automatic words and list Cobham-type results in various contexts.

Index

Figure 1 .

 1 Figure 1. A finite automaton accepting rep 2 (4N + 3).

Corollary 4 . 4 .

 44 Any formula ϕ(x) in the Presburger arithmetic N, + defines an ultimately periodic set of N.

Example 5 . 1 .

 51 Consider the morphism σ : {a, b, c} * → {a, b, c} * given by σ(a) = abcc, σ(b) = bcc, σ(c) = c and the coding τ : a, b → 1, c → 0. We get σ ∞ (a) = abccbccccbccccccbccccccccbccccccccccbcc • • • and τ (σ ∞ (a)) = 010010000100000010000000010000000000100 • • •. Using the special form of the images by σ of b and c, it is not difficult to see that the difference between the position of the nth b and the

Definition 5 . 3 .

 53 Let σ : A * → A * be a substitution over an alphabet A. The matrix M σ ∈ N A×A associated with σ is called the incidence matrix of σ and is defined by for all a, b ∈ A, (M σ ) a,b = |σ(b)| a .

  For instance, primitiveness of M σ implies the existence of the frequency of any factor occurring in any fixed point of σ. Note that if P(w) = t (p 1 , . . . , p r ), then |w| =

Lemma 5 . 10 (Definition 5 . 7 .

 51057 we have |σ n (0)| = (n + 2)2 n-1 and |σ n (1)| = 2 n showing that the situation is different from the uniform case. It can easily be described using the Jordan normal form of the incidence matrix M σ . Discussion of the following result can be found in[START_REF] Berthé | Combinatorics, Automata and Number Theory[END_REF] Section 4.7.3]. Chapter III.7 in[START_REF] Salomaa | Automata-theoretic aspects of formal power series[END_REF]). Let σ : A → A * be a substitution. For all a ∈ A one of the two following situations occur (1) there exists N ∈ N such that for all n > N , |σ n (a)| = 0, or, (2) there exist d(a) ∈ N and real numbers c(a), θ(a) such that lim n→+∞ |σ n (a)| c(a) n d(a) θ(a) n = 1. Moreover, in the situation (2), for all i ∈ {0, . . . , d(a)} there exists a letter b ∈ A appearing in σ j (a) for some j ∈ N and such that lim n→+∞ |σ n (b)| c(b) n i θ(a) n = 1. Let σ be a non-erasing substitution. For all a ∈ A, the pair (d(a), θ(a)) defined in Lemma 5.10 is called the growth type of a. If (d, θ) and (e, β) are two growth types, we say that (d, θ) is less than (e, β) (or (d, θ) < (e, β)) whenever θ < β or, θ = β and d < e. Consequently if the growth type of a ∈ A is less than the growth type of b ∈ A then lim n→+∞ |σ n (a)|/|σ n (b)| = 0. We say that a ∈ A is a growing letter if (d(a), θ(a)) > (0, 1) or equivalently, if lim n→+∞ |σ n (a)| = +∞. We set Θ := max{θ(a) | a ∈ A}, D := max{d(a) | ∀a ∈ A : θ(a) = Θ} and A max := {a ∈ A | θ(a) = Θ, d(a) = D}. The dominating eigenvalue of M σ is Θ.

Theorem 5 . 13 . [ 49 ]

 51349 Let d, e ∈ N \ {0} and α, β ∈ [1, +∞) such that (d, α) = (e, β) and satisfying one of the following three conditions: (i) α and β are multiplicatively independent; (ii) α, β > 1 and d = e; (iii) (α, β) = (1, 1) and, β = 1 and e = 0, or, α = 1 and d = 0. Let C be a finite alphabet. If x ∈ C ω is both (d, α)-substitutive and (e, β)-substitutive then the words occurring infinitely many times in x appear with bounded gaps.

Theorem 5 . 14 .

 514 Let d, e ∈ N and α, β ∈ [1, +∞). The set Ω = α n n d β m m e | n, m ∈ N is dense in [0, +∞) if and only if one of the following three conditions holds: (i) α and β are multiplicatively independent; (ii) α, β > 1 and d = e; (iii) β = 1 and e = 0, or, α = 1 and d = 0.

Definition 5 . 8 .

 58 Let σ : A * → A * be a substitution. If there exists a sub-alphabet B ⊆ A such that for all b ∈ B, σ(b) ∈ B * , then the substitution τ : B * → B * defined by the restriction τ (b) = σ(b), for all b ∈ B, is a sub-substitution of σ. Note that σ is in particular a sub-substitution of itself.

Theorem 5 . 21 .

 521 [54, Corollary 1] Let U be a Bertrand numeration basis such that rep U (N) = L(α) where α is a Parry number. A set X ⊂ N is U -recognizable if and

  A p-substitution (or substitution if we do not need to specify p) is a map S : A → A Bp where B p = B(0, p) = Π d i=1 {0, • • • , p -1}. The substitution S can be considered as a function from A N d into itself by setting S((T (x)) = [S(T (y))](z), for all T ∈ A N d where y ∈ N d and z ∈ B p are the unique vectors satisfying x = py + z.

We use the terminology of regular language, instead of rational language.

We indifferently use the terms sequence and infinite word.

Note that in[START_REF] Allouche | The ring of k-regular sequences[END_REF] the ground ring R is assumed to be Noetherian (every ideal in R is finitely generated), but this extra assumption is not needed in the above statement.

Acknowledgments

We would like to warmly thank Valérie Berthé, Alexis Bès, Véronique Bruyère, Christiane Frougny, Julien Leroy and Narad Rampersad for their useful comments after reading a preliminary version of this work.

A dynamical proof of this can be given as for the unidimensional case, see [START_REF] Durand | Cobham-Semenov theorem and N d -subshifts[END_REF] for the primitive case.

Self-similar tilings

In [START_REF] Cortez | Self-similar tiling systems, topological factors and stretching factors[END_REF], a Cobham-like theorem is expressed in terms of selfsimilar tilings of R d with a proof using ergodic measures, see [START_REF] Solomyak | Dynamics of self-similar tilings[END_REF] for more about selfsimilar tilings. From the point of view of dynamical systems, the main result in [START_REF] Ormes | A homeomorphism invariant for substitution tiling spaces[END_REF] is also a Cobham-like theorem for self-similar tilings.

Toward Cobham's theorem for the Gaussian integers

I. Kátai and J. Szabó proved in [START_REF] Kátai | Canonical number systems for complex integers[END_REF] that the sequences ((-p+i) n ) n 0 and ((-p-i) n ) n 0 give rise to numeration systems whose set of digits is {0, 1, . . . , p 2 }, p ∈ N \ {0}. It is an exercise to check that when p ∈ N \ {0} and q ∈ N \ {0} are different then -p + i and -q + i are multiplicatively independent. Therefore one could expect a Cobham-type theorem for the set of Gaussian integers

G. Hansel and T. Safer conjectured in [START_REF] Hansel | Vers un théorème de Cobham pour les entiers de Gauss[END_REF] the following: Conjecture 6.12. Let p and q be two different positive integers and S ∈ G. Then the following are equivalent.

(i) The set S is (-p + i)-recognizable and (-q + i)-recognizable;

(ii) There exists a periodic set P such that the symmetric difference set S∆P is finite.

The proof that (ii) implies (i) is easy. They tried to prove the other implication using the following (classical) steps:

S is syndetic (3) S is periodic up to some finite set.

They succeeded in proving (ii) as given by the next result. Theorem 6.13. Let p and q be two positive integers such that the set D p,q is dense in C. Let S ⊂ G be (-p + i)-recognizable and (-q + i)-recognizable. Then, S is syndetic.

Let us make some observations about the density of the set D p,q . Let -p + i = ae iθ and -q + i = be iφ . Proposition 6.14. The following are equivalent.

(i) The set D p,q is dense in C;

(ii) The set D p,q is dense on the circle: {e iθ | θ ∈ R} ⊂ D p,q ;

(iii) The following numbers are rationally independent (or linearly dependent over Q):