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 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. Cobham's theorem states that S written in bases b1 and b2 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[1] and has since given rise to many extensions and generalisations.[2][3]
Definitions
Let [math]\displaystyle{ n\gt 0 }[/math] be an integer. The representation of a natural number [math]\displaystyle{ n }[/math] in base [math]\displaystyle{ b }[/math] is the sequence of digits [math]\displaystyle{ n_0n_1\cdots n_h }[/math] such that
- [math]\displaystyle{ n=n_0+n_1b+\cdots+n_hb^h }[/math]
where [math]\displaystyle{ 0\le n_0,n_1,\ldots,n_h \lt b }[/math] and [math]\displaystyle{ n_h\gt 0 }[/math]. The word [math]\displaystyle{ n_0n_1\cdots n_h }[/math] is often denoted [math]\displaystyle{ \langle n\rangle_b }[/math], or more simply, [math]\displaystyle{ n_b }[/math].
A set of natural numbers S is recognisable in base [math]\displaystyle{ b }[/math] or more simply [math]\displaystyle{ b }[/math]-recognisable or [math]\displaystyle{ b }[/math]-automatic if the set [math]\displaystyle{ \{n_b\mid n\in S\} }[/math] of the representations of its elements in base [math]\displaystyle{ b }[/math] is a language recognisable by a finite automaton on the alphabet [math]\displaystyle{ \{0,1,\ldots,b-1\} }[/math].
Two positive integers [math]\displaystyle{ k }[/math] and [math]\displaystyle{ \ell }[/math] are multiplicatively independent if there are no non-negative integers [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math] such that [math]\displaystyle{ k^p=\ell^q }[/math]. For example, 2 and 3 are multiplicatively independent, but 8 and 16 are not since [math]\displaystyle{ 8^4=16^3 }[/math]. 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:[1]
Theorem (Cobham 1969) — Let [math]\displaystyle{ S }[/math] be a set of non-negative integers and let [math]\displaystyle{ m }[/math] and [math]\displaystyle{ n }[/math] be multiplicatively independent positive integers. Then [math]\displaystyle{ S }[/math] is recognizable by finite automata in both [math]\displaystyle{ m }[/math]-ary and [math]\displaystyle{ n }[/math]-ary notation if and only if it is ultimately periodic.
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]
Theorem — Let [math]\displaystyle{ k }[/math] and [math]\displaystyle{ \ell }[/math] be two multiplicatively independent integers. A sequence is both [math]\displaystyle{ k }[/math]-automatic and [math]\displaystyle{ \ell }[/math]-automatic only if it is [math]\displaystyle{ 1 }[/math]-automatic[6]
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 [math]\displaystyle{ u }[/math] and all integers [math]\displaystyle{ 0\le i \lt k }[/math], the set [math]\displaystyle{ S_i }[/math] of natural numbers [math]\displaystyle{ s }[/math] such that [math]\displaystyle{ u_s=i }[/math] is recognisable in base [math]\displaystyle{ k }[/math].
Formulation in logic
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]
- [math]\displaystyle{ \langle N, +, V_r\rangle }[/math]
of natural integers equipped with addition and the function [math]\displaystyle{ V_r }[/math] defined by [math]\displaystyle{ V_r(0)=1 }[/math] and for any positive integer [math]\displaystyle{ n }[/math], [math]\displaystyle{ V_r(n)=m }[/math] if [math]\displaystyle{ r^m }[/math] is the largest power of [math]\displaystyle{ r }[/math] that divides [math]\displaystyle{ n }[/math]. For example, [math]\displaystyle{ V_2(20)=4 }[/math], and [math]\displaystyle{ V_3(20)=1 }[/math].
A set of integers [math]\displaystyle{ S }[/math] is definable in first-order logic in [math]\displaystyle{ \langle N, +, V_r\rangle }[/math] if it can be described by a first-order formula with equality, addition, and [math]\displaystyle{ V_r }[/math].
Examples:
- The set of odd numbers is definable (without [math]\displaystyle{ V_r }[/math]) by the formula [math]\displaystyle{ (\exists y)(x=y+y+1) }[/math]
- The set [math]\displaystyle{ \{2^n\mid n\ge0\} }[/math] of the powers of 2 is definable by the simple formula [math]\displaystyle{ V_2(x)=x }[/math].
Cobham's theorem reformulated — Let S be a set of natural numbers, and let [math]\displaystyle{ k }[/math] and [math]\displaystyle{ \ell }[/math] be two multiplicatively independent positive integers. Then S is first-order definable in [math]\displaystyle{ \langle N, +, V_k\rangle }[/math] and in [math]\displaystyle{ \langle N, +, V_\ell\rangle }[/math] if and only if S is ultimately periodic.
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 [math]\displaystyle{ \langle N, +, V_k\rangle }[/math] and [math]\displaystyle{ \langle N, +, V_\ell\rangle }[/math] 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 [math]\displaystyle{ B=\{a,0,1\} }[/math] defined by
- [math]\displaystyle{ a \mapsto a1\ ,\quad 1\mapsto 10\ ,\quad 0\mapsto 00 }[/math]
which generates the infinite word
- [math]\displaystyle{ a11010001\cdots }[/math],
followed by the coding (that is, letter to letter) that maps [math]\displaystyle{ a }[/math] to [math]\displaystyle{ 0 }[/math] and leaves [math]\displaystyle{ 0 }[/math] and [math]\displaystyle{ 1 }[/math] unchanged, giving
- [math]\displaystyle{ 011010001\cdots }[/math].
The notion has been extended as follows:[9] a morphic word [math]\displaystyle{ s }[/math] is [math]\displaystyle{ \alpha }[/math]-substitutive for a certain number [math]\displaystyle{ \alpha }[/math] if when written in the form
- [math]\displaystyle{ s=\pi(f^\omega(b)) }[/math]
where the morphism [math]\displaystyle{ f:B^*\to B^* }[/math], prolongable in [math]\displaystyle{ b }[/math], has the following properties:
- all letters of [math]\displaystyle{ B }[/math] occur in [math]\displaystyle{ f^\omega(b) }[/math], and
- [math]\displaystyle{ \alpha\gt 1 }[/math] is the dominant eigenvalue of the matrix of morphism [math]\displaystyle{ f }[/math], namely, the matrix [math]\displaystyle{ M(f)=(m_{x,y})_{x\in B,y\in A} }[/math], where [math]\displaystyle{ m_{x,y} }[/math] is the number of occurrences of the letter [math]\displaystyle{ x }[/math] in the word [math]\displaystyle{ f(y) }[/math].
A set S of natural numbers is [math]\displaystyle{ \alpha }[/math]-recognisable if its characteristic sequence [math]\displaystyle{ s }[/math] is [math]\displaystyle{ \alpha }[/math]-substitutive.
A last definition: a Perron number is an algebraic number [math]\displaystyle{ z \gt 1 }[/math] such that all its conjugates belong to the disc [math]\displaystyle{ \{z' \in \Complex,|z'|\lt z\} }[/math]. 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.
Logic approach
The logic equivalent permits to consider more general situations: the automatic sequences over the natural numbers [math]\displaystyle{ \N }[/math] or recognisable sets have been extended to the integers [math]\displaystyle{ \Z }[/math], to the Cartesian products [math]\displaystyle{ \N^m }[/math], to the real numbers [math]\displaystyle{ \R }[/math] and to the Cartesian products [math]\displaystyle{ \R^m }[/math].[8]
- Extension to [math]\displaystyle{ \Z }[/math]
We code the base [math]\displaystyle{ k }[/math] integers by prepending to the representation of a positive integer the digit [math]\displaystyle{ 0 }[/math], and by representing negative integers by [math]\displaystyle{ k-1 }[/math] followed by the number's [math]\displaystyle{ k }[/math]-complement. For example, in base 2, the integer [math]\displaystyle{ -6=-8+2 }[/math] is represented as [math]\displaystyle{ 1010 }[/math]. The powers of 2 are written as [math]\displaystyle{ 010^* }[/math], and their negatives [math]\displaystyle{ 110^* }[/math] (since [math]\displaystyle{ 11000 }[/math] is the representation of [math]\displaystyle{ -16+8=-8 }[/math]).
- Extension to [math]\displaystyle{ \N^m }[/math]
A subset [math]\displaystyle{ X }[/math] of [math]\displaystyle{ N^m }[/math] is recognisable in base [math]\displaystyle{ k }[/math] if the elements of [math]\displaystyle{ X }[/math], written as vectors with [math]\displaystyle{ m }[/math] components, are recognisable over the resulting alphabet.
For example, in base 2, we have [math]\displaystyle{ 3=11_2 }[/math] and [math]\displaystyle{ 9=1001_2 }[/math]; the vector [math]\displaystyle{ \begin{pmatrix}3\\9\end{pmatrix} }[/math] is written as [math]\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} }[/math].
Semenov's theorem (1977)[10] — Let [math]\displaystyle{ r }[/math] and [math]\displaystyle{ s }[/math] be two multiplicatively independent positive integers. A subset [math]\displaystyle{ S }[/math] of [math]\displaystyle{ N^m }[/math] is [math]\displaystyle{ r }[/math]-recognisable and [math]\displaystyle{ s }[/math]-recognisable if and only if [math]\displaystyle{ S }[/math] is describable in Presburger arithmetic.
An elegant proof of this theorem is given by Muchnik in 1991 by induction on [math]\displaystyle{ m }[/math].[11]
Other extensions have been given to the real numbers and vectors of real numbers.[8]
Proofs
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]
Notes and references
- ↑ 1.0 1.1 Cobham, Alan (1969). "On the base-dependence of sets of numbers recognizable by finite automata". Mathematical Systems Theory 3 (2): 186–192. doi:10.1007/BF01746527.
- ↑ Durand, Fabien; Rigo, Michel (2010). "On Cobham’s Theorem". in Pin, J.-É.. Automata: from Mathematics to Applications. European Mathematical Society. https://www-fourier.ujf-grenoble.fr/sites/default/files/files/fichiers/cobham010711.pdf.
- ↑ Adamczewski, Boris; Bell, Jason (2010). "Automata in number theory". in Pin, J.-É.. Automata: from Mathematics to Applications. European Mathematical Society. https://adamczewski.perso.math.cnrs.fr/Chapter25.pdf.
- ↑ Cobham, Alan (1972). "Uniform tag sequences". Mathematical Systems Theory 6 (1–2): 164–192. doi:10.1007/BF01706087.
- ↑ Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: theory, applications, generalizations. Cambridge: Cambridge University Press. p. 350. ISBN 0-521-82332-3.
- ↑ A "1-automatic" sequence is a sequence that is ultimately periodic
- ↑ Büchi, J. R. (1990). "Weak Second-Order Arithmetic and Finite Automata". The Collected Works of J. Richard Büchi. 6. 87. doi:10.1007/978-1-4613-8928-6_22. ISBN 978-1-4613-8930-9.
- ↑ 8.0 8.1 8.2 Bruyère, Véronique (2010). "Around Cobham's theorem and some of its extensions". Satellite Workshop of Highlights of AutoMathA. http://www.mat.uc.pt/~amgc/daast/slides/daast-bruyere.
- ↑ 9.0 9.1 Durand, Fabien (2011). "Cobham's theorem for substitutions". Journal of the European Mathematical Society 13 (6): 1797–1812. doi:10.4171/JEMS/294. http://www.ems-ph.org/journals/show_pdf.php?issn=1435-9855&vol=13&iss=6&rank=8.
- ↑ Semenov, Alexei Lvovich (1977). "Predicates regular in two number systems are Presburger" (in ru). Sib. Mat. Zh. 18: 403-418. doi:10.1007/BF00967164.
- ↑ Muchnik (2003). "The definable criterion for definability in Presburger arithmetic and its applications". Theoretical Computer Science 290 (3): 1433–1444. doi:10.1016/S0304-3975(02)00047-6. https://core.ac.uk/download/pdf/82333239.pdf.
- ↑ Eilenberg, Samuel (1974). Automata, Languages and Machines, Vol. A. Pure and Applied Mathematics. New York: Academic Press. pp. xvi+451. ISBN 978-0-12-234001-7..
- ↑ Hansel, Georges (1982). "À propos d'un théorème de Cobham". in Perrin, D.. Actes de la Fête des mots. Rouen: Greco de programmation, CNRS. pp. 55–59.
- ↑ Perrin, Dominique (1990). "Finite Automata". in van Leeuwen, Jan. Handbook of Theoretical Computer Science. B: Formal Models and Semantics. Elsevier. pp. 1–57. ISBN 978-0444880741.
- ↑ Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: theory, applications, generalizations. Cambridge: Cambridge University Press. ISBN 0-521-82332-3.
- ↑ Shallit, Jeffrey; Allouche, Jean-Paul (31 March 2020). "Errata for Automatic Sequences: Theory, Applications, Generalizations". https://cs.uwaterloo.ca/~shallit/as-errata.pdf.
- ↑ Tomi Kärki (2005). "A Note on the Proof of Cobham's Theorem". University of Turku. http://www.tucs.fi/publications/attachment.php?fname=TR713.pdf.
- ↑ Michel Rigo; Laurent Waxweiler (2006). "A Note on Syndeticity, Recognizable Sets and Cobham's Theorem.". Bulletin of the EATCS 88: 169–173. http://eatcs.org/images/bulletin/beatcs88.pdf. Retrieved 23 January 2017.
- ↑ Paul Fermé, Willy Quach and Yassine Hamoudi (2015). "Le théorème de Cobham" (in French). http://perso.ens-lyon.fr/yassine.hamoudi/wp-content/uploads/2016/07/Cobham.pdf.
- ↑ Krebs, Thijmen J. P. (2021). "A More Reasonable Proof of Cobham's Theorem". International Journal of Foundations of Computer Science 32 (2): 203207. doi:10.1142/S0129054121500118. ISSN 0129-0541.
- ↑ Mol, Lucas; Rampersad, Narad; Shallit, Jeffrey; Stipulanti, Manon (2019). "Cobham's Theorem and Automaticity". International Journal of Foundations of Computer Science 30 (8): 1363–1379. doi:10.1142/S0129054119500308. ISSN 0129-0541.
Bibliography
- Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: theory, applications, generalizations. Cambridge: Cambridge University Press. ISBN 0-521-82332-3.
![]() | Original source: https://en.wikipedia.org/wiki/Cobham's theorem.
Read more |