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 \text { points determine a unique degree- } d \text { polynomial. }\] A note on terminology: If \(f\) is a polynomial that can be written as \(f(x)=\sum_{i=0}^{d} f_{i} x^{i}\), then we say that \(f\) is a degree-\(d\) polynomial. It would be more technically correct to say that the degree of \(f\) is at most \(d\) since we allow the leading coefficient \(f_{d}\) to be zero. For convenience, we’ll stick to saying "degree-\(d\) " to mean "degree at most \(d\) "

Polynomials Over the Reals

Theorem \(3.8\)

Let \(\left\{\left(x_{1}, y_{1}\right), \ldots,\left(x_{d+1}, y_{d+1}\right)\right\} \subseteq \mathbb{R}^{2}\) be a set of points whose \(x_{i}\) values are all distinct. Then (Poly Interpolation) there is a unique degree-d polynomial \(f\) with real coefficients that satisfies \(y_{i}=f\left(x_{i}\right)\) for all \(i .\)

Proof

To start, consider the following polynomial: \[\ell_{1}(\boldsymbol{x})=\frac{\left(\boldsymbol{x}-x_{2}\right)\left(\boldsymbol{x}-x_{3}\right) \cdots\left(\boldsymbol{x}-x_{d+1}\right)}{\left(x_{1}-x_{2}\right)\left(x_{1}-x_{3}\right) \cdots\left(x_{1}-x_{d+1}\right)}\] The notation is potentially confusing. \(\ell_{1}\) is a polynomial with formal variable \(\boldsymbol{x}\) (written in bold). The non-bold \(x_{i}\) values are just plain numbers (scalars), given in the theorem statement. Therefore the numerator in \(\ell_{1}\) is a degree- \(d\) polynomial in \(\boldsymbol{x}\). The denominator is just a scalar, and since all of the \(x_{i}\) ’s are distinct, we are not dividing by zero. Overall, \(\ell_{1}\) is a degree- \(d\) polynomial.

What happens when we evaluate \(\ell_{1}\) at one of the special \(x_{i}\) values?

• Evaluating \(\ell_{1}\left(x_{1}\right)\) makes the numerator and denominator the same, so \(\ell_{1}\left(x_{1}\right)=1\).
• Evaluating \(\ell_{1}\left(x_{i}\right)\) for \(i \neq 1\) leads to a term \(\left(x_{i}-x_{i}\right)\) in the numerator, so \(\ell_{1}\left(x_{i}\right)=0\).

Of course, \(\ell_{1}\) can be evaluated at any point (not just the special points \(x_{1}, \ldots, x_{d+1}\) ), but we don’t care about what happens in those cases.

We can similarly define other polynomials \(\ell_{j}\) :

\[\ell_{j}(\boldsymbol{x})=\frac{\left(\boldsymbol{x}-x_{1}\right) \cdots\left(\boldsymbol{x}-x_{j-1}\right)\left(\boldsymbol{x}-x_{j+1}\right) \cdots\left(\boldsymbol{x}-x_{d+1}\right)}{\left(x_{j}-x_{1}\right) \cdots\left(x_{j}-x_{j-1}\right)\left(x_{j}-x_{j+1}\right) \cdots\left(x_{j}-x_{d+1}\right)}\]

The pattern is that the numerator is "missing" the term \(\left(\boldsymbol{x}-x_{j}\right)\) and the denominator is missing the term \(\left(x_{j}-x_{j}\right)\), because we don’t want a zero in the denominator. Polynomials of this kind are called LaGrange polynomials. They are each degree-\(d\) polynomials, and they satisfy the property: \[\ell_{j}\left(x_{i}\right)= \begin{cases}1 & \text { if } i=j \\ 0 & \text { if } i \neq j\end{cases}\]

Now consider the following polynomial:

\[f(\boldsymbol{x})=y_{1} \ell_{1}(\boldsymbol{x})+y_{2} \ell_{2}(\boldsymbol{x})+\cdots+y_{d+1} \ell_{d+1}(\boldsymbol{x})\]

Note that \(f\) is a degree- \(d\) polynomial since it is the sum of degree-d polynomials (again, the \(y_{i}\) values are just scalars)

What happens when we evaluate \(f\) on one of the special \(x_{i}\) values? Since \(\ell_{i}\left(x_{i}\right)=1\) and \(\ell_{j}\left(x_{i}\right)=0\) for \(j \neq i\), we get:

\[\begin{aligned} f\left(x_{i}\right) &=y_{1} \ell_{1}\left(x_{i}\right)+\cdots+y_{i} \ell_{i}\left(x_{i}\right)+\cdots+y_{d+1} \ell_{d+1}\left(x_{i}\right) \\ &=y_{1} \cdot 0+\cdots+y_{i} \cdot 1+\cdots+y_{d+1} \cdot 0 \\ &=y_{i} \end{aligned}\]

So \(f\left(x_{i}\right)=y_{i}\) for every \(x_{i}\), which is what we wanted. This shows that there is some degree- \(d\) polynomial with this property.

Now let’s argue that this \(f\) is unique. Suppose there are two degree- \(d\) polynomials \(f\) and \(f^{\prime}\) such that \(f\left(x_{i}\right)=f^{\prime}\left(x_{i}\right)=y_{i}\) for \(i \in\{1, \ldots, d+1\}\). Then the polynomial \(g(\boldsymbol{x})=f(\boldsymbol{x})-f^{\prime}(\boldsymbol{x})\) also is degree- \(d\), and it satisfies \(g\left(x_{i}\right)=0\) for all \(i\). In other words, each \(x_{i}\) is a root of \(g\), so \(g\) has at least \(d+1\) roots. But the only degree-d polynomial with \(d+1\) roots is the identically-zero polynomial \(g(\boldsymbol{x})=0\). If \(g(\boldsymbol{x})=0\) then \(f=f^{\prime}\). In other words, any degree- \(d\) polynomial \(f^{\prime}\) that satisfies \(f^{\prime}\left(x_{i}\right)=y_{i}\) must be equal to \(f\). So \(f\) is the unique polynomial with this property.

Example \(\PageIndex{1}\)

Let’s figure out the degree-3 polynomial that passes through the points \((3,1),(4,1),(5,9),(2,6)\)

\(i\)	1	2	3	4
\(x_{i}\)	3	4	5	2
\(y_{i}\)	1	1	9	6

First, let’s construct the appropriate LaGrange polynomials:

\[\begin{aligned} &\ell_{1}(\boldsymbol{x})=\frac{\left(\boldsymbol{x}-x_{2}\right)\left(\boldsymbol{x}-x_{3}\right)\left(\boldsymbol{x}-x_{4}\right)}{\left(x_{1}-x_{2}\right)\left(x_{1}-x_{3}\right)\left(x_{1}-x_{4}\right)}=\frac{(\boldsymbol{x}-4)(\boldsymbol{x}-5)(\boldsymbol{x}-2)}{(3-4)(3-5)(3-2)}=\frac{\boldsymbol{x}^{3}-11 \boldsymbol{x}^{2}+38 \boldsymbol{x}-40}{2} \\ &\ell_{2}(\boldsymbol{x})=\frac{\left(\boldsymbol{x}-x_{1}\right)\left(\boldsymbol{x}-x_{3}\right)\left(\boldsymbol{x}-x_{4}\right)}{\left(x_{2}-x_{1}\right)\left(x_{2}-x_{3}\right)\left(x_{2}-x_{4}\right)}=\frac{(\boldsymbol{x}-3)(\boldsymbol{x}-5)(\boldsymbol{x}-2)}{(4-3)(4-5)(4-2)}=\frac{\boldsymbol{x}^{3}-10 \boldsymbol{x}^{2}+31 \boldsymbol{x}-30}{-2} \\ &\ell_{3}(\boldsymbol{x})=\frac{\left(\boldsymbol{x}-x_{1}\right)\left(\boldsymbol{x}-x_{2}\right)\left(\boldsymbol{x}-x_{4}\right)}{\left(x_{3}-x_{1}\right)\left(x_{3}-x_{2}\right)\left(x_{3}-x_{4}\right)}=\frac{(\boldsymbol{x}-3)(\boldsymbol{x}-4)(\boldsymbol{x}-2)}{(5-3)(5-4)(5-2)}=\frac{\boldsymbol{x}^{3}-9 \boldsymbol{x}^{2}+26 \boldsymbol{x}-24}{6} \\ &\ell_{4}(\boldsymbol{x})=\frac{\left(\boldsymbol{x}-x_{1}\right)\left(\boldsymbol{x}-x_{2}\right)\left(\boldsymbol{x}-x_{3}\right)}{\left(x_{4}-x_{1}\right)\left(x_{4}-x_{2}\right)\left(x_{4}-x_{3}\right)}=\frac{(\boldsymbol{x}-3)(\boldsymbol{x}-4)(\boldsymbol{x}-5)}{(2-3)(2-4)(2-5)}=\frac{\boldsymbol{x}^{3}-12 \boldsymbol{x}^{2}+47 \boldsymbol{x}-60}{-6} \end{aligned}\] As a sanity check, notice how: \[\begin{aligned} &\ell_{1}\left(x_{1}\right)=\ell_{1}(3)=\frac{3^{3}-11 \cdot 3^{2}+38 \cdot 3-40}{2}=\frac{2}{2}=1 \\ &\ell_{1}\left(x_{2}\right)=\ell_{1}(4)=\frac{4^{3}-11 \cdot 4^{2}+38 \cdot 4-40}{2}=\frac{0}{2}=0 \end{aligned}\]

It will make the next step easier if we rewrite all LaGrange polynomials to have the same denominator 6: \[\begin{array}{ll} \ell_{1}(\boldsymbol{x})=\frac{3 \boldsymbol{x}^{3}-33 \boldsymbol{x}^{2}+114 \boldsymbol{x}-120}{6} & \ell_{3}(\boldsymbol{x})=\frac{\boldsymbol{x}^{3}-9 \boldsymbol{x}^{2}+26 \boldsymbol{x}-24}{6} \\ \ell_{2}(\boldsymbol{x})=\frac{-3 \boldsymbol{x}^{3}+30 \boldsymbol{x}^{2}-93 \boldsymbol{x}+90}{6} & \ell_{4}(\boldsymbol{x})=\frac{-\boldsymbol{x}^{3}+12 \boldsymbol{x}^{2}-47 \boldsymbol{x}+60}{6} \end{array}\]

Our desired polynomial is

\[\begin{aligned} & f(\boldsymbol{x})=y_{1} \cdot \ell_{1}(\boldsymbol{x})+y_{2} \cdot \ell_{2}(\boldsymbol{x})+y_{3} \cdot \ell_{3}(\boldsymbol{x})+y_{4} \cdot \ell_{4}(\boldsymbol{x}) \\ & =1 \cdot \ell_{1}(\boldsymbol{x})+1 \cdot \ell_{2}(\boldsymbol{x})+9 \cdot \ell_{3}(\boldsymbol{x})+6 \cdot \ell_{4}(\boldsymbol{x}) \end{aligned}\]

\[\begin{aligned} & =\frac{1}{6}\left(3 x^{3}-12 x^{2}-27 x+114\right) \\ & =\frac{x^{3}}{2}-2 x^{2}-\frac{9 x}{2}+19 \end{aligned}\]

And indeed, \(f\) gives the correct values:

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

\[\begin{aligned} &f\left(x_{1}\right)=f(3)=\frac{3^{3}}{2}-2 \cdot 3^{2}-\frac{9 \cdot 3}{2}+19=1=y_{1} \\ &f\left(x_{2}\right)=f(4)=\frac{4^{3}}{2}-2 \cdot 4^{2}-\frac{9 \cdot 4}{2}+19=1=y_{2} \\ &f\left(x_{3}\right)=f(5)=\frac{5^{3}}{2}-2 \cdot 5^{2}-\frac{9 \cdot 5}{2}+19=9=y_{3} \\ &f\left(x_{4}\right)=f(2)=\frac{2^{3}}{2}-2 \cdot 2^{2}-\frac{9 \cdot 2}{2}+19=6=y_{4} \end{aligned}\]

Polynomials \(\bmod p\)

We will see a secret-sharing scheme based on polynomials, whose Share algorithm must choose a polynomial with uniformly random coefficients. Since we cannot have a uniform distribution over the real numbers, we must instead consider polynomials with coefficients in \(\mathbb{Z}_{p}\)

It is still true that \(d+1\) points determine a unique degree-\(d\) polynomial when working modulo \(p\), if \(p\) is a prime!

Theorem \(3.9\)

Let \(p\) be a prime, and let \(\left\{\left(x_{1}, y_{1}\right), \ldots,\left(x_{d+1}, y_{d+1}\right)\right\} \subseteq\left(\mathbb{Z}_{p}\right)^{2}\) be a set of points whose \(x_{i}\) val\((\) Interp \(\bmod p) \quad\) ues are all distinct. Then there is a unique degree-d polynomial \(f\) with coefficients from \(\mathbb{Z}_{p}\) that satisfies \(y_{i} \equiv_{p} f\left(x_{i}\right)\) for all \(i\).

The proof is the same as the one for Theorem 3.8, if you interpret all arithmetic modulo p. Addition, subtraction, and multiplication mod \(p\) are straight forward; the only nontrivial question is how to interpret "division mod \(p\) " which is necessary in the definition of the \(\ell_{j}\) polynomials. For now, just accept that you can always "divide" mod \(p\) (except by zero) when \(p\) is a prime. If you are interested in how division mod \(p\) works, look ahead to Chapter \(13 .\)

We can also generalize the observation that \(d+1\) points uniquely determine a degree- \(d\) polynomial. It turns out that:

For any \(k\) points, there are exactly \(p^{d+1-k}\) polynomials of degree- \(d\) that hit those points, \(\bmod p\).

Note how when \(k=d+1\), the statement says that there is just a single polynomial hitting the points.

Corollary 3.10

Let \(\mathcal{P}=\left\{\left(x_{1}, y_{1}\right), \ldots,\left(x_{k}, y_{k}\right)\right\} \subseteq\left(\mathbb{Z}_{p}\right)^{2}\) be a set of points whose \(x_{i}\) values are distinct. Letd (# of polys) satisfy \(k \leqslant d+1\) and \(p>d\). Then the number of degree-d polynomials \(f\) with coefficients in \(\mathbb{Z}_{p}\) that satisfy the condition \(y_{i} \equiv_{p} f\left(x_{i}\right)\) for all \(i\) is exactly \(p^{d+1-k}\).

Proof The proof is by induction on the value \(d+1-k\). The base case is when \(d+1-k=0\). Then we have \(k=d+1\) distinct points, and Theorem \(3.9\) says that there is a unique polynomial satisfying the condition. Since \(p^{d+1-k}=p^{0}=1\), the base case is true.

For the inductive case, we have \(k \leqslant d\) points in \(\mathcal{P}\). Let \(x^{*} \in \mathbb{Z}_{p}\) be a value that does not appear as one of the \(x_{i}\) ’s. Every polynomial must give some value when evaluated at \(x^{*} . \mathrm{So}\) \[\begin{aligned} &\text { [# of degree- } d \text { polynomials passing through points in } \mathcal{P}] \\ &\qquad=\sum_{y^{*} \in \mathbb{Z}_{p}}\left[\# \text { of degree- } d \text { polynomials passing through points in } \mathcal{P} \cup\left\{\left(x^{*}, y^{*}\right)\right\}\right] \\ &\stackrel{(\star)}{=} \sum_{y^{*} \in \mathbb{Z}_{p}} p^{d+1-(k+1)} \\ &\quad=p \cdot\left(p^{d+1-k-1}\right)=p^{d+1-k} \end{aligned}\] The equality marked \((\star)\) follows from the inductive hypothesis, since each of the terms involves a polynomial passing through a specified set of \(k+1\) points with distinct \(x\) coordinates.

Example \(\PageIndex{1}\)

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

What does a "polynomial mod p" look like? Consider an example degree-\(2\) polynomial: \(f\left ( \boldsymbol{x} \right)=\boldsymbol{x}^{2}+4\boldsymbol{x}+7\) When we plot this polynomial over the real numbers (the picture on the left), we get a familiar parabola. Let’s see what this polynomial "looks like" modulo 11 (i.e., in \(\mathbb{Z}_{11}\) ). Working mod 11 means to "wrap around" every time the polynomial crosses over a multiple of 11 along the \(y\)-axis. This results in the blue plot below: Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source) This is a picture of a mod-11 parabola. In fact, since we care only about \(\mathbb{Z}_{11}\) inputs to \(f\), you could rightfully say that just the 11 highlighted points alone (not the blue curve) are a picture of a mod-11 parabola.