Investigated by Erdős and Freud. This has been discussed on MathOverflow, where LeechLattice shows \[h(N) \ll N^{2/3}.\] The observation of Zachary Hunter in that question coupled with the bounds of Kelley-Meka [KeMe23] imply that \[h(N) \gg \exp(c(\log N)^{1/12})\] for some $c>0$.

Erdős observed that $\lvert A\rvert \gg N^{1/3}$ is possible, taking the first $\approx N^{1/3}$ multiples of some prime $p\approx N^{2/3}$.

Essentially solved by Nguyen and Vu [NgVu10], who proved that $\lvert A\rvert\ll N^{1/3}(\log N)^{O(1)}$.

See also [438].

This question was asked by Erdős to a young Terence Tao in 1985. We thank Tao for sharing this memory and a letter of Erdős describing the problem.

A conjecture of Erdős and Graham, who proved the lower bound \[f(n)\geq \left(\frac{1}{2}+o(1)\right)\frac{n}{\log n}.\] Their proof is to note that we can assume that $m< \binom{n+1}{2}$ and then, for any $m$, take $S=\{ kp : 1\leq k<\frac{n}{p}\}$ where $p$ is the least prime that does not divide $m$ (so $p<(2+o(1))\log n$).

The complementary bound \[f(n) \leq \left(\frac{1}{2}+o(1)\right)\frac{n}{\log n}\] was proved by Alon and Freiman [AlFr88], who chose $m$ as the least common multiple of $\{1,\ldots,s\}$ where $s$ is maximal such that $m\leq \frac{n^2}{20(\log n)^2}$.