Polynomials · The Lumenary

MotivationH

A box from a sheet of card

A cooperative of packaging makers in Oaxaca folds open boxes from rectangular sheets of card, $30$ cm by $20$ cm. From each corner they cut a square of side $x$ cm and fold up the sides. The box is $x$ cm tall, with a base of $(30 - 2x)$ by $(20 - 2x)$ cm, so its volume is

V(x) = x(30 - 2x)(20 - 2x) = 4x^3 - 100x^2 + 600x \quad \text{cubic centimetres}.

A customer wants boxes holding exactly one litre, $1000\ \text{cm}^3$ . Trying $x = 5$ gives $V(5) = 5 \cdot 20 \cdot 10 = 1000$ . Success! But is $x = 5$ the only size that works? A shorter, wider box might use the card differently.

We need to solve $4x^3 - 100x^2 + 600x - 1000 = 0$ , an equation of degree three. Guessing found one solution. This lesson shows how one known solution splits the problem into a smaller one, and how many solutions there can possibly be. (We finish the box at the end of the worked examples.)

IntuitionH

Polynomials are like numbers in base x

The number $312$ means $3 \cdot 10^2 + 1 \cdot 10 + 2$ . The expression $3x^2 + x + 2$ is the same pattern with the base $10$ replaced by a letter, and putting $x = 10$ gives back $312$ .

This is more than a coincidence of notation. You add polynomials by collecting like powers, as you add numbers column by column. You multiply them with the same grid as long multiplication, only without carrying: a coefficient may grow as large as it likes. And you divide them by a long-division process that works one leading term at a time. Polynomials are the integers of algebra, and the parallel runs deep — both have a division algorithm with remainders, both have "primes" (irreducible polynomials), and both factorise uniquely into them (up to signs or constant factors).

DefinitionsH

Definitions

Definition— polynomial

A polynomial in $x$ with real coefficients is an expression

p(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0,

where $n \ge 0$ is a whole number and $a_0, \dots, a_n$ are real numbers, the coefficients. Two polynomials are equal when their coefficients of each power of $x$ agree.

Definition— degree, leading coefficient

If $a_n \neq 0$ , then $n$ is the degree of $p$ , written $\deg p$ , and $a_n$ is its leading coefficient. A polynomial whose leading coefficient is $1$ is called monic. The zero polynomial (all coefficients $0$ ) has no degree: by convention we leave $\deg 0$ undefined (some books write $-\infty$ ).

Definition— root

A number $a$ is a root (or zero) of $p$ if $p(a) = 0$ . Here $p(a)$ means: substitute $a$ for $x$ and calculate.

Degree- $0$ polynomials are the non-zero constants; degrees $1, 2, 3, 4$ are called linear, quadratic, cubic and quartic. Expressions such as $1/x$ , $\sqrt{x}$ or $2^x$ are not polynomials: only whole-number powers of $x$ are allowed.

Theorem— Lemma (degree of a product)

If $p$ and $q$ are non-zero polynomials with real coefficients, then $pq \ne 0$ and $\deg(pq) = \deg p + \deg q$ . Also $\deg(p + q) \le \max(\deg p, \deg q)$ when $p + q \neq 0$ .

Proof

Let the leading terms be $a x^m$ and $b x^n$ with $a, b \ne 0$ . When we multiply out $pq$ , the only way to make $x^{m+n}$ is $a x^m \cdot b x^n$ ; every other product of terms has a smaller power. So the coefficient of $x^{m+n}$ in $pq$ is $ab$ , which is non-zero because a product of two non-zero real numbers is non-zero. No higher power appears. For the sum, no power above $\max(m, n)$ occurs in either polynomial.

∎

The sum can have a smaller degree than both summands: $(x^2 + x) + (-x^2 + 1) = x + 1$ .

Worked examplesH

Worked examples

Example— Special products

These identities hold for all numbers $a, b$ (expand the right-hand sides to check):

(a + b)^2 = a^2 + 2ab + b^2, \qquad a^2 - b^2 = (a - b)(a + b),

a^3 + b^3 = (a + b)(a^2 - ab + b^2), \qquad a^3 - b^3 = (a - b)(a^2 + ab + b^2).

Read from right to left they multiply; read from left to right they factorise. For example $x^4 - 16 = (x^2 - 4)(x^2 + 4) = (x - 2)(x + 2)(x^2 + 4)$ , and $8x^3 + 27 = (2x)^3 + 3^3 = (2x + 3)(4x^2 - 6x + 9)$ .

Example— Factorising by grouping

x^3 + 2x^2 - 9x - 18 = x^2(x + 2) - 9(x + 2) = (x + 2)(x^2 - 9) = (x + 2)(x - 3)(x + 3).

So the roots are $-2, 3, -3$ : a product is zero exactly when one of its factors is.

Example— Non-examples: what does not factorise

$x^2 + 1$ has no real roots ( $x^2 + 1 \ge 1$ for every real $x$ ), so it has no factor $x - a$ with $a$ real. It does factorise over the complex numbers: $x^2 + 1 = (x - i)(x + i)$ .
$x^2 - 2 = (x - \sqrt 2)(x + \sqrt 2)$ factorises with real coefficients but not with rational ones, because $\sqrt 2$ is irrational (see real numbers).

Whether a polynomial factorises depends on which numbers you allow as coefficients.

Example— Long division

Divide $p(x) = x^4 + 3x^3 - x + 5$ by $d(x) = x^2 + 1$ . At each step, divide the leading term of what is left by the leading term $x^2$ of $d$ :

$x^4 \div x^2 = x^2$ . Subtract $x^2(x^2 + 1) = x^4 + x^2$ : left with $3x^3 - x^2 - x + 5$ .
$3x^3 \div x^2 = 3x$ . Subtract $3x(x^2 + 1) = 3x^3 + 3x$ : left with $-x^2 - 4x + 5$ .
$-x^2 \div x^2 = -1$ . Subtract $-1 \cdot (x^2 + 1)$ : left with $-4x + 6$ .

The leftover $-4x + 6$ has degree $1 < 2 = \deg d$ , so we stop:

x^4 + 3x^3 - x + 5 = (x^2 + 3x - 1)(x^2 + 1) + (-4x + 6).

The quotient is $x^2 + 3x - 1$ and the remainder is $-4x + 6$ .

Example— Synthetic division by x − a

Dividing by $x - a$ is so common that it has a shortcut, synthetic division (Horner's or Ruffini's rule). Divide $2x^3 - 3x^2 - 11x + 6$ by $x - 3$ : write the coefficients, bring down the first, then repeatedly multiply by $3$ and add:

	$2$	$-3$	$-11$	$6$
$\times 3$		$6$	$9$	$-6$
sum	$2$	$3$	$-2$	$\mathbf{0}$

The bottom row gives the quotient $2x^2 + 3x - 2$ and the remainder $0$ . So $2x^3 - 3x^2 - 11x + 6 = (x - 3)(2x^2 + 3x - 2) = (x - 3)(2x - 1)(x + 2)$ .

Example— Finishing the box

Back to the box: $V(x) - 1000 = 4(x^3 - 25x^2 + 150x - 250)$ , and we know $x = 5$ is a root. Synthetic division by $x - 5$ gives

x^3 - 25x^2 + 150x - 250 = (x - 5)(x^2 - 20x + 50).

The quadratic factor has roots $x = 10 \pm \sqrt{50} = 10 \pm 5\sqrt 2$ , about $2.93$ and $17.07$ . A cut of $17.07$ cm is impossible on a $20$ cm side (we need $0 < x < 10$ ), but $x = 10 - 5\sqrt 2 \approx 2.93$ cm works: a shorter, wider one-litre box. The cooperative has two designs to choose from — and, as we will prove, a cubic can never have more than three roots, so there are no others hiding.

ProofH

Division, remainders and roots

Theorem— Division algorithm

Let $p$ and $d$ be polynomials with real (or rational) coefficients, $d \ne 0$ . Then there are unique polynomials $q$ (the quotient) and $r$ (the remainder) with

p = q\,d + r \qquad \text{and} \qquad r = 0 \text{ or } \deg r < \deg d.

Proof

Existence, by strong induction on the degree of $p$ . If $p = 0$ or $\deg p < \deg d$ , take $q = 0$ and $r = p$ . Otherwise let $p$ have leading term $a x^n$ and $d$ have leading term $b x^m$ , with $n \ge m$ . The polynomial

p_1 = p - \tfrac{a}{b} x^{n-m} d

has the $x^n$ terms cancelled, so $p_1 = 0$ or $\deg p_1 < n$ . By the induction hypothesis $p_1 = q_1 d + r$ with $r = 0$ or $\deg r < \deg d$ . Then $p = \big(q_1 + \tfrac{a}{b} x^{n-m}\big) d + r$ . (This is exactly one step of long division.)

Uniqueness. Suppose $q_1 d + r_1 = q_2 d + r_2$ , both remainders being $0$ or of degree less than $\deg d$ . Then $(q_1 - q_2)\,d = r_2 - r_1$ . If $q_1 \ne q_2$ , the lemma on products says the left side has degree $\deg(q_1 - q_2) + \deg d \ge \deg d$ . But the right side is $0$ or has degree less than $\deg d$ . That is impossible, so $q_1 = q_2$ , and then $r_1 = r_2$ .

∎

We needed to divide by the leading coefficient $b$ . That is why the theorem is stated for rational or real coefficients. With integer coefficients it still works when $d$ is monic, such as $d = x - a$ .

Theorem— Remainder theorem

The remainder when $p(x)$ is divided by $x - a$ is the number $p(a)$ . That is, $p(x) = (x - a)\,q(x) + p(a)$ for some polynomial $q$ .

Proof

First proof. By the division algorithm, $p(x) = (x - a)q(x) + r$ where $r$ is $0$ or has degree less than $1$ , so $r$ is a constant. Substituting $x = a$ gives $p(a) = 0 \cdot q(a) + r = r$ .

Second proof, without the division algorithm. For each $k \ge 1$ ,

x^k - a^k = (x - a)\left(x^{k-1} + x^{k-2}a + \cdots + x a^{k-2} + a^{k-1}\right),

as you can check by expanding (the middle terms cancel in pairs). If $p(x) = \sum_k c_k x^k$ then

p(x) - p(a) = \sum_{k} c_k \left(x^k - a^k\right),

and $x - a$ divides every term, so it divides $p(x) - p(a)$ .

∎

Theorem— Factor theorem

$x - a$ is a factor of $p(x)$ if and only if $p(a) = 0$ .

Proof

If $p(x) = (x - a)q(x)$ , then $p(a) = (a - a)\,q(a) = 0$ . Conversely, if $p(a) = 0$ , the remainder theorem gives $p(x) = (x - a)q(x) + 0$ .

∎

Theorem— Root bound

A non-zero polynomial of degree $n$ with real (or complex) coefficients has at most $n$ roots.

Proof

Induction on $n$ . A polynomial of degree $0$ is a non-zero constant and has no roots. Now let $\deg p = n \ge 1$ and assume the statement for degree $n - 1$ . If $p$ has no roots, we are done. Otherwise pick a root $a$ . By the factor theorem $p(x) = (x - a)q(x)$ , and by the lemma $\deg q = n - 1$ .

Let $b$ be any root of $p$ other than $a$ . Then $0 = p(b) = (b - a)\,q(b)$ . Since $b - a \ne 0$ and a product of real (or complex) numbers is zero only if a factor is zero, $q(b) = 0$ . So every root of $p$ is either $a$ or a root of $q$ . By the induction hypothesis $q$ has at most $n - 1$ roots, so $p$ has at most $1 + (n - 1) = n$ .

∎

Theorem— Corollary (identity theorem)

If two polynomials $p$ and $q$ , each zero or of degree at most $n$ , take the same values at $n + 1$ different numbers, then $p = q$ .

Proof

If $p \ne q$ , then $p - q$ is a non-zero polynomial of degree at most $n$ with at least $n + 1$ roots, contradicting the root bound.

∎

So a polynomial identity of degree $n$ can be proved by checking $n + 1$ values. That is unusual: in general, checking examples refutes but never proves. Here the root bound turns finitely many checks into a proof.

Theorem— Rational root test

Let $p(x) = a_n x^n + \cdots + a_1 x + a_0$ have integer coefficients, with $a_n \ne 0$ and $a_0 \neq 0$ . If a fraction $r/s$ in lowest terms is a root of $p$ , then $r$ divides $a_0$ and $s$ divides $a_n$ .

Proof

Substitute $x = r/s$ and multiply by $s^n$ :

a_n r^n + a_{n-1} r^{n-1} s + \cdots + a_1 r s^{n-1} + a_0 s^n = 0.

Every term except the last contains the factor $r$ , so $r$ divides $a_0 s^n$ . Since $r$ and $s$ have no common prime factor, $r$ shares none with $s^n$ , and so $r$ divides $a_0$ (by unique factorisation; see divisibility). Similarly every term except the first contains $s$ , so $s$ divides $a_n r^n$ and hence $s$ divides $a_n$ .

∎

For $2x^3 - 3x^2 - 11x + 6$ the only candidates are $\pm 1, \pm 2, \pm 3, \pm 6, \pm \tfrac12, \pm \tfrac32$ . Testing them finds $-2, \tfrac12, 3$ . For $x^3 - 2$ the candidates $\pm 1, \pm 2$ all fail, which proves that $\sqrt[3]{2}$ is irrational.

Note

Over the complex numbers much more is true. The fundamental theorem of algebra (first proved in the late 18th and early 19th centuries; see complex numbers) says every non-constant polynomial has a complex root. Applying the factor theorem again and again, every polynomial of degree $n$ splits into $n$ linear factors over $\mathbb{C}$ . So it has exactly $n$ complex roots when each is counted as often as its factor appears. We do not prove it here: every proof needs some analysis or topology — at the very least, the completeness of the real numbers.

Formal mathematicsF

The theorems, checked by Lean

Lean's library Mathlib has a type of polynomials, written R[X] for coefficients in R. In it, C a is the constant polynomial $a$ , p.eval a is $p(a)$ and p.natDegree is the degree. The special products are identities in any commutative ring, and the tactic ring checks them by expanding both sides:

diff_of_squaresLean 4Proved here from basic factsFormally verified

/-- **Difference of two squares:** `a² − b² = (a − b)(a + b)` in every commutative ring.
`ring` expands both sides and compares them — exactly the check you would do by hand. -/
theorem diff_of_squares {R : Type*} [CommRing R] (a b : R) :
    a ^ 2 - b ^ 2 = (a - b) * (a + b) := by
  ring

Axioms used: propext, Quot.soundformal/Lumenary/Polynomials.leanTry it in the Lean web editor

sum_and_diff_of_cubesLean 4Proved here from basic factsFormally verified

/-- **Sum and difference of two cubes:** `a³ + b³ = (a + b)(a² − ab + b²)` and
`a³ − b³ = (a − b)(a² + ab + b²)`. -/
theorem sum_and_diff_of_cubes {R : Type*} [CommRing R] (a b : R) :
    a ^ 3 + b ^ 3 = (a + b) * (a ^ 2 - a * b + b ^ 2) ∧
      a ^ 3 - b ^ 3 = (a - b) * (a ^ 2 + a * b + b ^ 2) := by
  constructor <;> ring

Axioms used: propext, Quot.soundformal/Lumenary/Polynomials.leanTry it in the Lean web editor

The second proof of the remainder theorem has two steps. First, $x - a$ divides $x^n - a^n$ , proved by induction from $x^{n+1} - a^{n+1} = x(x^n - a^n) + a^n(x - a)$ :

sub_dvd_pow_sub_pow'Lean 4Proved here from basic factsFormally verified

/-- **`x − a` divides `xⁿ − aⁿ`**, by induction on `n`, using the lesson's identity
`xⁿ⁺¹ − aⁿ⁺¹ = x(xⁿ − aⁿ) + aⁿ(x − a)`. (Mathlib: `sub_dvd_pow_sub_pow`.) -/
theorem sub_dvd_pow_sub_pow' {R : Type*} [CommRing R] (x a : R) (n : ℕ) :
    x - a ∣ x ^ n - a ^ n := by
  induction n with
  | zero => simp
  | succ n ih =>
    obtain ⟨q, hq⟩ := ih
    refine ⟨x * q + a ^ n, ?_⟩
    calc x ^ (n + 1) - a ^ (n + 1) = x * (x ^ n - a ^ n) + a ^ n * (x - a) := by ring
      _ = x * ((x - a) * q) + a ^ n * (x - a) := by rw [hq]
      _ = (x - a) * (x * q + a ^ n) := by ring

Axioms used: propext, Quot.soundformal/Lumenary/Polynomials.leanTry it in the Lean web editor

Then $p - p(a)$ is built from single terms $c\,x^k$ by adding, and each term is handled by the lemma:

remainder_theoremLean 4Proved here from basic factsFormally verified

/-- **Remainder theorem:** `X − a` divides `p − p(a)`, so `p = (X − a)·q + p(a)`.
As in the lesson: `p − p(a)` is a sum of terms `c (Xᵏ − aᵏ)`, and `X − a` divides each of them
(`sub_dvd_pow_sub_pow'`). Lean's induction principle `Polynomial.induction_on'` builds every
polynomial from single terms `c Xᵏ` by addition, so we check those two cases. -/
theorem remainder_theorem {R : Type*} [CommRing R] (p : R[X]) (a : R) :
    X - C a ∣ p - C (p.eval a) := by
  induction p using Polynomial.induction_on' with
  | add p q hp hq =>
    have h : p + q - C ((p + q).eval a) = (p - C (p.eval a)) + (q - C (q.eval a)) := by
      rw [eval_add, C_add]; ring
    rw [h]
    exact dvd_add hp hq
  | monomial n c =>
    have h : monomial n c - C ((monomial n c).eval a) = C c * (X ^ n - (C a) ^ n) := by
      rw [eval_monomial, ← C_mul_X_pow_eq_monomial, C_mul, C_pow]; ring
    rw [h]
    exact dvd_mul_of_dvd_right (sub_dvd_pow_sub_pow' X (C a) n) (C c)