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?

$\endgroup$
  • 1
    $\begingroup$ This question has been answered previously on this site. See for example here $\endgroup$ – Dilip Sarwate Dec 19 '11 at 15:53
  • 1
    $\begingroup$ 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... $\endgroup$ – N. S. Dec 19 '11 at 15:56
  • 5
    $\begingroup$ @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$. $\endgroup$ – Chris Eagle Dec 19 '11 at 16:05
  • $\begingroup$ @Dilip: Sorry; for some reason I didn't notice. Thanks for pointing that out. $\endgroup$ – Will Dana Dec 19 '11 at 17:13
  • $\begingroup$ 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} $$ $\endgroup$ – hardmath Nov 20 '17 at 1:24
8
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I always liked to show my students this, whenever I taught algebra. $\endgroup$ – Lubin Dec 20 '11 at 3:56
  • $\begingroup$ It is indeed a very neat application of Mobius inversion! $\endgroup$ – Álvaro Lozano-Robledo Dec 20 '11 at 4:06
  • $\begingroup$ Thank you for pointing this out. $\endgroup$ – Will Dana Dec 20 '11 at 6:32
2
$\begingroup$

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

$\endgroup$

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.