Cobham’s theorem and its extensions

Bell, Jason P.

Actes des rencontres du CIRM, Tome 1 (2009) no. 1, pp. 11-16.

Cobham’s theorem says that if $k$ and $\ell$ are two multiplicatively independent integers and $f\left(n\right)$ is a $k$- and $\ell$-automatic sequence, then $f\left(n\right)$ is eventually periodic. We give a summary of recent work on automatic sequences and their relation to Cobham’s theorem.

[1] B. Adamczewski and J. Bell. Function fields in positive characteristic: expansions and Cobham’s theorem. J. Algebra 319 (2008), no. 6, 2337–2350. | DOI | MR | Zbl

[2] J.-P. Allouche and J. Shallit. The ring of $k$-regular sequences. Theoret. Comput. Sci. 98 (1992), 163–197. | DOI | MR | Zbl

[3] J.-P. Allouche and J. Shallit. Automatic sequences. Theory, applications, generalizations. Cambridge University Press, Cambridge, 2003. | DOI | Zbl

[4] P.-G. Becker. $K$-regular power series and Mahler-type functional equations. J. Number Theory 49 (1994), 269–286. | DOI | MR | Zbl

[5] J. Bell. A generalization of Cobham’s theorem for regular sequences. Sém. Lothar. Combin. 54A (2005/07), Art. B54Ap, 15 pp. | Zbl

[6] J. Berstel and C. Reutenauer. Rational Series and Their Languages EATCS Monographs on Theoretical Computer Science (12), W. Brauer, G. Rozenberg, A. Saloma (Eds.) Springer-Verlag Berlin, Heidelberg 1988. | Zbl

[7] B. Bollobás. Graph theory. An introductory course. Springer-Verlag, New York-Berlin, 1979. | Zbl

[8] C. Chevalley. Introduction to the Theory of Algebraic Functions of One Variable. Mathematical Surveys No. VI, Amer. Math. Soc., 1951.

[9] G. Christol. Ensembles presques périodiques $k$-reconnaissables. Theor. Comput. Sci. 9 (1979), 141–145. | DOI | MR | Zbl

[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. | DOI | Zbl

[11] A. Cobham. On the base-dependence of sets of numbers recognizable by finite automata. Math. Systems Theory 3 (1969), 186–192. | DOI | MR | Zbl

[12] A. Cobham. Uniform tag sequences. Math. Systems Theory 6 (1972), 164–192. | DOI | MR | Zbl

[13] F. Durand. A generalization of Cobham’s theorem. Theory Comput. Systems 31 (1998), 169–185. | DOI | MR | Zbl

[14] F. Durand. A theorem of Cobham for non-primitive substitutions. Acta Arith. 104 (2002), no. 3, 225–241. | DOI | MR | Zbl

[15] G. Everest, A. van der Poorten, I. Shparlinski, and T. Ward. Recurrence sequences. Mathematical Surveys and Monographs, 104. American Mathematical Society, Providence, RI, 2003. | Zbl

[16] S. Fabre. Une généralisation du théorème de Cobham. Acta Arith. 67 (1994), 197–208. | DOI | Zbl

[17] I. Fagnot. On the subword equivalence problem for morphic words. Discrete Appl. Math. 75 (1997), no. 3, 231–253. | DOI | MR | Zbl

[18] H. Hahn. Über die nichtarchimedische Größensysteme (1907), reprinted in Gesammelte Abhandlungen I, Springer-Verlag, 1995. | DOI

[19] K. Kedlaya. The algebraic closure of the power series field in positive characteristic.Proc. Amer. Math. Soc. 129 (2001), 3461–3470. | DOI | MR | Zbl

[20] K. Kedlaya. Finite automata and algebraic extensions of function fields. J. Théor. Nombres Bordeaux 18 (2006), 379–420. | DOI | MR | Zbl

[21] G. Krause and T. Lenagan. Growth of Algebras and Gelfand–Kirillov Dimension, revised edition. Grad. Stud. Math., vol. 22, Amer. Math. Soc., Providence, RI, 2000. | Zbl

[22] M. Mendès France. Sur les décimales des nombres algébriques réels, in Sémin. Théor. Nombres, Bordeaux, 1979–1980, Exp. No. 28, 7 pp., Univ. Bordeaux I, Talence, 1980. | Zbl

[23] B. Randé. Équations fonctionnelles de Mahler et applications aux suites $p$-régulières. PhD thesis, Université Bordeaux I, 1992.