Multiplicative functions and $k$-automatic sequences
Journal de Théorie des Nombres de Bordeaux, Volume 13 (2001) no. 2, pp. 651-658.

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)\phantom{\rule{4pt}{0ex}}\text{mod}\phantom{\rule{4pt}{0ex}}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)$.

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)\phantom{\rule{4pt}{0ex}}\text{mod}\phantom{\rule{4pt}{0ex}}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)$.

@article{JTNB_2001__13_2_651_0,
author = {Soroosh Yazdani},
title = {Multiplicative functions and $k$-automatic sequences},
journal = {Journal de Th\'eorie des Nombres de Bordeaux},
pages = {651--658},
publisher = {Universit\'e Bordeaux I},
volume = {13},
number = {2},
year = {2001},
doi = {10.5802/jtnb.342},
zbl = {1002.11025},
mrnumber = {1879677},
language = {en},
url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.342/}
}
TY  - JOUR
TI  - Multiplicative functions and $k$-automatic sequences
JO  - Journal de Théorie des Nombres de Bordeaux
PY  - 2001
DA  - 2001///
SP  - 651
EP  - 658
VL  - 13
IS  - 2
PB  - Université Bordeaux I
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.342/
UR  - https://zbmath.org/?q=an%3A1002.11025
UR  - https://www.ams.org/mathscinet-getitem?mr=1879677
UR  - https://doi.org/10.5802/jtnb.342
DO  - 10.5802/jtnb.342
LA  - en
ID  - JTNB_2001__13_2_651_0
ER  - 
%0 Journal Article
%T Multiplicative functions and $k$-automatic sequences
%J Journal de Théorie des Nombres de Bordeaux
%D 2001
%P 651-658
%V 13
%N 2
%I Université Bordeaux I
%U https://doi.org/10.5802/jtnb.342
%R 10.5802/jtnb.342
%G en
%F JTNB_2001__13_2_651_0
Soroosh Yazdani. Multiplicative functions and $k$-automatic sequences. Journal de Théorie des Nombres de Bordeaux, Volume 13 (2001) no. 2, pp. 651-658. doi : 10.5802/jtnb.342. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.342/

[1] J.-P. Allouche, Sur la transcendance de la série formelle π. Sém. Théor. Nombres Bordeaux 2 (1990), 103-117. | Numdam | Zbl: 0709.11067

[2] J.-P. Allouche, D.S. Thakur, Automata and transcendence of the Tate period in finite characteristic. Proc. Amer. Math. Soc. 127 (1999), 1309-1312. | MR: 1476112 | Zbl: 0926.11038

[3] G. Christol, Ensembles presque periodiques k-reconnaissables. Theoret. Comput. Sci. 9 (1979), 141-145. | MR: 535129 | Zbl: 0402.68044

[4] G. Christol, T. Kamae, M. Mendès France, G. Rauzy, Suites algébriques, automates et substitutions. Bull. Soc. Math. France 108 (1980), 401-419. | Numdam | MR: 614317 | Zbl: 0472.10035

[5] A. Cobham, Uniform tag sequences. Math. Systems Theory 6 (1972), 164-192. | MR: 457011 | Zbl: 0253.02029

[6] P. Erdös, G. Szekeres, Über die Anzahl der Abelschen Gruppen gegebener Ordnung und über ein verwandtes zahlentheoretisches Problem. Acta Sci. Math.(Szeged) 7 (1935), 95-102. | JFM: 60.0893.02

[7] A. Ivi, P. Shiu, The distribution of powerful integers. Illinois J. Math. 26 (1982), 576-590. | MR: 674226 | Zbl: 0484.10024

[8] M. Minsky, S. Papert, Unrecognizable sets of numbers. J. Assoc. Comput. Mach. 13 (1966), 281-286. | MR: 207481 | Zbl: 0166.00601

[9] R. Sivaramakrishnan, Classical theory of arithmetic functions. Monographs and Textbooks in Pure and Applied Mathematics 126, Marcel Dekker, Inc., New York, 1989. | MR: 980259 | Zbl: 0657.10001

Cited by Sources: