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 at 12:23
• The conditions at least easily imply that all coefficients of $P$ and $Q$ are in $[0,1]$. – Emil Jeřábek supports Monica Aug 25 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. – Will Sawin Aug 25 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? – Gro-Tsen Aug 25 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. – Lutz Mattner Aug 26 at 8:45

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.

• 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. – Peter Mueller Sep 19 at 9:51
• @PeterMueller Thanks a lot. Just fixed and elaborated. – Yuri Negometyanov Sep 19 at 13:25
• 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. – Peter Mueller Sep 19 at 18:45
• 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. – Sil Sep 20 at 12:59
• @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. – Peter Mueller Sep 22 at 16:01