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$.

  • $\begingroup$ 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$. $\endgroup$ – Michael Dyrud Aug 20 '15 at 17:53
  • $\begingroup$ 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. $\endgroup$ – Arnaud D. Aug 20 '15 at 18:50
  • $\begingroup$ @Arnaud Ok, in my protocol, that condition was required I wanted to mention. $\endgroup$ – user13676 Aug 20 '15 at 19:03
  • $\begingroup$ the crucial question is, which degree shall $P$ and $P'$ have at most? $\endgroup$ – user251257 Aug 21 '15 at 13:59
  • $\begingroup$ @user251257 Their degree shall not be higher than $n-1$. $\endgroup$ – 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.

  • $\begingroup$ @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. $\endgroup$ – user13676 Aug 21 '15 at 10:29
  • $\begingroup$ Can I have your answer for this question please: math.stackexchange.com/questions/1405820/… $\endgroup$ – 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).

  • $\begingroup$ Why do you say the degree of $P'$ will be one less, aren't they interpolating with the same number of points? $\endgroup$ – Michael Dyrud Aug 20 '15 at 17:50
  • $\begingroup$ $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. $\endgroup$ – Michael Dyrud Aug 20 '15 at 17:58
  • $\begingroup$ So really, the answer is "it depends". It is certainly possible, but it is not always the case. $\endgroup$ – Michael Dyrud Aug 20 '15 at 17:59
  • 1
    $\begingroup$ 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$ $\endgroup$ – user13676 Aug 20 '15 at 18:02
  • 1
    $\begingroup$ 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). $\endgroup$ – Morgan Rodgers Aug 21 '15 at 11:36

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.