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)$.

  • 1
    $\begingroup$ 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. $\endgroup$ – Dietrich Burde Jun 27 '17 at 8:00
  • $\begingroup$ Are there any purely combinatorial ways? $\endgroup$ – Siddharth Joshi Jun 27 '17 at 8:12
  • $\begingroup$ The argument with $\mu(n)$ is purely combinatorial in the end. $\endgroup$ – Dietrich Burde Jun 27 '17 at 8:14
  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jun 27 '17 at 8:24
  • $\begingroup$ @user1952009: Have you used the recurrence relation that I've stated to prove this - $p^m = \sum_{d|m}d\lambda(d)$ $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.