# Counting monic irreducible polynomials of a particular degree without use of finite fields?

I know that every irreducible polynomial over $\mathbb F_p[x]$ of degree equal to the degree $m$ of a finite field $\mathbb F_{p^{m}}$ has a root in the field. Using this result we can count the number of irreducible polynomials of degree $m$ by counting elements in $F_{p^m}$ that don't belong to any sub-field of the finite field. However are there are other ways to count them?

For example, we can obtain a recurrence relation $$\ \sum_{{k=1} \\c_{1}i_{1}+...+c_{k}i_{k} \ = \ m \\1\le i_1<...<i_k} {{\lambda(1)+c_1-1}\choose{c_1}}...{{\lambda(k)+c_k-1}\choose{c_k}} \ = \ p^m$$ Where $\lambda(i)$ is the number of monic irreducible polynomials of degree $i$ and $c_1, c_2...c_k$ are natural numbers.

But this recurrence relation is not useful since we don't obtain a closed form solution. Are there other similar ways (combinatorial or recurrence) that provide a closed form solution for $\lambda(n)$.

• See the answers here, and the linked questions. Also this duplicate. Since the question is about finite fields, one cannot avoid them really. But one can use the Moebuis function. – Dietrich Burde Jun 27 '17 at 8:00
• Are there any purely combinatorial ways? – Siddharth Joshi Jun 27 '17 at 8:12
• The argument with $\mu(n)$ is purely combinatorial in the end. – Dietrich Burde Jun 27 '17 at 8:14
• I get the feeling that you are trying to work towards this method of arriving at the same formula. Mind you, I don't really recommend that approach, but it is an ok (albeit relatively standard) piece of generatingfunctionology, so you may find it interesting. – Jyrki Lahtonen Jun 27 '17 at 8:24
• @user1952009: Have you used the recurrence relation that I've stated to prove this - $p^m = \sum_{d|m}d\lambda(d)$ – Siddharth Joshi Jun 27 '17 at 9:19

In $\mathbb{F}_p[x]$ let $M(n) = \# \{$ monic polynomials of degree $n\} = p^n$

and $\lambda(n) = \# \{$ irreducibles monic polynomials of degree $n\}$.

What we want to show is $$n \lambda(n) = \sum_{d | n} \mu(d) p^{n/d} \Longleftrightarrow p^n= \sum_{d | n} d \lambda(d)$$

• A first proof is that $\sum_{d | n} d \lambda(d)$ is the total number of roots of irreducible polynomials of degree $d | n$, and they form a field of degree $n$ over $\mathbb{F}_p$ ie. with $p^n$ elements.

• A second proof is the zeta function (having an Euler product by unique factorization in irreducibles) $$\frac{1}{1-px} = \sum_{n=0}^\infty M(n) x^n = \prod_{n=1}^\infty \frac{1}{(1-x^n)^{\lambda(n)}} \tag{2}$$

Taking the logarithm, expanding $-\log(1-t) = \sum_{k=1}^\infty \frac{t^k}{k}$ and equating the coefficients gives the result.

Note expanding the product in $(2)$ gives the recursion formula you stated.