# One polynomial problem

It's known that a polynomial $f\in\mathbb{C}[x]$, whose degree is $n$, possesses integer values at each of the points: $0,1,4,\ldots,n^2$. Prove that this polynomial possesses an integer value at $m^2$ for any $m$.

-
In what field of numbers do the coefficients of your polynomial lie? $\mathbb{Z}$? $\mathbb{Q}$? $\mathbb{R}$? –  D_S Dec 25 '12 at 17:18
Sorry, I forgot to add this information. They are complex numbers. –  Michael Dec 25 '12 at 17:20
I tried to use interpolation ( Lagrange polynomial for example ), but I don't know how to use it correctly in this problem. –  Michael Dec 25 '12 at 17:34
Apparently I have the same problem. :) –  Hurkyl Dec 25 '12 at 17:36

The polynomial $g(x) = f(x^2)$ takes integer values at $0,\pm 1,\ldots,\pm n$, so it suffices to show that $g(x-n)$ (which has degree $2n$ and integer values at $0,\ldots,2n$) takes an integer value at $m$ for any $m$. This is easy to see by writing $g(x-n)$ in terms of the basis $\binom{x}{0},\binom{x}{1},\binom{x}{2},\ldots$ for the space of polynomials.

-
+1 $\text{Very nice!}$ –  Sasha Dec 25 '12 at 19:18

The first version of this answer contained a mistake. I've corrected that and made it community wiki in case someone might find it useful.

The following proposition, combined with the beautiful observation of D. Savitt that if we define $g(x)=f(x^2)$, the polynomial $g(x-n)$ is of degree $2n$ and has integer values at $0,1,\ldots,2n$, gives another way to solve the problem.

Proposition. Suppose $g\in\mathbb C[x]$ is a polynomial of degree $n$ and $g(k)$ is an integer for $k=0,1,\ldots,n$. Then $g(k)$ is an integer for all $k\in\mathbb Z$.

Proof. We proceed by induction on $n$. Clearly, the claim holds for $n=0$, since in this case, the polynomial is constant, and thus if has one integer value, it is integer everywhere. For the inductive step, assuming $g$ is of degree $n+1$ and $g(k)$ is integer for $k=0,1,\ldots,n+1$, define a new polynomial $h$ by $h(x) = g(x+1)-g(x)$. Now, the highest degree terms of $g(x+1)$ and $g(x)$ cancel in $h$ and thus $h$ is of degree $n$. Furthermore, by the assumptions on $g$ we have that $h(k)$ is an integer for $k=0,1,\ldots,n$. Therefore by the inductive hypothesis $h(k)$ is integer for $k\in\mathbb Z$. But this means $g(k+1)-g(k)$ is an integer for every $k\in\mathbb Z$. Since $g(0)$ is an integer, it follows that $g(k)$ is an integer for all $k\in\mathbb Z$. $\square$

-