5.1 Polynomials

Polynomial

A polynomial in one variable $x$ is an expression of the form
$f(x)=c_d{x}^d+c_{d-1}{x}^{d-1}+\cdots +c_{1}x+c_0,$
where $d\in \mathbb{N}$ is the degree of the polynomial (assuming $a_d\ne 0$), and $c_i$ is the $i$-th coefficient of the polynomial, typically a constant. This is known as the coefficient representation of a polynomial.

Given two polynomials $f(x)$ and $g(x)$, where $g(x)\ne 0$, and both defined over the same field, there exist unique polynomials $q(x)$ and $r(x)$, called the quotient and the remainder, such that
$f(x)=g(x)q(x)+r(x),$
with the constraint that $\mathrm{deg}r(x)<\mathrm{deg}g(x)$.

The computation of $q(x)$ and $r(x)$ is typically carried out using polynomial long division. The steps for the algorithm are as follows:

1. Arrange both the dividend $f_1(x)$ and divisor $g_1(x)$ in descending powers of $x$.
2. Initialize the quotient $q_1(x)=0$.
3. While $\mathrm{deg}{f}_i(x)\ge \mathrm{deg}{g}_i(x)$:
4. Divide the leading term of $f_i(x)$ by the leading term of $g_i(x)$.
5. Multiply $g_i(x)$ by this term.
6. Subtract the result from $f_i(x)$ to get $r_i(x)$.
7. Add this new term to $q_i$, and call it $q_{i+1}$.
8. Set $r_{i+1}(x)=f_i(x)$ for the next iteration.
9. Equivalently, you will be done when $\mathrm{deg}r<\mathrm{deg}g$.

Properties

(Factor Theorem) If $a$ is a root of a polynomial $f(x),$ then $(x-a)$ is a factor of $f(x)$, such that $f(x)=(x-a)q(x)$ for some $q(x)$ where $\mathrm{deg}q(x)=\mathrm{deg}f(x)-1$.

Dividing $f(x)$ by $(x-a)$ leads to $f(x)=(x-a)q(x)+r(x)$. Per polynomial division, the degree of the remainder is necessarily smaller than the degree of $(x-a)$, so it is a constant. However, $a$ is a root, so we have $f(a)=r(a)=0$. As such, $f(x)=(x-1)q(x)$ .

(Factorization Theorem) A degree-$d$ polynomial with $d$ distinct roots $a_1,\dots ,a_d$ can be written as $f(x)=c(x-a_1)(x-a_2)\cdots (x-a_d)$.

The factorization theorem is a continuation of the factor theorem. Apply it to all $d$ distinct roots, and you get the factorization, where $c=q(x)$ since the final quotient is a degree-$0$ polynomial.

(Number of Roots) A polynomial of degree $d$ has at most $d$ roots.

We’ll prove this by contradiction. Say that a polynomial of degree $d$ has $d+1$ roots. This means that a factorization $f(x)=(x-a_1)\dots (x-a_{d+1})q(x)$ exists. But then $f(x)$ would have a degree of at least $d+1$, contradicting the assumption that $\mathrm{deg}f=d$.

(Value Representation) Given $d+1$ points $(x_1,y_1),\dots ,(x_{d+1},y_{d+1})$ with all $x$-values distinct, there exists a unique polynomial $f(x)$ of degree at most $d$ that passes through all of those points (i.e., $f(x_i)=y_i$ for $1\le i\le d+1$).

We know that such a polynomial exists due to Lagrange interpolation. However, how do we know that it’s unique? Say that there exist two polynomials $f(x)$ and $g(x)$, such that $\mathrm{deg}f=d\ge \mathrm{deg}d$, that pass through all of our points.

Examples

(Very Easy) Longing for Division

(Easy) Polynomial Arithmetic Over the Reals

If $f$ and $g$ are non-zero real polynomials, how many real roots do the following polynomials have at least? How many can they have at most?

$f+g$ The sum can have as few as $0$ roots if both $f$ and $g$ are constant, or up to $\max (\mathrm{deg}f,\mathrm{deg}g)$ roots if no cancellation occurs in the highest-degree terms.

$f\times g$ Again if both polynomials are constants, the product can have zero roots. In general, multiplying two polynomials can lead to either adding or canceling out the leading terms. This means the product can have at most $d_f+d_g$ roots if the highest-degree terms are both positive.

$f/g$ (assuming it's a polynomial) Dividing a constant by a constant leads to a constant. Therefore, the minimum roots is $0$. Since we are dividing the leading term of $f$ by the leading term of $g$, the product can have at most $\mathrm{deg}f-\mathrm{deg}g$ roots.