ON CYCLOTOMIC POLYNOMIALS WITH ±1 COEFFICIENTS

PETER BORWEIN AND KWOK-KWONG STEPHEN CHOI

Abstract. 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−1 is cyclotomic if and only if

P (x) = ±ol_{p_{1}}(±x) \begin{matrix}o \\ l \end{matrix}_{p_{2}}(±x^{p_{1}}) ⋯ ol_{p_{r}}(±x^{p_{1}p_{2}···p_{r−1}}),

where N = p_{1}p_{2} ⋯ p_{r} and the p_{i} are primes, not necessarily distinct, and where ol_{p}(x) := (x^{p} − 1)/(x − 1) is the 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.