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

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.

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.

Received:
Published online:
DOI: 10.5802/jtnb.718
Michael Coons 1

1 University of Waterloo Department of Pure Mathematics 200 University Avenue West Waterloo, Ontario N2L 3G1, Canada
@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/}
}
TY  - JOUR
TI  - (Non)Automaticity of number theoretic functions
JO  - Journal de Théorie des Nombres de Bordeaux
PY  - 2010
DA  - 2010///
SP  - 339
EP  - 352
VL  - 22
IS  - 2
PB  - Université Bordeaux 1
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.718/
UR  - https://www.ams.org/mathscinet-getitem?mr=2769065
UR  - https://zbmath.org/?q=an%3A1223.11115
UR  - https://doi.org/10.5802/jtnb.718
DO  - 10.5802/jtnb.718
LA  - en
ID  - JTNB_2010__22_2_339_0
ER  - 
%0 Journal Article
%T (Non)Automaticity of number theoretic functions
%J Journal de Théorie des Nombres de Bordeaux
%D 2010
%P 339-352
%V 22
%N 2
%I Université Bordeaux 1
%U https://doi.org/10.5802/jtnb.718
%R 10.5802/jtnb.718
%G en
%F JTNB_2010__22_2_339_0
Michael Coons. (Non)Automaticity of number theoretic functions. Journal de Théorie des Nombres de Bordeaux, Volume 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

Cited by Sources: