Univariate polynomial interpolation with restricted degrees

Question

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.

Answer 1

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.

Answer 2

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.