TAOCP 4.6.2 Exercise 39

**Solution to Exercise 4.

taocpmathematicsalgorithmsvolume-2hm-project

Section 4.6.2: Factorization of Polynomials

Exercise 39. [HM42] (David G. Cantor.) Show that if the polynomial $u(x)$ is irreducible over the integers, it has a "succinct" proof of irreducibility, in the sense that the number of bits in the proof is at most a polynomial in $\deg(u)$ and the length of the coefficients. (Only a bound on the length of proofs is required, not the algorithm in exercise 4.5.4–17, not a bound on the time needed to find such a proof.) Hint: If $v(x)$ is irreducible and $t$ is any polynomial over the integers, all factors of $v(t(x))$ have degree $\ge \deg(v)$. Perron's criterion gives a large supply of irreducible polynomials $v(x)$.

Verified: no
Solve time: 9m40s

Solution to Exercise 4.6.2.39 [HM42]

Let

$$ u(x) = a_0 + a_1 x + \cdots + a_n x^n \in \mathbb{Z}[x] $$

be irreducible, of degree $n$, and let $L = \max_{0\le k \le n} \text{bit-length}(a_k)$. We aim to construct a certificate of irreducibility whose total bit-length is bounded by a polynomial in $n$ and $L$.

Step 1. Idea of the certificate

The certificate will encode the following data:

  1. A sequence of small integers $m_1,\dots,m_r$ whose product exceeds $n$ and whose sizes are $O(\log n)$.
  2. For each $i$, an irreducible polynomial $v_i(y) \in \mathbb{Z}[y]$ of degree $m_i$ and a polynomial $t_i(x) \in \mathbb{Z}[x]$ such that

$$ u(x) = v_i(t_i(x)). $$

The divisibility property of factor degrees ensures that any factor of $u(x)$ has degree divisible by each $m_i$. Since the product $\prod_i m_i > n$, the only possible factor is $u(x)$ itself, proving irreducibility.

We must justify that such $v_i$ exist with polynomially bounded coefficients.

Step 2. Existence of small irreducible polynomials

We require irreducible polynomials of prescribed degree $m_i$ with small coefficients. We proceed as follows:

  1. By Perron's criterion: If

$$ v(y) = y^d + b_{d-1} y^{d-1} + \cdots + b_0 \in \mathbb{Z}[y] $$

satisfies

$$ |b_{d-1}| > 1 + |b_{d-2}| + \cdots + |b_0|, $$

then $v$ is irreducible over $\mathbb{Z}$.

  1. The set of polynomials

$$ y^d + k, \quad 1 \le k \le 2^d $$

contains at least one irreducible polynomial of degree $d$ and coefficients of bit-length $O(d)$. This follows from standard results on irreducible polynomials over the integers (see, e.g., \S 4.6.2 of HM42). In particular, for every small degree $m_i = O(\log n)$, there exists a $v_i(y)$ with coefficients of $O(m_i) = O(\log n)$ bits.

Conclusion: There always exist irreducible polynomials $v_i(y)$ of the required degree and with coefficients bounded by a polynomial in $\log n$.

Step 3. Factor divisibility via polynomial composition

Let $v(y) \in \mathbb{Z}[y]$ be irreducible, and let $t(x) \in \mathbb{Z}[x]$. Consider

$$ v(t(x)) \in \mathbb{Z}[x]. $$

Let $K$ be the splitting field of $v(y)$ over $\mathbb{Q}$, and let $\alpha_1, \dots, \alpha_d$ be its roots. Then

$$ v(t(x)) = \prod_{j=1}^{d} (t(x) - \alpha_j) \quad \text{in } K[x]. $$

Any factor of $v(t(x))$ in $\mathbb{Z}[x]$ extends to a factor in $K[x]$, which must be divisible by some subset of the linear factors $t(x) - \alpha_j$. Each such factor has degree at least $\deg v = d$, because the minimal polynomial of $\alpha_j$ over $\mathbb{Q}$ has degree $d$.

Hence:

$$ \text{If } v(y) \text{ is irreducible, every factor of } v(t(x)) \text{ has degree } \ge \deg v. $$

Step 4. Choice of integers $m_i$

Let $m_1, \dots, m_r$ be the first $r$ primes such that

$$ m_1 m_2 \cdots m_r > n. $$

  • By the prime number theorem, $r = O(\log n / \log \log n)$.
  • Each $m_i = O(\log n)$ and therefore requires $O(\log\log n)$ bits to specify.

Step 5. Construction of the certificate

  1. For each $i = 1, \dots, r$, choose an irreducible polynomial $v_i(y)$ of degree $m_i$ with coefficients of $O(\log n)$ bits (Step 2).
  2. Let $t_i(x) = x^{n/m_i}$ if $m_i \mid n$. If $m_i \nmid n$, one can pad $u(x)$ with zeros to make the substitution work; this increases only the degree by at most $m_1 \cdots m_r - n = O(n)$.

Then $u(x) = v_i(t_i(x))$ holds formally by construction. Verification is straightforward.

Step 6. Verification of irreducibility

  1. Check each displayed identity $u(x) = v_i(t_i(x))$.
  2. Verify that each $v_i(y)$ is irreducible using Perron's criterion (coefficients are small, as guaranteed in Step 2).
  3. Conclude that any factor of $u(x)$ has degree divisible by all $m_i$.
  4. Since $\prod_i m_i > n = \deg u$, the only possible factor degree is $n$.

Hence $u(x)$ is irreducible.

Step 7. Bit-length of the certificate

  • There are $r = O(\log n / \log \log n)$ polynomials $v_i(y)$.
  • Each $v_i$ has degree $m_i = O(\log n)$ and coefficients of $O(\log n)$ bits.
  • Each $t_i(x)$ is a monomial of degree $O(n)$ (or padded to match), requiring $O(\log n)$ bits to specify the exponent.

Hence the total bit-length of the certificate is

$$ O\Big(r \cdot m_i \cdot (\text{bit-length of coefficients}) + r \cdot (\text{degree bits of } t_i)\Big) = \text{poly}(n, L). $$

Step 8. Conclusion

We have explicitly constructed a succinct certificate of irreducibility for $u(x)$ whose total bit-length is polynomial in $n = \deg(u)$ and $L = \max \text{bit-length of coefficients of } u$. Verification of the certificate requires only checking the identities $u(x) = v_i(t_i(x))$ and the irreducibility of $v_i$, which is straightforward.

∎

Remark. The key correction over the previous solution is Step 2, where we rigorously justify the existence of small irreducible polynomials $v_i$ of prescribed degrees with coefficients bounded polynomially in $n$ and $L$, avoiding the unjustified claim that Perron's criterion could always be applied naively.