8
$\begingroup$

I'm investigating irreducible polynomials over finite fields at the moment, and I wanted to know if there is a formula for the number of irreducible polynomials of degree n over a fixed finite field $\mathbb{F}_q$. Wolfram MathWorld gives the formula \begin{equation} \frac{1}{n}\sum_{d|n}\mu(\frac{n}{d})q^d \end{equation} However, neither it nor the OEIS page it links to offers any proof for this as far as I can tell, and I'm kind of confused by the presence of a divisor sum; I don't see why such a sum would appear in dealing with these polynomials.

So how does one prove this formula?

  • 1
    This question has been answered previously on this site. See for example [here](http://math.stackexchange.com/a/40812/15941)2011-12-19
  • 1
    Anyhow, this looks like the Mobius inversion formula. If $f(n)$ is the number of irreducible polynomials, this formula suggests that $q^n= \sum_{d|n} df(d) $, which doesn't look obvious to me...2011-12-19
  • 5
    @N.S.: That's obvious once you know that $x^{q^n}-x$ is the product of all the (monic) irreducible polynomials over $\mathbb{F}_q$ of degree dividing $n$.2011-12-19
  • 0
    @Dilip: Sorry; for some reason I didn't notice. Thanks for pointing that out.2011-12-19
  • 0
    Note: The Möbius function is defined by $$\mu(n) = \begin{cases} 0 & \text{when } n \text{ has one or more repeated prime factors} \\ 1 & \text{when } n=1 \\ (-1)^k & \text{when } n \text{ has exactly } k \text{ distinct prime factors} \end{cases} $$2017-11-20

2 Answers 2

8

Let $N_q(n)$ be the number of irreducible monic polynomials in $\mathbb{F}_q[x]$ of degree $n$. First prove that $$q^n = \sum_{d|n} d\cdot N_q(d).$$ Then, you can use the additive version of the Möbius inversion formula with $H(n)=q^n$ and $h(n)=nN_q(n)$, so that $H(n)=\sum_{d|n} h(d)$ implies that $h(n)=\sum_{d|n}\mu(\frac{n}{d})H(d)$.

  • 1
    I always liked to show my students this, whenever I taught algebra.2011-12-20
  • 0
    It is indeed a very neat application of Mobius inversion!2011-12-20
  • 0
    Thank you for pointing this out.2011-12-20
2

You may also have a look at A Classical Introduction to Modern Number theory, by Ireland and Rose, page 84.