Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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
Email: pborwein@cecm.sfu.ca

Michael J. Mossinghoff
Affiliation: Department of Mathematics, University of California, Los Angeles, Los Angeles, California 90095
Email: mjm@math.ucla.edu

DOI: http://dx.doi.org/10.1090/S0025-5718-02-01460-6
PII: S 0025-5718(02)01460-6
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