Determine all monic irreducible polynomials of degree $4$ in $\mathbb{Z_2[x]}$

Well these polynomials will be of the form -

$a_0 + a_1x + a_2x^2 + a_3x^3 + x^4$

So we have four coefficients that can each have values of either $0$ or $1$. So we have $2^4 = 16$ monic polynomials of degree $4$ in $\mathbb{Z_2[x]}$.

Now to determine the irreducible polynomicals is it necessary to write them all out and manually check if they are irreducible? Or is there some lemma I can apply here?

marked as duplicate by hardmath, user61527, tomasz, Calvin Lin, Dominic Michaelis Nov 15 '13 at 6:27

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • You'll start off with $2^3$ options, since they cannot have a zero constant term. – Pedro Tamaroff Nov 15 '13 at 0:40
  • @PedroTamaroff That is if they have a zero constant term then they are then reducible with $x$ being one of the factors, yes? – sonicboom Nov 15 '13 at 0:44
  • 1
    There is no reason to talk about "monic" polynomials over $\mathbb{Z}/2\mathbb{Z}$ – tfw cant into math Nov 15 '13 at 0:47
up vote 4 down vote accepted

You will need to exclude

  • the polynomials divisible by $X$, which are those without constant term $1$,

  • the polynomials divisible by $X+1$, which are those whose coefficients sum to $0$ (mod $2$),

  • the polynomial $(X^2+X+1)^2 = X^4 + X^2 + 1$.

  • So determining the irreducible polynomials is done by observation then, not by using some lemma? – sonicboom Nov 15 '13 at 1:01
  • So, your 2nd bullet point means that we have to exclude $x^4 + 1$. So as we have $2^3$ choices of polynomial (as we have already excluded the polys with constant term $0$), and we have excluded $x^4 + 1$ and $x^4 + x^2 +1$, then the remaining $6$ polys are the irreducible ones. Is that correct, or are there less than $6$ irreducible polys of degree $4$ in $\mathbb{Z_2[x]}$? – sonicboom Nov 15 '13 at 13:11
  • What are you basing this statement on - the polynomials divisible by $X+1$, which are those whose coefficients sum to $0$ (mod $2$)? – sonicboom Nov 15 '13 at 13:20
  • 2
    @sonicboom The coefficients sum to zero if and only if $1$ is a zero of the polynomial, which is if and only if it is divisible by $X-1 = X+1$. – tfw cant into math Nov 16 '13 at 5:40

The number of irreducible polynomials of degree $n$ over the field with $q = p^n$ elements is given by the formula $$ \frac{1}{n}\sum_{d \, \big| n} \mu \left( \frac{n}{d} \right) q^d, $$ where the sum is over divisors of $n$ and $\mu: \Bbb{Z}_{>0} \to \{ -1, 0, 1\}$ is the Möbius function given by $$ \mu(k) = \begin{cases} 1 & k = 1 \\ (-1)^m & k = p_1\cdots p_m \text{ for distinct primes } p_1, \ldots, p_m \\ 0 & \text{else.} \end{cases} $$

As far as finding the polynomials, I only know ad hoc methods.

Not the answer you're looking for? Browse other questions tagged or ask your own question.