Erdős Problem #1 — Maximum size of sets with distinct subset sums

Erdős posed the question in 1931 or 1932: must every set with distinct subset sums and largest element $a_k$ have $a_k$ growing essentially like $2^k$? Equivalently, is $f(n)$ bounded above by $\frac{\log n}{\log 2}+O(1)$?

Known results

• Erdős and Moser proved $a_k\geq c2^k/\sqrt{k}$.
• Elkies sharpened this to $a_k\geq(\sqrt{2/\pi}-o(1))k^{-1/2}2^k$.
• Bohman constructed examples with $a_k\leq0.22002\,2^k$ in 1998.
• Exhaustive computation gives minimum largest element $309$ for $k=10$, with no asymptotic conclusion.

February 5, 2026 note

A note dated February 5, 2026, records the conjecture as Conjecture 1.3 and gives the best preceding estimate $|S(n)|<\log_2 n+\frac12\log_2\log_2 n-\log_2 c^*+o(1)$, with $c^*=\sqrt{2/\pi}$ attributed to Dubroff, Fox, and Xu. It reports neither a proof nor a disproof.

Current status (as of September 2026): The logarithmic upper bound remains open; the best recorded general lower bound retains a factor $k^{-1/2}$, and no counterexample is recorded.