Univariate polynomials

A polynomial of degree $n$ is a function of the form $f(x) = a_n x^n + a_{n-1}x^{n-1} + \ldots + a_1 x + a_0$ where $a_i \in {\mathbb R}$ for all $i$ and $a_n \neq 0$. Denote by $\deg(f)$ the degree of polynomial $f$. For example, $q(x) = x^3 + 2x^2 - 1$ is a polynomial of degree three with coefficients $a_3 = 1, a_2 = 2, a_1=0, a_0= -1$. The evaluation of $f$ at $a$ is $f(a)$. For instance, $q(2) = (2)^3 + 2 (2)^2 -1 = 15$. We say that $a$ is a root of polynomial $p$ if $p(a) = 0$.

Exercise 119

Prove: $f(x) \sim a_n x^n$ for every $x \ge 1$.

Below are two fundamental results that we rely on in this chapter. We will prove them later.

Theorem 43 (Roots of polynomials)

A non-zero polynomial of degree $d$ has at most $d$ roots.

Theorem 44 (Interpolation)

Given any $d+1$ points in the plane: $(x_1,y_1), \ldots, (x_{d+1},y_{d+1}) \in {\mathbb R}^2$ where the $x_i$'s are distinct, there exists a unique degree-$d$ polynomial $p$ with $p(x_i) = y_i$ for all $i \in [d+1]$.

The figures below show the cases for polynomials of degree $1$ and $2$.

Figure 15: The unique line (degree-1 polynomial) through $(1,2)$ and $(3,1)$.

Figure 16: The unique parabola (degree-2 polynomial) through $(-2,3)$, $(0,1)$, and $(4,10)$

📄️ Proof of Theorem 44 (Interpolation)Single Page

📄️ Proof of Theorem 43 (Roots of polynomials)Single Page

📄️ Finite fieldsSingle Page

📄️ Application: Secret sharingSingle Page

📄️ Application: Error-correcting codesSingle Page