130
$\begingroup$

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

$\endgroup$
  • 19
    $\begingroup$ $x^3+1=(x+1)(x^2-x+1)$ is a rational example for why you need nonnegativity. $\endgroup$ – RP_ Aug 25 '19 at 12:23
  • 13
    $\begingroup$ The conditions at least easily imply that all coefficients of $P$ and $Q$ are in $[0,1]$. $\endgroup$ – Emil Jeřábek Aug 25 '19 at 13:06
  • 21
    $\begingroup$ 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. $\endgroup$ – Will Sawin Aug 25 '19 at 13:31
  • 20
    $\begingroup$ 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? $\endgroup$ – Gro-Tsen Aug 25 '19 at 22:42
  • 15
    $\begingroup$ 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. $\endgroup$ – Lutz Mattner Aug 26 '19 at 8:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.