Erdős Problem #543 — 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…

Erdős and Rényi established the original upper bound in 1965; Erdős conjectured in 1973 that its double-logarithmic error term could not be reduced to a smaller-order term. The problem is now answered negatively using additive groups of prime order.

Known results

• Erdős and Rényi, 1965: $f(N)\leq\log_2N+\frac{1}{\log 2}\log\log N+O(1)$ for finite abelian groups.
• Erdős and Hall: the stronger bound $f(N)\leq\log_2N+o(\log\log\log N)$ is false.

February 2026 negative resolution

The paper proves that for every fixed $0<c<\frac{1}{2\log 2}$, random subsets of $\mathbb{F}_p$ of size $\lfloor\log_2p+c\log\log p\rfloor$ fail to cover all subset sums with probability tending to $1$. Hence $f(p)\geq\log_2p+\left(\frac{1}{2\log 2}+o(1)\right)\log\log p$, disproving the proposed universal bound. ChatGPT-5.2 Pro supplied the initial qualitative proof idea; the authors repaired it and developed the quantitative refinement.

Current status (as of February 2026): The proposed universal bound is false, with a quantitative obstruction proved for prime-order groups; the exact threshold and behavior for other group families remain open.