Polynomial subsequences of certain automatic sequences (Q1311048): Difference between revisions

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