ECCC-Report TR11-002https://eccc.weizmann.ac.il/report/2011/002Comments and Revisions published for TR11-002en-usSun, 09 Jan 2011 01:35:32 +0200
Paper TR11-002
| On the Degree of Univariate Polynomials Over the Integers |
Gil Cohen,
Amir Shpilka,
Avishay Tal
https://eccc.weizmann.ac.il/report/2011/002We 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$.Sun, 09 Jan 2011 01:35:32 +0200https://eccc.weizmann.ac.il/report/2011/002