Polynomial subsequences of certain automatic sequences
type: Item
instance of: scholarly article
title: Polynomial subsequences of certain automatic sequences
zbMATH Open document ID: 0795.11009
author: Olivier Salon
author: Jean-Paul Allouche
published in: Journal de Théorie des Nombres de Bordeaux
publication date: 1994-01-26T00:00:00Z
full work available at URL: http://www.numdam.org/item
full work available at URL: https://eudml.org/doc/93566
review text: An automatic sequence \(u= (u(n))_ n\), that is a sequence recognizable by a finite automaton in base \(B\), can be characterized by the property that there are only a finite number of different sequences among the subsequences \((u (B^ k n+r))_ n\) for \(k\geq 0\) and \(0\leq r\leq B^ k-1\). If \((u(n))_ n\) is \(B\)-automatic, then so is the subsequence \(*u(an+b))_ n\) for any natural numbers \(a\) and \(b\). What can be said about the subsequence \(u\circ R= (u(R(n)))_ n\) where \(R\) is an integral polynomial? The sum \(s_ B(n)\), reduced modulo \(B\), of the digits of \(n\) in base \(B\) is \(B\)-automatic. Motivated by this example, the authors call \(u\) quasi strongly \(B\)-additive if \(u(B^ \gamma n+r)= u(n)+ u(r)\) for all \(\gamma\), \(n\) and \(r\) provided only that \(\gamma\) is sufficiently large in terms of \(r\). The main theorem then asserts that if \(R\) is a polynomial of degree at least 2 with \(R(N)\subset N\), \(u\) is quasi strongly \(B\)-additive and \(u\circ R\) is \(B\)-automatic, then \(u\) must be periodic. The proof is characteristically ingenious. It starts with the observation that if \(v\) is \(B\)-automatic and \(f_ n(x)= v(B^{x+(d-2)n} (B^ n+1)+1)\), then there is a positive integer \(T\) such that \(f_ n(n)= f_ n(n+T)\) for all sufficiently large \(n\). If \(u\) is quasi strongly \(B\)- additive and \(u\circ R\) is \(B\)-automatic, this leads to an additivity property \(u(\lambda (t+1)+\nu)= u(\lambda t+\nu)+ u(\lambda)\) for certain \(\lambda\) and \(\nu\) and then, since \(u\) takes only finitely many values, to the periodicity property for \(u\).
Mathematics Subject Classification ID: 11B85
zbMATH DE Number: 484165
zbMATH Keywords: polynomial subsequences
zbMATH Keywords: automatic sequence
reviewed by: John H. Loxton
MaRDI profile type: Publication
OpenAlex ID: W2053898424
cites work: Somme des chiffres et transcendance
cites work: Finite automata in number theory
cites work: Generalized Rudin-Shapiro sequences
cites work: The ring of \(k\)-regular sequences
cites work: Suites algébriques, automates et substitutions
cites work: Uniform tag sequences
cites work: Folds!
cites work: Q3803206
cites work: Q3988089
cites work: Q4012525
cites work: Q3764203
cites work: Q3798750
DOI: 10.5802/JTNB.82
description: scientific article; zbMATH DE number 484165