Note on the local growth of iterated polynomials

The local behavior of the iterates of a real polynomial is investigated. The fundamental result may be stated as follows: THEOREM. Let x_i, for i=1, 2, ..., n+2, be defined recursively by x_i+1=f(x_i), where x₁ is an arbitrary real number and f is a polynomial of degree n. Let x_i+1-x_i≧1 for i=1, ..., n + 1. Then for all i, 1 ≦i≦n, and all k, 1≦k≦n+1-i, {Mathematical expression} where f[x_i, ..., x_i+k] denotes the Newton difference quotient. As a consequence of this theorem, the authors obtain information on the local behavior of the solutions of certain nonlinear difference equations. There are several cases, of which the following is typical: THEOREM. Let {x_i}, i = 1, 2, 3, ..., be the solution of the nonlinear first order difference equation x_i+1=f(x_i) where x₁ is an arbitrarily assigned real number and f is the polynomial {Mathematical expression}. Let δ be positive with δ^n-1=|2^n-1/n!a_n|. Then, if n is even and a_n<0, there do not exist n + 1 consecutive increments Δx_i=x_i+1-x_i in the solution {x_i} with Δx_i≧δ. The special case in which the iterated polynomial has integer coefficients leads to a "nice" upper bound on a generalization of the van der Waerden numbers. A p_k-sequence of length n is defined to be a strictly increasing sequence of positive integers {x₁, ..., x_n} for which there exists a polynomial of degree at most k with integer coefficients and satisfying f(x_j)=x_j+1 for j=1, 2, ..., n-1. Define p_k(n) to be the least positive integer such that if {1, 2, ..., p_k(n)} is partitioned into two sets, then one of the two sets must contain a p_k-sequence of length n. THEOREM. p_n-2(n)≦(n!)^(n-2)!/2.