Archive:
Subtopics:
Comments disabled |
Sat, 27 May 2006 IntroductionAccording to legend, the imaginary unit i = √-1 was invented by mathematicians because the equation x^{2} + 1 = 0 had no solution. So they introduced a new number i, defined so that i^{2} + 1 = 0, and investigated the consequences. Like most legends, this one has very little to do with the real history of the thing it purports to describe. But let's pretend that it's true for a while.
Descartes' theoremIf P(x) is some polynomial, and z is some number such that P(z) = 0, then we say that z is a zero of P or a root of P. Descartes' theorem (yes, that Descartes) says that if z is a zero of P, then P can be factored into P = (x-z)P', where P' is a polynomial of lower degree, and has all the same roots as P, except without z. For example, consider P = x^{3} - 6x^{2} + 11x - 6. One of the zeroes of P is 1, so Descartes theorem says that we can write P in the form (x-1)P' for some second-degree polynomial P', and if there are any other zeroes of P, they will also be zeroes of P'. And in fact we can; x^{3} - 6x^{2} + 11x - 6 = (x-1)(x^{2} - 5x + 6). The other zeroes of the original polynomial P are 2 and 3, and both of these (but not 1) are also zeroes of x^{2} - 5x + 6.We can repeat this process. If a_{1}, a_{2}, ... a_{n} are the zeroes of some nth-degree polynomial P, we can factor P as (x-a_{1})(x-a_{2})...(x-a_{n}). The only possibly tricky thing here is that some of the a_{i} might be the same. x^{2} - 2x + 1 has a zero of 1, but twice, so it factors as (x-1)(x-1). x^{3} - 4x^{2} + 5x - 2 has a zero of 1, but twice, so it factors as (x-1)(x^{2} - 3x + 2), where (x^{2} - 3x + 2) also has a zero of 1, but this time only once. Descartes' theorem has a number of important corollaries: an nth-degree polynomial has no more than n zeroes. A polynomial that has a zero can be factored. When coupled with the so-called fundamental theorem of algebra, which says that every polynomial has a zero over the complex numbers, it implies that every nth-degree polynomial can be factored into a product of n factors of the form (x-z) where z is complex, or into a product of first- and second-degree polynomials with real coefficients.
The square roots of -1Suppose we want to know what the square roots of 1 are. We want numbers x such that x^{2} = 1, or, equivalently, such that x^{2} - 1 = 0. x^{2} - 1 factors into (x-1)(x+1), so the zeroes are ±1, and these are the square roots of 1. On the other hand, if we want the square roots of 0, we need the solutions of x^{2} = 0, and the corresponding calculation calls for us to factor x^{2}, which is just (x-0)(x-0), So 0 has the same square root twice; it is the only number without two distinct square roots.If we want to find the square roots of -1, we need to factor x^{2} + 1. There are no real numbers that do this, so we call the polynomial irreducible. Instead, we make up some square roots for it, which we will call i and j. We want (x - i)(x - j) = x^{2} + 1. Multiplying through gives x^{2} - (i + j)x + ij = x^{2} + 1. So we have some additional relationships between i and j: ij = 1, and i + j = 0. Because i + j = 0, we always dispense with j and just call it -i. But it's essential to realize that neither one is more important than the other. The two square roots are identical twins, different individuals that are completely indistinguishable from each other. Our choice about which one was primary was completely arbitrary. That doesn't even do justice to the arbitrariness of the choice: i and j are so indistinguishable that we still don't know which one got the primary notation. Every property enjoyed by i is also enjoyed by j. i^{3} = j, but j^{3} = i. e^{iπ} = -1, but so too e^{jπ} = -1. And so on. In fact, I once saw the branch of mathematics known as Galois theory described as being essentially the observation that i and -i were indistinguishable, plus the observation that there are no other indistinguishable pairs of complex numbers. Anyway, all this is to set up the main point of the article, which is to describe my favorite math problem of all time. I call it the "train problem" because I work on it every time I'm stuck on a long train trip. We are going to investigate irreducible polynomials; that is, polynomials that do not factor into products of simpler polynomials. Descartes' theorem implies that irreducible polynomials are zeroless, so we are going to start by looking for polynomials without zeroes. But we are not going to do it in the usual world of the real numbers. The answer in that world is simple: x^{2} + 1 is irreducible, and once you make up a zero for this polynomial and insert it into the universe, you are done; the fundamental theorem of algebra guarantees that there are no more irreducible polynomials. So instead of the reals, we're going to do this in a system known as Z_{2}.
Z_{2}Z_{2} is much simpler than the real numbers. Instead of lots and lots of numbers, Z_{2} has only two. (Hence the name: The 2 means 2 and the Z means "numbers". Z is short for Zahlen, which is German.) Z_{2} has only 0 and 1. Addition and multiplication are as you expect, except that instead of 1 + 1 = 2, we have 1 + 1 = 0.
The 1+1=0 oddity is the one and only difference between Z_{2} and ordinary algebra. All the other laws remain the same. To be explicit, I will list them below:
Algebra in Z_{2}But the 1+1=0 oddity does have some consequences. For example, a + a = a·(1 + 1) = a·0 = 0 for all a. This will continue to be true for all a, even if we extend Z_{2} to include more elements than just 0 and 1, just as x + x = 2x is true not only in the real numbers but also in their extension, the complex numbers.Because a + a = 0, we have a = -a for all a, and this means that in Z_{2}, addition and subtraction are the same thing. If you don't like subtraction—and really, who does?—then Z_{2} is the place for you. As a consequence of this, there are some convenient algebraic manipulations. For example, suppose we have a + b = c and we want to solve for a. Normally, we would subtract b from both sides. But in Z_{2}, we can add b to both sides, getting a + b + b = c + b. Then the b + b on the left cancels (because b + b = 0) leaving a = c + b. From now on, I'll call this the addition law. If you suffered in high school algebra because you wanted (a + b)^{2} to be equal to a^{2} + b^{2}, then suffer no more, because in Z_{2} they are equal. Here's the proof:
Because the ab + ab cancels in the last step. This happy fact, which I'll call the square law, also holds true for sums of more than two terms: (a + b + ... + z)^{2} = a^{2} + b^{2} + ... + z^{2}. But it does not hold true for cubes; (a + b)^{3} is a^{3} + a^{2}b + ab^{2} + b^{3}, not a^{3} + b^{3}.
Irreducible polynomials in Z_{2}Now let's try to find a polynomial that is irreducible in Z_{2}. The first degree polynomials are x and x+1, and both of these have zeroes: 0 and 1, respectively.There are four second-degree polynomials:
Note in particular that, unlike in the real numbers, x^{2} + 1 is not irreducible in Z_{2}. 1 is a zero of this polynomial, which, because of the square law, factors as (x+1)(x+1). But we have found an irreducible polynomial, x^{2} + x + 1. The other three second-degree polynomials all can be factored, but x^{2} + x + 1 cannot. Like the fictitious mathematicians who invented i, we will rectify this problem, by introducing into Z_{2} a new number, called b, which has the property that b^{2} + b + 1 = 0. What are the consequences of this? The first thing to notice is that we haven't added only one new number to Z_{2}. When we add i to the real numbers, we also get a lot of other stuff like i+1 and 3i-17 coming along for the ride. Here we can't add just b. We must also add b+1. The next thing we need to do is figure out how to add and multiply with b. The addition and multiplication tables are extended as follows:
The only items here that might require explanation are the entries in the lower-right-hand corner of the multiplication table. Why is b×b = b+1? Well, b^{2} + b + 1 = 0, by definition, so b^{2} = b + 1 by the addition law. Why is b × (b+1) = 1? Well, b × (b+1) = b^{2} + b = (b + 1) + b = 1 because the two b's cancel. Perhaps you can work out (b+1) × (b+1) for yourself. From here there are a number of different things we could investigate. But what I think is most crucial is to discover the value of b^{3}. Let's calculate that. b^{3} = b·b^{2}. b^{2}, we know, is b+1. So b^{3} = b(b+1) = 1. Thus b is a cube root of 1. People with some experience with this sort of study will not be surprised by this. The cube roots of 1 are precisely the zeroes of the polynomial x^{3} + 1 = 0. 1 is obviously a cube root of 1, and so Descartes' theorem says that x^{3} + 1 must factor into (x+1)P, where P is some second-degree polynomial whose zeroes are the other two cube roots. P can't be divisible by x, because 0 is not a cube root of 1, so it must be either (x+1)(x+1), or something else. If it were the former, then we would have x^{3} + 1 = (x+1)^{3}, but as I pointed out before, we don't. So it must be something else. The only candidate is x^{2} + x + 1. Thus the other two cube roots of 1 must be zeroes of x^{2} + x + 1. The next question we must answer without delay is: b is one of the zeroes of x^{2} + x + 1; what is the other? There is really only one possibility: it must be b+1, because that is the only other number we have. But another way to see this is to observe that if p is a cube root of 1, then p^{2} must also be a cube root of 1:
So we now know the three zeroes of x^{3} + 1: they are 1, b, and b^{2}. Since x^{3} + 1 factors into (x+1)(x^{2}+x+1), the two zeroes of x^{2}+x+1 are b and b^{2}. As we noted before, b^{2} = b+1. This means that x^{2} + x + 1 should factor into (x+b)(x+b+1). Multiplying through we get x^{2} + bx + (b+1)x + b(b+1) = x^{2} + x + 1, as hoped. Actually, the fact that both b and b^{2} are zeroes of x^{2}+x+1 is not a coincidence. Z_{2} has the delightful property that if z is a zero of any polynomial whose coefficients are all 0's and 1's, then z^{2} is also a zero of that polynomial. I'll call this Theorem 1. Theorem 1 is not hard to prove; it follows from the square law. Feel free to skip the demonstration which follows in the rest of the paragraph. Suppose the polynomial is P(x) = a_{n}x^{n} + a_{n-1}x^{n-1} + ... + a_{1}x + a_{0}, and z is a zero of P, so that P(z) = 0. Then (P(z))^{2} = 0 also, so (a_{n}z^{n} + a_{n-1}z^{n-1} + ... + a_{1}z + a_{0})^{2} = 0. By the square law, we have a_{n}^{2}(z^{n})^{2} + a_{n-1}^{2}(z^{n-1})^{2} + ... + a_{1}^{2}z^{2} + a_{0}^{2} = 0. Since all the a_{i} are either 0 or 1, we have a_{i}^{2} = a_{i}, so a_{n}(z^{n})^{2} + a_{n-1}(z^{n-1})^{2} + ... + a_{1}z^{2} + a_{0} = 0. And finally, (z^{k})^{2} = (z^{2})^{k}, so we get a_{n}(z^{2})^{n} + a_{n-1}(z^{2})^{n-1} + ... + a_{1}z^{2} + a_{0} = P(z^{2}) = 0, which is what we wanted to prove. Now you might be worried about something: the fact that b is a zero of x^{2} + x + 1 implies that b^{2} is also a zero; doesn't the fact that b^{2} is a zero imply that b^{4} is also a zero? And then also b^{8} and b^{16} and so forth? Then we would be in trouble, because x^{2} + x + 1 is a second-degree polynomial, and, by Descartes' theorem, cannot have more than two zeroes. But no, there is no problem, because b^{3} = 1, so b^{4} = b·b^{3} = b·1 = b, and similarly b^{8} = b^{2}, so we are getting the same two zeroes over and over.
Symmetry againJust as i and -i are completely indistinguishable from the point of view of the real numbers, so too are b and b+1 indistinguishable from the point of view of Z_{2}. One of them has been given a simpler notation than the other, but there is no way to tell which one we gave the simpler notation to! The one and only defining property of b is that b^{2} + b + 1 = 0; since b+1 also shares this property, it also shares every other property of b. b and b+1 are both cube roots of 1. Each, added to the other gives 1; each, added to 1 gives the other. Each, when multiplied by itself gives the other; each when multiplied by the other gives 1.
Third-degree polynomialsWe have pretty much exhausted the interesting properties of b and its identical twin b^{2}, so let's move on to irreducible third-degree polynomials. If a third-degree polynomial is reducible, then it is either a product of three linear factors, or of a linear factor and an irreducible second-degree polynomial. If the former, it must be one of the four products x^{3}, x^{2}(x+1), x(x+1)^{2}, or (x+1)^{3}. If the latter, it must be one of x(x^{2}+x+1) or (x+1)(x^{2}+x+1). This makes 6 reducible polynomials. Since there are 8 third-degree polynomials in all, the other two must be irreducible:
There are two irreducible third-degree polynomials. Let's focus on x^{3} + x + 1, since it seems a little simpler. As before, we will introduce a new number, c, which has the property c^{3} + c + 1 = 0. By the addition law, this implies that c^{3} = c + 1. Using this, we can make a table of powers of c, which will be useful later:
To calculate the entries in this table, just multiply each line by c to get the line below. For example, once we know that c^{5} = c^{2} + c + 1, we multiply by c to get c^{6} = c^{3} + c^{2} + c. But c^{3} = c + 1 by definition, so c^{6} = (c + 1) + c^{2} + c = c^{2} + 1. Once we get as far as c^{7}, we find that c is a 7th root of 1. Analogous to the way b and b^{2} were both cube roots of 1, the other 7th roots of 1 are c^{2}, c^{3}, c^{4}, c^{5}, c^{6}, and 1. For example, c^{5} is a 7th root of 1 because (c^{5})^{7} = c^{35} = (c^{7})^{5} = 1^{5} = 1. We've decided that c is a zero of x^{3} + x + 1. What are the other two zeroes? By theorem 1, they must be c^{2} and (c^{2})^{2} = c^{4}. Wait, what about c^{8}? Isn't that a zero also, by the same theorem? Oh, but c^{8} = c·c^{7} = c, so it's really the same zero again. What about c^{3}, c^{5}, and c^{6}? Those are the zeroes of the other irreducible third-degree polynomial, x^{3} + x^{2} + 1. For example, (c^{3})^{3} + (c^{3})^{2} + 1 = c^{9} + c^{6} + 1 = c^{2} + (c^{2}+1) + 1 = 0. So when we take Z_{2} and adjoin a new number that is a solution of the previously unsolvable equation x^{3} + x + 1 = 0, we're actually forced to add six new numbers; the resulting system has 8, and includes three different solutions to both irreducible third-degree polynomials, and a full complement of 7th roots of 1. Since the zeroes of x^{3} + x + 1 and x^{3} + x^{2} + 1 are all 7th roots of 1, this tells us that x^{7} + 1 factors as (x+1)(x^{3} + x + 1)(x^{3} + x^{2} + 1), which might not have been obvious.
OnwardI said this was my favorite math problem, but I didn't say what the question was. But by this time we have dozens of questions. For example:
And then, when I get tired of Z_{2}, I can start all over with Z_{3}.
[Other articles in category /math] permanent link |