On the degree of univariate polynomials over the integers

摘要

Abstract We study the following problem raised by von zur Gathen and Roche [6]: What is the minimal degree of a nonconstant polynomial f: {0,..., n} → {0,..., m}? Clearly, when m = n the function f(x) = x has degree 1. We prove that when m = n — 1 (i.e. the point {n} is not in the range), it must be the case that deg(f) = n — o(n). This shows an interesting threshold phenomenon. In fact, the same bound on the degree holds even when the image of the polynomial is any (strict) subset of {0,..., n}. Going back to the case m = n, as we noted the function f(x) = x is possible, however, we show that if one excludes all degree 1 polynomials then it must be the case that deg(f) = n — o(n). Moreover, the same conclusion holds even if m=O(n 1.475-?). In other words, there are no polynomials of intermediate degrees that map {0,...,n} to {0,...,m}. Furthermore, we give a meaningful answer when m is a large polynomial, or even exponential, in n. Roughly, we show that if $$m (_{,,,d}^{n/c} )$$ m ( d n / c ) , for some constant c, and d≤2n/15, then either deg(f) ≤ 展开▼