TAOCP 4.6.2 Exercise 27
Fix a degree $n \ge 1$.
Section 4.6.2: Factorization of Polynomials
Exercise 27. [**] [HM30] Prove that a random primitive polynomial over the integers is "almost always" irreducible, in some appropriate sense.
Verified: yes
Solve time: 3m45s
Fix a degree $n \ge 1$. For $H \ge 1$, let
$$ \mathcal P_n(H)={a_nx^n+\cdots+a_0 : |a_i|\le H,\ \gcd(a_0,\ldots,a_n)=1,\ a_n\ne0}. $$
We interpret “random primitive polynomial of degree $n$” as a polynomial chosen uniformly from $\mathcal P_n(H)$, and “almost always irreducible” means that
$$ \lim_{H\to\infty} \frac{#{f\in\mathcal P_n(H): f \text{ reducible in } \mathbf Z[x]}} {#\mathcal P_n(H)} =0. $$
We shall prove this.
First count primitive polynomials. The total number of degree-$n$ integer polynomials with $|a_i|\le H$ and $a_n\ne0$ is
$$ (2H)(2H+1)^n. $$
Among integer $(n+1)$-tuples, the proportion whose coordinates have greatest common divisor $1$ tends to
$$ \frac1{\zeta(n+1)}. $$
Hence
$$ #\mathcal P_n(H) = \frac{(2H)^{n+1}}{\zeta(n+1)} +O(H^n). $$
In particular,
$$ #\mathcal P_n(H)\asymp H^{n+1}. $$
Now estimate the reducible primitive polynomials.
Suppose
$$ f(x)=g(x)h(x), $$
where $f\in\mathcal P_n(H)$, and where $g,h\in\mathbf Z[x]$ are nonconstant. Since $f$ is primitive, Gauss’s lemma implies that $g$ and $h$ are primitive.
Write
$$ \deg g=r,\qquad \deg h=s,\qquad r,s\ge1,\qquad r+s=n. $$
Let
$$ g(x)=b_rx^r+\cdots+b_0,\qquad h(x)=c_sx^s+\cdots+c_0. $$
Since the coefficients of $f$ are bounded by $H$, we have in particular
$$ |b_rc_s|\le H, \qquad |b_0c_0|\le H. $$
For fixed $r,s$, we count the possible factorizations.
Choose integers $u,v$ with $|uv|\le H$. The number of such pairs is
$$ O(H\log H), $$
because
$$ \sum_{1\le |u|\le H}\Bigl\lfloor \frac{H}{|u|}\Bigr\rfloor =O(H\log H). $$
Thus there are $O(H\log H)$ possibilities for $(b_r,c_s)$, and likewise $O(H\log H)$ possibilities for $(b_0,c_0)$.
The remaining coefficients
$$ b_{r-1},\ldots,b_1,c_{s-1},\ldots,c_1 $$
may each take at most $O(H)$ values. Their total number is therefore
$$ O(H^{(r-1)+(s-1)}) = O(H^{n-2}). $$
Hence the number of reducible primitive polynomials arising from a factorization of degrees $r,s$ is
$$ O(H^{n-2}(H\log H)^2) = O(H^n(\log H)^2). $$
There are only finitely many pairs $(r,s)$ with $r+s=n$, so the total number of reducible primitive polynomials in $\mathcal P_n(H)$ is
$$ O(H^n(\log H)^2). $$
Therefore
$$ \frac{ #{f\in\mathcal P_n(H): f \text{ reducible}} }{ #\mathcal P_n(H) } = O!\left(\frac{(\log H)^2}{H}\right). $$
Since the right-hand side tends to $0$ as $H\to\infty$,
$$ \lim_{H\to\infty} \frac{#{f\in\mathcal P_n(H): f \text{ reducible}}} {#\mathcal P_n(H)} =0. $$
Thus, in the natural density sense, a random primitive polynomial over $\mathbf Z$ is almost always irreducible. ∎