On Cyclotomic Polynomials with ± 1 Coefficients

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–l is cyclotomic if and only if

where N = P₁P₁ … P_r and the P_i are primes, not necessarily distinct, and where ϕ_p(x) := (x^p – 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.

Keywords:

• Cyclotomic polynomials
• Mahler measure
• Littlewood polynomials