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

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?)

  • 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 $1$ and prescribed vanishing at $1$, 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 $0,1$ 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.

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

American Mathematical Society