TAOCP 4.6.2 Exercise 37
Consider a random monic polynomial $u(x)$ of degree $n$ with coefficients chosen uniformly from ${0,1,\ldots,p-1}$.
Section 4.6.2: Factorization of Polynomials
Exercise 37. [HM24] (George E. Collins.) Let $d_1, \ldots, d_r$ be positive integers whose sum is $n$, and let $p$ be prime. What is the probability that the irreducible factors of a random $n$th-degree integer polynomial $u(x)$ have degrees $d_1, \ldots, d_r$ when it is completely factored modulo $p$? Show that this probability is asymptotically the same as the probability that a random permutation on $n$ elements has cycles of lengths $d_1, \ldots, d_r$.
Verified: yes
Solve time: 2m33s
Solution
Consider a random monic polynomial $u(x)$ of degree $n$ with coefficients chosen uniformly from ${0,1,\ldots,p-1}$. Let its complete factorization modulo $p$ be
$u(x) = p_1(x) \cdots p_r(x),$
where $p_1(x), \ldots, p_r(x)$ are distinct monic irreducible polynomials over $\mathbb{F}p$, and $\deg(p_j) = d_j > 0$ for $1 \le j \le r$. By definition, $\sum{j=1}^r d_j = n$.
To find the probability that the factor degrees of a random polynomial are exactly $d_1, \ldots, d_r$, consider first the total number of monic polynomials of degree $n$ over $\mathbb{F}_p$, which is $p^n$.
Let $N(d_1,\ldots,d_r)$ denote the number of monic polynomials whose complete factorization has factor degrees $d_1, \ldots, d_r$. Each factor $p_j(x)$ is an irreducible polynomial of degree $d_j$. The number of monic irreducible polynomials of degree $d$ over $\mathbb{F}_p$ is given by
$I(d) = \frac{1}{d} \sum_{k \mid d} \mu(k) p^{d/k},$
where $\mu$ is the Möbius function (see Section 4.6.2, exercise 33).
Assuming the degrees $d_j$ are fixed, and because the factors are distinct, the number of ways to choose the $p_j(x)$ is
$\prod_{j=1}^r I(d_j).$
Each choice of distinct irreducible factors gives a unique monic polynomial up to ordering. Since multiplication is commutative, distinct orderings yield the same polynomial; therefore we must divide by $r!$ if the $d_j$ are all equal, or more generally by $\prod_k m_k!$ if $m_k$ factors have the same degree $d_k$.
Hence, exactly
$N(d_1,\ldots,d_r) = \frac{\prod_{j=1}^r I(d_j)}{\prod_k m_k!},$
where $m_k$ is the multiplicity of degree $d_k$ in the sequence $(d_1,\ldots,d_r)$.
The probability $P(d_1,\ldots,d_r)$ is then
$P(d_1,\ldots,d_r) = \frac{N(d_1,\ldots,d_r)}{p^n} = \frac{\prod_{j=1}^r I(d_j)}{p^n \prod_k m_k!}.$
For large $p$, the formula for $I(d_j)$ simplifies asymptotically to $I(d_j) \sim p^{d_j}/d_j$, since the terms with $k>1$ in the Möbius inversion are negligible compared to the leading $p^{d_j}$ term. Substituting $I(d_j) \sim p^{d_j}/d_j$ into the probability gives
$P(d_1,\ldots,d_r) \sim \frac{\prod_{j=1}^r p^{d_j}/d_j}{p^n \prod_k m_k!} = \frac{\prod_{j=1}^r 1/d_j}{\prod_k m_k!},$
because $\sum_{j=1}^r d_j = n$ implies $\prod_{j=1}^r p^{d_j}/p^n = 1$.
Now consider a random permutation of $n$ elements. Let its cycle decomposition have cycles of lengths $d_1, \ldots, d_r$. The number of permutations with this cycle type is
$\frac{n!}{\prod_{j=1}^r d_j \prod_k m_k!},$
where $m_k$ is the number of cycles of the same length $d_k$ (standard combinatorial fact). The total number of permutations is $n!$, so the probability that a random permutation has cycle lengths $d_1,\ldots,d_r$ is
$\frac{n! / (\prod_{j=1}^r d_j \prod_k m_k!)}{n!} = \frac{1}{\prod_{j=1}^r d_j \prod_k m_k!}.$
Comparing with the asymptotic probability $P(d_1,\ldots,d_r)$ for polynomials modulo a large prime $p$, we see that
$P(d_1,\ldots,d_r) \sim \frac{1}{\prod_{j=1}^r d_j \prod_k m_k!},$
which is exactly the same as the probability for the cycle decomposition of a random permutation. Therefore, the degree distribution of irreducible factors of a random polynomial modulo a large prime is asymptotically the same as the cycle length distribution of a random permutation on $n$ elements.
This completes the proof.
∎