Problem Statement
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)?\]
Categories:
Number Theory Group Theory
Progress
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.Source: erdosproblems.com/543 | Last verified: January 15, 2026