Multiplicative functions and \(k\)-automatic sequences (Q1606180)

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}\).