# 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.

• What do you mean by "represent the size"? This is rather ambiguous, but I assume that $m$ and $n$ are, respectively, the number of terms of those two polynomials. Is this correct? It would also help to know where the coefficients come from. For example, are they integer, real, or complex? – A.P. Jan 8 '16 at 22:58
• @AP Yes, sorry, $m$ and $n$ are the number of terms in the polynomials. – thesquaregroot Jan 8 '16 at 23:03
• Are you only counting nonzero terms? Are we dealing with real polynomials, or polynomials over a field, or what exactly? – Sean English Jan 10 '16 at 17:33
• @SE318 Yes, only non-zero terms. I don't have a specific criteria for the coefficients, though so far I've thought of them as being integers. – thesquaregroot Jan 10 '16 at 17:55

Consider $(x - 1)(x^n+ \dotsb + 1) = x^{n+1} -1$
• This shows that for cases of the form $(2, n)$ the answer is $2$, but I'm not sure I see how this leads to a more general solution? I could see this maybe being expanding to handle even cases, by treating the first polynomial as the product of $(x-1)$ and the complement of the prior result (i.e. $x^{n+1} + 1$), so I could see $(2k, n) \rightarrow 2$ but I'm not even sure that would necessarily hold for all $n$. – thesquaregroot Jan 9 '16 at 19:42
• @thesquaregroot, I believe the cyclotomic polynomials (i.e., factors of $x^n - 1$) provide examples. – vonbrand Jan 9 '16 at 21:35
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.