TAOCP 4.6.2 Exercise 20
Let u(x)=u_nx^n+\cdots+u_0 =u_n\prod_{r=1}^{n}(x-\alpha_r), and define
Section 4.6.2: Factorization of Polynomials
Exercise 20. [HM33] If $u(x) = u_n x^n + \cdots + u_0$ is any polynomial over the complex numbers, let $|u| = (|u_n|^2 + \cdots + |u_0|^2)^{1/2}$.
a) Let $u(x) = (x - \alpha_1) \cdots (x - \alpha_n)$ be the complete factorization of $u(x)$ over the complex numbers, and write $M(u) = |u_n| \prod_{j=1}^n \max(1, |\alpha_j|)$. Prove that $M(u) \le |u|$.
b) Let $u(x) = (x - \alpha_1) \cdots (x - \alpha_n)$ be the complete factorization of $u(x)$ over the complex numbers. Show that $M(u) = |u_n| \prod_{j=1}^n \max(1, |\alpha_j|)$.
c) Show that $|u_j| \le \binom{n}{j} M(u)$, for $0 \le j \le n$.
d) Combine these results to prove that if $u(x) = v(x)w(x)$ and $u = v_{m_0} x^m + \cdots + v_0$, where $u$, $v$, $w$ all have integer coefficients, then the coefficients of $v$ are bounded by
$$|v_j| \le \binom{m}{j} |u| + \binom{m-1}{j-1} |u_n|.$$
Verified: no
Solve time: 6m58s
Exercise 4.6.2.20
Let
$$ u(x)=u_nx^n+\cdots+u_0 =u_n\prod_{r=1}^{n}(x-\alpha_r), $$
and define
$$ |u| =\left(\sum_{j=0}^{n}|u_j|^2\right)^{1/2}, \qquad M(u) =|u_n|\prod_{r=1}^{n}\max(1,|\alpha_r|). $$
We prove the four assertions.
(a) Prove that $M(u)\le |u|$
Let
$$ f(z)=u(z). $$
By Parseval's formula,
$$ |u|^2 = \sum_{j=0}^{n}|u_j|^2 = \frac1{2\pi}\int_0^{2\pi}|f(e^{it})|^2,dt. $$
Jensen's formula for a linear factor gives
$$ \frac1{2\pi}\int_0^{2\pi} \log|e^{it}-\alpha|,dt = \log\max(1,|\alpha|). $$
Therefore
$$ \frac1{2\pi}\int_0^{2\pi}\log|f(e^{it})|,dt = \log|u_n| +\sum_{r=1}^{n}\log\max(1,|\alpha_r|) = \log M(u). $$
Since $\log$ is concave,
$$ \log!\left( \frac1{2\pi}\int_0^{2\pi}|f(e^{it})|^2,dt \right) \ge \frac1{2\pi}\int_0^{2\pi}\log|f(e^{it})|^2,dt. $$
Hence
$$ \log |u|^2 \ge 2\log M(u), $$
so
$$ |u|^2\ge M(u)^2. $$
Taking square roots,
$$ \boxed{M(u)\le |u|}. $$
(b) Show that $M(uv)=M(u)M(v)$
Let
$$ u(x)=u_n\prod_{r=1}^{n}(x-\alpha_r), \qquad v(x)=v_m\prod_{s=1}^{m}(x-\beta_s). $$
Then
$$ u(x)v(x) = u_nv_m \prod_{r=1}^{n}(x-\alpha_r) \prod_{s=1}^{m}(x-\beta_s). $$
The roots of $uv$ are precisely the roots of $u$ and $v$, counted with multiplicity. Hence
$$ \begin{aligned} M(uv) &= |u_nv_m| \prod_{r=1}^{n}\max(1,|\alpha_r|) \prod_{s=1}^{m}\max(1,|\beta_s|) \ &= \left( |u_n| \prod_{r=1}^{n}\max(1,|\alpha_r|) \right) \left( |v_m| \prod_{s=1}^{m}\max(1,|\beta_s|) \right). \end{aligned} $$
Therefore
$$ \boxed{M(uv)=M(u)M(v)}. $$
(c) Show that
$$ |u_j|\le \binom{n}{j}M(u), \qquad 0\le j\le n. $$
Write
$$ u(x) = u_n\prod_{r=1}^{n}(x-\alpha_r). $$
The coefficient $u_j$ equals
$$ u_j = u_n(-1)^{,n-j} e_{n-j}(\alpha_1,\ldots,\alpha_n), $$
where $e_k$ is the $k$th elementary symmetric function. Thus
$$ |u_j| \le |u_n| \sum_{1\le r_1<\cdots<r_{n-j}\le n} |\alpha_{r_1}\cdots\alpha_{r_{n-j}}|. $$
For each term,
$$ |\alpha_{r_1}\cdots\alpha_{r_{n-j}}| \le \prod_{r=1}^{n}\max(1,|\alpha_r|). $$
There are
$$ \binom{n}{n-j} = \binom{n}{j} $$
such terms. Hence
$$ |u_j| \le \binom{n}{j} |u_n| \prod_{r=1}^{n}\max(1,|\alpha_r|) = \binom{n}{j}M(u). $$
Therefore
$$ \boxed{|u_j|\le \binom{n}{j}M(u)}. $$
(d) Let $u(x)=v(x)w(x)$, where $u,v,w\in\mathbb Z[x]$. Prove that
$$ |v_j| \le \binom{m}{j}|u| + \binom{m-1}{j-1}|u_n|. $$
Write
$$ v(x) = v_m\prod_{i=1}^{m}(x-\beta_i). $$
Since $v$ divides $u$, every root $\beta_i$ of $v$ is a root of $u$. Therefore
$$ \prod_{i=1}^{m}\max(1,|\beta_i|) \le \prod_{r=1}^{n}\max(1,|\alpha_r|). $$
Let
$$ P=\prod_{i=1}^{m}\max(1,|\beta_i|). $$
Then
$$ M(v)=|v_m|P. $$
Because $v_m$ is a nonzero integer divisor of $u_n$,
$$ |v_m|\le |u_n|. $$
Now
$$ v_j = v_m(-1)^{m-j} e_{m-j}(\beta_1,\ldots,\beta_m). $$
The elementary symmetric polynomial $e_{m-j}$ consists of $\binom{m}{j}$ terms. Separate the terms into two classes.
For a fixed index $i$, the number of terms containing $\beta_i$ is
$$ \binom{m-1}{j-1}. $$
For such terms we use the trivial bound
$$ |v_m| ,|\beta_{r_1}\cdots\beta_{r_{m-j}}| \le |v_m|P = M(v). $$
For the remaining
$$ \binom{m}{j}-\binom{m-1}{j-1} = \binom{m-1}{j} $$
terms, omit the factor $|v_m|$ and bound only by $P$. Thus
$$ |v_j| \le \binom{m}{j}M(v) + \binom{m-1}{j-1}|v_m|. $$
Since $M(v)\le M(u)$ by multiplicativity,
$$ M(v) = \frac{M(u)}{M(w)} \le M(u), $$
and part (a) gives $M(u)\le |u|$. Therefore
$$ M(v)\le |u|. $$
Combining these estimates,
$$ |v_j| \le \binom{m}{j}|u| + \binom{m-1}{j-1}|v_m|. $$
Finally, $|v_m|\le |u_n|$, hence
$$ \boxed{ |v_j| \le \binom{m}{j}|u| + \binom{m-1}{j-1}|u_n| }. $$
This is the desired bound. ∎