The trinomials 1+ax^3+x^k are not unfair factors of 0-1 polynomials
A special case of the unfair 0–1 polynomial conjecture (MathOverflow 339137, Problem 28 in Ben Green’s list of 100 open problems): if a 0–1 polynomial factors into two monic polynomials with nonnegative coefficients, are both factors 0–1? The preceding case 1+ax²+xᵏ was treated by Dvorsky (2026).
- \(P\,Q \in \{0,1\}[x],\ Q \ge 0 \ \Rightarrow\ Q = 0 \quad (k \ge 4,\ 0\lt a\lt 1)\)
- \(q_n + a\,q_{n-3} + q_{n-k} = r_n \in \{0,1\}\)
- \(\tfrac12\lt a\lt 1:\ \text{by hand, partly checked in Lean 4}\)
- \(k \ge 67:\ \text{one interval certificate uniform in } k;\ \ k \le 149:\ \text{exact certificates}\)
Abstract
The unfair 0-1 polynomial conjecture asserts that if a polynomial with coefficients in {0,1} factors as a product of two monic polynomials with nonnegative real coefficients, then both factors are 0-1 polynomials. We prove that for every k >= 4 with k not divisible by 3 and every 0 < a < 1, the trinomial 1 + a x^3 + x^k does not divide any 0-1 polynomial with a nonzero cofactor having nonnegative coefficients; by reciprocity the same holds for 1 + a x^(k-3) + x^k. The proof analyses the forced recurrence q_n + a q_{n-3} + q_{n-k} = r_n in {0,1}. An exact class formula for the coefficients along a distinguished main branch and elementary deviation lemmas reduce the problem to the main branch; for a in (1/2,1) this is settled by hand, and for a in (0,1/2] and k >= 67 by a single rigorous interval-arithmetic certificate that is uniform in k. The remaining range k <= 149 is covered by exhaustive computer certificates with exact algebraic treatment of isolated parameters.
Cite
Otakhon U. Kenjaev (2026). The trinomials 1+ax^3+x^k are not unfair factors of 0-1 polynomials. Zenodo. https://doi.org/10.5281/zenodo.23311094