Polynomial subsequences of certain automatic sequences (Q1311048): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
Normalize DOI. |
||
(One intermediate revision by one other user not shown) | |||
Property / DOI | |||
Property / DOI: 10.5802/jtnb.82 / rank | |||
Property / cites work | |||
Property / cites work: Somme des chiffres et transcendance / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Finite automata in number theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Generalized Rudin-Shapiro sequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The ring of \(k\)-regular sequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Suites algébriques, automates et substitutions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Uniform tag sequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Folds! / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3803206 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3988089 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4012525 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3764203 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3798750 / rank | |||
Normal rank | |||
Property / DOI | |||
Property / DOI: 10.5802/JTNB.82 / rank | |||
Normal rank |
Latest revision as of 17:57, 10 December 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Polynomial subsequences of certain automatic sequences |
scientific article |
Statements
Polynomial subsequences of certain automatic sequences (English)
0 references
26 January 1994
0 references
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\).
0 references
polynomial subsequences
0 references
automatic sequence
0 references