1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ZoDiaC Jul 13 '18 at 8:03
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – ZoDiaC Jul 13 '18 at 7:59
  • 1
    $\begingroup$ 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. $\endgroup$ – ZoDiaC Jul 13 '18 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.