Tuesday, March 8, 2016

dividing polynomials: the backwards reverse tabular method

Among the Lakota people, the heyoka is a contrarian, jester, satirist or sacred clown. The heyoka speaks, moves and reacts in an opposite fashion to the people around them. - Wikipedia, Heyoka

A couple of earlier posts (this one and this one) describe how to use the grid method for dividing polynomials, and were intended to be helpful for people learning or teaching the topic. The current post shows some surprising things that happen when you mess around with the standard division algorithm, and is probably not quite as helpful. Specifically, if you divide in a "backwards" fashion, things can blow up spectacularly. If you are intrigued by the possibility of polynomial explosions, read on; for others: you've been warned.

When you divide single-variable polynomials g, the standard (euclidean) algorithm requires f to have a higher degree than g, and when you start dividing you take the term of the highest power of g and see what you should multiply that by to get the term with the highest power in f. This tells you the first term of your quotient q. In the example below, we look at the 3x term and ask how many times does it go into the 9x^3 term - the answer is 3x^2, which is the first term of our answer.

The rest of this example can be found in a more helpful post. The method illustrated above is sometimes called the "reverse tabular" method ("reverse" because using a table in the normal fashion of filling in the interior given the top row and left column is used for multiplying polynomials).

The standard approach of starting with the highest degree terms ensures that if you end up with a remainder, its degree will be less than the degree of the divisor, but also means that you can only divide when the degree of the divisor is less than the dividend. In the above example, 3x-2 is degree 1, which is less than the dividend which has degree 3; for this division problem it turns out that you will get a degree 0 remainder (remainder is 5).

But what if you did it backwards? Instead of starting with the highest degree terms in each polynomial, pick each one up by the tail and start with the smallest degree terms?  Flipping the polynomials around so they are backwards while using a grid makes it reasonable to call this the "backwards reverse tabular method."

The simple case - divisor is a factor

If you are in one of those lovely situations where the dividend is higher degree than the divisor, and there is no remainder (the divisor is a factor of the dividend), you will get the same answer as using the standard algorithm, but your table will look predictably different (the steps for the forwards direction are shown here).

Starting with the lowest term means that the table is filled in backwards, but otherwise nothing changes, you still get the same answer. This is not what happens in the case where standard division would give you a remainder.

The remainder case

In the standard "forwards" method, you work your way down and the terms that you are trying to clean up are of lesser and lesser degree. Anything leftover at the end (the remainder) will then necessarily be of lower degree than the highest term of the divisor.

However, following the backwards method, the terms you are trying to eliminate get bigger and bigger, and will just keep going if you can't tidy them up. Here's a division problem with a remainder, first forwards:

And now the same problem, backwards:

You'll find that you have to keep adding columns to your grid to keep up with the new terms that keep getting generated, so instead of a polynomial with a rational expression as a remainder we get...  an infinite series. This seems odd: how is that thing on the right hand side equal to the left hand side? Is the equality only true when the right hand side converges? All these worries go away if we treat these as formal power series.

Why would we ever divide polynomials this way?

Dividing the indivisible

Although this is giving us some alarming results, following the backwards method allows us to do something where the standard algorithm won't allow us to do anything. If the degree of the divisor is bigger than the degree of the dividend, the standard algorithm tells us to stop right away: nothing can be done. However, armed with our new backwards method we can start dividing (and, as we saw above, we might never stop).

Let's try an example where the numerator is just 1. In the first step below, we fill in what we want as our product, namely 1. However, to get this, we need to fill in a 1 on the top row (step 2), and multiplying this by the whole left column gives us extra terms that we now need to get rid of. In step 3, we see that we will need an x in the top row to eliminate the x that we introduced in the previous step.

And you will have to keep adding more columns to fill in new terms to eliminate the terms that you introduced in the previous two steps.

Those coefficients seem to be multiplying like rabbits. No kidding: it's the Fibonacci sequence. So, we can say that the expression on the left produces the sequence of coefficients on the right, and the rational expression on the left is called the generating function for the sequence of coefficients of the resulting power series.

Here's another neat one, in the same vein:

In this case the coefficients of the resulting power series are the triangular numbers. But there is something cool about the divisor as well: the divisor's coefficients are from the third row of Pascal's triangle (with alternating signs), and the triangular numbers are from the third column.

If you try this with the fourth row of Pascal's triangle, you'll find you get a power series whose coefficients are the fourth column (the tetrahedral numbers).

Most of the time, you'll want to divide polynomials in the usual way, and get the usual answers; sometimes you can learn a bit by doing things backwards.