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 $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)?

Source: erdosproblems.com/543

Number theory
Group theory

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

Disproved: the site credits ChatGPT and Tang with the negative answer, which shows that along the primes $p$ a uniformly chosen $k$ -subset of $\mathbb{F}_p$ with $k=\log_2p+o(\log\log p)$ leaves some residue unreachable as a subset sum with probability tending to one, as Erdős had expected; the accepted claim page is Tang 2026, and Ma and Tang's quantitative sharpening is the pending claim Ma and Tang 2026.

Problem 543

Status

Proof claims

Discussion