Number of irreducible polynomials over a finite field

Over a finite field, there are of course only finitely many irreducible monic polynomials. But how do you count them? Let $q = p^n$ be a power of a prime and let $N_q(d)$ denote the number of monic irreducible polynomials of degree $d$ over $\F_q$. The key to finding $N_q(d)$ is the following fact: the product of all the monic, irreducible polynomials of degree $d$ with $d \mid n$ in the finite field $\mathbb{F}_q$ is the polynomial
$$x^{q^n} – x.$$
So let’s say $f_1,f_2,\dots, f_k$ are all the irreducible monic polynomials of degree $d$ with $d\mid n$. By taking degrees on both sides of the equation $x^{q^n} -x = f_1f_2\cdots f_k$, we get the formula
$$q^n = \sum_{d\mid n} dN_q(d).$$
Hey this is pretty good! For example, if $q = 2$ and $n = 3$ then the formula reads
$$8 = N_2(1) + 3N_2(3)$$
Now, $N_q(1)$ is always easy to figure out. All monic linear polynomials are irreducible so $N_q(1) = q$. Therefore, $N_2(3) = 2$. In fact, these two polynomials are: $x^3 + x + 1$ and $x^3 + x^2 + 1$. Okay, what about if $q = 3$ and $n = 6$? Then our formula tells us that
$$3^6 = N_3(1) + 2N_3(2) + 3N_3(3) + 6N_3(6).$$
So we now have to recursively compute: if we did that we would get that $N_3(1) = 1$, and this gives $2N_3(2) = 6$. Finally, $3N_3(3) = 24$. Therefore, we would calculate that $N_3(6) = 116$. It would not be too hard to write such a recursive algorithm and I encourage the reader to try it.

However, there is an easier way to compute $N_q(n)$. It involves the Moebius function. It is a function $\mu$ on the positive integers that is define as follows:
$$\mu(n) = \left\{
\begin{matrix}1 & \text{if $n=1$}\\(-1)^k & \text{if $n$ is the product of $k$ distinct primes}\\ 0 & \text{if $p^2\mid n$ for some prime $p$}\end{matrix}\right.$$
The key feature of the Moebius function is the following theorem.

Moebius Inversion Formula. Let $f$ and $g$ be functions on the natural numbers taking values in the integers. Then $f(n) = \sum_{d\mid n}g(d)$ if and only if
$$ g(n) = \sum_{d\mid n} \mu(n/d)f(d).$$

The proof of this formula is not difficult. In fact, it uses just one fact: that $\sum_{d\mid n}\mu(d)$ is actually the characterstic function of 1. Once you prove this, just plug and chug and exchange the order of summation until something good happens. Now, the usefulness behind this theorem is that the $g(n)$ is something that you don’t want to compute recursively in a formula like $\sum_{d\mid n} g(d)$ and $f$ is a much easier function to compute. In this case, if you set $f(n) = q^n$ and $g(n) = nN_q(n)$, then we get the formula:
$$N_q(n) = \frac{1}{n}\sum_{d\mid n}\mu(n/d)q^d.$$
This is way better for two reasons. First, the function $\mu(d)$ is much easier to compute. Going back to our example of $q = 3$ and $n =6$ we get:
$$N_3(6) = \frac{1}{6}\sum_{d\mid 6} \mu(6/d)3^d\\
=\frac{1}{6}[ 3\mu(6) + 9\mu(3) + 27\mu(2) + 729\mu(1)]\\
=\frac{1}{6}[3 – 9 – 27 + 729] = 116$$
Great, it’s the same as before! Second, you might have also caught onto the following: because $\mu(n) = 0$ when $n$ is divisible by the square of a prime, many terms are zero for non-squarefree divisors. For example, if $p$ is a prime then:
$$N_q(p^k) = \frac{q^{p^{k-1}}(q^{p^k – p^{k-1}} -1)}{p^k}$$
Now that’s a slightly odd formula. But rest assured, it’s an integer. Of course it is for $q$ a power of $p$. But recall that Euler’s generalisation of Fermat’s theorem is that $m\mid a^{\phi(m)} – 1$ where $\phi(m)$ is Euler’s phi-function; in particular $\phi(p^k) = p^k – p^{k-1}$. This theorem reassures us that our formula for $N_q(p^k)$ is always an integer! Derive it yourself if you don’t believe me!

Here is a slightly larger example of computing the number of monic irreducible polynomials over a finite field: $N_7(1000)$ is:


Leave a comment

Fields marked with * are required. LaTeX snippets may be entered by surrounding them with single dollar signs. Use double dollar signs for display equations.