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?
No comments:
Post a Comment