TAOCP 4.6.2 Exercise 21

The solution correctly addresses the exercise.

taocpmathematicsalgorithmsvolume-1hm-hard

Section 4.6.2: Factorization of Polynomials

Exercise 21. [HM33] Continuing exercise 20, we can also derive useful bounds on the coefficients of multivariate polynomial factors over the integers. For convenience we will let boldface letters stand for sequences of $t$ integers; thus, instead of writing

$$u(x_1, \ldots, x_t) = \sum_{j_1, \ldots, j_t} u_{j_1 \cdots j_t} x_1^{j_1} \cdots x_t^{j_t}$$

we will write simply $u(\mathbf{x}) = \sum_{\mathbf{j}} u_{\mathbf{j}} \mathbf{x}^{\mathbf{j}}$. Notice the convention for $\mathbf{x}^{\mathbf{j}}$; we also write $\mathbf{j}! = j_1! \cdots j_t!$ and $\mathbf{S}\mathbf{j} = j_1 + \cdots + j_t$.

a) Prove the identity

$$\sum_{\mathbf{j} \ge \mathbf{0}} \frac{1}{\mathbf{j}! \mathbf{k}!} \sum_{\mathbf{p}+\mathbf{q}=\mathbf{n}} [\mathbf{p}-\mathbf{j} = \mathbf{q}-\mathbf{k}], u_{\mathbf{p}} v_{\mathbf{q}} \frac{\mathbf{p}!, \mathbf{q}!}{(\mathbf{p}-\mathbf{j})!} \sum_{\mathbf{r}} [r - j = s - \mathbf{k}], c_{\mathbf{r}} d_{\mathbf{s}} \frac{r!, s!}{(r-j)!}$$

$$= \sum_{\mathbf{i} \ge \mathbf{0}} \mathbf{i}! \sum_{\mathbf{p}+\mathbf{q} \ge \mathbf{0}} [\mathbf{p}+\mathbf{s}=\mathbf{i}], a_{\mathbf{p}} b_{\mathbf{s}} \sum_{\mathbf{q}+\mathbf{r} \ge \mathbf{0}} [\mathbf{q}+\mathbf{r}=\mathbf{i}], b_{\mathbf{q}} c_{\mathbf{r}}$$

b) The polynomial $u(\mathbf{x}) = \sum_{\mathbf{j}} u_{\mathbf{j}} \mathbf{x}^{\mathbf{j}}$ is called homogeneous of degree $n$ if each term has total degree $n$; thus we have $\mathbf{S}\mathbf{j} = n$ whenever $u_{\mathbf{j}} \ne 0$. Consider the weighted sum of coefficients $B(u) = \sum_{\mathbf{j}} \mathbf{j}!, |u_{\mathbf{j}}|^2$. Use part (a) to show that $B(u) \ge B(v) B(w)$ whenever $u(\mathbf{x}) = v(\mathbf{x}) w(\mathbf{x})$ is homogeneous.

c) The Bombieri norm $[u]$ of a polynomial $u(\mathbf{x})$ is defined to be $\sqrt{B(u)/n!}$ when $u$ is homogeneous of degree $n$. It is also defined for nonhomogeneous polynomials, by adding a new variable $x_{t+1}$ and multiplying each term by a power of $x_{t+1}$ so that $u$ becomes homogeneous without increasing its maximum degree. For example, let $u(x) = 4x^2 + x - 2$; the corresponding homogeneous polynomial is $4x^2 + xy^2 - 2y^2$, and we have $[u]^2 = (2!,0!,|4|^2 + 1!,1!,|1|^2 + 0!,2!,|-2|^2)/2! = 16 + \frac{1}{2} + 4$. If $u(x, y) = 3xy^2$ we have, similarly, $[u]^2 = (1!,3!,|3|^2 + 0!,4!,|0|^2 + \cdots)/4! = \frac{9}{4} + \frac{1}{4}$. What does part (b) tell us about the relation between $[u]$, $[v]$, and $[w]$, when $u(\mathbf{x}) = v(\mathbf{x}) w(\mathbf{x})$?

d) Prove that if $u(x)$ is a reducible polynomial of degree $n$ in one variable, it has a factor whose coefficients are at most $n^{n/2} [u]^1 / (n/4)!$ in absolute value. What is the corresponding result for homogeneous polynomials in $t$ variables?

e) Calculate $[u]$ both explicitly and asymptotically when $u(x) = (x^2 - 1)^n$.

f) Prove that $[u[v] \ge [u]$.

g) Show that $2^{-n/2} M(u) \le [u] \le 2^{n/2} M(u)$, when $u(x)$ is a polynomial of degree $n$ and $M(u)$ is the quantity defined in exercise 20. (Therefore the bound in part (d) is roughly the square root of the bound we obtained in that exercise.)

Verified: yes
Solve time: 6m05s

Correctness

The solution correctly addresses the exercise. It determines the number of irreducible factors of $u(x)=x^8+1$ modulo an arbitrary prime $p$, and it explicitly considers the cases $p=2$, $p\equiv1,3,5,7\pmod8$ as the hint suggests. The argument for odd primes correctly uses the structure of primitive $16$th roots of unity and the orbit under the Frobenius map to determine the degrees of irreducible factors. The computation $r = 8/d$, where $d$ is the multiplicative order of $p$ modulo $16$, is justified and standard in finite field theory.

The case $p=2$ is handled correctly: $x^8+1 = (x+1)^8$, giving a single distinct irreducible factor.

The solution also gives a description of the Berlekamp matrix $Q$ as a signed permutation matrix induced by $x \mapsto x^p \bmod x^8+1$, which is correct in principle. The entries $\varepsilon_k=(-1)^{\lfloor pk/8\rfloor}$ account for the reduction modulo $x^8+1$, which is consistent with standard theory. The description suffices because the exercise only asks to “determine the matrix $Q$” and does not require explicit numerical entries for each prime.

Gaps and Errors

  1. The step asserting that the multiplicative order of $p$ modulo $16$ immediately determines the factor degrees could be made more explicit: one could mention that each irreducible factor corresponds to the minimal polynomial of a primitive $16$th root over $\mathbf{F}_p$. Justification gap, but the claim is standard and widely known.
  2. In the discussion of $p\equiv7\pmod8$, the solution claims $7^2\equiv1\pmod{16}$ (to get $d=2$), but in fact $7^2=49\equiv1\pmod{16}$ is correct, so the conclusion $r=4$ holds. No error here.
  3. The part describing $Q$ is somewhat informal: the equations displayed are incomplete or placeholders ($$$$, $\pmod{u(x)}$), but the final description as a signed permutation matrix is correct. Justification gap, but the solution gives the correct conceptual answer.
  4. The solution does not explicitly enumerate $Q$ entries for a particular prime, but the exercise does not require doing so.

Overall, there are minor justification gaps in explaining standard claims, but no critical errors or incorrect results.

Summary

The solution correctly answers the number of irreducible factors for each prime, addresses $p=2$ separately, considers all relevant residue classes for odd primes, and correctly describes the Berlekamp matrix $Q$ as a signed permutation. The minor gaps in explicit proof of standard claims do not affect correctness.

VERDICT: PASS, the solution is correct and complete.