Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-24T10:38:55.376Z Has data issue: false hasContentIssue false
  • English
  • Français

Polynomials with Restricted Coefficients and Prescribed Noncyclotomic Factors

Published online by Cambridge University Press:  01 February 2010

Michael J. Mossinghoff
Michael J. Mossinghoff
Affiliation:
Department of Mathematics, Davidson College, Davidson, NC 28035, USA [email protected], http://www.davidson.edu/math/mossinghoff

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The algorithms described in this paper were developed to investigate three problems regarding polynomials with restricted coefficients: (i) determining whether there exist polynomials with {0, 1} coefficients and repeated noncyclotomic factors, (ii) searching for polynomials with {−1, 1} coefficients and small Mahler measure, and (iii) finding polynomials with {−1, 0, 1} coefficients with a root of high multiplicity off the unit circle. The results in the first problem presented here answer a question of Odlyzko and Poonen.

Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 6 , 2003 , pp. 314 - 325
Copyright
Copyright © London Mathematical Society 2003

References

1Amoroso, F., ‘Polynomials with prescribed vanishing at roots of unity’, Boll. Un. Mat. Ital. B (7) 9 (1995) 1021–1042.Google Scholar
2Bailey, D.H. and Broadhurst, D., ‘A seventeenth-order polylogarithm ladder’, arXiv:math.CA⁄9906134, 18 pp.Google Scholar
3Beaucoup, F., Borwein, P., Boyd, D.W. and Pinner, C., ‘Multiple roots of [–1, 1] power series’, J. London Math. Soc. (2) 57 (1998) 135–147.CrossRefGoogle Scholar
4Bombieri, E. and Vaaler, J.D., ‘Polynomials with low height and prescribed vanishing’, Analytic number theory and Diophantine problems (Stillwater, Oklahoma, 1984), Prog. Math. 70 (ed. Adolphson, A.C., Conrey, J.B., Ghosh, A. and Yager, R.I., Birkhäuser, Basel, 1987) 53–73.CrossRefGoogle Scholar
5Borwein, P., Erdélyi, T. and Kós, G., ‘Littlewood-type problems on [0, 1]’, Proc. London Math. Soc. (3) 79 (1999) 22–46.CrossRefGoogle Scholar
6Borwein, P., Hare, K.G. and Mossinghoff, M.J., ‘The Mahler measure of polynomials with odd coefficients’, Bull. London Math. Soc., to appear.Google Scholar
7Borwein, P. and Mossinghoff, M.J., ‘Polynomials with height 1 and prescribed vanishing at 1’, Experiment. Math. 9 (2000) 425–433.CrossRefGoogle Scholar
8Borwein, P. and Mossinghoff, M.J., ‘Newman polynomials with prescribed vanishing and integer sets with distinct subset sums’, Math. Comp. 72 (2003) 787–800.CrossRefGoogle Scholar
9Boyd, D.W., ‘Reciprocal polynomials having small measure’, Math. Comp. 35 (1980) 1361–1377.CrossRefGoogle Scholar
10Boyd, D.W., ‘Reciprocal polynomials having small measure II’, Math. Comp. 53 (1989) 355–357, S1–S5.CrossRefGoogle Scholar
11Boyd, D.W., ‘On a problem of Byrnes concerning polynomials with restricted coefficients’, Math. Comp. 66 (1997) 1697–1703.CrossRefGoogle Scholar
12Boyd, D.W., ‘On a problem of Byrnes concerning polynomials with restricted coefficients II’, Math. Comp. 71 (2002) 1205–1217.CrossRefGoogle Scholar
13Boyd, D.W. and Montgomery, H.L., ‘Cyclotomic partitions’, Number theory (Banff, Alberta, 1988), (ed. Mollin, R.A., de Gruyter, Walter, Berlin, 1990) 7–25.Google Scholar
14Cohen, H., Lewin, L. and Zagier, D., ‘A sixteenth-order polylogarithm ladder’, Experiment. Math. 1 (1992) 25–34.Google Scholar
15Dubickas, A., ‘On the order of vanishing at 1 of a polynomial’, Lithuanian Math. J. 39 (1999) 365–370.CrossRefGoogle Scholar
16Dubickas, A., ‘Three problems for polynomials of small measure’, Acta Arith. 98 (2001) 279–292.CrossRefGoogle Scholar
17‘GMP: The GNU multiple precision arithmetic library’, http://www.swox.com/gmp.Google Scholar
18Lehmer, D.H., ‘Factorization of certain cyclotomic functions’, Ann. of Math. (2) 34 (1933) 461–479.CrossRefGoogle Scholar
19Lenstra, A.K., Lenstra, H.W. Jr. and Lovász, L., ‘Factoring polynomials withrational coefficients’, Math. Ann. 261 (1982) 515–534.CrossRefGoogle Scholar
20Mignotte, M., ‘Sur les multiples des polynômes irréductibles’, Bull. Soc. Math. Belg. 27(1975) 225–229.Google Scholar
21Mossinghoff, M.J., ‘Lehmer's problem’, http://www.cecm.sfu.ca/~mjm/Lehmer.Google Scholar
22Mossinghoff, M.J., ‘Polynomials with small Mahler measure’, Math. Comp. 67 (1998) 1697–1705, S11–S14.CrossRefGoogle Scholar
23Mossinghoff, M.J., Pinner, C.G. and Vaaler, J.D., ‘Perturbing polynomials with all their roots on the unit circle’, Math. Comp. 67(1998) 1707–1726.CrossRefGoogle Scholar
24Odlyzko, A.M. and Poonen, B., ‘Zeros of polynomials with 0, 1 coefficients’, Enseign. Math. (2) 39 (1993) 317–348.Google Scholar
25Pathiaux, M., ‘Sur les multiples de polyônmes irréductibles associés à certains nombres algébriques’, Séminaire Delange-Pisot-Poitou 14 (1972⁄73) 9 pp.Google Scholar
26Shoup, V., ‘NTL: a library for doing number theory‘, http://www.shoup.net/ntl.Google Scholar
27Silverman, J.H., ‘Exceptional units and numbers of small Mahler measure’, Experiment. Math. 4 (1995) 69–83.CrossRefGoogle Scholar
28Smyth, C.J., ‘On the product of the conjugates outside the unit circle of an algebraic integer’, Bull. London Math. Soc. 3 (1971) 169–175.CrossRefGoogle Scholar