Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Newman polynomials with prescribed vanishing and integer sets with distinct subset sums

Authors: Peter Borwein and Michael J. Mossinghoff
Journal: Math. Comp. 72 (2003), 787-800
MSC (2000): Primary 11C08, 11B75, 11P99; Secondary :, 05D99, 11Y55
Published electronically: July 15, 2002
MathSciNet review: 1954968
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We study the problem of determining the minimal degree $d(m)$ of a polynomial that has all coefficients in $\{0,1\}$ and a zero of multiplicity $m$ at $-1$. We show that a greedy solution is optimal precisely when $m\leq5$, mirroring a result of Boyd on polynomials with $\pm1$ coefficients. We then examine polynomials of the form $\prod_{e\in E} (x^e+1)$, where $E$is a set of $m$ positive odd integers with distinct subset sums, and we develop algorithms to determine the minimal degree of such a polynomial. We determine that $d(m)$ satisfies inequalities of the form $2^m + c_1 m \leq d(m) \leq \frac{103}{96}\cdot2^m + c_2$. Last, we consider the related problem of finding a set of $m$ positive integers with distinct subset sums and minimal largest element and show that the Conway-Guy sequence yields the optimal solution for $m\leq9$, extending some computations of Lunnon.

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

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11C08, 11B75, 11P99, :, 05D99, 11Y55

Retrieve articles in all journals with MSC (2000): 11C08, 11B75, 11P99, :, 05D99, 11Y55

Additional Information

Peter Borwein
Affiliation: Department of Mathematics and Statistics, Simon Fraser University, Burnaby, British Columbia, Canada V5A 1S6

Michael J. Mossinghoff
Affiliation: Department of Mathematics, University of California, Los Angeles, Los Angeles, California 90095

Keywords: Newman polynomial; pure product; sum-distinct sets; Conway-Guy sequence
Received by editor(s): July 23, 2001
Published electronically: July 15, 2002
Article copyright: © Copyright 2002 American Mathematical Society