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 of a polynomial that has all coefficients in and a zero of multiplicity at . We show that a greedy solution is optimal precisely when , mirroring a result of Boyd on polynomials with coefficients. We then examine polynomials of the form , where is a set of positive odd integers with distinct subset sums, and we develop algorithms to determine the minimal degree of such a polynomial. We determine that satisfies inequalities of the form . Last, we consider the related problem of finding a set of positive integers with distinct subset sums and minimal largest element and show that the Conway-Guy sequence yields the optimal solution for , extending some computations of Lunnon.

**1.**Tom Bohman,*A sum packing problem of Erdős and the Conway-Guy sequence*, Proc. Amer. Math. Soc.**124**(1996), no. 12, 3627–3636. MR**1363448**, 10.1090/S0002-9939-96-03653-2**2.**Tom Bohman,*A construction for sets of integers with distinct subset sums*, Electron. J. Combin.**5**(1998), Research Paper 3, 14 pp. (electronic). MR**1486396****3.**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****4.**David W. Boyd,*On a problem of Byrnes concerning polynomials with restricted coefficients*, Math. Comp.**66**(1997), no. 220, 1697–1703. MR**1433263**, 10.1090/S0025-5718-97-00892-2**5.**-,*On a problem of Byrnes concerning polynomials with restricted coefficients, II*, Math. Comp.**71**(2002), 1205-1217.**6.**J. H. Conway and R. K. Guy,*Solution of a problem of P. Erdos*, Colloq. Math.**20**(1969), 307.**7.**Noam D. Elkies,*An improved lower bound on the greatest element of a sum-distinct set of fixed order*, J. Combin. Theory Ser. A**41**(1986), no. 1, 89–94. MR**826939**, 10.1016/0097-3165(86)90116-0**8.**Haruzo Hida,*A 𝑝-adic measure attached to the zeta functions associated with two elliptic modular forms. I*, Invent. Math.**79**(1985), no. 1, 159–195. MR**774534**, 10.1007/BF01388661**9.**Richard K. Guy,*Unsolved problems in number theory*, 2nd ed., Problem Books in Mathematics, Springer-Verlag, New York, 1994. Unsolved Problems in Intuitive Mathematics, I. MR**1299330****10.**A. F. Horadam,*Jacobsthal representation numbers*, Fibonacci Quart.**34**(1996), no. 1, 40–54. MR**1371475****11.**W. F. Lunnon,*Integer sets with distinct subset-sums*, Math. Comp.**50**(1988), no. 181, 297–320. MR**917837**, 10.1090/S0025-5718-1988-0917837-5**12.**Roy Maltby,*Bigger and better subset-sum-distinct sets*, Mathematika**44**(1997), no. 1, 56–60. MR**1464377**, 10.1112/S0025579300011979**13.**Albert Nijenhuis and Herbert S. Wilf,*Combinatorial algorithms*, 2nd ed., Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1978. For computers and calculators; Computer Science and Applied Mathematics. MR**510047****14.**A. M. Odlyzko and B. Poonen,*Zeros of polynomials with 0,1 coefficients*, Enseign. Math. (2)**39**(1993), no. 3-4, 317–348. MR**1252071****15.**R. Sedgewick,*Algorithms in C++, Parts 1-4*, 3rd ed., Addison-Wesley, Reading, MA, 1998.

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

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