Finding an interpolating polynomial on a set of points such that the polynomial only has extrema on those points

Suppose that we have an arbitrary set of points $S\subseteq\mathbb{C^2}$ and want to find a polynomial $P(X)$ such that $(x,y)\in S\Rightarrow y=P(x)$ and $P'(x)=0\Rightarrow (x, P(x))\in S$. In other words, find a polynomial that passes through all of the points but has no extrema except possibly at those points.

Because the zeros of the derivative of the polynomial are limited, $P'(X)=A(X-x_1)^{n_1}(X-x_2)^{n_2}...(X-x_{|S|})^{n_{|S|}}$ for some $n\in \mathbb N, A\in \mathbb C$ where $\forall x_k,\exists y_k$ such that $(x_k, y_k)\in S$. This can be integrated simply after expanding, so $P(X)=A\int((X-x_1)^{n_1}(X-x_2)^{n_2}...(X-x_{|S|})^{n_{|S|}})+C$ is the form of the polynomial.

If any two points have the same y-value, no polynomial can pass through both of them, so any set $S$ with that condition has no polynomial $P(X)$ fitting the conditions.

If $\exists (x_i,y), (x_j, y) \in S$ such that $x_i<x_k<x_j\Rightarrow\nexists y_k$ such that $(x_k, y_k)\in S$, the existence of such a polynomial can be ruled out. If a polynomial passes through $(x_i, y)$ and $(x_j, y)$, there must be some point $(x_k, y_k)$ between the two points such that $P'(x_k) = 0$. If this were not the case, the function would be either strictly increasing or strictly decreasing on the interval between the two points. Because the two points have the same y-value, any increase must be countered by a corresponding decrease, which contradicts that assumption. Because $P'(x_k)=0, (x_k, P(x_k))\in S$. But there are no such points in the set by the condition on the set $S$. Therefore there is no polynomial fitting the conditions for the set.

Suppose we pick some values for $n$ and integrate $P'(X)$. We can perform linear regression with the integral at each x-value in $S$ being the x-values and the actual y-values of the points being the y-values. This gives us the only $A, C$ that could possibly satisfy the first condition, and they are unique given at least two points.

Given only one point, there is an extra degree of freedom, giving an infinite number of solutions for each possible n-value, each of which corresponds to a degree of polynomial. If we have two points, we have one solution for each combination of 2 n-values. Using binomial coefficients, we can find exactly how many polynomials of each degree satisfy the equation, as well as find each polynomial by simply inputting arbitrary values for $n$, assuming each x- and y- value is unique between the two points.

Once we get to three points, it is possible to construct any number of sets for any polynomial, as long as each set is a superset of the extrema of the polynomial (including complex values). There may not be a solution for all sets of three or more points, however. Is it possible to construct a set of three or more points such that two polynomials satisfy the conditions? Three? An arbitrary number of polynomials? An infinite number of polynomials? Or can there only be one polynomial for sets with cardinality greater than two?

This is motivated by an attempt to improve polynomial interpolation by restricting polynomials between the data points, similarly to splines but with one polynomial instead of many. I doubt that there's a deterministic way to find such polynomials, so I'm just trying to figure out if a solution would be unique for more than two points.

• Using the words "set" and "cardinality" doesn't make it a question in set theory. – Alexander Shamov Jan 18 '14 at 2:25

In the beginning you say that your $x_k$ and $y_k$ are complex. Then most of the time you assume them to be real, call them "extrema", etc.
Anyway, if I understand correctly, you are asking for a polynomial whose ALL critical points and critical values are prescribed. (If $P'(x)=0$ then $x$ is called a critical point and $P(x)$ is called critical value).
This problem in general has no solutions. Indeed, a polynomial of degree $n$ depends on $n+1$ parameters, and has $n-1$ critical points and $n-1$ critical values, together you want to satisfy $2n-2$ conditions, which is impossible when $n>1$.
If all critical points and critical values are real, there is the exact condition that critical values must satisfy. Assuming for simlicity that critical points are simple, denote them by $x_1\leq x_2\leq\ldots\leq x_{n-1}$. Then the necessary and sufficient condition the critical values $y_k=P(x_k)$ must satisfy is $(y_k-y_{k-1})(y_{k+1}-y_k)<0$. So some critical values can be equal, contrary to what you say. One can obtain similar necessary and sufficient condition with multiple critical points.