# Why polynomials with coefficients $0,1$ like to have only factors with $0,1$ coefficients?

Conjecture. Let $$P(x),Q(x) \in \mathbb{R}[x]$$ be two monic polynomials with non-negative coefficients. If $$R(x)=P(x)Q(x)$$ is $$0,1$$ polynomial (coefficients only from $$\{0,1\}$$), then $$P(x)$$ and $$Q(x)$$ are also $$0,1$$ polynomials.

Is this conjecture true or is there a counter-example? If non-monics were allowed, we would have $$x^2=2x\cdot (x/2)$$, and with negative coefficients we could find for example $$x^4+1=(x^2+\sqrt{2}x+1)(x^2-\sqrt{2}x+1)$$. However with these two conditions the conjecture seems to hold for $$\deg R \leq 12$$ which I did verify by Maple (although a numerical errors in Maple factorization might have caused some false negatives).

This question has been asked on MSE in more than one week ago: https://math.stackexchange.com/questions/3325163/the-coefficients-of-a-product-of-monic-polynomials-are-0-and-1-if-the-polyn, but no solution has been found.

Edit (probability theory reformulation): An interesting alternative reformulation provided in comments by Gro-Tsen/Rémy Oudompheng: Assume $$X,Y$$ are independent random variables supported on a finite subset of the integers, and assume $$Z=X+Y$$ is uniformly distributed on its support: is it necessarily the case that $$X$$ and $$Y$$ are themselves uniformly distributed on their support? (Hence the [pr.probability] and [probability-distributions] tags).

Edit (further verification): As mentioned in the comments, Max Alekseyev has extended the verification to all degrees up to and including $$26$$, which was further improved up to degree $$32$$ by Peter Mueller using Groebner basis calculation (an approach without numerical issues).

• $x^3+1=(x+1)(x^2-x+1)$ is a rational example for why you need nonnegativity.
– RP_
Aug 25 '19 at 12:23
• The conditions at least easily imply that all coefficients of $P$ and $Q$ are in $[0,1]$. Aug 25 '19 at 13:06
• This does not hold true for Taylor series, because $\frac{1}{1-x} = \left(\frac{1}{1-x}\right)^p \left(\frac{1}{1-x}\right)^{1-p}$ and both factors have nonnegative coefficients. Aug 25 '19 at 13:31
• Here's yet another reformulation, which I owe to Rémy Oudompheng and which I think is lovely: assume $X,Y$ are random variables supported on a finite subset of the integers, and assume $Z=X+Y$ is uniformly distributed on its support: is it necessarily the case that $X$ and $Y$ are themselves uniformly distributed on their support? Aug 25 '19 at 22:42
• A partial positive answer: Yes, if it is assumed in addition that the coefficients are equal to 1 precisely for the exponents from some finite arithmetic progression. This was proved (for arithmetic progressions 0,1,…,k−1), by Krasner and Ranulac (1937), Sur une propri\'et\'e des polynomes de la division du cercle, C.R. Acad. Sci. Paris 204, 397--399.This result is cited, without mentioning sharpenings, some 50 years later on page 160 of Ruzsa and Sz\'ekely (1988), Algebraic Probability Theory. Aug 26 '19 at 8:45