I know that for every $n\in\mathbb{N}$, $n\ge 1$, there exists $p(x)\in\mathbb{F}_p[x]$ s.t. $\deg p(x)=n$ and $p(x)$ is irreducible over $\mathbb{F}_p$.

I am interested in counting how many such $p(x)$ there exist (that is, given $n\in\mathbb{N}$, $n\ge 1$, how many irreducible polynomials of degree $n$ exist over $\mathbb{F}_p$).

I don't have a counting strategy and I don't expect a closed formula, but maybe we can find something like "there exist $X$ irreducible polynomials of degree $n$ where $X$ is the number of...".

What are your thoughts ?

  • 2
    This question is ok, but has appeared here many times: At least here, here and also here. Voting to close as a duplicate. +1 to you all, though! – Jyrki Lahtonen Jun 2 '12 at 16:16
  • @JyrkiLahtonen: I was wondering if there is as much monic irreducible polynomial of degree $d$ on $\mathbb F_{p}[X]$ than irreducible polynomial of degree $d$ (not necessarily monic). I would say yes since if $X^d+a_{d-1}X^{d-1}+...+a_1X+a_0$ is irreducible, then $\alpha X^d+\alpha a_{d-1}X^{d-1}+...+\alpha a_1 X+a_0$ is irreducible and reciprocally if $a_nX^n+...+a_1X+a_0$ is irreducible, then $X^n+\frac{a_{n-1}}{a_n}X^{n-1}X^{n-1}+...+\frac{a_0}{a_n}$ is irreducible. But I'm not sure if it's true... – user386627 May 8 '17 at 13:39
up vote 25 down vote accepted

Theorem: Let $\mu(n)$ denote the Möbius function. The number of monic irreducible polynomials of degree $n$ over $\mathbb{F}_q$ is the necklace polynomial $$M_n(q) = \frac{1}{n} \sum_{d | n} \mu(d) q^{n/d}.$$

(To get the number of irreducible polynomials just multiply by $q - 1$.)

Proof. Let $M_n(q)$ denote the number in question. Recall that $x^{q^n} - x$ is the product of all the monic irreducible polynomials of degree dividing $n$. By counting degrees, it follows that $$q^n = \sum_{d | n} d M_d(q)$$

(since each polynomial of degree $d$ contributes $d$ to the total degree). By Möbius inversion, the result follows.

As it turns out, $M_n(q)$ has a combinatorial interpretation for all values of $q$: it counts the number of aperiodic necklaces of length $n$ on $q$ letters, where a necklace is a word considered up to cyclic permutation and an aperiodic necklace of length $n$ is a word which is not invariant under a cyclic permutation by $d$ for any $d < n$. More precisely, the cyclic group $\mathbb{Z}/n\mathbb{Z}$ acts by cyclic permutation on the set of functions $[n] \to [q]$, and $M_n(q)$ counts the number of orbits of size $n$ of this group action. This result also follows from Möbius inversion.

One might therefore ask for an explicit bijection between aperiodic necklaces of length $n$ on $q$ letters and monic irreducible polynomials of degree $n$ over $\mathbb{F}_q$ when $q$ is a prime power, or at least I did a few years ago and it turns out to be quite elegant.

Let me also mention that the above closed form immediately leads to the "function field prime number theorem." Let the absolute value of a polynomial of degree $d$ over $\mathbb{F}_q$ be $q^d$. (You can think of this as the size of the quotient $\mathbb{F}_q[x]/f(x)$, so in that sense it is analogous to the norm of an element of the ring of integers of a number field.) Then the above formula shows that the number of monic irreducible polynomials $\pi(n)$ of absolute value less than or equal to $n$ satisfies $$\pi(n) \sim \frac{n}{\log_q n}.$$

  • 1
    Shouldn't the first sum read $\mu(d)$ instead of $\mu(n)$? – Pedro Tamaroff Aug 4 '13 at 21:39
  • 1
    @Peter: yep. Thanks for the correction! – Qiaochu Yuan Aug 4 '13 at 21:54

With regards to your question, this paper has a formula for counting the number of monic irreducibles over a finite field.

The number of monic irreducible polynomials of degree $n$ over $\mathbb{F}_p$ equals

$$\frac{1}{n} \cdot \sum_{d|n} p^d \mu\left(\frac{n}{d}\right)$$

where $\mu$ is the Möbius function. This follows rather easily from the Möbius inversion formula. You can find details here. Note that this in particular implies the existence of one irreducible polynomial and therefore of the field with $p^n$ elements.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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