The Lowest-Degree Polynomial with Nonnegative Coefficients Divisible by the $n$-th Cyclotomic Polynomial

Abstract

We pose the question of determining the lowest-degree polynomial with nonnegative coefficients divisible by the $n$-th cyclotomic polynomial $\Phi_n(x)$. We show this polynomial is $1 + x^{n/p} + \cdots + x^{(p-1)n/p}$ where $p$ is the smallest prime dividing $n$ whenever $2/p > 1/q_1 + \cdots + 1/q_k$, where $q_1, \ldots, q_k$ are the other (distinct) primes besides $p$ dividing $n$. Determining the lowest-degree polynomial with nonnegative coefficients divisible by $\Phi_n(x)$ remains open in the general case, though we conjecture the existence of values of $n$ for which this degree is, in fact, less than $(p-1)n/p$.