On a Problem of Byrnes concerning Polynomials with Restricted Coefficients

We consider a question of Byrnes concerning the minimal degree $n$ of a polynomial with all coefficients in $\{-1,1\}$ which has a zero of a given order $m$ at $x = 1$. For $m \le 5$, we prove his conjecture that the monic polynomial of this type of minimal degree is given by $\prod _{k=0}^{m-1} (x^{2^{k}}-1)$, but we disprove this for $m \ge 6$. We prove that a polynomial of this type must have $n \ge e^{\sqrt {m}(1 + o(1))}$, which is in sharp contrast with the situation when one allows coefficients in $\{-1,0,1\}$. The proofs use simple number theoretic ideas and depend ultimately on the fact that $-1 \equiv 1 \pmod 2$.