TAOCP 4.6 Exercise 3
By equation (4), w_k=u_0v_k+u_1v_{k-1}+\cdots+u_kv_0, where coefficients with indices exceeding $s$ are taken to be $0$.
Section 4.6: Polynomial Arithmetic
Exercise 3. [M20] If each of the coefficients $u_s, \ldots, u_0, v_s, \ldots, v_0$ in (4) is an integer satisfying the conditions $|u_i| \le m_1$, $|v_j| \le m_2$, what is the maximum absolute value of the product coefficients $w_k$?
Verified: yes
Solve time: 1m09s
Solution
By equation (4),
$$ w_k=u_0v_k+u_1v_{k-1}+\cdots+u_kv_0, $$
where coefficients with indices exceeding $s$ are taken to be $0$. Since both polynomials have degree at most $s$, the number of nonzero terms in this sum is
$$ N_k= \begin{cases} k+1, & 0\le k\le s,\[4pt] 2s-k+1, & s\le k\le 2s. \end{cases} $$
Each summand satisfies
$$ |u_i v_{k-i}| \le |u_i|,|v_{k-i}| \le m_1m_2. $$
Hence, by the triangle inequality,
$$ |w_k| \le \sum |u_i v_{k-i}| \le N_k,m_1m_2. $$
Therefore
$$ |w_k| \le \begin{cases} (k+1)m_1m_2, & 0\le k\le s,\[4pt] (2s-k+1)m_1m_2, & s\le k\le 2s. \end{cases} $$
The largest value of $N_k$ occurs when $k=s$, for which
$$ N_s=s+1. $$
Consequently,
$$ |w_k|\le (s+1)m_1m_2 \qquad (0\le k\le 2s). $$
This bound is attained. Take
$$ u_i=m_1,\qquad v_j=m_2 \qquad (0\le i,j\le s). $$
Then
$$ w_s = \sum_{i=0}^{s} u_i v_{s-i} = \sum_{i=0}^{s} m_1m_2 = (s+1)m_1m_2. $$
Hence the maximum possible absolute value of a product coefficient is
$$ \boxed{(s+1)m_1m_2}. $$
∎