Sums and rational multiples of \(q\)-automatic sequences are \(q\)-automatic (Q1208730): Difference between revisions

Let us recall that a \(q\)-automatic sequence \((u_ n)_{n \geq 0}\) on the alphabet \({\mathcal A} = \{a_ 0,a_ 1,\dots,a_{r-1}\}\) is a sequence such that all the languages \(L_ j = \{\)base-\(q\) expansion of \(n\), \(u_ n = a_ j\}\subset \{0,1,\dots,q-1\}^*\) are rational. A theorem of \textit{G. Christol}, \textit{T. Kamae}, \textit{M. Mendès-France} and \textit{G. Rauzy} [Bull. Soc. Math. Fr. 108, 401-419 (1990; Zbl 0472.10035)] asserts that a sequence \((u_ n)_{n \geq 0}\) with values in \(\mathbb{F}_ q\) is \(q\)-automatic if and only if the formal power series \(\sum_{n \geq 0} u_ nx^ n\) is algebraic over \(\mathbb{F}_ q(x)\). Hence the sum and product of two \(q\)-automatic formal power series are \(q\)-automatic (indeed they are algebraic over \(\mathbb{F}_ q(x)\)). The author addresses the same question where \(\sum u_ nx^ n\) is replaced by \(\sum u_ n/r^ n\), (\({\mathcal A} = \{0,1,\dots,r-1\}\)). The somewhat surprising answer is that the sum of two ``\(q\)-automatic real numbers'' is also \(q\)- automatic, and that the product of such a number by a rational number is also \(q\)-automatic. The difficulty -- of course -- is to keep carries under control! Note that this result can be compared to, (but is different from) results of C. Frougny [see \textit{C. Frougny}, Math. Syst. Theory 25, 37-60 (1992), \textit{D. Berend} and \textit{C. Frougny}, Computability by finite automata and Pisot bases, Math. Syst. Theory (to appear), and \textit{C. Frougny} and \textit{B. Solomyak}, On representations of integers in linear numeration systems (preprint)], where the carry goes to infinity, although in Lehr's paper the carry ``comes from infinity''. Note also that from a theorem of Loxton and van der Poorten, the result of Lehr gives a (countable) set, containing only rational and transcendental numbers, which is a \(\mathbb{Q}\)-vector space! My last remark is that the word ``sequences'' in the title should have been replaced by ``real numbers''.