Polynomial Interpolation When $y_i$'s are Permuted

Recall, if we have a $d$-degree polynomial $f$, evaluate it at $\textbf{x}=(x_1,\ldots,x_n)$ we would get $\textbf{y}=(y_1,\ldots,y_n)$, where $f(x_i)=y_i$ and $d+1 \leq n$. The reverse is also true, so given $n$ pairs of $(x_i,y_i)$ we can interpolated polynomial $f$ whose degree is $d$.

Question: Is there any $n$ pairs $(x_i, y_j)$, where $i \neq j, y_i \in \textbf{y}, x_i \in \textbf{x},$ whose interpolation results in a polynomial, $f'$, where $\deg(f')\leq d$ ?

Please see below for more details:

Polynomial Interpolation and Data Integrity

• It is true that if $n=d+1$ then for any $n$ pairs $(x_i,y_i)$ one can find a polynomial of degree $d$ whose graph includes all of those points. But it is not true if $n>d+1$. In that case, the points $(x_i,y_i)$ can be so chose that one would need a polynomial of degree $>d$ to fit all of them perfectly. ${}\qquad{}$ – Michael Hardy Aug 2 '15 at 14:33
• You are asking whether, if we switch some of the values without switching the respective places, we could obtain a lower-degree polynomial? Yeah, that can happen. If you sample a linear function at many different places, and then switch the values around, you get a (generally) higher-degree interpolating polynomial. Then, if you switch the values back, you get back your linear function. – darij grinberg Aug 2 '15 at 14:34
• @darijgrinberg I could not understand your answer. But in my case $x_i$'s can be fixed and even we can assume that they are ordered. Now the question is Do interpolating $n$ pairs of $(x_i,y_j)$ result a polynomial of degree $\leq d$ ? – user13676 Aug 2 '15 at 14:40
• The answer may depend a little bit on the field the entries come from. Assuming that they are reals (though data integrity application suggests otherwise). If we fix $(x_1,x_2,\ldots,x_n)$ and generate real numbers $(y_1,y_2,\ldots,y_n)$ with some common random process (uniform from some interval, i.i.d. gaussian,...) then the probability for the interpolation polynomial to have degree $<n-1$ is zero. Checking out the finitely many ($n!$) permutations is not going to change that, still $P=0$. – Jyrki Lahtonen Aug 2 '15 at 15:00