Polynomial subsequences of certain automatic sequences
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\).
- Finite automata in number theory
- Folds!
- Generalized Rudin-Shapiro sequences
- scientific article; zbMATH DE number 4021221 (Why is no real title available?)
- scientific article; zbMATH DE number 4065109 (Why is no real title available?)
- scientific article; zbMATH DE number 4071020 (Why is no real title available?)
- scientific article; zbMATH DE number 32088 (Why is no real title available?)
- scientific article; zbMATH DE number 64882 (Why is no real title available?)
- Somme des chiffres et transcendance
- Suites algébriques, automates et substitutions
- The ring of k-regular sequences
- Uniform tag sequences
- Sums and rational multiples of \(q\)-automatic sequences are \(q\)-automatic
- Factors of generalised polynomials and automatic sequences
- Generalized Thue-Morse sequences of squares
- On a universal extraction procedure
- How to prove that a sequence is not automatic
- Pseudorandom sequences derived from automatic sequences
- Cyclotomic properties of polynomials associated with automatic sequences
- On the subword complexity of Thue-Morse polynomial extractions
- Linear independence of automatic formal power series
- Subsequences of automatic sequences and uniform distribution
- On subsequences of arithmetic sequences
- Subsequences of automatic sequences indexed by n^c and correlations
- On q-quasiadditive and q-quasimultiplicative functions
- Automatic sequences and generalised polynomials
- F_p-affine recurrent n-dimensional sequences over F_q are p-automatic
- Counterexamples to the p(t)-adic Littlewood conjecture over small finite fields
This page was built for publication: Polynomial subsequences of certain automatic sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1311048)
