(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, Tome 22 (2010) no. 2, pp. 339-352.

Abstract (VO)
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 Zbl

DOI : 10.5802/jtnb.718

Affiliations des auteurs :

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, Tome 22 (2010) no. 2, pp. 339-352. doi : 10.5802/jtnb.718. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.718/

Bibliographie
Cité par

[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

Shi-Chao Chen Automatic sequences and parity of partition functions, Advances in Applied Mathematics, Volume 166 (2025), p. 23 (Id/No 102869) | DOI:10.1016/j.aam.2025.102869 | Zbl:8015067
Jean-Paul Allouche; Jeffrey Shallit; Manon Stipulanti Combinatorics on words and generating Dirichlet series of automatic sequences, Discrete Mathematics, Volume 348 (2025) no. 8, p. 114487 | DOI:10.1016/j.disc.2025.114487
Jakub Konieczny On asymptotically automatic sequences, Acta Arithmetica, Volume 215 (2024) no. 3, pp. 249-287 | DOI:10.4064/aa230619-26-4 | Zbl:7927131
Michael Coons; John Lind Radial asymptotics of generating functions of $k$ -regular sequences, Bulletin of the Australian Mathematical Society, Volume 110 (2024) no. 3, pp. 528-534 | DOI:10.1017/s0004972724000480 | Zbl:7970542
Pierre-Adrien Tahay Characteristic sequences of the sets of sums of squares as columns of cellular automata, Combinatorics on words. 14th international conference, WORDS 2023, Umeå, Sweden, June 12–16, 2023. Proceedings, Cham: Springer, 2023, pp. 288-300 | DOI:10.1007/978-3-031-33180-0_22 | Zbl:7716998
J.-P. Allouche; J. Shallit; R. Yassawi How to prove that a sequence is not automatic, Expositiones Mathematicae, Volume 40 (2022) no. 1, pp. 1-22 | DOI:10.1016/j.exmath.2021.08.001 | Zbl:1497.11063
Jakub Konieczny; Mariusz Lemańczyk; Clemens Müllner Multiplicative automatic sequences, Mathematische Zeitschrift, Volume 300 (2022) no. 2, pp. 1297-1318 | DOI:10.1007/s00209-021-02834-3 | Zbl:1497.11064
Clemens Heuberger; Daniel Krenn Asymptotic analysis of regular sequences, Algorithmica, Volume 82 (2020) no. 3, pp. 429-508 | DOI:10.1007/s00453-019-00631-3 | Zbl:1476.11018
Jakub Konieczny On multiplicative automatic sequences, Bulletin of the London Mathematical Society, Volume 52 (2020) no. 1, pp. 175-184 | DOI:10.1112/blms.12317 | Zbl:1472.11088
Oleksiy Klurman; Pär Kurlberg A note on multiplicative automatic sequences. II, Bulletin of the London Mathematical Society, Volume 52 (2020) no. 1, pp. 185-188 | DOI:10.1112/blms.12318 | Zbl:1457.11023
Jean-Paul Allouche; Leo Goldmakher Mock characters and the Kronecker symbol, Journal of Number Theory, Volume 192 (2018), pp. 356-372 | DOI:10.1016/j.jnt.2018.04.022 | Zbl:1448.11062
Francisco J. Aragón Artacho; David H. Bailey; Jonathan M. Borwein; Peter B. Borwein Walking on real numbers (2013), Pi: The Next Generation (2016), p. 341 | DOI:10.1007/978-3-319-32377-0_21
William Duke; Ha Nam Nguyen Infinite products of cyclotomic polynomials, Bulletin of the Australian Mathematical Society, Volume 91 (2015) no. 3, pp. 400-411 | DOI:10.1017/s0004972715000039 | Zbl:1320.11087
Francisco J. Aragón Artacho; David H. Bailey; Jonathan M. Borwein; Peter B. Borwein Walking on real numbers, The Mathematical Intelligencer, Volume 35 (2013) no. 1, pp. 42-60 | DOI:10.1007/s00283-012-9340-x | Zbl:1282.11088
Jason P. Bell; Nils Bruin; Michael Coons Transcendence of generating functions whose coefficients are multiplicative, Transactions of the American Mathematical Society, Volume 364 (2012) no. 2, pp. 933-959 | DOI:10.1090/s0002-9947-2011-05479-6 | Zbl:1271.11095

Cité par 15 documents. Sources : Crossref, zbMATH