102
$\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$
  • 16
    $\begingroup$ $x^3+1=(x+1)(x^2-x+1)$ is a rational example for why you need nonnegativity. $\endgroup$ – RP_ Aug 25 at 12:23
  • 11
    $\begingroup$ The conditions at least easily imply that all coefficients of $P$ and $Q$ are in $[0,1]$. $\endgroup$ – Emil Jeřábek supports Monica Aug 25 at 13:06
  • 16
    $\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 at 13:31
  • 17
    $\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 at 22:42
  • 14
    $\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 at 8:45
-5
$\begingroup$

HINT

$\color{brown}{\textbf{Formulation of the problem.}}$

The OP identity has counterexample $$\left(\frac12x+\dfrac12\right)(2x^2+2) = x^3+x^2+x+1.$$ On the other hand, possible common factor $x^k$ both in LHS and RHS can be eliminated.

Let be $$\begin{cases} P(x)=1 + p_1x +p_2x^2 +\dots p_ax^a\\[4pt] Q(x)=1 + q_1x +q_2x^2 +\dots q_bx^b\\[4pt] R(x)=1 + r_1x +r_2x^2 +\dots r_{a+b}x^{a+b}\\[4pt] p_1\ge 0,\ p_2\ge 0,\ \dots,\ p_a\ge 0\\[4pt] q_1\ge 0,\ q_2\ge 0,\ \dots,\ q_b\ge 0\\[4pt] r_1\in\{0,1\},\ r_2\in\{0,1\},\ \dots,\ r_a\in\{0,1\}\\ 1\le a\le b, \end{cases}\tag1$$

then $$\begin{cases} r_1 = p_1+q_1\in\{0,1\}\\ r_2 = p_2+p_1q_1+q_2\in\{0,1\}\\ r_3 = p_3+p_2q_1+p_1q_2+q_3\in\{0,1\}\\ \dots\\ r_{a-1} = p_{a-1}+p_{a-2}q_1+\dots+p_1q_{a-2}+q_{a-1}\in\{0,1\}\\ r_{a} = p_a+p_{a-1}q_1+\dots+p_1q_{a-1}+q_a\in\{0,1\}\\ r_{a+1} = p_aq_1+p_{a-1}q_2+\dots+p_1q_a+q_{a+1}\in\{0,1\}\\ r_{a+2} = p_aq_2+p_{a-1}q_3+\dots+p_1q_{a+1}+q_{a+2}\in\{0,1\}\\ \dots\\ r_{b-1} = p_aq_{b-1-a}+p_{a-1}q_{b-a}+\dots+p_1q_{b-2}+q_{b-1}\in\{0,1\}\\ r_{b} = p_aq_{b-a}+p_{a-1}q_{b-a+1}+\dots+p_1q_{b-1}+q_b\in\{0,1\}\\ r_{b+1} = p_aq_{b+1-a}+p_{a-1}q_{b-a+2}+\dots+p_2q_{b-1}+p_1q_b\in\{0,1\}\\ \dots\\ r_{a+b-2} = p_aq_{b-2}+p_{a-1}q_{b-1}+p_{a-2}q_b\in\{0,1\}\\ r_{a+b-1} = p_{a}q_{b-1}+p_{a-1}q_b\in\{0,1\}\\ r_{a+b} = p_aq_b=1. \end{cases}\tag2$$

Required to prove that $a_i\in\{0,1\}, b_j\in\{0,1\},$ where $i=1\dots a, j=1\dots b.$

The system $(2)$ of bilinear equations with the discrete RHS describes the constraints to the polynomial convolution and looks undefined. On the other hand, all unknowns are non-negative, and this gives it some features of the transport task. This features can be used by the applying AM-GM inequality.

(AM-GM inequality):

If $u\ge0$ and $v\ge 0,$ then $u+v\ge2\sqrt {uv},$

wherein $\quad u+v=2\sqrt {uv}\quad$ iff $\quad u=v.$

$\color{brown}{\textbf{Examples.}}$

If $\color{brown}{\mathbf{a=b=2}}$ then $$ \left\{\begin{aligned} &p_1+q_1 \in\{0,1\}\\ &p_2+p_1q_1+q_2\in\{0,1\}\\ &p_1q_2+p_2q_1\in\{0,1\}\\ &p_2q_2 = 1 \end{aligned}\right.\Rightarrow \left\{\begin{aligned} &p_2+p_1q_1+q_2\in\{0,1\}\\ &p_2+q_2\ge2\\ &p_1+q_1 \in\{0,1\}\\ &p_1q_2+p_2q_1\in\{0,1\}, \end{aligned}\right.$$ i.e. there are not real solutions.

If $\color{brown}{\mathbf{a=3, b=4}}$ then calculations can be presented in the matrix form by the basis $\{1,p_1,p_2\dots\},$ using AM-GM in the form of $p_3+q_4\ge 2(p_3q_4) = 2,$ $$\begin{pmatrix} q_1 & 1 & 0 & 0 & \Large| & \{0,1\} \\[-4pt] q_2 & q_1 & 1 & 0 & \Large| & \{0,1\} \\[-4pt] \color{blue}{q_3} & q_2 & q_1 & \color{brown}1 & \Large| & \{0,1\} \\[-4pt] \color{brown}{q_4} & q_3 & q_2 & \color{blue}{q_1} & \Large| & \{0,1\} \\[-4pt] 0 & q_4 & q_3 & q_2 & \Large| & \{0,1\} \\[-4pt] 0 & 0 & q_4 & q_3 & \Large| & \{0,1\} \\[-4pt] 0 & 0 & 0 & \color{brown}{\mathbf{q_4}} & \Large| & \mathbf1 \end{pmatrix}\Rightarrow \begin{pmatrix} 0 & \color{green}{\mathbf1} & 0 & \Large| & \{0,1\} \\[-4pt] \color{green}{\mathbf{q_2}} & 0 & 1 & \Large| & \{0,1\} \\[-4pt] 0 & q_2 & 0 & \Large| & 0 \\[-4pt] 0 & 0 & q_2 & \Large| & 0 \\[-4pt] q_2 & 1 & 0 & \Large| & \{0,1\} \\[-4pt] 0 & 0 & \color{green}{\mathbf1} & \Large| & \{0,1\} \\[-4pt] p_3 & 0 & 0 & \Large| & 1 \\[-4pt] q_1 & 0 & 0 & \Large| & 0 \\[-4pt] q_3 & 0 & 0 & \Large| & 0 \\[-4pt] q_4 & 0 & 0 & \Large| & 1 \\[-4pt] \end{pmatrix}. $$ $p_1,p_2 \in\{0,1\}.$

Since $p_2+q_2\in\{0,1\},$ then $q_2\in\{0,1\},$ and required conditions are proved.

Let us consider cases $q_2=0$ and $q_2=1$, then $$ \begin{pmatrix} 0 & 1 & 0 & \Large| & \{0,1\} \\[-4pt] 0 & 0 & 1 & \Large| & \{0,1\} \\[-4pt] 0 & 0 & 0 & \Large| & 0 \\[-4pt] 0 & 0 & 0 & \Large| & 0 \\[-4pt] 0 & 1 & 0 & \Large| & \{0,1\} \\[-4pt] 0 & 0 & 1 & \Large| & \{0,1\} \\[-4pt] p_3 & 0 & 0 & \Large| & 1 \\[-4pt] q_1 & 0 & 0 & \Large| & 0 \\[-4pt] q_2 & 0 & 0 & \Large| & 0 \\[-4pt] q_3 & 0 & 0 & \Large| & 0 \\[-4pt] q_4 & 0 & 0 & \Large| & 1 \\[-4pt] \end{pmatrix}\bigcup \begin{pmatrix} 0 & 1 & 0 & \Large| & \{0,1\} \\[-4pt] 1 & 0 & \color{blue}{\mathbf1} & \Large| & \{0,1\} \\[-4pt] 0 & 1 & 0 & \Large| & 0 \\[-4pt] 0 & 0 & 1 & \Large| & 0 \\[-4pt] 1 & \color{blue}{\mathbf1} & 0 & \Large| & \{0,1\} \\[-4pt] 0 & 0 & 1 & \Large| & \{0,1\} \\[-4pt] p_3 & 0 & 0 & \Large| & 1 \\[-4pt] q_1 & 0 & 0 & \Large| & 0 \\[-4pt] q_2 & 0 & 0 & \Large| & 1 \\[-4pt] q_3 & 0 & 0 & \Large| & 0 \\[-4pt] q_4 & 0 & 0 & \Large| & 1 \\[-4pt] \end{pmatrix} $$$$ \Rightarrow \begin{pmatrix} p_1 & \Large| & \{0,1\} \\[-4pt] p_2 & \Large| & \{0,1\} \\[-4pt] p_3 & \Large| & 1 \\[-4pt] q_1 & \Large| & 0 \\[-4pt] q_2 & \Large| & 0 \\[-4pt] q_3 & \Large| & 0 \\[-4pt] q_4 & \Large| & 1 \\[-4pt] \end{pmatrix}\bigcup \begin{pmatrix} p_1 & \Large| & 0 \\[-4pt] p_2 & \Large| & 0 \\[-4pt] p_3 & \Large| & 1 \\[-4pt] q_1 & \Large| & 0 \\[-4pt] q_2 & \Large| & 1 \\[-4pt] q_3 & \Large| & 0 \\[-4pt] q_4 & \Large| & 1 \\[-4pt] \end{pmatrix}, $$ with the solutions in the required form: $$(1+x^3)(1+x^4) = 1+x^3+x^4+x^7,$$ $$(1+x^3)(1+x^2+x^4) = 1+x^2+x^3+x^4+x^5+x^7,$$ $$(1+x^2+x^3)(1+x^4) = 1+x^2+x^3+x^4+x^6+x^7,$$ $$(1+x+x^3)(1+x^4) = 1+x+x^3+x^4+x^5+x^7,$$ $$(1+x+x^2+x^3)(1+x^4) = 1+x+x^2+x^3+x^4+x^5+x^6+x^7.$$

$\color{brown}{\textbf{Terminology.}}$

Let $$b=a+h,$$ then the matrix form of $(2)$ in the basis $\{1,p_1,p_2,\dots,p_a\}$ is $$\hspace{-20mu}{\small\begin{pmatrix} q_1 & 1 & 0 & 0 & \dots & 0 & 0 & 0 & 0 & \Large| & \{0,1\} \\[-4pt] q_2 & q_1 & 1 & 0 & \dots & 0 & 0 & 0 & 0 & \Large| & \{0,1\} \\[-4pt] q_3 & q_2 & q_1 & 1 & \dots & 0 & 0 & 0 & 0 & \Large| & \{0,1\} \\[-4pt] &\dots&&&\dots&&&\dots&&\Large|&\dots\\[-4pt] q_{a-2} & q_{a-3} & q_{a-4} & q_{a-5} & \dots & q_1 & 1 & 0 & 0 & \Large| & \{0,1\} \\[-4pt] q_{a-1} & q_{a-2} & q_{a-3} & q_{a-4} & \dots & q_2 & q_1 & 1 & 0 & \Large| & \{0,1\} \\[-4pt] \color{blue}{\mathbf{q_a}} & q_{a-1} & q_{a-2} & q_{a-3} & \dots & q_3 & q_2 & q_1 & \color{brown}{\mathbf 1} & \Large| & \{0,1\} \\[-4pt] q_{a+1} & q_a & q_{a-1} & q_{a-2} & \dots & q_4 & q_3 & q_2 & q_1 & \Large| & \{0,1\} \\[-4pt] q_{a+2} & q_{a+1} & q_a & q_{a-1} & \dots & q_5 & q_4 & q_3 & q_2 & \Large| & \{0,1\} \\[-4pt] &\dots&&&\dots&&&\dots&&\Large|&\dots\\[-4pt] q_{a+h-2} & q_{a+h-3} & q_{a+h-4} & q_{a+h-5} & \dots & q_{h+1} & q_{h} & q_{h-1} & q_{h-2} & \Large| & \{0,1\} \\[-4pt] q_{a+h-1} & q_{a+h-2} & q_{a+h-3} & q_{a+h-4} & \dots & q_{h+2} & q_{h+1} & q_{h} & q_{h-1} & \Large| & \{0,1\} \\[-4pt] \color{brown}{\mathbf{q_{a+h}}} & q_{a+h-1} & q_{a+h-2} & q_{a+h-3} & \dots & q_{h+3} & q_{h+2} & q_{h+1} & \color{blue}{\mathbf{q_{h}}} & \Large| & \{0,1\} \\[-4pt] 0 & q_{a+h} & q_{a+h-1} & q_{a+h-2} & \dots & q_{h+4} & q_{h+3} & q_{h+2} & q_{h+1} & \Large| & \{0,1\} \\[-4pt] 0 & 0 & q_{a+h} & q_{a+h-1} & \dots & q_{h+5} & q_{h+4} & q_{h+3} & q_{h+2} & \Large| & \{0,1\} \\[-4pt] &\dots&&&\dots&&&\dots&&\Large|&\dots\\[-4pt] 0 & 0 & 0 & 0 & \dots & 0 & q_{a+h} & q_{a+h-1} & q_{a+h-2} & \Large| & \{0,1\} \\[-4pt] 0 & 0 & 0 & 0 & \dots & 0 & 0 & q_b & q_{a+h-1} & \Large| & \{0,1\} \\[-4pt] 0 & 0 & 0 & 0 & \dots & 0 & 0 & 0 & \color{brown}{\mathbf q_{a+h}} & \Large| & \mathbf1 \\[-4pt] \end{pmatrix}}.\tag3$$

Taking in account AM-GM inequality for the last equation of the system, one can write $$p_a+q_{a+h} \ge 2.\tag4$$

If $\color{brown}{\mathbf{h=0}},$ then the central equation contains both the term $p_a$ and the term $,\ q_{a+h}.$ Since RHS of the central equation of the system $(3)$ is smaller than 2, this equation contradicts with $(4).$ In this case, the system $(3)$ does not have real solutions.

Therefore, $$\color{brown}{\mathbf{h\in \mathbb N}}.$$

In this case, the terms $p_a$ and $q_{a+h}$ belong to the different equations of the system, wherein the sum of these equations is less or equals to 2. So the inequality $(4)$ can be satisfied only if $p_a=q_{a+h}=1,\ q_a=q_h=0.$

Unknown $p_a$ can be eliminated from the basis of the system matrix. Equalities $q_{a+h}=1$ and $q_a=q_h=0$ can be used immediately.

Then the system $(3)$ can be written in the form of $$\hspace{-20mu}\small{\begin{pmatrix} \color{brown}{\mathbf{q_1}} &\color{brown}{\mathbf 1} & 0 & 0 & \dots & 0 & 0 & 0 & \Large| & \{0,1\} \\[-4pt] q_2 & q_1 & 1 & 0 & \dots & 0 & 0 & 0 & \Large| & \{0,1\} \\[-4pt] q_3 & q_2 & q_1 & 1 & \dots & 0 & 0 & 0 & \Large| & \{0,1\} \\[-4pt] &\dots&&&\dots&&\dots&&\Large|&\dots\\[-4pt] q_{a-2} & q_{a-3} & q_{a-4} & q_{a-5} & \dots & q_1 & 1 & 0 & \Large| & \{0,1\} \\[-4pt] q_{a-1} & q_{a-2} & q_{a-3} & q_{a-4} & \dots & q_2 & q_1 & 1 & \Large| & \{0,1\} \\[-4pt] 0 & q_{a-1} & q_{a-2} & q_{a-3} & \dots & q_3 & q_2 & \color{brown}{\mathbf{q_1}} & \Large| & 0 \\[-4pt] q_{a+1}+q_1 & 0 & q_{a-1} & q_{a-2} & \dots & q_4 & q_3 & q_2 & \Large| & \{0,1\} \\[-4pt] q_{a+2}+q_2 & q_{a+1} & 0 & q_{a-1} & \dots & q_5 & q_4 & q_3 & \Large| & \{0,1\} \\[-4pt] &\dots&&&\dots&&\dots&&\Large|&\dots\\[-4pt] q_{a+h-2}+q_{h-2} & q_{a+h-3} & q_{a+h-4} & q_{a+h-5} & \dots & q_{h+1} & 0 & q_{h-1} & \Large| & \{0,1\} \\[-4pt] q_{a+h-1}+q_{h-1} & q_{a+h-2} & q_{a+h-3} & q_{a+h-4} & \dots & q_{h+2} & q_{h+1} & 0 & \Large| & \{0,1\} \\[-4pt] 0 & \color{brown}{\mathbf{q_{a+h-1}}} & q_{a+h-2} & q_{a+h-3} & \dots & q_{h+3} & q_{h+2} & q_{h+1} & \Large| & 0 \\[-4pt] q_{h+1} & 1 & q_{a+h-1} & q_{a+h-2} & \dots & q_{h+4} & q_{h+3} & q_{h+2} & \Large| & \{0,1\} \\[-4pt] q_{h+2} & 0 & 1 & q_{a+h-1} & \dots & q_{h+5} & q_{h+4} & q_{h+3} & \Large| & \{0,1\} \\[-4pt] &\dots&&&\dots&&\dots&&\Large|&\dots\\[-4pt] q_{a+h-2} & 0 & 0 & 0 & \dots & 0 & 1 & q_{a+h-1} & \Large| & \{0,1\} \\[-4pt] \color{brown}{\mathbf{q_{a+h-1}}} & 0 & 0 & 0 & \dots & 0 & 0 & \color{brown}{\mathbf1} & \Large| & \{0,1\} \\[-4pt] p_a & 0 & 0 & 0 & \dots & 0 & 0 & 0 & \Large| & 1 \\[-4pt] q_a & 0 & 0 & 0 & \dots & 0 & 0 & 0 & \Large| & 0 \\[-4pt] q_{h} & 0 & 0 & 0 & \dots & 0 & 0 & 0 & \Large| & 0 \\[-4pt] q_{a+h} & 0 & 0 & 0 & \dots & 0 & 0 & 0 & \Large| & 1 \\[-4pt] \end{pmatrix}}.\tag5$$

The matrix of the system $(5)$ has in the main part

  • $a$ columns and $(a+2h-1)$ rows, with filled first column,

  • zero RHS in the rows with the numbers $a$ and $a+h,$

  • the group of $(a+h+1)$ diagonals with diagonals of ones around the edges.

We call such a matrix "$(a,h)$-matrix".

Also, $(a,h)$-matrix can contain a list of the values of unknowns below the main part, which must be ignored in the structure definition.

Easy to prove that $$(u\in\{0,1\}) \wedge (u+v \in\{0,1\}) \Rightarrow (v\in\{0,1\}),$$ $$((a_1\dots a_k, w_1\dots w_k \in\{0,1\}) \wedge (b= a_j-\sum a_k w_k \ge 0) \Rightarrow (b\in\{0,1\}).\tag6$$

$\color{brown}{\textbf{$(a,h)$-matrices for $a=1,2.3$}}$

If $\color{brown}{\mathbf{a=1}}$ then $$ \begin{pmatrix} q_2+q_1 & \Large| & \{0,1\} \\[-4pt] q_3+q_2 & \Large| & \{0,1\} \\[-4pt] q_4+q_3 & \Large| & \{0,1\} \\[-4pt] \dots & \Large| & \dots \\[-4pt] q_h+q_{h-1} & \Large| & \{0,1\} \\[-4pt] p_1 & \Large| & 1 \\[-4pt] q_1 & \Large| & 0 \\[-4pt] q_h & \Large| & 0 \\[-4pt] q_{h+1} & \Large| & 1 \\[-4pt] \end{pmatrix}\Rightarrow \begin{pmatrix} q_2 & \Large| & \{0,1\} \\[-4pt] q_3+q_2 & \Large| & \{0,1\} \\[-4pt] q_4+q_3 & \Large| & \{0,1\} \\[-4pt] \dots & \Large| & \dots \\[-4pt] q_{h-1} & \Large| & \{0,1\} \\[-4pt] p_1 & \Large| & 1 \\[-4pt] q_1 & \Large| & 0 \\[-4pt] q_h & \Large| & 0 \\[-4pt] q_{h+1} & \Large| & 1 \\[-4pt] \end{pmatrix}. $$ Taking in account $(6),$ $$(p_1,q_1,q_2,\dots,q_{h+1})\in\{0,1\}^{h+2}.$$

If $\color{brown}{\mathbf{a=2}}$ then $$ \begin{pmatrix} q_1 & 1 & \Large| & \{0,1\} \\[-4pt] 0 & q_1 & \Large| & 0 \\[-4pt] q_3+q_1 & 0 & \Large| & \{0,1\} \\[-4pt] q_4+q_2 & q_3 & \Large| & \{0,1\} \\[-4pt] q_5+q_3 & q_4 & \Large| & \{0,1\} \\[-4pt] \dots &\dots & \Large| & \dots \\[-4pt] q_{h-1}+q_{h-3} & q_{h-2} & \Large| & \{0,1\} \\[-4pt] q_{h}+q_{h-2} & q_{h-1} & \Large| & \{0,1\} \\[-4pt] q_{h+1}+q_{h-1} & q_{h} & \Large| & \{0,1\} \\[-4pt] 0 & q_{h+1} & \Large| & 0 \\[-4pt] q_{h+1} & 1 & \Large| & \{0,1\} \\[-4pt] p_2 & 0 & \Large| & 1 \\[-4pt] q_2 & 0 & \Large| & 0 \\[-4pt] q_h & 0 & \Large| & 0 \\[-4pt] q_{h+2} & 0 & \Large| & 1 \\[-4pt] \end{pmatrix}\Rightarrow \begin{pmatrix} q_1 & 1 & \Large| & \{0,1\} \\[-4pt] 0 & \color{brown}{\mathbf{q_1}} & \Large| & 0 \\[-4pt] q_3+q_1 & 0 & \Large| & \{0,1\} \\[-4pt] q_4 & q_3 & \Large| & \{0,1\} \\[-4pt] q_5+q_3 & q_4 & \Large| & \{0,1\} \\[-4pt] \dots &\dots & \Large| & \dots \\[-4pt] q_{h-1}+q_{h-3} & q_{h-2} & \Large| & \{0,1\} \\[-4pt] q_{h-2} & q_{h-1} & \Large| & \{0,1\} \\[-4pt] q_{h+1}+q_{h-1} & 0 & \Large| & \{0,1\} \\[-4pt] 0 & \color{brown}{\mathbf{q_{h+1}}} & \Large| & 0 \\[-4pt] q_{h+1} & 1 & \Large| & \{0,1\} \\[-4pt] p_2 & 0 & \Large| & 1 \\[-4pt] q_2 & 0 & \Large| & 0 \\[-4pt] q_h & 0 & \Large| & 0 \\[-4pt] q_{h+2} & 0 & \Large| & 1 \\[-4pt] \end{pmatrix}\Rightarrow $$$$ \begin{pmatrix} q_1 & \Large| & \{0,1\} \\[-4pt] q_3+q_1 & \Large| & \{0,1\} \\[-4pt] q_4 & \Large| & \{0,1\} \\[-4pt] q_5+q_3 & \Large| & \{0,1\} \\[-4pt] \dots & \Large| & \dots \\[-4pt] q_{h-1}+q_{h-3} & \Large| & \{0,1\} \\[-4pt] q_{h-2} & \Large| & \{0,1\} \\[-4pt] q_{h+1}+q_{h-1} & \Large| & \{0,1\} \\[-4pt] q_{h+1} & \Large| & \{0,1\} \\[-4pt] p_1 & \Large| & 0 \\[-4pt] p_2 & \Large| & 1 \\[-4pt] q_2 & \Large| & 0 \\[-4pt] q_h & \Large| & 0 \\[-4pt] q_{h+2} & \Large| & 1 \\[-4pt] \end{pmatrix}\bigvee \begin{pmatrix} 0 & 1 & \Large| & \{0,1\} \\[-4pt] q_3 & 0 & \Large| & \{0,1\} \\[-4pt] q_4 & q_3 & \Large| & \{0,1\} \\[-4pt] q_5+q_3 & q_4 & \Large| & \{0,1\} \\[-4pt] \dots &\dots & \Large| & \dots \\[-4pt] q_{h-1}+q_{h-3} & q_{h-2} & \Large| & \{0,1\} \\[-4pt] q_{h-2} & q_{h-1} & \Large| & \{0,1\} \\[-4pt] q_{h-1} & 0 & \Large| & \{0,1\} \\[-4pt] q_2 & 0 & \Large| & 0 \\[-4pt] q_h & 0 & \Large| & 0 \\[-4pt] 0 & 1 & \Large| & \{0,1\} \\[-4pt] p_2 & 0 & \Large| & 1 \\[-4pt] q_1 & 0 & \Large| & 0 \\[-4pt] q_2 & 0 & \Large| & 0 \\[-4pt] q_h & 0 & \Large| & 0 \\[-4pt] q_{h+1} & 0 & \Large| & 0 \\[-4pt] q_{h+2} & 0 & \Large| & 1 \\[-4pt] \end{pmatrix}\Rightarrow $$$$ \begin{pmatrix} q_1 & \Large| & \{0,1\} \\[-4pt] q_3+q_1 & \Large| & \{0,1\} \\[-4pt] q_4 & \Large| & \{0,1\} \\[-4pt] q_5+q_3 & \Large| & \{0,1\} \\[-4pt] \dots & \Large| & \dots \\[-4pt] q_{h-1}+q_{h-3} & \Large| & \{0,1\} \\[-4pt] q_{h-2} & \Large| & \{0,1\} \\[-4pt] q_{h+1}+q_{h-1} & \Large| & \{0,1\} \\[-4pt] q_{h+1} & \Large| & \{0,1\} \\[-4pt] p_1 & \Large| & 0 \\[-4pt] p_2 & \Large| & 1 \\[-4pt] q_2 & \Large| & 0 \\[-4pt] q_h & \Large| & 0 \\[-4pt] q_{h+2} & \Large| & 1 \\[-4pt] \end{pmatrix}\bigvee \begin{pmatrix} q_3 & \Large| & \{0,1\} \\[-4pt] q_3+q_4 & \Large| & \{0,1\} \\[-4pt] q_3+q_4+q_5 & \Large| & \{0,1\} \\[-4pt] \dots & \Large| & \dots \\[-4pt] q_{h-1}+q_{h-4}+q_{h-3} & \Large| & \{0,1\} \\[-4pt] q_{h-2}+q_{h-1} & \Large| & \{0,1\} \\[-4pt] q_{h-1} & \Large| & \{0,1\} \\[-4pt] q_2 & \Large| & 0 \\[-4pt] q_h & \Large| & 0 \\[-4pt] p_1 & \Large| & 1 \\[-4pt] p_2 & \Large| & 1 \\[-4pt] q_1 & \Large| & 0 \\[-4pt] q_2 & \Large| & 0 \\[-4pt] q_h & \Large| & 0 \\[-4pt] q_{h+1} & \Large| & 0 \\[-4pt] q_{h+2} & \Large| & 1 \\[-4pt] \end{pmatrix}, $$ and obtained two $(1,h)$-matrices with LSH under $(6).$ So $$(p_1,p_2,q_1,q_2,\dots,q_{h+2})\in\{0,1\}^{h+2}.$$

If $\color{brown}{\mathbf{a=3}}$ then $$ \begin{pmatrix} q_1 & 1 & 0 & \Large| & \{0,1\} \\[-4pt] q_2 & q_1 & 1 & \Large| & \{0,1\} \\[-4pt] 0 & q_2 & \color{brown}{\mathbf{q_1}} & \Large| & 0 \\[-4pt] q_4+q_1 & 0 & q_2 & \Large| & \{0,1\} \\[-4pt] q_5+q_2 & q_4 & 0 & \Large| & \{0,1\} \\[-4pt] q_6 & q_5 & q_4 & \Large| & \{0,1\} \\[-4pt] \dots &\dots & \dots & \Large| & \dots \\[-4pt] q_{h-1}+q_{h-4} & q_{h-2} & q_{h-3} & \Large| & \{0,1\} \\[-4pt] q_{h-3} & q_{h-1} & q_{h-2} & \Large| & \{0,1\} \\[-4pt] q_{h+1}+q_{h-2} & 0 & q_{h-1} & \Large| & \{0,1\} \\[-4pt] q_{h+2}+q_{h-1} & q_{h+1} & 0 & \Large| & \{0,1\} \\[-4pt] 0 & q_{h+2} & q_{h+1} & \Large| & 0 \\[-4pt] q_{h+1} & 1 & \color{brown}{\mathbf{q_{h+2}}} & \Large| & \{0,1\} \\[-4pt] q_{h+2} & 0 & 1 & \Large| & \{0,1\} \\[-4pt] p_3 & 0 & 0 & \Large| & 1 \\[-4pt] q_3 & 0 & 0 & \Large| & 0 \\[-4pt] q_h & 0 & 0 & \Large| & 0 \\[-4pt] q_{h+3} & 0 & 0 & \Large| & 1 \\[-4pt] \end{pmatrix} $$$$ \Rightarrow \begin{pmatrix} q_1 & 1 & \Large| & \{0,1\} \\[-4pt] q_2 & q_1 & \Large| & \{0,1\} \\[-4pt] 0 & q_2 & \Large| & 0 \\[-4pt] q_4+q_1 & 0 & \Large| & \{0,1\} \\[-4pt] q_5+q_2 & q_4 & \Large| & \{0,1\} \\[-4pt] q_6 & q_5 & \Large| & \{0,1\} \\[-4pt] \dots &\dots & \Large| & \dots \\[-4pt] q_{h-1}+q_{h-4} & q_{h-2} & \Large| & \{0,1\} \\[-4pt] q_{h-3} & q_{h-1} & \Large| & \{0,1\} \\[-4pt] q_{h+1}+q_{h-2} & 0 & \Large| & \{0,1\} \\[-4pt] q_{h+2}+q_{h-1} & q_{h+1} & \Large| & \{0,1\} \\[-4pt] 0 & q_{h+2} & \Large| & 0 \\[-4pt] q_{h+1} & 1 & \Large| & \{0,1\} \\[-4pt] q_{h+2} & 0 & \Large| & \{0,1\} \\[-4pt] p_3 & 0 & \Large| & 1 \\[-4pt] p_2 & 0 & \Large| & 0 \\[-4pt] q_3 & 0 & \Large| & 0 \\[-4pt] q_h & 0 & \Large| & 0 \\[-4pt] q_{h+3} & 0 & \Large| & 1 \\[-4pt] \end{pmatrix}_{\{1,p_1\}}\bigvee \begin{pmatrix} 0 & \color{brown}{\mathbf1} & 0 & \Large| & \{0,1\} \\[-4pt] q_2 & 0 & 1 & \Large| & \{0,1\} \\[-4pt] 0 & q_2 & 0 & \Large| & 0 \\[-4pt] q_4 & 0 & q_2 & \Large| & \{0,1\} \\[-4pt] q_5+q_2 & q_4 & 0 & \Large| & \{0,1\} \\[-4pt] q_6 & q_5 & q_4 & \Large| & \{0,1\} \\[-4pt] \dots &\dots & \dots & \Large| & \dots \\[-4pt] q_{h-1}+q_{h-4} & q_{h-2} & q_{h-3} & \Large| & \{0,1\} \\[-4pt] q_{h-3} & q_{h-1} & q_{h-2} & \Large| & \{0,1\} \\[-4pt] q_{h-2} & 0 & q_{h-1} & \Large| & \{0,1\} \\[-4pt] q_{h+2}+q_{h-1} & 0 & 0 & \Large| & \{0,1\} \\[-4pt] 0 & q_{h+2} & 0 & \Large| & 0 \\[-4pt] 0 & 1 & q_{h+2} & \Large| & \{0,1\} \\[-4pt] q_{h+2} & 0 & 1 & \Large| & \{0,1\} \\[-4pt] p_3 & 0 & 0 & \Large| & 1 \\[-4pt] q_1 & 0 & 0 & \Large| & 0 \\[-4pt] q_3 & 0 & 0 & \Large| & 0 \\[-4pt] q_h & 0 & 0 & \Large| & 0 \\[-4pt] q_{h+1} & 0 & 0 & \Large| & 0 \\[-4pt] q_{h+3} & 0 & 0 & \Large| & 1 \\[-4pt] \end{pmatrix}\Rightarrow $$$$ \begin{pmatrix} q_1 & 1 & \Large| & \{0,1\} \\[-4pt] q_2 & q_1 & \Large| & \{0,1\} \\[-4pt] 0 & q_2 & \Large| & 0 \\[-4pt] q_4+q_1 & 0 & \Large| & \{0,1\} \\[-4pt] q_5+q_2 & q_4 & \Large| & \{0,1\} \\[-4pt] q_6 & q_5 & \Large| & \{0,1\} \\[-4pt] \dots &\dots & \Large| & \dots \\[-4pt] q_{h-1}+q_{h-4} & q_{h-2} & \Large| & \{0,1\} \\[-4pt] q_{h-3} & q_{h-1} & \Large| & \{0,1\} \\[-4pt] q_{h+1}+q_{h-2} & 0 & \Large| & \{0,1\} \\[-4pt] q_{h+2}+q_{h-1} & q_{h+1} & \Large| & \{0,1\} \\[-4pt] 0 & q_{h+2} & \Large| & 0 \\[-4pt] q_{h+1} & 1 & \Large| & \{0,1\} \\[-4pt] q_{h+2} & 0 & \Large| & \{0,1\} \\[-4pt] p_3 & 0 & \Large| & 1 \\[-4pt] p_2 & 0 & \Large| & 0 \\[-4pt] q_3 & 0 & \Large| & 0 \\[-4pt] q_h & 0 & \Large| & 0 \\[-4pt] q_{h+3} & 0 & \Large| & 1 \\[-4pt] \end{pmatrix}_{\{1,p_1\}}\bigvee \begin{pmatrix} 0 & 0 & \Large| & \{0,1\} \\[-4pt] q_2 & 1 & \Large| & \{0,1\} \\[-4pt] 0 & 0 & \Large| & 0 \\[-4pt] q_4 & q_2 & \Large| & \{0,1\} \\[-4pt] q_5+q_2 & 0 & \Large| & \{0,1\} \\[-4pt] q_6 & q_4 & \Large| & \{0,1\} \\[-4pt] \dots & \dots & \Large| & \dots \\[-4pt] q_{h-1}+q_{h-4} & q_{h-3} & \Large| & \{0,1\} \\[-4pt] q_{h-3} & q_{h-2} & \Large| & \{0,1\} \\[-4pt] q_{h-2} & q_{h-1} & \Large| & \{0,1\} \\[-4pt] q_{h+2}+q_{h-1} & 0 & \Large| & \{0,1\} \\[-4pt] 0 & 0 & \Large| & 0 \\[-4pt] 0 & q_{h+2} & \Large| & \{0,1\} \\[-4pt] q_{h+2} & 1 & \Large| & \{0,1\} \\[-4pt] p_1 & 0 & \Large| & 0 \\[-4pt] p_3 & 0 & \Large| & 1 \\[-4pt] q_1 & 0 & \Large| & 0 \\[-4pt] q_3 & 0 & \Large| & 0 \\[-4pt] q_h & 0 & \Large| & 0 \\[-4pt] q_{h+1} & 0 & \Large| & 0 \\[-4pt] q_{h+3} & 0 & \Large| & 1 \\[-4pt] \end{pmatrix}_{\{1,p_2\}}\bigvee \begin{pmatrix} 1 & 0 & \Large| & \{0,1\} \\[-4pt] q_2 & 1 & \Large| & \{0,1\} \\[-4pt] q_2 & 0 & \Large| & 0 \\[-4pt] q_4 & q_2 & \Large| & \{0,1\} \\[-4pt] q_2+q_4+q_5 & 0 & \Large| & \{0,1\} \\[-4pt] q_5+q_6 & q_4 & \Large| & \{0,1\} \\[-4pt] \dots & \dots & \Large| & \dots \\[-4pt] q_{h-1}+q_{h-4}+q_{h-2} & q_{h-3} & \Large| & \{0,1\} \\[-4pt] q_{h-3}+ q_{h-1} & q_{h-2} & \Large| & \{0,1\} \\[-4pt] q_{h-2} & q_{h-1} & \Large| & \{0,1\} \\[-4pt] q_{h+2}+q_{h-1} & 0 & \Large| & \{0,1\} \\[-4pt] q_{h+2} & 0 & \Large| & 0 \\[-4pt] 1 & q_{h+2} & \Large| & \{0,1\} \\[-4pt] q_{h+2} & 1 & \Large| & \{0,1\} \\[-4pt] p_1 & 0 & \Large| & 1 \\[-4pt] p_3 & 0 & \Large| & 1 \\[-4pt] q_1 & 0 & \Large| & 0 \\[-4pt] q_3 & 0 & \Large| & 0 \\[-4pt] q_h & 0 & \Large| & 0 \\[-4pt] q_{h+1} & 0 & \Large| & 0 \\[-4pt] q_{h+3} & 0 & \Large| & 1 \\[-4pt] \end{pmatrix}_{\{1,p_2\}}, $$ and all obtained $(2,h)$-matrix provides only solutions with $$(p_1,p_2,p_3,q_1,q_2,\dots,q_{h+3})\in\{0,1\}^{h+6}.$$

The common case can be proved by induction of $a$ or immediately, using combinatoric approach.

Both of approaches looks perspective ways to prove required conclusion in the arbitrary case.

$\endgroup$
  • 4
    $\begingroup$ The mistake is in the conclusion from equations (6). For instance, $p_1=q_1=1/2$, $p_{a-1}=q_{b-1}=0$ solves that system too. $\endgroup$ – Peter Mueller Sep 19 at 9:51
  • $\begingroup$ @PeterMueller Thanks a lot. Just fixed and elaborated. $\endgroup$ – Yuri Negometyanov Sep 19 at 13:25
  • 3
    $\begingroup$ I don't see how your edit fixes the problem pointed out in my comment. In fact I believe that this question does not have an easy answer. $\endgroup$ – Peter Mueller Sep 19 at 18:45
  • 3
    $\begingroup$ I am not sure how $\left(\frac12x+\dfrac12\right)(2x^2+2) = x^3+x^2+x+1$ is counter example, the conjecture is restricted to monic polynomial factors. $\endgroup$ – Sil Sep 20 at 12:59
  • 7
    $\begingroup$ @YuriNegometyanov Your various fixes resulted in a bloated answer where the initial mistakes are replaced by obscurities. You now draw conclusions without telling how the arguments are supposed to work. Instead of making the answer even longer, I suggest that you do the following: Try to formulate a proof using common mathematical language and reasoning that $p_1\in\{0,1\}$. I believe that showing even that is already quite difficult. So you will either achieve a major step towards a proof, or (what I consider more likely) you will realize that your approach does not work. $\endgroup$ – Peter Mueller Sep 22 at 16:01

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.