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].
An alternative, simpler, proof was given by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22], who improved the upper bound on the smallest modulus to $616000$.
The best known lower bound is a covering system whose minimum modulus is $42$, due to Owens [Ow14].
Hough and Nielsen [HoNi19] proved that at least one modulus must be divisible by either $2$ or $3$. A simpler proof of this fact was provided by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22].
Selfridge has shown (as reported in [Sc67]) that such a covering system exists if a covering system exists with moduli $n_1,\ldots,n_k$ such that no $n_i$ divides any other $n_j$ (but the latter has been shown not to exist, see [586]).
Is it true that \[\sum_{n\in A}\frac{1}{n}<\infty?\]
An example of an $A$ with this property where \[\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}\log N>0\] is given by the set of $p^2$, where $p\equiv 3\pmod{4}$ is prime.
Elsholtz and Planitzer [ElPl17] have constructed such an $A$ with \[\lvert A\cap\{1,\ldots,N\}\rvert\gg \frac{N^{1/2}}{(\log N)^{1/2}(\log\log N)^2(\log\log\log N)^2}.\]
Schoen [Sc01] proved that if all elements in $A$ are pairwise coprime then \[\lvert A\cap\{1,\ldots,N\}\rvert \ll N^{2/3}\] for infinitely many $N$. Baier [Ba04] has improved this to $\ll N^{2/3}/\log N$.
For the finite version see [13].
For the infinite version see [12].
In [Er92c] Erdős asks about the general version where $a\nmid (b_1+\cdots+b_r)$ for $a<\min(b_1,\ldots,b_r)$, and whether $\lvert A\rvert \leq N/(r+1)+O(1)$.
In [Er81] offered \$1000 for a proof or disproof even just in the special case when $k=3$, which he expected 'contains the whole difficulty'. He also wrote 'I really do not see why this question is so difficult'.
The usual focus is on the regime where $k=O(1)$ is fixed (say $k=3$) and $n$ is large, although for the opposite regime Kostochka, Rödl, and Talysheva [KRT99] have shown \[f(n,k)=(1+O_n(k^{-1/2^n}))k^n.\]
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].
Can the bound $O(\log N)$ be achieved? Must such an $A$ satisfy \[\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{\log N}> 1?\]
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.\]
Can a lacunary set $A\subset\mathbb{N}$ be an essential component?
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$.
Erdős later asked ([Er92b] and [Er95]) if the conjecture remains true provided $N\geq (1+o(1))p_k^2$ (or, in a weaker form, whether it is true for $N$ sufficiently large depending on $k$).
See also [534].
In [Er81] it is further conjectured that \[\max_{md\leq x}\left\lvert \sum_{1\leq k\leq m}f(kd)\right\rvert \gg \log x.\]
In [Er85c] Erdős also asks about the special case when $f$ is multiplicative.
See also [3].
In [Er73] mentions an unpublished proof of Haight that \[\lim \frac{\lvert A\cap [1,x]\rvert}{x}=0\] holds if the elements of $A$ are independent over $\mathbb{Q}$.
See also [858].
The answer is yes, which is a corollary of the density Hales-Jewett theorem, proved by Furstenberg and Katznelson [FuKa91].
See also [789].
These bounds were improved by Croot [Cr03b] who proved \[\frac{N}{L(N)^{\sqrt{2}+o(1)}}< f(N)<\frac{N}{L(N)^{1/6-o(1)}},\] where $f(N)=\exp(\sqrt{\log N\log\log N})$. These bounds were further improved by Chen [Ch05] and then by de la Bretéche, Ford, and Vandehey [BFV13] to \[\frac{N}{L(N)^{1+o(1)}}<f(N) < \frac{N}{L(N)^{\sqrt{3}/2+o(1)}}.\] The latter authors conjecture that the lower bound here is the truth.
In [Ru01] Ruzsa constructs an asymptotically best possible answer to this question (a so-called 'exact additive complement'); that is, there is such a set $A$ with \[\lvert A\cap\{1,\ldots,N\}\rvert \sim \frac{N}{\log_2N}\] as $N\to \infty$.
More generally, Bose and Chowla conjectured that the maximum size of $A\subseteq \{1,\ldots,N\}$ with all $r$-fold sums distinct (aside from the trivial coincidences) then \[\lvert A\rvert \sim N^{1/r}.\] This is known only for $r=2$ (see [30]).
If we further ask that $\lvert S\rvert=l$ (for any fixed $l$) then is the number of solutions \[\ll \frac{2^N}{N^2},\] with the implied constant independent of $l$ and $t$?
The second question was answered in the affirmative by Halász [Ha77], as a consequence of a more general multi-dimensional result.
Grimm proved that this is true if $k\ll \log n/\log\log n$. Erdős and Selfridge improved this to $k\leq (1+o(1))\log n$. Ramachandra, Shorey, and Tijdeman [RST75] have improved this to \[k\ll\left(\frac{\log n}{\log\log n}\right)^3.\]
Proved for all sufficiently large sets (including the sharper version which characterises the case of equality) independently by Szegedy [Sz86] and Zaharescu [Za87].
Proved for all sets by Balasubramanian and Soundararajan [BaSo96].
If $A\subseteq \{1,\ldots,n\}$ is such that all products $a_1\cdots a_r$ are distinct for $a_1<\cdots <a_r$ then is it true that \[\lvert A\rvert \leq \pi(n)+O(n^{\frac{r+1}{2r}})?\]
Is it attained by choosing all integers in $[1,(N/2)^{1/2}]$ together with all even integers in $[(N/2)^{1/2},(2N)^{1/2}]$?
This has been proved for $t\leq 12$ (see Costa and Pellegrini [CoPe20] and the references therein) and for $p-3\leq t\leq p-1$ (see Hicks, Ollis, and Schmitt [HOS19] and the references therein). Kravitz [Kr24] has proved this for \[t \leq \frac{\log p}{\log\log p}.\] (This was independently earlier observed by Will Sawin in a MathOverflow post.)
Bedert and Kravitz [BeKr24] have now proved this conjecture for \[t \leq e^{(\log p)^{1/4}}.\]
This is true, and was proved by Szemerédi [Sz76].
In [Er72] Erdős goes on to ask whether \[\lim \frac{\lvert A\rvert\lvert B\rvert\log N}{N^2}\] exists, and to determine its value.
In particular, is it true that $\ell(N)\sim N^{1/2}$?
In [AlEr85] Alon and Erdős make the stronger conjecture that perhaps $A$ can always be written as the union of at most $(1+o(1))N^{1/2}$ many Sidon sets. (This is easily verified for $A=\{1,\ldots,N\}$ using standard constructions of Sidon sets.)
Erdős and Spencer [ErSp89] proved that \[F(k) \geq 2^{ck^2/\log k}\] for some constant $c>0$. Balogh, Eberhrad, Narayanan, Treglown, and Wagner [BENTW17] have improved this to \[F(k) \geq 2^{2^{k-1}/k}.\]
Ahlswede and Khachatrian [AhKh96] observe that it is 'easy' to find a counterexample to this conjecture, which they informed Erdős about in 1992. Erdős then gave a refined conjecture, that if $N=q_1^{k_1}\cdots q_r^{k_r}$ (where $q_1<\cdots <q_r$ are distinct primes) then the maximum is achieved by, for some $1\leq j\leq r$, those integers in $[1,N]$ which are a multiple of at least one of \[\{2q_1,\ldots,2q_j,q_1\cdots q_j\}.\] This conjecture was proved by Ahlswede and Khachatrian [AhKh96].
See also [56].
Erdős writes this is 'intimately connected' with the sunflower problem [20]. Indeed, the conjectured upper bound would follow from the following stronger version of the sunflower problem: estimate the size of the largest set of integers $A$ such that $\omega(n)=k$ for all $n\in A$ and there does not exist $a_1,\ldots,a_r\in A$ and an integer $d$ such that $(a_i,a_j)=d$ for all $i\neq j$ and $(a_i/d,d)=1$ for all $i$. The conjectured upper bound for $f_r(N)$ would follow if the size of such an $A$ must be at most $c_r^k$. The original sunflower proof of Erdős and Rado gives the upper bound $c_r^kk!$.
See also [536].
Erdős describes a construction of Ruzsa which disproves this: consider the set of all squarefree numbers of the shape $p_1\cdots p_r$ where $p_{i+1}>2p_i$ for $1\leq i<r$. This set has positive density, and hence if $A$ is its intersection with $(N/2,N)$ then $\lvert A\rvert \gg N$ for all large $N$. Suppose now that $p_1a_1=p_2a_2=p_3a_3$ where $a_i\in A$ and $p_1,p_2,p_3$ are distinct primes. Without loss of generality we may assume that $a_2>a_3$ and hence $p_2<p_3$, and so since $p_2p_3\mid a_1\in A$ we must have $2<p_3/p_2$. On the other hand $p_3/p_2=a_2/a_3\in (1,2)$, a contradiction.
Resolved by Schinzel and Szekeres [ScSz59] who proved the answer to the first question is yes and the answer to the second is no, and in fact there are examples with at most $n/(\log n)^c$ many such $m$, for some constant $c>0$.
Chen [Ch96] has proved that if $n>172509$ then \[\sum_{a\in A}\frac{1}{a}< \frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{7}+\frac{1}{11}.\]
In [Er73] Erdős further speculates that in fact \[\sum_{a\in A}\frac{1}{a}\leq 1+o(1),\] where the $o(1)$ term $\to 0$ as $n\to \infty$.
See also [784].
In [Er73] Erdős says it is not even known in $\mathbb{R}$ whether $f(n)\to \infty$. Sarosh Adenwalla has observed that this is equivalent to minimising the number of distinct differences in a set $A\subset \mathbb{R}$ of size $n$ without three-term arithmetic progressions. Dumitrescu [Du08] proved that, in these terms, \[(\log n)^c \leq f(n) \leq 2^{O(\sqrt{\log n})}\] for some constant $c>0$.
Straus has observed that if $2^k\geq n$ then there exist $n$ points in $\mathbb{R}^k$ which contain no isosceles triangle and determine at most $n-1$ distances.
See also [656].
What choice of such an $A$ minimises the number of integers $m\leq n$ not divisible by any $a\in A$? Is this minimised by letting $n\geq q_1>q_2>\cdots$ be the consecutive primes in decreasing order and choosing $A=\{q_1,\ldots,q_k\}$ where $k$ is maximal such that \[\sum_{i=1}^k\frac{1}{q_i}\leq C?\]
The answer is yes, proved by Sárközy and Szemerédi [SaSz94]. Ruzsa [Ru17] has constructed, for any function $w(x)\to \infty$, such a pair of sets with \[A(x)B(x)-x<w(x)\] for infinitely many $x$.
Similarly, can one always find a set $A\subset\{1,\ldots,N\}$ with this property of size $\geq (1-o(1))N$?
Selfridge constructed such a set with density $1/e-\epsilon$ for any $\epsilon>0$: let $p_1<\cdots<p_k$ be a sequence of large consecutive primes such that \[\sum_{i=1}^k\frac{1}{p_i}<1<\sum_{i=1}^{k+1}\frac{1}{p_i},\] and let $A$ be those integers divisible by exactly one of $p_1,\ldots,p_k$.
For the second question the set of integers with a prime factor $>N^{1/2}$ give an example of a set with size $\geq (\log 2)N$. Erdős could improve this constant slightly.
Estimate $g(n)$.
Estimate $f(n)$. In particular is it true that $f(n)\leq n^{1/2+o(1)}$?
Estimate $h(n)$.
Estimate $l(n)$. In particular, is it true that $l(n)n^{-1/2}\to \infty$? Is it true that $l(n)< n^{1-c}$ for some $c>0$?
See also [876].