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…

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


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

| cite | improve this answer | |

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

| cite | improve this answer | |

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.