zbMATH — the first resource for mathematics

Multiplicative functions and \(k\)-automatic sequences. (English) Zbl 1002.11025
A sequence is \(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. More precisely, \({\mathbb{T}}=(t(n))_{n\geq 1}\) is \(k\)-automatic if the \(k\)-kernel \({\mathbb{T}}^{(k)}=\{T_{l,r}^{(k)}:l\geq 0\), \(0\leq r<k^l\}\) is finite, where \(T_{l,r}^{(k)}=(t(k^l+r))_{n\geq 1}\).
The author asks when a multiplicative function \(f\) can be \(k\)-automatic. Suppose \(v>1, h\geq 1\) are integers, \(b,c\) are relatively prime integers, \(f(q_1^h)\equiv 0\bmod v\) for infinitely many primes \(q_1\) and \(f(q_2)\not\equiv 0\bmod v\) for all primes \(q_2\equiv c\bmod b\). Then the sequence \((f(n)\bmod v)_{n\geq 1}\) is not \(k\)-automatic for any \(k\geq 2\). This is proved by showing that for each sufficiently large \(l\), there are integers \(r_1, r_2\) with \(0\leq r_i<k\) and \(n\) with \(f(k^ln+r_1)\equiv\bmod v, f(k^ln+r_2)\not\equiv 0\bmod v\) whence the \(k\)-kernel of \((f(n)\bmod v)\) is infinite. Start with a prime \(q_1\) such that \(q_1>k^l, f(q_1^h)\equiv 0\bmod v\) and a prime \(a=bm+c\) for which \(f(a)\not\equiv 0\bmod v\). Then we can choose \(n_0\) and \(j\) so that \(r_2\equiv a\bmod bk\) and \(n_0bk^l+jq_1^{h+1}b^2k^l+r_2\) is prime. Then \(n=n_0b+jq_1^{h+1}b^2\) gives the required result since \(n_0bk^l+r_1\equiv q_1^h\bmod q_1^{h+1}\) and \(f\) is multipicative. As examples of this result, for \(v\geq 3, k\geq 2\), \(\sigma_m(n)=\sum_{k|n} k^m\) is not \(k\)-automatic and so \(\sum_{n\geq 1} \sigma_m(n)X^n\) is transcendental over \({\mathbb{F}}_p(X)\) for odd primes \(p\), settling a conjecture of Allouche and Thakur. Also \(\varphi(n)\) and \(\mu(n)\) are not \(k\)-automatic.
The same conclusion is established for some multiplicative functions with \(f(q)\equiv 0\bmod v\) for all primes \(q\). This group includes \(\sigma_m(n)\bmod 2\) and \(\tau_m(n)\bmod v\).
The author leaves an open question over the automaticity of those multiplicative functions for which \(v\nmid f(n)\) for all \(n\geq 1\). An example here is the Liouville function \(\lambda(n)\) defined by \(\lambda(p_1^{\alpha_1}\cdots p_t^{\alpha_t})=(-1)^{\alpha_1+\cdots+\alpha_t}\).

11B85 Automata sequences
11A25 Arithmetic functions; related numbers; inversion formulas
Full Text: DOI EMIS Numdam EuDML
[1] Allouche, J.-P., Sur la transcendance de la série formelle π. Sém. Théor. Nombres Bordeaux2 (1990), 103-117. · Zbl 0709.11067
[2] Allouche, J.-P., Thakur, D.S., Automata and transcendence of the Tate period in finite characteristic. Proc. Amer. Math. Soc.127 (1999), 1309-1312. · Zbl 0926.11038
[3] Christol, G., Ensembles presque periodiques k-reconnaissables. Theoret. Comput. Sci.9 (1979), 141-145. · Zbl 0402.68044
[4] Christol, G., Kamae, T., Mendès France, M., Rauzy, G., Suites algébriques, automates et substitutions. Bull. Soc. Math. France108 (1980), 401-419. · Zbl 0472.10035
[5] Cobham, A., Uniform tag sequences. Math. Systems Theory6 (1972), 164-192. · Zbl 0253.02029
[6] Erdös, P., Szekeres, G., Ü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] Ivi, A., Shiu, P., The distribution of powerful integers. Illinois J. Math.26 (1982), 576-590. · Zbl 0484.10024
[8] Minsky, M., Papert, S., Unrecognizable sets of numbers. J. Assoc. Comput. Mach.13 (1966), 281-286. · Zbl 0166.00601
[9] Sivaramakrishnan, R., Classical theory of arithmetic functions. Monographs and Textbooks in Pure and Applied Mathematics126, Marcel Dekker, Inc., New York, 1989. · Zbl 0657.10001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.