This is Exercise 23(b) of Chapter V (Algebraic Extensions) from Lang's Algebra.
Let $k$ be finite field with $q$ elements, and let $\pi_q(n)$ be the number of monic irreducible polynomials $p \in k[X]$ of degree $\leq n$. Prove that $$ \pi_q(m) \sim \frac{q}{q-1} \frac{q^m}{m} \quad \text{for} \quad m \to \infty. $$
I have tried a few things but I'm not making any progress at all.
- The hint given in class was to take the logarithmic derivative of the zeta function that was defined in part (a) of the same problem. We defined the zeta function to be $$ Z(t) = (1-t)^{-1} \prod_p (1-t^{\deg p})^{-1}. $$ I computed this to be equal to the rational function $$ (1-t)^{-1}(1-qt)^{-1} $$ on the region $|t| < q^{-1}$. Taking the logarithmic derivative of $Z(t)$, I get $$ \frac{Z'(t)}{Z(t)} = \frac{1}{1-t} + \frac{q}{1-qt} = \frac{1+q-2qt}{(1-t)(1-qt)} = (1+q-2qt)Z(t). $$ I am not getting any further ideas at this point in how to use this to describe $\pi_q(n)$.
- From Exercise 22 I know that if $\psi(d)$ denotes the number of monic irreducible polynomials of degree $d$, then the total number of polynomials of degree $n$, which is $q^n$, can be expressed as $$ q^n = \sum_{d \mid n} d \psi(d). $$ Using the Möbius inversion formula, I can deduce that $$ n\psi(n) = \sum_{d \mid n} \mu(d) q^{n/d}, $$ where $\mu$ is the Möbius function. Since $\pi_q(m) = \sum_{k=1}^m \psi(k)$, I can use the above equation to write $$ \pi_q(m) = \sum_{k=1}^m \frac{1}{k} \sum_{d \mid k} \mu(d) q^{k/d}. $$ My intuition is that the highest power of $q$ will dominate the sum, so the RHS is approximately $$ \frac{q^m}{m}, $$ so I get roughly what I'm asked to show in the problem. I'm having trouble refining my ideas any further.
- I have also looked at this question, which asks the same problem, but no answers or comments have been posted there.
- Lang remarks after stating the problem, "This is the analogue of the prime number theorem in number theory, but it is essentially trivial in the present case, because the Riemann hypothesis is trivially verified." I have tried looking at the proof of the prime number theorem on the internet, but I haven't really understood it; and I certainly can't see how to deduce it from the Riemann hypothesis even in this case.
Any help in solving this problem would be appreciated.
Expanding on @JyrkiLahtonen's comment above.
I also apologise for any needless complication in explaining each step. I am unfamiliar with these manipulations, and would appreciate receiving other better answers.
As already observed, $n\psi(n)$ will be dominated by the term of largest exponent, namely $q^n$. So, let us estimate the size of the sum of the remaining terms. $$ n\psi(n) = q^n + \sum_{\substack{d \mid n \\ d > 1}} \mu(d) q^{n/d}, $$ so, $$ \sum_{\substack{d \mid n \\ d > 1}} \mu(d) q^{n/d} \leq \sum_{j = 1}^{\lfloor n/2 \rfloor} q^j = q\frac{q^{\lfloor n/2 \rfloor}-1}{q-1} \leq q\frac{q^{n/2}-1}{q-1}. $$ So, the error in estimating $\pi_q(m)$ can be calculated: $$ \pi_q(m) = \sum_{k=1}^m \psi(k) \leq \sum_{k=1}^m \frac{q^k}{k} + \sum_{k=1}^m \frac{q}{k}\frac{q^{k/2}-1}{q-1}, $$ so, $$ \sum_{k=1}^m \frac{q}{k}\frac{q^{k/2}-1}{q-1} \leq \sum_{k=1}^m q\frac{q^{k/2}-1}{q-1} = \frac{1}{1-q^{-1}} \left(q^{m/2}\frac{1-q^{-m/2}}{1-q^{-1/2}}-m\right). $$ Dividing the error term by $\frac{q}{q-1}\frac{q^m}{m}$ and letting $m \to \infty$, we get \begin{align} \lim_{m \to \infty} \frac{m}{q^{m/2}} \frac{1-q^{-m/2}}{1-q^{-1/2}} - \frac{m^2}{q^m} = 0. \end{align} Hence, \begin{align} \lim_{m \to \infty} \frac{\pi_q(m)}{\left( \frac{q}{q-1}\frac{q^m}{m} \right)} &\leq \lim_{m \to \infty} \frac{\sum_{k=1}^m \frac{q^k}{k}}{\left( \frac{q}{q-1}\frac{q^m}{m} \right)} + \lim_{m \to \infty} \frac{\sum_{k=1}^m \frac{q}{k}\frac{q^{k/2}-1}{q-1}}{\left( \frac{q}{q-1}\frac{q^m}{m} \right)} \\ &= (1-q^{-1}) \lim_{m \to \infty} \frac{\sum_{k=1}^m q^k/k}{q^m/m}. \end{align} On the other hand, $n\psi(n) \geq q^n$ for all $n$, so $$ \pi_q(m) \geq \sum_{k=1}^m \frac{q^k}{k} \implies \lim_{m \to \infty} \frac{\pi_q(m)}{\left( \frac{q}{q-1}\frac{q^m}{m} \right)} \geq (1-q^{-1}) \lim_{m \to \infty} \frac{\sum_{k=1}^m q^k/k}{q^m/m}. $$ Thus, $$ \lim_{m \to \infty} \frac{\pi_q(m)}{\left( \frac{q}{q-1}\frac{q^m}{m} \right)} = (1-q^{-1}) \lim_{m \to \infty} \frac{\sum_{k=1}^m q^k/k}{q^m/m}. $$ The limit on the right can be evaluated via the Stolz-Cesàro theorem and it evaluates to $(1-q^{-1})^{-1}$. Hence, $$ \lim_{m \to \infty} \frac{\pi_q(m)}{\left( \frac{q}{q-1}\frac{q^m}{m} \right)} = 1, $$ that is, $$ \pi_q(m) \sim \frac{q}{q-1} \frac{q^m}{m} \quad \text{for} \quad m \to \infty. $$