TAOCP 4.6.2 Exercise 5
Let A_{n,p}=\sum_{m=1}^n \frac{a_{m,p}}{p^m}, where $a_{m,p}$ denotes the number of monic irreducible polynomials of degree $m$ over $\mathbf F_p$.
Section 4.6.2: Factorization of Polynomials
Exercise 5. [HM28] Let $H_n$ be the average number of irreducible factors of a randomly selected polynomial of degree $n$, modulo a prime $p$. Show that $\lim_{n \to \infty} A_{n,p} = H_n$. What is the limiting average value of $2^r$, when $r$ is the number of irreducible factors?
Verified: yes
Solve time: 9m16s
Let
$$ A_{n,p}=\sum_{m=1}^n \frac{a_{m,p}}{p^m}, $$
where $a_{m,p}$ denotes the number of monic irreducible polynomials of degree $m$ over $\mathbf F_p$.
Let $r(u)$ denote the number of distinct monic irreducible factors of a monic polynomial $u$, and define
$$ H_n=\frac1{p^n}\sum_{\deg u=n} r(u), $$
where the sum extends over all monic polynomials of degree $n$.
We first prove that
$$ H_n=A_{n,p}. $$
For each monic irreducible polynomial $\pi$, define the indicator
$$ I_\pi(u)= \begin{cases} 1,&\pi\mid u,\ 0,&\pi\nmid u. \end{cases} $$
Since $r(u)$ counts the distinct irreducible divisors of $u$,
$$ r(u)=\sum_\pi I_\pi(u), $$
where the sum ranges over all monic irreducible polynomials.
Fix a monic irreducible polynomial $\pi$ of degree $m\le n$. A monic polynomial $u$ of degree $n$ is divisible by $\pi$ iff
$$ u=\pi v, $$
where $v$ is monic of degree $n-m$. There are exactly $p^{,n-m}$ such polynomials $v$. Hence
$$ \Pr(\pi\mid u)=\frac{p^{,n-m}}{p^n}=p^{-m}. $$
Therefore the average value of $I_\pi(u)$ is $p^{-m}$. Summing over all monic irreducible polynomials,
$$ \begin{aligned} H_n &= \frac1{p^n}\sum_{\deg u=n}\sum_\pi I_\pi(u) \ &= \sum_\pi \frac1{p^n}\sum_{\deg u=n} I_\pi(u) \ &= \sum_{m=1}^n a_{m,p}p^{-m}. \end{aligned} $$
Thus
$$ H_n=A_{n,p}. $$
Consequently,
$$ \lim_{n\to\infty}H_n = \lim_{n\to\infty}A_{n,p}. $$
Now consider
$$ F_n=\frac1{p^n}\sum_{\deg u=n}2^{r(u)}. $$
Write
$$ u=\prod_\pi \pi^{e_\pi}, $$
where the product ranges over all monic irreducible polynomials. Then
$$ r(u)=#{\pi:e_\pi>0}. $$
For each irreducible factor $\pi$ dividing $u$, a squarefree divisor either contains $\pi$ or does not contain $\pi$. Hence the number of squarefree divisors of $u$ is exactly $2^{r(u)}$. Therefore
$$ 2^{r(u)} = \sum_{\substack{d\mid u\ d\text{ squarefree}}}1. $$
Averaging over all monic polynomials $u$ of degree $n$,
$$ F_n = \frac1{p^n} \sum_{\deg u=n} \sum_{\substack{d\mid u\ d\text{ squarefree}}}1. $$
Since all sums are finite, we may interchange the order of summation:
$$ F_n = \frac1{p^n} \sum_{\substack{d\text{ monic}\ d\text{ squarefree}}} #{u:\deg u=n,\ d\mid u}. $$
If $\deg d=k\le n$, then every monic polynomial $u$ divisible by $d$ has the form
$$ u=dv, $$
where $v$ is monic of degree $n-k$. There are exactly $p^{,n-k}$ such $v$. Hence
$$ #{u:\deg u=n,\ d\mid u}=p^{,n-k}. $$
Therefore
$$ F_n = \sum_{\substack{d\text{ monic}\ d\text{ squarefree}\ \deg d\le n}} p^{-\deg d}. $$
Let $s_k$ denote the number of monic squarefree polynomials of degree $k$. Then
$$ F_n=\sum_{k=0}^n s_k p^{-k}. $$
Now $s_0=1$, and for every $k\ge1$,
$$ s_k=p^k-p^{k-1}. $$
Indeed, among the $p^k$ monic polynomials of degree $k$, exactly $p^{k-1}$ are divisible by the square of a nonconstant polynomial.
Hence
$$ \begin{aligned} F_n &= 1+\sum_{k=1}^n \frac{p^k-p^{k-1}}{p^k} \ &= 1+\sum_{k=1}^n\left(1-\frac1p\right) \ &= 1+n\left(1-\frac1p\right). \end{aligned} $$
Therefore
$$ \boxed{ \frac1{p^n}\sum_{\deg u=n}2^{r(u)} = 1+n\left(1-\frac1p\right) }. $$
In particular,
$$ F_n\sim \left(1-\frac1p\right)n, $$
so the limiting average value of $2^r$ is $+\infty$.