# 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. – André Nicolas Mar 30 '14 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. – André Nicolas Mar 30 '14 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 – Alessandro Codenotti Mar 30 '14 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. – user104254 Apr 2 '14 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? – Alessandro Codenotti Apr 2 '14 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$ ... – Hagen von Eitzen Apr 9 '14 at 6:15