# How do you quickly determine which coefficients are greater than zero when multiplying two univariate positive polynomials?

Suppose that I have two polynomials with a degree of $$n$$, $$A(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_0$$ and $$B(x) = b_nx^n + b_{n-1}x^{n-1} + ... + b_0$$ and the coefficients of these polynomials are zero or greater. Suppose I multiply $$A(X)$$ and $$B(x)$$, $$C(x) = A(x)B(x)$$.

For the polynomial $$C(x)$$, how do I determine if the term $$c_i$$ is zero or greater? What is the fastest algorithm for determining whether for all terms $$c_i$$ if it is zero or nonzero?

• I m sorry, I am slow and do not get your question. If $A$ and $B$ have positive coefficients, then so does $C$... What are you not telling me? – András Bátkai Dec 3 '18 at 6:38
• $A(x)$ and $B(x)$ only consists of coefficients that are either zero and greater than zero. For example, let $A(x) = x^ 2$ and $B(x) = x^2 + 1$. As a result, $A(x) B(x) = x^4 + x^2 + 1$. We notice from this result that the coefficents that are zero are terms $x^3$ and $x$. I was wondering if there is there is a fast polynomial, possibly faster than $O(nlogn)$, to compute the coefficients that would be zero. – mtber75 Dec 3 '18 at 6:50
• Well, there is an obvious linear-time ($O(i)$) algorithm: $c_i=0$ if and only if for each $j\le i$, $a_j=0$ or $b_{i-j}=0$. Since the answer depends on all these coefficients, you have at least to read them, hence you cannot make it significantly faster. – Emil Jeřábek Dec 3 '18 at 8:00
• It may be easier to write the question as follows: let $A, B$ be finite sets of nonnegative integers; is there a fast way to determine $C = \{a + b|a \in A, b \in B\}$? This is equivalent, by making $A$ the set of nonzero coefficients of $A(x)$, and similarly for $B,C$. – user44191 Dec 3 '18 at 8:00
• @EmilJeřábek I think mtber75 is looking for an algorithm to cover all of the $c_i$ at once, not one at a time. In that case, the naive algorithm takes $O(n^2)$ – user44191 Dec 3 '18 at 8:04

Since polynomial multiplication is essentially (non-cyclic) convolution, and for arbitrary polynomials $$A(x),B(x)$$, the fastest known convolution algorithms (based on the fast fourier transform) have complexity $$O(d \log d)$$ where $$d=\max\{\deg A,\deg B\},$$ without assumptions on the structure of the zero coefficients of $$A$$ and $$B,$$ there can't be a faster algorithm without any breakthroughs in algorithms computing convolutions.
Edit: In the light of the comments, I now realize that it is correct one does not need to compute the full convolution. Modeling the nonzero coefficients of $$A,B$$ as subsets $$S_A,S_B,$$ of $$\{1,\ldots,d\}$$ the question can be related to computing properties of the sumset $$S_A+S_B\subset \{1,2,\ldots,2d\}.$$
It seems to me that in general this can be done in time $$w_A w_B$$ in the worst case where $$w_A=\# S_A,$$ is the weight (no. of nonzero coefficients) of the polynomial or the cardinality of $$S_A,$$ etc. So certainly, if $$w_A w_B this would give an improvement.
If the specific coefficient was $$c_i,$$ and we were only interested in whether $$c_i$$ was zero, then one would only need to consider the sets $$S_A \cap \{0,1,2,\ldots,c_i\}$$ and $$S_b \cap \{0,1,2,\ldots c_i\}$$ and by scanning forward in one and backward in the other set, while looking for two terms which sum to $$c_i,$$ one could actually determine if $$c_i$$ was nonzero or not in $$O(c_i)$$ time.