Back to Search Start Over

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

Authors :
Costa, Simone
Dalai, Marco
Della Fiore, Stefano
Publication Year :
2021

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\H{o}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/\sqrt{n}$. In this paper, we weaken the condition by requiring that only sums corresponding to subsets of size smaller than or equal to $\lambda n$ be distinct. For this case, we derive lower and upper bounds on the smallest possible value of $a_n$.

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2107.07885
Document Type :
Working Paper