Erdős called this 'perhaps my first serious problem'. The powers of $2$ show that $2^n$ would be best possible here. The trivial lower bound is $N \gg 2^{n}/n$, since all $2^n$ distinct subset sums must lie in $[0,Nn)$. Erdős and Moser [Er56] proved \[ N\geq (\tfrac{1}{4}-o(1))\frac{2^n}{\sqrt{n}}.\] (In [Er85c] Erdős offered \$100 for any improvement of the constant $1/4$ here.)

A number of improvements of the constant have been given (see [St23] for a history), with the current record $\sqrt{2/\pi}$ first proved in unpublished work of Elkies and Gleason. Two proofs achieving this constant are provided by Dubroff, Fox, and Xu [DFX21], who in fact prove the exact bound $N\geq \binom{n}{\lfloor n/2\rfloor}$.

In [Er73] and [ErGr80] the generalisation where $A\subseteq (0,N]$ is a set of real numbers such that the subset sums all differ by at least $1$ is proposed, with the same conjectured bound. (The second proof of [DFX21] applies also to this generalisation.)

This problem appears in Erdős' book with Spencer [ErSp74] in the final chapter titled 'The kitchen sink'. As Ruzsa writes in [Ru99] "it is a rich kitchen where such things go to the sink".

The sequence of minimal $N$ for a given $n$ is A276661 in the OEIS.

See also [350].

Conjectured by Erdős and Turán. They also suggest the stronger conjecture that $\limsup 1_A\ast 1_A(n)/\log n>0$.

Another stronger conjecture would be that the hypothesis $\lvert A\cap [1,N]\rvert \gg N^{1/2}$ for all large $N$ suffices.

Erdős and Sárközy conjectured the stronger version that if $A=\{a_1<a_2<\cdots\}$ and $B=\{b_1<b_2<\cdots\}$ with $a_n/b_n\to 1$ are such that $A+B=\mathbb{N}$ then $\limsup 1_A\ast 1_B(n)=\infty$.

See also [40].

Conjectured by Erdős and Straus. Proved by Lorentz [Lo54].

Such a set is called an additive complement to the primes.

Erdős [Er54] proved that such a set $A$ exists with $\lvert A\cap\{1,\ldots,N\}\rvert\ll (\log N)^2$ (improving a previous result of Lorentz [Lo54] who achieved $\ll (\log N)^3$). Wolke [Wo96] has shown that such a bound is almost true, in that we can achieve $\ll (\log N)^{1+o(1)}$ if we only ask for almost all integers to be representable.

The answer to the third question is yes: Ruzsa [Ru98c] has shown that we must have \[\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{\log N}\geq e^\gamma\approx 1.781.\]

Erdős observed that this value is finite and $>1$.

Erdős [Er36c] proved this is true with $k$ replaced by $2k$ in the denominator (in a stronger form that only considers $A\cup (A+b)$ for some $b\in B$, see [38]).

Ruzsa has observed that this follows immediately from the stronger fact proved by Plünnecke [Pl70] that (under the same assumptions) \[d_S(A+B)\geq \alpha^{1-1/k}.\]

The minimum overlap problem. The example (with $N$ even) $A=\{N/2+1,\ldots,3N/2\}$ shows that $c\leq 1/2$ (indeed, Erdős initially conjectured that $c=1/2$). The lower bound of $c\geq 1/4$ is trivial, and Scherk improved this to $1-1/\sqrt{2}=0.29\cdots$. The current records are \[0.379005 < c < 0.380926\cdots,\] the lower bound due to White [Wh22] and the upper bound due to Haugland [Ha16].

The answer is no by Ruzsa [Ru87], who proved that if $A$ is an essential component then there exists some constant $c>0$ such that $\lvert A\cap \{1,\ldots,N\}\rvert \geq (\log N)^{1+c}$ for all large $N$.

Erdős [Er36c] proved that if $B$ is an additive basis of order $k$ then, for any set $A$ of Schnirelmann density $\alpha$, for every $N$ there exists some integer $b\in B$ such that \[\lvert (A\cup (A+b))\cap \{1,\ldots,N\}\rvert\geq \left(\alpha+\frac{\alpha(1-\alpha)}{2k}\right)N.\] It seems an interesting question (not one that Erdős appears to have asked directly, although see [35]) to improve the lower bound here, even in the case $B=\mathbb{N}$. Erdős observed that a random set of density $\alpha$ shows that the factor of $\frac{\alpha(1-\alpha)}{2}$ in this case cannot be improved past $\alpha(1-\alpha)$.

This is a stronger propery than $B$ being an essential component (see [37]). Linnik [Li42] gave the first construction of an essential component which is not an additive basis.

The trivial greedy construction achieves $\gg N^{1/3}$. The current best bound of $\gg N^{\sqrt{2}-1+o(1)}$ is due to Ruzsa [Ru98]. (Erdős [Er73] had offered \$25 for any construction which achieves $N^{c}$ for some $c>1/3$.) Erdős proved that for every infinite Sidon set $A$ we have \[\liminf \frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/2}}=0,\] and also that there is a set $A\subset \mathbb{N}$ with $\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}$ such that $1_A\ast 1_A(n)=O(1)$.

Erdős and Rényi have constructed, for any $\epsilon>0$, a set $A$ such that \[\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}\] for all large $N$ and $1_A\ast 1_A(n)\ll_\epsilon 1$ for all $n$.

A suitably constructed random set has this property if we are allowed to ignore an exceptional set of density zero. The challenge is obtaining this with no exceptional set. Erdős believed the answer should be no. Erdős and Sárkzözy proved that \[\frac{\lvert 1_A\ast 1_A(n)-\log n\rvert}{\sqrt{\log n}}\to 0\] is impossible. Erdős suggests it may even be true that the $\liminf$ and $\limsup$ of $1_A\ast 1_A(n)/\log n$ are always separated by some absolute constant.