Problem 425

Erdős Problem #425: declared status 'open'. Formalized: no. Let $F(n)$ be the maximum possible size of a subset $A\subseteq\{1,\ldots,N\}$ such that the products $ab$ are distinct for all $a<b$. Is there a constant $c$ such that$$F(n)=\pi(n)+(c+o(1))n^{3/4}(\log n)^{-3/2}?$$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}})?$$ Current best: Erd\H{o}s [Er68] proved that there exist some constants $0<c_1\leq c_2$ such that$$\pi(n)+c_1 n^{3/4}(\log n)^{-3/2}\leq F(n)\leq \pi(n)+c_2 n^{3/4}(\log n)^{-3/2}.$$This problem can also be considered in the real numbers: that is, what is the size of the the largest $A\subset [1,x]$ such that for any distinct $a,b,c,d\in A$ we have $\lvert ab-cd\rvert \geq 1$? Erd\H{o}s had conjectured (see [Er73] and [Er77c]) that $\lvert A\rvert=o(x)$. In [ErGr80] Erd\H{o}s and Graham report that Alexander had given a construction disproving this conjecture, establishing that $\lvert A\rvert\gg x$ is possible. Prize: no. Tags: number theory, sidon sets.