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$.
Answer
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.
No comments:
Post a Comment