# Number of irreducible polynomials over a finite field

Warning to PROMYS students: this blog post contains major spoilers regarding problems 4 and 6 of the Open Door Problem Set. Read at your own risk.

The following problem has appeared as problem P3 on the short exam #2 during PROMYS Europe 2016:

Let $p,n\in\mathbb N$ with $p$ prime. How many irreducible polynomials of degree $n$ are there in $\mathbb Z_p[x]$?

In part upon request of one of my friends, below I am typing up, verbatim (apart from minor typos), a solution which I have written down during the exam, between the following two horizontal lines. Below I am adding further explanations and comments, for anyone interested.

Let $c(n)$ be the number of irreducible polynomials in $\mathbb F_p[x]$ of degree $n$. I’ll show $\displaystyle p^n=\sum_{d\mid n}dc(d)$, so, by Möbius inversion, $\displaystyle nc(n)=\sum_{d\mid n}p^d\mu\left(\frac{n}{d}\right),c(n)=\frac{1}{n}\sum_{d\mid n}p^d\mu\left(\frac{n}{d}\right)$.

Let $\overline{\mathbb F_p}$ be the algebraic closure of $\mathbb F_p$ and let $\mathbb F_{p^n}$ be the set of roots of $x^{p^n}-x$ in $\overline{\mathbb F_p}$. Since $\left(x^{p^n}-x\right)'=-1$, all the roots are distinct. Using $(a+b)^p=a^p+b^p$ and, by induction, $(a+b)^{p^n}=a^{p^n}+b^{p^n}$, we see $\mathbb F_{p^n}$ is closed under addition, multiplication, nonzero inverses and contains $0,1$, so is a field. Indeed, this is the unique subfield of $\overline{\mathbb F_p}$ of size $p^n$: if $F$ was another such field, we see all its nonzero elements satisfy $x^{p^n-1}-1=0$, so all the elements satisfy $x^{p^n}-x=0$, thus $F\subseteq\mathbb F_{p^n}$, hence, by considering size, $F=\mathbb F_{p^n}$. Last but not least, $\mathbb F_{p^m}\subseteq\mathbb F_{p^n}$ iff $m\mid n$: indeed, any solution of $x^{p^m}=x$ also solves $x^{p^{mk}}=\left(\dots\left(x^{p^m}\right)^{p^m}\dots\right)^{p^m}=x$, for all $k\in\mathbb N$, so $\mathbb F_{p^m}\subseteq\mathbb F_{p^{mk}}$, and if $\mathbb F_{p^m}\subseteq\mathbb F_{p^n}$, then $\mathbb F_{p^n}$ is a finite-dimensional vector space over $\mathbb F_{p^m}$, so $|\mathbb F_{p^n}|=|\mathbb F_{p^m}|^k$ for some $k\in\mathbb N$, i.e. $n=mk$.

Finally, let $f\in\mathbb F_p[x]$ be irreducible of degree $d$. Any of its roots generates an extension of $\mathbb F_p$ of degree $d$, i.e. $\mathbb F_{p^d}$. In particular, all roots of $f$ lie in $\mathbb F_{p^d}$. As a lemma below I show $f$ has no multiple roots, so roots of $f$ are distinct roots of $x^{p^d}-x$, so $f\mid x^{p^d}-x$. Thus, for any $d\mid n$, $f\mid x^{p^n}-x$. Conversely, if $f\mid x^{p^n}-x$, its roots generate a subfield of $\mathbb F_{p^n}$ of size $p^d$, so $\mathbb F_{p^d}\subseteq\mathbb F_{p^n},d\mid n$. Thus, since $x^{p^n}-x$ is squarefree, we get that $x^{p^n}-x$ is precisely the product of monic irreducible polynomials of degrees dividing $n$. Comparing degrees, $p^n=\displaystyle\sum_{d\mid n}dc(d),c(n)=\frac{1}{n}\sum_{d\mid n}p^d\mu\left(\frac{n}{d}\right)$.

Lemma: $f\in\mathbb F_p[x]$ irreducible $\Rightarrow$ $f$ has no multiple roots.
Proof: Otherwise, $\gcd(f,f')\neq 1$. But $f$ is irreducible, so $f\mid f'$, hence $f'=0$. Thus all powers of $x$ with nonzero coefficient in $f$ have exponent divisible by $p$, say $f(x)=\displaystyle\sum_{k=0}^na_kx^{pk}$. But then $f(x)=\displaystyle\left(\sum_{k=0}^na_kx^k\right)^p$, contradicting irreducibility. $\square$

First, a remark – the above solution actually establishes the number of monic irreducible polynomials of given degree. In some sense, counting the monic ones is more natural, just like in $\mathbb Z$ we usually count just the positive primes, even though their additive inverses “should” count as primes just as well. Anyways, to get all irreducible polynomials, we just need to multiply by the number of possible leading coefficients – $p-1$.

Some of the notions I’ve used in the solution require more explanation than others (for example because they extend beyond the scope of material on PROMYS). I’ll explain them in an order deviating from the order in which they appear in the solution.

First of all, note that I have used notation $\mathbb F_p$ in place of $\mathbb Z_p$. Right now I remark that these mean precisely the same thing. There are at least three reasons why I prefer this notation. Firstly, $\mathbb Z_p$ has another, contradicting, meaning in number theory, namely it often denotes the ring of all $p$-adic integers. Secondly, it emphasizes that $F_p$ is a field – for general “modulo” rings my prefered notation is $\mathbb Z/n\mathbb Z$, which I would probably use if I’ve only cared about ring structure, but I wouldn’t ever write $\mathbb F_6$, since there is no field with $6$ elements. This brings me to the third point – we can generalize this notation to $\mathbb F_q$ denoting the field with $q$ elements, which it can’t be done with $\mathbb Z_q$ notation, since it already denotes $\mathbb Z/q\mathbb Z$. By the way, I say “the field with $q$ elements”, because it can be shown that there is precisely one such field, provided there is one. By the way, there is a neat characterization of sizes of finite fields – for any prime power $q=p^n$ there is precisely one field of size $q$, and no such field for other $q$. If we take existence of algebraic closure (which I discuss below) for granted, the solution gives us a construction of such field, but it’s quite instructive to try to prove this directly.

At one point I have mentioned a “finie-dimensional vector space”. A vector space over a field $F$ is, in nontechnical terms, a set $V$ of elements, called vectors, such that we can add any two vectors and we can multiply a vector by an element of $F$ in a way such that familiar properties such as commutativity, associativity and distributivity hold. A very important concept regarding a vector space is its dimension, which is, essentially, the least number of vectors needed to express all vectors in $V$ using these vectors, addition and multiplication by elements of $F$. We call the space finite-dimensional if this dimension is finite. These notions are central to linear algebra, which is the study of these spaces, as well as transformations between them.

An important example of a vector space in algebra is any field extension, i.e. any pair of fields $K\subseteq L$. $L$ can then be considered as a vector space over $K$ – we can add any two elements of $L$, and we can multiply an element of $L$ by an element of $K$ (we are “forgetting” that we can multiply arbitrary elements of $L$ when we think of it as of a vector space). In this scenario, there is another name for the dimension – we call it the degree of the extension. In case both $K,L$ are finite, there is a neat formula relating degree and their sizes: if we denote by $d$ the degree of this extension, then $|L|=|K|^d$. This is where the part “$|\mathbb F_{p^n}|=|\mathbb F_{p^m}|^k$ for some $k\in\mathbb N$” comes from.

It is a well-known fact, and it’s moderately easy to establish, that if $\alpha$ is a root of irreducible polynomial in $K[x]$ of degree $d$, then the degree of extension $K[\alpha]$, constructed by adjoining $\alpha$ to $K$, is equal to $d$ (note that this relates the two notions of “degree” we know – degree of a polynomial and degree of an extension). We can explicitly point out a minimal generating set – just take $1,\alpha,\dots,\alpha^{d-1}$.

Now let me say a few words about algebraic closure of a field $F$. It is a field extension $\overline F$ which has two defining properties: first, every nonconstant polynomial in $\overline F[x]$ must have a root in $\overline F$ (this is known as an algebraically closed field); second, every element of $\overline F$ must be a root of a nonzero polynomial from in $F[x]$. An example will nicely illustrate it: Consider first $F=\mathbb R$. The famous fundamental theorem of algebra states that every nonconstant polynomial with complex coefficients has a complex root, that is, $\mathbb C$ is algebraically closed. Moreover, any complex number $x+yi,x,y\in\mathbb R$ is a root of a polynomial $z^2-2xz+(x^2+y^2)$ with real coefficients. This means precisely that $\mathbb C=\overline{\mathbb R}$. However, $\mathbb C$ isn’t the algebraic closure of, say, $\mathbb Q$, because there are complex numbers (called transcendental numbers) which aren’t roots of nonzero polynomials with rational coefficients.

It can be shown that any field has a unique algebraic closure (hence we can speak of the algebraic closure). However, we don’t need exactly that. Note that in the proof we have only used the fact that any polynomial from $\mathbb F_p[x]$ has all its roots, i.e. factors into linear factors, in $\overline{\mathbb F_p}$. Hence, any algebraically closed field containing $\mathbb F_p$ would work for our purposes.

While we are speaking about polynomials, let’s take a minute to appreciate usefulness of derivatives. Their analytic definition (as a limit) wouldn’t make sense in most fields (just think about $\mathbb F_p$!). Nevertheless, we can still make sense of the notion of derivative by simply giving a formula for it (for this reason, it is often called formal derivative, since, in a way, it’s just manipulating symbols, and we don’t care about any “meaning” (e.g. analytic) of these operations). Derivative “detects” multiple factors of a polynomial. To be precise, if a polynomial $g^2$ divides $f$, then $g$ also divides $f'$, and hence $g\mid\gcd(f,f')$. In particular, if $f,f'$ are relatively prime, then $f$ has no square factors, i.e. is squarefree. As a special case of this we can deduce that if $\gcd(f,f')=1$, then $f$ has precisely $\deg f$ roots in a field extension in which it has all its roots, which we have used in case of $x^{p^n}-x$.

I also wanted to mention, even though it is within the scope of PROMYS, the Möbius inversion formula. If we take a function $f$ defined on natural numbers and then define a function $F(n)=\displaystyle\sum_{d\mid n}f(d)$, then there is, a priori, not much reason to expect that $f$ can be expressed in terms of $F$ in a simple way. But nevertheless there is – defining the Möbius $\mu$ function by $\mu(n)=(-1)^k$ if $n$ is a product of $k$ distinct primes and $\mu(n)=0$ if $n$ has a square factor, we have the identity $\displaystyle\sum_{d\mid n}\mu(d)=0$ if $n>1$ and $\displaystyle\sum_{d\mid n}\mu(d)=1$ for $n=1$, we can extract $f$ using the mentioned inversion formula: $f(n)=\displaystyle \sum_{d\mid n}F(d)\mu\left(\frac{n}{d}\right)$. This can be far generalized during the notion of Dirichlet convolution, but this is one wide topic by itself.

One last remark I’d like to make is to relate this topic to an earlier post I made, about Riemann hypothesis for polynomials over a finite field. Since standard Riemann hypothesis gives us tight bounds on the number of primes up to given order, we should expect something like that to work for irreducible polynomials. Indeed, from the derived formula we get $c(n)-\frac{p^n}{n}=\displaystyle\frac{1}{n}\sum_{d\mid n,d. Since no $d$ appearing that new sum will be greater than $\frac{n}{2}$, we can bound this difference in absolute value by $C\frac{p^{n/2}}{n}$ for some constant $C$. This is, more or less, on the same order of magnitude as the error predicted by the Riemann hypothesis in integers case. One can wonder however, why we don’t have a tighter bound – after all, polynomial zeta function has no zeros. The reason for that can be actually traced back to the inversion formula, but this is far beyond the scope of this discussion.

Further explanations already took me over twice as much as the solution itself, so I guess it’s a good time to end the post. Most of the explanations were at least in part superficial, so I don’t expect everyone to understand everything after reading it once. I will be happy to discuss any of the parts of the topic with anyone interested.

I will leave you with a question which you can try to answer yourself, to see how well you understand the topic (some food for thought, one could say): as discussed above, we also have finite fields $\mathbb F_q$ for $q$ not necessarily a prime. Does the derived formula for the number of irreducible polynomials hold in this case? More importantly, does the proof of this formula work? Can you generalize?