# (Non)Automaticity of number theoretic functions

• [1] University of Waterloo Department of Pure Mathematics 200 University Avenue West Waterloo, Ontario N2L 3G1, Canada
• Volume: 22, Issue: 2, page 339-352
• ISSN: 1246-7405

top

## Abstract

top
Denote by $\lambda \left(n\right)$ 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 $\lambda \left(n\right)$ is not $k$–automatic for any $k>2$. This yields that ${\sum }_{n=1}^{\infty }\lambda \left(n\right){X}^{n}\in {𝔽}_{p}\left[\left[X\right]\right]$ is transcendental over ${𝔽}_{p}\left(X\right)$ for any prime $p>2$. Similar results are proven (or reproven) for many common number–theoretic functions, including $\varphi$, $\mu$, $\Omega$, $\omega$, $\rho$, and others.

## How to cite

top

Coons, Michael. "(Non)Automaticity of number theoretic functions." Journal de Théorie des Nombres de Bordeaux 22.2 (2010): 339-352. <http://eudml.org/doc/116406>.

@article{Coons2010,
abstract = {Denote by $\lambda (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 $\lambda (n)$ is not $k$–automatic for any $k&gt; 2$. This yields that $\sum _\{n=1\}^\infty \lambda (n) X^n\in \mathbb\{F\}_p[[X]]$ is transcendental over $\mathbb\{F\}_p(X)$ for any prime $p&gt;2$. Similar results are proven (or reproven) for many common number–theoretic functions, including $\varphi$, $\mu$, $\Omega$, $\omega$, $\rho$, and others.},
affiliation = {University of Waterloo Department of Pure Mathematics 200 University Avenue West Waterloo, Ontario N2L 3G1, Canada},
author = {Coons, Michael},
journal = {Journal de Théorie des Nombres de Bordeaux},
keywords = {arithmetic functions; automaticity},
language = {eng},
number = {2},
pages = {339-352},
publisher = {Université Bordeaux 1},
title = {(Non)Automaticity of number theoretic functions},
url = {http://eudml.org/doc/116406},
volume = {22},
year = {2010},
}

TY - JOUR
AU - Coons, Michael
TI - (Non)Automaticity of number theoretic functions
JO - Journal de Théorie des Nombres de Bordeaux
PY - 2010
PB - Université Bordeaux 1
VL - 22
IS - 2
SP - 339
EP - 352
AB - Denote by $\lambda (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 $\lambda (n)$ is not $k$–automatic for any $k&gt; 2$. This yields that $\sum _{n=1}^\infty \lambda (n) X^n\in \mathbb{F}_p[[X]]$ is transcendental over $\mathbb{F}_p(X)$ for any prime $p&gt;2$. Similar results are proven (or reproven) for many common number–theoretic functions, including $\varphi$, $\mu$, $\Omega$, $\omega$, $\rho$, and others.
LA - eng
KW - arithmetic functions; automaticity
UR - http://eudml.org/doc/116406
ER -

## References

top
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. Zbl1195.11094MR2299740
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. Zbl0932.11017MR1653629
3. J.-P. Allouche, Transcendence of formal power series with rational coefficients. Theoret. Comput. Sci. 218 (1999), no. 1, 143–160, WORDS (Rouen, 1997). Zbl0916.68123MR1687784
4. J.-P. Allouche and H. Cohen, Dirichlet series and curious infinite products. Bull. London Math. Soc. 17 (1985), no. 6, 531–538. Zbl0577.10036MR813734
5. J.-P. Allouche, M. Mendès France, and J. Peyrière, Automatic Dirichlet series. J. Number Theory 81 (2000), no. 2, 359–373. Zbl0971.11006MR1752260
6. J.-P. Allouche and J. Shallit, Automatic sequences. Cambridge University Press, Cambridge, 2003. Zbl1086.11015MR1997038
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. Zbl1072.11002MR2150480
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. Zbl1236.11063MR2465652
9. F. Carlson, Über Potenzreihen mit ganzzahligen Koeffizienten. Math. Zeitschr. (1921), no. 9, 1–13. Zbl48.1208.02MR1544447
10. G. Christol, Ensembles presque périodiques $k$-reconnaissables. Theoret. Comput. Sci. 9 (1979), no. 1, 141–145. Zbl0402.68044MR535129
11. A. Cobham, Uniform tag sequences. Math. Systems Theory 6 (1972), 164–192. Zbl0253.02029MR457011
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. Zbl0668.10044MR1004130
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. Zbl37.0283.01MR1555035
15. J. Hadamard, Sur la distribution des zéros de la fonction $\zeta \left(s\right)$ et ses conséquences arithmétiques. Bull. Soc. Math. France 24 (1896), 199–220. Zbl27.0154.01MR1504264
16. J. Hartmanis and H. Shank, On the recognition of primes by automata. J. Assoc. Comput. Mach. 15 (1968), 382–389. Zbl0164.05201MR235916
17. E. Landau and A. Walfisz, Über die Nichtfortsetzbarkeit einiger durch Dirichletsche Reihen definierter Funktionen. Palermo Rend. (1920), no. 44, 82–86. Zbl47.0287.02
18. K. Mahler, Arithmetische Eigenschaften der Lösungen einer Klasse von Funktionalgleichungen. Math. Ann. 101 (1929), no. 1, 342–366. Zbl55.0115.01MR1512537
19. M. Minsky and S. Papert, Unrecognizable sets of numbers. J. Assoc. Comput. Mach. 13 (1966), 281–286. Zbl0166.00601MR207481
20. K. Nishioka, Mahler functions and transcendence. Lecture Notes in Mathematics, vol. 1631, Springer-Verlag, Berlin, 1996. Zbl0876.11034MR1439966
21. R. W. Ritchie, Finite automata and the set of squares. J. Assoc. Comput. Mach. 10 (1963), 528–531. Zbl0118.12601MR167374
22. A. Selberg, On the zeros of Riemann’s zeta-function. Skr. Norske Vid. Akad. Oslo I. 1942 (1942), no. 10, 59 pp. Zbl0028.11101MR10712
23. J. Shallit, Automaticity IV: Sequences, sets, and diversity. J. Théor. Nombres Bordeaux 8 (1996), no. 2, 347–367. Zbl0876.11010MR1438474
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. Zbl0601.10026MR882550
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. Zbl1002.11025MR1879677

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.