PROVED
This has been solved in the affirmative.
Let $0<\epsilon<1$ and let $g_\epsilon(N)$ be the minimal $k$ such that if $G$ is an abelian group of size $N$ and $A\subseteq G$ is a uniformly random subset of size $k$, and\[F_A(g) = \#\left\{ S\subseteq A : g = \sum_{x\in S}x\right\},\]then, with probability $\to 1$ as $N\to \infty$,\[\left\lvert F_A(g)-\frac{2^k}{N}\right\rvert \leq \epsilon \frac{2^k}{N}\]for all $g\in G$.
Estimate $g_\epsilon(N)$ - in particular, is it true that for all $\epsilon>0$\[g_\epsilon(N)=(1+o_\epsilon(1))\log_2N?\]
It is trivial that $g_\epsilon(N)\geq \log_2N$ for all $0<\epsilon<1$. Erdős and Rényi
[ErRe65] proved that for all $0<\epsilon<1$\[g_\epsilon(N) \leq (2+o(1))\log_2N+O_\epsilon(1).\]Erdős and Hall
[ErHa76] proved that, for all $0<\epsilon<1$,\[g_\epsilon(N)\leq \left(1+O_\epsilon\left(\frac{\log\log\log N}{\log\log N}\right)\right)\log_2N.\]See also
[543].
View the LaTeX source
This page was last edited 26 January 2026.
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 #1179, https://www.erdosproblems.com/1179, accessed 2026-03-01
