# Number of irreducible polynomials with degree $6$ in $\mathbb{F}_2[X]$

I'm looking for the number of irreducible polynomials with degree $6$ in $\mathbb{F}_2[X]$ with leading coefficient $1$.

First question: The leading coefficient $1$ is redudant because every polynomial of degree $6$ has leading coefficient $1$?

My solution: The polynomials must be of the form

$$x^6 + \dots + 1$$

to ensure the degree of $6$ and to ensure that $0$ is not a root. Now we have

$$\dots + \alpha_5x^5+ \dots +\alpha_1x+ \dots$$

with $\alpha_i \in \mathbb{F}_2$. To avoid that $1$ is root, an odd number of $\alpha_i$ must be $1$. The number of combinations for that would be $\frac{2^{(5-1)}}{2}$ = 8. Is that correct?

-
Here is an answer to more general question mathoverflow.net/questions/101464/… –  no identity Jul 15 '12 at 18:37

To finish doing it your way - first of all, you've miscounted - there's five numbers between $\alpha_1, \ldots, \alpha_5$, so you really want $2^5/2 = 16$. But there's still some of those polynomials that aren't irreducible: the problem is that just because a degree 6 polynomial doesn't have a root doesn't make it irreducible (that's only true for degree 2 and 3 polynomials). For example, $$x^6 + x^2 + 1 = (x^3 + x + 1)^2$$ in characteristic $2$, so it's not irreducible even though it's on your list.

To figure out which ones to throw out, let's write down the possible irreducible factors of a degree 6 polynomial with no linear factors:

possible irreducible quadratic factors: $x^2 + x + 1$

possible irreducible cubic factors: $x^3 + x^2 + 1$, $x^3 + x + 1$.

possible irreducible quartic factors: $x^4 + x^3 + 1$, $x^4 + x + 1$.

In making this last list I throw out $x^4 + x^2 + 1 = (x^2 + x + 1)^2$. I know the other two are irreducible because the only way I'm going to get a reducible quartic with no linear factors is for it to be the square of the quadratic.

We can't have an irreducible quintic factor because the quotient would be linear.

So, what could go wrong? We can partition 6 as $2 + 2 + 2$, $2 + 4$, or $3 + 3$; these are the only partitions that don't use a 1. There's one way to get a degree 6 polynomial by using a quadratic three times; two ways by using a quadratic and a quartic, and four ways by using two cubics.

So we need $16 - 1 - 2 - 4 = 9$. This agrees with the answer using Möbius inversion given on Mathoverflow.

-

For variety, a different approach. Each irreducible polynomial degree 6 polynomial has 6 distinct roots $\alpha$ with the property that $\mathbf{F}_2(\alpha) = \mathbf{F}_{64}$. Furthermore, no two distinct polynomials have overlapping roots.

There are 64 elements of $\mathbf{F}_{64}$. Of those:

• 2 of them lie in $\mathbf{F}_{2}$
• 4 of them lie in $\mathbf{F}_{4}$
• 8 of them lie in $\mathbf{F}_{8}$

(these are the only proper subfields). After counting everything carefully, this leaves $54 = 6 \cdot 9$ elements that do not lie in any subfield, and thus 9 irreducible polynomials.

-