# Polynomial interpolation over the integers such that all coefficients are from the integers

If one is given $$t$$ different points of a polynomial (all values are from the integers), is it then always possible to construct a polynomial of degree $$t$$ such that it interpolates all points AND all coefficients are from the integers?

Second: What if some of the points correspond to derivatives? So can the Brikhoff interpolation problem with $$t$$ points given be used to interpolate a polynomial of degree $$t$$ such that all coefficients are from the integers?

Note that it is wanted that we are only given $$t$$ points to interpolate a polynomial of degree $$t$$. This gives one degree of freedom. Otherwise it is easy to find a counterexample.

First question: Let $$x_1,x_2, \ldots, x_t \in \mathbb{N}_0$$ such that all $$x_i$$ are distinct and ordered, i.e., $$0\leq x_1 < x_2 < x_3 < \ldots < x_t$$. And let let $$y_1,y_2, \ldots, y_t \in \mathbb{Z}$$. Does there exist a polyonimial $$f(x) = a_0 + a_1x + a_2 x^2 + \ldots + a_t x^t$$ such that for all $$i$$ it holds that $$f(x_i)=y_i$$ and all $$a_j \in \mathbb{Z}$$.

Second question: Now assume that $$c_1^{i_1}, c_2^{i_2}, \ldots, c_t^{i_t} \in \mathbb{Z}$$, where $$i_j \in \mathbb{N}_0$$ is just an indice (not the power). For these indices it holds that $$0 \leq i_0 \leq i_1 \leq \ldots \leq i_t < t$$ and at least one $$i_j > 0$$.

Does there exist a polyonimial $$f(x) = a_0 + a_1x + a_2 x^2 + \ldots + a_t x^t$$ such that for all $$j$$ it holds that $$f^{i_j}(x_j)=c_j^{i_j}$$ and all $$a_j \in \mathbb{Z}$$, where $$f^{i_j}(x)$$ denotes the $$i_j$$-th derivative of $$f(x)$$.

I tried to solve the second question with Birkhoff interpolation. The Birkhoff interpolation can be used to reconstruct the function and also single coefficients: The interpolation of one coefficient is based on a matrix $$A$$ which is determined by all $$x_j$$ and $$c_j^{i_j}$$. Then a coefficient $$a_{k-1}$$ is computed as $$det(A_k)/det(A)$$ where $$A_k$$ is obtained from $$A$$ by replacing the $$k$$-th column of $$A$$ with the $$c_j^{i_j}$$ in lexicographic order. However, I'm not able to proof that $$det(A_k)/det(A) \in \mathbb{Z}$$. Note that if we want to interpolate the polynomial of degree $$t$$ with only $$t$$ points/derivatives given, then we have to see the birkhoff interpolation problem as a problem where we are given $$t+1$$ points/derivates but we are allowed to modify one point $$(x_z,c_z^{i_z})$$ arbitrarily.

The problem is also closely related to determinants, but I have very little knowledge in this area.

Until now, I couldn't construct a counterexample for it or proof it.

A proof, counterexample or any hints where to get additional information would be great! Or maybe someone knows something about the eigenvalues of the matrix of the Birkhoff interpolation?

• I edited the restriction on the $x_i$ to be in the natural numbers including zero. And for the second problem that we have at least one derivative. – ZoDiaC Jul 13 '18 at 8:03

In general this is not true. Take $t=2, x_1=-1,x_2=1,y_1=0,y_2=1$. Then $a_0-a_1+a_2=0, a_0+a_1+a_2=1$. Adding this equations results in $2(a_0+a_2)=1$ which is impossible for integers $a_0,a_2$.
• Thanks for the fast reply. I had a small mistake in my $x_i$ that they need to be in the natural numbers and not in the integers. Will it still fail? Especially for the second case? – ZoDiaC Jul 13 '18 at 7:59
• I got your idea, and now I can reconstruct a counter example for the first case: $x_1=2, x_2=4,y_1=0,y_2=1$, then $a_0 + 2 a_1 + 4 a_2 = 0$ and $a_0 + 4 a_1 + 16 a_2 = 1$, however subtracting these two equations implies that $2 (a_1 + 6 a_2) = 1$ which is still impossible for $a_i$ beeing an integer. – ZoDiaC Jul 13 '18 at 8:09