Abstract. We study arithmetical properties of sequences of polynomials defined over some field ${\msbm F}$ and satisfying various linear and nonlinear recurrence relations. Such sequences may describe the sequence of states of cellular automata. Some of the results obtained here are analogues of the corresponding ones for the case of recurrence sequences of integers. On the other hand, we also show that the function and number cases; the cases of one variable and of several variable polynomials; and the characteristic zero and positive characteristic cases for the base field ${\msbm F}$, each display substantial differences.

AMS Subject Classification (1991): 11B37, 11D61, 11D88

Received October 28, 1994, and in revised form March 16, 1995. (Registered under 5673/2009.)