On Cyclotomic Polynomials with ± 1 Coefficients

We characterize all cyclotomic polynomials of even degree with coefficients restricted to the set {+1, −1}. In this context a cyclotomic polynomial is any monic polynomial with integer coefficients and all roots of modulus 1. Inter alia we characterize all cyclotomic polynomials with odd coefficients. The characterization is as follows. A polynomial P(x) with coefficients ±1 of even degree N–l is cyclotomic if and only if where N = P1P1 … Pr and the Pi are primes, not necessarily distinct, and where ϕp(x) := (xp – 1)/ (x – 1) isthe p-th cyclotomic polynomial. We conjecture that this characterization also holds for polynomials of odd degree with ±1 coefficients. This conjecture is based on substantial computation plus a number of special cases. Central to this paper is a careful analysis of the effect of Graeffe's root squaring algorithm on cyclotomic polynomials.