Proving that Polynomial Division Works

I've been reading about polynomials lately and found that the polynomial division algorithm is a great example of a real algorithm that can be proved correct, and where a proof actually provides some insight in to how the algorithm works.

First lets get some notation out of the way: A polynomial, say  a , over a field  F is a formal sum:

 a = \sum_{k=0}^{n} a_k x^k

Expressions like

 1

 3 + 2x^4

 -19 + 2.3x + 1.5x^5

are all polynomials.

The set of all polynomials in variable  x over a field  F is denoted  F[x] .

I assume that if you are reading this you are familiar with the rules for polynomial addition, subtraction and multiplication, and that you know what the degree of a polynomial is, and what a monomial is.

The polynomial division algorithm

The polynomial division problem is: given u, v \in F[x] with  v \neq 0 find  q, r \in F[x] such that:

 u = qv + r

 deg(r) < deg(v) or  r = 0

We need to add the extra possibility  r = 0 because the degree of the zero polynomial is undefined.

An algorithm that can compute  q and  r is:

Input:  u \in F[x] ,  v \in F[x] ,  v \neq 0

 r \gets u

 q \gets 0

while  r \neq 0 and  lt(v) | lt(r) :

 r \gets r - \frac{lt(v)}{lt(r)} v

 q \gets q + \frac{lt(v)}{lt(r)}

return  (q, r)

The proof of correctness

We will break the proof up into 2 parts

  1. If the algorithm terminates it produces the correct result
  2. The algorithm always terminates

Proving the algorithm is correct when it terminates

First lets address part 1: proving that if the algorithm terminates it produces the correct result. This problem in turn will be broken into two parts

  1. First we prove that at the start of the while loop and after every iteration of the loop:  u = qv + r . The statement  u = qv + r is the loop invariant
  2. Second we prove that if the loop terminates  deg(r) < deg(v) or  r = 0

Proving that the invariant holds

At the start of the loop:

 r = u

 q = 0

So  qv + r = 0v + u = u

Now we need to show that if  u = qv + r on entry to the while loop, then it is true after one execution of the loop. To do this we need to introduce new variables to represent the values of  r and  q before and after the loop executes.

Lets call the values of  r and  q on entry to the loop  r_i and  q_i , and the values after execution of the loop  r_{i + 1} and  q_{i + 1} .

So assuming  u = q_{i}v + r_i , we need to show that after the execution of the loop  u = q_{i+1}v + r_{i+1} .

Looking at the body of the loop we can see that:

 r_{i+1} = r_i - \frac{lt(v)}{lt(r)} v

 q_{i+1} = q_i + \frac{lt(v)}{lt(r)}

So:

 q_{i+1}v + r_{i+1} = ( q_i + \frac{lt(v)}{lt(r)} )v + r_i - \frac{lt(v)}{lt(r)}v =

 q_i v + \frac{lt(v)}{lt(r)} v + r_i - \frac{lt(v)}{lt(r)}v =

 q_i v + r_i + \frac{lt(v)}{lt(r)} v - \frac{lt(v)}{lt(r)}v =

 q_i v + r_i = u

Proving the degree condition

Now we need to prove that  if the loop terminates:

 deg(v) > deg(r) or  r = 0

We split this up into two cases:  r = 0 an  r \neq 0 . If  r = 0 then we are done. If  r \neq 0 we have a little more work to do.

Looking at the loop we can see that the only way it will terminate is if

 \neg (lt(v) | lt(r))

So we need to prove that

 \neg (lt(v) | lt(r)) \Rightarrow deg(v) > deg(r)

This is actually pretty straightforward. By definition of the leading term of  a polynomial we know:

 lt(v) = c_v x^{deg(v)}

 lt(r) = c_r x^{deg(r)}

So by construction the term:  \frac{c_r}{c_v} x^{deg(r) - deg(v)} is the result of dividing  lt(r) by  lt(v) .  \neg (lt(v) | lt(r)) , if and only if this term is not defined.

There are only 2 ways the monomial  \frac{c_r}{c_v}x^{deg(r) - deg(v)} could be undefined: either  c_v = 0, or  deg(r) - deg(v) < 0 , but remember that the division algorithm assumes that  v \neq 0 , so it must be that:

 deg(r) - deg(v) < 0

Which is equivalent to the statement:

 deg(v) > deg(r)

Which is exactly what we set out to prove! Now we know that if the algorithm terminates it produces the correct quotient and remainder.

Proving termination

Producing the correct result when the algorithm stops is great, but does it always stop? Yes. The outline of why is below:

  1. Initially  r = 0 or  deg(r) \geq 0
  2. When  r = 0 or  deg(r) = 0 the algorithm terminates
  3. After every iteration of the loop either the degree of  r decreases or  r becomes zero.

The first statement follows from the definition of the degree of a polynomial. The degree of a polynomial is non-negative if it is defined, and is undefined for the zero polynomial.

The second statement follows straight from the algorithm itself. A program with no loops always terminates, and this program has only one loop, so if that loop terminates the program is guaranteed to terminate, and  r = 0 or  deg(r) = 0 is just saying that the loop condition is not met.

Proving that statement 3 is more involved. Lets suppose that the value of  r going into the loop is  r_i and the value after an iteration is  r_{i+1} . Then by definition:

 r_{i+1} = r_i - \frac{lt(r_i)}{lt(v)} v

So we need to prove that either:

 deg(r_i) > deg(r_i - \frac{lt(r_i)}{lt(v)} v)

or

 r_i - \frac{lt(r_i)}{lt(v)} v = 0

Without loss of generality we can rewrite  r as:

 r_i = lt(r_i) + r_l

And  v as:

 v = lt(v) + v_l

With this rewrite we can see that:

 r_{i+1} = lt(r_i) + r_l - \frac{lt(r_i)}{lt(v)} (lt(v) + v_l) =

 lt(r_i) + r_l - \frac{lt(r_i)}{lt(v)} lt(v) - \frac{lt(r_i)}{lt(v)} v_l =

 lt(r_i) + r_l - lt(r_i) - \frac{lt(r)}{lt(v)} v_l =

 r_l - \frac{lt(r)}{lt(v)} v_l

Now we have a few cases to consider. First lets suppose that:  r_l \neq 0 , \frac{lt(r)}{lt(v)}v_l \neq 0 , and  r_l - \frac{lt(r)}{lt(v)} v_l \neq 0 .

Then by the properties of polynomial degree we know that:

 deg(r_l - \frac{lt(r)}{lt(v)} v_l) \leq

 max(deg(r_l), deg(\frac{lt(r)}{lt(v)} v_l))

By definition  deg(r_l) < deg(r) , and  deg(v_l) < deg(v) .

Now suppose without loss of generality that :

 lt(v) = c_v x^{deg(v)}

 lt(r) = c_r x^{deg(r)}

Then:

 \frac{lt(r)}{lt(v)} = \frac{c_v}{c_r} x^{deg(v) - deg(r)}

so:

 deg(\frac{lt(r)}{lt(v)} v_l) = deg(\frac{lt(r)}{lt(v)}) + deg(v_l) =

 deg(v) - deg(r) + deg(v_l)

But since  deg(v_l) < deg(v) we know:

 deg(v) - deg(r) + deg(v_l) < deg(v) - deg(r) + deg(v) =

 2deg(v) - deg(r)

Since we are in the body of the loop we know that  lt(v) | lt(r) so  deg(v) < deg(r) , so:

 2deg(v) - deg(r) < 2deg(r) - deg(r) = deg(r)

So  deg(\frac{lt(r)}{lt(v)} v_l) < deg(r) and  deg(r_l) < deg(r) . It follows that:

 deg(r_{i+1}) = max(deg(r_l), deg(\frac{lt(r)}{lt(v)} v_l)) < deg(r)

So the degree of  r reduces after each step.

That resolves the most complicated case. Now lets take a look at the others: first suppose that  r_i - \frac{lt(r_i)}{lt(v)} v = 0. Since  r_{i+1} = r_i - \frac{lt(r_i)}{lt(v)} v = 0 so statement 3 is true and we are done.

If either  r_i = 0 or  \frac{lt(r_i)}{lt(v)} v = 0

Leave a Reply

Your email address will not be published. Required fields are marked *