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 differs by a finite set from a finite union of arithmetic progressions. The theorem was proved by Alan Cobham in 1969^[1] and has since given rise to many extensions and generalisations.^[2][3]

Let ${\displaystyle n>0}$ be an integer. The representation of a natural number ${\textstyle n}$ in base ${\textstyle b}$ is the sequence of digits ${\displaystyle n_{0}n_{1}\cdots n_{h}}$ such that

${\displaystyle n=n_{0}+n_{1}b+\cdots +n_{h}b^{h}}$

where ${\displaystyle 0\leq n_{0},n_{1},\ldots ,n_{h}<b}$ and ${\displaystyle n_{h}>0}$. The word ${\displaystyle n_{0}n_{1}\cdots n_{h}}$ is often denoted ${\displaystyle \langle n\rangle _{b}}$, or more simply, ${\displaystyle n_{b}}$.

A set of natural numbers S is recognisable in base ${\textstyle b}$ or more simply ${\textstyle b}$-recognisable or ${\textstyle b}$-automatic if the set ${\displaystyle \{n_{b}\mid n\in S\}}$ of the representations of its elements in base ${\displaystyle b}$ is a language recognisable by a finite automaton on the alphabet ${\displaystyle \{0,1,\ldots ,b-1\}}$.

Two positive integers ${\displaystyle k}$ and ${\displaystyle \ell }$ are multiplicatively independent if there are no non-negative integers ${\displaystyle p}$ and ${\displaystyle q}$ such that ${\displaystyle k^{p}=\ell ^{q}}$. For example, 2 and 3 are multiplicatively independent, but 8 and 16 are not since ${\displaystyle 8^{4}=16^{3}}$. Two integers are multiplicatively dependent if and only if they are powers of a same third integer.

More equivalent statements of the theorem have been given. The original version by Cobham is the following:^[1]

Another way to state the theorem is by using automatic sequences. Cobham himself calls them "uniform tag sequences.".^[4] The following form is found in Allouche and Shallit's book:^[5]

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 ${\displaystyle u}$ and all integers ${\displaystyle 0\leq i<k}$, the set ${\displaystyle S_{i}}$ of natural numbers ${\displaystyle s}$ such that ${\displaystyle u_{s}=i}$ is recognisable in base ${\displaystyle k}$.

Cobham's theorem can be formulated in first-order logic using a theorem proven by Büchi in 1960.^[7] This formulation in logic allows for extensions and generalisations. The logical expression uses the theory^[8]

${\displaystyle \langle N,+,V_{r}\rangle }$

of natural integers equipped with addition and the function ${\displaystyle V_{r}}$ defined by ${\displaystyle V_{r}(0)=1}$ and for any positive integer ${\textstyle n}$, ${\displaystyle V_{r}(n)=r^{m}}$ if ${\displaystyle r^{m}}$ is the largest power of ${\displaystyle r}$ that divides ${\textstyle n}$. For example, ${\displaystyle V_{2}(20)=4}$, and ${\displaystyle V_{3}(20)=1}$.

A set of integers ${\displaystyle S}$ is definable in first-order logic in ${\displaystyle \langle N,+,V_{r}\rangle }$ if it can be described by a first-order formula with equality, addition, and ${\displaystyle V_{r}}$.

Examples:

• The set of odd numbers is definable (without ${\displaystyle V_{r}}$) by the formula ${\displaystyle (\exists y)(x=y+y+1)}$
• The set ${\displaystyle \{2^{n}\mid n\geq 0\}}$ of the powers of 2 is definable by the simple formula ${\displaystyle V_{2}(x)=x}$.

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 ${\displaystyle \langle N,+,V_{k}\rangle }$ and ${\displaystyle \langle N,+,V_{\ell }\rangle }$ if and only if it is definable in Presburger arithmetic.

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 ${\displaystyle B=\{a,0,1\}}$ defined by

${\displaystyle a\mapsto a1\ ,\quad 1\mapsto 10\ ,\quad 0\mapsto 00}$

which generates the infinite word

${\displaystyle a11010001\cdots }$,

followed by the coding (that is, letter to letter) that maps ${\displaystyle a}$ to ${\displaystyle 0}$ and leaves ${\displaystyle 0}$ and ${\displaystyle 1}$ unchanged, giving

${\displaystyle 011010001\cdots }$.

The notion has been extended as follows:^[9] a morphic word ${\displaystyle s}$ is ${\displaystyle \alpha }$-substitutive for a certain number ${\displaystyle \alpha }$ if when written in the form

${\displaystyle s=\pi (f^{\omega }(b))}$

where the morphism ${\displaystyle f:B^{*}\to B^{*}}$, prolongable in ${\textstyle b}$, has the following properties:

• all letters of ${\displaystyle B}$ occur in ${\displaystyle f^{\omega }(b)}$, and
• ${\displaystyle \alpha >1}$ is the dominant eigenvalue of the matrix of morphism ${\displaystyle f}$, namely, the matrix ${\displaystyle M(f)=(m_{x,y})_{x\in B,y\in A}}$, where ${\displaystyle m_{x,y}}$ is the number of occurrences of the letter ${\displaystyle x}$ in the word ${\displaystyle f(y)}$.

A set S of natural numbers is ${\displaystyle \alpha }$-recognisable if its characteristic sequence ${\displaystyle s}$ is ${\displaystyle \alpha }$-substitutive.

A last definition: a Perron number is an algebraic number ${\displaystyle z>1}$ such that all its conjugates belong to the disc ${\displaystyle \{z'\in \mathbb {C} ,|z'|<z\}}$. These are exactly the dominant eigenvalues of the primitive matrices of positive integers.

We then have the following statement:^[9]

The logic equivalent permits to consider more general situations: the automatic sequences over the natural numbers ${\displaystyle \mathbb {N} }$ or recognisable sets have been extended to the integers ${\displaystyle \mathbb {Z} }$, to the Cartesian products ${\displaystyle \mathbb {N} ^{m}}$, to the real numbers ${\displaystyle \mathbb {R} }$ and to the Cartesian products ${\displaystyle \mathbb {R} ^{m}}$.^[8]

Extension to ${\displaystyle \mathbb {Z} }$

We code the base ${\displaystyle k}$ integers by prepending to the representation of a positive integer the digit ${\displaystyle 0}$, and by representing negative integers by ${\displaystyle k-1}$ followed by the number's ${\displaystyle k}$-complement. For example, in base 2, the integer ${\displaystyle -6=-8+2}$ is represented as ${\displaystyle 1010}$. The powers of 2 are written as ${\displaystyle 010^{*}}$, and their negatives ${\displaystyle 110^{*}}$ (since ${\displaystyle 11000}$ is the representation of ${\displaystyle -16+8=-8}$).

Extension to ${\displaystyle \mathbb {N} ^{m}}$

A subset ${\displaystyle X}$ of ${\displaystyle N^{m}}$ is recognisable in base ${\displaystyle k}$ if the elements of ${\displaystyle X}$, written as vectors with ${\displaystyle m}$ components, are recognisable over the resulting alphabet.

For example, in base 2, we have ${\displaystyle 3=11_{2}}$ and ${\displaystyle 9=1001_{2}}$; the vector ${\displaystyle {\begin{pmatrix}3\\9\end{pmatrix}}}$ is written as ${\displaystyle {\begin{pmatrix}0011\\1001\end{pmatrix}}={\begin{pmatrix}0\\1\end{pmatrix}}{\begin{pmatrix}0\\0\end{pmatrix}}{\begin{pmatrix}1\\0\end{pmatrix}}{\begin{pmatrix}1\\1\end{pmatrix}}}$.

An elegant proof of this theorem is given by Muchnik in 1991 by induction on ${\displaystyle m}$.^[11]

Other extensions have been given to the real numbers and vectors of real numbers.^[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.^[18] This part of the proof has been recently written.^[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.^[21]

• Allouche, Jean-Paul [in French]; Shallit, Jeffrey (2003). Automatic Sequences: theory, applications, generalizations. Cambridge: Cambridge University Press. ISBN 0-521-82332-3.