(Non)Automaticity of number theoretic functions

Michael Coons

doi:10.5802/jtnb.718

Michael Coons ¹

¹ University of Waterloo Department of Pure Mathematics 200 University Avenue West Waterloo, Ontario N2L 3G1, Canada

Journal de théorie des nombres de Bordeaux, Volume 22 (2010) no. 2, pp. 339-352.

Abstract
Résumé

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 $\sum_{n = 1}^{\infty} λ (n) X^{n} \in 𝔽_{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 $\sum_{n = 1}^{\infty} λ (n) X^{n} \in 𝔽_{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.

MR: 2769065 | Zbl: 1223.11115

DOI: 10.5802/jtnb.718

Author's affiliations:

Michael Coons ¹

¹ 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
AU  - Michael Coons
TI  - (Non)Automaticity of number theoretic functions
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2010
SP  - 339
EP  - 352
VL  - 22
IS  - 2
PB  - Université Bordeaux 1
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.718/
DO  - 10.5802/jtnb.718
LA  - en
ID  - JTNB_2010__22_2_339_0
ER  -

%0 Journal Article
%A Michael Coons
%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://jtnb.centre-mersenne.org/articles/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/

References
Cited by

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

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

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

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

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

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

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

[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

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

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

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

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

[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

[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

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

[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

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

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

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

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

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

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

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

Cited by Sources: