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

$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!

• Note that some cubic polynomials can be written in the form $(x - \alpha)(x^2 + c x + d)$ in more than one way, e.g., $x (x^2 - 1) = (x - 1)(x^2 + x)$. Mar 8, 2017 at 0:47
• @Travis Oh, I see. But could you please show me how to avoid overcounting? Any hint will be appreciate.
– Y.X.
Mar 8, 2017 at 0:50
• Sure: Suppose the cubic is totally factored: Either it is a product of three linear terms, a product of a linear term and an irreducible quadratic, or irreducible. You can count the first two cases separately, since you in particular know the number of irreducible quadratics from your previous step. Mar 8, 2017 at 0:53

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.

• I know that you are correct. But I am asking this method in particular. Could you please tell me how to do the counting?
– Y.X.
Mar 8, 2017 at 0:52
• A polynomial with degree $p^3-p$ is the product of all monic irreducible polynomials with degree $3$. By considering the degrees of the involved polynomials, it is trivial that there are $\frac{p^3-p}{3}$ monic irreducible polynomials with degree $3$, why do you need a more convoluted argument? Mar 8, 2017 at 0:54
• @Y.X.: anyway, I have added a combinatorial approach. Mar 8, 2017 at 2:35
• Thanks so much. But could you please have a look on the counting argument of degree 4? I am new to field theory and cannot understand your original method so far. So could you please point out if there is something wrong with my counting in the edited question?
– Y.X.
Mar 8, 2017 at 10:41
• @Y.X.: it is not fair to keep modifying the original question by adding further requests. I am going to include the case $d=4$ in my answer, but for the future, please ask separate questions and avoid chamaleon questions. Mar 8, 2017 at 13:55

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}.$$