Integer valued polynomial through some known points

Question

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

An integer valued polynomial $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 polynomial passing through these points?

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

Answer 1

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.

Answer 2

Although this is not an answer to any of your questions, it is definitely in the same flavor. So I want to share that here.

Claim: Let $r_0,\ldots,r_n$ be integers, and $p(x)$ be the Lagrange interpolation polynomial of degree at most $n-1$ such that $p(r_i)=r_{i+1}~ (i\in\{0,\ldots,n-1\})$. If you can find a polynomial $q(x)$ with integer coefficients such that $q(r_i)=r_{i+1}~ (i\in\{0,\ldots,n-1\})$, then $p$ must also be over $\mathbb{Z}$.

This result has been used in a paper of mine to study iterations of polynomials with integer coefficients. For a proof see Lemma 2.2 of https://arxiv.org/abs/2401.01435 .