Variations on the Erd\H{o}s distinct-sums problem

Abstract: Let

a_{1}, ..., a_{n}

be a set of positive integers with

a_{1} < d o t s < a_{n}

such that all

2^{n}

subset sums are distinct. A famous conjecture by ErdH{o}s states that

a_{n} > c c d o t 2^{n}

for some constant

c

, while the best result known to date is of the form

a_{n} > c c d o t 2^{n} / s q r t n

. In this paper, we weaken the condition by requiring that only sums corresponding to subsets of size smaller than or equal to

l a m b d a n

be distinct. For this case, we derive lower and upper bounds on the smallest possible value of

a_{n}

.

This page was built for publication: Variations on the Erd\H{o}s distinct-sums problem