Logo
All Random Solved Random Open
SOLVED
Let $g(n)$ be the maximal size of $A\subseteq \{1,\ldots,n\}$ such that $\prod_{n\in S}n$ are distinct for all $S\subseteq A$. Is it true that \[g(n) \leq \pi(n)+\pi(n^{1/2})+o\left(\frac{x^{1/2}}{\log n}\right)?\]
Erdős proved [Er66] \[g(n) \leq \pi(n)+O\left(\frac{x^{1/2}}{\log n}\right).\] This upper bound would be essentially best possible, since one could take $A$ to be all primes and squares of primes.

This was solved by Raghavan [Ra25], who proved that \[g(n) \leq \pi(n)+\pi(n^{1/2})+O(n^{5/12+o(1)}),\] and also that \[g(n) \geq \pi(n)+\pi(n^{1/2})+\pi(n^{1/3})/3-O(1).\]

Additional thanks to: Rishika Agrawal and Ryan Alweiss