We study the following problem raised by von zur Gathen and Roche:

What is the minimal degree of a nonconstant polynomial $f:\{0,\ldots,n\}\to\{0,\ldots,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,\ldots,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)$. Furthermore, the same conclusion holds even if $m=O(n^{1.475-\epsilon})$. In other words, there are no polynomials of intermediate degrees that map $\{0,\ldots,n\}$ to $\{0,\ldots,m\}$.

Moreover, we give a meaningful answer when $m$ is a large polynomial, or even exponential, in $n$. Consider the case $m=\frac{1}{d!}\cdot \left(\frac{n-d}{2e}\right)^{d}$. $f$ can of
course be a degree $d-1$ polynomial, e.g., $f(x)=x^{d-1}$ or even $f(x) = {x-n/2 \choose d-1}$ (whose range is bounded by ${n/2 \choose d-1}$). We show that when $d\leq 2n/15$, either $\deg(f)\leq d-1$ or $f$ must satisfy $\deg(f) \ge n/3 -O(d\log n)$. Stated differently, if we remove the `trivial' cases where $f$ is of degree at most $d-1$, the next example must have a very high degree. So, again, no polynomial of intermediate degree mapping $\{0,\ldots,n\}$ to $\left\{0,\ldots,\frac{1}{d!}\cdot \left(\frac{n-d}{2e}\right)^{d}\right\}$ exists.

We complement these results by showing that for every $d=o(\sqrt{n}/\log n)$ there exists a polynomial $f:\{0,\ldots,n\} \to \{0,\ldots,O(n^{d+0.5})\}$ of degree $n/3 -O(d\log n)\leq \deg(f) \leq n-O(d\log(n))$.

Our work considerably extends the results of von zur Gathen and Roche that studied the case $m=1$.