An Erdős problem on random subset sums in finite abelian groups

Abstract

Let $f(N)$ denote the least integer $k$ such that, if $G$ is an abelian group of order $N$ and $A\subseteq G$ is a uniformly random $k$-element subset, then with probability at least $\frac{1}{2}$ the subset-sum set $\{{\sum }_{x\in S}x:S\subseteq A\}$ equals $G$. In 1965, Erdős and Rényi proved that for all $N$, $$f(N)\le {\log }_{2}N+\left(\frac{1}{\log 2}+o(1)\right)\log \log N.$$ Erdős later conjectured that this bound cannot be improved to $f(N)\le {\log }_{2}N+o(\log \log N)$. In this paper we confirm this conjecture by showing that, for primes $p$, $$f(p)\ge {\log }_{2}p+\left(\frac{1}{2\log 2}+o(1)\right)\log \log p.$$

13 pages. This is the submitted version