On Newman polynomials which divide no Littlewood polynomial
Authors:
Arturas Dubickas and Jonas Jankauskas
Journal:
Math. Comp. 78 (2009), 327344
MSC (2000):
Primary 11R09, 11Y16, 12D05
Published electronically:
May 16, 2008
MathSciNet review:
2448710
Fulltext 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
(97a:11120)
 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
(99c:30005), http://dx.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
(98k:30006), http://dx.doi.org/10.1090/S0025571898009600
 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/clusterpages/ 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), 347366.
 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
(2004m:11177), http://dx.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
(2001k:11036)
 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
(98m:11014), http://dx.doi.org/10.4153/CJM19970473
 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
(2006e:11162), http://dx.doi.org/10.4064/aa11915
 11.
Michael
Filaseta, On the factorization of polynomials with small Euclidean
norm, Number theory in progress, Vol. 1 (ZakopaneKościelisko,
1997) de Gruyter, Berlin, 1999, pp. 143–163. MR 1689504
(2000c:11177)
 12.
Michael
Filaseta and Manton
Matthews Jr., On the irreducibility of 0,1polynomials of the form
𝑓(𝑥)𝑥ⁿ+𝑔(𝑥), Colloq.
Math. 99 (2004), no. 1, 1–5. MR 2084532
(2005g:11205), http://dx.doi.org/10.4064/cm9911
 13.
W. Hofschuster and W. Krämer, CXSC 2.0: A C++ Class Library for Extended Scientific Computing, Numerical Software with Result Verification, Lecture Notes in Computer Science, 2991, SpringerVerlag, Heidelberg, (2004) 1535 (available online at http://www.math.uniwuppertal.de/xsc/).
 14.
Michael
J. Mossinghoff, Polynomials with restricted coefficients and
prescribed noncyclotomic factors, LMS J. Comput. Math.
6 (2003), 314–325 (electronic). MR 2051588
(2004m:11034), http://dx.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. 34, 317–348. MR 1252071
(95b:11026)
 16.
Andrzej
Schinzel, On the reduced length of a polynomial with real
coefficients, Funct. Approx. Comment. Math. 35
(2006), 271–306. MR 2271619
(2007h:12001), http://dx.doi.org/10.7169/facm/1229442629
 17.
GMP, The GNU Multiple Precision Arithmetic Library (available online at http://swox.com/gmp/).
 1.
 F. Amoroso, Polynomials with prescribed vanishing at roots of unity, Boll. Un. Mat. Ital. B(7), 9 (1995), 10211024. MR 1369388 (97a:11120)
 2.
 F. Beaucoup, P. Borwein, D .W. Boyd and C. Pinner, Multiple roots of power series, J. London Math. Soc. (2), 57 (1998), 135147. 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), 715736. 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 http://www.dm.unipi.it/clusterpages/ 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), 347366.
 6.
 P. Borwein, K. G. Hare and M. J. Mossinghoff, The Mahler measure of polynomials with odd coefficients, Bull. London Math. Soc., 36 (2004), 332338. MR 2038720 (2004m:11177)
 7.
 P. Borwein and M. J. Mossinghoff, Polynomials with height and prescribed vanishing at , Exper. Math., 9 (2000), 425433. MR 1795875 (2001k:11036)
 8.
 P. Borwein and C. Pinner, Polynomials with coefficients and a root close to a given point. Canadian J. Math., 49 (1997), 887915. 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), 6579. MR 2163518 (2006e:11162)
 11.
 M. Filaseta, On the factorization of polynomials with small Euclidean norm, In: Number theory in progress (ZakopaneKoscielisko, 1997), de Gruyter, Berlin, 1 (1999), 143163. MR 1689504 (2000c:11177)
 12.
 M. Filaseta and M. Matthews, Jr., On the irreducibility of 0,  polynomials of the form , Colloq. Math., 99 (2004), 15. MR 2084532 (2005g:11205)
 13.
 W. Hofschuster and W. Krämer, CXSC 2.0: A C++ Class Library for Extended Scientific Computing, Numerical Software with Result Verification, Lecture Notes in Computer Science, 2991, SpringerVerlag, Heidelberg, (2004) 1535 (available online at http://www.math.uniwuppertal.de/xsc/).
 14.
 M. J. Mossinghoff, Polynomials with restricted coefficients and prescribed noncyclotomic factors, LMS J. Comput. Math., 3 (2003), 314325. MR 2051588 (2004m:11034)
 15.
 A. M. Odlyzko and B. Poonen, Zeros of polynomials with coefficients, Enseign. Math., 39 (1993), 317384. MR 1252071 (95b:11026)
 16.
 A. Schinzel, On the reduced length of a polynomial, Funct. Approx., Comment. Math., 35 (2006), 271306. MR 2271619 (2007h:12001)
 17.
 GMP, The GNU Multiple Precision Arithmetic Library (available online at http://swox.com/gmp/).
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 LT03225, Lithuania and Institute of Mathematics and Informatics, Akademijos 4, Vilnius LT08663, Lithuania
Email:
arturas.dubickas@mif.vu.lt
Jonas Jankauskas
Affiliation:
Department of Mathematics and Informatics, Vilnius University, Naugarduko 24, Vilnius LT03225, Lithuania
Email:
jonas.jankauskas@gmail.com
DOI:
http://dx.doi.org/10.1090/S0025571808021388
PII:
S 00255718(08)021388
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.
