Newman polynomials with prescribed vanishing and integer sets with distinct subset sums

Abstract:

We study the problem of determining the minimal degree $d(m)$ of a polynomial that has all coefficients in $\{0,1\}$ and a zero of multiplicity $m$ at $-1$. We show that a greedy solution is optimal precisely when $m\leq 5$, mirroring a result of Boyd on polynomials with $\pm 1$ coefficients. We then examine polynomials of the form $\prod _{e\in E} (x^e+1)$, where $E$ is a set of $m$ positive odd integers with distinct subset sums, and we develop algorithms to determine the minimal degree of such a polynomial. We determine that $d(m)$ satisfies inequalities of the form $2^m + c_1 m \leq d(m) \leq \frac {103}{96}\cdot 2^m + c_2$. Last, we consider the related problem of finding a set of $m$ positive integers with distinct subset sums and minimal largest element and show that the Conway-Guy sequence yields the optimal solution for $m\leq 9$, extending some computations of Lunnon.