Erdős Problem #796

declared status 'open'. Formalized: no. Let $k\geq 2$ and let $g_k(n)$ be the largest possible size of $A\subseteq \{1,\ldots,n\}$ such that every $m$ has $<k$ solutions to $m=a_1a_2$ with $a_1<a_2\in A$. Is it true that$$g_3(n)=\frac{\log\log n}{\log n}n+(c+o(1))\frac{n}{(\log n)^2}$$for some constant $c$? Current best: Erd\H{o}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). For $k=3$ 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}.$$The special case $k=2$ is the subject of [425]. Prize: no. Tags: number theory.

Notation is rendered from the stored source. The pinned checkout remains the exact record.