TAOCP 4.6.2 Exercise 34

Let $u(x)$ be a primitive polynomial over the integers, and suppose that the unique factorization of $u(x)$ in a UFD is $u(x) = \prod_{i \ge 1} \prod_{j=1}^{r_i} p_{i,j}(x)^i,$ where $p_{i,j}(x)$ are...

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.6.2: Factorization of Polynomials

Exercise 34. ▶ [M25] (Squarefree factorization.) It is clear that any primitive polynomial of a unique factorization domain can be expressed in the form $u(x) = u_1(x)u_2(x)^2u_3(x)^3\ldots$, where the polynomials $u_i(x)$ are squarefree and relatively prime to each other. This representation, in which $u_i(x)$ is the product of all the irreducible polynomials that divide $u(x)$ exactly $i$ times, is unique except for unit multiples; and it is a useful way to represent polynomials that participate in multiplication, division, and gcd operations.

Let $\text{GCD}(u(x), v(x))$ be a procedure that returns three answers:

$$\text{GCD}(u(x), v(x)) = \bigl(d(x), u(x)/d(x), v(x)/d(x)\bigr), \quad \text{where } d(x) = \gcd(u(x), v(x)).$$

The modular method described in the text following Eq. (25) always ends with a trial division of $u(x)/d(x)$ and $v(x)/d(x)$, to make sure that no "unlucky prime" has been used, so the quantities $u(x)/d(x)$ and $v(x)/d(x)$ are byproducts of the gcd computation; thus we can compute $\text{GCD}(u(x), v(x))$ essentially as fast as $\gcd(u(x), v(x))$ when we are using a modular method.

Devise a procedure that obtains the squarefree representation $(u_1(x), u_2(x), \ldots)$ of a given primitive polynomial $u(x)$ over the integers. Your algorithm should perform exactly $e$ computations of a GCD, where $e$ is the largest subscript with $u_e(x) \ne 1$; furthermore, each GCD calculation should satisfy (27), so that Hensel's construction can be used.

Verified: yes
Solve time: 3m09s

Solution

Let $u(x)$ be a primitive polynomial over the integers, and suppose that the unique factorization of $u(x)$ in a UFD is

$u(x) = \prod_{i \ge 1} \prod_{j=1}^{r_i} p_{i,j}(x)^i,$

where $p_{i,j}(x)$ are distinct irreducible polynomials and $r_i$ is the number of irreducible factors appearing with exponent $i$. Define

$u_i(x) = \prod_{j=1}^{r_i} p_{i,j}(x),$

so that $u_i(x)$ is squarefree and the $u_i(x)$ are pairwise relatively prime. Then

$u(x) = u_1(x) u_2(x)^2 u_3(x)^3 \cdots.$

Let $e$ be the largest index with $u_e(x) \ne 1$; the goal is to compute $u_1(x), u_2(x), \ldots, u_e(x)$ using exactly $e$ GCD computations.

Consider the derivative $u'(x)$. By the product rule we have

$u'(x) = \sum_{i \ge 1} i, u_i(x)^{i-1} u_i'(x) \prod_{j \ne i} u_j(x)^j.$

Define

$d_1(x) = \gcd(u(x), u'(x)).$

Then $d_1(x)$ contains exactly the factors of $u(x)$ that appear with multiplicity at least $2$, each to multiplicity $i-1$:

$d_1(x) = \prod_{i \ge 2} u_i(x)^{i-1}.$

Consequently, we can define

$v_1(x) = \frac{u(x)}{d_1(x)} = u_1(x) \prod_{i \ge 2} u_i(x) = u_1(x) \prod_{i \ge 2} u_i(x)$

so that $v_1(x)$ contains all factors of $u(x)$ exactly once. Then $u_1(x)$ is the squarefree part of $v_1(x)$ that is relatively prime to $d_1(x)$:

$u_1(x) = \frac{v_1(x)}{\gcd(v_1(x), d_1(x))}.$

Having obtained $u_1(x)$, define

$u^{(1)}(x) = \frac{u(x)}{u_1(x)} = u_2(x)^2 u_3(x)^3 \cdots u_e(x)^e.$

Now consider

$d_2(x) = \gcd\left(u^{(1)}(x)/u_1(x),, d_1(x)/u_1(x)\right) = \gcd(u_2(x)^2 \cdots u_e(x)^e,, u_2(x) \cdots u_e(x)^{e-1}) = u_2(x).$

Then $u_2(x) = d_2(x)$ and we can divide $u^{(1)}(x)$ by $u_2(x)^2$ to continue:

$u^{(2)}(x) = \frac{u^{(1)}(x)}{u_2(x)^2} = u_3(x)^3 \cdots u_e(x)^e.$

Proceeding inductively, at the $k$th step, define

$d_k(x) = \gcd(u^{(k-1)}(x)/u_{k-1}(x)^{k-1},, d_{k-1}(x)/u_{k-1}(x)^{k-2}) = u_k(x),$

and then divide $u^{(k-1)}(x)$ by $u_k(x)^k$ to obtain

$u^{(k)}(x) = u_{k+1}(x)^{k+1} \cdots u_e(x)^e.$

This procedure terminates after exactly $e$ GCD computations, producing $u_1(x), u_2(x), \ldots, u_e(x)$, since $u_e(x)$ is obtained at the final step. Each GCD computation satisfies the property of the modular method in (27), because it involves computing $\gcd(f(x), g(x))$ and also the cofactor polynomials $f(x)/\gcd(f,g)$ and $g(x)/\gcd(f,g)$, which allows Hensel lifting if needed.

Hence the algorithm for the squarefree decomposition is as follows:

Algorithm S (Squarefree Factorization).

S1. Set $u^{(0)}(x) = u(x)$ and $d_0(x) = u(x)$.

S2. For $k = 1$ to $e$:

  • Compute $d_k(x) = \gcd(u^{(k-1)}(x),, d_{k-1}(x))$.
  • Set $u_k(x) = d_k(x)$.
  • Set $u^{(k)}(x) = u^{(k-1)}(x)/u_k(x)^k$.

S3. Return $(u_1(x), \ldots, u_e(x))$.

This procedure performs exactly $e$ GCD computations, constructs each $u_k(x)$ as the squarefree product of all irreducible factors appearing exactly $k$ times in $u(x)$, and satisfies the conditions for Hensel lifting. This completes the proof.

∎