On the computational complexity of algebraic numbers: the Hartmanis–Stearns problem revisited

Adamczewski, Boris; Cassaigne, Julien; Le Gonidec, Marion

doi:10.1090/tran/7915

On the computational complexity of algebraic numbers: the Hartmanis–Stearns problem revisited
HTML articles powered by AMS MathViewer

by Boris Adamczewski, Julien Cassaigne and Marion Le Gonidec PDF

Trans. Amer. Math. Soc. 373 (2020), 3085-3115 Request permission

Abstract:

We consider the complexity of integer base expansions of algebraic irrational numbers from a computational point of view. A major contribution in this area is that the base-$b$ expansion of algebraic irrational real numbers cannot be generated by finite automata. Our aim is to provide two natural generalizations of this theorem. Our main result is that the base-$b$ expansion of algebraic irrational real numbers cannot be generated by deterministic pushdown automata. Incidentally, this completely solves the Hartmanis–Stearns problem for the class of multistack machines. We also confirm an old claim of Cobham from 1968 proving that such real numbers cannot be generated by tag machines with dilation factor larger than one. In order to stick with the modern terminology, we also show that the latter generate the same class of real numbers as morphisms with exponential growth.

References

Boris Adamczewski, On the expansion of some exponential periods in an integer base, Math. Ann. 346 (2010), no. 1, 107–116. MR 2558889, DOI 10.1007/s00208-009-0391-z
Boris Adamczewski and Yann Bugeaud, On the complexity of algebraic numbers. II. Continued fractions, Acta Math. 195 (2005), 1–20. MR 2233683, DOI 10.1007/BF02588048
Boris Adamczewski and Yann Bugeaud, On the complexity of algebraic numbers. I. Expansions in integer bases, Ann. of Math. (2) 165 (2007), no. 2, 547–565. MR 2299740, DOI 10.4007/annals.2007.165.547
Boris Adamczewski and Yann Bugeaud, Dynamics for $\beta$-shifts and Diophantine approximation, Ergodic Theory Dynam. Systems 27 (2007), no. 6, 1695–1711. MR 2371591, DOI 10.1017/S0143385707000223
Boris Adamczewski and Yann Bugeaud, Mesures de transcendance et aspects quantitatifs de la méthode de Thue-Siegel-Roth-Schmidt, Proc. Lond. Math. Soc. (3) 101 (2010), no. 1, 1–26 (French, with English and French summaries). MR 2661240, DOI 10.1112/plms/pdp054
Boris Adamczewski and Yann Bugeaud, Transcendence measures for continued fractions involving repetitive or symmetric patterns, J. Eur. Math. Soc. (JEMS) 12 (2010), no. 4, 883–914. MR 2654083, DOI 10.4171/JEMS/218
Boris Adamczewski and Yann Bugeaud, Nombres réels de complexité sous-linéaire: mesures d’irrationalité et de transcendance, J. Reine Angew. Math. 658 (2011), 65–98 (French, with English summary). MR 2831513, DOI 10.1515/CRELLE.2011.061
Boris Adamczewski, Yann Bugeaud, and Florian Luca, Sur la complexité des nombres algébriques, C. R. Math. Acad. Sci. Paris 339 (2004), no. 1, 11–14 (French, with English and French summaries). MR 2075225, DOI 10.1016/j.crma.2004.04.012
Boris Adamczewski and Julien Cassaigne, Diophantine properties of real numbers generated by finite automata, Compos. Math. 142 (2006), no. 6, 1351–1372. MR 2278750, DOI 10.1112/S0010437X06002247
Boris Adamczewski and Colin Faverjon, Méthode de Mahler: relations linéaires, transcendance et applications aux nombres automatiques, Proc. Lond. Math. Soc. (3) 115 (2017), no. 1, 55–90 (French, with English and French summaries). MR 3669933, DOI 10.1112/plms.12038
J. Albert, Propriétés combinatoires et arithmétiques de certaines suites automatiques et substitutives, Thèse de Doctorat de l’Université Paris Sud, 2006.
Jean-Paul Allouche and Jeffrey Shallit, Automatic sequences, Cambridge University Press, Cambridge, 2003. Theory, applications, generalizations. MR 1997038, DOI 10.1017/CBO9780511546563
J.-M. Autebert, Langages algébriques, Études et Recherches en Informatique. [Studies and Research in Computer Science], Masson, Paris, 1987 (French). MR 888601
Jean-Michel Autebert, Jean Berstel, and Luc Boasson, Context-free languages and pushdown automata, Handbook of formal languages, Vol. 1, Springer, Berlin, 1997, pp. 111–174. MR 1469995
J. Berstel and L. Boasson, Modèles de machines, Encyclopédie de l’informatique et des systèmes d’information, pp. 987–998, Vuibert, 2006.
Daniel Bertrand, Theta functions and transcendence, Ramanujan J. 1 (1997), no. 4, 339–350. International Symposium on Number Theory (Madras, 1996). MR 1608721, DOI 10.1023/A:1009749608672
É. Borel, Les probabilités dénombrables et leurs applications arithmétiques, Rend. Circ. Mat. Palermo 27 (1909), 247–271.
J. M. Borwein and P. B. Borwein, On the complexity of familiar functions and numbers, SIAM Rev. 30 (1988), no. 4, 589–601. MR 967961, DOI 10.1137/1030134
Yann Bugeaud, An explicit lower bound for the block complexity of an algebraic number, Atti Accad. Naz. Lincei Rend. Lincei Mat. Appl. 19 (2008), no. 3, 229–235. MR 2439519, DOI 10.4171/RLM/521
Yann Bugeaud, Automatic continued fractions are transcendental or quadratic, Ann. Sci. Éc. Norm. Supér. (4) 46 (2013), no. 6, 1005–1022 (English, with English and French summaries). MR 3134686, DOI 10.24033/asens.2208
Julien Cassaigne and François Nicolas, Factor complexity, Combinatorics, automata and number theory, Encyclopedia Math. Appl., vol. 135, Cambridge Univ. Press, Cambridge, 2010, pp. 163–247. MR 2759107
Didier Caucal and Marion Le Gonidec, Context-free sequences, Theoretical aspects of computing—ICTAC 2014, Lecture Notes in Comput. Sci., vol. 8687, Springer, Cham, 2014, pp. 259–276. MR 3278460, DOI 10.1007/978-3-319-10882-7_{1}6
N. Chomsky, Three models for the description of language, IRE Trans. Information Theory 18 (1956), 113–124.
A. Cobham, Functional equations for register machines, Proccedings of the Hawaii International Conference on System Sciences, Honolulu, pp. 10–13, 1968.
A. Cobham, A proof of transcendence based on functional equations, RC–2041, IBM Research Center, Yorktown Heights, New York, 1968.
A. Cobham, On the Hartmanis-Stearns problem for a class of tag machines, IEEE Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory, pp. 51–60, 1968.
Alan Cobham, Uniform tag sequences, Math. Systems Theory 6 (1972), 164–192. MR 457011, DOI 10.1007/BF01706087
Daniel Duverney, Keiji Nishioka, Kumiko Nishioka, and Iekata Shiokawa, Transcendence of Jacobi’s theta series, Proc. Japan Acad. Ser. A Math. Sci. 72 (1996), no. 9, 202–203. MR 1434685
D. Hamm, Contributions to formal language theory: Fixed points, complexity, and context-free sequences, M.Sc. Thesis, University of Waterloo, 1998.
J. Hartmanis and R. E. Stearns, On the computational complexity of algorithms, Trans. Amer. Math. Soc. 117 (1965), 285–306. MR 170805, DOI 10.1090/S0002-9947-1965-0170805-7
John E. Hopcroft and Jeffrey D. Ullman, Introduction to automata theory, languages, and computation, Addison-Wesley Series in Computer Science, Addison-Wesley Publishing Co., Reading, Mass., 1979. MR 645539
Marion Le Gonidec, Drunken man infinite words complexity, Theor. Inform. Appl. 42 (2008), no. 3, 599–613. MR 2434037, DOI 10.1051/ita:2008012
Marion Le Gonidec, On the complexity of a family of $k$-context-free sequences, Theoret. Comput. Sci. 414 (2012), 47–54. MR 2896582, DOI 10.1016/j.tcs.2011.09.022
J. Liouville, Sur des classes très étendues de quantités dont la valeur n’est ni algébrique, ni même réductible à des irrationelles algébriques, C. R. Acad. Sci. Paris 18 (1844), 883–885 et 993–995.
Kurt Mahler, Zur Approximation der Exponentialfunktion und des Logarithmus. Teil II, J. Reine Angew. Math. 166 (1932), 137–150 (German). MR 1581303, DOI 10.1515/crll.1932.166.137
Marvin L. Minsky, Computation: finite and infinite machines, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. MR 0356580
Marston Morse and Gustav A. Hedlund, Symbolic Dynamics, Amer. J. Math. 60 (1938), no. 4, 815–866. MR 1507944, DOI 10.2307/2371264
Yossi Moshe, On some questions regarding $k$-regular and $k$-context-free sequences, Theoret. Comput. Sci. 400 (2008), no. 1-3, 62–69. MR 2424342, DOI 10.1016/j.tcs.2008.02.018
Yu. V. Nesterenko, Modular functions and transcendence questions, Mat. Sb. 187 (1996), no. 9, 65–96 (Russian, with Russian summary); English transl., Sb. Math. 187 (1996), no. 9, 1319–1348. MR 1422383, DOI 10.1070/SM1996v187n09ABEH000158
Jean-Jacques Pansiot, Complexité des facteurs des mots infinis engendrés par morphismes itérés, Automata, languages and programming (Antwerp, 1984) Lecture Notes in Comput. Sci., vol. 172, Springer, Berlin, 1984, pp. 380–389 (French, with English summary). MR 784265, DOI 10.1007/3-540-13345-3_{3}4
Patrice Philippon, Groupes de Galois et nombres automatiques, J. Lond. Math. Soc. (2) 92 (2015), no. 3, 596–614 (French, with English and French summaries). MR 3431652, DOI 10.1112/jlms/jdv056
N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Mathematics, vol. 1794, Springer-Verlag, Berlin, 2002. Edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel. MR 1970385, DOI 10.1007/b13861
Martine Queffélec, Substitution dynamical systems—spectral analysis, 2nd ed., Lecture Notes in Mathematics, vol. 1294, Springer-Verlag, Berlin, 2010. MR 2590264, DOI 10.1007/978-3-642-11212-6
J. Shallit, A second course in formal languages and automata theory, Cambridge University Press, Cambridge, 2008.
M. Sipser, Introduction to the theory of computation, third edition, Wadsworth Publishing Co. Inc., 2012.
Seppo Sippu and Eljas Soisalon-Soininen, Parsing theory. Vol. I, EATCS Monographs on Theoretical Computer Science, vol. 15, Springer-Verlag, Berlin, 1988. Languages and parsing. MR 960693, DOI 10.1007/978-3-642-61345-6
A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction, Proc. London Math. Soc. (2) 43 (1937), no. 7, 544–546. MR 1575661, DOI 10.1112/plms/s2-43.6.544