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

DOI:
https://doi.org/10.1090/S0025-5718-08-02138-8

Published electronically:
May 16, 2008

MathSciNet review:
2448710

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Recall that a polynomial with coefficients and constant term is called a Newman polynomial, whereas a polynomial with coefficients is called a Littlewood polynomial. Is there an algebraic number 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 of degree at most we find a Littlewood polynomial divisible by . Moreover, it is shown that every trinomial where are positive integers and so, in particular, every Newman trinomial divides some Littlewood polynomial. Nevertheless, we prove that there exist Newman polynomials which divide no Littlewood polynomial, e.g., 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 , Littlewood polynomials and polynomials are distinct in the sense that between them there are only trivial relations and Moreover, The proofs of several main results (after some preparation) are computational.

**1.**Francesco Amoroso,*Polynomials with prescribed vanishing at roots of unity*, Boll. Un. Mat. Ital. B (7)**9**(1995), no. 4, 1021–1042 (English, with Italian summary). MR**1369388****2.**Frank Beaucoup, Peter Borwein, David W. Boyd, and Christopher Pinner,*Multiple roots of [-1,1] power series*, J. London Math. Soc. (2)**57**(1998), no. 1, 135–147. MR**1624809**, https://doi.org/10.1112/S0024610798005857**3.**Franck Beaucoup, Peter Borwein, David W. Boyd, and Christopher Pinner,*Power series with restricted coefficients and a root on a given ray*, Math. Comp.**67**(1998), no. 222, 715–736. MR**1468939**, https://doi.org/10.1090/S0025-5718-98-00960-0**4.**D. A. Bini and G. Fiorentino,*Numerical computation of polynomial roots v. 2.0*, FRISCO report (1998) (available online at`http://www.dm.unipi.it/cluster-pages/ 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.**Peter Borwein, Kevin G. Hare, and Michael J. Mossinghoff,*The Mahler measure of polynomials with odd coefficients*, Bull. London Math. Soc.**36**(2004), no. 3, 332–338. MR**2038720**, https://doi.org/10.1112/S002460930300287X**7.**Peter Borwein and Michael J. Mossinghoff,*Polynomials with height 1 and prescribed vanishing at 1*, Experiment. Math.**9**(2000), no. 3, 425–433. MR**1795875****8.**Peter Borwein and Christopher Pinner,*Polynomials with {0,+1,-1} coefficients and a root close to a given point*, Canad. J. Math.**49**(1997), no. 5, 887–915. MR**1604114**, https://doi.org/10.4153/CJM-1997-047-3**9.**P. Drungilas and A. Dubickas,*Roots of polynomials of bounded height*, Rocky Mt. J. Math. (to appear).**10.**Artūras Dubickas and Michael J. Mossinghoff,*Auxiliary polynomials for some problems regarding Mahler’s measure*, Acta Arith.**119**(2005), no. 1, 65–79. MR**2163518**, https://doi.org/10.4064/aa119-1-5**11.**Michael Filaseta,*On the factorization of polynomials with small Euclidean norm*, Number theory in progress, Vol. 1 (Zakopane-Kościelisko, 1997) de Gruyter, Berlin, 1999, pp. 143–163. MR**1689504****12.**Michael Filaseta and Manton Matthews Jr.,*On the irreducibility of 0,1-polynomials of the form 𝑓(𝑥)𝑥ⁿ+𝑔(𝑥)*, Colloq. Math.**99**(2004), no. 1, 1–5. MR**2084532**, https://doi.org/10.4064/cm99-1-1**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`http://www.math.uni-wuppertal.de/xsc/`).**14.**Michael J. Mossinghoff,*Polynomials with restricted coefficients and prescribed noncyclotomic factors*, LMS J. Comput. Math.**6**(2003), 314–325. MR**2051588**, https://doi.org/10.1112/S1461157000000474**15.**A. M. Odlyzko and B. Poonen,*Zeros of polynomials with 0,1 coefficients*, Enseign. Math. (2)**39**(1993), no. 3-4, 317–348. MR**1252071****16.**Andrzej Schinzel,*On the reduced length of a polynomial with real coefficients*, Funct. Approx. Comment. Math.**35**(2006), 271–306. MR**2271619**, https://doi.org/10.7169/facm/1229442629**17.**GMP,*The GNU Multiple Precision Arithmetic Library*(available online at`http://swox.com/gmp/`).

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

Email:
arturas.dubickas@mif.vu.lt

**Jonas Jankauskas**

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

Email:
jonas.jankauskas@gmail.com

DOI:
https://doi.org/10.1090/S0025-5718-08-02138-8

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.