Fp-affine recurrent -dimensional sequences over Fq are p-automatic

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