4

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.

Thanks in advance.

Michael Hardy
  • 1
windircurse
  • 1,894
  • I suppose the answer is $1$ and for degrees $ d>1$ one obtains something like unusually good rational approximations for $\sqrt[d]n$ – Hagen von Eitzen May 16 '16 at 21:39

1 Answers1

1

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.

This is a contradiction.

Therefore $P$ can not be of degree 2.

I'm not sure how to generalize this, since it depends on the explicit solution for quadratics.

I'll leave it at this and hope that someone can use the ideas in this answer.

marty cohen
  • 107,799
  • 1
    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$. – Gareth McCaughan May 17 '16 at 12:26