# The biggest possible degree of a polynomial given a condition

Let $P(x) \in R[x]$ be a polynomial with real coefficients such that $$(\forall n \in \mathbb N)(\exists q \in \mathbb Q)(P(q)=n)$$

What's the biggest possible value of $\deg P$? ($\deg P$ is the degree of polynomial $P$)

I have literally no clue as where to start, and a hint would be more then enough.

• I suppose the answer is $1$ and for degrees $d>1$ one obtains something like unusually good rational approximations for $\sqrt[d]n$ Commented May 16, 2016 at 21:39

An initial observation: If $P(x_n) = n$ for each $n$, then the sequence $(x_n)$ can not have an accumulation point, or else $P$ would have a singularity there, a contradiction (since $P$ is a polynomial).

Let's try $P(x) =ax+2+bx+c$.

If $P(x) = n$, then $ax^2+bx+c=n$, so $x =\dfrac{-x\pm\sqrt{b^2-4a(c-n)}}{2a}$, so $b^2-4a(c-n) =r^2$ or $n =\dfrac{r^2-b^2}{4a}+c$. For $n+1$, $n+1 =\dfrac{s^2-b^2}{4a}+c$ for some rational $s$.

Subtracting, $1 =\dfrac{s^2-r^2}{4a}$ or $4a =s^2-r^2$ or $s-r =\dfrac{4a}{s+r}$.

Since $(x_n)$ does not have an accumulation point, we can make $|s|$ and $|r|$ arbitrarily large.

But then we can make $s-r$ arbitrarily small, so $(x_n)$ would have an accumulation point at zero.

Therefore $P$ can not be of degree 2.
• We can do better than "no accumulation point": If $P(x_n)=n$ then in fact we have to have $|x_n|\rightarrow\infty$. For large enough $x$, $P\rightarrow\pm\infty$ monotonely "on each side", and in between $P$ is bounded. So for large enough $n$, $x_n$ has to lie in the monotone bits and hence its absolute value has to $\rightarrow\infty$. Commented May 17, 2016 at 12:26