Determine the number of irreducible polynomials of degrees 2, 3, and 6 over a prime field.

Question

Determine the number of irreducible polynomials of degrees 2, 3, and 6 over the prime field $\mathbb F_p$.

My question is related to the answer posted for the above question. I was scratching my head to understand how you come up to f(2)=g(2)−g(1)−(g(1)2) polynomial degree 2 and that of degree 3. Any help with that is appreciated. Is there a general formula that we need to follow or depend up on? How could I fit Möbius function here?

Answer 1

I’m still not sure after the exchange in the comments whether I can say anything new that Hagen hasn’t already said, but I’ll give it a try.

By definition, a polynomial is reducible exactly if it is the product of two polynomials with positive degrees. A polynomial of degree $2$ can only be the product of two polynomials with positive degrees by being the product of two polynomials of degree $1$. These two polynomials of degree $1$ can either be the same or different. Since $g(1)$ counts the polynomials of degree $1$, it also counts the ways to get a polynomial of degree $2$ by multiplying a polynomial of degree $1$ by itself (i.e. squaring it). For the case of two different polynomials, we need to count the pairs of different polynomials of degree $1$, since we get the same polynomial of degree $2$ no matter in which order we multiply the two polynomials of degree $1$. There are $\binom{g(1)}2$ such pairs of polynomials of degree $1$.

Thus, there are $g(1)$ polynomials of degree $2$ that are reducible because they are the square of a polynomial of degree $1$, and $\binom{g(1)}2$ polynomials of degree $2$ that are reducible because they are the product of a pair of polynomials of degree $1$. This exhausts all ways in which a polynomial of degree $2$ can be reducible, so if we subtract these two counts from the count $g(2)$ of all polynomials of degree $2$, we get the count of irreducible polynomials of degree $2$: $g(2)-g(1)-\binom{g(1)}2$. Further up, Hagen had shown that $g(n)=p^n$, since each of $n$ coefficients can be chosen independently from $p$ values. Thus $g(2)-g(1)-\binom{g(1)}2=p^2-p-\frac{p(p-1)}2=\frac{p(p-1)}2$.

I’ve tried my best to make every step of the argument explicit. If it’s still not clear, please do point to a specific part of it that you need further explanation for.

Answer 2

Hagen has made a valiant (and successful) attempt to give an elementary count of the irreducibles of low degree, but I think the more abstract and structural, more-or-less standard argument based on the use of Möbius Inversion is much more instructive.

Let $N_2$ be the number of quadratic irreducibles over the prime field $\Bbb F_p$. Now consider the quadratic extension of the field $\Bbb F_p$ of $p$ elements. This quadratic field has $p^2$ elements, which fall into two classes. Each element is either in $\Bbb F_p$ already, or its minimal polynomial is quadratic, with both roots in our field. (In fact, if $\alpha$ is one root, the other is $\alpha^p$.) Thus $2N_2$ is the count of this second class of elements. That is $p^2=2N_2+p$. In other words, $N_2=\frac{p^2-p}2$.

Same thing for $N_3=$ number of cubic irreducibles. Consider the (unique!) cubic extension of $\Bbb F_p$, with $p^3$ elements. Again, the elements of this field fall into two classes, either an element is in $\Bbb F_p$ already, or it generates a subfield of degree $3$, i.e. the whole thing. (Can’t generate a quadratic extension because the field extension degree is $3$, which has only the two divisors.) Again, this cubic element’s minimal polynomial is cubic (and if you started with the cubic element $\alpha$, the other roots of its minimal are $\alpha^p$ and $\alpha^{p^2}$). So once again, $p^3=3N_3+p$, and $N_3=\frac{p^3-p}3$.