Erdős [Er65] wrote it is 'not hard to prove' that\[k(n)\gg_\epsilon \exp((\log n)^{1/2-\epsilon})\]and it 'seems likely' that $k(n)=o(n^\epsilon)$, but had no non-trivial upper bound for $k(n)$.

It is not clear what he meant by a non-trivial bound for this problem, but Tao in the comments has given a simple argument proving $k(n) \leq (1+o(1))n^{1/2}$.

Tang has proved a lower bound of\[k(n)\geq \exp\left(\left(\frac{1}{\sqrt{2}}-o(1)\right)\sqrt{\log n\log\log n}\right).\]

View the LaTeX source

This page was last edited 30 December 2025.