Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
    
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

3 Answers 3

up vote 16 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}.$$

share|improve this answer
    
Shouldn't the first sum read $\mu(d)$ instead of $\mu(n)$? –  Pedro Tamaroff Aug 4 '13 at 21:39
    
@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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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