(Non)Automaticity of number theoretic functions

Coons, Michael¹

¹ 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)

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.

Résumé

Soit $\lambda \left(n\right)$ 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 $\lambda \left(n\right)$ n’est pas $k$–automatique pour $k>2$. Cela entraine que ${\sum }_{n=1}^{\infty }\lambda \left(n\right)X^n\in {𝔽}_p\left[\left[X\right]\right]$ est transcendant sur ${𝔽}_p\left(X\right)$ pour tous les nombres premiers $p>2$. Nous montrons (ou redémontrons) des résultats semblables pour les fonctions numériques $\varphi$, $\mu$, $\Omega$, $\omega$, $\rho$, et autres fonctions.

Détail

DOI : 10.5802/jtnb.718