Let A be a commutative ring with unit k ≥ 1 an integer. Let T : A k → A k be defined by
T ( x 1, . . . , - x k ) = ( T 1 ( - x 1, . . . , x k ) , . . . , - T k ( x 1 , . . . , x k ) ) ,
where each T i ( x 1, . . . , x k ) belongs to the polynomial ring A [ x 1, . . . , - x k ]. The degree of T is defined as the maximum of the total degrees of T i , 1 ≤ i ≤ k. A polynomial map T and an x 0 ∈ A k determine a sequence x n = T ( x n − 1 ) ( for n ≥ 1 ) of A k, the T-orbit of x 0. Let S ( d , k , A ) denote the set of all orbits of all polynomial maps A k → A k of degree ≤ d. Let &phgr; ( d , k , A ) be the smallest m such that S ( d , k , - A ) is m-prefix distinguishable, and let &phgr;* ( d , k ) be the supremum of &phgr; ( d , k , A ) over all rings A. The purpose of this paper is to examine &phgr;* ( d , k ).
It is a priori not even clear that &phgr; ( d , k , A ) is finite. Hence, theorem 1.1, which states that &phgr;* ( d , k ) < ∞ is surprising. The proof of this result is nonconstructive and uses Hilbert’s basis theorem. The authors were able to calculate the exact values of &phgr;* ( 1 , k ), which is k + 1, and &phgr;* ( d , 1 ), which is d + 1. They prove that if F is an algebraically closed field, &phgr; ( d , k , F ) ≥ and the asymptotic bound &phgr; ( d , k , F ) ≤ d ( 2 k − 1 − 1 ) k + 2 k − 1 ( 1 + O ( 1/d ) ).
The authors applied their results to the problem of extrapolating the value x n + 1 of an unknown polynomial recurrence ( mod M ) in k variables; this problem is known to be of degree ≤ d, given { x i : 0 ≤ i ≤ n } as data, where the modulus M is itself unknown. They give a polynomial time algorithm that produces an extrapolation n + 1, given { x n: 0 ≤ i ≤ n } as input, which fails only for c ( d , k , log 2 M ) values of n , where c ( d , k , log 2 M ) depends only on the given parameters.
I found this paper exceptionally interesting, and I recommend it to everyone interested in recurrence sequences and their applications in cryptography.
