# 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