(Non)Automaticity of number theoretic functions

2008/10/21 by Michael James Coons, Michael Coons, Coons, Michael
Computer Science · Mathematics · #11B85 #11J91 #11N64 #Computability, Logic, AI Algorithms #FOS: Mathematics #Mathematical Dynamics and Fractals #Number Theory (math.NT) #math.NT #msc:11B85 #msc:11J91 #msc:11N64 #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.0810.3709

11 pages

openalex publication_date 2008/10/21 · arxiv created 2008/10/29 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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ⁿ∈\mathbbF_p[[X]] is transcendental over \mathbbF_p(X) for any prime p>2. Similar results are proven (or reproven) for many common number--theoretic functions, including ϕ, μ, Ω, ω, ρ, and others.

Related

• Completely multiplicative functions taking values in \-1,1\
• Transcendence of the Gaussian Liouville number and relatives
• Transcendence of Power Series for Some Number Theoretic Functions
• Algorithm, probability, and prime numbers
• On the residue class distribution of the number of prime divisors of an integer