Variations on the Erdős distinct-sums problem

Simone Costa; Marco Dalai; Stefano Della Fiore

paper

Variations on the Erdős distinct-sums problem

arXiv:2107.07885

Abstract

Let ${a_{1}, ..., a_{n}}$ be a set of positive integers with $a_{1} < \dots < a_{n}$ such that all $2^{n}$ subset sums are distinct. A famous conjecture by Erdős states that $a_{n} > c \cdot 2^{n}$ for some constant $c$ , while the best result known to date is of the form $a_{n} > c \cdot 2^{n} / n$ . In this paper, we weaken the condition by requiring that only sums corresponding to subsets of size smaller than or equal to $λn$ be distinct. For this case, we derive lower and upper bounds on the smallest possible value of $a_{n}$ .