Find the irreducible polynomials of degree 1, 2, and 4 over ZZ/(2)

Find all the irreducible polynomials of degree 1, 2, or 4 over \mathbb{F}_2, and verify that their product is x^{16}-x.


Note that there are 2^k (monic) polynomials of degree k, as each non-leading coefficient can be either 0 or 1.

The polynomials of degree 1, p_1(x) = x and p_2(x) = x+1, are both irreducible.

There are 4 polynomials of degree 2, one of which is irreducible.

  1. x^2 = xx is reducible
  2. x^2+1 = (x+1)^2 is reducible
  3. x^2+x = x(x+1) is reducible
  4. p_3(x) = x^2+x+1 has no roots, and so is irreducible.

Before we address the degree 4 polynomials, we prove a lemma.

Lemma 1: If p(x) is a degree 4 polynomial over \mathbb{F}_2 with constant term 1 and p factors as a product of quadratics, then the linear and cubic terms of p are equal. Proof: We have (as we assume) p(x) = (x^2+ax+b)(x^2+cx+d) = x^4 + (a+c)x^3 + (b+d+ac)x^2 + (ad+bc)x+bd. Now bd = 1, so that b = d = 1. So p(x) = x^4 + (a+c)x^3 + acx^2 + (a+c)x + 1, as desired. \square

Lemma 2: \Phi_5(x) = x^4+x^3+x^2+x+1 is irreducible over \mathbb{F}_2. Proof: Clearly this has no roots. By Lemma 1, if \Phi_5(x) factors into two quadratics, then the factors’ linear terms, a and c, satisfy a+c=ac=1, which is impossible over \mathbb{F}_2. \square

There are 16 polynomials of degree 4.

  1. x^4 = xx^3 is reducible
  2. x^4+1 = (x^2+1)^2 is reducible
  3. x^4+x = x(x^3+1) is reducible
  4. x^4+x^2 = x^2(x^2+1) is reducible
  5. x^4+x^3 = x^3(x+1) is reducible
  6. p_4(x) = x^4+x+1 clearly has no roots, and by the lemma, has no quadratic factors. So p_4 is irreducible.
  7. x^4+x^2+1 = (x^2+x+1)^2 is reducible
  8. p_5(x) = x^4+x^3+1 clearly has no roots, and by Lemma 1, has no quadratic factors. So p_5 is irreducible.
  9. x^4+x^2+x = x(x^3+x+1) is reducible
  10. x^4+x^3+x = x(x^3+x^2+1) is reducible
  11. x^4+x^3+x^2 = x^2(x^2+x+1) is reducible
  12. x^4+x^2+x+1 has 1 as a root, so is reducible
  13. x^4+x^3+x^2+1 = (x+1)(x^3+1) is reducible
  14. x^4+x^3+x^2+1 has 1 as a root, so is reducible
  15. x^4+x^3+x^2+x = x(x^3+x^2+x+1) is reducible
  16. p_6(x) = x^4+x^3+x^2+x+1 = \Phi_5(x) is irreducible

So there are six irreducible polynomials of degree 1, 2, or 4 over \mathbb{F}_2:

  1. p_1(x) = x
  2. p_2(x) = x+1
  3. p_3(x) = x^2+x+1
  4. p_4(x) = x^4+x+1
  5. p_5(x) = x^4+x^3+1
  6. p_6(x) = x^4+x^3+x^2+x+1

It is easy (if tedious) to verify that the product of these polynomials is x^{16}-x. (WolframAlpha agrees.)

Post a comment or leave a trackback: Trackback URL.

Comments

  • Julien Wu  On July 29, 2012 at 5:08 pm

    To prove the irreducible polynomials of degree 4 are indeed irreducible is not also necessary to show that they cannot be reduced to the product of a degree 3 and degree 1 polynomial?

    • nbloomf  On August 17, 2012 at 11:12 pm

      Yes; this is accomplished by noting that the polynomial has no roots (since roots correspond to linear factors).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: