TAOCP 4.6.2 Exercise 2

Section 4.6.2: Factorization of Polynomials

Exercise 2. ▶ [M25] (a) Show that any monic polynomial $u(x)$, over a unique factorization domain, may be expressed uniquely in the form

$$u(x) = v(x)^2 w(x),$$

where $w(x)$ is squarefree (has no factor of positive degree of the form $d(x)^2$) and both $v(x)$ and $w(x)$ are monic. (b) (E. R. Berlekamp.) How many monic polynomials of degree $n$ are squarefree modulo $p$, when $p$ is prime?

Verified: yes
Solve time: 3m

Solution

(a) Let $R$ be a unique factorization domain (UFD), and let $u(x) \in R[x]$ be monic. Factor $u(x)$ into irreducible polynomials in $R[x]$:

$u(x) = \prod_{i=1}^k p_i(x)^{\alpha_i},$

where each $p_i(x)$ is monic and irreducible and $\alpha_i \ge 1$. Define

$v(x) = \prod_{i=1}^k p_i(x)^{\lfloor \alpha_i/2 \rfloor}, \qquad w(x) = \prod_{i=1}^k p_i(x)^{\alpha_i - 2\lfloor \alpha_i/2 \rfloor}.$

By construction, $v(x)$ and $w(x)$ are monic, $u(x) = v(x)^2 w(x)$, and $w(x)$ is squarefree because each exponent $\alpha_i - 2\lfloor \alpha_i/2 \rfloor$ is either 0 or 1.

To prove uniqueness, suppose $u(x) = \tilde v(x)^2 \tilde w(x)$ is another such factorization with $\tilde v(x)$ and $\tilde w(x)$ monic and $\tilde w(x)$ squarefree. Comparing irreducible factors, for each $i$ the exponent of $p_i(x)$ in $v(x)^2 w(x)$ must equal its exponent in $\tilde v(x)^2 \tilde w(x)$. If $\alpha_i$ is even, the exponent appears entirely in $v(x)^2$, so $\tilde v(x)$ must contain $p_i(x)^{\alpha_i/2}$. If $\alpha_i$ is odd, then $\tilde w(x)$ must contain $p_i(x)$, and $\tilde v(x)$ contains $p_i(x)^{(\alpha_i-1)/2}$. In every case, $\tilde v(x) = v(x)$ and $\tilde w(x) = w(x)$, proving uniqueness. This completes part (a). ∎

(b) Let $p$ be prime. We count the number of monic, squarefree polynomials of degree $n$ modulo $p$. Denote the set of all monic polynomials of degree $n$ by $M_n$, so $|M_n| = p^n$. Let $S_n$ be the set of monic, squarefree polynomials of degree $n$.

We use the standard inclusion–exclusion principle. Let $P$ be the set of monic irreducible polynomials over $\mathbb{F}_p$, and let $P_k$ be the subset of $P$ of degree dividing $k$. A monic polynomial $u(x)$ is not squarefree if and only if there exists an irreducible $f(x)$ such that $f(x)^2 \mid u(x)$.

Define the generating function

$F(t) = \sum_{n=0}^{\infty} |S_n| t^n.$

The unique factorization of monic polynomials over $\mathbb{F}_p$ implies

$\sum_{n=0}^{\infty} p^n t^n = \prod_{f \text{ monic, irreducible}} \frac{1}{1 - t^{\deg(f)}}.$

Squarefree monic polynomials correspond to choosing each irreducible factor at most once. Therefore

$\sum_{n=0}^{\infty} |S_n| t^n = \prod_{f \text{ monic, irreducible}} (1 + t^{\deg(f)}).$

Taking logarithms modulo $p$ is unnecessary; we can count directly. For degree $n$, denote $\mu(d)$ the Möbius function. Then the number of monic, squarefree polynomials of degree $n$ is

$|S_n| = \sum_{k=0}^n \mu(k) p^{n-k}.$

A simpler formula is obtained recursively: Let $p_n$ be the number of monic polynomials of degree $n$, $p_n = p^n$. Let $s_n$ be the number of squarefree monic polynomials of degree $n$. Each monic polynomial of degree $n$ can be written uniquely as $v(x)^2 w(x)$ with $w(x)$ squarefree, as in part (a). If $\deg(v) = m$, then $\deg(w) = n - 2m$, so

$p^n = \sum_{m=0}^{\lfloor n/2 \rfloor} p^m s_{n-2m}.$

Solving recursively for $s_n$, we find

$s_0 = 1, \quad s_1 = p, \quad s_n = p^n - \sum_{m=1}^{\lfloor n/2 \rfloor} p^m s_{n-2m}, \quad n \ge 2.$

This recurrence counts all squarefree monic polynomials modulo $p$. This completes part (b). ∎