The Universe of Discourse

My favorite math problem

Introduction

Descartes' theorem

We can repeat this process. If a₁, a₂, ... a_n are the zeroes of some nth-degree polynomial P, we can factor P as (x-a₁)(x-a₂)...(x-a_n).

The only possibly tricky thing here is that some of the a_i might be the same. x² - 2x + 1 has a zero of 1, but twice, so it factors as (x-1)(x-1). x³ - 4x² + 5x - 2 has a zero of 1, but twice, so it factors as (x-1)(x² - 3x + 2), where (x² - 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 -1

If we want to find the square roots of -1, we need to factor x² + 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² + 1. Multiplying through gives x² - (i + j)x + ij = x² + 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³ = j, but j³ = 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² + 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₂.

Z₂

+ 0 1 0 0 1 1 1 0

× 0 1 0 0 0 1 0 1

The 1+1=0 oddity is the one and only difference between Z₂ and ordinary algebra. All the other laws remain the same. To be explicit, I will list them below:

• a + 0 = a
• a + b = b + a
• (a + b) + c = a + (b + c)
• a × 0 = 0
• a × 1 = a
• a × b = b × a
• (a × b) × c = a × (b × c)
• a × (b + c) = a × c + b × c

Algebra in Z₂

Because a + a = 0, we have a = -a for all a, and this means that in Z₂, addition and subtraction are the same thing. If you don't like subtraction—and really, who does?—then Z₂ 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₂, 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)² to be equal to a² + b², then suffer no more, because in Z₂ they are equal. Here's the proof:

(a + b)2	=
(a + b)(a + b)	=
a(a + b) + b(a + b)	=
(a2 + ab) + (ba + b2)	=
a2 + ab + ab + b2	=
a2 + b2

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)² = a² + b² + ... + z². But it does not hold true for cubes; (a + b)³ is a³ + a²b + ab² + b³, not a³ + b³.

Irreducible polynomials in Z₂

There are four second-degree polynomials:

1. x²
2. x² + 1
3. x² + x
4. x² + x + 1

Polynomial	Zeroes	Factorization
x2	0 (twice)	x2
x2 + 1	1 (twice)	(x+1)2
x2 + x	0, 1	x(x+1)
x2 + x + 1	none

Note in particular that, unlike in the real numbers, x² + 1 is not irreducible in Z₂. 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² + x + 1. The other three second-degree polynomials all can be factored, but x² + x + 1 cannot.

Like the fictitious mathematicians who invented i, we will rectify this problem, by introducing into Z₂ a new number, called b, which has the property that b² + 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₂. 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:

+ 0 1 b b+1 0 0 1 b b+1 1 1 0 b+1 b b b b+1 0 1 b+1 b+1 b 1 0

× 0 1 b b+1 0 0 0 0 0 1 0 1 b b+1 b 0 b b+1 1 b+1 0 b+1 1 b

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² + b + 1 = 0, by definition, so b² = b + 1 by the addition law. Why is b × (b+1) = 1? Well, b × (b+1) = b² + 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³. Let's calculate that. b³ = b·b². b², we know, is b+1. So b³ = 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³ + 1 = 0. 1 is obviously a cube root of 1, and so Descartes' theorem says that x³ + 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³ + 1 = (x+1)³, but as I pointed out before, we don't. So it must be something else. The only candidate is x² + x + 1. Thus the other two cube roots of 1 must be zeroes of x² + x + 1.

The next question we must answer without delay is: b is one of the zeroes of x² + 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² must also be a cube root of 1:

b3	=	1
(b3)2	=	12
b6	=	1
(b2)3	=	1

So we now know the three zeroes of x³ + 1: they are 1, b, and b². Since x³ + 1 factors into (x+1)(x²+x+1), the two zeroes of x²+x+1 are b and b². As we noted before, b² = b+1.

This means that x² + x + 1 should factor into (x+b)(x+b+1). Multiplying through we get x² + bx + (b+1)x + b(b+1) = x² + x + 1, as hoped.

Actually, the fact that both b and b² are zeroes of x²+x+1 is not a coincidence. Z₂ has the delightful property that if z is a zero of any polynomial whose coefficients are all 0's and 1's, then z² 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_nxⁿ + a_n-1x^n-1 + ... + a₁x + a₀, and z is a zero of P, so that P(z) = 0. Then (P(z))² = 0 also, so (a_nzⁿ + a_n-1z^n-1 + ... + a₁z + a₀)² = 0. By the square law, we have a_n²(zⁿ)² + a_n-1²(z^n-1)² + ... + a₁²z² + a₀² = 0. Since all the a_i are either 0 or 1, we have a_i² = a_i, so a_n(zⁿ)² + a_n-1(z^n-1)² + ... + a₁z² + a₀ = 0. And finally, (z^k)² = (z²)^k, so we get a_n(z²)ⁿ + a_n-1(z²)^n-1 + ... + a₁z² + a₀ = P(z²) = 0, which is what we wanted to prove.

Now you might be worried about something: the fact that b is a zero of x² + x + 1 implies that b² is also a zero; doesn't the fact that b² is a zero imply that b⁴ is also a zero? And then also b⁸ and b¹⁶ and so forth? Then we would be in trouble, because x² + 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³ = 1, so b⁴ = b·b³ = b·1 = b, and similarly b⁸ = b², so we are getting the same two zeroes over and over.

Symmetry again

Third-degree polynomials

Polynomial				Zeroes	Factorization
x3				0, 0, 0	x3
x3			+ 1	1, b, b+1	(x+1)(x2+x+1)
x3		+ x		0, 1, 1	x(x+1)2
x3		+ x	+ 1	none
x3	+ x2			0, 0, 1	x2(x+1)
x3	+ x2		+ 1	none
x3	+ x2	+ x		0, b, b+1	x(x2+x+1)
x3	+ x2	+ x	+ 1	1, 1, 1	(x+1)3

There are two irreducible third-degree polynomials. Let's focus on x³ + x + 1, since it seems a little simpler. As before, we will introduce a new number, c, which has the property c³ + c + 1 = 0. By the addition law, this implies that c³ = c + 1. Using this, we can make a table of powers of c, which will be useful later:

c1	=		c
c2	=	c2
c3	=		c +	1
c4	=	c2 +	c
c5	=	c2 +	c +	1
c6	=	c2 +		1
c7	=			1

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⁵ = c² + c + 1, we multiply by c to get c⁶ = c³ + c² + c. But c³ = c + 1 by definition, so c⁶ = (c + 1) + c² + c = c² + 1. Once we get as far as c⁷, we find that c is a 7th root of 1. Analogous to the way b and b² were both cube roots of 1, the other 7th roots of 1 are c², c³, c⁴, c⁵, c⁶, and 1. For example, c⁵ is a 7th root of 1 because (c⁵)⁷ = c³⁵ = (c⁷)⁵ = 1⁵ = 1.

We've decided that c is a zero of x³ + x + 1. What are the other two zeroes? By theorem 1, they must be c² and (c²)² = c⁴. Wait, what about c⁸? Isn't that a zero also, by the same theorem? Oh, but c⁸ = c·c⁷ = c, so it's really the same zero again.

What about c³, c⁵, and c⁶? Those are the zeroes of the other irreducible third-degree polynomial, x³ + x² + 1. For example, (c³)³ + (c³)² + 1 = c⁹ + c⁶ + 1 = c² + (c²+1) + 1 = 0.

So when we take Z₂ and adjoin a new number that is a solution of the previously unsolvable equation x³ + 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³ + x + 1 and x³ + x² + 1 are all 7th roots of 1, this tells us that x⁷ + 1 factors as (x+1)(x³ + x + 1)(x³ + x² + 1), which might not have been obvious.

Onward

• We've seen cube roots and seventh roots of 1. Where did the fifth roots go?

  (The square theorem ensures that even-order roots are uninteresting. The fourth roots of 1, for example, are just 1, 1, 1, and 1. The sixth roots are the same as the cube roots, but repeated: 1, 1, b, b, b², and b².)

  The fifth roots, it turns out, appear later, as the four zeroes of the polynomial x⁴ + x³ + x² + x + 1. These four, and 1, are five of the 15 fifteenth roots of 1. Eight others appear as the zeroes of the other two irreducible fourth-degree polynomials, and the other two fifteenth roots are b and b². If we let d be a zero of one of the other irreducible fourth-degree polynomials, say x⁴ + x + 1, then the zeroes of this polynomial are d, d², d⁴, and d⁸, and the zeroes of the other are d⁷, d¹¹, d¹³, and d¹⁴. So we have an interesting situation. We can extend Z₂ by adjoining the zeroes of x³ + 1, to get a larger system with 4 elements instead of only 2. And we can extend Z₂ by adjoining the zeroes of x⁷ + 1, to get a larger system with 8 elements instead of only 2. But we can't do the corresponding thing with x⁵ + 1, because the fifth roots of 1 don't form a closed system. The sum of any two of the seventh roots of 1 was another seventh root of 1; for example, c³ + c⁴ = c⁶ and c + c² = c⁴. But the corresponding fact about fifth roots is false. Suppose, for example, that y⁵ = 1. We'd like for y + y² to be another fifth root of 1, but it isn't; it actually turns out that (y + y²)⁵ = b. For which n do the nth roots of 1 form a closed system?

• What do we get if we extend Z₂ with both b and c? What's bc? What's b + c? (Spoiler: b + c turns out to be zero of x⁶ + x⁵ + x³ + x² + 1, and is a 63rd root of 1, so we may as well call it f. bc = f⁴⁸.)

  The degree of a number is the degree of the simplest polynomial of which it is a zero. What's the degree of b + c? In general, if p and q have degrees d(p) and d(q), respectively, what can we say about the degrees of pq and p + q?

• Since there is an nth root of 1 for every odd n, that implies that for all odd n, there is some k such that n divides 2^k - 1. How are n and k related?

• For n = 2, 3, and 4, the polynomial xⁿ + x + 1 was irreducible. Is this true in general? (No: x⁵ + x + 1 = (x³ + x² + 1)(x² + x + 1).) When is it true? Is there a good way to find irreducible polynomials? How many irreducible polynomials are there of degree n? (The sequence starts out 0, 0, 1, 2, 3, 6, 9, 18, 30, 56, 99,...)

• The Galois theorem says that any finite field that contains Z₂ must have 2ⁿ elements, and its addition component must be isomorphic to a direct product of n copies of Z₂. Extending Z₂ with c, for example, gives us the field GF(8), obtained as the direct product of {0, 1}, {0, c}, and {0, c²}. The addition is very simple, but the multiplication, viewed in this light, is rather difficult, since it depends on knowing the secret identity c · c² = c + 1.

  Identify the element a₀ + a₁c + a₂c² with the number a₀ + 2a₁ + 4a₂, and let the addition operation be exclusive-or. What happens to the multiplication operation?

• Consider a linear-feedback shift register:

          # Arguments: N, a positive integer
          #            0 <= K <= 2**N-1
          MAXBIT = 2**N
          c = 2
          until c == 1:
            c *= 2
            if (c => MAXBIT):
              c &= ~MAXBIT
              c ^= K
            print c
  

  (Except that this function runs backward relative to the way that LFSRs usually work.)

  Does this terminate for all choices of N and K? (Yes.) For any given N, the maximum number of iterations of the until loop is 2^N - 1. For which choices of K is this maximum achieved?

• Consider irreducible sixth-degree polynomials. We should expect that adjoining a zero of one of these, say f, will expand Z₂ to contain 64 elements: 0, 1, f, f², ..., f⁶², and f⁶³ = 1. In fact, this is the case.

  But of these 62 new elements, some are familiar. Specifically, f⁹ = c, and f²¹ = b. Of the 62 powers of f, 8 are numbers we have seen before, leaving only 54 new numbers. Each irreducible 6th-degree polynomial has 6 of these 54 as its zeroes, so there are 9 such polynomials. What does this calculation look like in general?

• c¹, c², and c⁴ are zeroes of x³ + x + 1, one of the two irreducible third-degree polynomials. This means that x³ + x + 1 = (x + c¹)(x + c²)(x + c⁴). Multiplying out the right-hand side, we get: x³ + (c + c² + c⁴)x² + (c³ + c⁵ + c⁶)x + 1. Equating coefficients, we have c + c² + c⁴ = 0 and c³ + c⁵ + c⁶ = 1. c³, c⁵, and c⁶ are the zeroes of the other irreducible third-degree polynomial. Coincidence? (No.)

• The irreducible polynomials appear to come in symmetric pairs: if a_nxⁿ + a_n-1x^n-1 + ... + a₁x + a₀ is irreducible, then so is a₀xⁿ + a₁x^n-1 + ... + a_n-1x + a_n. Why?

• c¹, c², and c⁴ are the zeroes of one of the irreducible third-degree polynomials. 1, 2, and 4 are all the three-bit binary numbers that have exactly one 1 bit. c³, c⁵, and c⁶ are the zeroes the other irreducible third-degree polynomial. 3, 5, and 6 are all the three-bit binary numbers that have exactly one 0 bit. Coincidence? (No; theorem 1 is closely related here.)

  Now consider the analogous case for fourth-degree polynomials. The 4-bit numbers that have one 1 bit are 0001, 0010, 0100, and 1000 (1, 2, 4, and 8) which are all zeroes of one of the irreducible 4th-degree polynomials. The 4-bit numbers that have one 0 bit are 1110, 1101, 1011, and 0111 (7, 11, 13, and 14) which are all zeroes of another of the irreducible 4th-degree polynomials.

  The 4-bit numbers with two 1 bits and two 0 bits fall into two groups. In one group we have the numbers where similar bits are adjacent: 0011, 0110, 1100, and 1001, or 3, 6, 9, and 12. These are the zeroes of the third irreducible 4th-degree polynomial. The remaining 4-bit numbers are 0101 and 1010, which correspond to b and b².

  There is, therefore, a close relationship between the structure an extension of Z₂ and the so-called "necklace patterns" of bits, which are patterns that imagine that the bits are joined into a circle with no distinguishable starting point.

  The exceptional values (b and b²) corresponded to necklace patterns that did not possess the full n-fold symmetry. This occurs for composite values of n. But we might also expect to find exceptions at n = 11, since then 2ⁿ-1 = 2047 is composite. However, 2047 is exceptional in another way: 2047 = 23 · 89, and neither 23 nor 89 is a divisor of 2ⁿ-1 for any smaller value of n. Can we prove from this that when p is prime and 2^p-1 is not, the divisors of 2^p-1 do not divide 2^q-1 for any q < p?

• Since cⁱ are the seventh roots of 1, we have x⁷ + 1 = (x + 1)(x + c)(x + c²)...(x + c⁶). After dividing out the trivial factor of x+1, we are left with:

  x⁶ + x⁵ + ... + 1 = (x + c)(x + c²)...(x + c⁶)

  Multiplying through on the right side and equating coefficients gives:

  c + c2 + ... + c6	=	1
  cc2 + cc3 + ... + c5c6	=	1
  cc2c3 + cc2c4 + ... + c4c5c6	=	1
  ...	=	...
  cc2c3c4c5c6	=	1

  What, if anything, can one make of this?

And then, when I get tired of Z₂, I can start all over with Z₃.

[Other articles in category /math] permanent link