Problem Statement
Let $\epsilon>0$. Is there some set $A\subset \mathbb{N}$ of density $>1-\epsilon$ such that $a_1\cdots a_r=b_1\cdots b_s$ with $a_i,b_j\in A$ can only hold when $r=s$?
Similarly, can one always find a set $A\subset\{1,\ldots,N\}$ with this property of size $\geq (1-o(1))N$?
Similarly, can one always find a set $A\subset\{1,\ldots,N\}$ with this property of size $\geq (1-o(1))N$?
Categories:
Number Theory
Progress
An example of such a set with density $1/4$ is given by the integers $\equiv 2\pmod{4}$.Selfridge constructed such a set with density $1/e-\epsilon$ for any $\epsilon>0$: let $p_1<\cdots<p_k$ be a sequence of large consecutive primes such that\[\sum_{i=1}^k\frac{1}{p_i}<1<\sum_{i=1}^{k+1}\frac{1}{p_i},\]and let $A$ be those integers divisible by exactly one of $p_1,\ldots,p_k$.
For the second question the set of integers with a prime factor $>N^{1/2}$ give an example of a set with size $\geq (\log 2)N$. Erdős could improve this constant slightly.
In [Er65] Erdős reports that Ruzsa proved the maximal size of such an $A$ is $\leq (1-c)N$ for some constant $c>0$ for large $N$, but the proof 'is not yet published'. As far as I know, no such proof was ever published.
See also [421] and [795].
Source: erdosproblems.com/786 | Last verified: January 16, 2026