A problem of Erdős and Surányi [ErSu59], who proved that $g(n) \geq (2-o(1))n$, and that $g(3)=4$. Their lower bound construction takes $A$ as the set of $p_ip_j$ for $i\neq j$, where $p_1<\cdots <p_\ell$ is some set of primes such that $2p_1^2>p_\ell^2$.

Gallai was the first to consider problems of this type, and observed that $g(2)=2$ and $g(3)\geq 4$.

In [Er92c] Erdős offers '100 dollars or 1000 rupees', whichever is more, for a proof or disproof. (In 1992 1000 rupees was worth approximately \$38.60.)

Erdős and Surányi similarly asked what is the smallest $c_n\geq 1$ such that in any interval $I\subset [0,\infty)$ of length $c_n\max(A)$ there exists some $B\subseteq I\cap \mathbb{N}$ with $\lvert B\rvert=n$ such that\[\prod_{a\in A} a \mid \prod_{b\in B}b.\]They prove $c_2=1$ and $c_3=\sqrt{2}$, but have no good upper or lower bounds in general.


See also [709].

View the LaTeX source