(Non)Automaticity of number theoretic functions

Abstract: Denote by

l a m b d a (n)

Liouville's function concerning the parity of the number of prime divisors of

n

. Using a theorem of Allouche, Mend`es France, and Peyri`ere and many classical results from the theory of the distribution of prime numbers, we prove that

l a m b d a (n)

is not

k

--automatic for any

k > 2

. This yields that

s u m_{n = 1}^{i} n f t y l a m b d a (n) X^{n} i n m a t h b b F_{p} [[X]]

is transcendental over

m a t h b b F_{p} (X)

for any prime

p > 2

. Similar results are proven (or reproven) for many common number--theoretic functions, including

p h i

,

m u

,

O m e g a

,

o m e g a

,

h o

, and others.

Review text

The authors prove that Liouville's arithmetic function \(\lambda(n)\) is not \(k\)-automatic for any \(k>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>2\). Similar results are proven (or reproven) for many common arithmetic functions, including \(\phi \) (Euler's function ), \(\mu \) (Möbius), \(\Omega \), \(\omega \), \(\rho \), and others.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: (Non)Automaticity of number theoretic functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q628832)