系数为$\{-1,0,1\}$的多项式乘积的最大系数

hbghlyj

如果 $f(x),g(x) \in \mathbb{Z}[x]$ 的次数为 $m,n$ 且系数在 $\{-1,0,1\}$ 内，则 $f(x)g(x)$ 的最大系数的最大值为？

hbghlyj

$f(x)g(x) = \sum_{0\le k \leq m+n} x^k \sum_{\substack{i+j=k\\0\le i \leq m\\0\le j \leq n}}f_i g_j$ 的 $x^k$ 系数为 $\sum_{\substack{i+j=k\\0\le i \leq m\\0\le j \leq n}}f_i g_j$
而 $f_i g_j\in\{-1,0,1\}$
所以 $\sum_{\substack{i+j=k\\0\le i \leq m\\0\le j \leq n}}f_i g_j=\sum_{\substack{0\le i \leq m\\0\le k-i \leq n}}f_i g_j=\sum_{\substack{\max(0,k-n)\le i \leq\min(k,m)}}f_i g_j\le 1+\min(k,m)-\max(0,k-n)$
由此可以得出整个多项式的最大系数的上界
$$\max_{0\le k\le m+n}\left(1+\min(k,m)-\max(0,k-n)\right)$$

hbghlyj

设$m\le n$，则$\min(k,m)-\max(0,k-n)=\begin{cases}k&x\le m\\m&m\le x\le n\\m+n-k&x\ge n\end{cases}$
于是
$$\max_{0\le k\le m+n}\left(1+\min(k,m)-\max(0,k-n)\right)=m$$不知对不对