\documentclass[11pt,reqno]{amsart} \usepackage[T1]{fontenc} \usepackage{lmodern,microtype,mathtools,tikz,flafter} \usepackage[a4paper,textwidth=154mm,textheight=242mm,centering,headsep=6mm,footskip=10mm]{geometry} \usepackage[hidelinks]{hyperref} \hypersetup{pdftitle={The unfair 0-1 polynomial conjecture for trinomial factors}} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \setlength{\emergencystretch}{1.2em} \title[The unfair 0--1 conjecture for trinomial factors]{The unfair 0--1 polynomial conjecture\\ for trinomial factors} \date{20 November 2026} \begin{document} \begin{abstract} If a polynomial with coefficients in \(\{0,1\}\) is the product of two monic polynomials with nonnegative real coefficients and one factor is a trinomial, then both factors have coefficients in \(\{0,1\}\). Write the normalized trinomial as \(1+aX^r+X^m\). For the product and the other factor, place the coefficient of \(X^{im+jr}\) in row \(i\), column \(j\) of the corresponding array. If \(00\), it equals one and \(b_r=1-a\). This excludes \(m=2r\), for then \(c_{2r}\ge1+a(1-a)>1\). Reversing both polynomials exchanges \(r\) and \(m-r\), so we may take \(m>2r\). Write \(b_{i,j}=b_{im+jr}\) and \(c_{i,j}=c_{im+jr}\) for \(i,j\in\mathbb Z\). A step up adds \(m\) to the exponent and a step right adds \(r\). Applying \eqref{eq:cell} at exponent \(im+jr\) gives \[ b_{i,j}+b_{i-1,j}+a b_{i,j-1}=c_{i,j}. \] This identity holds even when an exponent labels several cells. If the left entry \(b_{i,j-1}\) is positive, then \(00\). A \emph{strip} runs from one drop column to the next, including both. Its width counts the steps between these columns. Within each strip we use local coordinates, with the starting drop at column zero and its bottom at row zero. \begin{lemma}[Four forced rows]\label{lem:strip} At a drop of depth \(d\), the \(d\) newly exposed cofactor entries form a binary word starting with one and ending with zero, with no adjacent ones. A widest strip has width \(k\ge5\). In every strip of width \(w\), the product digits in rows \(0,1,2,3\) equal one at all steps \(1\le j\le w\). \end{lemma} \begin{proof} At a drop of depth \(d\), the \(d\) entries below the old bottom have zero left neighbors. Their adjacent sums are binary, so induction from the new bottom shows that the entries are binary, start with one, and have no adjacent ones. A one immediately below the old bottom, together with the positive left input there, would give a product digit greater than one. The last of the new entries is therefore zero. In particular \(d\ge2\). Each drop has depth at least two, so at most \(r/2\) drops occur per period. Their spacings sum to \(m\), and the largest spacing is at least \(2m/r>4\). For example, \(r=2,m=5\) would force one drop of depth two every five steps. Fix any strip of width \(w\). Denote the cofactor entries in rows zero and one at step \(j\) by \(p_j,q_j\). Figure~\ref{fig:shared-column} follows these rows through a drop. Row \(-1\) is zero for \(j0\), which forces the row-one digit to be one as well. The two equations become \[ p_j=1-a p_{j-1},\qquad q_j=1-p_j-aq_{j-1}=a(p_{j-1}-q_{j-1}). \] Two steps in a widest strip give \(q_1=a\) and \(q_2=a(1-2a)\ge0\), so \(a\le1/2\). In fact \(a<1/2\). The roots of \(A\) are algebraic integers because they are roots of the monic integer polynomial \(C\). As a signed elementary symmetric function of these roots, \(a\) is an algebraic integer. A rational algebraic integer is an integer, which excludes \(a=1/2\). Now take any strip. Induction gives \(1-a\le p_j\le1\) and \(0a\ge q_{j-1}\). Row two receives \(q_j>0\) from below, so its product digit is one and its cofactor entry is at least \(1-q_j-a\ge1-2a>0\). This forces the digit in row three to be one. This proves the assertion through step \(w\). \end{proof} \section{Growth across a strip}\label{sec:growth} The algebraic norm of \(a\) is a nonzero integer. Since \(01\). Equation~\eqref{eq:cell} gives \(b_n\in\mathbb Z[a]\) by induction. Apply the embedding \(\sigma:\mathbb Q(a)\to\mathbb C\) that sends \(a\) to \(\lambda\). It fixes the product digits from Lemma~\ref{lem:strip}. To bound \(R\) from above, take \(D=\{\sigma(b_n):n\in\mathbb Z\}\). For \(b_n>0\) the digit \(c_{n+r}\) is one, so \eqref{eq:cell} gives \[ 1-\lambda\sigma(b_n)=\sigma(b_{n+r})+\sigma(b_{n+r-m}). \] For \(b_n=0\) we can write \(1=1+0\). Thus \(1-\lambda D\subseteq D+D\), and taking diameters gives \(R\,\mathrm{diam}(D)\le2\,\mathrm{diam}(D)\). The set \(D\) is finite and contains \(0,1\), so this gives \(R\le2\). Fix a strip of width \(w\). At step \(j\) let \(V_j(y)\) encode the cofactor entries in rows zero through three after embedding, with the entry from row \(i\) as the coefficient of \(y^i\). For \(1\le j\le w\) write \(\Delta_j=V_j-V_{j-1}\). \begin{lemma}[Column differences]\label{lem:growth} For a strip of width \(w\) preceded by one of width \(v\), there are complex numbers \(\alpha,\beta\) such that, for \(1\le j\le w\), \begin{equation}\label{eq:growth} \Delta_j=(-\lambda)^j(1+y)^{-j}(1+\alpha y^2+\beta y^3)\pmod{y^4}, \qquad |\alpha|\le R^v,\quad |\beta|\le vR^v . \end{equation} \end{lemma} \begin{proof} Work modulo \(y^4\), so multiplication by \(y\) shifts an entry up one row. Since row \(-1\) is zero, the four equations at step \(j\) combine to give \[ (1+y)V_j+\lambda V_{j-1}=U,\qquad U=1+y+y^2+y^3,\qquad 1\le j\le w. \] Subtracting the equations at steps \(j\) and \(j-1\) gives \((1+y)\Delta_j=-\lambda\Delta_{j-1}\) for \(j\ge2\). To include the first step, write its equation as \[ (1+y)\Delta_1=U-(1+y+\lambda)V_0=-\lambda\Delta_0 . \] This defines the auxiliary initial value \(\Delta_0\) that makes the recurrence hold at the first step. Its relation to the actual difference across the starting drop will depend on the product digits there. Since \(V_0=1\bmod y^2\), the constant and linear coefficients of \(\Delta_0\) are \(1,0\). Write \(\Delta_0=1+\alpha y^2+\beta y^3\). Iteration gives the formula in \eqref{eq:growth} on every strip. In particular the bottom two differences at its last step are \((-\lambda)^w\) and \(-w(-\lambda)^w\), independently of \(\alpha,\beta\). Let \(v\) be the width of the preceding strip and \(d\) the depth of the drop between them. Use the new row labels on the right of Figure~\ref{fig:shared-column}. The old steps \(v-1,v\) are now columns \(-1,0\). Let \(C_0(y)\) record the four product digits in column zero. Substituting its cell equation \((1+y)V_0+\lambda V_{-1}=C_0\) in the definition of \(\Delta_0\) gives \[ \Delta_0=(V_0-V_{-1})+(C_0-U)/\lambda \pmod{y^4}. \] In new rows \(d\le i<4\), the old strip supplies a product digit one at its final step. The correction vanishes there, and the old difference passes up by \(d\) rows. Below row \(d\), column \(-1\) is zero and column zero contains the new binary word. A one in the word forces a product digit one and has corrected difference \(1\). A zero has corrected difference \(0\) or \(-1/\lambda\), according to its product digit. Old row \(i\) becomes new row \(i+d\) at the drop. The coefficients \(\alpha,\beta\) occupy new rows two and three, respectively. Since \(d\ge2\), the only old differences that can reach them are those in the two boxed rows of Figure~\ref{fig:shared-column}. Each entry supplied by the new word has modulus at most one. Thus \[ \begin{array}{c|cc} \text{Drop depth }d & \text{Row two} & \text{Row three}\\ \hline 2 & \alpha=(-\lambda)^v & \beta=-v(-\lambda)^v\\ 3 & |\alpha|\le1 & \beta=(-\lambda)^v\\ \ge4 & |\alpha|\le1 & |\beta|\le1 \end{array} \] Since \(v\ge1\) and \(R>1\), all three cases give the bounds in \eqref{eq:growth}. \end{proof} \section{A Fourier bound for column differences}\label{sec:filter} At the end of a widest strip of width \(k\), the bottom difference has modulus \(R^k\). For \(R\) close to one this alone gives little growth. The next three rows involve the linear, quadratic, and cubic coefficients of \((1+y)^{-k}\). We will compare their contributions with a bound from the entire product. In fixed coordinates write \[ b^\Delta_{i,j}=\sigma(b_{i,j})-\sigma(b_{i,j-1}),\qquad c^\Delta_{i,j}=c_{i,j}-c_{i,j-1}. \] These arrays are bounded, and \(|c^\Delta_{i,j}|\le1\). Let \(y\) shift entries up one row and \(z\) shift them right one column. Subtracting the cell equations gives \[ F*b^\Delta=c^\Delta,\qquad F(y,z)=1+y+\lambda z, \] where \(*\) denotes convolution. A polynomial \(P(y)\) combines differences in neighboring rows. To bound \(P*b^\Delta\) it suffices to find \(K=P/F\) with absolutely summable Fourier coefficients \(\widehat K\). The identity \(KF=P\) will then express each filtered entry as a weighted sum of product-digit differences. Put \(x=R^2\). To choose \(P\), first locate the zeros of \(F\) on the torus \(|y|=|z|=1\). For a fixed \(y\), the zero \(z=-(1+y)/\lambda\) lies on the unit circle precisely when \(|1+y|=R\). The polynomial \[ Q(y)=(1+y)^2-xy \] detects this condition, since \(Q(y)/y=|1+y|^2-x\). Indeed, \(|Q|=\big||1+y|-R\big|(|1+y|+R)\le |F|(2+R)\) on the torus. Hence \(|Q^2/F|\le(2+R)|Q|\) wherever \(F\ne0\), and the quotient extends continuously by zero at every zero of \(F\). The coefficients of \((1+y)^{-k}\) alternate. Replacing \(y\) by \(-y\) makes them positive. The cubic \((1+y)Q(-y)\) also has nonnegative coefficients for \(x\ge1\). Its square provides the factor \(Q^2\) needed at the zeros of \(F\). Thus take \begin{equation}\label{eq:filter} P(y)=\big((1-y)Q(y)\big)^2,\qquad P(-y)=\big(1+(x-1)y+(x-1)y^2+y^3\big)^2 . \end{equation} \begin{proposition}[Fourier bound]\label{prop:kernel} Let \(1\le|\lambda|=R\le2\), \(F(y,z)=1+y+\lambda z\), and \(P\) be as in \eqref{eq:filter} with \(x=R^2\). The continuous extension \(K\) of \(P/F\) to the torus satisfies \[ \sum_{n,s\in\mathbb Z}|\widehat K(n,s)|<25R^3. \] \end{proposition} Appendix~\ref{app:fourier} proves Proposition~\ref{prop:kernel}. To apply it, observe that \(KF=P\) holds on the entire torus, including the zeros of \(F\). Taking Fourier coefficients gives \(\widehat K*F=P\). Proposition~\ref{prop:kernel} gives \(\widehat K\in\ell^1(\mathbb Z^2)\). Since \(F\) has finite support and \(b^\Delta\) is bounded, we may associate the convolutions. Using \(F*b^\Delta=c^\Delta\) and \(|c^\Delta_{i,j}|\le1\) gives \begin{equation}\label{eq:bound} \big|(P*b^\Delta)_{i,j}\big|=\big|(\widehat K*c^\Delta)_{i,j}\big|\le\sum_{n,s}|\widehat K(n,s)|<25R^3 \qquad (i,j\in\mathbb Z). \end{equation} In particular, this bound is independent of the strip width \(k\), whereas the differences at the last column contain the factor \((-\lambda)^k\) from \eqref{eq:growth}. \section{Excluding a widest strip}\label{sec:end} \begin{proof}[Proof of Theorem~\ref{thm:main}] Assume \(00\) and \(L_{k+1}-L_k=B_{k+1}\). Consequently \begin{equation}\label{eq:lower} B_k/x\ge14,\qquad L_k/x\ge36+6t+14(k-5). \end{equation} The full convolution also sees the rows below zero. At the last column they contain the newly exposed word \(\eta_i\) (\(i<0\)), extended by zeros below its bottom. Its entries are the actual differences there, since the preceding column was zero below row zero. In particular \(\eta_{-1}=0\) by Lemma~\ref{lem:strip}. Writing \(P_n=[y^n]P(y)\), the boundary contribution in output row \(i=1,2,3\) is \[ E_i=\sum_{n=i+2}^6P_n\eta_{i-n},\qquad (P_3,P_4,P_5,P_6)=\big(-2(1+t^2),\,t^2+2t,\,-2t,\,1\big). \] The positive coefficients sum to \(x^2\). The total modulus of the negative ones is at most \(2x^2\) in row one and at most \(2t\le x^2\) once \(P_3\) is omitted. As each \(\eta_{i-n}\) is zero or one, \(|E_1|\le2x^2\) and \(|E_2|,|E_3|\le x^2\). To compare with \eqref{eq:bound}, divide by \(xR^k\) and set \(u=R^k/x=R^{k-2}>1\). The global bound becomes \(25/(Ru)\le25/u\) and the three boundary bounds become \(2/u,1/u,1/u\). The bounds on the inherited terms give \(|\alpha|/x\le u\) and \(|\beta|/x\le ku\). For example, row two gives \(|B_k+\alpha|/x<26/u\), hence \(B_k/x0 . \] Also \(u<3\), so the rest of the upper bound in \eqref{eq:row3} satisfies \(2(k-5+t)u\le6(k-5+t)\). Adding gives \(L_k/x<36+6t+6(k-5)\), contrary to \eqref{eq:lower}. Thus \(a=1\), and the induction in \eqref{eq:cell} makes \(B\) binary. \end{proof} \smallskip\noindent\textit{Verification.} The Lean formalization of Theorem~\ref{thm:main}, including Proposition~\ref{prop:kernel}, uses mathlib and is available on GitHub at \href{https://github.com/esonde/unfair-polynomials-conjecture}{\texttt{esonde/unfair-polynomials-conjecture}}. \appendix \section{Proof of the Fourier bound}\label{app:fourier} We prove Proposition~\ref{prop:kernel}. With \(x=|\lambda|^2=R^2\), the kernel from Section~\ref{sec:filter} is \[ K(y,z)=\frac{(1-y)^2\big((1+y)^2-xy\big)^2}{1+y+\lambda z} \] on the unit torus, with its continuous extension at the zeros of the denominator. Our goal is to bound the sum of the absolute values of its Fourier coefficients by \(25R^3\). Expanding first in \(z\) gives a geometric series for each fixed \(y\). We then use Parseval's identity in the remaining variable to estimate all the coefficients together. \subsection*{Expansion in the column variable} Rotating \(z\) changes only the phases of the Fourier coefficients, so we may set \(\lambda=R\). Write \(y=T^2\) with \(T=e^{i\theta}\) and set \[ b=2\cos\theta,\qquad h=b^2,\qquad \omega=4-h . \] The substitution doubles row frequencies and preserves the sum of absolute coefficients. Since \(1+T^2=Tb\), \(Q(T^2)=T^2(h-x)\), and \((1-T^2)^2=-T^2\omega\), the kernel becomes \[ K(T^2,z)=-T^5\omega\,\frac{(h-x)^2}{b+Rz/T}. \] For fixed \(\theta\), expand the quotient in \(z/T\) when \(|b|>R\) and in its reciprocal when \(|b|R),\qquad g_{-j-1}(b)=(h-x)^2\frac{(-b)^j}{R^{j+1}}\quad (|b|R,\\[2pt] x^{-1}\sum_{j\ge0}(j+\tfrac12)(u/x)^j,& |b|,|v|