1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – A.P. Jan 8 '16 at 22:58
  • $\begingroup$ @AP Yes, sorry, $m$ and $n$ are the number of terms in the polynomials. $\endgroup$ – thesquaregroot Jan 8 '16 at 23:03
  • $\begingroup$ Are you only counting nonzero terms? Are we dealing with real polynomials, or polynomials over a field, or what exactly? $\endgroup$ – Sean English Jan 10 '16 at 17:33
  • $\begingroup$ @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. $\endgroup$ – thesquaregroot Jan 10 '16 at 17:55
0
$\begingroup$

Consider $(x - 1)(x^n+ \dotsb + 1) = x^{n+1} -1$

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – thesquaregroot Jan 9 '16 at 19:42
  • $\begingroup$ @thesquaregroot, I believe the cyclotomic polynomials (i.e., factors of $x^n - 1$) provide examples. $\endgroup$ – vonbrand Jan 9 '16 at 21:35
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.