## Question

It's well known that given some sequence points of $$n$$ points $$(x_i, y_i)$$ with $$x_i$$ distinct, that there exists a unique polynomial $$P$$ of degree $$d < n$$ such that for all $$i$$, $$P(x_i) = y_i$$, the Lagrange Interpolating Polynomial.

If all $$x_i, y_i$$ are integers, we can glean from the Lagrange Interpolation Formula that it is guaranteed that $$P(X) \in \mathbb{Q}[X]$$. But does there exist a polynomial $$F(X)$$ of higher degree satisfying the same property ($$F(x_i) = y_i$$) such that its coefficients are all integers?

## Solution

Strangely enough there exists no such polynomial if $$P$$ has some non integer coefficient. Proof is thanks to this mathoverflow answer:

First define $$D(X) \in \mathbb{Z}[X]$$ as $$D(X) = \prod (X - x_i)$$, ie the monic polynomial of degree $$n$$ whose roots are the $$x$$ coordinates of our points.

Next, suppose $$F(X)$$ has coefficients all integers. Since $$D(X)$$ is monic we can write:

$F(X) = D(X)Q(X) + R(X)$

Where $$Q(X), R(X) \in \mathbb{Z}[X]$$, and also $$deg(R(X)) < deg(D(X))$$.

Now we must have $$F(x_i) = R(x_i)$$, but this implies that $$R(X)$$ is the Lagrange interpolating polynomial since it has degree less than $$n$$ and satisfies $$R(x_i) = P(x_i)$$ for all $$i$$. Thus we can re-write:

$P(X) = F(X) - D(X)Q(X)$

Which implies that $$P(X) \in \mathbb{Z}[X]$$ since that latter set is closed under addition and multiplication.