FpFp-affine recurrent nn-dimensional sequences over FqFq are pp-automatic

A recurrent 22-dimensional sequence a(m,n)a(m,n) is given by fixing particular sequences a(m,0)a(m,0), a(0,n)a(0,n) as initial conditions and a rule of recurrence a(m,n)=f(a(m,n−1),a(m−1,n−1),a(m−1,n))a(m,n)=f(a(m,n−1),a(m−1,n−1),a(m−1,n)) for m,n≥1m,n≥1. We generalize this concept to an arbitrary number of dimensions and of predecessors. We give a criterion for a general nn-dimensional recurrent sequence to be alternatively produced by an nn-dimensional substitution — i.e. to be an automatic sequence. We show also that if the initial conditions are pp-automatic and the rule of recurrence is an FpFp-affine function, then the nn-dimensional sequence is pp-automatic. Consequently all such nn-dimensional sequences can be also defined by nn-dimensional substitution. Finally we show various positive examples, but also a 22-dimensional recurrent sequence which is not kk-automatic for any kk. As a byproduct we show that for polynomials f∈Q[X]f∈Q[X] with deg(f)≥2deg(f)≥2 and f(N)⊂Nf(N)⊂N, the characteristic sequence of the set f(N)f(N) is not kk-automatic for any kk.