Linear recurrences, dynamics, and finite-state machines

Jason Bell, University of Waterloo

Thursday, February 20th, 2020
3:30 PM - 4:30 PM
Hylan 1106A

A sequence $a_0,a_1,a_2,\ldots $ satisfies a linear recurrence over the complex numbers if there is some $d\ge 1$ and constants $c_1,\ldots c_d$ such that $a_n=c_1 a_{n-1}+\cdots + c_d a_{n-d}$ for $n$ sufficiently large. A celebrated result of Skolem, Mahler, and Lech says that if $a_n$ is a sequence that satisfies a linear recurrence then the set of $n$ for which $a_n=0$ is a finite union of infinite arithmetic progressions along with a finite set. We show how this can be recast in a purely dynamical framework and use this to give a geometric generalization. We also show that these results no longer hold in positive characteristic and how one can use finite-state machines to get an analogue of these results in positive characteristic. This is joint work with Dragos Ghioca and Tom Tucker and also joint work with Boris Adamczewski.

Event contact: jriveral at ur dot rochester dot edu