Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



On Newman polynomials which divide no Littlewood polynomial

Authors: Arturas Dubickas and Jonas Jankauskas
Journal: Math. Comp. 78 (2009), 327-344
MSC (2000): Primary 11R09, 11Y16, 12D05
Published electronically: May 16, 2008
MathSciNet review: 2448710
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Recall that a polynomial $ P(x) \in \mathbb{Z}[x]$ with coefficients $ 0, 1$ and constant term $ 1$ is called a Newman polynomial, whereas a polynomial with coefficients $ -1, 1$ is called a Littlewood polynomial. Is there an algebraic number $ \alpha$ which is a root of some Newman polynomial but is not a root of any Littlewood polynomial? In other words (but not equivalently), is there a Newman polynomial which divides no Littlewood polynomial? In this paper, for each Newman polynomial $ P$ of degree at most $ 8,$ we find a Littlewood polynomial divisible by $ P$. Moreover, it is shown that every trinomial $ 1+ux^a+vx^b,$ where $ a<b$ are positive integers and $ u, v \in \{-1,1\},$ so, in particular, every Newman trinomial $ 1+x^a+x^b,$ divides some Littlewood polynomial. Nevertheless, we prove that there exist Newman polynomials which divide no Littlewood polynomial, e.g., $ x^9+x^6+x^2+x+1.$ This example settles the problem 006:07 posed by the first named author at the 2006 West Coast Number Theory conference. It also shows that the sets of roots of Newman polynomials $ V_{\mathcal{N}}$, Littlewood polynomials $ V_{\mathcal{L}}$ and $ \{-1,0,1\}$ polynomials $ V$ are distinct in the sense that between them there are only trivial relations $ V_{\mathcal{N}}\subset V$ and $ V_{\mathcal{L}}\subset V.$ Moreover, $ V \ne V_{\mathcal{L}} \cup V_{\mathcal{N}}.$ The proofs of several main results (after some preparation) are computational.

References [Enhancements On Off] (What's this?)

  • 1. F. Amoroso, Polynomials with prescribed vanishing at roots of unity, Boll. Un. Mat. Ital. B(7), 9 (1995), 1021-1024. MR 1369388 (97a:11120)
  • 2. F. Beaucoup, P. Borwein, D .W. Boyd and C. Pinner, Multiple roots of $ [-1, 1]$ power series, J. London Math. Soc. (2), 57 (1998), 135-147. MR 1624809 (99c:30005)
  • 3. F. Beaucoup, P. Borwein, D .W. Boyd and C. Pinner, Power series with restricted coefficients and a root on a given ray, Math. Comp., 67 (1998), 715-736. MR 1468939 (98k:30006)
  • 4. D. A. Bini and G. Fiorentino, Numerical computation of polynomial roots v. 2.0, FRISCO report (1998) (available online at mpsolve/index.htm).
  • 5. P. Borwein, E. Dobrowolski and M. J. Mossinghoff, Lehmer's problem for polynomials with odd coefficients, Ann. of Math. (2), 166 (2007), 347-366.
  • 6. P. Borwein, K. G. Hare and M. J. Mossinghoff, The Mahler measure of polynomials with odd coefficients, Bull. London Math. Soc., 36 (2004), 332-338. MR 2038720 (2004m:11177)
  • 7. P. Borwein and M. J. Mossinghoff, Polynomials with height $ 1$ and prescribed vanishing at $ 1$, Exper. Math., 9 (2000), 425-433. MR 1795875 (2001k:11036)
  • 8. P. Borwein and C. Pinner, Polynomials with $ \{0, +1, -1\}$ coefficients and a root close to a given point. Canadian J. Math., 49 (1997), 887-915. MR 1604114 (98m:11014)
  • 9. P. Drungilas and A. Dubickas, Roots of polynomials of bounded height, Rocky Mt. J. Math. (to appear).
  • 10. A. Dubickas and M. J. Mossinghoff, Auxiliary polynomials for some problems regarding Mahler's measure, Acta Arith., 119 (2005), 65-79. MR 2163518 (2006e:11162)
  • 11. M. Filaseta, On the factorization of polynomials with small Euclidean norm, In: Number theory in progress (Zakopane-Koscielisko, 1997), de Gruyter, Berlin, 1 (1999), 143-163. MR 1689504 (2000c:11177)
  • 12. M. Filaseta and M. Matthews, Jr., On the irreducibility of 0, $ 1$ - polynomials of the form $ f(x)x^n+g(x)$, Colloq. Math., 99 (2004), 1-5. MR 2084532 (2005g:11205)
  • 13. W. Hofschuster and W. Krämer, C-XSC 2.0: A C++ Class Library for Extended Scientific Computing, Numerical Software with Result Verification, Lecture Notes in Computer Science, 2991, Springer-Verlag, Heidelberg, (2004) 15-35 (available online at$ \sim$xsc/).
  • 14. M. J. Mossinghoff, Polynomials with restricted coefficients and prescribed noncyclotomic factors, LMS J. Comput. Math., 3 (2003), 314-325. MR 2051588 (2004m:11034)
  • 15. A. M. Odlyzko and B. Poonen, Zeros of polynomials with $ 0, 1$ coefficients, Enseign. Math., 39 (1993), 317-384. MR 1252071 (95b:11026)
  • 16. A. Schinzel, On the reduced length of a polynomial, Funct. Approx., Comment. Math., 35 (2006), 271-306. MR 2271619 (2007h:12001)
  • 17. GMP, The GNU Multiple Precision Arithmetic Library (available online at

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11R09, 11Y16, 12D05

Retrieve articles in all journals with MSC (2000): 11R09, 11Y16, 12D05

Additional Information

Arturas Dubickas
Affiliation: Department of Mathematics and Informatics, Vilnius University, Naugarduko 24, Vilnius LT-03225, Lithuania -and- Institute of Mathematics and Informatics, Akademijos 4, Vilnius LT-08663, Lithuania

Jonas Jankauskas
Affiliation: Department of Mathematics and Informatics, Vilnius University, Naugarduko 24, Vilnius LT-03225, Lithuania

Keywords: Newman polynomial, Littlewood polynomial
Received by editor(s): December 10, 2007
Received by editor(s) in revised form: January 14, 2008
Published electronically: May 16, 2008
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society