# The number of irreducible polynomials over ${\mathbb F}_p$

Let $p$ be a prime number. The number of monic irreducible polynomial $P\in{\mathbb F}_p[X]$, in terms of the degree $d$, begins with $${\rm irr}(1)=p,\qquad{\rm irr}(2)=\frac{p(p-1)}2,\qquad{\rm irr}(3)=\frac{p(p^2-1)}3,\qquad{\rm irr}(4)=\frac{5p^2(p^2-1)}{12}.$$ This seems to be the beginning of a nice sequence of polynomials in $p$. Does someone know the general formula?

Motivation. As F. Brunault pointed out to me, there is a polynomial $\Pi_{n,p}$ that vanishes over ${\bf M}_n({\mathbb F}_p)$. Just take the lcm of all the polynomials of degree $n$ over $F_p$. In closed form, it is the product of all the irreducible polynomials of degree $d\le n$, to the power $[\frac{n}{d}]$ (integral part). The degree of $\Pi_{n,p}$ is $$\delta(n)=\sum_{d\le n}d[\frac{n}{d}]{\rm irr}(d).$$ In terms of $n$, this degree is $$\delta(1)=p,\quad\delta(2)=p(p+1),\quad\delta(3)=p(p^2+p+1),\quad\delta(4)=\frac13p(p+1)(5p^2-2p+3).$$

Edit. The values given above for $n=4$ are erroneous.

-

The product of all monic irreducible polynomials of degree dividing $d$ in $\mathbb F_q[x]$ is $$x^{q^d}-x,$$ so from Mobius inversion we get the number of irreducible polynomials of degree $d$ is $$M _d (q) = \frac{1}{d} \sum _{k | d} \mu(k) q ^{d/k}$$ This is known as the necklace polynomial.

-
For $n=4$, the factor $1/4$ does not coincide with Denis's $5/12$. I assume Denis made a calculation mistake? –  Tom De Medts Jul 6 '12 at 8:37
Should be $\mu(d)$ in the sum, I assume. –  Vladimir Dotsenko Jul 6 '12 at 8:48
And now (after the edit) it should be $\mu(k)$ in the sum, I assume. –  Tom De Medts Jul 6 '12 at 9:08
Ah, I can't seem to type a single equation right. Thanks for the correction. –  Gjergji Zaimi Jul 6 '12 at 9:12
Thanks; I see the reason: $x^{q^d}-x=0$ is the equation of $K={\mathbb F}_{q^d}$ over $k={\mathbb F}_q$, and every element of $K$ has a unique mimimal polynomial. –  Denis Serre Jul 6 '12 at 9:14

Gjergji Zaimi already said it all, but I want to point out a tiny bit longer but equally cute way to derive the same formula. Every monic polynomial over $\mathbb{F}\_q$ decomposes into a product of irreducibles uniquely, hence we have a formal power series equality $$\frac{1}{1-qt}=\prod_{k\ge 1}\frac{1}{(1-t^k)^{M_k(q)}}$$ (indeed, the coefficient of $t^n$ on the left is the number of monic polynomials of degree $n$, and the coefficient of $t^n$ on the right counts the decompositions into irreducibles with multiplicities). Taking logarithmic derivatives, one can do the M\"obius inversion and arrive at the formula pointed out by Gjergji.

-
This is of course the infinite product formula for the Weil zeta function of $\mathbb A^1$. –  Will Sawin Jul 6 '12 at 16:16