4
$\begingroup$

Let $D=\{d_1, d_2, \ldots, d_n\}$ be an integer set. I'd like to know if I can interpolate any collection of $n$ points $(x_1, y_1), (x_2, y_2), \ldots, (x_{n}, y_{n})$ by a polynomial whose degree lie in $D$. In other words, I am looking for a polynomial of the form $p(x) = \sum_{i=1}^n p_i x^{d_i}$ such that $p(x_i) = y_i$, for all $i=1, \ldots, n-1$.

Obviously, it is always possible to find such a polynomial if $D = \{0,1, \ldots, n-1\}$. On the other hand, if every element of $D$ is even, then this is not possible, since $p(x)$ would have to be even, and I can choose points $(x_i,y_i)$ breaking that. Likewise, if every element of $D$ is odd, then $p(x)$ will be odd, and interpolation is not always possible.

I'm hoping it is known exactly for which sets $D$ interpolation is possible but, barring that, any references to related literature would be appreciated.

$\endgroup$
2
$\begingroup$

I guess you mean that all $x_i$'s are different. Then the interpolation is always possible if and only if the $n\times n$ determinant $F(x_1,\dots,x_n)=\det(x_i^{d_j})$ is non-zero. $F$ is antisymmetric polynomial, thus divisible by $V=\prod_{i<j}(x_i-x_j)$. The fraction is known as a Schur function with parameters $d_1,d_2-1,d_3-2,\dots,d_n-(n-1)$, where we suppose that $d_1\leqslant d_2\leqslant d_3\leqslant \dots \leqslant d_n$. So your question rephrases as: which Schur functions take only positive values at points with mutually distinct coordinates. Sometimes it is indeed so: say, if $d_i=i-1$ for $i<n$ and $d_n=n$, then the Schur function is the complete symmetric polynomial $h_2=\sum_{i<j} x_ix_j+\sum x_i^2=\frac12((\sum x_i)^2+\sum x_i^2)>0$ unless $x_1=\dots=x_n=0$. I expect that the literature on symmetric functions contains the full answer.

$\endgroup$
2
$\begingroup$

The two cases you mention could be problems as would the case that $x_1=0 \neq y_1$ and the degrees are positive. As one more example, the determinant:

$$ \left| \begin {array}{ccc} 1&1&1\\ {a}^{2}&{b}^{2}& {c}^{2}\\ {a}^{3}&{b}^{3}&{c}^{3}\end {array} \right|=(b-a)(c-a)(c-b)(ab+bc+ca).$$

So you can find coefficients $q,r,s$ with $y=qx^3+rx^2+s$ interpolating the points $(a,y_1),(b,y_2),(c,y_3)$ as long as $c \neq \frac{-ab}{a+b}$, for example if $a,b,c$ are all positive. But if $c = \frac{-ab}{a+b}$ there are no solutions except for one value of $y_3$ when there are infinitely many.

On the other hand,

$$ \left| \begin {array}{ccc} 1&1&1\\ {a}&{b}& {c}\\ {a}^{4}&{b}^{4}&{c}^{4}\end {array} \right|=(b-a)(c-a)(c-b)(a^2+b^2+c^2+ab+bc+ca).$$

It is not hard to see that the final factor is non-zero for distinct real $a,b,c$ so here interpolation is always possible (over $\mathbb{R}$.)

In general the appropriate determinant is the product of the standard Vandermonde determinant $ \prod_{i \lt j}(x_j-x_i)$ and a symmetric polynomial of the $n$ variables. This final factor, or sometimes the entire determinant, is called a Schur Polynomial. So you might want to look into those polynomials.

$\endgroup$

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.