A method to count the number of monic irreducible polynomials of degree 2 or 3 or 4 in $\mathbb F_{p}[x]$

Question

$p$ is a prime number. I use the method as following to find out the number of monic irreducible polynomials of degree 2.

Count the number of monic not irreducible polynomials of degree 2:

If a monic polynomial $f(x)\in \mathbb F_{p}$ is of degree 2 and not irreducible, $f(x)=(x-\alpha)g(x)$ for some $g(x) \in \mathbb F_{p}$.

As $deg(g)=2-deg(x-\alpha)=2-1=1$.So $g=x-\beta$ for some $\beta \in \mathbb F$.

Thus all the not irreducible monic polynomial of degree $2$ is of the form $f(x)=(x-\alpha)(x-\beta)$.

If $\alpha =\beta$ $f(x)=(x-\alpha)^2$. We have $p$ polynomials $f(x)$ in this form.

If $\alpha \neq \beta$ , we have ${p \choose 2}=\frac{p!}{2!(p-2)!}=\frac{p(p-1)}{2}$ polynomials $f(x)$ in this form.

Hence, the total number of monic not irreducible polynomials of degree $2$ in $\mathbb F_{p}[x]$ is $p+\frac{p(p-1)}{2}=\frac{p(p+1)}{2}$

Monic polynomial of degree $2$ in $\mathbb F_{p}[x]$ has the form $x^2+ax+b$ with $a,b \in\mathbb F_{p}[x]$. Thus we have $p^2$ such polymials.

Thus the number of irreducible polynomial of degree $2$ in $\mathbb F_{p}[x]$ is $p^2-\frac{p(p+1)}{2}=\frac{p^2-p}{2}$

But when I turn to find out the number of monic irreducible polynomials of degree 3.

I find that all the not irreducible monic polynomial of degree $2$ is of the form $f(x)=(x-\alpha)(x^2+cx+d)$,so it seems that we have $p$ choices of $\alpha$, $p$ choices of $c$ and $p$ choices of $d$, thus we have $p^3$ not irreducible polynomials of degree $3$ in $ \mathbb F_{p}$.

But monic polynomial of degree $3$ in $\mathbb F_{p}[x]$ has the form $x^3+a_{1}x^2+a_{2}x+a_{3}$ with $a_{1},a_{2},a_{3} \in\mathbb F_{p}[x]$. Thus we have $p^3$ such monoc polymials.

So I think my counting when I try degree 3 is wrong.

I use the method as following to find out the number of monic irreducible polynomials of degree 4.

By using counting argument I have found that the number of irreducible polynomial of degree $2$ in $\mathbb F_{p}[x]$ is $p^2-\frac{p(p+1)}{2}=\frac{p^2-p}{2}$.

And we have $p^3-\frac{2p^3+p}{3}=\frac{p^3-p}{3}$ monic irreducible polynomials of degree $3$.

EDIT: Now I am doing the case of degree 4, could someone please have a look to my counting to see if it is correct? Thanks so much!

Monic polynomials of degree $4$ is of the form $x^4+a_{1}x^3+a_{2}x^2+a_{3}x+a_{4}$

where$a_{1},a_{2},a_{3},a_{4}$. Thus we have $p^4$ of them.

Let $f(x)$ be a not irreducible monic polynomials of degree $4$, then there are several possible form of $f(x)$

(i):$f(x)=(x-\alpha)(x-\beta)(x-\gamma)(x-\delta)$ with $\alpha,\beta,\gamma,\delta \in \mathbb F_{p}$.

(ii):$f(x)=(x-\alpha)(x-\beta)(x^2+ax+b)$ with $\alpha,\beta,a,b \in \mathbb F_{p}$ and $(x^2+ax+b)$ is a irreducible polynomial of degree $2$.

(iii)$f(x)=(x^2+ax+b)(x^2+cx+d)$ with $a,b,c,d \in \mathbb F_{p}$ and $(x^2+ax+b), (x^2+cx+d)$ are irreducible polynomials of degree $2$.

(iv)$f(x)=(x-\alpha)(x^3+ax^2+bx+c)$ with $\alpha,a,b,c \in \mathbb F_{p}$ and $(x^3+ax^2+bx+c)$ is a irreducible polynomial of degree $3$. We have $p+3{p \choose 2}+3{p \choose 3}+{p \choose 4}$ monic reducible polynomials of degree $4$ of form (i). $(p+{p \choose 2})\frac{p^2-p}{2}$ monic reducible polynomials of degree $4$ of form (ii). $\frac{p^2-p}{2}+{\frac{p^2-p}{2} \choose 2}$ monic reducible polynomials of degree $4$ of form (iii). and $p(\frac{p^3-p}{3})$ monic reducible polynomials of degree $4$ of form (iv).

But the wolfram alpha does not give me the desire number of number of irreducible polynomials of degree 4. So I guess something is wrong.

Could someone help me to find out what is wrong here and show the correct way? Thanks in advance!

Answer 1

Over $\mathbb{F}_p$, the product of all monic irreducible polynomials with degree $1$ or $2$ is given by $x^{p^2}-x$, the product of all monic irreducible polynomials with degree $1$ or $3$ is given by $x^{p^3}-x$ and the product of all monic irreducible polynomials with degree $1$ is given by $x^{p}-x$. It follows that there are $$\frac{p^2-p}{2}\text{ monic irreducible polynomials with degree } 2$$ and $$\frac{p^3-p}{3}\text{ monic irreducible polynomials with degree } 3.$$ This happens because a monic irreducible polynomial $q(x)$ with degree $d$ defines a finite field $\mathbb{F}_{p^d}\simeq\mathbb{F}_p[x]/(q(x))$ over which $\alpha\to\alpha^p$ is a field homomorphism (Frobenius' homomorphism).

As an alternative, a monic polynomial is irreducible over $\mathbb{F}_p$ iff it has no roots in $\mathbb{F}_p$. Reducible monic polynomials have the form $(x-a) q(x)$ (with $q(x)$ being a monic, irreducible, second-degree polynomial) or $(x-a_1)(x-a_2)(x-a_3)$. There are $p\cdot\frac{p^2-p}{2}$ polynomials in the first case and $p+p(p-1)+\binom{p}{3}$ polynomials in the second case (accounting for $1$, $2$ or $3$ distinct roots in the field). The conclusion is the same as before.

A monic, reducible polynomial with degree $4$ can completely split in linear factors (there are $p+p(p-1)+\binom{p}{2}+\binom{p}{2}(p-2)+\binom{p}{4}$ polynomials with such a property, associated with $a_1^4,a_1^3 a_2,a_1^2 a_2^2, a_1 a_2 a_3^2, a_1 a_2 a_3 a_4$), or split as the product of two quadratic irreducible polynomials (there are $\binom{(p^2-p)/2}{2}+(p^2-p)/2$ cases), or split as the product of a quadratic factor and two linear factors (there are $\frac{p^2-p}{2}\left(p+\binom{p}{2}\right)$ cases), or split as the product of a cubic factor and a linear factor (there are $p\cdot\frac{p^3-p}{3}$ cases). It follows that the number of irreducible, monic polynomials with degree $4$ is $\frac{p^4-p^2+1}{4}$.

A useful generalization of the previous approach is:

Over $\mathbb{F}_p$, there are $$ \frac{1}{k}\sum_{d\mid k} \mu\left(d\right)p^{k/d} $$ monic irreducible polynomials with degree $k$, with $\mu$ being Moebius' function.

Answer 2

There is an other counting argument for the degree 2 using some basic Number theory. Let $f(x)=x^2+bx+c$ be a monic polynomial in $\mathbb{F}_p[x]$. There is a simple criterion which says that $f(x)$ is reducible mod p iff the discriminant $\Delta = b^2-4c = 0 ~mod ~p$. Now we count the number of possibilities for this to occur. Let us choose any $b$ (there are $p$ choices)

$$b^2-4c = 0 ~mod ~p \Leftrightarrow \left( \frac{4c}{p}\right)=1\Leftrightarrow \left( \frac{c}{p}\right)=1.$$ where $\displaystyle \left( \frac{.}{p}\right)$ is the Legendre Symbol modulo $p$ we use the fact that it is a morphism and that $4=2^2$ is clearly a residue. It is not difficult to see that there are $\displaystyle \frac{(p+1)}{2}$ residues mod $p$ thus there are $(p+1)/2$ of possibilities for $c$. Thus the total number of choices for $b$ and $c$ is given by $$\displaystyle \frac{p(p+1)}{2}$$ which represents as we have seen the number of monic reducible polynomial of degree 2 in $\mathbb{F}_p[x]$. The total number of monic polynomial of degree 2 in $\mathbb{F}_p[x]$ is $p^2$ then the required number is $$N_{irr} = p^2-\frac{p(p+1)}{2} = \frac{(p^2-p)}{2}. $$