Polynomial Interpolation And polynomial Roots

Given $\{(x_1,y_1),...,(x_n,y_n)\}$, we can interpolate a polynomial $P$. Assume polynomial $P$ has some roots including an specific root $\beta$.

Consider we change one of $y_i$ to $y'_i$. Given $\{(x_1,y_1),...,(x_i,y'_i),..,(x_n,y_n)\}$ we interpolate a polynomial $P'$.

Question 1: Would it be possible that $P'$ has the root $\beta$, too?

Question 2: Would it be possible that $P'$ has the same degree as $P$ and $P'$ has the root $\beta$, too?

Notation: $y_i$ is defined as $P(x_i)=y_i$

Edit: $x_i \neq0$ , $x_i\neq x_j$, the polynomials, $x_i$'s and $y_i$'s are defined over finite field $\mathbb{F}_p$ for a large prime $p$.

• It's certainly possible that $P$ and $P'$ share a root, with the trivial case being where one of the points that is unchanged, say $(x_1,y_1)$, has $y$-coordinate $0$. – Michael Dyrud Aug 20 '15 at 17:53
• I don't really see why you want to specify $x_i\neq 0$. Up to a translation you can always assume one of your $x_i$ is zero, and this won't change anything to the answers to both your questions. – Arnaud D. Aug 20 '15 at 18:50
• @Arnaud Ok, in my protocol, that condition was required I wanted to mention. – user13676 Aug 20 '15 at 19:03
• the crucial question is, which degree shall $P$ and $P'$ have at most? – user251257 Aug 21 '15 at 13:59
• @user251257 Their degree shall not be higher than $n-1$. – user13676 Aug 21 '15 at 14:11

Actually if $\beta$ is not one of your $x_j$'s then it's impossible. Indeed, the two polynomials $P$ and $P'$ have degree $n-1$ (at most) and take the same value on all $x_j$ for $j\neq i$ (namely, $y_j$), so if they both vanished at $\beta$ they would have the same value at $n$ points, and thus they would be equal, which is not the case since they have different values at $x_i$.

Of course, as pointed out in the comments, if $\beta=x_j\neq x_i$ then $P$ and $P'$ trivially a common root.

• @Arnnaud Many thanks for the answer. Since my background is mainly computer science not math, I may ask some questions that look trivial to you mathematicians. First, I need to know why "it is impossible... if $x_i\neq\beta$ ". It would be great if you refer me to a theorem or a proof. Second, what if more than one values of $y_i$ can be changed. What would be an answer to questions 1 and 2, in this case? Thank you. – user13676 Aug 21 '15 at 10:29
• Can I have your answer for this question please: math.stackexchange.com/questions/1405820/… – user13676 Aug 22 '15 at 13:22

$P^{\prime}$ may have the same degree, though not necessarily. Consider the polynomial $x^{2}(x-1)$ through points $(0,0)$, $(1,0)$ and $(-1, -2)$. Replace the $-2$ with a $+2$, and now you have the polynomial $-x^{2}(x-1)$. Both share two roots and have the same degree. As mentioned in Michael's comment, you could possibly have the degree change (such as going between $\{(-1,1), (0,0), (1,1)\}$ where you have a quadratic, and $\{(-1,-1),(0,0), (1,1)\}$ where you have a linear equation).

• Why do you say the degree of $P'$ will be one less, aren't they interpolating with the same number of points? – Michael Dyrud Aug 20 '15 at 17:50
• $P'$ doesn't necessarily need the same degree though. It's possible that shifting a point will allow us to approximate with a function of lower degree. For example, if we have the set $\{(-1,-1),(0,0),(1,1)\}$ the interpolating polynomial will be $y=x^3$. If we change it to $\{(-1,1),(0,0),(1,1)\}$ our polynomial is now $y=x^2$, which is lower degree. – Michael Dyrud Aug 20 '15 at 17:58
• So really, the answer is "it depends". It is certainly possible, but it is not always the case. – Michael Dyrud Aug 20 '15 at 17:59
• Thank you for the answers. What if we define the polynomial over finite field $\mathbb{F}_p$ for a large prime $p$. So all the $x_i$'s and $y_i$'s are the fields elements. Would it still be possible? Also what if $x_i\neq 0$ – user13676 Aug 20 '15 at 18:02
• Sure, but it really goes to Arnaud's answer. You automatically will get two polynomials of degree at most $n-1$, sharing $n-1$ interpolated points. So if they also share the point $(\beta,0)$ as an extra point, they share $n$ points. The $n$ $x$-values are roots of $P(x) - P^{\prime}(x)$ . But $P(x) - P^{\prime}(x) = 0$ or has degree at most $n-1$ (in which case it can't have $n$ roots). – Morgan Rodgers Aug 21 '15 at 11:36