# 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$?

I have been stuck with this question for… quite sometime. Implications are mentioned after my question.

Is it true that if two real polynomials $$P(x), Q(x)$$, have their product equal to a 0-1 polynomial (e.g. $$1+x+x^5+x^{42}$$), and their coefficients are assumed to be non-negative, and are both monic, then these coefficients are also 0's and 1's?

I can prove it when the product is a reciprocal polynomial (a textbook case is $$1+x+x^2+x^3+\cdots+x^n$$), but I cannot manage to drop this condition.

Beware that there may exist factors with negative coefficients, the assumption is that both $$P, Q$$ do not.

This would explain why Linear Programming in the real fields seems to always find 0-1 factorizations in some tiling problems in dim. 1 (I know this has been recently disproved in higher dimension). This is a highly rewarding occurrence but it would be nice to understand why or at least to prove it…

• You probably need an extra assumption, like assuming that $P$ and $Q$ are monic; otherwise, take $P(x)=2x$, $Q(x)=x/2$. – W-t-P Aug 16 '19 at 14:40
• Of course you're right, forgot to mention it. I correct the question. – Emmanuel Amiot Aug 17 '19 at 15:43
• Note that I've asked this on MO: mathoverflow.net/questions/339137/… – Sil Aug 25 '19 at 11:38

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

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