### abstract

- Let N ∗(m) be the minimal length of a polynomial with ± 1c oef- ficients divisible by (x − 1)m. Byrnes noted that N ∗(m) ≤ 2m for each m, and asked whether in fact N ∗(m )=2 m. Boyd showed that N ∗(m )=2 m for all m ≤ 5, but N ∗(6) = 48. He further showed that N ∗(7) = 96, and that N ∗(8) is one of the 5 numbers 96, 144, 160, 176, or 192. Here we prove that N ∗(8) = 144. Similarly, let m∗(N ) be the maximal power of (x − 1) dividing some polynomial of degree N − 1w ith±1 coefficients. Boyd was able to find m∗(N )f or N< 88. In this paper we determine m∗(N )f or N< 168. j=0 x2 j − 1 . be large, N has to be divisible by a large power of 2. Also, if N fails to be divisible by some small prime, then it has to be exponentially large (as a function of m )f or P(N, m )t o be nonempty. Boyd's approach is based on an ingenious exploitation of the fact that, if P (x) ∈ P(N, m), then, in particular, for any algebraic integer ζ, the algebraic integer P (ζ) is divisible by (ζ − 1)m. In general, this would be of little help, as P (ζ )m ay take