Problem Statement
Let $g(n)$ be the maximal size of $A\subseteq \{1,\ldots,n\}$ such that the products $\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)?\]
Categories:
Number Theory
Progress
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).\]See also [786].
Source: erdosproblems.com/795 | Last verified: January 16, 2026