Chapter status:   👷   in progress   👷

TODO:

Polynomials

In this chapter, we cover general results about polynomials with coefficients in a ring.

We recall some abbreviations from the chapter about rings:

• UCR stands for unitary commutative ring,
• PID stands for principal ideal domain,
• UFD stands for unique factorization domain.

Contents

• Generalities
• Divisibility in Polynomial Rings
• Ring vs. Polynomial Ring: Summary
• Polynomial Evaluation and Roots
• Lagrange Interpolation
  • Generalized Polynomial Remainder Theorem
  • Computational Aspects
    • The Barycentric Formula
    • The Special Case of Roots of Unity
  • Applications

Generalities

Let $\mathbb{A}$ be a ring. A (univariate) polynomial with coefficients in $\mathbb{A}$ is an infinite sequence $(a_i{)}_{i\in \mathbb{N}}$ such that $a_i=0$ for all but a finite number of indices $i.$ Polynomials are traditionally denoted $$p(X)=a_0+a_{1}X+a_2{X}^2+\cdots =\sum _{i=0}^{\infty }{a}_i{X}^i$$ where $X$ is a symbol called indeterminate.

The set of all univariate polynomials over $\mathbb{A}$ is denoted $\mathbb{A}[X]:$ $$\mathbb{A}[X]:=\left\{\sum _{i=0}^{\infty }{a}_i{X}^i:a_i\in \mathbb{A},\exists N\in \mathbb{N},\forall i\ge N,a_i=0\right\}.$$

Polynomials can be added: $$\sum _{i=0}^{\infty }{a}_i{X}^i+\sum _{i=0}^{\infty }{b}_i{X}^i=\sum _{i=0}^{\infty }(a_i+b_i)X^i.$$

Polynomials can also be multiplied: $$\sum _{i=0}^{\infty }{a}_i{X}^i\cdot \sum _{j=0}^{\infty }{b}_j{X}^j=\sum _{k=0}^{\infty }{c}_k{X}^k\text{with}{c}_k=\sum _{i+j=k}{a}_i{b}_j.$$

Proposition 7.1. Let $\mathbb{A}$ be a ring. Then $\mathbb{A}[X]$ equipped with operations $+$ and $\cdot$ as defined above is a ring. If $\mathbb{A}$ is commutative, then so is $\mathbb{A}[X]$ and if $\mathbb{A}$ has a unity 1, then the constant polynomial $p(X)=1$ is the unity of $\mathbb{A}[X].$

The set $\mathbb{A}[X]$ is called the polynomial ring in $X$ over $\mathbb{A}.$ If we embed $\mathbb{A}$ into $\mathbb{A}[X]$ by identifying $a\in \mathbb{A}$ with the constant polynomial $p(X)=a,$ then $\mathbb{A}$ is a subring of $\mathbb{A}[X].$

The degree of a polynomial $p(X)$ is the largest power of $X$ occurring in $p(X)$ with a non-zero coefficient, with the convention that polynomial $0$ has degree $-\infty .$ Hence, $p(X)={\sum }_{i=0}^n{a}_i{X}^i$ has degree $n$ provided $a_n\ne 0.$ We let $\mathrm{deg}(p)$ denote the degree of a polynomial $p$ and ${\mathbb{A}}^{\le n}[X]$ denote the set of polynomials over $\mathbb{A}$ of degree at most $n.$ The leading term of $p(X)$ is its highest degree term $a_n{X}^n$ and the leading coefficient is $a_n.$ If the leading coefficient is 1 then the polynomial is said to be monic.

We will often drop the indeterminate from the notation, simply writing "polynomial $p$", keeping it mostly when writing the polynomial coefficients explicitly as in $p(X)={\sum }_{i=0}^n{a}_i{X}^i.$

Proposition 7.2. Let $\mathbb{A}$ be a ring and let $p$ and $q$ be two polynomials in $\mathbb{A}[X].$ Then $$\begin{array}{rl}& \mathrm{deg}(p+q)\le \max \left\{\mathrm{deg}(p),\mathrm{deg}(q)\right\}\\ & \mathrm{deg}(pq)\le \mathrm{deg}(p)+\mathrm{deg}(q).\end{array}$$ Moreover, if the leading coefficient of either $p$ or $q$ is not a zero divisor, then $$\mathrm{deg}(pq)=\mathrm{deg}(p)+\mathrm{deg}(q).$$

Proof

The first two inequalities follow straightforwardly from the definition of addition and multiplication in $\mathbb{A}[X].$ For the last part of the proposition, assume that $p$ has leading term $a{X}^n$ and $q$ has leading term $b{X}^m$ with $a\ne 0$ and $b\ne 0.$ Then $pq$ has leading term $ab{X}^{n+m}$ with $ab\ne 0$ as otherwise $a$ and $b$ would be zero divisors. Hence, $\mathrm{deg}(pq)=n+m=\mathrm{deg}(p)+\mathrm{deg}(q).$

On the other hand, when $\mathbb{A}$ has zero divisors, then one might have $\mathrm{deg}(pq)<\mathrm{deg}(p)+\mathrm{deg}(q)$ if the leading terms of $p$ and $q$ are $a{X}^n$ and $b{X}^m$ with $ab=0.$

When the coefficients are in an integral domain, we have additional properties.

Proposition 7.3. Let $\mathbb{D}$ be an integral domain. Then

• $\mathbb{D}[X]$ is an integral domain;
• for any polynomials $p,q\in \mathbb{D}[X],$ $\mathrm{deg}(pq)=\mathrm{deg}(p)+\mathrm{deg}(q);$
• the units of $\mathbb{D}[X]$ are the constant polynomials $p(X)=u$ for $u\in {\mathbb{D}}^{\ast }.$

Proof

Let $p$ and $q$ be two non-zero polynomials in $\mathbb{D}[X].$ If $p$ has leading term $a{X}^n$ and $q$ has leading term $b{X}^m$ with $a\ne 0$ and $b\ne 0,$ then $pq$ has leading term $ab{X}^{n+m}$ with $ab\ne 0$ since $\mathbb{D}$ is an integral domain. Hence, $pq$ is not the zero polynomial. This also shows that $\mathrm{deg}(pq)=\mathrm{deg}(p)+\mathrm{deg}(q).$ Clearly, for any unit $u\in {\mathbb{D}}^{\ast },$ the constant polynomial $p(X)=u$ is a unit with inverse the constant polynomial $u^{-1}.$ Conversely, if polynomials $p$ and $q$ are such that $pq=1,$ then (by the second point) necessarily $\mathrm{deg}(p)=\mathrm{deg}(q)=0,$ i.e., $p$ and $q$ are constant polynomials, and by definition these constants are units of $\mathbb{D}.$

Divisibility in Polynomial Rings

All definitions regarding divisibility that we gave for general rings apply to polynomial rings. We restate these definitions here for convenience.

Let $\mathbb{A}$ be a UCR. Given two polynomials $a$ and $b$ in $\mathbb{A}[X],$ we say that $b$ divides $a,$ or that $b$ is a factor of $a,$ or that $a$ is a multiple of $b,$ denoted $b\mid a,$ if there exists a polynomial $q\in \mathbb{A}[X]$ such that $a=qb.$

Proposition 7.4. Let $\mathbb{A}$ be a UCR and $a\in \mathbb{A}[X]$ be a non-zero polynomial. Then for every $b\in \mathbb{D}[X]$ such that the leading coefficient of $b$ is not a zero divisor, $$b\mid a\Rightarrow \mathrm{deg}(b)\le \mathrm{deg}(a).$$ In particular, this always holds when $\mathbb{A}$ is an integral domain.

Proof

Let $b$ be a polynomial dividing $a.$ By definition, there exists $q\in \mathbb{A}[X]$ such that $a=qb.$ Since the leading coefficient of $b$ is not a zero divisor, by Proposition 7.2, $$\mathrm{deg}(a)=\mathrm{deg}(q)+\mathrm{deg}(b).$$ Note that $q$ cannot be the zero polynomial as this would imply $a=0,$ hence $\mathrm{deg}(q)\ge 0$ and thus $\mathrm{deg}(a)\ge \mathrm{deg}(b).$

It is easy to see that this proposition does not hold when the leading coefficient of $b$ is a zero divisor: for example, over ${\mathbb{Z}}_4,$ $$(2X^2+1)(2X^2+1)=1$$ and hence $2X^2+1\mid 1.$

Two polynomials $a$ and $b$ are said to be associates if $a\mid b$ and $b\mid a.$ By [??], over an integral domain $\mathbb{D},$ $a,b\in \mathbb{D}[X]$ are associates if and only if there exists $u\in {\mathbb{D}}^{\ast }$ such that $a(X)=ub(X).$

In general, $\mathbb{A}[X]$ might not be Euclidean (as we will see shortly, this holds if and only if $\mathbb{A}$ is a field). However, one can perform division with remainder for polynomials as soon as the leading coefficient of the divisor is a unit.

Proposition 7.5. Let $\mathbb{A}$ be a UCR. Then for every polynomials $a,b\in \mathbb{A}[X]$ such that the leading coefficient of $b$ is in ${\mathbb{A}}^{\ast }$ (i.e., a unit), there exists unique polynomials $q$ and $r$ such that $a=bq+r$ and $\mathrm{deg}(r)<\mathrm{deg}(b).$

Proof

Consider the set of all polynomials of the form $a-cb$ for $c\in \mathbb{A}[X]:$ $$S:=\{a-cb\mid c\in \mathbb{A}[X]\}.$$ Let $r$ be a polynomial of minimal degree in $S$ and $q$ be such that $r=a-qb.$ Let us show that $\mathrm{deg}(r)<\mathrm{deg}(b).$ Indeed, assume that this does not hold. Let $u{X}^n$ and $v{X}^m$ be the leading terms of $b$ and $r$ respectively, with $m\ge n$ and $u\in {\mathbb{A}}^{\ast }.$ Consider the polynomial $r^{\prime }$ defined as $$r^{\prime }(X):=r(X)-v{u}^{-1}{X}^{m-n}b(X).$$ Then $r^{\prime }\in S.$ Since the leading terms of $r(X)$ and $v{u}^{-1}{X}^{m-n}b(X)$ are both $v{X}^m,$ they cancel and the leading term of $r^{\prime }$ has degree at most $m-1,$ so that $\mathrm{deg}(r^{\prime })<\mathrm{deg}(r),$ contradicting the assumption that $r$ has minimal degree in $S.$ Hence, $\mathrm{deg}(r)<\mathrm{deg}(b),$ which proves existence of a suitable pair $(q,r).$

Let us show uniqueness. Assume that there exists two pairs of polynomials $(q,r)\ne (q^{\prime },r^{\prime })$ such that $a=qb+r,$ $a=q^{\prime }b+r^{\prime },$ $\mathrm{deg}(r)<\mathrm{deg}(b),$ and $\mathrm{deg}(r^{\prime })<\mathrm{deg}(b).$ Then $$(q-q^{\prime })b=r^{\prime }-r.$$ Assume that $q\ne q^{\prime }.$ Note that the leading coefficient of $b$ is a unit and hence, by [??], is not a zero divisor. Hence, by Proposition 7.2, $$\mathrm{deg}(r^{\prime }-r)=\mathrm{deg}((q-q^{\prime })b)=\mathrm{deg}(q-q^{\prime })+\mathrm{deg}(b)\ge \mathrm{deg}(b),$$ where the last inequality holds because $q-q^{\prime }\ne 0.$ On the other hand, by Proposition 7.2, $$\mathrm{deg}(r-r^{\prime })\le \max \{\mathrm{deg}(r),\mathrm{deg}(r^{\prime })\}<\mathrm{deg}(b).$$ This is a contradiction and hence we must have $q=q^{\prime }$ and hence $r=r^{\prime },$ proving uniqueness.

Ring vs. Polynomial Ring: Summary

Polynomial Evaluation and Roots

Let $\mathbb{A}$ be a commutative ring. Given a polynomial $p(X)={\sum }_i{a}_i{X}^i$ in $\mathbb{A}[X]$ and an element $u\in \mathbb{A},$ the evaluation of $p(X)$ at $u,$ written $p(u),$ is ${\sum }_i{a}_i{u}^i.$ The function from $\mathbb{A}$ to $\mathbb{A}$ mapping $u$ to $p(u)$ is called the polynomial function associated with $p.$

In general, there is not a one-to-one correspondence between polynomials and polynomial functions. For example, over a finite commutative ring $\mathbb{A}=\{x_1,\dots ,x_n\},$ the polynomial $$p(X)=(X-x_1)\cdots (X-x_n)$$ evaluates to 0 at every element $x_i\in \mathbb{A}$ but $p$ is clearly different from the constant polynomial 0. Hence, this gives an example where two different polynomials yield the same polynomial function.

As wee will see below, if $\mathbb{A}$ is an infinite integral domain, though, there is a one-to-one correspondence between polynomials and polynomial functions.

We say that $u$ is a root of $p(X)$ if $p(u)=0.$ The following result gives an important sufficient and necessary condition for a ring element to be a root of a polynomial.

Theorem 7.1 (factor theorem). Let $\mathbb{A}$ be a UCR, $p\in \mathbb{A}[X]$ be a polynomial and $u\in \mathbb{A}$ be a ring element. Then $u$ is a root of $p(X)$ if and only if $X-u$ divides $p(X).$

The factor theorem is actually a special case of the following result.

Theorem 7.2 (polynomial remainder theorem). Let $\mathbb{A}$ be a UCR, $p\in \mathbb{A}[X]$ be a polynomial and $u,v\in \mathbb{A}$ be ring elements. Then $p(u)=v$ if and only if $X-u$ divides $p(X)-v.$

Proof

Assume that $X-u$ divides $p(X)-v.$ Then there exists $q\in \mathbb{A}[X]$ such that $$p(X)-v=q(X)(X-u).$$ Evaluating the two sides of this equality at $u$ yields $p(u)-v=0,$ i.e., $p(u)=v.$

Conversely, assume that $p(u)=v.$ Since the leading coefficient of $X-u$ is a unit, by Proposition 7.5, there exists polynomials $q$ and $r$ such that $$p(X)=(X-u)q(X)+r(X)$$ where $$\mathrm{deg}(r)<\mathrm{deg}(X-u)=1.$$ Hence, the polynomial $r$ must be a constant. Evaluating the polynomial equality at $u,$ we obtain that $r=p(u).$ Hence, $p(X)-v=(X-u)q(X),$ which exactly means that $X-u$ divides $p(X)-v.$

Note that the statement "$X-u$ divides $p(X)-v$" is equivalent to the statement "$v$ is the remainder of the division of $p(X)$ by $X-u$", hence the name of the theorem.

The factor theorem (which holds over any UCR) generalizes to multiple roots naturally, however only over integral domains. (We will see how the polynomial remainder theorem generalizes to multiple evaluations in a moment.)

Theorem 7.3 (generalized factor theorem). Let $\mathbb{D}$ be an integral domain, $p\in \mathbb{D}[X]$ be a polynomial, and $u_1,\dots ,u_n\in \mathbb{D}$ be $n$ distinct ring elements. Then $u_1,\dots ,u_n$ are roots of $p$ if and only if ${\prod }_{i=1}^n(X-u_i)$ divides $p.$

Proof

Assume that ${\prod }_{i=1}^n(X-u_i)$ divides $p.$ Then there exists $q\in \mathbb{D}[X]$ such that $$p(X)=q(X)\prod _{i=1}^n(X-u_i)$$ which implies that $p(u_1)=\cdots =p(u_n)=0.$

We will prove the converse by induction on $n.$ The case $n=1$ is simply the factor theorem. Assume that the implication holds for $n-1$ and let us prove that it holds for $n.$ Let $p\in \mathbb{D}[X]$ and $u_1,\dots ,u_n$ be distinct roots of $p.$ Since $u_n$ is in particular a root of $p,$ by the factor theorem, there exists $q\in \mathbb{D}[X]$ such that $$p(X)=(X-u_n)q(X).$$ Moreover, for every $i\in \{1,\dots ,n-1\},$ $$p(u_i)=(u_i-u_n)q(u_i)=0,$$ which implies that $q(u_i)=0$ since $u_i$ and $u_n$ are distinct and $\mathbb{D}$ has no zero divisors. Hence, $u_1,\dots ,u_{n-1}$ are roots of $q,$ which by the induction hypothesis implies that ${\prod }_{i=1}^{n-1}(X-u_i)$ divides $q.$ Since $p(X)=(X-u_n)q(X),$ ${\prod }_{i=1}^n(X-u_i)$ divides $p.$

This has an important consequence regarding the maximal number of roots of a polynomial.

Proposition 7.6. Let $\mathbb{D}$ be an integral domain and let $p\in \mathbb{D}[X]$ be a non-zero polynomial of degree $d.$ Then $p$ has at most $d$ distinct roots in $\mathbb{D}.$

Proof

This follows easily from the generalized factor theorem. Indeed, assume that $p$ has degree $d$ and has $n>d$ roots. Let $u_1,\dots ,u_n$ denote the roots of $p.$ Then ${\prod }_{i=1}^n(X-u_i)$ divides $p,$ a contradiction with Proposition 7.4 as a polynomial of degree $n$ cannot divide a non-zero polynomial of degree $d<n.$

Let us prove the proposition directly by induction on $d.$ The result clearly holds for $d=0.$ Let $d\ge 1$ and assume that the result holds for degree $0,\dots ,d-1.$ Let $p\in \mathbb{D}[X]$ be a polynomial of degree $d.$ If $p$ has no root then the result holds again. Otherwise, assume that $p$ has a root $u\in \mathbb{D}.$ Then, by the factor theorem, $p(X)=(X-u)q(X)$ for some polynomial $q,$ where, by Proposition 7.3, $q$ has degree $d-1.$ If $u^{\prime }$ is a root of $p$ distinct from $u,$ then $(u^{\prime }-u)q(u^{\prime })=0$ which implies that $q(u^{\prime })=0$ since $u^{\prime }-u\ne 0$ and $\mathbb{D}$ has no zero divisors. Since $q$ has at most $d-1$ distinct roots by the induction hypothesis, $p$ has at most $d$ distinct roots.

This proposition allows us to reconsider the relation between polynomials and polynomial functions.

Proposition 7.7. Let $\mathbb{D}$ be an integral domain and $p\in \mathbb{D}[X]$ be a polynomial such that for every $u\in \mathbb{D},$ $p(u)=0.$ If $\mathbb{D}$ is infinite, then $p$ is the zero polynomial.

Proof

Assume that $p$ is not the zero polynomial and let $d$ be the degree of $p.$ Then, by Proposition 7.6, $p$ has at most $d$ distinct roots in $\mathbb{D},$ a contradiction with the assumption that $p(u)=0$ for every $u\in \mathbb{D}$ since $\mathbb{D}$ is infinite. Hence, $p$ must be the zero polynomial.

Hence, over an infinite integral domain, if $p$ and $q$ are two polynomials such that $p(x)=q(x)$ for every $x\in \mathbb{D},$ then $p=q.$ In other words, there is a one-to-one mapping between polynomials and polynomial functions. However, not every function from $\mathbb{D}$ to $\mathbb{D}$ is a polynomial function: for example, the function $f$ such that $f(0)=1$ and $f(u)=0$ for $u\ne 0$ is not a polynomial since it has infinitely many roots yet it cannot be the function corresponding to the zero polynomial.

We can in fact be more precise with the following proposition.

Proposition 7.8. Let $\mathbb{D}$ be an integral domain. Let $\Phi :\mathbb{D}[X]\to \mathcal{F}(\mathbb{D})$ be the ring homomorphism mapping a polynomial to the corresponding polynomial function. Then:

1. If $\mathbb{D}$ is finite, then $\Phi$ is surjective but not injective.
2. If $\mathbb{D}$ is infinite, then $\Phi$ is injective but not surjective.

Remark 7.1. Note that being infinite and being an integral domain are two necessary conditions. Over infinite rings with zero divisors, a non-zero polynomial may evaluate to zero over the entire ring. See here.

Lagrange Interpolation

In all the following, a set $\mathcal{U}=\{u_1,\dots ,u_n\}$ of $n$ distinct field elements $u_i\in \mathbb{F}$ will be called an evaluation domain (or simply domain) of size $n.$

Theorem 7.4 (Lagrange interpolation theorem). Let $\mathbb{F}$ be a finite field and let $$\mathcal{E}=\{(u_1,v_1),\dots ,(u_n,v_n)\}\subset {\mathbb{F}}^2$$ be a set of $n$ pairs of field elements such that $u_i\ne u_j$ for $i\ne j.$ Then there is a unique polynomial $\ell (X)\in {\mathbb{F}}_{}^{(\le n-1)}[X],$ called the Lagrange interpolation polynomial for $\mathcal{E},$ such that $\ell (u_i)=v_i$ for every $i\in \{1,\dots ,n\}.$

Proof

Uniqueness is proved as follows: assume there exists two polynomials $p(X)$ and $q(X)$ interpolating the $n$ points. Then the polynomial $p(X)-q(X)$ has $n$ roots but has degree at most $n-1,$ hence by Proposition 7.6 it must be the zero polynomial, which implies that $p(X)=q(X).$

To establish existence, one introduces the Lagrange basis associated with the domain $\mathcal{U}=\{u_1,\dots ,u_n\}.$ This is the tuple of polynomials $({\ell }_1(X),\dots ,{\ell }_n(X))$ of degree $n-1$ defined as $${\ell }_j(X):=\prod _{\begin{array}{c}1\le k\le n\\ k\ne j\end{array}}\frac{X-u_k}{u_j-u_k}.$$ One can easily check that $${\ell }_j(u_i)=\{\begin{array}{ll}0& \text{if }i\ne j\\ 1& \text{if }i=j.\end{array}$$ Then the Lagrange interpolating polynomial for $\{(u_1,v_1),\dots ,(u_n,v_n)\}$ is given by $$\ell (X):=\sum _{j=1}^n{v}_j{\ell }_j(X).$$ This polynomial has degree at most $n-1$ and it is easy to see that $\ell (u_i)=v_i$ for every $i\in \{1,\dots ,n\}.$

Note that the Lagrange basis $({\ell }_1(X),\dots ,{\ell }_n(X))$ associated with any domain $\mathcal{U}=\{u_1,\dots ,u_n\}$ is indeed a basis for the $\mathbb{F}$-vector space ${\mathbb{F}}_{}^{(\le n-1)}[X]$ in the linear algebra sense. The coordinates of a polynomial $p\in {\mathbb{F}}_{}^{(\le n-1)}[X]$ in this basis are $(p(u_1),\dots ,p(u_n)).$

A polynomial specified by a tuple $(a_0,\dots ,a_{n-1})$ such that $p(X)={\sum }_{i=0}^{n-1}{a}_i{X}^i$ is sometimes said to be in coefficients form, while when it is specified by the values $(v_1,\dots ,v_n)$ it takes over some domain $\mathcal{U}=\{u_1,\dots ,u_n\}$ it is said to be in evaluation form. This is merely a change of basis.

Another way to look at Lagrange interpolation is as follows. Considering the coefficients $a_0,\dots ,a_{n-1}$ of a polynomial $p(X)={\sum }_{j=0}^{n-1}{a}_j{X}^j$ of degree $n-1$ as unknowns, each evaluation $p(u_i)=v_i,$ $i\in \{1,\dots ,n\}$ yields a linear equation $$\sum _{j=0}^{n-1}{u}_i^j{a}_j=v_i.$$ In matrix form, this yields $$\left(\begin{array}{ccccc}1& u_1& u_1^2& \cdots & u_1^{n-1}\\ 1& u_2& u_2^2& \cdots & u_2^{n-1}\\ & & ⋮& & \\ 1& u_n& u_n^2& \cdots & u_n^{n-1}\end{array}\right)\cdot \left(\begin{array}{c}{a}_0\\ a_1\\ ⋮\\ a_{n-1}\end{array}\right)=\left(\begin{array}{c}{v}_1\\ v_2\\ ⋮\\ v_n\end{array}\right)\text{\hspace{1em}(7.1)}$$ The matrix on the left-hand side is called a Vandermonde matrix. It is invertible if and only if the $u_i$'s are distinct, which gives another way to see that there is a unique polynomial of degree at most $n-1$ such that $p(u_i)=v_i$ for every $i\in \{1,\dots ,n\}.$

Generalized Polynomial Remainder Theorem

Lagrange interpolation allows us to formulate a generalization of the polynomial remainder theorem. Given an evaluation domain $\mathcal{U}=\{u_1,\dots ,u_n\},$ the vanishing polynomial over $\mathcal{U},$ denoted $z_{\mathcal{U}}(X),$ is the polynomial defined by $$z_{\mathcal{U}}(X):=\prod _{i=1}^n(X-u_i).$$ It is such that $z_{\mathcal{U}}(u)=0$ for every $u\in \mathcal{U},$ but it is not the Lagrange interpolation polynomial for $\{(u_1,0),\dots ,(u_n,0)\}$ since it has degree $n$ (the Lagrange interpolation polynomial for $\{(u_1,0),\dots ,(u_n,0)\}$ is actually the zero polynomial).

Theorem 7.5 (generalized polynomial remainder theorem). Let $p\in \mathbb{F}[X]$ be a polynomial, $n\in \{1,\dots ,\mathrm{deg}(p)\}$ be an integer, $u_1,\dots ,u_n\in \mathbb{F}$ be $n$ distinct field elements, and $v_1,\dots ,v_n\in \mathbb{F}$ be $n$ field elements (not necessarily distinct). Let $z(X)$ be the vanishing polynomial for $\{u_1,\dots ,u_n\}$ and $\ell (X)$ be the Lagrange interpolation polynomial for $\{(u_1,v_1),\dots ,(u_n,v_n)\}.$ Then $p(u_i)=v_i$ for every $i\in \{1,\dots ,n\}$ if and only if $z(X)$ divides $p(X)-\ell (X),$ or equivalently if and only if $\ell (X)$ is the remainder of the division of $p(X)$ by $z(X).$

Proof

Assume that $z(X)$ divides $p(X)-\ell (X),$ i.e., there exists $q\in \mathbb{F}[X]$ such that $p(X)=q(X)z(X)+\ell (X).$ Evaluating this equality at $u_i$ and using $z(u_i)=0$ and $\ell (u_i)=v_i$ implies that $p(u_i)=v_i$ for every $i\in \{1,\dots ,n\}.$

Conversely, assume that $p(u_i)=v_i$ for every $i\in \{1,\dots ,n\}.$ Since $\mathbb{F}[X]$ is Euclidean, there exists polynomials $q(X)$ and $r(X)$ such that $p(X)=q(X)z(X)+r(X)$ with $\mathrm{deg}(r)<\mathrm{deg}(z)=n.$ Evaluating this equality at $u_i,$ $i\in \{1,\dots ,n\},$ yields $r(u_i)=p(u_i)=v_i.$ Since $\mathrm{deg}(r)<n,$ $r$ is necessarily the Lagrange interpolation polynomial for $\{(u_1,v_1),\dots ,(u_n,v_n)\}.$

For $n=1,$ one exactly recovers the polynomial remainder theorem since for a single point $(u,v)$ the vanishing polynomial is $X-u$ and the Lagrange interpolation polynomial is simply the constant polynomial $\ell (X)=v.$

Computational Aspects

Newton's method and Neville's algorithm have quadratic complexity.

The Barycentric Formula

Assume we are given a set of $n$ evaluations $\mathcal{E}=\{(u_1,v_1),\dots (u_n,v_n)\}$ over domain $\mathcal{U}=\{u_1,\dots ,u_n\}.$ One can consider various task related to the Lagrange interpolation polynomial $\ell$ for $\mathcal{E}.$ One is to compute the coefficients $(a_0,\dots ,a_{n-1})$ of this polynomial. Another is to evaluate $\ell$ on a field element $u\notin \{u_1,\dots ,u_n\}.$

For the first task, one may be tempted to solve Eq. (7.1). However, this requires to invert a square matrix of size $n,$ which requires $O(n^3)$ field operations.

A very useful form for Lagrange interpolation is the so-called barycentric formula [BT04]. Let $z(X)$ be the vanishing polynomial for $\{u_1,\dots ,u_n\}$ and for $j\in \{1,\dots ,n\}$ let $w_j$ denote the barycentric weights defined as $$w_j:=\frac{1}{{\prod }_{\begin{array}{c}1\le k\le n\\ k\ne j\end{array}}(u_j-u_k)}.$$ Note that the formal derivative of $z(X)$ is $$z^{\prime }(X)=\sum _{i=1}^n\prod _{\begin{array}{c}1\le k\le n\\ k\ne i\end{array}}(X-u_k),$$ hence one also has $$w_j=\frac{1}{z^{\prime }(u_j)}.$$ Then the $j$-th polynomial of the Lagrange basis is $$\begin{array}{rl}{\ell }_j(X)& :=\prod _{\begin{array}{c}1\le k\le n\\ k\ne j\end{array}}\frac{X-u_k}{u_j-u_k}\\ & =w_j\frac{z(X)}{X-u_j}\end{array}$$ from which it follows that the Lagrange interpolation polynomial for $\mathcal{E}$ can be written as $$\ell (X)=z(X)\sum _{i=1}^n\frac{w_i{v}_i}{X-u_i}.$$ This is the barycentric Lagrange interpolation formula.

Based on this, here is how one can compute the coefficients of $\ell$ and evaluate $\ell$ on a point outside $\mathcal{U}$ in quasilinear time:

• compute the coefficients of $z(X)$ using a divide-and-conquer approach (see here)
• compute the coefficients of $z^{\prime }(X)$ from the ones of $z(X)$ (this requires $O(n)$ multiplications)
• compute $w_j=z^{\prime }(u_j),$ $j\in \{1,\dots ,n\},$ using multipoint evaluation

See also this.

Once this is done, computing $\ell (u)$ for $u\notin \mathcal{U}$ takes linear time using $$\ell (u)=z(u)\sum _{i=1}^n\frac{w_i{v}_i}{u-u_i}.$$

All in all, this yields an algorithm with complexity $O(n{\log }^{2}n)$ field operations.

The Special Case of Roots of Unity

The most favorable case from a computational point of view is when $\mathcal{U}$ is the subgroup of ${\mathbb{F}}^{\ast }$ consisting of $n$-th roots of unity. Then the vanishing polynomial takes a very simple form, namely $$z(X)=X^n-1.$$ Its formal derivative is simply $$z^{\prime }(X)=n{X}^{n-1}.$$

Applications

An important application of Lagrange interpolation is Shamir's secret sharing.