Automata and algebraicity. (Automates et algébricités.) (French) Zbl 1119.11020

For a finite set \(A\subset\mathbb N\) of digits, consider a sequence \(u=(u_n)\) with \(u_n\in A\) for all \(n\geq0\). There are several objects of interest in number theory naturally associated to \(u\): the real number \(\sum_{n\geq0}u_n| A|^{-n}\); the formal power series \(\sum_{n\geq0}u_nX^n\in\mathbb Q((X))\); the same formal power series viewed as an element of \(\mathbb F_p((X))\); the real continued fraction \([u_0+1,u_1+1,\dots]\). This survey paper is concerned with different aspects of the following question: how is ‘regularity’ of the sequence manifested in regularity of one of these objects? For brevity the case of the Thue-Morse sequence and the Fibonacci numbers is considered, with references to more general results.
The ‘Note ajoutée aux épreuves’ refers to recent work of B. Adamczewski and Y. Bugeaud, which has now appeared [Ann. Math. (2) 165, No. 2, 547–565 (2007; Zbl 1195.11094)].


11B85 Automata sequences
68R15 Combinatorics on words
68Q70 Algebraic theory of languages and automata


Zbl 1195.11094
Full Text: DOI Numdam EuDML


[1] B. Adamczewski, Transcendance de nombres réels et \(p\)-adiques par la méthode de Roth. Prétirage, 2004.
[2] B. Adamczewski, J. Cassaigne, On the transcendence of real numbers with a regular expansion. J. Number Theory 103 (2003), 27-37. · Zbl 1052.11052
[3] J.-P. Allouche, Nouveaux résultats de transcendance de réels à développement non aléatoire. Gaz. Math. 84 (2000), 19-34. · Zbl 1388.11046
[4] J.-P. Allouche, J. L. Davison, M. Queffélec, L. Q. Zamboni, Transcendence of Sturmian or morphic continued fractions. J. Number Theory 91 (2001), 39-66. · Zbl 0998.11036
[5] J.-P. Allouche, J. Shallit, The ubiquitous Prouhet-Thue-Morse sequence, in Sequences and their applications, Proceedings of SETA’98, C. Ding, T. Helleseth and H. Niederreiter (Eds.). Springer, 1999, pp. 1-16. · Zbl 1005.11005
[6] J.-P. Allouche, J. Shallit, Automatic sequences. Theory, Applications, Generalizations. Cambridge University Press, 2003, xvi + 571 pages. · Zbl 1086.11015
[7] J.-P. Allouche, L. Q. Zamboni, Algebraic irrational binary numbers cannot be fixed points of non-trivial constant length or primitive morphisms. J. Number Theory 69 (1998), 119-124. · Zbl 0918.11016
[8] É. Borel, Sur les chiffres décimaux de \(\sqrt{2}\) et divers problèmes de probabilités en chaîne. C. R. Acad. Sci. Paris 230 (1950), 591-593. Réédité dans : Œuvres d’É. Borel, vol. 2. Éditions du CNRS, Paris, 1972, pp. 1203-1204. · Zbl 0035.08302
[9] G. Christol, Ensembles presque périodiques \(k\)-reconnaissables. Theoret. Comput. Sci. 9 (1979), 141-145. · Zbl 0402.68044
[10] G. Christol, T. Kamae, M. Mendès France, G. Rauzy, Suites algébriques, automates et substitutions. Bull. Soc. Math. France 108 (1980), 401-419. · Zbl 0472.10035
[11] A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata. Math. Systems Theory 3 (1969), 186-192. · Zbl 0179.02501
[12] A. Cobham, Uniform tag sequences. Math. Systems Theory 6 (1972), 164-192. · Zbl 0253.02029
[13] L. V. Danilov, Some classes of transcendental numbers (en russe). Mat. Zametki 12 (1972), 149-154. Traduit dans : Math. Notes Acad. Sci. USSR 12 (1972), 524-527. · Zbl 0253.10026
[14] P. Fatou, Séries trigonométriques et séries de Taylor. Acta Math 30 (1906), 335-400. · JFM 37.0283.01
[15] S. Ferenczi, C. Mauduit, Transcendence of numbers with a low complexity expansion. J. Number Theory 67 (1997), 146-161. · Zbl 0895.11029
[16] J. H. Loxton, A. J. van der Poorten, Arithmetic properties of certain functions in several variables, III. Bull. Austral. Math. Soc. 16 (1977), 15-47. · Zbl 0339.10028
[17] K. Mahler, Arithmetische Eigenschaften der Lösungen einer Klasse von Funktionalgleichungen. Math. Ann. 101 (1929), 342-366. Corrigendum 103 (1930), 532. · JFM 55.0115.01
[18] M. Morse, Recurrent geodesics on a surface of negative curvature. Trans. Amer. Math. Soc. 22 (1921), 84-100. · JFM 48.0786.06
[19] K. Nishioka, T.-a. Tanaka, Z.-Y. Wen, Substitution in two symbols and transcendence. Tokyo J. Math. 22 (1999), 127-136. · Zbl 0940.11015
[20] G. Pólya, Über gewisse notwendige Determinantenkriterien für die Fortsetzbarkeit einer Potenzreihe. Math. Ann. 99 (1928), 687-706. · JFM 54.0340.07
[21] E. Prouhet, Mémoire sur quelques relations entre les puissances des nombres. C. R. Acad. Sci. Paris 33 (1851), 225.
[22] M. Queffélec, Transcendance des fractions continues de Thue-Morse. J. Number Theory 73 (1998), 201-211. · Zbl 0920.11045
[23] D. Roy, Approximation simultanée d’un nombre et de son carré. C. R. Math. Acad. Sci. Paris 336 (2003), 1-6. · Zbl 1038.11042
[24] D. Roy, Approximation to real numbers by cubic algebraic integers, I. Proc. London Math. Soc. 88 (2004), 42-62. · Zbl 1035.11028
[25] A. Thue, Über unendliche Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. 7 (1906), 1-22. Reprinted in Selected mathematical papers of Axel Thue. T. Nagell, ed., Universitetsforlaget, Oslo, 1977, pp. 139-158.
[26] A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912), 1-67. Reprinted in Selected mathematical papers of Axel Thue. T. Nagell, ed., Universitetsforlaget, Oslo, 1977, pp. 413-478. · JFM 43.0162.07
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.