Problem Statement
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}})?\]
Categories:
Number Theory Sidon Sets
Progress
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}.\]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ős had conjectured (see [Er73] and [Er77c]) that $\lvert A\rvert=o(x)$.In [ErGr80] Erdős and Graham report that Alexander had given a construction disproving this conjecture, establishing that $\lvert A\rvert\gg x$ is possible. Alexander's construction is given in [Er80], and we sketch a simplified version. Let $B\subseteq [1,X^2]$ be a Sidon set of integers of size $\gg X$ and\[A=\{ X e^{b/X^2} : b\in B\}.\]It is easy to check that\[\lvert ab-cd\rvert \geq X^2\lvert 1-e^{1/X^2}\rvert \gg 1\]for distinct $a,b,c,d\in A$, and (after rescaling $A$ by some constant factor) this produces a set of size $\gg X$ with the desired property in the interval $[X,O(X)]$. Furthermore, a simple modification allows for $A$ to also be $1$-separated.
In [Er77c] Erdős considers a similar generalisation for sets of complex numbers or complex integers.
See also [490], [793], and [796].
Source: erdosproblems.com/425 | Last verified: January 15, 2026