Cobham's theorem
Cobham's theorem is a theorem in combinatorics on words that has important connections with number theory, notably transcendental numbers, and automata theory. Informally, the theorem gives the condition for the members of a set "S" of natural numbers written in bases "b" and base "b" to be recognised by finite automata. Specifically, consider bases "b" and "b" such that they are not powers of the same integer. Cobham's theorem states that "S" written in bases "b" and "b" is recognised by finite automata if and only if "S" is a finite union of arithmetic progressions . The theorem was proved by Alan Cobham in 1969 and has since given rise to many extensions and generalisations. Definitions. Let formula_1 be an integer. The representation of a natural number formula_2 in base formula_3 is the sequence of digits formula_4 such that where formula_6 and formula_7. The word formula_4 is often denoted formula_9, or more simply, formula_10. A set of natural numbers "S" is "recognisable in base" formula_3 or more simply "formula_3-recognisable" or "formula_3-automatic" if the set formula_14 of the representations of its elements in base formula_15 is a language recognisable by a finite automaton on the  alphabet formula_16. Two positive integers formula_17 and formula_18 are multiplicatively independent if there are no non-negative integers formula_19 and formula_20 such that formula_21. For example, 2 and 3 are multiplicatively independent, but 8 and 16 are not since formula_22. Two integers are multiplicatively dependent if and only if they are powers of a same third integer. Problem statements. Original problem statement. More equivalent statements of the theorem have been given. The original version by Cobham is the following: Another way to state the theorem is by using automatic sequences. Cobham himself calls them "uniform tag sequences.". The following form  is found in Allouche and Shallit's book:We can show that the characteristic sequence of a set of natural numbers "S" recognisable by finite automata in base "k" is a "k"-automatic sequence and that conversely, for all "k"-automatic sequences formula_23 and all integers formula_24, the set formula_25 of natural numbers formula_26 such that formula_27 is recognisable in base formula_17. Formulation in logic. Cobham's theorem can be formulated in first-order logic using a theorem proven by Büchi in 1960. This formulation in logic allows for extensions and generalisations. The logical expression uses the theory of natural integers equipped  with addition and the function formula_30 defined by formula_31 and for any positive integer formula_2, formula_33 if formula_34 is the largest power of formula_35 that divides formula_2. For example, formula_37, and formula_38. A set of integers formula_39 is "definable in first-order logic in" formula_29 if it can be described by a first-order formula with equality, addition, and formula_30. Examples: We can push the analogy with logic further by noting that "S" is first-order definable in Presburger arithmetic if and only if it is ultimately periodic. So, a set "S" is definable in the logics formula_46 and formula_47  if and only if it is definable in Presburger arithmetic. Generalisations. Approach by morphisms. An automatic sequence is a particular morphic word, whose morphism is uniform, meaning that the length of the images generated by the morphism for each letter of its input alphabet is the same. A set of integers is hence "k"-recognisable if and only if its characteristic sequence is generated by a uniform morphism followed by a coding, where a coding is a morphism that maps each letter of the input alphabet to a letter of the output alphabet. For example, the characteristic sequence of the powers  of 2 is produced by the 2-uniform morphism (meaning each letter is mapped to a word of length 2) over the alphabet formula_48 defined by which generates the infinite word followed by the coding (that is, letter to letter) that maps formula_51 to formula_52 and leaves formula_52 and formula_54 unchanged, giving The notion has been extended as follows: a morphic word formula_26 is formula_57-"substitutive" for a certain number formula_57 if when written in the form where the morphism formula_60, prolongable in formula_3, has the following properties: A set "S" of natural numbers is formula_57-"recognisable" if its characteristic sequence formula_26  is formula_57-substitutive. A last definition: a "Perron number" is an algebraic number formula_73 such that all its conjugates belong to the disc formula_74. These are exactly the dominant eigenvalues of the primitive matrices of positive integers. We then have the following statement: Logic approach. The logic equivalent permits to consider more general situations: the automatic sequences over the natural numbers formula_75 or recognisable sets have been extended to the integers formula_76, to the Cartesian products formula_77, to the real numbers formula_78 and to the Cartesian products formula_79. We code the base formula_17 integers by prepending to the representation of  a positive integer the digit formula_52, and by representing negative integers by formula_83 followed by the number's formula_17-complement. For example, in base 2, the integer formula_85 is represented as formula_86. The powers of 2 are written as formula_87, and their negatives formula_88 (since formula_89 is the representation of formula_90). A subset formula_92 of formula_93 is recognisable in base formula_17 if the elements of formula_92, written as vectors with formula_96 components, are recognisable over the resulting alphabet. For example, in base 2, we have formula_97 and formula_98; the vector formula_99 is written as formula_100.An elegant proof of this theorem  is given by Muchnik in 1991 by induction on formula_96. Other extensions have been given to the real numbers and vectors of real numbers. Proofs. Samuel Eilenberg announced the theorem without proof in his book; he says "The proof is correct, long, and hard. It is a challenge to find a more reasonable proof of this fine theorem." Georges Hansel proposed a more simple proof, published in the not-easily accessible proceedings of a conference. The proof of Dominique Perrin and that of Allouche and Shallit's book contains the same error in one of the lemmas, mentioned in the  list of errata of the book. This error was uncovered in a note by Tomi Kärki, and corrected by Michel Rigo and Laurent Waxweiler. This part of the proof has been recently written. In January 2018, Thijmen J. P. Krebs announced, on Arxiv, a simplified proof of the original theorem, based on Dirichlet's approximation criterion instead of that of Kronecker; the article appeared in 2021. The employed method has been refined and used by Mol, Rampersad, Shallit and Stipulanti.