Logo
All Random Solved Random Open
OPEN
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}})?\]

Erdő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}.\] Surprisingly, if we consider the corresponding problem in the reals (so consider 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$) then Alexander proved that $\lvert A\rvert> x/8e$ is possible (disproving an earlier conjecture of Erdős [Er73] that $m=o(x)$). Alexander's construction seems to be unpublished, and I have no idea what it is.

See also [490], [793], and [796].

Additional thanks to: Rishika Agrawal