213

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

Michael Hardy
  • 11,922
  • 11
  • 81
  • 119
Sil
  • 2,181
  • 37
    $x^3+1=(x+1)(x^2-x+1)$ is a rational example for why you need nonnegativity. – R.P. Aug 25 '19 at 12:23
  • 17
    The conditions at least easily imply that all coefficients of $P$ and $Q$ are in $[0,1]$. – Emil Jeřábek Aug 25 '19 at 13:06
  • 12
    and algebraic integers. Unfortunately there are many algebraic integers in $[0,1]$ that are not integers. – Will Sawin Aug 25 '19 at 13:21
  • 31
    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. – Will Sawin Aug 25 '19 at 13:31
  • 5
    Here's a geometric reformulation, which may be more palatable: if we have a rectangle of sides $a\times b$ and a way to divide each side into (possibly degenerate) parts, viz., $a=a_0+\cdots+a_p$ and $b=b_0+\cdots+b_q$ (with all $a_i,b_j≥0$), and assuming $a_p=1$ and $b_q=1$ and that each of the diagonals has a total area $c_k := \sum_{i+j=k} a_i b_j$ which is either $0$ or $1$, does it follow that each of the $a_i,b_j$ is either $0$ or $1$? – Gro-Tsen Aug 25 '19 at 17:14
  • 1
    (Of course, if $c_k=0$ this means that every time $i+j=k$ with $0≤i≤p$ and $0≤j≤q$, either $a_i=0$ or $b_j=0$. This is a strong condition.) – Gro-Tsen Aug 25 '19 at 17:17
  • 12
    If there is a 0-1 solution, then $P$ and/or $Q$ must be very sparse, since $P(1)Q(1)=R(1)\le 1+\deg R$. – Brendan McKay Aug 25 '19 at 18:18
  • 2
    @WillSawin Does it hold true for Taylor series if any one of the three is restricted to being a monic polynomial? – user44191 Aug 25 '19 at 20:56
  • 32
    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? – Gro-Tsen Aug 25 '19 at 22:42
  • 8
    @Gro-Tsen Right, but you forgot to add that $X$ and $Y$ are independent. – Brendan McKay Aug 26 '19 at 08:01
  • 18
    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. – Lutz Mattner Aug 26 '19 at 08:45
  • 1
    @RP_ Every real polynomial of degree at least 3 is reducible over the reals into linear and quadratic factors. – Brendan McKay Aug 26 '19 at 10:22
  • @BrendanMcKay Ah yes, of course. Let me try again: 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? – Gro-Tsen Aug 26 '19 at 11:22
  • 6
    @Lutz Mattner This is a great reference! So, it seems that the problem is open since quite a while. I also found some forum discussions from 8 years ago discussing this problem: http://www.les-mathematiques.net/phorum/read.php?12,648286,649332#msg-649332 – Luca Ghidelli Aug 26 '19 at 12:41
  • 5
    @Lutz Mattner As you point out, Krasner and Ranulac solve the problem for only a simple case. In fact their short elementary proof, with not much more case-analysis, works in a more general case, that is, if the product has a "palindromic" sequence of 0,1 coefficients. I think this is the proof that Emmanuel Amiot has in mind in his question on MS https://math.stackexchange.com/q/3325163/176416 – Luca Ghidelli Aug 26 '19 at 12:46
  • 10
    Following the link in the first comment of @Luca Ghidelli, we see that Gerard Letac, an expert in such matters, regarded the problem as open eight years ago. And judging from the titles of the 46 papers citing the Krasner-Ranulac paper according to Google Scholar today, none of it appears to advertise a solution. So I conjecture that the conjecture is presently still open. (But, of course, actually looking at some of these 46 papers might refute this.) – Lutz Mattner Aug 26 '19 at 20:25
  • 3
    @RP_, one can also rationalize the OP counterexample: $x^4+4=(x^2+2x+2)(x^2-2x+2)$ – Michael Aug 26 '19 at 22:43
  • 2
    @Gro-Tsen is there a counterexample to the probabilistic version for the case of X, Y i.r.v. with non necessarily finite support on the nonnegative integers? (The example of the binomial series mentioned by Will Savin in this case wouldn't help, since at least one between the series of $(1-x)^{-p}$ and $(1-x)^{-1+p}$ has non-summable coefficients) – Pietro Majer Aug 27 '19 at 12:30
  • 2
    We are reduced to prove that $P$ and $Q$ have integer coefficients. – Sebastien Palcoux Aug 27 '19 at 17:44
  • 3
    @SebastienPalcoux That also follows from Emil Jeřábek's comment. – R.P. Aug 27 '19 at 18:18
  • Is there a counter-example for "$P,Q \in \mathbb{R}{\ge 0}[X]$ monic and $PQ \in \mathbb{Z}{\ge 0}[X]$ implies $P,Q \in \mathbb{Z}_{\ge 0}[X]$"? – Sebastien Palcoux Aug 27 '19 at 21:33
  • 1
    @PietroMajer That's equivalent to the original problem, since if a sum of two random variables has finite support, the variables have finite support as well. – Will Sawin Aug 27 '19 at 22:29
  • 3
    @Michael: Unfortunately x^4+4 is not a {0,1}-polynomial. There are numerous alternative rational counterexamples dropping nonnegativiti, since basically almost any random real factorization of a {0,1}-polynomial would do. A family of them is given by cyclotomic polynomials, for example $x^{210}+1=\Phi_{210}(x)*something(x)$. In any case I would not focus too much on the possibly-with-negative-coefficients factorizations. Indeed, the lack of nonnegativity misses all the delicate metric and combinatorial constraints of the problem. – Luca Ghidelli Aug 28 '19 at 01:59
  • 4
    @PietroMajer If the target distribution is uniform with discrete support, then it is necessarily with finite support. However there are examples of non-uniform continuous random variables whose sum is uniform on (0,1). These solutions are described in Lewis, T. (1967). The Factorisation of the rectangular distribution. Journal of Applied Probability, 4(3), 529-542. and they are quickly described by Gerard Letac here: http://www.les-mathematiques.net/phorum/read.php?12,648286,649332 – Luca Ghidelli Aug 28 '19 at 02:24
  • 4
    @SebastienPalcoux $P(x)Q(x)=x^2+3x+1$ – Luca Ghidelli Aug 28 '19 at 02:35
  • Sure! More generally, when $b,c \in \mathbb{Z}_{\ge 0}$, $\Delta = b^2 - 4c \ge 0$ and not a square, there is the counter-example: $x^2+bx+c = (x+\frac{b+\sqrt{b^2-4c}}{2})(x+\frac{b-\sqrt{b^2-4c}}{2})$. – Sebastien Palcoux Aug 28 '19 at 06:57
  • 9
    As a consequence of the Gauss Lemma, this is true if $P$ and $Q$ have rational coefficients. – Seva Aug 28 '19 at 17:25
  • 7
    It could be worthwhile to search for higher degree counter-examples. I am thinking of the fact that cyclotomic polynomials have all nonzero coefficients equal to +/- 1, up to degree 105, where the statement fails for the first time. Not that this phenomenon is necessarily related to your question, of course, but at least it shows one ignores the law of small numbers at one's own peril... – R.P. Aug 29 '19 at 13:19
  • 1
    @Seva, perhaps you could give your argument (combining the Gauss Lemma with Emil's remark, right?) in more detail. – Lutz Mattner Aug 29 '19 at 13:50
  • 3
    @LutzMattner: Suppose that $P$ and $Q$ are monic, have all their coefficients non-negative and rational, and their product $R:=PQ$ is a zero-one polynomial. Let $A$ and $B$ denote the least common denominator of the coefficients of $P$ and $Q$, respectively. We have $AP\cdot BQ=ABR$, all three polynomials involved having integer coefficients. By Gauss Lemma, any prime $p$ dividing $A$ must divide all coefficients of one of the polynomials $AP$ and $BQ$, contradicting the choice of $A$ and $B$. – Seva Aug 29 '19 at 14:45
  • 2
    (continued) Thus, $A=B=1$, showing that $P$ and $Q$ have in fact integer coefficients. These integer coefficients are non-negative and cannot exceed $1$; hence, they are in ${0,1}$. – Seva Aug 29 '19 at 14:46
  • Luca Ghidelli is absolutely right about "the proof I had in mind in https://math.stackexchange.com/q/3325163/176416" :). So is Gro-Tsen. Thanks for the answers here bvtw, they mean that the problem is still open. – E. Amiot Aug 29 '19 at 16:23
  • 5
    @Seva and Lutz Mattner: As already observed by Will Savin above, the coefficients of $P$ and $Q$ are algebraic integers. Thus, if they are rational, they are integers, hence $0$ or $1$. – Emil Jeřábek Aug 29 '19 at 20:52
  • @EmilJeřábek: Right, of course. In fact, this shows that $P$ and $Q$ cannot have any rational coefficients at all, except those equal $0$ or $1$. – Seva Sep 02 '19 at 05:09
  • 7
    I've verified the conjecture for $\mathrm{deg} R\leq 26$. – Max Alekseyev Sep 04 '19 at 15:53
  • @LucaGhidelli Why does the conjecture hold if the product $P(x)Q(x)$ is palindromic? Krasner and Rulac use that if a root of unity $\zeta$ is a root of $P$, then its complex conjugate $\bar\zeta=1/\zeta$ is a root of $P$ too. Thus if $P(x)Q(x)$ is palindromic and all the roots of $P(x)Q(x)$ are roots of unity, then their argument goes through. But I do not see how to omit the latter assumption. – Peter Mueller Sep 08 '19 at 18:22
  • 12
    BTW, I've verified the conjecture for $\deg R\le 32$ by a rigorous Groebner basis calculation, staying away from numerical issues. – Peter Mueller Sep 08 '19 at 18:27
  • 1
    @PeterMueller Maybe we read different papers. The argument I have in mind does not use roots at all, it suffices to work with the coefficients. First you assume R (0) is not zero. You make up a multiplication table with rows/cols corresponding to the coeff. of P/Q. Summing on the diagonals you get the coeffs of R. Then you prove that the first and last coefficient of P and Q equal 1. So on two diagonals of the multiplication table there are many zeros; this is useful in the next induction Then you prove that the second and second-to-last coefficients of P and Q are in {0,1} and they are ... – Luca Ghidelli Sep 09 '19 at 03:25
  • 1
    ... mirrored. Repeat cheching all details. The main lemma that is used in the argument is: if xy=0 and x+y is in {0,1}, then x,y are both in {0,1}. But I advise to become convinced of the argument by doing it yourself. I hope I described enough to reconstruct the proof – Luca Ghidelli Sep 09 '19 at 03:31
  • 1
    My personal understanding of the problem is that, if you write down the equations to make it work, you see that this is an overdetermined problem. Therefore a counterexample can be obtained almost exclusively through an improbable algebraic-combinatoric coincidence. Other partial progress can be made studying P of low degree [Q arbitrary] and I verified this in some cases. – Luca Ghidelli Sep 09 '19 at 03:44
  • 1
    I suppose that a low-technology line of attack may involve two different cases: when R is very sparse and when it is far from being so. In the latter case linear recurrences arise. I tried just a little using heights inequalities, but the problem is that the L2-norm is not an algebra norm. I don't see how the Bombieri height can be of help, but this is a positive real problem so inequalities should help – Luca Ghidelli Sep 09 '19 at 03:47
  • 2
    @LucaGhidelli I agree that your sketched argument works if only $P\cdot Q$ is assumed to be palindromic. – Peter Mueller Sep 09 '19 at 09:46
  • My answer is globally fixed. Waiting for the comments. – Yuri Negometyanov Sep 20 '19 at 18:46
  • Are there any examples where a zero-one polynomial is divisible by a monic polynomial with all coefficients in $[0,1]$, at least one of which is not in ${0,1}$? – Seva Sep 25 '19 at 15:27
  • 5
    @Seva $x^5+1$ is divisible by $x^2+\frac{\sqrt{5}-1}{2}x+1$ – Sil Sep 25 '19 at 16:24
  • @LutzMattner Your comment seems to answer a recently-asked question for a specific case of the main question here; I think you are the correct person to provide an answer. https://mathoverflow.net/questions/345884/if-the-sum-of-two-independent-random-variables-is-discrete-uniform-on-a-a – user44191 Nov 13 '19 at 01:30
  • As suggested by @LucaGhidelli, it is easy to rule out small degrees $P,Q$, for example $(1+a_1 x+x^2)(1+b_1x+\dots+b_{n-1}x^{n-1}+x^n)$ with $a_1 \in (0,1)$ gives $a_1 + b_1\in {0,1}$, so $b_1 \in (0,1)$ , and looking at the $x^2$ coefficient $1+a_1b_1+b_2>1$, impossible. Similar argument works for degrees $3,4$, maybe also higher (but i don't see how to generalize). – Sil Dec 24 '19 at 13:41
  • 1
    As a follow-up to @WillSawin's comment about Taylor series, there is also a counterexample if only one of the factors is constrained to be a polynomial. $\frac{2}{3} \cdot \frac{1}{1-t} + \frac{1}{3} \cdot \frac{1}{1 + (1/2) t}$ has positive coefficients, and multiplying it by $1+(1/2) t$ gives you $\frac{1}{1-t}$. – Ash Malyshev Jun 20 '20 at 20:58
  • 3
    The activity today is due to a new user suddenly appearing, answering a dozen or so questions (raking in an impressive amount of down votes) in just a few hours, then vanishing. – Yaakov Baruch Oct 25 '21 at 07:24
  • 2
    Nine answers, all deleted. – Gerry Myerson Oct 25 '21 at 12:10
  • This is from Gauss's lemma (polynomials. A general recommendations shall be to stay with popular names in Mathematics. – Steffen Jaeschke Nov 09 '22 at 14:54
  • There is a suggestion and an alleged solution if one factor has degree $\le 6$ by Claudio Procesi (apparently the real one!) at https://math.stackexchange.com/questions/3325163. Nevertheless, it looks to me that it is the straightforward approach which only works if one factor has degree $\le 4$. – Peter Mueller Dec 07 '22 at 18:10
  • 3
    @SteffenJaeschke What is from Gauss's lemma? – Will Orrick Jan 14 '23 at 04:27
  • 2
    Does this question hold the record for the number of deleted answers (now 10)? – Brendan McKay Aug 17 '23 at 07:17
  • @BrendanMcKay Not even close! (There are plenty more on this famous question). – Carl-Fredrik Nyberg Brodda Aug 17 '23 at 07:36
  • I think the equivalent random variable formulation is that the uniform discrete distribution is not decomposable. This is stronger than every summand being uniform on the support. The only support that matters are the equally spaced support points. The continuous uniform random variable is (strongly) decomposable owing to the infinite Bernoulli sum representation. Evidently the discrete uniform random variable is not strongly decomposable. – japalmer Aug 17 '23 at 08:21
  • It's not hard to show this for equal length sequences. So it comes down to showing that the convolution of two unequal length sequences must have at at least two unequal non-zero elements. – japalmer Aug 17 '23 at 09:32
  • Related. If we allow negative coefficients, and all coefficients of $P(x)Q(x)$ are in ${-1,0,1}$, then must all coefficients of $P(x)$ also be in ${-1,0,1}$ ? – Gerald Edgar Aug 17 '23 at 12:05
  • The conjecture can be reduced to a proposition on unit spaced discrete sequences, that a finite length sequence of 1's cannot be decomposed into a convolution of two positive sequences. This can easily be seen for sequences of the same length. Wolog, let the sequences both start with 1. Let the first end with $a$ and the second end with $b$. Then $a+b=1$ and $ab=1$, and thus $a$ and $b$ are not positive. So the problem is reduced to showing that the convolution of two positive sequences of unequal length cannot be a sequence of 1's. – japalmer Aug 20 '23 at 04:48
  • 2
    Another reference: Computational progress on the unfair 0-1 polynomial Conjecture by Kevin G. Hare. – Timothy Chow Jan 07 '24 at 05:05

0 Answers0