Sets with distinct subset sums

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

A finite set $S\subseteq\mathbb N$ has distinct subset sums if the function $T\mapsto\sum_{s\in T}s$ on $\mathcal P(S)$ is injective; the empty sum is zero. For $m\ge1$, put \[ f(m)=\min\{\max S:S\subseteq\mathbb N,\ |S|=m,\ S\text{ has distinct subset sums}\}. \]

Statement recorded in the supplied source.

Is there an absolute constant $C\in\mathbb R$ such that, for every $N\ge1$ and every sum-distinct $S\subseteq\{1,\ldots,N\}$, \[ |S|\le\log_2 N+C? \] Equivalently, is there a constant $c>0$ with $f(m)\ge c2^m$ for all $m\ge1$? More generally, determine the asymptotic behavior of $f(m)$. [S2]

Short English statement

Bound the size of a sum-distinct set by the binary logarithm of its largest permitted element plus an absolute constant, and determine the corresponding minimum-largest-element function.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3379 (OPG-414). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Sets with distinct subset sums, OPG-414. Original problem statement, full mathematical discussion, bibliography and comments. https://www.openproblemgarden.org/op/sets_with_distinct_subset_sums.