Minimum number of terms resulting from the product of two polynomials with a given number of terms Given two integers ($n$, $m$), what is the smallest number of terms that could result from the product of two polynomials with $n$ and $m$ non-zero terms respectively?
That is, what is the smallest number of non-zero terms that could result from the following product:
$$(a_1 x^{b_1} + \dots + a_n x ^ {b_n})(c_1 x^{d_1} + \dots + c_m x ^ {d_m})$$
where $a_i$ and $c_i$ are non-zero.
The answers to this question show that the answer cannot be $1$ in all cases, but it is obviously less than $n+m$, which should theoretically be the maximum.
 A: Consider $(x - 1)(x^n+ \dotsb + 1) = x^{n+1} -1$
A: I don't have a proof that this is best possible in mind, but I believe for $m,n>1$, $\min{(m,n)}$ can be done using a technique similar to vonbrand's answer using a generalized idea of Fibonacci numbers, the Fibonacci n step numbers: http://mathworld.wolfram.com/Fibonaccin-StepNumber.html
For (m,n) with $1<m\leq n$, consider $$(x^{m-1}+x^{m-2}+...+x-1)(f_0+f_1x+f_2x^2+...+f_{n-1}x^{n-1})$$ where $f_i$ is the $i$th Fibonacci $n-1$ step number. The Fibonacci recurrence relation guarantees that all the terms except the constant term and the $m-1$ terms of degree $n+m-2$ through $n$ cancel out.
A: The minimum is 2 for all cases. For even number of terms, there is an elegant factorization solution, but for odd number of terms, my solution made use of complex roots.
Let $A$ have $a$ terms, $B$ have $b$ terms.  $C=A\cdot B$.
We prove that for any $a,b\geq2$, we can always find $A,B$ so that $C$ has $2$ terms, which is obviously the minimum.

*

*$a$ or $b$ (or both) is even: assume $b$ is even.  \begin{align*}
x^{\frac{ab}{2}}-1&=(x^a-1)\left[(x^a)^{\frac{b}{2}-1}+(x^a)^{\frac{b}{2}-2}+\dots+1\right] \\
&=(x^{a-1}+x^{a-2}+\dots+1)(x-1)\left[(x^a)^{\frac{b}{2}-1}+(x^a)^{\frac{b}{2}-2}+\dots+1\right]
\end{align*} Let $A=x^{a-1}+x^{a-2}+\dots+1$, $B=(x-1)\left[(x^a)^{\frac{b}{2}-1}+(x^a)^{\frac{b}{2}-2}+\dots+1\right]$.  It's easy to check that $B$ has $b$ terms, since no terms in the expansion will cancel out.  

*Both $a$ and $b$ odd: (I did not find a similar proof like (1), so I used complex roots.)  We demonstrate with the example $a=3,b=7$.  The general case only substitutes numbers as $a$s and $b$s.  
We wish to construct $A$ to have $2$ roots and $B$ to have $b$ roots.  Plot the $8$ complex number solutions of $x^8+1=0$ on the unit circle.  Name them $z_1,z_2,\dots,z_8$.
Because $a,b$ is odd, $z_5=\overline{z_4},z_6=\overline{z_3},\dots,z_8=\overline{z_1}$  Let \begin{gather*}
A=(x-\mathcal{E}_1)(x-\overline{\mathcal{E}_1}) \\
B=(x-\mathcal{E}_2)(x-\overline{\mathcal{E}_2})(x-\mathcal{E}_3)(x-\overline{\mathcal{E}_3})(x-\mathcal{E}_4)(x-\overline{\mathcal{E}_4})
\end{gather*}  It's easy to check that both $A$ and $B$ have non-zero co-efficients.  

Note: the complex number solution can yield elementary factorization solutions for $a=3,b=3$.  \begin{gather*}
\underbrace{x^4+4}_\text{2 terms}=(\underbrace{x^2+2x+2}_\text{3 terms})(\underbrace{x^2-2x+2}_\text{3 terms})\tag{*} \\
A=\left((x-\left(\frac{\sqrt{2}}{2}+\frac{\sqrt{2}}{2}i\right)\right)\left(x-\left(\frac{\sqrt{2}}{2}-\frac{\sqrt{2}}{2}i\right)\right)=x^2-\sqrt{2}x+1
\end{gather*}  Similarly, we calculuate $$B=x^2+\sqrt{2}x+1$$  So $$x^4+1=(x^2+\sqrt{2}x+1)(x^2-\sqrt{2}x+1)$$  Let $x=\frac{\sqrt{2}}{2}t$ and we'd get: $$\frac{t^4}{4}+1=\left(\frac{t^2}{2}+t+1\right)\left(\frac{t^2}{2}-t+1\right)$$ which is exactly (*).
For a handwritten version of this answer with diagrams, see photo 1.
