Automatic sequences and generalised polynomials
From MaRDI portal
Directed graphs (digraphs), tournaments (05C20) Recurrences (11B37) Automata sequences (11B85) Distribution modulo one (11J71) Relations between ergodic theory and number theory (37A44) Dynamical systems involving transformations and group actions with special properties (minimality, distality, proximality, expansivity, etc.) (37B05) Symbolic dynamics (37B10)
Abstract: We conjecture that bounded generalised polynomial functions cannot be generated by finite automata, except for the trivial case when they are ultimately periodic. Using methods from ergodic theory, we are able to partially resolve this conjecture, proving that any hypothetical counterexample is periodic away from a very sparse and structured set. In particular, we show that for a polynomial with at least one irrational coefficient (except for the constant one) and integer , the sequence is never automatic. We also prove that the conjecture is equivalent to the claim that the set of powers of an integer is not given by a generalised polynomial.
Recommendations
Cites work
- \(p\)-adic valuations and \(k\)-regular sequences
- p-regularity of the p-adic valuation of the Fibonacci sequence
- A canonical form and the distribution of values of generalized polynomials
- A generalization of automatic sequences
- A little more about morphic Sturmian words
- A new proof of Szemerédi's theorem
- A Skolem-Mahler-Lech theorem in positive characteristic and finite automata
- An arithmetic regularity lemma, an associated counting lemma, and applications
- An inverse theorem for the Gowers \(U^{s+1}[N]\)-norm
- Analytic functions over \(\mathbb Z_p\) and \(p\)-regular sequences
- Automatic Sequences
- Characterizing regular languages with polynomial densities
- Continued fractions of algebraic power series in characteristic 2
- Distribution of values of bounded generalized polynomials
- Ergodic theory. With a view towards number theory
- Factors of generalised polynomials and automatic sequences
- Finding the growth rate of a regular or context-free language in polynomial time
- Finite automata and algebraic extensions of functions fields
- Function fields in positive characteristic: expansions and Cobham's theorem
- Generalization of automatic sequences for numeration systems on a regular language
- Gowers norms for the Thue-Morse and Rudin-Shapiro sequences
- scientific article; zbMATH DE number 3871452 (Why is no real title available?)
- scientific article; zbMATH DE number 3719449 (Why is no real title available?)
- scientific article; zbMATH DE number 29940 (Why is no real title available?)
- scientific article; zbMATH DE number 3497806 (Why is no real title available?)
- scientific article; zbMATH DE number 1333603 (Why is no real title available?)
- scientific article; zbMATH DE number 1973372 (Why is no real title available?)
- scientific article; zbMATH DE number 1737190 (Why is no real title available?)
- scientific article; zbMATH DE number 2220973 (Why is no real title available?)
- Linear equations over multiplicative groups, recurrences, and mixing. II
- Non-Regularity of ⌊α + log k n⌋
- On certain formal properties of grammars
- On some questions regarding \(k\)-regular and \(k\)-context-free sequences
- On Sturmian sequences which are invariant under some substitutions
- On substitution invariant Sturmian words: an application of Rauzy fractals
- On the base-dependence of sets of numbers recognizable by finite automata
- On uniformity of \(q\)-multiplicative sequences
- On vanishing coefficients of algebraic power series over fields of positive characteristic
- Polynomials Involving the Floor Function.
- Regularity of a function related to the 2-adic logarithm
- Sets of large values of correlation functions for polynomial cubic configurations
- Sparse generalised polynomials
- Strict Ergodicity and Transformation of the Torus
- The quantitative behaviour of polynomial orbits on nilmanifolds
- The ring of k-regular sequences
- The ring of \(k\)-regular sequences. II.
- Two notes on subshifts
- Uniform distribution of generalized polynomials
- Uniform distribution of generalized polynomials of the product type
- Uniform tag sequences
- When is an automatic set an additive basis?
Cited in
(16)- Polynomial subsequences of certain automatic sequences
- Multiplicative functions and \(k\)-automatic sequences
- Factors of generalised polynomials and automatic sequences
- A canonical form and the distribution of values of generalized polynomials
- Automata and finite order elements in the Nottingham group
- Cyclotomic properties of polynomials associated with automatic sequences
- Can you hear the shape of a Beatty sequence?
- scientific article; zbMATH DE number 6499262 (Why is no real title available?)
- Sparse generalised polynomials
- A generalization of automatic sequences
- On multiplicative automatic sequences
- Bracket words: A generalisation of Sturmian words arising from generalised polynomials
- Generalised polynomials and integer powers
- On asymptotically automatic sequences
- A graph-theoretic proof of Cobham's dichotomy for automatic sequences
- On the generating series of the degree sequence
This page was built for publication: Automatic sequences and generalised polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5222169)
