Multiplicative functions and $k$-automatic sequences

Yazdani, Soroosh

Journal de théorie des nombres de Bordeaux, Tome 13 (2001) no. 2, pp. 651-658

Abstract (VO)

A sequence is called $k$-automatic if the $n$’th term in the sequence can be generated by a finite state machine, reading $n$ in base $k$ as input. We show that for many multiplicative functions, the sequence ${\left(f\left(n\right)\text{mod}v\right)}_{n\ge 1}$ is not $k$-automatic. Among these multiplicative functions are ${\gamma }_m\left(n\right),{\sigma }_m\left(n\right),\mu \left(n\right)$ et $\phi \left(n\right)$.

Résumé

Une suite est dite $k$-automatique si son $n^e$ terme peut être engendré par une machine à états finis lisant en entrée le développement de $n$ en base $k$. Nous prouvons que, pour de nombreuses fonctions multiplicatives $f$, la suite ${\left(f\left(n\right)\text{mod}v\right)}_{n\ge 1}$ n’est pas $k$-automatique. C’est en particulier le cas pour les fonctions multiplicatives ${\gamma }_m\left(n\right),{\sigma }_m\left(n\right),\mu \left(n\right)$ et $\phi \left(n\right)$.