222
$\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).

Improve this question
$\endgroup$
61
  • 37
    $\begingroup$ $x^3+1=(x+1)(x^2-x+1)$ is a rational example for why you need nonnegativity. $\endgroup$
    – R.P.
    Commented Aug 25, 2019 at 12:23
  • 17
    $\begingroup$ The conditions at least easily imply that all coefficients of $P$ and $Q$ are in $[0,1]$. $\endgroup$
    – Emil Jeřábek
    Commented Aug 25, 2019 at 13:06
  • 31
    $\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
    Commented Aug 25, 2019 at 13:31
  • 32
    $\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
    Commented Aug 25, 2019 at 22:42
  • 18
    $\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
    Commented Aug 26, 2019 at 8:45

0

Reset to default

You must log in to answer this question.