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 b1 and base b2 to be recognised by finite automata.
Specifically, consider bases b1 and b2 such that they are not powers of the same integer.
The theorem was proved by Alan Cobham in 1969[1] and has since given rise to many extensions and generalisations.
A set of natural numbers S is recognisable in base
is a language recognisable by a finite automaton on the alphabet
Cobham himself calls them "uniform tag sequences.".
[4] The following form is found in Allouche and Shallit's book:[5]Theorem — Let
The logical expression uses the theory[8] of natural integers equipped with addition and the function
if it can be described by a first-order formula with equality, addition, and
Examples: Cobham's theorem reformulated — Let S be a set of natural numbers, and let
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.
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
unchanged, giving The notion has been extended as follows:[9] a morphic word
These are exactly the dominant eigenvalues of the primitive matrices of positive integers.
We then have the following statement:[9]Cobham's theorem for substitutions — Let α et β be two multiplicatively independent Perron numbers.
Then a sequence x with elements belonging to a finite set is both α-substitutive and β-substitutive if and only if x is ultimately periodic.
The logic equivalent permits to consider more general situations: the automatic sequences over the natural numbers
or recognisable sets have been extended to the integers
components, are recognisable over the resulting alphabet.
An elegant proof of this theorem is given by Muchnik in 1991 by induction on
[8] Samuel Eilenberg announced the theorem without proof in his book;[12] 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.
[13] The proof of Dominique Perrin[14] and that of Allouche and Shallit's book[15] contains the same error in one of the lemmas, mentioned in the list of errata of the book.
[16] This error was uncovered in a note by Tomi Kärki,[17] and corrected by Michel Rigo and Laurent Waxweiler.
[19] 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.
[20] The employed method has been refined and used by Mol, Rampersad, Shallit and Stipulanti.