Proceedings of the American Mathematical Society

Author(s): Tom Bohman
Journal: Proc. Amer. Math. Soc. 124 (1996), 3627-3636.
MSC (1991): Primary 11P99; Secondary 05D10
Retrieve article in: PDF
This article is available free of charge

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}$ .

[AS]: N. Alon and J. Spencer, The Probabilistic Method, Wiley, New York, 1992. MR 93h:62002
[B]: T. Bohman, A Construction For Sets of Integers With Distinct Subset Sums, in preparation.
[CG]: J.H. Conway and R.K. Guy, Sets of natural numbers with distinct sums, Notices Amer. Math. Soc. 15(1968), 345.
[E1]: P. Erd\H{o}s, personal communication.
[E2]: P. Erd\H{o}s, Problems and results from additive number theory, Colloq. Théorie des Nombres, Bruxelles, 1955, Liège & Paris, 1956, 127-137, esp. p. 137. MR 18:18a
[G1]: R. K. Guy, Sets of integers whose subsets have distinct sums, Theory and Practice of Combinatorics (A. Kotzig 60th Birthday Vol.), Ann. of Discrete Math., vol. 12, North-Holland, Amsterdam, 1982, pp. 141-154. MR 86m:11009
[G2]: R. K. Guy, Unsolved Problems in Number Theory, 2nd ed., Springer-Verlag, New York, 1994. CMP 95:02
[L]: W. F. Lunnon, Integer sets with distinct subset sums, Math. Comp., 50(1988) 297-320. MR 89a:11019

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

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: 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
Copyright of article: Copyright 1996, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6826 (e) ISSN 0002-9939 (p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS