# 3.3: Polynomial Interpolation

You are probably familiar with the fact that two points determine a line (in Euclidean geometry). It is also true that 3 points determine a parabola, and so on. The next secretsharing scheme we discuss is based on the following principle:

$$d + 1$$ points determine a unique degree-$$d$$ polynomial, and this is true even working modulo a prime.

A note on terminology: If ? is a polynomial that can be written as $$?(x) = \Sigma ^{d}_{i=0}\mathscr{f}_ix^i$$, then we say that ? is a degree–$$d$$ polynomial. It would be more technically correct to say that the degree of ? is at most d since we allow the leading coefficient $$?_d$$ to be zero. For convenience, we’ll stick to saying “degree-$$d$$” to mean “degree at most $$d$$.”

### Theorem $$\PageIndex{1}$$: Poly Interpolation

Let $$p$$ be a prime, and let $$\{(x_1,y_1),. . . , (x_{d+1},y_{d+1})\} \subseteq (\mathbb{Z}_p)^2$$ be a set of points whose xi values are all distinct. Then there is a unique degree-d polynomial ? with coefficients in $$\mathbb{Z}_p$$ that satisfies $$y_i \equiv_p ?(x_i)$$ for all i.

#### Proof

Let $$?(x) = \Sigma ^{d}_{i=0}?_ix^i$$ be a degree-$$d$$ polynomial. Consider the problem of evaluating ? on a set of points $$x_1,. . . ,x_{d+1}$$. We can express the values of ? as a linear function in the following way:

$\left[ \begin{array} { c } { f \left( x _ { 1 } \right) } \\ { f \left( x _ { 2 } \right) } \\ { \vdots } \\ { f \left( x _ { d + 1 } \right) } \end{array} \right] = \left[ \begin{array} { c c c c c c } { 1 } & { x _ { 1 } } & { x _ { 1 } ^ { 2 } } & { x _ { 1 } ^ { 3 } } & { \dots } & { x _ { 1 } ^ { d } } \\ { 1 } & { x _ { 2 } } & { x _ { 2 } ^ { 2 } } & { x _ { 2 } ^ { 3 } } & { \dots } & { x _ { 2 } ^ { d } } \\ { } & { \vdots } & { } & { \ddots } & { \vdots } \\ { 1 } & { x _ { d + 1 } } & { x _ { d + 1 } ^ { 2 } } & { x _ { d + 1 } ^ { 3 } } & { \cdots } & { x _ { d + 1 } ^ { d } } \end{array} \right] \left[ \begin{array} { c } { f _ { 0 } } \\ { f _ { 1 } } \\ { f _ { 2 } } \\ { f _ { 3 } } \\ { \vdots } \\ { f _ { d } } \end{array} \right]\nonumber$

What’s notable about this expression is that $$V$$ is a special kind of matrix called a Vandermonde matrix. A Vandermonde matrix is determined by the values $$x_1,. . . ,x_{d+1}$$. Then the $$(i,j)$$ entry of the matrix is $$x^{j−1}_i$$. One important property of Vandermonde matrices (that we won’t prove here) is that the determinant of a square Vandermonde matrix is:

$\operatorname { det } ( V ) = \prod _ { i < j } \left( x _ { j } - x _ { i } \right)\nonumber$

The Vandermonde matrix $$V$$ in our expression is square, having dimensions $$(d + 1) \times (d + 1)$$. Also, since all of the $$x_i$$ values are distinct, the expression for the determinant must be nonzero. That means $$V$$ is invertible!

So, knowing $$\{(x_1,y_1),. . . , (x_{d+1},y_{d+1})\}$$, we can solve for the coefficients of ? in the following equation:

$\left[ \begin{array} { c } { y _ { 1 } } \\ { y _ { 2 } } \\ { \vdots } \\ { y _ { d + 1 } } \end{array} \right] = \left[ \begin{array} { c c c c c } { 1 } & { x _ { 1 } } & { x _ { 1 } ^ { 2 } } & { x _ { 1 } ^ { 3 } } & { \dots } & { x _ { 1 } ^ { d } } \\ { 1 } & { x _ { 2 } } & { x _ { 2 } ^ { 2 } } & { x _ { 2 } ^ { 3 } } & { \dots } & { x _ { 2 } ^ { d } } \\ { } & { } & { \vdots } & { } & { \ddots } & { \vdots } \\ { 1 } & { x _ { d + 1 } } & { x _ { d + 1 } ^ { 2 } } & { x _ { d + 1 } ^ { 3 } } & { \cdots } & { x _ { d + 1 } ^ { d } } \end{array} \right] \left[ \begin{array} { c } { f _ { 0 } } \\ { f _ { 1 } } \\ { f _ { 2 } } \\ { f _ { 3 } } \\ { \vdots } \\ { f _ { d } } \end{array} \right]\nonumber$

$\Longrightarrow \left[ \begin{array} { c } { f _ { 0 } } \\ { f _ { 1 } } \\ { f _ { 2 } } \\ { f _ { 3 } } \\ { \vdots } \\ { f _ { d } } \end{array} \right] = \left[ \begin{array} { c c c c c } { 1 } & { x _ { 1 } } & { x _ { 1 } ^ { 2 } } & { x _ { 1 } ^ { 3 } } & { \dots } & { x _ { 1 } ^ { d } } \\ { 1 } & { x _ { 2 } } & { x _ { 2 } ^ { 2 } } & { x _ { 2 } ^ { 3 } } & { \dots } & { x _ { 2 } ^ { d } } \\ { } & { } & { \vdots } & { } & { \ddots } & { \vdots } \\ { 1 } & { x _ { d + 1 } } & { x _ { d + 1 } ^ { 2 } } & { x _ { d + 1 } ^ { 3 } } & { \cdots } & { x _ { d + 1 } ^ { d } } \end{array} \right] ^ { - 1 } \left[ \begin{array} { c } { y _ { 1 } } \\ { y _ { 2 } } \\ { \vdots } \\ { y _ { d + 1 } } \end{array} \right] \nonumber$

Note the matrix inverse in second equation. There is a unique solution for the vector $$f = (f_0,. . . , f_d)$$, hence a unique degree-$$d$$ polynomial $$f$$ fitting the points.

The proof was written as if the linear algebra was over the real numbers (or complex numbers if you prefer). Indeed, the statement is true for real and complex numbers. However, all of the logic still holds when the linear equations are over $$\mathbb{Z}_p$$, when p is a prime. Formally, this is because $$\mathbb{Z}_p$$ is a field (working modulo $$p$$, you have addition, multiplication, and inverses of nonzero elements). Most of what you know about linear algebra “just works” when matrix operations are in a field. Replacing the “=” sign (integer equality) with “$$\equiv\space p$$” (congruence modulo p), and all the steps of the proof still hold.