Newman polynomials with prescribed vanishing and integer sets with distinct subset sums
Authors:
Peter Borwein and Michael J. Mossinghoff
Journal:
Math. Comp. 72 (2003), 787800
MSC (2000):
Primary 11C08, 11B75, 11P99; Secondary :, 05D99, 11Y55
Published electronically:
July 15, 2002
MathSciNet review:
1954968
Fulltext 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 ConwayGuy sequence yields the optimal solution for , extending some computations of Lunnon.
 1.
Tom
Bohman, A sum packing problem of Erdős
and the ConwayGuy sequence, Proc. Amer. Math.
Soc. 124 (1996), no. 12, 3627–3636. MR 1363448
(97b:11027), http://dx.doi.org/10.1090/S0002993996036532
 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
(98k:11014)
 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
(2001k:11036)
 4.
David
W. Boyd, On a problem of Byrnes concerning
polynomials with restricted coefficients, Math.
Comp. 66 (1997), no. 220, 1697–1703. MR 1433263
(98a:11033), http://dx.doi.org/10.1090/S0025571897008922
 5.
, On a problem of Byrnes concerning polynomials with restricted coefficients, II, Math. Comp. 71 (2002), 12051217.
 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
sumdistinct set of fixed order, J. Combin. Theory Ser. A
41 (1986), no. 1, 89–94. MR 826939
(87b:05012), http://dx.doi.org/10.1016/00973165(86)901160
 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
(86m:11097), http://dx.doi.org/10.1007/BF01388661
 9.
Richard
K. Guy, Unsolved problems in number theory, 2nd ed., Problem
Books in Mathematics, SpringerVerlag, New York, 1994. Unsolved Problems in
Intuitive Mathematics, I. MR 1299330
(96e:11002)
 10.
A.
F. Horadam, Jacobsthal representation numbers, Fibonacci
Quart. 34 (1996), no. 1, 40–54. MR 1371475
(96j:11027)
 11.
W.
F. Lunnon, Integer sets with distinct
subsetsums, Math. Comp.
50 (1988), no. 181, 297–320. MR 917837
(89a:11019), http://dx.doi.org/10.1090/S00255718198809178375
 12.
Roy
Maltby, Bigger and better subsetsumdistinct sets,
Mathematika 44 (1997), no. 1, 56–60. MR 1464377
(98i:11012), http://dx.doi.org/10.1112/S0025579300011979
 13.
Albert
Nijenhuis and Herbert
S. Wilf, Combinatorial algorithms, 2nd ed., Academic Press,
Inc. [Harcourt Brace Jovanovich, Publishers], New YorkLondon, 1978. For
computers and calculators; Computer Science and Applied Mathematics. MR 510047
(80a:68076)
 14.
A.
M. Odlyzko and B.
Poonen, Zeros of polynomials with 0,1 coefficients, Enseign.
Math. (2) 39 (1993), no. 34, 317–348. MR 1252071
(95b:11026)
 15.
R. Sedgewick, Algorithms in C++, Parts 14, 3rd ed., AddisonWesley, Reading, MA, 1998.
 1.
 T. Bohman, A sum packing problem of Erdos and the ConwayGuy sequence, Proc. Amer. Math. Soc. 124 (1996) 36273636. 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), 425433. MR 2001k:11036
 4.
 D. W. Boyd, On a problem of Byrnes concerning polynomials with restricted coefficients, Math. Comp. 66 (1997), 16971703. MR 98a:11033
 5.
 , On a problem of Byrnes concerning polynomials with restricted coefficients, II, Math. Comp. 71 (2002), 12051217.
 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 sumdistinct set of fixed order, J. Combin. Theory Ser. A 41 (1986), 8994. MR 87b:05012
 8.
 R. K. Guy, Sets of integers whose subsets have distinct sums, pp. 141154 in Theory and Practice of Combinatorics, edited by A. Rosa, G. Sabidussi, and J. Turgeon, Ann. of Discrete Math. 12, NorthHolland, Amsterdam, 1982. MR 86m:11097
 9.
 R. K. Guy, Unsolved Problems in Number Theory, 2nd ed., SpringerVerlag, New York, 1994. MR 96e:11002
 10.
 A. F. Horadam, Jacobsthal representation numbers, Fibonacci Quart. 34 (1996), 4054. MR 96j:11027
 11.
 W. F. Lunnon, Integer sets with distinct subsetsums, Math. Comp. 50 (1988), 297320. MR 89a:11019
 12.
 R. Maltby, Bigger and better subsetsumdistinct sets, Mathematika 44 (1997), 5660. 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), 317348. MR 95b:11026
 15.
 R. Sedgewick, Algorithms in C++, Parts 14, 3rd ed., AddisonWesley, Reading, MA, 1998.
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/S0025571802014606
PII:
S 00255718(02)014606
Keywords:
Newman polynomial; pure product; sumdistinct sets; ConwayGuy sequence
Received by editor(s):
July 23, 2001
Published electronically:
July 15, 2002
Article copyright:
© Copyright 2002
American Mathematical Society
