OPEN
This is open, and cannot be resolved with a finite computation.
Define $f(N)$ be the minimal $k$ such that the following holds: if $G$ is an abelian group of size $N$ and $A\subseteq G$ is a random set of size $k$ then, with probability $\geq 1/2$, all elements of $G$ can be written as $\sum_{x\in S}x$ for some $S\subseteq A$. Is\[f(N) \leq \log_2 N+o(\log\log N)?\]
Erdős and Rényi
[ErRe65] proved that\[f(N) \leq \log_2N+O(\log\log N).\]Erdős believed improving this to $o(\log\log N)$ is impossible.
View the LaTeX source
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #543, https://www.erdosproblems.com/543, accessed 2026-01-16
