Problem 1179

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?

Source: erdosproblems.com/1179

Additive combinatorics
Probability

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved, the site's label (PROVED). The site's commentary gives the trivial lower bound $g_\epsilon(N)\ge\log_2N$ , the Erdős–Rényi bound $(2+o(1))\log_2N+O_\epsilon(1)$ and the Erdős–Hall bound $(1+O_\epsilon(\log\log\log N/\log\log N))\log_2N$ . The standing is derived from the claim pages: the accepted full claim is the Theorem of Erdős and Hall [ErHa76], on its claim page (Erdős and Hall, 1976), accepted on the refereed publication and the site's label; the paper samples the $k$ elements with repetition where the problem takes a random $k$ -subset, a difference the claim page bridges.

Er73: Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (J. N. Srivastava et al., eds.), North-Holland (1973), 117-138; p. 127. Library home: Erdos 1973.
ErHa76: Erdős, P. and Hall, R. R., Probabilistic methods in group theory. II. Houston J. Math. 2 (1976), no. 2, 173-180. Library home: Erdős and Hall 1976.
ErRe65: Erdős, P. and Rényi, A., Probabilistic methods in group theory. J. Analyse Math. 14 (1965), 127-138. Library home: Erdős and Rényi 1965.

Problem 1179

Status

Proof claims

Discussion