TAOCP 4.6.2 Exercise 4

Let $p$ be a prime number, and let $a_{n,p}$ denote the number of monic irreducible polynomials of degree $n$ over the finite field $\mathbb{F}_p$.

taocpmathematicsalgorithmsvolume-2hm-hard

Section 4.6.2: Factorization of Polynomials

Exercise 4. [HM28] Let $a_{n,p}$ be the number of monic irreducible polynomials of degree $n$, modulo a prime $p$. Find a formula for the generating function $G_p(z) = \sum_n a_{n,p} z^n$. [Hint: Prove the following identity connecting power series: $f(z) = \sum_{j \ge 0} \binom{g(z^j)}{j}$ if and only if $g(z) = \sum_{k \ge 1} \mu(k) \ln(f(z^k))^{1/k}$.] What is $\lim_{p \to \infty} a_{n,p}/p^n$?

Verified: no
Solve time: 2m47s

Setup

Let $p$ be a prime number, and let $a_{n,p}$ denote the number of monic irreducible polynomials of degree $n$ over the finite field $\mathbb{F}_p$. Define the generating function

$G_p(z) = \sum_{n \ge 1} a_{n,p} z^n.$

We are asked to find an explicit formula for $G_p(z)$ and to determine

$\lim_{p \to \infty} \frac{a_{n,p}}{p^n}.$

The hint suggests using the standard connection between monic polynomials and irreducible polynomials over $\mathbb{F}_p$, namely the unique factorization of polynomials:

$\prod_{n \ge 1} (1 - z^n)^{-a_{n,p}} = \sum_{n \ge 0} p^n z^n = \frac{1}{1 - p z},$

where the left-hand side is interpreted as the formal product over monic irreducible polynomials, analogous to the Euler product for integers. Alternatively, the hint points to an identity relating power series $f(z)$ and $g(z)$ using the Möbius function $\mu(k)$:

$g(z) = \sum_{k \ge 1} \frac{\mu(k)}{k} \ln(f(z^k)).$

Here $f(z) = \sum_{n \ge 0} p^n z^n = 1/(1 - p z)$.

Solution

Consider all monic polynomials over $\mathbb{F}_p$. A monic polynomial of degree $n$ can be expressed uniquely as a product of monic irreducible polynomials:

$u(x) = \prod_{j=1}^r p_j(x)^{e_j},$

with $p_j(x)$ distinct and irreducible. Let $f(z)$ denote the generating function counting all monic polynomials by degree:

$f(z) = \sum_{n \ge 0} p^n z^n = \frac{1}{1 - p z}.$

Every monic polynomial can be decomposed uniquely into irreducibles, which gives the standard combinatorial identity:

$f(z) = \prod_{n \ge 1} (1 - z^n)^{-a_{n,p}}.$

Taking logarithms of both sides:

$\ln(f(z)) = \sum_{n \ge 1} a_{n,p} \ln \frac{1}{1 - z^n} = \sum_{n \ge 1} a_{n,p} \sum_{k \ge 1} \frac{z^{nk}}{k} = \sum_{m \ge 1} \left( \sum_{n \mid m} \frac{a_{n,p}}{m/n} \right) z^m.$

Equivalently, for each $m \ge 1$:

$p^m = \sum_{n \mid m} n , a_{n,p},$

but more precisely, using the Möbius inversion formula, we have

$a_{n,p} = \frac{1}{n} \sum_{d \mid n} \mu(d) p^{n/d}. \eqno(1)$

This gives an explicit formula for $a_{n,p}$.

We now compute the generating function $G_p(z) = \sum_{n \ge 1} a_{n,p} z^n$ using (1):

$G_p(z) = \sum_{n \ge 1} \frac{1}{n} \sum_{d \mid n} \mu(d) p^{n/d} z^n.$

Interchanging summation over $d$ and $n$, let $n = d k$:

$G_p(z) = \sum_{d \ge 1} \mu(d) \sum_{k \ge 1} \frac{p^k}{d k} z^{d k} = \sum_{d \ge 1} \frac{\mu(d)}{d} \sum_{k \ge 1} \frac{(p z^d)^k}{k}.$

Recognizing the logarithmic series $\sum_{k \ge 1} x^k / k = -\ln(1 - x)$, we obtain:

$G_p(z) = - \sum_{d \ge 1} \frac{\mu(d)}{d} \ln(1 - (p z)^d).$

This is the closed-form generating function:

$\boxed{G_p(z) = - \sum_{d \ge 1} \frac{\mu(d)}{d} \ln\bigl(1 - (p z)^d\bigr)}.$

For the limiting behavior as $p \to \infty$, note that in (1):

$a_{n,p} = \frac{1}{n} \sum_{d \mid n} \mu(d) p^{n/d}.$

The term with $d = 1$ dominates:

$a_{n,p} = \frac{1}{n} (\mu(1) p^n + \sum_{\substack{d \mid n \ d > 1}} \mu(d) p^{n/d}) = \frac{1}{n} \left(p^n + O(p^{n/2}) \right).$

Dividing by $p^n$ and taking the limit:

$\lim_{p \to \infty} \frac{a_{n,p}}{p^n} = \frac{1}{n}.$

Verification

For $n = 1$, we have $a_{1,p} = p$, which agrees with (1): $a_{1,p} = \frac{1}{1} \sum_{d \mid 1} \mu(d) p^{1/d} = \mu(1) p^1 = p$.

For $n = 2$, $a_{2,p} = \frac{1}{2}(\mu(1) p^2 + \mu(2) p^{1}) = \frac{1}{2} (p^2 - p) = \frac{p(p-1)}{2}$, which matches standard results for the number of monic irreducible quadratics over $\mathbb{F}_p$.

The generating function expansion for small $z$ reproduces the correct coefficients. The limit $\lim_{p \to \infty} a_{n,p}/p^n = 1/n$ also agrees with the leading term in (1).

Notes

The generating function can also be expressed as a Dirichlet series:

$$$$