Algorithmic aspects of Newman polynomials and their divisors

We study the problem of determining which integer polynomials divide Newman polynomials. First, we investigate the 8 438 known polynomials with Mahler measure less than 1.3. Apart from the polynomials having a positive real root, all but three of them are shown to divide a Newman polynomial of degree at most 1000. Second, using an algorithmic certification method of Hare and Mossingho, we exhibit several polynomials that divide no Newman polynomial. Among them is a degree-10 polynomial with Mahler measure approximately equal to 1.419404632, which improves the best known upper bound for any universal constant σ, if such a constant exists, governing the existence of Newman multiples in terms of Mahler measure. Finally, writing l(x) for the polynomial obtained from Lehmer’s polynomial by the substitution x ↦ −x, we explicitly construct Newman polynomials divisible by l(x)² with degrees up to 150, and show that no Newman polynomial of degree at most 160 is divisible by l(x)³.