The automaticity conjecture for generalised-polynomial sequences

Let f ⁣:N0Ωf\colon\mathbb{N}_0\to\Omega be a sequence, where Ω\Omega is a finite alphabet. Call ff automatic if it is generated by a finite automaton, and call it a generalised-polynomial sequence if its values are given by a generalised polynomial. A sequence is ultimately periodic if it agrees with a periodic sequence outside a finite set. Automaticity conjecture. If a sequence ff is simultaneously automatic and generalised polynomial, then ff is ultimately periodic. This is the sequence formulation of the paper's motivating conjecture. The authors note that the Fibonacci word supplies a nontrivial generalised-polynomial sequence for a Zeckendorf-type notion of automaticity, while the conjecture concerns the usual positional notion; partial results are proved, but the general statement remains open.

Sources & referencesView supporting material

Primary source

Jakub Byszewski and Jakub Konieczny, “Automatic sequences and generalised polynomials”, arXiv:1705.08979 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.