×

On Newman polynomials which divide no Littlewood polynomial. (English) Zbl 1208.11123

A Newman polynomial is an element of \(\mathbb{Z}[x]\) with coefficients in \(\{0,1\}\) and constant term \(1.\) A Littlewood polynomial is one with coefficients in \(\{-1,1\}.\) Let \(V_{\mathcal{N}}\) be the set of roots of Newman polynomials, \(V_{\mathcal{L}}\) the roots of Littlewood polynomials, and \(V\) the roots of polynomials with coefficients in \(\{-1,0,1\}\) with nonzero constant term. The authors study the relationships amongst \(V_{\mathcal{N}},\) \(V_{\mathcal{L}}\), and \(V.\) In particular, they show that \(V_{\mathcal{N}}\) is not a subset of \(V_{\mathcal{L}}\) (and hence \(V_{\mathcal{N}},\) \(V_{\mathcal{L}},\) and \(V\) are distinct sets) by giving explicit examples of irreducible Newman polynomials that do not divide any Littlewood polynomial; e.g., \(x^9+x^6+x^2+x+1\). They also show that there are no such Newman polynomials of degree less than or equal to \(8\). On the other hand, the authors prove that every Newman trinomial \(1+x^a+x^b\) divides some Littlewood polynomial. A similar result is obtained for certain quadrinomials as well. The proofs are mostly computational. Two numerical algorithms are given: one for checking whether a polynomial in \(\mathbb{Z}[x]\) can divide a Littlewood polynomial, and one that determines whether a given Newman polynomial \(P\) divides a Littlewood polynomial \(L\) such that the height of \(L/P\) is less than or equal to a given integer.

MSC:

11R09 Polynomials (irreducibility, etc.)
11Y16 Number-theoretic algorithms; complexity
11C08 Polynomials in number theory

Software:

C-XSC 2.0; gmp; C-XSC
Full Text: DOI

References:

[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). · Zbl 0855.11010
[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. · Zbl 0922.30004 · doi: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. · Zbl 0889.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/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. · Zbl 1172.11034
[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. · Zbl 1143.11349 · doi: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. · Zbl 0999.12001
[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. · Zbl 0901.11022 · doi:10.4153/CJM-1997-047-3
[9] P. Drungilas and A. Dubickas, Roots of polynomials of bounded height, Rocky Mt. J. Math. (to appear). · Zbl 1186.12001
[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. · Zbl 1074.11018 · doi: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. · Zbl 0928.11015
[12] Michael Filaseta and Manton Matthews Jr., On the irreducibility of 0,1-polynomials of the form \?(\?)\?\(^{n}\)+\?(\?), Colloq. Math. 99 (2004), no. 1, 1 – 5. · Zbl 1060.11066 · doi: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/\( \sim\)xsc/). · Zbl 1126.65328
[14] Michael J. Mossinghoff, Polynomials with restricted coefficients and prescribed noncyclotomic factors, LMS J. Comput. Math. 6 (2003), 314 – 325. · Zbl 1134.11319 · doi: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. · Zbl 0814.30006
[16] Andrzej Schinzel, On the reduced length of a polynomial with real coefficients, Funct. Approx. Comment. Math. 35 (2006), 271 – 306. · Zbl 1192.12001 · doi:10.7169/facm/1229442629
[17] GMP, The GNU Multiple Precision Arithmetic Library (available online at http://swox.com/gmp/).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.