Polynomials

Polynomials are one of the first things you learn from high school. (I think.) You already know what they are. They look like $x^4 + 3x^2 + 6x + 10$ or $x^4y^7 + 3.51\, x^2z + 10y$. Basically, a polynomial is an expression consisting of variables and real numbers joined together with only addition, subtraction and multiplication. You might be wondering why I didn't include exponents; that's because you're only allowed nonnegative integer exponents, and those can be made using only multiplications, e.g., $x^3 = x\cdot x\cdot x$.

We can also look at polynomials as functions on the variables. For example, $p(x) = x^3 + 3x$ is a function mapping every $x$ into $x^3 + 3x$, so for instance $p(3) = 36$. And $q(x,y) = x^3y^2 + 5$ is a function mapping every pair $(x,y)$ into $x^3y^2 + 5$, so $q(1,2) = 9$.

Polynomials with a single variable

We'll focus on polynomials with a single variable, $x$. For example, $x^3 + 3x$ and $x^4 + 3x^2 + 6x + 10$.

Polynomials behave like numbers in many ways. There are operations between them that have counterparts with numbers: addition, subtraction, and multiplication. For example, $$(x^2 + 5) + (x^3 - 2x^2 + x) = x^3 -x^2 + x + 5,$$ $$(x^3 - 1) - (x^4 + 5) = -x^4 + x^3 - 6$$ and $$(x + 1)(x^2 - 1) = x^3 + x^2 - x - 1.$$ You can also divide polynomials, but there's no guarantee that the result is a polynomial. For example, $x^2 - 1$ divided by $x + 1$ is $x - 1$, but $1$ divided by $x$ is not a polynomial.

The additive identity in polynomials is $0$ and the multiplicative identity is $1$. (Note that $0$ and $1$ are also polynomials.) To form the additive inverse of a polynomial, simply negate all its coefficients.

In code, polynomials can be represented easily with just an array of its coefficients. I'm sure you'll be able to implement the polynomial operations above. (Try it!)

Polynomial division

Here are some useful stuff about polynomials.

First, although dividing polynomials doesn't always result in a polynomial, we can still talk about division and remainders, just like with regular integers. There is a slight change though: With regular integers, the “remainder” of the division $a/b$ is always less than $b$. With polynomials, the “remainder” of the division $a(x)/b(x)$ always has a degree less than the degree of $b(x)$.

For example, dividing $x^4 + 2x^3 + 3x^2 + 4x + 5$ by $x^2 + 1$ results in a quotient of $x^2 + 2x + 2$ and a remainder of $2x + 3$. Note that $2x + 3$ has degree less than $x^2 + 1$.

The existence of these polynomials follow from the following “division theorem for polynomials”:


Division theorem for polynomials. For $a(x)$ and $b(x)$ with $\operatorname{deg} b > 0$, there exist polynomials $q(x)$ and $r(x)$ such that $a(x) = b(x)q(x) + r(x)$ and either $r(x) = 0$ or $\operatorname{deg} r < \operatorname{deg} b$.

Other useful theorems follow from this:


Remainder theorem. The remainder when $p(x)$ is divided by $x - c$ is the constant polynomial $p(c)$.

For example, what is the remainder when $x^{10} - x^9 + 2x^8 - 3x^3$ is divided by $x - 2$? Using the remainder theorem, it's simply the value when $2$ is substituted: $$\begin{align*} & (2)^{10} - (2)^9 + 2(2)^8 - 3(2)^3 \\ &= 2^{10} - 2^9 + 2^9 - 3(8) \\ &= 1024 - 24 \\ &= 1000 \end{align*}$$

Thus, the remainder is $1000$, and we didn't even need to divide the polynomials!

Here's the proof:

Proof. By the division theorem, $p(x) = q(x)(x - c) + r(x)$ for some polynomials $q(x)$ and $r(x)$ with $\operatorname{deg} r < 1$. The latter means that $r(x)$ must be constant. So let's just write $r(x) = r$, so $p(x) = q(x)(x - c) + r$. Substituting $x = c$ to both sides, we get $p(c) = q(c)(c - c) + r = 0 + r = r$. Thus, the remainder is indeed $p(c)$.

A relationship between a linear factor and a root of a polynomial follows from the remainder theorem.


Factor theorem. $x - c$ is a factor of $p(x)$ if and only if $c$ is a root of $p(x)$.

Proof. For the forward direction, assume $x - c$ is a factor of $p(x)$. Then $p(x) = (x - c)q(x)$ for some polynomial $q(x)$. Substituting $x = c$ to both sides, we find that $p(c) = (c - c)q(c) = 0$, proving that $c$ is a root.

For the backward direction, assume $c$ is a root of $p(x)$. Then $p(c) = 0$. By the remainder theorem, $0$ is the remainder when $p(x)$ is divided by $x - c$. But this means that $x - c$ is a factor of $p(x)$!

Roots and coefficients

An interesting theorem relating the number of roots of a polynomial with the signs of the coefficients is Descartes' rule of signs. An introduction can be found in http://hotmath.com/hotmath_help/topics/descartes-rule-of-signs.html, and a proof sketch can be found in https://www.math.hmc.edu/funfacts/ffiles/20001.1.shtml.

There are also relationships between a polynomial's roots and the coefficients themselves. For example, consider the degree-4 polynomial $$(x - r_1)(x - r_2)(x - r_3)(x - r_4).$$ Expanding this product, we get $$\begin{align*} (x - r_1)(x - r_2)(x - r_3)(x - r_4) = x^4 &- (r_1 + r_2 + r_3 + r_4)x^3 \\ &+ (r_1r_2 + r_1r_3 + r_1r_4 + r_2r_3 + r_2r_4 + r_3r_4)x^2 \\ &- (r_1r_2r_3 + r_1r_2r_4 + r_1r_3r_4 + r_2r_3r_4)x \\ &+ r_1r_2r_3r_4\end{align*}$$ If we write the polynomial in coefficient form $x^4 + ax^3 + bx^2 + cx + d$, then we find that: $$\begin{align*} -a &= r_1 + r_2 + r_3 + r_4 \\ b &= r_1r_2 + r_1r_3 + r_1r_4 + r_2r_3 + r_2r_4 + r_3r_4 \\ -c &= r_1r_2r_3 + r_1r_2r_4 + r_1r_3r_4 + r_2r_3r_4 \\ d &= r_1r_2r_3r_4 \end{align*}$$

This means we can find out the sum and product of all the roots of a polynomial based only on the coefficients, without knowing the roots themselves! I'll leave it up to you to generalize this for higher degree polynomials.

As a side note, notice that each coefficient above can be expressed as a polynomial on the variables $r_1$, $r_2$, $r_3$ and $r_4$. This is also true for any other degree. These polynomials are called the elementary symmetric polynomials.

Polynomial factorization

We can also talk about factorization of (nonzero) polynomials. This is similar to integer factorization. Given a polynomial $p(x)$, we want to find two polynomials $a(x)$ and $b(x)$ such that $p(x) = a(x)b(x)$. However, just like we call $10\times 1$ a trivial factorization of a number $10$ (because it's not very interesting), we must also talk about trivial factorizations of polynomials. We say $p(x) = a(x)b(x)$ is a trivial factorization of $p(x)$ if $a(x)$ or $b(x)$ is constant. For example, $(2)(x^2-4)$ is a trivial factorization of $2x^2 - 8$, but $(2x+4)(x-2)$ is not.

Finally, we can also say a polynomial is prime if it doesn't have a nontrivial factorization. For example, $2x^2 - 8$ is not prime, as seen above. Note that constant polynomials are not considered prime.

However, primality of a polynomial actually depends on what coefficients we allow! For example, $x^2 - 3$ is prime when considering only rational coefficients, but it's not prime when considering real number coefficients because $x^2 - 3 = (x - \sqrt{3})(x + \sqrt{3})$. Also, if you're familiar with complex numbers, $x^2 + 4$ is prime on real coefficients, but not prime on complex coefficients, because $x^2 + 4 = (x + 2i)(x - 2i)$.

The product of two nonconstant polynomials is always of degree $\ge 2$. Thus, it can be shown that polynomials of degree $1$ are prime, no matter what coefficients we allow.

It's not exactly easy to factorize arbitrary polynomials, or even determine if it is prime. You might have learned how to factorize binomials such as $x^2 + 5x + 6$ from school, but what about higher-degree polynomials? It's not always so easy. For example, $x^4 + 4$ doesn't look factorable in rational numbers, but in fact it is: $$\begin{align*} x^4 + 4 &= x^4 + 4 + 0 \\ &= x^4 + 4 + (4x^2 - 4x^2) \\ &= (x^4 + 4x^2 + 4) - 4x^2 \\ &= (x^2 + 2)^2 - (2x)^2 \\ &= (x^2 + 2 - 2x)(x^2 + 2 + 2x) \\ &= (x^2 - 2x + 2)(x^2 + 2x + 2) \end{align*}$$

This worked because we were able to add the magic $(4x^2 - 4x^2)$ term. Of course this is just zero so it's okay to add it, but how do we know to add $(4x^2 - 4x^2)$ and not, say, $(5x^2 - 5x^2)$? There doesn't seem to be a general way to do it, especially for higher-degree polynomials. (Note: There are lots of good polynomial factorization methods, but we won't discuss them.)

Roots of polynomials

Note: This section requires complex numbers. If you don't know them yet, feel free to skip this.

However, when the coefficients are complex numbers, things are much easier. This is because of the following famous theorem:

Fundamental theorem of algebra. Every nonconstant polynomial on one variable with complex coefficients has at least one complex root.

Please watch this YouTube video for a nice proof of this theorem :D

Now, how does this help? This actually gives us an algorithm for factoring any complex polynomial!

  1. Find a (complex) root of $p(x)$. Let's call this root $c$. Then by the factor theorem, $x - c$ is a factor.
  2. Divide $p(x)$ by $x - c$ to get a new polynomial $q(x)$.
  3. Repeat the algorithm on $q(x)$, until the polynomial becomes constant.

Since at every step, the degree of the polynomial decreases by one, this halts after $\operatorname{deg} p$ steps. This gives us the following corollaries of the fundamental theorem of algebra:

Proposition 1. The only prime polynomials with complex coefficients are the linear polynomials.

Proposition 2. Every nonconstant polynomial on one variable with complex coefficients can be factored into linear polynomials.

The algorithm above can be converted to code straightforwardly. Dividing by a linear factor is easy. You can probably learn it from high school. The only issue now is how to find a root of a given polynomial. This is somewhat of a specialized topic, so we won't discuss it. Instead, we will refer the interested reader to popular root-finding algorithms such as Newton's method.

Problems