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

DOI:
https://doi.org/10.1090/S0025-5718-02-01460-6

Published electronically:
July 15, 2002

MathSciNet review:
1954968

Full-text PDF

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.**T. Bohman,*A sum packing problem of Erdos and the Conway-Guy sequence*, Proc. Amer. Math. Soc.**124**(1996) 3627-3636. MR**97b:11027****2.**-,*A construction for sets of integers with distinct subset sums*, Electron. J. Combin.**5**(1998), Research Paper 3, 14 pp. (electronic). MR**98k:11014****3.**P. Borwein and M. J. Mossinghoff,*Polynomials with height and prescribed vanishing at*, Experiment. Math.**9**(2000), 425-433. MR**2001k:11036****4.**D. W. Boyd,*On a problem of Byrnes concerning polynomials with restricted coefficients*, Math. Comp.**66**(1997), 1697-1703. MR**98a:11033****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.**N. 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), 89-94. MR**87b:05012****8.**R. K. Guy,*Sets of integers whose subsets have distinct sums*, pp. 141-154 in*Theory and Practice of Combinatorics*, edited by A. Rosa, G. Sabidussi, and J. Turgeon, Ann. of Discrete Math.**12**, North-Holland, Amsterdam, 1982. MR**86m:11097****9.**R. K. Guy,*Unsolved Problems in Number Theory*, 2nd ed., Springer-Verlag, New York, 1994. MR**96e:11002****10.**A. F. Horadam,*Jacobsthal representation numbers*, Fibonacci Quart.**34**(1996), 40-54. MR**96j:11027****11.**W. F. Lunnon,*Integer sets with distinct subset-sums*, Math. Comp.**50**(1988), 297-320. MR**89a:11019****12.**R. Maltby,*Bigger and better subset-sum-distinct sets*, Mathematika**44**(1997), 56-60. MR**98i:11012****13.**A. Nijenhuis and H. S. Wilf,*Combinatorial Algorithms*, Academic Press, Orlando, 1978. MR**80a:68076****14.**A. M. Odlyzko and B. Poonen,*Zeros of polynomials with coefficients*, Enseign. Math. (2)**39**(1993), 317-348. MR**95b:11026****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:
https://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