Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)

 

A sum packing problem of Erd\H{o}s
and the Conway-Guy sequence


Author: Tom Bohman
Journal: Proc. Amer. Math. Soc. 124 (1996), 3627-3636
MSC (1991): Primary 11P99; Secondary 05D10
MathSciNet review: 1363448
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A set \begin{math}S\end{math} of positive integers has distinct subset sums if the set \begin{math}\left \{ \sum _{x \in X} x : X \subset S \right \} \end{math} has \begin{math}2^{|S|}\end{math} distinct elements. Let

\begin{displaymath}f(n) = \min \{ \max S: |S|=n % \hskip 2mm \text {and} \hskip 2mm S % \hskip 2mm \text {has\hskip 2mm distinct\hskip 2mm subset \hskip 2mm sums}\}. \end{displaymath}

In 1931 Paul Erd\H{o}s conjectured that \begin{math}f(n) \ge c2^{n}\end{math} for some constant \begin{math}c\end{math}. In 1967 John Conway and Richard Guy constructed an interesting sequence of sets of integers. They conjectured that these sets have distinct subset sums and that they are close to the best possible (with respect to largest element). We prove that sets from this sequence have distinct subset sums. We also present some variations of this construction that give microscopic improvements in the best known upper bound on \begin{math}f(n)\end{math}.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (1991): 11P99, 05D10

Retrieve articles in all journals with MSC (1991): 11P99, 05D10


Additional Information

Tom Bohman
Affiliation: Department of Mathematics, Rutgers University, New Brunswick, New Jersey 08903
Address at time of publication: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Email: bohman@math.rutgers.edu

DOI: http://dx.doi.org/10.1090/S0002-9939-96-03653-2
PII: S 0002-9939(96)03653-2
Received by editor(s): June 6, 1995
Communicated by: Jeffry N. Kahn
Article copyright: © Copyright 1996 American Mathematical Society