Problem #796: Let $k\geq 2$ and let $g_k(n)$ be the largest possible size...

---

Progress

Erdős [Er64d] proved that if $2^{r-1}<k\leq 2^r$ then\[g_k(n) \sim \frac{(\log\log n)^{r-1}}{(r-1)!\log n}n\](which is the asymptotic count of those integers $\leq n$ with $r$ distinct prime factors).

In particular the asymptotics of $g_k(n)$ are known; in [Er69b] Erdős discussed the second order terms, and this question is implicit (especially when compared to the explicit question [425] he asked on several occasions).

In [Er69] this question actually appears with a denominator of $(\log n)^2$ in the second term. Furthermore, for $k=3$ he claims he could prove the existence of some $0<c_1\leq c_2$ such that\[\frac{\log\log n}{\log n}n+c_1\frac{n}{(\log n)^2}\leq g_3(n)\leq \frac{\log\log n}{\log n}n+c_2\frac{n}{(\log n)^2}.\]This is strange, since in [Er64d] both the upper and lower bound techniques that he used in fact prove\[\frac{\log\log n}{\log n}n+c_1\frac{n}{\log n}\leq g_3(n)\leq \frac{\log\log n}{\log n}n+c_2\frac{n}{\log n}\]for some constants $0<c_1\leq c_2$. My best guess is that the denominator of $(\log n)^2$ in [Er69] is just an unfortunate repeated typo, and $\log n$ was intended in both the reported bounds and the main question.

This correction is thanks to Tang, who noted independently (see the comments) the improved lower bound given above (indeed with an improvement in the constant $c_1$).

The special case $k=2$ is the subject of [425].