# Integer valued polynomial through some known points

I have 2 questions, but I'll put both of them here since they are closely related:

An integer valued polynomials $P(x)$ is a polynomial whose value $P(n)\in\mathbb{N}$ for every $n\in\mathbb{N}$.

1-I'm given a set of points with integer coordinates, I know it's possible to construct a Lagrange polynomial passing through them, but is it possible to construct an integer-valued polynomial passing through them? If yes, how? (I'm interested in a generic solution, not in one for a specific set of points)

2-I'm given a set of points with coordinates $(x_i,y_i)$ but this time some or all the $x_i$ are rational numbers, is it still possible to construct an integer valued polynomials passing through these points?

Edit: I reposted on MO this question, where it was answered.

• The answer to your first question is yes. This is discussed on Math Overflow, in a very accessible way. Mar 30, 2014 at 20:36
• For the second question, we need additional conditions. For example, there is no integer-valued polynomial $P$ such that $P(0)=1$ and $P(\pi)=0$. For an integer-valued polynomial has rational coefficients, and $\pi$ is transcendental. Mar 30, 2014 at 21:10
• Thanks for the link, I'm reading it right now. For the second question let's say all the given points have rational coordinates, since it isn't always possible with real ones Mar 30, 2014 at 21:25
• If $x_i$'s are rational numbers and $y_i$'s are integers, then it is a simple corollary of the first question: there exists a nonzero integer $n$, such that $nx_i$'s are integer, so there exists integer valued polynomial $Q$, s.t. $Q(nx_i)=y_i$. Then $P(x):=Q(nx)$ is a solution. Apr 2, 2014 at 15:51
• Nice answer! I am also interested in the case where both the $x_i$ and the $y_i$ are rational though, any idea about that one? Apr 2, 2014 at 16:30

1 given arbitrary values $y_0,y_1,y_2,\ldots,y_n$ we can compute the values $p(k)$ of the degree $\le n$ polynomial with $p(j)=y_j$, $0\le j\le n$ with the method of repeated differences. As a consequence, if all $y_i$ are integers, $p(x)$ will be an integer whenever $x$ is an integer. But can we (possibly by switching to a higher degree) ensure that $p(x)$ will be natural for natural $x$? Yes! Just use $m=1$ in the following
Proposition. Given $y_0,\ldots, y_n\in\mathbb Z$ and $m\in\mathbb Z$ there exists a polynomial $P(X)$ such that $P(k)\in\mathbb Z$ for $k\in \mathbb Z$, $P(k)=y_i$ for $0\le k\le n$, and $P(k)\ge m$ for $k>n$.
Proof. The case $n=0$ is easy: If $y_0\ge m$ take $P(x)=y_0$; and if $y_0< m$, take $P(x)=(m-y_0)x-y_0$. For the induction step, consider $y_0'=y_1-y_0,\ldots, y_{n-1}'=y_n-y_{n-1}$ and $m'=\max\{m-y_n,0\}$, find a polynomial $Q$ accordingly and consider $P(k)=y_0+\sum_{i=0}^{k-1}Q(i)$, which is indeed a polynomial (with $Q(x)=P(x+1)-P(x)$ as difference polynomial). The desired properties are readily checked. $_\square$
2 No. Any integer-valued polynomials necessarily have rational coefficients, hence cannot pass through $(\pi,\frac12)$, for example.
• Hm, that would translate (in the language of the first proposition) to an additional requirement of the form $q|P(qk)$ for all $qk>n$. This seems to be tricky if $q\not|y_n$ ... Apr 9, 2014 at 6:15