The coefficients of a product of monic polynomials are $0$ and $1$; if the polynomials' coefficients are non-negative, must they also be $0$ and $1$?

Solution 1:

Observation:

Suppose that $P(x)Q(x) = M(x)$, where $M$ is a $0-1$ polynomial and $P$, $Q$ are polynomials with non-negative coefficients as in your question. Define the following property of this product:

Property 1: For each term ($x^n$ say) in $M$, there is unique pair of terms in $P$ and $Q$ which uniquely multiply together to make this term.

Firstly, it seems that the conjecture is easy to prove with the assumption that property 1 holds.

Secondly, if the conjecture does hold (so that $P$ and $Q$ are necessarily both 0-1) then property 1 must hold for the product (i.e. every product).

Solution 2:

(Not an answer, but too big for a comment.)

Here is a nice probability problem.

Suppose we have two six-sided dice, with faces numbered $1,\dots,6$. But these are not fair dice, they are weighted. That is, probability of outcomes $1,\dots,6$ for the first die are some nonnegative numbers $a_1,\dots,a_6$, respectively, and for the second die $b_1,\dots,b_6$. Can we fix these weights somehow so that, when the two dice are rolled, all outcomes $2,\dots,12$ for the sum are equally likely?

Answer: no. You can probably find a solution on line.

Algebraically, it means:
The polynomial $\sum_{j=0}^{10} x^j$ cannot be factored as $(a_1+a_2x+\cdots+a_6x^5)(b_1 +b_2x+\cdots+b_6x^5)$ with all coefficients nonnegative.