(Non)Automaticity of number theoretic functions
Journal de Théorie des Nombres de Bordeaux, Tome 22 (2010) no. 2, pp. 339-352.

Soit λ(n) la fonction de Liouville indiquant la parité du nombre de facteurs dans la décomposition de n en facteurs premiers. En combinant un théorème d’Allouche, Mendès France, et Peyrière avec quelques résultats classiques de la théorie de la distribution des nombres premiers, nous démontrons que la fonction λ(n) n’est pas k–automatique pour k>2. Cela entraine que n=1 λ(n)X n 𝔽 p [[X]] est transcendant sur 𝔽 p (X) pour tous les nombres premiers p>2. Nous montrons (ou redémontrons) des résultats semblables pour les fonctions numériques ϕ, μ, Ω, ω, ρ, et autres fonctions.

Denote by λ(n) Liouville’s function concerning the parity of the number of prime divisors of n. Using a theorem of Allouche, Mendès France, and Peyrière and many classical results from the theory of the distribution of prime numbers, we prove that λ(n) is not k–automatic for any k>2. This yields that n=1 λ(n)X n 𝔽 p [[X]] is transcendental over 𝔽 p (X) for any prime p>2. Similar results are proven (or reproven) for many common number–theoretic functions, including ϕ, μ, Ω, ω, ρ, and others.

Reçu le :
Publié le :
DOI : https://doi.org/10.5802/jtnb.718
@article{JTNB_2010__22_2_339_0,
     author = {Michael Coons},
     title = {(Non)Automaticity of number theoretic functions},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     pages = {339--352},
     publisher = {Universit\'e Bordeaux 1},
     volume = {22},
     number = {2},
     year = {2010},
     doi = {10.5802/jtnb.718},
     mrnumber = {2769065},
     zbl = {1223.11115},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.718/}
}
Michael Coons. (Non)Automaticity of number theoretic functions. Journal de Théorie des Nombres de Bordeaux, Tome 22 (2010) no. 2, pp. 339-352. doi : 10.5802/jtnb.718. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.718/

[1] B. Adamczewski and Y. Bugeaud, On the complexity of algebraic numbers. I. Expansions in integer bases. Ann. of Math. (2) 165 (2007), no. 2, 547–565. | MR 2299740 | Zbl 1195.11094

[2] J.-P. Allouche, Note on the transcendence of a generating function. New trends in probability and statistics. Vol. 4 (Palanga, 1996), VSP, Utrecht, 1997, pp. 461–465. | MR 1653629 | Zbl 0932.11017

[3] J.-P. Allouche, Transcendence of formal power series with rational coefficients. Theoret. Comput. Sci. 218 (1999), no. 1, 143–160, WORDS (Rouen, 1997). | MR 1687784 | Zbl 0916.68123

[4] J.-P. Allouche and H. Cohen, Dirichlet series and curious infinite products. Bull. London Math. Soc. 17 (1985), no. 6, 531–538. | MR 813734 | Zbl 0577.10036

[5] J.-P. Allouche, M. Mendès France, and J. Peyrière, Automatic Dirichlet series. J. Number Theory 81 (2000), no. 2, 359–373. | MR 1752260 | Zbl 0971.11006

[6] J.-P. Allouche and J. Shallit, Automatic sequences. Cambridge University Press, Cambridge, 2003. | MR 1997038 | Zbl 1086.11015

[7] W. D. Banks, F. Luca, and I. E. Shparlinski, Irrationality of power series for various number theoretic functions. Manuscripta Math. 117 (2005), no. 2, 183–197. | MR 2150480 | Zbl 1072.11002

[8] P. Borwein and M. Coons, Transcendence of power series for some number theoretic functions. Proc. Amer. Math. Soc. 137 (2009), no. 4, 1303–1305. | MR 2465652 | Zbl pre05544539

[9] F. Carlson, Über Potenzreihen mit ganzzahligen Koeffizienten. Math. Zeitschr. (1921), no. 9, 1–13. | MR 1544447

[10] G. Christol, Ensembles presque périodiques k-reconnaissables. Theoret. Comput. Sci. 9 (1979), no. 1, 141–145. | MR 535129 | Zbl 0402.68044

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

[12] J. B. Conrey, More than two fifths of the zeros of the Riemann zeta function are on the critical line. J. Reine Angew. Math. 399 (1989), 1–26. | MR 1004130 | Zbl 0668.10044

[13] Ch.-J. de la Vallée Poussin, Recherches analytiques de la théorie des nombres premiers. Ann. Soc. Scient. Bruxelles 20 (1896), 183–256.

[14] P. Fatou, Séries trigonométriques et séries de Taylor. Acta Math. (1906), no. 30, 335–400. | MR 1555035

[15] J. Hadamard, Sur la distribution des zéros de la fonction ζ(s) et ses conséquences arithmétiques. Bull. Soc. Math. France 24 (1896), 199–220. | Numdam | MR 1504264

[16] J. Hartmanis and H. Shank, On the recognition of primes by automata. J. Assoc. Comput. Mach. 15 (1968), 382–389. | MR 235916 | Zbl 0164.05201

[17] E. Landau and A. Walfisz, Über die Nichtfortsetzbarkeit einiger durch Dirichletsche Reihen definierter Funktionen. Palermo Rend. (1920), no. 44, 82–86.

[18] K. Mahler, Arithmetische Eigenschaften der Lösungen einer Klasse von Funktionalgleichungen. Math. Ann. 101 (1929), no. 1, 342–366. | MR 1512537

[19] M. Minsky and S. Papert, Unrecognizable sets of numbers. J. Assoc. Comput. Mach. 13 (1966), 281–286. | MR 207481 | Zbl 0166.00601

[20] K. Nishioka, Mahler functions and transcendence. Lecture Notes in Mathematics, vol. 1631, Springer-Verlag, Berlin, 1996. | MR 1439966 | Zbl 0876.11034

[21] R. W. Ritchie, Finite automata and the set of squares. J. Assoc. Comput. Mach. 10 (1963), 528–531. | MR 167374 | Zbl 0118.12601

[22] A. Selberg, On the zeros of Riemann’s zeta-function. Skr. Norske Vid. Akad. Oslo I. 1942 (1942), no. 10, 59 pp. | MR 10712 | Zbl 0028.11101

[23] J. Shallit, Automaticity IV: Sequences, sets, and diversity. J. Théor. Nombres Bordeaux 8 (1996), no. 2, 347–367. | Numdam | MR 1438474 | Zbl 0876.11010

[24] E. C. Titchmarsh, The theory of the Riemann zeta-function. second ed., The Clarendon Press Oxford University Press, New York, 1986, Edited and with a preface by D. R. Heath-Brown. | MR 882550 | Zbl 0601.10026

[25] H. von Mangoldt, Zu Riemanns Abhandlung über die Anzahle der Primzahlen unter einer gegebenen Grösse. J. Reine Angew. Math. 144 (1895), 255–305.

[26] S. Yazdani, Multiplicative functions and k-automatic sequences. J. Théor. Nombres Bordeaux 13 (2001), no. 2, 651–658. | Numdam | MR 1879677 | Zbl 1002.11025