Editing Prime number theorem (section)

== Analogue for irreducible polynomials over a finite field ==
There is an analogue of the prime number theorem that describes the "distribution" of [[irreducible polynomial]]s over a [[finite field]]; the form it takes is strikingly similar to the case of the classical prime number theorem.

To state it precisely, let {{math|''F'' {{=}} GF(''q'')}} be the finite field with {{mvar|q}} elements, for some fixed {{mvar|q}}, and let {{mvar|N<sub>n</sub>}} be the number of [[monic polynomial|monic]] ''irreducible'' polynomials over {{mvar|F}} whose [[degree of a polynomial|degree]] is equal to {{mvar|n}}. That is, we are looking at polynomials with coefficients chosen from {{mvar|F}}, which cannot be written as products of polynomials of smaller degree. In this setting, these polynomials play the role of the prime numbers, since all other monic polynomials are built up of products of them. One can then prove that
: <math>N_n \sim \frac{q^n}{n}.</math>
If we make the substitution {{math|''x'' {{=}} ''q''<sup>''n''</sup>}}, then the right hand side is just
: <math>\frac{x}{\log_q x},</math>
which makes the analogy clearer. Since there are precisely {{math|''q''<sup>''n''</sup>}} monic polynomials of degree {{mvar|n}} (including the reducible ones), this can be rephrased as follows: if a monic polynomial of degree {{mvar|n}} is selected randomly, then the probability of it being irreducible is about&nbsp;{{math|{{sfrac|1|''n''}}}}.

One can even prove an analogue of the Riemann hypothesis, namely that
: <math>N_n = \frac{q^n}n + O\left(\frac{q^\frac{n}{2}}{n}\right).</math>

The proofs of these statements are far simpler than in the classical case. It involves a short, [[Combinatorics|combinatorial]] argument,<ref>{{cite journal|last1=Chebolu|first1=Sunil|first2=Ján|last2=Mináč|title=Counting Irreducible Polynomials over Finite Fields Using the Inclusion {{pi}} Exclusion Principle|journal=Mathematics Magazine|date=December 2011|volume=84|issue=5|pages=369–371|doi=10.4169/math.mag.84.5.369|jstor=10.4169/math.mag.84.5.369|arxiv=1001.0409|s2cid=115181186}}</ref> summarised as follows: every element of the degree {{mvar|n}} extension of {{mvar|F}} is a root of some irreducible polynomial whose degree {{mvar|d}} divides {{mvar|n}}; by counting these roots in two different ways one establishes that
: <math>q^n = \sum_{d\mid n} d N_d,</math>
where the sum is over all [[divisor]]s {{mvar|d}} of {{mvar|n}}. [[Möbius inversion]] then yields
: <math>N_n = \frac{1}{n} \sum_{d\mid n} \mu\left(\frac{n}{d}\right) q^d,</math>
where {{math|''μ''(''k'')}} is the [[Möbius function]]. (This formula was known to Gauss.<!-- although I haven't got a reference for this. -->) The main term occurs for {{math|''d'' {{=}} ''n''}}, and it is not difficult to bound the remaining terms. The "Riemann hypothesis" statement depends on the fact that the largest [[proper divisor]] of {{mvar|n}} can be no larger than {{math|{{sfrac|''n''|2}}}}.