Ytukyg

I know that for every $ninmathbb{N}$, $nge 1$, there exists $p(x)inmathbb{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 $ninmathbb{N}$, $nge 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 ?

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}/nmathbb{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}.$$

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 muleft(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.