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

Question

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…

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

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

Answer 3

This would follow from a combinatorial proposition (which I propose but maybe is obviously false, I haven't thought much yet but if $ P (t) $ has degree $ \leq 6 $ I verified it.) This can be checked to be true or false in any given situation.

The question is whether or not such a situation exists.

I give a definition first

1. A subset $ X $ of $ \mathbb N \times \mathbb N $ ($ \mathbb N $ the natural numbers) is said independent if the sum map from $ X $ to $ \mathbb N $ is injective,
2. strongly dependent if the partition given by + in $ X $ (the counterimages) has all parts with at least 2 elements,
3. Two sets $ A, B \subset \mathbb N $ are independent if $ A \times B $ is independent.

The question is whether there are two finite sets $ A, B \subset \mathbb N $ both containing 0, with $ h, k $ the respective maxima, which decompose as $ A = A_0 \cup A_1, \ B = B_0 \cup B_1 $ disjoint unions with $ 0, h \in A_0 $ and $ 0, k \in B_0 $.

1. With $ A_0, B_0 $ independent
2. $X:= A_1 \times B \cup A \times B_1 $ not empty and strongly dependent
3. the image $ C_0 $ of the sum applied to $ A_0 \times B_0 $ is disjoint from the image $ C_1 $ of the sum applied to $ A_1 \times B \cup A \times B_1 $? In particular $ A_0 \times B_0 $ is disjoint from $ A_1 \times B \cup A \times B_1 $.

The link is this. Let $ A $ be the support of $ P (t) $, $ B $ the support of $ Q (t) $ and $ C $ the support of $ R (t)= P (t) Q (t) $, then $C=A+B$. Let $ A_0 $ be the subset where the coefficients are equal to 1 likewise $ B_0 $ and $ A_1, B_1 $ the complements (where the coefficients are non-zero and $<1$). Then $ C $ decomposes into $ C_0 \cup C_1 $ where $ C_0 $ is the contribution of the terms in $ A_0, B_0 $ and these sets satisfy the previous properties.

So let us assume there is an example with $C_1\neq\emptyset$ the hope is to arrive to a contradiction. We start building such an example by first choosing the minimum $i\in A_1$. Note, if $ i = \min (A_1) $ then $ i = \min (A_1) = \min (B_1) $. In fact, then $ i = i + 0 \in C_1 $ and there must be another pair $ (a, b) \mid a + b = i, b \neq 0 $. If $ b <i $ then the same happens by induction. By duality $h- \max (A_1) = k-\max(B_1) $

Another observation, the problem can be dualized.

If $ R (t) = P (t) Q (t) $ with $ P (t), Q (t) $ of degrees $ h, k $ we have $$ t ^ {h + k} R (1 / t) = t ^ {h} P (1 / t) t ^ {k} Q (1 / t) $$ this implies that one can always reduce to case $ i = \min (A_1) $ with $ 1 \leq i <h / 2 $. So for instance if $h=6<k$ ($h=k$ is not possible) we have only two cases to analyse $i=1,2$ ($i=3$ is excluded since 3+3=6).

The argument looks like some sort of Sudoku!

$i=3$ is not possible since $6=3+3$.

If $i=2$ we must have $(2,0), (0,2)\in +^{-1}(2)\in X$. So $(2,2)\in X:= A_1 \times B \cup A \times B_1 $ and $+^{-1}(4)$ must have at least another element out of $(0,4), (1,3),(3,1),(4,0)$ but $(0,4), (4,0)$ in $X$ can be excluded otherwise $6=2+4\in A_1$. Say $3\in A_1$ so $1\in B_0, 3\notin B, 5\notin A$ then $(3,2)\in X$ and so there must be $(0,5)\in X$. \begin{equation}\label{pp} \begin{matrix} A:&0&\emptyset &2&3&\emptyset& \emptyset&6\\ B :&0&1&2&\emptyset &\emptyset &5&\emptyset\end{matrix} \end{equation} Now clearly the dual solution has $i=3$ which is not possible.