Number of irreducible polynomials over a finite field

I and some friends just came up with this. (We came up with some ideas for the proof, after coming across the formula on the internet.) This is the coolest application of the Möbius inversion formula that I’ve seen so far.

Let q be a prime power and n any positive integer. We wish to count the number C(n) of monic irreducible polynomials of degree n over the finite field \mathbb F_q.

Note that the zeros of

\displaystyle F_d(X):=\prod_{\deg(f)=d}f(X)

are precisely the elements of degree d over \mathbb F_q, where the product is taken over monic irreducible polynomials f\in\mathbb F_q[X]. Further, we have the following:

Lemma 1. Let g\neq h be relatively prime polynomials over a field k. Then g and h have no common zeros.

Proof. Since k[X] is a PID, there are polynomials u,v\in k[X] such that ug+vh=1. If \alpha is a common zero of g and h in some extension K/k, then X-\alpha divides 1=ug+vh in K[X], a contradiction. \square

Lemma 2. If f is irreducible over a field k, then f has distinct zeros.

Proof. Note that any multiple zero of f must be a common zero of f and its formal derivative f'. Since f is irreducible over k, it follows that f and f' are relatively prime over k. Now apply lemma 1 to f and f'. \square

It follows that the zeros of

\displaystyle \prod_{d\mid n}F_d(X)

are all distinct and are precisely the elements of the union of all the subfields of \mathbb F_{q^n}, which is just \mathbb F_{q^n}. This implies

(*)\qquad\qquad\qquad\qquad\quad\displaystyle\prod_{d\mid n}F_d(X)=X^{q^n}-X,

since \mathbb F_{q^n} is the splitting field of X^{q^n}-X over \mathbb F_q. Now a comparison of the degrees of both sides reveals that

\displaystyle\sum_{d\mid n}dC(d)=q^n.

Finally, Möbius inversion gives

\displaystyle \boxed{C(n)=\frac 1n\sum_{d\mid n}\mu(d)q^{n/d}}.

Advertisements

Leave a comment

Filed under Combinatorics, Number theory

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s