Unique Extrapolation of Polynomial Recurrences
Jeffrey C. Lagarias, James A. Reeds · SIAM Journal on Computing · 1988
Let a sequence of k-dimensional vectors ${\bf x}_0 ,{\bf x}_1 , \cdots $ (over a ring A) be determined by a polynomial recurrence of form ${\bf x}_n = T({\bf x}_{n - 1} )$, where $T:A^k \to A^k $ itself is known to be a polynomial map in k variables of degree at most d but is otherwise unknown. We show that there is a finite N such that the entire sequence $\{ {\bf x}_n :n \geqq 0\} $ can be deduced from the first $N + 1$ terms ${\bf x}_0 ,{\bf x}_1 , \cdots ,{\bf x}_N $ alone. The number $N = \phi (d,k,A)$ depends on d and k and the ring A but not on T. Let $\phi ^ * (d,k)$ denote the maximum of $\phi (d,k,A)$ over all commutative rings with unit. Then we show that $\phi ^ * (d,k) < \infty $. In particular, $\phi ^ * (d,1) = d + 1$ and $\phi ^ * (1,k) = k + 1$. In the general case $\phi ^ * (d,k) \geqq \left( {\begin{array}{*{20}c} {k + d} \\ k \\ \end{array} } \right)$ and equality does not always hold because $\phi ^ * (2,2) \geqq 7$. In addition, we show that for each k that $\max \{ \phi (d,k,{\bf F}):{\bf F}{\text{ a field}}\} $ is bounded by a polynomial in d. These results are applied to the problem of correctly extrapolating the values $\{ {{\bf x}_i :i \geqq 0} \}$ of an unknown polynomial recurrence $(\bmod M)$ in k variables of degree at most d, where d and k are known and M is not known. A polynomial-time algorithm is given which computes a value $\hat {\bf x}_{n + 1} $ given the values $\{ {{\bf x}_i :0 \leqq i \leqq n} \}$ of such a recurrence as input, and it is shown that $\hat {\bf x}_{n + 1} e {\bf x}_{n + 1} $ for at most \[ 1 + \phi ^ * (d,k) + \log \left( {M^{dN} N^{\tfrac{1}{2}N} } \right) \] values of n, where $N = 1 + k\left( {\begin{array}{*{20}c} {k + d} \\ k \\ \end{array} } \right)$.