Jump to content

Cobham's theorem

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Kritixilithos (talk | contribs) at 08:01, 26 June 2021 (Definitions). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Cobham's theorem is a theorem in combinatorics on words that has important connections with number theory, notably transcendental numbers, and automata theory. The theorem states that if the representations of a set of natural numbers S in two multiplicatively independent bases b1 and b2 form regular languages, then the set S is a finite union of arithmetic progressions. The theorem was proved by Alan Cobham in 1969.[1] It has since given rise to many extensions and generalisations.[2][3]

Definitions

Let be an integer. The representation of a natural number in base is the sequence of digits such that

where and . The word is often denoted , or more simply, .

A set of natural numbers S is recognisable in base or more simply -recognisable or -automatic if the set of the representations of its elements in base is a language recognisable by a finite automaton on the alphabet .

Two positive integers et are multiplicatively independent if there are no non-negative integers and such that . For example, 2 and 3 are multiplicatively independent, but 8 and 16 are not since . 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 be a set of non-negative integers and let and be multiplicatively independent positive integers. Then is recognizable by finite automata in both -ary and -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]

TheoremLet and be two multiplicatively independent integers. A sequence is both -automatic and -automatic only if it is -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 and all integers , the set of natural numbers such that is recognisable in base .

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]

of natural integers equipped with addition and the function defined by and for any positive integer , if is the largest power of that divides . For example, , and .

A set of integers is definable in first-order logic in if it can be described by a first-order formula with equality, addition, and .

Examples:

  • The set of odd numbers is definable (without ) by the formula
  • The set of the powers of 2 is definable by the simple formula .

Cobham's theorem reformulatedLet S be a set of natural numbers, and let and be two multiplicatively independent positive integers. Then S is first-order definable in and in 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 and 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 defined by

which generates the infinite word

,

followed by the coding (that is, letter to letter) that maps to and leaves and unchanged, giving

.

The notion has been extended as follows:[9] a morphic word is -substitutive for a certain number if when written in the form

where the morphism , prolongable in , has the following properties:

  • all letters of occur in , and
  • is the dominant eigenvalue of the matrix of morphism , namely, the matrix , where is the number of occurrences of the letter in the word .

A set S of natural numbers is -recognisable if its characteristic sequence is -substitutive.

A last definition: a Perron number is an algebraic number such that all its conjugates belong to the disc . These are exactly the dominant eigenvalues of the primitive matrices of positive integers.

We then have the following statement:[9]

Cobham's Theorem for substitutionsLet α 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 or recognisable sets have been extended to the integers , to the Cartesian products , to the real numbers and to the Cartesian products .[8]

Extension to

We code the base integers by prepending to the representation of a positive integer the digit , and by representing negative integers by followed by the number's -complement. For example, in base 2, the integer is represented as . The powers of 2 are written as , and their negatives (since is the representation of ).

Extension to

A subset of is recognisable in base if the elements of , written as vectors with components, are recognisable over the resulting alphabet.

For example, in base 2, we have and ; the vector is written as .

Semenov's Theorem (1977)[10]Let and be two multiplicatively independent positive integers. A subset of is -recognisable and -recognisable if and only if is describable in Presburger arithmetic.

An elegant proof of this theorem is given by Muchnik in 1991 by induction on .[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. ^ a b Cobham, Alan (1969). "On the base-dependence of sets of numbers recognizable by finite automata". Mathematical Systems Theory. 3 (2). doi:10.1007/BF01746527. MR 0250789.
  2. ^ Durand, Fabien; Rigo, Michel (2010) [Chapter originally written 2010]. "On Cobham's Theorem" (PDF). In Pin, J.-É. (ed.). Automata: from Mathematics to Applications. European Mathematical Society.
  3. ^ Adamczewski, Boris; Bell, Jason (2010) [Chapter originally written 2010]. "Automata in number theory" (PDF). In Pin, J.-É. (ed.). Automata: from Mathematics to Applications. European Mathematical Society.
  4. ^ Cobham, Alan (1972). "Uniform tag sequences". Mathematical Systems Theory. 6 (1–2). doi:10.1007/BF01706087. MR 0457011.
  5. ^ Allouche, Jean-Paul [in French]; Shallit, Jeffrey (2003). Automatic Sequences: theory, applications, generalizations. Cambridge: Cambridge University Press. p. 350. ISBN 0-521-82332-3.
  6. ^ A "1-automatic" sequence is a sequence that is ultimately periodic
  7. ^ Büchi, J. R. (1960). Weak second-order arithmetic and finite automata. Vol. 6. p. 87. doi:10.1007/978-1-4613-8928-6_22. ISBN 978-1-4613-8930-9. {{cite book}}: ISBN / Date incompatibility (help); |journal= ignored (help)
  8. ^ a b c Bruyère, Véronique (2010). "Around Cobham's theorem and some of its extensions". Dynamical Aspects of Automata and Semigroup Theories. Satellite Workshop of Highlights of AutoMathA. Retrieved 19 January 2017.
  9. ^ a b Durand, Fabien (2011). "Cobham's theorem for substitutions". Journal of the European Mathematical Society. 13 (6): 1797–1812. arXiv:1010.4009. doi:10.4171/JEMS/294.
  10. ^ Semenov, Alexei Lvovich (1977). "Predicates regular in two number systems are Presburger". Sib. Mat. Zh. (in Russian). 18: 403-418. MR 0450050. Zbl 0369.02023.
  11. ^ Muchnik (2003). "The definable criterion for definability in Presburger arithmetic and its applications" (PDF). Theoretical Computer Science. 290 (3). doi:10.1016/S0304-3975(02)00047-6.
  12. ^ 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..
  13. ^ Hansel, Georges (1982). "À propos d'un théorème de Cobham". In Perrin, D. (ed.). Actes de la Fête des mots (in French). Rouen: Greco de programmation, CNRS. pp. 55–59.
  14. ^ Perrin, Dominique (1990). "Finite Automata". In van Leeuwen, Jan (ed.). Handbook of Theoretical Computer Science. Vol. B: Formal Models and Semantics. Elsevier. pp. 1–57. ISBN 978-0444880741.
  15. ^ Allouche, Jean-Paul [in French]; Shallit, Jeffrey (2003). Automatic Sequences: theory, applications, generalizations. Cambridge: Cambridge University Press. ISBN 0-521-82332-3.
  16. ^ Shallit, Jeffrey; Allouche, Jean-Paul (31 March 2020). "Errata for Automatic Sequences: Theory, Applications, Generalizations" (PDF). Retrieved 25 June 2021.
  17. ^ Tomi Kärki (2005). "A Note on the Proof of Cobham's Theorem" (PDF). Rapport Technique n° 713. University of Turku. Retrieved 23 January 2017.
  18. ^ Michel Rigo; Laurent Waxweiler (2006). "A Note on Syndeticity, Recognizable Sets and Cobham's Theorem" (PDF). Bulletin of the EATCS. 88: 169-173. arXiv:0907.0624. MR 2222340. Zbl 1169.68490. Retrieved 23 January 2017.
  19. ^ Paul Fermé, Willy Quach and Yassine Hamoudi (2015). "Le théorème de Cobham" [Cobham's Theorem] (PDF) (in French). Archived from the original (PDF) on 2017-02-02. Retrieved 24 January 2017.
  20. ^ Krebs, Thijmen J. P. (2021). "A More Reasonable Proof of Cobham's Theorem". International Journal of Foundations of Computer Science. 32 (02): 203207. arXiv:1801.06704. doi:10.1142/S0129054121500118. ISSN 0129-0541.
  21. ^ Mol, Lucas; Rampersad, Narad; Shallit, Jeffrey; Stipulanti, Manon (2019). "Cobham's Theorem and Automaticity". International Journal of Foundations of Computer Science. 30 (08): 1363–1379. arXiv:1809.00679. doi:10.1142/S0129054119500308. ISSN 0129-0541.

Bibliography